extended-abstract

Public Access

Fork and Join Queueing Networks with Heavy Tails: Scaling Dimension and Throughput Limit

Authors:

Yun Zeng,

Jian Tan,

Cathy Honghui XiaAuthors Info & Claims

SIGMETRICS '18: Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems

Pages 122 - 124

https://doi.org/10.1145/3219617.3219668

Published: 12 June 2018 Publication History

PDF eReader

Abstract

Parallel and distributed computing systems are foundational to the success of cloud computing and big data analytics. Fork-Join Queueing Networks with Blocking (FJQN/Bs) are natural models for such systems. While engineering solutions have long been made to build and scale such systems, it is challenging to rigorously characterize the throughput performance of ever-growing systems, especially in the presence of heavy-tailed delays. In this paper, we utilize an infinite sequence of FJQN/Bs to study the throughput limit and focus on regularly varying service times with index α>1. We introduce two novel geometric concepts - scaling dimension and extended metric dimension - and show that an infinite sequence of FJQN/Bs is throughput scalable if the extended metric dimension <α-1 and only if the scaling dimension łe α-1. These results provide new insights on the scalability of a rich class of FJQN/Bs.

References

[1]

F. Baccelli, A. Chaintreau, Z. Liu, and A. Riabov. 2005. The one-to-many TCP overlay: A scalable and reliable multicast architecture INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, Vol. Vol. 3. IEEE, 1629--1640.

Google Scholar

[2]

A. Chaintreau. 2006. Processes of Interaction in Data Networks.PhD thesis, INRIA-ENS.

Google Scholar

[3]

A. Chaintreau. 2008. Sharpness: a tight condition for scalability. Structural Information and Communication Complexity (2008), 74--88.

Digital Library

Google Scholar

[4]

J.B. Martin. 2002. Large tandem queueing networks with blocking. Queueing Syst. Vol. 141, 1--2 (2002), 45--72.

Digital Library

Google Scholar

[5]

J.B. Martin. 2002. Linear growth for greedy lattice animals. Stoch. Proceedings Appl. Vol. 98, 1 (2002), 43--66.

Crossref

Google Scholar

[6]

C.H. Xia, Zhen Liu, Don Towsley, and Marc Lelarge. 2007. Scalability of fork/join queueing networks with blocking Proceedings of ACM Sigmetrics.

Digital Library

Google Scholar

[7]

Y. Zeng, A. Chaintreau, D. Towsley, and C.H. Xia. 2016. A Necessary and Sufficient Condition for Throughput Scalability of Fork and Join Networks with Blocking. In Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science. ACM, 25--36.

Digital Library

Google Scholar

[8]

Y. Zeng, J. Tan, and C.H. Xia. 2018. Fork and Join Queueing Networks with Heavy Tails: Scaling Dimension and Throughput Limit. arXiv preprint arXiv:1805.05197 (2018).

Google Scholar

Cited By

View all

Weissenberg JMichalski M(2024)Hardware Simulation of Multi-Service Queues2024 33rd International Conference on Computer Communications and Networks (ICCCN)10.1109/ICCCN61486.2024.10637623(1-2)Online publication date: 29-Jul-2024
https://doi.org/10.1109/ICCCN61486.2024.10637623
Zeng YTan JXia C(2019)Fork and Join Queueing Networks with Heavy TailsACM SIGMETRICS Performance Evaluation Review10.1145/3308809.330887246:1(122-124)Online publication date: 17-Jan-2019
https://doi.org/10.1145/3308809.3308872
Roy Dvan Ommeren Jde Koster RGharehgozli A(2022)Modeling landside container terminal queues: Exact analysis and approximationsTransportation Research Part B: Methodological10.1016/j.trb.2022.05.012162(73-102)Online publication date: Aug-2022
https://doi.org/10.1016/j.trb.2022.05.012
Show More Cited By

Index Terms

Fork and Join Queueing Networks with Heavy Tails: Scaling Dimension and Throughput Limit
1. Networks
  1. Network performance evaluation
    1. Network performance analysis
  2. Network properties
    1. Network structure
      1. Topology analysis and generation

