Journal
IEEE-ACM TRANSACTIONS ON NETWORKING
Volume 24, Issue 3, Pages 1336-1349Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TNET.2015.2440179
Keywords
Independent spanning trees; IP fast reroute; multilink failure recovery; multipath routing
Categories
Funding
- 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
Recommended
No Data Available