Nouvelles méthodes de réduction de la variance dans la simulation de type Monte Carlo d'événements rares

For systems that provide some kind of service while they are operational and stop providing it when they fail, it is of interest to determine parameters such as, for ex- ample, the probability of finding the system failed at any moment, the mean time between failures, or any measure that reflects the capacity of the system to provide service. The determination of these measures —known as dependability measures— is affected by a variety of factors, including the size of the system and the rarity of failures. This thesis studies some methods designed to determine these measures on large and highly reliable systems, i.e. systems formed by a large number of compo- nents, such that systems’ failures are rare events.Either directly or indirectly, part of the expressions for determining the measures of interest correspond to the probability that the system is in some state of failure. Some- how, this expressions evaluate the ratio —weighted by the probability distribution of the systems’ configurations— between the number of configurations in which the sys- tem fails and all possible configurations. If the system is large, the exact calculation of these probabilities, and consequently of the measures of interest, may be unfeasible. An alternative solution is to estimate these probabilities by simulation. One mecha- nism to make such estimation is Monte Carlo simulation, whose simplest version is crude or standard simulation. The problem is that if failures are rare, the number of it- erations required to estimate this probabilities by standard simulation, with acceptable accuracy, may be extremely large.In this thesis some existing methods to improve the standard simulation in the context of rare events are analyzed, some variance analyses are made and the methods are tested empirically over a variety of models. In all cases the improvement is achieved at the expense of reducing the variance of the estimator with respect to the standard estimator’s variance. Due to this variance reduction, the probability of the occurrence of rare events, with acceptable accuracy, can be achieved in a reasonable number of iterations. As a central part of this work, two new methods are proposed, one of them related to Splitting and the other one related to Conditional Monte Carlo.Splitting is a widely used method in performance and performability analysis, but scarcely applied for simulating highly reliable systems over static models (models with no temporal evolution). In its basic formulation Splitting keeps track of the tra- jectories of a stochastic process through its state space and it splits or multiplies the number of them at each threshold cross, for a given set of thresholds distributed be- tween the initial and the final state. One of the proposals of this thesis is an adaptation of Splitting to a static network reliability model. In the proposed method, a fictitious time stochastic process in which the network links keep changing their state is built, and Splitting is applied to this process. The method shows to be highly accurate and robust.Conditional Monte Carlo is a classical variance reduction technique, whose use is not widespread in the field of rare events. In its basic formulation Conditional Monte Carlo evaluates the probabilities of the events of interest, conditioning the indicator variables to not rare and easy to detect events. The problem is that part of this assess- ment includes the exact calculation of some probabilities in the model. One of the methods proposed in this thesis is an adaptation of Conditional Monte Carlo to the analysis of highly reliable Markovian systems. The proposal consists in estimating the probabilities whose exact value is needed, by means of a recursive application of Conditional Monte Carlo. Some features of this model are discussed and its efficiency is verified experimentally.Dans cette thèse, nous analysons deux approches différentes pour évaluer des métriques de sûreté de fonctionnement de réseaux de communications, l'une dans un cadre statique, l'autre dans un cadre dynamique. La première est une méthode de type Splitting pour le calcul de métriques de fiabilité définies donc dans un cadre statique, pour laquelle la thèse étudie la précision et la robustesse. La seconde appartient à la famille des méthodes de type Monte Carlo Conditionnel, utilisées pour analyser des modèles Markoviens dits hautement fiables. L'idée est d'appliquer recursivement la méthodologie Monte Carlo Conditionnel, en remplaçant des calculs partiels exacts qui font typiquement partie de cette approche par des estimations obtenues par simulation, de façon à ce que celles-ci se fassent dans un context d'événements non rares. L'efficacité de la technique est alors évaluée de façon expérimentale