< draft-ietf-rtgwg-rlfa-node-protection-09.txt   draft-ietf-rtgwg-rlfa-node-protection-10.txt >
Routing Area Working Group P. Sarkar, Ed. Routing Area Working Group P. Sarkar, Ed.
Internet-Draft Individual Contributor Internet-Draft Individual Contributor
Intended status: Standards Track S. Hegde Intended status: Standards Track S. Hegde
Expires: June 26, 2017 C. Bowers Expires: July 3, 2017 C. Bowers
Juniper Networks, Inc. Juniper Networks, Inc.
H. Gredler H. Gredler
RtBrick, Inc. RtBrick, Inc.
S. Litkowski S. Litkowski
Orange Orange
December 23, 2016 December 30, 2016
Remote-LFA Node Protection and Manageability Remote-LFA Node Protection and Manageability
draft-ietf-rtgwg-rlfa-node-protection-09 draft-ietf-rtgwg-rlfa-node-protection-10
Abstract Abstract
The loop-free alternates computed following the current Remote-LFA The loop-free alternates computed following the current Remote-LFA
specification guarantees only link-protection. The resulting Remote- specification guarantees only link-protection. The resulting Remote-
LFA nexthops (also called PQ-nodes), may not guarantee node- LFA nexthops (also called PQ-nodes), may not guarantee node-
protection for all destinations being protected by it. protection for all destinations being protected by it.
This document describes an extension to the Remote Loop-Free based IP This document describes an extension to the Remote Loop-Free based IP
fast reroute mechanisms described in [RFC7490], that describes fast reroute mechanisms described in [RFC7490], that describes
procedures for determining if a given PQ-node provides node- procedures for determining if a given PQ-node provides node-
protection for a specific destination or not. The document also protection for a specific destination or not. The document also
shows how the same procedure can be utilised for collection of shows how the same procedure can be uitilized for collection of
complete characteristics for alternate paths. Knowledge about the complete characteristics for alternate paths. Knowledge about the
characteristics of all alternate path is precursory to apply operator characteristics of all alternate path is precursory to apply operator
defined policy for eliminating paths not fitting constraints. defined policy for eliminating paths not fitting constraints.
Requirements Language Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC2119 [RFC2119]. document are to be interpreted as described in RFC2119 [RFC2119].
skipping to change at page 2, line 10 skipping to change at page 2, line 10
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on June 26, 2017. This Internet-Draft will expire on July 3, 2017.
Copyright Notice Copyright Notice
Copyright (c) 2016 IETF Trust and the persons identified as the Copyright (c) 2016 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 2, line 50 skipping to change at page 2, line 50
2.2.6.2. Node-Protecting Extended P-Space . . . . . . . . 7 2.2.6.2. Node-Protecting Extended P-Space . . . . . . . . 7
2.2.6.3. Q-Space . . . . . . . . . . . . . . . . . . . . . 8 2.2.6.3. Q-Space . . . . . . . . . . . . . . . . . . . . . 8
2.3. Computing Node-protecting R-LFA Path . . . . . . . . . . 9 2.3. Computing Node-protecting R-LFA Path . . . . . . . . . . 9
2.3.1. Computing Candidate Node-protecting PQ-Nodes for 2.3.1. Computing Candidate Node-protecting PQ-Nodes for
Primary nexthops . . . . . . . . . . . . . . . . . . 9 Primary nexthops . . . . . . . . . . . . . . . . . . 9
2.3.2. Computing node-protecting paths from PQ-nodes to 2.3.2. Computing node-protecting paths from PQ-nodes to
destinations . . . . . . . . . . . . . . . . . . . . 11 destinations . . . . . . . . . . . . . . . . . . . . 11
2.3.3. Computing Node-Protecting R-LFA Paths for 2.3.3. Computing Node-Protecting R-LFA Paths for
Destinations with ECMP primary nexthop nodes . . . . 13 Destinations with ECMP primary nexthop nodes . . . . 13
2.3.4. Limiting extra computational overhead . . . . . . . . 17 2.3.4. Limiting extra computational overhead . . . . . . . . 17
3. Manageabilty of Remote-LFA Alternate Paths . . . . . . . . . 18 3. Manageability of Remote-LFA Alternate Paths . . . . . . . . . 18
3.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 18 3.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 18
3.2. The Solution . . . . . . . . . . . . . . . . . . . . . . 18 3.2. The Solution . . . . . . . . . . . . . . . . . . . . . . 18
4. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 19 4. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 19
5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19
6. Security Considerations . . . . . . . . . . . . . . . . . . . 19 6. Security Considerations . . . . . . . . . . . . . . . . . . . 19
7. References . . . . . . . . . . . . . . . . . . . . . . . . . 19 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 19
7.1. Normative References . . . . . . . . . . . . . . . . . . 19 7.1. Normative References . . . . . . . . . . . . . . . . . . 19
7.2. Informative References . . . . . . . . . . . . . . . . . 20 7.2. Informative References . . . . . . . . . . . . . . . . . 20
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 20 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 20
skipping to change at page 5, line 50 skipping to change at page 5, line 50
Table 2: Remote-LFA backup paths via PQ-node R3 Table 2: Remote-LFA backup paths via PQ-node R3
Again a closer look at Table 2 shows that, unlike Table 1, where the 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 single PQ-node R2 provided node-protection for destinations R3 and
D2, if we choose R3 as the R-LFA nexthop, it does not provide node- D2, if we choose R3 as the R-LFA nexthop, it does not provide node-
protection for R3 and D2 anymore. If S chooses R3 as the R-LFA protection for R3 and D2 anymore. If S chooses R3 as the R-LFA
nexthop, in the event of the node-failure on primary nexthop E, on nexthop, in the event of the node-failure on primary nexthop E, on
the alternate path from S to R-LFA nexthop R3, one of parallel ECMP the alternate path from S to R-LFA nexthop R3, one of parallel ECMP
path between N and R3 also becomes unavailable. So for a Remote-LFA path between N and R3 also becomes unavailable. So for a Remote-LFA
nexthop to provide node-protection for a given destination, it is nexthop to provide node-protection for a given destination, it is
also mandatory that, the shortest path from S to the chosen PQ-node also mandatory that, the shortest paths from S to the chosen PQ-node
MUST NOT traverse the primary nexthop node. MUST NOT traverse the primary nexthop node.
2.2. Additional Definitions 2.2. Additional Definitions
This document adds and enhances the following definitions extending This document adds and enhances the following definitions extending
the ones mentioned in Remote-LFA [RFC7490] specification. the ones mentioned in Remote-LFA [RFC7490] specification.
2.2.1. Link-Protecting Extended P-Space 2.2.1. Link-Protecting Extended P-Space
The Remote-LFA [RFC7490] specification already defines this. The The Remote-LFA [RFC7490] specification already defines this. The
link-protecting extended P-space for a link S-E being protected is 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 the set of routers that are reachable from one or more direct
neighbors of S, except primary node E, without traversing the S-E neighbors of S, except primary node E, without traversing the S-E
link on any of the shortest path from the direct neighbor to the 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 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) least one ECMP path from the direct neighbor traversing the link(S-E)
being protected. being protected.
For a cost-based definition for Link-protecting Extended P-Space For a cost-based definition for Link-protecting Extended P-Space
refer to Section 2.2.6.1. refer to Section 2.2.6.1.
2.2.2. Node-Protecting Extended P-Space 2.2.2. Node-Protecting Extended P-Space
The node-protecting extended P-space for a primary nexthop node E The node-protecting extended P-space for a primary nexthop node E
skipping to change at page 6, line 39 skipping to change at page 6, line 39
the node E. This MUST exclude any direct neighbors for which there the node E. This MUST exclude any direct neighbors for which there
is at least one ECMP path from the direct neighbor traversing the is at least one ECMP path from the direct neighbor traversing the
node E being protected. node E being protected.
For a cost-based definition for Node-protecting Extended P-Space For a cost-based definition for Node-protecting Extended P-Space
refer to Section 2.2.6.2. refer to Section 2.2.6.2.
2.2.3. Q-Space 2.2.3. Q-Space
The Remote-LFA [RFC7490] draft already defines this. The Q-space for The Remote-LFA [RFC7490] draft already defines this. The Q-space for
a link S-E being protected is the set of routers that can reach a link S-E being protected is the set of nodes that can reach primary
primary node E, without traversing the S-E link on any of the node E, without traversing the S-E link on any of the shortest paths
shortest path from the node Y to primary nexthop E. This MUST from the node itself to primary nexthop E. This MUST exclude any
exclude any destination for which there is at least one ECMP path node for which there is at least one ECMP path from the node to the
from the node Y to the primary nexthop E traversing the link(S-E) primary nexthop E traversing the link(S-E) being protected.
being protected.
For a cost-based definition for Q-Space refer to Section 2.2.6.3. For a cost-based definition for Q-Space refer to Section 2.2.6.3.
2.2.4. Link-Protecting PQ Space 2.2.4. Link-Protecting PQ Space
A node Y is in link-protecting PQ space w.r.t to the link (S-E) being A node Y is in link-protecting PQ space w.r.t the link (S-E) being
protected, if and only if, Y is present in both link-protecting protected, if and only if, Y is present in both link-protecting
extended P-space and the Q-space for the link being protected. extended P-space and the Q-space for the link being protected.
2.2.5. Candidate Node-Protecting PQ Space 2.2.5. Candidate Node-Protecting PQ Space
A node Y is in candidate node-protecting PQ space w.r.t to the node A node Y is in candidate node-protecting PQ space w.r.t the node (E)
(E) being protected, if and only if, Y is present in both node- being protected, if and only if, Y is present in both node-protecting
protecting extended P-space and the Q-space for the link being extended P-space and the Q-space for the link being protected.
protected.
Please note, that a node Y being in candidate node-protecting PQ- Please note, that a node Y being in candidate node-protecting PQ-
space, does not guarantee that the R-LFA alternate path via the same, 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 in entirety, is unaffected in the event of a node failure of primary
nexthop node E. It only guarantees that the path segment from S to nexthop 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 PQ-node Y is unaffected by the same failure event. The PQ-nodes in
the candidate node-protecting PQ space may provide node protection the candidate node-protecting PQ space may provide node protection
for only a subset of destinations that are reachable through the for only a subset of destinations that are reachable through the
corresponding primary link. corresponding primary link.
2.2.6. Cost-Based Definitions 2.2.6. Cost-Based Definitions
This section provides cost-based definitions for some of the terms This section provides cost-based definitions for some of the terms
introduced in Section 2.2 of this document. introduced in Section 2.2 of this document.
2.2.6.1. Link-Protecting Extended P-Space 2.2.6.1. Link-Protecting Extended P-Space
Please refer to Section 2.2.1 for a formal definition for Link- Please refer to Section 2.2.1 for a formal definition for Link-
protecting Extended P-Space. protecting Extended P-Space.
A node Y is in link-protecting extended P-space w.r.t to the link A node Y is in link-protecting extended P-space w.r.t the link (S-E)
(S-E) being protected, if and only if, there exists at least one being protected, if and only if, there exists at least one direct
direct neighbor of S, Ni, other than primary nexthop E, that neighbor of S, Ni, other than primary nexthop E, that satisfies the
satisfies the following condition. following condition.
D_opt(Ni,Y) < D_opt(Ni,S) + D_opt(S,Y) D_opt(Ni,Y) < D_opt(Ni,S) + D_opt(S,Y)
Where, Where,
D_opt(A,B) : Distance on most optimum path from A to B. D_opt(A,B) : Distance on most optimum path from A to B.
Ni : A direct neighbor of S other than primary Ni : A direct neighbor of S other than primary
nexthop E. nexthop E.
Y : The node being evaluated for link-protecting Y : The node being evaluated for link-protecting
extended P-Space. extended P-Space.
Figure 3: Link-Protecting Ext-P-Space Condition Figure 3: Link-Protecting Ext-P-Space Condition
2.2.6.2. Node-Protecting Extended P-Space 2.2.6.2. Node-Protecting Extended P-Space
Please refer to Section 2.2.2 for a formal definition for Node- Please refer to Section 2.2.2 for a formal definition for Node-
protecting Extended P-Space. protecting Extended P-Space.
A node Y is in node-protecting extended P-space w.r.t to the node E A node Y is in node-protecting extended P-space w.r.t the node E
being protected, if and only if, there exists at least one direct being protected, if and only if, there exists at least one direct
neighbor of S, Ni, other than primary nexthop E, that satisfies the neighbor of S, Ni, other than primary nexthop E, that satisfies the
following condition. following condition.
D_opt(Ni,Y) < D_opt(Ni,E) + D_opt(E,Y) D_opt(Ni,Y) < D_opt(Ni,E) + D_opt(E,Y)
Where, Where,
D_opt(A,B) : Distance on most optimum path from A to B. D_opt(A,B) : Distance on most optimum path from A to B.
E : The primary nexthop on shortest path from S E : The primary nexthop on shortest path from S
to destination. to destination.
skipping to change at page 8, line 34 skipping to change at page 8, line 34
only guarantees that the R-LFA alternate path segment from S via 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 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 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 from node Y to the destination is also unaffected by the same failure
event. event.
2.2.6.3. Q-Space 2.2.6.3. Q-Space
Please refer to Section 2.2.3 for a formal definition for Q-Space. Please refer to Section 2.2.3 for a formal definition for Q-Space.
A node Y is in Q-space w.r.t to the link (S-E) being protected, if A node Y is in Q-space w.r.t the link (S-E) being protected, if and
and only if, the following condition is satisfied. only if, the following condition is satisfied.
D_opt(Y,E) < D_opt(S,E) + D_opt(Y,S) D_opt(Y,E) < D_opt(S,E) + D_opt(Y,S)
Where, Where,
D_opt(A,B) : Distance on most optimum path from A to B. D_opt(A,B) : Distance on most optimum path from A to B.
E : The primary nexthop on shortest path from S E : The primary nexthop on shortest path from S
to destination. to destination.
Y : The node being evaluated for Q-Space. Y : The node being evaluated for Q-Space.
Figure 5: Q-Space Condition Figure 5: Q-Space Condition
skipping to change at page 9, line 18 skipping to change at page 9, line 18
destination is comprised of two path segments as follows. destination is comprised of two path segments as follows.
1. Path segment from the computing router to the PQ-node (Remote-LFA 1. Path segment from the computing router to the PQ-node (Remote-LFA
alternate nexthop), and alternate nexthop), and
2. Path segment from the PQ-node to the destination being protected. 2. Path segment from the PQ-node to the destination being protected.
So to ensure a R-LFA alternate path for a given destination provides So to ensure a R-LFA alternate path for a given destination provides
node-protection we need to ensure that none of the above path node-protection we need to ensure that none of the above path
segments are affected in the event of failure of the primary nexthop segments are affected in the event of failure of the primary nexthop
node. Sections Section 2.3.1 and Section 2.3.2 shows how this can be node. Sections Section 2.3.1 and Section 2.3.2 show how this can be
ensured. ensured.
2.3.1. Computing Candidate Node-protecting PQ-Nodes for Primary 2.3.1. Computing Candidate Node-protecting PQ-Nodes for Primary
nexthops nexthops
To choose a node-protecting R-LFA nexthop for a destination R3, To choose a node-protecting R-LFA nexthop for a destination R3,
router S needs to consider a PQ-node from the candidate node- router S needs to consider a PQ-node from the candidate node-
protecting PQ-space for the primary nexthop E on shortest path from S protecting PQ-space for the primary nexthop E on shortest path from S
to R3. As mentioned in Section 2.2.2, to consider a PQ-node as to R3. As mentioned in Section 2.2.2, to consider a PQ-node as
candidate node-protecting PQ-node, there must be at least one direct candidate node-protecting PQ-node, there must be at least one direct
skipping to change at page 10, line 33 skipping to change at page 10, line 33
Some SPF implementations may also produce a list of links and nodes 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 traversed on the shortest path(s) from a given root to others. In
such implementations, router S may have executed a forward SPF with 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 each of its direct neighbors as the SPF root, executed as part of the
standard LFA [RFC5286] computations. So S may re-use the list of standard LFA [RFC5286] computations. So S may re-use the list of
links and nodes collected from the same SPF computations, to decide links and nodes collected from the same SPF computations, to decide
whether a node Y is a candidate node-protecting PQ-node or not. A whether a node Y is a candidate node-protecting PQ-node or not. A
node Y shall be considered as a node-protecting PQ-node, if and only 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 if, there is at least one direct neighbor of S, other than the
primary nexthop E, for which, the primary nexthop node E does not primary nexthop E, for which, the primary nexthop node E does not
exist on the list of nodes traversed on any of the shortest path(s) 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 from the direct neighbor to the PQ-node. Table 4 below is an
illustration of the mechanism with the topology in Figure 2. illustration of the mechanism with the topology in Figure 2.
+-----------+-------------------+-----------------+-----------------+ +-----------+-------------------+-----------------+-----------------+
| Candidate | Repair Tunnel | Link-Protection | Node-Protection | | Candidate | Repair Tunnel | Link-Protection | Node-Protection |
| PQ-node | Path(Repairing | | | | PQ-node | Path(Repairing | | |
| | router to PQ- | | | | | router to PQ- | | |
| | node) | | | | | node) | | |
+-----------+-------------------+-----------------+-----------------+ +-----------+-------------------+-----------------+-----------------+
| R2 | S->N->R1->R2 | Yes | Yes | | R2 | S->N->R1->R2 | Yes | Yes |
skipping to change at page 11, line 18 skipping to change at page 11, line 18
nodes for a given directly attached primary link, it shall follow the nodes for a given directly attached primary link, it shall follow the
procedure as proposed in this section, to choose one or more node- procedure as proposed in this section, to choose one or more node-
protecting R-LFA paths, for destinations reachable through the same protecting R-LFA paths, for destinations reachable through the same
primary link in the primary SPF graph. primary link in the primary SPF graph.
To find a node-protecting R-LFA path for a given destination, the 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 computing router needs to pick a subset of PQ-nodes from the
candidate node-protecting PQ-space for the corresponding primary candidate node-protecting PQ-space for the corresponding primary
nexthop, such that all the path(s) from the PQ-node(s) to the given nexthop, 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 destination remain unaffected in the event of a node failure of the
primary nexthop node. To determine wether a given PQ-node belongs to primary nexthop node. To determine whether a given PQ-node belongs
such a subset of PQ-nodes, the computing router MUST ensure that none to such a subset of PQ-nodes, the computing router MUST ensure that
of the primary nexthop node are found on any of the shortest paths none of the primary nexthop node are found on any of the shortest
from the PQ-node to the given destination. paths from the PQ-node to the given destination.
This document proposes an additional forward SPF computation for each This document proposes an additional forward SPF computation for each
of the PQ-nodes, to discover all shortest paths from the PQ-nodes to of the PQ-nodes, to discover all shortest paths from the PQ-nodes to
the destination. This will help determine, if a given primary the destination. This will help determine, if a given primary
nexthop node is on the shortest paths from the PQ-node to the given nexthop node is on the shortest paths from the PQ-node to the given
destination or not. To determine if a given candidate node- destination or not. To determine if a given candidate node-
protecting PQ-node provides node-protecting alternate for a given protecting PQ-node provides node-protecting alternate for a given
destination, or not, all the shortest paths from the PQ-node to the destination, or not, all the shortest paths from the PQ-node to the
given destination has to be inspected, to check if the primary given destination has to be inspected, to check if the primary
nexthop node is found on any of these shortest paths. To compute all nexthop node is found on any of these shortest paths. To compute all
skipping to change at page 13, line 43 skipping to change at page 13, line 43
2.3.3. Computing Node-Protecting R-LFA Paths for Destinations with ECMP 2.3.3. Computing Node-Protecting R-LFA Paths for Destinations with ECMP
primary nexthop nodes primary nexthop nodes
In certain scenarios, when one or more destinations maybe reachable In certain scenarios, when one or more destinations maybe reachable
via multiple ECMP (equal-cost-multi-path) nexthop nodes, and only via multiple ECMP (equal-cost-multi-path) nexthop nodes, and only
link-protection is required, there is no need to compute any link-protection is required, there is no need to compute any
alternate paths for such destinations. In the event of failure of alternate paths for such destinations. In the event of failure of
one of the nexthop links, the remaining primary nexthops shall always one of the nexthop links, the remaining primary nexthops shall always
provide link-protection. However, if node-protection is required, provide link-protection. However, if node-protection is required,
the rest of the primary nexthops may not gaurantee node-protection. the rest of the primary nexthops may not guarantee node-protection.
Figure 7 below shows one such example topology. Figure 7 below shows one such example topology.
D1 D1
2 / 2 /
S---x---E1 S---x---E1
/ \ / \ / \ / \
/ x / \ / x / \
/ \ / \ / \ / \
N-------E2 R3--D2 N-------E2 R3--D2
\ 2 / \ 2 /
\ / \ /
\ / \ /
R1-------R2 R1-------R2
2 2
Primary Nexthops: Primary Nexthops:
Destination D1 = [{ S-E1, E1}, {S-E2, E2}] Destination D1 = [{ S-E1, E1}, {S-E2, E2}]
Destination D2 = [{ S-E1, E1}, {S-E2, E2}] Destination D2 = [{ S-E1, E1}, {S-E2, E2}]
Figure 7: Toplogy with multiple ECMP primary nexthops Figure 7: Topology with multiple ECMP primary nexthops
In the above example topology, costs of all links are 1, except the In the above example topology, costs of all links are 1, except the
following links: following links:
Link: S-E1, Cost: 2 Link: S-E1, Cost: 2
Link: N-E2: Cost: 2 Link: N-E2: Cost: 2
Link: R1-R2: Cost: 2 Link: R1-R2: Cost: 2
In the above topology, on computing router S, destinations D1 and D2 In the above topology, on computing router S, destinations D1 and D2
are reachable via two ECMP nexthop nodes E1 and E2. However the are reachable via two ECMP nexthop nodes E1 and E2. However the
primary paths via nexthop node E2 also traverses via the nexthop node primary paths via nexthop node E2 also traverses via the nexthop node
E1. So in the event of node failure of nexthop node E1, both primary E1. So in the event of node failure of nexthop node E1, both primary
paths (via E1 and E2) becomes unavailable. Hence if node-protection paths (via E1 and E2) becomes unavailable. Hence if node-protection
is desired for destinations D1 and D2, alternate paths that does not is desired for destinations D1 and D2, alternate paths that does not
traverse any of the primary nexthop nodes E1 and E2, need to be traverse any of the primary nexthop nodes E1 and E2, need to be
computed. In the above topology the only alternate neighbor N does computed. In the above topology the only alternate neighbor N does
not provide such a LFA alternate path. Hence one (or more) R-LFA not provide such a LFA alternate path. Hence one (or more) R-LFA
node-proecting alternate paths for destinations D1 and D2, needs to node-protecting alternate paths for destinations D1 and D2, needs to
be computed. be computed.
In the above topology, following are the link-protecting PQ-nodes. In the above topology, following are the link-protecting PQ-nodes.
Primary Nexthop: E1, Link-Protecting PQ-Node: { R2 } Primary Nexthop: E1, Link-Protecting PQ-Node: { R2 }
Primary Nexthop: E2, Link-Protecting PQ-Node: { R2 } Primary Nexthop: E2, Link-Protecting PQ-Node: { R2 }
To find one (or more) node-protecting R-LFA paths for destinations D1 To find one (or more) node-protecting R-LFA paths for destinations D1
and D2, one (or more) node-protecting PQ-node(s) needs to be and D2, one (or more) node-protecting PQ-node(s) needs to be
skipping to change at page 15, line 35 skipping to change at page 15, line 35
Table 7: Computing Node-protected PQ-nodes for nexthop E1 and E2 Table 7: Computing Node-protected PQ-nodes for nexthop E1 and E2
In SPF implementations that also produce a list of links and nodes 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 traversed on the shortest path(s) from a given root to others, the
tunnel-repair paths from the computing router to candidate PQ-node tunnel-repair paths from the computing router to candidate PQ-node
can be examined to ensure that none of the primary nexthop nodes is can be examined to ensure that none of the primary nexthop nodes is
traversed. PQ-nodes that provide one (or more) Tunnel-repair traversed. PQ-nodes that provide one (or more) Tunnel-repair
paths(s) that does not traverse any of the primary nexthop nodes, are paths(s) that does not traverse any of the primary nexthop nodes, are
to be considered as node-protecting PQ-nodes. Table 8 below shows to be considered as node-protecting PQ-nodes. Table 8 below shows
the possible tunnel-repair paths tp PQ-node R2. the possible tunnel-repair paths to PQ-node R2.
+--------------+------------+-------------------+-------------------+ +--------------+------------+-------------------+-------------------+
| Primary-NH | PQ-Node | Tunnel-Repair | Exclude All | | Primary-NH | PQ-Node | Tunnel-Repair | Exclude All |
| (E) | (Y) | Paths | Primary-NH | | (E) | (Y) | Paths | Primary-NH |
+--------------+------------+-------------------+-------------------+ +--------------+------------+-------------------+-------------------+
| E1, E2 | R2 | S==>N==>R1==>R2 | Yes | | E1, E2 | R2 | S==>N==>R1==>R2 | Yes |
+--------------+------------+-------------------+-------------------+ +--------------+------------+-------------------+-------------------+
Table 8: Tunnel-Repair paths to PQ-node R2 Table 8: Tunnel-Repair paths to PQ-node R2
skipping to change at page 16, line 37 skipping to change at page 16, line 37
+----------+----------+-------+--------+--------+--------+----------+ +----------+----------+-------+--------+--------+--------+----------+
Table 9: Finding node-protecting R-LFA path for destinations D1 and Table 9: Finding node-protecting R-LFA path for destinations D1 and
D2 D2
In SPF implementations that also produce a list of links and nodes 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 traversed on the shortest path(s) from a given root to others, the
R-LFA paths via node-protecting PQ-node to final destination can be R-LFA paths via node-protecting PQ-node to final destination can be
examined to ensure that none of the primary nexthop nodes is examined to ensure that none of the primary nexthop nodes is
traversed. R-LFA path(s) that does not traverse any of the primary traversed. R-LFA path(s) that does not traverse any of the primary
nexthop nodes, gaurantees node-protection in the event of failure of nexthop nodes, guarantees node-protection in the event of failure of
any of the primary nexthop nodes. Table 10 below shows the possible any of the primary nexthop nodes. Table 10 below shows the possible
R-LFA-paths for destinations D1 and D2 via the node-protecting PQ- R-LFA-paths for destinations D1 and D2 via the node-protecting PQ-
node R2. node R2.
+-------------+------------+---------+-----------------+------------+ +-------------+------------+---------+-----------------+------------+
| Destination | Primary-NH | PQ-Node | R-LFA Paths | Exclude | | Destination | Primary-NH | PQ-Node | R-LFA Paths | Exclude |
| (D) | (E) | (Y) | | All | | (D) | (E) | (Y) | | All |
| | | | | Primary-NH | | | | | | Primary-NH |
+-------------+------------+---------+-----------------+------------+ +-------------+------------+---------+-----------------+------------+
| D1 | E1, E2 | R2 | S==>N==>R1==>R2 | No | | D1 | E1, E2 | R2 | S==>N==>R1==>R2 | No |
| | | | -->R3-->E1-->D1 | | | | | | -->R3-->E1-->D1 | |
| | | | | | | | | | | |
| D2 | E1, E2 | R2 | S==>N==>R1==>R2 | Yes | | D2 | E1, E2 | R2 | S==>N==>R1==>R2 | Yes |
| | | | -->R3-->D2 | | | | | | -->R3-->D2 | |
+-------------+------------+---------+-----------------+------------+ +-------------+------------+---------+-----------------+------------+
Table 10: R-LFA paths for destinations D1 and D2 Table 10: R-LFA paths for destinations D1 and D2
From Table 9 and Table 10, in the above example above, the R-LFA path From Table 9 and Table 10, in the example above, the R-LFA path from
from R2 does not meet the node-protecting inequality for destination R2 does not meet the node-protecting inequality for destination D1,
D1, while it does meet the same inequality for destination D2. And while it does meet the same inequality for destination D2. And so,
so, while R2 provides node-protecting R-LFA alternate for D2, it while R2 provides node-protecting R-LFA alternate for D2, it fails to
fails to provide node-protection for destination D1. Finally, while provide node-protection for destination D1. Finally, while it is
it is possible to get a node-protecting R-LFA path for D2, no such possible to get a node-protecting R-LFA path for D2, no such node-
node-protecting R-LFA path can be found for D1. protecting R-LFA path can be found for D1.
2.3.4. Limiting extra computational overhead 2.3.4. Limiting extra computational overhead
In addition to the extra reverse SPF computations suggested by the In addition to the extra reverse SPF computations suggested by the
Remote-LFA [RFC7490] draft (one reverse SPF for each of the directly Remote-LFA [RFC7490] draft (one reverse SPF for each of the directly
connected neighbors), this document proposes a forward SPF connected neighbors), this document proposes a forward SPF
computations for each PQ-node discovered in the network. Since the computations for each PQ-node discovered in the network. Since the
average number of PQ-nodes found in any network is considerably more average number of PQ-nodes found in any network is considerably more
than the number of direct neighbors of the computing router, the than the number of direct neighbors of the computing router, the
proposal of running one forward SPF per PQ-node may add considerably proposal of running one forward SPF per PQ-node may add considerably
to the overall SPF computation time. to the overall SPF computation time.
To limit the computational overhead of the approach proposed, this To limit the computational overhead of the approach proposed, this
document proposes that implementations MUST choose a subset from the document proposes that implementations MUST choose a subset from the
entire set of PQ-nodes computed in the network, with a finite limit 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 on the number of PQ-nodes in the subset. Implementations MUST choose
a default value for this limit and may provide user with a a default value for this limit and may provide user with a
configuration knob to override the default limit. Implementations configuration knob to override the default limit. Implementations
MUST also evaluate some default preference criteria while considering MUST also evaluate some default preference criteria while considering
a PQ-node in this subset. Finally, implementations MAY also allow a PQ-node in this subset. Finally, implementations MAY also allow
user to override the default preference criteria, by providing a the user to override the default preference criteria, by providing a
policy configuration for the same. policy configuration for the same.
This document proposes that implementations SHOULD use a default This document proposes that implementations SHOULD use a default
preference criteria for PQ-node selection which will put a score on preference criteria for PQ-node selection which will put a score on
each PQ-node, proportional to the number of primary interfaces for each PQ-node, proportional to the number of primary interfaces for
which it provides coverage, its distance from the computing router, 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 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 more primary interfaces SHOULD be preferred over PQ-nodes that
cover fewer primary interfaces. When two or more PQ-nodes cover the cover fewer primary interfaces. When two or more PQ-nodes cover the
same number of primary interfaces, PQ-nodes which are closer (based same number of primary interfaces, PQ-nodes which are closer (based
on metric) to the computing router SHOULD be preferred over PQ-nodes 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 farther away from it. For PQ-nodes that cover the same number of
primary interfaces and are the same distance from the the computing primary interfaces and are the same distance from the computing
router, the PQ-node with smaller router-id (or system-id in case of router, the PQ-node with smaller router-id (or system-id in case of
IS-IS) SHOULD be preferred. IS-IS) SHOULD be preferred.
Once a subset of PQ-nodes is found, computing router shall run a Once a subset of PQ-nodes is found, computing router shall run a
forward SPF on each of the PQ-nodes in the subset to continue with forward SPF on each of the PQ-nodes in the subset to continue with
procedures proposed in section Section 2.3.2. procedures proposed in Section 2.3.2.
3. Manageabilty of Remote-LFA Alternate Paths 3. Manageability of Remote-LFA Alternate Paths
3.1. The Problem 3.1. The Problem
With the regular Remote-LFA [RFC7490] functionality the computing With the regular Remote-LFA [RFC7490] functionality the computing
router may compute more than one PQ-node as usable Remote-LFA router may compute more than one PQ-node as usable Remote-LFA
alternate nexthops. Additionally an alternate selection policy may alternate nexthops. Additionally an alternate selection policy may
be configured to enable the network operator to choose one of them as be configured to enable the network operator to choose one of them as
the most appropriate Remote-LFA alternate. For such policy-based the most appropriate Remote-LFA alternate. For such policy-based
alternate selection to run, all the relevant path characteristics for alternate selection to run, all the relevant path characteristics for
each the alternate paths (one through each of the PQ-nodes), needs to each the alternate paths (one through each of the PQ-nodes), needs to
be collected. As mentioned before in section Section 2.3 the R-LFA be collected. As mentioned before in Section 2.3 the R-LFA alternate
alternate path through a given PQ-node to a given destination is path through a given PQ-node to a given destination is comprised of
comprised of two path segments. two path segments.
The first path segment (i.e. from the computing router to the PQ- 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 node) can be calculated from the regular forward SPF done as part of
standard and remote LFA computations. However without the mechanism standard and remote LFA computations. However without the mechanism
proposed in section Section 2.3.2 of this document, there is no way proposed in section Section 2.3.2 of this document, there is no way
to determine the path characteristics for the second path segment to determine the path characteristics for the second path segment
(i.e from the PQ-node to the destination). In the absence of the (i.e. from the PQ-node to the destination). In the absence of the
path characteristics for the second path segment, two Remote-LFA path characteristics for the second path segment, two Remote-LFA
alternate path may be equally preferred based on the first path alternate paths may be equally preferred based on the first path
segments characteristics only, although the second path segment segments characteristics only, although the second path segment
attributes may be different. attributes may be different.
3.2. The Solution 3.2. The Solution
The additional forward SPF computation proposed in Section 2.3.2 The additional forward SPF computation proposed in Section 2.3.2
document shall also collect links, nodes and path characteristics document shall also collect links, nodes and path characteristics
along the second path segment. This shall enable collection of along the second path segment. This shall enable collection of
complete path characteristics for a given Remote-LFA alternate path complete path characteristics for a given Remote-LFA alternate path
to a given destination. The complete alternate path characteristics to a given destination. The complete alternate path characteristics
shall then facilitate more accurate alternate path selection while shall then facilitate more accurate alternate path selection while
running the alternate selection policy. running the alternate selection policy.
As already specified in Section 2.3.4 to limit the computational As already specified in Section 2.3.4 to limit the computational
overhead of the approach proposed, forward SPF computations MUST be overhead of the proposed approach, forward SPF computations MUST be
run on a selected subset from the entire set of PQ-nodes computed in 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 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 subset. The detailed suggestion on how to select this subset is
specified in the same section. While this limits the number of specified in the same section. While this limits the number of
possible alternate paths provided to the alternate-selection policy, possible alternate paths provided to the alternate-selection policy,
this is needed keep the computational complexity within affordable this is needed to keep the computational complexity within affordable
limits. However if the alternate-selection policy is very limits. However if the alternate-selection policy is very
restrictive this may leave few destinations in the entire toplogy restrictive this may leave few destinations in the entire topology
without protection. Yet this limitation provides a necessary without protection. Yet this limitation provides a necessary
tradeoff between extensive coverage and immense computational tradeoff between extensive coverage and immense computational
overhead. overhead.
4. Acknowledgements 4. Acknowledgements
Many thanks to Bruno Decraene for providing his useful comments. We Many thanks to Bruno Decraene for providing his useful comments. We
would also like to thank Uma Chunduri for reviewing this document and would also like to thank Uma Chunduri for reviewing this document and
providing valuable feedback. Also, many thanks to Harish Raghuveer providing valuable feedback. Also, many thanks to Harish Raghuveer
for his review and comments on the initial versions of this document. for his review and comments on the initial versions of this document.
 End of changes. 33 change blocks. 
56 lines changed or deleted 54 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/