A tree convolution algorithm for the solution of queueing networks

ABSTRACT

A new algorithm called the tree convolution algorithm, for the computation of normalization constants and performance measures of product-form queueing networks, is presented. Compared to existing algorithms, the algorithm is very efficient in the solution of networks with many service centers and many sparse routing chains. (A network is said to have sparse routing chains if the chains visit, on the average, only a small fraction of all centers in the network.) In such a network, substantial time and space savings can be achieved by exploiting the network's routing information. The time and space reductions are made possible by two features of the algorithm: (1) the sequence of array convolutions to compute a normalization constant is determined according to the traversal of a tree; (2) the convolutions are performed between arrays that are smaller than arrays used by existing algorithms. The routing information of a given network is used to configure the tree to reduce the algorithm's time and space requirements; some effective heuristics for optimization are described. An exact solution of a communication network model with 64 queues and 32 routing chains is illustrated.

REFERENCES

• 1: Yonathan Bard, Some Extensions to Multiclass Queueing Network Analysis, Proceedings of the Third International Symposium on Modelling and Performance Evaluation of Computer Systems: Performance of Computer Systems, p.51-62, February 06-08, 1979
• 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: Bruel, S. C. and Balbo, G. Computational Algorithms for Closed Queueing Networks. Elsevier, North-Holland, New York, 1980.
• 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: Chandy, K. M., Herzog, U., and Woo L. S. Parametric analysis of queueing networks. IBM }. of Res. and Develop. 19, 1, (Jan. 1975) 43-49.
• 6: K. Mani Chandy , Doug Neuse, Linearizer: a heuristic algorithm for queueing network models of computing systems, Communications of the ACM, v.25 n.2, p.126-134, Feb 1982 [doi>10.1145/358396.358403]
• 7: 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]
• 8: Gerla, M. and Kleinrock, L. Flow control: A comparative survey. IEEE Trans. on Commun. COM 28, 4, (April 1980) 553-574.
• 9: Kleinrock, L. Queueing Systems, Vol. 2: Computer Applications. Wiley- Interscience, New York, 1976, pp. 458-484.
• 10: Lam, S. S. Queueing networks with population size constraints. IBM I. at Res. and Develop. 21, 4, (July 1977) 370-378.
• 11: Simon S. Lam, Dynamic Scaling and Growth Behavior of Queuing Network Normalization Constants, Journal of the ACM (JACM), v.29 n.2, p.492-513, April 1982 [doi>10.1145/322307.322321]
• 12: Simon S. Lam, A Simple Derivation of the MVA and LBANC Algorithms From the ConvolutionAlgorithm, University of Texas at Austin, Austin, TX, 1981
• 13: Simon S. Lam , Y. L. Lien, An Analysis of the Tree Convolution Algorithm, University of Texas at Austin, Austin, TX, 1981
• 14: Lam, S. S. and Lien, Y. L. Congestion control of packet communication networks by input buffer limits--A simulation study. IEEE Trans. on Computers G-30, 10, (Oct. 1981) 733-742.
• 15: Simon S. Lam , Y. Luke Lien, Optimal routing in networks with flow-controlled virtual channels, ACM SIGMETRICS Performance Evaluation Review, v.11 n.1, p.38-46, Spring 1981
• 16: Lam, S. S. and Wang, I. W. Queueing network models of packet switching networks, part 2: Networks with population size constraints. Performance Evaluation. 2, 3, (1982), 161-180.
• 17: Lavenberg, S. Closed multichain product form queueing networks with large population sizes. Prec. of Interface between Applied Probability and Computer Science, Boca Raton, Florida, Jan. 1981.
• 18: Yeong-Chang Luke Lien, Modelling and analysis of flow-controlled computer communication networks, 1981
• 19: Reiser, M. Numerical methods in separable queueing networks. Studies in Management Sci. 7, (1977) 113-142.
• 20: Reiser, M. A queueing network analysis of computer communication networks with window flow control. IEEE Trans. on Commun. COM- 27, 8, (Aug. 1979) 1199-1209.
• 21: Reiser, M. Mean value analysis and convolutional method for queuedependent servers in closed queueing networks. Performance Evaluation, 1, 1, (1981) 7-18.
• 22: Reiser, M. and Kobayashi, H. Queaeing networks with multiple closed chains: Theory and computational algorithms. IBM J. Res. Develop., 19, 3, (May 1975) 283-204.
• 23: 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]
• 24: Sauer, C. H. and Chandy, K. M. Computer Systems Performance Modeling. Prentice-Hall, Englewood Cliffs, New Jersey, 1981.
• 25: Schweitzer, P. Approximate analysis of multiclass closed networks of queues. Int. Conf. Stochastic Control and Optimization, Amsterdam, 1979.
• 26: Wang, J. W. and Lam, S. S. Queueing network models of packet switching networks, part 1: Open networks. Performance Evaluation, 2, 1, (1982) 9-21.
• 27: John Zahorjan, The approximate solution of large queueing network models, 1980

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques; Design studies

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Network communication
      D.4.8 Performance
          Subjects: Queueing theory; Modeling and prediction

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
algorithms, computational algorithms, design, performance, performance evaluation, product-form solution, queueing networks, sparse routing chains, theory, tree convolution algorithm