2014/10/01 by Canale, Eduardo, Romero, Pablo, Rubino, Gerardo
#Combinatorics (math.CO) #Distributed #FOS: Computer and information sciences #FOS: Mathematics #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.1410.0707
In classical network reliability analysis, the system under study is a network with perfect nodes but imperfect link, that fail stochastically and independently. There, the goal is to find the probability that the resulting random graph is connected, called reliability. Although the exact reliability computation belongs to the class of NP-Hard problems, the literature offers three exact methods for exact reliability computation, to know, Sum of Disjoint Products (SDPs), Inclusion-Exclusion and Factorization. Inspired in delay-sensitive applications in telecommunications, Héctor Cancela and Louis Petingi defined in 2001 the diameter-constrained reliability, where terminals are required to be connected by d hops or less, being d a positive integer, called diameter. Factorization theory in classical network reliability is a mature area. However, an extension to the diameter-constrained context requires at least the recognition of irrelevant links, and an extension of deletion-contraction formula. In this paper, we fully characterize the determination of irrelevant links. Diameter-constrained reliability invariants are presented, which, together with the recognition of irrelevant links, represent the building-blocks for a new factorization theory. The paper is closed with a discussion of trends for future work.