Routing Area Working Group
Internet Engineering Task Force (IETF)                    P. Sarkar, Ed.
Internet-Draft                                    Individual Contributor
Intended status:
Request for Comments: 8102                                  Arrcus, Inc.
Category: Standards Track                                       S. Hegde
Expires: July 24, 2017
ISSN: 2070-1721                                                C. Bowers
                                                  Juniper Networks, Inc.
                                                              H. Gredler
                                                           RtBrick, Inc.
                                                            S. Litkowski
                                                                  Orange
                                                        January 20,
                                                              March 2017

              Remote-LFA Node Protection and Manageability
                draft-ietf-rtgwg-rlfa-node-protection-13

Abstract

   The loop-free alternates (LFAs) computed following the current Remote-LFA
   remote-LFA specification guarantees only link-protection. link protection.  The
   resulting Remote-
   LFA nexthops remote-LFA next hops (also called PQ-nodes), "PQ-nodes") may not
   guarantee node- node protection for all destinations being protected by it.

   This document describes an extension to the Remote Loop-Free based remote-loop-free-based IP
   fast reroute mechanisms, mechanisms that specifes specifies procedures for determining if
   whether or not a given PQ-node provides node-protection node protection for a
   specific destination
   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
   alternate path paths is
   precursory a precursor to apply operator defined applying the operator-defined
   policy for eliminating paths not fitting the 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 Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents an 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 list  It represents the consensus of current Internet-
   Drafts is at http://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid the IETF community.  It has
   received public review and has been approved for a maximum publication by the
   Internet Engineering Steering Group (IESG).  Further information on
   Internet Standards is available in Section 2 of RFC 7841.

   Information about the current status of six months this document, any errata,
   and how to provide feedback on it may be updated, replaced, or obsoleted by other documents obtained at any
   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-Protecting PQ Space PQ-Space  . . . . . . . . . . . . . .   7
       2.2.5.  Candidate Node-Protecting PQ Space PQ-Space  . . . . . . . . .   7
       2.2.6.  Cost-Based Definitions  . . . . . . . . . . . . . . .   7
         2.2.6.1.  Link-Protecting Extended P-Space  . . . . . . . .   7   8
         2.2.6.2.  Node-Protecting Extended P-Space  . . . . . . . .   8
         2.2.6.3.  Q-Space . . . . . . . . . . . . . . . . . . . . .   9
     2.3.  Computing Node-protecting Node-Protecting R-LFA Path  . . . . . . . . . .   9
       2.3.1.  Computing Candidate Node-protecting Node-Protecting PQ-Nodes for
               Primary nexthops Next Hops . . . . . . . . . . . . . . . . . .   9
       2.3.2.  Computing node-protecting paths Node-Protecting Paths from PQ-nodes PQ-Nodes to
               destinations
               Destinations  . . . . . . . . . . . . . . . . . . . .  11
       2.3.3.  Computing Node-Protecting R-LFA Paths for
               Destinations with ECMP primary nexthop nodes  . . Multiple Primary Next-Hop Nodes . .  13
       2.3.4.  Limiting extra computational overhead Extra Computational Overhead . . . . . . . .  17
   3.  Manageability of Remote-LFA Alternate Paths . . . . . . . . .  18
     3.1.  The Problem . . . . . . . . . . . . . . . . . . . . . . .  18
     3.2.  The Solution  . . . . . . . . . . . . . . . . . . . . . .  19  18
   4.  Acknowledgements  .  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  19
   5.  IANA  Security Considerations . . . . . . . . . . . . . . . . . . . . .  19
   6.  Security Considerations  References  . . . . . . . . . . . . . . . . . . . . . . . . .  19
   7.
     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 only link-protection. link protection.  The resulting Remote-LFA remote-LFA
   alternate nexthops next hops (also referred to as the PQ-nodes) "PQ-nodes") may not
   provide
   node-protection node protection for all destinations covered by the same Remote-LFA
   remote-LFA alternate, in case of failure of the primary nexthop node.  Neither next-hop
   node, and it does the specification not 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
   possible Remote-LFA)
   alternate nexthops, remote-LFA), collect the complete set of path
   characteristics for each alternate path, run an alternate-selection
   policy (configured by the operator) operator), and find the best alternate
   path.  This will require that the Remote-LFA remote-LFA implementation to gather gathers
   all the required path characteristics along each link on the entire Remote-LFA
   remote-LFA alternate path.

   With current LFA [RFC5286] and Remote-LFA remote-LFA implementations, the
   forward SPF (and reverse SPF) is run with the computing router and
   its immediate 1-hop one-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.
   Consequently  Consequently, 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 determining node-protection node protection
   with Remote-LFA. remote-LFA.  The same procedure is also extended for the
   collection of a complete set of path attributes, enabling more
   accurate policy-
   based policy-based selection for alternate paths obtained with Remote-LFA.
   remote-LFA.

