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

D. Mukherjee, S.C. Borst, J.S.H. van Leeuwaarden, P.A. Whiting

Research output: Contribution to journalArticleAcademic

36 Downloads (Pure)

Abstract

We consider a system of $N$ identical server pools and a single dispatcher where tasks arrive as a Poisson process of rate $\lambda(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) \to \infty$ and $\lambda(N)/N \to \lambda$ as $N \to \infty$, 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)/\sqrt{N} \log(N) \to \infty$, 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($\sqrt{N}/\log(N)$), respectively.
Original languageEnglish
Article number1612.00722v1
Number of pages48
JournalarXiv
Issue numberarXiv:1612.00722v1
Publication statusPublished - 2 Dec 2016

Fingerprint

Resource allocation
Large scale systems
Servers
Fluids
Throughput

Bibliographical note

48 pages, 3 figures, companion paper of Universality of Power-of-d Load Balancing in Many-Server Systems (2016)

Cite this

Mukherjee, D., Borst, S. C., van Leeuwaarden, J. S. H., & Whiting, P. A. (2016). Asymptotic optimality of power-of-$d$ load balancing in large-scale systems. arXiv, (arXiv:1612.00722v1), [1612.00722v1].
@article{105bb0c3cb3e4292b41f762cca562fca,
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 $\lambda(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) \to \infty$ and $\lambda(N)/N \to \lambda$ as $N \to \infty$, 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)/\sqrt{N} \log(N) \to \infty$, 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($\sqrt{N}/\log(N)$), respectively.",
keywords = "math.PR",
author = "D. Mukherjee and S.C. Borst and {van Leeuwaarden}, J.S.H. and P.A. Whiting",
note = "48 pages, 3 figures, companion paper of Universality of Power-of-d Load Balancing in Many-Server Systems (2016)",
year = "2016",
month = "12",
day = "2",
language = "English",
journal = "arXiv",
publisher = "Cornell University Library",
number = "arXiv:1612.00722v1",

}

Mukherjee, D, Borst, SC, van Leeuwaarden, JSH & Whiting, PA 2016, 'Asymptotic optimality of power-of-$d$ load balancing in large-scale systems', arXiv, no. arXiv:1612.00722v1, 1612.00722v1.

Asymptotic optimality of power-of-$d$ load balancing in large-scale systems. / Mukherjee, D.; Borst, S.C.; van Leeuwaarden, J.S.H.; Whiting, P.A.

In: arXiv, No. arXiv:1612.00722v1, 1612.00722v1, 02.12.2016.

Research output: Contribution to journalArticleAcademic

TY - JOUR

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

AU - Mukherjee, D.

AU - Borst, S.C.

AU - van Leeuwaarden, J.S.H.

AU - Whiting, P.A.

N1 - 48 pages, 3 figures, companion paper of Universality of Power-of-d Load Balancing in Many-Server Systems (2016)

PY - 2016/12/2

Y1 - 2016/12/2

N2 - We consider a system of $N$ identical server pools and a single dispatcher where tasks arrive as a Poisson process of rate $\lambda(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) \to \infty$ and $\lambda(N)/N \to \lambda$ as $N \to \infty$, 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)/\sqrt{N} \log(N) \to \infty$, 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($\sqrt{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 $\lambda(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) \to \infty$ and $\lambda(N)/N \to \lambda$ as $N \to \infty$, 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)/\sqrt{N} \log(N) \to \infty$, 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($\sqrt{N}/\log(N)$), respectively.

KW - math.PR

UR - https://arxiv.org/pdf/1612.00722v1.pdf

M3 - Article

JO - arXiv

JF - arXiv

IS - arXiv:1612.00722v1

M1 - 1612.00722v1

ER -

Mukherjee D, Borst SC, van Leeuwaarden JSH, Whiting PA. Asymptotic optimality of power-of-$d$ load balancing in large-scale systems. arXiv. 2016 Dec 2;(arXiv:1612.00722v1). 1612.00722v1.