RoutingStateDistance

A path-based metric

Welcome.

Hello there. This is a companion page and repository for everything RoutingStateDistance-related.

Learn more about RSD or get in touch if you have other questions.

Visualization with RSD .

Routing State Distance

Routing State WHAT?!?
Scan through the difinition and read the paper for a complete study.

Code

Download the clustering and RSD computation code to reproduce our experiments or create your own.

Data

We make the RSD data publicly available for all to investigate and utilize.

Back to Top

About RSD

Abstract

Characterizing the set of routes used between domains is an important and difficult problem. The size and complexity of the millions of BGP paths in use at any time can hide important phenomena and hinder attempts to understand the path selection behavior of ASes. In this paper we introduce a new approach to analysis of the interdomain routing system designed to shed light on collective routing policies. Our approach starts by defining a new metric for ‘distance’ between prefixes, which we call routing state distance (RSD). We show that RSD has a number of properties that make it attractive for use in visualizing and analyzing the state of the BGP system. Further, since RSD is a metric, it lends itself naturally to use in clustering prefixes or ASes. In fact, the properties of RSD allow us to define a natural clustering criterion, and we show that this criterion admits to a simple clustering algorithm with provable approximation guarantees. We then show that by clustering ASes using RSD, one can uncover macroscopic behavior in BGP that was previously hidden. For example, we show how to identify groups of ASes having similar routing policies with respect to certain destinations, which apparently reflects shared sensitivity to economic or performance considerations. These routing patterns represent a considerable generalization and extension of the notion of BGP atoms to the case where routing policies are only locally and approximately similar across a set of prefixes.

Intuitive Definition of RSD

The RSD(a,b) is the number of positions where N(a) and N(b) differ -- where N(x) is a vector of next-hops each prefix uses to route to x.

Back to Top

Code.

Pivot Clustering

Matlab code to perform pivot clustering.
At a high level, a random prefix is picked as a 'pivot' and a cluster is created by grouping everything within a specified distance to the pivot. [See full paper for references and details]

Download

Overlap Clustering

Zip of matlab code to perform overlap clustering.
The key of this clustering is that each prefix can belong to more than one cluster -- resulting in clusters that overlap. [See full paper for references and details. Zip include ReadMe]

Download

RSD Computation

Code to generate the vector of pairwise rsds

Download
Back to Top

Data

Prefix List

Text file.
Lists all 135369 prefixes in the order they appear in the rows/columns of matrices

Download

Pairwise RSD

All pairwise rsd's.
Note: if rsd(i,j) is included, rsd(j,i) is NOT.

Download
Back to Top

Get in touch.

Questions. Comments. Proposals.

Our Team

Send us a message



Back to Top