Join-idle-queue with service elasticity

Debankur Mukherjee, Aleksandr Stolyar

Research output: Contribution to journalConference article

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 [4] (SIGMETRICS'17), which oers an efficient scalable implementation and yet achieves asymptotically optimal steady-state delay performance and energy consumption as the number of servers N ! 1. In the above work, the asymptotic results are obtained under the assumption that the queues have fixed-size finite buers, and therefore the fundamental question of stability of the proposed scheme with infinite buers 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 ! 1. 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.

Original languageEnglish (US)
Pages (from-to)18-20
Number of pages3
JournalPerformance Evaluation Review
Volume46
Issue number2
DOIs
StatePublished - Jan 17 2019
Event2018 Workshop on MAthematical Performance Modeling and Analysis, MAMA 2018 and Workshop on Critical Infrastructure Network Security, CINS 2018 - Irvine, United States
Duration: Jun 1 2018 → …

Fingerprint

Elasticity
Resource allocation
System stability
Servers
Energy utilization

Keywords

  • Auto-scaling
  • Fluid limit
  • Join-Idle-Queue
  • Load balancing
  • Many-server asymptotics
  • Mean-field limit
  • Stability

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this

Join-idle-queue with service elasticity. / Mukherjee, Debankur; Stolyar, Aleksandr.

In: Performance Evaluation Review, Vol. 46, No. 2, 17.01.2019, p. 18-20.

Research output: Contribution to journalConference article

Mukherjee, Debankur ; Stolyar, Aleksandr. / Join-idle-queue with service elasticity. In: Performance Evaluation Review. 2019 ; Vol. 46, No. 2. pp. 18-20.
@article{bc47afacbe0d42c5990102999af5db67,
title = "Join-idle-queue with service elasticity",
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 [4] (SIGMETRICS'17), which oers an efficient scalable implementation and yet achieves asymptotically optimal steady-state delay performance and energy consumption as the number of servers N ! 1. In the above work, the asymptotic results are obtained under the assumption that the queues have fixed-size finite buers, and therefore the fundamental question of stability of the proposed scheme with infinite buers 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 ! 1. 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 = "Auto-scaling, Fluid limit, Join-Idle-Queue, Load balancing, Many-server asymptotics, Mean-field limit, Stability",
author = "Debankur Mukherjee and Aleksandr Stolyar",
year = "2019",
month = "1",
day = "17",
doi = "10.1145/3305218.3305226",
language = "English (US)",
volume = "46",
pages = "18--20",
journal = "Performance Evaluation Review",
issn = "0163-5999",
publisher = "Association for Computing Machinery (ACM)",
number = "2",

}

TY - JOUR

T1 - Join-idle-queue with service elasticity

AU - Mukherjee, Debankur

AU - Stolyar, Aleksandr

PY - 2019/1/17

Y1 - 2019/1/17

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 [4] (SIGMETRICS'17), which oers an efficient scalable implementation and yet achieves asymptotically optimal steady-state delay performance and energy consumption as the number of servers N ! 1. In the above work, the asymptotic results are obtained under the assumption that the queues have fixed-size finite buers, and therefore the fundamental question of stability of the proposed scheme with infinite buers 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 ! 1. 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 [4] (SIGMETRICS'17), which oers an efficient scalable implementation and yet achieves asymptotically optimal steady-state delay performance and energy consumption as the number of servers N ! 1. In the above work, the asymptotic results are obtained under the assumption that the queues have fixed-size finite buers, and therefore the fundamental question of stability of the proposed scheme with infinite buers 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 ! 1. 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 - Auto-scaling

KW - Fluid limit

KW - Join-Idle-Queue

KW - Load balancing

KW - Many-server asymptotics

KW - Mean-field limit

KW - Stability

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

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

U2 - 10.1145/3305218.3305226

DO - 10.1145/3305218.3305226

M3 - Conference article

AN - SCOPUS:85061099633

VL - 46

SP - 18

EP - 20

JO - Performance Evaluation Review

JF - Performance Evaluation Review

SN - 0163-5999

IS - 2

ER -