|Xin Liu||Arizona State University, USA|
|Lei Ying||Arizona State University, USA|
Power-of-d-choices is a popular load balancing algorithm for many-server systems such as large-scale data centers. For each incoming job, the algorithm probes d servers, chosen uniformly at random from a total of N servers, and routes the job to the least loaded one. It is well known that power-of-d-choices reduces queueing delays by orders of magnitude compared to the policy that routes each incoming job to a randomly selected server. The question to be addressed in this paper is how large d needs to be so that power-of-d-choices achieves asymptotic zero delay like the join-the-shortest-queue (JSQ) algorithm, which is a special case of power-of-d-choices with d = N. We are interested in the heavy-traffic regime where the load of the system, denoted by λ, approaches to one as N increases, and assume λ = 1 − γN −α for 0 < γ < 1 and 0 ≤ α < 1/6. This paper establishes that when d = ω 1 1−λ , the probability that an incoming job is routed to a busy server is asymptotically zero, i.e. a job experiences zero queueing delay with probability one asymptotically; and when d = O 1 1−λ , the probability that a job is routed to a busy server is lower bounded by a positive constant independent of N. Therefore, our results show that d = ω(1 1−λ) is sufficient and almost necessary for achieving zero delay with the power-of-d-choices load balancing policy.