UNIVERSALITY OF LOAD BALANCING SCHEMES ON THE DIFFUSION SCALE

We consider a system of N parallel queues with identical exponential service rates and a single dispatcher where tasks arrive as a Poisson process. When a task arrives, the dispatcher always assigns it to an idle server, if there is any, and to a server with the shortest queue among d randomly selected servers otherwise (1 <= d <= N). This load balancing scheme subsumes the so-called join-the-idle queue policy (d = 1) and the celebrated join-the-shortest queue policy (d = N) as two crucial special cases. We develop a stochastic coupling construction to obtain the diffusion limit of the queue process in the Halfin-Whitt heavy-traffic regime, and establish that it does not depend on the value of d, implying that assigning tasks to idle servers is sufficient for diffusion level optimality.