GENWiki

Premier IT Outsourcing and Support Services within the UK

User Tools

Site Tools


rfc:rfc8102

Internet Engineering Task Force (IETF) P. Sarkar, Ed. Request for Comments: 8102 Arrcus, Inc. Category: Standards Track S. Hegde ISSN: 2070-1721 C. Bowers

                                                Juniper Networks, Inc.
                                                            H. Gredler
                                                         RtBrick, Inc.
                                                          S. Litkowski
                                                                Orange
                                                            March 2017
            Remote-LFA Node Protection and Manageability

Abstract

 The loop-free alternates (LFAs) computed following the current
 remote-LFA specification guarantees only link protection.  The
 resulting remote-LFA next hops (also called "PQ-nodes") may not
 guarantee node protection for all destinations being protected by it.
 This document describes an extension to the remote-loop-free-based IP
 fast reroute mechanisms that specifies procedures for determining
 whether or not a given PQ-node provides node protection for a
 specific 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 paths is a precursor to applying the operator-defined
 policy for eliminating paths not fitting the constraints.

Status of This Memo

 This is an Internet Standards Track document.
 This document is a product of the Internet Engineering Task Force
 (IETF).  It represents the consensus of the IETF community.  It has
 received public review and has been approved for 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 this document, any errata,
 and how to provide feedback on it may be obtained at
 http://www.rfc-editor.org/info/rfc8102.

Sarkar, et al. Standards Track [Page 1] RFC 8102 R-LFA Node Protection and Manageability March 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/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.

Sarkar, et al. Standards Track [Page 2] RFC 8102 R-LFA Node Protection and Manageability March 2017

Table of Contents

 1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   4
   1.1.  Abbreviations . . . . . . . . . . . . . . . . . . . . . .   4
   1.2.  Requirements Language . . . . . . . . . . . . . . . . . .   5
 2.  Node Protection with Remote-LFA . . . . . . . . . . . . . . .   5
   2.1.  The Problem . . . . . . . . . . . . . . . . . . . . . . .   5
   2.2.  Additional Definitions  . . . . . . . . . . . . . . . . .   7
     2.2.1.  Link-Protecting Extended P-Space  . . . . . . . . . .   7
     2.2.2.  Node-Protecting Extended P-Space  . . . . . . . . . .   7
     2.2.3.  Q-Space . . . . . . . . . . . . . . . . . . . . . . .   8
     2.2.4.  Link-Protecting PQ-Space  . . . . . . . . . . . . . .   8
     2.2.5.  Candidate Node-Protecting PQ-Space  . . . . . . . . .   8
     2.2.6.  Cost-Based Definitions  . . . . . . . . . . . . . . .   8
       2.2.6.1.  Link-Protecting Extended P-Space  . . . . . . . .   9
       2.2.6.2.  Node-Protecting Extended P-Space  . . . . . . . .   9
       2.2.6.3.  Q-Space . . . . . . . . . . . . . . . . . . . . .  10
   2.3.  Computing Node-Protecting R-LFA Path  . . . . . . . . . .  10
     2.3.1.  Computing Candidate Node-Protecting PQ-Nodes for
             Primary Next Hops . . . . . . . . . . . . . . . . . .  10
     2.3.2.  Computing Node-Protecting Paths from PQ-Nodes to
             Destinations  . . . . . . . . . . . . . . . . . . . .  12
     2.3.3.  Computing Node-Protecting R-LFA Paths for
             Destinations with Multiple Primary Next-Hop Nodes . .  14
     2.3.4.  Limiting Extra Computational Overhead . . . . . . . .  18
 3.  Manageability of Remote-LFA Alternate Paths . . . . . . . . .  19
   3.1.  The Problem . . . . . . . . . . . . . . . . . . . . . . .  19
   3.2.  The Solution  . . . . . . . . . . . . . . . . . . . . . .  20
 4.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  20
 5.  Security Considerations . . . . . . . . . . . . . . . . . . .  20
 6.  References  . . . . . . . . . . . . . . . . . . . . . . . . .  21
   6.1.  Normative References  . . . . . . . . . . . . . . . . . .  21
   6.2.  Informative References  . . . . . . . . . . . . . . . . .  21
 Acknowledgements  . . . . . . . . . . . . . . . . . . . . . . . .  21
 Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  22

Sarkar, et al. Standards Track [Page 3] RFC 8102 R-LFA Node Protection and Manageability March 2017

