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

fluid limithydrodynamic limitinteracting particle systemmeasure-valued processespower of two choicespropagation of chaosrandomized load balancingstochastic network

Mathematics Subject Classification ID

Functional limit theorems; invariance principles (60F17) Queueing theory (aspects of probability theory) (60K25) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Stochastic network models in operations research (90B15) Queues and service in operations research (90B22)

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.

Review text

The paper considers a network of \(N\) parallel queues in which jobs arrive according to a renewal process with rate \(\lambda N\). These jobs with independent and identically distributed service times are assigned to the shortest queue among a subset of \(d\) queues chosen uniformly at random, and leave the network on completion of the service. The main result of this article, Theorem 2.6, shows that under general conditions on the service time distribution and arrival processes, as \(N \to \infty \), the sequence of scaled state processes \(\nu (N)/N\) converges weakly to the unique solution of a coupled system of deterministic measure-valued equations.

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

• 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
• 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?)
• 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

(19)

• Interference queueing networks on grids
• The hydrodynamic limit of a randomized load balancing network
• Balancing queues by mean field interaction
• Randomized longest-queue-first scheduling for large-scale buffered systems
• Asymptotic independence of queues under randomized load balancing
• Chaoticity on path space for a queueing network with selection of the shortest queue among several
• Scalable Load Balancing in Networked Systems: A Survey of Recent Advances
• Diffusion approximations for load balancing mechanisms in cloud storage systems
• Insensitivity of the mean field limit of loss systems under \(\mathrm{SQ}(d)\) routeing
• A q-analogue of a result of Carlitz, Scoville and Vaughan via the homology of posets
• Large-time behaviour and the second eigenvalue problem for finite-state mean-field interacting particle systems
• Long-Time Limit of Nonlinearly Coupled Measure-Valued Equations that Model Many-Server Queues with Reneging
• 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
• A fluid approximation for a matching model with general reneging distributions
• Invariance principle and McKean-Vlasov limit for randomized load balancing in heavy traffic
• Fluid limit for a multi-server, multiclass random order of service queue with reneging and tracking of residual patience times
• Hydrodynamic limits of non-Markovian interacting particle systems on sparse graphs
• Mean-field analysis for load balancing on spatial graphs

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)