Loop-Free Alternate: OSPF meets EIGRP

Assume we have a simple triangular network:

Now imagine the A-to-C link fails. How will OSPF react to the link failure as compared to EIGRP? Which one will converge faster? Try to answer the questions before pressing the Read more link ;)

EIGRP: Feasible successors

EIGRP tries to use feasible successors to speed up the convergence process. Whenever B reports its distance to X to A, A compares B’s reported distance to its current feasibility distance. Lower reported distance means that B doesn’t use A to get to X (A is not B's successor). B is also not A's successor for X (that’s C as long as the A-to-C link is operational), but it’s a feasible successor. Using B to get traffic to X will not result in a routing loop.

A feasible successor is evaluated for individual destinations. From A’s perspective, B is a feasible successor for X and C is a feasible successor for Y.

Faced with A-to-C link loss, A can switch immediately to the feasible successor (B) for destination X. Convergence is immediate.

OSPF: Let’s make sure we’re in sync

OSPF is way more lackadaisical:

  • It changes the LSAs affected by the updates and floods them ... unless there’s been a recent topology change, in which case it goes and sits quietly in a corner until the timers throttle lsa hold-interval expires.
  • It waits a bit more, silently lamenting its misery, until the timers throttle spf spf-start timer expires.
  • It runs SPF algorithm, computes the new OSPF shortest-path tree, and copies the results in the IP routing table.

Total convergence time: 5+ seconds (unless you’ve done some serious tweaking).

Loop-Free Alternate Fast Reroute: Feasible Successor for OSPF

There’s no reason OSPF couldn’t have reacted faster – every single router knows the whole topology of all attached areas and can thus easily calculate which of its neighbors could be feasible successors. That’s exactly what LFA is doing:

  • OSPF (or IS-IS) routing process runs SPF, computes its own best paths, and installs them in the IP routing table (RIB).
  • After the network has converged, OSPF runs SPF algorithm from the perspective of its neighbors. If a neighbor’s SPF tree doesn’t use current router as the next hop for a specific destination, it’s safe to use that neighbor as a feasible successor.
  • The feasible successor information calculated by OSPF is downloaded in RIB and FIB, where it can be used immediately after the link failure.

Can I use it?

Loop Free Alternate Fast Reroute is available for OSPF and IS-IS in Cisco IOS 15.1(3)S and XE 3.4S. The IS-IS implementation is pretty rudimentary; the OSPF implementation allows you to specify numerous alternate path selection criteria. For example, you might prefer alternate paths that don’t go over a shared risk link group, through the same LAN interface, or through the next-hop router.

You’ll also find LFA for IS-IS in (at least) Junos 9.5 and LFA for OSPF in Junos 10.0, and in IOS XR 3.5 (IS-IS) and 3.9 (OSPF).

More information

The fun part

I wanted to write about a completely different topic and realized I have to cover yet another topic to explain the root cause of the problem I wanted to describe.

demotivational posters - THAT MOMENT

My ramblings tend to be recursive (as anyone who was forced to listen to my campfire stories can probably attest), and it turned out the final leaf in that recursive process was LFA. Will you try to guess where I started?

20 comments:

  1. Павел Доронин26 January, 2012 07:11

    Is this feature only for ospf v2 not v3?

    ReplyDelete
  2. The LFA concept can be implemented in any link state routing protocol, current Cisco IOS and Junos implementations are for IS-IS and OSPFv2.

    ReplyDelete
  3. mihalachioaie@gmail.com26 January, 2012 07:55

    Ivan, great exercise. Can you also cover square topology?

    ReplyDelete
  4. Have you looked at Pierre's presentation (link in the post)?

    ReplyDelete
  5. Anton Marchenko26 January, 2012 09:29

    It's hard to predict EIGRP behavior without knowing link costs. Given the same link attributes (bandwidth and delay) for all links in the triangular topology B won't be the feasible successor for X because B reported distance is not lower, but the same as A feasible distance.

    ReplyDelete
  6. Anton Marchenko26 January, 2012 09:38

    Also what do you think about theoretical possibility of using alternate paths computed using LFA for OSPF and IS-IS for unequal cost load balancing (like it can be done with EIGRP)?

    ReplyDelete
  7. In theory, it would be possible. In practice? I don't even know how much the EIGRP functionality is used ... and you can use MPLS-TE to get better results.

    ReplyDelete
  8. look like ipfrr per prefix was introduced back in iox 3.5, may be they changed to per link in 3.9?
    http://www.cisco.com/en/US/docs/ios_xr_sw/iosxr_r3.5/routing/configuration/guide/rc35rib.html#wp1088695

    ReplyDelete
  9. But only about 5 people worldwide run MPLS inside an enterprise network, which is where UCMP would be quite valuable. Often enterprise sites each have a primary WAN link and slower, lower cost WAN link for redundancy.

    Enterprises will most likely not implement MPLS en masse anytime soon, as the majority of installed and currently orderable enterprise gear doesn't support MPLS at all.

    ReplyDelete
  10. My humble quess is that you wanted to cover topology predictibility and/or link-state microloops? I dump LDP FRR cause it's closely related.

    ReplyDelete
  11. My first thought before I hit "read more" was - it depends". For OSPF, what if the two paths were equal costs? Then it would be immediate failover because the route already exist in the RIB.

    ReplyDelete
  12. Piotr Jablonski27 January, 2012 00:32

    In terms of convergence:
    1. On the CPU based platforms there should be no difference between EIGRP and IP LFA.
    2. On the distributed platforms IP LFA will be faster as HW FIB is ready for a switchover.

    In terms of your recursive process maybe you started at the intra-AS BGP convergence topic or possibility of the fast path switchover when you were in the serious traffic jam?

    ReplyDelete
  13. Great post. I did a lot of EIGRP work in the late 90s and early to mid 00s. One gig I was on was convert a very large utility from a mixed routing protocol to all EIGRP. Ivan's book on EIGRP was critical to my design and migration approach. EIGRP is very fast on convergence and when I was reading about MPLS Fast Reroute it reminded of EIGRP's feasible successor ability but manually created. Also there is adjusting timers for EIGRP, debounce timers, carrier delays NSF and BFD. OSPF has these options too. Now throw MPLS into it, LSPs need a L3 routing protocol to connect and you have more "junk" on top of your topology to influence convergence. I even for one client used the variance unequal cost load balancing feature to solve a problem. I haven't done much with it lately and not sure of its status. I liked EIGRP and if they update it can still be very very powerful.

    sheeshe it is 2012 where is that one protocol for all.

    Okay where is the post for IPX/SPX where you can have a 10k node network and none of the subnetting issues etc and now since we can all have 1 to 10gig links who cares if it is a heavy protocol. ;)

    ReplyDelete
  14. #1 - There should be no difference if you fine-tune the OSPF/IS-IS timers. With the default values, there will be 5+ second difference.

    #3 - Good thinking, but I started somewhere far far away 8-)

    ReplyDelete
  15. Piotr Jablonski27 January, 2012 11:30

    1. For default values on IOS yes, there will be a difference but not on IOS XR where timers are tuned by default.

    But my comment was for IPLFA vs. EIGRP. :)

    ReplyDelete
  16. Dhana Kaneshayogan27 January, 2012 16:01

    Strictly speaking, if the links were equal cost, then A would have no feasible successor to X via B if it lost the A-C link. The EIGRP feasibility condition is a strict one, and the cost for B-X via C must be less than A-X via C for the condition to be met.

    In practice when testing I see much quicker failover than OSPF dead time expiry. I reckon the link failure is detected in hardware, RIB, FIB entries are removed and this potentially forces OSPF to recalculate a path?

    ReplyDelete
  17. Nice, except it morse code compared to your articles :)

    ReplyDelete
  18. Or other "sane" networking operating systems where archaic timers don't exist. (i.e: Junos). Anyone know the timers on NX-OS?

    ReplyDelete
  19. ISR routers support MPLS, 6500's and Nexus support MPLS? What doesn't support it these days? Closet level switches?

    In other vendors, Juniper and other support MPLS as well. I think the adoption doesn't have to do with gear as much as it does with education.

    ReplyDelete
  20. Downstream paths have been talked about in IS-IS in the ISO10589 specification from 1980's. The spec on page 20 states:

    -> a set of paths which will get a PDU closer to its destination than the local system: these are called downstream paths

    The basic idea is as long as the cost from the neighbor is less than the cost from me, I can forward the packet for a particular destination to it.

    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.