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

A decade of bandwidth growth

▼ Next week I'm doing a guest lecture about the infrastructure of the internet. Turns out that I already talked about that in 2003 (PDF). One slide in that presentation caught my eye:

The image shows how bandwidth in research networks and ISP networks has grown, as well as the bandwidth provided by technologies such as Ethernet, Wi-Fi, mobile data, and consumer internet access. All of them show a healthy growth, although some start from extremely modest beginnings.

So I wondered what happened in the intermediate decade. Which would be:

Because research and ISP networks are so diverse, I didn't include these here. Of course this is all somewhat arbitrary, because few people use the highest available speeds. For instance, cable and fiber to the home internet access tops out at 100 Mbps or higher, but many people still use around 10 Mbps, either because of price or because they're limited to some form of DSL and a relatively long distance to the nearest telephone exchange. And LTE should be able to reach 300 Mbps, but I don't think that's available in commonly available handsets.

My impression that Ethernet had run out of steam is not entirely correct, the progression to 100 Gbps is roughly in line with the earlier growth path. Wi-Fi looks a little less impressive than I had thought on this logarithmic scale. However, there's just one super star here: mobile. It's hard to believe that we went from 100 kbps or so EDGE to 100 Mbps LTE in about a decade. Not everyone may be using LTE just yet, but 14 Mbps UMTS HSPA is in very wide use, there is really no reason to use anything less.

Permalink - posted 2014-09-04

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