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

Debankur Mukherjee, Sem Borst, Johan van Leeuwaarden, Philip Whiting

Research output: Contribution to journalArticleScientificpeer-review

Abstract

We consider a system of N identical server pools and a single dispatcher where tasks arrive as a Poisson process of rate λ(N). Arriving tasks cannot be queued, and must immediately be assigned to one of the server pools to start execution, or discarded. The execution times are assumed to be exponentially distributed with unit mean, and do not depend on the number of other tasks receiving service. However, the experienced performance (e.g. in terms of received throughput) does degrade with an increasing number of concurrent tasks at the same server pool. The dispatcher therefore 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. This assignment strategy is called the JSQ(d(N)) scheme, as it resembles the power-of-d version of the Join-the-Shortest-Queue (JSQ) policy, and will also be referred to as such in the special case d(N)=N.
We construct a stochastic coupling to bound the difference in the system occupancy processes between the 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 leverage the coupling to 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-level and diffusion-level while reducing the overhead by nearly a factor O(N) and O(N−−√/log(N)), respectively.
Original languageEnglish
JournalMathematics of Operations Research
Publication statusAccepted/In press - Sep 2019

Fingerprint

Asymptotic Optimality
Large-scale Systems
Load Balancing
Resource allocation
Join
Queue
Large scale systems
Servers
Server
Fluid Limits
Fluids
Diffusion Limit
Poisson process
Leverage
Diffusion Process
Execution Time
Immediately
Assign
Asymptotic optimality
Load balancing

Cite this

@article{ca8ec08e28ef4ec1b83ce3aaea27c65b,
title = "Asymptotic optimality of power-of-d load balancing in large-scale systems",
abstract = "We consider a system of N identical server pools and a single dispatcher where tasks arrive as a Poisson process of rate λ(N). Arriving tasks cannot be queued, and must immediately be assigned to one of the server pools to start execution, or discarded. The execution times are assumed to be exponentially distributed with unit mean, and do not depend on the number of other tasks receiving service. However, the experienced performance (e.g. in terms of received throughput) does degrade with an increasing number of concurrent tasks at the same server pool. The dispatcher therefore 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. This assignment strategy is called the JSQ(d(N)) scheme, as it resembles the power-of-d version of the Join-the-Shortest-Queue (JSQ) policy, and will also be referred to as such in the special case d(N)=N.We construct a stochastic coupling to bound the difference in the system occupancy processes between the 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 leverage the coupling to 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-level and diffusion-level while reducing the overhead by nearly a factor O(N) and O(N−−√/log(N)), respectively.",
author = "Debankur Mukherjee and Sem Borst and {van Leeuwaarden}, Johan and Philip Whiting",
year = "2019",
month = "9",
language = "English",
journal = "Mathematics of Operations Research",
issn = "0364-765X",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",

}

Asymptotic optimality of power-of-d load balancing in large-scale systems. / Mukherjee, Debankur; Borst, Sem; van Leeuwaarden, Johan; Whiting, Philip.

In: Mathematics of Operations Research, 09.2019.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

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

AU - Mukherjee, Debankur

AU - Borst, Sem

AU - van Leeuwaarden, Johan

AU - Whiting, Philip

PY - 2019/9

Y1 - 2019/9

N2 - We consider a system of N identical server pools and a single dispatcher where tasks arrive as a Poisson process of rate λ(N). Arriving tasks cannot be queued, and must immediately be assigned to one of the server pools to start execution, or discarded. The execution times are assumed to be exponentially distributed with unit mean, and do not depend on the number of other tasks receiving service. However, the experienced performance (e.g. in terms of received throughput) does degrade with an increasing number of concurrent tasks at the same server pool. The dispatcher therefore 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. This assignment strategy is called the JSQ(d(N)) scheme, as it resembles the power-of-d version of the Join-the-Shortest-Queue (JSQ) policy, and will also be referred to as such in the special case d(N)=N.We construct a stochastic coupling to bound the difference in the system occupancy processes between the 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 leverage the coupling to 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-level and diffusion-level while reducing the overhead by nearly a factor O(N) and O(N−−√/log(N)), respectively.

AB - We consider a system of N identical server pools and a single dispatcher where tasks arrive as a Poisson process of rate λ(N). Arriving tasks cannot be queued, and must immediately be assigned to one of the server pools to start execution, or discarded. The execution times are assumed to be exponentially distributed with unit mean, and do not depend on the number of other tasks receiving service. However, the experienced performance (e.g. in terms of received throughput) does degrade with an increasing number of concurrent tasks at the same server pool. The dispatcher therefore 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. This assignment strategy is called the JSQ(d(N)) scheme, as it resembles the power-of-d version of the Join-the-Shortest-Queue (JSQ) policy, and will also be referred to as such in the special case d(N)=N.We construct a stochastic coupling to bound the difference in the system occupancy processes between the 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 leverage the coupling to 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-level and diffusion-level while reducing the overhead by nearly a factor O(N) and O(N−−√/log(N)), respectively.

M3 - Article

JO - Mathematics of Operations Research

JF - Mathematics of Operations Research

SN - 0364-765X

ER -