TY - JOUR

T1 - Asymptotic optimality of power-of-d load balancing in large-scale systems

AU - Mukherjee, Debankur

AU - Borst, Sem C.

AU - van Leeuwaarden, Johan S. H.

AU - Whiting, Philip A.

PY - 2020/11

Y1 - 2020/11

N2 - We consider a system of N identical server pools and a single dispatcher in which tasks with unit-exponential service requirements arrive at rate λ(N). In order to optimize the experienced performance, the dispatcher aims to evenly distribute the tasks across the various server pools. Specifically, when a task arrives, the dispatcher assigns it to the server pool with the minimum number of tasks among d(N) randomly selected server pools. We construct a stochastic coupling to bound the difference in the system occupancy processes between the join-the-shortest-queue (JSQ) policy and a scheme with an arbitrary value of d(N). We use the coupling to derive the fluid limit in case d(N)→∞ and λ(N)/N→λ as N→∞along with the associated fixed point. The fluid limit turns out to be insensitive to the exact growth rate of d(N) and coincides with that for the JSQ policy. We further establish that the diffusion limit corresponds to that for the JSQ policy as well, as long as d(N)/- N √ log(N)→∞, and characterize the common limiting diffusion process. These results indicate that the JSQ optimality can be preserved at the fluid and diffusion levels while reducing the overhead by nearly a factor O(N) andO(- N √ /log(N)), respectively.

AB - We consider a system of N identical server pools and a single dispatcher in which tasks with unit-exponential service requirements arrive at rate λ(N). In order to optimize the experienced performance, the dispatcher aims to evenly distribute the tasks across the various server pools. Specifically, when a task arrives, the dispatcher assigns it to the server pool with the minimum number of tasks among d(N) randomly selected server pools. We construct a stochastic coupling to bound the difference in the system occupancy processes between the join-the-shortest-queue (JSQ) policy and a scheme with an arbitrary value of d(N). We use the coupling to derive the fluid limit in case d(N)→∞ and λ(N)/N→λ as N→∞along with the associated fixed point. The fluid limit turns out to be insensitive to the exact growth rate of d(N) and coincides with that for the JSQ policy. We further establish that the diffusion limit corresponds to that for the JSQ policy as well, as long as d(N)/- N √ log(N)→∞, and characterize the common limiting diffusion process. These results indicate that the JSQ optimality can be preserved at the fluid and diffusion levels while reducing the overhead by nearly a factor O(N) andO(- N √ /log(N)), respectively.

KW - load balancing

KW - power-of-d scheme

KW - join the shortest queue

KW - stochastic coupling

KW - functional limit theorems

KW - fluid limit

KW - diffusion limit

KW - many-server asymptotics

UR - http://www.scopus.com/inward/record.url?scp=85096037218&partnerID=8YFLogxK

UR - http://purl.org/au-research/grants/arc/DP1592400

U2 - 10.1287/MOOR.2019.1042

DO - 10.1287/MOOR.2019.1042

M3 - Article

AN - SCOPUS:85096037218

VL - 45

SP - 1535

EP - 1571

JO - Mathematics of Operations Research

JF - Mathematics of Operations Research

SN - 0364-765X

IS - 4

ER -