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

DOI10.1287/STSY.2018.0016MaRDI QIDQ5113886zbMATH OpenOpenAlexWikidataFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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)

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.

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

Cites work

• A simple dynamic routing problem
• Asymptotic independence of queues under randomized load balancing
• Deciding Which Queue to Join: Some Counterexamples
• Functional central limit theorems for a large network in which customers join the shortest of several queues
• Heavy-Traffic Limits for Queues with Many Exponential Servers
• Insensitive versus efficient dynamic load balancing in networks without blocking
• Join the shortest queue with many servers. The heavy-traffic asymptotics
• Join-the-shortest queue diffusion limit in Halfin-Whitt regime: tail asymptotics and scaling of extrema
• Large loss networks
• Large-deviation bounds for sampling without replacement
• Martingale proofs of many-server heavy-traffic limits for Markovian queues
• On the maximum queue length in the supermarket model
• On the optimal assignment of customers to parallel servers
• Optimal routing and buffer allocation for a class of finite capacity queueing systems
• Optimality of the shortest line discipline
• Probability Inequalities for Sums of Bounded Random Variables
• Queueing system with selection of the shortest of two queues: An asymptotic approach
• Sample Path Criteria for Weak Majorization
• Scalable load balancing in networked systems: universality properties and stochastic coupling methods
• Spectral gap of the Erlang A model in the Halfin-Whitt regime
• Stochastic-Process Limits
• Strong approximation for the supermarket model
• The supermarket model with bounded queue lengths in equilibrium
• Transient behavior of the Halfin-Whitt diffusion
• Universality of load balancing schemes on the diffusion scale

Cited in

(22)

• A general ``power-of-\(d\) dispatching framework for heterogeneous systems
• Job assignment in large-scale service systems with affinity relations
• 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
• Join Idle Queue with Service Elasticity: Large-Scale Asymptotics of a Nonmonotone System
• Universality of load balancing schemes on the diffusion scale
• Scalable load balancing in networked systems: universality properties and stochastic coupling methods
• Dynamic routing in a distributed parallel many-server service system: the effect of \(\xi \)-choice
• Many-server asymptotics for join-the-shortest-queue: large deviations and rare events
• Diffusion-level universality of many-server systems with concurrent service
• <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
• Power-of-two sampling in redundancy systems: the impact of assignment constraints
• k-nearest neighbor queues with delayed information
• Asymptotic optimality of power-of-\(d\) load balancing in large-scale systems
• A \(q\)-analogue of a result of Carlitz, Scoville and Vaughan via the homology of posets
• Scalable Load Balancing in Networked Systems: A Survey of Recent Advances
• Economies-of-scale in many-server queueing systems: tutorial and partial review of the QED Halfin-Whitt heavy-traffic regime
• A load balancing system in the many-server heavy-traffic asymptotics
• Near equilibrium fluctuations for supermarket models with growing choices
• Zero-wait load balancing with sparse messaging

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)