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

Daniela Hurtado-Lange*, Siva Theja Maguluri

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

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= ⌈ cNβ⌉ for some constants c> 0 and β≥ 0. We prove that α+ β> 3 is sufficient to observe that the average queue length scaled by N1-α 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.

Original languageEnglish (US)
Pages (from-to)353-391
Number of pages39
JournalQueueing Systems
Volume101
Issue number3-4
DOIs
StatePublished - Aug 2022

Keywords

  • Drift method
  • Join the shortest queue
  • Load balancing system
  • Lyapunov drift
  • Many-server heavy-traffic
  • Power-of-d choices
  • State space collapse
  • Stein’s method
  • Transform method

ASJC Scopus subject areas

  • Statistics and Probability
  • Computer Science Applications
  • Management Science and Operations Research
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'A load balancing system in the many-server heavy-traffic asymptotics'. Together they form a unique fingerprint.

Cite this