Diameter-constrained reliability : theory and applications

Abstract

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 V of terminals, a diameter d and independent failure probabilities q = 1 − p for each link. The goal is to find the probability Rd K,G 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 chapter 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. Given its NP-Hardness, several Monte Carlo-based algorithms algorithms are designed in order to find the DCR in general, inspired in two approaches: counting and interpolation. The results suggest that counting techniques outperform interpolation, and show scalability properties as well. Open problems and trends for future work are included in the conclusions.