draft-ietf-rtgwg-rlfa-node-protection-02.txt   draft-ietf-rtgwg-rlfa-node-protection-03.txt 
Routing Area Working Group P. Sarkar, Ed. Routing Area Working Group P. Sarkar, Ed.
Internet-Draft H. Gredler Internet-Draft S. Hegde
Intended status: Standards Track S. Hegde Intended status: Standards Track C. Bowers
Expires: December 17, 2015 C. Bowers Expires: April 8, 2016 Juniper Networks, Inc.
Juniper Networks, Inc. H. Gredler
Unaffiliated
S. Litkowski S. Litkowski
Orange Orange
H. Raghuveer October 6, 2015
June 15, 2015
Remote-LFA Node Protection and Manageability Remote-LFA Node Protection and Manageability
draft-ietf-rtgwg-rlfa-node-protection-02 draft-ietf-rtgwg-rlfa-node-protection-03
Abstract Abstract
The loop-free alternates computed following the current Remote-LFA The loop-free alternates computed following the current Remote-LFA
[I-D.ietf-rtgwg-remote-lfa] specification gaurantees only link- [RFC7490] specification guarantees only link-protection. The
protection. The resulting Remote-LFA nexthops (also called PQ- resulting Remote-LFA nexthops (also called PQ-nodes), may not
nodes), may not gaurantee node-protection for all destinations being guarantee node-protection for all destinations being protected by it.
protected by it.
This document describes procedures for determining if a given PQ-node This document describes procedures for determining if a given PQ-node
provides node-protection for a specific destination or not. The provides node-protection for a specific destination or not. The
document also shows how the same procedure can be utilised for document also shows how the same procedure can be utilised for
collection of complete characteristics for alternate paths. collection of complete characteristics for alternate paths.
Knowledge about the characteristics of all alternate path is Knowledge about the characteristics of all alternate path is
precursory to apply operator defined policy for eliminating paths not precursory to apply operator defined policy for eliminating paths not
fitting constraints. fitting constraints.
Requirements Language Requirements Language
skipping to change at page 2, line 7 skipping to change at page 2, line 7
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 December 17, 2015. This Internet-Draft will expire on April 8, 2016.
Copyright Notice Copyright Notice
Copyright (c) 2015 IETF Trust and the persons identified as the Copyright (c) 2015 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 30 skipping to change at page 2, line 30
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Node Protection with Remote-LFA . . . . . . . . . . . . . . . 3 2. Node Protection with Remote-LFA . . . . . . . . . . . . . . . 3
2.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 4 2.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 4
2.2. Few Additional Definitions . . . . . . . . . . . . . . . 5 2.2. Few Additional Definitions . . . . . . . . . . . . . . . 5
2.2.1. Link-Protecting Extended P-Space . . . . . . . . . . 5 2.2.1. Link-Protecting Extended P-Space . . . . . . . . . . 6
2.2.2. Node-Protecting Extended P-Space . . . . . . . . . . 6 2.2.2. Node-Protecting Extended P-Space . . . . . . . . . . 6
2.2.3. Q-Space . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.3. Q-Space . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.4. Link-Protecting PQ Space . . . . . . . . . . . . . . 8 2.2.4. Link-Protecting PQ Space . . . . . . . . . . . . . . 8
2.2.5. Candidate Node-Protecting PQ Space . . . . . . . . . 8 2.2.5. Candidate Node-Protecting PQ Space . . . . . . . . . 8
2.3. Computing Node-protecting R-LFA Path . . . . . . . . . . 8 2.3. Computing Node-protecting R-LFA Path . . . . . . . . . . 8
2.3.1. Computing Candidate Node-protecting PQ-Nodes for 2.3.1. Computing Candidate Node-protecting PQ-Nodes for
Primary nexthops . . . . . . . . . . . . . . . . . . 8 Primary nexthops . . . . . . . . . . . . . . . . . . 8
2.3.2. Computing node-protecting paths from PQ-nodes to 2.3.2. Computing node-protecting paths from PQ-nodes to
destinations . . . . . . . . . . . . . . . . . . . . 10 destinations . . . . . . . . . . . . . . . . . . . . 10
2.3.3. Limiting extra computational overhead . . . . . . . . 12 2.3.3. Limiting extra computational overhead . . . . . . . . 12
skipping to change at page 3, line 7 skipping to change at page 3, line 7
4. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 14 4. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 14
5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14
6. Security Considerations . . . . . . . . . . . . . . . . . . . 14 6. Security Considerations . . . . . . . . . . . . . . . . . . . 14
7. References . . . . . . . . . . . . . . . . . . . . . . . . . 14 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 14
7.1. Normative References . . . . . . . . . . . . . . . . . . 15 7.1. Normative References . . . . . . . . . . . . . . . . . . 15
7.2. Informative References . . . . . . . . . . . . . . . . . 15 7.2. Informative References . . . . . . . . . . . . . . . . . 15
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 15 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 15
1. Introduction 1. Introduction
The Remote-LFA [I-D.ietf-rtgwg-remote-lfa] specification provides The Remote-LFA [RFC7490] specification provides loop-free alternates
loop-free alternates that gaurantees only link-protection. The that guarantees only link-protection. The resulting Remote-LFA
resulting Remote-LFA alternate nexthops (also referred to as the PQ- alternate nexthops (also referred to as the PQ-nodes) may not provide
nodes) may not provide node-protection for all destinations covered node-protection for all destinations covered by the same, in case of
by the same, in case of failure of the primary nexthop node. Neither failure of the primary nexthop node. Neither does the specification
does the specification provide a means to determine the same. provide a means to determine the same.
Also, the LFA Manageability [I-D.ietf-rtgwg-lfa-manageability] Also, the LFA Manageability [I-D.ietf-rtgwg-lfa-manageability]
document, requires a computing router to find all possible (including document, requires a computing router to find all possible (including
all possible Remote-LFA) alternate nexthops, collect the complete set all possible Remote-LFA) alternate nexthops, collect the complete set
of path characteristics for each alternate path, run a alternate- of path characteristics for each alternate path, run a alternate-
selection policy (configured by the operator), and find the best selection policy (configured by the operator), and find the best
alternate path. This will require the Remote-LFA implementation to alternate path. This will require the Remote-LFA implementation to
gather all the required path characteristics along each link on the gather all the required path characteristics along each link on the
entire Remote-LFA alternate path. entire Remote-LFA alternate path.
With current LFA [RFC5286] and Remote-LFA implementations, the With current LFA [RFC5286] and Remote-LFA implementations, the
forward SPF (and reverse SPF) is run on the computing router and its forward SPF (and reverse SPF) is run on the computing router and its
immediate 1-hop routers as the roots. While that enables computation immediate 1-hop routers as the roots. While that enables computation
of path attributes (e.g. SRLG, Admin-groups) for first alternate of path attributes (e.g. SRLG, Admin-groups) for first alternate
path segment from the computing router to the PQ-node, there is no 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 means for the computing router to gather any path attributes for the
path segment from the PQ-node to destination. Consecutively any path segment from the PQ-node to destination. Consequently any
policy-based selection of alternate paths will consider only the path policy-based selection of alternate paths will consider only the path
attributes from the computing router up until the PQ-node. attributes from the computing router up until the PQ-node.
This document describes a procedure for determining node-protection This document describes a procedure for determining node-protection
with Remote-LFA. The same procedure are also extended for collection with Remote-LFA. The same procedure are also extended for collection
of complete set of path attributes, enabling more accurate policy- of a complete set of path attributes, enabling more accurate policy-
based selection for alternate paths obtained with Remote-LFA. based selection for alternate paths obtained with Remote-LFA.
2. Node Protection with Remote-LFA 2. Node Protection with Remote-LFA
Node-protection is required to provide protection of traffic on a Node-protection is required to provide protection of traffic on a
given forwarding node, against the failure of the first-hop node on given forwarding node, against the failure of the first-hop node on
the primary forwarding path. Such protection becomes more critical the primary forwarding path. Such protection becomes more critical
in the absence of mechanisms like non-stop-routing in the network. in the absence of mechanisms like non-stop-routing in the network.
Certain operators refrains from deploying non-stop-routing in their Certain operators refrain from deploying non-stop-routing in their
network, due to the significant additional performance complexities network, due to the significant additional performance complexities
it comes along with. In such cases node-protection is a must to it introduces. In such cases node-protection is a essential to
gaurantee un-interrupted flow of traffic, even in the case of an guarantee un-interrupted flow of traffic, even in the case of an
entire forwarding node going down. entire forwarding node going down.
The following sections discusses the node-protection problem in the The following sections discuss the node-protection problem in the
context of Remote-LFA and proposes a solution for solving the same. context of Remote-LFA and propose a solution.
2.1. The Problem 2.1. The Problem
To better illustrate the problem and the solution proposed in this To better illustrate the problem and the solution proposed in this
document the following topology diagram from the Remote-LFA document the following topology diagram from the Remote-LFA [RFC7490]
[I-D.ietf-rtgwg-remote-lfa] draft is being re-used with slight draft is being re-used with slight modification.
modification.
D1 D1
/ /
S-x-E S-x-E
/ \ / \
N R3--D2 N R3--D2
\ / \ /
R1---R2 R1---R2
Figure 1: Topology 1 Figure 1: Topology 1
In the above topology, for all (non-ECMP) destinations reachable via 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- the S-E link there is no standard LFA alternate. As per the Remote-
LFA [I-D.ietf-rtgwg-remote-lfa] alternate specifications node R2 LFA [RFC7490] alternate specifications node R2 being the only PQ-node
being the only PQ-node for the S-E link provides nexthop for all the for the S-E link provides nexthop for all the above destinations.
above destinations. Table 1 below, shows all possible primary and Table 1 below, shows all possible primary and Remote-LFA alternate
Remote-LFA alternate paths for each destination. paths for each destination.
+-------------+--------------+---------+-------------------------+ +-------------+--------------+---------+-------------------------+
| Destination | Primary Path | PQ-node | Remote-LFA Backup Path | | Destination | Primary Path | PQ-node | Remote-LFA Backup Path |
+-------------+--------------+---------+-------------------------+ +-------------+--------------+---------+-------------------------+
| R3 | S->E->R3 | R2 | S=>N=>R1=>R2->R3 | | R3 | S->E->R3 | R2 | S=>N=>R1=>R2->R3 |
| E | S->E | R2 | S=>N=>R1=>R2->R3->E | | E | S->E | R2 | S=>N=>R1=>R2->R3->E |
| D1 | S->E->D1 | R2 | S=>N=>R1=>R2->R3->E->D1 | | D1 | S->E->D1 | R2 | S=>N=>R1=>R2->R3->E->D1 |
| D2 | S->E->R3->D2 | R2 | S=>N=>R1=>R2->R3->D2 | | D2 | S->E->R3->D2 | R2 | S=>N=>R1=>R2->R3->D2 |
+-------------+--------------+---------+-------------------------+ +-------------+--------------+---------+-------------------------+
skipping to change at page 4, line 50 skipping to change at page 4, line 49
A closer look at Table 1 shows that, while the PQ-node R2 provides 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- link-protection for all the destinations, it does not provide node-
protection for destinations E and D1. In the event of the node- protection for destinations E and D1. In the event of the node-
failure on primary nexthop E, the alternate path from Remote-LFA failure on primary nexthop E, the alternate path from Remote-LFA
nexthop R2 to E and D1 also becomes unavailable. So for a Remote-LFA nexthop R2 to E and D1 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
mandatory that, the shortest path from the given PQ-node to the given mandatory that, the shortest path from the given PQ-node to the given
destination MUST not traverse the primary nexthop. destination MUST not traverse the primary nexthop.
In another extension of the topology in Figure 1 let us consider an In another extension of the topology in Figure 1 let us consider an
additional link between N and E. additional link between N and E with the same cost as the other
links.
D1 D1
/ /
S-x-E S-x-E
/ / \ / / \
N---+ R3--D2 N---+ R3--D2
\ / \ /
R1---R2 R1---R2
Figure 2: Topology 2 Figure 2: Topology 2
In the above topology, the S-E link is no more on any of the shortest In the above topology, the S-E link is no more on any of the shortest
paths from N to R3. Hence R3 is also included in both the Extended-P paths from N to R3, E and D1. Hence R3, E and D1 are also included
space and PQ space of E (w.r.t S-E link). Table 2 below, shows all in both the Extended-P space and Q space of E (w.r.t S-E link).
possible primary and R-LFA alternate paths via PQ-node R3, for each Table 2 below, shows all possible primary and R-LFA alternate paths
destination reachable through the S-E link in the above topology. via PQ-node R3, for each destination reachable through the S-E link
The R-LFA alternate paths via PQ-node R2 remains same as in Table 1. in the above topology. The R-LFA alternate paths via PQ-node R2
remains same as in Table 1.
+-------------+--------------+---------+------------------------+ +-------------+--------------+---------+------------------------+
| Destination | Primary Path | PQ-node | Remote-LFA Backup Path | | Destination | Primary Path | PQ-node | Remote-LFA Backup Path |
+-------------+--------------+---------+------------------------+ +-------------+--------------+---------+------------------------+
| R3 | S->E->R3 | R3 | S=>N=>E=>R3 | | R3 | S->E->R3 | R3 | S=>N=>E=>R3 |
| E | S->E | R3 | S=>N=>E=>R3->E | | E | S->E | R3 | S=>N=>E=>R3->E |
| D1 | S->E->D1 | R3 | S=>N=>E=>R3->E->D1 | | D1 | S->E->D1 | R3 | S=>N=>E=>R3->E->D1 |
| D2 | S->E->R3->D2 | R3 | S=>N=>E=>R3->D2 | | D2 | S->E->R3->D2 | R3 | S=>N=>E=>R3->D2 |
+-------------+--------------+---------+------------------------+ +-------------+--------------+---------+------------------------+
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
D1, 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 D1 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, the nexthop, in the event of the node-failure on primary nexthop E, on
alternate path from S to R-LFA nexthop R3 also becomes unavailable. the alternate path from S to R-LFA nexthop R3, one of parallel ECMP
So for a Remote-LFA nexthop to provide node-protection for a given path between N and R3 also becomes unavailable. So for a Remote-LFA
destination, it is also mandatory that, the shortest path from S to nexthop to provide node-protection for a given destination, it is
the chosen PQ-node MUST not traverse the primary nexthop node. also mandatory that, the shortest path from S to the chosen PQ-node
MUST not traverse the primary nexthop node.
2.2. Few Additional Definitions 2.2. Few 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 [I-D.ietf-rtgwg-remote-lfa] draft. the ones mentioned in Remote-LFA [RFC7490] draft.
2.2.1. Link-Protecting Extended P-Space 2.2.1. Link-Protecting Extended P-Space
The Remote-LFA [I-D.ietf-rtgwg-remote-lfa] draft already defines The Remote-LFA [RFC7490] draft already defines this. The link-
this. The link-protecting extended P-space for a link S-E being protecting extended P-space for a link S-E being protected is the set
protected is the set of routers that are reachable from one or more of routers that are reachable from one or more direct neighbors of S,
direct neighbors of S, except primary node E, without traversing the except primary node E, without traversing the S-E link on any of the
S-E link on any of the shortest path from the direct neighbor to the shortest path from the direct neighbor to the router. This MUST
router. This MUST exclude any direct neighbor for which there is exclude any direct neighbor for which there is at least one ECMP path
atleast one ECMP path from the direct neighbor traversing the from the direct neighbor traversing the link(S-E) being protected.
link(S-E) being protected.
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 to the link
(S-E) being protected, if and only if, there exists atleast one (S-E) being protected, if and only if, there exists at least one
direct neighbor of S, Ni, other than primary nexthop E, that direct neighbor of S, Ni, other than primary nexthop E, that
satisfies the following condition. satisfies the 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.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
being protected, is the set of routers that are reachable from one or being protected, is the set of routers that are reachable from one or
more direct neighbors of S, except primary node E, without traversing more direct neighbors of S, except primary node E, without traversing
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 atleast one ECMP path from the direct neighbor traversing the node is at least one ECMP path from the direct neighbor traversing the
E being protected. node E being protected.
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 to the node E
being protected, if and only if, there exists atleast 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.
Ni : A direct neighbor of S other than primary Ni : A direct neighbor of S other than primary
skipping to change at page 7, line 27 skipping to change at page 7, line 27
It must be noted that a node Y satisfying the condition in Figure 4 It must be noted that a node Y satisfying the condition in Figure 4
above only guarantees that the R-LFA alternate path segment from S 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 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 a node failure of E. It does not yet guarantee that the path segment
from node Y to the destination is also unaffected by the same failure from node Y to the destination is also unaffected by the same failure
event. event.
2.2.3. Q-Space 2.2.3. Q-Space
The Remote-LFA [I-D.ietf-rtgwg-remote-lfa] draft already defines The Remote-LFA [RFC7490] draft already defines this. The Q-space for
this. The Q-space for a link S-E being protected is the set of a link S-E being protected is the set of routers that can reach
routers that can reach primary node E, without traversing the S-E primary node E, without traversing the S-E link on any of the
link on any of the shortest path from the node Y to primary nexthop shortest path from the node Y to primary nexthop E. This MUST
E. This MUST exclude any destination for which there is atleast one exclude any destination for which there is at least one ECMP path
ECMP path from the node Y to the primary nexthop E traversing the from the node Y to the primary nexthop E traversing the link(S-E)
link(S-E) being protected. being protected.
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 to the link (S-E) being protected, if
and only if, the following condition is satisfied. and 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.
skipping to change at page 8, line 30 skipping to change at page 8, line 30
via the same, in entirety, is unaffected in the event of a node via the same, in entirety, is unaffected in the event of a node
failure of primary nexthop node E. It only guarantees that the path failure of primary nexthop node E. It only guarantees that the path
segment from S to PQ-node Y is unaffected by the same failure event. 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 The PQ-nodes in the candidate node-protecting PQ space may provide
node protection for only a subset of destinations that are reachable node protection for only a subset of destinations that are reachable
through the corresponding primary link. through the corresponding primary link.
2.3. Computing Node-protecting R-LFA Path 2.3. Computing Node-protecting R-LFA Path
The R-LFA alternate path through a given PQ-node to a given The R-LFA alternate path through a given PQ-node to a given
destination comprises 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 unaffected in the event of failure of the primary segments are affected in the event of failure of the primary nexthop
nexthop node. Sections Section 2.3.1 and Section 2.3.2 shows how node. Sections Section 2.3.1 and Section 2.3.2 shows how this can be
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 atleast one direct 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 neighbor Ni of S, such that all shortest paths from Ni to the PQ-node
does not traverse primary nexthop node E. does not traverse primary nexthop node E.
Implementations should run the inequality in Section 2.2.2 Figure 4 Implementations should run the inequality in Section 2.2.2 Figure 4
for all direct neighbor, other than primary nexthop node E, to for all direct neighbor, other than primary nexthop node E, to
determine whether a node Y is a candidate node-protecting PQ-node. determine whether a node Y is a candidate node-protecting PQ-node.
All of the metrics needed by this inequality would have been already All of the metrics needed by this inequality would have been already
collected from the forward SPFs rooted at each of direct neighbor S, collected from the forward SPFs rooted at each of direct neighbor S,
computed as part of standard LFA [RFC5286] implementation. With computed as part of standard LFA [RFC5286] implementation. With
reference to the topology in Figure 2, Table 3 below shows how the reference to the topology in Figure 2, Table 3 below shows how the
skipping to change at page 9, line 30 skipping to change at page 9, line 30
| R2 | N | 2 (N,R2) | 1 (N,E) | 2 | Yes | | R2 | N | 2 (N,R2) | 1 (N,E) | 2 | Yes |
| | | | | (E,R2) | | | | | | | (E,R2) | |
| R3 | N | 2 (N,R3) | 1 (N,E) | 1 | No | | R3 | N | 2 (N,R3) | 1 (N,E) | 1 | No |
| | | | | (E,R3) | | | | | | | (E,R3) | |
+------------+----------+----------+----------+---------+-----------+ +------------+----------+----------+----------+---------+-----------+
Table 3: Node-protection evaluation for R-LFA repair tunnel to PQ- Table 3: Node-protection evaluation for R-LFA repair tunnel to PQ-
node node
As seen in the above Table 3 , R3 does not meet the node-protecting As seen in the above Table 3 , R3 does not meet the node-protecting
extended-p-space inequality And so, while R2 is in candidate node- extended-p-space inequality and so, while R2 is in candidate node-
protecting PQ space, R3 is not. protecting PQ space, R3 is not.
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 it's direct neighbors as the SPF root, executed as part of each of it's direct neighbors as the SPF root, executed as part of
the standard LFA [RFC5286] computations. So S may re-use the list of the 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 atleast one direct neighbor of S, other than the primary if, there is at least one direct neighbor of S, other than the
nexthop E, for which, the primary nexthop node E does not exist on primary nexthop E, for which, the primary nexthop node E does not
the list of nodes traversed on any of the shortest path(s) from the exist on the list of nodes traversed on any of the shortest path(s)
direct neighbor to the PQ-node. Table 4 below is an illustration of from the direct neighbor to the PQ-node. Table 4 below is an
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 |
| R2 | S->E->R3->R2 | No | No | | R2 | S->E->R3->R2 | No | No |
| R3 | S->N->E->R3 | Yes | No | | R3 | S->N->E->R3 | Yes | No |
+-----------+-------------------+-----------------+-----------------+ +-----------+-------------------+-----------------+-----------------+
Table 4: Protection of Remote-LFA tunnel to the PQ-node Table 4: Protection of Remote-LFA tunnel to the PQ-node
As seen in the above Table 4 while R2 is candidate node-protecting As seen in the above Table 4 while R2 is candidate node-protecting
Remote-LFA nexthop for R3 and D2, it is not so for E and D1, since Remote-LFA nexthop for R3 and D2, it is not so for E and D1, since
the primary nexthop E is in the shortest path from R2 to E and F. the primary nexthop E is in the shortest path from R2 to E and D1.
2.3.2. Computing node-protecting paths from PQ-nodes to destinations 2.3.2. Computing node-protecting paths from PQ-nodes to destinations
Once a computing router finds all the candidate node-protecting PQ- Once a computing router finds all the candidate node-protecting PQ-
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 in 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 destination remain unaffected in the event of a node failure of the
primary nexthop node. To ensure this, the computing router will need primary nexthop node. To ensure this, the computing router will need
to ensure that, the primary nexthop node should not be on any of the to ensure that, the primary nexthop node should not be on any of the
shortest paths from the PQ-node to the given destination. shortest 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. The additional forward SPF computation for each PQ- the destination. The additional forward SPF computation for each PQ-
node, shall help determine, if a given primary nexthop node is on the node, shall help determine, if a given primary nexthop node is on the
shortest paths from the PQ-node to the given destination or not. To shortest paths from the PQ-node to the given destination or not. To
determine if a given candidate node-protecting PQ-node provides node- determine if a given candidate node-protecting PQ-node provides node-
protecting alternate for a given destination, the primary nexthop protecting alternate for a given destination, the primary nexthop
node should not be on any of the shortest paths from the PQ-node to node should not be on any of the shortest paths from the PQ-node to
the given destination. On running the forward SPF on a candidate the given destination. On running the forward SPF on a candidate
node-protecting PQ-node the computing router shall run the inequality node-protecting PQ-node the computing router shall run the inequality
in Figure 6 below. PQ-nodes that does not qualify the condition for in Figure 6 below. A PQ-node that does not qualify the condition for
a given destination, does not gaurantee node-protection for the path a given destination, does not guarantee node-protection for the path
segment from the PQ-node to the given destination. segment from the PQ-node to the given destination.
D_opt(Y,D) < D_opt(Y,E) + Distance_opt(E,D) D_opt(Y,D) < D_opt(Y,E) + Distance_opt(E,D)
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.
D : The destination node. D : The destination node.
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-protecting PQ-node being evaluated Y : The node-protecting PQ-node being evaluated
skipping to change at page 11, line 43 skipping to change at page 11, line 43
| D1 | E | 3 | 2 | 1 | No | | D1 | E | 3 | 2 | 1 | No |
| | | (R2,D1) | (R2,E) | (E,D1) | | | | | (R2,D1) | (R2,E) | (E,D1) | |
| D2 | E | 2 | 2 | 1 | Yes | | D2 | E | 2 | 2 | 1 | Yes |
| | | (R2,D2) | (R2,E) | (E,D2) | | | | | (R2,D2) | (R2,E) | (E,D2) | |
+-------------+------------+---------+--------+---------+-----------+ +-------------+------------+---------+--------+---------+-----------+
Table 5: Node-protection evaluation for R-LFA path segment between Table 5: Node-protection evaluation for R-LFA path segment between
PQ-node and destination PQ-node and destination
As seen in the above example above, R2 does not meet the node- As seen in the above example above, R2 does not meet the node-
protecting inequality for destination E, and F. And so, once again, protecting inequality for destination E, and D1. And so, once again,
while R2 is a node-protecting Remote-LFA nexthop for R3 and G, it is while R2 is a node-protecting Remote-LFA nexthop for R3 and D2, it is
not so for E and F. not so for E and D1.
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, to traversed on the shortest path(s) from a given root to others, to
determine whether a PQ-node provides node-protection for a given determine whether a PQ-node provides node-protection for a given
destination or not, the list of nodes computed from forward SPF run destination or not, the list of nodes computed from forward SPF run
on the PQ-node, for the given destination, should be inspected. In on the PQ-node, for the given destination, should be inspected. In
case the list contains the primary nexthop node, the PQ-node does not case the list contains the primary nexthop node, the PQ-node does not
provide node-protection. Else, the PQ-node guarantees node- provide node-protection. Else, the PQ-node guarantees node-
protecting alternate for the given destination. Below is an protecting alternate for the given destination. Below is an
illustration of the mechanism with candidate node-protecting PQ-node illustration of the mechanism with candidate node-protecting PQ-node
skipping to change at page 12, line 25 skipping to change at page 12, line 25
| R3 | R2->R3 | Yes | Yes | | R3 | R2->R3 | Yes | Yes |
| E | R2->R3->E | Yes | No | | E | R2->R3->E | Yes | No |
| D1 | R2->R3->E->D1 | Yes | No | | D1 | R2->R3->E->D1 | Yes | No |
| D2 | R2->R3->D2 | Yes | Yes | | D2 | R2->R3->D2 | Yes | Yes |
+-------------+-----------------+-----------------+-----------------+ +-------------+-----------------+-----------------+-----------------+
Table 6: Protection of Remote-LFA path between PQ-node and Table 6: Protection of Remote-LFA path between PQ-node and
destination destination
As seen in the above example while R2 is candidate node-protecting As seen in the above example while R2 is candidate node-protecting
R-LFA nexthop for R3 and G, it is not so for E and F, since the R-LFA nexthop for R3 and D2, it is not so for E and D1, since the
primary nexthop E is in the shortest path from R2 to E and F. primary nexthop E is in the shortest path from R2 to E and D1.
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. Limiting extra computational overhead
In addition to the extra reverse SPF computation, one per directly In addition to the extra reverse SPF computation, one per directly
connected neighbor, suggested by the Remote-LFA connected neighbor, suggested by the Remote-LFA [RFC7490] draft, this
[I-D.ietf-rtgwg-remote-lfa] draft, this document proposes a forward document proposes a forward SPF per PQ-node discovered in the
SPF per PQ-node discovered in the network. Since the average number network. Since the average number of PQ-nodes found in any network
of PQ-nodes found in any network is considerably more than the number is considerably more than the number of direct neighbors of the
of direct neighbors of the computing router, the proposal of running computing router, the proposal of running one forward SPF per PQ-node
one forward SPF per PQ-node may add considerably to the overall SPF may add considerably to the overall SPF computation time.
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 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, it's 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 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 Section 2.3.2.
3. Manageabilty of Remote-LFA Alternate Paths 3. Manageabilty of Remote-LFA Alternate Paths
3.1. The Problem 3.1. The Problem
With the regular Remote-LFA [I-D.ietf-rtgwg-remote-lfa] functionality With the regular Remote-LFA [RFC7490] functionality the computing
the computing router may compute more than one PQ-node as usable router may compute more than one PQ-node as usable Remote-LFA
Remote-LFA alternate nexthops. Additionally an alternate selection alternate nexthops. Additionally an alternate selection policy may
policy may be configured to enable the network operator to choose one be configured to enable the network operator to choose one of them as
of them as the most appropriate Remote-LFA alternate. For such the most appropriate Remote-LFA alternate. For such policy-based
policy-based alternate selection to run, all the relevant path alternate selection to run, all the relevant path characteristics for
characteristics for each the alternate paths (one through each of the each the alternate paths (one through each of the PQ-nodes), needs to
PQ-nodes), needs to be collected. As mentioned befor in section be collected. As mentioned before in section Section 2.3 the R-LFA
Section 2.3 the R-LFA alternate path through a given PQ-node to a alternate path through a given PQ-node to a given destination is
given destination comprises of two path segments. comprised of 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 path 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
skipping to change at page 14, line 35 skipping to change at page 14, line 34
the computational complexity within affordable limits. However if the computational complexity within affordable limits. However if
the alternate-selection policy is very restrictive this may leave few the alternate-selection policy is very restrictive this may leave few
destinations in the entire toplogy without protection. Yet this destinations in the entire toplogy without protection. Yet this
limitation provides a necessary tradeoff between extensive coverage limitation provides a necessary tradeoff between extensive coverage
and immense computational overhead. and immense computational 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. providing valuable feedback. Also, many thanks to Harish Raghuveer
for his review and comments on the initial versions of this document.
5. IANA Considerations 5. IANA Considerations
N/A. - No protocol changes are proposed in this document. N/A. - No protocol changes are proposed in this document.
6. Security Considerations 6. Security Considerations
This document does not introduce any change in any of the protocol This document does not introduce any change in any of the protocol
specifications. It simply proposes to run an extra SPF rooted on specifications. It simply proposes to run an extra SPF rooted on
each PQ-node discovered in the whole network. each PQ-node discovered in the whole network.
7. References 7. References
7.1. Normative References 7.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997. Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<http://www.rfc-editor.org/info/rfc2119>.
7.2. Informative References 7.2. Informative References
[I-D.ietf-rtgwg-lfa-manageability] [I-D.ietf-rtgwg-lfa-manageability]
Litkowski, S., Decraene, B., Filsfils, C., Raza, K., Litkowski, S., Decraene, B., Filsfils, C., Raza, K.,
Horneffer, M., and p. psarkar@juniper.net, "Operational Horneffer, M., and P. Sarkar, "Operational management of
management of Loop Free Alternates", draft-ietf-rtgwg-lfa- Loop Free Alternates", draft-ietf-rtgwg-lfa-
manageability-03 (work in progress), February 2014. manageability-11 (work in progress), June 2015.
[I-D.ietf-rtgwg-remote-lfa] [RFC5286] Atlas, A., Ed. and A. Zinin, Ed., "Basic Specification for
Bryant, S., Filsfils, C., Previdi, S., Shand, M., and S. IP Fast Reroute: Loop-Free Alternates", RFC 5286,
Ning, "Remote LFA FRR", draft-ietf-rtgwg-remote-lfa-06 DOI 10.17487/RFC5286, September 2008,
(work in progress), May 2014. <http://www.rfc-editor.org/info/rfc5286>.
[RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast [RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N.
Reroute: Loop-Free Alternates", RFC 5286, September 2008. So, "Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)",
RFC 7490, DOI 10.17487/RFC7490, April 2015,
<http://www.rfc-editor.org/info/rfc7490>.
Authors' Addresses Authors' Addresses
Pushpasis Sarkar (editor) Pushpasis Sarkar (editor)
Juniper Networks, Inc. Juniper Networks, Inc.
Electra, Exora Business Park Electra, Exora Business Park
Bangalore, KA 560103 Bangalore, KA 560103
India India
Email: psarkar@juniper.net Email: pushpasis.ietf@gmail.com; psarkar@juniper.net
Hannes Gredler
Juniper Networks, Inc.
1194 N. Mathilda Ave.
Sunnyvale, CA 94089
US
Email: hannes@juniper.net
Shraddha Hegde Shraddha Hegde
Juniper Networks, Inc. Juniper Networks, Inc.
Electra, Exora Business Park Electra, Exora Business Park
Bangalore, KA 560103 Bangalore, KA 560103
India India
Email: shraddha@juniper.net Email: shraddha@juniper.net
Chris Bowers Chris Bowers
Juniper Networks, Inc. Juniper Networks, Inc.
1194 N. Mathilda Ave. 1194 N. Mathilda Ave.
Sunnyvale, CA 94089 Sunnyvale, CA 94089
US US
Email: cbowers@juniper.net Email: cbowers@juniper.net
Hannes Gredler
Unaffiliated
Email: hannes@gredler.at
Stephane Litkowski Stephane Litkowski
Orange Orange
Email: stephane.litkowski@orange.com Email: stephane.litkowski@orange.com
Harish Raghuveer
Email: harish.r.prabhu@gmail.com
 End of changes. 45 change blocks. 
126 lines changed or deleted 127 lines changed or added

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