Scalable load balancing in networked systems: A survey of recent advances

Abstract

The basic load balancing scenario involves a single dispatcher where tasks arrive that must immediately be forwarded to one of $N$ single-server queues. We discuss recent advances on scalable load balancing schemes which provide favorable delay performance when $N$ grows large, and yet only require minimal implementation overhead. Join-the-Shortest-Queue (JSQ) yields vanishing delays as $N$ grows large, as in a centralized queueing arrangement, but involves a prohibitive communication burden. In contrast, power-of-$d$ or JSQ($d$) schemes that assign an incoming task to a server with the shortest queue among $d$ servers selected uniformly at random require little communication, but lead to constant delays. In order to examine this fundamental trade-off between delay performance and implementation overhead, we consider JSQ($d(N)$) schemes where the diversity parameter $d(N)$ depends on $N$ and investigate what growth rate of $d(N)$ is required to asymptotically match the optimal JSQ performance on fluid and diffusion scale. Stochastic coupling techniques and stochastic-process limits play an instrumental role in establishing the asymptotic optimality. We demonstrate how this methodology carries over to infinite-server settings, finite buffers, multiple dispatchers, servers arranged on graph topologies, and token-based load balancing including the popular Join-the-Idle-Queue (JIQ) scheme. In this way we provide a broad overview of the many recent advances in the field. This survey extends the short review presented at ICM 2018 (arXiv:1712.08555).

To appear in SIAM Review. arXiv admin note: substantial text overlap with arXiv:1712.08555

References in corpus (19)

• Differential equation approximations for Markov chains
• Validity of heavy traffic steady-state approximations in generalized Jackson Networks
• Pull-based load distribution in large-scale heterogeneous service systems
• On the maximum queue length in the supermarket model
• On the power of two choices: Balls and bins in continuous time
• Supermarket Queueing System in the Heavy Traffic Regime. Short Queue Dynamics
• Join-the-Shortest Queue Diffusion Limit in Halfin-Whitt Regime: Sensitivity on the Heavy-traffic Parameter
• On Universal Scaling of Distributed Queues under Load Balancing
• Throughput and Delay Optimality of Power-of-d Choices in Inhomogeneous Load Balancing Systems
• Designing Low-Complexity Heavy-Traffic Delay-Optimal Load Balancing Schemes: Theory to Algorithms
• Insensitivity of the mean-field Limit of Loss Systems Under Power-of-d Routing
• The Equilibrium States of Large Networks of Erlang Queues
• Heavy-traffic Delay Optimality in Pull-based Load Balancing Systems: Necessary and Sufficient Conditions
• Load Balancing Guardrails: Keeping Your Heavy Traffic on the Road to Low Response Times
• Heavy-Traffic Analysis of Queueing Systems with no Complete Resource Pooling
• Many-server asymptotics for Join-the-Shortest Queue in the Super-Halfin-Whitt Scaling Window
• Achieving Zero Asymptotic Queueing Delay for Parallel Jobs
• Zero Queueing for Multi-Server Jobs
• Near Equilibrium Fluctuations for Supermarket Models with Growing Choices

Cited by in corpus (8)

• Load balancing system under Join the Shortest Queue: Many-Server-Heavy-Traffic Asymptotics
• Load Balancing in Heterogeneous Server Clusters: Insights From a Product-Form Queueing Model
• Self-Learning Threshold-Based Load Balancing
• Asynchronous Load Balancing and Auto-scaling: Mean-Field Limit and Optimal Design
• MDS coding is better than replication for job completion times
• Many-server asymptotics for Join-the-Shortest Queue in the Super-Halfin-Whitt Scaling Window
• Load Balancing with Job-Size Testing: Performance Improvement or Degradation?
• Load balancing with heterogeneous schedulers