Lesson 68 · Special topics: queueing theory

The M/M/1 queue: why delay explodes near full load

Packets arrive at random and wait for one link to send them. The M/M/1 model turns that into two short formulas, L = ρ/(1−ρ) and W = 1/(μ−λ). Turn the load up from 50% to 99% and watch the average delay climb from 2 to 100 service times, then see why networks keep headroom.

12 min11 steps5 questionsAdvanced

Fig 68 · Interactive

Loading figure…

or ← →

Check yourself

5 quick questions

Pick an answer to see why. Your score saves with your progress.

01A link can send μ = 1,000 packets per second and packets arrive at λ = 800 per second. What is the load ρ?

ρ = λ/μ = 800 / 1,000 = 0.8. The link is busy 80% of the time.

02In that same M/M/1 queue (λ = 800/s, μ = 1,000/s), what is the average time a packet spends in the system?

W = 1/(μ − λ) = 1/(1,000 − 800) s = 1/200 s = 5 ms, five times the 1 ms service time.

03Load rises from ρ = 0.9 to ρ = 0.99. Roughly what happens to the average delay W?

W in service times is 1/(1−ρ): 1/0.1 = 10 at 0.9 and 1/0.01 = 100 at 0.99. About 10% more traffic makes delay ten times longer.

04What happens in an M/M/1 queue when packets arrive faster than the server can send them (ρ > 1)?

With ρ > 1 there is no steady state: on average the line grows by λ − μ packets per second. A real buffer fills, adds a long delay (bufferbloat) and then drops new arrivals.

05Why do network operators keep average link load well below 100%?

Spare capacity (1−ρ) is what drains random bursts. At 50% load W is 2 service times; at 99% it is 100.

Key terms

Glossary

M/M/1: Kendall notation for a queue with Poisson (memoryless) arrivals, exponentially distributed service times and one server, with one first-in, first-out line of unlimited length.
Arrival rate λ (lambda): The average number of packets that arrive per second.
Service rate μ (mu): The average number of packets the server can send per second when it is busy. The mean service time is 1/μ.
Utilisation ρ (rho): The load: ρ = λ/μ, the fraction of time the server is busy. The queue is stable only while ρ < 1.
L and W: L is the average number of packets in the system (waiting plus being sent); W is the average time each spends there. For M/M/1, L = ρ/(1−ρ) and W = 1/(μ−λ).
Little's law: L = λW: the average number in a system equals the arrival rate times the average time spent there. It holds for almost any stable queue.
Steady state: The long-run behaviour of a queue once averages stop changing. An M/M/1 queue has one only when ρ < 1.
Bufferbloat: Too much buffering for a link's speed: when the link is overloaded the queue grows long and adds large delay before any packet is dropped.

Fine print

Notes and sources

The 10 Mb/s link and the 1,250-byte average packet (so 1 ms per packet and μ = 1,000/s) are illustrative, as is the 1,000-packet buffer; every other number follows from the M/M/1 formulas.
The tray draws at most 8 waiting envelopes plus the one being sent; the count gives the real average number in the system.
L and W are long-run averages. At any moment the line may be empty or much longer: at ρ = 0.9 the chance of finding 10 or more packets already there is about 35%.
Real packet sizes are not exponential. With Poisson arrivals and any service time distribution (M/G/1), the Pollaczek–Khinchine formula still has 1/(1−ρ) in it: equal-size packets (M/D/1) wait half as long in the line, but delay explodes the same way.
Real traffic is also burstier than Poisson over long time scales (Leland et al., 1994), which makes queues near full load even longer than M/M/1 predicts.
ρ is the offered traffic in erlangs (ITU-T E.600). One server can carry at most 1 erlang; the multi-server case is Erlang C (M/M/c).

Quiz Unlocks after the last step.