Advertising Aggregates Routes

As a BGP admin, you will often need to make decisions on the ways to partition your IP Space, which routes to advertise to the Internet and which routes to suppress.

Ideally, you’d want to aggregate your IPv4/IPv6 Space as much as possible, by only advertising aggregate prefixes (also known as supernets and summary routes) to the Internet. Practically, this would mean that your Autonomous System (AS) will originate IP prefixes assigned to you by Regional Internet Registries (RIRs) or delegated to you by Upstream Providers, while suppressing all other advertisements. If everybody were to follow this rule, the Internet routing table would be much smaller and we would not have issues with FIB exhaustion.
Continue reading “Advertising Aggregates Routes”

2017 BGP Table Size Prediction and Potential Impact on Stability of Global Internet Infrastructure

Introduction

In this article, we will attempt to forecast the size of global internet routing table and analyze the potential impact of aforementioned routing growth on the stability of Internet infrastructure.

Global routing infrastructure is comprised of IPv4 and IPv6 routes advertised by BGP-speaking service providers and enterprises.  These BGP advertisements are processed by the routers and eventually programmed into special tables called Forwarding Information Table (FIB). There is a limit a number of FIB entries a particular system can support before running out of FIB capacity. The maximum FIB capacity of the platform is determined by such factors as ASIC, amount of memory, software license, etc.

Even within a single vendor’s portfolio, the maximum FIB size of available platforms varies dramatically, from a few thousand entries in a low-cost top or rack switch up to millions of entries in an expensive Internet router. It is important to note, that advertised FIB numbers may only be applicable to certain (typically IPv4) routes. Other route types, such as MPLS VPN and IPv6, might require more memory per entry, decreasing the overall FIB capacity.

For example, Cisco’s Catalyst 6500 / 7600 with 3BXL supervisor can support 1 Million IPv4 routes, but only 512K IPv6 routes.

It is also important to note, that not all vendors will support dynamic allocation of FIB entries between route-types. Instead, FIB might be pre-partitioned to support some arbitrary number of entries of a certain type. Previously mentioned 3BXL supervisor comes preconfigured to support 512K IPv4 + MPLS entries and 256K IPv6 + Multicast entries. It is easy to spot that in Cisco’s SUP720 implementation IPv6 routes take twice as much space as IPv4 entries.

Historic perspective

The problem of FIB capacity and growing Internet size is not new.

Multiple outages were reported back in 2008 when Internet BGP table size crossed 256K limit and again in 2014 when 512K entries limit was exceeded.

Service Providers and BGP-speaking enterprises had to take remedial actions in order to maintain Internet stability. We will discuss these actions later.

Internet Growth

There are two major forces that drive Internet table size growth – IPv4 space partitioning and new IPv6 advertisements.

IPv4 address exhaustion (https://en.wikipedia.org/wiki/IPv4_address_exhaustion) that occurred before 2011 and 2015 did not slow down the speed of IPv4 table growth, instead it accelerated the fragmentation of IPv4 space.

IPv4 Table Size Projection

As mentioned previously, IPv4 table size continues its rapid expansion, demonstrating approximately 10% year-over-year growth over the past few years.

2009 to 2017 IPv4 Table Size Growth:

2009 2010 2011 2012 2013 2014 2015 2016 2017
Table
Size (Thousand Routes)
286 316 345 409 466 499 536 591 648
Year
over
Year (%)
18 10 9 19 14 7 7 10 10

2017 IPv4 Table Size Growth to Date:

Month Jan Feb Mar Apr May Jun Jul Aug Sep Oct
Table Size (Thousand Routes) 648 653 663 663 673 676 679 684 688 691
Month over Month (%) 0.7 1.5 0.1 1.5 0.5 0.4 0.7 0.5 0.5
Compared to January (%) 0.7 2.2 0.3 3.9 4.4 4.8 5.5 6.1 6.6

Our statistical model shows that if this growth continues, global Internet table will surpass 1 Million entries sometime in 2020.

IPv4 BGP Table Size Growth Projection
IPv4 BGP Table Size Growth Projection

IPv6 Table Size Projection

As IPv6 gets adopted by Service Providers and Enterprises, IPv6 table size is also expected to continue to raise. The current year-over-year growth is about 30% with no signs of deceleration.

2009 to 2017 IPv6 Table Size Growth:

2009 2010 2011 2012 2013 2014 2015 2016 2017
Table Size (Thousand Routes) 1.6 2.5 4.1 7.7 12 17 22 27 37
Year
over
Year (%)
65 52 65 86 56 41 29 25 35

2017 IPv6 Table Size Growth to Date:

Jan Feb Mar Apr May Jun Jul Aug Sep Oct
Table Size (Thousand Routes) 36 37 38 39 40 40 42 43 44 44
Month over Month (%) 2.7 3.0 0.8 2.2 1.1 3.1 2.7 2.0 0.4
Compared to January (%) 2.7 5.7 6.6 9.0 10.3 13.7 16.7 19.0 19.5

While IPv6 table is not expected to grow to the same size as IPv4 table due to much bigger initial block allocations by the registries, ongoing IPv6 adoption will nonetheless lead to the table size increase.

IPv6 BGP Table Size Growth Projection
IPv6 BGP Table Size Growth Projection

FIB Utilization

IPv4 and IPv6 table size increases will translate into FIB size increase. The actual impact on your router will depend on a specific vendor’s implementation. In the best-case scenario, you will observe one-to-one correlation between the combined size of IPv4 and IPv6 tables and FIB table. More common scenario might be IPv6 entries using twice as much space as IPv4 entries. This later scenario is depicted below:

FIB Size Growth Projection

As you can deduce from the graph, routers that are capable of supporting 1Mln routes, will run out of FIB space sometime in 2019. In fact, you might run into problems much earlier than that, if you have

  • Large number of disaggregated internal routes, such as loopbacks, point-to-point IPs and customer routes
  • BGP policy allowing to accept long (>24) prefixes from external peers
  • Extensive public and private peering with partners who might advertise more specific routes not otherwise visible in the public Internet
  • Provide other services that require FIB space, such as Mutlicast, MPLS VPN, L2 VPN, etc.

What to expect

Assuming that the FIB size of your Internet-facing router is limited by 1 Mln entries, you can expect to run into issues sometime in 2019. The actual impact will depend on the platform in use. Some systems might attempt to fall back to RE-based forwarding for the destinations which could not be programmed in hardware. This might lead to high CPU utilization on the entire system and general instability of the router.

Other systems will simply drop traffic to such destinations. This scenario can manifest itself by customers unable to reach some sites on the Internet, while accessing other sites. You should monitor system logs and FIB utilization to spot the issue.

How to prepare

As an administrator, there are a few things you should do to be ready to withstand Internet size growth:

  • Understand your system’s FIB capacity to make sure you have enough room to accommodate expected Internet growth
  • If your system allows changing FIB partitioning, make sure it is set up in the most optimal way. For example, you might want to allow for up to 800K IPv4 and 100K IPv6 routes
  • If possible, upgrade your systems to support at least 2Mln FIB entries. This is applicable to both Routing Engine and Line Cards
  • If upgrade is not viable at the moment, consider inbound route-filtering to decrease the number of routes accepted from your peers. The general consensus is that you can safely drop all IPv4 /25 and longer prefixes while maintaining full reachability of Internet destinations.

Conclusion

Internet global routing table continues to grow with no signs of slowing down. The major contributor to this growth is an ongoing IPv4 disaggregation, as well as a proliferation of IPv6 Internet. As a network administrator, you need to be prepared to protect your network from negative consequences of this growth by optimizing your routing policies and upgrading physical infrastructure.