idnits 2.17.1 draft-ietf-mpls-loop-prevention-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. == 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 7) being 59 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 40 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 547 instances of weird spacing in the document. Is it really formatted ragged-right, rather than justified? ** There are 7 instances of too long lines in the document, the longest one being 4 characters in excess of 72. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 1391: '... the loop, some node in the loop MUST...' Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 41 has weird spacing: '... can be u...' == Line 43 has weird spacing: '...chanism can b...' == Line 44 has weird spacing: '...ordered downs...' == Line 45 has weird spacing: '...ount of infor...' == Line 48 has weird spacing: '...d, but only ...' == (542 more instances...) -- 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 (May 1999) is 9113 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) -- Possible downref: Non-RFC (?) normative reference: ref. '1' -- Possible downref: Non-RFC (?) normative reference: ref. '2' -- Possible downref: Non-RFC (?) normative reference: ref. '3' -- Possible downref: Non-RFC (?) normative reference: ref. '4' Summary: 7 errors (**), 0 flaws (~~), 9 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Network Working Group Yoshihiro Ohba 2 Internet-Draft Yasuhiro Katsube 3 Expiration Date: November 1999 Toshiba 5 Eric Rosen 6 Cisco Systems 8 Paul Doolan 9 Ennovate Networks 11 May 1999 13 MPLS Loop Prevention Mechanism 15 17 Status of this Memo 19 This document is an Internet-Draft and is in full conformance with 20 all provisions of Section 10 of RFC2026. 22 Internet-Drafts are working documents of the Internet Engineering 23 Task Force (IETF), its areas, and its working groups. Note that 24 other groups may also distribute working documents as Internet- 25 Drafts. 27 Internet-Drafts are draft documents valid for a maximum of six 28 months and may be updated, replaced, or obsoleted by other documents 29 at any time. It is inappropriate to use Internet-Drafts as 30 reference material or to cite them other than as "work in progress." 32 The list of current Internet-Drafts can be accessed at 33 http://www.ietf.org/ietf/1id-abstracts.txt 35 The list of Internet-Draft Shadow Directories can be accessed at 36 http://www.ietf.org/shadow.html. 38 Abstract 40 This paper presents a simple mechanism, based on "threads", which 41 can be used to prevent MPLS from setting up label switched path 42 (LSPs) which have loops. The mechanism is compatible with, but does 43 not require, VC merge. The mechanism can be used with either the 44 ordered downstream-on-demand allocation or ordered downstream 45 allocation. The amount of information that must be passed in a 46 protocol message is tightly bounded (i.e., no path-vector is used). 47 When a node needs to change its next hop, a distributed procedure is 48 executed, but only nodes which are downstream of the change are 49 involved. 51 Table of contents 53 1 Introduction .......................................... 3 54 2 Basic definitions ..................................... 4 55 3 Thread basics ......................................... 5 56 3.1 Thread attributes ..................................... 5 57 3.2 Thread loop ........................................... 6 58 3.3 Primitive thread actions .............................. 7 59 3.4 Examples of primitive thread actions ................. 9 60 4 Thread algorithm ...................................... 13 61 5 Applicability of the algorithm ........................ 14 62 5.1 LSP Loop prevention/detection ......................... 14 63 5.2 Using old path while looping on new path .............. 14 64 5.3 How to deal with ordered downstream allocation ........ 14 65 5.4 How to realize load splitting ......................... 14 66 6 Why this works ........................................ 16 67 6.1 Why a thread with unknown hop count is extended ....... 16 68 6.2 Why a rewound thread cannot contain a loop ............ 16 69 6.2.1 Case1: LSP with known link hop counts ................. 16 70 6.2.1 Case2: LSP with unknown link hop counts ............... 16 71 6.3 Why L3 loop is detected ............................... 16 72 6.4 Why L3 loop is not mis-detected ....................... 16 73 6.5 How a stalled thread automatically recovers from loop . 17 74 6.6 Why different colored threads do not chase each other . 17 75 7 Loop prevention examples .............................. 18 76 7.1 First example ......................................... 18 77 7.2 Second example ........................................ 22 78 8 Thread control block .................................. 23 79 8.1 Finite state machine .................................. 24 80 9 Comparison with path-vector/diffusion method .......... 27 81 10 Security considerations ............................... 27 82 11 Intellectual property considerations .................. 27 83 12 Acknowledgments ....................................... 28 84 13 Authors' Addresses .................................... 28 85 14 References ............................................ 28 86 Appendix A Further discussion of the algorithm ............. 29 88 1. Introduction 90 This paper presents a simple mechanism, based on "threads", which 91 can be used to prevent MPLS from setting up label switched paths 92 (LSPs) which have loops. 94 When an LSR finds that it has a new next hop for a particular FEC 95 (Forwarding Equivalence Class) [1], it creates a thread and extends 96 it downstream. Each such thread is assigned a unique "color", such 97 that no two threads in the network can have the same color. 99 For a given LSP, once a thread is extended to a particular next hop, 100 no other thread is extended to that next hop unless there is a 101 change in the hop count from the furthest upstream node. The only 102 state information that needs to be associated with a particular next 103 hop for a particular LSP is the thread color and hop count. 105 If there is a loop, then some thread will arrive back at an LSR 106 through which it has already passed. This is easily detected, since 107 each thread has a unique color. 109 Section 3 and 4 provide procedures for determining that there is no 110 loop. When this is determined, the threads are "rewound" back to 111 the point of creation. As they are rewound, labels get assigned. 112 Thus labels are NOT assigned until loop freedom is guaranteed. 114 While a thread is extended, the LSRs through which it passes must 115 remember its color and hop count, but when the thread has been 116 rewound, they need only remember its hop count. 118 The thread mechanism works if some, all, or none of the LSRs in the 119 LSP support VC-merge. It can also be used with either the ordered 120 downstream on-demand label allocation or ordered downstream 121 unsolicited label allocation [2,3]. The mechanism can also be 122 applicable to loop detection, old path retention, and 123 load-splitting. 125 The state information which must be carried in protocol messages, 126 and which must be maintained internally in state tables, is of fixed 127 size, independent of the network size. Thus the thread mechanism is 128 more scalable than alternatives which require that path-vectors be 129 carried. 131 To set up a new LSP after a routing change, the thread mechanism 132 requires communication only between nodes which are downstream of 133 the point of change. There is no need to communicate with nodes 134 that are upstream of the point of change. Thus the thread mechanism 135 is more robust than alternatives which require that a diffusion 136 computation be performed (see section 9). 138 2. Basic definitions 140 LSP 142 We will use the term LSP to refer to a multipoint-to-point tree 143 whose root is the egress node. See section 3.5 of [3]. 145 In the following, we speak as if there were only a single LSP being 146 set up in the network. This allows us to talk of incoming and 147 outgoing links without constantly saying something like "for the 148 same LSP. 150 Incoming Link, Upstream Link 151 Outgoing Link, Downstream Link 153 At a given node, a given LSP will have one or more incoming, or 154 upstream links, and one outgoing or downstream link. A "link" is 155 really an abstract relationship with an "adjacent" LSR; it is an 156 "edge" in the "tree", and not necessarily a particular concrete 157 entity like an "interface". 159 Leaf Node, Ingress Node 161 A node which has no upstream links. 163 Eligible Leaf Node 165 A node which is capable of being a leaf node. For example, a node 166 is not an eligible leaf node if it is not allowed to directly inject L3 167 packets created or received at the node into its outgoing link. 169 Link Hop Count 171 Every link is labeled with a "link hop count". This is the number 172 of hops between the given link and the leaf node which is furthest 173 upstream of the given link. At any node, the link hop count for 174 the downstream link is one more than the largest of the hop counts 175 associated with the upstream links. 177 We define the quantity "Hmax" at a given node to be the maximum of 178 all the incoming link hop counts. Note that, the link hop count of 179 the downstream link is equal to Hmax+1. At a leaf node, Hmax is 180 set to be zero. 182 An an example of link hop counts is shown in Fig.1. 184 1 2 185 A---B---C K 186 | | 187 |3 |1 188 | | 189 | 4 5 | 6 7 190 D---G---H---I---J 191 | 192 |2 193 1 | 194 E---F 196 Fig.1 Example of link hop counts 198 Next Hop Acquisition 200 Node N thought that FEC F was unreachable, but now has a next hop 201 for it. 203 Next Hop Loss 205 Node N thought that node A was the next hop for FEC F, but now no 206 longer has the next hop for FEC F. A node loses a next hop whenever 207 the next hop goes down. 209 Next Hop Change 211 At node N, the next hop for FEC F changes from node A to node B, 212 where A is different than B. A next hop change event can be seen as 213 a combination of a next hop loss event on the old next hop and a 214 next hop acquisition event on the new next hop. 216 3. Thread basics 218 A thread is a sequence of messages used to set up an LSP, in the 219 "ordered downstream-on-demand" (ingress-initiated ordered control) 220 style. 222 3.1. Thread attributes 224 There are three attributes related to threads. They may be encoded 225 into a single thread object as: 227 1 2 3 228 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 229 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 230 | | 231 + Color + 232 | | 233 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 234 | Hop Count | TTL | Reserved | 235 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 237 Thread Color 239 Every time a path control message is initiated by a node, the node 240 assigns a unique "color" to it. This color is to be unique in both 241 time and space: its encoding consists of an IP address of the node 242 concatenated with a unique event identifier from a numbering space 243 maintained by the node. The path setup messages that the node sends 244 downstream will contain this color. Also, when the node sends such 245 a message downstream, it will remember the color, and this color 246 becomes the color of the downstream link. 248 When a colored message is received, its color becomes the color of 249 the incoming link. The thread which consists of messages of a 250 certain color will be known as a thread of that color. 252 A special color value "transparent"(=all 0's) is reserved. 254 Thread Hop Count 256 In order to maintain link hop counts, we need to carry hop counts in 257 the path control messages. For instance, a leaf node would assign a 258 hop count of 1 to its downstream link, and would store that value 259 into a path setup message it sends downstream. When a path setup 260 message is sent downstream, a node would assign a hop count which is 261 one more than the largest of the incoming link hop counts, to its 262 downstream link, and would store that value into a path setup 263 message it sends downstream. Once the value is stored in a path 264 control message, we may refer to it has a "thread hop count". 266 A special hop count value "unknown"(=0xff), which is larger than any 267 other known value, is used when a loop is found. Once the thread 268 hop count is "unknown", it is not increased any more as the thread 269 is extended. 271 Thread TTL 273 To avoid infinite looping of control messages in some cases, a 274 thread TTL is used. When a node creates a path control message and 275 sends it downstream, it sets a TTL to the message, and the TTL is 276 decremented at each hop. When the TTL reaches 0, the message is not 277 forwarded any more. Unlike the thread hop counts and the thread 278 colors, the thread TTLs do not needs to be stored in incoming links. 280 3.2. Thread loop 282 When the same colored thread is received on multiple incoming links, 283 or the received thread color was assigned by the receiving node, it 284 is said that the thread forms a loop. A thread creator can tell 285 whether it assigned the received thread color by checking the IP 286 address part of the received thread color. 288 3.3. Primitive thread actions 290 Five primitive actions are defined in order to prevent LSP loops by 291 using threads: "extending", "rewinding", "withdrawing", "merging", 292 and "stalling". This section describes only each primitive action 293 and does not describe how these primitive actions are combined and 294 how the algorithm totally works. The main body of the algorithm is 295 described in section 4. 297 Thread Extending 299 When a node starts to send a path setup message to its next hop with 300 a set of thread attributes, it is said that "the node creates a 301 thread and extends it downstream". When a node receives a path 302 setup message from an upstream node with a set of thread attributes 303 and forwards it downstream, it is said that "the node receives a 304 thread and extends it downstream". The color and hop count of the 305 thread become the color and hop count of the outgoing link. 306 Whenever a thread is received on a particular link, the color and 307 hop count of that thread become the color and hop count of that 308 incoming link, replacing any color and hop count that the link may 309 have had previously. 311 For example, when an ingress node initiates a path setup, it creates 312 a thread and extends it downstream by sending a path setup message. 313 The thread hop count is set to be 1, and the thread color is set to 314 be the ingress node's address with an appropriate event identifier, 315 and the thread TTL is set to be its maximum value. 317 When a node receives a thread and extends it downstream, the node 318 either (i) extends the thread without changing color, or (ii) extend 319 the thread with changing color. The received thread is extended 320 with changing color if it is received on a new incoming link and 321 extended on an already existing outgoing link, otherwise, it is 322 extended without changing color. When a thread is extended with 323 changing color, a new colored thread is created and extended. 325 Thread creation does not occur only at leaf nodes. If an 326 intermediate node has an incoming link, it will create and extend a 327 new thread whenever it acquires a new next hop. 329 When a node notifies a next hop node of a decrease of the link hop 330 count, if it is not extending a colored thread, a transparent thread 331 is extended. 333 Thread Merging 335 When a node which has a colored outgoing link receives a new thread, 336 it does not necessarily extend the new thread. It may instead 'merge' 337 the new threads into the existing outgoing thread. In this case, no 338 messages are sent downstream. Also, if a new incoming thread is 339 extended downstream, but there are already other incoming threads, 340 these other incoming threads are considered to be merged into the 341 new outgoing thread. 343 Specifically, a received thread is merged if all the following 344 conditions hold: 346 o A colored thread is received by node N, AND 347 o The thread does not form a loop, AND 348 o N is not an egress node, AND 349 o N's outgoing link is colored, AND 350 o N's outgoing link hop count is at least one greater than the hop 351 count of the newly received thread. 353 When an outgoing thread rewinds (see below), any incoming threads 354 which have been merged with it will rewind as well. 356 Thread Stalling 358 When a colored thread is received, if the thread forms a loop, the 359 received thread color and hop count are stored on the receiving link 360 without being extended. This is the special case of thread merging 361 applied only for threads forming a loop and referred to as the 362 "thread stalling", and the incoming link storing the stalled thread 363 is called "stalled incoming link". A distinction is made between 364 stalled incoming links and unstalled incoming links. 366 Thread Rewinding 368 When a thread reaches a node which satisfies a particular loop-free 369 condition, the node returns an acknowledgment message back to the 370 message initiator in the reverse path on which the thread was 371 extended. The transmission of the acknowledgment messages is the 372 "rewinding" of the thread. 374 The loop-free condition is: 376 o A colored thread is received by the egress node, OR 377 o All of the following conditions hold: 378 (a) A colored thread is received by node N, AND 379 (b) N's outgoing link is transparent, AND 380 (c) N's outgoing link hop count is at least one greater than the 381 hop count of the newly received thread. 383 When a node rewinds a thread which was received on a particular 384 link, it changes the color of that link to transparent. 386 If there is a link from node M to node N, and M has extended a 387 colored thread to N over that link, and M determines (by receiving a 388 message from N) that N has rewound that thread, then M sets the 389 color of its outgoing link to transparent. M then continues 390 rewinding the thread, and in addition, rewinds any other incoming 391 thread which had been merged with the thread being rewound, 392 including stalled threads. 394 Each node can start label switching after the thread colors in all 395 incoming and outgoing links becomes transparent. 397 Note that transparent threads are threads which have already been 398 rewound; hence there is no such thing as rewinding a transparent 399 thread. 401 Thread Withdrawing 403 It is possible for a node to tear down a path. A node tears down 404 the portion of the path downstream of itself by sending teardown 405 messages to its next hop. This process is known as the "thread 406 withdrawing". 408 For example, suppose a node is trying to set up a path, and then 409 experiences a next hop change or a next hop loss. It will withdraw 410 the thread that it had extended down its old next hop. 412 If node M has extended a thread to node N, and node M then withdraws 413 that thread, N now has one less incoming link than it had before. If 414 N now has no other unstalled incoming links and N is not an eligible 415 leaf node, it must withdraw its outgoing thread. If N still has an 416 unstalled incoming link or N is an eligible leaf node, it may (or 417 may not) need to change the hop count of the outgoing link. 419 N needs to change the outgoing hop count if: 421 o The incoming link hop count that was just removed had a larger 422 hop count than any of the remaining incoming links, AND 423 o One of the following conditions holds: 424 (a) The outgoing link is transparent, OR 425 (b) The outgoing link has a known hop count. 427 If the outgoing link is transparent, it remains transparent, but the 428 new hop count needs to be sent downstream. If the outgoing link is 429 colored, a new thread (with a new color) needs to be created and 430 extended downstream. 432 3.4. Examples of primitive thread actions 434 The following notations are used to illustrate examples of primitive 435 actions defined for threads. 437 A pair of thread attributes stored in each link is represented by 438 "(C,H)", where C and H represent the thread color and thread hop 439 count, respectively. 441 A thread marked "+" indicates that it is created or received now. A 442 thread marked "-" indicates that it is withdrawn now. 444 A link labeled with squared brackets (e.g., "[a]") indicates that it 445 is an unstalled link. A link labeled with braces (e.g., "{a}") 446 indicates that it is a stalled link. 448 Fig. 2 shows an example in which a leaf node A creates a blue 449 thread and extends it downstream. 451 (bl,1) 452 A---[o1]---> 454 Fig.2 Thread extending at leaf node 456 Fig.3 shows an example of thread extending without changing color at 457 intermediate node. Assume that a node B has no incoming and 458 outgoing link before receiving a blue thread. When node B receives 459 the blue thread of hop count 1 on a new incoming link i1, it extends 460 the thread downstream without changing color (Fig.3(a)). After the 461 blue thread is extended, node B receives a red thread of hop count 462 unknown on incoming link i1 again (Fig.3(b)). The red thread is 463 also extended without changing its color, since both i1 and o1 464 already exists. 466 (bl,1)+ (bl,2) (re,U)+ (re,U) 467 ----[i1]--->B---[o1]----> ----[i1]--->B----[o1]---> 469 Fig.3(a) Fig.3(b) 471 Fig.3 Thread extending without changing color 473 Fig.4 shows an example of thread extending with changing color. 474 There are single incoming link i1 and single outgoing link o1 in 475 Fig.4(a). Then a red thread of hop count 3 is received on a new 476 incoming link i2. In this case, the received thread is extended 477 with changing color, i.e., a new green thread is created and 478 extended (Fig.4(b)), since o1 already exists. 480 (bl,1) (bl,2) (bl,1) (gr,4) 481 ----[i1]--->B----[o1]---> ----[i1]--->B----[o1]---> 482 ^ 483 | 484 ----[i2]----+ 485 (re,3)+ 487 Fig.4(a) Fig.4(b) 489 Fig.4 Thread extending with changing color 491 Fig.5 shows an example of thread merging. When a node B receives a 492 red thread of hop count 3, the received thread is not extended since 493 the outgoing link hop count is at least one greater than the 494 received thread hop count. Both the red and blue threads will be 495 rewound when the blue thread on outgoing link o1 is rewound. 497 (bl,3) (bl,4) 498 ----[i1]--->B----[o1]---> 499 ^ 500 | 501 ----[i2]----+ 502 (re,3)+ 504 Fig.5 Thread merging 506 Figs 6 and 7 show examples of thread stalling. When a node B 507 receives a blue thread of hop count 10 on incoming link i2 in Fig.6, 508 it "stalls" the received thread since the blue thread forms a loop. 509 In Fig.7, a leaf node A finds the loop of its own thread. 511 (bl,3) (bl,4) 512 ----[i1]--->B----[o1]---> 513 ^ 514 | 515 ----{i2}----+ 516 (bl,10)+ 518 Fig.6 Thread stalling (1) 520 (bl,10)+ (bl,1) 521 ----{i1}--->A----[o1]---> 523 Fig.7 Thread stalling (2) 525 Fig.8 shows an example of thread rewinding. When the yellow thread 526 which is currently being extended is rewound (Fig.8(a)), the node 527 changes all the incoming and outgoing thread color to transparent, 528 and propagates thread rewinding to upstream nodes (Fig.8(b)). 530 (bl,1) (ye,2) (tr,1) (tr,2) 531 ----[i2]--->B----[o1]---> ----[i2]--->B----[o1]---> 532 ^ ^ 533 | | 534 ----[i3]----+ ----[i3]----+ 535 (ye,1) (tr,1) 537 Fig.8(a) Fig.8(b) 539 Fig.8 Thread rewinding 541 Fig.9 shows an example of thread withdrawing. In Fig.9(a), the red 542 thread on incoming link i2 is withdrawn. Then Hmax decreases from 3 543 to 1, and node B creates a new green thread and extends it 544 downstream, as shown in Fig.9(b). 546 (bl,1) (re,4) (bl,1) (gr,2)+ 547 ----[i1]--->B---[o1]---> ----[i1]--->B----[o1]---> 548 ^ 549 | 550 ----[i2]----+ 551 (re,3)- 553 Fig.9(a) Fig.9(b) 555 Fig.9 Thread withdrawing (1) 557 Fig.10 shows another example of thread withdrawing. In Fig.10(a), 558 the red thread on incoming link i3 is withdrawn. In this case, Hmax 559 decreases from unknown to 1, however, no thread is extended as shown 560 in Fig.10(b), since the outgoing link has a colored thread and the 561 hop count is unknown. 563 (bl,1) (re,U) (bl,1) (re,U) 564 ----[i2]--->B----[o1]---> ----[i2]--->B----[o1]---> 565 ^ 566 | 567 ----[i3]----+ 568 (re,U)- 570 Fig.10(a) Fig.10(b) 572 Fig.10 Thread withdrawing (2) 574 Fig.11 shows another example of thread withdrawing. In Fig.11(a), 575 the transparent thread on incoming link i3 is withdrawn. In this 576 case, a transparent thread is extended (Fig.11(b)), since Hmax 577 decreases and the outgoing link is transparent. 579 (tr,1) (tr,U) (tr,1) (tr,2)+ 580 ----[i2]--->B----[o1]---> ----[i2]--->B----[o1]---> 581 ^ 582 | 583 ----[i3]----+ 584 (tr,U)- 586 Fig.11(a) Fig.11(b) 588 Fig.11 Thread withdrawing (3) 590 4. Thread algorithm 592 The ordered downstream-on-demand allocation is assumed here, 593 however, the algorithm can be adapted to the ordered downstream 594 allocation, as shown in section 5. 596 In the algorithm, a next hop change event will be separated into two 597 events: a next hop loss event on the old next hop and a next hop 598 acquisition event on the new next hop, in this order. 600 The following notations are defined: 602 Hmax: the largest incoming link hop count 603 Ni: the number of unstalled incoming links 605 The thread algorithm is described as follows. 607 When a node acquires a new next hop, it creates a colored thread and 608 extends it downstream. 610 When a node loses a next hop to which it has extended a thread, it 611 may withdraw that thread. As described in section 3, this may or 612 may not cause the next hop to take some action. Among the actions 613 the next hop may take are withdrawing the thread from its own next 614 hop, or extending a new thread to its own next hop. 616 A received colored thread is either stalled, merged, rewound, or 617 extended. A thread with TTL zero is never extended. 619 When a received thread is stalled at a node, if Ni=0 and the node 620 is not an eligible leaf node, initiate a thread withdrawing. 621 Otherwise, if Ni>0 and the received thread hop count is not unknown, 622 a colored thread of hop count unknown is created and extended. If 623 the received thread hop count is unknown, no thread is extended and 624 no further action is taken. 626 When a thread being extended is rewound, if the thread hop count is 627 greater than one more than Hmax, a transparent thread of hop count 628 (Hmax+1) is extended downstream. 630 When a node that has an transparent outgoing link receives a 631 transparent thread, if Hmax decreases the node extends it 632 downstream without changing color. 634 5. Applicability of the algorithm 636 The thread algorithm described in section 4 can be applied to 637 various LSP management policies. 639 5.1. LSP Loop prevention/detection 641 The same thread algorithm is applicable to both LSP loop prevention 642 and detection. 644 In loop prevention mode, a node transmits a label mapping (including 645 a thread object) for a particular LSP only when it rewinds the 646 thread for that LSP. No mapping message is sent until the thread 647 rewinds. 649 On the other hand, if a node operates in loop detection mode, it 650 returns a label mapping message without a thread object immediately 651 after receiving a colored thread. A node which receives a label 652 mapping message that does not have a thread object will not rewind 653 the thread. 655 5.2. Using old path while looping on new path 657 When a route changes, one might want to continue to use the old path 658 if the new route is looping. This is achieved simply by holding the 659 label assigned to the downstream link on the old path until the 660 thread being extended on the new route gets rewound. This is an 661 implementation choice. 663 5.3. How to deal with ordered downstream allocation 665 The thread mechanism can be also adapted to ordered downstream 666 allocation mode (or the egress-initiated ordered control) by 667 regarding the event of newly receiving of a label mapping message 668 [4] from the next hop as a next hop acquisition event. 670 Note that a node which doesn't yet have an incoming link behaves as 671 a leaf. In the case where the tree is being initially built up 672 (e.g., the egress node has just come up), each node in turn will 673 behave as a leaf for a short period of time. 675 5.4. How to realize load splitting 677 A leaf node can easily perform load splitting by setting up two 678 different LSPs for the same FEC. The downstream links for the two 679 LSPs are simply assigned different colors. The thread algorithm now 680 prevents a loop in either path, but also allows the two paths to 681 have a common downstream node. 683 If some intermediate node wants to do load splitting, the following 684 modification is made. Assume that there are multiple next hops for 685 the same FEC. If there are n next hops for a particular FEC, the 686 set of incoming links for that FEC's LSP can be partitioned into n 687 subsets, where each subset can be mapped to a distinct outgoing 688 link. This provides n LSPs for the FEC. Each such LSP uses a 689 distinct color for its outgoing link. The thread algorithm now 690 prevents a loop in any of the paths, but also allows two or more of 691 the paths to have a common downstream node. 693 In this case, an interesting situation may happen. Let's say that 694 in Fig.12, node B has two incoming links, i1 and i2, and two 695 outgoing links, o1 and o2, such that i1 is mapped to o1, while i2 is 696 mapped to o2. 698 If a blue thread received on i1 and extended on o1 is again received 699 at node B on i2, the blue thread is not regarded as forming a loop, 700 since i1 and i2 are regarded as belonging to different subsets. 701 Instead, the blue thread received on i2 is extended on o2. If the 702 thread extended on o2 is rewound, a single loop-free LSP which 703 traverses node B twice is established. 705 +------------------...--------------------+ 706 . (bl,3) (bl,4) | 707 . ----[i1]---+ +--[o1]---> .... --+ 708 . \ / 709 . v / 710 | B 711 | 712 +-----------[i2]--->B----[o2]---> 713 (bl,10)+ (bl,11) 715 Fig.12 Load splitting at intermediate node 717 There is another type of load splitting, in which packets arrived at 718 single incoming link can be label switched to any one of multiple 719 outgoing links. This case does not seem to be a good load-splitting 720 scheme, since the packet order in the same FEC is not preserved. 721 Thus, this draft does not focus on this case. 723 Whether that's a good type of load splitting or not, the fact 724 remains that ATM-LSRs cannot load split like this because ATM 725 switches just don't have the capability to make forwarding decisions 726 on a per-packet basis. 728 6. Why this works 730 6.1. Why a thread with unknown hop count is extended 732 In the algorithm, a thread of unknown hop count is extended when a 733 thread loop is detected. This reduces the number of loop prevention 734 messages by merging threads (of known hop count) that are flowing 735 inside or outside the loop. See Appendix A.12. 737 6.2. Why a rewound thread cannot contain a loop 739 6.2.1. Case1: LSP with known link hop counts 741 How can we be sure that an established path does not contain a loop 742 when the outgoing link hop count is NOT "unknown"? 744 Consider a sequence of LSRs , such that there is a loop 745 traversing the LSRs in the sequence. (I.e., packets from R1 go to 746 R2, then to R3, etc., then to Rn, and then from Rn to R1.) 748 Suppose that the thread hop count of the link between R1 and R2 is 749 k. Then by the above procedures, the hop counts between Rn and R1 750 must be k+n-1. But the algorithm also ensures that if a node has an 751 incoming hop count of j, its outgoing link hop count must be at 752 least of j+1. Hence, if we assume that the LSP established as a 753 result of thread rewinding contains a loop, the hop counts between 754 R1 and R2 must be at least k+n. From this we may derive the absurd 755 conclusion that n=0, and we may therefore conclude that there is no 756 such sequence of LSRs. 758 6.2.1. Case2: LSP with unknown link hop counts 760 An established path does not contain a loop as well, when the 761 outgoing link hop count is "unknown". This is because a colored 762 thread of unknown hop count is never rewound unless it reaches 763 egress. 765 6.3. Why L3 loop is detected 767 Regardless of whether the thread hop count is known or unknown, if 768 there is a loop, then some node in the loop will be the last node to 769 receive a thread over a new incoming link. This thread will always 770 arrive back at that node, without its color having changed. Hence 771 the loop will always be detected by at least one of the nodes in the 772 loop. 774 6.4. Why L3 loop is not mis-detected 776 Since no node ever extends the same colored thread downstream twice, 777 a thread loop is not detected unless there actually is an L3 routing 778 loop. 780 6.5. How a stalled thread automatically recovers from loop 782 Once a thread is stalled in a loop, the thread (or the path setup 783 request) effectively remains in the loop, so that a path 784 reconfiguration (i.e., thread withdrawing on the old path and thread 785 extending on the new path) can be issued from any node that may 786 receive a route change event so as to break the loop. 788 6.6. Why different colored threads do not chase each other 790 In the algorithm, multiple thread color and/or hop count updates may 791 happen if several leaf nodes start extending threads at the same 792 time. How can we prevent multiple threads from looping unlimitedly? 794 First, when a node finds that a thread forms a loop, it creates a 795 new thread of hop count "unknown". All the looping threads of a 796 known hop count which later arrive at the node would be merged into 797 this thread. Such a thread behaves like a thread absorber. 799 Second, the "thread extending with changing color" prevents two 800 threads from chasing each other. 802 Suppose that a received thread were always extended without changing 803 color. Then we would encounter the following situation. 805 G Y 806 | | 807 v v 808 R1------>R2 809 ^ | 810 | v 811 R4<------R3 813 Fig.13 Example of thread chasing 815 In Fig.13, (1) node G acquires R1 as a next hop, and starts to 816 extend a green thread of hop count 1, (2) node Y acquires R2 as a 817 next hop, and starts to extend a yellow thread of hop count 1, and 818 (3) both node G and node Y withdraws their threads before these 819 threads go round. 821 In this case, the yellow and green threads would go round and get 822 back to R2 and R1, respectively. When the threads get back to R2 823 and R1, however, the incoming links that store the yellow and green 824 colors no longer exist. As a result, the yellow and green threads 825 would chase each other forever in the loop. 827 However, since we have the "extending with changing color" 828 mechanism, this does not actually happen. When a green thread is 829 received at R2, R2 extends the thread with changing color, i.e., 830 creates a new red thread and extends it. Similarly, when a yellow 831 thread is received at R1, R1 creates a new purple thread and extends 832 it. Thus, the thread loop is detected even after node G and node Y 833 withdraw threads. This ensures that a thread is extended around the 834 loop which has a color assigned by some node that is in the loop. 836 There is at least one case even the "extending with changing color" 837 mechanism cannot treat, that is, the "self-chasing" in which thread 838 extending and thread withdrawing with regard to the same thread 839 chase each other in a loop. This case would happen when a node 840 withdraw a thread immediately after extending it into an L3 loop. 842 A heuristics for self-chasing is to delay the execution of thread 843 withdrawing at an initiating node of the thread withdrawing. 844 Anyway, the thread TTL mechanism can eliminate any kind of thread 845 looping. 847 7. Loop prevention examples 849 In this section, we show two examples to show how the algorithm can 850 prevent LSP loops in given networks. 852 We assume that the ordered downstream-on-demand allocation is 853 employed, that all the LSPs are with regard to the same FEC, and 854 that all nodes are VC-merge capable. 856 7.1. First example 858 Consider an MPLS network shown in Fig.14 in which an L3 loop exists. 859 Each directed link represents the current next hop of the FEC at 860 each node. Now leaf nodes R1 and R6 initiate creation of an LSP. 862 R11 ------- R10 <-------------------- R9 863 | | ^ 864 | | | 865 | | | 866 v v | 867 R1 -------> R2 --------> R3 --------> R4 --------- R5 868 [leaf] ^ 869 | 870 | 871 | 872 R6 -------> R7 --------> R8 873 [leaf] 875 Fig. 14 Example MPLS network (1) 877 Assume that R1 and R6 send a label request message at the same time, 878 and that the initial thread TTL is 255. First we show an example of 879 how to prevent LSP loops. 881 A set of thread attributes is represented by (color, hop count, TTL). 883 The request from R1 and R6 contains (re,1,255) and (bl,1,255), 884 respectively. 886 Assume that R3 receives the request originated from R1 before 887 receiving the request originated from R6. When R3 receives the 888 first request with red thread, R3 forwards it with (re,3,253) 889 without changing thread color, since both the receiving incoming 890 link and the outgoing link are newly created. Then R3 receives the 891 second request with blue thread. In this time, the outgoing link is 892 already exists. Thus, R3 performs thread extending with changing 893 color, i.e., creates a new brown thread and forwards the request 894 with (br,4,255). 896 When R2 receives the request from R10 with (re,6,250), it finds that 897 the red thread forms a loop, and stalls the red thread. Then, R2 898 creates a purple thread of hop count unknown and extends it 899 downstream by sending a request with (pu,U,255) to R3, where "U" 900 represents "unknown". 902 After that, R2 receives another request from R10 with (br,7,252). 903 The brown thread is merged into purple thread. R2 sends no request 904 to R3. 906 On the other hand, the purple thread goes round without changing 907 color through existing links, and R2 finds the thread loop and 908 stalls the purple thread. Since the received thread hop count is 909 unknown, no thread is created any more. In this case no thread 910 rewinding occurs. The current state of the network is shown in 911 Fig.15. 913 *: location of thread stalling 915 (pu,U) 916 R11 ------- R10 <-------------------- R9 917 | | ^ 918 | |(pu,U)* | 919 | | |(pu,U) 920 v v | 921 R1 -------> R2 --------> R3 --------> R4 --------- R5 922 [leaf] (re,1) (pu,U) ^ (pu,U) 923 | 924 | (bl,3) 925 | 926 R6 -------> R7 --------> R8 927 [leaf] (bl,1) (bl,2) 929 Fig.15 The network state 931 Then R10 changes its next hop from R2 to R11. 933 Since R10 has a purple thread on the old downstream link, it first 934 sends a path teardown message to the old next hop R2 for withdrawing 935 the purple thread. Next, it creates a green thread of hop count 936 unknown and sends a request with (gr,U,255) to R11. 938 When R2 receives the teardown message from R10, R2 removes the 939 stalled incoming link between R10 and R2. 941 On the other hand, the green thread reaches R1 and Hmax is updated 942 from zero to unknown. In this case, R1 performs thread extending 943 with changing color since the thread is received on a new incoming 944 link but extended on the already existing outgoing link. As a 945 result, R1 creates an orange thread of hop count unknown and extend 946 it to R2. 948 The orange thread goes round through existing links without changing 949 color, and finally it is stalled at R1. 951 The state of the network is now shown in Fig.16. 953 *: location of thread stalling 955 (or,U) (or,U) 956 R11 <------ R10 <-------------------- R9 957 | | ^ 958 |(or,U)* | | 959 | | |(or,U) 960 v | | 961 R1 -------> R2 --------> R3 --------> R4 --------- R5 962 [leaf] (or,U) (or,U) ^ (or,U) 963 | 964 | (bl,3) 965 | 966 R6 -------> R7 --------> R8 967 [leaf] (bl,1) (bl,2) 969 Fig.16 The network state 971 Then R4 changes its next hop from R9 to R5. 973 Since R4 is extending an orange thread, it first sends a teardown 974 message to the old next hop R9 to withdraw the orange thread on the 975 old route. Next, it creates a yellow thread of hop count unknown, 976 and sends a request message with (ye,U,255) to R5. 978 Since R5 is the egress node, the yellow thread rewinding starts. R5 979 returns a label mapping message. The thread rewinding procedure is 980 performed at each node, as the label mapping message is returned 981 upstream hop-by-hop. 983 If R1 receives a label mapping message before receiving the orange 984 thread's withdrawal from R11, R1 returns a label mapping message to 985 R11. On receiving the orange thread's withdrawal, R1 will create a 986 transparent thread and extend it by sending an update message with 987 (tr,1,255) in order to notify downstream of the known hop count. 989 Otherwise, if R1 receives the orange thread's withdrawal before 990 receiving a label mapping message, R1 removes the stalled incoming 991 orange link and waits for rewinding of the outgoing orange thread. 992 Finally, when R1 receives a label mapping message from R2, it 993 creates a transparent thread (tr,1,255) and extend it downstream. 995 In both cases, a merged LSP ((R1->R2),(R6->R7->R8))->R3->R4->R5) is 996 established and every node obtains the correct link hop count. The 997 final network state is shown in Fig.17. 999 R11 <------ R10 <-------------------- R9 1000 | | | 1001 | | | 1002 | | | 1003 v | | 1004 R1 -------> R2 --------> R3 --------> R4 --------> R5 1005 [leaf] (tr,1) (tr,2) ^ (tr,4) (tr,5) 1006 | 1007 | (tr,3) 1008 | 1009 R6 -------> R7 --------> R8 1010 [leaf] (tr,1) (tr,2) 1012 Fig.17 The final network state 1014 7.2. Second example 1016 +----- R6----> R7-----+ 1017 | | 1018 | v 1019 R1---->R2 R4----->R5 1020 | ^ 1021 | | 1022 +--------->R3---------+ 1024 Fig.18 Example MPLS network (2) 1026 Assume that in Fig.18, there is an established LSP 1027 R1->R2->R3->R4->R5, and the next hop changes at R2 from R3 to R6. 1028 R2 sends a request to R6 with a red thread (re,2,255). When the 1029 request with (re,4,253) reaches R4, it extends the thread to R5 with 1030 changing color. Thus, a new green thread is created at R4 and 1031 extended to R5 by sending an update message with (gr,5,255). 1033 When R5 receives the update, it updates the incoming link hop count 1034 to 5 and returns an ack (or a notification message with a success 1035 code) for the update. When R4 receives the ack for the update, it 1036 returns a label mapping message to R7. 1038 When R2 receives the label mapping message on the new route, it 1039 sends a teardown message to R3. When R4 receives the teardown 1040 message, it does not sends an update to R5 since Hmax does not 1041 change. Now an established LSP R1->R2->R6->R7->R4->R5 is obtained. 1043 Then, the next hop changes again at R2 from R6 to R3. 1045 R2 sends a request with a blue thread (bl,2,255) to R3. R3 forwards 1046 the request with (bl,3,254) to R4. 1048 When R4 receives the request, it immediately returns a label mapping 1049 message to R3 since Hmax does not change. 1051 When R2 receives the label mapping message on the new route, it 1052 sends a teardown message to R6. The teardown message reaches R4, 1053 triggering an update message with a transparent thread (tr,4,255) to 1054 R5, since Hmax decreases from 4 to 3. R5 updates the incoming link 1055 hop count to 4 without returning an ack. 1057 8. Thread control block 1059 A thread control block (TCB) is maintained per LSP at each node and 1060 may contain the following information: 1062 - FEC 1063 - State 1064 - Incoming links 1065 Each incoming link has the following attributes: 1066 o neighbor: upstream neighbor node address 1067 o color: received thread color 1068 o hop count: received thread hop count 1069 o label 1070 o S-flag: indicates a stalled link 1071 - Outgoing links 1072 Each outgoing link has the following attributes: 1073 o neighbor: downstream neighbor node address 1074 o color: received thread color 1075 o hop count: received thread hop count 1076 o label 1077 o C-flag: indicates the link to the current next hop 1079 If a transparent thread is received on an incoming link for which no 1080 label is assigned yet or a non-transparent color is stored, discard 1081 the thread without entering the FSM. An error message may be 1082 returned to the sender. 1084 Whenever a thread is received on an incoming link, the following 1085 actions are taken before entering the FSM: (1) Store the received 1086 thread color and hop count on the link, replacing the old thread 1087 color and hop count, and (2) set the following flags that are used 1088 for an event switch within "Recv thread" event (see section 8.1). 1090 o Color flag (CL-flag): 1091 Set if the received thread is colored. 1092 o Loop flag (LP-flag): 1093 Set if the received thread forms a loop. 1094 o Arrived on new link flag (NL-flag): 1095 Set if the received thread arrives on a new incoming link. 1097 If LP-flag is set, there must be an incoming link L, other than the 1098 receiving link, which stores the same thread color as the received 1099 one. The TCB to which link L belongs is referred to as the 1100 "detecting TCB". If the receiving LSR is VC-merge capable, the 1101 detecting TCB and the receiving TCB is the same, otherwise, the two 1102 TCBs are different. 1104 Before performing a thread extending, the thread TTL is decremented 1105 by one. If the resulting TTL becomes zero, the thread is not 1106 extended but silently discarded. Otherwise, the thread is extended 1107 and the extended thread hop count and color are stored into the 1108 outgoing link. 1110 When a node receives a thread rewinding event, if the received 1111 thread color and the extending thread color are different, it 1112 discards the event without entering the FSM. 1114 8.1. Finite state machine 1116 An event which is "scheduled" by an action in an FSM must be passed 1117 immediately after the completion of the action. 1119 The following variables are used in the FSM: 1120 o Ni: number of unstalled incoming links 1121 o Hmax: largest incoming hop count 1122 o Hout: hop count of the outgoing link for the current next hop 1123 o Hrec: hop count of the received thread 1125 In the FSM, if Hmax=unknown, the value for (Hmax+1) becomes the 1126 value reserved for unknown hop count plus 1. For example, if 1127 Hmax=unknown=255, the value (Hmax+1) becomes 256. 1129 A TCB has three states; Null, Colored, and Transparent. When a TCB 1130 is in state Null, there is no outgoing link and Ni=0. The state 1131 Colored means that the node is extending a colored thread on the 1132 outgoing link for the current next hop. The state Transparent means 1133 that the node is the egress node or the outgoing link is 1134 transparent. 1136 The flag value "1" represents the flag is set, "0" represents the 1137 flag is not set, and "*" means the flag value is either 1 or 0. 1139 The FSM allows to have one transparent outgoing link on the old 1140 next hop and one colored outgoing link on the current next hop. 1141 However, it is not allowed to have a colored outgoing link on 1142 the old next hop. 1144 State Null: 1146 Event Action New state 1147 Recv thread 1148 Flags 1149 CL LP NL 1150 0 * * Do nothing. No change 1151 1 0 * If the node is egress, start thread rewinding Transparent 1152 and change the color of the receiving link to 1153 transparent. 1154 Otherwise, extend the received thread without Colored 1155 changing color. 1156 1 1 * Stall the received thread; if Hrec0 and HrecA----->B<---Y 1750 ^ | 1751 | v 1752 W--->D<-----C<---Z 1754 In this example, there is a loop A-B-C-D-A. However, there are also 1755 threads entering the loop from X, Y, Z, and W. Once the loop is 1756 detected, there really is no reason why any other thread should have 1757 to wrap around the loop. It would be better to simply mark presence 1758 of the loop in each node. 1760 To do this, we introduce the notion of the "unknown" hop count, U. 1761 This hop count value is regarded as being larger than any other hop 1762 count value. A thread with hop count U will be known as a 1763 "U-thread". 1765 A.12.1 When an incoming thread with a known hop count stalls, and there 1766 is an outgoing thread, we assign the hop count U to the outgoing 1767 thread, and we assign a new color to the outgoing thread as 1768 well. 1770 As a result, the next hop will then have an incoming U-thread, with 1771 the newly assigned color. This causes its outgoing thread in turn 1772 to be assigned hop count U and the new color. The rules we have 1773 already given will then cause each link in the loop to be assigned 1774 the new color and the hop count U. When this thread either reaches 1775 its originator, or any other node which already has an incoming 1776 thread of the same color, it stalls. 1778 In our example above, this will cause the links AB, BC, CD, and DA 1779 to be given hop count U. 1781 Now let's add one more rule: 1783 A.12.2 When a thread with a known hop count reaches a node that has a 1784 colored outgoing U-thread, the incoming thread merges into the 1785 outgoing thread. (Actually, this is just a consequence of a 1786 rule which has already been given, since U is greater than any 1787 known hop count.) 1789 Then if W, X, Y, or Z attempt to extend a thread to D, A, B, or C 1790 respectively, those threads will immediately stall. Once all the 1791 links are marked as being within a loop, no other threads are 1792 extended around the loop, i.e., no other setup messages will 1793 traverse the loop. 1795 Here is our example topology with the link hop counts that would 1796 exist during a loop: 1798 1 U 1 1799 X--->A----->B<---Y 1800 ^ | 1801 U | |U 1802 | v 1803 W--->D<-----C<---Z 1804 1 U 1 1806 A.13. Some Special Rules for Hop Count U 1808 When a U-thread encounters a thread with known hop count, the usual 1809 rules apply, remembering that U is larger than any known hop count 1810 value. 1812 However, we need to add a couple of special rules for the case when 1813 a U-thread encounters a U-thread. Since we can't tell which of the 1814 two U-threads is really the longer, we need to make sure that each 1815 of the U-threads is extended. 1817 A.13.1 If an incoming colored U-thread arrives at a node which already 1818 has an incoming U-thread of that color, or arrives at the node 1819 which created that U-thread, then the thread stalls. 1821 (Once a loop is detected, there is no need to further extend the 1822 thread.) 1824 A.13.2 If an incoming colored U-thread arrives at a node which has a 1825 transparent outgoing U-thread to its next hop, the incoming 1826 thread is extended. 1828 A.13.3 If an incoming colored U-thread arrives at a node which has a 1829 colored outgoing U-thread, and if the incoming link over which 1830 the thread was received was already an incoming link of the LSP, 1831 the thread is extended. 1833 A.13.4 If an incoming colored U-thread arrives at a node which has a 1834 colored outgoing U-thread, and if the incoming link over which 1835 the thread was received was NOT already an incoming link of the 1836 LSP, a new U-thread is created and extended. All the incoming 1837 threads are merged into it. This is known in the main body of 1838 this draft as "extending the thread with changing color". 1840 These rules ensure that an incoming U-thread is always extended (or 1841 merged into a new U-thread which then gets extended), unless it is 1842 already known to form a loop. 1844 What is the purpose of rule A.13.4? There are certain cases where a 1845 loop can form, but where the node which created the looping thread 1846 is not part of the loop. Rule A.13.4 ensures that when there is a 1847 loop, there will be a looping thread which was created by some node 1848 which is actually in the loop. This in turn ensures that the loop 1849 will be detected well before the thread TTL expires. 1851 The rule of "extending the thread with changing color" is also 1852 applied when extending a thread with a known hop count. 1854 A.13.5 When a received colored thread with a known hop count is 1855 extended, if the node has an outgoing thread, and if the 1856 incoming link over which the thread was received was NOT already 1857 an incoming link of the LSP, a new thread is created and 1858 extended. All the incoming threads are merged into it. This is 1859 an exceptional case of A.5.1. 1861 A.14. Recovering From a Loop 1863 Here is our example topology again, in the presence of a loop. 1865 1 U 1 1866 X--->A----->B<---Y 1867 ^ | 1868 U | |U 1869 | v 1870 W--->D<-----C<---Z 1871 1 U 1 1873 Suppose now that C's next hop changes from D to some other node E, 1874 thereby breaking the loop. For simplicity, we will assume that E is 1875 the egress node. 1877 C will withdraw its outgoing U-thread from D (9.1). It will also 1878 create a new thread (12.1), assign it a new color, assign it hop 1879 count U (the largest hop count of C's incoming threads), merge its 1880 two other incoming threads into the new thread (12.2), and extend 1881 the new thread to E, resulting the following configuration: 1883 1 U 1 1884 X--->A----->B<---Y 1885 ^ | 1886 U | |U 1887 | v 1888 W--->D C<---Z 1889 1 | 1 1890 U| 1891 v 1892 E 1894 When the thread from C to E rewinds, the merged threads also rewind 1895 (8.4). This process of rewinding can now proceed all the way back 1896 to the leafs. While this is happening, of course, D will note that 1897 its outgoing thread hop count should be 2, not U, and will make this 1898 change (9.3). As a result, A will note that its outgoing hop count 1899 should be 3, not U, and will make this change. So at some time in 1900 the future, we might see the following: 1902 1 3 1 1903 X--->A----->B<---Y 1904 ^ | 1905 2 | |U 1906 | v 1907 W--->D C<---Z 1908 1 | 1 1909 U| 1910 v 1911 E 1913 After a short period, we see the following: 1915 1 3 1 1916 X--->A----->B<---Y 1917 ^ | 1918 2 | |4 1919 | v 1920 W--->D C<---Z 1921 1 | 1 1922 5| 1923 v 1924 E 1926 with all threads transparent, and we have a fully set up non-looping 1927 path. 1929 A.15. Continuing to Use an Old Path 1931 Nothing in the above requires that any node withdraw a transparent 1932 thread. Existing transparent threads (established paths) can 1933 continue to be used, even while new paths are being set up. 1935 If this is done, then some node may have both a transparent outgoing 1936 thread (previous path) and a colored outgoing thread (new path being 1937 set up). This would happen only if the downstream links for the two 1938 threads are different. When the colored outgoing thread rewinds 1939 (and becomes transparent), the previous path should be withdrawn.