面向ForCES架构的分布式OSPF协议的研究与实现
摘要
随着互联网流量和规模的不断增大,对路由器的性能要求越来越高。基于ForCES (Forwarding and Control Elements Separation,转发件与控制件分离)架构的路由器的集中式控制平面的存储和计算能力等受到一定限制,难以满足未来网络需求。所以,研究分布式路由协议的实现,提高控制平面的性能以更好地满足未来网络的需求,具有实际应用意义。
本文主要研究面向ForCES架构的分布式OSPF协议实现的若干关键技术,主要包括：(1)面向ForCES架构的分布式OSPF协议的实现模型；(2)面向ForCES架构的分布式OSPF协议实现模型的分析与研究；(3)面向ForCES架构的分布式OSPF路由表管理与路由同步机制的研究。
在以上关键技术研究的基础上,本文主要做了以下几方面的工作。
(1)根据对Zebra OSPF路由协议模块的耦合性的研究,对面向ForCES架构的分布式OSPF路由协议模块进行分解。
(2)从理论上分析与比较两种面向ForCES架构的分布式OSPF实现模型,通过分析与比较OSPF协议中Hello包处理、泛洪信息处理以及OSPF的收敛性,选择了一种较好的模型进行详细设计与实现。
(3)对面向ForCES架构的分布式OSPF同步机制进行研究,提出了面向ForCES架构的分布式OSPF路由表管理以及路由表和转发表同步的实现方案。
(4)对面向ForCES架构的分布式OSPF的相关模块进行设计与实现,主要包括分布式OSPF控制模块和转发模块的设计与实现。
(5)最后,对本文所实现的面向ForCES架构的分布式OSPF协议进行功能测试和性能分析。测试结果验证了分布式OSPF实现模型的可行性与正确性,同时,通过性能分析得出本文所设计的分布式OSPF路由器在Hello包的处理以及所产生的Flooding信息流量方面优于集中式OSPF路由器。
As the Internet flow and scale continuous increase, the performance requirements of routers is getting higher and higher. Centralized control plane in is ForCES-based router suffer certain limits, such as storage and computing power. Therefore, it is difficult to meet future network demand. So, it is significant to study distributed routing protocols to improve control plane of the performance for satisfying the needs of future network.
This thesis mainly studies some key techniques of distributed OSPF in ForCES-based routers, including:(1) decomposition scheme of distributed OSPF implementation; (2) analysis of distributed OSPF implementation; (3) routing table management and routing synchronization mechanism.
Depending on the study of the above key technologies, this thesis mainly completes the following tasks.
(1) The module of Zebra OSPF routing protocols are allocated to CE and FE, based on the coupling between modules.
(2) Two kinds of distributed OSPF implementations are theoretically compared and analyzed in terms of hello packet processing, flooding processing, and protocol convergence.
(3) Synchronization mechanism in distributed OSPF is studied. The scheme of the routing table management and routing synchronization for ForCES architecture is designed.
(4) The scheme of distributed OSPF for the ForCES architecture has been implemented.
(5) Finally, we carried out experiments to test and analyze distributed OSPF for ForCES architecture. The test results show the scheme of distributed OSPF is feasible and correct. Furthermore, through the performance analysis, we found that this design of distributed OSPF router is superior to the centralized OSPF routers in hello packet processing and flooding information flows.
本文主要研究面向ForCES架构的分布式OSPF协议实现的若干关键技术,主要包括：(1)面向ForCES架构的分布式OSPF协议的实现模型；(2)面向ForCES架构的分布式OSPF协议实现模型的分析与研究；(3)面向ForCES架构的分布式OSPF路由表管理与路由同步机制的研究。
在以上关键技术研究的基础上,本文主要做了以下几方面的工作。
(1)根据对Zebra OSPF路由协议模块的耦合性的研究,对面向ForCES架构的分布式OSPF路由协议模块进行分解。
(2)从理论上分析与比较两种面向ForCES架构的分布式OSPF实现模型,通过分析与比较OSPF协议中Hello包处理、泛洪信息处理以及OSPF的收敛性,选择了一种较好的模型进行详细设计与实现。
(3)对面向ForCES架构的分布式OSPF同步机制进行研究,提出了面向ForCES架构的分布式OSPF路由表管理以及路由表和转发表同步的实现方案。
(4)对面向ForCES架构的分布式OSPF的相关模块进行设计与实现,主要包括分布式OSPF控制模块和转发模块的设计与实现。
(5)最后,对本文所实现的面向ForCES架构的分布式OSPF协议进行功能测试和性能分析。测试结果验证了分布式OSPF实现模型的可行性与正确性,同时,通过性能分析得出本文所设计的分布式OSPF路由器在Hello包的处理以及所产生的Flooding信息流量方面优于集中式OSPF路由器。
As the Internet flow and scale continuous increase, the performance requirements of routers is getting higher and higher. Centralized control plane in is ForCES-based router suffer certain limits, such as storage and computing power. Therefore, it is difficult to meet future network demand. So, it is significant to study distributed routing protocols to improve control plane of the performance for satisfying the needs of future network.
This thesis mainly studies some key techniques of distributed OSPF in ForCES-based routers, including:(1) decomposition scheme of distributed OSPF implementation; (2) analysis of distributed OSPF implementation; (3) routing table management and routing synchronization mechanism.
Depending on the study of the above key technologies, this thesis mainly completes the following tasks.
(1) The module of Zebra OSPF routing protocols are allocated to CE and FE, based on the coupling between modules.
(2) Two kinds of distributed OSPF implementations are theoretically compared and analyzed in terms of hello packet processing, flooding processing, and protocol convergence.
(3) Synchronization mechanism in distributed OSPF is studied. The scheme of the routing table management and routing synchronization for ForCES architecture is designed.
(4) The scheme of distributed OSPF for the ForCES architecture has been implemented.
(5) Finally, we carried out experiments to test and analyze distributed OSPF for ForCES architecture. The test results show the scheme of distributed OSPF is feasible and correct. Furthermore, through the performance analysis, we found that this design of distributed OSPF router is superior to the centralized OSPF routers in hello packet processing and flooding information flows.
引文
[1]Forwarding and Control Element Separation [J/OL],Dec.2007. http://www.ietf.org/html.charters/forces-charter.html
[2]Doria (Ed.), et al, ForCES Protocol Specification [EB/OL], Internet Draft, March 2006.
[3]W. M. Wang.J. Hadi Salim, Alex Audu. "ForCES Transport Mapping Layer (TML) Service Primitives", work in progress [EB/OL], http://www.tools.ietf.org/html/draft-ietf-forces-tmlsp/.
[4]Weiming Wang, Ligang Dong, and Bin Zhuge, "TCP and UDP based ForCES Protocol TML over IP Networks" [EB/OL], http://www.tools.ietf.org/html/draft-wang-forces-iptml/.
[5]H.Khosravi et al., "TCP/IP based TML (Transport Mapping Layer) for ForCES protocol" [EB/OL], work in progress, http://www.tools.ietf.org/html/draft-ietf-forces-tcptml/.
[6]J. Halpern, "A base Library for use with the ForCES Protocol and Model", work in progress, http://www.tools.ietf.org/html/draft-halpern-forces-lfblibrary-base/.
[7]J.Halpern and Huaiyuan Ma, "A VPN Library for use with the ForCES Protocol and Model", work in progress, http://www.ietf.org/internet-drafts/draft-halperb-forces-lfblibrary-vpn-00.txt
[8]Weiming Wang, E. Haleplidis, K. Ogawa, F. Jia, and J. Halpern, "ForCES LFB Library", work in progress, http://www.tools.ietf.org/html/draft-ietf-forces-lfb-lib/
[9]寇晓蕤,罗军勇,蔡延荣.网络协议分析[M].北京：机械工程出版社：2009.
[10]Optical Internetworking Forum (OIF) [M/OL], http://www.oiforum.com/.
[11]Wang WM, Dong LG, Zhuge B. Analysis and implementation of an open programmable router based on forwarding and control element separation. Journal of Computer Science and Technology [J],2008.
[12]Robert Haas, Toshiaki Suzuki. Architecture of the Flexinet ForCES-based Control Point [J],2005.
[13]国防科技大学.新一代网络路由器[P].2004年国家863计划成果信息：2004.
[14]M. Hidell,O. Hagsand, P. Sjodin. Distributed Control for Decentralized Modular Routers [J].{Proc. SNCNW 2004} in Karlstad. Sweden,2004.
[15]N. Feamster, H. T. Balakrishnan Henriksson. U. Nordqvist and D. K. Liu. Embedded protocol processor for fast and efficient packet exception [R]. Technical Report Technical Report,2002.
[16]B. S. Ang. An evaluation of all attempts at offloading TCP/IP protocol processing onto an 1960m-based inic [R]. Technical Report Technical Report,2001.
[17]H. Bilic, B. Yitzhak. Deferred segmentation for wire-speed transmission of large TCP frames over standard GBE networks [R]. Technical report. Israel Institute of technology,2001.
[18]T. Blackwell. Speeding up protocols for small messages. In Conference proceedings on Applications, technologies, architectures, and protocols for computer communications [J]. Palo Alto, California,1996.
[19]S. Wang, J. S. Su. A survey of technology for TCP acceleration. Journal of Software [J],2004.
[20]R. Westrelin, N. Fugier, E. Nordmark, K. Kunze and E. Lemoine. Studying network protocol offload with emulation:Approach and preliminary results [C]. In 12th Annual IEEE Symposium on High Performance Interconnects. Stanford, CA,2004.
[21]M. Bjokman and P. Gunningberg. Perfomance modeling of multiprocessor implementations of protocols [J]. IEEE/ACM Transactions on Networking,1998.
[22]D. C. Schmidt and T. Suda. Measuring the performance of parallel message-based process architectures [C]. In Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies. Volume 2. Boston, Massachusetts,1995.
[23]M. Kaiserswerth. The parallel protocol engine. IEEE [J], ACM Transactions on Networking,1993.
[24]E. M. Nahum. D. J. Yates and D. Towsley. Performance issues in parallelized network protocols [R]. In USENIX Symposium on Operating Systems Design and Implementation,1994.
[25]张晓哲,卢锡城,朱培栋,彭伟.一种集群路由器节点转发表单映像一致性同步框架及关键算法[J].软件学报,2006.
[26]张晓哲,朱培栋,卢锡城.基于Cluster的BGP协议分布式并行实现模型及关键算法[J].计算机研究与发展.2004.
[27]Xiao-zhe Zhang, Peidong Zhu, and Xi-cheng Lu. Fully-Distributed and Highly-Parallelized Implementation Model of BGP4 Based on Clustered Routers [C]. In:Proe. Of 4th International Conference on Networking. Reunion Island, France:Springer,2005.
[28]张晓哲,卢锡城,苏金树.分布式BGP协议体系结构[J].长沙：国防科学技术大学学报.2006.
[29]李少勇.面向集群路由器的分布式BGP协议路由同步机制的研究与实现[D].长沙：国防科学技术大学,2008.
[30]蹇戈.分布式BGP协议邻居规模可扩展性分析与负载均衡研究[D].长沙：国防科学技术大学,2009.
[31]张创业.OSPF协议分布式研究与实现[D].郑州：解放军信息工程大学,2003.
[32]M. Deval, H. Khosravi, R. Muralidhar and R. Yavatkar. Distributed control plane architecture for network elements [J]. Intel Technology Journal,2003.
[33]X. P. Xiao and L. M. Ni. Parallel routing table computation for scalable IP routers [J]. Dhabaleswar K. Panda CBS. editor. In Proceedings of the IEEE International Workshop on CANPC. Las Vegas, Nevada, USA: Springer-Verlag,1998.
[34]Jesper Larsson Traff and Christos D. Zaroliagis, A Parallel Priority Data Structure With Applications [J], Dept. of Computer Science, University of Arhus. DK-8000 Arhus C, Denmark,1999.
[35]A Crauser, K. Mehlhom, U. Meyer, and P. Sanders, A Parallelization of Dijkstra's Shortest Path Algorithm [J],1998.
[36]U. Meyer and P. Sanders, A Parallel Single Source Shortest Path Algorithm [J],1998.
[37]崔耀文.OSPF协议软件的设计与实现[D].成都：电子科技大学.2003.
[38]Zebra [J/OL], http://www.Zebra.org/.
[39]Intel. Intel IXP2400 and IXP2800 Network Processor Programmer's Reference Manual [EB/OL],2004.
[40]Intel, Protocol Support Service Design Specification [R], Dec.2004.
[41]NPForum [EB/OL], http://www.npforum.org/techin/IPv4-Rev2-IA.pdf.
[42]J. T. Moy(美).OSPF协议剖析[M].北京：中国电力出版社,2002.
[43]车佳敏,林昭文,马严.OSPF协议的收敛性能研究[J].北京：中国科技论文在线,2009.
[44]张宏科,苏伟,武勇.网络处理器原理与技术[M].北京：北京邮电大学出版社：2004.
[45]Zebra configuration [J/OL], http://www.linuxsir.org/bbs/showthread.php?s=&threadid=135417.
[46]Intel. Intel IXP2XXX Product Line of Network Processors Development Tools User's Guide [EB/OL],2004.
[2]Doria (Ed.), et al, ForCES Protocol Specification [EB/OL], Internet Draft, March 2006.
[3]W. M. Wang.J. Hadi Salim, Alex Audu. "ForCES Transport Mapping Layer (TML) Service Primitives", work in progress [EB/OL], http://www.tools.ietf.org/html/draft-ietf-forces-tmlsp/.
[4]Weiming Wang, Ligang Dong, and Bin Zhuge, "TCP and UDP based ForCES Protocol TML over IP Networks" [EB/OL], http://www.tools.ietf.org/html/draft-wang-forces-iptml/.
[5]H.Khosravi et al., "TCP/IP based TML (Transport Mapping Layer) for ForCES protocol" [EB/OL], work in progress, http://www.tools.ietf.org/html/draft-ietf-forces-tcptml/.
[6]J. Halpern, "A base Library for use with the ForCES Protocol and Model", work in progress, http://www.tools.ietf.org/html/draft-halpern-forces-lfblibrary-base/.
[7]J.Halpern and Huaiyuan Ma, "A VPN Library for use with the ForCES Protocol and Model", work in progress, http://www.ietf.org/internet-drafts/draft-halperb-forces-lfblibrary-vpn-00.txt
[8]Weiming Wang, E. Haleplidis, K. Ogawa, F. Jia, and J. Halpern, "ForCES LFB Library", work in progress, http://www.tools.ietf.org/html/draft-ietf-forces-lfb-lib/
[9]寇晓蕤,罗军勇,蔡延荣.网络协议分析[M].北京：机械工程出版社：2009.
[10]Optical Internetworking Forum (OIF) [M/OL], http://www.oiforum.com/.
[11]Wang WM, Dong LG, Zhuge B. Analysis and implementation of an open programmable router based on forwarding and control element separation. Journal of Computer Science and Technology [J],2008.
[12]Robert Haas, Toshiaki Suzuki. Architecture of the Flexinet ForCES-based Control Point [J],2005.
[13]国防科技大学.新一代网络路由器[P].2004年国家863计划成果信息：2004.
[14]M. Hidell,O. Hagsand, P. Sjodin. Distributed Control for Decentralized Modular Routers [J].{Proc. SNCNW 2004} in Karlstad. Sweden,2004.
[15]N. Feamster, H. T. Balakrishnan Henriksson. U. Nordqvist and D. K. Liu. Embedded protocol processor for fast and efficient packet exception [R]. Technical Report Technical Report,2002.
[16]B. S. Ang. An evaluation of all attempts at offloading TCP/IP protocol processing onto an 1960m-based inic [R]. Technical Report Technical Report,2001.
[17]H. Bilic, B. Yitzhak. Deferred segmentation for wire-speed transmission of large TCP frames over standard GBE networks [R]. Technical report. Israel Institute of technology,2001.
[18]T. Blackwell. Speeding up protocols for small messages. In Conference proceedings on Applications, technologies, architectures, and protocols for computer communications [J]. Palo Alto, California,1996.
[19]S. Wang, J. S. Su. A survey of technology for TCP acceleration. Journal of Software [J],2004.
[20]R. Westrelin, N. Fugier, E. Nordmark, K. Kunze and E. Lemoine. Studying network protocol offload with emulation:Approach and preliminary results [C]. In 12th Annual IEEE Symposium on High Performance Interconnects. Stanford, CA,2004.
[21]M. Bjokman and P. Gunningberg. Perfomance modeling of multiprocessor implementations of protocols [J]. IEEE/ACM Transactions on Networking,1998.
[22]D. C. Schmidt and T. Suda. Measuring the performance of parallel message-based process architectures [C]. In Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies. Volume 2. Boston, Massachusetts,1995.
[23]M. Kaiserswerth. The parallel protocol engine. IEEE [J], ACM Transactions on Networking,1993.
[24]E. M. Nahum. D. J. Yates and D. Towsley. Performance issues in parallelized network protocols [R]. In USENIX Symposium on Operating Systems Design and Implementation,1994.
[25]张晓哲,卢锡城,朱培栋,彭伟.一种集群路由器节点转发表单映像一致性同步框架及关键算法[J].软件学报,2006.
[26]张晓哲,朱培栋,卢锡城.基于Cluster的BGP协议分布式并行实现模型及关键算法[J].计算机研究与发展.2004.
[27]Xiao-zhe Zhang, Peidong Zhu, and Xi-cheng Lu. Fully-Distributed and Highly-Parallelized Implementation Model of BGP4 Based on Clustered Routers [C]. In:Proe. Of 4th International Conference on Networking. Reunion Island, France:Springer,2005.
[28]张晓哲,卢锡城,苏金树.分布式BGP协议体系结构[J].长沙：国防科学技术大学学报.2006.
[29]李少勇.面向集群路由器的分布式BGP协议路由同步机制的研究与实现[D].长沙：国防科学技术大学,2008.
[30]蹇戈.分布式BGP协议邻居规模可扩展性分析与负载均衡研究[D].长沙：国防科学技术大学,2009.
[31]张创业.OSPF协议分布式研究与实现[D].郑州：解放军信息工程大学,2003.
[32]M. Deval, H. Khosravi, R. Muralidhar and R. Yavatkar. Distributed control plane architecture for network elements [J]. Intel Technology Journal,2003.
[33]X. P. Xiao and L. M. Ni. Parallel routing table computation for scalable IP routers [J]. Dhabaleswar K. Panda CBS. editor. In Proceedings of the IEEE International Workshop on CANPC. Las Vegas, Nevada, USA: Springer-Verlag,1998.
[34]Jesper Larsson Traff and Christos D. Zaroliagis, A Parallel Priority Data Structure With Applications [J], Dept. of Computer Science, University of Arhus. DK-8000 Arhus C, Denmark,1999.
[35]A Crauser, K. Mehlhom, U. Meyer, and P. Sanders, A Parallelization of Dijkstra's Shortest Path Algorithm [J],1998.
[36]U. Meyer and P. Sanders, A Parallel Single Source Shortest Path Algorithm [J],1998.
[37]崔耀文.OSPF协议软件的设计与实现[D].成都：电子科技大学.2003.
[38]Zebra [J/OL], http://www.Zebra.org/.
[39]Intel. Intel IXP2400 and IXP2800 Network Processor Programmer's Reference Manual [EB/OL],2004.
[40]Intel, Protocol Support Service Design Specification [R], Dec.2004.
[41]NPForum [EB/OL], http://www.npforum.org/techin/IPv4-Rev2-IA.pdf.
[42]J. T. Moy(美).OSPF协议剖析[M].北京：中国电力出版社,2002.
[43]车佳敏,林昭文,马严.OSPF协议的收敛性能研究[J].北京：中国科技论文在线,2009.
[44]张宏科,苏伟,武勇.网络处理器原理与技术[M].北京：北京邮电大学出版社：2004.
[45]Zebra configuration [J/OL], http://www.linuxsir.org/bbs/showthread.php?s=&threadid=135417.
[46]Intel. Intel IXP2XXX Product Line of Network Processors Development Tools User's Guide [EB/OL],2004.