Did you know the internet table can be compressed significantly? We explain how the PTX and ACX7000 routers running Junos EVO are currently implementing FIB compression.
FIB Compression has been discussed for a very long time in this industry, but what most people probably don't know: it's already very efficiently deployed in many production networks. The maximum compression ratio we can get on today's internet table is 82% but we found in production networks it was reducing the FIB table by 50-65% in most cases.
This article has been initially written for PTX Series but the exact same feature is implemented on all ACX7000 routers (with the exception of the ACX7024).
RIPE NCC announced in November 2019 they made their final IPv4 allocation, and still, the public internet table is growing at a constant rate, exceeding 930,000 entries at the time of this publication (September 2022). IPv4 table is a very constrained resource, you can easily imagine that IPv6 table is growing significantly faster and the entries are larger by nature. The CIDR Report presents in their aggregation report how different Autonomous Systems disaggregate their allocated prefixes.
In light blue, we represent the routes received from the BGP neighbors. Note that routes can be learned from any source, BGP, IGP, local, or static, ... It's not relevant in this context, we just happened to use BGP to easily advertise large tables.
In green, we represent prefixes compressed by the algorithm.
In dotted line, the prefixes are not installed in hardware.
In solid line, the prefixes are pushed in FIB.
High-level description of the mechanisms used to compress the FIB
Implementation on PTX devices: support and limitations
Verification of these principles with concrete examples in the lab
How far we can compress today's internet table? What could be the best case?
The demonstration we don't lose a single packet when reshuffling the compression tree
How efficiently it compresses routes in our customer's networks?
In the Diagram 2 example, three prefixes are received from a BGP speaker, all pointing to the same NH1. The two /31s are "covered" by the superset /30. 192.0.2.4/31 and 192.0.2.6/31 are "shadowed" and not pushed in the PFE FIB, we will only install the /30.
In Diagram 3, we demonstrate two compression levels:
.12/32 and .13/32 can be aggregated to .12/31
.13/32 and .14/32 can be aggregated to .14/31
And these two aggregates can be summarized themselves to .12/30
We are installing a single route, 192.0.2.12/30.
Keep in mind these prefixes need to have the same forwarding behavior. That means, the same next-hop address:
Figure 5: Example with Different Next-Hop Addresses
The example in Diagram 4 illustrates why it's not possible to aggregate these 12 prefixes to a unique 192.0.2.0/28: three of them "in the middle" don't have the same Next-Hop address. Yet, we can summarize this tree into three routes.
Note: the aggregation is not limited to prefixes of similar length. We gathered multiple /32s and multiple /31s prefixes to generated 192.0.2.0/29.
The following example is showing another level of subtleties for the compression algorithm.
Figure 6: More Specific Prefix Scenario.
In this situation, the router received 5 prefixes:
Four of them can be aggregated to 192.0.2.0/29
The last one 192.0.2.5/32 is more specific than the received 192.0.2.4/31 but is pointing to a different NH2, so it's not "shadowed".
This 5th prefix is not breaking the tree structure and doesn't affect the compression. We will install two prefixes in hardware: 192.0.2.0/29-->NH1 and 192.0.2.5/32-->NH2
The compression ratio will be different from customer to customer, and even between two routers in different places/roles in the network. Not only the number but the variety of next-hop addresses will influence the algorithm performance.
Later in this article, we will demonstrate how far we can compress the public view using a single next-hop (the best possible case). And we will present the FIB space reduction, measured in different live networks.
The compression algorithm handles unicast IPv4 and IPv6 prefixes. The advertising protocols (or even local, static, ...) used to learn these routes are not important because compression is performed at the FIB level. It works for routes in inet.0 or L3VPN VRFs. Finally, it has no impact on uRPF check.
FIB compression is not implemented for multicast routes. The size of the multicast tables wouldn't justify it.
Some "features" can prevent routes from being aggregated, like:
In such cases, the specific routes will not be compressed.
Today, the first routers to natively support the features are the PTX powered by Express 4 chipset and running Junos EVO:
PTX10001-36MR
LC1201 and LC1202 line cards in PTX10000 chassis
Other platforms based on Junos EVO will implement the same algorithm soon.
FIB compression has been introduced for the PTX platforms listed above starting from 21.2R1. The feature is enabled by default, it doesn't require any specific configuration.
The algorithm is implemented at the line card CPU by the "evo-aftman-bt" process. You notice it doesn't happen at the Routing Engine (RE) level but in a distributed fashion, as close as possible to the PFE.
The routes are not modified in the RIB, or other protocol tables, therefore, compression does not affect redistribution.
Figure 7: Implementation of the Compression Algorithm in PTX Router
Diagram 6 represents a chassis with Express 4 Line Cards.
In a fixed form-factor router like PTX10001-36MR, it's simplified: we don't need to replicate the route objects in the Distributed DataStore (DDS) for example. In our chassis example, the prefixes are distributed via this datastore and the evo-aftman-bt will construct the radix tree. The compression happens here. Eventually, the evo-cda-bt process will program the compressed FIB in the PFE hardware table.
Let's have a look at the behavior of this algorithm in the lab with concrete examples. We will use a router connected to a route and traffic generator, symbolized with this icon in the following diagrams:
192.0.2.12/32 and 192.0.2.13/32 are compressed to 192.0.2.12/31 (in blue) 192.0.2.14/32 and 192.0.2.15/32 are compressed to 192.0.2.14/31 (in blue) - both /31 aggregates from the previous step are also aggregated into 192.0.2.2/30 (in green) - And it continues level after level up to 192.0.2.0/28 - The NH type "software" represents the entries created by the compression algorithm.
regress@rtme-ptx10:pfe> show route proto ip index 0 prefix 192.0.2.14/32 detail
Protocol : IPv4
Table : default
Prefix : 192.0.2.14 (primary)
NH : 13027 (software)
Flags : 0x00008000
Details :
guid : 833230259553
type : user
nhid : 13027
Forwarding state:
installed? : no
(Installed parent: 192.0.2.0/28)
regress@rtme-ptx10:pfe> show route proto ip index 0 prefix 192.0.2.0/28 detail
Protocol : IPv4
Table : default
Prefix : 192.0.2.0/28 (primary)
NH : 13027 (software)
Flags : 0x00008000
Details :
guid : 0
type : user
nhid : 13027
Forwarding state:
installed? : yes
nh-token : 6068
regress@rtme-ptx10:pfe>
In this last output, we check the handling of a specific prefix (192.0.2.14/32) and we can notice it's not installed in favor of the parent prefix 192.0.2.0/28.
The neighbour 15.1.2.2 advertises a single route 192.0.2.12/32 modifying the structure of the tree, leading to a less efficient compression ratio:
Figure 12: New Radix Tree after new NH injection
We verify the aggregation and the prefixes not installed in FIB with the following CLI.
The aggregated routes are those computed by the algorithm and represented in green in the diagram. The uninstalled routes are represented in dotted lines in the diagram.
If you don't want to verify each prefix one by one, count them: we have seven aggregate entries in the output (and seven green boxes in the diagram). In the same manner, we have fourteen entries in the uninstalled CLI ouput (and fourteen dotted line boxes in the diagram too).
We can also check specific prefixes and see which ones are installed or not. If not, the output gives us the installed parent.
This other test will illustrate the "more specific prefix" principle detailed earlier. A large block of contiguous /24s is aggregated and a more specific /25 with a different next-hop is added in the mix:
Figure 13: Advertisement of More Specific Prefixes
As mentioned earlier, this feature is activated by default on the Express 4 routers since Junos release 21.2R1: it has been deployed in many production networks and we can verify the compression performance in real conditions.
"Indirect" represents the next-hop addresses used by BGP in our case.
In this chart, we have RIB table, number of next=hop and the compression efficiency (representing the FIB space reduction).
RIB Table size
Number of NH
FIB Space Reduction
Customer A IPv4
913170
137
59%
Customer A IPv6
155979
137
62%
Customer B IPv4
884835
1600
55%
Customer B IPv6
149367
1600
60%
Customer C IPv4
968587
2030
56%
Customer C IPv6
153519
2030
60%
When the feature has been introduced in 2020, we also measured the compression in diverse networks (IPv4 and IPv6 public tables were slightly smaller).
RIB Table size
Number of NH
FIB Space Reduction
Customer 1 IPv4
814621
133
69%
Customer 2 IPv4
816791
148
61%
Customer 3 IPv4
801872
1000
69%
Customer 4 IPv4
838589
59
86%
Customer 5 IPv4
958854
2538
55%
Customer 6 IPv4
967325
1815
61%
Customer 7 IPv4
811385
453
58%
Customer 8 IPv6
83313
21
54%
The recent examples are showing a compression performance ranging from 50% to 62%. The marketing message "compression doubles the FIB space", is even conservative in some cases.
Every network will show a different level of compression depending on the way routes are mapped to next hop addresses:
In the best case, all best routes will point to a unique NH (that's what we test in next section).
In the worst pathological case, all contiguous routes are using different next-hop addresses and can not be compressed.
To illustrate the worst case, we are taking a portion of the potaroo routes used in next section. They have three BGP feeds / NH addresses, and the variety of NH prevents compression for this specific series of routes.
Consequently, we can NOT derive a rule to estimate the compression performance based on the number of next-hop addresses present in the table. We can't predict how prefixes are linked to each NH and how they are distributed. It shows the limits of what we can do in the lab. To estimate the compression benefits before deploying the PTX in production, you'll need the full output of routes and next-hop information. The real life numbers presented in the chart above are the most definitive proof of the algorithm efficiency.
To understand how far the current internet table can be compressed, we advertised the internet routes present in https://bgp.potaroo.net/as2.0/bgptable.txt to "single-attached" router.
Figure 15: Best Case Test Topology
Of course, a single default route would do the same job ;)
But the purpose of this test is to identify how far we can compress a current internet table if all existing routes point to the same next hop. That represents the best case we can reach with this implementation.
It's an interesting finding. In September 2022, with the internet view proposed by potaroo.net, we can compress the IPv4 table by 82% (that means it will occupy only 18% of the space it would have used without compression) and the IPv6 table by 72%.
Again, it's an best-case scenario for internet table. But your table can potentially contain many IGP routes that can be compressed too.
What happens when a network event triggers the rebuild of the radix tree and the re-installation of FIB table blocks? It's a legitimate question since the network and internet are not static, you may receive new routes, or existing routes could be resolved by a new Next-Hop address (a different peering point for example).
Like every Junos process, the FIB compression implementation follows a make-before-break logic. That means that all the changes are brought into the FIB before we remove the previous entries. It guarantees we don't create any black holes while the system is converging.
We will run the following test in the lab to demonstrate the compression algorithm doesn't cause any packet drop while re-constructing a large tree.
Let's start with a very big aggregation of 1M contiguous /31 routes into a single /11.
Figure 16: Advertisement of 1M Contiguous Prefixes
regress@rtme-ptx10:pfe> show route proto ip index 0 select installed
Index Destination NH Id NH Type NH Token GUID
----- -------------------------------- --------- --------- --------- --------
0 default 34 discard 1140 833223655665
0 0.0.0.0 34 discard 1140 622770257990
<SNIP>
0 15.1.3.255 11034 bcast 5464 841813591844
0 193.0/11 13036 software 6104 0
0 224/4 35 mdiscard 1141 622770257992
0 224.0.0.1 31 mcast 1137 622770257985
0 255.255.255.255 32 bcast 1138 622770257987
regress@rtme-ptx10:pfe>
Now, we break the aggregation structure with the advertisement of two /32s in the middle of this perfect alignment via a different eBGP peer (therefore, a different NH address)
Figure 17: Additional Advertisement of Two /32 Prefixes
The introduction of these two routes reshuffled the compression and we have 21 entries programmed in the FIB instead of one.
Now that we know what the advertisement of these two prefixes does on the compression structure, let's verify the potential collateral impact on traffic.
We will move back and forth between two "states" in the lab.
State 1:
A full internet v4 table is advertised on top of the previous million /31s entries. And we generate traffic to these prefixes. All of them. It represents more or less 2M routes, and streams.
We advertise the two prefixes from a different next-hop, breaking the 1M aggregation and creating a re-computation of the tree, while having the "background traffic" of all internet routes.
regress@rtme-ptx10> show route 193.2.41.136
inet.0: 1979003 destinations, 1979003 routes (1979003 active, 0 holddown, 0 hidden)
+ = Active Route, - = Last Active, * = Both
193.2.41.136/32 *[BGP/170] 00:00:12, localpref 100
AS path: 65002 I, validation-state: unverified
> to 15.1.2.2 via et-0/0/0:1.0
mgmt_junos.inet.0: 3 destinations, 3 routes (3 active, 0 holddown, 0 hidden)
+ = Active Route, - = Last Active, * = Both
0.0.0.0/0 *[Static/5] 3d 16:33:58
> to 10.83.153.254 via re0:mgmt-0.0
regress@rtme-ptx10> show route 193.2.41.137
inet.0: 1979003 destinations, 1979003 routes (1979003 active, 0 holddown, 0 hidden)
+ = Active Route, - = Last Active, * = Both
193.2.41.137/32 *[BGP/170] 00:00:09, localpref 100
AS path: 65002 I, validation-state: unverified
> to 15.1.2.2 via et-0/0/0:1.0
mgmt_junos.inet.0: 3 destinations, 3 routes (3 active, 0 holddown, 0 hidden)
+ = Active Route, - = Last Active, * = Both
0.0.0.0/0 *[Static/5] 3d 16:33:55
> to 10.83.153.254 via re0:mgmt-0.0
regress@rtme-ptx10>
We have this background traffic going to every internet prefix in the table and every one of these 1M /31 prefixes. Plus, we have this specific stream block for the two /32 prefixes that will be received via et-0/0/0:2 or et-0/0/0:3 depending on the advertisement.
On the traffic/route generator, we will alternate advertisements and withdrawals.
After 10 changes, we check the total number of packets on both ports (verifying we received as much as we sent).
Figure 20: IXIA Results
695,477,144 packets sent and received: As expected, not a single packet dropped in this experiment.
We understand that we can't go very far in a lab, but it demonstrates the make-before-break approach used in our implementation. No impact on the prefixes being compressed or "de-aggregated" and no impact on the traffic carried by other prefixes in the table.
Many thanks to Suneesh Babu, Dmitry Shokarev, Dmitry Bugrimenko, Edward Ricioppo, Zuhair Makawa, Kevin F Wang and Alex Varghese for their help describing the FIB compression concepts, testing it in our Sunnyvale labs, and collecting data from customer deployments.
