Computer Science – Networking and Internet Architecture
Scientific paper
2009-08-05
Computer Science
Networking and Internet Architecture
9 pages, submitted to INFOCOM 2010
Scientific paper
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 accomplished by using a subset of these paths to forward redundant data units or combinations (if network coding is allowed) 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. 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 study two problems: namely, pre-cut protection and post-cut protection. Although our objective in both problems is the same, where we aim to maximize the number of protected paths, our analysis shows that the nature of these two problems are very different, and that the pre-cut protection problem is much harder. Specifically, we prove the hardness of the pre-cut protection problem, formulate it as an integer linear program, and propose a heuristic approach to solve it. Simulations show that the performance of the heuristic is acceptable even on relatively large networks. In the post-cut problem we show that all the data units, forwarded by the min-cut edges not incident to T, can be post-cut-protected.
Al-Kofahi Osameh M.
Kamal Ahmed E.
No associations
LandOfFree
Max-Flow Protection using Network Coding does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Max-Flow Protection using Network Coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Max-Flow Protection using Network Coding will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-255252