Heavy Traffic and Diffusion Approximations for Queues

Simulating an order queue exactly — tracking every individual arrival, every individual service completion, one at a time — is precise but computationally heavy and gives you a jumble of numbers rather than intuition. When a server or matching system runs close to fully loaded, though, something convenient happens: the queue length, viewed from far enough away, starts to look like ordinary Brownian motion with a drift, the same random walk used to model stock prices. Heavy traffic theory says exactly when and why this happens, and it lets you swap a hard discrete queueing problem for a much more tractable continuous one.

An analogy: a crowd near a doorway

Imagine a doorway people pass through one at a time, with a crowd building up in front of it. If the doorway is mostly idle, the crowd size is small and jumps around unpredictably — no smooth pattern. But if the crowd arrives almost as fast as the doorway can let people through, the crowd size becomes a large, slowly drifting number that moves in small relative steps, buffeted by whether slightly more or fewer people arrived in the last minute than left. From a distance, that slow drifting is well described by a continuous, jittery path rather than by tracking individuals — the same simplification the eye makes watching a packed doorway from afar versus watching one person at a time.

The idea, one symbol at a time

Let $Q(t)$ be the number in the system (in queue plus in service) at time $t$, and let $\rho$ be utilization as before. Heavy traffic means $\rho \to 1$: arrivals almost keep pace with service capacity. Under heavy traffic, after rescaling time and queue length appropriately, $Q(t)$ converges to a reflected Brownian motion $X(t)$:

$$X(t) = \mu t + \sigma B(t) + L(t), \qquad X(t) \ge 0,$$

where $B(t)$ is standard Brownian motion (pure random jitter, no drift), $\mu$ is the drift (negative when the server has slight spare capacity, so the queue tends to drain), $\sigma$ is the volatility of arrival-and-service noise (driven by the same $C_a^2, C_s^2$ terms from Kingman's formula), and $L(t)$ is a "reflecting" term pushing the process back up whenever it would go negative — a queue can't have fewer than zero people. In plain English: near saturation, the queue behaves like a stock price with a slight downward pull, continuous random noise, and a floor at zero.

The steady-state distribution of a reflected Brownian motion with negative drift $\mu < 0$ is exponential with rate $2|\mu|/\sigma^2$, which recovers exactly the same $\rho/(1-\rho)$-type blow-up as $\rho \to 1$: as drift $\mu \to 0^-$, the mean queue length $\sigma^2/(2|\mu|)$ grows without bound.

Worked example 1: matching-engine queue depth

An exchange's matching engine handles $\lambda = 995$ orders per second on average, with capacity $\mu_{\text{cap}} = 1000$ per second, so $\rho = 0.995$ — deep in heavy traffic. Suppose the combined variability gives an effective diffusion parameter $\sigma^2 = 50$ (orders²/second) and drift $\mu = -(1000 - 995) = -5$ per second (net drain rate). The approximate steady-state mean queue length is:

$$\mathbb{E}[Q] \approx \frac{\sigma^2}{2|\mu|} = \frac{50}{2 \times 5} = 5 \text{ orders in the system}.$$

If capacity is upgraded so the drain rate improves to $\mu = -10$ (i.e., $\rho = 0.99$), holding $\sigma^2$ fixed:

$$\mathbb{E}[Q] \approx \frac{50}{20} = 2.5 \text{ orders} .$$

Doubling the drain rate roughly halves the queue — the diffusion approximation gives this instantly without discrete-event simulation.

Worked example 2: a risk batch job near a deadline

An overnight risk job processes files at a rate that's 98% of the incoming rate ($\rho = 0.98$, drift $\mu = -0.02$ files/minute in scaled units) with noise $\sigma^2 = 0.08$. Approximate mean backlog:

$$\mathbb{E}[Q] \approx \frac{0.08}{2 \times 0.02} = 2 \text{ (scaled units)} .$$

If a bad night pushes $\rho$ to 0.995 ($\mu = -0.005$) with the same noise, the backlog approximation jumps to $0.08 / 0.01 = 8$ — a four-fold jump from a small shift in utilization, illustrating why near-saturation systems are so sensitive to small load changes.

What this means in practice

Heavy-traffic diffusion approximations let a quant reason about matching-engine backlogs, market-maker inventory near risk limits, or batch-processing pipelines running close to their throughput ceiling, using the same toolkit (drift, volatility, reflecting boundaries) already familiar from modeling asset prices — a genuine two-way bridge between queueing and stochastic-process modeling. They're most valuable exactly where exact discrete formulas get intractable: multi-server systems, general (non-Poisson) arrivals, or networks of queues.