Basic Queueing Theory

M/M/-/- Type Queues

Copyright 2002, Sanjay K. Bose 1

Kendall’s Notation for Queues

A/B/C/D/E

Shorthand notation where A, B, C, D, E describe the queue

Applicable to a large number of simple queueing scenarios

Copyright 2002, Sanjay K. Bose 2

1
Kendall’s Notation for Queues A/B/C/D/E

M exponential
A Inter-arrival time distribution D deterministic
B Service time distribution Ek Erlangian (order k)
G general
C Number of servers
D Maximum number of jobs that can be there in the
system (waiting and in service)
Default ∞ for infinite number of waiting positions
E Queueing Discipline (FCFS, LCFS, SIRO etc.)
Default is FCFS

M/M/1 or M/M/1/∞ Single server queue with Poisson arrivals,

exponentially distributed service times and infinite number of
waiting positions
Copyright 2002, Sanjay K. Bose 3

Little’s Result

N=λW (2.9)

Nq=λWq (2.10)

Result holds in general for virtually all types of queueing

situations where
λ = Mean arrival rate of jobs that actually enter the system

Jobs blocked and refused entry into the system will not be
counted in λ

Copyright 2002, Sanjay K. Bose 4

2
Little’s Result

α(t), Arrivals in (0,t)

β(t), Departures in (0,t)
Number of customers
(arrivals/departures)
N
(t

increments by
one

Time t

Graphical Illustration/Verification of Little's Result

Copyright 2002, Sanjay K. Bose 5

Little’s Result

Consider the time interval (0,t) where t is large, i.e. t→∞

t

Area(t) = area between α(t) and β(t) at time t = [α (t ) − β (t )]dt ∫

0

Area(t )
Average Time W spent in system = lim t →∞
α (t )

Area (t ) α (t ) Area (t )
Average Number N in system = lim t → ∞ = lim t →∞
t t α (t )

α (t )
Since, λ = lim t → ∞ Therefore, N= λW
t

Copyright 2002, Sanjay K. Bose 6

3
The PASTA “Poisson Arrivals See Time Averages”
Property
pk(t) =P{system is in state k at time t }
qk(t) =P{an arrival at time t finds the system in state k}
N(t) be the actual number in the system at time t
A(t, t+∆t) be the event of an arrival in the time interval (t, t+∆t)

qk (t ) = lim ∆t →0 P{N (t ) = k | A(t , t + ∆t}

Then P{A(t , t + ∆t | N (t ) = k |}P{N (t ) = k }
= lim ∆t →0 = p k (t )
P{A(t , t + ∆t}

because P{A(t, t+∆t)|N(t) = k} = P{A(t, t+∆t)}

Copyright 2002, Sanjay K. Bose 7

Equilibrium Solutions for M/M/-/- Queues

Method 1: Obtain the differential-difference equations as in Section 1.2

or Section 2.2. Solve these under equilibrium conditions along with the
normalization condition.

Method 2: Directly write the flow balance equations for proper choice
of closed boundaries as illustrated in Section 2.2 and solve these along
with the normalization condition.

Method 3: Identify the parameters of the birth-death Markov chain for

the queue and directly use equations (2.7) and (2.8) as given in Section
2.2.
In the following, we have used this approach

Copyright 2002, Sanjay K. Bose 8

4
 ∞ ) Queue
M/M/1 (or M/M/1/∞
For ρ <1
λk = λ ∀k k
λ
p k = p0   = p0 ρ k
µk = 0 k =0 µ
=µ k = 1, 2, 3,....... p0 = (1 − ρ )

∞ ∞ Using
ρ N 1
N= ∑ ip =∑ iρ (1 − ρ ) = 1 − ρ
i =0
i
i =0
i W= =
λ µ (1 − ρ )
Little’s
Result

1 ρ ρ2 Using
Wq = W − = N q = λWq = Little’s
µ µ (1 − ρ ) (1 − ρ )
Result

Copyright 2002, Sanjay K. Bose 9

∞ Queue with Discouraged Arrivals

M/M/1/∞

λ For ρ = λ/µ < ∞

λk = ∀k k −1 k
k +1 λ λ 1
p k = p0 ∏
i = 0 µ (i + 1)
= p0  
 µ  k!
(2.14)

µk = 0 k =0 λ
p0 = exp(− ) (2.15)
=µ k = 1, 2, 3,....... µ
∞
∞  λ 
N= ∑
k =0
kpk =
λ
µ
λeff = ∑λ
k =0
k p k = µ 1 − exp(− ) 
 µ 
N λ
W= = Little’s Effective Arrival
λeff  λ 
µ 2 1 − exp(− )  Result Rate
 µ 

Copyright 2002, Sanjay K. Bose 10

5
M/M/1/∞ Queue with Discouraged Arrivals

In this case, PASTA is not applicable as the overall arrival process is

not Poisson
i
λ 1
πr = P{arriving customer sees r in system P{Ei } = pi = e − λ / µ  
 µ  i!
(before joining the system)}
∆E be the event of an arrival in (t, t+∆t) λ∆t
Ei is the event of the system being in state i P{∆E | Ei } = i + 1
P{E r }P{∆E | Er } P{E }P{∆E | Er }
π r = P{Er | ∆E} = = ∞ r
P{∆E}
∑
P{Ei }P{∆E | Ei }
i =0
r +1
λ 1  e −λ / µ  ∞
k +1 λ
π r =  
µ

( r + 1)!  1 − e − λ / µ



W= ∑
k =0 µ
πk = 2
µ (1 − e −λ / µ )

Copyright 2002, Sanjay K. Bose 11

M/M/m/∞ ∞ Queue (m servers, infinite number of waiting

positions)

λk = λ ∀k µ k = kµ 0 ≤ k ≤ (m − 1)
= mµ k ≥m

ρk
For ρ = λ/µ < m pk = p0 for k≤m
k!
(2.16)
ρk
= p0 for k > m
Erlang’s m!m k −m
C-Formula −1
 m −1 ρ k mρ m 
p0 =  ∑ + 

 k =0 k! m!(m − ρ ) 
(2.17)

∞
mρ m
P{queueing} = ∑
k =m
p k = C ( m , ρ ) = p0
m!( m − ρ )
(2.18)

Copyright 2002, Sanjay K. Bose 12

6
M/M/m/m Queue (m server loss system, no waiting)

λk = λ k<m
=0 otherwise ( Blocking or Loss Condition )
µ k = kµ 0≤ k ≤m
=0 otherwise
ρk
pk = p0 for k≤m
For k! (2.19)
=0 otherwise
λ
ρ= <∞ 1
µ p0 = (2.20)
m
ρk
∑
k = 0 k!

Copyright 2002, Sanjay K. Bose 13

M/M/m/m Queue (m server loss system, no waiting)

Simple model for a telephone exchange where a line is given only

if one is available; otherwise the call is lost

Blocking Probability B(m,ρ) = P{an arrival finds all servers busy

and leaves without service}

ρm
B (m, ρ ) = p0 Erlang’s B-Formula (2.21)
m!
ρB (m − 1, ρ )
B(m, ρ ) = m
B(0, ρ ) = 1 ρB (m − 1, ρ )
(2.22)
1+
m

Copyright 2002, Sanjay K. Bose 14

7
M/M/1/K Queue (single server queue with K-1 waiting
positions)
λk = λ k<K
=0 otherwise ( Blocking or Loss Condition )
µk = µ k≤K
=0 otherwise

pk = p0 ρ k for k≤K (2.23)

For
=0 otherwise
λ
ρ = <∞ (1 − ρ )
µ p0 = (2.24)
(1 − ρ K +1 )

Copyright 2002, Sanjay K. Bose 15

M/M/1/-/K Queue (single server, infinite number of

waiting positions, finite customer population K)
λk = λ (K − k ) k<K
=0 otherwise ( Blocking or Loss Condition )
µk = µ k≤K
=0 otherwise

K!
pk = p0 ρ k k=1,.….,K (2.25)
For ( K − k )!
λ 1
ρ= <∞ p0 = (2.26)
µ K

∑
K!
ρ k

k =0 ( K − k )!

Copyright 2002, Sanjay K. Bose 16

8
 ∞ Queue
Delay Analysis for a FCFS M/M/1/∞
(Section 2.6.1)

Q: Queueing Delay (not counting service time for an arrival

pdf fQ(t), cdf FQ(t), LQ(s) = LT(fQ(t)}

W=Q+T W: Total Delay ( waiting time and service time) for an arrival
pdf fW(t), cdf FW(t), LW(s) = LT(fW(t)}

T: Service Time
µ
f T (t ) = µe − µ t FT (t ) = e − µ t LT ( s) =
(s + µ )
Since µ
LW ( s ) = LQ ( s) fW (t ) = f Q (t ) * [ µe − µt ] (2.30)
Q⊥T (s + µ )
Knowing the distribution of either W or Q, the distribution of the
other may be found

Copyright 2002, Sanjay K. Bose 17

For a particular arrival of interest -

FQ(t) = P{queueing delay ≤ t}
= P{queueing time=0} + [Σn≥1 P{queueing time≤ t | arrival found
n jobs in system}]pn Erlang-n distribution for
∞
sum of n exponential r.v.s
µ ( µx ) n −1 − µx
t
FQ (t ) = (1 − ρ ) + (1 − ρ )∑ ρ ∫n
e dx
n =1 x =0
( n − 1)!
∞
( µxρ ) n −1
t

∫
= (1 − ρ ) + (1 − ρ ) ρ µe − µx ∑
n =1 (n − 1)!
dx (2.31)
0
t

∫
= (1 − ρ ) + (1 − ρ ) ρ µe − µx (1− ρ ) dx = (1 − ρ ) + ρ (1 − e − µt (1− ρ ) )
0
dFQ (t )
f Q (t ) = = δ (t )(1 − ρ ) + λ (1 − ρ )e − µt (1− ρ ) (2.32)
dt t

∫
fW (t ) = (1 − ρ ) µe − µt + λ (1 − ρ ) µ e − µ (1− ρ )( t − x ) e − µx dx = ( µ − λ ) e − ( µ − λ ) t
0

Copyright 2002, Sanjay K. Bose 18

9
 Departure of
customer of
interest
• PASTA applicable to this
Time spent in system by the
customer of interest queue
• N and NQ seen by an arrival
same as the time-averaged
values
Arrival of Arrivals coming while the
customer customer of interest is in the
of interest system

Arrival/Departure of Customer/Job of
Interest from a FCFS M/M/1Queue

Let
N* = Number in the system that a job will see left behind when it departs
pn*=P{N*=n} for N*=0, 1,....,∞

Copyright 2002, Sanjay K. Bose 19

Departure of
customer of
interest
Time spent in system by the For a FCFS queue, number left
customer of interest
behind by a job will be equal
to the number arriving while it
is in the system.
Arrival of Arrivals coming while the
customer customer of interest is in the
of interest system

∞ ∞ ∞
(λt ) n −λt
G* ( z) = ∑
n=0
z n pn* = ∑ ∫
n=0
zn
n!
e fW (t )dt (2.36)
t =0
∞

∫
= e −λt (1− z ) f W (t ) dt = LW (λ − λz )
0

dG * ( z ) dLW (s ) (2.37)
E{N * } = = −λ = λW
dz z =1
ds s = 0

Copyright 2002, Sanjay K. Bose 20

10
 An important general observation can also be made along the lines
of Eq. (2.36).

Consider the number arriving from a Poisson process with rate λ

in a random time interval T where LT(s)=LT{fT(t)}. The generating
function G(z) of this will be given by

G ( z ) = LT (λ − λz )

and the mean number will be E{N}= λ E{T}

This result will be found to be useful in various places in our

subsequent analysis.

Copyright 2002, Sanjay K. Bose 21

∝ Queue
Delay Analysis for the FCFS M/M/m/∝
(Section 2.6.2)

Using an approach similar to that used for the M/M/1 queue, we obtain
the following

  mρ m    µp0 ρ me − µ ( m − ρ ) t 
f Q (t ) = 1 − p0   δ (t ) +   u (t ) (2.34)
  m!( m − ρ )    (m − 1)! 

  mρ m   − µt  µp0 ρ m [e − µ ( m − ρ )t − e − µt ] 
fW (t ) = 1 − p0    µe −   (2.35)
  m!( m − ρ )    (m − 1)!(1 − m − ρ ) 

See Section 2.6.2 for the details and the intermediate steps

Copyright 2002, Sanjay K. Bose 22

11