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