Join-the-shortest queue diffusion limit in Halfin–Whitt regime: Tail asymptotics and scaling of extrema
Authors:
- Sayan BanerjeeSBSayan Banerjee
- Debankur MukherjeeDMDebankur Mukherjee
- 1 April 2019
- journal article
- research article
- Published by Institute of Mathematical Statistics in The Annals of Applied Probability
- Vol. 29 (2) , 1262-1309
Abstract
Consider a system of $N$ parallel single-server queues with unit-ex ponential 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 (Math. Oper. Res. 43 (2018) 867–886) 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 convergence result extends to the steady state as well, that is, stationary occupancy measure of the system converges weakly to the steady state of the diffusion process as $N\to\infty$, proving the interchange of limits result. 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. The technique and the intermediate results might be of independent interest, and can possibly be used in understanding the bulk behavior of the process.
Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- First Passage Times to Congested States of Many-Server Systems in the Halfin–Whitt RegimeStochastic Models, 2014
- Steady-state $GI/G/n$ queue in the Halfin–Whitt regimeThe Annals of Applied Probability, 2013
- On the rate of convergence to stationarity of the M/M/N queue in the Halfin–Whitt regimeThe Annals of Applied Probability, 2013
- Transient behavior of the Halfin–Whitt diffusionStochastic Processes and their Applications, 2011
- Introduction to Probability Theory2010
- Slow energy dissipation in anharmonic oscillator chainsCommunications on Pure and Applied Mathematics, 2009
- Long time asymptotics for constrained diffusions in polyhedral domainsStochastic Processes and their Applications, 2007
- On Positive Recurrence of Constrained Diffusion ProcessesThe Annals of Probability, 2001
- Lyapunov Functions for Semimartingale Reflecting Brownian MotionsThe Annals of Probability, 1994
- Heavy-Traffic Limits for Queues with Many Exponential ServersOperations Research, 1981