Survivable routing meets diversity coding

摘要

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 |V|) 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.