Heavy-traffic limits replace near-capacity queues with reflected Brownian models. See the scaling, the exponential limit and why queue wait differs from total system time.
Heavy-traffic queueing approximation
A heavy-traffic queueing approximation replaces a queue operating close to capacity with a simpler limiting stochastic model after rescaling its workload and clock. In the classical single-server setting, the limit is a reflected Brownian motion. This helps a quant reason about congestion in a pricing-job pipeline or risk-computation service when spare capacity is small and random bursts accumulate.
“Heavy traffic” means approaching a critical load from the stable side. It does not mean that a queue has a large arrival rate in absolute terms, or that an overloaded system has a stationary delay distribution.
Why a reflecting boundary appears
Consider one server working first come, first served, with an unlimited waiting room and no abandonment. Let An be the time between arrivals n and n+1, Sn the service time of job n, and Wq,n its wait before service starts. The accounting identity is
Wq,n+1=max{0,Wq,n+Sn−An}.
Work builds up when service takes longer than the next interarrival interval. When the backlog runs out, it stops at zero; unused capacity cannot become a negative waiting time. Near capacity, a small downward drift competes with accumulated fluctuations. Brownian motion approximates those fluctuations, while reflection enforces the boundary.
A reflected Brownian model has the form
Xt=X0−rt+σBt+Lt,r>0,σ>0,
where Bt is standard Brownian motion and Lt is the minimal continuous, nondecreasing regulator that keeps Xt≥0 and increases only at zero. Its stationary distribution is exponential, with rate2r/σ2. The negative drift is essential for this equilibrium. Wang and Glynn, §§1–2.
The rescaling is part of the claim
Here is a precise stationary version. Measure durations in units of mean service time m. Take independent i.i.d. service variables Vn and interarrival variables Un, each with mean one, and set
Sn=mVn,An=ρmUn,0<ρ<1.
Hold their distributions fixed while ρ↑1. A convenient sufficient regularity condition is that Un,Vn have finite exponential moments in a neighbourhood of zero, with
At the process level, the corresponding scaling shrinks workload by ε=1−ρ and observes roughly ε−2 arrivals per unit of the new clock. The clock here counts arrivals, not seconds. After normalization by m, drift tends to −1 and variance rate to v. A stationary approximation also needs stationary-limit justification: convergence of paths over finite intervals alone does not justify exchanging the long-time and heavy-traffic limits. Olvera-Cravioto, Blanchet and Glynn, §1.
A ten-percent idle probability does not disappear by approximation
Take a fictional stationary M/M/1 processing queue with Poisson arrivals at λ=9 jobs per second, independent exponential service at μ=10 jobs per second, and first-come, first-served service. Its utilisation is ρ=λ/μ=0.9 and mean service time is 0.1 second.
The exact waiting-time tail is
P(Wq>w)=ρe−(μ−λ)w,w≥0.
Thus P(Wq=0)=1−ρ=0.1. Conditional on having to wait, Wq is exponential with rate μ−λ; unconditionally, it includes an atom at zero. Jelenković and Tan, §II-A, Example 1.
Integrating that tail, then adding service time, gives two different means:
E[Wq]=μ−λρ=0.9 s,E[T]=E[Wq]+μ1=1.0 s.
Here T=Wq+S is total time in the system. Calling the second number “queue wait” adds service to the wrong quantity.
For this exponential family v=2. Define Y=(1−ρ)μWq. Direct substitution gives
P(Y>y)=ρe−y⟶e−y,y≥0.
The zero-wait atom vanishes only as ρ↑1. Using the limiting exponential at ρ=0.9 gives a mean queue wait of 1.0 second instead of the exact 0.9. It gives P(Wq>1 s)≈0.3679, versus the exact 0.3311. The equality between that approximate mean and the exact system mean is particular to this example; it does not change the meaning of queue wait.
Exact stationary M/M/1 scaled wait tails are rho times exp minus y: at y zero they start at 0.5, 0.9 and 0.99, approaching the exponential limit at 1. At arrival rate 9 and service rate 10 jobs per second, zero-wait mass is 10%, mean queue wait is 0.9 seconds and mean total system time is 1 second.
Original exact calculation for fictional stationary queues. The common scaled horizontal axis reveals convergence; the missing tail probability at zero is the probability of immediate service.
What the limit leaves out
The Kingman queueing approximation turns heavy-traffic insight into a practical mean-wait formula using arrival and service variability. The broader method here concerns stochastic-process and distributional limits, including their scaling and boundary conditions.
A high utilisation alone does not validate the classical model. Correlated arrivals, priorities, finite buffers and abandonment change its input or boundary rules. Heavy-tailed service can also make the far waiting-time tail differ sharply from an exponential approximation, even when service variance is finite: taking utilisation to one and taking the delay threshold to infinity are different limits. Olvera-Cravioto, Blanchet and Glynn, §§1–2.
For the underlying exact stationary queue calculations, Markovian Queues: The M/M/1 and M/M/s Models develops the geometric number-in-system law and capacity condition. Its public preview is open; the full lesson requires membership.
