Join-idle-queue with service elasticity: large-scale asymptotics of a non-monotone system
D. Mukherjee, A. Stolyar
Research output: Contribution to journal › Article › Academic
We consider the model of a token-based joint auto-scaling and load balancing strategy, proposed in a recent paper by Mukherjee, Dhara, Borst, and van Leeuwaarden (SIGMETRICS '17), which offers an efficient scalable implementation and yet achieves asymptotically optimal steady-state delay performance and energy consumption as the number of servers $N\to\infty$. In the above work, the asymptotic results are obtained under the assumption that the queues have fixed-size finite buffers, and therefore the fundamental question of stability of the proposed scheme with infinite buffers was left open. In this paper, we address this fundamental stability question. The system stability under the usual subcritical load assumption is not automatic. Moreover, the stability may not even hold for all $N$. The key challenge stems from the fact that the process lacks monotonicity, which has been the powerful primary tool for establishing stability in load balancing models. We develop a novel method to prove that the subcritically loaded system is stable for large enough $N$, and establish convergence of steady-state distributions to the optimal one, as $N \to \infty$. The method goes beyond the state of the art techniques -- it uses an induction-based idea and a "weak monotonicity" property of the model; this technique is of independent interest and may have broader applicability.
math.PR
cs.PF
Authors version Arxiv
Fingerprint Dive into the research topics of 'Join-idle-queue with service elasticity: large-scale asymptotics of a non-monotone system'. Together they form a unique fingerprint.
Join Mathematics
Queue Mathematics
Elasticity Mathematics
Load Balancing Mathematics
Monotonicity Mathematics
Energy Consumption Mathematics
Finite Buffer Mathematics
Steady-state Distribution Mathematics
Mukherjee, D., & Stolyar, A. (2018). Join-idle-queue with service elasticity: large-scale asymptotics of a non-monotone system. arXiv.
Mukherjee, D. ; Stolyar, A. / Join-idle-queue with service elasticity: large-scale asymptotics of a non-monotone system. In: arXiv. 2018.
@article{c24143a110c24bc88e2520ec581b1e32,
title = "Join-idle-queue with service elasticity: large-scale asymptotics of a non-monotone system",
abstract = "We consider the model of a token-based joint auto-scaling and load balancing strategy, proposed in a recent paper by Mukherjee, Dhara, Borst, and van Leeuwaarden (SIGMETRICS '17), which offers an efficient scalable implementation and yet achieves asymptotically optimal steady-state delay performance and energy consumption as the number of servers $N\to\infty$. In the above work, the asymptotic results are obtained under the assumption that the queues have fixed-size finite buffers, and therefore the fundamental question of stability of the proposed scheme with infinite buffers was left open. In this paper, we address this fundamental stability question. The system stability under the usual subcritical load assumption is not automatic. Moreover, the stability may not even hold for all $N$. The key challenge stems from the fact that the process lacks monotonicity, which has been the powerful primary tool for establishing stability in load balancing models. We develop a novel method to prove that the subcritically loaded system is stable for large enough $N$, and establish convergence of steady-state distributions to the optimal one, as $N \to \infty$. The method goes beyond the state of the art techniques -- it uses an induction-based idea and a {"}weak monotonicity{"} property of the model; this technique is of independent interest and may have broader applicability.",
keywords = "math.PR, cs.PF",
author = "D. Mukherjee and A. Stolyar",
note = "30 pages",
journal = "arXiv",
publisher = "Cornell University Library",
Mukherjee, D & Stolyar, A 2018, 'Join-idle-queue with service elasticity: large-scale asymptotics of a non-monotone system', arXiv.
Join-idle-queue with service elasticity: large-scale asymptotics of a non-monotone system. / Mukherjee, D.; Stolyar, A.
In: arXiv, 03.2018.
T1 - Join-idle-queue with service elasticity: large-scale asymptotics of a non-monotone system
AU - Mukherjee, D.
AU - Stolyar, A.
N1 - 30 pages
N2 - We consider the model of a token-based joint auto-scaling and load balancing strategy, proposed in a recent paper by Mukherjee, Dhara, Borst, and van Leeuwaarden (SIGMETRICS '17), which offers an efficient scalable implementation and yet achieves asymptotically optimal steady-state delay performance and energy consumption as the number of servers $N\to\infty$. In the above work, the asymptotic results are obtained under the assumption that the queues have fixed-size finite buffers, and therefore the fundamental question of stability of the proposed scheme with infinite buffers was left open. In this paper, we address this fundamental stability question. The system stability under the usual subcritical load assumption is not automatic. Moreover, the stability may not even hold for all $N$. The key challenge stems from the fact that the process lacks monotonicity, which has been the powerful primary tool for establishing stability in load balancing models. We develop a novel method to prove that the subcritically loaded system is stable for large enough $N$, and establish convergence of steady-state distributions to the optimal one, as $N \to \infty$. The method goes beyond the state of the art techniques -- it uses an induction-based idea and a "weak monotonicity" property of the model; this technique is of independent interest and may have broader applicability.
AB - We consider the model of a token-based joint auto-scaling and load balancing strategy, proposed in a recent paper by Mukherjee, Dhara, Borst, and van Leeuwaarden (SIGMETRICS '17), which offers an efficient scalable implementation and yet achieves asymptotically optimal steady-state delay performance and energy consumption as the number of servers $N\to\infty$. In the above work, the asymptotic results are obtained under the assumption that the queues have fixed-size finite buffers, and therefore the fundamental question of stability of the proposed scheme with infinite buffers was left open. In this paper, we address this fundamental stability question. The system stability under the usual subcritical load assumption is not automatic. Moreover, the stability may not even hold for all $N$. The key challenge stems from the fact that the process lacks monotonicity, which has been the powerful primary tool for establishing stability in load balancing models. We develop a novel method to prove that the subcritically loaded system is stable for large enough $N$, and establish convergence of steady-state distributions to the optimal one, as $N \to \infty$. The method goes beyond the state of the art techniques -- it uses an induction-based idea and a "weak monotonicity" property of the model; this technique is of independent interest and may have broader applicability.
KW - math.PR
KW - cs.PF
JO - arXiv
JF - arXiv
Mukherjee D, Stolyar A. Join-idle-queue with service elasticity: large-scale asymptotics of a non-monotone system. arXiv. 2018 Mar.