Diverse Routing in Networks With Probabilistic Failures

• Published in: IEEE/ACM transactions on networking 2010-12, Vol.18 (6), p.1895-1907
• Main Authors: Hyang-Won Lee, Modiano, Eytan, Kayi Lee
• Format: Article
• Language: English
• Subjects: Algorithms; Communication networks; Computer networks; Correlated failures; Correlation; disjoint paths; Failure; Government; Linear approximation; Links; Networks; Optical fiber cables; Optical fiber communication; Optical fiber networks; path protection; Probabilistic methods; probabilistic shared risk link group (SRLG); Probability theory; Protection; random link failures; Routing; Routing (telecommunications); Telecommunication network reliability; Telecommunication traffic
• ISSN: 1063-6692; 1558-2566
• DOI: 10.1109/TNET.2010.2050490

We develop diverse routing schemes for dealing with multiple, possibly correlated, failures. While disjoint path protection can effectively deal with isolated single link failures, recovering from multiple failures is not guaranteed. In particular, events such as natural disasters or intentional attacks can lead to multiple correlated failures, for which recovery mechanisms are not well understood. We take a probabilistic view of network failures where multiple failure events can occur simultaneously, and develop algorithms for finding diverse routes with minimum joint failure probability. Moreover, we develop a novel Probabilistic Shared Risk Link Group (PSRLG) framework for modeling correlated failures. In this context, we formulate the problem of finding two paths with minimum joint failure probability as an integer nonlinear program (INLP) and develop approximations and linear relaxations that can find nearly optimal solutions in most cases.