OpenBGPD

▼ As part of my BGP training course, I explain to the participants that they can get BGP either by buying a router from the likes of Cisco or Juniper, or by running routing software such as Zebra, Quagga or OpenBGPD on a Unix (-like) operating system. Then I always mention that I haven't tried OpenBGPD yet, but I really should.

There's no time like the present, so I decided to take the plunge today.

OpenBGPD is a daemon implementing the BGP protocol that was developed for OpenBSD. So I first tried installing an OpenBSD 5.6 VM, which was pretty painless. Unfortunately, I couldn't get the OpenBSD package manager to install OpenBGPD for me. So I went to www.openbgpd.org (where I borrowed the image above). The latest version of OpenBGPD is 4.6, which is five years old—and it wouldn't compile. I never know whether it's my mediocre Unix skills or an actual show stopping issue in these cases. Update: the mediocre skills. As @tvlooy points out: OpenBGPD is included in the OpenBSD base install.

I then installed a FreeBSD 10 VM, which is also relatively painless but requires a bit more configuration during the installation process. However, FreeBSD has OpenBGPD in its ports system, and it installed from there without issue.

So now for the interesting part: configuring OpenBGPD.

It's really interesting to see a more Unix-like take on running BGP. The de facto standard way to configure and run BGP is the one invented by Cisco: you type configuration commands which are immediately applied to the active configuration. Zebra/Quagga uses the same model, even letting you interact with the daemon using telnet. Juniper, on the other hand, uses a very different model, where you use commands to modify the configuration and then "commit" that configuration (or roll back if necessary, very old school DBMS style).

With OpenBGPD, you simply edit the /usr/local/etc/bgpd.conf file after reading the man page. When you're done, you tell the bgpd to reload the configuration. I like this a lot. Monitoring the state of BGP sessions and the BGP table is done using the bgpctl utility, which lets you run clear and show commands that aren't entirely unfamiliar.

I plan on doing the BGP training course exercises using OpenBGPD myself next week, and see how well everything works in practice. The filtering/policy system seems to be inspired by the PF firewall with its insane "the last match is the one that counts" system, and the link between a filter rule and a neighbor is much less direct than with other systems. But I'm trying to keep an open mind.

OpenBGPD looks fairly mature from what I've seen so far, with one small but annoying omission: although you can configure 32-bit AS numbers in both ASDOT and ASPLAIN formats in the configuration file, bgpctl only shows them in ASDOT format. That means that if you have a BGP session with DE-CIX which has AS 196610, bgpctl will show that session as being towards AS 3.2. I.e., ASDOT notation is two 16-bit numbers separated by a dot (3.2) while ASPLAIN is simply a 32-bit number in decimal (196610). ASDOT was in vogue for a while when 32-bit AS numbers were introduced, but quickly fell out of favor as people realized that making regular expressions that match AS numbers with a dot in them would be very annoying. There's even a three-page RFC explaining all of this.

Permalink - posted 2015-01-31

IPv6 addresses and AS numbers in 2014

▼ After yesterday's final yearly IPv4 address report, I thought that today, I'd look at the other numbers the five Regional Internet Registries give out: IPv6 addresses and autonomous system (AS) numbers.

I have pages that show the latest numbers for these based on the most recently imported RIR data: IPv6 and AS numbers.

On January first, 2015, the total number of IPv6 addresses given out was 12626804692343330164921678734295040. The number of IPv6 addresses that are currently set aside for regular "global unicast" use is 42535295865117307932921825928971026432, so 0.0296% of the IPv6 address space has been used up so far. (And we can increase the global unicast space by at least a factor six if we need to.)

