idnits 2.17.1 draft-decraene-rtgwg-backoff-algo-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (July 3, 2014) is 3577 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Outdated reference: A later version (-02) exists of draft-litkowski-rtgwg-spf-uloop-pb-statement-00 Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group B. Decraene 3 Internet-Draft Orange 4 Intended status: Standards Track July 3, 2014 5 Expires: January 4, 2015 7 Back-off SPF algorithm for link state IGP 8 draft-decraene-rtgwg-backoff-algo-00 10 Abstract 12 This document defines a standard algorithm to back-off link-state IGP 13 SPF computations. 15 This improves interoperability by reducing the probability and/or 16 duration of transient forwarding loops during the IGP convergence in 17 the area/level when the network reacts to multiple consecutive 18 events. 20 Requirements Language 22 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 23 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 24 document are to be interpreted as described in RFC 2119 [RFC2119]. 26 Status of This Memo 28 This Internet-Draft is submitted in full conformance with the 29 provisions of BCP 78 and BCP 79. 31 Internet-Drafts are working documents of the Internet Engineering 32 Task Force (IETF). Note that other groups may also distribute 33 working documents as Internet-Drafts. The list of current Internet- 34 Drafts is at http://datatracker.ietf.org/drafts/current/. 36 Internet-Drafts are draft documents valid for a maximum of six months 37 and may be updated, replaced, or obsoleted by other documents at any 38 time. It is inappropriate to use Internet-Drafts as reference 39 material or to cite them other than as "work in progress." 41 This Internet-Draft will expire on January 4, 2015. 43 Copyright Notice 45 Copyright (c) 2014 IETF Trust and the persons identified as the 46 document authors. All rights reserved. 48 This document is subject to BCP 78 and the IETF Trust's Legal 49 Provisions Relating to IETF Documents 50 (http://trustee.ietf.org/license-info) in effect on the date of 51 publication of this document. Please review these documents 52 carefully, as they describe your rights and restrictions with respect 53 to this document. Code Components extracted from this document must 54 include Simplified BSD License text as described in Section 4.e of 55 the Trust Legal Provisions and are provided without warranty as 56 described in the Simplified BSD License. 58 1. Introduction 60 Link state IGP, such as IS-IS [ISO10589-Second-Edition] and OSPF 61 [RFC2328], performs distributed computation on all nodes of the area/ 62 level. In order to have consistent routing tables across the 63 network, such distributed computation requires that all routers have 64 the same vision of the network (Link State DataBase (LSDB)) and 65 perform their computation at the same time. 67 In general, when the network is stable, there is a desire to compute 68 the new SPF as soon as the failure is known, in order to quickly 69 route around the failure. However, when the network is experiencing 70 multiple consecutive failures over a short period of time, there is a 71 desire to limit the frequency of SPF computations. Indeed, this 72 allow reducing the control plane resources used by IGP and all 73 protocols/sub system reacting on it such as LDP, RSVP-TE, BGP, Fast 74 ReRoute computations, FIB updates..., reduce the churn on nodes and 75 in the network, in particular reduce side effects such as micro-loops 76 which may happen during each IGP convergence. 78 To allow for this, some back-off algorithm have been implemented. 79 Different implementations choose different algorithms, hence in a 80 multi-vendor network, it's not possible to enforce that all routers 81 triggers their SPF computation after the same waiting delay. This 82 situation increases the average differential delay between routers 83 end of RIB computation. It also increases the probability that 84 different routers compute their RIB based on a different LSDB. Both 85 increases the probability and/or duration of micro-loops. 87 To allow for multi-vendors networks having all the routers delaying 88 their SPF for the same duration, this document specifies a 89 standardized algorithm. The algorithm is proposed based on its 90 popularity on existing implementations and its large deployed base. 91 It's not implied that this algorithm is the best. Implementations 92 may offer alternative optional algorithms. 94 2. Exponential back off algorithm 96 This backoff algorithm introduces a delay between the event 97 triggering a new RIB computation and the start of the computation. 99 The initial wait time is set to INITIAL_WAIT. 101 Subsequent wait times are exponentially delayed by INCREMENTAL_WAIT, 102 2*INCREMENTAL_WAIT, 4* INCREMENTAL_WAIT, 8* INCREMENTAL_WAIT... up to 103 reaching the maximum value MAX_WAIT. 105 If no new trigger is received for two times MAX_WAIT_TIME, the delay 106 is set back to INITIAL_WAIT. 108 The back off algorithm makes no difference regarding the type of 109 computation performed to compute the updated RIB. For example no 110 distinction is made between a full SPF, an incremental SPF or a PRC 111 computation. 113 3. Parameters 115 INITIAL_WAIT SHOULD be configurable from 0 ms to at least 5 s. 117 INCREMENTAL_WAIT SHOULD be configurable from 0 ms to at least 5 s. 119 MAX_WAIT SHOULD be configurable from 0 ms to at least 10 s. 121 In this version of the draft, it's proposed to not define default 122 values because such values are subject to change over time as 123 hardware and software improve and as customers requirements increase. 124 In addition, such timers may be very network dependant. 126 4. Impact on micro-loops 128 Micro-loops during IGP convergence are due to a non synchronized or 129 non ordered update of the forwarding information tables (FIB) RFC 130 5715 [RFC5715] RFC 6976 [RFC6976] draft.litkowski-rtgwg-spf-uloop-pb- 131 statement [I-D.litkowski-rtgwg-spf-uloop-pb-statement]. FIB are 132 installed after multiple steps such as SPF wait time, SPF 133 computation, FIB distribution and FIB update. This document only 134 address the first contribution. This standardized procedure reduces 135 the probability and/or duration of micro-loops when the IGP 136 experience multiple consecutive events. It does not remove all 137 micro-loops. However, it is beneficial and its cost seems limited 138 compared to full solutions such as RFC 5715 [RFC5715] or RFC 6976 139 [RFC6976]. 141 5. IANA Considerations 143 No IANA actions required. 145 6. Security considerations 147 This document has no impact on the security of the IGP. 149 7. Acknowledgements 151 We would like to acknowledge Hannes Gredler and Les Ginsberg for the 152 discussions related to this document. 154 8. References 156 8.1. Normative References 158 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 159 Requirement Levels", BCP 14, RFC 2119, March 1997. 161 8.2. Informative References 163 [I-D.litkowski-rtgwg-spf-uloop-pb-statement] 164 Litkowski, S., "Link State protocols SPF trigger and delay 165 algorithm impact on IGP microloops", draft-litkowski- 166 rtgwg-spf-uloop-pb-statement-00 (work in progress), June 167 2014. 169 [ISO10589-Second-Edition] 170 International Organization for Standardization, 171 "Intermediate system to Intermediate system intra-domain 172 routeing information exchange protocol for use in 173 conjunction with the protocol for providing the 174 connectionless-mode Network Service (ISO 8473)", ISO/IEC 175 10589:2002, Second Edition, Nov 2002. 177 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. 179 [RFC5715] Shand, M. and S. Bryant, "A Framework for Loop-Free 180 Convergence", RFC 5715, January 2010. 182 [RFC6976] Shand, M., Bryant, S., Previdi, S., Filsfils, C., 183 Francois, P., and O. Bonaventure, "Framework for Loop-Free 184 Convergence Using the Ordered Forwarding Information Base 185 (oFIB) Approach", RFC 6976, July 2013. 187 Author's Address 189 Bruno Decraene 190 Orange 191 38 rue du General Leclerc 192 Issy Moulineaux cedex 9 92794 193 France 195 Email: bruno.decraene@orange.com