Optimal Load Balancing with Locality Constraints

Wentao Weng, Xingyu Zhou, R. Srikant

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationSIGMETRICS 2021 - Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems
PublisherAssociation for Computing Machinery, Inc
Pages49-50
Number of pages2
ISBN (Electronic)9781450380720
DOIs
StatePublished - May 31 2021
Event2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2021 - Virtual. Online, China
Duration: Jun 14 2021Jun 18 2021

Conference

Conference2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2021
Country/TerritoryChina
CityVirtual. Online
Period6/14/216/18/21

Keywords

  • asymptotic optimality
  • cloud computing
  • delay performance
  • load balancing

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Hardware and Architecture
  • Software

Fingerprint

Dive into the research topics of 'Optimal Load Balancing with Locality Constraints'. Together they form a unique fingerprint.

Cite this