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

DOI10.1287/MOOR.2019.1042zbMATH Open1455.60124arXiv1612.00722OpenAlexW2980494667MaRDI QIDQ3387935FDOQ3387935

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)

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.

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

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

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)

Cites Work

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

Cited In (19)

• Self-Learning Threshold-Based Load Balancing
• Scalable Load Balancing in Networked Systems: A Survey of Recent Advances
• Infinite horizon asymptotic average optimality for large-scale parallel server networks
• 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
• Load Balancing Under Strict Compatibility Constraints
• Utility Maximizing Load Balancing Policies
• Asymptotically optimal open-loop load balancing
• 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
• Diffusion approximations for load balancing mechanisms in cloud storage systems
• A general ``power-of-\(d\) dispatching framework for heterogeneous 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)