More Web Proxy on the site http://driver.im/

article

Free access

On the properties of approximate mean value analysis algorithms for queueing networks

Authors:

K. R. Pattipati,

M. M. KostrevaAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 16, Issue 1

Pages 244 - 252

https://doi.org/10.1145/1007771.55623

Published: 01 May 1988 Publication History

Abstract

This paper presents new formulations of the approximate mean value analysis (MVA) algorithms for the performance evaluation of closed product-form queueing networks. The key to the development of the algorithms is the derivation of vector nonlinear equations for the approximate network throughput. We solve this set of throughput equations using a nonlinear Gauss-Seidel type distributed algorithms, coupled with a quadratically convergent Newton's method for scalar nonlinear equations. The throughput equations have enabled us to: (a) derive bounds on the approximate throughput; (b) prove the existence, uniqueness, and convergence of the Schweitzer-Bard (S-B) approximation algorithm for a wide class of monotone, single class networks, (c) establish the existence of the S-B solution for multi-class, monotone 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 the asymptotic convergence of the various versions of the distributed algorithms in multi-class networks with single server and infinite server nodes. The asymptotic convergence is established using results from convex programming and convex duality theory. Extension of our algorithms to mixed networks is straighfoward. Only multi-class results are presented in this paper.

References

[1]

1. Lazowska, E.D., Quantitative System Performance: Computer System Analysis Using Queueing Network Models, Prentice-Hall, Englewood Cliffs: NJ, 1984.

Digital Library

[2]

2. Sauer, C.H., and K.M. Chandy, Computer Systems Performance Modeling, Prentice - Hall, Englewood Cliffs, NJ, 1981.

[3]

3. Lavenberg, S.S., (Ed.) Computer Performance Modeling Handbook, Academic Press, NY, 1983.

Digital Library

[4]

4. Schweitzer, P. "Approximate Analysis of Multi-class Closed Networks of Queues", Proceedings of the International Conference on Stochastic Control and Optimization. Amsterdam, 1979.

[5]

5. Bard, Y. "Some Extensions to Multi-class Queueing Network Analysis", in Performance of Computer Systems. M. Arato, A. Butrimenko, and E. Gelenbe, (Eds.), North Holland, Amsterdam, 1979.

Digital Library

[6]

6. Chandy, K.M. and D. Neuse, "Linearizer: A Heuristic Algorithm for Queueing Network Models of Computing Systems", Comm. of the ACM, Vol. 25, pp. 126-134, 1982.

Digital Library

[7]

7. Neuse, D., "Approximate Analysis of Large and General Queueing Networks", Ph. D Thesis, Dept. of Computer Science, TR LCS-8206, Univ. of Texas, Austin, 1982.

Digital Library

[8]

8. Krzesinski, A., and J. Greyling, "Improved Linearizer Methods for Queueing Networks with Queue Dependent Centers," Proceedings of the ACM SIGMETRICS Conference, 1984, pp. 41-51.

Digital Library

[9]

9. Chow, W.-M., Approximations for Large Scale Closed Queueing Networks", Performance Evaluation Review, Vol. 3, pp. 1-12, 1983.

[10]

10. De Souza e Silva, E., S.S. Lavenberg, and R.R. Muntz, "A Perspective on Iterative Methods for the Approximate Analysis of Closed Queueing Networks", in Mathematical Computer Performance and Reliability. G. Iazeolla, et al., (Eds.), North Holland, Amsterdam, 1984.

Digital Library

[11]

11. Zahorjan, J., K. Sevcik, D.L. Eager, and B.I. Galler, "Balanced Job Bound Analysis of Queueing Networks", Comm. of the ACM, Vol. 25, pp. 134-141, 1982.

Digital Library

[12]

12. Eager, D.L. and K. Sevcik, "Performance Bound Hierarchies for Queueing Networks", ACM Trans. Computer Systems. Vol. 1, pp. 99-115, 1983.

Digital Library

[13]

13. Mckenna, J. and D. Mitra, "Asymptotic Expansions and Integral Representations of Moments of Queuelengths in Closed Markovian Queueing Networks", Journal. of ACM. Vol. 31, pp. 346-360, 1984.

Digital Library

[14]

14. Eager, D.L. and K. Sevcik, "Bound Hierarchies for Multiple-Class Queueing Networks," Journal of ACM, Vol. 33, pp. 179-206, 1986.

Digital Library

[15]

15. Reiser, M. and S.S. Lavenberg, "Mean-Value-Analysis of Closed Multi-Chain Queueing Networks", Journal of ACM. Vol. 27, pp. 313-322, 1980.

Digital Library

[16]

16. Ortega, J. and W. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, New York, 1970.

Digital Library

[17]

17. Wilkinson, J.H., The algebraic Eigenvalue Problem, Clarendon Press: Oxford, 1965.

Digital Library

[18]

