A New Method For Computing The Normalization Constant Of Multiple-Chain Queueing Networks

Abstract

In a recent paper a new recursive expression was obtained for the normalization constant of product-form multiple chain closed queueing networks. This expression formed the basis of a new general purpose algorithm (named RECAL) for computing the mean performance measures. This paper is concerned with the computational aspects of obtaining the normalization constant using the new recursive expression. We present a computationally efficient formulation of the recursion and evaluate the computational complexity. This new algorithm, for computing the normalization constant, is substantially more efficient than the convolution algorithm when there are many routing chains in the network. The new algorithm therefore extends the range of queueing networks for which the normalization constant can be computed efficiently by exact means.

Résumé

Une nouvelle expression récursive pour la constante de normalisation de réseaux de files d’attente à plusieurs chaines fermées a été obtenue récemment par les auteurs. Cette expression était la base d’un nouvel algorithme (appelé RECAL) pour le calcul des mesures moyennes de performance. La présente publication traite des aspects du calcul de la constante de normalisation, utilisant la nouvelle expression récursive. Ce nouvel algorithme pour la constante de normalisation est beaucoup plus efficace que Talgorithme de convolution quand il y a plusieurs chaines de routage dans le réseau. Par conséquent, l’algorithme élargit le champ des réseaux de files d’attente dont on peut obtenir la constante de normalisation par des moyens exacts.

Additional information

Notes on contributors

A.E. Conway

ADRIAN E. CONWAY received the BA SC in Electrical Engineering from the University of Ottawa, Canada, in 1981, the MASC degree in Communication Engineering from the Imperial College of Science and Technology, London, England, in 1983, and the PH D degree in Electrical Engineering from the University of Ottawa in 1986. During 1984-5 he was a visiting researcher at the Advanced Studies Department of BULLTransac and also the Institut National de Recherche en Informatique et an Automatique (INRIA), both in Paris, France. Since the beginning of 1986 he has been doing post-doctoral research at the IBM T.J. Watson Research Centre, Yorktown Heights, NY, USA.

N.D. Georganas

NICHOLAS D. GEORGANAS is Dean of Engineering and Professor in the Department of Electrical Engineering, University of Ottawa. He received the Dipl. Ing. degree in Electrical and Mechanical Engineering from the National Technical University of Athens, Greece, in 1966 and the PH D (Summa Cum Laude) in Electrical Engineering from the University of Ottawa in 1970. He has been a faculty member in the Department of Electrical Engineering, University of Ottawa since 1970 and served as chairman from 1981 to 1984. On sabbatical leaves he spent 1977–8 with the IBM Centre d'Etudes et Recherche, La Gaude, France and 1984–5 with BULL-Transac and INRIA in Paris, France. During 1985–6, he served as chairman of the Grants Selection Committee for Electrical Engineering of the Natural Sciences and Engineering Research Council of Canada. His current research interests are in Performance Evaluation of Computer Systems, Computer-Communications, Local Area Networks and Integrated Communication Systems.