GGP, EGP and 25 years of BGP: a brief history of internet routing

Although there was the ARPANET before it, the internet as we know it today came about in the early 1980s when TCP/IP was invented. Even back then, the nascent internet was a network of networks, and those newfangled IP packets needed to be routed from one organization’s network to another organization’s network. In other words: there was a need for an inter-domain routing protocol. (No, those domains have nothing to do with the DNS: inter-domain means between networks run by different organizations.)

The early days: GGP

The very early internet ran a protocol called the Gateway to Gateway Protocol (GGP). GGP is briefly outlined as part of RFC 823, which describes the DARPA Internet Gateway. Remember that back then, the word “gateway” was used for what we today call a router. GGP was basically a slightly more advanced version of the very simple RIP routing protocol. As such, GGP was a distance-vector protocol, which means Router A tells router B that it can reach Google over three hops, and then Router B knows it can reach Google over four hops.

1984: EGP

In 1984, GGP gave way to the Exterior Gateway Protocol (RFC 904). EGP is much more mature than GGP, but is still a simple distance vector protocol. A limitation of EGP is that it only allows for a tree-like network topology. That means that there can only a single path between any two parts of the network. But that’s not a big deal back in the 1980s, as in 1986, the National Science Foundation created the (56 kbps!) NSFNET which back the “backbone” of the internet. As such, all long distance traffic passed through the NSFNET, which was upgraded to 1.5 Mbps in 1988 and 45 Mbps in 1991. EGP introduced the notion of “autonomous systems”, with each separate network engaging in EGP routing having its own autonomous system (AS) number.

1989 – 1991: BGP-1, 2 and 3

In 1989, the Border Gateway Protocol (BGP, RFC 1105) was introduced as a successor to EGP. Note that BGP is also an exterior gateway protocol (EGP) as opposed to interior gateway protocols (IGPs) such as RIP and OSPF. Unlike all other routing protocols, BGP doesn’t automatically discover other routers running BGP. Rather, an administrator has to configure the IP addresses and AS numbers of BGP neighbors manually. This also allows BGP to run over TCP and not have to worry about BGP messages getting lost, duplicated or reordered.

Like EGP, BGP-1 still only supported hierarchical network topologies with only up, down and horizontal relationships. That limitation was removed in BGP version 2 a year later (RFC 1163). Another year later BGP-3 (RFC 1267) came around, which improved some of BGP’s inner workings. But BGP, too, is a distance vector protocol like RIP, lacking the sophistication of link state protocols such as OSPF.

1994: BGP-4 and CIDR

In the early 1990s, the internet was growing quickly, with more and more networks requiring a range of IP addresses. Back in those days, IP addresses came in three flavors: class A blocks of nearly 17 million addresses, class B blocks of 65 thousand addresses, and class C blocks with 256 addresses. The class an IP address belongs to is encoded in the top three bits of the IP address: addresses starting with 0 – 127 are class A, 128 – 191 are class B and 192 – 223 class C.

Most organizations needed more than 256 but less than 65000 addresses, so they got a class B block. But there are only 16384 of those, and it looked like the class B blocks would be gone in another year or two. So rather than giving a university that wanted to connect 4000 computers a class B block and have them waste 60000 addresses, they got 16 class C blocks. There are 2 million of those, so this policy change allowed for ample future growth.

However, now a new network wouldn’t add a single entry for a class B block to the BGP routing table, but 16 class Cs. So the routing tables started to grow very fast and quickly started becoming too large for the routers of the day. This issue was solved in BGP-4 in 1994 (RFC 1654, later RFC 1771 and then RFC 4271). BGP-4 adds the notion of classless inter-domain routing (RFC 1519), which removes the notion of having the IP address space separated into three classes.

Instead, we use prefix notation to indicate the size of an address block. So 192.0.2.0/24 means an address range starting at 192.0.2.0 and 24 of the 32 IPv4 address bits are given, so 8 bits are left. 2 to the power 8 is 256, so this is a range of 256 addresses, i.e., 192.0.2.0 – 192.0.2.255. If that’s not enough, we can increase this to 192.0.2.0/23, which holds 512 addresses, or 192.0.2.0 – 192.0.3.255. As a result, BGP-4 would transmit an address range like 192.87.192.0 – 192.87.207.255 a single 192.87.192.0/20 prefix rather than 16 class C blocks.

