COMP9334
Capacity Planning for Computer Systems and Networks
Week 8A: Web services and fork-join queues
COMP9334
1
This lecture
• Web services • Whatisit?
• Performanceanalysis
• Fork-join queue • Markovchain
• MVA
T1,2021 COMP9334 2
Web access versus Web services
(a) Web access
(b) Composite web service for travel
T1,2021 COMP9334 3
Web service performance issues
• Metrics
• Responsetime
• Throughput • Availability
• Performance analysis method • Operationalanalysis
• Markovchain
T1,2021 COMP9334 4
Web service flow graph
Va,Vh,Vc: Relative Visit Ratio
T1,2021 COMP9334 5
Every request to the travel site generates on average Va requests to the Airline web service etc.
T1,2021 COMP9334 6
Similarly,
Xh = Throughput of hotel web service
Xc = Throughput of car rental web service
• Can you find an upper bound on the throughput of the travel site
T1,2021 COMP9334 7
Example:
Xa = 20 requests/s Xh = 15 requests/s Xc = 10 requests/s Va = 4, Vh = 2, Vc = 1
The airline web service is the bottleneck of the travel web site.
T1,2021 COMP9334 8
More complex web service graphs
What is the bound on throughput of web service A?
T1,2021 COMP9334 9
Bound on the throughput of web service A is:
T1,2021 COMP9334 10
Response time analysis
• The bottleneck analysis only gives an upper bound on the throughput
• Can we find the response time? • Markovchain
• ApproximateMVA
• We begin with a motivating example
T1,2021 COMP9334 11
A simple web service scenario (1)
Web service 1
User request
Reply to user
composite web service
Request 1
Reply 1 Reply 2
Request 2
• •
A composite web service uses two web services Sequence of events
1. Composite web service receives a user request
2. Composite web service sends Request 1 and Request 2
3. The web services reply independently
• That is, Reply 1 and Reply 2 may arrive at different times
4. After the composite web service receives both replies, it responds to the user
T1,2021 COMP9334 12
Web service 2
A simple web service scenario (2)
Web service 1
User request
Reply to user
composite web service
Request 1
Reply 1 Reply 2
Request 2
• •
•
Recall the definition of response time
Response time of Web Service 1
= Time at which composite web service receives Reply 1 minus
Time at which composite web service sends Request 1
Similarly for Web Service 2.
Web service 2
T1,2021 COMP9334 13
A simple web service scenario (3)
Web service 1
User request
Reply to user
composite web service
Request 1
Reply 1 Reply 2
Request 2
Web service 2
• Assuming that:
• Web service 1 has a response time distribution of
• 0.2s with probability 0.5
• 0.3s with probability 0.5
• Web service 2 has a response time distribution of
• 0.2s with probability 0.5
• 0.3s with probability 0.5
• What is the average time that the composite web
service has to wait until both replies are returned?
T1,2021 COMP9334
14
A simple web service scenario (4)
Web service 1
User request
Reply to user
composite web service
Request 1
Reply 1 Reply 2
Request 2
Web service 2
• What if the service time distribution is:
• Web service 1 has a response time distribution of
• 0.2s with probability 0.5
• 0.3s with probability 0.5
• Web service 2 has a response time distribution of
• 0.2s with probability 0.5
• 0.5s with probability 0.5
• What is the average time that the composite web
service has to wait until both replies are returned?
T1,2021 COMP9334
15
Analysis scenario
• Lessonlearnt:Slowwebservicescanbecomethe bottleneck for composite web service
• WeconsiderCompositeWebServices(illustrationnext slide)
• WithparallelinvocationofNservices
• Webservices1throughN-1haveameanservicetimeofS
(exponentially distributed)
• WebserviceNhasameanservicetimeofgxS(exponentially distributed)
• ThenextservicestepcanonlybecompletedafteralltheseNsteps have been completed.
Note that if 𝜶 < 1, then server N
is slower than the other (N-1) servers.
T1,2021 COMP9334 16
𝟏 𝜶
xS
Servers 1 to N-1 : mean response time = S
Server N: mean response time = 𝜶 x S
T1,2021 COMP9334 17
𝟏 𝜶
xS
Fork-join system
• The type of system described earlier is known as fork-join system
• Forkisreferringtotheparallelinvocation
• Allservicesmustcompleteatthejoiningpointbeforethenext
service can start
T1,2021 COMP9334 18
You’ve seen parallel processing before:
M/M/m queue Fork-join queue
: :
fork : join :
What is the difference between these two
queueing networks?
T1,2021 COMP9334
19
Servers 1 to N-1 : mean response time = S
Server N: mean response time = 𝜶 x S
• Wewanttounderstandhow𝜶affectstheresponse time of the composite web services
• LetT(𝜶)=responsetimeasafunctionof𝜶
T1,2021 COMP9334 20
𝟏 𝜶
xS
What is T(1)?
• In this case, all constituent web services have the same response time distribution
• If all mean response times are exponentially distributed with mean S
(We will explain how this is obtained later.)
T1,2021 COMP9334 21
How about T(𝜶) for 𝜶>1? • We use Markov chain.
• States (i,j,k)
• i(i=0,…,N-1)isthenumberofwebservicesstillrunninginfast
Web services
• j(j=0,1)isthenumberofwebservicesrunningontheslow Web service
• k(k=1,2,..,N)isthenumberofwebservicesyettocomplete
# $
• Define 𝜇 =
T1,2021
COMP9334 22
𝜶 < 1 o r %# > 1
aμ P(N) (N-1,1,N)
μ 𝜶μ
(N-1,0,N-1) R(N-1) (N-1)μ
(N-2,0,N-2) R(N-2) (N-2)μ
(N-1)μ Q(N-2) (N-2,1,N-1)
(N-2)μ Q(N-3) (N-3,1,N-2)
(N-3)μ Q(N-4) (N-4,1,N-3)
(N-4)μ Q(1) (1,1,2)
𝜶μ
𝜶μ 𝜶μ
(N-3,0,N-3)
R(N-3)
(2,0,2) R(2) μ 𝜶μ μ
(0,1,1) Q(0) (1,0,1) R(1) T1,2021 COMP9334
23
𝜶
T(𝜶)
𝜶
Note: When 𝜶 = 1, T(𝜶) = HN S
𝜶
T1,2021
COMP9334
24
How T(𝜶)/S varies with 𝜶?
T(𝜶)/S
T1,2021
COMP9334
25
𝜶
1
𝛼
Other examples of fork-join QNs
• Disk array, e.g. RAID (= Redundant Array of Independent Disks)
RAID controller
Example of RAID1 Mirrored disks
T1,2021 COMP9334
26
Fork-join in disk array
Example 1
Read a file in parallel
1st half of the file from Disk 0 2nd half of the file from Disk 1 Need to wait for both halves of the file before the next operation
I/O requests
RAID controller
Example 2 Write to disk.
Need to write to both disks (for consistency)
Need to wait for both disks to complete
T1,2021 COMP9334 27
Fork-join queueing networks
• Exact results are hard to come by
• Approximate solution methods are used
T1,2021 COMP9334 28
A Queueing network with a fork-join subsystem
fork
join
Serial subsystem
Parallel subsystem
T1,2021 COMP9334
29
Approximate MVA for fork-join queueing networks
• For MVA with fork-join, the basic unit is a subsystem
• Asubsystemcanbeeitheraserialsubsystem(=adevice)or
parallel one
• Aserialsubsystemisaspecialcaseofparallelsubsystem
• Incomparison,thebasicunitforMVAbeforeisadevice
T1,2021 COMP9334 30
Arrival Theorem for Parallel Subsystems (1)
• Consideraparallelsubsystemwithkparallelservicecentres • Theaveragetimeeachjobrequiresateachservicecentreis
S (exponentially distributed)
μ =1/S
T1,2021 COMP9334 31
Arrival Theorem for Parallel Subsystems (2)
One of the
n jobs (customers)
T1,2021 COMP9334 32
Note that if k = 1, the subsystem is serial and is identical to a device in MVA analysis that we have seen before.
This is the same arrival theorem that we’ve seen before.
T1,2021 COMP9334 33
Notation:
T1,2021 COMP9334 34
MVA for fork-join systems:
Mean # jobs in each subsystem
(n-1) jobs in system n jobs in system
Mean response time of each subsystem
Throughput of the system
Mean # jobs in each subsystem
T1,2021 COMP9334
35
Example
• A system consists of a processor and 2 disk arrays
• Disk arrays operate under synchronous workload
• Transactions are blocked until I/O are completed
Service demand
# parallel systems
Processor
0.01
1
Disk array 1
0.02
2
Disk array 2
0.03
3
What is the system response time when there are 50 transactions? How many transactions can the system have if the system response time should not exceed 1s?
T1,2021 COMP9334 36
Exercise
• The MVA algorithm on p.35 assumes that you have both visit ratios Vi and mean service time Si available
• You may recall that service demand Di = Vi * Si
• Now, let us assume that you are only given the service demands Di. That is, you know only Di but you do not know Vi and Si. How can you modify the MVA algorithm on p.35 so that it can work with knowing service demands only?
T1,2021 COMP9334 37
References (1)
• Webservices
• D. Mensace et al. Static and Dynamic Processor Scheduling Disciplines in Heterogeneous Parallel Architectures,” Journal of Parallel and Distributed Computing, Vol. 28 (1), July 1995, pp. 1-18.
• D. Mensace, “QoS Issues in Web Services,” IEEE Internet Computing, November/December 2002, Vol. 6, No. 6.
• D. Mensace, “Response Time Analysis of Composite Web Services,” IEEE Internet Computing, January/February 2004, Vol. 8, No. 1
• D. Mensace, “Composing Web Services: A QoS View,” D. Menasce, IEEE Internet Computing, Vol. 8., No. 6, Nov/Dec 2004.
• These papers can be downloaded from the course website (use your CSE password)
• Wedidn’tcoverthelastpaperbutit’swellwortharead.
• Derivation of Markov chain on pp. 22-24 is further explained in the file
forkjoin_mc.pdf
T1,2021 COMP9334 38
References (2)
• Fork-join MVA
• Menasceetal.,”Performancebydesing”.Section15.6.
• Addition references outside the scope of this course • TutorialonRAIDhttp://www.slcentral.com/articles/01/1/raid/
T1,2021 COMP9334 39