AS hegemony: measuring AS interdependence

By on 30 May 2018

Category: Tech matters

Tags: , , ,

2 Comments

Blog home

How does your network depend on other networks? In this article, we present a new tool that helps you measure Autonomous System (AS) dependencies.

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 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 (that is, 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 (for example, 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 2018 [PDF 4.6 MB].

In the above example, AS2907 has a 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 a 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 interdependencies 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 anycast 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 the 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 ASNs that had leaked prefixes. This AS is usually accessed via Comcast’s main AS (AS7922), but during the BGP route leak Level(3) (AS3356) it 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.

Watch Emile Aben’s presentation on this topic at RIPE 76.

Original post appeared on RIPE Labs.

Romain Fontugne is a senior researcher at IIJ Research Lab, Japan, who focuses on Internet measurements, traffic analysis, and network security.

Rate this article

The views expressed by the authors of this blog are their own and do not necessarily reflect the views of APNIC. Please note a Code of Conduct applies to this blog.

2 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

Please answer the math question * Time limit is exhausted. Please reload CAPTCHA.

Top