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

article

Free access

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

Authors:

K. R. Pattipati,

M. M. Kostreva,

J. L. TeeleAuthors Info & Claims

Journal of the ACM (JACM), Volume 37, Issue 3

Pages 643 - 673

https://doi.org/10.1145/79147.214074

Published: 01 July 1990 Publication History

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]

AGRAWAL, A. Meta Modeling: A Study of Approximation in Queueing Networks. M.I.T. Press, Cambridge, Mass., 1985.

[2]

AVRIEL, M. Nonlinear Programming. Prentice-Hall, Englewood Cliffs, N.J., 1976.

[3]

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.

[4]

BERTSEKAS, D.P. Constrained Optimization and Lagrange Multiplier Methods. Academic Press, Orlando, Fla., 1982.

[5]

BERTSEKAS, D. P., AND TSITSIKLIS, J. N. Parallel and Distributed Computation. Prentice-Hall, Englewood Cliffs, N.J., 1989.

[6]

BUZEN, J.P. Computational algorithms for closed queueing networks with exponential servers. Commun. ACM 16 (1973), 527-531.

[7]

CHANDY, K. M., AND NEUSE, D. Linearizer: A heuristic algorithm for queueing network models of computing systems. Commun. ACM 25 (1982), 126-134,

[8]

CHANDY, K. M., AND SAUER, C. H. Computational algorithms for product form queueing networks. Commun. ACM 23 (1980), 573-583.

[9]

CHow, W.-M. Approximation for large scale closed queue networks. Perf. Eval. Rev. 3 (1983), 1-12.

[10]

CONWAY, A. E., DE SOUZA E SILVA, E., AND LAVENBERG, S.S. Mean value analysis by chain of product form queueing networks. IEEE Trans. Comput. C-38 (1989), 432-442.

[11]

CONWAY, A. E., AND GEORGANAS, N.O. RECAL--A new efficient algorithm for the exact analysis of multiple-chain closed queueing networks. J. ACM 33 (1986), 768-79 I.

[12]

DENNIS, j. E., AND SCHNABEL, R. B. Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice-Hall, Englewood Cliffs, N.J., 1983.

[13]

DE SOUZA E SILVA, E., LAVENBERG, S. S., AND MUNTZ, R.R. A perspective on iterative methods for the approximate analysis of closed queueing networks. In Mathematical Computer Performance and Reliability, G. lazeolla, P. J. Courtois, and A. Hordjik, eds. North Holland, Amsterdam, 1984, pp. 225-244.

[14]

EAGER, D. L., AND SEVCIK, K. Performance bound hierarchies for queuing networks. ACM Trans. Comput. Syst. I (1983), 99-115.

[15]

EAGER, D. L., AND SEVCIK, K. An analysis of an approximation algorithm for queueing networks. Perf. Eval. 4 (1984), 275-284.

[16]

EAGER, D. L., AND SEVCIK, K. Bound hierarchies for multiple-class queueing networks. J. ACM 33 (1986), 179-206.

[17]

GOLUB, G. H., AND VAN LOAN, C.F. Matrix Computations, 2nd edition. Johns Hopkins Press, Baltimore, Md., 1989.

[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]

KRZESlNSKI, A., AND GREYLING, J. Improved linearizer methods for queueing networks with queue dependent centers. In Proceedings of the ACM SIGMETRICS Conference, 1984, pp. 41-51.

[21]

LAM, S. S., AND LIEN, Y.L. A tree convolution algorithm for the solution of queueing networks. Tech. Rep. TR-165. Dept. of Computer Science, Univ. of Texas, Austin, Tex., 1982.

[22]

LAVENBERG, S. S., ed. Computer Performance Modeling Handbook. Academic Press, Orlando, Fla., 1983.

[23]

LAZOWSKA, E. D., GRAHAM, G. S., ZAHORJAN, J., AND SEVCIK, K. C. Quantitative System Performance: Computer System 'Analysis Using Queueing Network Models. Prentice-Hall, Englewood Cliffs, N.J., 1984.

[24]

LUENBERGER, D. G. Introduction to Linear and Nonlinear Programming, Addison-Wesley, Reading, Mass., 1973.

[25]

MCKENNA, J., AND MITRA, D. Asymptotic expansions and integral representations of moments of queuelengths in closed markovian queueing networks. J. ACM 31 (1984), 346-360.

[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]

NEUSE, D. Approximate analysis of large and general queueing networks. Ph.D. dissertation, Dept. of Computer Science, TR-LCS-8206, Univ. of Texas, Austin, Tex., 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]

ORTEGA, J., AND RHEINBOLDT, W. lterative Solution of Nonlinear Equations in Several Variables. Academic Press, Orlando, Fla., 1970.

[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]

