Queues everywhere: arrivals, service and waiting
A router port, a supermarket checkout and a web server are the same machine: customers arrive, wait in line and are served. Watch packets arrive at rate λ and leave at rate μ, see why random arrivals queue even when the link is often idle, why waits soar as utilisation nears 1, and how engineers name queues with Kendall's A/S/c.
5 quick questions
Pick an answer to see why. Your score saves with your progress.
01A link sends 1,500-byte packets at 12 Mb/s. What is its service rate μ?
One packet is 1,500 × 8 = 12,000 bits. At 12,000,000 bits per second it takes 1 ms to send, so the link can serve 1,000 packets per second.
02Packets arrive at 900 per second at a server that can handle 1,000 per second. What is the utilisation ρ?
ρ = λ ÷ μ = 900 ÷ 1,000 = 0.9. The server is busy 90% of the time on average and idle 10%.
03Arrivals are 1,500 per second and one server handles 1,000 per second. What happens to the line?
When λ is larger than μ, more arrive than can leave: 1,500 − 1,000 = 500 extra packets join the line each second. It grows without limit until the buffer fills and packets are dropped.
04Why do packets wait at all when utilisation is only 0.6?
With perfectly even arrivals nobody would wait. Real arrivals bunch up, so a packet that arrives while another is being sent has to wait. For an M/D/1 queue at ρ = 0.6 and 1 ms service the average wait is 0.75 ms.
05In Kendall notation, what does M/D/2 describe?
A/S/c lists the arrival pattern, the service pattern and the number of servers. M is memoryless (random, Poisson) arrivals, D is deterministic (fixed) service time, and 2 is the number of servers.
Glossary
- Queueing system
- Customers that arrive, a line where they wait, and one or more servers that serve them. Packets at a router port, shoppers at tills and requests at a web server all fit.
- Arrival rate λ (lambda)
- How many customers arrive per second on average. The mean gap between arrivals is 1 ÷ λ.
- Service rate μ (mu)
- How many customers one server can finish per second when it is never idle: 1 ÷ the service time.
- Utilisation ρ (rho)
- The fraction of time the servers are busy: λ ÷ (c × μ) for c servers. A queue is stable only when ρ is below 1.
- Stable queue
- A queue whose line stays finite on average. If arrivals reach or pass the servers' capacity, the line grows without limit.
- Kendall notation
- A short name A/S/c for a queue: arrival pattern / service pattern / number of servers, for example M/M/1 or M/D/2.
- M, D and G
- Letters used in Kendall notation: M = memoryless (random, Poisson arrivals or exponential service), D = deterministic (fixed), G = general (any pattern).
Notes and sources
- The 12 Mb/s link and the arrival rates of 600, 900 and 1,500 packets per second are illustrative round numbers; every packet is 1,500 bytes (the Ethernet MTU), so service takes exactly 1 ms.
- The waits for random arrivals use the Pollaczek-Khinchin formula for an M/D/1 queue (Bertsekas and Gallager, Data Networks, §3.5). With random packet sizes (M/M/1) they would be twice as long: 1.5 ms at ρ = 0.6.
- The animation shows one short stretch of arrivals; queue lengths in it come and go, while the meter gives long-run averages.
- The tray draws at most 8 envelopes.
- A real buffer is finite: in overload the line fills it and the router drops new arrivals (tail drop), so the delay stops growing but packets are lost.
- Bertsekas and Gallager, Data Networks (2nd ed.), ch. 3: Delay Models in Data Networks
- D. G. Kendall (1953), Stochastic Processes Occurring in the Theory of Queues, Annals of Mathematical Statistics 24(3)
- L. Kleinrock, Queueing Systems, Volume 1: Theory (Wiley, 1975)
- M. Harchol-Balter, Performance Modeling and Design of Computer Systems (Cambridge, 2013)
- MIT OpenCourseWare 6.262: Discrete Stochastic Processes
Quiz Unlocks after the last step.