CaltechAUTHORS
  A Caltech Library Service

Asymptotically Optimal Load Balancing in Large-scale Heterogeneous Systems with Multiple Dispatchers

Zhou, Xingyu and Shroff, Ness and Wierman, Adam (2020) Asymptotically Optimal Load Balancing in Large-scale Heterogeneous Systems with Multiple Dispatchers. ACM SIGMETRICS Performance Evaluation Review, 48 (3). pp. 57-58. ISSN 0163-5999. https://resolver.caltech.edu/CaltechAUTHORS:20210308-133521968

[img] PDF - Published Version
See Usage Policy.

768Kb
[img] PDF - Submitted Version
Creative Commons Attribution.

336Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20210308-133521968

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1145/3453953.3453965DOIArticle
https://arxiv.org/abs/2002.08908arXivDiscussion Paper
https://resolver.caltech.edu/CaltechAUTHORS:20200526-152856053Related ItemPerformance Evaluation Journal (Elsevier)
ORCID:
AuthorORCID
Shroff, Ness0000-0002-4606-6879
Additional Information:© 2020 is held by author/owner(s). This project has been funded in part through NSF grants: CNS-2007231, CNS-1719371, and CNS-1717060 and NSF grants AitF-1637598 and CNS-1518941.
Funders:
Funding AgencyGrant Number
NSFCNS-2007231
NSFCNS-1719371
NSFCNS-1717060
NSFCCF-1637598
NSFCNS-1518941
Subject Keywords:Asymptotically optimal; Load balancing; Heterogeneous systems, Multiple dispatchers, Delayed information
Issue or Number:3
Record Number:CaltechAUTHORS:20210308-133521968
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20210308-133521968
Official Citation:Xingyu Zhou, Ness Shroff, and Adam Wierman. 2021. Asymptotically Optimal Load Balancing in Large-scale Heterogeneous Systems with Multiple Dispatchers. SIGMETRICS Perform. Eval. Rev. 48, 3 (December 2020), 57–58. DOI: https://doi.org/10.1145/3453953.3453965
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:108346
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:08 Mar 2021 23:29
Last Modified:08 Mar 2021 23:29

Repository Staff Only: item control page