1. Introduction

 The Remote-LFA specification [RFC7490] provides loop-free alternates
 that guarantee only link protection.  The resulting remote-LFA
 alternate next hops (also referred to as the "PQ-nodes") may not
 provide node protection for all destinations covered by the same
 remote-LFA alternate, in case of failure of the primary next-hop
 node, and it does not provide a means to determine the same.
 Also, the LFA Manageability document [RFC7916] requires a computing
 router to find all possible alternate next hops (including all
 possible remote-LFA), collect the complete set of path
 characteristics for each alternate path, run an alternate-selection
 policy (configured by the operator), and find the best alternate
 path.  This will require that the remote-LFA implementation gathers
 all the required path characteristics along each link on the entire
 remote-LFA alternate path.
 With current LFA [RFC5286] and remote-LFA implementations, the
 forward SPF (and reverse SPF) is run with the computing router and
 its immediate one-hop routers as the roots.  While that enables
 computation of path attributes (e.g., Shared Risk Link Group (SRLG)
 and Admin-groups) for the first alternate path segment from the
 computing router to the PQ-node, 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, 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
 with remote-LFA.  The same procedure is also extended for the
 collection of a complete set of path attributes, enabling more
 accurate policy-based selection for alternate paths obtained with
 remote-LFA.

1.1. Abbreviations

 This document uses the following list of abbreviations:
    LFA: Loop-Free Alternates
    RLFA or R-LFA: Remote Loop-Free Alternates
    ECMP: Equal-Cost Multiple Path
    SPF: Shortest Path First graph computations
    NH: Next-Hop node

Sarkar, et al. Standards Track [Page 4] RFC 8102 R-LFA Node Protection and Manageability March 2017

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 is required to provide protection of traffic on a
 given forwarding 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 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 overheads it comes along with.
 In such cases, node protection is essential to guarantee
 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 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 remote-LFA document
 [RFC7490] 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, there is no standard LFA alternate.  As per the remote-
 LFA [RFC7490] alternate specifications, node R2 being the only PQ-
 node for the S-E link provides the next hop for all of the above
 destinations.  Table 1 shows all possible primary and remote-LFA
 alternate paths for each destination.

Sarkar, et al. Standards Track [Page 5] RFC 8102 R-LFA Node Protection and Manageability March 2017

  +-------------+--------------+---------+-------------------------+
  | Destination | Primary Path | PQ-node | Remote-LFA Backup Path  |
  +-------------+--------------+---------+-------------------------+
  | R3          | S->E->R3     | R2      | S=>N=>R1=>R2->R3        |
  | E           | S->E         | R2      | S=>N=>R1=>R2->R3->E     |
  | D1          | S->E->D1     | R2      | S=>N=>R1=>R2->R3->E->D1 |
  | D2          | S->E->R3->D2 | R2      | S=>N=>R1=>R2->R3->D2    |
  +-------------+--------------+---------+-------------------------+
            Table 1: Remote-LFA Backup Paths via PQ-Node R2
 A closer look at Table 1 shows that, while the PQ-node R2 provides
 link protection for all the destinations, it does not provide node
 protection for destinations E and D1.  In the event of the node-
 failure on primary next hop E, the alternate path from the remote-LFA
 next hop R2 to E and D1 also becomes unavailable.  So, for a remote-
 LFA next hop to provide node protection for a given destination, the
 shortest path from the given PQ-node to the given destination MUST
 NOT traverse the primary next hop.
 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
                                          /
                                     S-x-E
                                    /   / \
                                   N---+   R3--D2
                                    \     /
                                    R1---R2
                         Figure 2: Topology 2
 In the above topology, the S-E link is no longer on any of the
 shortest paths from N to R3, E, and D1.  Hence, R3, E, and D1 are
 also included in both the extended P-space and the Q-space of E (with
 respect to the S-E link).  Table 2 shows all possible primary and
 R-LFA alternate paths via PQ-node R3 for each destination reachable
 through the S-E link in the above topology.  The R-LFA alternate
 paths via PQ-node R2 remain the same as in Table 1.

