【作者】 包广斌；

【导师】 袁占亭；

【作者基本信息】 兰州理工大学 ， 控制理论与控制工程， 2009， 博士

【摘要】 BGP (Border Gateway Protocol)作为Internet路由体系结构的核心协议,其稳定性已成为人们所关心的焦点。本文以BGP路由稳定性作为研究对象,着重研究了影响BGP路由稳定性的关键问题,并提出了相应的稳定性解决方案,为Internet稳定运行提供了可靠的数据分析方法和快速的故障解决方案。通过理论研究、仿真分析、实验证实的研究方法,主要做了以下几个方面的工作：BGP路由抽象模型的研究和建立。本文以Internet路由体系结构为研究对象,深入研究了Internet路由系统的基本理论和动态行为规律,基于静态或动态数学模型,系统分析了BGP路由抖动、收敛延时、路由配置故障等影响BGP路由稳定性的关键问题。结合图论和拓扑学的已有知识给出BGP路由抽象模型,以简化对BGP路由稳定性问题的研究。BGP路由抖动的检测和消除方法研究。要从根本上解决路由抖动问题,最实际的方法就是找到路由抖动的源头并加以抑制。根据Griffin的BGP路由模型提出了改进的稳定路径问题模型,运用竞争有向图理论,用形式化方法详细描述了BGP路由抖动问题的本质,建立了抖动路由到路由策略冲突的映射关系,提出了基于消除策略冲突的路由抖动检测和消除方法,较好地解决了BGP路由策略所引发的路由抖动问题。BGP路由收敛性分析和改进。通过对BGP路由慢收敛现象的研究,发现造成BGP路由慢收敛的4个主要原因：1)链路或路由器失败造成的BGP路由探索延时；2)BGP最小路由通告时间会推迟BGP最佳路由的通告时间；3) AS(Autonomous System)间路由策略会影响BGP路由收敛时间；4)路由抖动抑制机制也会增加BGP路由收敛时间。研究发现,随着网络规模和连接密度的增加,BGP路由的收敛时间和消息开销都迅速增大,Tdown(路由失效)收敛时间上限达到O(n),其中n是AS节点数,消息开销上限达到|EN|·n,其中|EN|是AS间直连的链路数量。针对BGP路由慢收敛问题,本文提出了基于安全路径向量协议模型的路由收敛改进算法,通过检测AS间失效链路的根源节点,并在路由更新消息中携带根源节点信息,使接收更新的节点可以迅速撤销所有与根源节点相关的失效路由,从而提高收敛速度,减少路由更新消息开销。改进算法克服了BGP路由普遍采用的路由抖动抑制技术引起的网络收敛变慢问题,Tdown收敛时间上限下降为O(d),其中d是网络直径,更新消息开销下降为(?)EN(?), BGP路由收敛速度得到了显著提高。在BGP路由配置故障检测方法的研究中,本文主要针对路由源配置故障和路由输出配置故障进行分析。根据目前静态和动态检测方法中存在的问题,提出了两种路由配置故障检测方法：第一种方法,通过分析AS间关系和BGP路由通告原则,提出基于BGP路由输出规则的路由配置故障检测算法,该算法实现简单,便于实施,整个算法的时间复杂度为O(n·d),适合部署在AS间关系较为简单的BGP网络中。第二种方法,采用数理统计中随机变量的假设检验方法,通过分析一段时间内BGP对等体之间路由更新消息的统计量变化,实现基于广义似然比检验(Generalized Likelihood Ratio Test)的异常路由更新检测,进而推断BGP路由错误配置情况。该算法的结果不受AS之间的具体连接关系的影响,适合部署在AS间连接关系复杂的BGP网络中。在仿真实验过程中,本文使用美国Oregon大学Route View项目提供的在线BGP路由信息和欧洲IP资源网络协调中心RIPE NCC的RIS (Routing Information Service)项目网站上提供的路由信息作为实验数据。采用美国Michigan大学开发的MRT (Multi-threaded Routing Toolkit)来构造网络检测平台,用MRT所提供的动态注入BGP路由的功能,构造了脚本驱动的故障注入工具,将实验设定的路由故障注入到相应的仿真网络中。采用SSFNet (Scalable Simulation Framework Network)进行仿真实验,证实了本文所设计算法的仿真实验结果和理论分析结论基本吻合。更多还原

【Abstract】 BGP (Border Gateway Protocol) as the key agreement of the Internet routing system, its stability has become the focus of our concern. This paper mainly researched the critical problems influencing the stability of BGP routing, and proposed the corresponding solutions to it, which provide the reliable data-based analytical methods and fast fault solutions for the stable operation of the Internet. By means of theoretical study, simulation analysis, and research methods of experimental proof the key aspects of the work were made as follows.The study and establishment of an abstract model of BGP routing. Targeted to the Internet routing system, the basic theory of it and the dynamic law of behavior were deeply studied. On the basis of the static or dynamic mathematical model, the paper systematically analyzed the key issues which affect the BGP routing stability such as the BGP routing flap, convergence delay, and routing configuration fault, etc. In terms of the relevant knowledge of the protocol, an abstract model of BGP routing was given in order to simplify the stability of BGP routing issues.The study of BGP routing flap detection and elimination method. In order to fundamentally solve the routing flap problem, the most practical way is to find out the source of routing flap and then restrain it. In view of Griffin’s BGP routing model, this paper proposed an improved model of the Stable Path Problem, and utilized the Dispute Diagraph Theory and described the nature problem of BGP routing flap in detail with the formal methods. In addition, the paper established the mapping of the flapping route to the routing policy conflict and offered BGP routing flap detection algorithm and elimination methods on the basis of eliminating the policy conflict and better solved the problems of the routing flap triggered by BGP routing conflict.The analysis and improvement of BGP routing convergence. Through study to the phenomenon of slow convergence of BGP routing, the paper found the following four reasons resulted in the convergence delay:The link or router failure will lead to the delay of BGP routing exploration; The MRAI will postpone the best routing advertisement time; The routing policy between AS (Autonomous System) will affect the BGP routing convergence time and routing flap suppression system will increase the BGP routing convergence time. The study found that the BGP protocol convergence time and message overhead have increased rapidly as the network scale and the linkage density increases. While the upper boundary of Tdown convergence time reached O(n), where n is the AS number of nodes, the upper boundary of the message overhead reached|EN|·n,where|EN|is the number of direct links between AS. In the light of the slow convergence problem of BGP routing, this paper presented an algorithm to improve the routing convergence based on the safe path vector protocol model. By detecting the root nodes of AS link failure and carrying the root node information in a routing-update message, all the routing failure related to the root node can be quickly removed when receiving the updating nodes, so as to improve the convergence speed and reduce the overhead of routing-update message. The improved algorithm overcomes the slow network convergence problems caused by the routing flap suppression which have been widely used in BGP routing. Thus the upper boundary of Tdown convergence time fall off to O(d), where d is the network diameter, and the overhead of routing-update message go down to|EN|, the speed of BGP routing convergence will be increased remarkably.In the study of detecting the BGP routing configuration faults, this paper mainly analyzed the routing source fault configuration and the output fault configuration. According to the common problems existed in the current static and dynamic testing methods, two methods of detection to the routing configuration faults were proposed:The first method, in accordance with the analysis of the relationship between AS and the principles of BGP routing advertisement, the detection algorithm of BGP routing configuration faults based on the BGP routing output regulation was put forward. The time complexity of the algorithm which is easy to realize and implement is viewed as O(n·d) which can be fit for the deployment in the BGP network of a simple relationship between AS.The second method, the hypothesis testing method of random variable in mathematical statistics was adopted to analyze the change statistics of routing-update message between BGP routers in a period of time and then to realize the detection of the anomalous routing updates based on Generalized Likelihood Ratio. Accordingly, the circumstances of BGP routing configuration faults can be deduced. The results of the algorithm are not influenced by the specific connection relationship between AS, which can be fit for the deployment in the BGP network of a complicated relationship between AS.In the simulation process, the paper adopted the on-line BGP routing information provided by Route View project of United States Oregon University and the project website of European IP Resource Network Coordination Center RIPE NCC’s RIS (Routing Information Service) as an important source of experiment data. The network monitoring platform was constructed with the MRT (Multi-threaded Routing Toolkit) which were developed by Michigan University of the United States and a script-driven fault injection tool was created in application of the functions of dynamic injection into BGP routing offered by MRT in order to inject the setting route faults into the corresponding simulation network. So the results of simulation in this paper basically tally with the conclusion of theoretical analysis in the simulation experiments conducted by the SSFNet (Scalable Simulation Framework Network).更多还原