Review: On Inferring Autonomous System Relationships in the Internet

The paper presented heuristic algorithms (i.e., Basic Algorithm, Refined Algorithm and Final Algorithm) that infer the augmented AS graph from BGP routing tables, which classified an interconnected AS pair into customer-provider, peering and sibling relationships [1].

They performed experimental study of AS relationships in the Internet using BGP routing tables, which were retrieved from the Route Views server in Oregon. Their inference results were verified with AT&T internal information and, overall, classifies more than 90.5% of AS pairs into provider-customer relationships, less than 1.5% of AS pairs into sibling relationships, and less than 8% of AS pairs into peering relationships. Also, they were able to identify routing table entries that stem from unusual AS relationships or router misconfigurations.

The rest of the paper elaborated on (a) overview of interdomain routing and related work, (b) AS relationships and routing table entry patterns, (c) heuristic algorithms for inferring AS relationships, (d) inferring AS relationships in the internet and (e) conclusion and future work.

The experiment is beneficial for ISPs in improving their routing policies and configuration (i.e., filtering of routes) as well as for planning their future contractual agreements with other ISPs. Ultimately, end-users will be mutually benefited if Internet routing will become more reliable. Hopefully, intelligent systems/applications can be incorporated in automating routing policies.

Reference:

[1] Lixin Gao, On Inferring Autonomous System Relationships in the Internet, IEEE/ACM Transactions on Networking, vol.9, no.6, p.733-745, December 2001