TY - GEN
T1 - Optimal Load Balancing with Locality Constraints
AU - Weng, Wentao
AU - Zhou, Xingyu
AU - Srikant, R.
N1 - Publisher Copyright:
© 2021 Owner/Author.
PY - 2021/6
Y1 - 2021/6
N2 - 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.
AB - 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.
KW - asymptotic optimality
KW - cloud computing
KW - delay performance
KW - load balancing
UR - http://www.scopus.com/inward/record.url?scp=85103030620&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85103030620&partnerID=8YFLogxK
U2 - 10.1145/3410220.3456279
DO - 10.1145/3410220.3456279
M3 - Conference contribution
AN - SCOPUS:85131761731
T3 - Performance Evaluation Review
SP - 49
EP - 50
BT - SIGMETRICS '21: Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems
PB - Association for Computing Machinery
T2 - 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2021
Y2 - 14 June 2021 through 18 June 2021
ER -