## 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 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.

Original language | English (US) |
---|---|

Pages (from-to) | 353-391 |

Number of pages | 39 |

Journal | Queueing Systems |

Volume | 101 |

Issue number | 3-4 |

DOIs | |

State | Published - 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