面向集群路由器的分布式BGP协议路由同步机制的研究与实现
|
摘要
集群结构的路由器由于其自身的分布式特点,在支持网络端口密度、报文转发能力、控制平面计算能力以及设备生命周期等方面具有强大的优势,具有非常广阔的发展空间。但现有集群路由器中BGP协议的实现仍然沿用单进程或者单线程方式,没有真正实现软件意义上的可扩展性。因此为了应对BGP协议面临的性能挑战和满足下一代互联网的需求,研究如何实现集群路由器环境下BGP协议分布式处理,具有重要的实际意义和广阔的应用前景。
本文在分析开源路由协议软件Quagga BGPD实现结构的基础上,基于集群路由器体系结构下的分布计算模式,参与设计了基于集群结构的分布式BGP协议模型,深入研究了BGP路由器的规模可扩展性、分布式的路由存储和并行计算以及BGP会话迁移等关键问题。本文重点对内部通信模块和路由同步模块进行了设计,并提出了基于UDP的可靠广播和单播通信机制,实现了分布式BGP路由器实体间的高效可靠通信,保证了分布式BGP全局最优路由视图在转发平面和外部协议行为上与BGP协议规范的一致性,完成了分布式BGP原型系统的编码和测试。
本文的上述工作对在核心路由器中设计与实现更高性能的BGP协议具有重要的参考价值,同时为分布式BGP路由协议在商用高端集群路由器中的实际应用提供了详细的参考设计和丰富有力的试验数据。
Because of it’s distributed characteristics, the cluster router is powerful in the following aspects: support of the network port density, the message forwarding capability, the control plane computing power, and the equipment life cycle; therefore, it has very broad development space. However, in the current cluster router, the realization of BGP protocol is still achieved in single-process or single-thread, and there is no real sense of the software scalability. Therefore, in order to solve the performance challenges faced by BGP protocol and to meet the needs of next-generation Internet, the research on how to achieve BGP distributed processing on the router cluster environment is of important practical significance and broad application prospects.
Based on the analysis of the BGPD structure of open source routing protocol software Quagga and the distributed computing model in the router cluster architecture, this paper has been involved in the design of the structure of the cluster-based distributed BGP protocol and an in-depth study of the BGP router's size scalability, distributed storage and parallel computing of route information as well as other key issues such as the BGP sessions migration. This paper focused on the design of internal communication module and internal routing synchronization module, bring up an reliable unicast and broadcast communication mechanism based on UDP protocol, realized the highly efficient and reliable communication among the entities of the distributed BGP router, made sure that the global optimum view of distributed BGP protocol is in line with the norms in the forwarding plane and the external acts, and finally finished the coding and testing of the distributed BGP prototype system.
In this paper, the above-mentioned work is an important reference in the design and implementation of more high-performance BGP protocol in the core router, at the same time it provides a detailed reference design and rich and powerful experimental data in the practical application of the distributed BGP protocol in the high-end commercial cluster routers.
本文在分析开源路由协议软件Quagga BGPD实现结构的基础上,基于集群路由器体系结构下的分布计算模式,参与设计了基于集群结构的分布式BGP协议模型,深入研究了BGP路由器的规模可扩展性、分布式的路由存储和并行计算以及BGP会话迁移等关键问题。本文重点对内部通信模块和路由同步模块进行了设计,并提出了基于UDP的可靠广播和单播通信机制,实现了分布式BGP路由器实体间的高效可靠通信,保证了分布式BGP全局最优路由视图在转发平面和外部协议行为上与BGP协议规范的一致性,完成了分布式BGP原型系统的编码和测试。
本文的上述工作对在核心路由器中设计与实现更高性能的BGP协议具有重要的参考价值,同时为分布式BGP路由协议在商用高端集群路由器中的实际应用提供了详细的参考设计和丰富有力的试验数据。
Because of it’s distributed characteristics, the cluster router is powerful in the following aspects: support of the network port density, the message forwarding capability, the control plane computing power, and the equipment life cycle; therefore, it has very broad development space. However, in the current cluster router, the realization of BGP protocol is still achieved in single-process or single-thread, and there is no real sense of the software scalability. Therefore, in order to solve the performance challenges faced by BGP protocol and to meet the needs of next-generation Internet, the research on how to achieve BGP distributed processing on the router cluster environment is of important practical significance and broad application prospects.
Based on the analysis of the BGPD structure of open source routing protocol software Quagga and the distributed computing model in the router cluster architecture, this paper has been involved in the design of the structure of the cluster-based distributed BGP protocol and an in-depth study of the BGP router's size scalability, distributed storage and parallel computing of route information as well as other key issues such as the BGP sessions migration. This paper focused on the design of internal communication module and internal routing synchronization module, bring up an reliable unicast and broadcast communication mechanism based on UDP protocol, realized the highly efficient and reliable communication among the entities of the distributed BGP router, made sure that the global optimum view of distributed BGP protocol is in line with the norms in the forwarding plane and the external acts, and finally finished the coding and testing of the distributed BGP prototype system.
In this paper, the above-mentioned work is an important reference in the design and implementation of more high-performance BGP protocol in the core router, at the same time it provides a detailed reference design and rich and powerful experimental data in the practical application of the distributed BGP protocol in the high-end commercial cluster routers.
引文
[1] Z.H. Gong, Z.G. Sun. The architectures of clustered router. Technical report, Com-puter School of National University of Defence Technology, 2004.
[2] K. McCloghrie, D. Perkins and J. Schoenwaelder. Structure of management information version 2 (smiv2). RFC 2578, 1999.
[3] Y. Rekhter. A Border Gateway Protocol 4 (BGP-4). RFC 1771, 1995.
[4] J. Moy. OSPF Version 2. RFC 2328, 1998.
[5] G. Malkin. RIP Version 2 RFC 1723, 1994.
[6] D. Oran. OSI IS-IS Intra-domain Routing Protocol. RFC 1142, 1990.
[7] G. Huston. Internet bgp table, Http://bgp.potaroo.net, 2005.
[8] Z.H. Ge, D. R. Figueiredo, S. Jaiswal and L.X. Gao. On the hierarchical structure of the logical internet graph. In Proc. SPIE ITCom, 2001.
[9] Cidr report. Http://www.cidr-report.org, 2004.
[10] A. Feldmann, H.W. Kong, O. Maennel and A. Tudor. Measuring bgp pass-through times. Barakat C and Pratt I, editors, In Passive Active Measurement Workshop, 2004, 3015: 267-277.
[11] N. Taft. The basics of bgp routing and its performance in today's internet. In RHDM High-Speed Networks and Multimedia Workshop. France, 2001.
[12] T. Griffin, F.B. Shepherd and G. Wilfong. The stable paths problem and interdomain routing. IEEE/ACM Transactions On Networking, 2002, 10(1): 232-234.
[13] T. Griffin and G. Wilfong. On the correctness of ibgp configuration. In Proc. ACM SIGCOMM, 2002.
[14] C. Abovitz, A. Atujia, A. Bose and F. Jahanian. Delayed internet routing convergence. IEEE/ACM Transactions On Networking, 2001, 9(3): 293-306.
[15] S. Agarwal, C.N. Chuah, S. Bhattacharyya and C. Diot. Impact of bgp dynamics on router cpu utilization. Barakat C and Pratt I, editors, In Passive Active Measurement Workshop, 2004, 3015: 278-288.
[16] S. Halabi. Pluris massively parallel routing. Technical report. Pluris Inc, 1999.
[17] Avici systems technology. Http://www.avici.com, 2004.
[18] Juniper Networks. Juniper networks t640 internet routing node with matrix technology, 2002.
[19] M. MARUYAMA and N. TAKAHASHI, et al. Corerouter-1:an experiental parallel ip router using a cluster of workstations. IEICE TRANS.COMMUN, 1997, E80(10): 1407-1414.
[20] Gnu zebra (routing software). Http://www.zebra.org, 2003.
[21] Quagga routing software suite. Http://www.quagga.net, 2005.
[22] Xorp: extensible open router platform. Http://www.xorp.org, 2005.
[23] Cisco Networks. Http://www.cisco.com, 2004.
[24] Qnx software systems. Http://www.qnx.com, 2005.
[25] N. Feamster, H.T. Balakrishnan Henriksson, U. Nordqvist and D.K. Liu. Embedded protocol processor for fast and efficient packet eception. Technical Report Technical Report, 2002.
[26] B.S. Ang. An evaluation of an attempt at offloading tcp/ip protocol processing onto an i960rn-based inic. Technical Report Technical Report, 2001.
[27] H. Bilic, B. Yitzhak. Deferred segmentation for wire-speed transmission of large tcp frames over standard gbe networks. Technical report, Israel Institute of technology, 2001.
[28] T. Blackwell. Speeding up protocols for small messages. In Conference proceedings on Applications, technologies, architectures, and protocols for computer communications. Palo Alto, California, 1996.
[29] S. Wang, J. S. Su. A survey of technology for tcp acceleration. Journal of Software, 2004, 5(11): 1689-1699.
[30] N. Hutchinson, L. Peterson. The x-kernel: An architecture for implementing network protocols. IEEE Trans. Software Eng, 1991, 17: 64-75.
[31] D. C. Schmidt, T. Suda. Measuring the performance of parallel message-based process architectures. In Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies, volume 2. Boston, Massachusetts, 1995.
[32] M. Kaiserswerth. The parallel protocol engine. IEEE/ACM Transactions On Networking, 1993, 1(6): 650-663.
[33] E. M. Nahum, D. J. Yates and D. Towsley. Performance issues in parallelized network protocols. In USENIX Symposium on Operating Systems Design and Implementation, 1994.
[34] M. Deval, H. Khosravi, R. Muralidhar and R. Yavatkar. Distributed control plane architecture for network elements. Intel Technology Journal, 2003, 7(4): 1689-1699.
[35] R. Westrelin, N. Fugier, E. Nordmark, K. Kunze and E. Lemoine. Studying network protocol offload with emulation: Approach and preliminary results. In 12th Annual IEEE Symposium on High Performance Interconnects. Stanford, CA, 2004.
[36] X.P. Xiao and L. M. Ni. Parallel routing table computation for scalable ip routers. Dhabaleswar K. Panda CBS, editor, In Proceedings of the IEEE International Workshop on CANPC. Las Vegas, Nevada, USA: Springer-Verlag, 1998.
[37] Rekhter Y, Gross P. Application of the border gateway protocol in the internet. T J Watson Research Center, IBM Corp and MCI. Tech Rep: RFC 1772, 1995.
[38] Traina P. Experience with the BGP-4 protocol. Cisco Systems, TechRep: RFC1773, 1995.
[39] Traina P. BGP-4 protocol analysis. Cisco Systems, Tech Rep: RFC1774, 1995.
[40] Y. Rekhter, T. Li. A border gateway protocol 4 (BGP-4). T J Watson Research Center, IBM Corp and Cisco Systems. Tech Rep: RFC 1771, 1995.
[41] Y. Rekhter, T. Li. A Border Gateway Protocol 4 (BGP-4). Tech Rep: RFC 4271, 2006.
[42]张晓哲,朱培栋,卢锡城.基于集群路由器体系结构的BGP分布并行实现技术研究,计算机工程与科学, 2007(1): 5-7.
[43]张晓哲,卢锡城.路由协议并行处理技术研究.国防科学技术大学博士学位论文, 2005.
[44]张晓哲,卢锡城,苏金树.分布式BGP协议体系结构.国防科技大学学报, 2006.03: 81-86.
[45]范晓勃,吴建平,徐恪.分布式路由协议BGP-4的实现与优化.计算机研究与发展, 2000(3): 367-371.
[46] Graceful Restart Mechanism for BGP. Tech Rep: RFC4724, 2007.
[47] Graceful restart improves on BGP. Network World Tech Update, 2002.
[48] AX4000. http://www.spirent.com, 1998.
[2] K. McCloghrie, D. Perkins and J. Schoenwaelder. Structure of management information version 2 (smiv2). RFC 2578, 1999.
[3] Y. Rekhter. A Border Gateway Protocol 4 (BGP-4). RFC 1771, 1995.
[4] J. Moy. OSPF Version 2. RFC 2328, 1998.
[5] G. Malkin. RIP Version 2 RFC 1723, 1994.
[6] D. Oran. OSI IS-IS Intra-domain Routing Protocol. RFC 1142, 1990.
[7] G. Huston. Internet bgp table, Http://bgp.potaroo.net, 2005.
[8] Z.H. Ge, D. R. Figueiredo, S. Jaiswal and L.X. Gao. On the hierarchical structure of the logical internet graph. In Proc. SPIE ITCom, 2001.
[9] Cidr report. Http://www.cidr-report.org, 2004.
[10] A. Feldmann, H.W. Kong, O. Maennel and A. Tudor. Measuring bgp pass-through times. Barakat C and Pratt I, editors, In Passive Active Measurement Workshop, 2004, 3015: 267-277.
[11] N. Taft. The basics of bgp routing and its performance in today's internet. In RHDM High-Speed Networks and Multimedia Workshop. France, 2001.
[12] T. Griffin, F.B. Shepherd and G. Wilfong. The stable paths problem and interdomain routing. IEEE/ACM Transactions On Networking, 2002, 10(1): 232-234.
[13] T. Griffin and G. Wilfong. On the correctness of ibgp configuration. In Proc. ACM SIGCOMM, 2002.
[14] C. Abovitz, A. Atujia, A. Bose and F. Jahanian. Delayed internet routing convergence. IEEE/ACM Transactions On Networking, 2001, 9(3): 293-306.
[15] S. Agarwal, C.N. Chuah, S. Bhattacharyya and C. Diot. Impact of bgp dynamics on router cpu utilization. Barakat C and Pratt I, editors, In Passive Active Measurement Workshop, 2004, 3015: 278-288.
[16] S. Halabi. Pluris massively parallel routing. Technical report. Pluris Inc, 1999.
[17] Avici systems technology. Http://www.avici.com, 2004.
[18] Juniper Networks. Juniper networks t640 internet routing node with matrix technology, 2002.
[19] M. MARUYAMA and N. TAKAHASHI, et al. Corerouter-1:an experiental parallel ip router using a cluster of workstations. IEICE TRANS.COMMUN, 1997, E80(10): 1407-1414.
[20] Gnu zebra (routing software). Http://www.zebra.org, 2003.
[21] Quagga routing software suite. Http://www.quagga.net, 2005.
[22] Xorp: extensible open router platform. Http://www.xorp.org, 2005.
[23] Cisco Networks. Http://www.cisco.com, 2004.
[24] Qnx software systems. Http://www.qnx.com, 2005.
[25] N. Feamster, H.T. Balakrishnan Henriksson, U. Nordqvist and D.K. Liu. Embedded protocol processor for fast and efficient packet eception. Technical Report Technical Report, 2002.
[26] B.S. Ang. An evaluation of an attempt at offloading tcp/ip protocol processing onto an i960rn-based inic. Technical Report Technical Report, 2001.
[27] H. Bilic, B. Yitzhak. Deferred segmentation for wire-speed transmission of large tcp frames over standard gbe networks. Technical report, Israel Institute of technology, 2001.
[28] T. Blackwell. Speeding up protocols for small messages. In Conference proceedings on Applications, technologies, architectures, and protocols for computer communications. Palo Alto, California, 1996.
[29] S. Wang, J. S. Su. A survey of technology for tcp acceleration. Journal of Software, 2004, 5(11): 1689-1699.
[30] N. Hutchinson, L. Peterson. The x-kernel: An architecture for implementing network protocols. IEEE Trans. Software Eng, 1991, 17: 64-75.
[31] D. C. Schmidt, T. Suda. Measuring the performance of parallel message-based process architectures. In Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies, volume 2. Boston, Massachusetts, 1995.
[32] M. Kaiserswerth. The parallel protocol engine. IEEE/ACM Transactions On Networking, 1993, 1(6): 650-663.
[33] E. M. Nahum, D. J. Yates and D. Towsley. Performance issues in parallelized network protocols. In USENIX Symposium on Operating Systems Design and Implementation, 1994.
[34] M. Deval, H. Khosravi, R. Muralidhar and R. Yavatkar. Distributed control plane architecture for network elements. Intel Technology Journal, 2003, 7(4): 1689-1699.
[35] R. Westrelin, N. Fugier, E. Nordmark, K. Kunze and E. Lemoine. Studying network protocol offload with emulation: Approach and preliminary results. In 12th Annual IEEE Symposium on High Performance Interconnects. Stanford, CA, 2004.
[36] X.P. Xiao and L. M. Ni. Parallel routing table computation for scalable ip routers. Dhabaleswar K. Panda CBS, editor, In Proceedings of the IEEE International Workshop on CANPC. Las Vegas, Nevada, USA: Springer-Verlag, 1998.
[37] Rekhter Y, Gross P. Application of the border gateway protocol in the internet. T J Watson Research Center, IBM Corp and MCI. Tech Rep: RFC 1772, 1995.
[38] Traina P. Experience with the BGP-4 protocol. Cisco Systems, TechRep: RFC1773, 1995.
[39] Traina P. BGP-4 protocol analysis. Cisco Systems, Tech Rep: RFC1774, 1995.
[40] Y. Rekhter, T. Li. A border gateway protocol 4 (BGP-4). T J Watson Research Center, IBM Corp and Cisco Systems. Tech Rep: RFC 1771, 1995.
[41] Y. Rekhter, T. Li. A Border Gateway Protocol 4 (BGP-4). Tech Rep: RFC 4271, 2006.
[42]张晓哲,朱培栋,卢锡城.基于集群路由器体系结构的BGP分布并行实现技术研究,计算机工程与科学, 2007(1): 5-7.
[43]张晓哲,卢锡城.路由协议并行处理技术研究.国防科学技术大学博士学位论文, 2005.
[44]张晓哲,卢锡城,苏金树.分布式BGP协议体系结构.国防科技大学学报, 2006.03: 81-86.
[45]范晓勃,吴建平,徐恪.分布式路由协议BGP-4的实现与优化.计算机研究与发展, 2000(3): 367-371.
[46] Graceful Restart Mechanism for BGP. Tech Rep: RFC4724, 2007.
[47] Graceful restart improves on BGP. Network World Tech Update, 2002.
[48] AX4000. http://www.spirent.com, 1998.