AbstractA 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
- Jeffrey P. Buzen. Computational algorithms for closed queueing networks with exponential servers. Communications of the ACM, 16(9):527-531, September 1973.
- A. E. Conway and N. D. Georganas. RECAL -- a new efficient algorithm for the exact analysis of multiple-chain closed queuing networks. Journal of the ACM, 33(4):768-791, October 1986.
- Simon S. Lam. Dynamic scaling and growth behavior of queuing network normalization constants. Journal of the ACM, 29(2):492-513, April 1982.
- Simon S. Lam and Y. Luke Lien. A tree convolution algorithm for the solution of queueing networks. Communications of the ACM, 26(3):203-215, March 1983.
- J. McKenna and Debasis Mitra. Asymptotic expansions and integral representations of moments of queue lengths in closed Markovian networks. Journal of the ACM, 31(2):346-360, April 1984.
- M. Reiser and S. S. Lavenberg. Mean-value analysis of closed multichain queuing networks. Journal of the ACM, 27(2):313-322, April 1980.
- Edmundo de Souza e Silva and S. S. Lavenberg. Calculating joint queue-length distributions in product-form queuing networks. Journal of the ACM, 36(1):194-207, January 1989.