Of course the number of individual IPv6 addresses is rather meaningless, as each Ethernet or Wi-Fi network uses up 18446744073709551616 of those, even if there's only a single IPv6 system connected to that network. A more meaningful number is the number of /32s given out. A /32 is the size of the address block given to small-to-mediumsize ISPs. The equivalent of 159,372.68 /32s had been given out on January first, 17,916.90 of which in 2014. That number varies a bit from year to year, as some large ISPs or government entities happen to get particularly large blocks of addresses. However, the number of IPv6 address blocks has been growing fairly steadily from 2510 in 2010 to 4536 in 2014, with a total of 22,118 given out on January first. (For IPv4 the total is 145,917, which is 9039 higher than the total on January first, 2014.) Split out per RIR region:

              2014              Totals
RIR      Blocks   In /32s   Blocks   In /32s
 
AfriNIC     62      51.00     449    4617.00
APNIC      528    2663.00    3730   46210.15
ARIN       512    5232.68    4193   41465.94
LACNIC    1208    1363.20    3370    7989.54
RIPENCC   2226    8607.00   10376   59090.03

As every BGP expert knows, in order to advertise those IPv4 and IPv6 address blocks into the global routing system, you need an autonomous system number. Originally, those were 16 bits, allowing for 64512 usable AS numbers. 58,800 of those had been given out by January first, 2015, with the yearly rate being between 3500 and 4000 in recent years and 3056 in 2014.

However, BGP has been modified to work with 32-bit AS numbers. 9475 of those have been given out; 2052 in 2011, 1706 in 2012, 1577 in 2013 and 2988 in 2014. So the total number of AS numbers given out went pas 6000 for the first time last year. The mix is rather different at the different RIRs (ASNs given out in 2014):

RIR        16+32      32    % 32
 
AfriNIC      141     114     81%
APNIC       1299     722     56%
ARIN        1587     421     27%
LACNIC       964     570     59%
RIPENCC     2053    1161     57%

Unlike with the transition from IPv4 to IPv6, where you need to adopt IPv6 in order to talk to other IPv6 users, existing 16-bit AS numbers can be used to talk to routers that have a 32-bit AS number, making for a much easier transition.

Permalink - posted 2015-01-09

Internet exchange renumbering: everything old is new again

▼ This week, the Amsterdam Internet Exchange is renumbering its peering LAN.

An internet exchange (IX) is simply a very big Ethernet. Members connect a router port to that Ethernet, and can then exchange packets with each other. When you want to exchange traffic with many other networks, obviously this is more efficient than setting up dedicated connections with all these other networks.

Until this week, AMS-IX used a /22 prefix, allowing for about a thousand connected routers. That was no longer enough, so they got a new /21 prefix, which can accommodate two thousand connected routers. This means that all the currently connected routers must get a new address. No big deal. This is why search-and-replace was invented.

However, sometimes someone makes a mistake. Like configuring <new address>/22 instead of <new address>/21. And then letting that /22 propagate to other networks over BGP. Suppose:

• 192.0.0.0/21 is the prefix used on the IX peering LAN
• 192.0.2.1 peers with 192.0.2.2
• 192.0.2.3 advertises 192.0.0.0/22
• 192.0.2.1 wants to send a BPG keepalive packet to 192.0.2.2. Normally this packet would go to the port where 192.0.0.0/21 is configured. But the 192.0.0.0/22 prefix is "more specific", so the packet is sent on its way to the source of the 192.0.0.0/22 prefix: router 192.0.2.3.
• 192.0.2.3 forwards the packet to router 192.0.2.2
• All's well that ends well? Not so fast. In BGP, there are not supposed to be any intermediate routers between two BGP routers. 192.0.2.2 sees the packet traversed and extra hop, rejects it and resets the BGP session.
• 192.0.2.1 can no longer send traffic to 192.0.2.2

