[Intermediate] — Why waiting lines behave as they do: Little’s law, the M/M/1 and M/M/c queues, why waiting explodes as utilisation approaches 100%, and why one shared queue beats several separate ones. The note that explains your server’s latency graph.

Source: [reference] — see the domain note. The code below was run and its output checked.

Before you start

You should know what a probability distribution and its mean are → random variables and distributions. Knowing what a Markov chain is helps but isn’t required → Markov chains.

After this lesson you will be able to:

  1. Use Little’s law to get one of (number in system, arrival rate, time in system) from the other two, for any stable system.
  2. Compute waiting times for M/M/1 and M/M/c queues.
  3. Explain, with numbers, why waiting time blows up as utilisation approaches 1, and why pooling servers helps.
  4. Say how variability in arrivals and service changes waiting, and what that means for capacity planning.

Study route: sections 1–3, then stop and do check question 1. Then M/M/c and pooling (section 5), variability, and the code.

The kid version

At a school tuck shop, one person serves and each customer takes about a minute. If a customer arrives every two minutes, there’s hardly ever a queue. If one arrives every 70 seconds, sometimes two turn up close together and a small queue forms, then clears. But if one arrives every 62 seconds, the server is busy almost all the time, and whenever a little bunch of customers arrives, the queue has no time to clear before the next bunch. Queues don’t grow steadily as a shop gets busier. They stay small, then suddenly get huge as the server gets close to never resting.

Where the analogy stops working. It sounds like it’s about averages: “the server can handle it, on average”. But queues are caused by randomness — customers bunching up and some taking longer than others. A perfectly regular shop with a customer exactly every 62 seconds would never have a queue at all.

1. Why this exists

Queues are everywhere: bank tellers, call centres, hospital beds, toll booths — and in software, request handlers, thread pools, database connection pools, message brokers and CPU run queues. The questions are always the same:

  1. How long will people (or requests) wait?
  2. How many servers do we need to keep waits below a target?
  3. What happens when demand rises 10%?

The simple approach is to compare average capacity with average demand: “we can serve 10 an hour and get 8, so we’re fine.” Queueing theory shows why that reasoning fails: at 80% utilisation the average customer already spends five times the service time in the system, and at 95% it’s twenty times.

Terms used in queueing theory

  1. Arrival rate: This is the average number of arrivals per unit time, written (lambda). 8 customers an hour means .
  2. Service rate: This is the average number of customers one server can finish per unit time, written (mu). A service taking 6 minutes on average means per hour.
  3. Server: This is whatever does the work — a cashier, a CPU core, a worker thread. is the number of servers.
  4. Utilisation: This is also known as traffic intensity or load. Written (rho), it’s the fraction of time a server is busy: . A queue is only stable — doesn’t grow forever — when .
  5. Poisson arrivals: This means arrivals happen independently and at random at a steady average rate, so the time between them follows an exponential distribution. Many independent customers each deciding on their own give approximately Poisson arrivals.
  6. Memoryless: The exponential distribution is memoryless: how long you’ve already waited tells you nothing about how much longer it’ll be. This property is what makes the M/M/1 formulas simple.
  7. Kendall notation: This is the shorthand A/S/c for queue types: arrival process / service distribution / number of servers. M means Markovian (Poisson arrivals or exponential service), D means deterministic (fixed), G means general (any distribution).
  8. , , , : is the average number in the system (queueing plus being served); is the average number queueing. is the average time in the system; is the average time queueing. So .
  9. Steady state: This is the long-run behaviour after the effect of the starting conditions has faded. The formulas in this note describe steady state.

2. Little’s law

Little’s law states that, for any stable system, the average number of items in it equals the arrival rate multiplied by the average time each item spends in it.

It holds for any arrival pattern, any service distribution, any number of servers, and any queue discipline. It’s as close to a conservation law as queueing has.

Using it. A coffee shop has 6 customers inside on average and serves 30 an hour. Then each customer spends hours, 12 minutes, inside — measured without timing anyone.

In software: a service handles 500 requests per second with an average latency of 40 ms. Then on average requests are in flight. If the thread pool has 16 threads, requests must be queueing somewhere. Little’s law is the fastest sanity check for concurrency settings.

It also applies to just the queue (), or just the servers ( busy servers on average).

3. The M/M/1 queue

One server, Poisson arrivals at rate , exponential service at rate , first-come first-served, unlimited waiting room. The results, for :

