--- 1/draft-ietf-rtgwg-rlfa-node-protection-08.txt 2016-12-23 11:13:27.987308965 -0800
+++ 2/draft-ietf-rtgwg-rlfa-node-protection-09.txt 2016-12-23 11:13:28.031309995 -0800
@@ -1,24 +1,24 @@
Routing Area Working Group P. Sarkar, Ed.
Internet-Draft Individual Contributor
Intended status: Standards Track S. Hegde
-Expires: May 21, 2017 C. Bowers
+Expires: June 26, 2017 C. Bowers
Juniper Networks, Inc.
H. Gredler
RtBrick, Inc.
S. Litkowski
Orange
- November 17, 2016
+ December 23, 2016
Remote-LFA Node Protection and Manageability
- draft-ietf-rtgwg-rlfa-node-protection-08
+ draft-ietf-rtgwg-rlfa-node-protection-09
Abstract
The loop-free alternates computed following the current Remote-LFA
specification guarantees only link-protection. The resulting Remote-
LFA nexthops (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 described in [RFC7490], that describes
@@ -43,21 +43,21 @@
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
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 (c) 2016 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
@@ -80,31 +80,34 @@
2.2.5. Candidate Node-Protecting PQ Space . . . . . . . . . 7
2.2.6. Cost-Based Definitions . . . . . . . . . . . . . . . 7
2.2.6.1. Link-Protecting Extended P-Space . . . . . . . . 7
2.2.6.2. Node-Protecting Extended P-Space . . . . . . . . 7
2.2.6.3. Q-Space . . . . . . . . . . . . . . . . . . . . . 8
2.3. Computing Node-protecting R-LFA Path . . . . . . . . . . 9
2.3.1. Computing Candidate Node-protecting PQ-Nodes for
Primary nexthops . . . . . . . . . . . . . . . . . . 9
2.3.2. Computing node-protecting paths from PQ-nodes to
destinations . . . . . . . . . . . . . . . . . . . . 11
- 2.3.3. Limiting extra computational overhead . . . . . . . . 13
- 3. Manageabilty of Remote-LFA Alternate Paths . . . . . . . . . 14
- 3.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 14
- 3.2. The Solution . . . . . . . . . . . . . . . . . . . . . . 15
- 4. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 15
- 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15
- 6. Security Considerations . . . . . . . . . . . . . . . . . . . 15
- 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 15
- 7.1. Normative References . . . . . . . . . . . . . . . . . . 15
- 7.2. Informative References . . . . . . . . . . . . . . . . . 16
- Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 16
+ 2.3.3. Computing Node-Protecting R-LFA Paths for
+ Destinations with ECMP primary nexthop nodes . . . . 13
+ 2.3.4. Limiting extra computational overhead . . . . . . . . 17
+ 3. Manageabilty of Remote-LFA Alternate Paths . . . . . . . . . 18
+ 3.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 18
+ 3.2. The Solution . . . . . . . . . . . . . . . . . . . . . . 18
+
+ 4. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 19
+ 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19
+ 6. Security Considerations . . . . . . . . . . . . . . . . . . . 19
+ 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 19
+ 7.1. Normative References . . . . . . . . . . . . . . . . . . 19
+ 7.2. Informative References . . . . . . . . . . . . . . . . . 20
+ Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 20
1. Introduction
The Remote-LFA [RFC7490] specification provides loop-free alternates
that guarantee only link-protection. The resulting Remote-LFA
alternate nexthops (also referred to as the PQ-nodes) may not provide
node-protection for all destinations covered by the same, in case of
failure of the primary nexthop node. Neither does the specification
provide a means to determine the same.
@@ -572,21 +576,187 @@
The procedure described in this document helps no more than to
determine whether a given Remote-LFA alternate provides node-
protection for a given destination or not. It does not find out any
new Remote-LFA alternate nexthops, outside the ones already computed
by standard Remote-LFA procedure. However, in case of availability
of more than one PQ-node (Remote-LFA alternates) for a destination,
and node-protection is required for the given primary nexthop, this
procedure will eliminate the PQ-nodes that do not provide node-
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
Remote-LFA [RFC7490] draft (one reverse SPF for each of the directly
connected neighbors), this document proposes a forward SPF
computations 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.
@@ -648,21 +818,21 @@
3.2. The Solution
The additional forward SPF computation proposed in Section 2.3.2
document shall also collect links, nodes and path characteristics
along the second path segment. This shall enable collection of
complete path characteristics for a given 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.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
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 keep the computational complexity within affordable
limits. However if the alternate-selection policy is very
restrictive this may leave few destinations in the entire toplogy
without protection. Yet this limitation provides a necessary