Join-the-shortest queue diffusion limit in Halfin-Whitt regime: sensitivity on the heavy-traffic parameter

DOI10.1214/19-AAP1496zbMATH Open1434.60263arXiv1809.01739OpenAlexW3006690594MaRDI QIDQ2180378FDOQ2180378

Authors: Sayan Banerjee, Debankur Mukherjee 

Publication date: 13 May 2020

Published in: The Annals of Applied Probability (Search for Journal in Brave)

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 (Math. Oper. Res., 43(3):867-886, 2018) identified a novel limiting diffusion process that arises as the weak-limit of the appropriately scaled occupancy measure of the system under the JSQ policy in the Halfin-Whitt regime, where $$ as $Noinfty$. The analysis of this diffusion goes beyond the state of the art techniques, and even proving its ergodicity is non-trivial, and was left as an open question. Recently, exploiting a generator expansion framework via the Stein's method, Braverman (arXiv:1801.05121, 2018) established its exponential ergodicity, and adapting a regenerative approach, Banerjee and Mukherjee (Ann. Appl. Probab., 29(2):1262-1309, 2018) analyzed the tail properties of the stationary distribution and path fluctuations of the diffusion. However, the analysis of the bulk behavior of the stationary distribution, viz., the moments, remained intractable until this work. In this paper, we perform a thorough analysis of the bulk behavior of the stationary distribution of the diffusion process, and discover that it exhibits different qualitative behavior, depending on the value of the heavy-traffic parameter $$. Moreover, we obtain precise asymptotic laws of the centered and scaled steady state distribution, as $$ tends to 0 and $infty$. Of particular interest, we also establish a certain intermittency phenomena in the $$ regime and a surprising distributional convergence result in the $$ regime.

Full work available at URL: https://arxiv.org/abs/1809.01739

Recommendations

• Join-the-shortest queue diffusion limit in Halfin-Whitt regime: tail asymptotics and scaling of extrema
• Join the shortest queue with many servers. The heavy-traffic asymptotics
• Steady-state analysis of the join-the-shortest-queue model in the Halfin-Whitt regime
• Transient behavior of the Halfin-Whitt diffusion
• Universality of load balancing schemes on the diffusion scale

zbMATH Keywords

local timeHalfin-Whitt regimeregenerative processesdiffusion limitjoin the shortest queuesteady-state analysisnonelliptic diffusion

Mathematics Subject Classification ID

Diffusion processes (60J60) Queueing theory (aspects of probability theory) (60K25) Stochastic integral equations (60H20) Renewal theory (60K05)

Cites Work

• Title not available (Why is that?)
• Markov chains and stochastic stability
• Concentration inequalities and model selection. Ecole d'Eté de Probabilités de Saint-Flour XXXIII -- 2003.
• Heavy-Traffic Limits for Queues with Many Exponential Servers
• Title not available (Why is that?)
• Steady-state GI/G/\(n\) queue in the Halfin-Whitt regime
• Lyapunov functions for semimartingale reflecting Brownian motions
• On the rate of convergence to stationarity of the M/M/\(n\) queue in the Halfin-Whitt regime
• Spectral gap of the Erlang A model in the Halfin-Whitt regime
• Transient behavior of the Halfin-Whitt diffusion
• On positive recurrence of constrained diffusion processes
• Long time asymptotics for constrained diffusions in polyhedral domains
• Slow energy dissipation in anharmonic oscillator chains
• Economies-of-scale in many-server queueing systems: tutorial and partial review of the QED Halfin-Whitt heavy-traffic regime
• Join-the-shortest queue diffusion limit in Halfin-Whitt regime: tail asymptotics and scaling of extrema
• Join the shortest queue with many servers. The heavy-traffic asymptotics
• First passage times to congested states of many-server systems in the Halfin-Whitt regime
• Universality of load balancing schemes on the diffusion scale
• Gravitation versus Brownian motion
• Steady-state analysis of the join-the-shortest-queue model in the Halfin-Whitt regime
• Scalable load balancing in networked systems: universality properties and stochastic coupling methods
• Universality of power-of-\(d\) load balancing in many-server systems

Cited In (9)

• Join-the-shortest queue diffusion limit in Halfin-Whitt regime: tail asymptotics and scaling of extrema
• Scalable Load Balancing in Networked Systems: A Survey of Recent Advances
• Join the shortest queue with many servers. The heavy-traffic asymptotics
• Steady-state analysis of the join-the-shortest-queue model in the Halfin-Whitt regime
• The inert drift atlas model
• The Join-the-Shortest-Queue System in the Halfin-Whitt Regime: Rates of Convergence to the Diffusion Limit
• A load balancing system in the many-server heavy-traffic asymptotics
• Inert drift system in a viscous fluid: steady state asymptotics and exponential ergodicity
• Universality of load balancing schemes on the diffusion scale

This page was built for publication: Join-the-shortest queue diffusion limit in Halfin-Whitt regime: sensitivity on the heavy-traffic parameter

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2180378)