Fast transient simulation of Markovian models of highly dependable systems

In this paper we investigate fast simulation techniques for the estimation of transient measures in Markovian models of highly dependable systems. For such models, standard simulation techniques are inefficient as system failure events are rare. Two importance sampling techniques, namely forcing and failure biasing, have been found to increase the efficiency in estimating such measures. However, experiments have shown that these techniques work well only for the case where the time horizon is 'small' and result in poor estimates otherwise. To gain a better understanding of this phenomenon we analyze the importance sampling heuristics for the case of estimating the expected interval unavailability. We show that for any fixed given time horizon the estimates using importance sampling have bounded relative error (i.e., the relative error of the simulation estimate remains bounded as failure rates tend to zero; this is contrasted to standard simulation in which the relative error tends to infinity). However, for time horizons that are large these techniques are shown to be inefficient. For this case we develop bounds on the measure and then instead of estimating the measure we estimate these bounds. We prove that these bounds can be very efficiently estimated and that for time horizons that are not 'small', the bounds approach the measure as failure rates tend to zero. © 1994.