Journal
ANNALS OF PROBABILITY
Volume 34, Issue 2, Pages 493-527Publisher
INST MATHEMATICAL STATISTICS-IMS
DOI: 10.1214/00911790500000710
Keywords
supermarket model; join the shortest queue; random choices; power of two choices; maximum queue length; load balancing; equilibrium; concentration of measure
Categories
Ask authors/readers for more resources
There are n queues, each with a single server. Customers arrive in a Poisson process at rate lambda n, where 0 < lambda < 1. Upon arrival each customer selects d >= 2 servers uniformly at random, and joins the queue at a least-loaded server among those chosen. Service times are independent exponentially distributed random variables with mean 1. We show that the system is rapidly mixing, and then investigate the maximum length of a queue in the equilibrium distribution. We prove that with probability tending to 1 as n -> infinity the maximum queue length takes at most two values, which are lnlnn/lnd + O(l).
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available