Survivable Routing Meets Diversity Coding

Pasic, Alija and Tapolcai, János and Babarczi, Péter and Bérczi-Kovács, Erika and Király, Zoltán and Rónyai, Lajos (2015) Survivable Routing Meets Diversity Coding. In: IFIP Networking Conference, 2015 May 20-22, Toulouse, France.

[C15] Networking 2015.pdf - Published Version

Download (401kB) | Preview


Survivable routing methods have been thoroughly investigated in the past decades in transport networks. However, the proposed approaches suffered either from slow recovery time, poor bandwidth utilization, high computational or operational complexity, and could not really provide an alternative to the widely deployed single edge failure resilient dedicated 1 + 1 protection approach. Diversity coding is a candidate to overcome these difficulties with a relatively simple technique: dividing the connection data into two parts, and adding some redundancy at the source node. However, a missing link to make diversity coding a real alternative to 1+1 in transport networks is finding its minimum cost survivable routing, even in sparse topologies, where previous approaches may fail. In this paper we propose a polynomial-time algorithm with O(|V||E| log |Vw) complexity for this routing problem. On the other hand, we show that the same routing problem turns to be NP-hard as soon as we limit the forwarding capabilities of some nodes and the capacities of some links of the network.

Item Type: Conference or Workshop Item (Paper)
Subjects: Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
Depositing User: Dr Péter Babarczi
Date Deposited: 17 Sep 2015 18:06
Last Modified: 31 Dec 2017 00:15

Actions (login required)

Edit Item Edit Item