Sarkar, et al. Standards Track [Page 6] RFC 8102 R-LFA Node Protection and Manageability March 2017

   +-------------+--------------+---------+------------------------+
   | Destination | Primary Path | PQ-node | Remote-LFA Backup Path |
   +-------------+--------------+---------+------------------------+
   | R3          | S->E->R3     | R3      | S=>N=>E=>R3            |
   | E           | S->E         | R3      | S=>N=>E=>R3->E         |
   | D1          | S->E->D1     | R3      | S=>N=>E=>R3->E->D1     |
   | D2          | S->E->R3->D2 | R3      | S=>N=>E=>R3->D2        |
   +-------------+--------------+---------+------------------------+
            Table 2: Remote-LFA Backup Paths via PQ-Node R3
 Again, a closer look at Table 2 shows that, unlike Table 1 where the
 single PQ-node R2 provided node protection for destinations R3 and
 D2, if we choose R3 as the R-LFA next hop, it no longer provides node
 protection for R3 and D2.  If S chooses R3 as the R-LFA next hop and
 if there is a node-failure on primary next hop E, then one of the
 parallel ECMP paths between N and R3 also becomes unavailable on the
 alternate path from S to R-LFA next hop R3.  So, for a remote-LFA
 next hop to provide node protection for a given destination, the
 shortest paths from S to the chosen PQ-node MUST NOT traverse the
 primary next-hop node.

2.2. Additional Definitions

 This document adds and enhances the following definitions, extending
 the ones mentioned in the Remote-LFA specification [RFC7490].

2.2.1. Link-Protecting Extended P-Space

 The Remote-LFA 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) being protected.
 For a cost-based definition for link-protecting extended P-space,
 refer to Section 2.2.6.1.

2.2.2. Node-Protecting Extended P-Space

 The node-protecting extended P-space for a primary next-hop node E
 being protected is the set of routers that are reachable from one or
 more direct neighbors of S, except primary node E, without traversing
 node E.  This MUST exclude any direct neighbors for which there is at

Sarkar, et al. Standards Track [Page 7] RFC 8102 R-LFA Node Protection and Manageability March 2017

 least one ECMP path from the direct neighbor traversing the node E
 being protected.
 For a cost-based definition for node-protecting extended P-space,
 refer to Section 2.2.6.2.

2.2.3. Q-Space

 The Remote-LFA document [RFC7490] 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 next hop E.  This MUST
 exclude any node for which there is at least one ECMP path from the
 node to the primary next hop E traversing the link (S-E) being
 protected.
 For a cost-based definition for Q-Space, refer to Section 2.2.6.3.

2.2.4. Link-Protecting PQ-Space

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

2.2.5. Candidate Node-Protecting PQ-Space

 A node Y is in a candidate node-protecting PQ-space with respect to
 the node (E) being protected if and only if Y is present in both the
 node-protecting extended P-space and the Q-space for the link being
 protected.
 Please note that a node Y being in a candidate node-protecting PQ-
 space does not guarantee that the R-LFA alternate path via the same,
 in entirety, is unaffected in the event of a node failure of primary
 next-hop node E.  It only guarantees that the path segment from S to
 PQ-node Y is unaffected by the same failure event.  The PQ-nodes in
 the candidate node-protecting PQ-space may provide node protection
 for only a subset of destinations that are reachable through the
 corresponding primary link.

2.2.6. Cost-Based Definitions

 This section provides cost-based definitions for some of the terms
 introduced in Section 2.2 of this document.

Sarkar, et al. Standards Track [Page 8] RFC 8102 R-LFA Node Protection and Manageability March 2017

2.2.6.1. Link-Protecting Extended P-Space

 Please refer to Section 2.2.1 for a formal definition of link-
 protecting extended P-space.
 A node Y is in a link-protecting extended P-space with respect to the
 link (S-E) being protected if and only if there exists at least one
 direct neighbor of S (Ni) other than primary next hop E that
 satisfies the following condition.
 D_opt(Ni,Y) < D_opt(Ni,S) + D_opt(S,Y)
 Where,
   D_opt(A,B) : Distance on the most optimum path from A to B.
          Ni  : A direct neighbor of S other than primary
                next hop E.
           Y  : The node being evaluated for link-protecting
                extended P-Space.
            Figure 3: Link-Protecting Ext-P-Space Condition

