Although traceroute has the potential to discover AS links that are invisible to existing BGP monitors, it is well known that the common approach for mapping router IP addresses to AS numbers based on BGP routing tables is highly error-prone. We develop a systematic framework to quantify the potential errors of traceroute measurement in AS-level topology inference. In comparing traceroute-derived AS paths with BGP AS paths, we take a novel approach to identifying mismatched path segments and then inferring the causes of these mismatches through a set of tests. Our results show that about 60% of mismatches are due to routers using IP addresses belonging to peering neighbors. This result helps settle a debate in previous works regarding the major cause of errors in traceroute measurement. With the approximate ground truth of the ASes with BGP monitors inside, we identify the inaccuracy of publicly available traceroute-derived topology datasets and find that between 8% and 42% of AS adjacencies on the monitored ASes are false. With a new method to characterize AS links, we show that the derived (false) links between Tier-1/large ISPs and their customers' customers appear more frequently than real links do.

Despite significant efforts to obtain an accurate picture of the Internet's actual connectivity structure at the level of individual autonomous systems (ASes), much has remained unknown in terms of the quality of the inferred AS maps that have been widely used by the research community. In this paper we assess the quality of the inferred Internet maps through case studies of a set of ASes. These case studies allow us to establish the ground truth of AS-level Internet connectivity between the set of ASes and their directly connected neighbors. They also enable a direct comparison between the ground truth and inferred topology maps and yield new insights into questions such as which parts of the actual topology are adequately captured by the inferred maps, and which parts are missing and why. This information is critical in assessing for what kinds of real-world networking problems the use of currently inferred AS maps or proposed AS topology models are, or are not, appropriate. More importantly, our newly gained insights also point to new directions towards building realistic and economically viable Internet topology maps.

A prefix hijack attack involves an attacker announcing victim networks' IP prefixes into the global routing system. As a result, data traffic from portions of the Internet can be diverted to attacker networks. Prefix hijack attacks are a serious security threat in the Internet and it is important to understand the factors that affect the resiliency of victim networks against these attacks. In this paper, we conducted a systematic study to gauge the effectiveness of prefix hijacks launched at different locations in the Internet topology. Our study shows that direct customers of multiple tier-1 networks are the most resilient, even more than the tier-1 networks themselves. Conversely, if these customer networks are used to launch prefix hijacks, they would also be the most effective launching pads for attacks. We verified our results through case studies using real prefix hijack incidents that had occurred in the Internet.

The global Internet routing infrastructure is a large and complex distributed system where routing changes occur constantly. Our objective in this paper is to develop a simple and effective inference solution that can identify the AS or inter-AS link failures that trigger large scale routing changes in near realtime. We achieve this goal through a novel approach based on link weights. We measure the weight of each inter-AS link by the number of routes carried over that link, and keep track of its expected value and variance. We then correlate the weight changes of adjacent links and use a min-cut heuristic to find candidates for the origin of change. This work makes three contributions. First, we keep track of link weights rather than the routes of individual prefixes and thus our analysis is based on an aggregate view. Second, we use expected value and mean deviation of the link weights to identify routing events and distinguish route changes caused by failures from those by recoveries. Finally we use a min-cut heuristic based on the classification of routing events to accurately identify the AS or inter-AS link most likely responsible for the observed route changes. We verified our design using BGP data collected from operational Internet. Our efficient and accurate routing diagnosis solution can greatly help us gain better understanding of the dynamics in the operational Internet.

In this paper we propose a new routing protocol and address scheme, geographically informed inter-domain routing (GIRO). GIRO departs from previous geographic addressing proposals in that it uses geographic information to assist, not to replace, the provider-based IP address allocation and policy-based routing. We show that, by incorporating geographic information into the IP address structure, GIRO can significantly improve the scalability and performance of the global Internet routing system. Within the routing policy constraints, geographic information enables the selection of shortest available routing paths. We evaluate GIRO'S performance through simulations using a Rocketfuel-measured Internet topology. Our results show that, compared to the current practice, GIRO can reduce the geographic distance for 70% of the existing BGP paths, and the reduction is more than 40% for about 20% of the paths. Furthermore, encoding geographic information into IP addresses also enables GIRO to apply geographical route aggregation, and a combination of geographic and topological aggregation can lead to 75% reduction of the current BGP routing table size.

Characterizing the evolution of Internet topology is important to our understanding of the Internet architecture and its interplay with technical, economic and social forces. A major challenge in obtaining empirical data on topology evolution is to identify real topology changes from the observed topology changes, since the latter can be due to either topology changes or transient routing dynamics. In this paper, we formulate the topology liveness problem and propose a solution based on the analysis of BGP data. We find that the impact of transient routing dynamics on topology observation decreases exponentially over time, and that the real topology dynamics consist of a constant-rate birth process and a constant-rate death process. Our model enables us to infer real topology changes from observation data with a given confidence level. We demonstrate the usefulness of the model by applying it to three applications: providing more accurate views of the topology, evaluating theoretical evolution models, and empirically characterizing the trends of topology evolution. We find that customer networks and provider networks have distinct evolution trends, which can provide an important input to the design of future Internet routing architecture.

A number of previous measurement studies [10, 12, 17] have shown the existence of path exploration and slow convergence in the global Internet routing system, and a number of protocol enhancements have been proposed to remedy the problem [21, 15, 4, 20, 5]. However all the previous measurements were conducted over a small number of testing prefixes. There has been no systematic study to quantify the pervasiveness of BGP slow convergence in the operational Internet, nor there is any known effort to deploy any of the proposed solutions.In this paper we present our measurement results from identifying BGP slow convergence events across the entire global routing table. Our data shows that the severity of path exploration and slow convergence varies depending on where prefixes are originated and where the observations are made in the Internet routing hierarchy. In general, routers in tier-1 ISPs observe less path exploration, hence shorter convergence delays than routers in edge ASes, and prefixes originated from tier-1 ISPs also experience less path exploration than those originated from edge ASes. Our data also shows that the convergence time of route fail-over events is similar to that of new route announcements, and significantly shorter than that of route failures, which confirms our earlier analytical results [19]. In addition, we also developed a usage-time based path preference inference method which can be used by future studies of BGP dynamics.

We conduct a systematic study on the pervasiveness and persistency of one specific phenomenon in the global routing system: a small set of highly active prefixes accounts for a large number of routing updates. Our data analysis shows that this phenomenon is commonly observed from monitors in many different ISPs, and exists throughout our 3-year study period. The analysis further shows that the majority of these prefixes are highly active for only one or a few days, while a small number of them are persistently active over long period of time. Case studies demonstrate that the causes of these high routing activity include topological failures, BGP path exploration, protocol defects, and the failure of turning on protection mechanisms.