Inferring AS Relationships in the Internet

In this paper, the authors attempt to "map" the relationships between autonomous systems and the ways they interact through routing. First, the paper defines the different kinds of relationships between AS's, similar to how the Interdomain paper defines them, although this paper has several additional relationship types. Then, the paper shows how to construct a graph of the AS's where each AS is a vertex and their relationships are expressed as edges.

This is done by considering the way routing is related to the relationship. For example a customer will not want to route its provider's routes; seeing how the routing between the two is expressed tells us something about how the AS's are related. By using heuristics, the authors are able to map the AS's quite well.

Admittedly, some of the details were over my head in terms of how the graph is constructed, but I understood the gist. This is not a fault of the paper, but moreso due to my relative ignorance of BGP. I understood most of how the policies express relationships; I think the paper does a good job of formally detailing how policy and relationship can be used to interchangably.

The confirmation of their results, however, left me scratching my head. "As much as 99.1%" is quite an ambiguous number; this could be anything between 0 and 99.1. Furthermore, they don't specify what kinds of information AT&T internally has, or how it got it--- are their relationships accurate? If they only deal with AT&T's connectivity, then we can assume they are accurate, but what percentage of inferences does that cover? I was unsatisfied by their metrics in this sense.