  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.
