Asymptotic expansion for large closed queuing networks

ABSTRACT

In this paper, a new asymptotic method is developed for analyzing closed BCMP queuing networks with a single class (chain) consisting of a large number of customers, a single infinite server queue, and a large number of single server queues with fixed (state-independent) service rates. Asymptotic approximations are computed for the normalization constant (partition function) starting directly from a recursion relation of Buzen. The approach of the authors employs the ray method of geometrical optics and the method of matched asymptotic expansions. The method is applicable when the servers have nearly equal relative utilizations or can be divided into classes with nearly equal relative utilizations. Numerical comparisons are given that illustrate the accuracy of the asymptotic approximations.

REFERENCES

• 1: Milton Abramowitz, Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables,, Dover Publications, Incorporated, 1974
• 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: BENDER, C. M., AND ORSZAG, S.A. Advanced Mathematical Methods for Scientists and Engineers. McGraw-Hill, New York, 1978.
• 4: BUZEN, J. P. Queueing network models of multiprogramming. Ph.D. dissertation. Division of Engineering and Applied Physics, Harvard Univ., Cambridge, Mass., 1971.
• 5: 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]
• 6: K. Mani Chandy , Charles H. Sauer, Computational algorithms for product form queueing networks, Communications of the ACM, v.23 n.10, p.573-583, Oct. 1980 [doi>10.1145/359015.359020]
• 7: A. E. Conway , N. D. Georganas, RECAL—a new efficient algorithm for the exact analysis of multiple-chain closed queuing networks, Journal of the ACM (JACM), v.33 n.4, p.768-791, Oct. 1986 [doi>10.1145/6490.6495]
• 8: COURANT, R., AND HILBERT, D. Methods of Mathematical Physics, vol. 2. Interscience, New York, 1962.
• 9: Peter J. Denning , Jeffrey P. Buzen, The Operational Analysis of Queueing Network Models, ACM Computing Surveys (CSUR), v.10 n.3, p.225-261, Sept. 1978 [doi>10.1145/356733.356735]
• 10: GORDON, W. J., AND NEWELL, G.F. Closed queueing systems with exponential servers. Oper. Res. 15 (1967), 254-265.
• 11: JACKSON, J.R. J obshop-like queueing systems. Manage Sci. 10 (1963), 131-142.
• 12: KELLER, J.B. Rays, waves, and asymptotics. Bull. Amer. Math. Soc. 84 (1978), 727-750.
• 13: Stephen S. Lavenberg, Computer Performance Modeling Handbook, Academic Press, Inc., Orlando, FL, 1983
• 14: MCKENNA, J. Extensions and applications of RECAL in the solution of closed product-form queueing networks. Commun. in Statist., Stochastic Models 4 (1988), 235-276.
• 15: MCKENNA, J., AND MITRA, O. Integral representations and asymptotic expansions for closed Markovian queueing networks: normal usage. Bell Syst. Tech. J. 61 (1982), 661-683.
• 16: J. McKenna , Debasis Mitra, Asymptotic Expansions and Integral Representations of Moments of Queue Lengths in Closed Markovian Networks, Journal of the ACM (JACM), v.31 n.2, p.346-360, April 1984 [doi>10.1145/62.322432]
• 17: Debasis Mitra , J. McKenna, Asymptotic expansions for closed Markovian networks with state-dependent service rates, Journal of the ACM (JACM), v.33 n.3, p.568-592, July 1986 [doi>10.1145/5925.5935]
• 18: M. Reiser , S. S. Lavenberg, Mean-Value Analysis of Closed Multichain Queuing Networks, Journal of the ACM (JACM), v.27 n.2, p.313-322, April 1980 [doi>10.1145/322186.322195]
• 19: Wnlx'r, W. Open and closed models for networks of queues. AT&T Bell Lab. Tech. J. 63 (1984), 1911-1979.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.m MISCELLANEOUS
      Subjects: Queueing theory**

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Performance, Theory