AS Relationships -- with geographic annotations
The Internet is composed of thousands of ISPs that operate individual parts of the Internet infrastructure. ISPs engage in both formal and informal relationships to collectively and ubiquitously route traffic in the Internet. These relationships turn into reality when two companies create physical connections between their networks, either by simply connecting two routers in a single location, or connecting pairs of routers in many different cities. Understanding the geographic nature of these relationships can facilitate activities such as: realistic simulation of AS path prediction; application performance estimation; predicting the likelihood that two ASes will interconnect; and visualizing the geographic distribution of networks.
We combined inference techniques that leveraged four types of data: BGP Communities (BC), Looking Glass servers (LG), Multilateral Peering (MLP), and Macroscopic Internet Topology Data Kit (ITDK).
The first geolocation technique uses BGP communities. A BGP community is an optional transitive BGP attribute that contains a string of 32-bit numeric values. Communities attached to prefix advertisements encode meta-data about the advertised prefixes. Typically, the first 16 bits of each community value represents the ASN that uses the community, while the last 16 bits encode a value with predetermined (and often publicly documented) semantics. One popular application of BGP communities is to annotate prefixes with the geographic location of the border router where the prefix advertisement first reaches the AS. BGP communities are not entirely standardized. Each operator may use different values to encode geographic information at various granularities. To interpret community values, we constructed a dictionary of community definitions collected by IRR records and from (scraping) web pages of NOCs (Network Operation Centers) as explained in [Giotsas 2014]. We used the communities that encode a geographic location at city-level granularity (or finer) to parse BGP records extracted from the RouteViews and RIPE RIS collectors. We mapped an AS link to the location encoded by a community if the near-end AS of the AS link is the same as the first 16 bits of the geo-tagging community.
The second technique we used to geolocate AS links uses Looking Glass (LG) servers to extract the connectivity of an AS at a particular location, using the Periscope platform [Giotsas 2015]. LGs offer web-based interfaces to BGP routers which often allow the execution of the show ip bgp summary command, which provides a list of AS adjacencies at the particular router. When the LG also provides the location of the router, we can geolocate the adjacencies returned by the show ip bgp summary command to the location of the router from which the command was executed.
A third technique we used to geolocate AS links relied on inferences of multilateral peering (MLP) links at IXP route-servers; we then mapped the interconnection location to the route server's location. To infer multilateral peering, we queried available IXP LGs for their AS-level adjacencies, the prefixes advertised by each neighbor, and the prefix redistribution communities set on each prefix according. By combining these data as explained in [Giotsas 2013], we inferred the per-prefix advertisement control policies that each AS has applied. If two ASes connect to the same route server, and have configured their policies to allow each other to receive their advertisements, then we infer that a peering link exists over that route server, and consequently at the city where the route server is located.
A fourth technique we use is to examine geolocation links connected to edge ASes. We define edge ASes as an AS with no other ASes in its customer cone. This means that the AS does not provide transit for any other AS and is mostly likely in a single location. Additionally, NetAcuity must geolocate all of the AS'es prefixes to a single location. Since this AS is in a single location, any link connected to it must be at its location.
The final technique we used relies on AS link inferences in CAIDA's Macroscopic Internet Topology Data Kit (ITDK). The ITDK is an Internet-wide router-level map constructed from traceroutes taken from from CAIDA's Archipelago monitors. The ITDK assigns each router a single AS based on the methodology presented in [Huffaker 2010]; then, if a plurality of the router's interfaces are assigned to the same geographic location by NetAcuity, we assign the router that geographic location. We infer an AS link between two ASes if there exists a direct link between the two ASes in the ITDK, and both routers at either end of that link share the same location.
|[Giotsas 2013]||Giotsas, Vasileios, Shi Zhou, and Matthew Luckie. "Inferring multilateral peering." In Proceedings of the Ninth ACM conference on Emerging networking experiments and technologies, pp. 247-258. ACM, 2013.|
|[Giotsas 2014]||Giotsas, Vasileios, Matthew Luckie, and Bradley Huffaker. "Inferring complex AS relationships." Proceedings of the 2014 Conference on Internet Measurement Conference. ACM, 2014.|
|[Giotsas 2015]||Giotsas, Vasileios, Amogh Dhamdhere, and K. C. Claffy. "Periscope: Unifying Looking Glass Querying." International Conference on Passive and Active Network Measurement. Springer International Publishing, 2016.|
|[Huffaker 2010]||Bradley Huffaker, Amogh Dhamdhere, Marina Fomenkov, and K.C. Claffy " Toward Topology Dualism: Improving the Accuracy of AS Annotations for Routers" Proceeding of the Passive and Active Network Measurement Workshop (PAM), Apr 2010.|