Interdomain Internet Routing

H. Balakrishnan, "Interdomain Internet Routing," MIT Lecture Notes.

One line summary: In this lecture the author describes the Border Gateway Protocol (BGP), used used to exchange reachability information for interdomain routing in the Internet, describing its operation as well as pointing out several flaws in the protocol.

Summary

This lecture starts by explaining that the Internet service is provided by a large number of commercial entities called Internet Service Providers (ISPs) which own an administer portions of the wide-area routing infrastructure called autonomous systems (ASs). ASs are classified into tiers based on their size and routing scope, e.g. the ISPs that have global scope are Tier-1 ISPs, whereas local providers tend to be Tier-3 ISPs. Within each AS, routing is done via Interior Gateway Protocols (IGPs) such as RIP and OSPF. Routing between ASs is accomplished through BGP. BGP is used to exchange routing information between ASs. ASs interconnections are generally either transit or peering type connections. In transit connections, one ASs acts as the customer and the other as the provider, where the provider gives the customer access to some or all of the destinations in its routing tables. In peering connections, ASs share some subset of their routing tables with each other, and these connections tend to be between business competitors. The first kind of interconnection tends to generate revenue for the provider, while the second does not.

BGP consists of two parts: eBGP between ASs and iBGP within an AS. In BGP, one router opens a BGP connection with another router using an OPEN message. The routers then exchange some of their routing information subject to filtering rules which ASs use to determine which routes to share. This exchange is done by UPDATE messages, which consist of an IP prefix followed by a number of attributes. These attributes are what ASs use to apply their filtering rules. Some of these attributes include Next Hop, AS Path, Local Preference, and Multiple-Exit Discriminator (MED). As mentioned, eBGP is used to disseminate routes between ASs, and eBGP connections are usually point-to-point. Two main goals eBGP must meet are loop-free forwarding and complete visibility. Within an AS, routers use iBGP to learn information about routes external to the AS, although the routing protocol used within the AS itself will be one of the IGPs. Ideally, iBGP routers within an AS would be organized into a full mesh, but as some ASs have large numbers of internal routers, this solution is not scalable. Within an AS, there are two methods for organizing iBGP routers into some sort of hierarchy to improve scalability. The first is to use route reflectors, and the second is to set up confederations.

Critique

There are many issues with BGP that cause it to not function as desired. One issue is that because peering interconnections between ASs usually occur between business competitors, financial motivations cause ASs to attempt to force other ASs to use up their resources (i.e. bandwidth) carrying packets in the wide-area network, leading to a large amount of asymmetrical routing. In addition, as mentioned before, there is an issue with scalability. Even bigger issues are caused by the lack of origin authentication. Because of this, misconfigurations or malicious users can cause a route to any IP prefix to be incorrectly advertised from an AS, causing traffic to be routed to that AS when that AS does not actually own that set of IPs. The propagation of incorrect routing information via BGP can affect huge portions of the Internet and result in users being unable to connect to the mis-advertised addresses. Also, by advertising false routing information via BGP, malicious users can engage in such activities as transmitting hard to trace email spam. An additional issue with BGP is convergence. BGP initially can take several minutes to converge, and in addition, to prevent propagation of transient faulty routing information, many routers use the policy of ignoring frequently changing advertisements, increasing convergence time. Another issue is that the increase of multi-homed customer networks is causing additional stress by increasing routing complexity, churn, and convergence time.

There are several things I found interesting about this lecture. One is the vulnerability of BGP to misconfigurations and malicious activity. I wonder if it is possible to “fix” BGP to address this issue or if it would be more advisable to attempt to replace BGP with a better protocol, if one even exists. Given the capacity for massive routing failures caused by BGP, I wonder what measures are taken to prevent them from occurring more often. I also found the discussion of the effect of financial interests of ISPs on routing interesting. It seems that ISPs engage in a fair amount of subterfuge, subverting routing goals. It might be interesting to examine this activity in more detail, and possibly determine if it would be possible to design a protocol to prevent this sort of behavior or create incentives to improve routing in the Internet, or if this sort of behavior is unavoidable given the nature of the participants.