Queueing theory: what it is and why latency spikes

Queueing theory is the mathematics of waiting lines: from how fast work arrives, how long each job takes and how many servers there are, it predicts how long jobs wait and how long the queue gets. For software, its most useful result is that response time grows slowly at moderate load and then sharply as a server approaches 100% busy. In the simplest model, a server busy 90% of the time answers ten times slower on average than an idle one.

The figures below are arithmetic from standard formulas, checked with a script, with no test run behind them. Sources were checked on 1 November 2026.

These are means for the M/M/1 queue: one server, Poisson arrivals and exponential service times.

What is queueing theory?

It is the branch of probability that models work arriving, waiting and being served. A queue is described by its arrivals, its service times, its number of servers and its queue discipline, the order in which waiting jobs are picked.

Larson and Odoni’s Urban Operations Research, an open MIT text, lists bank tellers, checkout counters and toll booths as classic cases. A web server fits the same frame: requests arrive, threads or cores serve them, and the rest wait in a queue.

Where did queueing theory come from?

From the telephone exchange, where A. K. Erlang worked out the first results for the Copenhagen Telephone Company.

Erlang’s 1909 paper showed that calls made at random follow the Poisson distribution, and his 1917 formula for loss and waiting time was soon used by telephone companies in many countries, according to his MacTutor biography. David Kendall’s 1953 paper, Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain, introduced the notation still in use, as Geoffrey Grimmett’s account of his work notes. Little’s proof of L = λW and Kingman’s heavy-traffic results followed in 1961.

What does Kendall’s notation such as M/M/1 mean?

It names a queue in three parts, A/S/c: the distribution of gaps between arrivals, that of service times, and the number of servers. M/M/1 means random arrivals, exponential service times and one server.

M stands for memoryless (Poisson arrivals or exponential times), D for deterministic and G for general, meaning any distribution: M/D/1 is one server with a constant service time.

How does response time grow with utilization?

In an M/M/1 queue, the mean time in the system is W = 1/(μ − λ), which equals S/(1 − ρ). As utilization ρ approaches 1, W grows without limit.

lambda = arrival rate        mu = service rate (1 / S)
rho    = lambda / mu         (utilization, must stay below 1)
W      = 1 / (mu - lambda)   = S / (1 - rho)

Larson and Odoni derive this for a single-operator call centre and show there is no steady state at ρ ≥ 1: the queue keeps growing. The same source shows the time in the system is exponentially distributed, so every percentile scales by the same 1/(1 − ρ) factor, and the p95 is about three times the mean: 600 ms in the 0.9 row above.

Why does latency knee before the CPU reaches 100%?

Because a request waits whenever it finds the server busy, and that happens more often as utilization rises. Under M/M/1 assumptions, response time has already doubled at 50% utilization.

The saturating resource may also be a connection pool, a database lock or a single-threaded event loop, and the busiest one sets the curve. The early knee is why target utilization sits well below 100%. Work back from your latency budget: with S = 20 ms and a 100 ms mean target, the table allows about 80%, and a 60 ms target about 67%, before bursts take their share.

LoadFocus’s Capacity panel groups a finished run by the number of active virtual users and reports the last level that held before the error rate passed 1% or the p95 rose above double the best level, provided no higher level recovered. It needs a single-generator run that ramps up through at least three load levels, with the top at least double the lowest. By the arithmetic above, if the lightest level left the bottleneck nearly idle, the doubling trips just past 50% utilization; if the lightest level already loaded it to ρ0, the doubling trips later, above (1 + ρ0)/2 under M/M/1.

Why does variability matter as much as utilization?

Queues come from randomness: bursts of arrivals and occasional slow jobs. In heavy traffic, waiting time grows with the variability of both, multiplied by a ρ/(1 − ρ) term.

Kingman’s 1961 paper, The single server queue in heavy traffic, shows that when a single server’s traffic intensity is near 1, the queue is long and the waiting time approximately exponential. Course notes from TU Eindhoven and the Technion give an approximation for its mean (the Technion calls it the Allen-Cunneen approximation; it is also widely known as Kingman’s formula):

Wq ≈ rho / (1 - rho) × (ca² + cs²) / 2 × S
ca, cs = coefficient of variation (std dev / mean)
         of arrival gaps and of service times

Wq is the wait before service starts. Exponential times have c² = 1, giving the M/M/1 wait of 9S at 90% utilization. A constant service time halves it to 4.5S; cs² = 4, as a mix of cache hits and slow database calls can produce, raises it to 22.5S. Steady synthetic traffic is less variable than production, so a test tends to show less queueing than real bursts will.

How do more servers (M/M/c) help?

Several servers sharing one queue absorb random bursts much better than the same servers with a queue each, so each server can run busier for the same wait.

From Larson and Odoni’s M/M/m formulas, with every server 90% busy, W is 10S for one server, 5.3S for two sharing a queue and 3.0S for four. Four instances behind a balancer that picks a free one behave like the last case; four that each take a random quarter of the traffic behave like separate M/M/1 queues at 10S.

How does Little’s law fit in?

Little’s law, L = λW, ties the average number of requests in a system to their arrival rate and their time inside, whatever the distributions. Queueing theory gives you W, and Little’s law turns it into L.

In the 0.9 row, 45 requests per second at W = 200 ms means 9 requests inside on average. Our Little’s law article uses the same law to size and check load tests.

Where do these models break down in load testing?

They assume an open stream of independent arrivals and a steady state. A test with a fixed number of virtual users is a closed system, where arrivals slow down as responses do.

• Closed tests. With N virtual users, at most N requests are in the system, so the request rate falls where an open queue would grow, and think time lowers it further. Our open vs closed workload model article explains why that hides saturation.
• LoadFocus runs k6 scripts, but arrival-rate scenarios run there with a fixed number of users, as its script validator warns. Read those runs as closed tests: past the knee, expect a flat request rate and rising response times.
• Steady state. Warm-up, caches and autoscaling change the service rate mid-run, so compare levels held long enough to settle.

FAQ

Is it queueing theory or queuing theory? Both spellings are correct and name the same field. Kingman’s 1961 paper writes “queueing time”, while Little’s proof from the same year has “Queuing Formula” in its title.

Does queueing theory need Poisson arrivals? Only for exact M/M/1 results. G/G/1 approximations such as Kingman’s formula use the mean and variability of arrival gaps and service times, and Little’s law needs no assumption about the distributions.

Related reading

• Little’s law in load testing: size and check your tests
• Open vs closed workload model: which one should you use?
• Throughput vs latency: how they interact under load
• Tail latency: what it is and how to measure it
• Think time in load testing: what it is and how to set it

The technical claims in this article have not been independently reviewed.