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]