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

article

The general form linearizer algorithms: A new family of approximate mean value analysis algorithms

Authors:

Kenneth C. Sevcik,

Giuseppe Serazzi,

Shouhong WangAuthors Info & Claims

Performance Evaluation, Volume 65, Issue 2

Pages 129 - 151

https://doi.org/10.1016/j.peva.2007.05.005

Published: 01 February 2008 Publication History

Abstract

Approximate Mean Value Analysis (AMVA) is a popular technique for analyzing queueing network models due to the accuracy and efficiency that it affords. Currently, there is no algorithm that is more accurate than, and yet has the same computational cost as, the Linearizer algorithm, one of the most popular among different AMVA algorithms that trade off accuracy and efficiency. In this paper, we present a new family of AMVA algorithms, termed the General Form Linearizer (GFL) algorithms, for analyzing product-form queueing networks. The Linearizer algorithm is a special instance of this family. We show that some GFL algorithms yield more accurate solutions than, and have the same numerical properties and computational complexities as, the Linearizer algorithm. We also examine the numerical properties and computational costs of different implementations of the new and existing AMVA algorithms.

References

[1]

Balbo, G. and Serazzi, G., Asymptotic analysis of multiclass closed queueing networks: Common bottleneck. Performance Evaluation. v26 i1. 51-72.

[2]

Balbo, G. and Serazzi, G., Asymptotic analysis of multiclass closed queueing networks: Multiple bottlenecks. Performance Evaluation. v30 i3. 115-152.

[3]

Bard, Y., Some extensions to multiclass queueing network analysis. In: Arato, M., Butrimenko, A., Gelenbe, E. (Eds.), Performance of Computer Systems, North-Holland, Amsterdam, Netherlands. pp. 51-62.

[4]

Baskett, F., Chandy, K.M., Muntz, R.R. and Palacios, F.G., Open, closed, and mixed networks of queues with different classes of customers. Journal of the ACM. v22 i2. 248-260.

[5]

Buzen, J.P., Computational algorithms for closed queueing networks with exponential servers. Communications of the ACM. v16 i9. 527-531.

[6]

Chow, W.-M., Approximations for large scale closed queueing networks. Performance Evaluation. v3 i1. 1-12.

[7]

Chandy, K.M. and Neuse, D., Linearizer: A heuristic algorithm for queueing network models of computing systems. Communications of the ACM. v25 i2. 126-134.

[8]

Chandy, K.M. and Sauer, C.H., Computational algorithms for product form queueing networks. Communications of the ACM. v23 i10. 573-583.

[9]

Conway, A.E. and Georganas, N.D., RECAL - a new efficient algorithm for the exact analysis of multiple-chain closed queueing networks. Journal of the ACM. v33 i4. 768-791.

[10]

Conway, A.E., de Souza e Silva, E. and Lavenberg, S.S., Mean value analysis by chain product form queueing networks. IEEE Transactions on Computers. vC-38 i3. 432-442.

[11]

Cremonesi, P., Schweitzer, P.J. and Serazzi, G., A unifying framework for the approximate solution of closed multiclass queuing networks. IEEE Transaction on Computers. vC-51 i12. 1423-1434.

[12]

Denning, P.J. and Buzen, J.P., The operational analysis of queueing network models. Computing Surveys. v10 i3. 225-261.

[13]

Dennis Jr., J.E. and Schnabel, R.B., Numerical Methods for Unconstrained Optimization and Nonlinear Equations. 1983. Prentice-Hall, Englewood Cliffs, NJ.

[14]

D.L. Eager, Bounding algorithms for queueing network models of computer systems, Ph.D. Thesis, Tech. Rept. CSRG-156, Department of Computer Science, University of Toronto, 1984

[15]

Eager, D.L. and Sevcik, K.C., Analysis of an approximation algorithm for queueing networks. Performance Evaluation. v4 i4. 275-284.

[16]

Eager, D.L. and Sevcik, K.C., Bound hierarchies for multiple-class queueing networks. Journal of the ACM. v33 i1. 179-206.

[17]

Hoyme, K.P., Bruell, S.C., Afshari, P.V. and Kain, R.Y., A tree-structured mean value analysis algorithm. ACM Transactions on Computer Systems. v4 i2. 178-185.

[18]

Hsieh, C.T. and Lam, S.S., PAM - a noniterative approximate solution method for closed multichain queueing networks. ACM SIGMETRICS Performance Evaluation Review. v16 i1. 261-269.

[19]

Gelenbe, E., Glynn, P. and Sigman, K., Queues with negative arrivals. Journal of Applied Probability. v28. 245-250.

[20]

Lam, S.S., A simple derivation of the MVA and LBANC algorithms from the convolution algorithm. IEEE Transactions on Computers. vC-32 i11. 1062-1064.

[21]

Lam, S.S. and Lien, Y.L., A tree convolution algorithm for the solution of queueing networks. Communications of the ACM. v26 i3. 203-215.

[22]

