Optimal Load Balancing with Locality Constraints
Open Access
- 31 May 2021
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 49-50
Abstract
Applications in cloud platforms motivate the study of efficient load balancing under job-server constraints and server heterogeneity. In this paper, we study load balancing on a bipartite graph where left nodes correspond to job types and right nodes correspond to servers, with each edge indicating that a job type can be served by a server. Thus edges represent locality constraints, i.e., an arbitrary job can only be served at servers which contain certain data and/or machine learning (ML) models. Servers in this system can have heterogeneous service rates. In this setting, we investigate the performance of two policies named Join-the-Fastest-of-the-Shortest-Queue (JFSQ) and Join-the-Fastest-of-the-Idle-Queue (JFIQ), which are simple variants of Join-the-Shortest-Queue and Join-the-Idle-Queue, where ties are broken in favor of the fastest servers. Under a "well-connected'' graph condition, we show that JFSQ and JFIQ are asymptotically optimal in the mean response time when the number of servers goes to infinity. In addition to asymptotic optimality, we also obtain upper bounds on the mean response time for finite-size systems. We further show that the well-connectedness condition can be satisfied by a random bipartite graph construction with relatively sparse connectivity.Keywords
Funding Information
- NSF (National Science Foundation) (CPS ECCS 17-39189, CCF 19-34986, ECCS 16-09370)
- Army Research Office (W911NF-19-1-0379)
- Office of Naval Research (Navy N00014-19-1-2566)
This publication has 5 references indexed in Scilit:
- Scalable load balancing in the presence of heterogeneous serversPerformance Evaluation, 2021
- Optimal Load Balancing with Locality ConstraintsProceedings of the ACM on Measurement and Analysis of Computing Systems, 2020
- Pull-based load distribution in large-scale heterogeneous service systemsQueueing Systems, 2015
- 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