Load balancing system under Join the Shortest Queue: Many-Server-Heavy-Traffic Asymptotics

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.

References in corpus (8)

• Validity of heavy traffic steady-state approximations in generalized Jackson Networks
• Asymptotic optimality of maximum pressure policies in stochastic processing networks
• Scalable load balancing in networked systems: A survey of recent advances
• Diffusion models and steady-state approximations for exponentially ergodic Markovian queues
• Transform Methods for Heavy-Traffic Analysis
• Join-the-Shortest Queue Diffusion Limit in Halfin-Whitt Regime: Sensitivity on the Heavy-traffic Parameter
• On Universal Scaling of Distributed Queues under Load Balancing
• Throughput and Delay Optimality of Power-of-d Choices in Inhomogeneous Load Balancing Systems

Cited by in corpus (1)

• Heavy-Traffic Optimal Size- and State-Aware Dispatching