2.2.6.2. Node-Protecting Extended P-Space

 Please refer to Section 2.2.2 for a formal definition of node-
 protecting extended P-space.
 A node Y is in a node-protecting extended P-space with respect to the
 node E being protected if and only if there exists at least one
 direct neighbor of S (Ni) other than primary next hop E, that
 satisfies the following condition.
 D_opt(Ni,Y) < D_opt(Ni,E) + D_opt(E,Y)
 Where,
   D_opt(A,B) : Distance on the most optimum path from A to B.
           E  : The primary next hop on the shortest path from S
                to destination.
           Ni : A direct neighbor of S other than primary
                next hop E.
            Y : The node being evaluated for node-protecting
                extended P-Space.
            Figure 4: Node-Protecting Ext-P-Space Condition
 Please 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

Sarkar, et al. Standards Track [Page 9] RFC 8102 R-LFA Node Protection and Manageability March 2017

 from node Y to the destination is also unaffected by the same failure
 event.

2.2.6.3. Q-Space

 Please refer to Section 2.2.3 for a formal definition of Q-Space.
 A node Y is in Q-space with respect to the link (S-E) being protected
 if and only if the following condition is satisfied:
 D_opt(Y,E) < D_opt(S,E) + D_opt(Y,S)
 Where,
   D_opt(A,B) : Distance on the most optimum path from A to B.
           E  : The primary next hop on the shortest path from S
                to destination.
           Y  : The node being evaluated for Q-Space.
                      Figure 5: Q-Space Condition

2.3. Computing 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:
 1.  Path segment from the computing router to the PQ-node (Remote-LFA
     alternate next hop), and
 2.  Path segment from the PQ-node to the destination being protected.
 So, to ensure that an R-LFA alternate path for a given destination
 provides node protection, we need to ensure that none of the above
 path segments are affected in the event of failure of the primary
 next-hop node.  Sections 2.3.1 and 2.3.2 show how this can be
 ensured.

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

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

Sarkar, et al. Standards Track [Page 10] RFC 8102 R-LFA Node Protection and Manageability March 2017

 Implementations SHOULD run the inequality in Section 2.2.6.2,
 Figure 4 for all direct neighbors, other than primary next-hop node
 E, to determine whether a node Y is a candidate node-protecting 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
 shows how the above condition can be used to determine the candidate
 node-protecting PQ-space for S-E link (primary next hop E).
 +------------+----------+----------+----------+---------+-----------+
 | Candidate  |  Direct  |  D_opt   |  D_opt   |  D_opt  | Condition |
 |  PQ-node   | Nbr (Ni) |  (Ni,Y)  |  (Ni,E)  |  (E,Y)  |    Met    |
 |    (Y)     |          |          |          |         |           |
 +------------+----------+----------+----------+---------+-----------+
 |     R2     |    N     | 2 (N,R2) | 1 (N,E)  |    2    |    Yes    |
 |            |          |          |          |  (E,R2) |           |
 |     R3     |    N     | 2 (N,R3) | 1 (N,E)  |    1    |     No    |
 |            |          |          |          |  (E,R3) |           |
 +------------+----------+----------+----------+---------+-----------+
  Table 3: Node-Protection Evaluation for R-LFA Repair Tunnel to PQ-
                                 Node
 As seen in the above Table 3, R3 does not meet the node-protecting
 extended p-space inequality; 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 computations [RFC5286].  So, S may re-use the list of
 links and nodes collected from the same SPF computations to decide
 whether or not a node Y is a candidate node-protecting PQ-node.  A
 node Y shall be considered as a node-protecting PQ-node if and only
 if there is at least one direct neighbor of S, other than the primary
 next hop E for which the primary next-hop node E does not exist on
 the list of nodes traversed on any of the shortest paths from the
 direct neighbor to the PQ-node.  Table 4 is an illustration of the
 mechanism with the topology in Figure 2.

Sarkar, et al. Standards Track [Page 11] RFC 8102 R-LFA Node Protection and Manageability March 2017

 +-------------+---------------------------+------------+------------+
 | Candidate   | Repair Tunnel Path        | Link       | Node       |
 | PQ-node     | (Repairing router to PQ-  | Protection | Protection |
 |             | node)                     |            |            |
 +-------------+---------------------------+------------+------------+
 | R2          | S->N->R1->R2              | Yes        | Yes        |
 | R2          | S->E->R3->R2              | No         | No         |
 | R3          | S->N->E->R3               | Yes        | No         |
 +-------------+---------------------------+------------+------------+
        Table 4: Protection of Remote-LFA Tunnel to the PQ-Node
 As seen in the above Table 4, while R2 is a candidate node-protecting
 remote-LFA next hop for R3 and D2, it is not so for E and D1, since
 the primary next hop E is on the shortest path from R2 to E and D1.

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

