Universality of Load Balancing Schemes on Diffusion Scale

Abstract

We consider a system of $N$ parallel queues with identical exponential service rates and a single dispatcher where tasks arrive as a Poisson process. When a task arrives, the dispatcher always assigns it to an idle server, if there is any, and to a server with the shortest queue among $d$ randomly selected servers otherwise $(1\le d\le N)$. This load balancing scheme subsumes the so-called Join-the-Idle Queue (JIQ) policy $(d=1)$ and the celebrated Join-the-Shortest Queue (JSQ) policy $(d=N)$ as two crucial special cases. We develop a stochastic coupling construction to obtain the diffusion limit of the queue process in the Halfin-Whitt heavy-traffic regime, and establish that it does not depend on the value of $d$, implying that assigning tasks to idle servers is sufficient for diffusion level optimality.

References in corpus (2)

• Martingale proofs of many-server heavy-traffic limits for Markovian queues
• Pull-based load distribution in large-scale heterogeneous service systems

Cited by in corpus (9)

• Scalable load balancing in networked systems: A survey of recent advances
• Universality of Power-of-$d$ Load Balancing in Many-Server Systems
• Optimal Service Elasticity in Large-Scale Distributed Systems
• 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
• Self-Learning Threshold-Based Load Balancing
• Many-Server Asymptotics for Join-the-Shortest-Queue: Large Deviations and Rare Events
• Steady-State Convergence of the Continuous-Time Routing System with General Distributions in Heavy Traffic