Research Of Inter-domain Routing Modeling And Analysis

The current version of Border Gateway Protocol has been the same since the 1990 s. However, the Internet, which BGP serves for, is playing a more and more important role in human societies. With the rapid growth of network scale, traffic scale, and type of applications, BGP’s defects turn out to be critical factors which limit the Internet’s development. Because of BGP’s low scalability and indefinite control semantics, it is very difficult to understand and predict BGP’s routing behaviors, leading to difficulties in improving network efficiency, locating route instabilities, and ensuring route security. Because BGP doesn’t verify the authenticity and efficiency of route announcements, inefficient(even malicious) route announcement can be easily broadcasted in BGP’s routing system, leading to traffic hijacks and economic losses. Since the Internet and BGP are both deployed and driven by the economic interests, researches on BGP can be valuable to the future inter-domain protocols. Considering all the above reasons, we propose to study the topology, routing decision process, routing transmission process, and routing security problems. We propose a few improvements on the existing understandings and methods. Generally, this thesis made the following contributions:First, we qualify the completeness of AS level topology measurement. BGP collectors are the dominant data source for topology measurement. The income of a BGP monitor is severely impacted by its position. However, few previou works have systematically studied the topology observed from a BGP monitor. In this paper, we formally prove the range limit of topology observed by a BGP monitor. By comparing with the actual BGP data, we found that the observed P-P links are less than 30% of its range limit. By analyzing the relationships between the characteristics of observed ASes and the completeness of observed topology for those ASes, we found that the completeness of the topology is impacted by the distance to the BGP monitor, its adjacency, and other factors. We also propose an algorithm for monitor selection which detects 30% more P-P links compared to random selection.Second, we quantify the AS level routing policy changes. Routing policy changes may induce routing behavior changes, and mislead the corresponding researches. However, the research community has invested little effort into this topic. In this paper, we propose to model the routing decision process according to the preference to each neighboring AS, called neighbor preference, and prove the correctness of our model. By comparing the neighbor preference changes in successive days, we propose an algorithm to identify routing policy changes, and apply this algorithm to the Routeviews data in 2012. As a further analysis, we find that: at least 20% prefixes’ routing policy has changed at least once within 6 months; an AS’s routing policy changes usually with a constant rate, but non-tier1 ASes may endure a large scale routing policy changing event; AS business relationship changes and topology changes are not the main reasons of routing policy changes which indicate our method can review routing policy changes in a finer granularity.Third, we discuss the prediction of the AS level paths in dynamic network environment. Predicting the routing paths between any given pair of ASes is very useful in network diagnosis, traffic engineering, and protocol analysis. Existing methods address this problem by resolving the best path. However, due to route deficiencies, routing policy changes, and other causes, the best path changes over time. Consequently, existing methods for path prediction fail to capture routing dynamics. To predict AS-level paths in dynamic scenarios, we apply the neighbor preference model to extract the topology and route choice configurations from the observed BGP data. We further build the model with strict policies to ensure our model’s routing convergence; formally prove that it converges; and discuss the path prediction capturing routing dynamics by disabling links. By evaluating the consistency between our model and the actually observed paths, we show that our model outperforms the state-of-the-art work.Finally, we propose to detect BGP routing anomaly. Routing anomaly is very important for BGP, since BGP is vulnerable to malicious attacks and misconfigurations. If the detection result reports a lot of false positives, one may need further confirmation before utilizing the detection result. Consequently, avoiding false positive is very important to ensure the effectiveness of the route anomaly detection. In this paper, we propose routing anomaly detection methods for prefix hijack and route leak, and further prove that our detection results include no false positive.