RECAL—a new efficient algorithm for the exact analysis of multiple-chain closed queuing networks

Abstract

RECAL, a Re cursion by C hain Al gorithm for computing the mean performance measures of product-form multiple-chain closed queuing networks, is presented. It is based on a new recursive expression that relates the normalization constant of a network with r closed routing chains to those of a set of networks having ( r - 1) chains. It relies on the artifice of breaking down each chain into constituent subchains that each have a population of one. The time and space requirements of the algorithm are shown to be polynomial in the number of chains. When the network contains many routing chains, the proposed algorithm is substantially more efficient than the convolution or mean value analysis algorithms. The algorithm, therefore, extends the range of queuing networks that can be analyzed efficiently by exact means.