no. 17 · Wednesday 18 November 2026
Critical heavy traffic and diffusion limits for shortest-of-d dynamic routing
Abstract
We study shortest-of-$d$ routing, with fixed $d\ge2$, in $N$ parallel queues with independent finite-state Markov service environments switching at rate $κ_N$. At the critical load $ρ_N=1-1/N$, the empirical measure of the centered queue lengths, under stationarity, converges in distribution to a random probability measure determined by its mean. We identify the mean's density and the conditional independence of fixed finite collections of centered queues in the limit. On time scales of order $N$, the centered empirical mean converges to a diffusion with explicit drift and constant diffusion coefficient. These limits hold when $κ_N/N\to\infty$, along subsequences with convergent lattice phase. The diffusion limit extends to centered initial empirical measures tight in the first Wasserstein topology, with means converging in law. A short initial layer prepares the limiting family while preserving the limiting mean. Empirical approximation holds in time-integrated Wasserstein distance.
- fields
- Probability