idnits 2.17.1 draft-zinin-microloop-analysis-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1.a on line 19. -- Found old boilerplate from RFC 3978, Section 5.5 on line 468. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 441. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 448. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 454. ** The document seems to lack an RFC 3978 Section 5.1 IPR Disclosure Acknowledgement. ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead of the newer disclaimer which includes the IETF Trust according to RFC 4748. ** The document uses RFC 3667 boilerplate or RFC 3978-like boilerplate instead of verbatim RFC 3978 boilerplate. After 6 May 2005, submission of drafts without verbatim RFC 3978 boilerplate is not accepted. The following non-3978 patterns matched text found in the document. That text should be removed or replaced: This document is an Internet-Draft and is subject to all provisions of Section 3 of RFC 3667. By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 9 longer pages, the longest (page 2) being 60 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 10 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (October 2004) is 7132 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) == Missing Reference: 'OSPF' is mentioned on line 48, but not defined == Missing Reference: 'ISIS' is mentioned on line 48, but not defined == Missing Reference: 'IPFRR' is mentioned on line 253, but not defined == Unused Reference: 'Ref1' is defined on line 423, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. 'Ref1' Summary: 9 errors (**), 0 flaws (~~), 8 warnings (==), 8 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group Alex Zinin 3 Internet Draft Alcatel 4 Expiration Date: April 2005 October 2004 5 File name: draft-zinin-microloop-analysis-00.txt 7 Analysis and Minimization of Microloops in 8 Link-state Routing Protocols 10 draft-zinin-microloop-analysis-00.txt 12 Status of this Memo 14 This document is an Internet-Draft and is subject to all provisions 15 of section 3 of RFC 3667. By submitting this Internet-Draft, each 16 author represents that any applicable patent or other IPR claims of 17 which he or she is aware have been or will be disclosed, and any of 18 which he or she become aware will be disclosed, in accordance with 19 RFC 3668. 21 Internet Drafts are working documents of the Internet Engineering 22 Task Force (IETF), its Areas, and its Working Groups. Note that other 23 groups may also distribute working documents as Internet Drafts. 25 Internet-Drafts are draft documents valid for a maximum of six months 26 and may be updated, replaced, or obsoleted by other documents at any 27 time. It is inappropriate to use Internet-Drafts as reference 28 material or to cite them other than a "work in progress." 30 The list of current Internet-Drafts can be accessed at 31 http://www.ietf.org/ietf/1id-abstracts.txt 33 The list of Internet-Draft Shadow Directories can be accessed at 34 http://www.ietf.org/shadow.html. 36 Abstract 38 Link-state routing protocols (e.g. OSPF or IS-IS) are known to 39 converge to a loop-free state within a finite period of time after a 40 failure. It is normal, however, to observe short-term loops during 41 the period of failure propagation, route recalculation, and 42 forwarding table update, due to the asynchronous nature of link-state 43 protocol operation. This document provides an analysis of formation 44 of such microloops and suggests simple mechanisms to minimize them. 46 1 Introduction 48 Link-state routing protocols, such as [OSPF] and [ISIS] converge to a 49 loop-free state within a finite period of time after a failure. 50 Additional failures postpone the convergence, but do not get in its 51 way. 53 During the period of convergence, however, link-state protocols 54 exhibit short-term routing table inconsistencies caused by the 55 protocol's asynchronous nature. These incornsistencies may cause 56 short-term packet loops, also known as microloops. For example, see a 57 sample network in Figure 1. 59 +--+ 1 +--+ 60 |A |---------|B | 61 +--+ +--+ 62 | \ 10 | 63 5| ------ |1 64 | \ | 65 +--+ 10 \+--+ 66 |E |---------|C | 67 +--+ +--+ 68 \_ / 69 5 \ /1 (failure) 70 +--+ 71 |D | 72 +--+ 74 Figure 1. Microloop example 76 We are interested in routers A and B and their best paths towards D. 77 Before failure, B's best path to D is B-C-D with cost 2, and A's best 78 path is A-B-C-D with cost 3. When link C-D fails, both C and D 79 announce their link state information with link C-D missing. Within 80 finite period of time, both A and B shall receive the topology update 81 and converge on it, installing new best paths: A-E-D (10) for A, and 82 B-A-E-D (11) for B. However, if, due to timing differences, B 83 calculates and installs its new best path through A before A has a 84 chance to switch from B to E, a microloop will form between A and B 85 for the duration of time required for A to complete its routing table 86 update. 88 Similar microloops may form when other topological changes happen in 89 the network. For example, a new link or a node is added, a link cost 90 is changed, etc. In summary, whenever a topological change in the 91 network results in changes of the shortest path three (SPT) for more 92 than one node, it is possible for the network to exhibit temporary 93 loops. 95 This document provides an analysis of microloop formation. 96 Specifically, we categorize different types of reconvergence 97 scenarios, and explore their properties. We then show that in certain 98 scenaiors microloops do not form, in others they can be eliminated 99 using simple techniques described in this document, and define 100 scenarios where more sophisticated loop avoidance mechanisms may be 101 necessary. 103 2 Analysis 105 To analyse the behavior of a network during reconvergence, we look at 106 a given router and its neighbors before failure and during the 107 transition to the new routes. More specifically, we analyse whether 108 switching to the new routing information can result in loop formation 109 or not. 111 2.1 Terminology 113 The following terms are used in the draft. 115 Downstream neighbor 116 Neighbor N of router S is considered S's downstream neighbor 117 for destination D, if Dopt(N, D) < Dopt(S, D) 119 Primary neighbor 120 Neighbor N of router S is considered S's primary neighbor for 121 destination D, if N provides the shortest path to D according 122 to the SPF calculation. 124 Loop-free neighbor 125 Neighbor N of router S is considered S's loop-free neighbor 126 for destination D, if Dopt(N, D) < Dopt(N, S) + Dopt(S, D). 127 Note that a loop-free neighbor may be, for example, router's 128 primary before or after failure. 130 2.2 Next hop safety condition 132 We start the analysis with the following observation: 134 When router X learns about a topology change and starts using 135 neighbor Y as its new primary neighbor for a given destination, a 136 microloop between X and Y can only form if the topology before 137 failure of topology after failure are such that Y uses X as its 138 primary neighbor for the same destination. 140 Indeed, if the topologies before and after failure are such that Y 141 does not use X as it's next hop, then there is no moment in time 142 before Y learned about the failure or after it learned about it 143 when it would forward traffic to X. Hence, at least one of the two 144 topologies must be such that Y uses X as its next hop for a 145 microloop between X and Y to form. 147 Based on the above, we can define a safety condition for neighbor Y 148 of router X that has just learned about a topology change. Note that 149 the condition must satisfy the topological criteria above, and be 150 non-recursive, i.e. not lead to loops if both X and Y follow it. 152 Next-hop safety condition: 154 After a topology change, it is safe for router X to switch to 155 neigbor Y as its next-hop for a specific destination if the 156 path through Y satisfies both of the following criteria: 158 1. X considered Y as its loop-free neighbor based on the 159 topology before change AND 161 2: X considers Y as its downstream neighbor based on the 162 topology after change. 164 The first requirement ensures that Y has not been forwarding 165 traffic to X before the change occured and both X and Y used 166 old topology. The second requirement makes sure Y does not 167 forward traffic to X when Y learns the new topology. 169 The difference in the two characteristics is there to make 170 sure that X and Y do not recursively consider each other as 171 safe next-hops when they learn about the failure. 173 3.2 Transition types 175 Here, we analyse different types of scenarios that a given router may 176 find itself in after learning about a topology change. 178 For each topological change, the network will have three major types 179 of nodes categorized by the degree of safety of their old primary, 180 new primary, and other neighbors. 182 Type A 184 Routers whose new primary next-hops after the topology change 185 are safe and transition to them will not create a microloop. 186 Two subtypes are recognized: 188 A1: Routers whose SPT hasn't been affected by the topology 189 change, and hence their primaries haven't changed. 191 A2: Routers whose new primary satisfies the safety condition 193 Type B 195 Routers whose new primary next-hops after the topology change 196 do not satisfy the safety condition, but that have at least 197 one other neighbor that does. Note that such a neighbor can be 198 the router's old primary (type B1) or a neighbor that is nei- 199 ther old nor new primary (type B2). 201 Type C 203 Routers that have no neighbor that satisfies the safety condi- 204 tion. 206 It is clear that type-A routers can immediately switch to their new 207 primary next hops once they are calculated after the topology change. 209 It can also be shown that if type-B routers do not immediately switch 210 to their new primaries, but use their safe next-hops for some time, 211 switching to the new primaries later will not create loops, provided 212 that their downstream routers have also switched to the safe hops or 213 have already switched to the new primaries. 215 The following section defines this mechanism more formally. 217 3.3 Basic loop prevention mechanism 219 On discovering the topology change and calculating the new SPT, each 220 router checks the safety status of each neighbor using the condition 221 in section 3.1, calculates the new routes, and applies the following 222 logic for each route depending on the type of role it finds itself 223 in: 225 Type A: 226 The new route can be installed immediately. 228 Type B: 229 The new route is installed with one or more temporary next- 230 hops that satisfy the safety condition. The router uses these 231 safe next-hops for time DELAY_TYPEB, and only then installs 232 the new primary next-hops. 234 Type C: 235 Installation of the new route is delayed by time DELAY_TYPEC. 237 Until then, the router continues to use its old next-hops. 239 DELAY_TYPEB and DELAY_TYPEC are two configurable constants. They 240 should be configured with the same value on all routers in the net- 241 work and such that following equation is true: 243 DELAY_TYPEB > DELAY_TYPEC > fault-propagation-time 245 where fault-propagation-time is the time it is expected to take 246 routers in the network to propagate new link-state information, cal- 247 culate the new SPT, check the safety condition of the neighbors, and 248 install required FIB entries. 250 Suggested default values for DELAY_TYPEB and DELAY_TYPEC are 4 and 2 251 seconds correspondingly. 253 Note that if routers in the network already implement [IPFRR], this 254 algorithm adds minimal complexity. Its other advantage is that it 255 does not require explicit ordering or signaling between routers. Each 256 router determines its type relative to the experienced failure and 257 decides how to transition. 259 The above algorithm minimizes the probability of loop formation. More 260 specifically, loops will only be possible when two neighboring 261 routers both experience the type C condition after the topology 262 change. Appendix A shows that transitions between A-A, A-B, A-C, and 263 B-C routers are loop-free. 265 2.6 Coverage analysis 266 268 3 Security Considerations 269 271 Appendix A. Loop formation analysis 273 S is the calculating router discovering the failure through a link- 274 state update. P is the old primary, NP is the new primary. 276 BF: 277 <------ 278 [P]----------------[S]----------------[NP] 279 ...>? 281 AF: 283 ------> 284 [P]----------------[S]----------------[NP] 285 ?<... 287 To analyze possible loop formation, we need to check the following: 289 1) if it is possible for P to start forwarding packets to S 290 before S switches to NP 292 2) if it is possible for NP to be forwarding packets back to S 293 before or after S starts using it 295 Assumptions are that type-As switch-over to NP immediately, and type- 296 Bs and type-Cs wait certain amount of time so that: 298 DELAY_TYPEB > DELAY_TYPEC > fault-propagation-time 300 1. S is type A: 302 BF analysis: 304 1.1 If P is another type-A, then S cannot be its new primary, since 305 S has not been P's LFA before (since it's been fwd'ing through P). 306 Hence, P will not route through S AF, and the will be no loops 307 between P and S. 309 1.2 If P is a type-B, then S hasn't been P's LF neighbor BF, and P 310 will not forward through S at least for DELAY_TYPEB, which gives S 311 enough time to switch to NP. After DELAY_TYPEB P may start using S 312 as it's new primary. 314 1.3 If P is a type-C, then it hasn't been forwarding traffic to S 315 BF, and will not use S as its new primary at least for DELAY_TYPEC, 316 which should give S enough time to switch to NP. 318 1.4 Consequently, no loops will form between a type-A node and it's 319 old primary before the type-A nodes switches to its new primary. 321 AF analysis: 323 1.5 Regardless of its type, NP has not been forwarding packets to S 324 BF and will not do so AF by definition of type-A. 326 1.6 Consequently, no loops will form between a type-A node and it's 327 new primary before or after the type-A nodes switches to it. 329 2. S is type B: 331 BF analysis: 333 2.1 If P is a type-A, then similarly to 1.1 above, there will be no 334 routes between P and S. 336 2.2 If P is another type-B, then similarly to 1.2, S will not be 337 used by P for at least DELAY_TYPEB, and S will have enough time to 338 switch to its safe hops or NP. 340 2.3 If P is a type-C, then similarly to 1.3, S hasn't been receiv- 341 ing traffic from P BF, and will not AF for at least DELAY_TYPEC, 342 which should give S enough time to switch to its safe hops or NP. 344 2.4 Consequently, no loops will form between a type-B node and it's 345 old primary before the type-B nodes switches to its new primary. 347 AF analysis: 349 2.5 If NP is a type-A, then because of the DELAY_TYPEB NP must have 350 had enough time to switch to its new NP, which cannot be S by defi- 351 nition of SPT considering that NP is S's new nexthop in the SPT AF. 353 2.6 If NP is another type-B, then because of DELAY_TYPEB, NP must 354 have had enough time to switch from its old primary and can equally 355 likely be routing through either its safe hops, or its new primary. 356 Neither of the two can be S by definition of a downstream node (for 357 safe hops) and SPT (for new primary). 359 2.7 If NP is a type-C, then because DELAY_TYPEB > DELAY_TYPEC, NP 360 must have had enough time to switch to its new primary, which can't 361 be S by definition of SPT and considering that NP is S's nexthop in 362 the SPT AF. 364 2.8 Consequently, no loops will form between a type-B node and it's 365 new primary before or after the type-A nodes switches to it. 367 3. S is type C: 369 BF analysis: 371 3.1 If P is a type-A, then similarly to 1.1 before, S has not been 372 P's LF neighbor before and hence won't be its new primary, so no 373 loops will form between P and S. 375 3.2 If P is a type-B, then similarly to 1.2, S will not be used by 376 P for at least DELAY_TYPEB, and because DELAY_TYPEB > DELAY_TYPEC, 377 S will have enough time to switch to NP. 379 3.3 If P is another type-C, then it hasn't been using S as its pri- 380 mary BF, but it is possible for P to consider S as its new primary 381 AF and to install routes before S after their DELAY_TYPEC expires. 382 Hence, a microloop is possible between P and S. 384 3.4 Consequently, a microloop between a type-C node and its old 385 primary is possible only if the old primary is also a type-C node 386 and it considers S as its new primary AF. Note that DELAY_TYPEC 387 only delays probably loop formation, but does not increase its 388 duration, as both neighboring routers are using the same delay. 390 AF analysis: 392 3.5 If NP is a type-A, then because of the DELAY_TYPEC NP must have 393 had enough time to switch to its new NP, which cannot be S by defi- 394 nition of SPT considering that NP is S's new nexthop in the SPT AF. 396 3.6 If NP is a type-B, then because of DELAY_TYPEC, NP must have 397 had enough time to switch to its safe hops, which can't be S by 398 definition of a downstream node and considering that NP is S's new 399 SPT next-hop. 401 3.7 If NP is another type-C, a loop is possible if S's DELAY_TYPEC 402 expires before that on NP and NP has been using S as its primary 403 BF. 405 3.8 Consequently, a microloop between a type-C node and its new 406 primary is possible only if the new primary is also a type-C node 407 and S was NP's primary BF. 409 4. Given the above analysis, it can be noted that, for a given fail- 410 ure, presence of single type-C nodes in the network does not create 411 microloops. 412 It is the C-C combination that introduces this potential. 414 Acknowledgements 416 The author would like to thank Don Fedyk, Chris Martin, Mike Shand, 417 and Alex Audu, for the discussion on this idea. Special thanks go to 418 Alia Atlas who, among other things, was instrumental in fine-tuning 419 the safety condition. 421 References 423 [Ref1] Ref1 full 425 Author's Address 426 Alex Zinin 427 Alcatel 428 701 E Middlefield Rd 429 Mountain View, CA 94043 430 E-mail: zinin@psg.com 432 IPR Disclaimer 434 The IETF takes no position regarding the validity or scope of any 435 Intellectual Property Rights or other rights that might be claimed 436 to pertain to the implementation or use of the technology 437 described in this document or the extent to which any license 438 under such rights might or might not be available; nor does it 439 represent that it has made any independent effort to identify any 440 such rights. Information on the procedures with respect to rights 441 in RFC documents can be found in BCP 78 and BCP 79. 443 Copies of IPR disclosures made to the IETF Secretariat and any 444 assurances of licenses to be made available, or the result of an 445 attempt made to obtain a general license or permission for the use 446 of such proprietary rights by implementers or users of this 447 specification can be obtained from the IETF on-line IPR repository 448 at http://www.ietf.org/ipr. 450 The IETF invites any interested party to bring to its attention 451 any copyrights, patents or patent applications, or other 452 proprietary rights that may cover technology that may be required 453 to implement this standard. Please address the information to the 454 IETF at ietf-ipr@ietf.org. 456 Full Copyright Statement 458 Copyright (C) The Internet Society (2004). This document is subject 459 to the rights, licenses and restrictions contained in BCP 78, and 460 except as set forth therein, the authors retain all their rights. 462 This document and the information contained herein are provided on an 463 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 464 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 465 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 466 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 467 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 468 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.