多路径路由优化技术研究
|
摘要
现在的互联网络应用大多是使用单路由协议,数据采用单路径方式进行传递,由于数据沿着一条路径传输,路由开销和网络延迟较大,在负载较大的时候容易引起拥塞。多路径路由是指通过一定的约束规则,在网络中找出源节点到目的节点的多条路径,报文遵循一定的策略在网内路由。多路径路由比单路径路由协议具有更优的性能,是路由技术的研究热点之一。目前学术界已提出了多种多路径路由协议,针对时延、安全、负载均衡均有所改善,但尚缺乏一种多路径路由协议能够满足在大规模网络中可靠性和可扩展性的需求。
本文分析了现阶段的多种多路径路由技术,特别是对其中的源路由和中间路级由技术的优缺点进行了详细的分析,结合两者的优点提出了一种改进的多路径路由技术,并通过分析指出,改进的多路径路由技术的性能依赖于中间路由节点的设置。文章在已知网络拓扑和未知网络拓扑这两种应用场景中,提出了多种可行的设置中间路由节点的算法。
在已知网络拓扑的情况下,本文提出了基于遍历和基于综合评分的设置中间路由节点算法。基于遍历设置中间路由节点算法实现了遍历求解组合优化,从简单到复杂提出并实现了三个算法,包括了简单的遍历、引入模拟退火的遍历和改进求解逻辑的遍历算法,其中改进求解逻辑的遍历算法将组合优化问题转换成对单个节点的求解,能有效地提高求解效率。基于综合评分设置路由节点算法借鉴了信息搜索的思想,提出了节点对分离路径指标贡献度评估的模型,中间路由节点对分离路径指标的贡献度可以由分离路径权值和度权值来决定。仿真结果证明基于综合评分算法有良好的效率和性能。
在未知网络拓扑的情况下,结合中间路由算法的特点,提出了一个基于拓扑关键点求解中间路由节点的算法,记为MRABTN。对拓扑关键点进行分布式的检测,然后对检测到的拓扑关键点进行避免能够快速地找到接近最优的中间路由节点,仿真结果说明,引入了分布式求解的基于拓扑关键点算法有良好的效率和性能。
Currently, Internet routing protocol is single path routing, data transmits along a single path, this will bring large routing overhead and the network delay, and also will cost congestion easily. Multi-path routing is a protocol that finds paths through a certain constraint rules, and transmits data through multi paths. Multi-path routing has better performance over single path routing, now is a research focus. Presently, there are a variety of multi-path routing protocols proposed brought out to meet the security, load balancing improvement requirement. But it lacks a multi-path protocol to meet the reliability and scalability needs in large-scale network.
This paper analyzes a variety of multi-path routing protocols, which has a special detail analysis on source routing and intermediate routing. We point out the advantages and disadvantages of source routing and intermediate routing, and then give a new multi-path routing which combines the advantages of source routing and intermediate routing. And we point out that the new multi-path routing performance depends on the intermediate nodes set. This paper bases on two applications scenario: known network topology and unknown network topology to put forward some algorithms those set the intermediate nodes property.
In the case of known network topology scenario, we propose traversal and integrated scoring intermediate routing nodes setting algorithm. The traversal algorithms have three algorithms, which are simple traversal algorithm, traversal algorithm that import simulated annealing and improve traversal algorithm. The improve traversal algorithm translates the combinatorial optimization problem into single nodes solution, this can effectively improve the solve efficiency. Integrated scoring algorithm is based on the mind of information searching, give a model that can score nodes. The simulation results show integrated scoring algorithm has good performance.
In the case of unknown network topology scenario, we propose a distributed detect intermediate nodes algorithm which we mark as MRABTN. We discover the existing of topologically-critical nodes which we call TN, give a simple, effective, distributed method to detect the TN and avoid them, then find the most valuable intermediate nodes. Simulation results show that MRABTN has good performance.
At last, we conclude the paper and point out the future improvement direction.
本文分析了现阶段的多种多路径路由技术,特别是对其中的源路由和中间路级由技术的优缺点进行了详细的分析,结合两者的优点提出了一种改进的多路径路由技术,并通过分析指出,改进的多路径路由技术的性能依赖于中间路由节点的设置。文章在已知网络拓扑和未知网络拓扑这两种应用场景中,提出了多种可行的设置中间路由节点的算法。
在已知网络拓扑的情况下,本文提出了基于遍历和基于综合评分的设置中间路由节点算法。基于遍历设置中间路由节点算法实现了遍历求解组合优化,从简单到复杂提出并实现了三个算法,包括了简单的遍历、引入模拟退火的遍历和改进求解逻辑的遍历算法,其中改进求解逻辑的遍历算法将组合优化问题转换成对单个节点的求解,能有效地提高求解效率。基于综合评分设置路由节点算法借鉴了信息搜索的思想,提出了节点对分离路径指标贡献度评估的模型,中间路由节点对分离路径指标的贡献度可以由分离路径权值和度权值来决定。仿真结果证明基于综合评分算法有良好的效率和性能。
在未知网络拓扑的情况下,结合中间路由算法的特点,提出了一个基于拓扑关键点求解中间路由节点的算法,记为MRABTN。对拓扑关键点进行分布式的检测,然后对检测到的拓扑关键点进行避免能够快速地找到接近最优的中间路由节点,仿真结果说明,引入了分布式求解的基于拓扑关键点算法有良好的效率和性能。
Currently, Internet routing protocol is single path routing, data transmits along a single path, this will bring large routing overhead and the network delay, and also will cost congestion easily. Multi-path routing is a protocol that finds paths through a certain constraint rules, and transmits data through multi paths. Multi-path routing has better performance over single path routing, now is a research focus. Presently, there are a variety of multi-path routing protocols proposed brought out to meet the security, load balancing improvement requirement. But it lacks a multi-path protocol to meet the reliability and scalability needs in large-scale network.
This paper analyzes a variety of multi-path routing protocols, which has a special detail analysis on source routing and intermediate routing. We point out the advantages and disadvantages of source routing and intermediate routing, and then give a new multi-path routing which combines the advantages of source routing and intermediate routing. And we point out that the new multi-path routing performance depends on the intermediate nodes set. This paper bases on two applications scenario: known network topology and unknown network topology to put forward some algorithms those set the intermediate nodes property.
In the case of known network topology scenario, we propose traversal and integrated scoring intermediate routing nodes setting algorithm. The traversal algorithms have three algorithms, which are simple traversal algorithm, traversal algorithm that import simulated annealing and improve traversal algorithm. The improve traversal algorithm translates the combinatorial optimization problem into single nodes solution, this can effectively improve the solve efficiency. Integrated scoring algorithm is based on the mind of information searching, give a model that can score nodes. The simulation results show integrated scoring algorithm has good performance.
In the case of unknown network topology scenario, we propose a distributed detect intermediate nodes algorithm which we mark as MRABTN. We discover the existing of topologically-critical nodes which we call TN, give a simple, effective, distributed method to detect the TN and avoid them, then find the most valuable intermediate nodes. Simulation results show that MRABTN has good performance.
At last, we conclude the paper and point out the future improvement direction.
引文
[1]徐恪,吴建平,徐明伟.高等计算机网络[M].北京:机械工业出版社,2005: 176-213
[2]朱伟. Adhoc网络独立多路径路由的研究与改进[D].山东:山东大学,2006:22-25
[3]安辉耀.移动自主网中多路径路由技术研究[D].安徽:国防科技大学,2005:9-11
[4] N. F. Maxemchuk. Dispersity Routing: Past and Present [J]. IEEE2007
[5] M.Ashibani, D.Mashao,Nleya. Performance Analysis of Burst Level Bandwidth Allocation using Multipath Routing Reservation[C]. EUROCON’2001, Trends in Communications, International Conference on. Vol. 1: 70-76
[6] N.Taft-Plotkin, B.Bellur, and R.Ogier. Quality-of-Service Routing Using Maximally Disjoint Paths[C]. Proceeding of IEEE IWQoS’99: 119-128
[7] Yu-Tse Chen,P.David Fisher. An Efficient Two-Layer Irregular-Channel Router[C]. Circuits and Systems, Proceeding of the 33rd Midwest Symposium on 1991: 167-171
[8] Patrick W.Dowd, Kalyani Bogineni,Khaled A.Aly, James A.Perreault. Hierarchical Scalable Photonic Architectures for High-Performance Processor Interconnection[J]. IEEE Transactions on Computers. Vol. 42, No.9, September 1993: 1105-p1121
[9] Te-Chou Su, Jia-Shung Wang. Buffered Multicast Routing for Video-on-Demand Systems[C]. Communications, 1999. ICC’99. Vol2: 1000-1005
[10] Fengyun Cao, Jaswinder Pal Singh. Efficient Event Routing in Content-based Publish-Subscribe Service Networks. INFOCOM 2004. Vol2: 929-940
[11] Carl A.Sunshine. Soure Routing in Computer Networks[J]. IEEE 1990. p29-p34
[12]周逊,马弘舸,卢宇.基于源路由的多路径路由协议[J].西南交通大学学报, Vol41 No.2: 550-555.
[13] N. F. Maxemchuk. Dispersity Routing[J]. IEEE1993.
[14] Pierre Francois, Olivier Bonaventure. An evaluation of IP-based Fast RerouteTechniques[C]. CoNext’05, October 24-27, 2005, Toulouse, France: 244-p245
[15] Wen Xu, Jennifer Rexford. MIRO: Multi-path Interdomain Routing[C]. SIGCOMM’06, September 11-15, 2006, Pisa, Italy: 171-183
[16] Xiaowei Yang. NIRA: A New Internet Routing Architecture[C]. ACM SIGCOMM 2003 Workshops August 25&27, 2003, Karlsruhe, Germany: 301-313
[17] Dapeng Zhu, Mark Gritter, David R. Cheriton. Feedback Based Routing[C]. ACM SIGCOMM Computer Communication Review, Volume 33, Number 1: January 2003: 71-77
[18]黄松,许勇,张凌.基于多路径路由机制的网络生存性分析[J].中国科学E辑:信息科学,2008年第38卷第10期:1774-1782
[19] Ying-Hong Wang, Hung-Zu lin, Shu-Min Chang. Interference on multipath QoS routing for ad hoc wireless network [C].Distributed Computing Systems Workshops, 2004. Proceedings. 24th International Conference on. USA: IEEE, 2004: 104-109
[20] Jiayue He, Jennifer Rexford. Towards Internet-wide Multipath Routing[J]. IEEE Network, 2008, Volume 22: 16-21
[21] Jong-Moon Chung, Sunttha Panguluru. Multiple LSP Routing Network Security for MPLS Networking[A]. MWSCAS-2002[C]. 2002, 2:605-608
[22] Lee Kyeongja. Comparison of multipath algorithms for load balancing in a MPLS network [A]. ICOIN 2005 [C]. Berlin Heidelberg: Springer-Verlag, 2005: 463-470
[23] Song Jeonghwa. Dynamic load distribution in MPLS networks [A]. ICOIN 2003 [C]. Berlin Heidelberg: Springer-Verlag, 2003: 989-999
[24]王娜,马海龙,程东年,汪斌强. Hidra:一个分级域间路由架构[J].计算机学报,2009年第32卷第3期:377-390
[25] David B.Johnson, David A. Maltz, Josh Broch. DSR: The Dynamic Source Routing Protocol for Multi-Hop Wireless Ad hoc Network. in Ad Hoc Networking. Addison-Wesley, 2001. Chapter 5: 139-172,
[26]王正元.基于状态转移的组合优化方法研究[D].安徽:国防科技大学. 2004:10-20
[27]马少平,朱小燕.人工智能[M].北京:清华大学出版社. 2004:284-300
[28] Brin S, Page L. The Anatomy of a Large-scale Hypertextual Web Search Engine [J]. Computer Networks, 1998, 30: 107-117.
[29] Kleinberg J M. Authoritative Sources in a Hyperlinked Environment[J]. Journal of the ACM, 1999, 46(5):
[30]李振华,陈贵海,邱彤庆.分点:无结构对等网络的拓扑关键点[J]. Journal of Software, Vol.19, No.9, September 2008 : 2376-2388
[31] Microsoft . .Net Framework技术[S]. http://msdn.microsoft.com/zh-cn/netframework / default.aspx
[32] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction To Algorithms (Second Edition)[M]. The MIT Press. 2004: 366-370
[2]朱伟. Adhoc网络独立多路径路由的研究与改进[D].山东:山东大学,2006:22-25
[3]安辉耀.移动自主网中多路径路由技术研究[D].安徽:国防科技大学,2005:9-11
[4] N. F. Maxemchuk. Dispersity Routing: Past and Present [J]. IEEE2007
[5] M.Ashibani, D.Mashao,Nleya. Performance Analysis of Burst Level Bandwidth Allocation using Multipath Routing Reservation[C]. EUROCON’2001, Trends in Communications, International Conference on. Vol. 1: 70-76
[6] N.Taft-Plotkin, B.Bellur, and R.Ogier. Quality-of-Service Routing Using Maximally Disjoint Paths[C]. Proceeding of IEEE IWQoS’99: 119-128
[7] Yu-Tse Chen,P.David Fisher. An Efficient Two-Layer Irregular-Channel Router[C]. Circuits and Systems, Proceeding of the 33rd Midwest Symposium on 1991: 167-171
[8] Patrick W.Dowd, Kalyani Bogineni,Khaled A.Aly, James A.Perreault. Hierarchical Scalable Photonic Architectures for High-Performance Processor Interconnection[J]. IEEE Transactions on Computers. Vol. 42, No.9, September 1993: 1105-p1121
[9] Te-Chou Su, Jia-Shung Wang. Buffered Multicast Routing for Video-on-Demand Systems[C]. Communications, 1999. ICC’99. Vol2: 1000-1005
[10] Fengyun Cao, Jaswinder Pal Singh. Efficient Event Routing in Content-based Publish-Subscribe Service Networks. INFOCOM 2004. Vol2: 929-940
[11] Carl A.Sunshine. Soure Routing in Computer Networks[J]. IEEE 1990. p29-p34
[12]周逊,马弘舸,卢宇.基于源路由的多路径路由协议[J].西南交通大学学报, Vol41 No.2: 550-555.
[13] N. F. Maxemchuk. Dispersity Routing[J]. IEEE1993.
[14] Pierre Francois, Olivier Bonaventure. An evaluation of IP-based Fast RerouteTechniques[C]. CoNext’05, October 24-27, 2005, Toulouse, France: 244-p245
[15] Wen Xu, Jennifer Rexford. MIRO: Multi-path Interdomain Routing[C]. SIGCOMM’06, September 11-15, 2006, Pisa, Italy: 171-183
[16] Xiaowei Yang. NIRA: A New Internet Routing Architecture[C]. ACM SIGCOMM 2003 Workshops August 25&27, 2003, Karlsruhe, Germany: 301-313
[17] Dapeng Zhu, Mark Gritter, David R. Cheriton. Feedback Based Routing[C]. ACM SIGCOMM Computer Communication Review, Volume 33, Number 1: January 2003: 71-77
[18]黄松,许勇,张凌.基于多路径路由机制的网络生存性分析[J].中国科学E辑:信息科学,2008年第38卷第10期:1774-1782
[19] Ying-Hong Wang, Hung-Zu lin, Shu-Min Chang. Interference on multipath QoS routing for ad hoc wireless network [C].Distributed Computing Systems Workshops, 2004. Proceedings. 24th International Conference on. USA: IEEE, 2004: 104-109
[20] Jiayue He, Jennifer Rexford. Towards Internet-wide Multipath Routing[J]. IEEE Network, 2008, Volume 22: 16-21
[21] Jong-Moon Chung, Sunttha Panguluru. Multiple LSP Routing Network Security for MPLS Networking[A]. MWSCAS-2002[C]. 2002, 2:605-608
[22] Lee Kyeongja. Comparison of multipath algorithms for load balancing in a MPLS network [A]. ICOIN 2005 [C]. Berlin Heidelberg: Springer-Verlag, 2005: 463-470
[23] Song Jeonghwa. Dynamic load distribution in MPLS networks [A]. ICOIN 2003 [C]. Berlin Heidelberg: Springer-Verlag, 2003: 989-999
[24]王娜,马海龙,程东年,汪斌强. Hidra:一个分级域间路由架构[J].计算机学报,2009年第32卷第3期:377-390
[25] David B.Johnson, David A. Maltz, Josh Broch. DSR: The Dynamic Source Routing Protocol for Multi-Hop Wireless Ad hoc Network. in Ad Hoc Networking. Addison-Wesley, 2001. Chapter 5: 139-172,
[26]王正元.基于状态转移的组合优化方法研究[D].安徽:国防科技大学. 2004:10-20
[27]马少平,朱小燕.人工智能[M].北京:清华大学出版社. 2004:284-300
[28] Brin S, Page L. The Anatomy of a Large-scale Hypertextual Web Search Engine [J]. Computer Networks, 1998, 30: 107-117.
[29] Kleinberg J M. Authoritative Sources in a Hyperlinked Environment[J]. Journal of the ACM, 1999, 46(5):
[30]李振华,陈贵海,邱彤庆.分点:无结构对等网络的拓扑关键点[J]. Journal of Software, Vol.19, No.9, September 2008 : 2376-2388
[31] Microsoft . .Net Framework技术[S]. http://msdn.microsoft.com/zh-cn/netframework / default.aspx
[32] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction To Algorithms (Second Edition)[M]. The MIT Press. 2004: 366-370