Accession Number:

ADA624083

Title:

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

Descriptive Note:

Technical rept.

Corporate Author:

BROWN UNIV PROVIDENCE RI

Personal Author(s):

Report Date:

2014-04-16

Pagination or Media Count:

47.0

Abstract:

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 MM1 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.

Subject Categories:

  • Statistics and Probability
  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE