Name
Abstract | ||
|---|---|---|
Network failures may lead to serious packet loss and degrade network performance. Therefore, loop-free alternates (LFA) have been widely deployed by many Internet service providers to cope with single network component failure in large Internet backbones. However, the efficiency of LFA has not been sufficiently studied. Some existing methods have extremely large computational overhead, and their computational complexity is linear with the average node degree of the network. The current methods consume a large amount of central processing unit resources, thereby aggravating the burden on the router. To improve the routing resilience without introducing significant extra overhead, this study proposes an incremental alternate computation with negative augmentation algorithm (IAC), which is based on incremental shortest path first algorithm. First, IAC turns the problem of quick implementation of LFA into efficiently calculating the minimum cost of all its neighbors to all other network nodes on the shortest path tree rooted at the computing node. Then, several theorems for calculating the cost are presented and their correctness is validated. Finally, we evaluate IAC through simulations with real-world and generated topologies. Compared with TBFH, DMPA, and DMPA-e, which are algorithms optimized for limited scenarios, IAC finds approximately 50% more available alternates, is more than three times faster, and provides node protection capabilities that TBFH, DMPA, and DMPA-e cannot provide. These advantages make IAC a good candidate for traditional telecommunication networks and emerging complex networks that require failure repair and load balancing in a highly dynamic environment. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1016/j.jnca.2019.102501 | Journal of Network and Computer Applications |
Keywords | Field | DocType |
Loop-free alternates,Fast reroute,Multipath routing,Network availability | Overhead (computing),Shortest path problem,Computer science,Load balancing (computing),Packet loss,Computer network,Node (networking),Network topology,Shortest-path tree,Distributed computing,Network performance | Journal |
Volume | ISSN | Citations |
151 | 1084-8045 | 0 |
PageRank | References | Authors |
0.34 | 0 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Haijun Geng | 1 | 4 | 3.44 |
| Han Zhang | 2 | 123 | 28.55 |
| Xingang Shi | 3 | 166 | 22.66 |
| Zhiliang Wang | 4 | 201 | 34.74 |
| Xia Yin | 5 | 320 | 44.72 |