Access Restriction

Author Choudhury, Gagan L. ♦ Leung, Kin K. ♦ Whitt, Ward
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1995
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Euler summation ♦ Closed queuing networks ♦ Dimension reduction ♦ Generating function ♦ Normalization constant ♦ Numerical transform inversion ♦ Partition function ♦ Performance analysis ♦ Production-form model ♦ Scaling
Abstract A new algorithm is developed for calculating normalization constants (partition functions) and moments of product-form steady-state distributions of closed queuing 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 $\textit{p}-dimensional$ transforms, as occur with queuing networks having $\textit{p}$ closed chains, the algorithm recursively performs $\textit{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 queuing 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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1995-09-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 42
Issue Number 5
Page Count 36
Starting Page 935
Ending Page 970

Open content in new tab

   Open content in new tab
Source: ACM Digital Library