OSPF and IS-IS support for LFA calculation

SPF computation in IS-IS and OSPF is enhanced to compute LFA alternate routes for each learned prefix and populate it in RTM.

The following figure shows a simple network topology with point-to-point (P2P) interfaces and highlights three routes to reach router R5 from router R1.

Figure: Example topology with primary and LFA routes

The primary route is via R3. The LFA route via R2 has two equal cost paths to reach R5. The path by way of R3 protects against failure of link R1-R3. R1 computes this route by checking that the cost for R2 to reach R5 by way of R3 is lower than the cost by way of routes R1 and R3. This condition is referred to as the Loop-free Criterion (LFC).

The path by way of R2 and R4 can be used to protect against the failure of router R3. However, with the link R2-R3 metric set to 5, R2 sees the same cost to forward a packet to R5 by way of R3 and R4. Therefore, R1 cannot guarantee that enabling the LFA next-hop R2 protects against R3 node failure. This means that the LFA next-hop R2 provides link protection only for prefix R5. If the metric of link R2-R3 is changed to 8, the LFA next-hop R2 provides node protection since a packet to R5 always goes over R4. That is, it is required that R2 become loop-free with respect to both the source node R1 and the protected node R3.

The following figure shows an example where the primary next hop uses a broadcast interface.

Figure: Example topology with broadcast interfaces

In order for next-hop R2 to be a link-protect LFA for route R5 from R1, it must be loop-free with respect to the R1-R3 link Pseudo-Node (PN). However, because R2 also has a link to that PN, its cost to reach R5 by way of the PN or router R4 is the same. Therefore, R1 cannot guarantee that enabling the LFA next-hop R2 protects against a failure impacting link R1-PN, because this may cause the entire subnet represented by the PN to go down. If the metric of link R2-PN is changed to 8, R2 next-hop is an LFA providing link protection.

The following are the detailed equations for this criterion as described in RFC 5286, Basic Specification for IP Fast Reroute: Loop-Free Alternates:

For a P2P interface, if SPF finds multiple LFA next-hops for a specified primary next-hop, it uses the following selection algorithm.

  1. SPF picks the node-protect type in favor of the link-protect type.

  2. If there is more than one LFA next-hop within the selected type, SPF picks one based on the least cost.

  3. If more than one LFA next-hop with the same cost results from step 2, SPF selects the first one. This is not a deterministic selection and varies following each SPF calculation.

For a broadcast interface, a node-protect LFA is not necessarily a link-protect LFA if the path to the LFA next-hop goes over the same PN as the primary next-hop. Similarly, a link-protect LFA may not guarantee link protection if it goes over the same PN as the primary next-hop. The selection algorithm when SPF finds multiple LFA next-hops for a specified primary next-hop is modified as follows.

  1. The algorithm splits the LFA next-hops into two sets.

    • The first set consists of LFA next-hops that do not go over the PN used by the primary next-hop.

    • The second set consists of LFA next-hops that go over the PN used by the primary next-hop.

  2. If there is more than one LFA next-hop in the first set, SPF picks the node-protect type in favor of the link-protect type.

  3. If there is more than one LFA next-hop within the selected type, SPF picks one based on the least cost.

  4. If more than one LFA next-hop with equal cost results from step 3, SPF selects the first one from the remaining set. This is not a deterministic selection and varies following each SPF calculation.

  5. If no LFA next-hop results from step D, SPF reruns steps 2 through 4 using the second set.

This algorithm is more flexible than strictly applying the preceding Rule 3; that is, the link-protect rule in the presence of a PN and specified in RFC 5286. A node-protect LFA that does not avoid the PN, that is, does not guarantee link protection, can still be selected as a last resort. Similarly, a link-protect LFA that does not avoid the PN can still be selected as a last resort.

Both the computed primary next-hop and LFA next-hop for a specified prefix are programmed into RTM.

Parent topic: IP Fast-Reroute for OSPF and IS-IS prefixes