RemoteLFA Node Protection and Manageability
draftietfrtgwgrlfanodeprotection13
The information below is for an old version of the document that is already published as an RFC.
Document  Type 
This is an older version of an InternetDraft that was ultimately published as RFC 8102.



Authors  Pushpasis Sarkar , Shraddha Hegde , Chris Bowers , Hannes Gredler , Stephane Litkowski  
Last updated  20181220 (Latest revision 20170120)  
Replaces  draftpsarkarrtgwgrlfanodeprotection  
RFC stream  Internet Engineering Task Force (IETF)  
Formats  
Reviews 
RTGDIR Early review
(of
02)
by Mike Shand
Has issues


Additional resources  Mailing list discussion  
Stream  WG state  Submitted to IESG for Publication  
Document shepherd  Jon Mitchell  
Shepherd writeup  Show Last changed 20161117  
IESG  IESG state  RFC 8102 (Proposed Standard)  
Consensus boilerplate  Yes  
Telechat date  (None)  
Responsible AD  Alia Atlas  
Send notices to  "Jon Mitchell" <jrmitche@puck.nether.net>  
IANA  IANA review state  Version Changed  Review Needed  
IANA action state  No IANA Actions 
draftietfrtgwgrlfanodeprotection13
Routing Area Working Group P. Sarkar, Ed. InternetDraft Individual Contributor Intended status: Standards Track S. Hegde Expires: July 24, 2017 C. Bowers Juniper Networks, Inc. H. Gredler RtBrick, Inc. S. Litkowski Orange January 20, 2017 RemoteLFA Node Protection and Manageability draftietfrtgwgrlfanodeprotection13 Abstract The loopfree alternates computed following the current RemoteLFA specification guarantees only linkprotection. The resulting Remote LFA nexthops (also called PQnodes), may not guarantee node protection for all destinations being protected by it. This document describes an extension to the Remote LoopFree based IP fast reroute mechanisms, that specifes procedures for determining if a given PQnode provides nodeprotection for a specific destination or not. The document also shows how the same procedure can be utilized for collection of complete characteristics for alternate paths. Knowledge about the characteristics of all alternate path is precursory to apply operator defined policy for eliminating paths not fitting constraints. 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 in RFC2119 [RFC2119]. Status of This Memo This InternetDraft is submitted in full conformance with the provisions of BCP 78 and BCP 79. InternetDrafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as InternetDrafts. The list of current Internet Drafts is at http://datatracker.ietf.org/drafts/current/. Sarkar, et al. Expires July 24, 2017 [Page 1] InternetDraft RLFA NodeProtection and Manageability January 2017 InternetDrafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use InternetDrafts as reference material or to cite them other than as "work in progress." This InternetDraft will expire on July 24, 2017. 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/licenseinfo) 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 2. Node Protection with RemoteLFA . . . . . . . . . . . . . . . 4 2.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 4 2.2. Additional Definitions . . . . . . . . . . . . . . . . . 6 2.2.1. LinkProtecting Extended PSpace . . . . . . . . . . 6 2.2.2. NodeProtecting Extended PSpace . . . . . . . . . . 6 2.2.3. QSpace . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.4. LinkProtecting PQ Space . . . . . . . . . . . . . . 7 2.2.5. Candidate NodeProtecting PQ Space . . . . . . . . . 7 2.2.6. CostBased Definitions . . . . . . . . . . . . . . . 7 2.2.6.1. LinkProtecting Extended PSpace . . . . . . . . 7 2.2.6.2. NodeProtecting Extended PSpace . . . . . . . . 8 2.2.6.3. QSpace . . . . . . . . . . . . . . . . . . . . . 9 2.3. Computing Nodeprotecting RLFA Path . . . . . . . . . . 9 2.3.1. Computing Candidate Nodeprotecting PQNodes for Primary nexthops . . . . . . . . . . . . . . . . . . 9 2.3.2. Computing nodeprotecting paths from PQnodes to destinations . . . . . . . . . . . . . . . . . . . . 11 2.3.3. Computing NodeProtecting RLFA Paths for Destinations with ECMP primary nexthop nodes . . . . 13 2.3.4. Limiting extra computational overhead . . . . . . . . 17 3. Manageability of RemoteLFA Alternate Paths . . . . . . . . . 18 3.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 18 Sarkar, et al. Expires July 24, 2017 [Page 2] InternetDraft RLFA NodeProtection and Manageability January 2017 3.2. The Solution . . . . . . . . . . . . . . . . . . . . . . 19 4. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 19 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19 6. Security Considerations . . . . . . . . . . . . . . . . . . . 19 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 20 7.1. Normative References . . . . . . . . . . . . . . . . . . 20 7.2. Informative References . . . . . . . . . . . . . . . . . 20 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 20 1. Introduction The RemoteLFA [RFC7490] specification provides loopfree alternates that guarantee only linkprotection. The resulting RemoteLFA alternate nexthops (also referred to as the PQnodes) may not provide nodeprotection for all destinations covered by the same RemoteLFA alternate, in case of failure of the primary nexthop node. Neither does the specification provide a means to determine the same. Also, the LFA Manageability [RFC7916] document requires a computing router to find all possible (including all possible RemoteLFA) alternate nexthops, collect the complete set of path characteristics for each alternate path, run an alternateselection policy (configured by the operator) and find the best alternate path. This will require the RemoteLFA implementation to gather all the required path characteristics along each link on the entire RemoteLFA alternate path. With current LFA [RFC5286] and RemoteLFA implementations, the forward SPF (and reverse SPF) is run with the computing router and its immediate 1hop routers as the roots. While that enables computation of path attributes (e.g. SRLG, Admingroups) for first alternate path segment from the computing router to the PQnode, there is no means for the computing router to gather any path attributes for the path segment from the PQnode to destination. Consequently any policybased selection of alternate paths will consider only the path attributes from the computing router up until the PQnode. This document describes a procedure for determining nodeprotection with RemoteLFA. The same procedure is also extended for collection of a complete set of path attributes, enabling more accurate policy based selection for alternate paths obtained with RemoteLFA. 1.1. Abbreviations This document uses the following list of abbreviations. LFA  Loop Free Alternates Sarkar, et al. Expires July 24, 2017 [Page 3] InternetDraft RLFA NodeProtection and Manageability January 2017 RLFA or RLFA  Remote Loop Free Alternates ECMP  Equal Cost Multiple Path SPF  Shortest Path First graph computations NH  Next Hop node 2. Node Protection with RemoteLFA Nodeprotection is required to provide protection of traffic on a given forwarding node, against the failure of the firsthop node on the primary forwarding path. Such protection becomes more critical in the absence of mechanisms like nonstoprouting in the network. Certain operators refrain from deploying nonstoprouting in their network, due to the required complex state synchronization between redundant control plane hardwares it requires, and the significant additional performance complexities it hence introduces. In such cases nodeprotection is essential to guarantee uninterrupted flow of traffic, even in the case of an entire forwarding node going down. The following sections discuss the nodeprotection problem in the context of RemoteLFA and propose a solution. 2.1. The Problem To better illustrate the problem and the solution proposed in this document the following topology diagram from the RemoteLFA [RFC7490] draft is being reused with slight modification. D1 / SxE / \ N R3D2 \ / R1R2 Figure 1: Topology 1 In the above topology, for all (nonECMP) destinations reachable via the SE link there is no standard LFA alternate. As per the Remote LFA [RFC7490] alternate specifications node R2 being the only PQnode for the SE link provides nexthop for all the above destinations. Table 1 below, shows all possible primary and RemoteLFA alternate paths for each destination. Sarkar, et al. Expires July 24, 2017 [Page 4] InternetDraft RLFA NodeProtection and Manageability January 2017 +++++  Destination  Primary Path  PQnode  RemoteLFA 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: RemoteLFA backup paths via PQnode R2 A closer look at Table 1 shows that, while the PQnode R2 provides linkprotection for all the destinations, it does not provide node protection for destinations E and D1. In the event of the node failure on primary nexthop E, the alternate path from RemoteLFA nexthop R2 to E and D1 also becomes unavailable. So for a RemoteLFA nexthop to provide nodeprotection for a given destination, it is mandatory that, the shortest path from the given PQnode to the given destination MUST NOT traverse the primary nexthop. In another extension of the topology in Figure 1 let us consider an additional link between N and E with the same cost as the other links. D1 / SxE / / \ N+ R3D2 \ / R1R2 Figure 2: Topology 2 In the above topology, the SE link is no more on any of the shortest paths from N to R3, E and D1. Hence R3, E and D1 are also included in both the ExtendedP space and Q space of E (w.r.t SE link). Table 2 below, shows all possible primary and RLFA alternate paths via PQnode R3, for each destination reachable through the SE link in the above topology. The RLFA alternate paths via PQnode R2 remains same as in Table 1. Sarkar, et al. Expires July 24, 2017 [Page 5] InternetDraft RLFA NodeProtection and Manageability January 2017 +++++  Destination  Primary Path  PQnode  RemoteLFA 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: RemoteLFA backup paths via PQnode R3 Again a closer look at Table 2 shows that, unlike Table 1, where the single PQnode R2 provided nodeprotection for destinations R3 and D2, if we choose R3 as the RLFA nexthop, it does not provide node protection for R3 and D2 anymore. If S chooses R3 as the RLFA nexthop, in the event of the nodefailure on primary nexthop E, on the alternate path from S to RLFA nexthop R3, one of parallel ECMP path between N and R3 also becomes unavailable. So for a RemoteLFA nexthop to provide nodeprotection for a given destination, it is also mandatory that, the shortest paths from S to the chosen PQnode MUST NOT traverse the primary nexthop node. 2.2. Additional Definitions This document adds and enhances the following definitions extending the ones mentioned in RemoteLFA [RFC7490] specification. 2.2.1. LinkProtecting Extended PSpace The RemoteLFA [RFC7490] specification already defines this. The linkprotecting extended Pspace for a link SE 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 SE 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(SE) being protected. For a costbased definition for Linkprotecting Extended PSpace refer to Section 2.2.6.1. 2.2.2. NodeProtecting Extended PSpace The nodeprotecting extended Pspace for a primary nexthop 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 the node E. This MUST exclude any direct neighbors for which there Sarkar, et al. Expires July 24, 2017 [Page 6] InternetDraft RLFA NodeProtection and Manageability January 2017 is at least one ECMP path from the direct neighbor traversing the node E being protected. For a costbased definition for Nodeprotecting Extended PSpace refer to Section 2.2.6.2. 2.2.3. QSpace The RemoteLFA [RFC7490] draft already defines this. The Qspace for a link SE being protected is the set of nodes that can reach primary node E, without traversing the SE link on any of the shortest paths from the node itself to primary nexthop E. This MUST exclude any node for which there is at least one ECMP path from the node to the primary nexthop E traversing the link(SE) being protected. For a costbased definition for QSpace refer to Section 2.2.6.3. 2.2.4. LinkProtecting PQ Space A node Y is in linkprotecting PQ space w.r.t the link (SE) being protected, if and only if, Y is present in both linkprotecting extended Pspace and the Qspace for the link being protected. 2.2.5. Candidate NodeProtecting PQ Space A node Y is in candidate nodeprotecting PQ space w.r.t the node (E) being protected, if and only if, Y is present in both nodeprotecting extended Pspace and the Qspace for the link being protected. Please note, that a node Y being in candidate nodeprotecting PQ space, does not guarantee that the RLFA alternate path via the same, in entirety, is unaffected in the event of a node failure of primary nexthop node E. It only guarantees that the path segment from S to PQnode Y is unaffected by the same failure event. The PQnodes in the candidate nodeprotecting PQ space may provide node protection for only a subset of destinations that are reachable through the corresponding primary link. 2.2.6. CostBased Definitions This section provides costbased definitions for some of the terms introduced in Section 2.2 of this document. 2.2.6.1. LinkProtecting Extended PSpace Please refer to Section 2.2.1 for a formal definition for Link protecting Extended PSpace. Sarkar, et al. Expires July 24, 2017 [Page 7] InternetDraft RLFA NodeProtection and Manageability January 2017 A node Y is in linkprotecting extended Pspace w.r.t the link (SE) being protected, if and only if, there exists at least one direct neighbor of S, Ni, other than primary nexthop 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 most optimum path from A to B. Ni : A direct neighbor of S other than primary nexthop E. Y : The node being evaluated for linkprotecting extended PSpace. Figure 3: LinkProtecting ExtPSpace Condition 2.2.6.2. NodeProtecting Extended PSpace Please refer to Section 2.2.2 for a formal definition for Node protecting Extended PSpace. A node Y is in nodeprotecting extended Pspace w.r.t the node E being protected, if and only if, there exists at least one direct neighbor of S, Ni, other than primary nexthop 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 most optimum path from A to B. E : The primary nexthop on shortest path from S to destination. Ni : A direct neighbor of S other than primary nexthop E. Y : The node being evaluated for nodeprotecting extended PSpace. Figure 4: NodeProtecting ExtPSpace Condition Please note, that a node Y satisfying the condition in Figure 4 above only guarantees that the RLFA 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. Sarkar, et al. Expires July 24, 2017 [Page 8] InternetDraft RLFA NodeProtection and Manageability January 2017 2.2.6.3. QSpace Please refer to Section 2.2.3 for a formal definition for QSpace. A node Y is in Qspace w.r.t the link (SE) 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 most optimum path from A to B. E : The primary nexthop on shortest path from S to destination. Y : The node being evaluated for QSpace. Figure 5: QSpace Condition 2.3. Computing Nodeprotecting RLFA Path The RLFA alternate path through a given PQnode to a given destination is comprised of two path segments as follows. 1. Path segment from the computing router to the PQnode (RemoteLFA alternate nexthop), and 2. Path segment from the PQnode to the destination being protected. So to ensure a RLFA alternate path for a given destination provides nodeprotection we need to ensure that none of the above path segments are affected in the event of failure of the primary nexthop node. Sections Section 2.3.1 and Section 2.3.2 show how this can be ensured. 2.3.1. Computing Candidate Nodeprotecting PQNodes for Primary nexthops To choose a nodeprotecting RLFA nexthop for a destination R3, router S needs to consider a PQnode from the candidate node protecting PQspace for the primary nexthop E on shortest path from S to R3. As mentioned in Section 2.2.2, to consider a PQnode as candidate nodeprotecting PQnode, there must be at least one direct neighbor Ni of S, such that all shortest paths from Ni to the PQnode does not traverse primary nexthop node E. Implementations SHOULD run the inequality in Section 2.2.2 Figure 4 for all direct neighbors, other than primary nexthop node E, to determine whether a node Y is a candidate nodeprotecting PQnode. Sarkar, et al. Expires July 24, 2017 [Page 9] InternetDraft RLFA NodeProtection and Manageability January 2017 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 3 below shows how the above condition can be used to determine the candidate node protecting PQspace for SE link (primary nexthop E). +++++++  Candidate  Direct  D_opt  D_opt  D_opt  Condition   PQnode  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: Nodeprotection evaluation for RLFA repair tunnel to PQ node As seen in the above Table 3, R3 does not meet the nodeprotecting extendedpspace inequality and so, while R2 is in candidate node protecting 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. So S may reuse the list of links and nodes collected from the same SPF computations, to decide whether a node Y is a candidate nodeprotecting PQnode or not. A node Y shall be considered as a nodeprotecting PQnode, if and only if, there is at least one direct neighbor of S, other than the primary nexthop E, for which, the primary nexthop node E does not exist on the list of nodes traversed on any of the shortest paths from the direct neighbor to the PQnode. Table 4 below is an illustration of the mechanism with the topology in Figure 2. Sarkar, et al. Expires July 24, 2017 [Page 10] InternetDraft RLFA NodeProtection and Manageability January 2017 +++++  Candidate  Repair Tunnel  LinkProtection  NodeProtection   PQnode  Path(Repairing      router to PQ      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 RemoteLFA tunnel to the PQnode As seen in the above Table 4 while R2 is candidate nodeprotecting RemoteLFA nexthop for R3 and D2, it is not so for E and D1, since the primary nexthop E is in the shortest path from R2 to E and D1. 2.3.2. Computing nodeprotecting paths from PQnodes to destinations Once a computing router finds all the candidate nodeprotecting PQ nodes for a given directly attached primary link, it shall follow the procedure as proposed in this section, to choose one or more node protecting RLFA paths, for destinations reachable through the same primary link in the primary SPF graph. To find a nodeprotecting RLFA path for a given destination, the computing router needs to pick a subset of PQnodes from the candidate nodeprotecting PQspace for the corresponding primary nexthop, such that all the path(s) from the PQnode(s) to the given destination remain unaffected in the event of a node failure of the primary nexthop node. To determine whether a given PQnode belongs to such a subset of PQnodes, the computing router MUST ensure that none of the primary nexthop node are found on any of the shortest paths from the PQnode to the given destination. This document proposes an additional forward SPF computation for each of the PQnodes, to discover all shortest paths from the PQnodes to the destination. This will help determine, if a given primary nexthop node is on the shortest paths from the PQnode to the given destination or not. To determine if a given candidate node protecting PQnode provides nodeprotecting alternate for a given destination, or not, all the shortest paths from the PQnode to the given destination has to be inspected, to check if the primary nexthop node is found on any of these shortest paths. To compute all the shortest paths from a candidate nodeprotecting PQnode to one (or more) destination, the computing router MUST run the forward SPF on the candidate nodeprotecting PQnode. Soon after running the forward SPF, the computer router SHOULD run the inequality in Sarkar, et al. Expires July 24, 2017 [Page 11] InternetDraft RLFA NodeProtection and Manageability January 2017 Figure 6 below, once for each destination. A PQnode that does not qualify the condition for a given destination, does not guarantee nodeprotection for the path segment from the PQnode to the specific destination. D_opt(Y,D) < D_opt(Y,E) + Distance_opt(E,D) Where, D_opt(A,B) : Distance on most optimum path from A to B. D : The destination node. E : The primary nexthop on shortest path from S to destination. Y : The nodeprotecting PQnode being evaluated Figure 6: NodeProtecting Condition for PQnode to Destination All of the above metric costs except D_opt(Y, D), can be obtained with forward and reverse SPFs with E(the primary nexthop) as the root, run as part of the regular LFA and RemoteLFA implementation. The Distance_opt(Y, D) metric can only be determined by the additional forward SPF run with PQnode Y as the root. With reference to the topology in Figure 2, Table 5 below shows how the above condition can be used to determine nodeprotection with node protecting PQnode R2. +++++++  Destination  PrimaryNH  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: Nodeprotection evaluation for RLFA path segment between PQnode and destination As seen in the above example above, R2 does not meet the node protecting inequality for destination E, and D1. And so, once again, while R2 is a nodeprotecting RemoteLFA nexthop for R3 and D2, it is not so for E and D1. Sarkar, et al. Expires July 24, 2017 [Page 12] InternetDraft RLFA NodeProtection and Manageability January 2017 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 a PQnode provides nodeprotection for a given destination or not, the list of nodes computed from forward SPF run on the PQnode, for the given destination, SHOULD be inspected. In case the list contains the primary nexthop node, the PQnode does not provide nodeprotection. Else, the PQnode guarantees node protecting alternate for the given destination. Below is an illustration of the mechanism with candidate nodeprotecting PQnode R2 in the topology in Figure 2. +++++  Destination  Shortest Path  LinkProtection  NodeProtection    (Repairing      router to PQ      node)    +++++  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 RemoteLFA path between PQnode and destination As seen in the above example while R2 is candidate nodeprotecting RLFA nexthop for R3 and D2, it is not so for E and D1, since the primary nexthop E is in the shortest path from R2 to E and D1. The procedure described in this document helps no more than to determine whether a given RemoteLFA alternate provides node protection for a given destination or not. It does not find out any new RemoteLFA alternate nexthops, outside the ones already computed by standard RemoteLFA procedure. However, in case of availability of more than one PQnode (RemoteLFA alternates) for a destination, and nodeprotection is required for the given primary nexthop, this procedure will eliminate the PQnodes that do not provide node protection and choose only the ones that does. 2.3.3. Computing NodeProtecting RLFA Paths for Destinations with ECMP primary nexthop nodes In certain scenarios, when one or more destinations maybe reachable via multiple ECMP (equalcostmultipath) nexthop nodes, and only linkprotection is required, there is no need to compute any alternate paths for such destinations. In the event of failure of Sarkar, et al. Expires July 24, 2017 [Page 13] InternetDraft RLFA NodeProtection and Manageability January 2017 one of the nexthop links, the remaining primary nexthops shall always provide linkprotection. However, if nodeprotection is required, the rest of the primary nexthops may not guarantee nodeprotection. Figure 7 below shows one such example topology. D1 2 / SxE1 / \ / \ / x / \ / \ / \ NE2 R3D2 \ 2 / \ / \ / R1R2 2 Primary Nexthops: Destination D1 = [{ SE1, E1}, {SE2, E2}] Destination D2 = [{ SE1, E1}, {SE2, E2}] Figure 7: Topology with multiple ECMP primary nexthops In the above example topology, costs of all links are 1, except the following links: Link: SE1, Cost: 2 Link: NE2: Cost: 2 Link: R1R2: Cost: 2 In the above topology, on computing router S, destinations D1 and D2 are reachable via two ECMP nexthop nodes E1 and E2. However the primary paths via nexthop node E2 also traverses via the nexthop node E1. So in the event of node failure of nexthop node E1, both primary paths (via E1 and E2) becomes unavailable. Hence if nodeprotection is desired for destinations D1 and D2, alternate paths that does not traverse any of the primary nexthop nodes E1 and E2, need to be computed. In the above topology the only alternate neighbor N does not provide such a LFA alternate path. Hence one (or more) RLFA nodeprotecting alternate paths for destinations D1 and D2, needs to be computed. In the above topology, following are the linkprotecting PQnodes. Sarkar, et al. Expires July 24, 2017 [Page 14] InternetDraft RLFA NodeProtection and Manageability January 2017 Primary Nexthop: E1, LinkProtecting PQNode: { R2 } Primary Nexthop: E2, LinkProtecting PQNode: { R2 } To find one (or more) nodeprotecting RLFA paths for destinations D1 and D2, one (or more) nodeprotecting PQnode(s) needs to be determined first. Inequalities specified in Section 2.2.6.2 and Section 2.2.6.3 can be evaluated to compute the nodeprotecting PQ space for each of the nexthop nodes E1 and E2, as shown in Table 7 below. To select a PQnode as nodeprotecting PQnode for a destination with multiple primary nexthop nodes, the PQnode MUST satisfy the inequality for all primary nexthop nodes. Any PQnode which is NOT nodeprotecting PQnode for all the primary nexthop nodes, MUST NOT be chosen as the nodeprotecting PQnode for destination. ++++++++  Primar  Candidat  Direc  D_opt  D_opt  D_opt  Condition   y Next  e PQ  t 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 Nodeprotected PQnodes for nexthop 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 tunnelrepair paths from the computing router to candidate PQnode can be examined to ensure that none of the primary nexthop nodes is traversed. PQnodes that provide one (or more) Tunnelrepair paths(s) that does not traverse any of the primary nexthop nodes, are to be considered as nodeprotecting PQnodes. Table 8 below shows the possible tunnelrepair paths to PQnode R2. +++++  PrimaryNH  PQNode  TunnelRepair  Exclude All   (E)  (Y)  Paths  PrimaryNH  +++++  E1, E2  R2  S==>N==>R1==>R2  Yes  +++++ Table 8: TunnelRepair paths to PQnode R2 Sarkar, et al. Expires July 24, 2017 [Page 15] InternetDraft RLFA NodeProtection and Manageability January 2017 From Table 7 and Table 8, in the above example, R2 being node protecting PQnode for both primary nexthops E1 and E2, should be chosen as the nodeprotecting PQnode for destinations D1 and D2 that are both reachable via primary nexthop nodes E1 and E2. Next, to find a nodeprotecting RLFA path from nodeprotecting PQ node to destinations D1 and D2, inequalities specified in Figure 6 should be evaluated, to ensure if R2 provides a nodeprotecting RLFA path for each of these destinations, as shown below in Table 9. For a RLFA path to qualify as nodeprotecting RLFA path for a destination with multiple ECMP primary nexthop nodes, the RLFA path from the PQnode to the destination MUST satisfy the inequality for all primary nexthop 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: Finding nodeprotecting RLFA path for destinations 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 RLFA paths via nodeprotecting PQnode to final destination can be examined to ensure that none of the primary nexthop nodes is traversed. RLFA path(s) that does not traverse any of the primary nexthop nodes, guarantees nodeprotection in the event of failure of any of the primary nexthop nodes. Table 10 below shows the possible RLFApaths for destinations D1 and D2 via the nodeprotecting PQ node R2. Sarkar, et al. Expires July 24, 2017 [Page 16] InternetDraft RLFA NodeProtection and Manageability January 2017 ++++++  Destination  PrimaryNH  PQNode  RLFA Paths  Exclude   (D)  (E)  (Y)   All       PrimaryNH  ++++++  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: RLFA paths for destinations D1 and D2 From Table 9 and Table 10, in the example above, the RLFA path from R2 does not meet the nodeprotecting inequality for destination D1, while it does meet the same inequality for destination D2. And so, while R2 provides nodeprotecting RLFA alternate for D2, it fails to provide nodeprotection for destination D1. Finally, while it is possible to get a nodeprotecting RLFA path for D2, no such node protecting RLFA path can be found for D1. 2.3.4. Limiting extra computational overhead In addition to the extra reverse SPF computations suggested by the RemoteLFA [RFC7490] draft (one reverse SPF for each of the directly connected neighbors), this document proposes a forward SPF computations for each PQnode discovered in the network. Since the average number of PQnodes 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 PQnode 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 PQnodes computed in the network, with a finite limit on the number of PQnodes in the subset. Implementations MUST choose a default value for this limit and may provide 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 PQnode in this subset. The exact default preference criteria to be used 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. Sarkar, et al. Expires July 24, 2017 [Page 17] InternetDraft RLFA NodeProtection and Manageability January 2017 This document proposes that implementations SHOULD use a default preference criteria for PQnode selection which will put a score on each PQnode, proportional to the number of primary interfaces for which it provides coverage, its distance from the computing router, and its routerid (or systemid in case of ISIS). PQnodes that cover more primary interfaces SHOULD be preferred over PQnodes that cover fewer primary interfaces. When two or more PQnodes cover the same number of primary interfaces, PQnodes which are closer (based on metric) to the computing router SHOULD be preferred over PQnodes farther away from it. For PQnodes that cover the same number of primary interfaces and are the same distance from the computing router, the PQnode with smaller routerid (or systemid in case of ISIS) SHOULD be preferred. Once a subset of PQnodes is found, computing router shall run a forward SPF on each of the PQnodes in the subset to continue with procedures proposed in Section 2.3.2. 3. Manageability of RemoteLFA Alternate Paths 3.1. The Problem With the regular RemoteLFA [RFC7490] functionality the computing router may compute more than one PQnode as usable RemoteLFA alternate nexthops. Additionally [RFC7916] specifies a LFA (and RemoteLFA) manageability framework, in which an alternate selection policy may be configured to let the network operator choose one of them as the most appropriate RemoteLFA alternate. For such policy based alternate selection to run, the computing router needs to collect all the relevant path characteristics (as specified in section 6.2.4 of [RFC7916]) for each of the alternate paths (one through each of the PQnodes). As mentioned before in Section 2.3 the RLFA alternate path through a given PQnode to a given destination is comprised of two path segments. Section 6.2.5.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 alternate path(s). The first path segment (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. However 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. from the PQnode to the destination). In the absence of the path characteristics for the second path segment, two RemoteLFA alternate paths may be equally preferred based on the first path segments characteristics only, although the second path segment attributes may be different. Sarkar, et al. Expires July 24, 2017 [Page 18] InternetDraft RLFA NodeProtection and Manageability January 2017 3.2. The Solution The additional forward SPF computation proposed in Section 2.3.2 document shall also collect links, nodes and path characteristics along the second path segment. This shall enable collection of complete path characteristics for a given RemoteLFA 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 Section 2.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 PQnodes computed in the network, with a finite limit on the number of PQnodes 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 alternateselection policy, this is needed to keep the computational complexity within affordable limits. However if the alternateselection policy is very restrictive 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] or any parts of it. This document specifies a mechanism to meet the requirements specified in section 6.5.2.4 in [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 versions of this document. 5. IANA Considerations N/A.  No protocol changes are proposed in this document. 6. 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 PQnode discovered in the whole network. Sarkar, et al. Expires July 24, 2017 [Page 19] InternetDraft RLFA NodeProtection and Manageability January 2017 7. References 7.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.rfceditor.org/info/rfc2119>. [RFC5286] Atlas, A., Ed. and A. Zinin, Ed., "Basic Specification for IP Fast Reroute: LoopFree Alternates", RFC 5286, DOI 10.17487/RFC5286, September 2008, <http://www.rfceditor.org/info/rfc5286>. [RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N. So, "Remote LoopFree Alternate (LFA) Fast Reroute (FRR)", RFC 7490, DOI 10.17487/RFC7490, April 2015, <http://www.rfceditor.org/info/rfc7490>. 7.2. Informative References [RFC7916] Litkowski, S., Ed., Decraene, B., Filsfils, C., Raza, K., Horneffer, M., and P. Sarkar, "Operational Management of LoopFree Alternates", RFC 7916, DOI 10.17487/RFC7916, July 2016, <http://www.rfceditor.org/info/rfc7916>. Authors' Addresses Pushpasis Sarkar (editor) Individual Contributor Email: pushpasis.ietf@gmail.com Shraddha Hegde Juniper Networks, Inc. Electra, Exora Business Park Bangalore, KA 560103 India Email: shraddha@juniper.net Sarkar, et al. Expires July 24, 2017 [Page 20] InternetDraft RLFA NodeProtection and Manageability January 2017 Chris Bowers Juniper Networks, Inc. 1194 N. Mathilda Ave. Sunnyvale, CA 94089 US Email: cbowers@juniper.net Hannes Gredler RtBrick, Inc. Email: hannes@rtbrick.com Stephane Litkowski Orange Email: stephane.litkowski@orange.com Sarkar, et al. Expires July 24, 2017 [Page 21]