A tree-structured mean value analysis algorithm

Abstract

In a recent paper, Lam and Lien described an algorithm called tree-convolution that can reduce the space and computation time required for evaluating sparse multiclass, product-form queueing networks. In this paper, we develop an exact algorithm based on mean value analysis (MVA) that is the counterpart of the tree-convolution algorithm. The order of reduction in storage and computation achieved by our new Tree-MVA algorithm compared to the standard MVA algorithm is the same order of reduction obtained by the tree-convolution algorithm over that of the standard convolution algorithm. Our Tree-MVA algorithm preserves the inherent simplicity of MVA based algorithms.