Paper Info
Title
Dynamic Distributed Algorithm For Computing Multiple Next-Hops On A Tree
Abstract
High reliability is always pursued by network designers. Multipath routing can provide multiple paths for transmission and failover, and is considered to be effective in the improvement of the network reliability. However, existing multipath routing algorithms focus on how to find as many paths as possible, rather than their computation or communication overhead.We propose a dynamic distributed multipath algorithm (DMPA) to help a router in a link-state network find multiple next-hops for each destination. A router runs the algorithm locally and independently, where only one single shortest path tree (SPT) needs to be constructed, and no message other than the basic link states is disseminated. DMPA maintains the SPT and dynamically adjusts it in response to network state changes, so the sets of next-hops can be incrementally and efficiently updated. At the same time, DMPA guarantees loop-freeness of the induced forwarding path by a partial order of the routers underpinning it.We evaluate DMPA and compare it with some latest multipath algorithms, using a set of real, inferred and synthetic topologies. The results show that DMPA can provide good reliability and fast recovery for the network with very low overhead.
Year
DOI
Venue
2013
10.1109/ICNP.2013.6733581
2013 21ST IEEE INTERNATIONAL CONFERENCE ON NETWORK PROTOCOLS (ICNP)
Field
DocType
Volume
Multipath propagation,Failover,Multipath routing,Computer science,Computer network,Network topology,Distributed algorithm,Reliability (computer networking),Router,Shortest-path tree,Distributed computing
Conference
null
Issue
ISSN
Citations 
null
1092-1648
0
PageRank 
References 
Authors
0.34
11
4
Name
Order
Citations
PageRank
Haijun Geng143.44
Xingang Shi216622.66
Xia Yin332044.72
Zhiliang Wang420134.74