The hydrodynamic limit of a randomized load balancing network
Authors:
- Reza AghajaniRAReza Aghajani
- Kavita RamananKRKavita Ramanan
- 1 August 2019
- journal article
- research article
- Published by Institute of Mathematical Statistics in The Annals of Applied Probability
- Vol. 29 (4) , 2114-2174
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 subset of $d$ queues chosen uniformly at random, 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 countable sequence of interacting stochastic measure-valued evolution equations. 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. As a simple corollary, 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.
Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- Decay of tails at equilibrium for FIFO join the shortest queue networksThe Annals of Applied Probability, 2013
- Asymptotic independence of queues under randomized load balancingQueueing Systems, 2012
- Load balancing via random local search in closed and open systemsQueueing Systems, 2012
- Law of large numbers limits for many-server queuesThe Annals of Applied Probability, 2011
- Fluid limits of many-server queues with renegingThe Annals of Applied Probability, 2010
- Randomized load balancing with general service time distributionsACM SIGMETRICS Performance Evaluation Review, 2010
- Strong approximation for the supermarket modelThe Annals of Applied Probability, 2005
- Statistical Analysis of a Telephone Call CenterJournal of the American Statistical Association, 2005
- Chaoticity on path space for a queueing network with selection of the shortest queue among severalJournal of Applied Probability, 2000
- Asymptotic Behaviour of the Variance of Renewal Processes and Random WalksThe Annals of Probability, 1978