Asymptotically Optimal Load Balancing in Large-scale Heterogeneous Systems with Multiple Dispatchers
- 5 March 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 48 (3), 57-58
- https://doi.org/10.1145/3453953.3453965
Abstract
We consider the load balancing problem in large-scale heterogeneous systems with multiple dispatchers. We introduce a general framework called Local-Estimation-Driven (LED). Under this framework, each dispatcher keeps local (possibly outdated) estimates of the queue lengths for all the servers, and the dispatching decision is made purely based on these local estimates. The local estimates are updated via infrequent communications between dispatchers and servers. We derive sufficient conditions for LED policies to achieve throughput optimality and delay optimality in heavy-traffic, respectively. These conditions directly imply delay optimality for many previous local-memory based policies in heavy traffic. Moreover, the results enable us to design new delay optimal policies for heterogeneous systems with multiple dispatchers. Finally, the heavy-traffic delay optimality of the LED framework also sheds light on a recent open question on how to design optimal load balancing schemes using delayed information.Keywords
This publication has 9 references indexed in Scilit:
- Open Problem—Load Balancing Using Delayed InformationStochastic Systems, 2019
- Heavy-traffic Delay Optimality in Pull-based Load Balancing SystemsProceedings of the ACM on Measurement and Analysis of Computing Systems, 2018
- Designing Low-Complexity Heavy-Traffic Delay-Optimal Load Balancing SchemesProceedings of the ACM on Measurement and Analysis of Computing Systems, 2017
- Analyzing distributed Join-Idle-Queue: A fluid limit approachPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2016
- Evolve or DiePublished by Association for Computing Machinery (ACM) ,2016
- Pull-based load distribution in large-scale heterogeneous service systemsQueueing Systems, 2015
- Heavy traffic optimal resource allocation algorithms for cloud computing clustersPerformance Evaluation, 2014
- Join-Idle-Queue: A novel load balancing algorithm for dynamically scalable web servicesPerformance Evaluation, 2011
- The power of two choices in randomized load balancingIEEE Transactions on Parallel and Distributed Systems, 2001