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 platform using software-based switching 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 you have 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 have to 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 made sense to implement LFA for those routing protocols as well.

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. More in a future post ...

The fun part – Where am I going?

This is the second article in the path that started with OSPF Loop Free Alternates. Can you guess where I’m going to as I’m slowly unwinding the recursion spaghetti that got me here?


No, this definitely doesn't look like my thought process (picture from The Red Brick Road)

12 comments:

  1. Павел Доронин27 January, 2012 08:28

    May be you start from here
    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

    ReplyDelete
  2. Good guess, and definitely another interesting topic (thank you!), but not even close.

    BTW, with LFA we don't always have loop-free alternative (Pierre Francois' presentation addressed that in details).

    ReplyDelete
  3. I'm sure that I'm way off here, but it's Friday and I'm hungover, so I'm using that as my excuse.

    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.

    ReplyDelete
  4. Attaboy!

    ReplyDelete
  5. Павел Доронин27 January, 2012 17:11

    Wow Tim! You are magician!

    ReplyDelete
  6. Hmmm, are you supporting my theory of your thought process, or my Thursday night binge? :)

    ReplyDelete
  7. Bertrand Duvivier20 February, 2012 03:19

    Ivan,

    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)

    ReplyDelete
  8. So Ivan, as i can see from the both article, there is no difference between LFA & PIC... Is it?

    ReplyDelete
    Replies
    1. It's my understanding that PIC is the backup-path-in-FIB mechanism, while LFA is an OSPF/IS-IS-specific solution that calculates those backup paths.

      Delete
    2. Thank you, Ivan!

      Delete
  9. I little typo Pierre Francoise => Pierre Francois at the second paragraph

    ReplyDelete

You don't have to log in to post a comment, but please do provide your real name/URL. Anonymous comments might get deleted.

Ivan Pepelnjak, CCIE#1354, is the chief technology advisor for NIL Data Communications. He has been designing and implementing large-scale data communications networks as well as teaching and writing books about advanced technologies since 1990. See his full profile, contact him or follow @ioshints on Twitter.