(A more specific prefix is a smaller range of IP addresses. 192.0.0.0/21 is BGP talk for the address range 192.0.0.0 - 192.0.7.255. 192.0.0.0/22 is the range 192.0.0.0 - 192.0.3.255. Because the latter identifies a smaller range of IP addresses, the packets are sent in that direction, just like you'd follow a sign "Paris" rather than a sign "France" if you were going to Paris, even though Paris is part of France so presumably following the sign "France" would also get you to Paris.)

The sad thing is that the exact same thing happened in 2003, when the AMS-IX renumbered from a /24 to a /23. I always warn against this issue during my training courses, and tell students to filter the IX prefixes of internet exchanges they're connected to, as well as all possible subprefixes (more specifics) that fall within that IX prefix. For instance:

!
ip prefix-list import deny 172.16.0.0/12 le 32
ip prefix-list import deny 80.249.208.0/21 le 32
ip prefix-list import permit 0.0.0.0/0 le 24
!

This prefix list will reject incoming updates with your own prefix and all possible more specifics (assuming your prefix is 172.16.0.0/12) as well as the AMS-IX prefix 80.249.208.0/21 and all possible subprefixes. It then allows all prefixes with a prefix length of no more than /24, which is common practice for IPv4.

"le" means "less or equal" so "172.16.0.0/12 le 32" means:

172.16.0.0/12
172.16.0.0/13
172.24.0.0/13
...
172.31.255.254/31
172.31.255.254/32
172.31.255.255/32

Hopefully, by the time AMS-IX connects more than 2000 routers, the issue is moot because we no longer use IPv4. But for now: happy renumbering!

Permalink - posted 2014-10-15

BGP table hitting 512k limit in older routers

▼ It's never a good sign when the regular press reports about BGP-related issues, such as last week: Browsing speeds may slow as net hardware bug bites (BBC). The problem is that the BGP table has started to hit the 512k FIB limit in some older routers. Numerous outages and slowdowns were reported to be caused by this, but it's unclear to which degree that's accurate.

So what's a FIB and why would it be limited to 512k (524288) prefixes?

BGP routers actually have (at least) three different tables where IP address prefixes are stored, along with a next hop address: the BGP RIB, the main routing table / RIB and the FIB. The BGP Routing Information Base collects all information received over BGP that's not immediately filtered out. So if you have two ISPs, they will both send all the prefixes for all networks in the world that are currently reachable—which means that your router has two copies of every prefix, one with a next hop address pointing to ISP A and one with a next hop pointing to ISP B.

For each prefix, BGP then decides which path is better and sends the prefix plus next hop address pointing to either A or B to the main routing table. The main routing table also holds non-BGP routing information. In large networks, all the internal stuff and routes for customers can add up to thousands or tens of thousands of routing table entries.

Finally, a Forwarding Information Base (FIB) is constructed from the main routing table that is used to actually forward packets to the router identified by the next hop address. Some routers use regular RAM to store the FIB, others use a Ternary Content Addressable Memory. RAM sizes are pretty large these days and typically don't have a fixed limit, as it's shared by many processes running on a router. But TCAMs are special memories with a tiny bit of processing power. Basically, you can show a prefix to a TCAM and then the TCAM will tell you the address where that prefix is stored—you don't have to search through the memory one step at a time. This means TCAMs are very fast, but they are also more expensive than RAM and they run fairly hot. So TCAM sizes are limited.

Nothing new under the sun

Cisco 6500 and 7600 modular routers/switches used to have supervisor modules with a TCAM limit of 256k. And then in 2008 the routing table grew to 256k, so people had to upgrade in a hurry. If they bought new supervisor modules that can handle 512k, they got six years of use out of those, hence Geoff Huston's statement that "Nothing in BGP looks like it's melting".

Because different networks have different numbers of internal prefixes and there are also slight differences between the number of prefixes each ISP announces to its customers, different people get bitten by the issue at different times. Also, TCAMs are often partitioned into different parts: one for the IPv4 routing table, one for the IPv6 routing table, one for MPLS, one for filtering... In some cases, simply changing the partitioning is enough to get by for a while. Alternatively, it's always possible to filter BGP prefixes. As Randy Bush says:

❝half the routing table is deagg crap. filter it.❞

The trouble is, you then lose connectivity towards the filtered prefixes, and there is no obvious way to only filter out the prefixes that are unnecessary deaggregation. If your network is non-huge, the solution is to use a default route pointing to your ISP / one of your ISPs as a safety net. What I used to do many years ago when using severely underpowered routers to run BGP is simply filter out all AS paths longer than five ASes from both our ISPs. Then, if one ISP has a long path and one a short path, I'd still have the short path which I'd want to use anyway. If neither had a short path, chances were it was a non-critical prefix far away, so handling it through a possibly non-optimal default route was unlikely to be problematic.

However, large networks don't have anyone they can point a default route to. So they have to have more recent routers, and they pretty much always do. However, it's not unheard of for older network equipment live out its final years in far away corners of big networks, so they could still have minor issues.

Mea culpa

Although during my training courses, I always warn people that they should buy routers big enough to hold enough prefixes for some years to come, I really should have been more explicit and posted a warning here on this site. At least Cisco did: The Size of the Internet Global Routing Table and Its Potential Side Effects.

The future

Geoff Huston expects the IPv4 table to hit 1 million in 2019 and recommends buying routers that can handle at least 2 million prefixes. Unfortunately, it's not always obvious how many prefixes a router can handle, especially if the TCAM is used for more than just the IPv4 FIB. So make sure what the limits are before you spend your money. Also, keep an eye on the weekly routing table report so you can take action when the BGP table starts creeping up to your routers' limits.

Further reading:

• Global Internet Routing Table Reaches 512k Milestone (Cisco blog)
• What caused today's Internet hiccup (BGPmon)
• Internet Touches Half Million Routes: Outages Possible Next Week (Renesys blog)

Permalink - posted 2014-08-19 - 🇳🇱 Nederlandse versie

"Nothing in BGP looks like it's melting"

▼ At the February NANOG meeting, Geoff Huston talked about BGP in 2013. For a quarter of a century, there have been concerns about BGP hitting scalability issues. The Internet Architecture Board even organized a meeting to discuss the issue in 2006. However, Geoff argues that the current growth is not presenting any immediate problems: "Nothing in BGP looks like it's melting".

One of the interesting things is that the number of prefixes in BGP continues to grow at about 11% per year even though Asia and Europe were out of fresh IPv4 addresses by 2013. The number of IPv4 addresses covered by the prefixes advertised in BGP didn't grow as fast, though. Annoyingly, 50% of the half million prefixes in BGP are small address blocks (more specific prefixes) that fall within a larger address blocks (aggregates) that are also present in BGP. And the really amazing thing is that 80% of the number of daily BGP updates—which has been extremely stable for years—is caused by these more specifics.

The graph that blew my mind is this one, BGP growth vs Moore's Law:

However, that's assuming that the processing required scales linearly with the number of prefixes. That's probably (close to) true for running the BGP protocol. But that's not the hard part. The hard part is matching destination IP addresses in millions of packets per second with half a million or more prefixes in the forwarding information base (FIB) that the router hardware uses. There's pressure on FIB performance from two directions: the number of prefixes and the number of packets per second. So FIBs need to get faster and get bigger at the same time. It doesn't look like we're going to be in trouble in the immediate future, but it would still be good if we could get rid of all that unnecessary deaggregation.

Anyway, that's all IPv4. What about IPv6? Yes, it's growing. But not setting the world on fire by any stretch of the imagination. At current rates, IPv6 will reach parity with IPv4 in 2030. However, IPv6 deaggregation levels seem to be heading towards the 50% mark where IPv4 has been for some time.

Read the slides here, or download an almost 2 GB MPEG4 file of the presentation from the NANOG website. The presentation is 25 minutes and 10 minutes worth of questions and remarks from the audience, including one of the big deaggregation offenders.

Or read Addressing 2013 and especially BGP in 2013 - The Churn Report, especially if you're not completely sure about all the background and terminology.

Permalink - posted 2014-06-30 - 🇳🇱 Nederlandse versie