The Hierarchical FIB: How CEF Lets BGP Converge in Milliseconds
The Problem With a Flat FIB
Imagine an edge router carrying a full Internet table, around a million IPv4 prefixes, learned by iBGP from two PEs. Half of those prefixes use PE2's loopback as the BGP next hop and half use PE3's. Now the core link towards PE2 fails, and the IGP finds a new path to PE2 through another router. Nothing about BGP has changed: same prefixes, same next hop 2.2.2.2, same attributes. Only the way to reach 2.2.2.2 is different. How long does it take before all those prefixes forward correctly again?
The answer depends entirely on how the Forwarding Information Base is built. In a flat FIB, every prefix stores its own final forwarding answer: outgoing interface and Layer 2 rewrite, copied in when the route was installed. The recursion through 2.2.2.2 is resolved once and then forgotten. When the path to 2.2.2.2 changes, the router has to find every one of the half a million prefixes that used the old path and rewrite each entry. Convergence time grows with the size of the table, which is the worst possible property for a router that carries the Internet.
A hierarchical FIB keeps the recursion. Each BGP prefix in the FIB does not store an interface. It stores a pointer to a shared object that represents the next hop 2.2.2.2, and that object, in turn, points to the IGP path and adjacency that currently reach 2.2.2.2. Half a million prefixes share one object. When the IGP path changes, the router updates the single shared object, and every prefix behind it uses the new path at the same moment. Convergence no longer depends on how many prefixes there are. It depends only on how fast the IGP and one FIB update happen.
R1#show ip cef 192.0.2.0/24 detail
192.0.2.0/24, epoch 2
recursive via 2.2.2.2
nexthop 10.1.12.2 GigabitEthernet0/0
The "recursive via 2.2.2.2" line is the visible sign of the hierarchy. The prefix points to the next hop 2.2.2.2, and the indented line shows what that next hop currently resolves to. Any other prefix with next hop 2.2.2.2 shows the same structure, because they all point to the same object.
From Shared Next Hops to BGP PIC
Sharing the next hop solves one failure case, a change inside the core. It does not solve the harder case where the next hop itself disappears. If PE2 fails completely, there is no new path to 2.2.2.2 for the IGP to find. BGP must notice that 2.2.2.2 is gone, run its best path algorithm for every affected prefix, choose PE3 as the new next hop, and install the result. On a large table that is slow again, because it is per-prefix work in the control plane.
BGP Prefix Independent Convergence, BGP PIC, extends the hierarchy to fix this. The idea is to calculate the backup path before the failure and store it in the FIB alongside the primary. When the primary next hop becomes unreachable, the data plane switches all affected prefixes to the precomputed backup by changing one shared structure, and BGP can then reconverge at its own pace in the background without traffic waiting for it.
There are two parts to the feature, and they map onto the two failure cases. PIC Core covers failures inside the core, where the next hop is still reachable through another IGP path. It is the hierarchical FIB described above, and on IOS XE it is enabled by default. The command "#cef table output-chain build favor memory-utilization" turns it off and builds a flatter, smaller FIB, trading convergence speed for memory. PIC Edge covers the failure of the next hop itself, and it needs BGP to give CEF a second path to install as a backup.
The backup path has to exist in BGP first. By default a router only keeps the paths its neighbours send, and with route reflectors that may be only one path per prefix. Features such as additional paths, best external or diverse path exist to make sure the second path reaches the router. Once it is there, BGP is told to install it.
R1(config)#router bgp 65001
R1(config-router)#address-family ipv4 unicast
R1(config-router-af)#bgp additional-paths install
R1#show ip bgp 198.51.100.0
BGP routing table entry for 198.51.100.0/24, version 31
Paths: (2 available, best #1, table default)
Advertised to update-groups:
1
Refresh Epoch 1
64500
203.0.113.1 from 203.0.113.1 (203.0.113.1)
Origin IGP, metric 0, localpref 100, valid, external, best
Refresh Epoch 1
64500
3.3.3.3 (metric 20) from 3.3.3.3 (3.3.3.3)
Origin IGP, metric 0, localpref 100, valid, internal, backup/repair
The eBGP path is best and the iBGP path through PE3 is marked as the backup. This is the documented IPv4 case on IOS XE: an eBGP primary with an iBGP backup. The FIB now holds both.
R1#show ip cef 198.51.100.0/24 detail
198.51.100.0/24, epoch 2
recursive via 203.0.113.1
attached to GigabitEthernet0/2
recursive via 3.3.3.3, repair
nexthop 10.1.13.3 GigabitEthernet0/1
The second recursive path carries the word "repair". It is not used for forwarding while the primary is healthy, so this is not load sharing. It is a standby branch already resolved and waiting. When the eBGP link fails, CEF switches to the repair path without waiting for BGP to finish its work.
Design Rules and CCIE Edge Cases
With PIC in place, the remaining questions are about when it helps, what it costs and how it can mislead you, and they are the questions a CCIE candidate is expected to answer.
The first rule is that PIC only switches as fast as the router detects the failure. A directly connected eBGP link going down is detected almost immediately. A remote PE failing is detected when the IGP withdraws its loopback, or through BFD. If the only signal is the BGP hold timer expiring, the precomputed backup sits unused for up to three minutes. Fast detection is half of the design, and that is why PE loopbacks should be carried as /32 host routes. A summary or a default route can keep a dead next hop looking reachable, and then PIC never triggers at all.
The second rule is about memory. A hierarchical FIB with backup paths uses more memory than a flat one, because every prefix carries an extra branch. On routers with full tables and limited memory, "#cef table output-chain build favor memory-utilization" may be a deliberate choice. Know that it disables PIC Core, and document it.
The third rule is about interaction with other features. On IOS XE, "#bgp advertise-best-external" enables PIC by itself. If "#bgp additional-paths install" is entered after it on the same router, the second command is rejected. The two are related, not mutually exclusive in purpose, but the configuration order matters, so check the running configuration after the change rather than assuming both took effect.
The fourth rule concerns IOS XR, which builds its FIB on each line card. On XR, a PIC selection policy for a VPN must also be applied under the VRF address family. Otherwise the backup is selected in the VPNv4 table but never installed in the VRF RIB and CEF, and the repair path the design depends on simply does not exist in the data plane. As always, the FIB is the proof.
RP/0/RP0/CPU0:XR1#show cef vrf CUST-A 198.51.100.0/24
Wed Nov 11 18:42:10.531 UTC
198.51.100.0/24, version 112, source-destination sharing
Prefix Len 24
via 2.2.2.2/32, 0 dependencies, recursive
next hop 10.2.12.2/32 Gi0/0/0/0 via 10.2.12.0/24
valid remote adjacency
Only one path appears. If the design expected a backup through 3.3.3.3, this output says it is not there, whatever the BGP table shows.
The practical takeaway is that BGP convergence on a modern Cisco router is mostly a data plane property. BGP decides which paths exist and which is best, but the hierarchical FIB decides whether a failure costs milliseconds or minutes. When you design for fast convergence, read "#show ip cef" with the detail keyword, look for the "recursive via" structure and the "repair" branch, and trust the FIB over any control plane table.