Universality of Power-of-$d$ Load Balancing in Many-Server Systems

Abstract

We consider a system of $N$ parallel single-server queues with unit exponential service rates and a single dispatcher where tasks arrive as a Poisson process of rate $\lambda (N)$. When a task arrives, the dispatcher assigns it to a server with the shortest queue among $d(N)$ randomly selected servers ($1\le d(N)\le N$). This load balancing strategy is referred to as a JSQ($d(N)$) scheme, marking that it subsumes the celebrated Join-the-Shortest Queue (JSQ) policy as a crucial special case for $d(N)=N$. We construct a stochastic coupling to bound the difference in the queue length processes between the JSQ policy and a scheme with an arbitrary value of $d(N)$. We use the coupling to derive the fluid limit in the regime where $\lambda (N)/N\to \lambda <1$ as $N\to \infty$ with $d(N)\to \infty$, along with the associated fixed point. The fluid limit turns out not to depend on the exact growth rate of $d(N)$, and in particular coincides with that for the JSQ policy. We further leverage the coupling to establish that the diffusion limit in the critical regime where $(N-\lambda (N))/\sqrt{N}\to \beta >0$ as $N\to \infty$ with $d(N)/(\sqrt{N}\log (N))\to \infty$ corresponds to that for the JSQ policy. These results indicate that the optimality of the JSQ policy can be preserved at the fluid-level and diffusion-level while reducing the overhead by nearly a factor O($N$) and O($\sqrt{N}/\log (N)$), respectively.

39 pages, 2 figures, companion paper of arXiv:1612.00722

References in corpus (3)

• Martingale proofs of many-server heavy-traffic limits for Markovian queues
• On the maximum queue length in the supermarket model
• Universality of Load Balancing Schemes on Diffusion Scale

Cited by in corpus (7)

• Scalable load balancing in networked systems: A survey of recent advances
• Supermarket Model on Graphs
• Join-the-Shortest Queue Diffusion Limit in Halfin-Whitt Regime: Tail Asymptotics and Scaling of Extrema
• Join-the-Shortest Queue Diffusion Limit in Halfin-Whitt Regime: Sensitivity on the Heavy-traffic Parameter
• Load balancing system under Join the Shortest Queue: Many-Server-Heavy-Traffic Asymptotics
• Many-Server Asymptotics for Join-the-Shortest-Queue: Large Deviations and Rare Events
• Utility maximizing load balancing policies