AESOP home


Exact Aggregation Strategies for Semi-Markov Performance Models

Jeremy T. Bradley, Nicholas J. Dingle, William J. Knottenbelt

Conference or Workshop Paper
SPECTS 2003, International Symposium on Performance Evaluation of Computer and Telecommunication Systems, Montreal, Canada, July 20-24 2003
July, 2003

Semi-Markov modelling paradigms are more expressive than their Markovian counterparts but are equally vulnerable to the state space explosion problem. This paper addresses this issue by presenting an exact state-by-state aggregation algorithm for semi-Markov models. Empirical evidence shows that the computational complexity of our method depends critically on the order in which the states are aggregated. We investigate different state-ordering strategies and find one that aggregates a large proportion (circa 75%) of our example state spaces at minimal cost. This leaves a significantly smaller model which can then be analysed for performance-related quantities such as passage-time quantiles. We demonstrate our technique on several examples, including a 541,280 state model which is reduced to 173,101 states.

PDF of full publication (678.4 kilobytes)
(need help viewing PDF files?)
GZipped Postscript of full publication (331.8 kilobytes)
(need help viewing GZipped Postscript files?)

Information from