Stability, Memory, and Messaging Trade-Offs in Heterogeneous Service Systems
Pages 1862 - 1874
Abstract
We consider a heterogeneous distributed service system consisting of n servers with unknown and possibly different processing rates. Jobs with unit mean arrive as a renewal process of rate proportional to n and are immediately dispatched to one of several queues associated with the servers. We assume that the dispatching decisions are made by a central dispatcher with the ability to exchange messages with the servers and endowed with a finite memory used to store information from one decision epoch to the next, about the current state of the queues and about the service rates of the servers. We study the fundamental resource requirements (memory bits and message exchange rate) in order for a dispatching policy to be always stable. First, we present a policy that is always stable while using a positive (but arbitrarily small) message rate and log2(n) bits of memory. Second, we show that within a certain broad class of policies, a dispatching policy that exchanges o(n2) messages per unit of time, and with o(log (n)) bits of memory, cannot be always stable.
References
[1]
Anselmi J (2019) Combining size-based load balancing with round-robin for scalable low latency. IEEE Trans. Parallel Distributed Systems 31(4):886–896.
[2]
Anselmi J, Dufour F (2020) Power-of-d-choices with memory: Fluid limit and optimality. Math. Oper. Res. 45(3):862–888.
[3]
Atar R, Keslassy I, Mendelson G, Orda A, Vargaftik S (2020) Persistent-Idle load-distribution. Stochastic Systems 10(2):152–169.
[4]
Bramson M (2011) Stability of join the shortest queue network. Ann. Appl. Probab. 21(4):1568–1625.
[5]
Foster F (1953) On the stochastic matrices associated with certain queueing processes. Ann. Math. Statist. 24(3):355–360.
[6]
Gamarnik D, Tsitsiklis JN, Zubeldia M (2018) Delay, memory, and messaging tradeoffs in distributed service systems. Stochastic Systems 8(1):45–74.
[7]
Gamarnik D, Tsitsiklis JN, Zubeldia M (2020) A lower bound on the queueing delay in resource constrained load balancing. Ann. Appl. Probab. 30(2):870–901.
[8]
Lu Y, Xie Q, Kliot G, Geller A, Larus J, Greenberg A (2011) Join-Idle-Queue: A novel load balancing algorithm for dynamically scalable web services. Performance Evaluation 68(11):1056–1071.
[9]
Mitzenmacher M (1996) The power of two choices in randomized load balancing. Unpublished PhD thesis, University of California, Berkeley.
[10]
Mukherjee D, Borst S, van Leeuwaarden J, Whiting P (2016) Universality of power-of-d load balancing schemes. Workshop Math. Perform. Model. Anal. ACM SIGMETRICS Performance Evaluation Rev. 44(2):36–38.
[11]
Shah D, Prabhakar B (2002) The use of memory in randomized load balancing. Proc. IEEE Internat. Sympos. Inform. Theory (Institute of Electrical and Electronics Engineers, Piscataway, NJ).
[12]
Stolyar A (2015) Pull-based load distribution in large-scale heterogeneous service systems. Queueing Systems 80(4):341–361.
[13]
van der Boor M, Zubeldia M, Borst S (2020) Zero-wait load balancing with sparse messaging. Oper. Res. Lett. 48(3):368–375.
[14]
Vargaftik S, Keslassy I, Orda A (2020) LSQ: Load balancing in large-scale heterogeneous systems with multiple dispatchers. IEEE/ACM Trans. Networking 28(3):1186–1198.
[15]
Vvedenskaya ND, Dobrushin RL, Karpelevich FI (1996) Queueing system with selection of the shortest of two queues: An asymptotic approach. Problems Inform. Transmission 32(1):15–27.
[16]
Zhou X, Shroff N, Wierman A (2021) Asymptotically optimal load balancing in large-scale heterogeneous systems with multiple dispatchers. ACM SIGMETRICS Performance Evaluation Rev. 48(3):57–58.
Index Terms
- Stability, Memory, and Messaging Trade-Offs in Heterogeneous Service Systems
Index terms have been assigned to the content through auto-classification.
Recommendations
Understanding the trade-offs in multi-level cell ReRAM memory design
DAC '13: Proceedings of the 50th Annual Design Automation ConferenceResistive Random Access Memory (ReRAM) is one of the most promising emerging memory technologies as a potential replacement for DRAM memory and/or NAND Flash. Multi-level cell (MLC) ReRAM, which can store multiple bits in a single ReRAM cell, can ...
Performance Trade-Offs in Using NVRAM Write Buffer for Flash Memory-Based Storage Devices
While NAND flash memory is used in a variety of end-user devices, it has a few disadvantages, such as asymmetric speed of read and write operations, inability to in-place updates, among others. To overcome these problems, various flash-aware strategies ...
Performance Analysis of Load Balancing Policies with Memory
VALUETOOLS '20: Proceedings of the 13th EAI International Conference on Performance Evaluation Methodologies and ToolsJoining the shortest or least loaded queue among d randomly selected queues are two fundamental load balancing policies. Under both policies the dispatcher does not maintain any information on the queue length or load of the servers. In this paper we ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2021, INFORMS.
Publisher
INFORMS
Linthicum, MD, United States
Publication History
Published: 01 August 2022
Accepted: 11 June 2021
Received: 10 July 2020
Author Tags
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 03 Mar 2025