M/M/1: utilization and tail latency

M/M/1 is a fully solvable model of random arrivals and service. It explains nonlinear waiting near full utilization and shows why a mean alone cannot represent every user's experience.

From state balance to means

Assume exogenous Poisson arrivals at $\lambda$, IID exponential service at $\mu$, mutual independence, one FCFS server, unlimited waiting space, and no abandonment or retries. State $n$ counts all jobs inside. Arrivals increase it at rate $\lambda$; when nonempty, completions decrease it at rate $\mu$.

Stationary adjacent-state balance is ${\pi }_n\lambda ={\pi }_{n+1}\mu$. With $\rho =\lambda /\mu$, normalizing the geometric series yields:

$${\pi }_n=(1-\rho ){\rho }^n,\rho <1;L=\sum _{n\ge 0}n{\pi }_n=\frac{\rho }{1-\rho }.$$

Consequently:

$$E[T]=\frac{1}{\mu -\lambda },E[W_q]=\frac{\rho }{\mu -\lambda },L_q=\frac{{\rho }^2}{1-\rho }.$$

At $\rho \ge 1$ the infinite-state chain has no normalizable stationary distribution. Continuing the formula to obtain a negative wait is invalid. Equality is not a safe equilibrium for this stochastic queue.

An exactly computable tail

An arrival sees $n$ other jobs with probability ${\pi }_n$. Memoryless service makes its system time the sum of $n+1$ independent exponential stages. Mixing these sums with geometric weights gives:

$$P(T>t)=e^{-(\mu -\lambda )t},t\ge 0.$$

Waiting has a different distribution: probability $1-\rho$ corresponds to immediate service.

$$P(W_q>t)=\rho e^{-(\mu -\lambda )t},P(W_q=0)=1-\rho .$$

The system-time $p$ quantile is $t_p=-\ln (1-p)/(\mu -\lambda )$. Thus p99 is approximately 4.605 times the mean in this model. That ratio is not a universal production rule.

At $\mu =100$/s and $\rho =0.8$, mean system time is 50 ms, mean wait 40 ms and system-time p99 about 230 ms. At $\rho =0.9$, they become 100, 90 and 461 ms. Mean service remains 10 ms throughout.

Derive a conditional capacity boundary

Requiring system-time p99 at most 200 ms in this model gives:

$$\mu -\lambda \ge \frac{\ln 100}{0.2}\approx 23.026{\mathrm{s}}^{-1}.$$

With $\mu =100$/s, this permits $\lambda \le 76.974$/s. The result is conditional on the model. Long services, batching, several stages or a slowing dependency require another model and validation with load tests.

A utilization curve also does not capture every scaling effect. More workers may leave the bottleneck's $\mu$ unchanged; contention may even reduce it. Identify service occupancy and load-dependent behavior before treating service capacity as constant.

Check your understanding

1. At 50% utilization, do half of requests have zero total latency?

2. Can an observed production mean be multiplied by 4.605 to obtain p99?

Further reading

MIT Urban Operations Research, section 4.6.1 derives the state and residence-time distributions. Next, we keep mean service fixed while relaxing exponential service.