Throughput Scalability Analysis of Fork-Join Queueing Networks
成果类型：
Article
署名作者：
Zeng, Yun; Chaintreau, Augustin; Towsley, Don; Xia, Cathy H.
署名单位：
University System of Ohio; Ohio State University; Columbia University; University of Massachusetts System; University of Massachusetts Amherst
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.2018.1748
发表日期：
2018
页码：
1728-1743
关键词：
摘要：
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.