Research And Improvement Mechanism Design On Internet Inter-domain Routing Dynamics

Inter-domain routing system is known as the core component of the Internet, not only for the routing information it provides to glue the whole network together, but also for its relative stability that enables the continuous evolution of the Internet. As a typical distributing system, the inter-domain routing system relies on the exchange of route information among internal nodes to perform its function. This dynamic behavior in part determines what the inter-domain routing system behaves like, including scalability, stability, convergence property, security and so on. This thesis tries many kinds of ways to solve the problems facing current inter-domain routing dynamics, ranging from routing dynamics quantification, propagation analysis of route hijacking, exploration of new ways of route dynamics optimization, to new mechanism design. Our contributions are as follows.First of all, we discover some pathologic behavior of current inter-domain routing dynamics by measuring and analyzing Internet routing data.(1) The cause analysis of route changes reveals that most of the BGP updates are caused by COMMUNITY or AS Path changes, and there are many duplicate updates in BGP routing.(2) By analyzing the distribution of routing updates on network prefixes, we find that route flap is an important contributor to the excessive BGP updates in the inter-domain routing.(3) Further analysis of route flap shows that BGP path exploration(the phenomenon that a networking event usually triggers multiple BGP updates in a topologically distant router) dramatically amplifies the number of BGP updates, in which the number of paths involved are usually limited, showing path locality. These insights does not only deepen our understanding on inter-domain routing dynamics, but also provide some new ways of thinking of routing mechanism optimization.Second, by analyzing and modeling the propagation of route hijacking in inter-domain routing system, we uncover the reason why Internet ASes(Autonomous System, AS for short) are extremely vulnerable to route hijacking. We first model and formalize the AS-level immunity to BGP hijacking, and then calculate the sufficient condition and necessary condition for an AS to perceive the prefix hijacking via local BGP information, as well as the upper bound of such immunity. The evaluation shows that more than 80% of ASes have no immunity to routing hijacking at all and less than 0.26% of ASes have immunity higher than 85%. Further analysis pinpoints the root cause of such low immunity—―provider barrier‖, that the victim AS‘s providers prefer customer routes and thus prevent the propagation of hijacking routes to the victim AS. These researches establish theoretical basis for both the understanding on route hijacking and the design of efficient route monitoring.Third, in order to suppress route flap and the superfluous route updates caused by it, we design and implement PEA(Path Exploration Aggregation) mechanism based on the path locality theory. PEA performs aggregation on the transient paths explored by a highly active prefix, and propagates the aggregated path instead to reduce the updates caused by as-path changes. Moreover, in order to avoid the use of unstable routes, PEA purposely prolongs the aggregated path via as-path prepending to make it less preferred in the perspective of downstream routers. Evaluation results show that PEA can reduce BGP routing updates by up to 63.1%, shorten path exploration duration by up to 53.3%, and accelerate the convergence 7.39 seconds on average per routing event. These results are much better than three similar mechanisms, RFD(Route Flap Damping) included.Fourth, in order to cut off the propagation of unstable routes in inter-domain routing system, we propose a mechanism named BGP-VP(BGP-Virtual Path). Compared with PEA, BGP-VP makes two important changes.(1) BGP-VP estimates when to isolate route flap with route event frequency other than route change frequency, in order to avoid misjudgment.(2) Once a route flap is detected, BGP-VP converts the routing topology consisting of ASes affected by this flap into a single-source-single-sink network, and uses the virtual path from the source to the sink to represent all the paths that traverse through this network. We prove that BGP-VP can not only prevent the propagation of flapping routes, but also resolve the route ―dispute wheel‖. For details, for a given route dispute wheel, by deploying BGP-VP on any nodes of its minimum dispute wheel, the route dispute wheel can be solved. These findings are meaningful to the elimination of persistent route oscillation in current inter-domain routing system.Fifth, to tackle provider barrier and improve AS level immunity against route hijacking, we design a cooperation based monitoring mechanism. We define and evaluate the security capacity that an AS can obtain by participating in this cooperative monitoring, and the tolerance of failure of the built cooperative network by each AS. Besides, we also evaluate how the cooperative partner selection policy impacts these two measures. Experimental results show that by peering with only 25 cautiously selected ASes, one AS can improve its immunity to 95% against EA attack, in which the attacker AS would advertise the bogus route to all of its neighbors. The cooperative relationship between ASes fall into the category of direct reciprocity, in which a pair of ASes should usually derive similar amount of utility from each other. In this thread, we study and evaluate the precondition for this cooperative relationship to survive and evolve. The evaluation results show that although Tier 1 and Transit ASes have some advantages over Stub AS in defending against EA attack, they still need the cooperation of Stub ASes to deal with the thread of EC attack, where the attacker AS advertises the bogus route to only customer ASes.Sixth, we solve the two problems common to all the route monitoring solutions deployed in large scale:(1) how to identify the key events from the massive amount of routing events;(2) how to detect the route hijacking events against the cooperative monitor itself. Regarding the first problem, we propose a multi-dimension correlation method, which aggregates and filters received route changes in the granularity of occurrence time, involved prefix and observation vantage points. With this method, the reported origin changes, next-hop changes and reachability losses are 89.01%, 96.02% and 99.86% fewer than those without correlation respectively. Regarding the second problem, we propose a validation method, which correlates the information from BGP notifications, BGP route table, backward data packets and active probing to confirm whether the cooperative monitor is hijacked or not. This method is very accurate that no false positives are detected during the six month study period. On the basis of these work, we design and implement a cooperative monitor. The evaluation on bandwidth cost shows that the traffic loads the deployment of cooperative monitor imposed on the underlying network infrastructure are negligible.Seventh, accurate IP-to-AS mappings are necessary to BGP security monitoring, however, the frequent variations of the ownership and usage of IP and AS number resources make it very difficult to trace such information. From the perspective of Knowledge Plane(David D. Clark named it as a pervasive system within the network that provide services and advice to other elements of the network), we propose an automatic framework that enables the generation of accurate IP-to-AS mappings. This framework consists of several steps. We first formalize the allocation and utilization activities of Internet number resources(including IP addresses and AS numbers). To characterize the internal relationships between the entities represented by the records of RIR data, we then build a meta network, which is subsequently converted into a simpler network consisting of network operators and relationships among them. At last, a community discovery algorithm is used to divide this network into clusters, each of which is considered as an organization involved in Internet resource allocation and utilization activities. This model and framework is of great help in enhancing the capability of ISPs against prefix hijacking, improving the security of inter-domain routing system and deepening the understanding on Internet ecosystem.