One week ago, an error at Verizon, a large Internet server provider, resulted in some 15K new networks being introduced into the Internet. This caused the global Internet routing table to breach 512K total routes. 512K is the maximum number of routes some older Internet routers can handle by default. Beyond this point, the affected routers may crash, refuse to learn new routes, or begin to drop traffic.
So if you have begun to feel that the Internet is a little slow, or some sites are sporadically offline or inaccessible, this may be the reason.
This problem did not come unexpected. A post in May 2014 forecasted the D-day to happen “not earlier than August and not later than October”, and indeed, it arrived on-schedule on 12 Aug 2014. Cisco also warned about the issue in a support document. There are easy workarounds on affected hardware.
If you’re keen to know about the technical background of this issue, read on.
Internet devices use a route table to determine how to send traffic to their destination. Your humble desktop computer also has a route table, albeit a very small a basic one, possibly just two or a little more routes. The routers at your school, office, or small-medium organisations might have a somewhat more complicated route table, where you might be looking at, say, 100 routes or so. At the heart of the Internet, however, and this is at the very large networks and top-tier Internet service providers, their routers may be looking at several hundred thousands of routes.
Checking the route table, especially one that has several hundred thousand routes, for every packet is very compute intensive. There is no short cut in software to search through these tables. Cisco’s solution was to implement the route processing in hardware, using Ternary Content Addressable Memory (TCAM). Ordinary memory return a value stored at an address that you supply as input. TCAMs, however, return the address of the matching data (i.e. content) you specify. You can picture TCAMs as a kind of associative array implemented in hardware. Searching route tables is not simple, in case you wondered. It’s not like you can do a binary search, or organise the table into a B-tree. No. Route table search involves a longest prefix match.
For the computer science people, TCAM search is performed in O(1) time. Yup. Super efficient. It’s the reason why the big networking gear can process packets at such tremendous speeds.
Unfortunately, the default TCAM configuration on some Cisco products limit the IPv4 route entries to 512K. This includes many of the most popular Cisco networking gear, including Catalyst 6500 switches (they route too), 7600 routers, ASR 9000 routers, etc. The workaround reconfigures the routers to give more TCAM space for holding IPv4 route entries.
The Internet is huge. You may have heard the Internet has already officially run out of IPv4 addresses to allocate at the top-level. 73% of the allocated address space (2.7 billion addresses) is announced in the global Internet route table. Today, there are about 47K autonomous systems network (ASN). An ASN is like, say, StarHub or SingTel.
At this time, the size of the global Internet routing table has fallen below the critical 512K threshold. This is only a temporary relief. Last week, it was a network maintenance that had gone awry. However, the growth is inevitable, and it shouldn’t be surprising to see the route table breach 512K again soon.