Computation of bounds for transient measures of large rewarded Markov models using regenerative randomization
In this paper we generalize a method (called regenerative randomization) for the transient solution of continuous time Markov models. The generalized method allows to compute two transient measures (the expected transient reward rate and the expected averaged reward rate) for rewarded continuous time Markov models with a structure covering bounding models which are useful when a complete, exact model has unmanageable size. The method has the same good properties as the well-known (standard) randomization method: numerical stability, well-controlled computation error, and ability to specify the computation error in advance, and, for large enough models and long enough times, is significantly faster than the standard randomization method. The method requires the selection of a regenerative state and its performance depends on that selection. For a class of models, class C?, including typical failure/repair models with exponential failure and repair time distributions and repair in every state with failed components, a natural selection for the regenerative state exists, and results are available assessing approximately the performance of the method for that natural selection in terms of visible model characteristics. Those results can be used to anticipate when the method can be expected to be significantly faster than standard randomization for models in that class. The potentially superior efficiency of the regenerative randomization method compared to standard randomization for models not in class C? is illustrated using a large performability model of a fault-tolerant multiprocessor system. Rewarded continuous time Markov models are widely used for performance, dependability and performability analysis of computer and telecommunication systems. Realistic modeling of such systems usually yields Markov models whose size exceeds the available memory resources. An approach to deal with the largeness problem is the use of bounding Markov models. However, even those bounding models can have very large state spaces, making important the development of efficient numerical solution techniques. Often, one is interested in transient characteristics of the system which require the transient analysis of the model. This paper generalizes a method, called regenerative randomization, for the transient analysis of Markov models, so that it can be used for the computation of bounds for the expected transient reward rate and the expected averaged reward rate transient measures with general reward rate structures including arbitrary non-negative reward rates associated with the states of the model. Examples of such measures are the unavailability of a fault-tolerant system at time t and the expected interval unavailability of a fault-tolerant system at time t. The method has the same good properties as the well-known standard randomization (also called uniformization) method: numerical stability, well-controlled computation error, and ability to specify the computation error in advance, and, for large models and long mission times, can be significantly faster than that method. Furthermore, for a class of models, class C?, including typical failure/repair models with exponential failure and repair time distributions and repair in every state with failed components, theoretical results are available assessing the performance of the method in terms of visible model characteristics. Those results can be used to anticipate when the generalized regenerative randomization method can be expected to be competitive for class C? models. The generalized regenerative randomization method allows a numerically stable, with well-controlled and specifiable-in-advance error, solution of some large rewarded continuous time Markov models in affordable CPU times.
randomization transient analysis continuous time markov chains rewarded models