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

With North America out of IPv4, do we trade, translate or transition to IPv6?

▼ It's official: for all intents and purposes, North America is out of IPv4 addresses. Two of the four other regions have been in that situation for some time, and Latin America will be joining North America, Europe and Asia in about a month. That leaves Africa, which still has almost 50 million IPv4 addresses, which are used up at a rate of 5 - 10 million a year.

Does this mean that if you're running a business that requires a regular infusion of new IP addresses, it's time to relocate to Africa?

Not quite. The Internet Engineering Task Force saw all of this coming twenty years ago—which they should, having hobbled TCP/IP with a meager 32-bit address space for a maximum of about 4 billion IPv4 addresses. But they fixed that with IPv6, which increases the address length to no less than 128 bits for a near-infinite number of addresses.

Unfortunately, a system that only speaks the new IPv6 can't directly talk to a system that only speaks the current IPv4. So giving people just IPv6 means they can't talk to the 97% of internet users or the 90% of top 500 web sites that haven't adopted the new protocol yet.

But don't start looking for apartments in Nairobi or Casablanca just yet: it's also possible to trade IPv4 addresses. The big question is: to what degree will that solve the lack of available IPv4 addresses? We know that Microsoft and Amazon have bought large numbers of IPv4 addresses, and there have also been larger numbers of small exchanges. The going rate seems to be around $10 an address, which is expected to go up to about $30.

Microsoft and Amazon run cloud services where large numbers of virtual machines need IP addresses, which they probably couldn't get the "normal" way. In the Asia-Pacific region, there have also been exchanges of small and medium-sized IPv4 blocks. Obviously, paying $2560 for a "/24" (256 addresses), which is the smallest usable block of IPv4 addresses, is not a big deal for content providers.

However, the big ISPs and telcos that use IP addresses by the hundreds of thousands or millions haven't entered this market so far. The big question is: will they? Until now, a company like Comcast paid pennies per address for its multi-million blocks of IPv4 addresses. Having to pay $30 for an IPv4 address to give to every new customer would be a big hit to their bottom line. Worse, what if a year later the going rate is $60? And then $120, and so on? (And I'm not even talking about the headache of having to acquire more and more smaller and smaller blocks as the years progress.)

Rather than spend $30,000,000 on a million IPv4 addresses, a big ISP could probably spend a lot less on Carrier Grade NAT (CGN) equipment that makes it possible for multiple users to share a single IPv4 address. They still 100,000 addresses to connect a million new customers, but they probably have that kind of address space in reserve, or if not, they can take it from existing users and put those behind the CGN, too.

In the meantime, more and more ISPs are rolling out IPv6 for their users. Today, IPv6-only connectivity is not good enough to replace regular IPv4 connectivity, but the day that it will be is approaching. Even today being limited to just IPv6 connectivity for an hour or two wouldn't be too inconvenient for me. Sure, I wouldn't be able to read many news sites or post to Twitter, but I can get my email over IPv6, visit Google, Facebook, Wikipedia.

So my advice to HP: if you can get a billion dollars for those 33 million IPv4 addresses you're holding (after buying DEC), take it. You'll wish you had when IPv6 reaches critical mass and people start asking themselves why they're still bothering with that arcane 1980s network protocol. However, I'm not an economist, but I would think having millions of IPv4 addresses enter the market would lower the price.

Bottom line: small amounts of IPv4 address space will always be available in some form. But assuming you'll be able to either buy low or sell high many thousands or even millions of IPv4 addresses at any point in the future is a risky bet.

This article also appeared on the Kalorama blog. Also see this post on the topic by Louis Sterchi over there.

Permalink - posted 2014-04-28 - 🇳🇱 Nederlandse versie

Ethernet energy efficiency

▼ How power-hungry are various permutations of Ethernet on modern MacBook Pros? Tests performed and written up by Jeroen van der Ham and Iljitsch van Beijnum.

For some reason, we thought it would be a good idea to make the students of the System and Network Engineering master program test whether various permutations of IPv4/IPv6, energy-efficient Ethernet (eee) and jumboframes use more or less power. While the students were busy measuring, we were bored so we decided to run the same tests ourselves using our MacBook Pros (with Retina Display®)—Jeroen the 15" mid-2012 model and Iljitsch the 13" late 2013 model. These computers are too thin to house an Ethernet port, so we used Apple's Thunderbolt - Gigabit Ethernet adapter. We looked at the number of milliamps taken from the battery to see how much power the entire system used during various tests.

We didn't realize it at first, but the most surprising result was actually the first one, looking at system power use with the adapter plugged into the computer, but without attaching a network cable. This increased system power use by 300 mA, or about 3.4 Watts. On the 15" MBP this is already significant, increasing power use from 1250 to 1550 mA. But the 13" MBP only used 370 mA without the adapter plugged in, so its power use almost doubled after plugging in the adapter!

Could it be that the secret to the long battery life of Apple's recent laptops is the fact that they come without an Ethernet port?

We continued our testing trying different possibilities with Energy Efficient Ethernet (eee) turned on or off. Students in 2012 already looked at the general impact of eee on energy usage for clusters. They found that it provides an energy saving of up to 40% in switches, depending on the amount of traffic. Energy usage goes up when traffic goes up, but it already maxes out when you are using roughly 40% of the bandwidth. We confirmed this in our testing: there is not much difference with eee when the interface is idle, or with full traffic.

More significant energy savings started to appear when we enabled jumbo-frames (MTU 9000). The amount of data that goes through the adapter remains virtually identical, but with only one-sixth as many packets per second, the impact of per-packet overhead is greatly reduced, and this shows in the energy consumption. With full traffic in one direction this saves you over 10%. These savings also add up if you have traffic in both directions, in our experiments we saw a savings 16-19% for a bidirectional fully-utilized link.

Not surprisingly, the biggest difference in energy usage is to scale down the interface speed. When we forced the interface down to 10Mbps we saw a saving of up to 49% with full utilisation. Then again, if you're sending a large file, it is going to take a lot longer, and you basically use a lot more energy, only more distributed over time.

The results of our measurements are in the table below, but note that our measurements (using the System Profiler battery current figures) weren't very precise. The numbers give a pretty rough indication. If you want to do something serious with this data, perform your own experiments.

Total system power use	MBP15	MBP13
Interface attached vs baseline	+24%	+92%
Baseline vs idle eee	+27%	+110%
Idle eee vs no eee	-6%	-1%
Idle eee vs iperf 1 Gbps TCP eee	+74%	+97%
iperf 1 Gbps TCP eee vs no eee	-3%	-1%
iperf 1 Gbps TCP jumbo eee vs no jumbo eee	-13%	-12%
iperf 0.5 Gbps UDP eee vs no eee	+1%	+1%
iperf 1 Gbps TCP bi-di eee vs unidirectional eee	-0%	-3%
iperf 1 Gbps TCP bi-di jumbo eee vs no jumbo bi-di eee	-19%	-16%
iperf 10 Mbps TCP no eee vs 1 Gbps	-38%	-49%

We did some extra tests to look at the impact of jumboframes on CPU use. Please note that our Thunderbolt-to-Gigabit Ethernet adapters don't support TCP segmentation offloading (TSO). With 1500-byte packets the CPU utilization on the MBP13 was about 16%, with 9000-byte packets about 90%. Despite being idle more than 80% of the time, the CPU still ran at its advertised 2.4 GHz clock speed:

So the difference in CPU power use was 18% (7.9 W for 1500 bytes vs 6.4 W for 9000 bytes), despite the difference in CPU utilization only being 5%.

Permalink - posted 2014-03-03