IS-IS and OSPF Support for Loop-Free Alternate Calculation

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

Figure 1 illustrates a simple network topology with point-to-point (P2P) interfaces and highlights three routes to reach router R5 from router R1.

Figure 1. Topology with Primary and LFA Routes

The primary route is by way of R3. The LFA route by way of R2 has two equal cost paths to reach R5. The path by way of R3 protects against failure of link R1-R3. This route is computed by R1 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. R2 must be loop-free with respect to source node R1.

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. Thus 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, then the LFA next-hop R2 provides node protection because a packet to R5 always goes over R4. In other words it is required that R2 becomes loop-free with respect to both the source node R1 and the protected node R3.

Consider the case where the primary next-hop uses a broadcast interface as illustrated in Figure 2.

Figure 2. 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’s Pseudo-Node (PN). However, because R2 has also a link to that PN, its cost to reach R5 by way of the PN or router R4 are the same. Thus 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, then R2 next-hop is an LFA providing link protection.

The following are the detailed rules for this criterion as provided in RFC 5286:

• Rule 1: Link-protect LFA backup next-hop (primary next-hop R1-R3 is a P2P interface): Distance_opt(R2, R5) < Distance_opt(R2, R1) + Distance_opt(R1, R5) and, Distance_opt(R2, R5) ≥ Distance_opt(R2, R3) + Distance_opt(R3, R5)

• Rule 2: Node-protect LFA backup next-hop (primary next-hop R1-R3 is a P2P interface): Distance_opt(R2, R5) < Distance_opt(R2, R1) + Distance_opt(R1, R5) and, Distance_opt(R2, R5) < Distance_opt(R2, R3) + Distance_opt(R3, R5)

• Rule 3: Link-protect LFA backup next-hop (primary next-hop R1-R3 is a broadcast interface): Distance_opt(R2, R5) < Distance_opt(R2, R1) + Distance_opt(R1, R5) and, Distance_opt(R2, R5) < Distance_opt(R2, PN) + Distance_opt(PN, R5) where; PN stands for the R1-R3 link Pseudo-Node.

For the case of P2P interface, if SPF finds multiple LFA next-hops for a specific primary next-hop, it follows the following selection algorithm:

1. It 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, then it picks one based on the least cost.

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

For the case of 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 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 which do not go over the PN used by primary next-hop.

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

2. If there is more than one LFA next-hop in the first set, it 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, then it picks one based on the least cost.

4. If more than one LFA next-hop with equal cost results from Step C, 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 B-D using the second set.

This algorithm is more flexible than strictly applying Rule 3 above; the link protect rule in the presence of a PN and specified in RFC 5286. A node-protect LFA which does not avoid the PN; does not guarantee link protection, can still be selected as a last resort. The same thing, a link-protect LFA which does not avoid the PN may still be selected as a last resort. Both the computed primary next-hop and LFA next-hop for a specific prefix are programmed into RTM.