1.1.  Abbreviations

   This document uses the following list of abbreviations.

      LFA - Loop Free abbreviations:

      LFA: Loop-Free Alternates

      RLFA or R-LFA - R-LFA: Remote Loop Free Loop-Free Alternates

      ECMP - Equal Cost

      ECMP: Equal-Cost Multiple Path

      SPF -
      SPF: Shortest Path First graph computations

      NH - Next Hop

      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 in RFC 2119 [RFC2119].

2.  Node Protection with Remote-LFA

   Node-protection

   Node protection is required to provide protection of traffic on a
   given forwarding node, node against the failure of the first-hop node on
   the primary forwarding path.  Such protection becomes more critical
   in the absence of mechanisms like non-stop-routing non-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 performance complexities overheads it hence introduces. comes along with.
   In such
   cases node-protection cases, node protection is essential to guarantee un-interrupted
   uninterrupted 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 of Remote-LFA remote-LFA and propose a solution.

2.1.  The Problem

   To better illustrate the problem and the solution proposed in this
   document
   document, the following topology diagram from the Remote-LFA remote-LFA document
   [RFC7490]
   draft is 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-E link link, there is no standard LFA alternate.  As per the Remote- remote-
   LFA [RFC7490] alternate specifications specifications, node R2 being the only PQ-node PQ-
   node for the S-E link provides nexthop the next hop for all of the above
   destinations.  Table 1 below, below shows all possible primary and Remote-LFA remote-
   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-LFA backup paths Backup Paths via PQ-node PQ-Node R2

   A closer look at Table 1 shows that, while the PQ-node R2 provides
   link-protection
   link protection for all the destinations, it does not provide node- node
   protection for destinations E and D1.  In the event of the node-
   failure on primary nexthop next hop E, the alternate path from Remote-LFA
   nexthop the remote-LFA
   next hop R2 to E and D1 also becomes unavailable.  So  So, for a Remote-LFA
   nexthop remote-
   LFA next hop to provide node-protection node 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 primary nexthop. next hop.

   In another extension of the topology in Figure 1 1, 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 no more longer on any of the
   shortest paths from N to R3, E E, and D1.  Hence  Hence, R3, E E, and D1 are
   also included in both the Extended-P space extended P-space and Q space the Q-space of E (w.r.t (with
   respect to the S-E link).  Table 2 below, below shows all possible primary
   and R-LFA alternate paths via PQ-node R3, R3 for each destination
   reachable through the S-E link in the above topology.  The R-LFA
   alternate paths via PQ-node R2
   remains remain 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 Backup Paths via PQ-node PQ-Node R3

   Again

   Again, a closer look at Table 2 shows that, unlike Table 1, 1 where the
   single PQ-node R2 provided node-protection node protection for destinations R3 and
   D2, if we choose R3 as the R-LFA nexthop, next hop, it does not provide node- no longer provides node
   protection for R3 and D2 anymore. D2.  If S chooses R3 as the R-LFA
   nexthop, in the event of the next hop and
   if there is a node-failure on primary nexthop next hop E, on
   the alternate path from S to R-LFA nexthop R3, then one of the
   parallel ECMP
   path paths between N and R3 also becomes unavailable.  So unavailable on the
   alternate path from S to R-LFA next hop R3.  So, for a Remote-LFA
   nexthop remote-LFA
   next hop to provide node-protection node protection for a given destination, it is
   also mandatory that, the
   shortest paths from S to the chosen PQ-node MUST NOT traverse the
   primary nexthop next-hop node.

2.2.  Additional Definitions

   This document adds and enhances the following definitions definitions, 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 the link(S-E) link
   (S-E) being protected.

   For a cost-based definition for Link-protecting Extended P-Space 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 nexthop next-hop node E
   being protected, 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 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 node-protecting extended P-space,
   refer to Section 2.2.6.2.

2.2.3.  Q-Space

   The Remote-LFA document [RFC7490] draft already 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 primary nexthop next hop E.  This MUST
   exclude any node for which there is at least one ECMP path from the
   node to the primary nexthop next hop E traversing the link(S-E) link (S-E) being
   protected.

   For a cost-based definition for Q-Space Q-Space, refer to Section 2.2.6.3.

2.2.4.  Link-Protecting PQ Space PQ-Space

   A node Y is in a link-protecting PQ space w.r.t PQ-space with respect to the link
   (S-E) being
   protected, protected if and only if, if Y is present in both link-protecting link-
   protecting extended P-space and the Q-space for the link being
   protected.

2.2.5.  Candidate Node-Protecting PQ Space PQ-Space

   A node Y is in a candidate node-protecting PQ space w.r.t PQ-space with respect to
   the node (E) being protected, protected if and only if, if Y is present in both the
   node-protecting extended P-space and the Q-space for the link being
   protected.

   Please note, 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 primary
   nexthop
   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 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 for Link- of link-
   protecting Extended P-Space. extended P-space.

   A node Y is in a link-protecting extended P-space w.r.t with respect to the
   link (S-E) being protected, protected if and only if, if there exists at least one
   direct neighbor of S, Ni, S (Ni) other than primary nexthop 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 primary
                  nexthop
                  next 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 definition for Node- of node-
   protecting Extended P-Space. extended P-space.

   A node Y is in a node-protecting extended P-space w.r.t with respect to the
   node E being protected, protected if and only if, if there exists at least one
   direct neighbor of S, Ni, S (Ni) other than primary nexthop 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 nexthop next hop on the shortest path from S
                  to destination.
             Ni : A direct neighbor of S other than primary
                  nexthop
                  next hop E.
              Y : The node being evaluated for node-protecting
                  extended P-Space.

              Figure 4: Node-Protecting Ext-P-Space Condition

   Please note, 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 for of Q-Space.

   A node Y is in Q-space w.r.t with respect to the link (S-E) being protected, protected
   if and only if, if the following condition is satisfied. 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 nexthop next hop on the shortest path from S
                  to destination.
             Y  : The node being evaluated for Q-Space.

                        Figure 5: Q-Space Condition

2.3.  Computing Node-protecting Node-Protecting R-LFA Path

   The R-LFA alternate path through a given PQ-node to a given
   destination is comprised of two path segments as follows. follows:

   1.  Path segment from the computing router to the PQ-node (Remote-LFA
       alternate nexthop), next hop), and

   2.  Path segment from the PQ-node to the destination being protected.

   So

   So, to ensure a that an R-LFA alternate path for a given destination
   provides
   node-protection node protection, we need to ensure that none of the above
   path segments are affected in the event of failure of the primary nexthop
   next-hop node.  Sections Section 2.3.1 and Section 2.3.2 show how this can be
   ensured.

