Summary:
This paper introduces a heuristic algorithm which is able to infer the relationships among Internet Autonomous Systems (AS). The inter-AS agreements in today's Internet takes one of the forms of costumer-provider, peering, mutual transit and mutual backup. The importance of this information lies on the fact that inter-domain routing (BGP) is a policy based routing scheme and therefore connectivity and reachability are not equivalent. Furthermore ISPs do not expose their contractual agreements for most of the time and therefore such algorithms can be quite useful in better understanding the state of the internet and improving it.
The algorithm works by deriving an annotated AS graph with the edges indicating provider-customer (~customer-provider), peer-to-peer and sibling-to-sibling (mutual transit/backup) relationship which is compatible with the BGP route tables. Each route in a route table has been a result of recursive export policies enforced by different ASs. The route entries can be divided onto (possibly) UpHill Path which only traverses through customer-provider and sibling-to-sibling edges (possibly) followed by a peer-to-peer edge (possibly) followed by a downhill path which only contains provider-customer or sibling-to-sibling edges.
Combining this information with size/degree proportionality of the ASs and the possible relationships the proposed algorithm is able to infer the AT&T ISP relationships with its neighboring ASs with 90.5% accuracy and more than 50% siblings are confirmed through the WHOIS lookup service (which I'm not sure if this last number indicates a good performance in sibling-to-sibling prediction). This information can be used by ISPs to possibly debug the erronous entries in their BGP route tables and plan for future contractual agreements.
Critique:
I found this paper interesting but have hoped for better quantitative evaluation of importance/relevance and impact of such algorithms (even though I agree with the general arguments). In general a nice paper but would agree for dropping it for a more exciting paper.
No comments:
Post a Comment