Pollaczek-Khinchine mean formula
The Pollaczek-Khinchine mean formula gives stationary mean queueing delay in an M/G/1 FCFS queue from the arrival rate and the first two service-time moments.
For one work-conserving FCFS server with unlimited waiting space, independent Poisson arrivals and iid service times S, let rho = lambda E[S] < 1. With a finite second moment, E[Q] = lambda E[S^2] / (2(1-rho)); E[R] = E[Q] + E[S]. Lambda and S must use compatible time units. There are no vacations or abandonment in this model. [1]
The second moment is Var(S) + E[S]^2, not just E[S]^2. Low utilization alone therefore does not guarantee short waiting when service times vary. The general-arrival Kingman expression discussed by Harchol-Balter and Scully is an approximation, not an exact replacement for this Poisson result. [2]
In Hesela's constructed example, constant 1 ms service and a mixture of 99% 0.5 ms requests with 1% 50.5 ms requests both average 1 ms. At 200 requests/s, both have 20% utilization, but mean waiting is 0.125 ms versus 3.21875 ms. The second moment of the mixture is 25.75 ms^2. These are exact model calculations, not device measurements. [3]
The formula is for a mean, not p99. A completion-latency sample is not automatically a service-time sample, and a multiqueue SSD is not automatically one FCFS server. [3]
Relations
Citations
- Larson and Odoni: Urban Operations Research, section 4.7, equations 4.79-4.82; M/G/1 mean waiting.
- Harchol-Balter and Scully: The most common queueing theory questions asked by computer systems practitioners, section 1.
- Hesela: exact service-variance examples, assumptions, rational outputs and replay tests.
Sources & caveats
- Primary theory and source synthesis; no empirical sample or SSD prediction.
- The exact examples use Python Fraction and retain request-weighted probabilities, compatible units and stability checks.