The hydrodynamic limit of a randomized load balancing network

DOI10.1214/18-AAP1444MaRDI QIDQ2330457zbMATH OpenWikidataFDO

Authors Reza Aghajani, Kavita Ramanan

Publication date 22 October 2019

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

Full work available at URL https://arxiv.org/abs/1707.02005, https://projecteuclid.org/euclid.aoap/1563869039

zbMATH Keywords

interacting particle systempropagation of chaoshydrodynamic limitfluid limitmeasure-valued processesstochastic networkrandomized load balancingpower of two choices

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) 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) Functional limit theorems; invariance principles (60F17) Stochastic network models in operations research (90B15)

Abstract: Randomized load balancing networks arise in a variety of applications, and allow for efficient sharing of resources, while being relatively easy to implement. We consider a network of parallel queues in which incoming jobs with independent and identically distributed service times are assigned to the shortest queue among a randomly chosen subset of $d$ queues, and leave the network on completion of service. Prior work on dynamical properties of this model has focused on the case of exponential service distributions. In this work, we analyze the more realistic case of general service distributions. We first introduce a novel particle representation of the state of the network, and characterize the state dynamics via a sequence of interacting measure-valued stochastic processes. Under mild assumptions, we show that the sequence of scaled state processes converges, as the number of servers goes to infinity, to a hydrodynamic limit that is characterized as the unique solution to a countable system of coupled deterministic measure-valued equations. We also establish a propagation of chaos result that shows that finite collections of queues are asymptotically independent. The general framework developed here is potentially useful for analyzing a larger class of models arising in diverse fields including biology and materials science.

Recommendations

• A \(q\)-analogue of a result of Carlitz, Scoville and Vaughan via the homology of posets
• Asymptotic independence of queues under randomized load balancing
• Strong approximation for the supermarket model
• Balancing queues by mean field interaction
• Universality of load balancing schemes on the diffusion scale

Cites work

• scientific article; zbMATH DE number 1631026 (Why is no real title available?)
• scientific article; zbMATH DE number 3951715 (Why is no real title available?)
• scientific article; zbMATH DE number 1515832 (Why is no real title available?)
• scientific article; zbMATH DE number 2199827 (Why is no real title available?)
• scientific article; zbMATH DE number 3274494 (Why is no real title available?)
• Analyses of load stealing models based on families of differential equations
• Analysis of Randomized Join-the-Shortest-Queue (JSQ) Schemes in Large Heterogeneous Processor-Sharing Systems
• Applied Probability and Queues
• Asymptotic behaviour of the variance of renewal processes and random walks
• Asymptotic independence of queues under randomized load balancing
• Chaoticity on path space for a queueing network with selection of the shortest queue among several
• Decay of tails at equilibrium for FIFO join the shortest queue networks
• Fluid limits of many-server queues with reneging
• Law of large numbers limits for many-server queues
• Load balancing via random local search in closed and open systems
• On the Skorokhod topology
• Point processes and queues. Martingale dynamics
• Queueing system with selection of the shortest of two queues: An asymptotic approach
• Stability of join the shortest queue networks
• Statistical Analysis of a Telephone Call Center
• Strong approximation for the supermarket model
• The hydrodynamic limit of a randomized load balancing network

Cited in

(14)

• Interference queueing networks on grids
• Scalable Load Balancing in Networked Systems: A Survey of Recent Advances
• A fluid approximation for a matching model with general reneging distributions
• Large-time behaviour and the second eigenvalue problem for finite-state mean-field interacting particle systems
• Asymptotic independence of queues under randomized load balancing
• Balancing queues by mean field interaction
• Randomized longest-queue-first scheduling for large-scale buffered systems
• Insensitivity of the mean field limit of loss systems under \(\mathrm{SQ}(d)\) routeing
• Long-Time Limit of Nonlinearly Coupled Measure-Valued Equations that Model Many-Server Queues with Reneging
• The hydrodynamic limit of a randomized load balancing network
• A \(q\)-analogue of a result of Carlitz, Scoville and Vaughan via the homology of posets
• Mean-field fluctuations at diffusion scale in threshold-based randomized routing for processor sharing systems and applications
• On the maximum queue length of the hyper scalable load balancing push strategy
• Diffusion approximations for load balancing mechanisms in cloud storage systems

This page was built for publication: The hydrodynamic limit of a randomized load balancing network

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