Paper Info
Title
Minimum Cost Survivable Routing Algorithms for Generalized Diversity Coding
Abstract
Generalized diversity coding is a promising proactive recovery scheme against single edge failures for unicast connections in transport networks. At the source node, the user data is split into two parts, and their bitwise XOR is computed as a third redundancy sub-flow. In order to guarantee instantaneous failure recovery without costly node upgrades, the network must ensure that any two of the three sub-flows reach the destination node in case of a single edge failure only by allowing flow duplication or merging identical flows, and avoiding any coding operation in the core network. In this paper, we investigate the corresponding routing problem to calculate capacity-efficient routes for these sub-flows. We propose a polynomial-time algorithm for topologies without capacity constraints on the links and without capability limitations of the nodes. We show that with node limitations the presented algorithm (as well as a minimum cost disjoint path-pair) provides a 4/3-approximation for the routing problem. Furthermore, we formulate an integer linear program to provide a minimum cost solution with arbitrary constraints in general graphs and we propose a polynomial-time algorithm in directed acyclic graphs. Our simulation results suggest that with upgrading only a small set of core network nodes with flow duplication and merging capabilities most of the benefits of generalized diversity coding can be achieved.
Year
DOI
Venue
2020
10.1109/TNET.2019.2963574
IEEE/ACM Transactions on Networking
Keywords
DocType
Volume
Survivable routing,incremental deployment,diversity coding,instantaneous recovery,transport networks
Journal
28
Issue
ISSN
Citations 
1
1063-6692
0
PageRank 
References 
Authors
0.34
0
6
Name
Order
Citations
PageRank
Alija Pasic1174.18
Péter Babarczi29213.47
János Tapolcai336441.42
Erika R. Bérczi-Kovács4113.94
Zoltán Király513117.24
Lajos Rónyai639752.05