Load Balancing in Stochastic Networks: Algorithms, Analysis, and Game Theory.

摘要

The classic randomized load balancing model is the so-called supermarket model, which describes a system in which customers arrive to a service center with n parallel servers according to a Poisson process with rate lamdba-n, where lamba is less than 1. Upon arrival, each customer samples d queues independently and uniformly at random before joining the shortest of those sampled. Customers are served according to a first-in first-out (FIFO) scheduling rule, and their service times are assumed to be mutually independent and exponentially distributed with unit mean mu = 1. Any ties that may occur are broken randomly. When d = 1, the model reduces to a system of n independent M/M/1 queues, for which it is a classical result that the stationary queue length distribution at a single queue is geometric with parameter lambda, and thus has an exponential decay rate. When d greater than or equal to 2, the model is not exactly solvable, but asymptotic results show that as n, the number of servers, goes to infinity, the limiting stationary distribution of a queue decays superexponentially. Moreover, the majority of this gain in performance is already obtained when d = 2. In particular, this shows that with just a slight increase in sampling cost, from d = 1 to d = 2, the performance is almost as good as in the case when all queues are sampled (that is, the Join-the-Shortest-Queue system where d = n). This phenomenon is referred to as the power of two choices, and this classic model is well studied.