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