Interdomain Routing

This paper is an informal discussion of the BGP. It initially discusses the reasons for the existence of such a protocol; this includes a small lesson on the structure of the internet (with multiple tiers of ISPs, from universities and small business at tier 3 up to tier 1 ISPs). The goal of BGP4 is to allow different autonomous systems to exchange reachability information. A given tier 2 ISP wishes to inform peers about all of its customers (thereby providing its customers faster connections to customers of competing ISPs in the same region), and at the same time, it wishes to acquire reachability information from its provider (thereby giving its customers access to the parts of the internet that the ISP knows nothing about). There are a few additional constraints, such as the fact that no ISP wants to export information about its peers to other peers (since it is not benefiting directly from any traffic that its peers route through its gateways).

The protocol is fairly simple; it is simply a collection of data that is forwarded from one gateway to the next (and is sometimes changed when forwarded). The first is LOCAL PREF, which determines whether the information being given is for a local customer. This information is used (as stated above) to make decisions about whether or not to forward reachability information. The second is the ASPATH. This is the path that is taken within a single AS; its length is used as a factor to determine which routing information is optimal. MED is a number which can be used to give a preference to certain paths (i.e. routing long paths across a provider instead of internal gateways). There is also eBGP vs iBGP (prefer routes learned from peers to routes that were propagated through internal gateways), as well as IGP (internal path). If everything is a tie, then the AS employs some deterministic tiebreaker.

This paper is fairly unclear at times (since it actually appears to be lecture notes, I hope nobody's offended). It does a poor job of distinguishing between the protocol itself (which is fairly simple) and the task of designing a system that will efficiently and correctly implement the protocol. Often, there are references to the topology of the gateway connections, which is a topic that (while very interconnected with the protocol) should probably be treated separately.

One of the reasons the topology is best treated separately is because (as the paper says), there are several open problems in determining the best topology. In particular, in the section on failover and scalability, it is noted that in order to have a backup path in place in case of a failure, it is necessary to use pad the ASPATH that comes across a particular connection for particular IP prefixes. This is obviously not a scalable solution, and the question of how to do this is open-ended.