RFC 8102
Remote-LFA Node Protection and Manageability
RFC 8102: Remote-LFA Node Protection and Manageability 🎀
okay bestie, this is RFC 8102 from the IETF (Internet Engineering Task Force) 🦋 It's a Standards Track document, so it's an actual Internet standard and not just a vibe. It was published in March 2017 and has ISSN 2070-1721. The editor is P. Sarkar (Arrcus, Inc.), with co-authors S. Hegde (Arrcus, Inc.), C. Bowers (Juniper Networks, Inc.), H. Gredler (RtBrick, Inc.), and S. Litkowski (Orange) 🧚. The title block doesn't list anything it obsoletes or updates, so it's standing on its own 💅
Abstract ✨
okay so the LFAs (loop-free alternates) you get from the current remote-LFA spec only guarantee link protection 🔗 and the resulting remote-LFA next hops (aka "PQ-nodes") might not guarantee node protection for every destination they're covering 😬
this doc adds an extension to the remote-loop-free-based IP fast reroute mechanisms. It gives procedures for figuring out whether a given PQ-node provides node protection for a specific destination 🫶 It also shows how that same procedure can be used to collect the complete characteristics of alternate paths. And knowing the characteristics of all alternate paths is a precursor to applying operator-defined policy that kicks out paths not fitting the constraints. main character energy for sure 👑
Status of This Memo 📜
This is an Internet Standards Track document 💜
This document is a product of the Internet Engineering Task Force (IETF). It represents the consensus of the IETF community. It went through public review and got approved for publication by the Internet Engineering Steering Group (IESG). More info on Internet Standards is in Section 2 of RFC 7841.
For the current status, any errata, and how to send feedback, check http://www.rfc-editor.org/info/rfc8102 🔍
Copyright Notice ©️
Copyright (c) 2017 IETF Trust and the persons identified as the document authors. All rights reserved. 🌈
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) as in effect on the date this document was published. Please read these carefully, because they describe your rights and restrictions for this document 🙈 Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions, and they come without warranty as described in the Simplified BSD License 💅
Table of Contents 🗺️
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 4
1.2. Requirements Language . . . . . . . . . . . . . . . . . . 5
2. Node Protection with Remote-LFA . . . . . . . . . . . . . . . 5
2.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 5
2.2. Additional Definitions . . . . . . . . . . . . . . . . . 7
2.2.1. Link-Protecting Extended P-Space . . . . . . . . . . 7
2.2.2. Node-Protecting Extended P-Space . . . . . . . . . . 7
2.2.3. Q-Space . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.4. Link-Protecting PQ-Space . . . . . . . . . . . . . . 8
2.2.5. Candidate Node-Protecting PQ-Space . . . . . . . . . 8
2.2.6. Cost-Based Definitions . . . . . . . . . . . . . . . 8
2.2.6.1. Link-Protecting Extended P-Space . . . . . . . . 9
2.2.6.2. Node-Protecting Extended P-Space . . . . . . . . 9
2.2.6.3. Q-Space . . . . . . . . . . . . . . . . . . . . . 10
2.3. Computing Node-Protecting R-LFA Path . . . . . . . . . . 10
2.3.1. Computing Candidate Node-Protecting PQ-Nodes for
Primary Next Hops . . . . . . . . . . . . . . . . . . 10
2.3.2. Computing Node-Protecting Paths from PQ-Nodes to
Destinations . . . . . . . . . . . . . . . . . . . . 12
2.3.3. Computing Node-Protecting R-LFA Paths for
Destinations with Multiple Primary Next-Hop Nodes . . 14
2.3.4. Limiting Extra Computational Overhead . . . . . . . . 18
3. Manageability of Remote-LFA Alternate Paths . . . . . . . . . 19
3.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 19
3.2. The Solution . . . . . . . . . . . . . . . . . . . . . . 20
4. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20
5. Security Considerations . . . . . . . . . . . . . . . . . . . 20
6. References . . . . . . . . . . . . . . . . . . . . . . . . . 21
6.1. Normative References . . . . . . . . . . . . . . . . . . 21
6.2. Informative References . . . . . . . . . . . . . . . . . 21
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . 21
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 221. Introduction ✨
okay so the Remote-LFA spec [RFC7490] gives you loop-free alternates that only guarantee link protection 🔗 The resulting remote-LFA alternate next hops (also called the "PQ-nodes") might not give node protection for every destination covered by the same remote-LFA alternate when the primary next-hop node fails 😭 and there's no way to figure that out either. 🙈
then there's the LFA Manageability doc [RFC7916], which says a computing router has to find all possible alternate next hops (including every possible remote-LFA), collect the full set of path characteristics for each alternate path, run an alternate-selection policy that the operator configured, and then pick the best alternate path 💅 For that, the remote-LFA implementation has to gather all the required path characteristics along each link on the entire remote-LFA alternate path. that's a lot, honestly 🍓
here's the thing: with current LFA [RFC5286] and remote-LFA implementations, the forward SPF (and reverse SPF) runs with the computing router and its immediate one-hop routers as the roots 🌸 That lets you compute path attributes (e.g., Shared Risk Link Group (SRLG) and Admin-groups) for the first alternate path segment, from the computing router to the PQ-node. but there's no way for the computing router to gather any path attributes for the path segment from the PQ-node to the destination. so any policy-based selection of alternate paths only considers path attributes from the computing router up until the PQ-node. not iconic 💀
so this doc describes a procedure for determining node protection with remote-LFA. the same procedure is also extended to collect a complete set of path attributes, which means more accurate policy-based selection for alternate paths found with remote-LFA 🦋
1.1. Abbreviations 🔤
this document uses the following abbreviations:
- LFA: Loop-Free Alternates
- RLFA or R-LFA: Remote Loop-Free Alternates
- ECMP: Equal-Cost Multiple Path
- SPF: Shortest Path First graph computations
- NH: Next-Hop node
1.2. Requirements Language 📣
okay this part is the important one 🫶 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119]. so those capitalized words carry the RFC 2119 meaning, periodt ✨
2. Node Protection with Remote-LFA 🛡️
so node protection is needed to protect traffic on a given forwarding node against the failure of the first-hop node on the primary forwarding path 🧚 It gets even more critical when the network doesn't have something like non-stop routing. some operators skip non-stop-routing because it needs complicated state synchronization between redundant control plane hardwares, plus it brings a lot of extra computation and performance overhead 😩 in those cases, node protection is essential to keep traffic flowing smoothly, even if an entire forwarding node goes down 💖
the following sections talk about the node-protection problem in the context of remote-LFA and propose a solution 🌈
2.1. The Problem 💅
Okay bestie, let's get into the actual problem 🫶 To make it clear, we're reusing the topology diagram from the remote-LFA doc [RFC7490], with a tiny tweak.
D1
/
S-x-E
/ \
N R3--D2
\ /
R1---R2
Figure 1: Topology 1In this topology, every non-ECMP destination reachable over the S-E link has no standard LFA alternate 😭 Per the remote-LFA [RFC7490] rules, R2 is the only PQ-node for the S-E link, so it's the next hop for all of those destinations. Table 1 lays out every primary and remote-LFA backup path.
+-------------+--------------+---------+-------------------------+
| Destination | Primary Path | PQ-node | Remote-LFA Backup Path |
+-------------+--------------+---------+-------------------------+
| R3 | S->E->R3 | R2 | S=>N=>R1=>R2->R3 |
| E | S->E | R2 | S=>N=>R1=>R2->R3->E |
| D1 | S->E->D1 | R2 | S=>N=>R1=>R2->R3->E->D1 |
| D2 | S->E->R3->D2 | R2 | S=>N=>R1=>R2->R3->D2 |
+-------------+--------------+---------+-------------------------+
Table 1: Remote-LFA Backup Paths via PQ-Node R2Now here's the tea 🫖 R2 gives link protection for all of them, but it does not give node protection for E and D1. If primary next hop E goes down, the path from R2 to E and D1 goes down with it 💀 So for a remote-LFA next hop to give node protection for a given destination, the shortest path from the given PQ-node to the given destination MUST NOT traverse the primary next hop.
Okay, let's level it up! Add a link between N and E with the same cost as the other links 🦋
D1
/
S-x-E
/ / \
N---+ R3--D2
\ /
R1---R2
Figure 2: Topology 2In this one, the S-E link isn't on any shortest path from N to R3, E, or D1 anymore 🙈 So R3, E, and D1 end up in both the extended P-space and the Q-space of E (with respect to the S-E link). Table 2 shows every primary and R-LFA path via PQ-node R3 for each destination reachable over the S-E link. The R-LFA paths via PQ-node R2 stay the same as in Table 1.
+-------------+--------------+---------+------------------------+
| Destination | Primary Path | PQ-node | Remote-LFA Backup Path |
+-------------+--------------+---------+------------------------+
| R3 | S->E->R3 | R3 | S=>N=>E=>R3 |
| E | S->E | R3 | S=>N=>E=>R3->E |
| D1 | S->E->D1 | R3 | S=>N=>E=>R3->E->D1 |
| D2 | S->E->R3->D2 | R3 | S=>N=>E=>R3->D2 |
+-------------+--------------+---------+------------------------+
Table 2: Remote-LFA Backup Paths via PQ-Node R3Looking at Table 2 again: unlike Table 1, where the single PQ-node R2 gave node protection for R3 and D2, choosing R3 as the R-LFA next hop means it no longer gives node protection for R3 and D2 💔 If S picks R3 and there's a node failure on primary next hop E, one of the parallel ECMP paths between N and R3 is also gone on the alternate path from S to R-LFA next hop R3. So for a remote-LFA next hop to give node protection for a given destination, the shortest paths from S to the chosen PQ-node MUST NOT traverse the primary next-hop node.
2.2. Additional Definitions 🎀
This doc adds to and levels up the following definitions, extending the ones in the Remote-LFA spec [RFC7490].
2.2.1. Link-Protecting Extended P-Space
The Remote-LFA spec [RFC7490] already defines this one 💖 The link-protecting extended P-space for a link S-E being protected is the set of routers that are reachable from one or more direct neighbors of S, except primary node E, without traversing the S-E link on any of the shortest paths from the direct neighbor to the router. This MUST exclude any direct neighbor for which there is at least one ECMP path from the direct neighbor traversing the link (S-E) being protected.
For a cost-based definition for link-protecting extended P-space, refer to Section 2.2.6.1.
2.2.2. Node-Protecting Extended P-Space
The node-protecting extended P-space for a primary next-hop node E being protected is the set of routers that are reachable from one or more direct neighbors of S, except primary node E, without traversing node E. This MUST exclude any direct neighbors for which there is at least one ECMP path from the direct neighbor traversing the node E being protected.
For a cost-based definition for node-protecting extended P-space, refer to Section 2.2.6.2.
2.2.3. Q-Space
The Remote-LFA doc [RFC7490] already defines this one too ✨ The Q-space for a link S-E being protected is the set of nodes that can reach primary node E, without traversing the S-E link on any of the shortest paths from the node itself to primary next hop E. This MUST exclude any node for which there is at least one ECMP path from the node to the primary next hop E traversing the link (S-E) being protected.
For a cost-based definition for Q-Space, refer to Section 2.2.6.3.
2.2.4. Link-Protecting PQ-Space
A node Y is in a link-protecting PQ-space with respect to the link (S-E) being protected if and only if Y is present in both link-protecting extended P-space and the Q-space for the link being protected.
2.2.5. Candidate Node-Protecting PQ-Space
A node Y is in a candidate node-protecting PQ-space with respect to the node (E) being protected if and only if Y is present in both the node-protecting extended P-space and the Q-space for the link being protected.
Please note that a node Y being in a candidate node-protecting PQ-space does not guarantee that the R-LFA alternate path via the same, in entirety, is unaffected in the event of a node failure of primary next-hop node E. It only guarantees that the path segment from S to PQ-node Y is unaffected by the same failure event. The PQ-nodes in the candidate node-protecting PQ-space may provide node protection for only a subset of destinations that are reachable through the corresponding primary link.
2.2.6. Cost-Based Definitions
This section provides cost-based definitions for some of the terms introduced in Section 2.2 of this document.
2.2.6.1. Link-Protecting Extended P-Space
Please refer to Section 2.2.1 for a formal definition of link-protecting extended P-space.
A node Y is in a link-protecting extended P-space with respect to the link (S-E) being protected if and only if there exists at least one direct neighbor of S (Ni) other than primary next hop E that satisfies the following condition.
D_opt(Ni,Y) < D_opt(Ni,S) + D_opt(S,Y)
Where,
D_opt(A,B) : Distance on the most optimum path from A to B.
Ni : A direct neighbor of S other than primary
next hop E.
Y : The node being evaluated for link-protecting
extended P-Space.
Figure 3: Link-Protecting Ext-P-Space Condition2.2.6.2. Node-Protecting Extended P-Space
Please refer to Section 2.2.2 for a formal definition of node-protecting extended P-space.
A node Y is in a node-protecting extended P-space with respect to the node E being protected if and only if there exists at least one direct neighbor of S (Ni) other than primary next hop E, that satisfies the following condition.
D_opt(Ni,Y) < D_opt(Ni,E) + D_opt(E,Y)
Where,
D_opt(A,B) : Distance on the most optimum path from A to B.
E : The primary next hop on the shortest path from S
to destination.
Ni : A direct neighbor of S other than primary
next hop E.
Y : The node being evaluated for node-protecting
extended P-Space.
Figure 4: Node-Protecting Ext-P-Space ConditionPlease note that a node Y satisfying the condition in Figure 4 above only guarantees that the R-LFA alternate path segment from S via direct neighbor Ni to the node Y is not affected in the event of a node failure of E. It does not yet guarantee that the path segment from node Y to the destination is also unaffected by the same failure event.
2.2.6.3. Q-Space
Please refer to Section 2.2.3 for a formal definition of Q-Space.
A node Y is in Q-space with respect to the link (S-E) being protected if and only if the following condition is satisfied:
D_opt(Y,E) < D_opt(S,E) + D_opt(Y,S)
Where,
D_opt(A,B) : Distance on the most optimum path from A to B.
E : The primary next hop on the shortest path from S
to destination.
Y : The node being evaluated for Q-Space.
Figure 5: Q-Space Condition2.3. Computing Node-Protecting R-LFA Path 🧚
The R-LFA alternate path through a given PQ-node to a given destination is made of two path segments:
- Path segment from the computing router to the PQ-node (Remote-LFA alternate next hop), and
- Path segment from the PQ-node to the destination being protected.
So, to make sure an R-LFA alternate path for a given destination provides node protection, we need to make sure that neither of those path segments gets affected when the primary next-hop node fails. Sections 2.3.1 and 2.3.2 show how this can be ensured. 👑
2.3.1. Computing Candidate Node-Protecting PQ-Nodes for Primary Next Hops ✨
Okay so, bestie 💖 when S wants a node-protecting R-LFA next hop for R3, it has to look at a PQ-node from the candidate node-protecting PQ-space for the primary next hop E, which is the next hop on S's shortest path to R3. Remember from Section 2.2.2: a PQ-node only counts as a candidate node-protecting PQ-node if at least one direct neighbor Ni of S has no shortest path to that PQ-node going through the primary next-hop node E. It's giving "find the friend who doesn't need to walk past the drama" 🙈
Implementations SHOULD run the inequality in Section 2.2.6.2, Figure 4 for every direct neighbor other than the primary next-hop node E, to figure out whether a node Y is a candidate node-protecting PQ-node. All the metrics this inequality needs were already collected from the forward SPFs rooted at each direct neighbor of S, which get computed anyway for standard LFA [RFC5286] 🧚 So no extra work there, iconic. Using the topology in Figure 2, Table 3 shows how this check decides the candidate node-protecting PQ-space for the S-E link (primary next hop E) 👑
+------------+----------+----------+----------+---------+-----------+
| Candidate | Direct | D_opt | D_opt | D_opt | Condition |
| PQ-node | Nbr (Ni) | (Ni,Y) | (Ni,E) | (E,Y) | Met |
| (Y) | | | | | |
+------------+----------+----------+----------+---------+-----------+
| R2 | N | 2 (N,R2) | 1 (N,E) | 2 | Yes |
| | | | | (E,R2) | |
| R3 | N | 2 (N,R3) | 1 (N,E) | 1 | No |
| | | | | (E,R3) | |
+------------+----------+----------+----------+---------+-----------+
Table 3: Node-Protection Evaluation for R-LFA Repair Tunnel to PQ-
NodeAs you can see in Table 3, R3 doesn't pass the node-protecting extended p-space inequality 💀 So even though R2 makes it into the candidate node-protecting PQ-space, R3 gets left out. Not me being dramatic, it's just the math 😭
Some SPF implementations can also spit out a list of the links and nodes traversed on the shortest path(s) from a given root to everyone else. In those implementations, S may have run a forward SPF with each of its direct neighbors as the root, as part of the standard LFA computations [RFC5286]. So S can reuse that list of links and nodes to decide whether a node Y is a candidate node-protecting PQ-node 🌸 A node Y shall be considered as a node-protecting PQ-node if and only if there is at least one direct neighbor of S, other than the primary next hop E, for which the primary next-hop node E does not show up on the list of nodes traversed on any of the shortest paths from that direct neighbor to the PQ-node. Table 4 shows this mechanism working on the topology in Figure 2 🦋
+-------------+---------------------------+------------+------------+
| Candidate | Repair Tunnel Path | Link | Node |
| PQ-node | (Repairing router to PQ- | Protection | Protection |
| | node) | | |
+-------------+---------------------------+------------+------------+
| R2 | S->N->R1->R2 | Yes | Yes |
| R2 | S->E->R3->R2 | No | No |
| R3 | S->N->E->R3 | Yes | No |
+-------------+---------------------------+------------+------------+
Table 4: Protection of Remote-LFA Tunnel to the PQ-NodeAs Table 4 shows, R2 is a candidate node-protecting remote-LFA next hop for R3 and D2, but not for E and D1. The reason is that the primary next hop E sits on the shortest path from R2 to E and to D1, so R2 can't protect them 🥺
2.3.2. Computing Node-Protecting Paths from PQ-Nodes to Destinations 💅
Once a computing router has found all the candidate node-protecting PQ-nodes for a given directly attached primary link, it should follow the procedure in this section to pick one or more node-protecting R-LFA paths for destinations reachable through that same primary link in the primary SPF graph. It's a whole process, but it's so worth it ✨
To find a node-protecting R-LFA path for a given destination, the computing router needs to pick a subset of PQ-nodes from the candidate node-protecting PQ-space for the matching primary next hop. The point is that every path from those PQ-nodes to the destination stays unaffected if the primary next-hop node fails 🛡️ To check whether a given PQ-node is in that subset, the computing router MUST make sure that none of the primary next-hop nodes show up on any of the shortest paths from the PQ-node to the destination. No cheating allowed 🙅♀️
This document adds an extra forward SPF computation for each PQ-node, to find all the shortest paths from that PQ-node to the destination. That's how we know whether a primary next-hop node is sitting on any of those paths. To decide if a candidate node-protecting PQ-node really provides node protection for a destination, every shortest path from the PQ-node to that destination has to be checked for the primary next-hop node. To run this, the computing router MUST run the forward SPF on the candidate node-protecting PQ-node. Right after that forward SPF, the computing router SHOULD run the inequality in Figure 6 below, once for each destination. A PQ-node that fails the condition for a given destination does not guarantee node protection for the path segment from that PQ-node to that specific destination 🚫
D_opt(Y,D) < D_opt(Y,E) + Distance_opt(E,D)
Where,
D_opt(A,B) : Distance on the most optimum path from A to B.
D : The destination node.
E : The primary next hop on the shortest path from S
to destination.
Y : The node-protecting PQ-node being evaluated
Figure 6: Node-Protecting Condition for PQ-Node to DestinationAll of the metric costs above, except D_opt(Y, D), can be grabbed from forward and reverse SPFs with E (the primary next hop) as the root, which run as part of the regular LFA and remote-LFA implementation 🌈 The Distance_opt(Y, D) metric can only be found by that extra forward SPF run with PQ-node Y as the root. Using the topology in Figure 2, Table 5 shows that this condition can decide node protection for a node-protecting PQ-node R2 💖
+-------------+------------+---------+--------+---------+-----------+
| Destination | Primary-NH | D_opt | D_opt | D_opt | Condition |
| (D) | (E) | (Y, D) | (Y, E) | (E, D) | Met |
+-------------+------------+---------+--------+---------+-----------+
| R3 | E | 1 | 2 | 1 | Yes |
| | | (R2,R3) | (R2,E) | (E,R3) | |
| E | E | 2 | 2 | 0 (E,E) | No |
| | | (R2,E) | (R2,E) | | |
| D1 | E | 3 | 2 | 1 | No |
| | | (R2,D1) | (R2,E) | (E,D1) | |
| D2 | E | 2 | 2 | 1 | Yes |
| | | (R2,D2) | (R2,E) | (E,D2) | |
+-------------+------------+---------+--------+---------+-----------+
Table 5: Node-Protection Evaluation for R-LFA Path Segment between
PQ-Node and DestinationAs the example above shows, R2 fails the node-protecting inequality for destinations E and D1. So once again, R2 is a node-protecting remote-LFA next hop for R3 and D2, but not for E and D1 🥹
For SPF implementations that also produce a list of the links and nodes traversed on the shortest path(s) from a given root to others, the inequality in Figure 6 above doesn't need to be evaluated. Instead, to find out whether a PQ-node gives node protection for a given destination, the list of nodes computed from the forward SPF run on that PQ-node for the given destination SHOULD be inspected. If the list contains the primary next-hop node, the PQ-node does not provide node protection. Otherwise, the PQ-node guarantees the node-protecting alternate for that destination 🫧 Here's the mechanism in action with candidate node-protecting PQ-node R2 in the topology from Figure 2:
+-------------+---------------------------+------------+------------+
| Destination | Shortest Path (Repairing | Link | Node |
| | router to PQ-node) | Protection | Protection |
+-------------+---------------------------+------------+------------+
| R3 | R2->R3 | Yes | Yes |
| E | R2->R3->E | Yes | No |
| D1 | R2->R3->E->D1 | Yes | No |
| D2 | R2->R3->D2 | Yes | Yes |
+-------------+---------------------------+------------+------------+
Table 6: Protection of Remote-LFA Path between PQ-node and
DestinationAs the example above shows, R2 is a candidate node-protecting R-LFA next hop for R3 and D2, but not for E and D1. That's because the primary next hop E is on the shortest path from R2 to E and D1 🌷
The procedure in this document only tells you whether a given remote-LFA alternate provides node protection for a given destination. It doesn't discover any new remote-LFA alternate next hops beyond the ones the standard remote-LFA procedure already computed. But if a destination has more than one PQ-node (remote-LFA alternate) and node protection is needed for the given primary next hop, this procedure throws out the PQ-nodes that don't provide node protection and keeps only the ones that do 🎀
2.3.3. Computing Node-Protecting R-LFA Paths for Destinations with Multiple Primary Next-Hop Nodes ✨
okay bestie, so sometimes a destination can be reachable through multiple ECMP (equal-cost-multi-path) next-hop nodes, and if you only need link protection, you don't have to compute any alternate paths for it 🫶 if one of the next-hop links dies, the other primary next hops shall always cover link protection. but if you need node protection, the rest of the primary next hops may not guarantee it 😭 here's an example topology (Figure 7) that shows exactly that drama 🦋
D1
2 /
S---x---E1
/ \ / \
/ x / \
/ \ / \
N-------E2 R3--D2
\ 2 /
\ /
\ /
R1-------R2
2Figure 7: Topology with Multiple ECMP Primary Next Hops
Primary Next hops:
Destination D1 = [{ S-E1, E1}, {S-E2, E2}]
Destination D2 = [{ S-E1, E1}, {S-E2, E2}]In this topology, every link costs 1 except these three, which are the main characters here 💅
Link: S-E1, Cost: 2
Link: N-E2: Cost: 2
Link: R1-R2: Cost: 2So on computing router S, destinations D1 and D2 are both reachable through two ECMP next-hop nodes, E1 and E2 🌸 but the primary path via E2 also goes through E1 💀 which means if E1 goes down, both primary paths are gone. if you want node protection for D1 and D2, you need alternate paths that avoid both E1 and E2 entirely 🙈 the only alternate neighbor here is N, and N doesn't give you a valid LFA alternate path. so you need one or more R-LFA node-protecting alternate paths for D1 and D2. main character energy 👑
The link-protecting PQ-nodes look like this:
Primary Next Hop: E1, Link-Protecting PQ-Node: { R2 }
Primary Next Hop: E2, Link-Protecting PQ-Node: { R2 }To find one (or more) node-protecting R-LFA paths for D1 and D2, you first need to figure out one (or more) node-protecting PQ-node(s) 🧚 you can evaluate the inequalities from Sections 2.2.6.2 and 2.2.6.3 to work out the node-protecting PQ-space for each of E1 and E2, which is what Table 7 shows 🍓 and here's the rule: to pick a PQ-node as a node-protecting PQ-node for a destination with multiple primary next-hop nodes, that PQ-node MUST satisfy the inequality for all of those primary next-hop nodes. any PQ-node that is not a node-protecting PQ-node for all the primary next-hop nodes MUST NOT be chosen as the node-protecting PQ-node for that destination. no exceptions, bestie 🚫
+--------+----------+-------+--------+--------+---------+-----------+
| Primary| Candidate| Direct| D_opt | D_opt | D_opt | Condition |
| Next | PQ- | Nbr | (Ni,Y) | (Ni,E) | (E,Y) | Met |
| Hop | node (Y) | (Ni) | | | | |
| (E) | | | | | | |
+--------+----------+-------+--------+--------+---------+-----------+
| E1 | R2 | N | 3 | 3 | 2 | Yes |
| | | | (N,R2) | (N,E1) | (E1,R2) | |
| E2 | R2 | N | 3 | 2 | 3 | Yes |
| | | | (N,R2) | (N,E2) | (E2,R2) | |
+--------+----------+-------+--------+--------+---------+-----------+Table 7: Computing Node-Protected PQ-Nodes for Next Hop E1 and E2
In SPF implementations that also spit out a list of the links and nodes traversed on the shortest path(s) from a root to everything else, you can check the tunnel-repair paths from the computing router to a candidate PQ-node and make sure none of the primary next-hop nodes show up 👀 any PQ-node with at least one tunnel-repair path that avoids all the primary next-hop nodes is a node-protecting PQ-node, period 💜 Table 8 shows the possible tunnel-repair paths to R2:
+--------------+------------+-------------------+-------------------+
| Primary-NH | PQ-Node | Tunnel-Repair | Exclude All |
| (E) | (Y) | Paths | Primary-NH |
+--------------+------------+-------------------+-------------------+
| E1, E2 | R2 | S==>N==>R1==>R2 | Yes |
+--------------+------------+-------------------+-------------------+Table 8: Tunnel-Repair Paths to PQ-Node R2
So from Tables 7 and 8, R2 is a node-protecting PQ-node for both E1 and E2 🎀 and it should be chosen as the node-protecting PQ-node for D1 and D2, since both of them are reachable through E1 and E2.
Next up, you need a node-protecting R-LFA path from that PQ-node to D1 and D2. You evaluate the inequalities from Figure 6 to check that R2 gives a node-protecting R-LFA path for each destination, as Table 9 shows 🦋 for an R-LFA path to count as node-protecting for a destination with multiple ECMP primary next-hop nodes, the R-LFA path from the PQ-node to that destination MUST satisfy the inequality for all primary next-hop nodes. no shortcuts 💅
+----------+----------+-------+--------+--------+--------+----------+
| Destinat | Primary- | PQ- | D_opt | D_opt | D_opt | Condition|
| ion (D) | NH (E) | Node | (Y, D) | (Y, E) | (E, D) | Met |
| | | (Y) | | | | |
+----------+----------+-------+--------+--------+--------+----------+
| D1 | E1 | R2 | 3 (R2, | 2 (R2, | 1 (E1, | No |
| | | | D1) | E1) | D1) | |
| D1 | E2 | R2 | 3 (R2, | 3 (R2, | 2 (E2, | Yes |
| | | | D1) | E2) | D1) | |
| D2 | E1 | R2 | 2 (R2, | 2 (R2, | 2 (E1, | Yes |
| | | | D2) | E1) | D2) | |
| D2 | E2 | R2 | 2 (R2, | 2 (R2, | 3 (E2, | Yes |
| | | | D2) | E2) | D2) | |
+----------+----------+-------+--------+--------+--------+----------+Table 9: Finding Node-Protecting R-LFA Path for Destinations D1 and D2
Again, if your SPF implementation also gives you the list of links and nodes on the shortest paths, you can check the R-LFA paths from a node-protecting PQ-node to the final destination and make sure none of the primary next-hop nodes are traversed 🫶 one or more R-LFA paths that dodge every primary next-hop node guarantees node protection if any of those primary next-hop nodes fails. Table 10 lists the possible R-LFA paths for D1 and D2 via the node-protecting PQ-node R2:
+-------------+------------+---------+-----------------+------------+
| Destination | Primary-NH | PQ-Node | R-LFA Paths | Exclude |
| (D) | (E) | (Y) | | All |
| | | | | Primary-NH |
+-------------+------------+---------+-----------------+------------+
| D1 | E1, E2 | R2 | S==>N==>R1==>R2 | No |
| | | | -->R3-->E1-->D1 | |
| | | | | |
| D2 | E1, E2 | R2 | S==>N==>R1==>R2 | Yes |
| | | | -->R3-->D2 | |
+-------------+------------+---------+-----------------+------------+Table 10: R-LFA Paths for Destinations D1 and D2
So from Tables 9 and 10, the R-LFA path from R2 doesn't meet the node-protecting inequality for D1, but it does meet it for D2 😭 so R2 gives you a node-protecting R-LFA alternate for D2, but for D1 it just can't provide node protection. bestie, it's possible to get a node-protecting R-LFA path for D2, but no such path can be found for D1. that's the tea ☕
2.3.4. Limiting Extra Computational Overhead 🧮
On top of the extra reverse SPF computations suggested by the Remote-LFA document [RFC7490] (one reverse SPF for each directly connected neighbor), this document proposes a forward SPF computation for each PQ-node discovered in the network 💀 the average number of PQ-nodes in any network is way more than the number of direct neighbors of the computing router, so running one forward SPF per PQ-node can add a lot to the overall SPF computation time. it's giving slow 🐢
To keep that overhead in check, this document specifies that implementations MUST choose a subset from the entire set of PQ-nodes computed in the network, with a finite limit on how many PQ-nodes are in that subset 🫶 implementations MUST choose a default value for this limit, and they may give the user a configuration knob to override the default limit. this document suggests 16 as a default value for the limit 🌈 implementations MUST also evaluate some default preference criteria while considering a PQ-node in this subset. what exactly those default preference criteria are is outside the scope of this document and is a matter of implementation 🤷♀️ finally, implementations MAY also allow the user to override the default preference criteria by providing a policy configuration for the same. ✨
This document proposes that implementations SHOULD use a default preference criteria for PQ-node selection that puts a score on each PQ-node. The score is proportional to the number of primary interfaces the PQ-node provides coverage for, its distance from the computing router, and its router-id (or system-id in case of IS-IS) 💖 PQ-nodes that cover more primary interfaces SHOULD be preferred over PQ-nodes that cover fewer. when two or more PQ-nodes cover the same number of primary interfaces, the ones that are closer (based on metric) to the computing router SHOULD be preferred over the ones farther away 🏃♀️ and for PQ-nodes that cover the same number of primary interfaces and are the same distance from the computing router, the PQ-node with the smaller router-id (or system-id in case of IS-IS) SHOULD be preferred. tiebreaker moment 🎀
Once a subset of PQ-nodes is found, a computing router shall run a forward SPF on each of the PQ-nodes in the subset to continue with the procedures proposed in Section 2.3.2 🦋
3. Manageability of Remote-LFA Alternate Paths 🌸
3.1. The Problem 💅
okay so with the regular remote-LFA [RFC7490] functionality, the computing router can end up finding more than one PQ-node it could use as a remote-LFA alternate next hop 🦋. Then [RFC7916] shows up with an LFA (and remote-LFA) manageability framework 👑, where the network operator can configure an alternate selection policy to pick whichever one is the most appropriate. For that policy to actually run, the computing router needs to collect all the relevant path characteristics (as specified in Section 6.2.4 of [RFC7916]) for each alternate path, one through each PQ-node. As I mentioned back in Section 2.3, the R-LFA alternate path through a given PQ-node to a given destination is made of two path segments 🧚. Section 6.2.4 of [RFC7916] says that any kind of alternate selection policy must consider path characteristics for both path segments while evaluating one or more RLFA alternate paths. Iconic behaviour, honestly.
The first path segment (from the computing router to the PQ-node) can be calculated from the regular forward SPF that gets done as part of standard and remote LFA computations ✨. The problem is that, without the mechanism proposed in Section 2.3.2 of this document, there is no way to determine the path characteristics for the second path segment (from the PQ-node to the destination) 😭. So without that second segment info, two remote-LFA alternate paths might look equally preferred based only on the first segment, even though their second segment attributes are totally different. Not me getting a worse path because the info was missing 💀.
3.2. The Solution 🌸
The additional forward SPF computation proposed in Section 2.3.2 shall also collect links, nodes, and path characteristics along the second path segment 🫶. This shall enable the collection of complete path characteristics for a given remote-LFA alternate path to a given destination. Those complete alternate path characteristics shall then make the alternate path selection way more accurate when the alternate selection policy runs 🔥.
As already specified in Section 2.3.4, the proposed approach has to keep its computational overhead under control, so forward SPF computations must be run on a selected subset of the entire set of PQ-nodes computed in the network, with a finite limit on how many PQ-nodes are in that subset 🎀. The detailed suggestion on how to pick this subset is in the same section. Yes, this limits the number of possible alternate paths handed to the alternate-selection policy, but it's needed to keep the computational complexity within affordable limits 💜. Just be aware that if the alternate-selection policy is super restrictive, this may leave few destinations in the entire topology unprotected 🙈. It's a necessary tradeoff between extensive coverage and immense computational overhead, and that's the vibe we're choosing 🦋.
The mechanism proposed in this section does not modify or invalidate any part of [RFC7916]. This document specifies a mechanism to meet the requirements specified in Section 6.2.5.4 of [RFC7916]. Not touching the original RFC at all, bestie 🧚.
4. IANA Considerations 🌈
This document does not require any IANA actions. Zero registry drama, zero paperwork, just vibes ✨.
5. Security Considerations 💀
This document does not introduce any change in any of the protocol specifications. It simply proposes to run an extra SPF rooted on each PQ-node discovered in the whole network. Nothing on the wire changes, but the extra SPF runs are the thing to keep in mind, so take this one seriously, fr fr 🔥.
6. References ⭐
6.1. Normative References 🫶
- [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <http://www.rfc-editor.org/info/rfc2119>.
- [RFC5286] Atlas, A., Ed. and A. Zinin, Ed., "Basic Specification for IP Fast Reroute: Loop-Free Alternates", RFC 5286, DOI 10.17487/RFC5286, September 2008, <http://www.rfc-editor.org/info/rfc5286>.
- [RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N. So, "Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)", RFC 7490, DOI 10.17487/RFC7490, April 2015, <http://www.rfc-editor.org/info/rfc7490>.
6.2. Informative References 🦋
- [RFC7916] Litkowski, S., Ed., Decraene, B., Filsfils, C., Raza, K., Horneffer, M., and P. Sarkar, "Operational Management of Loop-Free Alternates", RFC 7916, DOI 10.17487/RFC7916, July 2016, <http://www.rfc-editor.org/info/rfc7916>.
Acknowledgements 💖
Many thanks to Bruno Decraene for providing his useful comments 🌷. We would also like to thank Uma Chunduri for reviewing this document and providing valuable feedback 🫶. Also, many thanks to Harish Raghuveer for his review and comments on the initial draft versions of this document 👑.
Authors' Addresses 🎀
Pushpasis Sarkar (editor)
Arrcus, Inc.
Email: pushpasis.ietf@gmail.com
Shraddha Hegde
Juniper Networks, Inc.
Electra, Exora Business Park
Bangalore, KA 560103
India
Email: shraddha@juniper.net
Chris Bowers
Juniper Networks, Inc.
1194 N. Mathilda Ave.
Sunnyvale, CA 94089
United States of America
Email: cbowers@juniper.net
Hannes Gredler
RtBrick, Inc.
Email: hannes@rtbrick.com
Stephane Litkowski
Orange
Email: stephane.litkowski@orange.comThat's the whole thing, bestie 🧚💖
📦 where this page comes from
- ietf: rfc8102 2017-03
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms