Passage time distributions in large Markov chains

ABSTRACT

Probability distributions of response times are important in the design and analysis of transaction processing systems and computer-communication systems. We present a general technique for deriving such distributions from high-level modelling formalisms whose state spaces can be mapped onto finite Markov chains. We use a load-balanced, distributed implementation to find the Laplace transform of the first passage time density and its derivatives at arbitrary values of the transform parameter s. Setting s = 0 yields moments while the full passage time distribution is obtained using a novel distributed Laplace transform inverter based on the Laguerre method. We validate our method against a variety of simple densities, cycle time densities in certain overtake-free (tree-like) queueing networks and a simulated Petri net model. Our implementation is thereby rigorously validated and has already been applied to substantial Markov chains with over 1 million states. Corresponding theoretical results for semi-Markov chains are also presented.

REFERENCES

• 1: J. Abate, G. Choudhury, and W. Whitt. On the Laguerre method for numerically inverting Laplace transforms. INFORMS Journal on Computing, 8(4):413-427, 1996.
• 2: J. Abate, G. Choudhury, and W. Whitt. An introduction to numerical transform inversion and its application to probability models. In W. Grassman, editor, Computational Probability, pages 257-323, Kluwer, Boston, 2000.
• 3: Joseph Abate , Ward Whitt, The Fourier-series method for inverting transforms of probability distributions, Queueing Systems: Theory and Applications, v.10 n.1-2, p.5-88, Jan. 1992 [doi>10.1007/BF01158520]
• 4: J. Abate and W. Whitt. Numerical inversion of Laplace transforms of probability distributions. ORSA Journal on Computing, 7(1):36-43, 1995.
• 5: Gunter Bolch , Stefan Greiner , Hermann de Meer , Kishor S. Trivedi, Queueing networks and Markov chains: modeling and performance evaluation with computer science applications, Wiley-Interscience, New York, NY, 1998
• 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: Daniel D. Deavours , William H. Sanders, An efficient disk-based tool for solving large Markov models, Performance Evaluation, v.33 n.1, p.67-84, June 1998 [doi>10.1016/S0166-5316(98)00010-8]
• 8: H. Duduna. Passage times for overtake-free paths in Gordon-Newell networks. Advances in Applied Probability, 14:672-686, 1982.
• 9: William Gropp , Ewing Lusk , Anthony Skjellum, Using MPI: portable parallel programming with the message-passing interface, MIT Press, Cambridge, MA, 1994
• 10: P. Harrison. Laplace transform inversion and passage-time distributions in Markov processes. Journal of Applied Probability, 27:74-87, 1990.
• 11: Peter G. Harrison , Naresh M. Patel, Performance Modelling of Communication Networks and Computer Architectures (International Computer S, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1992
• 12: J. Keilson and W. Nunn. Laguerre transformation as a tool for the numerical solution of integral equations of convolution type. Applied Mathematics and Computation, 5:313-359, 1979.
• 13: F. Kelly and P. Pollett. Sojourn times in closed queueing networks. Advances in Applied Probability, 15:638-656, 1983.
• 14: W. Knottenbelt. Generalised Markovian analysis of timed transition systems. Master's thesis, University of Cape Town, Cape Town, South Africa, July 1996.
• 15: W. Knottenbelt. Parallel Performance Analysis of Large Markov Models. PhD thesis, Imperial College, London, United Kingdom, February 2000.
• 16: W. Knottenbelt and P. Harrison. Distributed disk-based solution techniques for large Markov models. In Proceedings of the 3rd International Meeting on the Numerical Solution of Markov Chains (NSMC '99), pages 58-75, Zaragoza, Spain, September 1999.
• 17: W. J. Knottenbelt , P. G. Harrison , M. A. Mestern , P. S. Kritzinger, A probabilistic dynamic technique for the distributed generation of very large state spaces, Performance Evaluation, v.39 n.1-4, p.127-148, Feb. 2000 [doi>10.1016/S0166-5316(99)00061-9]
• 18: William T. Weeks, Numerical Inversion of Laplace Transforms Using Laguerre Functions, Journal of the ACM (JACM), v.13 n.3, p.419-429, July 1966 [doi>10.1145/321341.321351]