REISER, M., AND LAVENBERG, S.S. Mean-value-analysis of closed multi-chain queueing networks. J. ACM 27 (1980), 310-322.

[36]

RHEINBOLDT, W.C. Methods for Solving Systems of Nonlinear Equations. SIAM, Philadelphia, Pa., 1974.

[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]

WILKINSON, J.H. The Algebraic Eigenvalue Problem. Clarendon Press, Oxford, England, 1965.

[42]

ZAHORJAN, J., SEVCIK, K., EAGER, I). L., AND GALLER, B. I. Balanced job bound analysis of queueing networks. Commun. ACM 25 (1982), 134-141.

Cited By

Piazza CRossi SSmuseva D(2024)Efficient Algorithm for Proportional Lumpability and Its Application to Selfish Mining in Public BlockchainsAlgorithms10.3390/a1704015917:4(159)Online publication date: 15-Apr-2024
https://doi.org/10.3390/a17040159
Casale GGao YNiu ZZhu L(2024)LN: A Flexible Algorithmic Framework for Layered Queueing Network AnalysisACM Transactions on Modeling and Computer Simulation10.1145/363345734:3(1-26)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3633457
Casale GHarrison POng W(2021)Facilitating load-dependent queueing analysis through factorizationPerformance Evaluation10.1016/j.peva.2021.102241152:COnline publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1016/j.peva.2021.102241
Show More Cited By

Index Terms

Approximate mean value analysis algorithms for queuing networks: existence, uniqueness, and convergence results
1. Computing methodologies
  1. Modeling and simulation
    1. Model development and analysis
      1. Modeling methodologies

Recommendations

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 ...
On the properties of approximate mean value analysis algorithms for queueing networks

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 Journal of the ACM

Journal of the ACM Volume 37, Issue 3

July 1990

247 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/79147

Issue’s Table of Contents

Copyright © 1990 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1990

Published in JACM Volume 37, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
972
Total Downloads

Downloads (Last 12 months)85
Downloads (Last 6 weeks)15

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Piazza CRossi SSmuseva D(2024)Efficient Algorithm for Proportional Lumpability and Its Application to Selfish Mining in Public BlockchainsAlgorithms10.3390/a1704015917:4(159)Online publication date: 15-Apr-2024
https://doi.org/10.3390/a17040159
Casale GGao YNiu ZZhu L(2024)LN: A Flexible Algorithmic Framework for Layered Queueing Network AnalysisACM Transactions on Modeling and Computer Simulation10.1145/363345734:3(1-26)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3633457
Casale GHarrison POng W(2021)Facilitating load-dependent queueing analysis through factorizationPerformance Evaluation10.1016/j.peva.2021.102241152:COnline publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1016/j.peva.2021.102241
Li SLuo QHampshire R(2021)Optimizing large on-demand transportation systems through stochastic conic programmingEuropean Journal of Operational Research10.1016/j.ejor.2020.10.053295:2(427-442)Online publication date: Dec-2021
https://doi.org/10.1016/j.ejor.2020.10.053
Ghobaei-Arani MKhorsand RRamezanpour M(2019)An autonomous resource provisioning framework for massively multiplayer online games in cloud environmentJournal of Network and Computer Applications10.1016/j.jnca.2019.06.002Online publication date: Jun-2019
https://doi.org/10.1016/j.jnca.2019.06.002
Legato PMazza R(2019)Class Aggregation for Multi-class Queueing Networks with FCFS Multi-server StationsQueueing Theory and Network Applications10.1007/978-3-030-27181-7_14(221-239)Online publication date: 27-Aug-2019
https://dl.acm.org/doi/10.1007/978-3-030-27181-7_14
Khorsand RGhobaei-Arani MRamezanpour M(2018)WITHDRAWN: A fuzzy auto-scaling approach using workload prediction for MMOG application in a cloud environmentSimulation Modelling Practice and Theory10.1016/j.simpat.2018.07.009Online publication date: Aug-2018
https://doi.org/10.1016/j.simpat.2018.07.009
Waizmann TTribastone MAvritzer AIosup AZhu XBecker S(2016)DiffLQNCompanion Publication for ACM/SPEC on International Conference on Performance Engineering10.1145/2859889.2859896(63-68)Online publication date: 12-Mar-2016
https://dl.acm.org/doi/10.1145/2859889.2859896
Casale GPrez JWang W(2015)QD-AMVAPerformance Evaluation10.1016/j.peva.2015.06.00691:C(80-98)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1016/j.peva.2015.06.006
Anselmi JD'Auria BWalton N(2013)Closed Queueing Networks Under CongestionMathematics of Operations Research10.1287/moor.1120.058338:3(469-491)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1287/moor.1120.0583
Show More Cited By

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 Article

Media

Figures

Other

Tables

View Issue’s Table of Contents