Join the Shortest Queue with Many Servers. The Heavy Traffic Asymptotics

2015/02/03 by Patrick Eschenfeldt, David Gamarnik, Eschenfeldt, Patrick +1 · 4 citations
Business, Management and Accounting · Decision Sciences · Engineering · #Advanced Queuing Theory Analysis #Probability and Risk Models #Advanced Wireless Network Optimization

paper · pdf · doi:10.48550/arxiv.1502.00999

Abstract

We consider queueing systems with n parallel queues under a Join the Shortest Queue (JSQ) policy in the Halfin-Whitt heavy traffic regime. We use the martingale method to prove that a scaled process counting the number of idle servers and queues of length exactly 2 weakly converges to a two-dimensional reflected Ornstein-Uhlenbeck process, while processes counting longer queues converge to a deterministic system decaying to zero in constant time. This limiting system is comparable to that of the traditional Halfin-Whitt model, but there are key differences in the queueing behavior of the JSQ model. In particular, only a vanishing fraction of customers will have to wait, but those who do will incur a constant order waiting time.

Cited by

• Transform Method for Stochastic Processing and Matching Networks
• Zero-Waiting Load Balancing with Heterogeneous Servers in Heavy Traffic
• Large Deviation Asymptotics for the Supermarket Model with Growing Choices
• Steady-State Behavior of Some Load Balancing Mechanisms in Cloud Storage Systems

Related

• Many-server asymptotics for Join-the-Shortest Queue in the Super-Halfin-Whitt Scaling Window
• Asymptotic Optimality of the Speed-Aware Join-the-Shortest-Queue in the Halfin-Whitt Regime for Heterogeneous Systems
• The join-the-shortest-queue system in the Halfin-Whitt regime: rates of convergence to the diffusion limit
• Supermarket Queueing System in the Heavy Traffic Regime. Short Queue Dynamics
• Many-Server Asymptotics for Join-the-Shortest-Queue: Large Deviations and Rare Events