An efficient algorithm for the exact analysis of multiclass queueing networks with large population sizes

ABSTRACT

We introduce an efficient algorithm for the exact analysis of closed multiclass product-form queueing network models with large population sizes. We adopt a novel approach, based on linear systems of equations, which significantly reduces the cost of computing normalizing constants. With the proposed algorithm, the analysis of a model with N circulating jobs of multiple classes requires essentially the solution of N linear systems with order independent of population sizes.A distinguishing feature of our approach is that we can immediately apply theorems, solution techniques, and decompositions for linear systems to queueing network analysis. Following this idea, we propose a block triangular form of the linear system that further reduces the requirements, in terms of both time and storage, of an exact analysis. An example illustrates the efficiency of the resulting algorithm in presence of large populations.

REFERENCES

• 1: Simonetta Balsamo , Raif O. Onvural , Vittoria De Nitto Persone, Analysis of Queueing Networks with Blocking, Kluwer Academic Publishers, Norwell, MA, 2001
• 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: Andrea Bertozzi , James McKenna, Multidimensional residues, generating functions, and their application to queueing networks, SIAM Review, v.35 n.2, p.239-268, June 1993 [doi>10.1137/1035045]
• 4: Raymond M. Bryant , Anthony E. Krzesinski , M. Seetha Lakshmi , K. Mani Chandy, The MVA priority approximation, ACM Transactions on Computer Systems (TOCS), v.2 n.4, p.335-359, Nov. 1984 [doi>10.1145/357401.357406]
• 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: Stanley Cabay, Exact solution of linear equations, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.392-398, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806310]
• 7: G. Casale. The Throughput Analysis of Product-Form Queueing Networks. PhD thesis, Politecnico di Milano, Milan, Italy, 2006.
• 8: 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]
• 9: 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]
• 10: Gagan L. Choudhury , Kin K. Leung , Ward Whitt, Calculating normalization constants of closed queueing networks by numerically inverting their generating functions, Journal of the ACM (JACM), v.42 n.5, p.935-970, Sept. 1995 [doi>10.1145/210118.210122]
• 11: D.J.A. Cohen. Basic Techniques of Combinatorial Theory. John Wiley and Sons, 1978.
• 12: A. E. Conway , E. de Souza e Silva , S. S. Lavenberg, Mean Value Analysis by Chain of Product form Queueing Networks, IEEE Transactions on Computers, v.38 n.3, p.432-442, March 1989 [doi>10.1109/12.21129]
• 13: 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]
• 14: Paolo Cremonesi , Claudio Gennaro, Integrated Performance Models for SPMD Applications and MIMD Architectures, IEEE Transactions on Parallel and Distributed Systems, v.13 n.12, p.1320-1332, December 2002 [doi>10.1109/TPDS.2002.1158268]
• 15: Paolo Cremonesi , Paul J. Schweitzer , Giuseppe Serazzi, A Unifying Framework for the Approximate Solution of Closed Multiclass Queuing Networks, IEEE Transactions on Computers, v.51 n.12, p.1423-1434, December 2002 [doi>10.1109/TC.2002.1146708]
• 16: Edmundo de Souza e Silva , S. S. Lavenberg, Calculating joint queue-length distributions in product-form queuing networks, Journal of the ACM (JACM), v.36 n.1, p.194-207, Jan. 1989 [doi>10.1145/58562.58563]
• 17: E. de Sousa e Silva and R.R. Muntz. Queueing networks: Solutions and applications. Technical Report CSD-890052, CS Dep. - UCLA, Sep 1989.
• 18: J.G. Dumas et al. Linbox: A generic library for exact linear algebra. In Proc. ICMS'02, pages 40--50, World Scientific, Singapore, 2002.
• 19: David Goldberg, What every computer scientist should know about floating-point arithmetic, ACM Computing Surveys (CSUR), v.23 n.1, p.5-48, March 1991 [doi>10.1145/103162.103163]
• 20: G. H. Golub and C. F. Van Loan. Matrix computations. Johns Hopkins Univ. Press, 1996.
• 21: T. Granlund. GNU MP: The GNU Multiple Precision Arithmetic Library, Aug 2000. http://www.swox.se/.
• 22: P.G. Harrison. On normalizing constants in queueing networks. Operations research, 33:464--468, 1985.
• 23: Peter G. Harrison , Sérgio Coury, On the asymptotic behaviour of closed multiclass queueing networks, Performance Evaluation, v.47 n.2, p.131-138, February 2002 [doi>10.1016/S0166-5316(01)00061-X]
• 24: Peter G. Harrison , Ting Ting Lee, A New Recursive Algorithm for Computing Generating Functions in Closed Multi-Class Queueing Networks, Proceedings of the The IEEE Computer Society's 12th Annual International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems (MASCOTS'04), p.231-238, October 04-08, 2004
• 25: J. Kriz. Throughput bounds for closed queueing networks. Perf. Eval., 4(1):1--10, 1984.
• 26: 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]
• 27: S. Lam. A simple derivation of the mva and lbanc algorithms from the convolution algorithm. IEEE Trans. Comp., 32:1062--1064, 1983.
• 28: S. S. Lavenberg, A perspective on queueing models of computer performance, Performance Evaluation, v.10 n.1, p.53-76, Oct. 1989 [doi>10.1016/0166-5316(89)90005-9]
• 29: Edward D. Lazowska , John Zahorjan , G. Scott Graham , Kenneth C. Sevcik, Quantitative system performance: computer system analysis using queueing network models, Prentice-Hall, Inc., Upper Saddle River, NJ, 1984
• 30: J. D. C. Little. A proof of the queueing formula L=λW. Operations Research, pages 9:383--387, 1961.
• 31: Michael T. McClellan, The Exact Solution of Systems of Linear Equations with Polynomial Coefficients, Journal of the ACM (JACM), v.20 n.4, p.563-588, Oct. 1973 [doi>10.1145/321784.321787]
• 32: 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]
• 33: M. Reiser and H. Kobayashi. Queueing networks with multiple closed chains: Theory and computational algorithms. IBM J. Res. Dev., 19(3):283--294, 1975.
• 34: 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]
• 35: J. A. Rolia , K. C. Sevcik, The Method of Layers, IEEE Transactions on Software Engineering, v.21 n.8, p.689-700, August 1995 [doi>10.1109/32.403785]
• 36: P.J. Schweitzer. Approximate analysis of multiclass closed networks of queues. In Int'l Conf. on Stoch. Control and Optim., Amsterdam, pages 25--29, 1979.
• 37: M. Sereno. Mean value analysis of product form solution queueing networks with repetitive service blocking. Perf. Eval., 36--37:19--33, 1999.
• 38: The PARI Group, Bordeaux. PARI/GP, version 2.1.5, 2004. http://pari.math.u-bordeaux.fr/.
• 39: John Zahorjan , Kenneth C. Sevcik , Derek L. Eager , Bruce Galler, Balanced job bound analysis of queueing networks, Communications of the ACM, v.25 n.2, p.134-141, Feb 1982 [doi>10.1145/358396.358447]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

General Terms:
Algorithms, Performance, Theory

Keywords:
computational algorithms, exact analysis, multiclass models, normalizing constant, product-form queueing networks