Networks of queues and real traffic
A packet crosses a queue at every router hop. Model each hop as an M/M/1 queue, use Jackson's theorem to chain three of them, and add up the delay. Then see the tail (p99), what bursty real traffic does to the answer, and why a little spare capacity removes most of the delay.
5 quick questions
Pick an answer to see why. Your score saves with your progress.
01Packets arrive at 8,000 per second and the link can send 10,000 per second (M/M/1). How long does a packet spend at this hop on average?
T = 1 / (μ − λ) = 1 / (10,000 − 8,000) s = 1/2,000 s = 0.5 ms. That is 0.4 ms waiting plus 0.1 ms being sent.
02Why can we simply add the delays of the three hops in a Jackson network?
Burke's theorem says an M/M/1 queue's departures are Poisson again, and Jackson's theorem says each node then behaves like its own M/M/1 queue. Mean delays add up: 0.5 + 0.5 + 0.5 = 1.5 ms.
03Traffic grows from 8,000 to 9,500 packets/s on 10,000 packets/s links. What happens to the mean delay over three hops?
Each hop goes from 1/2,000 s = 0.5 ms to 1/500 s = 2 ms, so three hops go from 1.5 ms to 6 ms: four times longer for 19% more traffic. Near full utilisation, delay grows very fast.
04What does p99 latency mean?
p99 is the 99th percentile: 99 packets in 100 arrive faster, 1 slower. Over three M/M/1 hops at ρ 0.8 the mean is 1.5 ms but the p99 is 4.2 ms.
05Real traffic arrives in bursts. Compared with the M/M/1 answer at the same utilisation, the waiting time is usually...
Kingman's formula shows the wait grows with how uneven the gaps between arrivals are. With gaps twice as uneven as Poisson (ca² = 4), the wait at ρ 0.8 is 2.5 times the M/M/1 value: 1.0 ms instead of 0.4 ms.
Glossary
- Utilisation (ρ)
- The fraction of time a link is busy: arrival rate divided by the rate it can send, ρ = λ / μ. It must stay below 1 or the queue grows without limit.
- Poisson arrivals
- Arrivals at random moments, independent of each other, at a steady average rate; the gaps between them follow an exponential distribution.
- M/M/1 queue
- A queue with Poisson arrivals, exponential service times and one server. Mean time in the system is 1 / (μ − λ).
- Little's law
- Average number in a system = arrival rate × average time each spends there (L = λT). It holds for almost any queue.
- Jackson network
- A network of exponential-service queues with Poisson outside arrivals and random routing; each node then behaves like its own M/M/1 queue (Jackson, 1957).
- Tandem queues
- Queues in a row, where everything that leaves one goes into the next, like the router hops along a path.
- Tail latency (p99)
- The delay that 99% of packets or requests beat. It shows the slow cases that averages hide.
- Headroom
- Spare capacity kept on purpose so utilisation stays well below 1, which keeps queues and delay short.
Notes and sources
- The 1,250-byte mean packet, the traffic rates and ca² = 4 are illustrative; every other number follows from them with the formulas shown.
- M/M/1 and Jackson assume Poisson arrivals, exponential service times, first-in first-out service and buffers that never overflow. Real packet sizes are not exponential and a packet keeps its size at every hop; Kleinrock's independence approximation treats them as fresh at each hop, which works well when many flows mix.
- Adding p99s hop by hop is wrong in general: the p99 of a sum is less than the sum of the p99s. The Erlang-3 result needs independent hop times, which tandem M/M/1 queues have (Reich, 1957) but general Jackson networks with feedback do not.
- Each tray draws at most 5 envelopes; the meter gives the real average number waiting.
- The delays here are waiting plus sending at each hop; propagation along the cables and processing inside the routers add a fixed amount on top.
- Utilisation measured as a 5-minute average can look calm while short bursts fill the queues, which is why operators also watch queue drops and percentile delay.
- J. R. Jackson, Networks of Waiting Lines, Operations Research 5(4), 1957
- P. J. Burke, The Output of a Queuing System, Operations Research 4(6), 1956
- J. D. C. Little, A Proof for the Queuing Formula L = λW, Operations Research 9(3), 1961
- J. F. C. Kingman, The single server queue in heavy traffic, Proc. Cambridge Phil. Soc. 57(4), 1961
- Leland, Taqqu, Willinger and Wilson, On the Self-Similar Nature of Ethernet Traffic, IEEE/ACM ToN 2(1), 1994
- Paxson and Floyd, Wide Area Traffic: The Failure of Poisson Modeling, IEEE/ACM ToN 3(3), 1995
- MIT OpenCourseWare 6.263J Data Communication Networks (Bertsekas and Gallager, Data Networks, ch. 3)
- M. Harchol-Balter, Performance Modeling and Design of Computer Systems (Cambridge University Press, 2013)
Quiz Unlocks after the last step.