Limited choice and locality considerations for load balancing
This paper considers the problem of routing Poisson arrivals to N 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.
limited choice load balancing parallel queues