COMP9334
Capacity Planning for Computer Systems and Networks
Week 7B: Mean Value Analysis
COMP9334
1
This lecture
• Methods to efficiently analyse a closed queueing network
• Motivation
• Youhavelearnthowtoanalyseaclosedqueueingnetworkin Week 3B using Markov chain
• However,themethodcanonlybeusedforasmallnumberofusers
• This week we will study a method that can be used for a
large number of users
• Let us begin by revisiting the database server example in Week 3B
T1,2021 COMP9334 2
DB server example
2 users
Fast Disk (15s)
CPU (10s)
Slow Disk (30s)
• 1 CPU, 1 fast disk, 1 slow disk.
• Peak demand = 2 users in the system all the time.
• Transactions alternate between CPU and disks.
• The transactions will equally likely find files on either disk
• Service time are exponentially distributed with mean showed in
parentheses.
T1,2021 COMP9334 3
Markov chain solution to the DB server problem
• In Week 3B, we used Markov chain to solve this problem
• We use a 3-tuple (X,Y,Z) as the state
• Xis#usersatCPU
• Y is # users at fast disk
• Z is # users at slow disk
• Examples
• (2,0,0): both users at CPU
• (1,0,1): one user at CPU and one user at slow disk
• Six possible states
• (2,0,0) (1,1,0) (1,0,1) (0,2,0) (0,1,1) (0,0,2)
T1,2021 COMP9334 4
Markov model for the database server with 2 users
2,0,0
3
3
0,2,0
1,1,0
3
2
4
2
1,0,1
4
3
4
3
0,1,1
2
3
0,0,2
T1,2021
COMP9334
5
Solving the model
• SolvefortheprobabilityineachstateP(2,0,0),P(1,1,0), etc.
• Thereare6statessoweneed6equations
• AftersolvingforP(2,0,0),P(1,1,0)etc.wecanfind • Utilisation
• Throughput,
• Responsetime,
• Average number of users in each component etc.
T1,2021 COMP9334 6
What if we have 3 users instead?
• Whatifwehave3usersinthedatabaseexampleinstead of only 2 users?
• Wecontinuetouse(X,Y,Z)asthestate • Xisthe#usersatCPU
• Yisthe#usersatthefastdisk
• Zisthe#usersattheslowdisk
• Howmanystateswillyouneed?
• Weneed10states: • (3,0,0),
• (2,1,0),(2,0,1)
• (1,2,0),(1,1,1),(1,0,2)
• (0,3,0),(0,2,1),(0,1,2),(0,0,3)
T1,2021 COMP9334 7
What if there are n users?
• Youcanshowthatiftherearenusersinthedatabase
server, the number of states m required will be
• Forn=100,m(=#states)~50000
• Youcanautomatethecomputationalprocessbutwhereis the computational bottleneck?
• Solvingasystemofmlinearequationsinmunknownshasa complexity of O(m3)
• Forourdatabaseserverwithnusers,thecomputational complexity is about O(n6)
T1,2021 COMP9334 8
Weaknesses of Markov model
• TheMarkovmodelforapracticalsystemwillrequiremany states due to
• Largenumberofusers
• Largenumberofcomponents
• Large#states
• Moretransitionstoidentify
• Though this can be automated
• Ifyou’vemstates,youneedtosolveasetofmequations.Alarger
set of equation to solve.
• The complexity of solving a set of m linear equations in m
unknowns is O(m3)
T1,2021 COMP9334 9
Mean value analysis (MVA)
• Aniterativemethodtofindthe • Utilisation
• Meanthroughput
• Meanresponsetime
• Meannumberofusers
• ThecomplexityisapproximatelyO(nk)where • nisthenumberofusers
• kisthenumberofdevices
• ThecomplexityofMVAmakesitaverypracticalmethod
T1,2021 COMP9334 10
MVA – overview
• MVA analysis has been derived for
• Closedmodel • Single-class
• Multi-class • Openmodel
• Mixedmodelwithbothopenandclosedqueueing
• This lecture discusses MVA for single-class closed model
T1,2021 COMP9334 11
MVA for closed system
• Consider a closed queueing network with a single-class of customers
• You are given a system with K devices
• You are given that each customer
• VisitsdevicejonaverageV(j)times
• RequiresameanservicetimeofS(j)fromdevicej
• Note: The service time required is assumed to be exponentially
distributed
• From the information given, we can deduce that the service demand D(j) for device j is V(j) S(j)
• How do we obtain D(j) for a practical system?
T1,2021 COMP9334 12
Key idea behind MVA
• Key idea behind MVA is iteration
• Ifyouknowthesolutiontotheproblemwhentherearen customers in the system, you can find the solution when there are (n+1) customers
T1,2021 COMP9334 13
Let us consider a simple example to motivate the iteration in MVA. Consider device j (say) of a queueing network.
Device j Assume that we know when there are 2
customers in the system, the average
number of users in device j is 0.6 (say).
What happens when there are 3 customers?
T1,2021 COMP9334 14
What happens when there are 3 customers?
Device j
The 3rd customer
• Let us assume the 3rd customer is arriving at device j.
• Where will the other 2 customers be? We cannot tell exactly but
we know that there is on average of 0.6 customers in device j
when there are 2 customers.
• The 3rd customer will see on average 0.6 customers when
it arrives at device j.
T1,2021 COMP9334 15
When there are n customers …
One of the n customers
Arrival Theorem
• If there are (n-1) customers in the system, the mean number of customers in device j is z customers,
• Then, when there are n customers, each customer arriving at device j will see on average z customers ahead of itself
in device j.
Device j
T1,2021 COMP9334 16
How can Arrival Theorem help?
Device j
One of the n customers
Let S(j) = mean service time at device j.
When there are n customers,
The mean waiting time at device j = z S(j)
The mean response time at device j = (z+1) S(j)
z out of (n-1) customers are here.
T1,2021 COMP9334 17
Iterations of MVA:
Mean number of customers in each device
#customers = n-1
Mean response time for each device
…..
…..
Mean number of customers in each device
#customers = n
Mean response time for each device ….
#customers = n+1
T1,2021 COMP9334 18
Some notation
T1,2021 COMP9334 19
System response time
Throughput of the system
Throughput of each device
Mean response time of each device
Mean # customers in each device
T1,2021 COMP9334
20
Initialisation of MVA:
Mean number of customers in each device
#customers = 0
Mean response time for each device
…..
…..
Mean number of customers in each device
#customers = 1
Mean response time for each device ….
#customers = 2
T1,2021 COMP9334 21
Let us apply MVA to the database server example
2 users
Fast Disk (15s)
CPU (10s)
Device 1 = CPU; Device 2 = Fast disk; Device 3 = Slow disk
Slow Disk (30s)
• Determinetheperformancewhenthereare2usersinthesystem • Andhowabout3users?
T1,2021 COMP9334 22
Limitation of MVA
• MVA allows you to find the mean value of throughput, response time etc.
• However, if you are interested to find the probability that the system is in a certain state. MVA cannot give you the answer. You will need to resort to Markov model.
T1,2021 COMP9334 23
Extensions of MVA
• Closed queueing networks with multiple classes of customers
• Example:Databaseserverswith2classesofcustomers
• One class of customers require mean service time of 0.02s, 0.03s
and 0.05s from the CPU, fast and slow disk
• Another class of customers require mean service time of 0.04s, 0.01s and 0.1s from the CPU, fast and slow disk
• Open queueing networks • Mixed queueing networks
T1,2021 COMP9334 24
Assumptions behind MVA
• The service time is exponentially distributed
• The service time required at each component is independent
• Forexample,MVAassumesthattheservicetimerequiredatCPUis independent of the service time at the disk
2 users
CPU (10s)
Fast Disk (15s)
Slow Disk (30s)
T1,2021 COMP9334
25
Solution to network of queues
• You have seen two possible methods to solve a network of queues
• Analyticalsolution • Simulation
• For closed queueing networks with exponentially distributed service time
• Markovchain • MVA
• Commercial simulation tools can deal with hundred of nodes
T1,2021 COMP9334 26
Multicast in wireless mesh networks
• Inmyresearchon designing multicast protocol for wireless mesh networks, we use simulation package Qualnet to investigate which of the multicast protocols that we have designed is better
• Thenetworkhas400 wireless mesh routers (= 400 queues)
• You can find out more on my research from my web site: http://www.cse.unsw.edu.au/~ctchou/
T1,2021 COMP9334
27
Analytical solution versus simulation
• Analytical solution
• Limitedtospecificcases
• E.g. Exponential assumptions
• Efficientcomputationalgorithmexistsforcertaincases
• MVA for closed queueing networks with exponential service time • Simulation
• Canapplytogeneralsettings
• Difference classes of traffic, protocols etc.
• Canapplytoreasonablylargenetworkstoo
T1,2021 COMP9334 28
References
• The primary reference for MVA for closed queueing networks with one class of customer is:
• Chapter12,Menasceetal.,“Performancebydesign”
• An alternative reference for MVA is Chapter 6 of Edward Lazowska et al, Quantitative System Performance, Prentice Hall, 1984. (Now out of print but can be download from http://www.cs.washington.edu/homes/lazowska/qsp/)
• NotethatChapter6hasawidercoverage.Ittalksaboutopen queueing network as well as approximation method too.
• For a formal mathematical proof of Arrival Theorem, see Bertsekas and Gallager, “Data networks”, Section 3.8.3
T1,2021 COMP9334 29