Join Idle Queue with Service Elasticity: Large-Scale Asymptotics of a Nonmonotone System

DOI10.1287/STSY.2019.0030zbMATH Open1447.60138arXiv1803.07689OpenAlexW3099545209WikidataQ126594155 ScholiaQ126594155MaRDI QIDQ5113913FDOQ5113913

Author name not available (Why is that?)

Publication date: 18 June 2020

Published in: Stochastic Systems (Search for Journal in Brave)

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, arXiv:1703.08373), which offers an efficient scalable implementation and yet achieves asymptotically optimal steady-state delay performance and energy consumption as the number of servers $Noinfty$. 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 $Noinfty$. 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.

Full work available at URL: https://arxiv.org/abs/1803.07689

Recommendations

• Large-scale join-idle-queue system with general service times
• Many-server asymptotics for join-the-shortest-queue: large deviations and rare events
• Join the shortest queue with many servers. The heavy-traffic asymptotics
• Asymptotically optimal idling in the \(GI/GI/N+GI\) queue
• \(M/M/n/m\) queueing systems with non-identical servers
• Large fork-join queues with nearly deterministic arrival and service times
• Equilibrium joining strategies in batch service queueing systems
• Strategic Joining in an M/M/1 Constant Retrial Queue with Reserved Idle Time Under N-Policy
• Queue-and-idleness-ratio controls in many-server service systems
• A unified approach for large queue asymptotics in a heterogeneous multiserver queue

zbMATH Keywords

stabilityload balancingmean-field limitfluid limitjoin idle queue

Mathematics Subject Classification ID

Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Functional limit theorems; invariance principles (60F17)

Cites Work

• Markov chains and stochastic stability
• Queueing system with selection of the shortest of two queues: An asymptotic approach
• On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models
• Title not available (Why is that?)
• A service system with on-demand agent invitations
• Exact analysis of the \(\mathrm{M}/\mathrm{M}/k/\mathrm{setup}\) class of Markov chains via recursive renewal reward
• Asymptotic independence of queues under randomized load balancing
• Ergodicity of stochastic processes describing the operation of open queueing networks
• Decay of tails at equilibrium for FIFO join the shortest queue networks
• Title not available (Why is that?)
• Pull-based load distribution among heterogeneous parallel servers: the case of multiple routers
• Pull-based load distribution in large-scale heterogeneous service systems
• Stability conditions for a discrete-time decentralised medium access algorithm
• A Law of Large Numbers for M/M/c/Delayoff-Setup Queues with Nonstationary Arrivals
• Universality of load balancing schemes on the diffusion scale
• Large-scale join-idle-queue system with general service times
• Universality of Power-of-d Load Balancing in Many-Server Systems

Cited In (1)

• Scalable Load Balancing in Networked Systems: A Survey of Recent Advances

This page was built for publication: Join Idle Queue with Service Elasticity: Large-Scale Asymptotics of a Nonmonotone System

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113913)