draft-ietf-rtgwg-rlfa-node-protection-08.txt   draft-ietf-rtgwg-rlfa-node-protection-09.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: May 21, 2017 C. Bowers Expires: June 26, 2017 C. Bowers
Juniper Networks, Inc. Juniper Networks, Inc.
H. Gredler H. Gredler
RtBrick, Inc. RtBrick, Inc.
S. Litkowski S. Litkowski
Orange Orange
November 17, 2016 December 23, 2016
Remote-LFA Node Protection and Manageability Remote-LFA Node Protection and Manageability
draft-ietf-rtgwg-rlfa-node-protection-08 draft-ietf-rtgwg-rlfa-node-protection-09
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
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 May 21, 2017. This Internet-Draft will expire on June 26, 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 47 skipping to change at page 2, line 47
2.2.5. Candidate Node-Protecting PQ Space . . . . . . . . . 7 2.2.5. Candidate Node-Protecting PQ Space . . . . . . . . . 7
2.2.6. Cost-Based Definitions . . . . . . . . . . . . . . . 7 2.2.6. Cost-Based Definitions . . . . . . . . . . . . . . . 7
2.2.6.1. Link-Protecting Extended P-Space . . . . . . . . 7 2.2.6.1. Link-Protecting Extended P-Space . . . . . . . . 7
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. Limiting extra computational overhead . . . . . . . . 13 2.3.3. Computing Node-Protecting R-LFA Paths for
3. Manageabilty of Remote-LFA Alternate Paths . . . . . . . . . 14 Destinations with ECMP primary nexthop nodes . . . . 13
3.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 14 2.3.4. Limiting extra computational overhead . . . . . . . . 17
3.2. The Solution . . . . . . . . . . . . . . . . . . . . . . 15 3. Manageabilty of Remote-LFA Alternate Paths . . . . . . . . . 18
4. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 15 3.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 18
5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 3.2. The Solution . . . . . . . . . . . . . . . . . . . . . . 18
6. Security Considerations . . . . . . . . . . . . . . . . . . . 15
7. References . . . . . . . . . . . . . . . . . . . . . . . . . 15 4. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 19
7.1. Normative References . . . . . . . . . . . . . . . . . . 15 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19
7.2. Informative References . . . . . . . . . . . . . . . . . 16 6. Security Considerations . . . . . . . . . . . . . . . . . . . 19
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 16 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 19
7.1. Normative References . . . . . . . . . . . . . . . . . . 19
7.2. Informative References . . . . . . . . . . . . . . . . . 20
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 20
1. Introduction 1. Introduction
The Remote-LFA [RFC7490] specification provides loop-free alternates The Remote-LFA [RFC7490] specification provides loop-free alternates
that guarantee only link-protection. The resulting Remote-LFA that guarantee only link-protection. The resulting Remote-LFA
alternate nexthops (also referred to as the PQ-nodes) may not provide alternate nexthops (also referred to as the PQ-nodes) may not provide
node-protection for all destinations covered by the same, in case of node-protection for all destinations covered by the same, in case of
failure of the primary nexthop node. Neither does the specification failure of the primary nexthop node. Neither does the specification
provide a means to determine the same. provide a means to determine the same.
skipping to change at page 13, line 34 skipping to change at page 13, line 34
The procedure described in this document helps no more than to The procedure described in this document helps no more than to
determine whether a given Remote-LFA alternate provides node- determine whether a given Remote-LFA alternate provides node-
protection for a given destination or not. It does not find out any protection for a given destination or not. It does not find out any
new Remote-LFA alternate nexthops, outside the ones already computed new Remote-LFA alternate nexthops, outside the ones already computed
by standard Remote-LFA procedure. However, in case of availability by standard Remote-LFA procedure. However, in case of availability
of more than one PQ-node (Remote-LFA alternates) for a destination, of more than one PQ-node (Remote-LFA alternates) for a destination,
and node-protection is required for the given primary nexthop, this and node-protection is required for the given primary nexthop, this
procedure will eliminate the PQ-nodes that do not provide node- procedure will eliminate the PQ-nodes that do not provide node-
protection and choose only the ones that does. protection and choose only the ones that does.
2.3.3. Limiting extra computational overhead 2.3.3. Computing Node-Protecting R-LFA Paths for Destinations with ECMP
primary nexthop nodes
In certain scenarios, when one or more destinations maybe reachable
via multiple ECMP (equal-cost-multi-path) nexthop 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 nexthop links, the remaining primary nexthops shall always
provide link-protection. However, if node-protection is required,
the rest of the primary nexthops may not gaurantee node-protection.
Figure 7 below shows one such example topology.
D1
2 /
S---x---E1
/ \ / \
/ x / \
/ \ / \
N-------E2 R3--D2
\ 2 /
\ /
\ /
R1-------R2
2
Primary Nexthops:
Destination D1 = [{ S-E1, E1}, {S-E2, E2}]
Destination D2 = [{ S-E1, E1}, {S-E2, E2}]
Figure 7: Toplogy with multiple ECMP primary nexthops
In the above example topology, costs of all links are 1, except the
following links:
Link: S-E1, Cost: 2
Link: N-E2: Cost: 2
Link: R1-R2: Cost: 2
In the above topology, on computing router S, destinations D1 and D2
are reachable via two ECMP nexthop nodes E1 and E2. However the
primary paths via nexthop node E2 also traverses via the nexthop node
E1. So in the event of node failure of nexthop node E1, both primary
paths (via E1 and E2) becomes unavailable. Hence if node-protection
is desired for destinations D1 and D2, alternate paths that does not
traverse any of the primary nexthop nodes E1 and E2, need to be
computed. In the above topology the only alternate neighbor N does
not provide such a LFA alternate path. Hence one (or more) R-LFA
node-proecting alternate paths for destinations D1 and D2, needs to
be computed.
In the above topology, following are the link-protecting PQ-nodes.
Primary Nexthop: E1, 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
and D2, one (or more) node-protecting PQ-node(s) needs to be
determined first. Inequalities specified in Section 2.2.6.2 and
Section 2.2.6.3 can be evaluated to compute the node-protecting PQ-
space for each of the nexthop nodes E1 and E2, as shown in Table 7
below. To select a PQ-node as node-protecting PQ-node for a
destination with multiple primary nexthop nodes, the PQ-node MUST
satisfy the inequality for all primary nexthop nodes. Any PQ-node
which is NOT node-protecting PQ-node for all the primary nexthop
nodes, MUST NOT be chosen as the node-protecting PQ-node for
destination.
+--------+----------+-------+--------+--------+---------+-----------+
| Primar | Candidat | Direc | D_opt | D_opt | D_opt | Condition |
| y Next | e PQ- | t Nbr | (Ni,Y) | (Ni,E) | (E,Y) | Met |
| hop | node (Y) | (Ni) | | | | |
| (E) | | | | | | |
+--------+----------+-------+--------+--------+---------+-----------+
| E1 | R2 | N | 3 | 3 | 2 | Yes |
| | | | (N,R2) | (N,E1) | (E1,R2) | |
| E2 | R2 | N | 3 | 2 | 3 | Yes |
| | | | (N,R2) | (N,E2) | (E2,R2) | |
+--------+----------+-------+--------+--------+---------+-----------+
Table 7: Computing Node-protected PQ-nodes for nexthop E1 and E2
In SPF implementations that also produce a list of links and nodes
traversed on the shortest path(s) from a given root to others, the
tunnel-repair paths from the computing router to candidate PQ-node
can be examined to ensure that none of the primary nexthop nodes is
traversed. PQ-nodes that provide one (or more) Tunnel-repair
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
the possible tunnel-repair paths tp 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 Table 7 and Table 8, in the above example, R2 being node-
protecting PQ-node for both primary nexthops E1 and E2, should be
chosen as the node-protecting PQ-node for destinations D1 and D2 that
are both reachable via primary nexthop nodes E1 and E2.
Next, to find a node-protecting R-LFA path from node-protecting PQ-
node to destinations D1 and D2, inequalities specified in Figure 6
should be evaluated, to ensure if R2 provides a node-protecting R-LFA
path for each of these destinations, as shown below in Table 9. For
a R-LFA path to qualify as node-protecting R-LFA path for a
destination with multiple ECMP primary nexthop nodes, the R-LFA path
from the PQ-node to the destination MUST satisfy the inequality for
all primary nexthop nodes.
+----------+----------+-------+--------+--------+--------+----------+
| Destinat | Primary- | PQ- | D_opt | D_opt | D_opt | Conditio |
| ion (D) | NH (E) | Node | (Y, D) | (Y, E) | (E, D) | n Met |
| | | (Y) | | | | |
+----------+----------+-------+--------+--------+--------+----------+
| D1 | E1 | R2 | 3 (R2, | 2 (R2, | 1 (E1, | No |
| | | | D1) | E1) | D1) | |
| D1 | E2 | R2 | 3 (R2, | 3 (R2, | 2 (E2, | Yes |
| | | | D1) | E2) | D1) | |
| D2 | E1 | R2 | 2 (R2, | 2 (R2, | 2 (E1, | Yes |
| | | | D2) | E1) | D2) | |
| D2 | E2 | R2 | 2 (R2, | 2 (R2, | 3 (E2, | Yes |
| | | | D2) | E2) | D2) | |
+----------+----------+-------+--------+--------+--------+----------+
Table 9: Finding 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 node-protecting PQ-node to final destination can be
examined to ensure that none of the primary nexthop nodes is
traversed. R-LFA path(s) that does not traverse any of the primary
nexthop nodes, gaurantees node-protection in the event of failure of
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-
node R2.
+-------------+------------+---------+-----------------+------------+
| Destination | Primary-NH | PQ-Node | R-LFA Paths | Exclude |
| (D) | (E) | (Y) | | All |
| | | | | Primary-NH |
+-------------+------------+---------+-----------------+------------+
| D1 | E1, E2 | R2 | S==>N==>R1==>R2 | No |
| | | | -->R3-->E1-->D1 | |
| | | | | |
| D2 | E1, E2 | R2 | S==>N==>R1==>R2 | Yes |
| | | | -->R3-->D2 | |
+-------------+------------+---------+-----------------+------------+
Table 10: R-LFA paths for destinations D1 and D2
From Table 9 and Table 10, in the above example above, the R-LFA path
from R2 does not meet the node-protecting inequality for destination
D1, while it does meet the same inequality for destination D2. And
so, while R2 provides 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 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.
skipping to change at page 15, line 15 skipping to change at page 19, line 7
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.3 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 approach proposed, 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 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 toplogy
without protection. Yet this limitation provides a necessary without protection. Yet this limitation provides a necessary
 End of changes. 7 change blocks. 
17 lines changed or deleted 186 lines changed or added

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