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 att...

Full description

Saved in:
Bibliographic Details
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
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1063-6692
1558-2566
DOI:10.1109/TNET.2010.2050490