Recommendations

Fork and Join Queueing Networks with Heavy Tails: Scaling Dimension and Throughput Limit
SIGMETRICS '18

Parallel and distributed computing systems are foundational to the success of cloud computing and big data analytics. Fork-Join Queueing Networks with Blocking (FJQN/Bs) are natural models for such systems. While engineering solutions have long been ...
Fork and Join Queueing Networks with Heavy Tails: Scaling Dimension and Throughput Limit
Parallel and distributed computing systems are foundational to the success of cloud computing and big data analytics. These systems process computational workflows in a way that can be mathematically modeled by a fork-and-join queueing network with ...
Analysis of a fork/join station with inputs from a finite population subnetwork with multi-server stations

Forks/join stations are commonly used to model synchronization constraints in queuing networks. This paper presents an exact analysis of a fork/join station with inputs from stations composed of multiple exponential servers. The queue length process at ...

Comments

Information & Contributors

Information

Published In

SIGMETRICS '18: Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems

June 2018

155 pages

ISBN:9781450358460

DOI:10.1145/3219617

General Chair:
Konstantinos Psounis
University of Southern California
,
Program Chairs:
Aditya Akella
University of Wisconsin-Madison
,
Adam Wierman
California Institute of Technology

ACM SIGMETRICS Performance Evaluation Review Volume 46, Issue 1
SIGMETRICS '18
June 2018
142 pages
ISSN:0163-5999
DOI:10.1145/3292040
Editor:
Nidhi Hegde
Borealis AI
Issue’s Table of Contents

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 June 2018

Check for updates

Author Tags

Qualifiers

Extended-abstract

Funding Sources

National Science Foundation

Conference

SIGMETRICS '18

Sponsor:

SIGMETRICS

SIGMETRICS '18: ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems

June 18 - 22, 2018

CA, Irvine, USA

Acceptance Rates

SIGMETRICS '18 Paper Acceptance Rate 54 of 270 submissions, 20%;

Overall Acceptance Rate 459 of 2,691 submissions, 17%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
323
Total Downloads

Downloads (Last 12 months)68
Downloads (Last 6 weeks)9

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Weissenberg JMichalski M(2024)Hardware Simulation of Multi-Service Queues2024 33rd International Conference on Computer Communications and Networks (ICCCN)10.1109/ICCCN61486.2024.10637623(1-2)Online publication date: 29-Jul-2024
https://doi.org/10.1109/ICCCN61486.2024.10637623
Zeng YTan JXia C(2019)Fork and Join Queueing Networks with Heavy TailsACM SIGMETRICS Performance Evaluation Review10.1145/3308809.330887246:1(122-124)Online publication date: 17-Jan-2019
https://doi.org/10.1145/3308809.3308872
Roy Dvan Ommeren Jde Koster RGharehgozli A(2022)Modeling landside container terminal queues: Exact analysis and approximationsTransportation Research Part B: Methodological10.1016/j.trb.2022.05.012162(73-102)Online publication date: Aug-2022
https://doi.org/10.1016/j.trb.2022.05.012
Russo GCardellini VCasale GPresti F(2021)MEAD: Model-Based Vertical Auto-Scaling for Data Stream Processing2021 IEEE/ACM 21st International Symposium on Cluster, Cloud and Internet Computing (CCGrid)10.1109/CCGrid51090.2021.00041(314-323)Online publication date: May-2021
https://doi.org/10.1109/CCGrid51090.2021.00041
Roy Dvan Ommeren Jde Koster MGharehgozli A(undefined)Effect of Service Priority and Resource Synchronization Choices on Landside Terminal Queues: Exact Analysis and ApproximationsSSRN Electronic Journal10.2139/ssrn.3532297
https://doi.org/10.2139/ssrn.3532297

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Fork and Join Queueing Networks with Heavy Tails: Scaling Dimension and Throughput Limit

Fork and Join Queueing Networks with Heavy Tails: Scaling Dimension and Throughput Limit

Analysis of a fork/join station with inputs from a finite population subnetwork with multi-server stations