Journal of the ACM Bibliography

Gagan L. Choudhury, Kin K. Leung, and Ward Whitt. Calculating normalization constants of closed queueing networks by numerically inverting their generating functions. Journal of the ACM, 42(5):935-970, September 1995. [BibTeX entry]

A new algorithm is developed for calculating normalization constants (partition functions) and moments of product-form steady-state distributions of closed queueing networks and related models. The essential idea is to numerically invert the generating function of the normalization constant and related generating functions appearing in expressions for the moments. It is known that the generating function of the normalization constant often has a remarkably simple form, but numerical inversion evidently has not been considered before. For p-dimensional transforms, as occur with queueing networks having p closed chains, the algorithm recursively performs p one-dimensional inversions. The required computation grows exponentially in the dimension, but the dimension can often be reduced by exploiting conditional decomposition based on special structure. For large populations, the inversion algorithm is made more efficient by computing large sums using Euler summation. The inversion algorithm also has a very low storage requirement. A key ingredient in the inversion algorithm is scaling. An effective static scaling is developed for multichain closed queueing networks with only single-server and (optionally) infinite-server queues. An important feature of the inversion algorithm is a self-contained accuracy check, which allows the results to be verified in the absence of alternative algorithms. Copyright 1995 by ACM, Inc.

The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.

Categories and Subject Descriptors: C.4 [Performance of Systems] -- modeling techniques; F.2.1 [Analysis of Algorithms and Problem Complexity]: Numerical Algorithms and Problems -- computation of transformations; G.1.4 [Numerical Analysis]: Quadrature and Numerical Differentiation -- multiple quadrature; G.1.m [Numerical Analysis]: Miscellaneous -- miscellaneous

General Terms: Algorithms, Performance, Theory

Additional Key Words and Phrases: closed queueing networks, dimension reduction, Euler summation, generating function, normalization constant, numerical transform inversion, partition function, performance analysis, product-form model, scaling

Selected references


  • Journal of the ACM homepage
  • Bibliography top level
  • Journal of the ACM Author Index
  • Search the HBP database