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