Sarkar, et al. Standards Track [Page 12] RFC 8102 R-LFA Node Protection and Manageability March 2017

 qualify the condition for a given destination does not guarantee 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 next hop on the shortest path from S
                to destination.
           Y  : The node-protecting PQ-node being evaluated
    Figure 6: Node-Protecting Condition for PQ-Node to Destination
 All of the above metric costs, except D_opt(Y, D), can be obtained
 with forward and reverse SPFs with E (the primary next hop) as the
 root, run as part of the regular LFA and 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 shows that the above
 condition can be used to determine 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 for R-LFA Path Segment between
                        PQ-Node and Destination
 As seen in the example above, R2 does not meet the node-protecting
 inequality for destination E and D1.  And so, once again, while R2 is
 a node-protecting remote-LFA next hop for R3 and D2, it is not so for
 E and D1.

Sarkar, et al. Standards Track [Page 13] RFC 8102 R-LFA Node Protection and Manageability March 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 or not a PQ-node provides node protection for a
 given destination, the list of nodes computed from forward SPF that
 run on the PQ-node for the given destination SHOULD be inspected.  In
 case the list contains the primary next-hop node, the PQ-node does
 not provide 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 (Repairing  | Link       | Node       |
 |             | router to PQ-node)        | Protection | Protection |
 +-------------+---------------------------+------------+------------+
 | R3          | R2->R3                    | Yes        | Yes        |
 | E           | R2->R3->E                 | Yes        | No         |
 | D1          | R2->R3->E->D1             | Yes        | No         |
 | D2          | R2->R3->D2                | Yes        | Yes        |
 +-------------+---------------------------+------------+------------+
      Table 6: Protection of Remote-LFA Path between PQ-node and
                              Destination
 As seen in the above example, while R2 is a candidate node-protecting
 R-LFA next hop for R3 and D2, it is not so for E and D1, since the
 primary next hop E is 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 alternate provides node
 protection for a given destination.  It does not find out any new
 remote-LFA alternate next hops, outside the ones already computed by
 the standard remote-LFA procedure.  However, in the case of
 availability of more than one PQ-node (remote-LFA alternates) for a
 destination where node protection is required for the given primary
 next hop, this procedure will eliminate the PQ-nodes that do not
 provide node protection and choose only the ones that do.

2.3.3. Computing Node-Protecting R-LFA Paths for Destinations with

      Multiple Primary Next-Hop Nodes
 In certain scenarios, when one or more destinations may be reachable
 via multiple ECMP (equal-cost-multi-path) next-hop nodes and only
 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 next-hop links, the remaining primary next hops shall
 always provide link protection.  However, if node protection is

Sarkar, et al. Standards Track [Page 14] RFC 8102 R-LFA Node Protection and Manageability March 2017

 required, the rest of the primary next hops may not guarantee 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 Next hops:
   Destination D1 = [{ S-E1, E1}, {S-E2, E2}]
   Destination D2 = [{ S-E1, E1}, {S-E2, E2}]
        Figure 7: Topology with Multiple ECMP 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 next-hop nodes E1 and E2.  However, the
 primary paths via next-hop node E2 also traverse via the next-hop
 node E1.  So, in the event of node failure of next-hop node E1, both
 primary paths (via E1 and E2) become unavailable.  Hence, if node
 protection is desired for destinations D1 and D2, alternate paths
 that do not traverse any of the primary next-hop nodes E1 and E2 need
 to be computed.  In the above topology, the only alternate neighbor N
 does not provide such an LFA alternate path.  Hence, one or more
 R-LFA node-protecting alternate paths for destinations D1 and D2,
 needs to be computed.
 In the above topology, the link-protecting PQ-nodes are as follows:
    Primary Next Hop: E1, Link-Protecting PQ-Node: { R2 }
    Primary Next Hop: E2, Link-Protecting PQ-Node: { R2 }

