< draft-ietf-rtgwg-backoff-algo-00.txt		draft-ietf-rtgwg-backoff-algo-01.txt >
	Network Working Group B. Decraene		Network Working Group B. Decraene
	Internet-Draft Orange		Internet-Draft Orange
	Intended status: Standards Track May 4, 2015		Intended status: Standards Track S. Litkowski
	Expires: November 5, 2015		Expires: December 21, 2015 Orange Business Service
			H. Gredler
			Juniper Networks, Inc.
			A. Lindem
			Cisco Systems
			P. Francois
			IMDEA Networks Institute
			June 19, 2015
	Back-off SPF algorithm for link state IGP		SPF Back-off algorithm for link state IGPs
	draft-ietf-rtgwg-backoff-algo-00		draft-ietf-rtgwg-backoff-algo-01
	Abstract		Abstract
	This document defines a standard algorithm to back-off link-state IGP		This document defines a standard algorithm to back-off link-state IGP
	SPF computations.		SPF computations.
	Having one standardized algorithm improves interoperability by		Having one standard algorithm improves interoperability by reducing
	reducing the probability and/or duration of transient forwarding		the probability and/or duration of transient forwarding loops during
	loops during the IGP convergence in the area/level when the network		the IGP convergence when the IGP reacts to multiple proximate IGP
	reacts to multiple consecutive events.		events.
	Requirements Language		Requirements Language
	The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",		The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
	"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this		"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
	document are to be interpreted as described in [RFC2119].		document are to be interpreted as described in [RFC2119].
	Status of This Memo		Status of This Memo
	This Internet-Draft is submitted in full conformance with the		This Internet-Draft is submitted in full conformance with the
	skipping to change at page 1, line 42 ¶		skipping to change at page 1, line 49 ¶
	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 November 5, 2015.		This Internet-Draft will expire on December 21, 2015.
	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 20 ¶		skipping to change at page 2, line 25 ¶
	to this document. Code Components extracted from this document must		to this document. Code Components extracted from this document must
	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 . . . . . . . . . . . . . . . . . . . . . . . . 2		1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
	2. High level goals . . . . . . . . . . . . . . . . . . . . . . 3		2. High level goals . . . . . . . . . . . . . . . . . . . . . . 3
	3. Definitions and parameters . . . . . . . . . . . . . . . . . 3		3. Definitions and parameters . . . . . . . . . . . . . . . . . 3
	4. Principle of SPF delay algorithm . . . . . . . . . . . . . . 4		4. Principles of SPF delay algorithm . . . . . . . . . . . . . . 4
	5. Specification of SPF delay algorithm . . . . . . . . . . . . 4		5. Specification of the SPF delay algorithm . . . . . . . . . . 5
	6. Impact on micro-loops . . . . . . . . . . . . . . . . . . . . 5		6. Parameters . . . . . . . . . . . . . . . . . . . . . . . . . 6
	7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 5		7. Impact on micro-loops . . . . . . . . . . . . . . . . . . . . 6
	8. Security considerations . . . . . . . . . . . . . . . . . . . 5		8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 7
	9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 5		9. Security considerations . . . . . . . . . . . . . . . . . . . 7
	10. References . . . . . . . . . . . . . . . . . . . . . . . . . 6		10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 7
	10.1. Normative References . . . . . . . . . . . . . . . . . . 6		11. References . . . . . . . . . . . . . . . . . . . . . . . . . 7
	10.2. Informative References . . . . . . . . . . . . . . . . . 6		11.1. Normative References . . . . . . . . . . . . . . . . . . 7
	Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 6		11.2. Informative References . . . . . . . . . . . . . . . . . 7
			Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 8
	1. Introduction		1. Introduction
	Link state IGP, such as IS-IS [ISO10589-Second-Edition] and OSPF		Link state IGPs, such as IS-IS [ISO10589-Second-Edition] and OSPF
	[RFC2328], performs distributed computation on all nodes of the area/		[RFC2328], perform distributed route computation on all routers of
	level. In order to have consistent routing tables across the		the area/level. In order to have consistent routing tables across
	network, such distributed computation requires that all routers have		the network, such distributed computation requires that all routers
	the same vision of the network (Link State DataBase (LSDB)) and		have the same version of the network topology (Link State DataBase
	perform their computation at the same time.		(LSDB)) and perform their computation at the same time.
	In general, when the network is stable, there is a desire to compute		In general, when the network is stable, there is a desire to compute
	the new SPF as soon as the failure is known, in order to quickly		the new SPF as soon as the failure is detected in order to quickly
	route around the failure. However, when the network is experiencing		route around the failure. However, when the network is experiencing
	multiple consecutive failures over a short period of time, there is a		multiple proximate failures over a short period of time, there is a
	desire to limit the frequency of SPF computations. Indeed, this		conflicting desire to limit the frequency of SPF computations.
	allow reducing the control plane resources used by IGP and all		Indeed, this allows a reduction in control plane resources used by
	protocols/sub system reacting on it such as LDP, RSVP-TE, BGP, Fast		IGPs and all protocols/subsystem reacting on the attendant route
	ReRoute computations, FIB updates..., reduce the churn on nodes and		change, such as LDP, RSVP-TE, BGP, Fast ReRoute computations, FIB
	in the network, in particular reduce side effects such as micro-loops		updates... This will reduce the churn on routers and in the network
	which may happen during each IGP convergence.		and, in particular, reduce the side effects such as micro-loops that
			ensue during IGP convergence.
	To allow for this, some back-off algorithm have been implemented.		To allow for this, IGPs implement a SPF back-off algorithm.
	Different implementations choose different algorithms, hence in a		Different implementations choose different algorithms. Hence, in a
	multi-vendor network, it's not possible to enforce that all routers		multi-vendor network, it's not possible to ensure that all routers
	triggers their SPF computation after the same waiting delay. This		trigger their SPF computation after the same delay. This situation
	situation increases the average differential delay between routers		increases the average differential delay between routers completing
	end of RIB computation. It also increases the probability that		their SPF computation. It also increases the probability that
	different routers compute their RIB based on a different LSDB. Both		different routers compute their FIBs based on a different LSDB
	increases the probability and/or duration of micro-loops.		versions. Both factors increase the probability and/or duration of
			micro-loops.
	To allow for multi-vendors networks having all the routers delaying		To allow multi-vendor networks to have all routers delay their SPF
	their SPF for the same duration, this document specifies a		computations for the same duration, this document specifies a
	standardized algorithm. Implementations may offer alternative		standard algorithm. Optionally, implementations may offer
	optional algorithms.		alternative algorithms.
	2. High level goals		2. High level goals
	The high level goals of this algorithm are the following:		The high level goals of this algorithm are the following:
	o Very fast convergence for single simple events (link failure).		o Very fast convergence for a single event (e.g., link failure).
	o Fast convergence in general while the IGP stability is considered		o Slightly paced fast convergence for multiple proximate IGP events
	under control.		while IGP stability is considered acceptable.
	o A long delay when the IGP stability is considered out of control,		o Delayed convergence when the IGP stability is problematic. This
	in order to let all related process calm down.		will allow the IGP and related processes to conserve resources
			during the period of instability.
	o At any time, try to avoid using different SPF_TIMERS values for		o Always try to avoid different SPF_DELAY timers values across
	nodes in the area/level. Even though not all nodes will receive		different routers in the area/level. Even though not all routers
	IGP message at the same time (due to difference in distance from		will receive IGP messages at the same time (due to differences
	the source and due to different flooding implementations on the		both in the distance from the originator of the IGP event and in
	path from the source).		flooding implementations).
	3. Definitions and parameters		3. Definitions and parameters
	IGP events: An LSDB change requiring a new RIB computation (topology		IGP events: An IGP LSDB change requiring a new routing table
	change, prefix change, metric change). No distinction is done		computation. Examples are a topology change, a prefix change, a
	between the type of computation performed (e.g. full SPF, incremental		metric change on link or prefix...
	SPF, PRC). The type of computation is a local consideration.
	The SPF_DELAY timer can take the following values:		Routing table computation: computation of the routing table, by the
			IGP, using the IGP LSDB. No distinction is made between the type of
			computation performed. e.g., full SPF, incremental SPF, Partial Route
			Computation (PRC). The type of computation is a local consideration.
			This document may indifferently use the terms routing table
			computation or SPF computation.
	INITIAL_WAIT: a very small delay to quickly handle link failure.		The SPF_DELAY is the delay introduced between the IGP event and the
	e.g. 0 millisecond.		start of the routing table computation. It can take the following
			values:
	FAST_WAIT: a small delay to have a fast convergence. e.g. 50-100		INITIAL_WAIT: a very small delay to quickly handle link failure,
	millisecond. Note: we want to be fast, but as this failure requires		e.g., 0 milliseconds.
	multiple IGP events, being too fast increase the probability to
	receive additional IGP events just after the RIB computation.
	LONG_WAIT: a long delay as IGP is unstable. e.g. 2 seconds. Note:		FAST_WAIT: a small delay to have a fast convergence in case of
	let's bring calm in the IGP.		single component failure (node, SRLG..), e.g., 50-100 milliseconds.
			Note: we want to be fast, but as this failure results in multiple
			IGP events, being too fast increases the probability to receive
			additional network events immediately after the SPF computation.
	The TIME_TO_CONVERGE timer is the time to learn all the IGP events		LONG_WAIT: a long delay when the IGP is unstable, e.g., 2 seconds.
	related to a single failure (e.g. node failure, SRLG failure). e.g. 1		Note: Allow the IGP network to stabilize.
	second. It's mostly dependent on variation of failure detection
	times between all nodes which are neighbour to the failure, and then
	may depend on different flooding algorithms of nodes in the network.
	The HOLD_DOWN timer is the time needed with no IGP events received,		The TIME_TO_LEARN timer is the maximum duration typically needed to
	before considering that the IGP is quiet again and we can set the		learn all the IGP events related to a single component failure (e.g.,
	SPF_DELAY back to INITAL_WAIT. e.g. 5 seconds.		router failure, SRLG failure), e.g., 1 second. It's mostly dependent
			on variation of failure detection times between all routers that are
			adjacent to the failure. Additionally, it may depend on the
			different flooding implementations for routers in the network.
	4. Principle of SPF delay algorithm		The HOLD_DOWN timer is the time needed with no received IGP events
			before considering the IGP to be stable again, allowing the SPF_DELAY
			to be restored to INITIAL_WAIT. e.g., 3 seconds.
	The first IGP event is handled very quickly (INITIAL_WAIT) in order		4. Principles of SPF delay algorithm
	to be very reactive for the first event if it only needs one IGP
	event (e.g. link failure, prefix change).
	If more IGP events are received quickly after, we consider that they		For this first IGP event, we assume that there has been a single
	are related to the same single failure, and handle the IGP events		simple change in the network which can be taken into account using a
	relatively quickly (FAST_WAIT) during the time needed to receive all		single routing computation (e.g., link failure, prefix (metric)
	the IGP events related to the failure (TIME_TO_CONVERGE).		change) and we optimize for very fast convergence, delaying the
			routing computation by INITIAL_WAIT. Under this assumption, there is
			no benefit in delaying the routing computation. In a typical
			network, this is the most common type of IGP event. Hence, it makes
			sense to optimize this case.
	If IGP events are still received after this time, then the network is		If subsequent IGP events are received in a short period of time
	presumably experiencing multiple independent failures and the while		(TIME_TO_LEARN), we then assume that a single component failed, but
	waiting for its stability, the computations are delayed for a longer		that this failure requires the knowledge of multiple IGP events in
	time (LONG_WAIT).		order for the IGP routing to converge. Under this assumption, we
			want fast convergence since this is a normal network situation.
			However, there is a benefit in waiting for all IGP events related to
			this single component failure so that the IGP can compute the post-
			failure routing table in a single route computation. In this
			situation, we delay the routing computation by FAST_WAIT.
	Note: previous SPF delay algorithms used to count the number of RIB		If IGP events are still received after TIME_TO_LEARN seconds from the
	computations. However, as all nodes may receive the LSP events in a		initial IGP event, then the network is presumably experiencing
	different way we cannot assume that all nodes will perform the same		multiple independent failures and while waiting for network
	number of SPF computations or that they will schedule them at the		stability, the computations are delayed for a longer time represented
	same time. For example, assuming that the SPF delay is 50 ms, node		by LONG_WAIT. This SPF_delay is kept until no IGP events are
	R1 may receive 3 IGP events (E1, E2, E3) in those 50 ms and hence		received for HOLD_DOWN seconds.
	will perform a single routing computation. While another node R2 may
	only receive 2 events (E1, E2) in those 50ms and hence will schedule
	another routing computation when further receiving E3. That's why
	this document prefers to define a time limit (TIME_TO_CONVERGE) since
	the first event, rather than a number of routing computations.
	5. Specification of SPF delay algorithm		Note: previous SPF delay algorithms used to count the number of SPF
			computations. However, as all routers may receive the IGP events at
			different times, we cannot assume that all routers will perform the
			same number of SPF computations or that they will schedule them at
			the same time. For example, assuming that the SPF delay is 50 ms,
			router R1 may receive 3 IGP events (E1, E2, E3) in those 50 ms and
			hence will perform a single routing computation. While another
			router R2 may only receive 2 events (E1, E2) in those 50 ms and hence
			will schedule another routing computation when receiving E3. That's
			why this document defines a time (TIME_TO_LEARN) from the initial
			event detection/reception as opposed to defining the number of SPF
			computations to determine when the IGP is unstable.
	When the previous IGP events is more than HOLD_DOWN ago:		5. Specification of the SPF delay algorithm
			When no IGP events have occurred during the HOLD_DOWN interval:
	o The IGP is set to the QUIET state.		o The IGP is set to the QUIET state.
	When the IGP is in the QUIET state and an IGP event is received:		When the IGP is in the QUIET state and an IGP event is received:
	o The time of this first IGP event is stored in FIRST_EVENT_TIME.		o The time of this first IGP event is stored in FIRST_EVENT_TIME.
	o The next RIB computation time is set to LSP receive time +		o The next routing table computation is scheduled at: this IGP event
	INITIAL_WAIT.		received time + INITIAL_WAIT.
	o The IGP is set to the FAST_WAIT state.		o The IGP is set to the FAST_WAIT state.
	When the IGP is in the FAST_WAIT state and an IGP event is received:		When the IGP is in the FAST_WAIT state and an IGP event is received:
	o If more than TIME_TO_CONVERGE has passed since FIRST_EVENT_TIME,		o If more than the TIME_TO_LEARN interval has passed since
	then the IGP is set to the HOLD_DOWN state.		FIRST_EVENT_TIME, then the IGP is set to the HOLD_DOWN state.
	o If the next RIB_computation time is in the past, set the next RIB		o If a routing table computation is not already scheduled, one is
	computation time to LSP receive time + FAST_WAIT.		scheduled at: this IGP event received time + FAST_WAIT.
	When the IGP is in the HOLD_DOWN state and an IGP event is received:		When the IGP is in the HOLD_DOWN state and an IGP event is received:
	o If the next RIB_computation time is in the past, set the next RIB		o If a routing table computation is not already scheduled, one is
	computation time to LSP receive time + LONG_WAIT.		scheduled at: this IGP event received time + LONG_WAIT.
	6. Impact on micro-loops		6. Parameters
	Micro-loops during IGP convergence are due to a non synchronized or		All the parameters MUST be configurable. All the delays
	non ordered update of the forwarding information tables (FIB)		(INITIAL_WAIT, FAST_WAIT, LONG_WAIT, TIME_TO_LEARN, HOLD_DOWN) SHOULD
	[RFC5715] [RFC6976] [I-D.litkowski-rtgwg-spf-uloop-pb-statement].		be configurable at the millisecond granularity. They MUST be
	FIB are installed after multiple steps such as SPF wait time, SPF		configurable at least at the tenth of second granularity. The
	computation, FIB distribution and FIB update. This document only		configurable range for all the parameters SHOULD be at least from 0
	address the first contribution. This standardized procedure reduces		milliseconds to 60 seconds.
	the probability and/or duration of micro-loops when the IGP
	experience multiple consecutive events. It does not remove all
	micro-loops. However, it is beneficial and its cost seems limited
	compared to full solutions such as [RFC5715] or [RFC6976].
	7. IANA Considerations		This document does not propose default values for the parameters
			because these values are expected to be context dependent.
			Implementations are free to propose their own default values.
			When setting the (default) values, one SHOULD consider the customer's
			or their applications' requirements, the computational power of the
			routers, the size of the network, and, in particular, the number of
			IP prefixes advertised in the IGP, the frequency and number of IGP
			events, the number of protocols reactions/computations triggered by
			IGP SPF (e.g., BGP, PCEP, Traffic Engineering CSPF, Fast ReRoute
			computations).
			Note that some or all of these factors may change over the life of
			the network. In case of doubt, it's RECOMMENDED to play it safe and
			start with safe, i.e., longer timers.
			For the standard algorithm to be effective in mitigating micro-loops,
			it is RECOMMENDED that all routers in the IGP domain, or at least all
			the routers in the same area/level, have exactly the same configured
			values.
			7. Impact on micro-loops
			Micro-loops during IGP convergence are due to a non-synchronized or
			non-ordered update of the forwarding information tables (FIB)
			[RFC5715] [RFC6976] [I-D.ietf-rtgwg-spf-uloop-pb-statement]. FIBs
			are installed after multiple steps such as SPF wait time, SPF
			computation, FIB distribution, and FIB update. This document only
			addresses the first contribution. This standardized procedure
			reduces the probability and/or duration of micro-loops when the IGP
			experience multiple proximate events. It does not prevent all micro-
			loops. However, it is beneficial and its cost seems limited compared
			to full solutions such as [RFC5715] or [RFC6976].
			8. IANA Considerations
	No IANA actions required.		No IANA actions required.
	8. Security considerations		9. Security considerations
	This document has no impact on the security of the IGP.		This algorithm presented in this document does not in any way
			compromise the security of the IGP. In fact, the HOLD_DOWN state may
			mitigate the effects of Denial-of-Service (DOS) attacks generating
			many IGP events.
	9. Acknowledgements		10. Acknowledgements
	We would like to acknowledge Hannes Gredler, Les Ginsberg and Pierre		We would like to acknowledge Les Ginsberg, Uma Chunduri, and Mike
	Francois for the discussions related to this document.		Shand for the discussions and comments related to this document.
	10. References		11. References
	10.1. Normative References		11.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, March 1997.
	10.2. Informative References		11.2. Informative References
	[I-D.litkowski-rtgwg-spf-uloop-pb-statement]		[I-D.ietf-rtgwg-spf-uloop-pb-statement]
	Litkowski, S., "Link State protocols SPF trigger and delay		Litkowski, S., "Link State protocols SPF trigger and delay
	algorithm impact on IGP microloops", draft-litkowski-		algorithm impact on IGP microloops", draft-ietf-rtgwg-spf-
	rtgwg-spf-uloop-pb-statement-02 (work in progress), March		uloop-pb-statement-00 (work in progress), May 2015.
	2015.
	[ISO10589-Second-Edition]		[ISO10589-Second-Edition]
	International Organization for Standardization,		International Organization for Standardization,
	"Intermediate system to Intermediate system intra-domain		"Intermediate system to Intermediate system intra-domain
	routeing information exchange protocol for use in		routeing information exchange protocol for use in
	conjunction with the protocol for providing the		conjunction with the protocol for providing the
	connectionless-mode Network Service (ISO 8473)", ISO/IEC		connectionless-mode Network Service (ISO 8473)", ISO/IEC
	10589:2002, Second Edition, Nov 2002.		10589:2002, Second Edition, Nov 2002.
	[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.		[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
	[RFC5715] Shand, M. and S. Bryant, "A Framework for Loop-Free		[RFC5715] Shand, M. and S. Bryant, "A Framework for Loop-Free
	Convergence", RFC 5715, January 2010.		Convergence", RFC 5715, January 2010.
	[RFC6976] Shand, M., Bryant, S., Previdi, S., Filsfils, C.,		[RFC6976] Shand, M., Bryant, S., Previdi, S., Filsfils, C.,
	Francois, P., and O. Bonaventure, "Framework for Loop-Free		Francois, P., and O. Bonaventure, "Framework for Loop-Free
	Convergence Using the Ordered Forwarding Information Base		Convergence Using the Ordered Forwarding Information Base
	(oFIB) Approach", RFC 6976, July 2013.		(oFIB) Approach", RFC 6976, July 2013.
	Author's Address		Authors' Addresses
	Bruno Decraene		Bruno Decraene
	Orange		Orange
	38 rue du General Leclerc		38 rue du General Leclerc
	Issy Moulineaux cedex 9 92794		Issy Moulineaux cedex 9 92794
	France		France
	Email: bruno.decraene@orange.com		Email: bruno.decraene@orange.com
			Stephane Litkowski
			Orange Business Service
			Email: stephane.litkowski@orange.com
			Hannes Gredler
			Juniper Networks, Inc.
			1194 N. Mathilda Ave.
			Sunnyvale, CA 94089
			US
			Email: hannes@juniper.net
			Acee Lindem
			Cisco Systems
			301 Midenhall Way
			Cary, NC 27513
			USA
			Email: acee@cisco.com
			Pierre Francois
			IMDEA Networks Institute
			1194 N. Mathilda Ave.
			Leganes
			ES
			Email: pierre.francois@imdea.org
End of changes. 46 change blocks.
	134 lines changed or deleted		200 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/