Monte Carlo methods in diameter-constrained reliability

摘要

A classical requirement in the design of communication networks is that all entities must be connected. In a network where links may fail, the connectedness probability is called all-terminal reliability. The model is suitable for FTTH services, where link failures are unpredictable. In real scenarios, terminals must be connected by a limited number of hops. Therefore, we study the Diameter-Constrained Reliability (DCR). We are given a simple graph G = (V, E), a subset K is contained in V of terminals, a diameter d and independent failure probabilities q=1-p for each link. The goal is to find the probability R_(K,G)~d that all terminals remain connected by paths composed by d hops or less. The general DCR computation is NP-Hard, and the target probability is a polynomial in p. In this paper we study the DCR metric. It connects reliability with quality, and should be considered in the design of the physical layer in FTTH services together with connectivity requirements. We include a full discussion of the computational complexity of the DCR as a function of the number of terminals k = |K| and diameter d. Then, we find efficient DCR computation for Monma graphs, an outstanding family of topologies from robust network design. The computation suggests corollaries that enrich the subset of instances that accept efficient DCR computation. Inspired in its NP-Hardness, we introduce two approximation algorithms in order to find the DCR in general. The first one estimates the target polynomial counting special subgraphs. The second finds pointwise estimations of the polynomial using conditioned-Monte Carlo, and applies Newton's interpolation followed by a rounding-stage of the coefficients. The performance of both methods is discussed on the lights of Complete, Harary and Monma graphs. In order to study scalability, we analytically find the diameter-constrained reliability of a series-parallel graph with 44 nodes and 72 links. The results suggest that our counting implementation outperforms the interpolation technique, and is scalable as well. Open problems and trends for future work are included in the conclusions.