Routing State Distance – a new metric for understanding Internet routing

The Internet Research Task Force (IRTF) has been hosting some of the most interesting talks at recent IETF meetings as the Applied Networking Research Prize winners are given the stage to present the work for which they have been recognised. At the IETF86 meeting in Orlando earlier this month, Gonca Gürsun, a PhD student from Boston University and the most recent recipient of the ANRP, discussed a new metric for analysing the structure of Internet routing.

The Routing State Distance (RSD) metric is a tool to analyse BGP routing policies and can be used for visualisation of networks and routes, detecting patterns in routing behaviour, and provides new insights about the routing fabric of the Internet. RSD is roughly a measure of how similar or dissimilar routes to a given destination network are (for a full explanation, see the paper for which Gonca won her award: Gonca Gürsun, Natali Ruchansky, Evimaria Terzi and Mark Crovella. Routing State Distance: A Path-based Metric For Network Analysis. Proc. ACM Internet Measurement Conference (IMC), November 2012, Boston, MA, USA). This way of looking at the Internet allows us to see some interesting patterns emerge.

Using 48 million routing paths collected from Routeviews and RIPE RIS projects with over 359 Internet vantage points, Gonca and her collaborators set out to understand what RSD could reveal about the structure of Internet routing and the early results are fascinating.

RSD visualisation reveals clusters of networks that make similar routing decisions. The two very distinct clusters in the Figure illustrate the effect of Hurricane Electric’s very open peering policy. Sources always route through Hurricane Electric if the option exists. This is a macro-scale cluster arising from the peering policy of a single operator and it is visible in any random sample from the dataset – a true Internet-wide phenomenon! Gonca’s research also reveals smaller clusters which seem to be driven more by geopolitical concerns and the affinities of operators from specific countries.

RSD is an original and very interesting way to look at the Internet’s routing structure. Promising future directions for the research include going beyond visualisation to detecting routing instabilities and anomalies. Code, data and more information is available at: Gonca’s slides are at:

ANRP prizes will be awarded at the two remaining IETF meetings this year, and the call for nominations for the 2014 award cycle will open after the summer.