Prefix-Independent Convergence (PIC): Fixing the FIB Bottleneck
Did you rush to try OSPF Loop-Free Alternate on a Cisco 7200 after reading my LFA blog post… and disappointedly discovered that it only works on Cisco 7600? The reason is simple: while LFA does add feasible-successor-like behavior to OSPF, its primary mission is to improve RIB-to-FIB convergence time.
If you want to know more details, I would strongly suggest you browse through the IP Fast Reroute Applicability presentation Pierre Francois had @ EuroNOG 2011. To summarize what he told us:
- It’s relatively easy to fine-tune OSPF or IS-IS and get convergence times in tens of milliseconds. SPF runs reasonably fast on modern processors, more so with incremental SPF optimizations.
- A software-based switching platform can use the SPF results immediately (thus, there’s no real need for LFA on a Cisco 7200).
- The true bottleneck is the process of updating distributed forwarding tables (FIBs) from the IP routing table (RIB) on platforms that use hardware switching. That operation can take a relatively long time if the router has to update many prefixes.
The generic optimization of the RIB-to-FIB update process is known as Prefix-Independent Convergence (PIC). If the routing protocols can pre-compute alternate paths, suitably designed FIB can use that information to cache alternate next hops. Updating such a FIB no longer involves numerous updates to individual prefixes; you must change only the next-hop reachability information.
PIC was first implemented for BGP (you can find more details, including interesting discussions of FIB architectures, in another presentation Pierre Francois had @ EuroNOG), which usually carries hundreds of thousands of prefixes that point to a few tens of different next hops. It seems some Service Providers carry way too many routes in OSPF or IS-IS, so it also made sense to implement LFA for those routing protocols.
In its simplest form, BGP PIC goes a bit beyond exiting EBGP/IBGP multipathing and copies backup path information into RIB and FIB. Distributing alternate paths throughout the network requires numerous additional tweaks, from modified BGP path propagation rules to modified BGP route reflector behavior.
IGP-based “restoration” techniques have one important problem. During the time of re-convergence, temporary micro-loops may exist in the topology due to inconsistency of FIB (forwarding) tables of different routers. This behavior is fundamental to link-state algorithms, as routers closer to failure tend to update their forwarding database before the other routers.
Postet from here:
http://blog.ine.com/2010/06/02/ospf-fast-convergenc/
With LFA we always have Loop free alternative and avoid micro-loops during convergence. And you want to describe that nowtime something is changed?
Or maybe LFA applicabilityin SP networks?
http://tools.ietf.org/html/draft-ietf-rtgwg-lfa-applicability-06
BTW, with LFA we don't always have loop-free alternative (Pierre Francois' presentation addressed that in details).
Perhaps you are delving into a comparison of optimizations used for RIB-to-FIB convergence time for the routing protocols vs. what would be required in a controller-based OpenFlow environment.
You mentioned router not always have an LFA.
This true and depend of topoogy, ring topology for exemple is a good case.
Remote LFA will address this caveats. Remote LFA wil compute the PQ node and then establish a dLDP session with PQ node and establish a MPLS tunnel automatically.
PQ node is the first node not sending traffic back to the router.
Cisco implementation will be available in march 2012.
Bertrand (PM LFA, ISIS & BGP)