20 years of BGP

▼ 20 years ago today, I got my first autonomous system (AS) number, marking my entry in the BGP business. (5399, if you're wondering.)

To quote Ferris Bueller: "Life moves pretty fast. If you don't stop and look around once in a while, you could miss it." So let's look back and see what has happened over those 20 years.

Back in 1995, BGP had been around for about six years: BGP versions 1 - 3 were published as RFCs in 1989, 1990 and 1991, respectively. And then in 1994, the BGP-4 spec was published and that's still the version we use today. Crazy, right? I remember when I was writing my BGP book (published by O'Reilly in 2002), my editor asked whether there'd be a new version of BGP soon. I told him not to worry about it.

bART

However, pretty much all other aspects of the internet have changed in those two decades. The first version of the IPv6 specifications wouldn't be published until several months later. I hadn't heard of Network Address Translation (NAT) yet—RFC 1918 hadn't even been published! So we had to use RFC 1597 to get our private addresses. But IPv4 addresses were plentiful those days, so why would we? DHCP had been out for a couple of years, but I'm pretty sure I hadn't used it by then: stuff either was configured manually, or through PPP.

Yes, those were the days of screeching modems. AS5399 was the AS number for bART Internet Services, a small ISP in The Hague. When I first got in touch with bART they had a 28 kbps link to one ISP and a 128 kbps link to another. But all the traffic flowed over the slow line. I rerouted most of it over the faster line, which landed me a job. But obviously being able to use both lines together would be even better, but to do that right, you need BGP to do proper "multihoming".

One of the perks of working at an ISP was that I was able to get my own leased line. Back in those days, you could lease a regular copper phone wire between two locations, and this was relatively cheap (55 guilders (25 euros) a month, IIRC) if both locations were served by the same telephone exchange. As one third of The Hague is connected to the really, really huge exchange in the Marnixstraat, that applied to me. However, my leased line was only 28k, so around that same time I got my ISDN line (which I would keep until 2007), which was much faster at 64 kbps, or even 128 kbps if you bundled both channels. But remember, those channels were metered so that could get expensive, even for local calls. Today, I have a 120 Mbps cable connection at home, which is a thousand times faster. That makes for a bandwidth increase of about 41% per year. I remember signing a contract for 2 Mbps internet service for 30,000 guilders (13,000 euros) per month a year later. So the wholesale price of bandwidth has also gone down by about a factor 1000 in 20 years.

Size of the BGP table

We initially ran BGP on a Cisco 2501 router , maxed out with16 MB RAM. Back then, the BGP table was around 30,000 prefixes, which just about fit in that 16 MB. I don't remember what kind of router we switched to as the table size outgrew that 16 MB. Today, there are about 560,000 IPv4 prefixes in the BGP table, so roughly a factor 20 increase in 20 years, or about 16% per year.

