多下一跳路由算法研究
|
摘要
当前因特网域内路由广泛采用的单下一跳路由算法,易造成传输路径集中,网络资源浪费,并且故障恢复速度较慢。多下一跳路由技术实现了多下一跳并行转发,能充分利用网络资源,有效减少拥塞,提升网络性能。
本论文依托国家863探索导向类课题“一种基于节点势能导向的多路由产生机制”,在不改变现有网络工作模式的前提下,提出了一种基于最短路径搜索序列定势的多下一跳路由算法。
论文主要内容如下:
1.分析了已有的两类典型多下一跳路由算法——SP(Shortest Path)机制和st编号机制。SP根据最优距离确定可行下一跳,未能充分挖掘网络冗余资源;st源于数学中的图论,依据网络拓扑规划路由,未考虑路由属性,所得路由性能不佳。通过对两类算法的分析,为后文的算法设计提供了研究思路。
2.结合课题中的势能思想,借鉴两类算法提出了基于最短路径搜索序列定势的多下一跳路由算法——D-SSPA(Dijkstra-Search Sequence Potential Algorithm)。由目的节点执行Dijkstra搜索算法完成对网络中所有节点的定势,邻居节点间依据其序号值即势能赋值大小,按照从高势能节点流向低势能节点的约定规范链路传输方向,从而完成整个网络的路由规划。仿真结果表明,该算法充分挖掘了网络的冗余资源,生成的路由图优于SP和st,节点和链路负载均衡度均有提高,而且能获得更高的网络吞吐量和更低的丢包率。
3.提出一种针对多下一跳路由机制下单链路故障的分级评估响应算法——HERA (Hierarchical Evaluation Response Algorithm)。该算法对故障进行分级评估,将故障处理分为本节点收敛、上游节点收敛和全网收敛,从而将故障的影响范围尽可能控制在局部。通过对不同连接度的网络进行仿真,结果表明,相比全网收敛机制,HERA缩短了收敛时间,有效增强了网络的稳定性。在MCI网络的单链路故障下,将HERA加载于D-SSPA、SP和st,得到D-SSPA的收敛时间平均比SP缩短了21.7%,比st缩短了9.5%。
The single next hop routing algorithm which widely used today makes the transmission paths tend to centralize, leading to a waste of network resources and slow recovery from failures. Multi-Next Hop Routing technology makes each node forward packets to multiple neighbor nodes and implements parallel transmission. The mechanism can make better use of network resources, reduce transmission congestion effectively, and improve network performance. Combined with the national 863 objective orientation project "a multi-next hop routing mechanism based on node potential orientation", this dissertation proposes a Multi-Next Hop Routing Algorithm based on search sequence numbering by the prerequisite not to alter the current network work mode.
The main work of this dissertation is outlined as follows:
1.Two typical multi-next hop routing algorithms——SP (Shortest Path) and st numbering mechanism are analyzed. SP determines feasible next hops according to the optimal distance, which can not fully exploit the network resources; st routing may be of poor performance, because st is based on graph theory simply and network property is failed to take into account when planning the routing. The analysis of both algorithms provides research approach for algorithm design.
2.Combined with potential idea, multi-next hop routing algorithm based on shortest path search sequence potential——D-SSPA (Dijkstra-Search Sequence Potential Algorithm) is proposed in this thesis. The destination nodes execute search algorithm to complete sequencing of all nodes, link transmission direction of neighbor nodes according to the size of their assignments. The algorithm fully exploits the network resources, the routing graph generated by D-SSPA is better than SP and st, and the simulation analysis indicates that, load balance of nodes and links is improved, network throughput and packet loss rate performance are also superior to the both.
3.A Hierarchical Evaluation Response Algorithm(HERA)which deals with the single link failure based on multi-next hop routing mechanism is presented. Under this mechanism, failures are divided into three levels: convergence of this node, convergence of the upstream neighbors and global convergence, which makes the failure influence locally as far as possible. Simulation results show that, in networks with different connectivity, HERA can trigger global convergence as little as possible, failure recovery time is shortened, and the stability of the network is enhanced effectively. Under a single link failure, convergence time of D-SSPA decreased 21.7% than the SP, and decreased 9.5% than st.
本论文依托国家863探索导向类课题“一种基于节点势能导向的多路由产生机制”,在不改变现有网络工作模式的前提下,提出了一种基于最短路径搜索序列定势的多下一跳路由算法。
论文主要内容如下:
1.分析了已有的两类典型多下一跳路由算法——SP(Shortest Path)机制和st编号机制。SP根据最优距离确定可行下一跳,未能充分挖掘网络冗余资源;st源于数学中的图论,依据网络拓扑规划路由,未考虑路由属性,所得路由性能不佳。通过对两类算法的分析,为后文的算法设计提供了研究思路。
2.结合课题中的势能思想,借鉴两类算法提出了基于最短路径搜索序列定势的多下一跳路由算法——D-SSPA(Dijkstra-Search Sequence Potential Algorithm)。由目的节点执行Dijkstra搜索算法完成对网络中所有节点的定势,邻居节点间依据其序号值即势能赋值大小,按照从高势能节点流向低势能节点的约定规范链路传输方向,从而完成整个网络的路由规划。仿真结果表明,该算法充分挖掘了网络的冗余资源,生成的路由图优于SP和st,节点和链路负载均衡度均有提高,而且能获得更高的网络吞吐量和更低的丢包率。
3.提出一种针对多下一跳路由机制下单链路故障的分级评估响应算法——HERA (Hierarchical Evaluation Response Algorithm)。该算法对故障进行分级评估,将故障处理分为本节点收敛、上游节点收敛和全网收敛,从而将故障的影响范围尽可能控制在局部。通过对不同连接度的网络进行仿真,结果表明,相比全网收敛机制,HERA缩短了收敛时间,有效增强了网络的稳定性。在MCI网络的单链路故障下,将HERA加载于D-SSPA、SP和st,得到D-SSPA的收敛时间平均比SP缩短了21.7%,比st缩短了9.5%。
The single next hop routing algorithm which widely used today makes the transmission paths tend to centralize, leading to a waste of network resources and slow recovery from failures. Multi-Next Hop Routing technology makes each node forward packets to multiple neighbor nodes and implements parallel transmission. The mechanism can make better use of network resources, reduce transmission congestion effectively, and improve network performance. Combined with the national 863 objective orientation project "a multi-next hop routing mechanism based on node potential orientation", this dissertation proposes a Multi-Next Hop Routing Algorithm based on search sequence numbering by the prerequisite not to alter the current network work mode.
The main work of this dissertation is outlined as follows:
1.Two typical multi-next hop routing algorithms——SP (Shortest Path) and st numbering mechanism are analyzed. SP determines feasible next hops according to the optimal distance, which can not fully exploit the network resources; st routing may be of poor performance, because st is based on graph theory simply and network property is failed to take into account when planning the routing. The analysis of both algorithms provides research approach for algorithm design.
2.Combined with potential idea, multi-next hop routing algorithm based on shortest path search sequence potential——D-SSPA (Dijkstra-Search Sequence Potential Algorithm) is proposed in this thesis. The destination nodes execute search algorithm to complete sequencing of all nodes, link transmission direction of neighbor nodes according to the size of their assignments. The algorithm fully exploits the network resources, the routing graph generated by D-SSPA is better than SP and st, and the simulation analysis indicates that, load balance of nodes and links is improved, network throughput and packet loss rate performance are also superior to the both.
3.A Hierarchical Evaluation Response Algorithm(HERA)which deals with the single link failure based on multi-next hop routing mechanism is presented. Under this mechanism, failures are divided into three levels: convergence of this node, convergence of the upstream neighbors and global convergence, which makes the failure influence locally as far as possible. Simulation results show that, in networks with different connectivity, HERA can trigger global convergence as little as possible, failure recovery time is shortened, and the stability of the network is enhanced effectively. Under a single link failure, convergence time of D-SSPA decreased 21.7% than the SP, and decreased 9.5% than st.
引文
[1] RFC1058.C.Hendrick.Routing Information Protocol[S].IETF, 1988.
[2] R. Bellman. On a routing problem. Quarterly Applied Mathematics [J].1958, 16(1):87-90.
[3] RFC2328.OSPF version 2[S].IETF, 1988.
[4] RFC1195.Use of OSI IS-IS for Routing in TCP/IP and Dual Environments[S].IETF, 1990.
[5] E. Dijkstra. A note on two problems in connection with graphs, Numerical Mathematics [J].1959, 1(1):269-271.
[6]葛建立,吴剑章.TCP/IP路由技术(第一卷)[M].北京:人民邮电出版社,2003:141-173.
[7] R. Albrightson, J.J. Garcia-Luna-Aceves, J. Boyle. EIGRP-A Fast Routing Protocol Based on Distance Vectors [A]. In:Network/Interop.1994[C].Berlin Germany, 1994:1-13.
[8] Masip-Bruin. X, Yannuzzi. M, Domingo-Pascual. J, et al. Research Challenges in Qos Routing [J].Computer Communications, 2006, 29:563–581.
[9] Rosen. E, Viswanathan. A, Callon. R. Multiprotocol Label Switching Architecture[S]. RFC 3031, IETF, January 2001.
[10] NF Maxemchuk. Dispersity Routing[A].In: IEEE Int Conf Communications (ICC1975)[C], San Francisco, CA: 1975:10-41.
[11] Dongmei Wang, Guangzhi Li, Robert Doverspike. On-line Restoration for Multi-Path Routing [A]. In: Proceedings of Design of Reliable Communication Networks (DRCN). 5th International Workshop[C]. CA, USA: IEEE, 2005, 10(16): 41-46.
[12] S. Rai, B. Mukherjee, O. Deshpande. IP resilience within an autonomous system: Current approaches, challenges, and future directions [A].In:IEEE Communications Magazine[C], vol. 43, no. 10:142–149.
[13] A. Nucci, et al.IGP Link Weight Assignment for Transient Link Failures [A].Elsevier ITC 18, 2003.
[14] Srinivas Vutukury, J.J. Garcia-Luna-Aceves. MDVA: A Distance-Vector Multipath Routing Protocol [A]. In: Proceedings of the INFOCOM 2001, 20th Annual Joint Conference of the IEEE Computer and Communications Societies[C], Anchorage, USA, 2001.
[15] Srinivas Vutukury. Multipath Routing Mechanisms for Traffic Engineering and Quality of Service in the Internet [D]. Ph.D thesis, Santa Cruz: University of California, March 2001.
[16]陈文平.多下一跳快速自愈路由技术研究[D].郑州:信息工程大学,2009.
[17] Narvaez. P, Siu. K. Y. Efficient Algorithms for Multi-Path Link State Routing [A]. In: Proceedings of ISCOM'99[C].Kaohsiung, Taiwan, November 1999.
[18] S. Vutukury, J.J. Garcia-Luna-Aceves. A Simple Approximation to Minimum Delay Routing [A]. In: Proc. of ACM SIGCOMM[C].Cambridge, Massachusetts, USA, 1999.
[19] H. S. Palakurthi. Study of Multipath Routing for QoS Provisioning[A].EECS 803-Introduction to Research, October 5,2001:1-6.
[20] Akon. M. M, Asaduzzaman. S, Rahman. Md. S. Proposal for st-Routing Protocol [J]. Telecommunication Systems, 2004, 25, 3-4:287-298.
[21] Booth. K. S, Lueker. G. S. Testing the Consecutive Ones Property, Interval Graphs, and Graph Planarity Testing Using PQ-Tree Algorithms [J]. Journal of Computer Systems Science, 1976, 13:335-379.
[22] G. Di Battista, P. Eades, R. Tamassia, I.G. Tollis. Graph Drawing [A]. Prentice-Hall, Upper Saddle River, NJ, 1999.
[23] F. Annexstein, K. Berman. Directional routing via generalized st-numberings [A]. SIAM J. Discrete Math, 2000, 13(2):268–279.
[24] Ulrik Brandes. Eager st-ordering [A].In: Proc. European Symposium on Algorithms[C], 2002:247-256.
[25] SSFNet 1.5[EB/OL]. http:// www .ssfnet .org/.
[26] BRITE Topology Generator [EB/OL]. http://www.cs.bu.edu/brite/.
[27]郭卓.分布式QoS路由算法的研究[D].沈阳:沈阳工业大学,2007.
[28] Blai Bonet, Hector Geffner. Learning Depth-First Search: A Unified Approach to Heuristic Search in Determinstic and Non-Determinstic Settings, and its application to MDPs[A].American Association for Artificial Intelligence,2006.
[29] Cormen. T. H, Leiserson. C. E, Rivest. R. L, et al. Introduction to Algorithms, Second Edition [M]. MIT Pressan McGraw-Hill, 2001:436-483.
[30] Prim. R. C. Shortest Connection Networks and Some Generations [J]. Bell System Tech. J, 1957, 36:1389-1401.
[31] Awduche D, et a1. Overview and principles of Internet traffic engineering[S]. Internet RFC 3272, May 2002.
[32] Moore D, Shannon C, Claffy K. Code-Red: a case study on the spread and victims of an Internet worm [A].In:Proceedings of ACM SIGCOMM Internet Measurement Workshop,Marseille,France, 2002[C].New York, USA: ACM Press, 2002:273-284.
[33] A. Markopoulou, G. Iannaccone, S. Bhattacharyya, et al. Characterization of Failures in an IP Backbone [A]. In: Proc. of IEEE INFOCOM 2004[C], Hong Kong, China, 2004: 7-11.
[34] John TM. OSPF: Anatomy of an Internet Routing Protocol [M]. Massachusetts, USA: Addison Wesley Longman, Inc, 1998:4-4.
[35] Pierre F, Clarence F, John E, et al. Achieving sub-second IGP convergence in large IP networks [J]. ACM SIGCOMM Computer Communication Review, 2005, 35(2):5-44.
[36] Lee S, Yu YZ, Nelakuditi S, et al. Proactive vs reactive approaches to failure resilient routing[A].In: Proceedings of INFOCOM[C]. Hong Kong: IEEE Press, 2004: 7-11.
[37] Kvalbein A, Audun Fosselie Hansen, Cicic T, et al. Fast IP network recovery using multiple routing configurations[A].In:Proceedings of INFOCOM[C]. Barcelona, Spai, IEEE Press, 2006:1-11.
[38] S. Iyer, S. Bhattacharyya, N. Taft, C. Diot. An approach toalleviate link overload asobserved on an IP backbone[A]. In:Proceedings of INFOCOM’03[C], Mar. 2003:406–416.
[39] Psenak P, Mirtorabi S, Roy A. Multi-Topology (MT) routing in SPF [Z]. IETF Internet Draft (work in progress), February 2006.
[40] Atlas A. Basic Specification for IP fast-reroute: loop-free alternates [Z]. IETF Internet Draft (work in progress), February 2006.
[41] Basu A, Riecke J. Stability issues in OSPF routing [A].In: Proceedings of ACM Special Interest Group on Data Communication, San Diego, California, United States,2001[C]. New York, USA: ACM Press, 2001:225-236.
[42] Yuan Zhong, Xin Yuan. Impact of Resource Reservation on Distributed Multi-path Quality of Service Routing Schemes [A]. The Eighth International Workshop on Quality of Service, 2000:95-104.
[43] Zvi Rosberg, Andrew Zalesky, Hai Le Vu. Analysis of OBS Networks with Limited Wavelength Conversion[A].In:IEEE/ACM Transactions on Networking[C], 2006:1118-1127.
[2] R. Bellman. On a routing problem. Quarterly Applied Mathematics [J].1958, 16(1):87-90.
[3] RFC2328.OSPF version 2[S].IETF, 1988.
[4] RFC1195.Use of OSI IS-IS for Routing in TCP/IP and Dual Environments[S].IETF, 1990.
[5] E. Dijkstra. A note on two problems in connection with graphs, Numerical Mathematics [J].1959, 1(1):269-271.
[6]葛建立,吴剑章.TCP/IP路由技术(第一卷)[M].北京:人民邮电出版社,2003:141-173.
[7] R. Albrightson, J.J. Garcia-Luna-Aceves, J. Boyle. EIGRP-A Fast Routing Protocol Based on Distance Vectors [A]. In:Network/Interop.1994[C].Berlin Germany, 1994:1-13.
[8] Masip-Bruin. X, Yannuzzi. M, Domingo-Pascual. J, et al. Research Challenges in Qos Routing [J].Computer Communications, 2006, 29:563–581.
[9] Rosen. E, Viswanathan. A, Callon. R. Multiprotocol Label Switching Architecture[S]. RFC 3031, IETF, January 2001.
[10] NF Maxemchuk. Dispersity Routing[A].In: IEEE Int Conf Communications (ICC1975)[C], San Francisco, CA: 1975:10-41.
[11] Dongmei Wang, Guangzhi Li, Robert Doverspike. On-line Restoration for Multi-Path Routing [A]. In: Proceedings of Design of Reliable Communication Networks (DRCN). 5th International Workshop[C]. CA, USA: IEEE, 2005, 10(16): 41-46.
[12] S. Rai, B. Mukherjee, O. Deshpande. IP resilience within an autonomous system: Current approaches, challenges, and future directions [A].In:IEEE Communications Magazine[C], vol. 43, no. 10:142–149.
[13] A. Nucci, et al.IGP Link Weight Assignment for Transient Link Failures [A].Elsevier ITC 18, 2003.
[14] Srinivas Vutukury, J.J. Garcia-Luna-Aceves. MDVA: A Distance-Vector Multipath Routing Protocol [A]. In: Proceedings of the INFOCOM 2001, 20th Annual Joint Conference of the IEEE Computer and Communications Societies[C], Anchorage, USA, 2001.
[15] Srinivas Vutukury. Multipath Routing Mechanisms for Traffic Engineering and Quality of Service in the Internet [D]. Ph.D thesis, Santa Cruz: University of California, March 2001.
[16]陈文平.多下一跳快速自愈路由技术研究[D].郑州:信息工程大学,2009.
[17] Narvaez. P, Siu. K. Y. Efficient Algorithms for Multi-Path Link State Routing [A]. In: Proceedings of ISCOM'99[C].Kaohsiung, Taiwan, November 1999.
[18] S. Vutukury, J.J. Garcia-Luna-Aceves. A Simple Approximation to Minimum Delay Routing [A]. In: Proc. of ACM SIGCOMM[C].Cambridge, Massachusetts, USA, 1999.
[19] H. S. Palakurthi. Study of Multipath Routing for QoS Provisioning[A].EECS 803-Introduction to Research, October 5,2001:1-6.
[20] Akon. M. M, Asaduzzaman. S, Rahman. Md. S. Proposal for st-Routing Protocol [J]. Telecommunication Systems, 2004, 25, 3-4:287-298.
[21] Booth. K. S, Lueker. G. S. Testing the Consecutive Ones Property, Interval Graphs, and Graph Planarity Testing Using PQ-Tree Algorithms [J]. Journal of Computer Systems Science, 1976, 13:335-379.
[22] G. Di Battista, P. Eades, R. Tamassia, I.G. Tollis. Graph Drawing [A]. Prentice-Hall, Upper Saddle River, NJ, 1999.
[23] F. Annexstein, K. Berman. Directional routing via generalized st-numberings [A]. SIAM J. Discrete Math, 2000, 13(2):268–279.
[24] Ulrik Brandes. Eager st-ordering [A].In: Proc. European Symposium on Algorithms[C], 2002:247-256.
[25] SSFNet 1.5[EB/OL]. http:// www .ssfnet .org/.
[26] BRITE Topology Generator [EB/OL]. http://www.cs.bu.edu/brite/.
[27]郭卓.分布式QoS路由算法的研究[D].沈阳:沈阳工业大学,2007.
[28] Blai Bonet, Hector Geffner. Learning Depth-First Search: A Unified Approach to Heuristic Search in Determinstic and Non-Determinstic Settings, and its application to MDPs[A].American Association for Artificial Intelligence,2006.
[29] Cormen. T. H, Leiserson. C. E, Rivest. R. L, et al. Introduction to Algorithms, Second Edition [M]. MIT Pressan McGraw-Hill, 2001:436-483.
[30] Prim. R. C. Shortest Connection Networks and Some Generations [J]. Bell System Tech. J, 1957, 36:1389-1401.
[31] Awduche D, et a1. Overview and principles of Internet traffic engineering[S]. Internet RFC 3272, May 2002.
[32] Moore D, Shannon C, Claffy K. Code-Red: a case study on the spread and victims of an Internet worm [A].In:Proceedings of ACM SIGCOMM Internet Measurement Workshop,Marseille,France, 2002[C].New York, USA: ACM Press, 2002:273-284.
[33] A. Markopoulou, G. Iannaccone, S. Bhattacharyya, et al. Characterization of Failures in an IP Backbone [A]. In: Proc. of IEEE INFOCOM 2004[C], Hong Kong, China, 2004: 7-11.
[34] John TM. OSPF: Anatomy of an Internet Routing Protocol [M]. Massachusetts, USA: Addison Wesley Longman, Inc, 1998:4-4.
[35] Pierre F, Clarence F, John E, et al. Achieving sub-second IGP convergence in large IP networks [J]. ACM SIGCOMM Computer Communication Review, 2005, 35(2):5-44.
[36] Lee S, Yu YZ, Nelakuditi S, et al. Proactive vs reactive approaches to failure resilient routing[A].In: Proceedings of INFOCOM[C]. Hong Kong: IEEE Press, 2004: 7-11.
[37] Kvalbein A, Audun Fosselie Hansen, Cicic T, et al. Fast IP network recovery using multiple routing configurations[A].In:Proceedings of INFOCOM[C]. Barcelona, Spai, IEEE Press, 2006:1-11.
[38] S. Iyer, S. Bhattacharyya, N. Taft, C. Diot. An approach toalleviate link overload asobserved on an IP backbone[A]. In:Proceedings of INFOCOM’03[C], Mar. 2003:406–416.
[39] Psenak P, Mirtorabi S, Roy A. Multi-Topology (MT) routing in SPF [Z]. IETF Internet Draft (work in progress), February 2006.
[40] Atlas A. Basic Specification for IP fast-reroute: loop-free alternates [Z]. IETF Internet Draft (work in progress), February 2006.
[41] Basu A, Riecke J. Stability issues in OSPF routing [A].In: Proceedings of ACM Special Interest Group on Data Communication, San Diego, California, United States,2001[C]. New York, USA: ACM Press, 2001:225-236.
[42] Yuan Zhong, Xin Yuan. Impact of Resource Reservation on Distributed Multi-path Quality of Service Routing Schemes [A]. The Eighth International Workshop on Quality of Service, 2000:95-104.
[43] Zvi Rosberg, Andrew Zalesky, Hai Le Vu. Analysis of OBS Networks with Limited Wavelength Conversion[A].In:IEEE/ACM Transactions on Networking[C], 2006:1118-1127.