In approximately one year’s time, the global routing table will grow past the magic 512000 prefix mark and render millions of routers unable to carry the global routing table. If you operate a router with BGP on a public AS number, you should probably read on.

Every so often seismic events happen in the tech world, such as the Millennium and leap second bugs, hash collisions and IPv4 depletion. All of these events have the ability to wreak havoc far and wide, but before I go into the detail of what’s about to happen, let me first give you a bit of background.

What is the Global Routing Table (GRT)?

The Global Routing Table is the definitive list of all IP address ranges in use on the Internet. Over time this list grows as new IP ranges are allocated to service providers, and often grows again as these ranges are subdivided, allocated to downstream customers and advertised individually. This is known as de-aggregation and is generally frowned upon, though in practise very little is actually done to police it.

GRT growth can also be caused by traffic flow engineering, whereby larger address ranges are split up and re-advertised at higher granularity to balance incoming traffic across multiple providers. This form of de-aggregation is more acceptable, but the end result is the same: a bloated Global Routing Table.

So why do we care how many IP address ranges are advertised to the Internet? In an ideal world we should not care, after all growth of “The Internet” is a good thing right? As a network operator there are two main reasons why GRT growth should be managed.

Firstly, router CPU Usage during major topology changes (and the time taken for that change to take effect) is directly proportional to the number of routes being added to – or removed from – a router’s tables. The faster a router can converge (apply local policies and reduce all known routes to a “best” set) the more stable that router will be, and extrapolating to the wider Internet, the more stable the whole Internet will become in turn.

Secondly routing table capacity is finite. The number of routes that a router can hold in its table is often fixed by the manufacturer, and apart from minor tweaks to split the resources between IPv4 and IPv6 cannot be increased without costly module or entire router upgrades. Routers designed to operate at provider borders are designed to handle 512000, 1024000 or 1536000 routes in the table, with the vast majority of low to mid end systems (and even some high end systems) coming in at the 512000 route mark.

The problem

Conservative predictions suggest that the global routing table could reach 512000 routes within the next 12 months.

Here is a graph of GRT growth.

At this point hundreds of thousands, possibly millions of Internet facing routers will no longer be able to hold a full routing table. Despite the somewhat inflammatory nature of this blog’s title, your router is highly unlikely to explode! However, depending upon the router:

  • Poorly written router firmwares could crash as the limit is breached, sending affected networks into a death spiral of router resets until the situation is identified and fixed. One would hope that all widely-deployed router firmwares would be adequately tested by vendors in the coming months and advisories issued in plenty of time.
  • Depending upon the firmware design, routing tables could overflow into the router’s slow path memory, causing poor packet forwarding performance to overflowed destinations. Interface queue backlogs caused by slow lookups on busy routers could cause many packets to be dropped severely degrading router and network performance or even crashing routers as a result of resource starvation.
  • Other strange, undefined things could happen. Hopefully others will post suggestions in comments below!

How can I avoid being affected by this issue?

Just because you don’t run a BGP speaking router doesn’t mean you are immune from this problem. It can’t do any harm to check with your hosting provider and make sure they have performed adequate auditing to ensure their network will continue to function well as the global routing table grows through the 512000 route mark.

If you do run BGP speaking routers you should contact your router vendor, or read your system documentation to see whether your router is affected. Remember to take into account that routing table memory is often shared with IPv6 routes as well, and that a single IPv6 route normally takes up the same space as two IPv4 entries.

If you are affected by this issue, then fortunately there are several options available. Replacing the affected router with a system designed for larger routing tables could be the best way forward, if a little costly.

Alternatively it may be possible to filter out a large number of routes and replace them with a default route pointed at your highest bandwidth transit provider. Filtering routes to /23 or higher will typically remove more than half of the entries from your routing table, buying you lots of time or even making the problem go away forever. The downside is that some traffic will be taking a non-optimal path to its destination and traffic load will become unbalanced as disproportionate traffic is routed to a single provider.

You could even consider hosting with CatN…

Finally, some live numbers for those who crave detail!

