Decomposition and aggregation by class in closed queueing networks

Abstract

A method is described whereby a multiple-class closed network of first-come first-served (FCFS) queues can be analyzed exactly by a decomposition and aggregation procedure that proceeds class by class, rather than node by node. First, the FCFS network is transformed into an equivalent network of processor-sharing queues in which a hierarchy of subsystems associated with subsets of the classes may be identified. This decomposition and aggregation procedure reduces the multiple-class queuing networks into a hierarchy of single-class queueing network problems. The reduced system is constructed containing one particular class of customers. A parametric analysis of this class with respect to the routing can then be made. The time and space requirements of this parametric analysis technique are derived and compared to the requirements of a straightforward repetitive analysis of the network using the convolution algorithm. An example parametric analysis of a store-and-forward communication network model is given.