Throughput Scalability Analysis of Fork-Join Queueing Networks
Yun Zeng, Augustin Chaintreau, Don Towsley, Cathy H. Xia
Operations Research · 2018 · Volume 66 · Issue 6
Abstract
Parallel and distributed processing systems have expanded in size as technology advances in cloud computing and big data analytics. A critical issue concerns throughput scalability: whether throughput decreases to zero as the systems scale in size and capabilities. We model parallel and distributed processing systems as fork and join queueing networks with blocking (FJQN/Bs). Such networks can have arbitrary topology, arbitrary initial state, and generally distributed service times. We propose a key topological concept, called the “minimum level,” that determines the throughput scalability of FJQN/Bs. We construct throughput bounds as functions of minimum level, network degree, buffer sizes, and processing speed, and we present necessary and/or sufficient conditions to guarantee throughput scalability of arbitrary size and topology FJQN/Bs. The e-companion is available at https://doi.org/10.1287/opre.2018.1748 .
Keywords
fork-join queueing networks, blocking, throughput scalability, performance bounds, last passage percolation
Enable JavaScript for citation tools and additional paper interactions.