Internet AS-level Topology: Discovery and Analysis

Abstract

The Autonomous System (AS) level topology of the Internet is critical for future protocol design, performance evaluation, simulation and analysis. Despite significant research efforts over the past decade, the AS-level topology of the Internet is far from complete. Worse, recent studies highlight that the incompleteness problem is much larger than previously believed. In this thesis, we highlight the importance of two under utilized AS-level topology data sources: Looking glass (LG) servers and Internet Routing Registries (IRR). By querying Looking glass (LG) servers, we build an AS topology estimate of around 143 K AS links from 245 LG servers across 110 countries. We find 20 K new AS links in the AS topology from the LG servers. We observe 620 neighboring ASes of the LG servers that are not sharing their BGP traces with any of RouteViews [49], RIPE-RIS [65], and PCH [66]. We discover 686 new ASes in the AS topology from the LG servers that are hidden from other AS topologies. Overall, we conclude that collecting BGP traces from the LG servers help increase the narrow view of BGP observed from current BGP collectors [38]. However, the AS topology view from the LG servers suffers from limited vantage points of the LG servers and BGP export policies employed by the neighboring ASes of LG servers. Understanding the benefits and limitations of LG servers, we explore Internet Routing Registries (IRR), which are a set of databases used by ASes to register their inter-domain routing policies. More specifically, we first present a methodology to extract AS-level topology (e.g., bilateral and multilateral peering links) from the IRR. We extract 610 K AS links from the IRR dataset of Nov. 1st, 2013

68% of which can be matched in BGP, traceroute, and in the cliques of Internet eXchange points (IXPs). We find active usage of the IRR by member ASes of IXPs, which results in inferring peering matrices of many large and small IXPs. Finally, we present a methodology to infer business relationships between ASes using routing polices stored in the IRR. We show that the overall accuracy of our algorithm is comparable (97% for p2c, 95% for p2p links) to the existing algorithms, which infer AS relationships using BGP AS paths. We conclude that the IRR is a strong complementary source for better understandings of the structure, performance, dynamics, and evolution of the Internet since it is actively used by a large number of operational ASes in the Internet.