More Like this

1. Load Balancing in Parallel Queues and Rank-Based Diffusions

   https://doi.org/10.1287/moor.2023.0050  

   Banerjee, Sayan; Budhiraja, Amarjit; Estevez, Benjamin (May 2025, Mathematics of Operations Research)

   Consider a queuing system with K parallel queues in which the server for each queue processes jobs at rate n and the total arrival rate to the system is [Formula: see text], where [Formula: see text] and n is large. Interarrival and service times are taken to be independent and exponentially distributed. It is well known that the join-the-shortest-queue (JSQ) policy has many desirable load-balancing properties. In particular, in comparison with uniformly at random routing, the time asymptotic total queue-length of a JSQ system, in the heavy traffic limit, is reduced by a factor of K. However, this decrease in total queue-length comes at the price of a high communication cost of order [Formula: see text] because at each arrival instant, the state of the full K-dimensional system needs to be queried. In view of this, it is of interest to study alternative routing policies that have lower communication costs and yet have similar load-balancing properties as JSQ. In this work, we study a family of such rank-based routing policies, which we will call Marginal Size Bias Load-Balancing policies, in which [Formula: see text] of the incoming jobs are routed to servers with probabilities depending on their ranked queue length and the remaining jobs are routed uniformly at random. A particular case of such routing schemes, referred to as the marginal JSQ (MJSQ) policy, is one in which all the [Formula: see text] jobs are routed using the JSQ policy. Our first result provides a heavy traffic approximation theorem for such queuing systems in terms of reflected diffusions in the positive orthant [Formula: see text]. It turns out that, unlike the JSQ system, where, due to a state space collapse, the heavy traffic limit is characterized by a one-dimensional reflected Brownian motion, in the setting of MJSQ (and for the more general rank-based routing schemes), there is no state space collapse, and one obtains a novel diffusion limit which is the constrained analogue of the well-studied Atlas model (and other rank-based diffusions) that arise from certain problems in mathematical finance. Next, we prove an interchange of limits ([Formula: see text] and [Formula: see text]) result which shows that, under conditions, the steady state of the queuing system is well approximated by that of the limiting diffusion. It turns out that the latter steady state can be given explicitly in terms of product laws of Exponential random variables. Using these explicit formulae, and the interchange of limits result, we compute the time asymptotic total queue-length in the heavy traffic limit for the MJSQ system. We find the striking result that, although in going from JSQ to MJSQ, the communication cost is reduced by a factor of [Formula: see text], the steady-state heavy traffic total queue-length increases by at most a constant factor (independent of n, K) which can be made arbitrarily close to one by increasing a MJSQ parameter. We also study the case where the system is overloaded—namely, [Formula: see text]. For this case, we show that although the K-dimensional MJSQ system is unstable, unlike the setting of random routing, the system has certain desirable and quantifiable load-balancing properties. In particular, by establishing a suitable interchange of limits result, we show that the steady-state difference between the maximum and the minimum queue lengths stays bounded in probability (in the heavy traffic parameter n). Funding: Financial support from the National Science Foundation [RTG Award DMS-2134107] is gratefully acknowledged. S. Banerjee received financial support from the National Science Foundation [NSF-CAREER Award DMS-2141621]. A. Budhiraja received financial support from the National Science Foundation [Grant DMS-2152577]. 

   more » « less
2. Many-Server Asymptotics for Join-the-Shortest-Queue in the Super-Halfin-Whitt Scaling Window

   https://doi.org/10.1287/moor.2021.0133  

   Zhao, Zhisheng; Banerjee, Sayan; Mukherjee, Debankur (July 2025, Mathematics of Operations Research)

   Join-the-shortest queue (JSQ) is a classical benchmark for the performance of parallel-server queueing systems because of its strong optimality properties. Recently, there has been significant progress in understanding its large-system asymptotic behavior. In this paper, we analyze the JSQ policy in the super-Halfin-Whitt scaling window when load per server [Formula: see text] scales with the system size N as [Formula: see text] for [Formula: see text] and [Formula: see text]. We establish that the centered and scaled total queue length process converges to a certain Bessel process with negative drift, and the associated (centered and scaled) steady-state total queue length, indexed by N, converges to a [Formula: see text] distribution. The limit laws are universal in the sense that they do not depend on the value of [Formula: see text] and exhibit fundamentally different behavior from both the Halfin–Whitt regime ([Formula: see text]) and the nondegenerate slowdown (NDS) regime ([Formula: see text]). Funding: This work was supported by the National Science Foundation to S. Banerjee [Grants CAREER DMS-2141621 and RTG DMS-2134107] and D. Mukherjee and Z. Zhao [Grants CIF-2113027 and CPS-2240982]. 

   more » « less
3. Load Balancing Under Strict Compatibility Constraints

   https://doi.org/10.1287/moor.2022.1258  

   Rutten, Daan; Mukherjee, Debankur (April 2022, Mathematics of Operations Research)

   Consider a system with N identical single-server 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 mean-field approximation is accurate. However, such dense compatibility graphs are infeasible for large-scale implementation. We characterize a class of sparse compatibility graphs for which the mean-field 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
4. Invariant States of Hydrodynamic Limits of Randomized Load-Balancing Networks

   https://doi.org/10.1287/moor.2020.0282  

   Agarwal, Pooja; Ramanan, Kavita (June 2025, Mathematics of Operations Research)

   Randomized load-balancing algorithms play an important role in improving performance in large-scale networks at relatively low computational cost. A common model of such a system is a network of N parallel queues in which incoming jobs with independent and identically distributed service times are routed on arrival using the join-the-shortest-of-d-queues routing algorithm. Under fairly general conditions, it was shown by Aghajani and Ramanan that as the size of the system goes to infinity, the state dynamics converge to the unique solution of a countable system of coupled deterministic measure-valued equations called the hydrodynamic equations. In this article, a characterization of invariant states of these hydrodynamic equations is obtained and, when d=2, used to construct a numerical algorithm to compute the queue length distribution and mean virtual waiting time in the invariant state. Additionally, it is also shown that under a suitable tail condition on the service distribution, the queue length distribution of the invariant state exhibits a doubly exponential tail decay, thus demonstrating a vast improvement in performance over the case [Formula: see text], which corresponds to random routing, when the tail decay could even be polynomial. Furthermore, numerical evidence is provided to support the conjecture that the invariant state is the limit of the steady-state distributions of the N-server models. The proof methodology, which entails analysis of a coupled system of measure-valued equations, can potentially be applied to other many-server systems with general service distributions, where measure-valued representations are useful. 

   more » « less
5. Job Dispatching Policies for Queueing Systems with Unknown Service Rates

   https://doi.org/10.1145/3466772.3467047  

   Choudhury, Tuhinangshu; Joshi, Gauri; Wang, Weina; Shakkottai, Sanjay (July 2021, ACM MobiHoc: International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks)

   null (Ed.)

   In multi-server 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 join-the-shortest-queue 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 exploration-exploitation trade-off 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 bandit-based exploration policy that learns the service rates from observed job departures. Unlike the standard multi-armed 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 bandit-based exploration policy. 

   more » « less