Network reliability determination, is an NP-hard problem. For instance, in telecommunications, it is desired to evaluate the probability that a selected group of nodes (e.g. just one pair) communicate or not, or an a electric power systems, where we need to estimate the risk that electricity is not delivered to certain nodes, or in transportation systems, where damaged routes can be determined. In all these cases, a set of disconnected nodes can lead to critical financials security consequences. A precise estimation of the reliability is, therefore, needed. Modern communication networks are characterized by their large size, so the estimation trough Monte Carlo simulation process is often the favorable choice. The standard form of this algorithm samples N copies of the graph (representing the network) independently, where the unreliability is estimated from the proportion of N copies for which the selected nodes are not connected. In these networks, the probabilities of failure of connections are small and therefore the network failure becomes rare. This poses major challenges to estimate the network reliability. In this thesis we present different techniques based on importance sampling (IS) for reliability network estimation, which consist in doing a certain changes in the sampling probability arcs. With this technique, the original sampling probabilities arcs are replaced by new probabilities, requiring to multiply the old estimator with the likelihood ratio to remain unbiased. We are particularly interested in the study and determination of reliability of highly reliable networks represented by static graphs. In this case the unreliability is very small, in some case it is around 10−10, which make the standard Monte Carlo approach useless, because in order to estimate this probability we need a sample size larger than ten billion. For a good estimation of system reliability with minimum cost, we have studied, analyzed and developed the following concepts : - First we developed a method based on(IS). The sampling process of all graph arcs with the new probability is represented by a Markov chain, where at each step we determine the link state by the new probability determined by the states of all links previously sampled. Values of these probabilities are approximated by the minimal cut have largest probability of unreliability. Proves of the good properties of the estimator based on IS are obtained. - A second development, consists in applying techniques of series parallel reductions at each stage of sampling IS in order to reduce the variance and the time simulation. - The last point is to combine the unreliability approximation based on minimal cut which underestimates the unreliability with another approximation, an overestimation based on minimal path, for better approximate zero variance estimator. Optimization algorithms are used to find the optimal adjustment factor the two approximations.
