week03
COMP9334 1
COMP9334
Capacity Planning for Computer Systems
and Networks
Week 3: Queues with Poisson arrivals
Pre-lecture exercise 1:
• Let X and Y be two events
• Let Prob[X] = Probability that event X occurs
• Let Prob[Y] = Probability that event Y occurs
• Question: Under what condition will the following equality
hold?
• Prob[X or Y] = Prob[X] + Prob[Y]
S1,2018 COMP9334 2
Pre-lecture exercise 2: Where is Felix? (Page 1)
• You have two boxes: Box 1 and Box 2, as well as a cat called Felix
• The two boxes are connected by a tunnel
• Felix likes to hide inside these boxes and travels between them using the
tunnel.
• Felix is a very fast cat so the probability of finding him in the tunnel is zero
• You know Felix is in one of the boxes but you don’t know which one
S1,2018 COMP9334 3
21
Pre-lecture exercise 2: Where is Felix? (Page 2)
• Notation:
• Prob[A] = probability that event A occurs
• Prob[A | B] = probability that event A occurs given event B
• You do know
• Felix is in one of the boxes at times 0 and 1
• Prob[ Felix is in Box 1 at time 0] = 0.3
• Prob[ Felix will be in Box 2 at time 1| Felix is in Box 1 at time 0] = 0.4
• Prob[ Felix will be in Box 1 at time 1| Felix is in Box 2 at time 0] = 0.2
• Calculate
• Prob[ Felix is in Box 1 at time 1]
• Prob[ Felix is in Box 2 at time 1]
S1,2018 COMP9334 4
1 2
Pre-lecture exercise 3
• 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?
S1,2018 COMP9334 5
Value Probability
1 0.1
2 0.1
3 0.2
4 0.1
5 0.3
6 0.2
S1,2018 COMP9334 6
Week 1:
• Modelling a computer system as a network of queues
• Example: Open queueing network consisting of two
queuesOpen queueing network
External arrivals
Workload intensity specified by arrival rate
Unbounded number of customers in the system
In equilibrium, flow in = flow out
) throughput = arrival rate
Page 26
S1,2018 COMP9334 7
Week 2:
• Operational analysis
• Measure #completed jobs, busy time etc
• Operational quantities: utilisation, response time, throughput etc.
• Operational laws relate the operational quantities
• Bottleneck analysis
S1,2018 COMP9334 8
Little’s Law
• Applicable to any “box” that contains some queues or servers
• Mean number of jobs in the “box” =
Mean response time x Throughput
• We will use Little’s Law in this lecture to derive the mean response time
• We first compute the mean number of jobs in the “box” and throughput
S1,2018 COMP9334 9
This week (1)
• Open, single server queues and
• How to find:
• Waiting time
• Response time
• Mean queue length etc.
• The technique to find waiting time etc. is called Queueing
Theory
Arrivals Departures
S1,2018 COMP9334 10
This week (2)
• Open, multi-server queue
• How to find:
• Waiting time
• Response time
• Mean queue length etc.
1
2
3
m
m servers
Arrivals
Departures
S1,2018 COMP9334 11
What will you be able to do with the results?
Configuration 1:
processing speed = m p
1
mm servers of
speed p
Arrivals
Configuration 2:
1
m
Split arrivals
into m queues
m servers of
speed p
Arrivals
Configuration 3:
Which configuration has the
best response time?
S1,2018 COMP9334 12
Be patient
• We will show how we can obtain the response time
• It takes a number of steps to obtain the answer
• It takes time to stand in a queue, it also takes time to derive
results in queuing theory!
S1,2018 COMP9334 13
Single Server Queue: Terminology
Time spent waiting
Response Time T
= Waiting time W + Service time S
l
W S
T = W + 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.
S1,2018 COMP9334 14
Single server system
• In order to determine the response time, you need to know
• The inter-arrival time probability distribution
• The service time probability distribution
• Possible distributions
• Deterministic
• Constant inter-arrival time
• Constant service time
• Exponential distribution
• We will focus on exponential distribution
S1,2018 COMP9334 15
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
S1,2018 COMP9334 16
Poisson distribution (1)
• The following are equivalent
• The inter-arrival time is independent and exponentially distributed
with parameter l
• The number of arrivals in an interval T is a Poisson distribution with
parameter l
• Mean inter-arrival time = 1 / l
• Mean number of arrivals in time interval T = l T
• Mean arrival rate = l
S1,2018 COMP9334 17
Poisson distribution (2)
• Poisson distribution arises from a large number of
independent sources
• An example from Week 2:
• N customers, each with a probability of p per unit time to make a request.
• This creates a Poisson arrival with l = Np
• Another interpretation of Poisson arrival:
• Consider a small time interval d
• This means dn (for n >= 2) is negligible
• Probability [ no arrival in d ] = 1 – l d
• Probability [ 1 arrival in d ] = l d
• Probability [ 2 or more arrivals in d ] » 0
• This interpretation can be derived from:
S1,2018 COMP9334 18
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 µ
• The probability that the service time is between t and t + dt is:
• Here: µ = service rate = 1 / mean service time
• Another interpretation of exponential service time:
• Consider a small time interval d
• Probability [ a job will finish its service in next d seconds ] = µ d
• Probability [ a job will not finish its service in next d seconds ] = 1 – µ d
dt
S1,2018 COMP9334 19
Sample queueing problems
• Consider a call centre
• Calls are arriving according to Poisson distribution with rate l
• The length of each call is exponentially distributed with parameter µ
• Mean length of a call is 1/ µ (in, e.g. seconds)
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.
Call centre:
• Queueing theory will be able to answer these questions:
• What is the mean waiting time for a call?
• What is the probability that a call is rejected?
S1,2018 COMP9334 20
Road map
• We will start by looking at a call centre with one operator
and no holding slot
• This may sound unrealistic but we want to show how we can solve
a typical queueing network problem
• After that we go into queues that are more complicated
S1,2018 COMP9334 21
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?
• The call is rejected
• What happens to a call that arrives when the operator is
idle?
• The call is admitted without delay.
• We are interested to find the probability that an arriving call
is rejected.
Arrivals
1 operator. No holding slot.
Call centre:
S1,2018 COMP9334 22
Solution (1)
• There are two possibilities for the operator:
• Busy or
• Idle
• Let
• State 0 = Operator is idle (i.e. #calls in the call centre = 0)
• State 1 = Operator is busy (i.e. #calls in the call centre = 1)
?
?
S1,2018 COMP9334 23
Solution (2)
• No call at call centre at t + Dt can be caused by
• No call at time t and no call arrives in [t, t + Dt], or
• 1 call at time t and the call finishes in [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].
S1,2018 COMP9334 24
Solution (3)
• Similarly, we can show that
• If we let Dt è 0, we have
S1,2018 COMP9334 25
Solution (4)
• We can solve these equations to get
• This is too complicated, let us look at steady state solution
S1,2018 COMP9334 26
Solution (5)
• From the steady state solution, we have
• The probability that an arriving call is rejected
• = The probability that the operator is busy
• =
• Let us check whether it makes sense
• For a constant µ, if the arrival rate rate l increases, will the
probability that the operator is busy go up or down?
• Does the formula give the same prediction?
S1,2018 COMP9334 27
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
S1,2018 COMP9334 28
Faster way to obtain steady state solution (1)
• Transition from State 0 to State 1
• Caused by an arrival, the rate is l
• Transition from State 1 to State 0
• Caused by a completed service, the rate is µ
• State diagram representation
• Each circle is a state
• Label the arc between the states with transition rate
0 1
l
µ
S1,2018 COMP9334 29
Faster way to obtain steady state solution (2)
• Steady state means
• rate of transition out of a state = Rate of transition into a state
• We have for state 0:
0 1
l
µ
S1,2018 COMP9334 30
Faster way to obtain steady state solution (3)
• We can do the same for State 1:
• Steady state means
• Rate of transition into a state = rate of transition out of a state
• We have for state 1:
0 1
l
µ
S1,2018 COMP9334 31
Faster way to obtain steady state solution (4)
• We have one equation
• We have 2 unknowns and we need one more equation.
• Since we must be either one of the two states:
• Solving these two equations, we get the same steady state solution as
before
S1,2018 COMP9334 32
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
S1,2018 COMP9334 33
Let us have a look at our call centre problem again
• Consider a call centre
• Calls are arriving according to Poisson distribution with rate l
• The length of each call is exponentially distributed with parameter µ
• Mean length of a call is 1/ µ
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.
Call centre:
• We solve the problem for m = 1 and n = 0
• We call this a M/M/1/1 queue (explanation on the next page)
• How about other values of m and n
S1,2018 COMP9334 34
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:
M / M / s (/ B)
Service time
distribution
is Markovian
i.e exponential
Number of servers
Buffer Positions
(wait room)
Inter-arrival
distribution
is Markovian
i.e. Exponential
The call centre example on the last page is a M/M/m/(m+n) queue
If n = ∞, we simply write M/M/m
S1,2018 COMP9334 35
M/M/1 queue
Exponential
Inter-arrivals (l)
Infinite buffer One serverExponential
Service time (µ)
• Consider a call centre analogy
• Calls are arriving according to Poisson distribution with rate l
• The length of each call is exponentially distributed with parameter µ
• Mean length of a call is 1/ µ
Arrivals
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.
• Queueing theory will be able to answer these questions:
• What is the mean waiting time for a call?
S1,2018 COMP9334 36
Solving M/M/1 queue (1)
• We will solve for the steady state response
• Define the states of the queue
• State 0 = There is zero job in the system (= The server is idle)
• State 1 = There is 1 job in the system (= 1 job at the server, no job
queueing)
• State 2 = There are 2 jobs in the system (= 1 job at the server, 1 job
queueing)
• State k = There are k jobs in the system (= 1 job at the server, k-1 job
queueing)
• The state transition diagram
0
l
µ
1
l
µ
2
l
µ
3
l
µ
K-1 k
l
µ
. . . . .
S1,2018 COMP9334 37
Solving M/M/1 queue (2)
0
l
µ
1
l
µ
2
l
µ
3
l
µ
K-1 k
l
µ
. . . . .
S1,2018 COMP9334 38
Solving M/M/1 queue (3)
0
l
µ
1
l
µ
2
l
µ
3
l
µ
K-1 k
l
µ
. . . . .
S1,2018 COMP9334 39
Solving M/M/1 queue (4)
0
l
µ
1
l
µ
2
l
µ
3
l
µ
K-1 k
l
µ
. . . . .
S1,2018 COMP9334 40
Solving M/M/1 queue (5)
In general
We have
S1,2018 COMP9334 41
Solving M/M/1 queue (6)
With and
Since
Arrival rate < service rate r = utilisation = Prob server is busy = 1 - P0 = 1- Prob server is idle S1,2018 COMP9334 42 Solving M/M/1 queue (7) With This is the probability that there are k jobs in the system. To find the response time, we will make use of Little’s law. First we need to find the mean number of customers = S1,2018 COMP9334 43 Solving M/M/1 queue (8) Little’s law: mean number of customers = throughput x response time Throughput is l (why?) l S1,2018 COMP9334 44 Solving M/M/1 queue (9) What is the mean waiting time at the queue? Mean waiting time = mean response time - mean service time We know mean response time (from last slide) Mean service time is = 1 / µ l S1,2018 COMP9334 45 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®¥ S1,2018 COMP9334 46 Multi-server queues M/M/m 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 1 2 3 m Exponential Inter-arrivals (l) Exponential Service time (µ) Infinite buffer m servers S1,2018 COMP9334 47 A call centre analogy of M/M/m queue • Consider a call centre analogy • Calls are arriving according to Poisson distribution with rate l • The length of each call is exponentially distributed with parameter µ • Mean length of a call is 1/ µ 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. S1,2018 COMP9334 48 State transition for M/M/m 0 l µ 1 l 2µ 2 l 3µ 3 l mµ m m+1 l mµ . . . . mµ l S1,2018 COMP9334 49 M/M/m • Following the same method, we have mean response time T is where S1,2018 COMP9334 50 Multi-server queues M/M/m/m with no waiting room 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 • Otherwise, it will be served by one of the available servers 1 2 3 m Exponential Inter-arrivals (l) Exponential Service time (µ) No waiting Room or No buffer m servers S1,2018 COMP9334 51 A call centre analogy of M/M/m/m queue • Consider a call centre analogy • Calls are arriving according to Poisson distribution with rate l • The length of each call is exponentially distributed with parameter µ • Mean length of a call is 1/ µ Arrivals Call centre with m operators If all m operators are busy, the call is dropped. S1,2018 COMP9334 52 State transition for M/M/m/m 0 l µ 1 l 2µ 2 l 3µ 3 mµ mm-1 l . . (m-1)µ l m-2 Probability that an arrival is blocked = Probability that there are m customers in the system where “Erlang B formula” S1,2018 COMP9334 53 What configuration has the best response time? Configuration 1: processing speed = m p 1 mm servers of speed p Arrivals Configuration 2: 1 m Split arrivals into m queues m servers of speed p Arrivals Configuration 3: Try out the tutorial question! S1,2018 COMP9334 54 References • Recommended reading • Queues with Poisson arrival are discussed in • Bertsekas and Gallager, Data Networks, Sections 3.3 to 3.4.3 • Note: I derived the formulas here using continuous Markov chain but Bertsekas and Gallager used discrete Markov chain • Mor Harchal-Balter. Chapters 13 and 14