Join-the-Shortest Queue Diffusion Limit in Halfin-Whitt Regime: Tail Asymptotics and Scaling of Extrema

Abstract

Consider a system of $N$ parallel single-server queues with unit-exponential service time distribution and a single dispatcher where tasks arrive as a Poisson process of rate $\lambda (N)$. When a task arrives, the dispatcher assigns it to one of the servers according to the Join-the-Shortest Queue (JSQ) policy. Eschenfeldt and Gamarnik (2015) established that in the Halfin-Whitt regime where $(N-\lambda (N))/\sqrt{N}\to \beta >0$ as $N\to \infty$, appropriately scaled occupancy measure of the system under the JSQ policy converges weakly on any finite time interval to a certain diffusion process as $N\to \infty$. Recently, it was further established by Braverman (2018) that the stationary occupancy measure of the system converges weakly to the steady state of the diffusion process as $N\to \infty$. In this paper we perform a detailed analysis of the steady state of the above diffusion process. Specifically, we establish precise tail-asymptotics of the stationary distribution and scaling of extrema of the process on large time-interval. Our results imply that the asymptotic steady-state scaled number of servers with queue length two or larger exhibits an Exponential tail, whereas that for the number of idle servers turns out to be Gaussian. From the methodological point of view, the diffusion process under consideration goes beyond the state-of-the-art techniques in the study of the steady-state of diffusion processes. Lack of any closed form expression for the steady state and intricate interdependency of the process dynamics on its local times make the analysis significantly challenging. We develop a technique involving the theory of regenerative processes that provides a tractable form for the stationary measure, and in conjunction with several sharp hitting time estimates, acts as a key vehicle in establishing the results.

arXiv comment41 pages; To appear in the Annals of Applied Probability

References in corpus (6)

• Universality of Power-of-$d$ Load Balancing in Many-Server Systems
• Steady-state $GI/GI/n$ queue in the Halfin-Whitt regime
• Universality of Load Balancing Schemes on Diffusion Scale
• Asymptotically Optimal Load Balancing Topologies
• On the rate of convergence to stationarity of the M/M/N queue in the Halfin-Whitt regime
• Economies-of-scale in resource sharing systems: tutorial and partial review of the QED heavy-traffic regime

Cited by in corpus (6)

• Scalable load balancing in networked systems: A survey of recent advances
• Join-the-Shortest Queue Diffusion Limit in Halfin-Whitt Regime: Sensitivity on the Heavy-traffic Parameter
• Load balancing system under Join the Shortest Queue: Many-Server-Heavy-Traffic Asymptotics
• Many-Server Asymptotics for Join-the-Shortest-Queue: Large Deviations and Rare Events
• Steady-State Convergence of the Continuous-Time Routing System with General Distributions in Heavy Traffic
• The Inert Drift Atlas Model