In any communication network, the maximum number of link-disjoint paths between any pair of communicating nodes, S and T, is limited by the S-T minimum link-cut. Multipath routing protocols have been proposed in the literature to make use of these S-T paths in enhancing the survivability of the S-T information flow. This is usually done by using a subset of these paths to forward redundant data from S to T. Therefore, this enhancement in survivability reduces the useful S-T information rate. In this paper we present a new way to enhance the survivability of the S-T information flow without compromising the maximum achievable S-T information rate, which is especially important in wireless networks where wireless resources are limited. To do this, bottleneck links (in the min-cut) 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. Protection is implemented using the technique of network coding, and using coefficients from the binary field. 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 results from an optimal ILP. Simulations show that the performance of the heuristic is acceptable even on relatively large networks.
['Osameh M. Al-Kofahi', 'Ahmed E. Kamal']
Max-Flow Protection Using Network Coding