We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A load balancing system in the many-server heavy-traffic asymptotics.
- Authors
Hurtado-Lange, Daniela; Maguluri, Siva Theja
- Abstract
We study a load balancing system in the many-server heavy-traffic regime. We consider a system with N servers, where jobs arrive to the system according to a Poisson process and have an exponentially distributed size with mean 1. We parametrize the arrival rate so that the arrival rate per server is 1 - N - α , where α > 0 is a parameter that represents how fast the load grows with respect to the number of servers. The many-server heavy-traffic regime corresponds to the limit as N → ∞ , and subsumes several regimes, such as the Halfin–Whitt regime ( α = 1 / 2 ), the NDS regime ( α = 1 ), as α ↓ 0 it approximates mean field and as α → ∞ it approximates the classical heavy-traffic regime. Most of the prior work focuses on regimes with α ∈ [ 0 , 1 ] . In this paper, we focus on the case when α > 1 and the routing algorithm is power-of-d choices with d = ⌈ c N β ⌉ for some constants c > 0 and β ≥ 0 . We prove that α + β > 3 is sufficient to observe that the average queue length scaled by N 1 - α converges to an exponential random variable. In other words, if α + β > 3 , the scaled average queue length behaves similarly to the classical heavy-traffic regime. In particular, this result implies that if d is constant, we require α > 3 and if routing occurs according to JSQ we require α > 2 . We provide two proofs to our result: one based on the Transform method introduced in Hurtado-Lange and Maguluri (Stoch Syst 10(4):275–309, 2020) and one based on Stein's method. In the second proof, we also compute the rate of convergence in Wasserstein's distance. In both cases, we additionally compute the rate of convergence in expected value. All of our proofs are powered by state space collapse.
- Subjects
ROUTING algorithms; POISSON processes; RANDOM variables; STATE power; QUEUEING networks; QUEUING theory
- Publication
Queueing Systems, 2022, Vol 101, Issue 3/4, p353
- ISSN
0257-0130
- Publication type
Article
- DOI
10.1007/s11134-022-09847-7