2017/09/10 by Jianan Zhang, Zhang, Jianan, Eytan Modiano +1 · 3 citations
Computer Science · Engineering · Mathematics · Physics and Astronomy · #Combinatorics #Complex Network Analysis Techniques #Complex network #Computer network #Computer science #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #Discrete mathematics #Disjoint sets #Distributed computing #Distributed systems and fault tolerance #Engineering #FOS: Computer and information sciences #Infrastructure Resilience and Vulnerability Analysis #Interdependence #Interdependent networks #Mathematics #Networking and Internet Architecture (cs.NI) #Node (physics) #Path (computing) #Routing (electronic design automation) #Topology (electrical circuits) #cs.DM #cs.DS #cs.NI
paper · pdf · doi:10.48550/arxiv.1709.03033
published in arXiv (Cornell University) (Cornell University) · Preliminary version was presented at INFOCOM 2017
openalex publication_date 2017/09/10 · arxiv created 2021/11/26 · arxiv updated 2021/11/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
We consider a model of two interdependent networks, where every node in one network depends on one or more supply nodes in the other network and a node fails if it loses all of its supply nodes. We develop algorithms to compute the failure probability of a path, and obtain the most reliable path between a pair of nodes in a network, under the condition that each supply node fails independently with a given probability. Our work generalizes the classical shared risk group model, by considering multiple risks associated with a node and letting a node fail if all the risks occur. Moreover, we study the diverse routing problem by considering two paths between a pair of nodes. We define two paths to be d-failure resilient if at least one path survives after removing d or fewer supply nodes, which generalizes the concept of disjoint paths in a single network, and risk-disjoint paths in a classical shared risk group model. We compute the probability that both paths fail, and develop algorithms to compute the most reliable pair of paths.