Lavenberg, S.S. and Reiser, M., Stationary state probabilities of arrival instants for closed queueing networks with multiple types of customers. Journal of Applied Probability. v17 i4. 1048-1061.

[23]

Lazowska, E.D., Graham, G.S., Zahorjan, J. and Sevcik, K.C., Quantitative System Performance: Computer System Analysis Using Queueing Network Models. 1984. Prentice-Hall, Englewood Cliffs, NJ.

[24]

Little, J.D.C., A proof of the queueing formula L=λW. Operations Research. v9 i3. 383-387.

[25]

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

[26]

Pattipati, K.R., Kostreva, M.M. and Teele, J.L., Approximate mean value analysis algorithms for queueing networks: Existence, uniqueness, and convergence results. Journal of the ACM. v37 i3. 643-673.

[27]

Reiser, M. and Kobayashi, H., Queueing networks with multiple closed chains: Theory and computational algorithms. IBM Journal of Research and Development. v19 i3. 283-294.

[28]

M. Reiser, H. Kobayashi, On the convolution algorithm for separable queueing networks, in: Proceedings of the International Symposium on Computer Performance Measurement, Modeling, and Evaluation, Cambridge, Great Britain, 1976, pp. 109-117

[29]

Reiser, M. and Lavenberg, S.S., Mean value analysis of closed multichain queueing networks. Journal of the ACM. v27 i2. 313-322.

[30]

Rheinboldt, W.C., Methods for Solving Systems of Nonlinear Equations. 1974. SIAM, Philadelphia, PA.

[31]

P.J. Schweitzer, Approximate analysis of multiclass closed networks of queues, in: Proceedings of the International Conference on Stochastic Control and Optimization, Amsterdam, Netherlands, 1979, pp. 25-29

[32]

Schweitzer, P.J., Serazzi, G. and Broglia, M., A queue-shift approximation technique for product-form queueing networks. In: Lecture Notes in Computer Science, vol. 1469. Springer-Verlag, New York, NY. pp. 267-279.

Digital Library

[33]

Sevcik, K.C. and Mitrani, I., The distribution of queueing network states at input and output instants. Journal of the ACM. v28 i2. 358-371.

[34]

K. Sevcik, H. Wang, An improved approximate mean value analysis algorithm for solving separable queueing network models, Tech. Rept. CSRG-379, Department of Computer Science, University of Toronto, 1999

[35]

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: Iazeolla, G., Courtois, P.J., Hordijk, A. (Eds.), Mathematical Computer Performance and Reliability, North-Holland, Amsterdam, Netherlands. pp. 225-244.

[36]

de Souza e Silva, E., Lavenberg, S.S. and Muntz, R.R., A clustering approximation technique for queueing network models with a large number of chains. IEEE Transactions on Computers. vC-35 i5. 419-430.

[37]

de Souza e Silva, E. and Lavenberg, S.S., Calculating joint queue-length distributions in product-form queueing networks. Journal of the ACM. v36 i1. 194-207.

[38]

de Souza e Silva, E. and Muntz, R.R., A note on the computational cost of the linearizer algorithm for queueing networks. IEEE Transactions on Computers. v39 i6. 840-842.

[39]

Tucci, S. and Sauer, C.H., The tree MVA algorithm. Performance Evaluation. v5 i3. 187-196.

[40]

Wang, H. and Sevcik, K.C., Experiments with improved approximate mean value analysis algorithms. Performance Evaluation. v39 i1-4. 189-206.

[41]

Zahorjan, J., Eager, D.L. and Sweillam, H.M., Accuracy, speed, and convergence of approximate mean value analysis. Performance Evaluation. v8 i4. 255-270.

Cited By

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

Index Terms

The general form linearizer algorithms: A new family of approximate mean value analysis algorithms
1. Computing methodologies
  1. Modeling and simulation
    1. Model development and analysis
      1. Model verification and validation
  2. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Linear algebra algorithms
2. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on matrices
  2. Probability and statistics
    1. Statistical paradigms
      1. Queueing theory
      2. Statistical graphics

Recommendations

Simple Relationships Among Moments of Queue Lengths in Product form Queueing Networks

Obtains simple relationships among partial derivatives and moments of mean queue lengths in product form queueing network models. It is shown that the mean value analysis equations can be used to obtain recursive expressions which make it possible to ...
The analysis of batch sojourn-times in polling systems

We consider a cyclic polling system with general service times, general switch-over times, and simultaneous batch arrivals. This means that at an arrival epoch, a batch of customers may arrive simultaneously at the different queues of the system. For ...
Polling systems with a gated/exhaustive discipline
ValueTools '08: Proceedings of the 3rd International Conference on Performance Evaluation Methodologies and Tools

We consider a polling system where the server cyclically serves the queues according to the following discipline: the server does one round of visits to the queues applying the gated service discipline at each of the queues, followed by one round of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Performance Evaluation

Performance Evaluation Volume 65, Issue 2

February, 2008

105 pages

ISSN:0166-5316

Issue’s Table of Contents

Copyright © © 2007.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 February 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

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

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents