On Inferring Autonomous System Relationships in the Internet

The author discusses a heuristics based algorithm to determine AS relationships (which are often kept under some non-disclosure agreement for business purposes).

The author first provides necessary background information regarding Internet architecture and BGP routing policies and tables. The author then gives detailed definitions that capture certain graph phenomenon  (downhill versus uphill edges, etc) before eventually discussing the algorithm for classifying transit pairs and edges (provider-to-customer, etc). The author then shows how well their algorthim performed experimentally on data collected from the Route Views server in Oregon.

This paper has a fairly substantial amount of definitions and explanations, which made its overall impression be a bit overwhelming. Unfortunately, it seemed to be the case that the author felt he needed to provide the necessary background information for his audience. That being said, there is a lot of good content that will probably be helpful in getting people to communicate about these issues. My only real critique of the paper was that I had a hard time relating to the motivation of the work and how it will enable future work (probably because this isn't my area).

That being said the paper still provides interesting information (section A. Internet Archtiecture and section B. Routing Policies and BGP Routing Tables) that I found valuable for understanding certain "basic" principles. For example, even statements like "the scalability of the internet routing protocol depends on the contiguousness of IP addresses" which are obvious in retrospect, seemed like a nice and helpful reminder about the "why" of certain Internet decisions.

Other than how this work will enable future work (which as I admitted before I don't completely understand), I think the important ramifications of this work is reinforcing how routing policies can sometimes give you results which are not, for certain customers, preferable. For example, the paper reinforced how local pref attributes override shortest path length attributes! This means my packet may take longer to get where I want it to go because my ISP makes more money by sending it the long way. In fact, it would be really interesting, and cool, to see if we could some how measure this (is it a really pervasive issue in the Internet? or because of the topology this issue rarely comes up?).