Limited choice and locality considerations for load balancing

This paper considers the problem of routing Poisson arrivals to N parallel servers under the condition that the system is heavily loaded. We propose a scheme in which a proportion of arrivals are routed randomly, while the others are routed to one of two neighbouring queues using load information. We show that this scheme, which exploits a limited amount of load information and takes into account locality considerations, achieves performance close to that of a routing policy which requires complete load information. In addition, we show that this scheme has a diffusion scaled queue length process that is the same as if all of the servers were pooled with a single queue (in other words, no routing decision need be made). Our insights provide an additional option in load balancing, complementing the related work on the power of two choices.