Approximate mean value analysis algorithms for queuing networks: existence, uniqueness, and convergence results

ABSTRACT

This paper is concerned with the properties of nonlinear equations associated with the Scheweitzer-Bard (S-B) approximate mean value analysis (MVA) heuristic for closed product-form queuing networks. Three forms of nonlinear S-B approximate MVA equations in multiclass networks are distinguished: Schweitzer, minimal, and the nearly decoupled forms. The approximate MVA equations have enabled us to: (a) derive bounds on the approximate throughput; (b) prove the existence and uniqueness of the S-B throughput solution, and the convergence of the S-B approximation algorithm for a wide class of monotonic, single-class networks; (c) establish the existence of the S-B solution for multiclass, monotonic networks; and (d) prove the asymptotic (i.e., as the number of customers of each class tends to ∞) uniqueness of the S-B throughput solution, and (e) the convergence of the gradient projection and the primal-dual algorithms to solve the asymptotic versions of the minimal, the Schweitzer, and the nearly decoupled forms of MVA equations for multiclass networks with single server and infinite server nodes. The convergence is established by showing that the approximate MVA equations are the gradient vector of a convex function, and by using results from convex programming and the convex duality theory.

REFERENCES

• 1: Subhash C. Agrawal, Metamodeling: a study of approximations in queueing models, Massachusetts Institute of Technology, Cambridge, MA, 1985
• 2: AVRIEL, M. Nonlinear Programming. Prentice-Hall, Englewood Cliffs, N.J., 1976.
• 3: 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
• 4: BERTSEKAS, D.P. Constrained Optimization and Lagrange Multiplier Methods. Academic Press, Orlando, Fla., 1982.
• 5: Dimitri P. Bertsekas , John N. Tsitsiklis, Parallel and distributed computation: numerical methods, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 6: 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]
• 7: 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]
• 8: 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]
• 9: CHow, W.-M. Approximation for large scale closed queue networks. Perf. Eval. Rev. 3 (1983), 1-12.
• 10: 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]
• 11: 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]
• 12: J. E. Dennis, Jr. , Robert B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Classics in Applied Mathematics, 16), Soc for Industrial & Applied Math, 1996
• 13: Edmundo de Souza e Silva , Stephen S. Lavenberg , Richard R. Muntz, A Perspective on Iterative Methods for the Approximate Analysis of Closed Queueing Networks, Proceedings of the International Workshop on Computer Performance and Reliability, p.225-244, September 26-30, 1983
• 14: Derek L. Eager , Kenneth C. Sevcik, Performance bound hierarchies for queueing networks, ACM Transactions on Computer Systems (TOCS), v.1 n.2, p.99-115, May 1983 [doi>10.1145/357360.357363]
• 15: Derek L. Eager , Kenneth C. Sevcik, An analysis of an approximation algorithm for queueing networks, Performance Evaluation, v.4 n.4, p.275-284, Nov. 1984 [doi>10.1016/0166-5316(84)90012-9]
• 16: Derek L. Eager , Kenneth C. Sevcik, Bound hierarchies for multiple-class queuing networks, Journal of the ACM (JACM), v.33 n.1, p.179-206, Jan. 1986 [doi>10.1145/4904.4992]
• 17: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 18: HEIDELBERGER, P., AND LAVENBERG, S.S. Computer performance evaluation methodology. IEEE Trans. Comput. C-33 (1984), 1195-1220.
• 19: JOHNSON, R. E., KOKEMEISTER, F. L., AND WOLK, E.S. Calculus and Analytic Geometry. Allyn and Bacon, Inc., Boston, Mass., 1975.
• 20: A. Krzesinski , J. Greyling, Improved lineariser methods for queueing networks with queue dependent centres, Proceedings of the 1984 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.41-51, January 1984
• 21: Simon S. Lam , Y. L. Lien, A Tree Convolution Algorithm for Queueing Networks, University of Texas at Austin, Austin, TX, 1981
• 22: Stephen S. Lavenberg, Computer Performance Modeling Handbook, Academic Press, Inc., Orlando, FL, 1983
• 23: 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
• 24: LUENBERGER, D. G. Introduction to Linear and Nonlinear Programming, Addison-Wesley, Reading, Mass., 1973.
• 25: 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]
• 26: MORE, J. J., GARBOW, I. S., AND HILLSTROM, K. E. User guide for minpack~l. ANL-80-74. Argonne National Laboratory, Argonne, I11.
• 27: MORE, J., ANO RHEINBOLDT, W. On P- and S-functions and Related Classes of n-dimensional Nonlinear Mappings. Lin. Alg. Appl. 6 (1973), 45-68.
• 28: Douglas Malcolm Neuse, Approximate analysis of large and general queueing networks, 1982
• 29: ORTEGA, J. M., AND RHEINBOLDT, W. C. Local and global convergence of generalized linear iterations, in Proceedings of the 1968 SIAM Symposium on Numerical Solution of Nonlinear Problems. SIAM Publications, Philadelphia, Pa., 1970.
• 30: James M. Ortega , Werner C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 31: PATTIPATI, K. R., AND KOSTREVA, M.M. On the convergence of the approximate mean value analysis algorithms for queueing networks: Multi-class case. Tech. Rep. ESE-TR-87-11. Dept. of Electrical and Systems Engineering. Univ. Connecticut, Storrs, Conn.
• 32: PATTIPATI, K. R., KOSTREVA, M. M., AND TEELE, J. L. Approximate mean value analysis algorithms of queueing networks: Modified formulations and convergence results. Tech. Rep. ESE- TR-89-1. Dept. of Electrical and Systems Engineering. University of Connecticut, Storrs, Conn.
• 33: PATTIPATI, K. R., AND SHAW, J. Heuristic algorithms for the performance evaluation of computer systems: A new look at an old problem. In Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing (Bangalore, India, Dec.). IEEE, New York, 1984, pp. 867-872.
• 34: PATTIPATI, K. R., AND TEELE, J.L. On the convergence of the appoximate mean value analysis algorithms for queueing networks: Single class case. Tech. Rep. ESE-TR-87-10. Dept. Electrical and Systems Engineering. Univ. of Connecticut, Storrs, Conn.
• 35: 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]
• 36: Werner C. Rheinboldt, Methods for Solving Systems of Nonlinear Equations, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1998
• 37: SAUER, C. H., AND CHANDV, K. M. Computer Systems Performance Modeling. Prentice-Hall, Englewood Cliffs, N.J., 1981.
• 38: SCIaWEITZER, P. Approximate analysis of multi-class closed networks of queues. In Proceedings of the International Conference on Stochastic Control and Optimization. Amsterdam, Netherlands, 1979.
• 39: SURf, R. A concept of monotonicity and its characterization for closed queueing networks. Oper. Res. 33, 3 (May 1985), 606-625.
• 40: WHITT, W. Open and closed models for networks of queues. A T&T Bell Lab. Tech. J. 63 (1984), 1911-1979.
• 41: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988
• 42: 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