Where they come from, in words. Track the number in the system as a Markov chain: it goes up by one at rate and down by one at rate . In steady state, the flow from ” in system” up to "" must equal the flow back down, so . That makes the probabilities geometric: . The mean of that distribution is , which is , and Little’s law gives .

A worked example

A help desk gets calls an hour; each takes 6 minutes on average, so per hour.

  1. Utilisation: . The agent is busy 80% of the time.
  2. Average number in system: .
  3. Average time in system: hours, 30 minutes. Check with Little’s law: . ✓
  4. Average wait before being served: hours, 24 minutes — four times the 6-minute call itself.

Pause and predict: calls rise to 9 an hour (12.5% more). What happens to ?

hour. 12.5% more demand doubled the time in the system. At 9.5 calls an hour, it’s 2 hours.

4. Why utilisation is a cliff

Write as a multiple of the service time :

Utilisation 0.50.70.80.90.950.99
Time in system ÷ service time23.351020100
 time in system, in multiples of the service time (one █ = 1×)

 ρ = 0.50  ██                       2×
 ρ = 0.70  ███                      3.3×
 ρ = 0.80  █████                    5×
 ρ = 0.90  ██████████               10×
 ρ = 0.95  ████████████████████     20×
 ρ = 0.99  ███████████████████…     100× — off the chart

The relationship is : flat at first, then vertical. This is the most important picture in capacity planning:

  1. “We’re only at 85% CPU” is not comfortable for a latency-sensitive service. Small surges push it into the steep part.
  2. The last 10% of utilisation costs the most latency. Running at 70% instead of 90% roughly triples the headroom against surges.
  3. It’s why autoscalers target 50–70%, not 95% → control theory explains why they oscillate as well.

5. Multiple servers and pooling

The M/M/c queue

identical servers share one queue. The formula for the probability that an arrival has to wait is the Erlang C formula, from A. K. Erlang’s 1917 work on telephone exchanges. With (the average number of busy servers) and :

Then (Little) and . Call centres size their staff with exactly these formulas.

Three designs with the same total capacity

The help desk still gets 8 calls an hour. Compare three designs, each able to handle 10 calls an hour in total:

  1. One fast agent (): from section 3, hours.
  2. Two slower agents sharing one queue ( each, M/M/2). , . . . . h, h.
  3. Two slower agents, each with their own queue, calls split evenly (two M/M/1 with , ): hour.
DesignTime in system
One fast server30 min
Two slow servers, one shared queue33 min
Two slow servers, separate queues60 min

Two lessons:

  1. Pooling nearly halves the wait. With separate queues, one agent can sit idle while the other has a line. A shared queue never wastes an idle server. That’s why banks and airports use a single snake queue, and why a shared work queue beats pinning requests to a worker.
  2. One fast server beats several slow ones for total time, because when there are few customers, the fast server finishes each one sooner. But the gap is small, and two servers give resilience if one fails.

6. Variability is the enemy

The M/M formulas assume exponential service times, which are highly variable. What if every call took exactly 6 minutes (M/D/1)?

The Pollaczek–Khinchine formula handles any service distribution (M/G/1). With the coefficient of variation of service time (standard deviation ÷ mean):

For exponential service, , which gives the M/M/1 result. For fixed service, , halving the queue. For very variable service — most calls quick, a few very long — can be 3 or more, and queues are five times worse than M/M/1.

So there are two levers on waiting time: utilisation and variability. Reducing either works. In software terms: cutting tail latency (a few slow requests) shortens the queue for everyone, which is why one slow query can degrade a whole service.

Worked example — the formulas in Python

Runnable, standard library only.

# queues.py — note 12: M/M/1 and M/M/c formulas, and the price of high utilisation
from math import factorial
 
def mmc(lam, mu, c):
    """Return (utilisation, P(wait), Lq, Wq, W) for an M/M/c queue."""
    a, rho = lam / mu, lam / (c * mu)
    if rho >= 1:
        raise ValueError("unstable: arrivals at least as fast as total service")
    tail = a ** c / (factorial(c) * (1 - rho))
    p0 = 1 / (sum(a ** n / factorial(n) for n in range(c)) + tail)
    p_wait = tail * p0                        # Erlang C formula
    lq = p_wait * rho / (1 - rho)
    wq = lq / lam                             # Little's law on the queue
    return rho, p_wait, lq, wq, wq + 1 / mu
 
