Diverse Routing in Networks with Probabilistic Failures

12 years 10 months ago
Diverse Routing in Networks with Probabilistic Failures
—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 Non-Linear Program (INLP), and develop approximations and linear relaxations that can find nearly optimal solutions in most cases.
Hyang-Won Lee, Eytan Modiano
Added 24 May 2010
Updated 24 May 2010
Type Conference
Year 2009
Authors Hyang-Won Lee, Eytan Modiano
Comments (0)