11Return to Queueing Theory• Build on the previous material– From single-hop queueing delay to end-to-end queueing delay– Overall delay experienced in routing a packet from source to destination node• Queueing Networks– Section 3.6 in text– Each queue represents a node which may have multiple input streams of “arrivals” from other nodes– Also, output stream may be split to multiple next-hop queues– Arrival process at one queue may depend on departure processes of multiple other queues, so probably is not Poisson– System is complex! What can be done?2Example• “Transmission line” model– Rate λarrivals over one link, fixed length packets• Service times are constant (equal to transmission delay 1/µ), so Q1 is M/D/1 (D means deterministic) Arrivals into Q2separated by at least 1/µ• If rate of second link is ≥ that of first link, there is NO waiting in the second queue EVER!– If packet lengths are iid exponential, this becomes M/M/1• How to characterize/analyze the second queue?Server ServerRate λ arrivalsQ1 Q22How to Evaluate Delay?– Setup:• Assume multiple packet streams each following a unique path• Let xsbe the arrival rate (in packets/second) for stream s • For circuit switching:– Arrivals on a link (i,j) occur with rate λijequal to summation of xsfor each stream s traversing (i,j)• For packet switching:– Include fraction fij(s) of packets in stream s traversing (i,j)Stream 13Kleinrock Independence Approximation• 1964: Kleinrock suggests that random merger of several packet streams into a single stream restores independence of arrival times and packet lengths• In particular, for densely connected networks with moderate-to-heavy traffic, inputs are approximately Poisson processesStream 1435Analysis under KIA• Average number of packets in queue or service:– For link (i,j), Nij= λij/ (µij–λij) where 1/µijis average transmit delay– Total packets in queue or service N is summation of Nijover all links (i,j)• Average queueing delay:– From Little’s Theorem, T = N/γ, where γis sum rate of all xsarrival streams• Including proc/prop delay dijat each (i,j):– Add the term λijdijin the summation6Time Reversibility• Let X be a DTMC, and let Xndenote the state at time n>>0. Let’s look at the behavior backward in time, instead of looking forward in time.• Let P*ijbe the reverse transition probability given by Pr[Xm= j | Xm+1= i].• Show that πiP*ij= πjPji• Def: A DTMC X is time reversible if P*ij= Pij. In this case, the stationary distribution of the reversed DTMC X*is the same as the forward chain X.– We immediately see that a DTMC X is time reversible if and only if the detailed balance equations hold.• This extends in a straightforward way to CTMCs.47Burke’s Theorem• Theorem (Burke): Consider an M/M/1, M/M/k, or M/M/∞ queue with arrival rate λ, and suppose the system starts in steady-state. Then:– The departure process is Poisson with rate λ.– The number of customers in the system at time t is independent of the sequence of departure times prior to t.• Why is this true?– M/M/1, M/M/k, and M/M/ ∞ are time reversible CTMCs.– Departures prior to time t are arrivals after time t in reversed process, which is Poisson, so future arrivals do not depend on system occupancy.8Example – Revisited• Returning to the previous example:– Suppose Q1 is M/M/1 with exp. service rate µ1.– From Burke’s Theorem, arrivals to Q2 are Poisson with rate λand exp. service rate µ2 M/M/1.– πn(i)= ρin(1-ρi), ρi= λ/µi, i=1,2– From 2ndpart of Burke’s Theorem, number of customers in each queue is independent, so Pr[n in Q1, m in Q2] = πn(1)πm(2)– This is a simple example of an acyclic queueing networkServer ServerRate λ arrivalsQ1 Q259Queueing Networks• Setup:– A network of K queues, each with a single server, service rate µiat queue i– Arrivals into the network at queue i follow a Poisson process with rate ri. At least one riis positive.– Customer served by queue i moves to queue j with probability Pij– leaves with residual probability– Total arrival rate into queue j is– Let ρj= λj/ µj10Queueing Network State Space• Let n = (n1,…,nK) denote a state in the state space XK, where X is the state space of each queue (here, the non-negative integers), i.e. ni= number of customers in queue i.• State transitions (with very high probability):– New arrival at queue j (with rate rj)• State n(j+) = n + ej= (n1,…,nj-1,nj+1,nj+1,…,nK)– Exit system from queue j (with rate )• State n(j-) = n – ej= (n1,…,nj-1,nj-1,nj+1,…,nK)– Customer moves from j to i (with rate µjPji)• State n(j-, i+) = n – ej+ ei611Jackson’s Theorem• Theorem (Jackson): For such a queueingnetwork, if ρj< 1 for j=1,…,K, then for all n=(n1,…,nK), nj>= 0, we have• In other words, queueing network behaves as independent collection of M/M/1 queues even though the arrival to each queue is not Poisson.12Closed Queueing Networks• Same setup as before, only ri=0 and Pijsum to 1 over j for all i=1,…,K, i.e. nobody enters and nobody leaves, soand total number of customers is fixed at M.• Here, πncan be positive only if n1+…+nK=