A load balancing system in the many-server heavy-traffic asymptotics

Daniela Hurtado-Lange () and Siva Theja Maguluri ()
Additional contact information
Daniela Hurtado-Lange: William & Mary
Siva Theja Maguluri: Georgia Institute of Technology

Queueing Systems: Theory and Applications, 2022, vol. 101, issue 3, No 6, 353-391

Abstract: 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^{-\alpha }$$ 1 - N - α , where $$\alpha >0$$ α > 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\rightarrow \infty $$ N → ∞ , and subsumes several regimes, such as the Halfin–Whitt regime ( $$\alpha =1/2$$ α = 1 / 2 ), the NDS regime ( $$\alpha =1$$ α = 1 ), as $$\alpha \downarrow 0$$ α ↓ 0 it approximates mean field and as $$\alpha \rightarrow \infty $$ α → ∞ it approximates the classical heavy-traffic regime. Most of the prior work focuses on regimes with $$\alpha \in [0,1]$$ α ∈ [ 0 , 1 ] . In this paper, we focus on the case when $$\alpha >1$$ α > 1 and the routing algorithm is power-of-d choices with $$d=\lceil cN^\beta \rceil $$ d = ⌈ c N β ⌉ for some constants $$c>0$$ c > 0 and $$\beta \ge 0$$ β ≥ 0 . We prove that $$\alpha +\beta >3$$ α + β > 3 is sufficient to observe that the average queue length scaled by $$N^{1-\alpha }$$ N 1 - α converges to an exponential random variable. In other words, if $$\alpha +\beta >3$$ α + β > 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 $$\alpha >3$$ α > 3 and if routing occurs according to JSQ we require $$\alpha >2$$ α > 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.

Keywords: Many-server heavy-traffic; Load balancing system; Stein’s method; Transform method; State space collapse; Join the shortest queue; Power-of-d choices; Drift method; Lyapunov drift; 60K25; 68M20; 90B22; 60H99 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11134-022-09847-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:queues:v:101:y:2022:i:3:d:10.1007_s11134-022-09847-7

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/11134/

DOI: 10.1007/s11134-022-09847-7

Access Statistics for this article

Queueing Systems: Theory and Applications is currently edited by Sergey Foss

More articles in Queueing Systems: Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().