Universality of Power-of-d Load Balancing in Many-Server Systems

DOI10.1287/STSY.2018.0016zbMATH Open1446.60073arXiv1612.00723OpenAlexW3102247904WikidataQ128679219 ScholiaQ128679219MaRDI QIDQ5113886FDOQ5113886

Johan S. H. van Leeuwaarden, Phil Whiting, Sem Borst, Debankur Mukherjee

Publication date: 18 June 2020

Published in: Stochastic Systems (Search for Journal in Brave)

Abstract: We consider a system of $N$ parallel single-server queues with unit exponential service rates and a single dispatcher where tasks arrive as a Poisson process of rate $lambda(N)$. When a task arrives, the dispatcher assigns it to a server with the shortest queue among $d(N)$ randomly selected servers ($1leqd(N)leqN$). This load balancing strategy is referred to as a JSQ($d(N)$) scheme, marking that it subsumes the celebrated Join-the-Shortest Queue (JSQ) policy as a crucial special case for $d(N)=N$. We construct a stochastic coupling to bound the difference in the queue length processes between the JSQ policy and a scheme with an arbitrary value of $d(N)$. We use the coupling to derive the fluid limit in the regime where $lambda(N)/Nolambda<1$ as $Noinfty$ with $d(N)oinfty$, along with the associated fixed point. The fluid limit turns out not to depend on the exact growth rate of $d(N)$, and in particular coincides with that for the JSQ policy. We further leverage the coupling to establish that the diffusion limit in the critical regime where $$ as $Noinfty$ with $d(N)/(sqrtNlog(N))oinfty$ corresponds to that for the JSQ policy. These results indicate that the optimality of the JSQ policy can be preserved at the fluid-level and diffusion-level while reducing the overhead by nearly a factor O($N$) and O($sqrtN/log(N)$), respectively.

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

zbMATH Keywords

load balancingfunctional limit theoremsdiffusion limitfluid limitjoin the shortest queuestochastic couplingmany-server asymptoticspower-of-\(d\) scheme

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Queueing theory (aspects of probability theory) (60K25) Functional limit theorems; invariance principles (60F17)

Cites Work

• Probability Inequalities for Sums of Bounded Random Variables
• Queueing system with selection of the shortest of two queues: An asymptotic approach
• Stochastic-Process Limits
• Heavy-Traffic Limits for Queues with Many Exponential Servers
• Martingale proofs of many-server heavy-traffic limits for Markovian queues
• Large loss networks
• Functional central limit theorems for a large network in which customers join the shortest of several queues
• On the maximum queue length in the supermarket model
• Asymptotic independence of queues under randomized load balancing
• A simple dynamic routing problem
• On the optimal assignment of customers to parallel servers
• Optimality of the shortest line discipline
• Deciding Which Queue to Join: Some Counterexamples
• Spectral gap of the Erlang A model in the Halfin-Whitt regime
• Transient behavior of the Halfin-Whitt diffusion
• Strong approximation for the supermarket model
• Optimal routing and buffer allocation for a class of finite capacity queueing systems
• 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
• Insensitive versus efficient dynamic load balancing in networks without blocking
• Universality of load balancing schemes on the diffusion scale
• Large-Deviation Bounds for Sampling without Replacement
• SCALABLE LOAD BALANCING IN NETWORKED SYSTEMS: UNIVERSALITY PROPERTIES AND STOCHASTIC COUPLING METHODS
• The supermarket model with bounded queue lengths in equilibrium
• Sample Path Criteria for Weak Majorization

Cited In (14)

• k-Nearest Neighbor Queues with Delayed Information
• Join Idle Queue with Service Elasticity: Large-Scale Asymptotics of a Nonmonotone System
• Scalable Load Balancing in Networked Systems: A Survey of Recent Advances
• Job assignment in large-scale service systems with affinity relations
• Many-server asymptotics for join-the-shortest-queue: large deviations and rare events
• Dynamic routing in a distributed parallel many-server service system: the effect of \(\xi \)-choice
• A load balancing system in the many-server heavy-traffic asymptotics
• Near equilibrium fluctuations for supermarket models with growing choices
• Join-the-shortest queue diffusion limit in Halfin-Whitt regime: sensitivity on the heavy-traffic parameter
• Asymptotic Optimality of Power-of-d Load Balancing in Large-Scale Systems
• Zero-wait load balancing with sparse messaging
• Diffusion-level universality of many-server systems with concurrent service
• Steady-state analysis of load-balancing algorithms in the sub-Halfin–Whitt regime
• Economies-of-Scale in Many-Server Queueing Systems: Tutorial and Partial Review of the QED Halfin--Whitt Heavy-Traffic Regime

This page was built for publication: Universality of Power-of-d Load Balancing in Many-Server Systems

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