Applications

Routing State Distance

A New Metric for Understanding Internet Routing

By: Mat Ford

Date: July 1, 2013

line break image

The Internet Research Task Force (IRTF) has been host to some of the most interesting talks offered at recent IETF meetings thanks to the presentations given by winners of the Applied Networking Research Prize (ANRP). At the IETF86 meeting in Orlando, Florida, Gonca Gürsun, a Ph.D. 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 for analysing BGP routing policies and can also be used for visualising networks and routes, detecting patterns in routing behaviour, and providing new insights about the routing fabric of the Internet. RSD is roughly a measure of the similarity or dissimilarity of routes to a given destination network (for a full explanation, see the paper for which Gürsun won her award, Routing State Distance: A Path-based Metric for Network Analysis[1]). This new way of looking at the Internet enables us to see some interesting patterns.

Using 48-million routing paths collected from Routeviews and Réseaux IP Européens (RIPE) Routing Information Service (RIS) projects with more than 359 Internet vantage points, Gürsun 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 macroscale 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! Gürsun’s research also reveals smaller clusters that 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 her research include going beyond visualisation to detecting routing instabilities and anomalies. Code, data, and more information are available at http://csr.bu.edu/rsd. Gürsun’s slides can be found at http://www.ietf.org/proceedings/86/slides/slides-86-irtfopen-1.pdf.

ANRP prizes will be awarded at the two remaining IETF meetings this year. The call for nominations for the 2014 award cycle is open until 30 November; nominations can be submitted online at http://irtf.org/anrp/2014/.

References

1. 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. http://cs-people.bu.edu/goncag/papers/imc12-rsd.pdf