TI-LFA algorithm

At a high level, the TI-LFA link protection algorithm searches for the closest Q node to the computing node and then selects the closest P node to this Q node, up to a number of labels corresponding to the value of ti-lfa max-sr-frr-labels labels, on each of the post-convergence paths to each destination node or prefix D. Consider the topology in Figure: Selecting link-protect TI-LFA backup path where router R3 computes a TI-LFA next hop for protecting link R3-R4.

For each destination node D:

1. Compute the post-convergence SPF on the topology without the protected link.

   In Figure: Selecting link-protect TI-LFA backup path, R3 finds a single post-convergence path to destination D via R1.

   Note: The post-convergence SPF does not include IGP shortcut.

2. Compute the extended P-Space of R3 with respect to protected link R3-R4 on the post-convergence paths.

   This is the set of nodes Yi in the post-convergence paths which are reachable from R3 neighbors without any path transiting the protected link R3-R4.

   R3 computes an LFA SPF rooted at each of its neighbors within the post-convergence paths, that is, R1, using the following equation:

   Distance_opt(R1, Yi) < Distance_opt(R1, R3) + Distance_opt(R3, Yi)

   Where, Distance_opt(A,B) is the shortest distance between A and B. The extended P-space calculation yields only node R1.

3. Compute Q-space of R3 with respect to protected link R3-R4 in the post-convergence paths.

   This is the set of nodes Zi in the post-convergence paths from which the neighbor node R4 of the protected link, acting as a proxy for all destinations D, can be reached without any path transiting the protected link R3-R4.

   Distance_opt(Zi, R4) < Distance_opt(Zi, R3) + Distance_opt(R3, R4)

   The Q-space calculation yields nodes R2 and R4.

   This is the same computation of the Q-space performed by the remote LFA algorithm, except that the TI-LFA Q-space computation is performed only on the post-convergence.

4. For each post-convergence path, search for the closest Q-node and select the closest P-node to this Q-node, up to a number of labels corresponding to the value of ti-lfa max-sr-frr-labels labels.

   In the topology in Figure: Selecting link-protect TI-LFA backup path, there is a single post-convergence path, a single P-node (R1), and the closest of the two found Q-nodes to the P-Node is R2.

   R3 installs the repair tunnel to the P-Q set and includes the node-SID of R1 and the adjacency SID of the adjacency over link R1-R2 in the label stack. Note that because the P-node R1 is a neighbor of the computing node R3, the node SID of R1 is not needed and the label stack of the repair tunnel is compressed to the adjacency SID over link R1-R2 as shown in Figure: Selecting link-protect TI-LFA backup path.

   When a P-Q set is found on multiple ECMP post-convergence paths, the following selection rules are applied, in ascending order, to select a set from a single path:

   1. the lowest number of labels

   2. the next hop to the neighbor router with the lowest router-id (OSPF) or system-id (ISIS)

   3. the next hop corresponding to the Q node with the lowest router-id (OSPF) or system-id (ISIS)

   If multiple links with adjacency SID exist between the selected P node and the selected Q node, the following rules are used to select one of them:

   1. the adjacency SID with the lowest metric

   2. the adjacency SID with the lowest SID value if same lowest metric