Modeling And Analysis Of Bgp Routing Stability

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).