AS relationships: inference and validation

By Xenofontas A. Dimitropoulos, Dmitri V. Krioukov, Marina Fomenkov, Bradley Huffaker, Young Hyun, K. Claffy, George F. Riley. CCRV, 2006

384 citations recorded by the source corpus.

Research on performance, robustness, and evolution of the global Internet is fundamentally handicapped without accurate and thorough knowledge of the nature and structure of the contractual relationships between Autonomous Systems (ASs). In this work we introduce novel heuristics for inferring AS relationships. Our heuristics improve upon previous works in several technical aspects, which we outline in detail and demonstrate with several examples. Seeking to increase the value and reliability of our inference results, we then focus on validation of inferred AS relationships. We perform a survey with ASs' network administrators to collect information on the actual connectivity and policies of the surveyed ASs. Based on the survey results, we find that our new AS relationship inference techniques achieve high levels of accuracy: we correctly infer 96.5% customer to provider (c2p), 82.8% peer to peer (p2p), and 90.3% sibling to sibling (s2s) relationships. We then cross-compare the reported AS connectivity with the AS connectivity data contained in BGP tables. We find that BGP tables miss up to 86.2% of the true adjacencies of the surveyed ASs. The majority of the missing links are of the p2p type, which highlights the limitations of present measuring techniques to capture links of this type. Finally, to make our results easily accessible and practically useful for the community, we open an AS relationship repository where we archive, on a weekly basis, and make publicly available the complete Internet AS-level topology annotated with AS relationship information for every pair of AS neighbors.

Subfields: Artificial Intelligence, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/41ce63a9f52ed060d6cbddc94d9805c60d809bef

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

Power-Law Distributions in Empirical Data (2007, background): “In some cases it is known that the sampling procedure used to obtain these subsets may be biased, as, for example, in the protein interactions [56], citations and authorships [9], and the Internet [2, 15].”
Can internet video-on-demand be profitable? (2007, methodology): “Finally, we point out that the inferred AS relationships from CAIDA [10], which we used in this study, may be very conservative.”
A Survey of BGP Security Issues and Solutions (2010, methodology): “One drawback of the registry model is that corporations often consider their routing policies and topological information to be proprietary (and are thus reluctant to share it), though measurement tools such as Rocketfuel [13] provide relatively accurate maps of an ISP’s internal topology, and algor”