12th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems (MASCOTS'04)
A New Recursive Algorithm for Computing Generating Functions in Closed Multi-Class Queueing Networks
Volendam, The Netherlands
October 04-October 08
ISBN: 0-7695-2251-3
We obtain an algorithm that implements a recursive generating function (RGF) for computing the normalising constant in closed, multi-class, product-form queueing networks with multiple, load-independent servers of the same load. It expresses the generating function of a q-class network in terms of the generating functions of a set of (q-1)-class networks. The result for a multi-class network can therefore be deduced hierarchically by finding the normalising constants of a collection of single class networks. A storage management scheme is devised, based on a depth-first recursion tree traversal, to optimise both time and storage requirements and the numerical precision of the resulting RGF algorithm is investigated. In two-class networks, the space and time requirements of RGF are shown to be smaller than for the convolution and RECAL algorithms when the networks contain a moderate to large number of customers. With more classes, RGF gives better performance than the other two methods in many-node networks that are organised in a few groups of several identical nodes.
Citation:
Peter G. Harrison, Ting Ting Lee, "A New Recursive Algorithm for Computing Generating Functions in Closed Multi-Class Queueing Networks," mascots, pp.231-238, 12th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems (MASCOTS'04), 2004