The (thin) Bridges of AS Connectivity: Measuring Dependency using AS Hegemony

Inter-domain routing is a crucial part of the Internet designed for arbitrary policies, economical models, and topologies. This versatility translates into a substantially complex system that is hard to comprehend. Monitoring the inter-domain routing infrastructure is however essential for understanding the current state of the Internet and improving it. In this paper we design a methodology to answer two simple questions: Which are the common transit networks used to reach a certain AS? How much does this AS depends on these transit networks? To answer these questions we digest AS paths advertised with the Border Gateway Protocol (BGP) into AS graphs and measure node centrality, that is the likelihood of an AS to lie on paths between two other ASes. Our proposal relies solely on the AS hegemony metric, a new way to quantify node centrality while taking into account the bias towards the partial view offered by BGP. Our analysis using 14 years of BGP data refines our knowledge on Internet flattening but also exhibits the consolidated position of tier-1 networks in today's IPv4 and IPv6 Internet. We also study the connectivity to two content providers (Google and Akamai) and investigate the AS dependency of networks hosting DNS root servers. These case studies emphasize the benefits of the proposed method to assist ISPs in planning and assessing infrastructure deployment.