A Simple Steady-State Analysis of Load Balancing Algorithms in the Sub-Halfin-Whitt Regime
Authors:
Preprint
Abstract
This paper studies a class of load balancing algorithms for many-server ($N$ servers) systems assuming finite buffer with size $b-1$ (i.e. a server can have at most one job in service and $b-1$ jobs in queue). We focus on steady-state performance of load balancing algorithms in the heavy traffic regime such that the load of system is $\lambda = 1 - N^{-\alpha}$ for $0<\alpha<0.5,$ which we call sub-Halfin-Whitt regime ($\alpha=0.5$ is the so-called the Halfin-Whitt regime). We establish a sufficient condition under which the probability that an incoming job is routed to an idle server is one asymptotically. The class of load balancing algorithms that satisfy the condition includes join-the-shortest-queue (JSQ), idle-one-first (I1F), join-the-idle-queue (JIQ), and power-of-$d$-choices (Po$d$) with $d=N^\alpha\log N$. The proof of the main result is based on the framework of Stein's method. A key contribution is to use a simple generator approximation based on state space collapse.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- SCALABLE LOAD BALANCING IN NETWORKED SYSTEMS: UNIVERSALITY PROPERTIES AND STOCHASTIC COUPLING METHODS2019
- Join-the-shortest queue diffusion limit in Halfin–Whitt regime: Tail asymptotics and scaling of extremaThe Annals of Applied Probability, 2019
- Heavy-Traffic Delay Insensitivity in Connection-Level Models of Data Transfer with Proportionally Fair Bandwidth SharingACM SIGMETRICS Performance Evaluation Review, 2018
- Expected Values Estimated via Mean-Field Approximation are 1/N-AccurateProceedings of the ACM on Measurement and Analysis of Computing Systems, 2017
- Stein's Method for Mean Field Approximations in Light and Heavy Traffic RegimesProceedings of the ACM on Measurement and Analysis of Computing Systems, 2017
- Stein’s method for steady-state diffusion approximations of $M/\mathit{Ph}/n+M$ systemsThe Annals of Applied Probability, 2017
- Pull-based load distribution in large-scale heterogeneous service systemsQueueing Systems, 2015
- Join-Idle-Queue: A novel load balancing algorithm for dynamically scalable web servicesPerformance Evaluation, 2011
- Performance of Multiclass Markovian Queueing Networks Via Piecewise Linear Lyapunov FunctionsThe Annals of Applied Probability, 2001
- The power of two choices in randomized load balancingIEEE Transactions on Parallel and Distributed Systems, 2001