Sarkar, et al. Standards Track [Page 15] RFC 8102 R-LFA Node Protection and Manageability March 2017

 To find one (or more) node-protecting R-LFA paths for destinations D1
 and D2, one (or more) node-protecting PQ-node(s) need to be
 determined first.  Inequalities specified in Sections 2.2.6.2 and
 2.2.6.3 can be evaluated to compute the node-protecting PQ-space for
 each of the 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 next-hop nodes, the PQ-node MUST satisfy the
 inequality for all primary next-hop nodes.  Any PQ-node that is NOT a
 node-protecting PQ-node for all the primary next-hop nodes MUST NOT
 be chosen as the node-protecting PQ-node for the destination.
 +--------+----------+-------+--------+--------+---------+-----------+
 | Primary| Candidate| Direct| D_opt  | D_opt  |  D_opt  | Condition |
 |  Next  |   PQ-    |  Nbr  | (Ni,Y) | (Ni,E) |  (E,Y)  |    Met    |
 |  Hop   | node (Y) |  (Ni) |        |        |         |           |
 |  (E)   |          |       |        |        |         |           |
 +--------+----------+-------+--------+--------+---------+-----------+
 |   E1   |    R2    |   N   |   3    |   3    |    2    |    Yes    |
 |        |          |       | (N,R2) | (N,E1) | (E1,R2) |           |
 |   E2   |    R2    |   N   |   3    |   2    |    3    |    Yes    |
 |        |          |       | (N,R2) | (N,E2) | (E2,R2) |           |
 +--------+----------+-------+--------+--------+---------+-----------+
   Table 7: Computing Node-Protected PQ-Nodes for Next Hop E1 and E2
 In SPF implementations that also 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 next-hop nodes are
 traversed.  PQ-nodes that provide one or more Tunnel-repair paths
 that do not traverse any of the primary 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 to PQ-Node R2
 From Tables 7 and 8 in the example above, R2 is a node-protecting PQ-
 node for both primary next hops E1 and E2 and should be chosen as the
 node-protecting PQ-node for destinations D1 and D2 that are both
 reachable via the primary next-hop nodes E1 and E2.

Sarkar, et al. Standards Track [Page 16] RFC 8102 R-LFA Node Protection and Manageability March 2017

 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 to ensure that R2 provides a node-protecting
 R-LFA path for each of these destinations, as shown below in Table 9.
 For an R-LFA path to qualify as a node-protecting R-LFA path for a
 destination with multiple ECMP primary next-hop nodes, the R-LFA path
 from the PQ-node to the destination MUST satisfy the inequality for
 all primary next-hop nodes.
 +----------+----------+-------+--------+--------+--------+----------+
 | Destinat | Primary- |  PQ-  | D_opt  | D_opt  | D_opt  | Condition|
 | ion (D)  |  NH (E)  |  Node | (Y, D) | (Y, E) | (E, D) |   Met    |
 |          |          |  (Y)  |        |        |        |          |
 +----------+----------+-------+--------+--------+--------+----------+
 |    D1    |    E1    |   R2  | 3 (R2, | 2 (R2, | 1 (E1, |    No    |
 |          |          |       |  D1)   |  E1)   |  D1)   |          |
 |    D1    |    E2    |   R2  | 3 (R2, | 3 (R2, | 2 (E2, |   Yes    |
 |          |          |       |  D1)   |  E2)   |  D1)   |          |
 |    D2    |    E1    |   R2  | 2 (R2, | 2 (R2, | 2 (E1, |   Yes    |
 |          |          |       |  D2)   |  E1)   |  D2)   |          |
 |    D2    |    E2    |   R2  | 2 (R2, | 2 (R2, | 3 (E2, |   Yes    |
 |          |          |       |  D2)   |  E2)   |  D2)   |          |
 +----------+----------+-------+--------+--------+--------+----------+
            Table 9: Finding Node-Protecting R-LFA Path for
                        Destinations D1 and D2
 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 next-hop nodes are
 traversed.  One or more R-LFA paths that do not traverse any of the
 primary next-hop nodes guarantees node protection in the event of
 failure of any of the primary next-hop nodes.  Table 10 shows the
 possible R-LFA-paths for destinations D1 and D2 via the node-
 protecting PQ-node R2.

Sarkar, et al. Standards Track [Page 17] RFC 8102 R-LFA Node Protection and Manageability March 2017

 +-------------+------------+---------+-----------------+------------+
 | Destination | Primary-NH | PQ-Node |   R-LFA Paths   |  Exclude   |
 |     (D)     |    (E)     |   (Y)   |                 |    All     |
 |             |            |         |                 | Primary-NH |
 +-------------+------------+---------+-----------------+------------+
 |      D1     |   E1, E2   |    R2   | S==>N==>R1==>R2 |     No     |
 |             |            |         | -->R3-->E1-->D1 |            |
 |             |            |         |                 |            |
 |      D2     |   E1, E2   |    R2   | S==>N==>R1==>R2 |    Yes     |
 |             |            |         |    -->R3-->D2   |            |
 +-------------+------------+---------+-----------------+------------+
           Table 10: R-LFA Paths for Destinations D1 and D2
 From Tables 9 and 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.  So, while
 R2 provides a node-protecting R-LFA alternate for D2, it fails to
 provide 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

 In addition to the extra reverse SPF computations suggested by the
 Remote-LFA document [RFC7490] (one reverse SPF for each of the
 directly connected neighbors), this document proposes a forward SPF
 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 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. Standards Track [Page 18] RFC 8102 R-LFA Node Protection and Manageability March 2017

 This document proposes that implementations SHOULD use a default
 preference criteria for PQ-node selection 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 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 [RFC7490] functionality, the computing
 router may compute more than one PQ-node as usable remote-LFA
 alternate next hops.  Additionally, [RFC7916] specifies an LFA (and 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 alternates.  For such a
 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 PQ-nodes).  As mentioned before in Section 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.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 paths.
 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 PQ-node to the destination).  In the absence of the path
 characteristics for the second path segment, two remote-LFA alternate
 paths may be equally preferred based on the first path segment
 characteristics only, although the second path segment attributes may
 be different.

Sarkar, et al. Standards Track [Page 19] RFC 8102 R-LFA Node Protection and Manageability March 2017

3.2. The Solution

 The additional forward SPF computation proposed in Section 2.3.2
 shall also collect links, nodes, and path characteristics along the
 second path segment.  This shall enable the collection of complete
 path characteristics for a given remote-LFA alternate path to a given
 destination.  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 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, if the alternate-selection 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
 any part of [RFC7916].  This document specifies a mechanism to meet
 the requirements specified in Section 6.2.5.4 of [RFC7916].

4. IANA Considerations

 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.

Sarkar, et al. Standards Track [Page 20] RFC 8102 R-LFA Node Protection and Manageability March 2017

6. References

6.1. Normative References

 [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
            Requirement Levels", BCP 14, RFC 2119,
            DOI 10.17487/RFC2119, March 1997,
            <http://www.rfc-editor.org/info/rfc2119>.
 [RFC5286]  Atlas, A., Ed. and A. Zinin, Ed., "Basic Specification for
            IP Fast Reroute: Loop-Free Alternates", RFC 5286,
            DOI 10.17487/RFC5286, September 2008,
            <http://www.rfc-editor.org/info/rfc5286>.
 [RFC7490]  Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N.
            So, "Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)",
            RFC 7490, DOI 10.17487/RFC7490, April 2015,
            <http://www.rfc-editor.org/info/rfc7490>.

6.2. Informative References

 [RFC7916]  Litkowski, S., Ed., Decraene, B., Filsfils, C., Raza, K.,
            Horneffer, M., and P. Sarkar, "Operational Management of
            Loop-Free Alternates", RFC 7916, DOI 10.17487/RFC7916,
            July 2016, <http://www.rfc-editor.org/info/rfc7916>.

Acknowledgements

 Many thanks to Bruno Decraene for providing his useful comments.  We
 would also like to thank Uma Chunduri for reviewing this document and
 providing valuable feedback.  Also, many thanks to Harish Raghuveer
 for his review and comments on the initial draft versions of this
 document.

Sarkar, et al. Standards Track [Page 21] RFC 8102 R-LFA Node Protection and Manageability March 2017

Authors' Addresses

 Pushpasis Sarkar (editor)
 Arrcus, Inc.
 Email: pushpasis.ietf@gmail.com
 Shraddha Hegde
 Juniper Networks, Inc.
 Electra, Exora Business Park
 Bangalore, KA  560103
 India
 Email: shraddha@juniper.net
 Chris Bowers
 Juniper Networks, Inc.
 1194 N. Mathilda Ave.
 Sunnyvale, CA  94089
 United States of America
 Email: cbowers@juniper.net
 Hannes Gredler
 RtBrick, Inc.
 Email: hannes@rtbrick.com
 Stephane Litkowski
 Orange
 Email: stephane.litkowski@orange.com

Sarkar, et al. Standards Track [Page 22]

/data/webs/external/dokuwiki/data/pages/rfc/rfc8102.txt · Last modified: 2017/03/10 02:00 by 127.0.0.1

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki