idnits 2.17.1 draft-bryant-shand-lf-conv-frmwk-02.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 on line 18. -- Found old boilerplate from RFC 3978, Section 5.5 on line 894. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 870. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 877. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 883. ** 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. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 7 longer pages, the longest (page 22) being 63 lines Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. 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 (Mar 2006) is 6614 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: 'RFC2119' is mentioned on line 48, but not defined == Missing Reference: 'RFC3036' is mentioned on line 109, but not defined ** Obsolete undefined reference: RFC 3036 (Obsoleted by RFC 5036) == Missing Reference: 'MPLS-TE' is mentioned on line 124, but not defined == Missing Reference: 'IPFRR' is mentioned on line 126, but not defined == Missing Reference: 'APPL' is mentioned on line 195, but not defined == Missing Reference: 'ZININ' is mentioned on line 809, but not defined == Missing Reference: 'TUNNEL' is mentioned on line 572, but not defined == Missing Reference: 'RFC791' is mentioned on line 542, but not defined == Missing Reference: 'LDP' is mentioned on line 558, but not defined == Missing Reference: 'TIMER' is mentioned on line 626, but not defined == Missing Reference: 'NTP' is mentioned on line 828, but not defined Summary: 4 errors (**), 0 flaws (~~), 14 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 INTERNET DRAFT A Framework for Loop-free Convergence Mar 2006 4 Network Working Group S. Bryant 5 Internet Draft M. Shand 6 Expiration Date: Sept 2006 Cisco Systems 8 Mar 2006 10 A Framework for Loop-free Convergence 11 13 Status of this Memo 15 By submitting this Internet-Draft, each author represents that any 16 applicable patent or other IPR claims of which he or she is aware 17 have been or will be disclosed, and any of which he or she becomes 18 aware will be disclosed, in accordance with Section 6 of BCP 79. 20 Internet-Drafts are working documents of the Internet Engineering 21 Task Force (IETF), its areas, and its working groups. Note that 22 other groups may also distribute working documents as 23 Internet-Drafts. 25 Internet-Drafts are draft documents valid for a maximum of six 26 months and may be updated, replaced, or obsoleted by other 27 documents at any time. It is inappropriate to use Internet-Drafts 28 as reference material or to cite them other than as "work in 29 progress." 31 The list of current Internet-Drafts can be accessed at 32 http://www.ietf.org/1id-abstracts.html 33 The list of Internet-Draft Shadow Directories can be accessed at 34 http://www.ietf.org/shadow.html 36 Abstract 37 This draft describes mechanisms that may be used to prevent or to 38 suppress the formation of micro-loops when an IP or MPLS network 39 undergoes topology change due to failure, repair or management 40 action. 42 Conventions used in this document 44 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 45 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in 46 this document are to be interpreted as described in RFC 2119 47 [RFC2119]. 49 Table of Contents 50 1. Introduction......................................................4 52 2. The Nature of Micro-loops.........................................5 54 3. Applicability.....................................................6 56 4. Micro-loop Control Strategies......................................6 58 5. Loop mitigation...................................................7 60 6. Micro-loop Prevention.............................................9 61 6.1. Incremental Cost Advertisement.................................9 62 6.2. Nearside Tunneling............................................11 63 6.3. Farside Tunnels...............................................12 64 6.4. Distributed Tunnels...........................................13 65 6.5. Packet Marking................................................13 66 6.6. MPLS New Labels...............................................13 67 6.7. Ordered FIB Update............................................15 68 6.8. Synchronised FIB Update.......................................16 69 7. Using PLSN In Conjunction With Other Methods......................17 71 8. Loop Suppression.................................................18 73 9. Compatibility Issues.............................................19 75 10. Comparison of Loop-free Convergence Methods......................19 77 11. IANA considerations.............................................20 79 12. Security Considerations.........................................20 81 13. Intellectual Property Statement..................................20 83 14. Disclaimer of Validity..........................................21 85 15. copyright Statement.............................................21 87 16. Normative References............................................21 89 17. Informative References..........................................21 91 18. Authors' Addresses..............................................22 92 1. Introduction 94 When there is a change to the network topology (due to the failure 95 or restoration of a link or router, or as a result of management 96 action) the routers need to converge on a common view of the new 97 topology and the paths to be used for forwarding traffic to each 98 destination. During this process, referred to as a routing 99 transition, packet delivery between certain source/destination 100 pairs may be disrupted. This occurs due to the time it takes for 101 the topology change to be propagated around the network together 102 with the time it takes each individual router to determine and then 103 update the forwarding information base (FIB) for the affected 104 destinations. During this transition, packets may be lost due to 105 the continuing attempts to use the failed component, and due to 106 forwarding loops. Forwarding loops arise due to the inconsistent 107 FIBs that occur as a result of the difference in time taken by 108 routers to execute the transition process. This is a problem that 109 occurs in both IP networks and MPLS networks that use LDP [RFC3036] 110 as the label switched path (LSP) signaling protocol. 112 The service failures caused by routing transitions are largely 113 hidden by higher-level protocols that retransmit the lost data. 114 However new Internet services are emerging which are more sensitive 115 to the packet disruption that occurs during a transition. To make 116 the transition transparent to their users, these services require a 117 short routing transition. Ideally, routing transitions would be 118 completed in zero time with no packet loss. 120 Regardless of how optimally the mechanisms involved have been 121 designed and implemented, it is inevitable that a routing 122 transition will take some minimum interval that is greater than 123 zero. This has led to the development of a TE fast-reroute 124 mechanism for MPLS [MPLS-TE]. Alternative mechanisms that might be 125 deployed in an MPLS network and mechanisms that may be used in an 126 IP network are work in progress in the IETF [IPFRR]. Any repair 127 mechanism may however be disrupted by the formation of micro-loops 128 during the period between the time when the failure is announced, 129 and the time when all FIBs have been updated to reflect the new 130 topology. 132 There is, however, little point in introducing new mechanisms into 133 an IP network to provide fast re-route, without also deploying 134 mechanisms that prevent the disruptive effects of micro-loops which 135 may starve the repair or cause congestion loss as a result of 136 looping packets. 138 The disruptive effect of micro-loops is not confined to periods 139 when there is a component failure. Micro-loops can, for example, 140 form when a component is put back into service following repair. 141 Micro-loops can also form as a result of a network maintenance 142 action such as adding a new network component, removing a network 143 component or modifying a link cost. 145 This framework provides a summary of the mechanisms that have been 146 proposed to address the micro-loop issue. 148 2. The Nature of Micro-loops 150 Micro-loops may form during the periods when a network is re- 151 converging following ANY topology change, and are caused by 152 inconsistent FIBs in the routers. During the transition, micro- 153 loops may occur over a single link between a pair of routers that 154 temporarily use each other as the next hop for a prefix. Micro- 155 loops may also form when a cycle of routers have the next router in 156 the cycle as a next hop for a prefix. Cyclic micro-loops always 157 include at least one link with an asymmetric cost, and/or at least 158 two symmetric cost link cost changes within the convergence time. 160 Micro-loops have two undesirable side-effects; congestion and 161 repair starvation. A looping packet consumes bandwidth until it 162 either escapes as a result of the re-synchronization of the FIBs, 163 or its TTL expires. This transiently increases the traffic over a 164 link by as much as 128 times, and may cause the link to congest. 165 This congestion reduces the bandwidth available to other traffic 166 (which is not otherwise affected by the topology change). As a 167 result the "innocent" traffic using the link experiences increased 168 latency, and is liable to congestive packet loss. 170 In cases where the link or node failure has been protected by a 171 fast re-route repair, the inconsistency in the FIBs prevents some 172 traffic from reaching the failure and hence being repaired. The 173 repair may thus become starved of traffic and hence become 174 ineffective. Thus in addition to the congestive damage, the repair 175 is rendered ineffective by the micro-loop. Similarly, if the 176 topology change is the result of management action the link could 177 have been retained in service throughout the transition (i.e. the 178 link acts as its own repair path), however, if micro-loops form, 179 they prevent productive forwarding during the transition. 181 Unless otherwise controlled, micro-loops may form in any part of 182 the network that forwards (or in the case of a new link, will 183 forward) packets over a path that includes the affected topology 184 change. The time taken to propagate the topology change through the 185 network, and the non-uniform time taken by each router to calculate 186 the new shortest path tree (SPT) and update its FIB may 187 significantly extend the duration of the packet disruption caused 188 by the micro-loops. In some cases a packet may be subject to 189 disruption from micro-loops which occur sequentially at links along 190 the path, thus further extending the period of disruption beyond 191 that required to resolve a single loop. 193 3. Applicability 195 Loop free convergence techniques are applicable [APPL] to any 196 situation in which micro-loops may form. For example the 197 convergence of a network following: 199 1) Component failure. 201 2) Component repair. 203 3) Management withdrawal of a component. 205 4) Management insertion or a component. 207 5) Management change of link cost (either positive or negative). 209 6) External cost change, for example change of external gateway as 210 a result of a BGP change. 212 7) A Shared risk link group failure. 214 In each case, a component may be a link or a router. 215 Loop free convergence techniques are applicable to both IP networks 216 and MPLS enabled networks that use LDP, including LDP networks that 217 use the single-hop tunnel fast-reroute mechanism. 219 4. Micro-loop Control Strategies. 221 Micro-loop control strategies fall into three basic classes: 223 1. Micro-loop mitigation 225 2. Micro-loop prevention 227 3. Micro-loop suppression 229 A micro-loop mitigation scheme works by re-converging the network 230 in such a way that it reduces, but does not eliminate, the 231 formation of micro-loops. Such schemes cannot guarantee the 232 productive forwarding of packets during the transition. 234 A micro-loop prevention mechanism controls the re-convergence of 235 network in such a way that no micro-loops form. Such a micro-loop 236 prevention mechanism allows the continued use of any fast repair 237 method until the network has converged on its new topology, and 238 prevents the collateral damage that occurs to other traffic for the 239 duration of each micro-loop. 241 A micro-loop suppression mechanism attempts to eliminate the 242 collateral damage done by micro-loops to other traffic. This may be 243 achieved by, for example, using a packet monitoring method, which 244 detects that a packet is looping and drops it. Such schemes make no 245 attempt to productively forward the packet throughout the network 246 transition. 248 Note that all known micro-loop mitigation and micro-loop prevention 249 mechanisms extend the duration of the re-convergence process. When 250 the failed component is protected by a fast re-route repair this 251 implies that the converging network requires the repair to remain 252 in place for longer than would otherwise be the case. The extended 253 convergence time means any traffic which is NOT repaired by an 254 imperfect repair experiences a significantly longer outage than it 255 would experience with conventional convergence. 257 When a component is returned to service, or when a network 258 management action has taken place, this additional delay does not 259 cause traffic disruption, because there is no repair involved. 260 However the extended delay is undesirable, because it increases the 261 time that the network takes to be ready for another failure, and 262 hence leaves it vulnerable to multiple failures. 264 5. Loop mitigation 266 The only known loop mitigation approach is the Path Locking with 267 safe-neighbors (PLSN) method described in [ZININ]. In this method, 268 a micro-loop free next-hop safety condition is defined as follows: 269 In a symmetric cost network, it is safe for router X to change to 270 the use of neighbor Y as its next-hop for a specific destination if 271 the path through Y to that destination satisfies both of the 272 following criteria: 274 1. X considers Y as its loop-free neighbor based on the 275 topology before the change AND 277 2. X considers Y as its downstream neighbor based on the 278 topology after the change. 280 In an asymmetric cost network, a stricter safety condition is 281 needed, and the criterion is that: 283 X considers Y as its downstream neighbor based on the 284 topology both before and after the change. 286 Based on these criteria, destinations are classified by each router 287 into three classes: 289 Type A destinations: Destinations unaffected by the change and also 290 destinations whose next hop after the change satisfies the safety 291 criteria. 293 Type B destinations: Destinations that cannot be sent via the new 294 primary next-hop because the safety criteria are not satisfied, but 295 which can be sent via another next-hop that does satisfy the safety 296 criteria. 298 Type C destinations: All other destinations. 300 Following a topology change, Type A destinations are immediately 301 changed to go via the new topology. Type B destinations are 302 immediately changed to go via the next hop that satisfies the 303 safety criteria, even though this is not the shortest path. Type B 304 destinations continue to go via this path until all routers have 305 changed their Type C destinations over to the new next hop. Routers 306 must not change their Type C destinations until all routers have 307 changed their Type A2 and Type B destinations to the new or 308 intermediate (safe) next hop. 310 Simulations indicate that this approach produces a significant 311 reduction in the number of links that are subject to micro-looping. 312 However unlike all of the micro-loop prevention methods it is only 313 a partial solution. In particular, micro-loops may form on any link 314 joining a pair of type C routers. 316 Because routers delay updating their Type C destination FIB 317 entries, they will continue to route towards the failure during the 318 time when the routers are changing their Type A and B destinations, 319 and hence will continue to productively forward packets provided 320 that viable repair paths exist. 322 A backwards compatibility issue arises with PLSN. If a router is 323 not capable of micro-loop control, it will not correctly delay its 324 FIB update. If all such routers had only type A destinations this 325 loop mitigation mechanism would work as it was designed. 326 Alternatively, if all such incapable routers had only type C 327 destinations, the "covert" announcement mechanism used to trigger 328 the tunnel based schemes could be used to cause the Type A and Type 329 B destinations to be changed, with the incapable routers and 330 routers having type C destinations delaying until they received the 331 "real" announcement. Unfortunately, these two approaches are 332 mutually incompatible. 334 Note that simulations indicate that in most topologies treating 335 type B destinations as type C results in only a small degradation 336 in loop prevention. Also note that simulation results indicate that 337 in production networks where some, but not all, links have 338 asymmetric costs, using the stricter asymmetric cost criterion 339 actually REDUCES the number of loop free destinations, because 340 fewer destinations can be classified as type A or B. 342 This mechanism operates identically for both "bad-news" events, 343 "good-news" events and SRLG failure. 345 6. Micro-loop Prevention 347 Eight micro-loop prevention methods have been proposed: 349 1. Incremental cost advertisement 351 2. Nearside tunneling 353 3. Farside tunneling 355 4. Distributed tunnels 357 5. Packet marking 359 6. New MPLS labels 361 7. Ordered FIB update 363 8. Synchronized FIB update 365 6.1. Incremental Cost Advertisement 367 When a link fails, the cost of the link is normally changed from 368 its assigned metric to "infinity" in one step. However, it can be 369 proved that no micro-loops will form if the link cost is increased 370 in suitable increments, and the network is allowed to stabilize 371 before the next cost increment is advertised. Once the link cost 372 has been increased to a value greater than that of the lowest 373 alternative cost around the link, the link may be disabled without 374 causing a micro-loop. 376 The criterion for a link cost change to be safe is that any link 377 which is subjected to a cost change of x can only cause loops in a 378 part of the network that has a cyclic cost less than or equal to x. 379 Because there may exist links which have a cost of one in each 380 direction, resulting in a cyclic cost of two, this can result in 381 the link cost having to be raised in increments of one. However the 382 increment can be larger where the minimum cost permits. Determining 383 the minimum link cost in the network is trivial, but unfortunately, 384 calculating the optimum increment at each step is thought to be a 385 costly calculation. 387 This approach has the advantage that it requires no change to the 388 routing protocol. It will work in any network that uses a link- 389 state IGP because it does not require any co-operation from the 390 other routers in the network. However the method can be extremely 391 slow, particularly if large metrics are used. For the duration of 392 the transition some parts of the network continue to use the old 393 forwarding path, and hence use any repair mechanism for an extended 394 period. In the case of a failure that cannot be fully repaired, 395 some destinations may become unreachable for an extended period. 397 Where the micro-loop prevention mechanism was being used to support 398 a fast re-route repair the network may be vulnerable to a second 399 failure for the duration of the controlled re-convergence. 401 Where the micro-loop prevention mechanism was being used to support 402 a reconfiguration of the network the extended time is less of an 403 issue. In this case, because the real forwarding path is available 404 throughout the whole transition, there is no conflict between 405 concurrent change actions throughout the network. 407 It will be appreciated that when a link is returned to service, its 408 cost is reduced in small steps from "infinity" to its final cost, 409 thereby providing similar micro-loop prevention during a "good- 410 news" event. Note that the link cost may be decreased from 411 "infinity" to any value greater than that of the lowest alternative 412 cost around the link in one step without causing a micro-loop. 413 When the failure is an SRLG the link cost increments must be 414 coordinated across all members of the SRLG. This may be achieved by 415 completing the transition of one link before starting the next, or 416 by interleaving the changes. This can be achieved without the need 417 for any protocol extensions, by for example, using existing 418 identifiers to establish the ordering and the arrival of LSP/LSAs 419 to trigger the generation of the next increment. 421 6.2. Nearside Tunneling 423 This mechanism works by creating an overlay network using tunnels 424 whose path is not effected by the topology change and carrying the 425 traffic affected by the change in that new network. When all the 426 traffic is in the new, tunnel based, network, the real network is 427 allowed to converge on the new topology. Because all the traffic 428 that would be affected by the change is carried in the overlay 429 network no micro-loops form. 431 When a failure is detected (or a link is withdrawn from service), 432 the router adjacent to the failure issues a new ("covert") routing 433 message announcing the topology change. This message is propagated 434 through the network by all routers, but is only understood by 435 routers capable of using one of the tunnel based micro-loop 436 prevention mechanisms. 438 Each of the micro-loop preventing routers builds a tunnel to the 439 closest router adjacent to the failure. They then determine which 440 of their traffic would transit the failure and place that traffic 441 in the tunnel. When all of these tunnels are in place, the failure 442 is then announced as normal. Because these tunnels will be 443 unaffected by the transition, and because the routers protecting 444 the link will continue the repair (or forward across the link being 445 withdrawn), no traffic will be disrupted by the failure. When the 446 network has converged these tunnels are withdrawn, allowing traffic 447 to be forwarded along its new "natural" path. The order of tunnel 448 insertion and withdrawal is not important, provided that the 449 tunnels are all in place before the normal announcement is issued. 451 This method completes in bounded time, and is much faster than the 452 incremental cost method. Depending on the exact design, it 453 completes in two or three flood-SPF-FIB update cycles. 455 At the time at which the failure is announced as normal, micro- 456 loops may form within isolated islands of non-micro-loop preventing 457 routers. However, only traffic entering the network via such 458 routers can micro-loop. All traffic entering the network via a 459 micro-loop preventing router will be tunneled correctly to the 460 nearest repairing router, including, if necessary being tunneled 461 via a non-micro-loop preventing router, and will not micro-loop. 463 Where there is no requirement to prevent the formation of micro- 464 loops involving non-micro-loop preventing routers, a single, 465 "normal" announcement may be made, and a local timer used to 466 determine the time at which transition from tunneled forwarding to 467 normal forwarding over the new topology may commence. 469 This technique has the disadvantage that it requires traffic to be 470 tunneled during the transition. This is an issue in IP networks 471 because not all router designs are capable of high performance IP 472 tunneling. It is also an issue in MPLS networks because the 473 encapsulating router has to know the labels set that the 474 decapsulating router is distributing. 476 A further disadvantage of this method is that it requires co- 477 operation from all the routers within the routing domain to fully 478 protect the network against micro-loops. 480 When a new link is added, the mechanism is run in "reverse". When 481 the "covert" announcement is heard, routers determine which traffic 482 they will send over the new link, and tunnel that traffic to the 483 router on the near side of that link. This path will not be 484 affected by the presence of the new link. When the "normal" 485 announcement is heard, they then update their FIB to send the 486 traffic normally according to the new topology. Any traffic 487 encountering a router that has not yet updated its FIB will be 488 tunneled to the near side of the link, and will therefore not loop. 490 When a management change to the topology is required, again exactly 491 the same mechanism protects against micro-looping of packets by the 492 micro-loop preventing routers. 494 When the failure is an SRLG, the required strategy is to classify 495 traffic according the first member of the SRLG that it will 496 traverse on its way to the destination, and to tunnel that traffic 497 to the router that is closest to that SRLG member. This will 498 require multiple tunnel destinations, in the limiting case, one per 499 SRLG member. 501 6.3. Farside Tunnels 503 Farside tunneling loop prevention requires the loop preventing 504 routers to place all of the traffic that would traverse the failure 505 in one or more tunnels terminating at the router (or in the case of 506 node failure routers) at the far side of the failure. The 507 properties of this method are a more uniform distribution of repair 508 traffic than is a achieved using the nearside tunnel method, and in 509 the case of node failure, a reduction in the decapsulation load on 510 any single router. 512 Unlike the nearside tunnel method (which uses normal routing to the 513 repairing router), this method requires the use of a repair path to 514 the farside router. This may be provided by the not-via mechanism, 515 in which case no further computation is needed. 517 The mode of operation is otherwise identical to the nearside 518 tunneling loop prevention method (Section 6.2). 520 6.4. Distributed Tunnels 522 In the distributed tunnels loop prevention method, each router 523 calculates its own repair and forwards traffic affected by the 524 failure using that repair. Unlike the FRR case, the actual failure 525 is known at the time of the calculation. The objective of the loop 526 preventing routers is to get the packets that would have gone via 527 the failure into G-space [TUNNEL] using routers that are in F- 528 space. Because packets are decapsulated on entry to G-space, rather 529 than being forced to go to the farside of the failure, more optimum 530 routing may be achieved. This method is subject to the same 531 reachability constraints described in [TUNNEL]. 533 The mode of operation is otherwise identical to the nearside 534 tunneling loop prevention method (Section 6.2). 536 6.5. Packet Marking 538 If packets could be marked in some way, this information could be 539 used to assign them to one of: the new topology, the old topology 540 or a transition topology. They would then be correctly forwarded 541 during the transition. This could, for example, be achieved by 542 allocating a Type of Service bit to the task [RFC791]. This 543 mechanism works identically for both "bad-news" and "good-news" 544 events. It also works identically for SRLG failure. There are three 545 problems with this solution: 547 1) The packet marking bit may not available. 549 2) The mechanism would introduce a non-standard forwarding 550 procedure. 552 3) Packet marking using either the old or the new topology would 553 double the size of the FIB, however some optimizations may be 554 possible. 556 6.6. MPLS New Labels 558 In an MPLS network that is using LDP [LDP] for label distribution, 559 loop free convergence can be achieved through the use of new labels 560 when the path that a prefix will take through the network changes. 562 As described in Section 6.2, the repairing routers issue a covert 563 announcement to start the loop free convergence process. All loop 564 preventing routers calculate the new topology and determine whether 565 their FIB needs to be changed. If there is no change in the FIB 566 they take no part in the following process. 568 The routers that need to make a change to their FIB consider each 569 change and check the new next hop to determine whether it will use 570 a path in the OLD topology which reaches the destination without 571 traversing the failure (i.e. the next hop is in F-space with 572 respect to the failure [TUNNEL]). If so the FIB entry can be 573 immediately updated. For all of the remaining FIB entries, the 574 router issues a new label to each of its neighbors. This new label 575 is used to lock the path during the transition in a similar manner 576 to the previously described loop-free convergence with tunnels 577 method (Section 6.2). Routers receiving a new label install it in 578 their FIB, for MPLS label translation, but do not yet remove the 579 old label and do not yet use this new label to forward IP packets. 580 i.e. they prepare to forward using the new label on the new path, 581 but do not use it yet. Any packets received continue to be 582 forwarded the old way, using the old labels, towards the repair. 584 At some time after the covert announcement, an overt announcement 585 of the failure is issued. This announcement MUST NOT be issued 586 until such time as all routers have carried out all of their covert 587 announcement activities. On receipt of the overt announcement all 588 routers that were delaying convergence move to their new path for 589 both the new and the old labels. This involves changing the IP 590 address entries to use the new labels, AND changing the old labels 591 to forward using the new labels. 593 Because the new label path was installed during the covert phase, 594 packets reach their destinations as follows: 596 o If they do not go via any router using a new label they go 597 via the repairing router and the repair. 599 o If they meet any router that is using the new labels they 600 get marked with the new labels and reach their destination 601 using the new path, back-tracking if necessary. 603 When all routers have changed to the new path the network is 604 converged. At some time later, when it can be assumed that all 605 routers have moved to using the new path, the FIB can be cleaned up 606 to remove the, now redundant, old labels. 608 As with other method methods this new labels may be modified to 609 provide loop prevention for "good news". There are also a number of 610 optimizations of this method. Further details will be provided in a 611 forthcoming draft. 613 6.7. Ordered FIB Update 615 The Ordered FIB loop prevention method is described in [OFIB]. 616 Micro-loops occur following a failure or a cost increase, when a 617 router closer to the failed component revises its routes to take 618 account of the failure before a router which is further away. By 619 analyzing the reverse spanning tree over which traffic is directed 620 to the failed component in the old topology, it is possible to 621 determine a strict ordering which ensures that nodes closer to the 622 root always process the failure after any nodes further away, and 623 hence micro-loops are prevented. 625 When the failure has been announced, each router waits a multiple 626 of the convergence timer [TIMER]. The multiple is determined by the 627 node's position in the reverse spanning tree, and the delay value 628 is chosen to guarantee that a node can complete its processing 629 within this time. The convergence time may be reduced by employing 630 a signaling mechanism to notify the parent when all the children 631 have completed their processing, and hence when it was safe for the 632 parent to instantiate its new routes. 634 The property of this approach is therefore that it imposes a delay 635 which is bounded by the network diameter although in many cases it 636 will be much less. 638 When a link is returned to service the convergence process above is 639 reversed. A router first determines its distance (in hops) from the 640 new link in the NEW topology. Before updating its FIB, it then 641 waits a time equal to the value of that distance multiplied by the 642 convergence timer. 644 It will be seen that network management actions can similarly be 645 undertaken by treating a cost increase in a manner similar to a 646 failure and a cost decrease similar to a restoration. 648 The ordered FIB mechanism requires all nodes in the domain to 649 operate according to these procedures, and the presence of non 650 co-operating nodes can give rise to loops for any traffic which 651 traverses them (not just traffic which is originated through them). 652 Without additional mechanisms these loops could remain in place for 653 a significant time. 655 It should be noted that this method requires per router ordering, 656 but not per prefix ordering. A router must wait its turn to update 657 its FIB, but it should then update its entire FIB. 659 When an SRLG failure occurs a router must classify traffic into the 660 classes that pass over each member of the SRLG. Each router is then 661 independently assigned a ranking with respect to each SRLG member 662 for which they have a traffic class. These rankings may be 663 different for each traffic class. The prefixes of each class are 664 then changed in the FIB according to the ordering of their specific 665 ranking. Again, as for the single failure case, signaling may be 666 used to speed up the convergence process. 668 Note that the special SRLG case of a full or partial node failure, 669 can be deal with without using per prefix ordering, by running a 670 single reverse SPF rooted at the failed node (or common point of 671 the subset of failing links in the partial case). 673 There are two classes of signaling optimization that can be applied 674 to the ordered FIB loop-prevention method: 676 1. When the router makes NO change, it can signal 677 immediately. This significantly reduces the time taken by 678 the network to process long chains of routers that have no 679 change to make to their FIB. 681 2. When a router HAS changed, it can signal that it has 682 completed. This is more problematic since this may be 683 difficult to determine, particularly in a distributed 684 architecture, and the optimization obtained is the difference 685 between the actual time taken to make the FIB change and the 686 worst case timer value. This saving could be of the order of 687 one second per hop. 689 There is another method of executing ordered FIB which is based on 690 pure signaling [OB]. Methods that use signaling as an optimization 691 are safe because eventually they fall back on the established IGP 692 mechanisms which ensure that networks converge under conditions of 693 packet loss. However a mechanism that relies on signaling in order 694 to converge requires a reliable signaling mechanism which must be 695 proven to recover from any failure circumstance. 697 6.8. Synchronised FIB Update 699 Micro-loops form because of the asynchronous nature of the FIB 700 update process during a network transition. In many router 701 architectures it is the time taken to update the FIB itself that is 702 the dominant term. One approach would be to have two FIBs and, in a 703 synchronized action throughout the network, to switch from the old 704 to the new. One way to achieve this synchronized change would be to 705 signal or otherwise determine the wall clock time of the change, 706 and then execute the change at that time, using NTP [NTP] to 707 synchronize the wall clocks in the routers. 709 This approach has a number of major issues. Firstly two complete 710 FIBs are needed which may create a scaling issue and secondly a 711 suitable network wide synchronization method is needed. However, 712 neither of these are insurmountable problems. 714 Since the FIB change synchronization will not be perfect there may 715 be some interval during which micro-loops form. Whether this scheme 716 is classified as a micro-loop prevention mechanism or a micro-loop 717 mitigation mechanism within this taxonomy is therefore dependent on 718 the degree of synchronization achieved. 720 This mechanism works identically for both "bad-news" and "good- 721 news" events. It also works identically for SRLG failure. 722 Further consideration needs to be given to interoperating with 723 routers that do not support this mechanism. Without a suitable 724 interoperating mechanism, loops may form for the duration of the 725 synchronization delay. 727 7. Using PLSN In Conjunction With Other Methods 729 All of the tunnel methods and packet marking can be combined with 730 PLSN [ZININ] to reduce the traffic that needs to be protected by 731 the advanced method. Specifically all traffic could use PLSN except 732 traffic between a pair of routers both of which consider the 733 destination to be type C. The type C to type C traffic would be 734 protected from micro-looping through the use of a loop prevention 735 method. 737 However, determining whether the new next hop router considers a 738 destination to be type C may be computationally intensive. An 739 alternative approach would be to use a loop prevention method for 740 all local type C destinations. This would not require any 741 additional computation, but would require the additional loop 742 prevention method to be used in cases which would not have 743 generated loops (i.e. when the new next-hop router considered this 744 to be a type A or B destination). 746 The amount of traffic that would use PLSN is highly dependent on 747 the network topology and the specific change, but would be expected 748 to be in the region %70 to %90 in typical networks. 750 However, PLSN cannot be combined safely with Ordered FIB. Consider 751 the network fragment shown below: 753 R 754 /|\ 755 / | \ 756 1/ 2| \3 757 / | \ cost S->T = 10 758 Y-----X----S----T cost T->S = 1 759 | 1 2 | 760 |1 | 761 D---------------+ 762 20 764 On failure of link XY, according to PLSN, S will regard R as a safe 765 neighbor for traffic to D. However the ordered FIB rank of both R 766 and T will be zero and hence these can change their FIBs during the 767 same time interval. If R changes before T, then a loop will form 768 around R, T and S. This can be prevented by using a stronger safety 769 condition than PLSN currently specifies, at the cost of introducing 770 more type C routers, and hence reducing the PLSN coverage. 772 8. Loop Suppression 774 A micro-loop suppression mechanism recognizes that a packet is 775 looping and drops it. One such approach would be for a router to 776 recognize, by some means, that it had seen the same packet before. 777 It is difficult to see how sufficiently reliable discrimination 778 could be achieved without some form of per-router signature such as 779 route recording. A packet recognizing approach therefore seems 780 infeasible. 782 An alternative approach would be to recognize that a packet was 783 looping by recognizing that it was being sent back to the place 784 that it had just come from. This would work for the types of loop 785 that form in symmetric cost networks, but would not suppress the 786 cyclic loops that form in asymmetric networks. 788 This mechanism operates identically for both "bad-news" events, 789 "good-news" events and SRLG failure. 791 The problem with this class of micro-loop control strategies is 792 that whilst they prevent collateral damage they do nothing to 793 enhance the productive forwarding of packets during the network 794 transition. 796 9. Compatibility Issues 798 Deployment of any micro-loop control mechanism is a major change to 799 a network. Full consideration must be given to interoperation 800 between routers that are capable of micro-loop control, and those 801 that are not. Additionally there may be a desire to limit the 802 complexity of micro-loop control by choosing a method based purely 803 on its simplicity. Any such decision must take into account that if 804 a more capable scheme is needed in the future, its deployment will 805 be complicated by interaction with the scheme previously deployed. 807 10. Comparison of Loop-free Convergence Methods 809 PLSN [ZININ] is an efficient mechanism to prevent the formation of 810 micro-loops, but is only a partial solution. It is a useful adjunct 811 to some of the complete solutions, but may need modification. 813 Incremental cost advertisement is impractical as a general solution 814 because it takes too long to complete. However, it is universally 815 available, and hence may find use in certain network 816 reconfiguration operations. 818 Packet Marking is probably impractical because of the need to find 819 the marking bit and to change the forwarding behavior. 821 Of the remaining methods distributed tunnels is significantly more 822 complex than nearside or farside tunnels, and should only be 823 considered if there is a requirement to distribute the tunnel 824 decapsulation load. 826 Synchronised FIBs is a fast method, but has the issue that a 827 suitable synchronization mechanism needs to be defined. One method 828 would be to use NTP [NTP], however the coupling of routing 829 convergence to a protocol that uses the network may be a problem. 830 During the transition there will be some micro-looping for a short 831 interval because it is not possible to achieve complete 832 synchronization of the FIB changeover. 834 The ordered FIB mechanism has the major advantage that it is a 835 control plane only solution. However, SRLGs require a per- 836 destination calculation, and the convergence delay is high, bounded 837 by the network diameter. The use of signaling as an accelerator 838 will reduce the number of destinations that experience the full 839 delay, and hence reduce the total re-convergence time to an 840 acceptable period. 842 The nearside and farside tunnel methods deal relatively easily with 843 SRLGs and uncorrelated changes. The convergence delay would be 844 small. However these methods require the use of tunneled forwarding 845 which is not supported on all router hardware, and raises issues of 846 forwarding performance. When used with PLSN, the amount of traffic 847 that was tunneled would be significantly reduced, thus reducing the 848 forwarding performance concerns. If the selected repair mechanism 849 requires the use of tunnels, then a tunnel based loop prevention 850 scheme may be acceptable. 852 11. IANA considerations 854 There are no IANA considerations that arise from this draft. 856 12. Security Considerations 858 All micro-loop control mechanisms raise significant security issues 859 which must be addressed in their detailed technical description. 861 13. Intellectual Property Statement 863 The IETF takes no position regarding the validity or scope of any 864 Intellectual Property Rights or other rights that might be claimed 865 to pertain to the implementation or use of the technology described 866 in this document or the extent to which any license under such 867 rights might or might not be available; nor does it represent that 868 it has made any independent effort to identify any such rights. 869 Information on the procedures with respect to rights in RFC 870 documents can be found in BCP 78 and BCP 79. 872 Copies of IPR disclosures made to the IETF Secretariat and any 873 assurances of licenses to be made available, or the result of an 874 attempt made to obtain a general license or permission for the use 875 of such proprietary rights by implementers or users of this 876 specification can be obtained from the IETF on-line IPR repository 877 at http://www.ietf.org/ipr. 879 The IETF invites any interested party to bring to its attention any 880 copyrights, patents or patent applications, or other proprietary 881 rights that may cover technology that may be required to implement 882 this standard. Please address the information to the IETF at 883 ietf-ipr@ietf.org. 885 14. Disclaimer of Validity 887 This document and the information contained herein are provided on 888 an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE 889 REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND 890 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, 891 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT 892 THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR 893 ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A 894 PARTICULAR PURPOSE. 896 15. copyright Statement 898 Copyright (C) The Internet Society (2006). 900 This document is subject to the rights, licenses and restrictions 901 contained in BCP 78, and except as set forth therein, the authors 902 retain all their rights. 904 16. Normative References 906 There are no normative references. 908 17. Informative References 910 Internet-drafts are works in progress available from 911 913 APPL Bryant, S., Shand, M., "Applicability of Loop- 914 free Convergence", , March 2006, (work in 916 progress). 918 IPFRR Shand, M., "IP Fast-reroute Framework", 919 , 920 March 2006, (work in progress). 922 LDP Andersson, L., Doolan, P., Feldman, N., 923 Fredette, A. and B. Thomas, "LDP 924 Specification", RFC 3036, 925 January 2001. 927 NTP RFC1305 Network Time Protocol (Version 3) 928 Specification, Implementation and Analysis. D. 929 Mills. February 2006. 931 [OB] Avoiding transient loops during IGP convergence 932 P. Francois, O. Bonaventure 933 IEEE INFOCOM 2005, March 2005, Miami, Fl., USA 935 [OFIB] Francois et. al., "Loop-free convergence using 936 ordered FIB updates", , March 2006 (work in progress). 939 RFC791 RFC-791, Internet Protocol Protocol 940 Specification, September 1981 942 TIMER S. Bryant, et. al. , "Synchronisation of Loop 943 Free Timer Values", , March 2005 945 TUNNEL Bryant, S., Shand, M., "IP Fast Reroute using 946 tunnels", , 947 Apr 2005 (work in progress). 949 ZININ Zinin, A., "Analysis and Minimization of 950 Microloops in Link-state Routing Protocols", 951 , 952 February 2006 (work in progress). 954 18. Authors' Addresses 956 Mike Shand 957 Cisco Systems, 958 250, Longwater Ave, 959 Green Park, 960 Reading, RG2 6GB, 961 United Kingdom. Email: mshand@cisco.com 963 Stewart Bryant 964 Cisco Systems, 965 250, Longwater Ave, 966 Green Park, 967 Reading, RG2 6GB, 968 United Kingdom. Email: stbryant@cisco.com