Scalable load balancing in networked systems: A survey of recent advances
arXiv:1806.05444 · doi:10.1137/20M1323746
Abstract
The basic load balancing scenario involves a single dispatcher where tasks arrive that must immediately be forwarded to one of single-server queues. We discuss recent advances on scalable load balancing schemes which provide favorable delay performance when grows large, and yet only require minimal implementation overhead. Join-the-Shortest-Queue (JSQ) yields vanishing delays as grows large, as in a centralized queueing arrangement, but involves a prohibitive communication burden. In contrast, power-of- or JSQ() schemes that assign an incoming task to a server with the shortest queue among 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() schemes where the diversity parameter depends on and investigate what growth rate of 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).
arXiv commentTo appear in SIAM Review. arXiv admin note: substantial text overlap with arXiv:1712.08555
References in corpus (37)
- 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
- Universality of Power-of- Load Balancing in Many-Server Systems
- On the maximum queue length in the supermarket model
- Steady-state queue in the Halfin-Whitt regime
- On the power of two choices: Balls and bins in continuous time
- Universality of Load Balancing Schemes on Diffusion Scale
- Asymptotic approximations for stationary distributions of many-server queues with abandonment
- Asymptotically Optimal Load Balancing Topologies
- Supermarket Model on Graphs
- On Mean Field Convergence and Stationary Regime
- Optimal Service Elasticity in Large-Scale Distributed Systems
- Join-the-Shortest Queue Diffusion Limit in Halfin-Whitt Regime: Tail Asymptotics and Scaling of Extrema
- GB-PANDAS: Throughput and heavy-traffic optimality analysis for affinity scheduling
- On the rate of convergence to stationarity of the M/M/N queue in the Halfin-Whitt regime
- Asymptotic Optimality of Power-of- Load Balancing in Large-Scale Systems
- 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
- Averaging over fast variables in the fluid limit for Markov chains: Application to the supermarket model with memory
- Join-Idle-Queue with Service Elasticity: Large-Scale Asymptotics of a Non-monotone System
- Throughput and Delay Optimality of Power-of-d Choices in Inhomogeneous Load Balancing Systems
- Approximate performance analysis of generalized join the shortest queue routing
- 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
- Economies-of-scale in resource sharing systems: tutorial and partial review of the QED heavy-traffic regime
- 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
- Contrasting Effects of Replication in Parallel Systems: From Overload to Underload and Back
- 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
- Balanced routing of random calls
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