18. Golub, G.H. and C. F. Van Loan, Matrix Computations, Johns Hopkins Press, Baltimore, MD, 1984.

[19]

19. Hiedelberger, P. and S.S. Lavenberg, "Computer Performance Evaluation Methodology", IEEE Trans. Computers. Vol. C-33, pp. 1195-1220, 1984.

Digital Library

[20]

20. Avriel, M., Nonlinear Programming. Prentice-Hall, Englewood Cliffs, NJ, 1976.

[21]

21. Ortega, J.M., and W.C. Rheinboldt, "Local and Global Convergence of Generalized Linear Iterations," Proc. 1968 SIAM Symp. on Numerical Solution of Nonlinear Problems. SIAM Publications, Phila., PA, 1970.

[22]

22. Schechter, S., "Iteration Methods for Nonlinear Problems," Transactions of the American Mathematical Monthly, Vol. 104, pp. 179-189, 1962.

[23]

23. Schechter, S., "Relaxation Methods for Convex Problems," SIAM Journal on Numerical Analysis, VOl. 5, 1968, pp. 601-612.

[24]

24. More, J., and W. Rheinboldt, "On P- and S-functions and Related Classes of n-dimensional Nonlinear Mappings," Linear Algebra and Applications, Vol. 6, 1973, pp. 45-68.

[25]

25. Whitt, W. "Open and Closed Models for Networks of Queues", AT&T Bell Laboratories Technical Journal, Vol. 63, pp.1911-1979, 1984.

[26]

26. D.G. Luenberger, Introduction to Linear and Nonlinear Programming, Addison-Wesley, Reading, MA, 1973.

[27]

27. Bertsekas, D.P. Constrained Optimization and Langrange Multiplier Methods. Academic Press, New York, 1982.

[28]

28. Agarwal, A., Meta Modeling,: A Study of Approximation in Queueing Networks, M.I.T. Press, Cambridge, MA 1985.

Digital Library

[29]

29. Pattipati, K.R., and J.L. Teele, "On the Convergence of the Approximate Mean Value Analysis Algorithms for Queueing Networks: Single Class Case," Department of Electrical and Systems Engineering, ESE-TR-87-10, Univ. of Connecticut, Storrs, CT 06268.

[30]

30. Gale, D. and H. Nikaido, "The Jacobian Matrix and Global Univalence of Mappings," Mathematische Annalen, Vol. 159, 1965, pp. 81-93.

[31]

31. Eager, D.L. and K. Sevick, "An analysis of an approximation algorithm for queueing networks," Performance Evaluation, vol. 4, pp. 275-284, 1984.

Digital Library

[32]

32. Pattipati, K.R., Kostreva, M. and J.L. Teele "Approximate Mean Value Analysis Algorithms for Queueing Networks: New Formulations and Convergence Results," sub. to Journal of ACM, Sept. 1987.

Cited By

Kastner MPattipati KDunham S(1989)CAPRES: a software tool for modeling and analysis of fault-tolerant computer architecturesConference Proceedings., IEEE International Conference on Systems, Man and Cybernetics10.1109/ICSMC.1989.71372(624-629)Online publication date: 1989
https://doi.org/10.1109/ICSMC.1989.71372

Index Terms

On the properties of approximate mean value analysis algorithms for queueing networks

Recommendations

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

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 ...
On the properties of approximate mean value analysis algorithms for queueing networks
SIGMETRICS '88: Proceedings of the 1988 ACM SIGMETRICS conference on Measurement and modeling of computer systems

This paper presents new formulations of the approximate mean value analysis (MVA) algorithms for the performance evaluation of closed product-form queueing networks. The key to the development of the algorithms is the derivation of vector nonlinear ...
Approximate Analysis of Load Dependent General Queueing Networks

A method for obtaining approximate solutions to load-dependent closed queueing networks containing general service-time distributions and first-come-first-served scheduling disciplines is presented. The technique demonstrated is an extension of the well-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 16, Issue 1

May 1988

266 pages

ISSN:0163-5999

DOI:10.1145/1007771

Issue’s Table of Contents

SIGMETRICS '88: Proceedings of the 1988 ACM SIGMETRICS conference on Measurement and modeling of computer systems
May 1988
282 pages
ISBN:0897912543
DOI:10.1145/55595
Chairman:
C. U. Smith
L&S Computer Technology

Copyright © 1988 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1988

Published in SIGMETRICS Volume 16, Issue 1

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
189
Total Downloads

Downloads (Last 12 months)48
Downloads (Last 6 weeks)4

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kastner MPattipati KDunham S(1989)CAPRES: a software tool for modeling and analysis of fault-tolerant computer architecturesConference Proceedings., IEEE International Conference on Systems, Man and Cybernetics10.1109/ICSMC.1989.71372(624-629)Online publication date: 1989
https://doi.org/10.1109/ICSMC.1989.71372

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents