COMP9334
Capacity Planning for Computer Systems and Networks
Week 3A: Queues with Poisson arrivals (2)
COMP9334
1
Pre-lecture exercise
• You have a loaded die with 6 faces with values 1, 2, 3, 4, 5 and 6
• The probability that you can get each face is given in the table below
• What is the mean value that you can get?
Value
Probability
1
0.1
2
0.1
3
0.2
4
0.1
5
0.3
6
0.2
T1, 2021 COMP9334 2
Single-server queue
Arrivals
• Open,singleserverqueues
• Howtofind: • Waitingtime
• Responsetime
• Meanqueuelengthetc.
Departures
• Thetechniquetofindwaitingtimeetc.iscalledQueueing Theory
T1, 2021 COMP9334 3
Multiple server queue
Arrivals
Departures
1
2 3
• Open,multi-serverqueue
• Howtofind: • Waitingtime
• Responsetime
• Meanqueuelengthetc.
m
m servers
T1, 2021
COMP9334
4
What will you be able to do with the results?
Configuration 1:
processing speed = m p
Configuration 3:
Arrivals
Randomly
assign the arrivals into m queues
1
m
Configuration 2: Arrivals
1
m servers of speed p
m
T1, 2021 COMP9334
5
m servers of
Which configuration has the best response time?
speed p
Single Server Queue: Terminology
l
WS
Time spent waiting
T=W+S
Response Time T
= Waiting time W + Service time S
Note: We use T for response time because this is the notation in many queueing theory books. For a similar reason, we will use r for utilisation rather than U.
T1, 2021 COMP9334 6
Call centre analogy from Week 2B
• Consider a call centre
• CallsarearrivingaccordingtoPoissondistributionwithratel
• Thelengthofeachcallisexponentiallydistributedwithparameterμ • Meanlengthofacallis1/μ
Arrivals
Call centre:
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.
• We solved the problems for
• (m=1andn=0),and(m=1andn=1)
• How about other values of m and n? What about response time?
T1, 2021 COMP9334 7
Kendall’s notation
• To represent different types of queues, queueing theorists use the Kendall’s notation
• The call centre example on the previous page can be represented as:
Inter-arrival distribution
is Markovian i.e. Exponential
M / M / s (/ B)
Service time distribution
is Markovian i.e. Exponential
Buffer Positions (wait room)
Number of servers
The call centre example on the last page is a M/M/m/(m+n) queue If n = ∞, we simply write M/M/m
T1, 2021 COMP9334 8
M/M/1 queue
Exponential Inter-arrivals (l)
Exponential Service time (μ)
Infinite buffer
One server
• Consider a call centre analogy
• CallsarearrivingaccordingtoPoissondistributionwithratel
• Thelengthofeachcallisexponentiallydistributedwithparameterμ • Meanlengthofacallis1/μ
Arrivals
• Queueing theory will be able to answer these questions: • Whatarethemeanwaitingtime,meanresponsetimeforacall?
Call centre with 1 operator
If the operator is busy, the centre will put
the call on hold.
A customer will wait until his call is answered.
T1, 2021 COMP9334 9
Little’s Law
• Applicabletoany“box”thatcontainssomequeuesorservers • Meannumberofjobsinthe“box”=
Mean response time x Throughput
• WewilluseLittle’sLawinthislecturetoderivethemeanresponsetime
• We first compute the mean number of jobs in the “box” and throughput
T1, 2021 COMP9334 10
M/M/1: State and transition diagram
• Wewillsolveforthesteadystateresponse
• Definethestatesofthequeue
• State 0 = There is zero job in the system (= The server is idle)
• State1=Thereis1jobinthesystem(=1jobattheserver,nojob queueing)
• State2=Thereare2jobsinthesystem(=1jobattheserver,1job queueing)
• State k = There are k jobs in the system (= 1 job at the server, k-1 job queueing)
• Thestatetransitiondiagram lll
l
..
μμ
0123…
μ
K-1
l
k
μ
μ
T1, 2021 COMP9334
11
l
0
μ
M/M/1 state balance:
ll
l
k
l
..
μμ
123…
μ
K-1
μ
T1, 2021
COMP9334
12
M/M/1 state balance: Exercise 1
l
1
μ
ll
l
..
μμ
l
…
μ
• Exercise:WritethestatebalanceequationforState1
k
023
μ
K-1
T1, 2021 COMP9334
13
M/M/1 state balance: Exercise 2
lll
l
..
μμ
0123…
μ
K-1
l
k
μ
μ
• Exercise: Write the state balance equation for magenta box, i.e. Rate of transiting out of the magenta box
= Rate of transiting into the magenta box
T1, 2021 COMP9334 14
l
0
l
1
μ
μ
State balance for State 1
State balance for State 1 and State 2 combined
Which state balance is easier to work with?
l
2
l
…
μ
l
..
μμ
3
K-1
k
T1, 2021
COMP9334
15
M/M/1 state balance: Relating P2 and P0
l
0
μ
l
1
μ
l
2
l
…
μ
l
..
μμ
3
K-1
k
T1, 2021
COMP9334
16
M/M/1 state balance: Relating P3 and P0
lll
l
..
μμ
0123…
μ
K-1
l
k
μ
μ
T1, 2021 COMP9334
17
M/M/1 state balance: Relating Pk and P0
In general
We have
T1, 2021 COMP9334 18
Solving for Pk
With and
Since
Arrival rate < service rate
T1, 2021 COMP9334
19
r = utilisation
= Prob server is busy = 1 - P0
= 1- Prob server is idle
Exercise: Mean number of jobs
Recall that
and we have calculated that
Determine the mean number of jobs in the system. Hint 1: Look at pre-lecture exercise 1.
You can use the following formula to help you.
T1, 2021 COMP9334 20
Mean number of jobs
The mean number of jobs in the system =
T1, 2021 COMP9334 21
M/M/1: mean response time
l
Little’s law:
mean number of customers = throughput x response time
Throughput is l (why?)
T1, 2021 COMP9334 22
Mean waiting time = mean response time - mean service time We know mean response time (from last slide)
Mean service time is = 1 / μ
Exercise: M/M/1 mean waiting time
l
What is the mean waiting time at the queue?
T1, 2021 COMP9334 23
Using the service time parameter (1/μ = 15ms) in the example, let us see how response time T varies with l
Observation: Response time increases sharply when r gets close
to 1
Infinite queue assumption
means r ® 1, T®¥
T1, 2021
COMP9334
24
Non-linear effect on response time
• The response time of an M/M/1 queue
• Assuming the mean arrival rate is 10 requests/s
• We will calculate the effect of service rate on response time • Complete the following table and see what you can conclude
Service rate
11
22
Utilisation 𝛌/𝝁
10/11 = 0.909
10/22 = 0.454
Response time
1
0.08
• Doubling the service rate can sometimes reduce by response time by a factor more than 2.
T1, 2021 COMP9334 25
Multi-server queues M/M/m
Exponential 1 Inter-arrivals (l)
Exponential
Service time (μ) 2
All arrivals go into one queue.
Customers can be served by any one of the m servers.
When a customer arrives • If all servers are busy, it will join the queue
• Otherwise, it will be served by one of the available servers
Infinite buffer
m servers T1, 2021 COMP9334
26
3
m
A call centre analogy of M/M/m queue
• Consider a call centre analogy
• CallsarearrivingaccordingtoPoissondistributionwithratel
• Thelengthofeachcallisexponentiallydistributedwithparameterμ • Meanlengthofacallis1/μ
Arrivals
Call centre with m operators
If all m operators are busy, the centre will put the call on hold.
A customer will wait until his call is answered.
T1, 2021 COMP9334 27
State transition for M/M/m
llll
0123..
μ 2μ 3μ mμ mμ mμ
l
l
..
m
m+1
T1, 2021 COMP9334 28
M/M/m
• Followingthesamemethod,wehavemeanresponsetimeTis
where
T1, 2021 COMP9334 29
Multi-server queues M/M/m/m with no waiting room
Exponential 1 Inter-arrivals (l)
Exponential
Service time (μ) 2
An arrival can be served by any one of the m servers.
When a customer arrives • If all servers are busy, it will depart from the system
No waiting Room or No buffer
• Otherwise, it will be served by one of the available servers
3
m servers T1, 2021 COMP9334
30
m
A call centre analogy of M/M/m/m queue
• Consider a call centre analogy
• CallsarearrivingaccordingtoPoissondistributionwithratel
• Thelengthofeachcallisexponentiallydistributedwithparameterμ • Meanlengthofacallis1/μ
Arrivals
Call centre with m operators
If all m operators are busy, the call is dropped.
T1, 2021 COMP9334 31
State transition for M/M/m/m
lll l
l
0123..
μ 2μ 3μ (m-1)μ mμ
Probability that an arrival is blocked
= Probability that there are m customers in the system
where
“Erlang B formula”
m-2 m-1 m
T1, 2021 COMP9334
32
What configuration has the best response time?
Configuration 1:
processing speed = m p
Configuration 3:
Arrivals
Randomly
assign the arrivals into m queues
1
m
Configuration 2: Arrivals
1
m servers of speed p
m
Try out the tutorial question!
m servers of
T1, 2021 COMP9334 speed p 33
References
• Recommended reading
• QueueswithPoissonarrivalarediscussedin
• BertsekasandGallager,DataNetworks,Sections3.3to3.4.3
• Note:IderivedtheformulashereusingcontinuousMarkovchain
but Bertsekas and Gallager used discrete Markov chain
• MorHarchal-Balter.Chapters13and14
T1, 2021 COMP9334 34