Here is a snapshot and some basic analysis of route table usage on a typical BGP router on the CatN network. This router is connected to:

  • an upstream transit provider, which is providing us with a full global routing table
  • the LINX peering exchange, which provides direct routes to many UK and EU based destinations
  • our core network containing several other routers connected to other transit providers sending the GRT

This router has a single transit connection, which has been up for 325 days and currently receives 420718 routes:

SSH@xxxx#show ip bgp sum
  Neighbor Address  AS#         State   Time     Rt:Accepted Filtered Sent     ToSend      174         ESTAB 325d 3h47m    420718   1        1        0

Taking into account all routing protocols, this router has a total of 420501 routes installed, 221476 of which are a relatively small /24 prefix (or 256 consecutive IP addresses – the minimum sized address range normally accepted by BGP routers):

SSH@xxxx#show ip route summary
IP Routing Table - 420501 entries:
  8 connected, 0 static, 0 RIP, 31 OSPF, 420462 BGP, 0 ISIS
  Number of prefixes:
  /8: 18 /9: 14 /10: 29 /11: 87 /12: 240 /13: 475 /14: 850 /15: 1553 /16: 12396 /17: 6498 /18: 10764 /19: 21152 /20: 30305 /21: 32286 /22: 42539 /23: 39744 /24: 221476 /25: 3 /26: 3 /27: 11 /28: 4 /29: 6 /30: 22 /32: 26 
Nexthop Table Entry - 325 entries

In total, this router knows of 881626 total possible destinations which have been learned from our 5 externally-facing Internet connections. Of all these routes, there were 422582 distinct networks, of which 422245 routes were accepted as the best possible route to the respective IP address range.

Of these 421431 routes, 358715 “best routes” are available via an external connection on this router, and 63530 “best routes” are available via other externally-connected routers on our network.

The final point to note is that we do not de-aggregate our IP address range, so we are not aggravating the GRT growth situation in any way.

SSH@xxxx#show ip bgp routes summary
  Total number of BGP routes (NLRIs) Installed     : 881626
  Distinct BGP destination networks                : 422582
  Filtered bgp routes for soft reconfig            : 345
  Routes originated by this router                 : 1
  Routes selected as BEST routes                   : 422245
  BEST routes not installed in IP forwarding table : 0
  Unreachable routes (no IGP route for NEXTHOP)    : 0
  IBGP routes selected as best routes              : 63530
  EBGP routes selected as best routes              : 358714


Leave a Reply

Your email address will not be published. Required fields are marked *

  1. David Kirkhope says:

    Could this article be summarised for non-techies.

    • Mark Sutton says:

      Hi David, certainly – I’ll try! The non techie explanation is that Internet Service Providers (the companies connecting you to the Internet), the Web Hosting companies (those connecting web sites to the Internet), many large businesses, universities and other organisations use devices called “routers” to connect to each other, and this is what creates “The Internet”. Many of these companies’ routers are set up to talk to each other and exchange information so that each router can build its own “map” of the Internet. This map is used to get information (e.g. emails and web page clicks) from A to B.

      As the Internet has grown, this map has gone from 10s of entries to thousands, then hundreds of thousands to the current number – approximately 430,000 and expecting to grow past 500,000 in approximately 12 months. Unfortunately many of the routers connected to the Internet cannot store more than 512,000 routes and once they fill up they could start behaving badly. This will have a knock on affect for the people and web sites behind affected routers, possibly even causing downtime. This article is intended to raise awareness giving people and companies the warning they need to prepare.

      • Jim says:

        Good sum up in layman’s terms. 😉

        Looks like network infrastructure guys are going to have their hands full soon enough

  2. scott says:

    Can you advice of manufacturers that are affected by this issue and how to find out the maximum bgp prefix on a router?

  3. Sean Gonsman says:

    It seems we have just reached the 512,000 threshold. There are major internet outages reported today:

    You can see a nice graph of the GRT here:

    Could this be the reason for the outages?

    • Mark Sutton says:

      Absolutely! What happened yesterday was the result of routers unable to cope with a routing table >512k routes. Actually it was more of a warning shot, since a large ISP mistakenly added 15k routes in one go. They since withdrew the routes again and the net is settled again for now. But not for long – the problem has not been fixed, as not all routers can be reconfigured and many will need to be physically replaced which will take time.