On Inferring Autonomous System Relationships in the Internet

Summary
This paper presents an overview of some BGP concepts, some formal definitions of properties of graphs of Autonomous Systems (AS), and and algorithm for heuristacally inferring relationships. These relationships are often not made public as they are business relationships, so the ability to infer them helps us gain a deeper understanding of Internet topology.

An AS graph is built from public BGP routing tables. The graph's edges are classified into one of three types:

• provider-to-customer - the only directed edge, indicates a relationship in which the provider provides service to a paying customer
• peer-to-peer - edges indicating peering agreements between ASs
• sibling-to-sibling - edges between siblings

By splitting the graph into trees the authors are able to work out uphill and downhill paths. Uphill paths are made up of edges that are customer-to-provider or sibling-sibling edges. A downhill path a path of provider-to-customer edges or sibling-to-sibling edges. By looking at maximal paths, and noting that providers should have a higher degree in the graph, we can infer what relationships exist between ASs. Information about what ASs provide transit to other ASs can be used to discover peering relationships.

The authors test their inferred relationships on Route Views data, and verify it by asking AT&T to confirm their results. They classify 90.5% of edges as provider-to-customer, less than 1.5% as sibling-to-sibling edges, and less that 8% as peer-to-peer edges. The AT&T verification shows that the majority of their edges are classified correctly. 100% of their customer relations are correct, which is already 90.5% of all the edges they classified. However, the provider info is wanting. They infer that AT&T has one provider while in reality it has none, meaning they get 0% on that metric. The sample size isn't really big enough to tell us anything about the efficacy of their provider inference however.

Comments
While this paper is clearly quite an achievement, I did not find it all that interesting. We've already looked at BGP so that part of the paper didn't give me much, and the rest of the paper is pretty heavy theoretical going with not much of payoff.

I also found the verification of the result pretty unsatisfactory. While I realize that AT&T cannot release real data so show more detailed results, the very high level percentage correct figures left me wanting more. The 0% correct result on provider inference is a pretty glaring example of the problem with this verification method.

This felt like a paper more useful to someone deeply involved in this particular area, and less well suited to a general networking class. I would remove it from the syllabus.