A component-level path composition approach for efficient transient analysis of large CTMCs

Vinh V. Lam, Peter Buchholz, William H. Sanders

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Path-based techniques make the analysis of very large Markov models feasible by trading off high computational complexity for low space complexity. Often, a drawback in these techniques is that they have to evaluate many paths in order to compute reasonably tight bounds on the exact solutions of the models. In this paper, we present a path composition algorithm to speed up path evaluation significantly. It works by quickly composing subpaths that are precomputed locally at the component level. The algorithm is computationally efficient since individual subpaths are precomputed only once, and the results are reused many times in the computation of all composed paths. To the best of our knowledge, this work is the first to propose the idea of path composition for the analysis of Markov models. A practical implementation of the algorithm makes it feasible to solve even larger models, since it helps not only in evaluating more paths faster but also in computing long paths efficiently by composing them from short ones. In addition to presenting the algorithm, we demonstrate its application and evaluate its performance in computing the reliability and availability of a large distributed information service system in the presence of fault propagation and in computing the probabilities of buffer overflow and buffer flushing in a media multicast system with varying system configurations.

Original languageEnglish (US)
Title of host publicationProceedings - DSN 2006
Subtitle of host publication2006 International Conference on Dependable Systems and Networks
Pages485-494
Number of pages10
DOIs
StatePublished - Dec 22 2006
EventDSN 2006: 2006 International Conference on Dependable Systems and Networks - Philadelphia, PA, United States
Duration: Jun 25 2006Jun 28 2006

Publication series

NameProceedings of the International Conference on Dependable Systems and Networks
Volume2006

Other

OtherDSN 2006: 2006 International Conference on Dependable Systems and Networks
CountryUnited States
CityPhiladelphia, PA
Period6/25/066/28/06

    Fingerprint

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this

Lam, V. V., Buchholz, P., & Sanders, W. H. (2006). A component-level path composition approach for efficient transient analysis of large CTMCs. In Proceedings - DSN 2006: 2006 International Conference on Dependable Systems and Networks (pp. 485-494). [1633537] (Proceedings of the International Conference on Dependable Systems and Networks; Vol. 2006). https://doi.org/10.1109/DSN.2006.1