An accurate Internet topology graph is important in many areas of
networking, from deciding ISP business relationships to diagnosing
network anomalies. Most Internet mapping efforts have derived the
network structure, at the level of interconnected autonomous systems
(ASes), from a limited number of either BGP- or traceroute-
based data sources. While techniques for charting the topology
continue to improve, the growth of the number of vantage points is
significantly outpaced by the rapid growth of the Internet.
In this paper, we argue that a promising approach to revealing the hidden areas of the Internet topology is through active measurement from an observation platform that scales with the growing In- ternet. By leveraging measurements performed by an extension to a popular P2P system, we show that this approach indeed exposes significant new topological information. Based on traceroute measurements from more than 992, 000 IPs in over 3, 700 ASes dis- tributed across the Internet hierarchy, our proposed heuristics identify 23, 914 new AS links not visible in the publicly-available BGP data ĘC 12.86% more customer-provider links and 40.99% more peering links, than previously reported. We validate our heuristics using data from a tier-1 ISP and show that they correctly filter out all false links introduced by public IP-to-AS mapping. We have made the identified set of links and their inferred relationships publically available.