A New Aggregation Technique for the Analysis of Extended Open Fork/Join Queueing Networks by Decomposition

Abstract:
In this paper we present a new approach for the analysis of extended fork/join queueing networks. We consider networks of queues with phase-type distributed inter-arrival and service times whose dynamic behaviour can be mapped to Quasi-Birth-and-Death processes (QBD). We furthermore allow for the existence of fork/join nodes that synchronise several parallel subnets. The analysis of this type of queueing networks is based on the well-known decomposition approach by Kühn/Whitt. To deal with fork/join subnets we apply a method of Balsamo et al. They consider the isolated analysis of a simple type of fork/join nodes that synchronise several single server queues with (heterogenous) phase-type distributed service times and a common phase-type distributed inter-arrival process. We extend this technique to the analysis of extended fork/join nodes that synchronise several parallel networks of queues instead of single server queues. Therefore, we apply a new aggregation technique that reduces the analysis of extended fork/join nodes to the analysis of simple fork/join nodes.