The discovery of Autonomous Systems (ASes) interconnections and the inference of their commercial Type of Relationships (ToR) has been motivated by the need to accurately calculate AS-level paths. An inherent problem in current algorithms is their extensive use of heuristics, causing unbounded errors that are spread over all inferred relationships. We propose a near-deterministic algorithm for solving the ToR inference problem that uses the Internet’s core, a dense sub-graph of top-level ASes.
We test several methods for creating such a core and demonstrate the robustness of the algorithm to the core’s size and density, the inference period, and errors in the core. We evaluate the algorithm using AS-level paths collected from RouteViews BGP paths and DIMES traceroute measurements. Our proposed algorithm deterministically infers over 95% of the approximately 58,000 AS topology links using a week worth of data and as little as 20 ASes in the core. The algorithm infers 2–3 times more peer-to-peer relationships in links discovered only by DIMES than in RouteViews, validating the need for a broad and diverse Internet measurement effort. (pdf) Best Student Paper Award