kingman-approximation · research · also Kingman's formula, VUT approximation

Kingman approximation

The Kingman approximation estimates mean waiting in a single-server FCFS queue from utilization, mean service time and arrival and service variability.

Write E[Q] approximately equal to ((c_a^2 + c_s^2)/2) * rho/(1-rho) * E[S], where rho = lambda E[S], c_a^2 = Var(A)/E[A]^2 and c_s^2 = Var(S)/E[S]^2. A is an interarrival interval, not a request count. The inputs are squared coefficients of variation (SCVs), not unsquared CVs. [1]

The usual GI/G/1 interpretation has iid interarrival intervals, iid service times independent of arrivals, one work-conserving nonpreemptive FCFS server, unlimited waiting space, finite second moments and 0 < rho < 1. The heavy-traffic basis concerns a family of queues approaching saturation; it does not certify an arbitrary finite-load estimate or a storage p99. Stronger moment-convergence results need their own regularity conditions. [2]

SCV one does not establish Poisson arrivals. Intervals 0.5 and 3 with probabilities 0.8 and 0.2 have mean one and variance one but are not exponential. Even with equal arrival means and SCVs, exact GI/M/1 mean waits can differ: at 50% utilization and exponential mean-1 ms service, three declared arrival laws give 1, 0.958912 and 0.699539 ms. [5]

At mean service 1 ms and service SCV one, changing arrival SCV from 0.25 to 4 changes the estimate from 2.5 to 10 ms at 80% utilization. These are evaluations of an approximation, not observed waits or measured approximation errors. Marginal SCVs do not encode serial correlation or feedback from a closed-loop load generator. [4]

Relations

related
Queueing delay, Service time, Pollaczek-Khinchine mean formula

Citations

  1. Harchol-Balter and Scully: The most common queueing theory questions asked by computer systems practitioners, section 1; VUT expression and SCV definitions. (accessed 2026-11-19)
  2. Boon, Janssen and van Leeuwaarden: Heavy-traffic single-server queues and the transform method, arXiv:2206.09844v1 (2022), sections 1-3. (accessed 2026-11-19)
  3. Hesela: VUT sensitivity calculations and moment-matched non-Poisson counterexample. (accessed 2026-11-19)
  4. Hesela: Equal arrival moments do not identify mean waiting; GI/M/1 model, primary-source equations and rational numerical certificates. (accessed 2026-11-19)

Further reading

  1. J. F. C. Kingman: The single server queue in heavy traffic, 57(4), 902-904 (1961). Bibliographic provenance; DOI 10.1017/S0305004100036094. (accessed 2026-11-19)
Sources & caveats
  • Source synthesis plus exact arithmetic applied to an approximate formula; no hardware measurements or simulation.
  • The original 1961 publisher record establishes attribution; the open 2022 manuscript was used to inspect the theory and its stronger assumptions.

JSON: /data/terms/kingman-approximation.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Kingman approximation. Hesela. 2026-11-20. https://hesela.dev/terms/kingman-approximation/