Network Working Group B. Decraene
Internet-Draft Orange
Intended status: Standards Track July 3, 2014
Expires: January 4, 2015
Back-off SPF algorithm for link state IGP
draft-decraene-rtgwg-backoff-algo-00
Abstract
This document defines a standard algorithm to back-off link-state IGP
SPF computations.
This improves interoperability by reducing the probability and/or
duration of transient forwarding loops during the IGP convergence in
the area/level when the network reacts to multiple consecutive
events.
Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119].
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on January 4, 2015.
Copyright Notice
Copyright (c) 2014 IETF Trust and the persons identified as the
document authors. All rights reserved.
Decraene Expires January 4, 2015 [Page 1]
Internet-Draft SPF back-off algo July 2014
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
1. Introduction
Link state IGP, such as IS-IS [ISO10589-Second-Edition] and OSPF
[RFC2328], performs distributed computation on all nodes of the area/
level. In order to have consistent routing tables across the
network, such distributed computation requires that all routers have
the same vision of the network (Link State DataBase (LSDB)) and
perform their computation at the same time.
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
route around the failure. However, when the network is experiencing
multiple consecutive failures over a short period of time, there is a
desire to limit the frequency of SPF computations. Indeed, this
allow reducing the control plane resources used by IGP and all
protocols/sub system reacting on it such as LDP, RSVP-TE, BGP, Fast
ReRoute computations, FIB updates..., reduce the churn on nodes and
in the network, in particular reduce side effects such as micro-loops
which may happen during each IGP convergence.
To allow for this, some back-off algorithm have been implemented.
Different implementations choose different algorithms, hence in a
multi-vendor network, it's not possible to enforce that all routers
triggers their SPF computation after the same waiting delay. This
situation increases the average differential delay between routers
end of RIB computation. It also increases the probability that
different routers compute their RIB based on a different LSDB. Both
increases the probability and/or duration of micro-loops.
To allow for multi-vendors networks having all the routers delaying
their SPF for the same duration, this document specifies a
standardized algorithm. The algorithm is proposed based on its
popularity on existing implementations and its large deployed base.
It's not implied that this algorithm is the best. Implementations
may offer alternative optional algorithms.
Decraene Expires January 4, 2015 [Page 2]
Internet-Draft SPF back-off algo July 2014
2. Exponential back off algorithm
This backoff algorithm introduces a delay between the event
triggering a new RIB computation and the start of the computation.
The initial wait time is set to INITIAL_WAIT.
Subsequent wait times are exponentially delayed by INCREMENTAL_WAIT,
2*INCREMENTAL_WAIT, 4* INCREMENTAL_WAIT, 8* INCREMENTAL_WAIT... up to
reaching the maximum value MAX_WAIT.
If no new trigger is received for two times MAX_WAIT_TIME, the delay
is set back to INITIAL_WAIT.
The back off algorithm makes no difference regarding the type of
computation performed to compute the updated RIB. For example no
distinction is made between a full SPF, an incremental SPF or a PRC
computation.
3. Parameters
INITIAL_WAIT SHOULD be configurable from 0 ms to at least 5 s.
INCREMENTAL_WAIT SHOULD be configurable from 0 ms to at least 5 s.
MAX_WAIT SHOULD be configurable from 0 ms to at least 10 s.
In this version of the draft, it's proposed to not define default
values because such values are subject to change over time as
hardware and software improve and as customers requirements increase.
In addition, such timers may be very network dependant.
4. 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) RFC
5715 [RFC5715] RFC 6976 [RFC6976] draft.litkowski-rtgwg-spf-uloop-pb-
statement [I-D.litkowski-rtgwg-spf-uloop-pb-statement]. FIB are
installed after multiple steps such as SPF wait time, SPF
computation, FIB distribution and FIB update. This document only
address the first contribution. This standardized procedure reduces
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 RFC 5715 [RFC5715] or RFC 6976
[RFC6976].
Decraene Expires January 4, 2015 [Page 3]
Internet-Draft SPF back-off algo July 2014
5. IANA Considerations
No IANA actions required.
6. Security considerations
This document has no impact on the security of the IGP.
7. Acknowledgements
We would like to acknowledge Hannes Gredler and Les Ginsberg for the
discussions related to this document.
8. References
8.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
8.2. Informative References
[I-D.litkowski-rtgwg-spf-uloop-pb-statement]
Litkowski, S., "Link State protocols SPF trigger and delay
algorithm impact on IGP microloops", draft-litkowski-
rtgwg-spf-uloop-pb-statement-00 (work in progress), June
2014.
[ISO10589-Second-Edition]
International Organization for Standardization,
"Intermediate system to Intermediate system intra-domain
routeing information exchange protocol for use in
conjunction with the protocol for providing the
connectionless-mode Network Service (ISO 8473)", ISO/IEC
10589:2002, Second Edition, Nov 2002.
[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
[RFC5715] Shand, M. and S. Bryant, "A Framework for Loop-Free
Convergence", RFC 5715, January 2010.
[RFC6976] Shand, M., Bryant, S., Previdi, S., Filsfils, C.,
Francois, P., and O. Bonaventure, "Framework for Loop-Free
Convergence Using the Ordered Forwarding Information Base
(oFIB) Approach", RFC 6976, July 2013.
Decraene Expires January 4, 2015 [Page 4]
Internet-Draft SPF back-off algo July 2014
Author's Address
Bruno Decraene
Orange
38 rue du General Leclerc
Issy Moulineaux cedex 9 92794
France
Email: bruno.decraene@orange.com
Decraene Expires January 4, 2015 [Page 5]