Mean-Value Analysis of Closed Multichain Queuing Networks

ABSTRACT

It is shown that mean queue sizes, mean waiting times, and throughputs in closed multiple-chain queuing networks which have product-form solution can be computed recursively without computing product terms and normalization constants. The resulting computational procedures have improved properties (avoidance of numerical problems and, in some cases, fewer operations) compared to previous algorithms. Furthermore, the new algorithms have a physically meaningful interpretation which provides the basis for heuristic extensions that allow the approximate solution of networks with a very large number of closed chains, and which is shown to be asymptotically valid for large chain populations.

REFERENCES

• 1: BARD, Y The modehng of some scheduling strategies for an mteractwe computer system In Computer Performance, K M. Chandy and M Relser, Eds., North Holland, Amsterdam, 1977, pp 113-137.
• 2: Forest Baskett , K. Mani Chandy , Richard R. Muntz , Fernando G. Palacios, Open, Closed, and Mixed Networks of Queues with Different Classes of Customers, Journal of the ACM (JACM), v.22 n.2, p.248-260, April 1975 [doi>10.1145/321879.321887]
• 3: James Paul Bouhana, Operational aspects of centralized queueing networks., 1978
• 4: Jeffrey P. Buzen, Computational algorithms for closed queueing networks with exponential servers, Communications of the ACM, v.16 n.9, p.527-531, Sept. 1973 [doi>10.1145/362342.362345]
• 5: Cox, D.R. A use of complex probabilities in the theory of stochastic processes. Pro(:. Cambridge Phil. Soc. M (1955), 313-319.
• 6: GORDON, W. T., AND NEWELL, G.F. Closed queuing systems with exponential servers. Operaoons Res 15 (Apr. 1967), 252-265.
• 7: JACKSON, J.R. Jobshop-fike queuing systems. Management Sci. 10 (Oct 1963), 131-142.
• 8: LAVENBERO, S. S, AND REISER, M. Stauonary state probabilities of arrival instants for closed queumg network with mulOple types of customers. Res. Pep RC 7592, IBM Thomas J. Watson Res. Ctr., Yorktown Heights, N.Y Apr. 1979. To appear in J. Appl. Prob, (Dec. 1980).
• 9: NEtrrs, M. F Probabdity dtstributtons of phase type To appear m Liber Amicorum, Leuven, Belgium.
• 10: PITTEL, B. Closed exponential networks of queues with blocking, the Jackson type stationary dtstnbuuon and its asymptotic analysts Res. Rep RC 6174, IBM Thomas J. Watson Res. Ctr, Yorktown Heights, N Y., 1976
• 11: RelsvR,M Numerical methods m separable queuing networks. Stu&es m Management Sa 7 (1977), 113- 142
• 12: Rtls~R, M. A queuing network analysis of computer ~ommumcation networks with window flow control IEEE Trans. Commun. 27 (Aug. 1979), 1199-1209.
• 13: M. Reiser , H. Kobayashi, Horner's rule for the evaluation of general closed queueing networks, Communications of the ACM, v.18 n.10, p.592-593, Oct. 1975 [doi>10.1145/361020.361217]
• 14: REIS~R, M., AND KOBAYASHI, H Queuing networks with multiple closed chains, theory and computauonal algorithms IBM J Res and Develop 19 (May 1975), 283-294.
• 15: SHUM, A.Queuing models for computer systems with general service tune dtstnbuuons Ph D Th, Harvard U, Cambridge, Mass, Dec. 1976

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Theory, Verification