On the analysis of randomized load balancing schemes

It is well known that simple randomized load balancing schemes can balance load effectively while incurring only a small overhead, making such schemes appealing for practical systems. In this paper we provide new analyses for several such dynamic randomized load balancing schemes. Our work extends a previous analysis of the supermarket model, a model that abstracts a simple, efficient load balancing scheme in the setting where j obs arrive at a large system of parallel processors. In this model, custome rs arrive at a system of n servers as a Poisson stream of rate lambda n, la mbda < 1, with service requirements exponentially distributed with mean 1. Each customer chooses d servers independently and uniformly at random from the n servers, and is served according to the First In First Out (FIFO) pro tocol at the choice with the fewest customers. For the supermarket model, i t has been shown that using d = 2 choices yields an exponential improvement in the expected time a customer spends in the system over d = 1 choice (si mple random selection) in equilibrium. Here we examine several variations, including constant service times and threshold models, where a customer mak es up to d successive choices until finding one below a set threshold. Our approach involves studying limiting, deterministic models representing the behavior of these systems as the number of servers n goes to infinity. Results of our work include useful general theorems for showing that these deterministic systems are stable or converge exponentially to fixed points. We also demonstrate that allowing customers two choices instead of just on e leads to exponential improvements in the expected time a customer spends in the system in several of the related models we study, reinforcing the co ncept that just two choices yields significant power in load balancing.