2.3.1.  Computing Candidate Node-protecting Node-Protecting PQ-Nodes for Primary
        nexthops Next
        Hops

   To choose a node-protecting R-LFA nexthop next hop for a destination R3,
   router S needs to consider a PQ-node from the candidate node-
   protecting PQ-space for the primary nexthop next 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-node
   does do not traverse primary nexthop next-hop node E.

   Implementations SHOULD run the inequality in Section 2.2.2 2.2.6.2,
   Figure 4 for all direct neighbors, other than primary nexthop next-hop node
   E, to determine whether a node Y is a candidate node-protecting PQ-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 3 below
   shows how the above condition can be used to determine the candidate node-
   protecting
   node-protecting PQ-space for S-E link (primary nexthop 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 Node-Protection Evaluation for R-LFA repair tunnel Repair Tunnel to PQ-
                                   node
                                   Node

   As seen in the above Table 3, R3 does not meet the node-protecting
   extended-p-space inequality and
   extended p-space inequality; so, while R2 is in candidate node-
   protecting PQ 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.  So computations [RFC5286].  So, S may re-use the list of
   links and nodes collected from the same SPF computations, computations to decide
   whether or not a node Y is a candidate node-protecting PQ-node or not. PQ-node.  A
   node Y shall be considered as a node-protecting PQ-node, PQ-node if and only
   if,
   if there is at least one direct neighbor of S, other than the primary nexthop E,
   next hop E for which, which the primary nexthop next-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-Protection Link       | Node-Protection Node       |
   | 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-LFA tunnel Tunnel to the PQ-node PQ-Node

   As seen in the above Table 4 4, while R2 is a candidate node-protecting
   Remote-LFA nexthop
   remote-LFA next hop for R3 and D2, it is not so for E and D1, since
   the primary nexthop next hop E is in on the shortest path from R2 to E and D1.

2.3.2.  Computing node-protecting paths Node-Protecting Paths from PQ-nodes PQ-Nodes to destinations Destinations

   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 this section, section to choose one or more node-
   protecting R-LFA paths, 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 primary
   nexthop, 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
   primary nexthop next-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 primary nexthop node next-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 the PQ-nodes, PQ-nodes to discover all shortest paths from the PQ-nodes to
   the destination.  This will help determine, if determine whether or not a given
   primary
   nexthop next-hop node is on the shortest paths from the PQ-node to
   the given
   destination or not. destination.  To determine if whether or not a given candidate node-
   protecting
   node-protecting PQ-node provides node-protecting alternate for a
   given destination, or not, all the shortest paths from the PQ-node to the
   given destination has have to be inspected, inspected to check if the primary
   nexthop next-
   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 given destination, destination does not guarantee
   node-protection node
   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 primary nexthop 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 PQ-Node to Destination

   All of the above metric costs costs, except D_opt(Y, D), can be obtained
   with forward and reverse SPFs with E(the E (the primary nexthop) next hop) as the
   root, run as part of the regular LFA and Remote-LFA remote-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 5 below shows how that the above
   condition can be used to determine node-protection node 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 evaluation Node-Protection Evaluation for R-LFA path segment Path Segment between
                          PQ-node
                          PQ-Node and destination Destination

   As seen in the above example above, R2 does not meet the node-
   protecting node-protecting
   inequality for destination E, E and D1.  And so, once again, while R2 is
   a node-protecting Remote-LFA nexthop remote-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 provides node-protection node protection for a
   given
   destination or not, destination, the list of nodes computed from forward SPF that
   run on the PQ-node, PQ-node for the given destination, destination SHOULD be inspected.  In
   case the list contains the primary nexthop next-hop node, the PQ-node does
   not provide node-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 to PQ-   |                 |                 |
   |             | 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-LFA path Path between PQ-node and
                                destination
                                Destination

   As seen in the above example example, while R2 is a candidate node-protecting
   R-LFA nexthop next hop for R3 and D2, it is not so for E and D1, since the
   primary nexthop next hop E is in on 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 given Remote-LFA remote-LFA alternate provides node- node
   protection for a given destination or not. destination.  It does not find out any new Remote-LFA
   remote-LFA alternate nexthops, next hops, outside the ones already computed by
   the standard Remote-LFA remote-LFA procedure.  However, in the case of
   availability of more than one PQ-node (Remote-LFA (remote-LFA alternates) for a destination,
   and node-protection
   destination where node protection is required for the given primary nexthop,
   next hop, this procedure will eliminate the PQ-nodes that do not
   provide node- node protection and choose only the ones that does. do.

2.3.3.  Computing Node-Protecting R-LFA Paths for Destinations with ECMP
        primary nexthop nodes
        Multiple Primary Next-Hop Nodes

   In certain scenarios, when one or more destinations maybe may be reachable
   via multiple ECMP (equal-cost-multi-path) nexthop nodes, next-hop nodes and only
   link-protection
   link protection is required, there is no need to compute any
   alternate paths for such destinations.  In the event of failure of
   one of the nexthop next-hop links, the remaining primary nexthops next hops shall
   always provide link-protection. link protection.  However, if node-protection node protection is
   required, the rest of the primary nexthops next hops may not guarantee node-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

   Primary Nexthops: Next hops:
     Destination D1 = [{ S-E1, E1}, {S-E2, E2}]
     Destination D2 = [{ S-E1, E1}, {S-E2, E2}]

          Figure 7: Topology with multiple Multiple ECMP primary nexthops Primary 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 ECMP nexthop next-hop nodes E1 and E2.  However  However, the
   primary paths via nexthop next-hop node E2 also traverses traverse via the nexthop next-hop
   node E1.  So  So, in the event of node failure of nexthop next-hop node E1, both
   primary paths (via E1 and E2) becomes become unavailable.  Hence  Hence, if node-protection node
   protection is desired for destinations D1 and D2, alternate paths
   that does do not traverse any of the primary nexthop next-hop nodes E1 and E2, E2 need
   to be computed.  In the above topology topology, the only alternate neighbor N
   does not provide such a an LFA alternate path.  Hence  Hence, 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 are the link-protecting PQ-nodes. PQ-nodes are as follows:

      Primary Nexthop: Next Hop: E1, Link-Protecting PQ-Node: { R2 }

      Primary Nexthop: 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) needs need to be
   determined first.  Inequalities specified in Section Sections 2.2.6.2 and
   Section
   2.2.6.3 can be evaluated to compute the node-protecting PQ-
   space PQ-space for
   each of the nexthop next-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 primary nexthop next-hop nodes, the PQ-node MUST satisfy the
   inequality for all primary nexthop next-hop nodes.  Any PQ-node
   which that is NOT a
   node-protecting PQ-node for all the primary nexthop
   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    |
   |  hop  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 Node-Protected PQ-Nodes for nexthop Next 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 primary nexthop next-hop nodes is are
   traversed.  PQ-nodes that provide one (or more) or more Tunnel-repair
   paths(s) pathss
   that does do not traverse any of the primary nexthop 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-Repair paths Paths to PQ-node PQ-Node R2

   From Table Tables 7 and Table 8, 8 in the above example, example above, R2 being node-
   protecting PQ-node is a node-protecting PQ-
   node for both primary nexthops next hops E1 and E2, E2 and should be chosen as the
   node-protecting PQ-node for destinations D1 and D2 that are both
   reachable via the primary nexthop next-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 be evaluated, evaluated to ensure if that R2 provides a node-protecting
   R-LFA path for each of these destinations, as shown below in Table 9.
   For
   a an R-LFA path to qualify as a node-protecting R-LFA path for a
   destination with multiple ECMP primary nexthop next-hop nodes, the R-LFA path
   from the PQ-node to the destination MUST satisfy the inequality for
   all primary nexthop next-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: Finding node-protecting Node-Protecting R-LFA path Path for destinations 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
   R-LFA paths via a node-protecting PQ-node to the final destination
   can be examined to ensure that none of the primary nexthop next-hop nodes is are
   traversed.  One or more R-LFA path(s) paths that does do not traverse any of the
   primary
   nexthop nodes, next-hop nodes guarantees node-protection node protection in the event of
   failure of any of the primary nexthop next-hop nodes.  Table 10 below shows
   the possible R-LFA-paths for destinations D1 and D2 via the node-protecting PQ-
   node 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 Paths for destinations Destinations D1 and D2
   From Table Tables 9 and Table 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
   provide node-protection node 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.  Limiting extra computational overhead Extra 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 SPF
   computations
   computation 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 this document, 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 which that 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-nodes which that 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 regular Remote-LFA remote-LFA [RFC7490] functionality functionality, the computing
   router may compute more than one PQ-node as usable Remote-LFA remote-LFA
   alternate nexthops.  Additionally next hops.  Additionally, [RFC7916] specifies a an LFA (and
   Remote-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 appropriate Remote-LFA alternate. remote-LFA alternates.  For such policy-
   based a
   policy-based alternate selection to run, the computing router needs
   to collect all the relevant path characteristics (as specified in
   section
   Section 6.2.4 of [RFC7916]) for each of the alternate paths (one
   through each of the PQ-nodes).  As mentioned before in Section 2.3 2.3,
   the R-LFA alternate path through a given PQ-node to a given
   destination is comprised of two path segments.  Section 6.2.5.4 6.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 alternate path(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.  However  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. (i.e.,
   from the PQ-node to the destination).  In the absence of the path
   characteristics for the second path segment, two Remote-LFA remote-LFA alternate
   paths may be equally preferred based on the first path segments segment
   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.2
   document
   shall also collect links, nodes nodes, and path characteristics along the
   second path segment.  This shall enable the collection of complete
   path characteristics for a given Remote-LFA remote-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 Section 2.3.4 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 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.  However  However, if the alternate-selection policy is very
   restrictive
   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 part of it. [RFC7916].  This document specifies a mechanism to meet
   the requirements specified in section 6.5.2.4 in Section 6.2.5.4 of [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.

   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.  References

7.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>.

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 Contributor
   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
   US
   United States of America

   Email: cbowers@juniper.net

   Hannes Gredler
   RtBrick, Inc.

   Email: hannes@rtbrick.com
   Stephane Litkowski
   Orange

   Email: stephane.litkowski@orange.com