Lecture 7
Burke’s Theorem and Networks of Queues
Eytan Modiano
Massachusetts Institute of Technology
Eytan Modiano
Slide 1
?Burke’s Theorem
? An interesting property of an M/M/1 queue, which greatly
simplifies combining these queues into a network, is the
surprising fact that the output of an M/M/1 queue with arrival rate λ
is a Poisson process of rate λ
– This is part of Burke's theorem, which follows from reversibility
? A Markov chain has the property that
– P[future | present, past] = P[future | present]
Conditional on the present state, future states and past states are
independent
P[past | present, future] = P[past | present]
=> P[X
n
=j |X
n+1
=i, X
n+2
=i
2
,...] = P[X
n
=j | X
n+1
=i] = P*
ij
Eytan Modiano
Slide 2
Burke’s Theorem (continued)
? The state sequence, run backward in time, in steady state, is a
Markov chain again and it can be easily shown that
p
i
P*
ij
= p
j
P
ji
(e.g., M/M/1 (p
n
)λ=(p
n+1
)μ)
? A Markov chain is reversible if P*ij = Pij
– Forward transition probabilities are the same as the backward
probabilities
– If reversible, a sequence of states run backwards in time is
statistically indistinguishable from a sequence run forward
? A chain is reversible iff p
i
P
ij
=p
j
P
ji
? All birth/death processes are reversible
– Detailed balance equations must be satisfied
Eytan Modiano
Slide 3
Implications of Burke’s Theorem
time
Arrivals
Departures
time
? Since the arrivals in forward time form a Poisson process, the
departures in backward time form a Poisson process
? Since the backward process is statistically the same as the forward
process, the (forward) departure process is Poisson
? By the same type of argument, the state (packets in system) left by a
(forward) departure is independent of the past departures
– In backward process the state is independent of future arrivals
Eytan Modiano
Slide 4
NETWORKS OF QUEUES
Exponential
Exponential
M/M/1
M/M/1
?
Poisson
λ λ
Poisson
Poisson
λ
? The output process from an M/M/1 queue is a Poisson process of
the same rate λ as the input
? Is the second queue M/M/1?
Eytan Modiano
Slide 5
Independence Approximation
(Kleinrock)
? Assume that service times are independent from queue to queue
– Not a realistic assumption: the service time of a packet is determined
by its length, which doesn't change from queue to queue
x
2
1
3
2
4
x
1
Link 3,4
? X
p
= arrival rate of packets along path p
? Let λ
ij
= arrival rate of packets to link (i,j)
λ
ij
=
∑
X
p
P traverses link (i, j)
? μ
ij
= service rate on link (i,j)
Eytan Modiano
Slide 6
Kleinrock approximation
? Assume all queues behave as independent M/M/1 queues
λ
ij
N
ij
=
μ
ij
?λ
ij
? N = Ave. packets in network, T = Ave. packet delay in network
λ
ij
N = N
ij
=
μ
ij
?λ
i, j ij
N
∑
, T =
λ
λ = X
P
= total external arrival rate
∑
all paths p
? Approximation is not always good, but is useful when accuracy of
prediction is not critical
– Relative performance but not actual performance matters
– E.g., topology design
Eytan Modiano
Slide 7
Slow truck effect
Long packet
Short packets
queue queue queue
? Example of bunching from slow truck effect
– long packets require long service at each node
– Shorter packets catch up with the long packets
? Similar to phenomenon that we experience on the roads
– Slow car is followed by many faster cars because they
catch up with it
Eytan Modiano
Slide 8
Jackson Networks
? Independent external Poisson arrivals
? Independent Exponential service times
– Same job has independent service time at different queues
? Independent routing of packets
– When a packet leaves node i it goes to node j with probability P
ij
– Packet leaves system with probability
1 ?=
∑
j
P
ij
– Packets can loop inside network
? Arrival rate at node i,
λ
i
= r
i
+=
∑
k
λ
k
P
ki
External Internal arrivals from
arrivals Other nodes
– Set of equations can be solve to obtain unique λ
i
’s
– Service rate at node i = μ
i
Eytan Modiano
Slide 9
Jackson Network (continued)
r
(1?P) λ
μ >> λ=
+
x
λ=
λP
External input
Internal inputs
External input
? Customers are processed fast (μ >> λ)=
? Customers exit with probability (1-P)
– Customers return to queue with probability P
– λ== r + Pλ==> λ== r/(1-P)
? When P is large, each external arrival is followed by a burst of
internal arrivals
– Arrivals to queues are not Poisson
Eytan Modiano
Slide 10
Jackson’s Theorem
v
? We define the state of the system to be
n = (n
1
, n
2
L n
k
)
where n
i
is the number of customers at node i
? Jackson's theorem:
i =k i =k
n
i
P(n
v
) =
∏=
P
i
( n
i
)=
∏
ρ
i
(1 ?=ρ
i
), where ρ
i
=
λ
i
i 1 i 1
μ
i
? That is, in steady state the state of node i (n
i
) is independent of the
states of all other nodes (at a given time)
– Independent M/M/1 queues
– Surprising result given that arrivals to each queue are neither
Poisson nor independent
– Similar to Kleinrock’s independence approximation
– Reversibility
Exogenous outputs are independent and Poisson
The state of the entire system is independent of past exogenous departures
Eytan Modiano
Slide 11
Example
λ
1
λ
2
r
μ
1
μ
2
3/8
2/83/8
λ
1
= ?
λ
2
= ?
P(n
1
,n
2
) = ?
Eytan Modiano
Slide 12