期刊
IEEE-ACM TRANSACTIONS ON NETWORKING
卷 24, 期 3, 页码 1336-1349出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TNET.2015.2440179
关键词
Independent spanning trees; IP fast reroute; multilink failure recovery; multipath routing
类别
资金
- National Science Foundation [CNS-1117274]
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).
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据