Load balancing and density dependent jump Markov processes
- 24 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 96 (02725428) , 213-222
- https://doi.org/10.1109/sfcs.1996.548480
Abstract
We provide a new approach for analyzing both static and dynamic randomized load balancing strategies. We demonstrate the approach by providing the first analysis of the following model: customers arrive as a Poisson stream of rate /spl lambda//sub n/, /spl lambda/<1, at a collection of n servers. Each customer chooses some constant d servers independently and uniformly at random from the n servers, and waits for service at the one with the fewest customers. Customers are served according to the first-in first-out (FIFO) protocol, and the service time for a customer is exponentially distributed with mean 1. We call this problem the supermarket model. We wish to know how the system behaves, and in particular we are interested in the expected time a customer spends in the system in equilibrium. The model provides a good abstraction of a simple, efficient load balancing scheme in the setting where jobs arrive at a large system of parallel processors. This model appears more realistic than similar models studied previously, in that it is both dynamic and open: that is, customers arrive over time, and the number of customers is not fixed.Keywords
This publication has 22 references indexed in Scilit:
- Asymptotic analysis of an assignment problem arising in a distributed communications protocolPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Tail bounds for occupancy and the satisfiability threshold conjecturePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- The Power-Series Algorithm Applied to the Shortest-Queue ModelOperations Research, 1992
- Efficient PRAM simulation on a distributed memory machinePublished by Association for Computing Machinery (ACM) ,1992
- A trace-driven simulation study of dynamic load balancingIEEE Transactions on Software Engineering, 1988
- Adaptive load sharing in homogeneous distributed systemsIEEE Transactions on Software Engineering, 1986
- Markov ProcessesPublished by Wiley ,1986
- Maximum matching in sparse random graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1981
- Optimality of the shortest line disciplineJournal of Applied Probability, 1977
- Ordinary Differential Equations in Banach SpacesLecture Notes in Mathematics, 1977