A. E. Conway
Abstract
RECAL, a Recursion by Chain Algorithm for computing the mean performance measures of product-form multiple-chain closed queuing networks, is presented. It is based on a new recursive expression that relates the normalization constant of a network with r closed routing chains to those of a set of networks having (r - 1) chains. It relies on the artifice of breaking down each chain into constituent subchains that each have a population of one. The time and space requirements of the algorithm are shown to be polynomial in the number of chains. When the network contains many routing chains, the proposed algorithm is substantially more efficient than the convolution or mean value analysis algorithms. The algorithm, therefore, extends the range of queuing networks that can be analyzed efficiently by exact means.
- 1 BASKETT, F., CHANDY, K.M., MUNTZ, R.R., AND PALACIOS, F.G. Open, closed, and mixed networks of queues with different classes of customers. J. ACM 22, 2 (Apr. 1975), 248-260. Google Scholar
Digital Library
- 2 BRUELL, S.C., AND BALBO, G. ComputationalAlgorithmsfor Closed Queueing Networks. Elsevier- North Holland, New York, 1980.Google Scholar
- 3 BUZEN, J.P. Computational algorithms for closed queueing networks with exponential servers. Commun. ACM 16, 9 (Sept. 1973), 527-531. Google ScholarDigital Library
- 4 CHANDY, K.M., AND NEUSE, O. Linearizer: A heuristic algorithm for queueing network models of computer systems. Commun. ACM 25, 2 (Feb. 1982), 126-133. Google ScholarDigital Library
- 5 CHANDY, K.M., AND SAUER, C.H. Computational algorithms for product form queueing networks. Commun. ACM 23, l0 (Oct. 1980), 573-583. Google ScholarDigital Library
- 6 CONWAY, A.E., AND GEORGANAS, N.D. A new method for computing the normalization constant of multiple chain queueing networks. INFOR 24, 3 (Aug. 1986).Google Scholar
- 7 COURTOIS, P.J. Decomposability: Queueing and Computer System Applications. Academic Press, Orlando, Fla., 1977.Google Scholar
- 8 LAM, S.S. Dynamic scaling and growth behavior of queuing network normalization constants. J. ACM29, 2 (Apr. 1982), 492-513. Google ScholarDigital Library
- 9 LAM, S.S., AND LIEN, Y.L. A tree convoluted algorithm for the solution of queueing networks. Commun. ACM 26, 3 (Mar. 1983), 203-215. Google ScholarDigital Library
- 10 LAM, S.S., AND WONG, j.W. Queueing network models of packet switching networks. Part 2: Networks with population size constraints. Perform. EvaL 2, 3 (1982), 161 - 180.Google ScholarCross Ref
- 11 LAVENBERG, S.S., ED. Computer Performance Modeling Handbook. Academic Press, Orlando, Fla. 1983. Google Scholar
- 12 LAVENBERG, S.S., AND REISER, M. Stationary state probabilities at arrival instants for closed queueing networks with multiple types of customers. J. Appl. Prob. 17 (Dec. 1980), 1048-1061.Google ScholarCross Ref
- 13 LITTLE, J.D.C. A proof of the queueing formula L = hW. Oper. Res. 9 (1961), 383-387.Google ScholarDigital Library
- 14 MCKENNA, J., AND MITRA, n. Integral representations and asymptotic expansions for closed Markovian queueing networks: Normal usage. Bell Syst. Tech. J. 61, 5 (May-June 1982), 661-683.Google ScholarCross Ref
- 15 MCKENNA, J., AND MITRA, D. Asymptotic expansions and integral representations of moments of queue lengths in closed Markovian networks. J. ACM 31, 2 (Apr. 1984), 346-360. Google ScholarDigital Library
- 16 NEUSE, D.M. Approximate analysis of large and general queueing networks. Ph.D. dissertation, Univ. of Texas, Austin, 1982. Google ScholarDigital Library
- 17 REISER, M., AND KOBAYASHI, H. Queueing networks with multiple closed chains: Theory and computational algorithms. IBM J. Res. Dev., 19 (May 1975), 283-294.Google ScholarDigital Library
- 18 REISER, M., AND LAVENBERG, S.S. Mean-value analysis of closed multichain queuing networks. J. ACM 27, 2 (Apr. 1980), 313-322. Google ScholarDigital Library
- 19 SAUER, C.H., AND CHANDY, K.M. Computer Systems Performance modeling. Prentice-Hall, Englewood Cliffs, N.J., 1981.Google Scholar
Index Terms
- RECAL—a new efficient algorithm for the exact analysis of multiple-chain closed queuing networks
Recommendations
RECAL—a new efficient algorithm for the exact analysis of multiple-chain closed queueing networks (abstract)
RECAL, a Recursion by Chain Algorithm for computing the mean performance measures of product-form multiple-chain closed queueing networks, is presented. It is based on a new recursive expression which relates the normalization constant of a network with ...
RECAL—a new efficient algorithm for the exact analysis of multiple-chain closed queueing networks (abstract)
SIGMETRICS '85: Proceedings of the 1985 ACM SIGMETRICS conference on Measurement and modeling of computer systemsRECAL, a Recursion by Chain Algorithm for computing the mean performance measures of product-form multiple-chain closed queueing networks, is presented. It is based on a new recursive expression which relates the normalization constant of a network with ...
Closed Queueing Networks Under Congestion: Nonbottleneck Independence and Bottleneck Convergence
We analyze the behavior of closed multiclass product-form queueing networks when the number of customers grows to infinity and remains proportionate on each route or class. First, we focus on the stationary behavior and prove the conjecture that the ...
Comments