The Internet is composed of networks that rely on each other to provide global connectivity. Consequently the reachability of a network depends greatly on the connectivity of other networks, and the understanding of interdependencies between Autonomous Systems (ASes) is essential for deployment decisions, routing decisions, and connectivity troubleshooting.

Our new tool measures AS dependencies and addresses the following questions:

• What are the common transit networks to my AS?

• How much does my AS depend on these transit networks?

• How many networks depend on a certain transit network?

Our approach is simple: we digest Border Gateway Protocol (BGP) data into AS graphs and measure nodes centrality (i.e. the likelihood of an AS to lie on paths between two other ASes).

For example, the following graph shows AS paths between BGP monitors (blue nodes) and the University of Tokyo (red node, AS2501). All other nodes in the graph represent transit networks seen on the way to the University of Tokyo.

Figure 1: AS paths between BGP monitors (blue nodes) and the University of Tokyo (red node) as seen in BGPlay

In this graph central nodes (e.g. AS2914 and AS2907) represent common transit providers towards the origin AS. This example shows that the reachability of the University of Tokyo is largely depending on SINET (AS2907) and NTT (AS2914). To better quantify these dependencies we have devised a metric called AS hegemony.

This is a new way to quantify node centrality that takes into account the partial and self-centric view offered by BGP monitors. AS hegemony ranges between 0 and 1 and is intuitively interpreted as the average fraction of paths crossing a node. The details are available in our research report, presented at PAM’18.

In the above example, AS2907 has an hegemony equal to 1, meaning that it is usually present in all AS paths between a randomly selected BGP monitor and the University of Tokyo. AS2914 has an hegemony of 0.8 as it is seen on most paths, and other ASes have values closer to 0.

Using this new metric we can also monitor AS interdepencies over time. For example, we can check if NTT and SINET are always the main transit networks for the University of Tokyo. Or we can monitor the number of ASes that rely on NTT. Significant changes in these AS dependencies would reveal routing changes that can have a certain impact on end users.

A look at some ASes dependencies

The above example for the University of Tokyo was fairly easy, the university depends mainly on the main academic network  in Japan (SINET) which depends mainly on the main national Internet service provider (NTT).

Some cases are not that straightforward, especially for large networks with multiple points of presence. Good examples are ASes hosting DNS root servers. These ASes usually announce anycasted addresses from numerous locations. Identifying the main transit networks for these ASes can be a real challenge, but they are crucial to improve resiliency.

F-root

To illustrate this we take a look at the dependencies of the AS originating the IP address of the F-root server (AS3557) during the deployment of new instances in Cloudflare.

Figure 2: Dependencies of F-root in the Cloudflare AS

In early 2017, we observed three dominant transit ASes for the network hosting the F-root server. AS30132 and AS1280 are direct upstream networks managed by ISC, the administrator of the F-root server. AS6939 (Hurricane Electric) is the main provider for AS1280, and is found in about a third of the AS paths towards the F-root server. Starting in March 2017, Cloudflare (AS13335) starts providing connectivity to new F-root instances. This new infrastructure is clearly visible in our results: Cloudflare's hegemony is fluctuating around 0.2 and seems to divert traffic from other instances as the three other transit networks have their hegemony proportionally decreased. From these results we deduce that the addition of Cloudflare has successfully reduced F-root dependencies on other ASes.

Level(3) BGP route leak

AS interdependency changes can also reveal significant routing anomalies. The following figure shows the AS hegemony changes during the Comcast outage caused by Level(3) BGP route leak on 6 November 2017.

Figure 3: AS hegemony changes during the Comcast outage on 6 November 2017

AS33651 is one of Comcast’s ASN that had leaked prefixes. This AS is usually accessed via Comcast main AS (AS7922), but during the BGP route leak Level(3) (AS3356) became the main transit network for AS33651 which caused significant spikes in packet loss and latency.

Your AS / Online results

We provide results for all public ASNs on http://ihr.iijlab.net through a web interface and a REST API. For example, http://ihr.iijlab.net/ihr/15169/asn/ shows that Google's main AS (AS15169) has no dependencies on other networks and it provides connectivity to a handful of other ASes managed by Google.

These results are updated daily, hoping that it will help network operators to understand their AS dependencies. In order to improve this service we also encourage operators to send us feedback.

Please note that Emile Aben presented this topic during RIPE 76.