Computational algorithms for product form queueing networks

ABSTRACT

In the last two decades there has been special interest in queueing networks with a product form solution. These have been widely used as models of computer systems and communication networks. Two new computational algorithms for product form networks are presented. A comprehensive treatment of these algorithms and the two important existing algorithms, convolution and mean value analysis, is given.

REFERENCES

• 1: Bard, Y. Some extensions to multiclass queueing. G320-2124, IBM Cambridge Scientific Ctr., Cambridge, Mass., Nov. 1978.
• 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: Buzen, J.P. Queueing network models ofmultiprogramming. Ph.D. Th., Harvard Univ., Cambridge, Mass., 1971.
• 4: Chandy, K.M. The analysis and solutions for general queueing networks. Proc. 6th Ann. Princeton Conf. on Inform. Sci. and Syst., 1972, pp. 224-228.
• 5: Chandy, K.M., Herzog, U., and Woo, L.S. Parametric analysis of queueing networks. IBM J. Res. Develop. 19, 1 (Jan. 1975), 43--49.
• 6: K. Mani Chandy , John H. Howard, Jr. , Donald F. Towsley, Product Form and Local Balance in Queueing Networks, Journal of the ACM (JACM), v.24 n.2, p.250-263, April 1977 [doi>10.1145/322003.322009]
• 7: 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]
• 8: Jackson, J.R. Jobshop-like queueing systems. Management Sci. 10, (1963), 131-142
• 9: Kobayashi, H. A computational algorithm for queue distributions via Polya theory of enumeration. Rep. RC-6154, IBM Thomas J. Watson Res. Ctr., Yorktown Heights, N.Y., Aug. 1976.
• 10: Lam, S.S. Queueing networks with population size constraints. IBM J. Res. Develop. 21, 4 (July 1977), 370-378.
• 11: Little, J.D.C. A proof of the queueing formula L = h W. Operations Res. 9, (1961), 383-387.
• 12: Moore, F.R. Computational model of a closed queueing network with exponential servers. IBM J. Res. Develop. 16, 6 (June 1972), 567- 572.
• 13: Reiser, M., and Kobayashi, H. Queueing networks with multiple closed chains: Theory and computational algorithms. 1BM J. Res. Develop. 19, 3 (May 1975).
• 14: Reiser, M. Numerical methods in separable queueing networks. Rep. RC-5842, Thomas J. Watson Res. Ctr., Yorktown Heights, N.Y., Feb. 1976.
• 15: 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]
• 16: Reiser, M., and Saner, C.H. Queueing network models: Methods of solution and their program implementation. In Current Trends in Programming Methodology, Volume Ill: Software Modeling and Its Impact on Performance, K.M. Chandy and R.T. Yeh, Eds., Prentice- Hall, Englewood Cliffs, N.J., 1978, pp. 115-167.
• 17: Reiser, M. Mean-value analysis and convolution method for queue-dependent servers in closed queueing networks. Rep. RZ-1009, IBM Zurich Res. Ctr., Zurich, Switzerland, 1980.
• 18: Reynolds, P.F. Queueing network algorithms on programmable pocket calculators. To appear as a Tech. Rep., Dept. of Comptr. Sci., Univ. of Texas at Austin.
• 19: Charles H. Sauer , K. Mani Chandy, The impact of distributions and disciplines on multiple processor systems, Communications of the ACM, v.22 n.1, p.25-34, Jan. 1979 [doi>10.1145/359046.359053]
• 20: Saner, C.H., and Chandy, K.M. Computer System Performance Modeling: A Primer. Prentice-Hall, Englewood Cliffs, N.J. (to appear).
• 21: Sevcik, K.C., and Klawe, M.M. Operational analysis versus stochastic modelling of computer systems. Proc. Comptr. Sci. and Statistics: 12th Ann. Syrup. on the Interface, Univ. of Waterloo, May 1979.
• 22: Smith, J.L. An analysis of time sharing computer systems using Markov models. Proc. 1966 Spring Joint Comptr. Conf., Vol. 28, AFIPS Press, Alexandria, Va., pp. 87-95.
• 23: Donald Fred Towsley, Local balance models of computer systems., 1975
• 24: Wulf, W., and Bell, C.G.C.mmp, a multi-miniprocessor. Proc. 1972 Fall Joint Comptr. Conf., Vol. 41, AFIPS Press, Alexandria, Va., pp. 765-777.
• 25: Zahorjan, J.L. Computational algorithms for queueing networks with product form solutions. In Topics in Performance Evaluation, G.S. Graham, Ed., CSRG-100, Comptr. Systs. Res. Group, Univ. of Toronto, Toronto, Ontario, Canada, July 1979.

INDEX TERMS

Keywords:
performance evaluation, product form, queueing networks