Paper Info
Title
A Necessary and Sufficient Condition for Throughput Scalability of Fork and Join Networks with Blocking.
Abstract
Due to emerging applications such as cloud computing and big data analytics, modern information processing systems are growing increasingly large and complex. A critical issue concerns the throughput performance as the system grows in size. This paper models distributed information processing systems as fork and join queueing networks with blocking. We identify necessary and sufficient conditions for throughput scalability of such fork and join networks as they grow in size. Previous studies have either focused on special structured networks such as tandem or tree networks, or provided only necessary conditions for throughput scalability. In this paper, we show that such necessary conditions are not sufficient. We present a key topological concept called ``minimum level" of the underlying graph, and develop lower and upper bounds for the throughput of arbitrary FJQN/Bs. The bounds depend on network degree, minimum level, deterministic cycle time, buffer sizes, and service time distributions, but not on network size. We show that level-boundedness and degree-boundedness are necessary and sufficient conditions to guarantee that the throughput of an FJQN/B is bounded away from zero as network size goes to infinity.
Year
DOI
Venue
2016
10.1145/2896377.2901470
SIGMETRICS
Keywords
Field
DocType
fork/join, performance bound, queueing network, scalability, throughput
Fork (system call),Information processing,Computer science,Computer network,Real-time computing,Queueing theory,Throughput,Fork–join queue,Big data,Cloud computing,Scalability,Distributed computing
Conference
Citations 
PageRank 
References 
1
0.64
8
Authors
4
Name
Order
Citations
PageRank
Yun Zeng110.64
Augustin Chaintreau22086116.37
Don Towsley3186931951.05
Cathy Xia423917.94