A hop-by-hop dynamic distributed multipath routing mechanism for link state network
A hop-by-hop dynamic distributed multipath routing mechanism for link state network
复制标题
链路状态网络逐跳动态分布式多路径路由机制
DOI：
10.1016/j.comcom.2017.12.008
复制
发表时间：
2018
影响因子：
6
通讯作者：
Xia Yin
中科院分区：
文献类型：
--
作者：
Haijun Geng;Xingang Shi;Zhiliang Wang;Xia Yin
高可靠性一直是网络设计者、运营商和用户追求的目标。多路径路由可以为传输和故障转移提供多条路径，被认为是提高网络可靠性的有效途径，但现有的多路径路由算法都是为了找到尽可能多的路径并保证无环路，其计算或通信开销往往被忽略。例如，路由器要么构建多个最短路径树，要么与每个目的地的邻居交换信息，当与大量邻居连接时，成本特别高。此外，这些算法通常执行从头开始重新计算每当网络状态的变化，导致进一步的资源scarcity.We提出了一种算法，DMPA（动态多路径算法），在链路状态网络中的路由器计算多个下一跳为每个目的地。该算法基于普通网络链路状态构建一棵最短路径树，并根据网络状态的变化动态调整最短路径树，从而有效地计算和增量更新下一跳节点集。同时，DMPA通过隐式地保持路由器的偏序来保证诱导路由路径的无环性，并通过引入跳数（一个依赖于拓扑结构的度量）对DMPA进行了进一步的扩展（DMPA-e），我们使用一些真实的和推断的ISP拓扑结构以及一组合成拓扑结构对所提出的算法进行了评估，并将它们与几种最新的多路径算法进行了比较。我们的研究结果表明，我们提出的算法可以提供良好的可靠性和快速恢复的网络非常低的开销。
High reliability is always pursued by network designers, operators and users. Multipath routing can provide multiple paths for transmission and failover, and is considered to be effective in the improvement of network reliability.Existing multipath routing algorithms are tailored to find as many paths as possible and to guarantee loop-freeness, with their computation or communication overhead often overlooked. For example, a router either constructs multiple shortest path trees, or exchanges information with its neighbors for every destination, witnessing a particularly high cost when connecting with a large number of neighbors. Moreover, these algorithms typically perform a recomputation from scratch whenever the network state changes, leading to further resource scarcity.We propose an algorithm, DMPA (dynamic multipath algorithm), for a router in a link-state network to compute multiple next-hops for each destination. The algorithm constructs one single shortest path tree based on ordinary network link states, and dynamically adjusts it in response to network state changes, so the sets of next-hops can be efficiently computed and incrementally updated. At the same time, DMPA guarantees loop-freeness of the induced routing path by implicitly maintaining a partial order of the routers underpinning it. And also, we present a further extension of DMPA (DMPA-e) by incorporating hop count, a topology dependent metric.We evaluate the proposed algorithms and compare them with several latest multipath algorithms, using some real and inferred ISP topologies, and also a set of synthetic topologies. Our results show that our proposed algorithms can provide good reliability and fast recovery for the network with very low overhead.
登录
查看更多内容
DOI：
10.1109/icnp.2015.44
发表时间：
2015-11
期刊：
2015 IEEE 23rd International Conference on Network Protocols (ICNP)
影响因子：
--
作者：
János Tapolcai;G. Rétvári;P. Babarczi;Erika R. Kovács;Panna Kristof;G. Enyedi
通讯作者：
János Tapolcai;G. Rétvári;P. Babarczi;Erika R. Kovács;Panna Kristof;G. Enyedi
DOI：
10.1109/tnet.2014.2369855
发表时间：
2015-08
期刊：
IEEE/ACM Transactions on Networking
影响因子：
--
作者：
S. Antonakopoulos;Yigal Bejerano;P. Koppol
通讯作者：
S. Antonakopoulos;Yigal Bejerano;P. Koppol
DOI：
10.1109/tnet.2011.2123916
发表时间：
2011-10
期刊：
IEEE/ACM Transactions on Networking
影响因子：
--
作者：
K. Kwong;Lixin Gao;Roch Guérin;Zhi-Li Zhang
通讯作者：
K. Kwong;Lixin Gao;Roch Guérin;Zhi-Li Zhang
DOI：
10.17487/rfc5286
发表时间：
2008-09
期刊：
RFC
影响因子：
--
作者：
Alia Atlas;A. Zinin
通讯作者：
Alia Atlas;A. Zinin
DOI：
10.1109/infcom.2004.1354492
发表时间：
2004-03
期刊：
IEEE INFOCOM 2004
影响因子：
--
作者：
Sanghwan Lee;Yinzhe Yu;Srihari Nelakuditi;Zhi-Li Zhang;Chen-Nee Chuah
通讯作者：
Sanghwan Lee;Yinzhe Yu;Srihari Nelakuditi;Zhi-Li Zhang;Chen-Nee Chuah