Lecture 7 Burkes Theorem and Networks of Queues Eytan Modiano Massachusetts Institute of Technolog
Lecture 7 Burke’s Theorem and Networks of Queues Eytan Modiano Massachusetts Institute of Technology Eytan Modiano Slide 1
口 Burkes theoren 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 n is a Poisson process of rate n 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 ndependent PLpast present, future]= P[past present =>PDX可a+1=,Xn+22]=Px到x-=P
�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[Xn=j |Xn+1 =i, Xn+2=i2,...] = P[Xn=j | Xn+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 (e.g, M/M/1(Pn)=(Pn+)u A Markov chain is reversible if P*j=Pi 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 Pi=p Pji All birth/death processes are reversible Detailed balance equations must be satisfied
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 piP*ij = pj Pji (e.g., M/M/1 (p n)λ=(pn+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 pi Pij=pj Pji • All birth/death processes are reversible – Detailed balance equations must be satisfied Eytan Modiano Slide 3
Implications of Burke's Theorem Arrivals time Departures 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 ty pe 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
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 t he state is independent of future arrivals Eytan Modiano Slide 4
NETWORKS OF QUEUES Exponential Exponential Poisson Poisson Poisson M/M/1 M/M/ ? The output process from an M/M/1 queue is a Poisson process of the same rate n as the input Is the second queue M/M/1?
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 Link 3. 4 p- arrival rate of packets along path p Let 2a=arrival rate of packets to link(,i) A,= 2X P traverses link (i,j) service rate on link(i,j
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, w hich doesn't change from queue to queue x2 1 3 2 4 x1 Link 3,4 • Xp = arrival rate of packets along path p • Let λij = arrival rate of packets to link (i,j) λij = ∑ Xp 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 N=Ave packets in network, T= Ave packet delay in network N=∑ =∑ X= total external arrival rate P ll path 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
Kleinrock approximation • Assume all queues behave as independent M/M/1 queues λij Nij = µij − λij • N = Ave. packets in network, T = Ave. packet delay in network λij N = Nij = i, j µij − λij N ∑ , T = λ λ = ∑XP = 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 Short packets Long packet 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
Slow truck effect Short packets Long packet 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 Pi Packet leaves system with probability 1 Packets can loop inside network Arrival rate at node i, + k ki External Internal arrivals from arrivals Other nodes Set of equations can be solve to obtain unique ns Service rate at node i= Hi
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 Pij – Packet leaves system with probability 1 −=∑j Pij – Packets can loop inside network • Arrival rate at node i, λi = ri +=∑k λk Pki 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 μ>>入 AP External input External input Internal inputs Y文t Customers are processed fast (u>>n Customers exit with probability(1-P) Customers return to queue with probability P A=r+Pλ>M=r/(1P) When P is large, each external arrival is followed by a burst of internal arrivals Arrivals to queues are not Poisson
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