Finding Failure-Disjoint Paths for Path Diversity Protection in Communication Networks

In the paper we consider a flow problem closely related to path diversity protection in communication networks. Given a weighted directed graph where some arcs are subject to failures while others are resilient, we aim at computing a shortest pair of failure-disjoint paths. If a resilient arc is use...

Full description

Saved in:
Bibliographic Details
Published in:IEEE communications letters 2010-08, Vol.14 (8), p.776-778
Main Authors: Zotkiewicz, Mateusz, Ben-Ameur, Walid, Pioro, Michal
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Communication networks
Computation
Computer Science
Contracts
Costs
directed graphs
Discrete Mathematics
diversity reception
Electrical Engineering, Electronic Engineering, Information Engineering
Elektroteknik och elektronik
Engineering and Technology
Exact sciences and technology
Failure
failure-disjoint paths
Graphs
network reliability
Networking and Internet Architecture
Operation, maintenance, reliability
Optimization methods
path diversity protection
polynomial-time algorithm
Polynomials
Protection
resilient arc
SONET
Synchronous digital hierarchy
Systems, networks and services of telecommunications
Teknik
Telecommunication network reliability
Telecommunication traffic
Telecommunications
Telecommunications and information theory
Transmission and modulation (techniques and equipments)
weighted directed graph
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:In the paper we consider a flow problem closely related to path diversity protection in communication networks. Given a weighted directed graph where some arcs are subject to failures while others are resilient, we aim at computing a shortest pair of failure-disjoint paths. If a resilient arc is used by both paths, its cost is counted only once. We present an original polynomial-time algorithm for solving the problem.
ISSN:1089-7798
1558-2558
DOI:10.1109/LCOMM.2010.08.100653