Algorithms for Product-Form Networks Although product-form solutions can be expressed very easily as formulae, the computation of state probabilities in a closed queueing network is very time consuming if a straightforward computation of the normalization constant using Eq. () is carried out. As seen in Example , considerable computation is needed to analyze even a single class network with a small number of jobs, primarily because the formula makes a pass through all the states of the underlying CTMC. Therefore we need to develop efficient algorithms to reduce the computation time [Buze71] | Queueing Networks and Markov Chains Gunter Botch Stefan Greiner Hermann de Meer Kishor S. Trivedi Copyright 1998 John Wiley Sons Inc. Print ISBN 0-471-19366-6 Online ISBN 0-471-20058-1 Xif Sj Algorithms for Product-Form Networks Although product-form solutions can be expressed very easily as formulae the computation of state probabilities in a closed queueing network is very time consuming if a straightforward computation of the normalization constant using Eq. is carried out. As seen in Example considerable computation is needed to analyze even a single class network with a small number of jobs primarily because the formula makes a pass through all the states of the underlying CTMC. Therefore we need to develop efficient algorithms to reduce the computation time Buze71 Many efficient algorithms for calculating performance measures of closed product-form queueing networks have been developed. The most important ones are the convolution algorithm and the mean value analysis MVA ReLa80 . The convolution algorithm is an efficient iterative technique for calculating the normalization constant which is needed when all performance measures are computed using a set of simple equations. In contrast the mean value analysis is an iterative technique where the mean values of the performance measures can be computed directly without computing the normalization constant. We also introduce the RECAL algorithm CoGe86 recursion by chain algorithm which is well suited for networks with many job classes. The fourth and last method for analyzing product-form networks presented in detail is the so-called flow-equivalent server method CHW75b ABP85 This method is well suited when we are especially interested in computing the performance of a single station or a part of the network. There are several other algorithms that we do not cover in detail due to space limitations. Based on the mean value analysis ChSa80 and SaCh81 developed an algorithm called LBANC local balance .
