This content will become publicly available on February 22, 2025
We consider largescale load balancing systems where processing time distribution of tasks depend on both task and server types. We analyze the system in the asymptotic regime where the number of task and server types tend to infinity proportionally to each other. In such heterogeneous setting, popular policies like Join Fastest Idle Queue (JFIQ), Join Fastest Shortest Queue (JFSQ) are known to perform poorly and they even shrink the stability region. Moreover, to the best of our knowledge, in this setup, finding a scalable policy with provable performance guarantee has been an open question prior to this work. In this paper, we propose and analyze two asymptotically delayoptimal dynamic load balancing approaches: (a) one that efficiently reserves the processing capacity of each server for good tasks and route tasks under the Join Idle Queue policy; and (b) a speedpriority policy that increases the probability of servers processing tasks at a high speed. Introducing a novel analytical framework and using the meanfield method and stochastic coupling arguments, we prove that both policies above achieve asymptotic zero queueing, whereby the probability that a typical task is assigned to an idle server tends to 1 as the system scales.
more » « less Award ID(s):
 2113027
 NSFPAR ID:
 10522111
 Publisher / Repository:
 ACM
 Date Published:
 Journal Name:
 ACM SIGMETRICS Performance Evaluation Review
 Volume:
 51
 Issue:
 4
 ISSN:
 01635999
 Page Range / eLocation ID:
 26 to 27
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

null (Ed.)Applications in cloud platforms motivate the study of efficient load balancing under jobserver 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 JointheFastestoftheShortestQueue (JFSQ) and JointheFastestoftheIdleQueue (JFIQ), which are simple variants of JointheShortestQueue and JointheIdleQueue, where ties are broken in favor of the fastest servers. Under a "wellconnected'' 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 finitesize systems. We further show that the wellconnectedness condition can be satisfied by a random bipartite graph construction with relatively sparse connectivity.more » « less

Abstract This paper studies load balancing for many‐server (
N servers) systems. Each server has a buffer of sizeb − 1, and can have at most one job in service andb − 1 jobs in the buffer. The service time of a job follows the Coxian‐2 distribution. We focus on steady‐state performance of load balancing policies in the heavy traffic regime such that the normalized load of system isλ = 1 −N ^{−α}for 0 <α < 0.5. We identify a set of policies that achieve asymptotic zero waiting. The set of policies include several classical policies such as join‐the‐shortest‐queue (JSQ), join‐the‐idle‐queue (JIQ), idle‐one‐first (I1F) and power‐of‐d ‐choices (Pod ) withd =O (N ^{α} logN ). The proof of the main result is based on Stein's method and state space collapse. A key technical contribution of this paper is the iterative state space collapse approach that leads to a simple generator approximation when applying Stein's method. 
The fundamental problem in the study of parallelserver systems is that of finding and analyzing routing policies of arriving jobs to the servers that efficiently balance the load on the servers. The most wellstudied policies are (in decreasing order of efficiency) join the shortest workload (JSW), which assigns arrivals to the server with the least workload; join the shortest queue (JSQ), which assigns arrivals to the smallest queue; the powerof[Formula: see text] (PW([Formula: see text])), which assigns arrivals to the shortest among [Formula: see text] queues that are sampled from the total of [Formula: see text] queues uniformly at random; and uniform routing, under which arrivals are routed to one of the [Formula: see text] queues uniformly at random. In this paper we study the stability problem of parallelserver systems, assuming that routing errors may occur, so that arrivals may be routed to the wrong queue (not the smallest among the relevant queues) with a positive probability. We treat this routing mechanism as a probabilistic routing policy, named a [Formula: see text]allocation policy, that generalizes the PW([Formula: see text]) policy, and thus also the JSQ and uniform routing, where [Formula: see text] is an [Formula: see text]dimensional vector whose components are the routing probabilities. Our goal is to study the (in)stability problem of the system under this routing mechanism, and under its “nonidling” version, which assigns new arrivals to an idle server, if such a server is available, and otherwise routes according to the [Formula: see text]allocation rule. We characterize a sufficient condition for stability, and prove that the stability region, as a function of the system’s primitives and [Formula: see text], is in general smaller than the set [Formula: see text]. Our analyses build on representing the queue process as a continuoustime Markov chain in an ordered space of [Formula: see text]dimensional realvalued vectors, and using a generalized form of the Schurconvex order.more » « less

null (Ed.)In multiserver queueing systems where there is no central queue holding all incoming jobs, job dispatching policies are used to assign incoming jobs to the queue at one of the servers. Classic job dispatching policies such as jointheshortestqueue and shortest expected delay assume that the service rates and queue lengths of the servers are known to the dispatcher. In this work, we tackle the problem of job dispatching without the knowledge of service rates and queue lengths, where the dispatcher can only obtain noisy estimates of the service rates by observing job departures. This problem presents a novel explorationexploitation tradeoff between sending jobs to all the servers to estimate their service rates, and exploiting the currently known fastest servers to minimize the expected queueing delay. We propose a banditbased exploration policy that learns the service rates from observed job departures. Unlike the standard multiarmed bandit problem where only one out of a finite set of actions is optimal, here the optimal policy requires identifying the optimal fraction of incoming jobs to be sent to each server. We present a regret analysis and simulations to demonstrate the effectiveness of the proposed banditbased exploration policy.more » « less

Consider a system with N identical singleserver queues and a number of task types, where each server is able to process only a small subset of possible task types. Arriving tasks select [Formula: see text] random compatible servers and join the shortest queue among them. The compatibility constraints are captured by a fixed bipartite graph between the servers and the task types. When the graph is complete bipartite, the meanfield approximation is accurate. However, such dense compatibility graphs are infeasible for largescale implementation. We characterize a class of sparse compatibility graphs for which the meanfield approximation remains valid. For this, we introduce a novel notion, called proportional sparsity, and establish that systems with proportionally sparse compatibility graphs asymptotically match the performance of a fully flexible system. Furthermore, we show that proportionally sparse random compatibility graphs can be constructed, which reduce the server degree almost by a factor [Formula: see text] compared with the complete bipartite compatibility graph.more » « less