Universality of power-of-d load balancing in many-server systems

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

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

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

Recommendations

• Asymptotic optimality of power-of-\(d\) load balancing in large-scale systems
• Universality of load balancing schemes on the diffusion scale
• Scalable load balancing in networked systems: universality properties and stochastic coupling methods
• A load balancing system in the many-server heavy-traffic asymptotics
• Power-of-d-Choices with Memory: Fluid Limit and Optimality

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 (21)

• Join Idle Queue with Service Elasticity: Large-Scale Asymptotics of a Nonmonotone System
• Scalable Load Balancing in Networked Systems: A Survey of Recent Advances
• Scalable load balancing in networked systems: universality properties and stochastic coupling methods
• Job assignment in large-scale service systems with affinity relations
• Many-server asymptotics for join-the-shortest-queue: large deviations and rare events
• Economies-of-scale in many-server queueing systems: tutorial and partial review of the QED Halfin-Whitt heavy-traffic regime
• Asymptotic optimality of power-of-\(d\) load balancing in large-scale systems
• Dynamic routing in a distributed parallel many-server service system: the effect of \(\xi \)-choice
• k-nearest neighbor queues with delayed information
• <scp>Steady‐state</scp> analysis of load balancing with Coxian‐2 distributed service times
• Load Balancing Under Strict Compatibility Constraints
• Utility Maximizing Load Balancing Policies
• 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
• Steady-state analysis of load-balancing algorithms in the sub-Halfin-Whitt regime
• A \(q\)-analogue of a result of Carlitz, Scoville and Vaughan via the homology of posets
• Zero-wait load balancing with sparse messaging
• Universality of load balancing schemes on the diffusion scale
• Diffusion-level universality of many-server systems with concurrent service
• A general ``power-of-\(d\) dispatching framework for heterogeneous systems

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)