Research On Survivability Of Inter-domain Routing System Of The Internet

With the development of network technology, the Internet has become an indispensable part of modern society. As a critical component of the Internet, the survivability of the inter-domain routing system is attracting significant attentions from industrial and academic communities. Due to the large scale of topology, the distributed structure of autonomous management, the dynamic process of evolvement, the vulnerability of BGP, and the complex dependency between routing protocol and topology, the survivability issue is destined to be a long standing issue of the Internet. In this thesis, we study the survivability of inter-domain routing system under two types of threats, including prefix hijacking attacks and related failures. The results of this research are very important for the defense against attack, the recovery from failure and the improvement of routing protocol. The contributions of this thesis are as follows:Firstly, to solve the problem that currently few methods effectively characterize reroutings in the whole Internet, we propose a method to characterize inter-domain reroutings based on betweenness centrality of AS. By analyzing the neighboring-destination routes and global routes separately, our method empowers users to identify the temporal, topological, and relational characteristics of route changes. We apply our method to investigate the Internet’s reactions to four different disruptive events, including routing attack on You Tube in February 2008, AS4761 hijacking event in January 2011, the ‘311’ Japan earthquake in March 2011, and SEA-ME-WE 4 cable fault in April 2010. This examination reveals many new insights. For example, direct providers of attackers and victims are the most critical positions for amplifying impact of prefix hijacking attacks. Moreover, the route flapping and the congestion caused by the side-effect of rerouting after cable faults significantly degraded path quality. These four disruptive events are real cases of the following researches in this thesis. It is a fundamental step to characterize routing changes before studying the survivability of inter-domain routing system.Secondly, in the traditional environment of the Internet, few of the detection mechanisms against prefix hijackings have been practically deployed in a large scale. Inaccuracy of detection and inefficiency of deployment are two major causing problems. In this thesis, we study the impact of prefix hijacking attack on inter-domain routing system. Based on the key observation that the distribution of traffic load to a prefix will change unusually after the prefix is hijacked, we present a system LDC to detect BGP prefix hijacking by passively monitoring Load Distribution Change on direct providers of prefix’s owner, with the purpose of Leveraging Data-plane information to detect Control-plane problem. Comparing with previous prefix hijacking detections, LDC is more accurate in detection, more efficient in deployment and robust in victim notification. Through large amount of simulations of hijacking attacks and AS failure events based on empirical topology data of the Internet, we evaluate the relationships between detecting threshold, registry policy, detecting mode and detecting accuracy of LDC. Moreover, based on historical data, we employ LDC to detect a real prefix hijacking event, the You Tube event, to exemplify its usage and advantages.Thirdly, to better understand the dynamics of inter-domain routing system under prefix hijackings in a complex environment of network, we study the impact of this attack with multiple attackers and multiple victims in cloud computing networks for the first time. We model this problem as a goal programming task, which programs prefix hijacking scenes rationally to achieve highest impact under certain constraints, and then solve it by applying a genetic algorithm. By analyzing the best solution to the problem, we find that victims play a more important role in affecting impact than attackers. The impact does not always increase along with the increasing amounts of attackers and victims. On the contrary, if victims are more than 20, the impact decreases to 0 gradually. For goal programming, the degree of an AS is a major criterion to be considered, since the hijacking scenario with higher-degree attackers and higher-degree victims will achieve higher impact. These findings are useful for cloud service providers to better understand the influencing factors of survivability issues, and secure cloud computing networks by defensing against prefix hijacking attacks.Fourthly, to describe the unique ‘virtual cut’ and ‘automatic restoration’ characteristics of inter-domain routing system under cascading failures, we propose a model CAFEIN(model for CAscading Failur Es in INter-domain routing system) for the first time, and characterize the survivability of inter-domain routing system by reachability and number of rerouting messages. Based on the model, we study the factors that influence the survivability of the Internet under cascading failures, the affecting scope of cascading failures, and the propagation process of cascading failures. Results of simulations reveal following findings: First, due to the co-location of data plane and control plane of BGP, the survivability of inter-domain routing system is sensitive to the cascading failures triggered by a single initial failure, which bring a great deal of added burden to almost all the core ASes, especially the low-level ones, crippling their ability to make routing decisions. Second, when the tolerance parameter of AS links is less than 0.1, the cascading effect tends to be amplified globally. Third, the effect triggered by intentional attack is greater than that triggered by random breakdown. But the difference between them is not as prominent as previous research due to the unique automatic-restoration process in inter-domain routing system. At last, the links which are heavily loaded or near the initial failure are more likely to be congested when the cascading effect is getting more severe.Finally, to study the open issue of assessing survivability of logical networks under large-scale physical failures, we propose a model for regional failures in inter-domain routing system for the first time, which is called REFER(model for REgional Failur Es in inter-domain Routing system). Based on the model, we assess the impact of regional failures on inter-domain routing system on a finer level, considering different routing polices of intra-domain and inter-domain routing systems. Then we perform simulations on an empirical topology with geographical characteristics of the Internet to simulate a regional failure that locates at a city with important IXP. Results show that the Internet is robust under a city-level regional failure. The reachability is almost the same after the failure, and the reroutings occur at the edge of the Internet, hardly affecting the core of inter-domain routing system.