Internalizing Interdomain Internet Routing

A Review on Interdomain Internet Routing

Hari Balakrishnan and Nick Feamster, authors of Interdomain Internet Routing, [1] explains how Internet Service Providers, autonomous from each other, exchange routing information and packets among them which influence its commercial value among systems and to their respective customers.

Summary
In Internet routing infrastracture, a large number of unequal (in terms of resources and capabilities) and competing ISP are actually cooperating to provide global connectivity that the end users enjoy. Each ISPs have different policies for exchanging and selecting routes.

There are two ways how autonomous systems interconnect with each other – (1) provider-customer or the transit and (2) provider-provider or the peering. Transit involves financial matters among clients and service providers while peering involves reciprocal agreements that may or may not include financial settlements. In the latter case, involved providers have mutual access to a subset of each others’ routing tables. In this regard,

ISPs are charging their clients for the entries of the latter in the former’s routing tables.

However, due to the economics of ISP, they only provide

selective transit which involves full transit capabilities for their own transit customers in both directions, some transit between mutual customers and transit only for one’s transit customers to one’s providers.

Border Gateway Protocol

As a review, BGP [2], which resides in the application layer of the Internet Protocol suite,
maintains a table of IP networks or ‘prefixes’ which designate network reachability among autonomous systems by selecting routes decisions based on path and network policies. eBGP sessions are between BGP-speaking routers in different SAs while iBGP are between routers in the same AS. The aim is to eliminate deflections and forwarding loops and

routers picks the same route that it would have picked and had it seen the best routes from each eBGP router in the AS

. Quadratic scaling such as inheritance of the properties chosen by the router reflector to all clients can be prevented by configuration of correct iBGP topology or hierarchy.

The paper detailed the BGP attributes. In summary, these are the rules to be considered in order of top priority [1].

1. Highest LOCAL PREF
2. Shortest ASPATCH length
3. Lowest MED preferred
4. Preferred eBGP or iBGP
5. Lowest IGP path cost to next hop
6. Smallest router ID or IP address

Convergence and other problems
BGP is like any other protocol with weaknesses. Here are some of them:

• Convergence after a fault has been detected could take a super-exponential number of steps. [1]
• Route flapping [2] or the repeated withdrawal and reannouncement of route information which can cause excessive activity in all the other routers that know about the broken link, as the same route is continuously injected and withdrawn from the routing tables.
• Damping as a solution for route flapping introduces problem in convergence
• Growth of the Internet routing table. This would take longer stabilization.
• A need for load balancing of multi-homed networks [2]
• BGP hijacking [2]

Conclusion
I haven’t seen and read an implementation as alternative to BGP. Mostly, the implementations for routing are improvements for BGP. There’s a need for an implementation that should be able to address the rapid growth of internet routing table as it adds to burden of stabilizing the routes when something failed. However, as of the moment, the gateways that couldn’t take the large routing tables have few remaining days in the server room.

[1] Hari Balakrishnan and Nick Feamster, “Interdomain Internet Routing”
[2] http://en.wikipedia.org/wiki/Border_Gateway_Protocol

Possibly Related Posts:

• Look Up! It’s a Chord!
• Chord-ially Inviting
• Relationship Between ASes: It’s Complicated
• Fly, DARPA, Fly!
• Does The End Justify The Means?