COMP9334
Capacity Planning for Computer Systems and Networks
Week 2B: Queues with Poisson arrivals
COMP9334
1
Pre-lecture exercise: Where is Felix? (Page 1)
• Youhavetwoboxes:Box1andBox2,aswellasacatcalledFelix
• Thetwoboxesareconnectedbyatunnel
• Felixlikestohideinsidetheseboxesandtravelsbetweenthemusingthe tunnel.
• Felixisaveryfastcatsotheprobabilityoffindinghiminthetunneliszero
• YouknowFelixisinoneoftheboxesbutyoudon’tknowwhichone
12
T1, 2021 COMP9334 2
Pre-lecture exercise: Where is Felix? (Page 2)
• Notation:
• Prob[A]=probabilitythateventAoccurs
• Prob[A|B]=probabilitythateventAoccursgiveneventB
• You do know
• Felixisinoneoftheboxesattimes0and1
• Prob[FelixisinBox1attime0]=0.3
• Prob[FelixwillbeinBox2attime1|FelixisinBox1attime0]=0.4 • Prob[FelixwillbeinBox1attime1|FelixisinBox2attime0]=0.2
• Calculate
• Prob[FelixisinBox1attime1]
12
T1, 2021 COMP9334
3
Pre-lecture exercise: Where is Felix? (Page 3)
• You want to calculate: Prob[ Felix is in Box 1 at time 1]
• Hint: There are two ways that Felix can end up in Box 1 at time 1
• FelixisinBox1attime0ANDhe ;OR • FelixisinBox2attime0ANDhe
• After you’ve figured out the 1 2 above, you will need:
doesn’t move
moves
Reminder:
Prob[A or B] = Prob[A] + Prob[B] – Prob[A and B] Prob[A and B] = Prob[A] Prob[B | A]
(Special case: A and B are mutually exclusive)
Prob[A or B] = Prob[A] + Prob[B] if Prob[A and B] = 0
T1, 2021 COMP9334 4
Performance analysis
• Modelling a computer system as a network of queues • Operational analysis
• Can be used to find performance bound • What if you want more exact performance?
• Need to consider
• Probabilitydistributionofthearrivalprocess • Probabilitydistributionoftheservicetime
T1, 2021 COMP9334 5
Exponential inter-arrival with rate l
Arrivals
Inter-arrival time
We assume that successive arrivals are independent Probability that inter-arrival time is between x and x + dx
= l exp(- lx) dx
T1, 2021 COMP9334 6
Poisson distribution
• The following are equivalent
• Theinter-arrivaltimeisindependentandexponentiallydistributed
with parameter l
• ThenumberofarrivalsinanintervalTisaPoissondistributionwith
parameter l
• Mean inter-arrival time = 1 / l
• Mean number of arrivals in time interval T = l T • Mean arrival rate = l
T1, 2021 COMP9334 7
Sample queueing problems
• Consider a call centre
• CallsarearrivingaccordingtoPoissondistributionwithratel
• Thelengthofeachcallisexponentiallydistributedwithparameterμ • Mean length of a call is 1/ μ (in, e.g. seconds)
Call centre:
Arrivals
m operators
If all operators are busy, the centre can put
at most n additional calls on hold.
If a call arrives when all operators and holding slots are used, the call is rejected.
• Queueing theory will be able to answer these questions: • Whatistheprobabilitythatacallisrejected?(Thislecture)
• Whatisthemeanwaitingtimeforacall?(Nextlecture)
T1, 2021 COMP9334 8
Let us start simple
• We will start by looking at a call centre with one operator and no holding slot
• Thismaysoundunrealisticbutwewanttoshowhowwecansolve a typical queueing network problem
Poisson Arrivals
Call centre:
1 operator. No holding slot.
Poisson Arrivals
T1, 2021 COMP9334 9
Analysis strategy
• The analysis will consider what happens over a small time interval d
• This is so that we can consider only two possibilities in each time interval
T1, 2021 COMP9334 10
Poisson distribution
• Considerasmalltimeintervald
• This means dn (for n >= 2) is negligible
• An interpretation of Poisson arrival:
• Probability[noarrivalind]=1-ld
• Probability[1arrivalind]=ld
• Probability [ 2 or more arrivals in d ] » 0
• This interpretation can be derived from:
T1, 2021 COMP9334 11
Service time distribution
• Service time = the amount of processing time a job requires from the server
• We assume that the service time distribution is exponential with parameter μ
• Theprobabilitythattheservicetimeisbetweentandt+dtis: dt
• Here: μ = service rate = 1 / mean service time
• Another interpretation of exponential service time:
• Considerasmalltimeintervald
• Probability[ajobwillfinishitsserviceinnextdseconds]=μd
• Probability[ajobwillnotfinishitsserviceinnextdseconds]=1-μd T1, 2021 COMP9334 12
Call centre with 1 operator and no holding slots
• Let us see how we can solve the queuing problem for a very simple call centre with 1 operator and no holding slots
• What happens to a call that arrives when the operator is busy?
• Thecallisrejected
• What happens to a call that arrives when the operator is idle?
• Thecallisadmittedwithoutdelay.
• We are interested to find the probability that an arriving call
is rejected.
Poisson Arrivals
Call centre:
1 operator. No holding slot.
T1, 2021 COMP9334 13
Solution (1)
• There are two possibilities for the operator: • Busyor
• Idle
• Let
• State0=Operatorisidle(i.e.#callsinthecallcentre= • State1=Operatorisbusy(i.e.#callsinthecallcentre=
T1, 2021 COMP9334 14
?
0)
1)
?
Solution (2)
• Nocallatcallcentreatt+Dtcanbecausedby
• Nocallattimetandnocallarrivesin[t,t+Dt],or • 1callattimetandthecallfinishesin[t,t+Dt]
Question: Why do we NOT have to consider the following possibility: No customer at time t & 1 customer arrives in [t, t + Dt] &
the call finishes within [t, t + Dt].
T1, 2021 COMP9334 15
Solution (3)
• Similarly, we can show that
• If we let Dt!0, we have
T1, 2021 COMP9334 16
Solution (4)
• We can solve these equations to get
T1, 2021 COMP9334 17
Solution (5)
• We can solve these equations to get
• This is too complicated, let us look at steady state solution
T1, 2021 COMP9334 18
Solution (5)
• From the steady state solution, we have • Theprobabilitythatanarrivingcallisrejected
• =Theprobabilitythattheoperatorisbusy •=
• Let us check whether it makes sense
• Foraconstantμ,ifthearrivalrateratelincreases,willthe
probability that the operator is busy go up or down? • Doestheformulagivethesameprediction?
T1, 2021 COMP9334 19
An alternative interpretation
• We have derived the following equation: • Which can be rewritten as:
• At steady state:
Rate of leaving state 0
Rate of entering state 0
T1, 2021 COMP9334
20
Faster way to obtain steady state solution (1)
• Transition from State 0 to State 1 • Causedbyanarrival,therateisl
• Transition from State 1 to State 0
• Causedbyacompletedservice,therateisμ
• State diagram representation
• Eachcircleisastate
• Labelthearcbetweenthestateswithtransitionrate
l
μ
0
1
T1, 2021 COMP9334
21
Faster way to obtain steady state solution (2)
• Steady state means
• rateoftransitionoutofastate=Rateoftransitionintoastate
• We have for state 0:
l
μ
0
1
T1, 2021 COMP9334
22
Faster way to obtain steady state solution (3)
• WecandothesameforState1: • Steadystatemeans
• Rate of transition into a state = rate of transition out of a state • Wehaveforstate1:
l
μ
0
1
T1, 2021 COMP9334
23
Faster way to obtain steady state solution (4)
• Wehaveoneequation
• Wehave2unknownsandweneedonemoreequation.
• Sincewemustbeeitheroneofthetwostates:
• Solvingthesetwoequations,wegetthesamesteadystatesolutionas before
T1, 2021 COMP9334 24
Summary
• Solving a queueing problem is not simple
• It is harder to find how a queue evolves with time
• It is simpler to find how a queue behaves at steady state
• Procedure:
• Draw a diagram with the states
• Add arcs between states with transition rates
• Derive flow balance equation for each state, i.e. • Rate of entering a state = Rate of leaving a state
• Solve the equation for steady state probability
T1, 2021
COMP9334 25
Don’t forget the probabilistic interpretation
• Change in probability in State 0
Rate of leaving state 0
Rate of entering state 0
Prob[Leaving State 0 | State 0]
Prob[Entering State 0 | State 1]
T1, 2021 COMP9334
26
A call centre with 1 operator and 1 holding slot
• We want to determine the probability that an arriving call will be rejected
Poisson Arrivals
Call centre:
1 operators. 1 holding slot.
T1, 2021 COMP9334 27
Analysing the queueing problem
• The system can be in one of the following three states • State0=0callinthesystem(=theoperatorisidle)
• State1=1callinthesystem(=Operatorbusy.Holdingslotempty.) • State2=2callsinthesystem(=Operatorbusy.Holdingslot
occupied.)
• Define the probability that a certain state occurs
T1, 2021 COMP9334 28
The transition probabilities
• Consider a small time interval d
• GiventhesystemisinState1
• What is the probability that it will move to State 0?
• What is the probability that it will move to State 2?
• Transiting from State 1!State 0
• Thiscanonlyoccurwhenacallfinishesintimeintervald • Conditionalprobabilityforthistooccur=μd
• Transiting from State 1!State 2
• Thiscanonlyoccurwhenacallarrivesintimeintervald
• Conditionalprobabilityforthistooccur=ld • Prob[State1!State0|State1]=μd • Prob[State1!State2|State1]=ld
T1, 2021 COMP9334 29
Exercise: The transition probabilities
• Can you work out the following transition probabilities • Prob[State0!State1|State0]=ld
• Prob[State0!State2|State0]=0
• Prob[State2!State0|State2]=0
• Prob[State2!State1|State2]= μd
T1, 2021 COMP9334 30
The state transition diagram
• Giventhefollowingtransitionprobabilities(overasmalltimeintervald)
• Prob
• Prob
• Prob
• Prob
• Prob
• Prob
[State [State
[State [State [State [State
0 ! State 0 ! State
1 ! State 1 ! State 2 ! State 2 ! State
1 | 2 |
0 | 2 | 0 | 1 |
State State
State State State State
0] = ld 0] = 0 1] = μd 1] = ld 2] =
2] =
• Wedrawthefollowingstatetransitiondiagram
• Note 1: We label the arc with transition rate = transition probability / d
• Note 2: Arcs with zero rate are not drawn
l
l
0
1
2
μ
0
μd
T1, 2021
COMP9334
31
μ
Setting up the balance equations (1)
• Forsteadystate,wehave
• Prob of transiting into a “box” = Prob of transiting out of a “box” • Rate of transiting into a “box” = Rate of transiting out of a “box”
• Notea“box”canincludeoneormorestate • The“box”isthedottedsquareshownbelow
0
l
μ
1
l
μ
2
T1, 2021
COMP9334
32
Exercise: Setting up the balance equations (2)
• Setupthebalanceequationsforthe • Red box
• Green box 0
μ l
μ
1
l
l
μ l
μ
2
2
0
1
T1, 2021
COMP9334
33
The balance equations
• There are three balance equations
• Note that these three equations are not linearly independent • Firstequation+Thirdequation=Secondequation
• There are 3 unknowns (P0, P1, P2) but we have only 2 equations
• We need 1 more equation. What is it?
T1, 2021 COMP9334 34
Solving for the steady state probabilities
• An addition equation: Sum( Probabilities ) = 1
• Solve the following equations for the steady state
probabilities P0, P1, P2 :
• By solving these 3 equations, we have
T1, 2021 COMP9334 35
Steady state probabilities
• By solving the equations on the previous slide, we have the steady state probabilities are:
• If we know the values of l and μ, we can find the numerical values of these probabilities
• Do the expressions make sense?
T1, 2021
COMP9334
36
Summary and References
• Summary
• Poissonqueueswith1server+(0or1)holdingslot • Howtosolvethesteadystatesolution
• Recommended reading
• QueueswithPoissonarrivalarediscussedin
• BertsekasandGallager,DataNetworks,Sections3.3to3.4.3
• Note:IderivedtheformulashereusingcontinuousMarkovchain but Bertsekas and Gallager used discrete Markov chain
T1, 2021 COMP9334 37