Variability, M/G/1 and Kingman’s approximation

At the same mean service time and utilization, an occasional very long job can delay many followers. M/G/1 exposes the role of the service second moment. Kingman's approximation adds interarrival variability to a mean-wait estimate.

Why long jobs are encountered more often

Sampling a busy server at a random time favors a service interval of length $s$ in proportion to $s$: it occupies more time. Its residual-work area is $s^2/2$. For IID service, the mean residual service conditional on a busy observation is:

$$E[R\mid \text{busy}]=\frac{E[S^2]}{2E[S]}.$$

This is $E[S]/2$ for deterministic service and $E[S]$ for exponential service. It is an average under time sampling, not a claim that an individual job is always halfway through.

The Pollaczek–Khinchine formula

Assume Poisson arrivals, IID service independent of arrivals, one FCFS server, unlimited space and $\rho =\lambda E[S]<1$. With finite $E[S^2]$, waiting consists of residual work in service plus the complete work of jobs ahead. PASTA and $L_q=\lambda E[W_q]$ give:

$$E[W_q]=\rho \frac{E[S^2]}{2E[S]}+L_{q}E[S]=\frac{\lambda E[S^2]}{2}+\rho E[W_q].$$

Rearrange to obtain the exact PK mean within M/G/1:

$$E[W_q]=\frac{\lambda E[S^2]}{2(1-\rho )}=\frac{\rho }{1-\rho }\frac{1+C_s^2}{2}E[S].$$

At mean service 10 ms and $\rho =0.8$, values $C_s^2=0,1,9$ give mean waits of 20, 40 and 200 ms. Mean service work has not increased; the chance of encountering a long service and the resulting accumulated wait have.

A stationary distribution need not have a finite waiting mean

Under the usual IID M/G/1 conditions, finite $E[S]$ and $\rho <1$ can yield a stationary system. If $E[S^2]=\infty$, FCFS mean waiting can nevertheless be infinite. A suitably scaled Pareto service distribution with shape strictly between 1 and 2 has this property.

Every finite dataset can produce a finite sample variance. That does not establish a finite population second moment. Inspect large jobs, timeout censoring, request categories and sensitivity to observation length; a few extremes alone do not identify a tail family.

General arrivals and Kingman's approximation

For FCFS GI/GI/1 with mutually independent IID gap and service sequences and finite second moments, a commonly used approximation is:

$$E[W_q]\approx \frac{\rho }{1-\rho }\frac{C_a^2+C_s^2}{2}E[S].$$

This mean approximation is motivated by heavy-traffic analysis. It is neither a general upper bound nor a p99 formula. Low load, strong dependence or batch arrivals can create substantial error. When arrivals really are Poisson, $C_a^2=1$ recovers exact PK numerically; measuring that moment alone does not establish exactness.

First hold $C_a^2=1$ and vary service variability, then move $C_a^2$ away from 1. The solid curve remains a Poisson reference; only the dashed curve uses the chosen arrival variability. They are not two exact answers for the same system.

Check your understanding

1. Replace deterministic service with exponential service of the same mean. How does M/G/1 mean waiting change?

2. A few large jobs affect many users despite moderate average utilization. What should be examined first?

Further reading

See MIT section 4.7 for PK, and Tran-Gia and Hossfeld's lecture for the distinction between approximation and bound. The examples, code and figures here were independently constructed.