Load balancing system under Join the Shortest Queue: Many-Server-Heavy-Traffic Asymptotics
Preprint
Abstract
We study the load balancing system operating under Join the Shortest Queue (JSQ) in the many-server heavy-traffic regime. If $N$ is the number of servers, we let the difference between the total service rate and the total arrival rate be $N^{1-\alpha}$ with $\alpha>0$. We show that for $\alpha>4$ the average queue length behaves similarly to the classical heavy-traffic regime. Specifically, we prove that the distribution of the average queue length multiplied by $N^{1-\alpha}$ converges to an exponential random variable. Moreover, we show a result analogous to state space collapse. We provide two proofs for our result: one using the one-sided Laplace transform, and one using Stein's method. We additionally obtain the rate of convergence in the Wasserstein's distance.
Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Scalable Load Balancing in Networked Systems: A Survey of Recent AdvancesSIAM Review, 2022
- Stein’s method for the single server queue in heavy trafficStatistics & Probability Letters, 2020
- A Simple Steady-State Analysis of Load Balancing Algorithms in the Sub-Halfin-Whitt RegimeACM SIGMETRICS Performance Evaluation Review, 2019
- Diffusion models and steady-state approximations for exponentially ergodic Markovian queuesThe Annals of Applied Probability, 2014
- Asymptotically tight steady-state queue length bounds implied by drift conditionsQueueing Systems, 2012
- Load balancing and density dependent jump Markov processes2002
- The power of two choices in randomized load balancingIEEE Transactions on Parallel and Distributed Systems, 2001
- A simple dynamic routing problemIEEE Transactions on Automatic Control, 1980
- A Basic Dynamic Routing Problem and DiffusionIEEE Transactions on Communications, 1978
- Optimality of the shortest line disciplineJournal of Applied Probability, 1977