Thursday, September 4, 2008

On Inferring Autonomous System Relationships in the Internet (UMass)

The paper is based on a very nifty idea that one can use BGP routing table entries to infer AS relationships based on the provider-customer-peer-sibling business model. The inference algorithms presented are heuristic-based. Its targeted the method on data from the Route View Project ( and verified its results with high accuracy (>90%) with one particular ISP, AT&T.

It first shows a nice overall picture of the structure of inter-domain routing. It follows with very in-depth details on the BGP protocol and addresses the role of some of centralized efforts, such as IRR and ARIN, for inter-network routing. The introduction and background sections were very helpful in bringing context and understanding for different agencies in the network, although i feel that the author abused the formal proofs and notations quite a bit. The overall value of this paper is really seeing the way networks are connected really conforms to what the underlying business model is. I think the paper should stay -- but only under the condition that it is to bring context rather than spanking students with the unnecessary formalisms.

Most of the research mentioned in related work seem to be a reverse engineering for discovering connectivity and by-passing the administrative/policy layer that BGP imposes. It suggests that BGP could be designed better in the first place to export connectivity information and allow these analyses more formally.

No comments: