域间路由不稳定性监测分析技术研究
摘要
随着网络带宽的不断增加,Internet上的应用服务越来越多,同时,这些应用服务对网络性能的要求也越来越高。路由系统是网络互联的核心部分,它控制着网络流量的传输。当路由不稳定时,网络整体或局部的性能会严重下降,如瞬时大量丢包、路由收敛延迟和传输延迟等。然而,仅靠路由协议无法保障路由系统长期稳定地运行。随着Internet以及ISPs不断膨胀,路由不稳定抑制方法的作用越来越小,域间路由不稳定问题逐渐突出。因此,全面有效地监测域间路由不稳定性就显得尤为重要,这对于及时准确地发现和排查路由故障具有重要的意义,是网络测量和管理的重要内容之一。
目前,已有的域间路由不稳定性监测分析方法和工具只能从整体角度大致反映网络不稳定状况,不够全面,无法给故障排查提供有效依据。本文的工作即以实现全面、有效的域间路由不稳定性监测技术为目标,从相关的工程项目、理论研究、实用工具三个方面进行了全面深入的调研,并在结合路由监测系统的应用环境、功能特点、性能要求的基础上,做了如下方面的工作:
1.提出了域间路由不稳定性的分析指标和方法。该方法首先在<对等体、前缀>二元组的BGP更新消息序列层面上,从多个方面提出了能够反映域间路由不稳定性的指标,作为全面分析不稳定性的基础。然后归纳了三个更高层面的分析方法,从而提供了多层次的域间路由不稳定性监测视图。
2.基于所提出的指标和方法,实现了域间路由不稳定性的分析工具FlapView,该工具弥补了现有测量工具监测信息单一的缺点,具有实时、有效、全面的特点。通过应用于实际BGP消息的分析,验证了工具的有效性。
3.设计了路由监测系统的结构和功能,实现原型系统。根据路由监测系统的应用环境、性能要求、功能需求,设计了系统的结构和功能,主要包含数据采集、数据处理和分析、结果显示、管理控制四个部分,具有良好的可扩展性、可靠性、易用性。在此基础上实现了原型系统,为系统的后期实施和改进奠定了基础。
With the increasing of network bandwidth, there are more and more applications and services on Internet. At the same time, these applications have more and more requirements to network performance. Routing system is the core component of Internet, and it controls the paths taken by the traffic in the network. When routes are instable, the performance of the entire network or its portion will be degraded, such as increased burst loss, delays in the time for route convergence and traffic transport. However, only using routing protocols is not enough to build the stable operation of the routing system. The expansion of Internet and ISPs weaken the methods of route damping, and the inter-domain routing instability becomes more and more obvious. Therefore, we need monitoring and analyzing the inter-domain routing instability exactly to enable better understanding of issues and factors leading to inter-domain routing instability, troubleshoot routing problems and direct network planning.Currently, there is no special methods and tools available that can monitor and analyze inter-domain routing instability effectively. This paper takes the goals of valid, exact mornitoring routing instability, and makes a comprehensive investigation from related projects, studies and tools. The following work has been done based on the applying environment, functional characteristic, performance requirement of routing monitoring system:1. Analysis metrics and methods for inter-domain routing instability are proposed. First, it present metrics that can reflect inter-domain routing instability from various aspects at the layer where BGP UPDATE messages are grouped by the given tuple. Based on this, analysis on three other higher layers is proposed. Thus, it provides multi-layer views for monitoring inter-domain routing instability.2. A tool of Flap View is developed based on previously proposed analysis metrics and methods. The tool makes up with the drawback of current monitoring tools which have single monitoring metrics, and it has the advantages of real time, effectivity, comprehension. We verify the validation of this tool by using it to analyze real BGP messages.
3. The framework and functions of the route monitoring system are designed, based on the requirement of applying environment, performance, and etc. The four main components of the system are data collecting and analyzing, result displaying, and management control. A prototype, which is flexible and extensible, is developed that meets these requirements. It is the first step toward further development.
目前,已有的域间路由不稳定性监测分析方法和工具只能从整体角度大致反映网络不稳定状况,不够全面,无法给故障排查提供有效依据。本文的工作即以实现全面、有效的域间路由不稳定性监测技术为目标,从相关的工程项目、理论研究、实用工具三个方面进行了全面深入的调研,并在结合路由监测系统的应用环境、功能特点、性能要求的基础上,做了如下方面的工作:
1.提出了域间路由不稳定性的分析指标和方法。该方法首先在<对等体、前缀>二元组的BGP更新消息序列层面上,从多个方面提出了能够反映域间路由不稳定性的指标,作为全面分析不稳定性的基础。然后归纳了三个更高层面的分析方法,从而提供了多层次的域间路由不稳定性监测视图。
2.基于所提出的指标和方法,实现了域间路由不稳定性的分析工具FlapView,该工具弥补了现有测量工具监测信息单一的缺点,具有实时、有效、全面的特点。通过应用于实际BGP消息的分析,验证了工具的有效性。
3.设计了路由监测系统的结构和功能,实现原型系统。根据路由监测系统的应用环境、性能要求、功能需求,设计了系统的结构和功能,主要包含数据采集、数据处理和分析、结果显示、管理控制四个部分,具有良好的可扩展性、可靠性、易用性。在此基础上实现了原型系统,为系统的后期实施和改进奠定了基础。
With the increasing of network bandwidth, there are more and more applications and services on Internet. At the same time, these applications have more and more requirements to network performance. Routing system is the core component of Internet, and it controls the paths taken by the traffic in the network. When routes are instable, the performance of the entire network or its portion will be degraded, such as increased burst loss, delays in the time for route convergence and traffic transport. However, only using routing protocols is not enough to build the stable operation of the routing system. The expansion of Internet and ISPs weaken the methods of route damping, and the inter-domain routing instability becomes more and more obvious. Therefore, we need monitoring and analyzing the inter-domain routing instability exactly to enable better understanding of issues and factors leading to inter-domain routing instability, troubleshoot routing problems and direct network planning.Currently, there is no special methods and tools available that can monitor and analyze inter-domain routing instability effectively. This paper takes the goals of valid, exact mornitoring routing instability, and makes a comprehensive investigation from related projects, studies and tools. The following work has been done based on the applying environment, functional characteristic, performance requirement of routing monitoring system:1. Analysis metrics and methods for inter-domain routing instability are proposed. First, it present metrics that can reflect inter-domain routing instability from various aspects at the layer where BGP UPDATE messages are grouped by the given
3. The framework and functions of the route monitoring system are designed, based on the requirement of applying environment, performance, and etc. The four main components of the system are data collecting and analyzing, result displaying, and management control. A prototype, which is flexible and extensible, is developed that meets these requirements. It is the first step toward further development.
引文
[1] C. Labovitz, G. Malan, and F. Jahanian, "Internet routing instability," inIEEE/ACM Trans. Networking, vol. 6, Oct. 1998, pp. 515-528.
[2] V. Paxson, "End-to-end Internet packet dynamics," IEEE/ACM Trans. Networking, vol. 7, pp. 277-292, June 1999.
[3] Ramesh Govindan, Anoop Reddy: An Analysis of Internet Inter-Domain Topology and Route Stability. INFOCOM 1997: 850-857
[4] J. Rexford, J. Wang, Z. Xiao, and Y. Zhang. BGP Routing Stability of Popular Destinations. In Proceeds of Internet Measurement Workshop, November 2002.
[5] C. Labovitz, A. Ahuja, A. Bose, and F. Jahanian, "Delayed Internet routing convergence" IEEE/ACM Trans. Networking, vol. 9, pp. 293-306, June 2001.
[6] RIPE's Routing Information Service, http://www.ris.ripe.net/
[7] Craig Labovitz, Abha Ahuja, Farnam Jahanian: Experimental Study of Internet Stability and Backbone Failures. FTCS 1999: 278-285
[8] Ke Zhang, Amy Yen, Xiaoliang Zhao, Daniel Massey, Shyhtsun Felix Wu, Lixia Zhang: On Detection of Anomalous Routing Dynamics in BGP. NETWORKING 2004: 259-270
[9] Aman Shaikh, Anujan Varma, Lampros Kalampoukas, Rohit Dube: Routability stability in congested networks: experimentation and analysis. SIGCOMM 2000: 163-174
[10] Craig Labovitz, G. Robert Malan, Farnam Jahanian: Origins of Internet Routing Instability. INFOCOM 1999: 218-226
[11] K. Varadhan, R. Govindan, and D. Estrin, "Persistent Route Oscillations in Internet Domain Routing", Technical Report USC CS TR.96-631, Department of Computer Science, University of Southern California, Feb. 1996.
[12] Anja Feldmann, Olaf Maennel, Zhuoqing Morley Mao, Arthur W. Berger, Bruce M. Maggs: Locating Internet routing instabilities. SIGCOMM 2004: 205-218
[13]Sam Halabi, Danny McPherson. Internet 路由结构.北京:人民邮电出版社. 2003.6 91-99,137-201,287-292
[14] Matthew Caesar, L. Subramanian, Randy H. Katz, "Root cause analysis, of Internet routing dynamics", Technical Report UCB/CSD-. 04-1302, UC Berkeley, november 2003.
[15] Mohit Lad, Dan Massey, Lixia Zhang, "Visualizing Internet Routing Dynamics using Link-Rank", UCLA Technical Report TR050010, March 2005.
[16]RFC 1771, "A Border Gateway Protocol 4 (BGP-4)", http://www.faqs.org/rfcs/rfc1771.html
[17] T. G. Griffin, "What is the Sound of One Route Flapping?", Dartmouth Summer Workshop, 2002
[18] BGP Data Analysis Project. http://www.clarkson.edu/projects/itl/HOWTOS/bgpAnalysis/
[19] Internet Performance Measurement and Analysis, http://www.merit.edu/~ipma/
[20] Merit Network Inc. Routing Assets Database, http://www.radb.net/
[21] CERNET BGP View Project, http://bgpview.6test.edu.cn/bgp-view/download.shtml
[22] Tool: ASExplorer. http://www.merit.edu/~ipma/docs/Manual/asexplorer.html
[23] Tool: BGPlay. http://www.ris.ripe.net/bgplay/
[24] Tool: FlapGraph. http://www.merit.edu/~ipma/docs/Manual/flapgraph.html
[25] C. Alaettinoglu, "Scalable router configuration for the Internet," in Proc. IEEE IC3N, Oct. 1996.
[26] G. Huston, "Interconnection, peering, and settlements," in Proc. INET, June 1999.
[27] Lixin Gao: On inferring autonomous system relationships in the internet. IEEE/ACM Trans. Netw. 9(6): 733-745 (2001)
[28] Ford, L. R. Jr., and Fulkerson, D. R., "Flows in Networks", Princeton University Press, Princeton, N.J., 1962.
[29] RFC 1058, "Routing Information Protocol", http://www.faqs.org/rfcs/rfclO58.html
[30] RFC 2453, " RIP Version 2", http://www.faqs.org/rfcs/rfc2453.html
[31]IGRP, http://www.cisco.com/univercd/cc/td/doc/cisintwk/ito_doc/igrp.htm
[32]Enhanced IGRP, http://www.cisco.com/univercd/cc/td/doc/cisintwk/ito_doc/en_igrp.htm
[33] RFC 1878, "Variable Length Subnet Table for IPv4", www.isi.edu/in-notes/rfc1878.txt
[34] RFC 1519, "Classless Inter-Domain Routing(CIDR)", www.isi.edu/in-notes/rfcl519.txt
[35] RFC 1583, "OSPF Version 2", www.isi.edu/in-notes/rfcl583.txt
[36] ISO 10589, "Intermediate System to Intermediate System"; RFC 1195, "Use of OSI IS-IS for Routing in TCP/IP and Dual Environments", www.isi.edu/in-notes/rfcl 195.txt
[37] W.Richard Stevens. TCP/IP 详解,卷一:协议.北京:机械工业出版社. 2002.3 97-99
[38] Public Route Server for internet use: http://www.netdigix.com/servers.html
[39] Route Views Project: http://www.routeviews.org/
[40] Reverse Traceroute and Looking Glass servers in the World: http://www.caida.org/analysis/routing/reversetrace/
[41] RIPE NCC Looking Glass Services: http://www.ris.ripe.net/cgi-bin/lg/index.cgi
[42] Merit IRR Services: http://www.irr.net/
[43] Intra-Domain Routing Stability Measurement Project: http://rtanaly.koganei.wide.ad.jp/
[44] Multi-threaded Routing Toolkit Project: http://www.mrtd.net/
[45] the Cooperative Association for Internet Data Analysis, http://www.caida.org/
[46] V. I. Levenshtein. Binary codes capable of correcting deletions, insertions and reversals. DokladyAkademii Nauk SSSR 163(4) p845-848, 1965
[47] RFC2439, BGP Route Flap Damping, http://www.faqs.org/rfcs/rfc2439.html
[2] V. Paxson, "End-to-end Internet packet dynamics," IEEE/ACM Trans. Networking, vol. 7, pp. 277-292, June 1999.
[3] Ramesh Govindan, Anoop Reddy: An Analysis of Internet Inter-Domain Topology and Route Stability. INFOCOM 1997: 850-857
[4] J. Rexford, J. Wang, Z. Xiao, and Y. Zhang. BGP Routing Stability of Popular Destinations. In Proceeds of Internet Measurement Workshop, November 2002.
[5] C. Labovitz, A. Ahuja, A. Bose, and F. Jahanian, "Delayed Internet routing convergence" IEEE/ACM Trans. Networking, vol. 9, pp. 293-306, June 2001.
[6] RIPE's Routing Information Service, http://www.ris.ripe.net/
[7] Craig Labovitz, Abha Ahuja, Farnam Jahanian: Experimental Study of Internet Stability and Backbone Failures. FTCS 1999: 278-285
[8] Ke Zhang, Amy Yen, Xiaoliang Zhao, Daniel Massey, Shyhtsun Felix Wu, Lixia Zhang: On Detection of Anomalous Routing Dynamics in BGP. NETWORKING 2004: 259-270
[9] Aman Shaikh, Anujan Varma, Lampros Kalampoukas, Rohit Dube: Routability stability in congested networks: experimentation and analysis. SIGCOMM 2000: 163-174
[10] Craig Labovitz, G. Robert Malan, Farnam Jahanian: Origins of Internet Routing Instability. INFOCOM 1999: 218-226
[11] K. Varadhan, R. Govindan, and D. Estrin, "Persistent Route Oscillations in Internet Domain Routing", Technical Report USC CS TR.96-631, Department of Computer Science, University of Southern California, Feb. 1996.
[12] Anja Feldmann, Olaf Maennel, Zhuoqing Morley Mao, Arthur W. Berger, Bruce M. Maggs: Locating Internet routing instabilities. SIGCOMM 2004: 205-218
[13]Sam Halabi, Danny McPherson. Internet 路由结构.北京:人民邮电出版社. 2003.6 91-99,137-201,287-292
[14] Matthew Caesar, L. Subramanian, Randy H. Katz, "Root cause analysis, of Internet routing dynamics", Technical Report UCB/CSD-. 04-1302, UC Berkeley, november 2003.
[15] Mohit Lad, Dan Massey, Lixia Zhang, "Visualizing Internet Routing Dynamics using Link-Rank", UCLA Technical Report TR050010, March 2005.
[16]RFC 1771, "A Border Gateway Protocol 4 (BGP-4)", http://www.faqs.org/rfcs/rfc1771.html
[17] T. G. Griffin, "What is the Sound of One Route Flapping?", Dartmouth Summer Workshop, 2002
[18] BGP Data Analysis Project. http://www.clarkson.edu/projects/itl/HOWTOS/bgpAnalysis/
[19] Internet Performance Measurement and Analysis, http://www.merit.edu/~ipma/
[20] Merit Network Inc. Routing Assets Database, http://www.radb.net/
[21] CERNET BGP View Project, http://bgpview.6test.edu.cn/bgp-view/download.shtml
[22] Tool: ASExplorer. http://www.merit.edu/~ipma/docs/Manual/asexplorer.html
[23] Tool: BGPlay. http://www.ris.ripe.net/bgplay/
[24] Tool: FlapGraph. http://www.merit.edu/~ipma/docs/Manual/flapgraph.html
[25] C. Alaettinoglu, "Scalable router configuration for the Internet," in Proc. IEEE IC3N, Oct. 1996.
[26] G. Huston, "Interconnection, peering, and settlements," in Proc. INET, June 1999.
[27] Lixin Gao: On inferring autonomous system relationships in the internet. IEEE/ACM Trans. Netw. 9(6): 733-745 (2001)
[28] Ford, L. R. Jr., and Fulkerson, D. R., "Flows in Networks", Princeton University Press, Princeton, N.J., 1962.
[29] RFC 1058, "Routing Information Protocol", http://www.faqs.org/rfcs/rfclO58.html
[30] RFC 2453, " RIP Version 2", http://www.faqs.org/rfcs/rfc2453.html
[31]IGRP, http://www.cisco.com/univercd/cc/td/doc/cisintwk/ito_doc/igrp.htm
[32]Enhanced IGRP, http://www.cisco.com/univercd/cc/td/doc/cisintwk/ito_doc/en_igrp.htm
[33] RFC 1878, "Variable Length Subnet Table for IPv4", www.isi.edu/in-notes/rfc1878.txt
[34] RFC 1519, "Classless Inter-Domain Routing(CIDR)", www.isi.edu/in-notes/rfcl519.txt
[35] RFC 1583, "OSPF Version 2", www.isi.edu/in-notes/rfcl583.txt
[36] ISO 10589, "Intermediate System to Intermediate System"; RFC 1195, "Use of OSI IS-IS for Routing in TCP/IP and Dual Environments", www.isi.edu/in-notes/rfcl 195.txt
[37] W.Richard Stevens. TCP/IP 详解,卷一:协议.北京:机械工业出版社. 2002.3 97-99
[38] Public Route Server for internet use: http://www.netdigix.com/servers.html
[39] Route Views Project: http://www.routeviews.org/
[40] Reverse Traceroute and Looking Glass servers in the World: http://www.caida.org/analysis/routing/reversetrace/
[41] RIPE NCC Looking Glass Services: http://www.ris.ripe.net/cgi-bin/lg/index.cgi
[42] Merit IRR Services: http://www.irr.net/
[43] Intra-Domain Routing Stability Measurement Project: http://rtanaly.koganei.wide.ad.jp/
[44] Multi-threaded Routing Toolkit Project: http://www.mrtd.net/
[45] the Cooperative Association for Internet Data Analysis, http://www.caida.org/
[46] V. I. Levenshtein. Binary codes capable of correcting deletions, insertions and reversals. DokladyAkademii Nauk SSSR 163(4) p845-848, 1965
[47] RFC2439, BGP Route Flap Damping, http://www.faqs.org/rfcs/rfc2439.html