So with four versions in the first five years, we should be on BGP version 20 by now, right? Or at least 7 or 8. But no, we’re still on BGP-4 today! All BGP innovations since 1994 are in the form of optional extensions. This is made possible because BGP allows the definition of new path attributes that are attached to each prefix, where a bit indicates whether an unknown path attribute should or shouldn’t be propagated.

A short overview of extensions to BGP over the past 20 years:

1996: communities (RFC 1997)

Communities are user-defined values that can be attached to a prefix that can be used to trigger actions one or more ASes away. For instance, Level 3 publishes a list of communities in the RIPE database that inform customers where a prefix was learned and let customers influence how Level 3 handles their prefixes.

1998: multiprotocol extensions (RFC 2283)

When BGP-4 was created, IPv6 didn’t exist yet. Obviously, when IPv6 came around, it became useful to also engage in inter-domain routing for the new IP version. So a set of extensions was created that allows BGP to carry routing information for pretty much any protocol or “address family”, including multicast, IPv6, IPv6 multicast, VPNs, et cetera. A single BGP process—sometimes even a single BGP session—handles the multiple protocols.

1998: the TCP MD5 option (RFC 2385)

To protect the TCP session BGP runs over from spoofed reset packets and from third parties impersonating a BGP neighbor, an option was added to protect the TCP session BGP runs over with an MD5 hash. Only if both sides have the same password can they generate the correct hashes, all packets with incorrect hashes are ignored. This is not really an extension to BGP, as the MD5 hash is encoded in a TCP option.

1998: flap damping (RFC 2439)

Due to bad BGP implementations in the late 1990s a substantial number of prefixes kept appearing and disappearing from the BGP tables (“flapping”). This caused excessive CPU load on routers. Flap damping lets a BGP router penalize flapping prefixes and ignore them for a while to make the BGP system more stable.

2000: route refresh (RFC 2918)

BGP relies on filters to avoid security problems and mistakes. But when a filter is changed after prefixes are already propagated, those prefixes don’t automatically go away. So after modifying a filter, it’s necessary to reset a BGP session by tearing it down and reestablishing the connection. However, this means there is a short outage—or a long one if flap damping is triggered. Route refresh allows routers to ask each other to push out all their prefixes so new filters are applied without destructive side effects.

2007: the 32-bit AS number capability (RFC 4893)

Around 2000, it became clear that having 16 bits for AS numbers, allowing for 64512 of them, wasn’t enough in the long run. (71648 are given out as of today.) Obviously updated BGP speakers can exchange 32-bit AS numbers, but what if there’s an old BGP router in the middle? Each router adds its own AS to the AS path attached to each prefix, making it easy to detect loops, because then it sees its own AS number is already present. 32-bit AS number capable routers keep the 16-bit AS path but add a 32-bit one. If a route passes through a 16-bit capable router, the 16-bit path will be updated but not the 32-bit one. The first 32-bit router will detect this and repair the 32-bit AS path. This means it’s not necessary for the whole internet to upgrade before 32-bit AS numbers can be used.

The 32-bit AS path (propagating from right to left) isn’t updated by AS 3, but is repaired by AS 4.

2016 (?): BGPsec (draft-ietf-sidr-bgpsec-protocol-13)

Although the TCP MD5 option protects BGP from attacks against TCP, it doesn’t make sure that the information two BGP routers exchange is actually correct. As such, it’s not unheard of for prefixes to be injected into BGP by someone else than the owner of those addresses—by accident or maliciously. RPKI, which operates on individual routers and doesn’t touch the BGP protocol directly, makes sure only the correct AS can inject a prefix into BGP. But a malicious party can still craft a fake AS path to get around that. BGPsec secures the AS path with cryptographic signatures. The IETF is currently still working on BGPsec.

So in the future we may be exchanging IPv8 prefixes between autonomous systems with 64-bit AS numbers protected with RPKI and BGPsec, but it’s more than likely this will still happen over BGP-4.

It’s the bible for this protocol, yet explained in a clear way and to the point.