A component-level path-based simulation approach for efficient analysis of large Markov models

ABSTRACT

Markov models are used in many industrial applications, but, for very large models, simulation is often currently the only viable evaluation technique. However, simulation techniques that are based on evaluating trajectories at the level of individual states and transitions can be inefficient because they have to keep track of many details. Moreover, since they use statistical methods, estimating solutions at higher confidence intervals requires the evaluation of an increasingly large number of trajectories which often leads to poor performance. On the other hand, analytical path-based techniques can be used for computing guaranteed bounds on the true solutions, but they can have poor performance because they must evaluate many paths to obtain reasonable bounds. In this paper, we present a path-based simulation approach for evaluating models at the component, rather than individual state/transition, level. At this level of abstraction, the approach can compute more accurate solutions than traditional discrete-event simulation techniques can in a given amount of time. In addition to presenting the approach, we compare its performance and effectiveness against a path-based analytic technique.

REFERENCES

• 1: Derisavi, S., P. Kemper, and W. H. Sanders. 2003. Symbolic state-space exploration and numerical analysis of state-sharing composed models. In Proceedings of NSMC'03: The Fourth International Conference on the Numerical Solution of Markov Chains, 167--189.
• 2: Bennett L. Fox , Peter W. Glynn, Computing Poisson probabilities, Communications of the ACM, v.31 n.4, p.440-445, April 1988 [doi>10.1145/42404.42409]
• 3: Howard, R. A. 1971. Dynamic probabilistic systems, vol. ii: Semi-markov and decision processes. John Wiley & Sons, Inc.
• 4: Vinh V. Lam , Peter Buchholz , William H. Sanders, A Structured Path-Based Approach for Computing Transient Rewards of Large CTMCs, Proceedings of the The Quantitative Evaluation of Systems, First International Conference on (QEST'04), p.136-145, September 27-30, 2004 [doi>10.1109/QEST.2004.3]
• 5: John C. S. Lui , Richard R. Muntz, Computing bounds on steady state availability of repairable computer systems, Journal of the ACM (JACM), v.41 n.4, p.676-707, July 1994 [doi>10.1145/179812.179848]
• 6: Stewart, W. J. 1994. Introduction to the Numerical Solution of Markov Chains. Princeton University Press.