4.5 Article

IP Fast Rerouting and Disjoint Multipath Routing With Three Edge-Independent Spanning Trees

Journal

IEEE-ACM TRANSACTIONS ON NETWORKING
Volume 24, Issue 3, Pages 1336-1349

Publisher

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TNET.2015.2440179

Keywords

Independent spanning trees; IP fast reroute; multilink failure recovery; multipath routing

Funding

  1. National Science Foundation [CNS-1117274]

Ask authors/readers for more resources

We develop approaches for disjoint multipath routing and fast recovery in IP networks that guarantee recovery from arbitrary two link failures. We achieve this by developing the first known algorithm to construct three edge-independent spanning trees, which has a running time complexity of O(V-2) The property of these trees is that the paths from a source to the destination on the trees are mutually link-disjoint. We illustrate how the three edge-independent trees rooted at a destination may be employed to achieve multipath routing and IP fast recovery. We discuss different ways of employing the trees. The routing of packets is based on the destination address and the input interface over which the packet was received. If the trees are employed exclusively for multipath routing, then no packet overhead is required. If the trees are employed for failure recovery, then the overhead bits will range from 0 to 2 bits depending on the flexibility sought in routing. We evaluate the performance of the trees in fast recovery by comparing the path lengths provided under single-and dual-link failures with an earlier approach based on tunneling. We also evaluate the performance of the trees when used for multipath routing and compare it to equal-cost multipaths (ECMP).

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.5
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available