Thursday, September 4, 2008

On Inferring Autonomous System Relationships in the Internet

BGP allows autonomous systems to make their own routing decisions, and these are often based on commercial considerations. This paper uses a set of publicly available BGP routes to infer relationships among ASes. The paper does a good job of introducing BGP’s functioning.

The inference heuristics rely on BGP being a path-vector protocol. The heuristics are based on two observations: - (1) it is not possible for a path to go from a provider to customer and then to a provider (the customer has to unfairly pay for this transit!), and (2) a peering edge cannot come after a provider to customer edge (as the customer now has to pay his provider for providing peering transit). The degree in the AS-graph is also used to infer relationships between ASes. The inferences are verified using data from AT&T, and they match.


1. Is this the first/best paper talking about inferring AS relationships? Did this lead to better simulations for future research? It would be interesting to know what followed up after this work.

2. While this is definitely good work, I would suggest taking this off the reading list. This seemed too narrow in scope, and I did get bogged down in its formal details; we should have a paper that is more generic. Something like Hari’s paper about finding BGP misconfigurations might be better.

1 comment:

Randy H. Katz said...

While not the first paper on this topic, Gao took it to a whole new level. Follow on papers improved her work, but really it was just a refinement. The reason why I like this work is that it shows how hard it is to determine the structure of the Internet while working from the edge in. I'll certainly consider your suggestion of including the BGP misconfiguration paper ... if they let me teach this again!