print("one fast server   (M/M/1, mu=10):", [round(x, 3) for x in mmc(8, 10, 1)])
print("two slow, pooled  (M/M/2, mu=5): ", [round(x, 3) for x in mmc(8, 5, 2)])
print("two slow, separate (each M/M/1, lam=4, mu=5): W =", round(mmc(4, 5, 1)[4], 3))
print()
for rho in (0.5, 0.7, 0.8, 0.9, 0.95, 0.99):
    w = mmc(rho * 10, 10, 1)[4]
    print(f"utilisation {rho:.2f}: time in system = {w / 0.1:5.1f} x the service time")
python3 queues.py

Expected output:

one fast server   (M/M/1, mu=10): [0.8, 0.8, 3.2, 0.4, 0.5]
two slow, pooled  (M/M/2, mu=5):  [0.8, 0.711, 2.844, 0.356, 0.556]
two slow, separate (each M/M/1, lam=4, mu=5): W = 1.0

utilisation 0.50: time in system =   2.0 x the service time
utilisation 0.70: time in system =   3.3 x the service time
utilisation 0.80: time in system =   5.0 x the service time
utilisation 0.90: time in system =  10.0 x the service time
utilisation 0.95: time in system =  20.0 x the service time
utilisation 0.99: time in system = 100.0 x the service time

For M/M/1, , which is why the first line shows 0.8 twice.

Common pitfalls and traps

  1. Planning on averages. “Capacity 10, demand 8, fine” ignores randomness. The queue at 80% utilisation is already large.
  2. Forgetting . At there’s no steady state — the queue grows without limit, and the formulas give nonsense (negative waits).
  3. Assuming exponential everything. Real service times are often more variable (heavy tails), real arrivals often burstier. M/M formulas can then be optimistic.
  4. Steady state that never arrives. A lunchtime rush lasting 30 minutes may never reach steady state. Simulation (note 14) handles time-varying demand better.
  5. Separate queues by accident. Sharding requests to workers by hash creates separate queues. Pooling the work usually cuts latency for the same hardware.
  6. Little’s law on the wrong boundary. , and must all describe the same system — all of it, or just the queue.

Check your understanding

  1. A database connection pool holds requests for an average of 15 ms, and the service makes 2,000 queries a second. How many connections are in use on average?
  2. In the M/M/1 help desk at , , what’s the probability the agent is idle? What’s the probability that there are 3 or more people in the system?
  3. Why does a shared queue beat separate queues, even when the servers and the total arrivals are identical?
  4. A service has average utilisation 60% but serves a mix of 1 ms and 200 ms requests. Why might its latency be worse than M/M/1 predicts?
After your attempt — answers
  1. connections on average. A pool of 20 would be a bottleneck.
  2. . . More than half the time, a caller finds at least two others ahead of or with them.
  3. With separate queues, it can happen that one server is idle while customers wait in the other’s queue. A shared queue never lets a server idle while anyone waits, so the same capacity is used more fully exactly when it matters.
  4. The service times are highly variable ( well above 1), and by Pollaczek–Khinchine the queue length grows with . Short requests get stuck behind long ones.

Practice — independent task

  1. Predict, then compute: a clinic gets 12 patients an hour, each doctor sees 5 an hour, and the target is an average wait in the queue under 10 minutes. Predict the number of doctors needed, then use mmc to find the smallest that meets the target.
  2. Apply to software: estimate, for a service you know (or an invented one with stated numbers): arrival rate, mean service time, number of workers. Use Little’s law to check in-flight requests, and mmc to estimate queueing at today’s load and at 1.5× load.
  3. Extend: add an mg1(lam, mu, cs) function using the Pollaczek–Khinchine formula, and print for at .

Done when: part 1 gives a number with a justification; part 2 produces a short paragraph saying at what load the service gets into trouble; part 3 shows for is exactly half of .

Answer to part 1 — after your attempt

gives and h (13 minutes) — not enough. gives and h (about 2.2 minutes). So 4 doctors. Note the jump: adding one doctor cut the wait by about 80%, because 3 doctors sat in the steep part of the curve.

Before moving on

You’re ready when you can apply Little’s law in your head, compute M/M/1 waits, sketch the curve from memory and say what it means for capacity planning, and explain why pooling helps.

Recap:

  1. Little’s law, , holds for any stable system.
  2. M/M/1: ; time in system is service times — a cliff near .
  3. M/M/c with Erlang C sizes multi-server systems; pooled queues beat separate ones.
  4. Variability matters as much as utilisation: queue length scales with .

Next: Inventory Models — the other classic stochastic problem: how much to keep in stock, and when to reorder.

↑ Back to Operations Research