Max-Flow Protection Using Network Coding

In this paper we present a new way to enhance the survivability of the information flow between two communicating nodes S and T without compromising the maximum achievable S-T information rate. To do this, bottleneck links should only forward useful information, and not redundant data units. We introduce the idea of extra source or destination connectivity with respect to a certain S-T max-flow, and then we introduce two problems: namely, pre-cut protection and post-cut protection. Because of space limitations we only focus on the pre cut protection problem. Specifically, we show that the pre-cut protection problem is NP-hard, we propose a heuristic approach to solve it, and we compare the performance of this heuristic to an ILP. Simulations show that the performance of the heuristic is acceptable even on relatively large networks.