Exact aggregate solutions for M/G/1-type Markov processes

ABSTRACT

We introduce a new methodology for the exact analysis of M/G/1-type Markov processes. The methodology uses basic, well-known results for Markov chains by exploiting the structure of the repetitive portion of the chain and recasting the overall problem into the computation of the solution of a finite linear system. The methodology allows for the calculation of the aggregate probability of a finite set of classes of states from the state space, appropriately defined. Further, it allows for the computation of a set of measures of interest such as the system queue length or any of its higher moments. The proposed methodology is exact. Detailed experiments illustrate that the methodology is also numerically stable, and in many cases can yield significantly less expensive solutions when compared with other methods, as shown by detailed time and space complexity analysis.

REFERENCES

• 1: D. A. Bini and B. Meini. Using displacement structure for solving non-skip-free M/G/1 type Markov chains. In A. Alfa and S. Chakravarthy, editors, Advances in Matrix Analytic Methods for Stochastic Models, pages 17-37, Notable Publications Inc. NJ, 1998.
• 2: D. A. Bini, B. Meini and V. Ramaswami. Analyzing M/G/1 paradigms through QBDs: the role of the block structure in computing the matrix G. In G. Latouche and P. Taylor, editors, Advances in Algorithmic Methods for Stochastic Models, pages 73-86, Notable Publications Inc. NJ, 2000.
• 3: G. Ciardo, A. Riska, and E. Smirni. An aggregation-based solution method for M/G/1-type processes. In B. Plateau, W. J. Stewart, and M. Silva, editors, Numerical Solution of Markov Chains, pages 21-40. Prensas Universitarias de Zaragoza, Zaragoza, Spain, 1999.
• 4: G. Ciardo and E. Smirni. ETAQA: an efficient technique for the analysis of QBD-processes by aggregation. Performance Evaluation, Vol.(36-37), pages 71-93, 1999.
• 5: D. Heyman and D. Lucantoni. Modeling multiple IP traffic streams with rate limits. In Proceedings of the 17th International Teletraffic Congress, Brazil, Dec. 2001.
• 6: G. Latouche and V. Ramaswami. Introduction to Matrix Geometric Methods in Stochastic Modeling. ASA-SIAM Series on Statistics and Applied Probability. SIAM, Philadelphia PA, 1999.
• 7: B. Meini. An improved FFT-based version of Ramaswami's formula. Comm. Statist. Stochastic Models, vol. 13 pages 223-238, 1997.
• 8: B. Meini. Solving M/G/1 type Markov chains: Recent advances and applications. Comm. Statist. Stochastic Models, vol 14(1&2) pages 479-496, 1998.
• 9: Randolph Nelson, Probability, stochastic processes, and queueing theory: the mathematics of computer performance modeling, Springer-Verlag New York, Inc., New York, NY, 1995
• 10: M. F. Neuts. Matrix-geometric solutions in stochastic models. Johns Hopkins University Press, Baltimore, MD, 1981.
• 11: M. F. Neuts. Structured stochastic matrices of M/G/1 type and their applications. Marcel Dekker, New York, NY, 1989.
• 12: B. F. Nielsen. Modelling long-range dependent and heavy-tailed phenomena by matrix analytic methods. In Advances in Matrix-Analytic Methods for Stochastic Models, G. Latouche and P. Taylor (eds.). Notable Publications, pages 265-278, 2000.
• 13: V. Ramaswami and G. Latouche. A general class of Markov processes with explicit matrix-geometric solutions. OR Spektrum, vol. 8 pages 209-218, Aug. 1986.
• 14: V. Ramaswami. A stable recursion for the steady state vector in Markov chains of M/G/1 type. Commun. Statist.- Stochastic Models, vol. 4 pages 183-263, 1988.
• 15: V. Ramaswami and J. L. Wang. A hybrid analysis/simulation for ATM performance with application to quality-of-service of CBR traffic. Telecommunication Systems, vol. 5 pages 25-48, 1996.
• 16: Alma Riska , Evgenia Smirni, MAMSolver: A Matrix Analytic Methods Tool, Proceedings of the 12th International Conference on Computer Performance Evaluation, Modelling Techniques and Tools, p.205-211, April 14-17, 2002
• 17: A. Riska, M. Squillante, S.-Z. Yu, Z. Liu, and L. Zhang, Matrix-analytic analysis of a MAP/PH/1 queue fitted to web server data. to appear at the 4thConference on Matrix-Analytic Methods, Adelaide, Australia, July 2002.
• 18: M. S. Squillante. Matrix-analytic methods: Applications, results and software tools. In G. Latouche and P. Taylor, editors, Advances in Matrix-Analytic Methods for Stochastic Models, Notable Publications Inc. NJ, 2000.
• 19: L. N. Trefethen and D. Bau III. Numerical Linear Algebra. SIAM, Philadelphia, 1997.

INDEX TERMS

Keywords:
M/G/1-type processes, Markov chains, aggregation, matrix analytic method