Asymptotic optimality of power-of-d load balancing in large-scale systems

DOI10.1287/MOOR.2019.1042MaRDI QIDQ3387935zbMATH OpenOpenAlexFDO

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

Publication date 8 January 2021

Published in Mathematics of Operations Research (Search for Journal in Brave)

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

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) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Abstract: We consider a system of $N$ identical server pools and a single dispatcher where tasks arrive as a Poisson process of rate $lambda(N)$. Arriving tasks cannot be queued, and must immediately be assigned to one of the server pools to start execution, or discarded. The execution times are assumed to be exponentially distributed with unit mean, and do not depend on the number of other tasks receiving service. However, the experienced performance (e.g. in terms of received throughput) does degrade with an increasing number of concurrent tasks at the same server pool. The dispatcher therefore aims to evenly distribute the tasks across the various server pools. Specifically, when a task arrives, the dispatcher assigns it to the server pool with the minimum number of tasks among $d(N)$ randomly selected server pools. This assignment strategy is called the JSQ$(d(N))$ scheme, as it resembles the power-of-$d$ version of the Join-the-Shortest-Queue (JSQ) policy, and will also be referred to as such in the special case $d(N)=N$. We construct a stochastic coupling to bound the difference in the system occupancy 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 case $d(N)oinfty$ and $lambda(N)/Nolambda$ as $Noinfty$, along with the associated fixed point. The fluid limit turns out to be insensitive to the exact growth rate of $d(N)$, and coincides with that for the JSQ policy. We further leverage the coupling to establish that the diffusion limit corresponds to that for the JSQ policy as well, as long as $d(N)/sqrtNlog(N)oinfty$, and characterize the common limiting diffusion process. These results indicate that the JSQ optimality 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

• Universality of power-of-\(d\) load balancing in many-server systems
• Universality of load balancing schemes on the diffusion scale
• Scalable load balancing in networked systems: universality properties and stochastic coupling methods
• Power-of-d-Choices with Memory: Fluid Limit and Optimality
• Asymptotically optimal open-loop load balancing

Cites work

• scientific article; zbMATH DE number 44889 (Why is no real title available?)
• scientific article; zbMATH DE number 3500818 (Why is no real title available?)
• scientific article; zbMATH DE number 1947316 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• A Skorokhod map on measure-valued paths with applications to priority queues
• A simple dynamic routing problem
• Deterministic and stochastic differential inclusions with multiple surfaces of discontinuity
• Double Skorokhod Map and Reneging Real-Time Queues
• Extremal properties of the shortest/longest non-full queue policies in finite-capacity systems with state-dependent service rates
• Heavy traffic analysis for EDF queues with reneging
• Heavy-Traffic Approximations for Service Systems With Blocking
• Heavy-Traffic Limits for Queues with Many Exponential Servers
• Join the shortest queue with many servers. The heavy-traffic asymptotics
• Large loss networks
• Largest weighted delay first scheduling: Large deviations and optimality
• Law of large numbers for the many-server earliest-deadline-first queue
• Martingale proofs of many-server heavy-traffic limits for Markovian queues
• On the optimal assignment of customers to parallel servers
• Optimal routing and buffer allocation for a class of finite capacity queueing systems
• Optimality of routing and servicing in dependent parallel processing systems
• Optimality of the shortest line discipline
• Optimality of the shortest line discipline with state-dependent service rates
• Pull-based load distribution among heterogeneous parallel servers: the case of multiple routers
• Pull-based load distribution in large-scale heterogeneous service systems
• Queueing system with selection of the shortest of two queues: An asymptotic approach
• Reflected diffusions defined via the extended Skorokhod map
• Sample Path Criteria for Weak Majorization
• Some Properties of the Erlang Loss Function
• Stochastic differential equations with reflecting boundary conditions
• Stochastic-Process Limits
• The Effect of Increasing Routing Choice on Resource Pooling
• The Skorohod oblique reflection problem in domains with corners and application to stochastic differential equations
• Universality of load balancing schemes on the diffusion scale
• Universality of power-of-\(d\) load balancing in many-server systems

Cited in

(19)

• Self-Learning Threshold-Based Load Balancing
• Infinite horizon asymptotic average optimality for large-scale parallel server networks
• Scalable Load Balancing in Networked Systems: A Survey of Recent Advances
• Scalable load balancing in networked systems: universality properties and stochastic coupling methods
• Logarithmic heavy traffic error bounds in generalized switch and load balancing systems
• Sensitivity of mean-field fluctuations in Erlang loss models with randomized routing
• Economies-of-scale in many-server queueing systems: tutorial and partial review of the QED Halfin-Whitt heavy-traffic regime
• Universality of power-of-\(d\) load balancing in many-server systems
• Queue-length-aware dispatching in large-scale heterogeneous systems
• Delay, memory, and messaging tradeoffs in distributed service systems
• Asymptotically optimal open-loop load balancing
• Load Balancing Under Strict Compatibility Constraints
• Utility Maximizing Load Balancing Policies
• A load balancing system in the many-server heavy-traffic asymptotics
• Pull-based load distribution in large-scale heterogeneous service systems
• Universality of load balancing schemes on the diffusion scale
• Systems with large flexible server pools: instability of ``natural load balancing
• A general ``power-of-\(d\) dispatching framework for heterogeneous systems
• Diffusion approximations for load balancing mechanisms in cloud storage systems

This page was built for publication: Asymptotic optimality of power-of-\(d\) load balancing in large-scale systems

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