Routing Area Working GroupInternet Engineering Task Force (IETF) P. Sarkar, Ed.Internet-Draft Individual Contributor Intended status:Request for Comments: 8102 Arrcus, Inc. Category: Standards Track S. HegdeExpires: July 24, 2017ISSN: 2070-1721 C. Bowers Juniper Networks, Inc. H. Gredler RtBrick, Inc. S. Litkowski OrangeJanuary 20,March 2017 Remote-LFA Node Protection and Manageabilitydraft-ietf-rtgwg-rlfa-node-protection-13Abstract The loop-free alternates (LFAs) computed following the currentRemote-LFAremote-LFA specification guarantees onlylink-protection.link protection. The resultingRemote- LFA nexthopsremote-LFA next hops (also calledPQ-nodes),"PQ-nodes") may not guaranteenode-node protection for all destinations being protected by it. This document describes an extension to theRemote Loop-Free basedremote-loop-free-based IP fast reroutemechanisms,mechanisms thatspecifesspecifies procedures for determiningifwhether or not a given PQ-node providesnode-protectionnode protection for a specificdestination or not.destination. The document also shows how the same procedure can be utilized for the collection of complete characteristics for alternate paths. Knowledge about the characteristics of all alternatepathpaths isprecursorya precursor toapply operator definedapplying the operator-defined policy for eliminating paths not fitting the constraints. Status of This Memo ThisInternet-Draftissubmitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documentsan Internet Standards Track document. This document is a product of the Internet Engineering Task Force (IETF).Note that other groups may also distribute working documents as Internet-Drafts. The listIt represents the consensus ofcurrent Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents validthe IETF community. It has received public review and has been approved fora maximumpublication by the Internet Engineering Steering Group (IESG). Further information on Internet Standards is available in Section 2 ofsix monthsRFC 7841. Information about the current status of this document, any errata, and how to provide feedback on it may beupdated, replaced, or obsoleted by other documentsobtained atany time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on July 24, 2017.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) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to 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 are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 3 1.2. Requirements Language . . . . . . . . . . . . . . . . . . 4 2. Node Protection with Remote-LFA . . . . . . . . . . . . . . . 4 2.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 4 2.2. Additional Definitions . . . . . . . . . . . . . . . . . 6 2.2.1. Link-Protecting Extended P-Space . . . . . . . . . . 6 2.2.2. Node-Protecting Extended P-Space . . . . . . . . . . 6 2.2.3. Q-Space . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.4. Link-ProtectingPQ SpacePQ-Space . . . . . . . . . . . . . . 7 2.2.5. Candidate Node-ProtectingPQ SpacePQ-Space . . . . . . . . . 7 2.2.6. Cost-Based Definitions . . . . . . . . . . . . . . . 7 2.2.6.1. Link-Protecting Extended P-Space . . . . . . . .78 2.2.6.2. Node-Protecting Extended P-Space . . . . . . . . 8 2.2.6.3. Q-Space . . . . . . . . . . . . . . . . . . . . . 9 2.3. ComputingNode-protectingNode-Protecting R-LFA Path . . . . . . . . . . 9 2.3.1. Computing CandidateNode-protectingNode-Protecting PQ-Nodes for PrimarynexthopsNext Hops . . . . . . . . . . . . . . . . . . 9 2.3.2. Computingnode-protecting pathsNode-Protecting Paths fromPQ-nodesPQ-Nodes todestinationsDestinations . . . . . . . . . . . . . . . . . . . . 11 2.3.3. Computing Node-Protecting R-LFA Paths for Destinations withECMP primary nexthop nodes . .Multiple Primary Next-Hop Nodes . . 13 2.3.4. Limitingextra computational overheadExtra Computational Overhead . . . . . . . . 17 3. Manageability of Remote-LFA Alternate Paths . . . . . . . . . 18 3.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 18 3.2. The Solution . . . . . . . . . . . . . . . . . . . . . .1918 4.Acknowledgements .IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19 5.IANASecurity Considerations . . . . . . . . . . . . . . . . . . .. .19 6.Security ConsiderationsReferences . . . . . . . . . . . . . . . . . . . . . . . . . 197.6.1. Normative References . . . . . . . . . . . . . . . . . . 19 6.2. Informative References . . . . . . .20 7.1. Normative References .. . . . . . . . . . 20 Acknowledgements . . . . . . .20 7.2. Informative References. . . . . . . . . . . . . . . . . 20 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 20 1. Introduction The Remote-LFA[RFC7490]specification [RFC7490] provides loop-free alternates that guarantee onlylink-protection.link protection. The resultingRemote-LFAremote-LFA alternatenexthopsnext hops (also referred to as thePQ-nodes)"PQ-nodes") may not providenode-protectionnode protection for all destinations covered by the sameRemote-LFAremote-LFA alternate, in case of failure of the primarynexthop node. Neithernext-hop node, and it doesthe specificationnot provide a means to determine the same. Also, the LFA Manageability[RFC7916]document [RFC7916] requires a computing router to find all possible alternate next hops (including all possibleRemote-LFA) alternate nexthops,remote-LFA), collect the complete set of path characteristics for each alternate path, run an alternate-selection policy (configured by theoperator)operator), and find the best alternate path. This will require that theRemote-LFAremote-LFA implementationto gathergathers all the required path characteristics along each link on the entireRemote-LFAremote-LFA alternate path. With current LFA [RFC5286] andRemote-LFAremote-LFA implementations, the forward SPF (and reverse SPF) is run with the computing router and its immediate1-hopone-hop routers as the roots. While that enables computation of path attributes(e.g. SRLG,(e.g., Shared Risk Link Group (SRLG) and Admin-groups) for the first alternate path segment from the computing router to the PQ-node, there is no means for the computing router to gather any path attributes for the path segment from the PQ-node to the destination.ConsequentlyConsequently, any policy-based selection of alternate paths will consider only the path attributes from the computing router up until the PQ-node. This document describes a procedure for determiningnode-protectionnode protection withRemote-LFA.remote-LFA. The same procedure is also extended for the collection of a complete set of path attributes, enabling more accuratepolicy- basedpolicy-based selection for alternate paths obtained withRemote-LFA.remote-LFA. 1.1. Abbreviations This document uses the following list of 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 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 inRFC2119RFC 2119 [RFC2119].1.1. Abbreviations This document uses the following list of 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 node2. Node Protection with Remote-LFANode-protectionNode protection is required to provide protection of traffic on a given forwardingnode,node against the failure of the first-hop node on the primary forwarding path. Such protection becomes more critical in the absence of mechanisms likenon-stop-routingnon-stop routing in the network. Certain operators refrain from deploying non-stop-routing in their network, due to the required complex state synchronization between redundant control plane hardwares it requires, and the significant additional computation and performancecomplexitiesoverheads ithence introduces.comes along with. In suchcases node-protectioncases, node protection is essential to guaranteeun-interrupteduninterrupted flow of traffic, even in the case of an entire forwarding node going down. The following sections discuss the node-protection problem in the context ofRemote-LFAremote-LFA and propose a solution. 2.1. The Problem To better illustrate the problem and the solution proposed in thisdocumentdocument, the following topology diagram from theRemote-LFAremote-LFA document [RFC7490]draftis being re-used with slight modification. D1 / S-x-E / \ N R3--D2 \ / R1---R2 Figure 1: Topology 1 In the above topology, for all (non-ECMP) destinations reachable via the S-Elinklink, there is no standard LFA alternate. As per theRemote-remote- LFA [RFC7490] alternatespecificationsspecifications, node R2 being the onlyPQ-nodePQ- node for the S-E link providesnexthopthe next hop for all of the above destinations. Table 1below,below shows all possible primary andRemote-LFAremote- LFA alternate paths for each destination. +-------------+--------------+---------+-------------------------+ | 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-LFAbackup pathsBackup Paths viaPQ-nodePQ-Node R2 A closer look at Table 1 shows that, while the PQ-node R2 provideslink-protectionlink protection for all the destinations, it does not providenode-node protection for destinations E and D1. In the event of the node- failure on primarynexthopnext hop E, the alternate path fromRemote-LFA nexthopthe remote-LFA next hop R2 to E and D1 also becomes unavailable.SoSo, for aRemote-LFA nexthopremote- LFA next hop to providenode-protectionnode protection for a given destination,it is mandatory that,the shortest path from the given PQ-node to the given destination MUST NOT traverse the primarynexthop.next hop. In another extension of the topology in Figure11, let us consider an additional 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 2 In the above topology, the S-E link is nomorelonger on any of the shortest paths from N to R3,EE, and D1.HenceHence, R3,EE, and D1 are also included in both theExtended-P spaceextended P-space andQ spacethe Q-space of E(w.r.t(with respect to the S-E link). Table 2below,below shows all possible primary and R-LFA alternate paths via PQ-nodeR3,R3 for each destination reachable through the S-E link in the above topology. The R-LFA alternate paths via PQ-node R2remainsremain 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-LFAbackup pathsBackup Paths viaPQ-nodePQ-Node R3AgainAgain, a closer look at Table 2 shows that, unlike Table1,1 where the single PQ-node R2 providednode-protectionnode protection for destinations R3 and D2, if we choose R3 as the R-LFAnexthop,next hop, itdoes not provide node-no longer provides node protection for R3 andD2 anymore.D2. If S chooses R3 as the R-LFAnexthop, in the event of thenext hop and if there is a node-failure on primarynexthopnext hop E,on the alternate path from S to R-LFA nexthop R3,then one of the parallel ECMPpathpaths between N and R3 also becomesunavailable. Sounavailable on the alternate path from S to R-LFA next hop R3. So, for aRemote-LFA nexthopremote-LFA next hop to providenode-protectionnode protection for a given destination,it is also mandatory that,the shortest paths from S to the chosen PQ-node MUST NOT traverse the primarynexthopnext-hop node. 2.2. Additional Definitions This document adds and enhances the followingdefinitionsdefinitions, extending the ones mentioned in the Remote-LFA[RFC7490] specification.specification [RFC7490]. 2.2.1. Link-Protecting Extended P-Space The Remote-LFA[RFC7490]specification [RFC7490] already defines this. 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 thelink(S-E)link (S-E) being protected. For a cost-based definition forLink-protecting Extended P-Spacelink-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 primarynexthopnext-hop node E beingprotected,protected is the set of routers that are reachable from one or more direct neighbors of S, except primary node E, without traversingthenode 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 forNode-protecting Extended P-Spacenode-protecting extended P-space, refer to Section 2.2.6.2. 2.2.3. Q-Space The Remote-LFA document [RFC7490]draftalready defines this. 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 primarynexthopnext hop E. This MUST exclude any node for which there is at least one ECMP path from the node to the primarynexthopnext hop E traversing thelink(S-E)link (S-E) being protected. For a cost-based definition forQ-SpaceQ-Space, refer to Section 2.2.6.3. 2.2.4. Link-ProtectingPQ SpacePQ-Space A node Y is in a link-protectingPQ space w.r.tPQ-space with respect to the link (S-E) beingprotected,protected if and onlyif,if Y is present in bothlink-protectinglink- protecting extended P-space and the Q-space for the link being protected. 2.2.5. Candidate Node-ProtectingPQ SpacePQ-Space A node Y is in a candidate node-protectingPQ space w.r.tPQ-space with respect to the node (E) beingprotected,protected if and onlyif,if Y is present in both the node-protecting extended P-space and the Q-space for the link being protected. Pleasenote,note that a node Y being in a candidate node-protecting PQ-space,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 primarynexthopnext-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-protectingPQ spacePQ-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 definitionfor Link-of link- protectingExtended P-Space.extended P-space. A node Y is in a link-protecting extended P-spacew.r.twith respect to the link (S-E) beingprotected,protected if and onlyif,if there exists at least one direct neighbor ofS, Ni,S (Ni) other than primarynexthop E,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 primarynexthopnext hop E. Y : The node being evaluated for link-protecting extended P-Space. Figure 3: Link-Protecting Ext-P-Space Condition 2.2.6.2. Node-Protecting Extended P-Space Please refer to Section 2.2.2 for a formal definitionfor Node-of node- protectingExtended P-Space.extended P-space. A node Y is in a node-protecting extended P-spacew.r.twith respect to the node E beingprotected,protected if and onlyif,if there exists at least one direct neighbor ofS, Ni,S (Ni) other than primarynexthopnext 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 primarynexthopnext hop on the shortest path from S to destination. Ni : A direct neighbor of S other than primarynexthopnext hop E. Y : The node being evaluated for node-protecting extended P-Space. Figure 4: Node-Protecting Ext-P-Space Condition Pleasenote,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 definitionforof Q-Space. A node Y is in Q-spacew.r.twith respect to the link (S-E) beingprotected,protected if and onlyif,if the following condition issatisfied.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 primarynexthopnext hop on the shortest path from S to destination. Y : The node being evaluated for Q-Space. Figure 5: Q-Space Condition 2.3. ComputingNode-protectingNode-Protecting R-LFA Path The R-LFA alternate path through a given PQ-node to a given destination is comprised of two path segments asfollows.follows: 1. Path segment from the computing router to the PQ-node (Remote-LFA alternatenexthop),next hop), and 2. Path segment from the PQ-node to the destination being protected.SoSo, to ensureathat an R-LFA alternate path for a given destination providesnode-protectionnode protection, we need to ensure that none of the above path segments are affected in the event of failure of the primarynexthopnext-hop node. SectionsSection2.3.1 andSection2.3.2 show how this can be ensured. 2.3.1. Computing CandidateNode-protectingNode-Protecting PQ-Nodes for PrimarynexthopsNext Hops To choose a node-protecting R-LFAnexthopnext hop for a destination R3, router S needs to consider a PQ-node from the candidate node- protecting PQ-space for the primarynexthopnext hop E on the shortest path from S to R3. As mentioned in Section 2.2.2, to consider a PQ-node as a candidate node-protecting PQ-node, there must be at least one direct neighbor Ni of S, such that all shortest paths from Ni to the PQ-nodedoesdo not traverse primarynexthopnext-hop node E. Implementations SHOULD run the inequality in Section2.2.22.2.6.2, Figure 4 for all direct neighbors, other than primarynexthopnext-hop node E, to determine whether a node Y is a candidate node-protectingPQ-node.PQ- node. All of the metrics needed by this inequality would have been already collected from the forward SPFs rooted at each of direct neighbor S, computed as part of standard LFA [RFC5286] implementation. With reference to the topology in Figure 2, Table 3belowshows how the above condition can be used to determine the candidatenode- protectingnode-protecting PQ-space for S-E link (primarynexthopnext 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 evaluationNode-Protection Evaluation for R-LFArepair tunnelRepair Tunnel to PQ-nodeNode As seen in the above Table 3, R3 does not meet the node-protectingextended-p-space inequality andextended p-space inequality; so, while R2 is in candidate node- protectingPQ space,PQ-space, R3 is not. Some SPF implementations may also produce a list of links and nodes traversed on the shortest path(s) from a given root to others. In such implementations, router S may have executed a forward SPF with each of its direct neighbors as the SPF root, executed as part of the standard LFA[RFC5286] computations. Socomputations [RFC5286]. So, S may re-use the list of links and nodes collected from the same SPFcomputations,computations to decide whether or not a node Y is a candidate node-protectingPQ-node or not.PQ-node. A node Y shall be considered as a node-protectingPQ-node,PQ-node if and onlyif,if there is at least one direct neighbor of S, other than the primarynexthop E,next hop E forwhich,which the primarynexthopnext-hop node E does not exist on the list of nodes traversed on any of the shortest paths from the direct neighbor to the PQ-node. Table 4 below is an illustration of the mechanism with the topology in Figure 2.+-----------+-------------------+-----------------+-----------------++-------------+---------------------------+------------+------------+ | Candidate | Repair Tunnel Path |Link-ProtectionLink |Node-ProtectionNode | | PQ-node |Path(Repairing | | | | |(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-LFAtunnelTunnel to thePQ-nodePQ-Node As seen in the above Table44, while R2 is a candidate node-protectingRemote-LFA nexthopremote-LFA next hop for R3 and D2, it is not so for E and D1, since the primarynexthopnext hop E isinon the shortest path from R2 to E and D1. 2.3.2. Computingnode-protecting pathsNode-Protecting Paths fromPQ-nodesPQ-Nodes todestinationsDestinations Once a computing router finds all the candidate node-protecting PQ- nodes for a given directly attached primary link, it shall follow the procedure as proposed in thissection,section to choose one or more node- protecting R-LFApaths,paths for destinations reachable through the same primary link in the primary SPF graph. 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 corresponding primarynexthop,next hop, such that all the path(s) from the PQ-node(s) to the given destination remain unaffected in the event of a node failure of the primarynexthopnext-hop node. To determine whether a given PQ-node belongs to such a subset of PQ-nodes, the computing router MUST ensure that none of the primarynexthop nodenext-hop nodes are found on any of the shortest paths from the PQ-node to the given destination. This document proposes an additional forward SPF computation for each of thePQ-nodes,PQ-nodes to discover all shortest paths from the PQ-nodes to the destination. This will helpdetermine, ifdetermine whether or not a given primarynexthopnext-hop node is on the shortest paths from the PQ-node to the givendestination or not.destination. To determineifwhether or not a given candidatenode- protectingnode-protecting PQ-node provides node-protecting alternate for a given destination,or not,all the shortest paths from the PQ-node to the given destinationhashave to beinspected,inspected to check if the primarynexthopnext- hop node is found on any of these shortest paths. To compute all the shortest paths from a candidate node-protecting PQ-node to one(or more) destination,or more destinations, the computing router MUST run the forward SPF on the candidate node-protecting PQ-node. Soon after running the forward SPF, the computer router SHOULD run the inequality in Figure 6 below, once for each destination. A PQ-node that does not qualify the condition for a givendestination,destination does not guaranteenode-protectionnode protection for the path segment from the PQ-node to the 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 primarynexthopnext hop on the shortest path from S to destination. Y : The node-protecting PQ-node being evaluated Figure 6: Node-Protecting Condition forPQ-nodePQ-Node to Destination All of the above metriccostscosts, except D_opt(Y, D), can be obtained with forward and reverse SPFs withE(theE (the primarynexthop)next hop) as the root, run as part of the regular LFA andRemote-LFAremote-LFA implementation. The Distance_opt(Y, D) metric can only be determined by the additional forward SPF run with PQ-node Y as the root. With reference to the topology in Figure 2, Table 5belowshowshowthat the above condition can be used to determinenode-protectionnode protection with 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 evaluationNode-Protection Evaluation for R-LFApath segmentPath Segment betweenPQ-nodePQ-Node anddestinationDestination As seen in theaboveexample above, R2 does not meet thenode- protectingnode-protecting inequality for destinationE,E and D1. And so, once again, while R2 is a node-protectingRemote-LFA nexthopremote-LFA next hop for R3 and D2, it is not so for E and D1. In SPF implementations that also produce a list of links and nodes traversed on the shortest path(s) from a given root to others, the inequality in Figure 6 above need not be evaluated. Instead, to determine whether or not a PQ-node providesnode-protectionnode protection for a givendestination or not,destination, the list of nodes computed from forward SPF that run on thePQ-node,PQ-node for the givendestination,destination SHOULD be inspected. In case the list contains the primarynexthopnext-hop node, the PQ-node does not providenode-protection.node protection. Else, the PQ-node guarantees the node- protecting alternate for the given destination. Below is an illustration of the mechanism with candidate node-protecting PQ-node R2 in the topology in Figure 2.+-------------+-----------------+-----------------+-----------------++-------------+---------------------------+------------+------------+ | Destination | Shortest Path| Link-Protection | Node-Protection | | |(Repairing | Link | Node | | | router toPQ- | | | | | node)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-LFApathPath between PQ-node anddestinationDestination As seen in the aboveexampleexample, while R2 is a candidate node-protecting R-LFAnexthopnext hop for R3 and D2, it is not so for E and D1, since the primarynexthopnext hop E isinon the shortest path from R2 to E and D1. The procedure described in this document helps no more than to determine whether or not a givenRemote-LFAremote-LFA alternate providesnode-node protection for a givendestination or not.destination. It does not find out any newRemote-LFAremote-LFA alternatenexthops,next hops, outside the ones already computed by the standardRemote-LFAremote-LFA procedure. However, in the case of availability of more than one PQ-node(Remote-LFA(remote-LFA alternates) for adestination, and node-protectiondestination where node protection is required for the given primarynexthop,next hop, this procedure will eliminate the PQ-nodes that do not providenode-node protection and choose only the ones thatdoes.do. 2.3.3. Computing Node-Protecting R-LFA Paths for Destinations withECMP primary nexthop nodesMultiple Primary Next-Hop Nodes In certain scenarios, when one or more destinationsmaybemay be reachable via multiple ECMP (equal-cost-multi-path)nexthop nodes,next-hop nodes and onlylink-protectionlink protection is required, there is no need to compute any alternate paths for such destinations. In the event of failure of one of thenexthopnext-hop links, the remaining primarynexthopsnext hops shall always providelink-protection.link protection. However, ifnode-protectionnode protection is required, the rest of the primarynexthopsnext hops may not guaranteenode-protection.node protection. Figure 7 below shows one such example topology. D1 2 / S---x---E1 / \ / \ / x / \ / \ / \ N-------E2 R3--D2 \ 2 / \ / \ / R1-------R2 2 PrimaryNexthops:Next hops: Destination D1 = [{ S-E1, E1}, {S-E2, E2}] Destination D2 = [{ S-E1, E1}, {S-E2, E2}] Figure 7: Topology withmultipleMultiple ECMPprimary nexthopsPrimary Next Hops In the above example topology, costs of all links are 1, except the following links: Link: S-E1, Cost: 2 Link: N-E2: Cost: 2 Link: R1-R2: Cost: 2 In the above topology, on computing router S, destinations D1 and D2 are reachable via two ECMPnexthopnext-hop nodes E1 and E2.HoweverHowever, the primary paths vianexthopnext-hop node E2 alsotraversestraverse via thenexthopnext-hop node E1.SoSo, in the event of node failure ofnexthopnext-hop node E1, both primary paths (via E1 and E2)becomesbecome unavailable.HenceHence, ifnode-protectionnode protection is desired for destinations D1 and D2, alternate paths thatdoesdo not traverse any of the primarynexthopnext-hop nodes E1 andE2,E2 need to be computed. In the abovetopologytopology, the only alternate neighbor N does not provide suchaan LFA alternate path.HenceHence, one(or more)or more R-LFA node-protecting alternate paths for destinations D1 and D2, needs to be computed. In the above topology,following arethe link-protectingPQ-nodes.PQ-nodes are as follows: PrimaryNexthop:Next Hop: E1, Link-Protecting PQ-Node: { R2 } PrimaryNexthop:Next Hop: E2, Link-Protecting PQ-Node: { R2 } To find one (or more) node-protecting R-LFA paths for destinations D1 and D2, one (or more) node-protecting PQ-node(s)needsneed to be determined first. Inequalities specified inSectionSections 2.2.6.2 andSection2.2.6.3 can be evaluated to compute the node-protectingPQ- spacePQ-space for each of thenexthopnext-hop nodes E1 and E2, as shown in Table 7 below. To select a PQ-node as a node-protecting PQ-node for a destination with multiple primarynexthopnext-hop nodes, the PQ-node MUST satisfy the inequality for all primarynexthopnext-hop nodes. Any PQ-nodewhichthat is NOT a node-protecting PQ-node for all the primarynexthop nodes,next-hop nodes MUST NOT be chosen as the node-protecting PQ-node for the destination. +--------+----------+-------+--------+--------+---------+-----------+ | Primar | Candidat | Direc | D_opt | D_opt | D_opt | Condition | | y Next | e PQ- | t Nbr | (Ni,Y) | (Ni,E) | (E,Y) | Met | |hopHop | 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: ComputingNode-protected PQ-nodesNode-Protected PQ-Nodes fornexthopNext Hop E1 and E2 In SPF implementations that also produce a list of links and nodes traversed on the shortest path(s) from a given root to others, the tunnel-repair paths from the computing router to candidate PQ-node can be examined to ensure that none of the primarynexthopnext-hop nodesisare traversed. PQ-nodes that provide one(or more)or more Tunnel-repairpaths(s)pathss thatdoesdo not traverse any of the primarynexthop nodes,next-hop nodes are to be considered as node-protecting PQ-nodes. Table 8 below shows the possible tunnel-repair paths to PQ-node 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-RepairpathsPaths toPQ-nodePQ-Node R2 FromTableTables 7 andTable 8,8 in theabove example,example above, R2being node- protecting PQ-nodeis a node-protecting PQ- node for both primarynexthopsnext hops E1 andE2,E2 and should be chosen as the node-protecting PQ-node for destinations D1 and D2 that are both reachable via the primarynexthopnext-hop nodes E1 and E2. Next, to find a node-protecting R-LFA path from a node-protecting PQ- node to destinations D1 and D2, inequalities specified in Figure 6 should beevaluated,evaluated to ensureifthat R2 provides a node-protecting R-LFA path for each of these destinations, as shown below in Table 9. Foraan R-LFA path to qualify as a node-protecting R-LFA path for a destination with multiple ECMP primarynexthopnext-hop nodes, the R-LFA path from the PQ-node to the destination MUST satisfy the inequality for all primarynexthopnext-hop nodes. +----------+----------+-------+--------+--------+--------+----------+ | Destinat | Primary- | PQ- | D_opt | D_opt | D_opt | Conditio | | ion (D) | NH (E) | Node | (Y, D) | (Y, E) | (E, D) | n 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: Findingnode-protectingNode-Protecting R-LFApathPath fordestinationsDestinations D1 and D2 In SPF implementations that also produce a list of links and nodes traversed on the shortest path(s) from a given root to others, the R-LFA paths via a node-protecting PQ-node to the final destination can be examined to ensure that none of the primarynexthopnext-hop nodesisare traversed. One or more R-LFApath(s)paths thatdoesdo not traverse any of the primarynexthop nodes,next-hop nodes guaranteesnode-protectionnode protection in the event of failure of any of the primarynexthopnext-hop nodes. Table 10 below shows the possible R-LFA-paths for destinations D1 and D2 via thenode-protecting PQ- nodenode- 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-LFApathsPaths fordestinationsDestinations D1 and D2 FromTableTables 9 andTable 10,10 in the example above, the R-LFA path from R2 does not meet the node-protecting inequality for destination D1, while it does meet the same inequality for destination D2.And so,So, while R2 provides a node-protecting R-LFA alternate for D2, it fails to providenode-protectionnode protection for destination D1. Finally, while it is possible to get a node-protecting R-LFA path for D2, no such node- protecting R-LFA path can be found for D1. 2.3.4. Limitingextra computational overheadExtra Computational Overhead In addition to the extra reverse SPF computations suggested by the Remote-LFA document [RFC7490]draft(one reverse SPF for each of the directly connected neighbors), this document proposes a forward SPFcomputationscomputation for each PQ-node discovered in the network. Since the average number of PQ-nodes found in any network is considerably more than the number of direct neighbors of the computing router, the proposal of running one forward SPF per PQ-node may add considerably to the overall SPF computation time. To limit the computational overhead of the approach proposed, 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 the number of PQ-nodes in the subset. Implementations MUST choose a default value for this limit and may provide the user with a configuration knob to override the default limit. This document suggests 16 as a default value for this limit. Implementations MUST also evaluate some default preference criteria while considering a PQ-node in this subset. The exact default preference criteria to be used is outside the scope of thisdocument,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 selectionwhichthat will put a score on each PQ-node, proportional to the number of primary interfaces for which it provides coverage, 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 primary interfaces. When two or more PQ-nodes cover the same number of primary interfaces, PQ-nodeswhichthat are closer (based on metric) to the computing router SHOULD be preferred over PQ-nodes farther away from it. For PQ-nodes that cover the same number of primary interfaces and are the same distance from the computing router, the PQ-node with smaller router-id (or system-id in case of IS-IS) SHOULD be preferred. 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 procedures proposed in Section 2.3.2. 3. Manageability of Remote-LFA Alternate Paths 3.1. The Problem With the regularRemote-LFAremote-LFA [RFC7490]functionalityfunctionality, the computing router may compute more than one PQ-node as usableRemote-LFAremote-LFA alternatenexthops. Additionallynext hops. Additionally, [RFC7916] specifiesaan LFA (andRemote-LFA)a remote-LFA) manageability framework, in which an alternate selection policy may be configured to let the network operator choose one of them as the most appropriateRemote-LFA alternate.remote-LFA alternates. For suchpolicy- baseda policy-based alternate selection to run, the computing router needs to collect all the relevant path characteristics (as specified insectionSection 6.2.4 of [RFC7916]) for each of the alternate paths (one through each of the PQ-nodes). As mentioned before in Section2.32.3, the R-LFA alternate path through a given PQ-node to a given destination is comprised of two path segments. Section6.2.5.46.2.4 of [RFC7916] specifies that any kind of alternate selection policy must consider path characteristics for both path segments while evaluating one or more RLFA alternatepath(s).paths. The first path segment(i.e.(i.e., from the computing router to the PQ- node) can be calculated from the regular forward SPF done as part of standard and remote LFA computations.HoweverHowever, 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(i.e.(i.e., from the PQ-node to the destination). In the absence of the path characteristics for the second path segment, twoRemote-LFAremote-LFA alternate paths may be equally preferred based on the first pathsegmentssegment characteristics only, although the second path segment attributes may be different. 3.2. The Solution The additional forward SPF computation proposed in Section 2.3.2documentshall also collect links,nodesnodes, and path characteristics along the second path segment. This shall enable the collection of complete path characteristics for a givenRemote-LFAremote-LFA alternate path to a given destination. The complete alternate path characteristics shall then facilitate more accurate alternate path selection while running the alternate selection policy. As already specified in Section2.3.42.3.4, to limit the computational overhead of the proposed approach, forward SPF computations must be run on a selected subset from the entire set of PQ-nodes computed in the network, with a finite limit on the number of PQ-nodes in the subset. The detailed suggestion on how to select this subset is specified in the same section. While this limits the number of possible alternate paths provided to the alternate-selection policy, this is needed to keep the computational complexity within affordable limits.HoweverHowever, if the alternate-selection policy is veryrestrictiverestrictive, this may leave few destinations in the entire topology without protection. Yet this limitation provides a necessary tradeoff between extensive coverage and immense computational overhead. The mechanism proposed in this section does not modify or invalidate[RFC7916] oranypartspart ofit.[RFC7916]. This document specifies a mechanism to meet the requirements specified insection 6.5.2.4 inSection 6.2.5.4 of [RFC7916].5.4. IANA ConsiderationsN/A. - No protocol changes are proposed in this document. 6.This document does not require any IANA actions. 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.7.6. References7.1.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>.7.2.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>.4.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)Individual ContributorArrcus, 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 94089USUnited States of America Email: cbowers@juniper.net Hannes Gredler RtBrick, Inc. Email: hannes@rtbrick.com Stephane Litkowski Orange Email: stephane.litkowski@orange.com