Universality of load balancing schemes on the diffusion scale

DOI10.1017/JPR.2016.68MaRDI QIDQ2956514zbMATH OpenOpenAlexDBLPWikidataFDO

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

Publication date 17 January 2017

Published in Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.02657, https://projecteuclid.org/euclid.jap/1481132840

zbMATH Keywords

load balancingqueueing theorysample path comparisonstochastic couplingsupermarket mode

Mathematics Subject Classification ID

Queueing theory (aspects of probability theory) (60K25) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Communication networks in operations research (90B18) Queues and service in operations research (90B22) Stochastic scheduling theory in operations research (90B36)

Abstract: We consider a system of $N$ parallel queues with identical exponential service rates and a single dispatcher where tasks arrive as a Poisson process. When a task arrives, the dispatcher always assigns it to an idle server, if there is any, and to a server with the shortest queue among $d$ randomly selected servers otherwise $(1leqdleqN)$. This load balancing scheme subsumes the so-called Join-the-Idle Queue (JIQ) policy $(d=1)$ and the celebrated Join-the-Shortest Queue (JSQ) policy $(d=N)$ as two crucial special cases. We develop a stochastic coupling construction to obtain the diffusion limit of the queue process in the Halfin-Whitt heavy-traffic regime, and establish that it does not depend on the value of $d$, implying that assigning tasks to idle servers is sufficient for diffusion level optimality.

Recommendations

• Universality of power-of-d load balancing in many-server systems
• Asymptotic optimality of power-of-\(d\) load balancing in large-scale systems
• Scalable load balancing in networked systems: universality properties and stochastic coupling methods
• Asymptotic independence of queues under randomized load balancing
• Join-the-shortest queue diffusion limit in Halfin-Whitt regime: sensitivity on the heavy-traffic parameter

Cited in

(32)

• Asymptotics of insensitive load balancing and blocking phases
• Join-the-shortest queue diffusion limit in Halfin-Whitt regime: tail asymptotics and scaling of extrema
• The supermarket model with bounded queue lengths in equilibrium
• 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
• Join-the-shortest queue diffusion limit in Halfin-Whitt regime: sensitivity on the heavy-traffic parameter
• Zero-wait load balancing with sparse messaging
• A lower bound on the queueing delay in resource constrained load balancing
• Stability of JSQ in queues with general server-job class compatibilities
• Many-server asymptotics for join-the-shortest-queue: large deviations and rare events
• Analysis of the shortest relay queue policy in a cooperative random access network with collisions
• The hydrodynamic limit of a randomized load balancing network
• Pull-based load distribution among heterogeneous parallel servers: the case of multiple routers
• Steady-state analysis of the join-the-shortest-queue model in the Halfin-Whitt regime
• Asymptotic optimality of power-of-\(d\) load balancing in large-scale systems
• Asymptotic independence of queues under randomized load balancing
• Inventory accumulation with multiple products
• Large-scale join-idle-queue system with general service times
• To pool or not to pool: queueing design for large-scale service systems
• Self-Learning Threshold-Based Load Balancing
• Scalable Load Balancing in Networked Systems: A Survey of Recent Advances
• Universality of power-of-d load balancing in many-server systems
• Join Idle Queue with Service Elasticity: Large-Scale Asymptotics of a Nonmonotone System
• Scalable load balancing in networked systems: universality properties and stochastic coupling methods
• Diffusion approximations for load balancing mechanisms in cloud storage systems
• Insensitivity of the mean field limit of loss systems under \(\mathrm{SQ}(d)\) routeing
• scientific article; zbMATH DE number 6783405 (Why is no real title available?)
• <scp>Steady‐state</scp> analysis of load balancing with Coxian‐2 distributed service times
• Diffusion-level universality of many-server systems with concurrent service
• Utility Maximizing Load Balancing Policies
• Load Balancing Under Strict Compatibility Constraints
• Optimal rate-matrix pruning for large-scale heterogeneous systems

This page was built for publication: Universality of load balancing schemes on the diffusion scale

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