pollaczek-khinchine-formula · research · also Pollaczek-Khinchin formula, P-K mean formula

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

related
Service time, Queueing delay, Inspection paradox, Kingman approximation, Processor sharing

Citations

  1. Larson and Odoni: Urban Operations Research, section 4.7, equations 4.79-4.82; M/G/1 mean waiting. (accessed 2026-11-19)
  2. Harchol-Balter and Scully: The most common queueing theory questions asked by computer systems practitioners, section 1. (accessed 2026-11-19)
  3. Hesela: exact service-variance examples, assumptions, rational outputs and replay tests. (accessed 2026-11-19)
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.

JSON: /data/terms/pollaczek-khinchine-formula.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Pollaczek-Khinchine mean formula. Hesela. 2026-11-20. https://hesela.dev/terms/pollaczek-khinchine-formula/