< 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.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/