The Skeleton of the Internet

Research works concerning AS (Autonomous Systems) level Internet topology measurements typically aim at obtaining near-complete maps of the AS structure. In this paper, we take a fundamentally different approach by inspecting several concurrently visible local views of the AS graph stored at individual BGP route servers. We find that each of these views exhibits the characteristic properties of complex graphs having power-law degree distribution, large clustering coefficient and the small world property. As a main contribution, the intersection of these views is investigated to identify the skeleton of the Internet consisting of edges seen by most of the ASes. Our measurements support the surprising claim that this skeleton is a scale-free complex network, having a giant connected component with a dense part in its heart forming the critical AS level core. We identify the edges in the skeleton as critical infrastructure, any changes of which induces an Internet-wide effect with BGP updates propagating to all ASes. Finally, we reinterpret the path inflation metric using the local view approach and show that local path inflation can be very diverse in different ASes.