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

Review: Interdomain Internet Routing

The lecture entitled "Interdomain Internet Routing", provided a thorough understanding of how the internet works and operates in the real-world. It ponders on the interconnection of networks (i.e., how routers hook up with other routers and their respective exchange of routing protocols) in order to provide internet service [1].

The internet is an interconnection of unequal networks [2] and is administered by different domains and commercial enterprises. Hence, business competition and issues of trust arise amongst Internet Service Providers (ISPs) in providing global connectivity to their subscribers.

Throughout the lecture, more detailed Internet routing infrastructure and issues were discussed. Among the interdomain routing concepts addressed were Autonomous Systems (ASes), Inter-AS relationships and features of the Border Gateway Protocol (BGP). Under Inter-AS relationships, the lecture focused on peering vs transit and exporting and importing routes (route filtering). Also explained were design goals, protocol, disseminating routes within AS, policy expression (filters and rankings) and exchanging reachability of BGP. Failover and Security including Multi-homing, Convergence and Correctness Problems were also addressed.

It is noted that BGP is a simple protocol but its operation was said to be extremely complex. I wonder whether its design goals are still achievable with the growing internet demand? Will it still scale? How about being flexible? How will it handle security and failure? Are there any alternatives or recent modifications on its protocol? Is there a chance that the cost of internet service becomes cheaper or even free?

References:

[1] Hari Balakrishnan and Nick Feamster, "Lecture 4: Interdomain Internet Routing"
[2] http://www-inst.eecs.berkeley.edu/~ee122/sp04/network%20layer2_print.pdf