Back in 2006, the Internet Architecture Board held a "routing and addressing" workshop in Amsterdam, where the issue of the growth of the BGP table was discussed. For a long time, this was considered a serious problem. We even came up with Shim6 in the IETF to allow for multihoming without using BGP with IPv6, but that never went anywhere as people just used BGP to multihome with IPv6. So, 16% annual growth of the BGP table is inconvenient, but apparently not as inconvenient as the alternatives. (Of course, if you run BGP to multihome, that solves your problem immediately while increasing the BGP table for everyone. Waiting for the whole world to adopt Shim6 so you can multihome without BGP doesn't provide that instant gratification even though it keeps the routing table small and thus the routers cheap(er).)

BGP's evolution

I still have a Cisco 2503 (that's the model with an ISDN port) lying around. I think we used IOS 10.3 or so back in 1995. If I load that IOS version on the 2503, I'm pretty sure that 2503 with the 20-year-old software could still talk BGP with a current router. (Well, until that 16 MB RAM is full.) However, that is not to say that nothing has changed in intermediate decades. A whole bunch of capabilities were added over the years, including:

• communities, for tagging routes with additional information
• flap damping, to keep unstable prefixes from being propagated
• the TCP MD5 option to protect BGP sessions against spoofed packets
• multiprotocol extensions, to support IPv6, multicast, VPNs and more
• route refresh, to allow sessions to be reset non-destructively
• the 32-bit AS number capability
• and in the not-too-distant future: BGPsec, which will make BGP more secure

The creators of BGP-4 did a great job with the extension mechanism, allowing the protocol to be extended as needed with very few backward compatibility issues. So future network protocol creators, take heed. And as a result, we'll probably be running BGP-4 forever, although it's hard to say what will be bolted onto it in the future.

BGP and me

Over the past 20 years, I have configured BGP for dozens of clients on about a dozen different types of routers, I wrote a book about BGP, started bgpexpert.com, wrote a master's thesis on a crazy way to do multipath in BGP and proposed an improvement to the protocol. Since my book came out, I've been doing BGP training courses, having trained at least 200, but probably more than 300 people. And I'm sure BGP and me haven't seen the last of each other. But right now, I have a movie to watch, candles to blow out and pie to eat!

Permalink - posted 2015-08-15

5 minutes of BGP instability after leap second

▼ This July 30th, at 23:59:60, a leap second was added to Coordinated Universal Time (UTC). Dyn Research posted the following graph on Twitter that shows there was significant BGP update instability for five minutes after the leap second occurred:

Unfortunately, it's not clear why this happened. However, leap seconds have triggered all kinds of mishaps in the past. They're basically miniature Y2K problems. Time and time again, software engineers show that they can't be trusted to take corner cases into account properly.

This does remind me of a situation about a decade ago, where I had a customer that experienced BGP instability every night at the same time. They used Quagga running on Linux machines. We couldn't figure out what the problem was, until we realized that at that very moment, the ntpdate command was run from the cron. ntpdate synchronizes the system clock with an NTP server. As the machine in question had a very poor system clock, this meant that the system's time was adjusted a lot every night, I think a minute or more, but definitely more than 30 seconds.

Which meant that if Quagga had gotten a BGP keepalive message 8 seconds earlier, it now thought that was 38 seconds ago. If BGP is configured with a hold time of 30 seconds, this means that Quagga now thinks the other side has been quiet for longer than the hold time and it'll tear down the BGP session. This is what happened every night for a bunch of BGP sessions. We solved this by running the NTP daemon continuously, so there was never a big adjustment in system time. (Alternatively, just letting the time drift would also have worked.)

The minimum BGP hold time is 3 seconds, so adjusting for an (improperly handled) leap second shouldn't be able to make BGP think the hold time for a session is expired. However, there could be bug somewhere else that impacted BGP.

I'm not sure whether these kinds of issues are a good argument in favor of abandoning leap seconds, as the bugs won't go away, they'll just show up at a less predictable time. But I don't like the current leap second practice, as they're unpredictable, and you can't calculate the time difference in seconds between two dates without taking the entire list of leap seconds into account. I think it would be better to save the leap seconds up and apply them all at the end of a century.

Permalink - posted 2015-07-06

Bring on the 2.5, 5 and 25 Gbps Ethernet!

▼ I'm at the RIPE meeting in Amsterdam this week. Yesterday, one of the first presentations was one from Alcatel-Lucent's Greg Hankins: Evolution of Ethernet Speeds: What’s New and What’s Next (PDF, see here for a link to the video recording).

Apparently, we're going to get some new Ethernet speeds in the (relatively) near future, such as 2.5, 5 and 25 Gbps. I can't wait!

My first computer with Gigabit Ethernet was the PowerBook I bought in 2003. It's now more than a decade later and my current Apple laptop... doesn't have any Ethernet at all. But for 20 to 30 euros/dollars you can get a 10/100/1000 Mbps Ethernet adapter that connects to either a Thunderbolt or a USB3 port. That's exactly as fast as the Ethernet port on my old PowerBook, even though according to Geekbench 2, my late-2013 MacBook Pro is more than ten times faster than the 1.25 GHz PowerBook (32-bit scores are 7110 vs 658). The SSD in the MBP is also about ten times faster than the HDD in the PB at about 800 vs 80 MB/s. USB is 5 Gbps instead of 480 Mbps, Wi-Fi 1300 vs 54 Mbps. It's just the Ethernet that's been completely stagnant.

So why is that? We've had 10 Gigabit Ethernet since the early 2000s. But the problem with that is that originally, 10GE was designed to work over fiber, which can easily handle that bandwidth. It took a lot of work to make 10GE work over copper, and that never got cheap in the way that GE got cheap so we never got 10/100/1000/10000 Mbps Ethernet ports the same way we went from 10/100 to 10/100/1000 Mbps Ethernet ports on our laptops and desktops. Even the biggest and baddest Mac that you can buy today, the Mac Pro, only has two 10/100/1000 ports, and no extension slots for adding 10GE.

The problem with all of this is that Gigabit Ethernet tops out at about 119 MB/s. That's more than enough to saturate any internet connection that a mere mortal can afford, but it's not enough to keep up with our SSDs or even a RAID array when copying files locally, with SSDs that easily go over 500 MB/s these days. With 2.5 Gbps Ethernet we'd get a lot closer at about 300 MB/s, and 5 Gbps Ethernet would be even better at about 600 MB/s. With modern designs, I expect that 5 but certainly 2.5 Gbps over regular twisted pair cabling can be made sufficiently cheap that these speeds will be supported routinely, and USB3 can easily handle 2.5 Gbps and probably also 5 Gbps. 2.5 and 5 Gbps are also intended to run over existing cat 5e/cat 6 cabling over distances of 100 meters, the same as Gigabit Ethernet. Traditionally, higher speeds over copper require more advanced cabling and/or support shorter distances.

There will also be 25 Gbps Ethernet that will be a nice step up for big servers that now use 10 Gbps, and perhaps 50 Gbps in the future. See the presentation for what's new for 10 and 40 Gbps and even 400 Gbps.

Permalink - posted 2015-05-12

RPKI is ready for real-world deployment

▼ For some years now, the Regional Internet Registries have been rolling out RPKI. The Resource Public Key Infrastructure allows holders of IP addresses to authorize an autonomous system to inject those addresses in BGP. (See here for an overview of how RPKI works and more links.)

I've always thought it would be hard to deploy RPKI in the real world, because it's just way too easy for a certificate or ROA (route origination authorization) to expire. If that then leads to routes becoming invalid and the addresses in question being unreachable, that would be a good example of the cure being worse than the disease.

Fortunately, that's not the case: RPKI is ready for real-world deployment today.

The way to deploy RPKI that's suggested in RFC 6483 as well as the relevant Cisco and Juniper documentation is to assign different local preference values to the three possible RPKI states, such as:

• Valid (RPKI checks out): local preference of 200 (highest)
• Unknown (no RPKI for this prefix): local preference of 100 (normal)
• Invalid (RPKI present but doesn't check out): local preference of 50 (lowest)

So packets will follow a path that is RPKI-validated if available. If not, they follow a path that isn't covered by RPKI if that's available. Only if there's no "valid" or "unknown" paths, the packets will be sent over an "invalid" path that is covered by RPKI, but validation failed. The trouble with this approach is that it still allows for invalid more specific prefixes to hijack traffic. For instance:

RIPE has a ROA for prefix 193.0.0.0/21 that allows AS 3333 to originate that prefix, with a maximum prefix length of /21. So if AS 4444 originates 193.0.0.0/21, that will result in the following BGP table:

    Network       Next Hop       Metric LocPrf Weight Path
>*  193.0.0.0/21  19.11.111.244      10    200      0 3333 i
 *                29.249.178.10      10     50      0 4444 i

So effectively, the path through AS 4444 is ignored. However, AS 4444 could also do this:

    Network       Next Hop       Metric LocPrf Weight Path
>*  193.0.0.0/21  19.11.111.244      10    200      0 3333 i
>*  193.0.0.0/24  29.249.178.10      10     50      0 4444 i
>*  193.0.1.0/24  29.249.178.10      10     50      0 4444 i
>*  193.0.2.0/24  29.249.178.10      10     50      0 4444 i
>*  193.0.3.0/24  29.249.178.10      10     50      0 4444 i
>*  193.0.4.0/24  29.249.178.10      10     50      0 4444 i
>*  193.0.5.0/24  29.249.178.10      10     50      0 4444 i
>*  193.0.6.0/24  29.249.178.10      10     50      0 4444 i
>*  193.0.7.0/24  29.249.178.10      10     50      0 4444 i

So even though the path towards the /21 is still routed to AS 3333, the packets flow to AS 4444 because of the longest match first rule. Solution: filter out "invalid" prefixes completely.

But then, what happens when RIPE forgets to renew their certificate or ROA in time? If their prefix would then revert to "invalid", it would disappear from routing tables everywhere, and RIPE would be unreachable:

    Network       Next Hop       Metric LocPrf Weight Path

In this scenario, it would be very dangerous to filter "invalid" prefixes, as RPKI is still relatively immature and mistakes will happen.

However, it turns out that the results of expired certificates and ROAs aren't actually problematic. In a post to the NANOG list, Alex Band points out:

If ARIN (or another other RIR) went offline or signed broken data, all signed prefixes that previously has the RPKI status "Valid", would fall back to the state "Unknown", as if they were never signed in the first place. The state would NOT be "Invalid".

So what would happen is this:

    Network       Next Hop       Metric LocPrf Weight Path
>*  193.0.0.0/21  19.11.111.244      10    100      0 3333 i

Obviously, in this case the protection against unauthorized origination of the prefixes in question would go away, but in the normal situation where nobody tries to hijack those prefixes, they would still be reachable and a mistake with certificate or ROA expiration wouldn't immediately lead to a network disappearing off of the internet.

In other words: deploy RPKI today. It doesn't protect against all forms of malicious address hijacking, but it does offer very robust protection against accidental unauthorized route origination, such as the infamous Youtube/Pakistan incident. Also, you can run an RPKI validator locally without the need for your upstream ISPs or peers to do the same.

Permalink - posted 2015-04-30