idnits 2.17.1 draft-ietf-mpls-loop-prevention-01.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 8) 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 550 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 1401: '... the loop, some node in the loop MUST...' Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 44 has weird spacing: '... can be u...' == Line 46 has weird spacing: '...chanism can b...' == Line 47 has weird spacing: '...ordered downs...' == Line 48 has weird spacing: '...ount of infor...' == Line 51 has weird spacing: '...d, but only ...' == (545 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 9110 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 To view the list Internet-Draft Shadow Directories, see 39 http://www.ietf.org/shadow.html. 41 Abstract 43 This paper presents a simple mechanism, based on "threads", which 44 can be used to prevent MPLS from setting up label switched path 45 (LSPs) which have loops. The mechanism is compatible with, but does 46 not require, VC merge. The mechanism can be used with either the 47 ordered downstream-on-demand allocation or ordered downstream 48 allocation. The amount of information that must be passed in a 49 protocol message is tightly bounded (i.e., no path-vector is used). 50 When a node needs to change its next hop, a distributed procedure is 51 executed, but only nodes which are downstream of the change are 52 involved. 54 Table of contents 56 1 Introduction .......................................... 3 57 2 Basic definitions ..................................... 4 58 3 Thread basics ......................................... 5 59 3.1 Thread attributes ..................................... 5 60 3.2 Thread loop ........................................... 6 61 3.3 Primitive thread actions .............................. 7 62 3.4 Examples of primitive thread actions ................. 9 63 4 Thread algorithm ...................................... 13 64 5 Applicability of the algorithm ........................ 14 65 5.1 LSP Loop prevention/detection ......................... 14 66 5.2 Using old path while looping on new path .............. 14 67 5.3 How to deal with ordered downstream allocation ........ 14 68 5.4 How to realize load splitting ......................... 14 69 6 Why this works ........................................ 16 70 6.1 Why a thread with unknown hop count is extended ....... 16 71 6.2 Why a rewound thread cannot contain a loop ............ 16 72 6.2.1 Case1: LSP with known link hop counts ................. 16 73 6.2.1 Case2: LSP with unknown link hop counts ............... 16 74 6.3 Why L3 loop is detected ............................... 16 75 6.4 Why L3 loop is not mis-detected ....................... 16 76 6.5 How a stalled thread automatically recovers from loop . 17 77 6.6 Why different colored threads do not chase each other . 17 78 7 Loop prevention examples .............................. 18 79 7.1 First example ......................................... 18 80 7.2 Second example ........................................ 22 81 8 Thread control block .................................. 23 82 8.1 Finite state machine .................................. 24 83 9 Comparison with path-vector/diffusion method .......... 27 84 10 Security considerations ............................... 27 85 11 Intellectual property considerations .................. 27 86 12 Acknowledgments ....................................... 28 87 13 Authors' Addresses .................................... 28 88 14 References ............................................ 28 89 Appendix A Further discussion of the algorithm ............. 29 91 1. Introduction 93 This paper presents a simple mechanism, based on "threads", which 94 can be used to prevent MPLS from setting up label switched paths 95 (LSPs) which have loops. 97 When an LSR finds that it has a new next hop for a particular FEC 98 (Forwarding Equivalence Class) [1], it creates a thread and extends 99 it downstream. Each such thread is assigned a unique "color", such 100 that no two threads in the network can have the same color. 102 For a given LSP, once a thread is extended to a particular next hop, 103 no other thread is extended to that next hop unless there is a 104 change in the hop count from the furthest upstream node. The only 105 state information that needs to be associated with a particular next 106 hop for a particular LSP is the thread color and hop count. 108 If there is a loop, then some thread will arrive back at an LSR 109 through which it has already passed. This is easily detected, since 110 each thread has a unique color. 112 Section 3 and 4 provide procedures for determining that there is no 113 loop. When this is determined, the threads are "rewound" back to 114 the point of creation. As they are rewound, labels get assigned. 115 Thus labels are NOT assigned until loop freedom is guaranteed. 117 While a thread is extended, the LSRs through which it passes must 118 remember its color and hop count, but when the thread has been 119 rewound, they need only remember its hop count. 121 The thread mechanism works if some, all, or none of the LSRs in the 122 LSP support VC-merge. It can also be used with either the ordered 123 downstream on-demand label allocation or ordered downstream 124 unsolicited label allocation [2,3]. The mechanism can also be 125 applicable to loop detection, old path retention, and 126 load-splitting. 128 The state information which must be carried in protocol messages, 129 and which must be maintained internally in state tables, is of fixed 130 size, independent of the network size. Thus the thread mechanism is 131 more scalable than alternatives which require that path-vectors be 132 carried. 134 To set up a new LSP after a routing change, the thread mechanism 135 requires communication only between nodes which are downstream of 136 the point of change. There is no need to communicate with nodes 137 that are upstream of the point of change. Thus the thread mechanism 138 is more robust than alternatives which require that a diffusion 139 computation be performed (see section 9). 141 2. Basic definitions 143 LSP 145 We will use the term LSP to refer to a multipoint-to-point tree 146 whose root is the egress node. See section 3.5 of [3]. 148 In the following, we speak as if there were only a single LSP being 149 set up in the network. This allows us to talk of incoming and 150 outgoing links without constantly saying something like "for the 151 same LSP. 153 Incoming Link, Upstream Link 154 Outgoing Link, Downstream Link 156 At a given node, a given LSP will have one or more incoming, or 157 upstream links, and one outgoing or downstream link. A "link" is 158 really an abstract relationship with an "adjacent" LSR; it is an 159 "edge" in the "tree", and not necessarily a particular concrete 160 entity like an "interface". 162 Leaf Node, Ingress Node 164 A node which has no upstream links. 166 Eligible Leaf Node 168 A node which is capable of being a leaf node. For example, a node 169 is not an eligible leaf node if it is not allowed to directly inject L3 170 packets created or received at the node into its outgoing link. 172 Link Hop Count 174 Every link is labeled with a "link hop count". This is the number 175 of hops between the given link and the leaf node which is furthest 176 upstream of the given link. At any node, the link hop count for 177 the downstream link is one more than the largest of the hop counts 178 associated with the upstream links. 180 We define the quantity "Hmax" at a given node to be the maximum of 181 all the incoming link hop counts. Note that, the link hop count of 182 the downstream link is equal to Hmax+1. At a leaf node, Hmax is 183 set to be zero. 185 An an example of link hop counts is shown in Fig.1. 187 1 2 188 A---B---C K 189 | | 190 |3 |1 191 | | 192 | 4 5 | 6 7 193 D---G---H---I---J 194 | 195 |2 196 1 | 197 E---F 199 Fig.1 Example of link hop counts 201 Next Hop Acquisition 203 Node N thought that FEC F was unreachable, but now has a next hop 204 for it. 206 Next Hop Loss 208 Node N thought that node A was the next hop for FEC F, but now no 209 longer has the next hop for FEC F. A node loses a next hop whenever 210 the next hop goes down. 212 Next Hop Change 214 At node N, the next hop for FEC F changes from node A to node B, 215 where A is different than B. A next hop change event can be seen as 216 a combination of a next hop loss event on the old next hop and a 217 next hop acquisition event on the new next hop. 219 3. Thread basics 221 A thread is a sequence of messages used to set up an LSP, in the 222 "ordered downstream-on-demand" (ingress-initiated ordered control) 223 style. 225 3.1. Thread attributes 227 There are three attributes related to threads. They may be encoded 228 into a single thread object as: 230 1 2 3 231 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 232 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 233 | | 234 + Color + 235 | | 236 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 237 | Hop Count | TTL | Reserved | 238 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 240 Thread Color 242 Every time a path control message is initiated by a node, the node 243 assigns a unique "color" to it. This color is to be unique in both 244 time and space: its encoding consists of an IP address of the node 245 concatenated with a unique event identifier from a numbering space 246 maintained by the node. The path setup messages that the node sends 247 downstream will contain this color. Also, when the node sends such 248 a message downstream, it will remember the color, and this color 249 becomes the color of the downstream link. 251 When a colored message is received, its color becomes the color of 252 the incoming link. The thread which consists of messages of a 253 certain color will be known as a thread of that color. 255 A special color value "transparent"(=all 0's) is reserved. 257 One possible method for unique color assignment is, starting the 258 event identifier from its initial value, and incrementing it by one 259 (modulo its maximum value) each time a color is assigned. In this 260 method, the initial event identifier is either selected at random or 261 assigned to be larger than the largest event identifier used on the 262 previous system incarnation. 264 Thread Hop Count 266 In order to maintain link hop counts, we need to carry hop counts in 267 the path control messages. For instance, a leaf node would assign a 268 hop count of 1 to its downstream link, and would store that value 269 into a path setup message it sends downstream. When a path setup 270 message is sent downstream, a node would assign a hop count which is 271 one more than the largest of the incoming link hop counts, to its 272 downstream link, and would store that value into a path setup 273 message it sends downstream. Once the value is stored in a path 274 control message, we may refer to it has a "thread hop count". 276 A special hop count value "unknown"(=0xff), which is larger than any 277 other known value, is used when a loop is found. Once the thread 278 hop count is "unknown", it is not increased any more as the thread 279 is extended. 281 Thread TTL 283 To avoid infinite looping of control messages in some cases, a 284 thread TTL is used. When a node creates a path control message and 285 sends it downstream, it sets a TTL to the message, and the TTL is 286 decremented at each hop. When the TTL reaches 0, the message is not 287 forwarded any more. Unlike the thread hop counts and the thread 288 colors, the thread TTLs do not needs to be stored in incoming links. 290 3.2. Thread loop 292 When the same colored thread is received on multiple incoming links, 293 or the received thread color was assigned by the receiving node, it 294 is said that the thread forms a loop. A thread creator can tell 295 whether it assigned the received thread color by checking the IP 296 address part of the received thread color. 298 3.3. Primitive thread actions 300 Five primitive actions are defined in order to prevent LSP loops by 301 using threads: "extending", "rewinding", "withdrawing", "merging", 302 and "stalling". This section describes only each primitive action 303 and does not describe how these primitive actions are combined and 304 how the algorithm totally works. The main body of the algorithm is 305 described in section 4. 307 Thread Extending 309 When a node starts to send a path setup message to its next hop with 310 a set of thread attributes, it is said that "the node creates a 311 thread and extends it downstream". When a node receives a path 312 setup message from an upstream node with a set of thread attributes 313 and forwards it downstream, it is said that "the node receives a 314 thread and extends it downstream". The color and hop count of the 315 thread become the color and hop count of the outgoing link. 316 Whenever a thread is received on a particular link, the color and 317 hop count of that thread become the color and hop count of that 318 incoming link, replacing any color and hop count that the link may 319 have had previously. 321 For example, when an ingress node initiates a path setup, it creates 322 a thread and extends it downstream by sending a path setup message. 323 The thread hop count is set to be 1, and the thread color is set to 324 be the ingress node's address with an appropriate event identifier, 325 and the thread TTL is set to be its maximum value. 327 When a node receives a thread and extends it downstream, the node 328 either (i) extends the thread without changing color, or (ii) extend 329 the thread with changing color. The received thread is extended 330 with changing color if it is received on a new incoming link and 331 extended on an already existing outgoing link, otherwise, it is 332 extended without changing color. When a thread is extended with 333 changing color, a new colored thread is created and extended. 335 Thread creation does not occur only at leaf nodes. If an 336 intermediate node has an incoming link, it will create and extend a 337 new thread whenever it acquires a new next hop. 339 When a node notifies a next hop node of a decrease of the link hop 340 count, if it is not extending a colored thread, a transparent thread 341 is extended. 343 Thread Merging 345 When a node which has a colored outgoing link receives a new thread, 346 it does not necessarily extend the new thread. It may instead 'merge' 347 the new threads into the existing outgoing thread. In this case, no 348 messages are sent downstream. Also, if a new incoming thread is 349 extended downstream, but there are already other incoming threads, 350 these other incoming threads are considered to be merged into the 351 new outgoing thread. 353 Specifically, a received thread is merged if all the following 354 conditions hold: 356 o A colored thread is received by node N, AND 357 o The thread does not form a loop, AND 358 o N is not an egress node, AND 359 o N's outgoing link is colored, AND 360 o N's outgoing link hop count is at least one greater than the hop 361 count of the newly received thread. 363 When an outgoing thread rewinds (see below), any incoming threads 364 which have been merged with it will rewind as well. 366 Thread Stalling 368 When a colored thread is received, if the thread forms a loop, the 369 received thread color and hop count are stored on the receiving link 370 without being extended. This is the special case of thread merging 371 applied only for threads forming a loop and referred to as the 372 "thread stalling", and the incoming link storing the stalled thread 373 is called "stalled incoming link". A distinction is made between 374 stalled incoming links and unstalled incoming links. 376 Thread Rewinding 378 When a thread reaches a node which satisfies a particular loop-free 379 condition, the node returns an acknowledgment message back to the 380 message initiator in the reverse path on which the thread was 381 extended. The transmission of the acknowledgment messages is the 382 "rewinding" of the thread. 384 The loop-free condition is: 386 o A colored thread is received by the egress node, OR 387 o All of the following conditions hold: 388 (a) A colored thread is received by node N, AND 389 (b) N's outgoing link is transparent, AND 390 (c) N's outgoing link hop count is at least one greater than the 391 hop count of the newly received thread. 393 When a node rewinds a thread which was received on a particular 394 link, it changes the color of that link to transparent. 396 If there is a link from node M to node N, and M has extended a 397 colored thread to N over that link, and M determines (by receiving a 398 message from N) that N has rewound that thread, then M sets the 399 color of its outgoing link to transparent. M then continues 400 rewinding the thread, and in addition, rewinds any other incoming 401 thread which had been merged with the thread being rewound, 402 including stalled threads. 404 Each node can start label switching after the thread colors in all 405 incoming and outgoing links becomes transparent. 407 Note that transparent threads are threads which have already been 408 rewound; hence there is no such thing as rewinding a transparent 409 thread. 411 Thread Withdrawing 413 It is possible for a node to tear down a path. A node tears down 414 the portion of the path downstream of itself by sending teardown 415 messages to its next hop. This process is known as the "thread 416 withdrawing". 418 For example, suppose a node is trying to set up a path, and then 419 experiences a next hop change or a next hop loss. It will withdraw 420 the thread that it had extended down its old next hop. 422 If node M has extended a thread to node N, and node M then withdraws 423 that thread, N now has one less incoming link than it had before. If 424 N now has no other unstalled incoming links and N is not an eligible 425 leaf node, it must withdraw its outgoing thread. If N still has an 426 unstalled incoming link or N is an eligible leaf node, it may (or 427 may not) need to change the hop count of the outgoing link. 429 N needs to change the outgoing hop count if: 431 o The incoming link hop count that was just removed had a larger 432 hop count than any of the remaining incoming links, AND 433 o One of the following conditions holds: 434 (a) The outgoing link is transparent, OR 435 (b) The outgoing link has a known hop count. 437 If the outgoing link is transparent, it remains transparent, but the 438 new hop count needs to be sent downstream. If the outgoing link is 439 colored, a new thread (with a new color) needs to be created and 440 extended downstream. 442 3.4. Examples of primitive thread actions 444 The following notations are used to illustrate examples of primitive 445 actions defined for threads. 447 A pair of thread attributes stored in each link is represented by 448 "(C,H)", where C and H represent the thread color and thread hop 449 count, respectively. 451 A thread marked "+" indicates that it is created or received now. A 452 thread marked "-" indicates that it is withdrawn now. 454 A link labeled with squared brackets (e.g., "[a]") indicates that it 455 is an unstalled link. A link labeled with braces (e.g., "{a}") 456 indicates that it is a stalled link. 458 Fig. 2 shows an example in which a leaf node A creates a blue 459 thread and extends it downstream. 461 (bl,1) 462 A---[o1]---> 464 Fig.2 Thread extending at leaf node 466 Fig.3 shows an example of thread extending without changing color at 467 intermediate node. Assume that a node B has no incoming and 468 outgoing link before receiving a blue thread. When node B receives 469 the blue thread of hop count 1 on a new incoming link i1, it extends 470 the thread downstream without changing color (Fig.3(a)). After the 471 blue thread is extended, node B receives a red thread of hop count 472 unknown on incoming link i1 again (Fig.3(b)). The red thread is 473 also extended without changing its color, since both i1 and o1 474 already exists. 476 (bl,1)+ (bl,2) (re,U)+ (re,U) 477 ----[i1]--->B---[o1]----> ----[i1]--->B----[o1]---> 479 Fig.3(a) Fig.3(b) 481 Fig.3 Thread extending without changing color 483 Fig.4 shows an example of thread extending with changing color. 484 There are single incoming link i1 and single outgoing link o1 in 485 Fig.4(a). Then a red thread of hop count 3 is received on a new 486 incoming link i2. In this case, the received thread is extended 487 with changing color, i.e., a new green thread is created and 488 extended (Fig.4(b)), since o1 already exists. 490 (bl,1) (bl,2) (bl,1) (gr,4) 491 ----[i1]--->B----[o1]---> ----[i1]--->B----[o1]---> 492 ^ 493 | 494 ----[i2]----+ 495 (re,3)+ 497 Fig.4(a) Fig.4(b) 499 Fig.4 Thread extending with changing color 501 Fig.5 shows an example of thread merging. When a node B receives a 502 red thread of hop count 3, the received thread is not extended since 503 the outgoing link hop count is at least one greater than the 504 received thread hop count. Both the red and blue threads will be 505 rewound when the blue thread on outgoing link o1 is rewound. 507 (bl,3) (bl,4) 508 ----[i1]--->B----[o1]---> 509 ^ 510 | 511 ----[i2]----+ 512 (re,3)+ 514 Fig.5 Thread merging 516 Figs 6 and 7 show examples of thread stalling. When a node B 517 receives a blue thread of hop count 10 on incoming link i2 in Fig.6, 518 it "stalls" the received thread since the blue thread forms a loop. 519 In Fig.7, a leaf node A finds the loop of its own thread. 521 (bl,3) (bl,4) 522 ----[i1]--->B----[o1]---> 523 ^ 524 | 525 ----{i2}----+ 526 (bl,10)+ 528 Fig.6 Thread stalling (1) 530 (bl,10)+ (bl,1) 531 ----{i1}--->A----[o1]---> 533 Fig.7 Thread stalling (2) 535 Fig.8 shows an example of thread rewinding. When the yellow thread 536 which is currently being extended is rewound (Fig.8(a)), the node 537 changes all the incoming and outgoing thread color to transparent, 538 and propagates thread rewinding to upstream nodes (Fig.8(b)). 540 (bl,1) (ye,2) (tr,1) (tr,2) 541 ----[i2]--->B----[o1]---> ----[i2]--->B----[o1]---> 542 ^ ^ 543 | | 544 ----[i3]----+ ----[i3]----+ 545 (ye,1) (tr,1) 547 Fig.8(a) Fig.8(b) 549 Fig.8 Thread rewinding 551 Fig.9 shows an example of thread withdrawing. In Fig.9(a), the red 552 thread on incoming link i2 is withdrawn. Then Hmax decreases from 3 553 to 1, and node B creates a new green thread and extends it 554 downstream, as shown in Fig.9(b). 556 (bl,1) (re,4) (bl,1) (gr,2)+ 557 ----[i1]--->B---[o1]---> ----[i1]--->B----[o1]---> 558 ^ 559 | 560 ----[i2]----+ 561 (re,3)- 563 Fig.9(a) Fig.9(b) 565 Fig.9 Thread withdrawing (1) 567 Fig.10 shows another example of thread withdrawing. In Fig.10(a), 568 the red thread on incoming link i3 is withdrawn. In this case, Hmax 569 decreases from unknown to 1, however, no thread is extended as shown 570 in Fig.10(b), since the outgoing link has a colored thread and the 571 hop count is unknown. 573 (bl,1) (re,U) (bl,1) (re,U) 574 ----[i2]--->B----[o1]---> ----[i2]--->B----[o1]---> 575 ^ 576 | 577 ----[i3]----+ 578 (re,U)- 580 Fig.10(a) Fig.10(b) 582 Fig.10 Thread withdrawing (2) 584 Fig.11 shows another example of thread withdrawing. In Fig.11(a), 585 the transparent thread on incoming link i3 is withdrawn. In this 586 case, a transparent thread is extended (Fig.11(b)), since Hmax 587 decreases and the outgoing link is transparent. 589 (tr,1) (tr,U) (tr,1) (tr,2)+ 590 ----[i2]--->B----[o1]---> ----[i2]--->B----[o1]---> 591 ^ 592 | 593 ----[i3]----+ 594 (tr,U)- 596 Fig.11(a) Fig.11(b) 598 Fig.11 Thread withdrawing (3) 600 4. Thread algorithm 602 The ordered downstream-on-demand allocation is assumed here, 603 however, the algorithm can be adapted to the ordered downstream 604 allocation, as shown in section 5. 606 In the algorithm, a next hop change event will be separated into two 607 events: a next hop loss event on the old next hop and a next hop 608 acquisition event on the new next hop, in this order. 610 The following notations are defined: 612 Hmax: the largest incoming link hop count 613 Ni: the number of unstalled incoming links 615 The thread algorithm is described as follows. 617 When a node acquires a new next hop, it creates a colored thread and 618 extends it downstream. 620 When a node loses a next hop to which it has extended a thread, it 621 may withdraw that thread. As described in section 3, this may or 622 may not cause the next hop to take some action. Among the actions 623 the next hop may take are withdrawing the thread from its own next 624 hop, or extending a new thread to its own next hop. 626 A received colored thread is either stalled, merged, rewound, or 627 extended. A thread with TTL zero is never extended. 629 When a received thread is stalled at a node, if Ni=0 and the node 630 is not an eligible leaf node, initiate a thread withdrawing. 631 Otherwise, if Ni>0 and the received thread hop count is not unknown, 632 a colored thread of hop count unknown is created and extended. If 633 the received thread hop count is unknown, no thread is extended and 634 no further action is taken. 636 When a thread being extended is rewound, if the thread hop count is 637 greater than one more than Hmax, a transparent thread of hop count 638 (Hmax+1) is extended downstream. 640 When a node that has an transparent outgoing link receives a 641 transparent thread, if Hmax decreases the node extends it 642 downstream without changing color. 644 5. Applicability of the algorithm 646 The thread algorithm described in section 4 can be applied to 647 various LSP management policies. 649 5.1. LSP Loop prevention/detection 651 The same thread algorithm is applicable to both LSP loop prevention 652 and detection. 654 In loop prevention mode, a node transmits a label mapping (including 655 a thread object) for a particular LSP only when it rewinds the 656 thread for that LSP. No mapping message is sent until the thread 657 rewinds. 659 On the other hand, if a node operates in loop detection mode, it 660 returns a label mapping message without a thread object immediately 661 after receiving a colored thread. A node which receives a label 662 mapping message that does not have a thread object will not rewind 663 the thread. 665 5.2. Using old path while looping on new path 667 When a route changes, one might want to continue to use the old path 668 if the new route is looping. This is achieved simply by holding the 669 label assigned to the downstream link on the old path until the 670 thread being extended on the new route gets rewound. This is an 671 implementation choice. 673 5.3. How to deal with ordered downstream allocation 675 The thread mechanism can be also adapted to ordered downstream 676 allocation mode (or the egress-initiated ordered control) by 677 regarding the event of newly receiving of a label mapping message 678 [4] from the next hop as a next hop acquisition event. 680 Note that a node which doesn't yet have an incoming link behaves as 681 a leaf. In the case where the tree is being initially built up 682 (e.g., the egress node has just come up), each node in turn will 683 behave as a leaf for a short period of time. 685 5.4. How to realize load splitting 687 A leaf node can easily perform load splitting by setting up two 688 different LSPs for the same FEC. The downstream links for the two 689 LSPs are simply assigned different colors. The thread algorithm now 690 prevents a loop in either path, but also allows the two paths to 691 have a common downstream node. 693 If some intermediate node wants to do load splitting, the following 694 modification is made. Assume that there are multiple next hops for 695 the same FEC. If there are n next hops for a particular FEC, the 696 set of incoming links for that FEC's LSP can be partitioned into n 697 subsets, where each subset can be mapped to a distinct outgoing 698 link. This provides n LSPs for the FEC. Each such LSP uses a 699 distinct color for its outgoing link. The thread algorithm now 700 prevents a loop in any of the paths, but also allows two or more of 701 the paths to have a common downstream node. 703 In this case, an interesting situation may happen. Let's say that 704 in Fig.12, node B has two incoming links, i1 and i2, and two 705 outgoing links, o1 and o2, such that i1 is mapped to o1, while i2 is 706 mapped to o2. 708 If a blue thread received on i1 and extended on o1 is again received 709 at node B on i2, the blue thread is not regarded as forming a loop, 710 since i1 and i2 are regarded as belonging to different subsets. 711 Instead, the blue thread received on i2 is extended on o2. If the 712 thread extended on o2 is rewound, a single loop-free LSP which 713 traverses node B twice is established. 715 +------------------...--------------------+ 716 . (bl,3) (bl,4) | 717 . ----[i1]---+ +--[o1]---> .... --+ 718 . \ / 719 . v / 720 | B 721 | 722 +-----------[i2]--->B----[o2]---> 723 (bl,10)+ (bl,11) 725 Fig.12 Load splitting at intermediate node 727 There is another type of load splitting, in which packets arrived at 728 single incoming link can be label switched to any one of multiple 729 outgoing links. This case does not seem to be a good load-splitting 730 scheme, since the packet order in the same FEC is not preserved. 731 Thus, this draft does not focus on this case. 733 Whether that's a good type of load splitting or not, the fact 734 remains that ATM-LSRs cannot load split like this because ATM 735 switches just don't have the capability to make forwarding decisions 736 on a per-packet basis. 738 6. Why this works 740 6.1. Why a thread with unknown hop count is extended 742 In the algorithm, a thread of unknown hop count is extended when a 743 thread loop is detected. This reduces the number of loop prevention 744 messages by merging threads (of known hop count) that are flowing 745 inside or outside the loop. See Appendix A.12. 747 6.2. Why a rewound thread cannot contain a loop 749 6.2.1. Case1: LSP with known link hop counts 751 How can we be sure that an established path does not contain a loop 752 when the outgoing link hop count is NOT "unknown"? 754 Consider a sequence of LSRs , such that there is a loop 755 traversing the LSRs in the sequence. (I.e., packets from R1 go to 756 R2, then to R3, etc., then to Rn, and then from Rn to R1.) 758 Suppose that the thread hop count of the link between R1 and R2 is 759 k. Then by the above procedures, the hop counts between Rn and R1 760 must be k+n-1. But the algorithm also ensures that if a node has an 761 incoming hop count of j, its outgoing link hop count must be at 762 least of j+1. Hence, if we assume that the LSP established as a 763 result of thread rewinding contains a loop, the hop counts between 764 R1 and R2 must be at least k+n. From this we may derive the absurd 765 conclusion that n=0, and we may therefore conclude that there is no 766 such sequence of LSRs. 768 6.2.1. Case2: LSP with unknown link hop counts 770 An established path does not contain a loop as well, when the 771 outgoing link hop count is "unknown". This is because a colored 772 thread of unknown hop count is never rewound unless it reaches 773 egress. 775 6.3. Why L3 loop is detected 777 Regardless of whether the thread hop count is known or unknown, if 778 there is a loop, then some node in the loop will be the last node to 779 receive a thread over a new incoming link. This thread will always 780 arrive back at that node, without its color having changed. Hence 781 the loop will always be detected by at least one of the nodes in the 782 loop. 784 6.4. Why L3 loop is not mis-detected 786 Since no node ever extends the same colored thread downstream twice, 787 a thread loop is not detected unless there actually is an L3 routing 788 loop. 790 6.5. How a stalled thread automatically recovers from loop 792 Once a thread is stalled in a loop, the thread (or the path setup 793 request) effectively remains in the loop, so that a path 794 reconfiguration (i.e., thread withdrawing on the old path and thread 795 extending on the new path) can be issued from any node that may 796 receive a route change event so as to break the loop. 798 6.6. Why different colored threads do not chase each other 800 In the algorithm, multiple thread color and/or hop count updates may 801 happen if several leaf nodes start extending threads at the same 802 time. How can we prevent multiple threads from looping unlimitedly? 804 First, when a node finds that a thread forms a loop, it creates a 805 new thread of hop count "unknown". All the looping threads of a 806 known hop count which later arrive at the node would be merged into 807 this thread. Such a thread behaves like a thread absorber. 809 Second, the "thread extending with changing color" prevents two 810 threads from chasing each other. 812 Suppose that a received thread were always extended without changing 813 color. Then we would encounter the following situation. 815 G Y 816 | | 817 v v 818 R1------>R2 819 ^ | 820 | v 821 R4<------R3 823 Fig.13 Example of thread chasing 825 In Fig.13, (1) node G acquires R1 as a next hop, and starts to 826 extend a green thread of hop count 1, (2) node Y acquires R2 as a 827 next hop, and starts to extend a yellow thread of hop count 1, and 828 (3) both node G and node Y withdraws their threads before these 829 threads go round. 831 In this case, the yellow and green threads would go round and get 832 back to R2 and R1, respectively. When the threads get back to R2 833 and R1, however, the incoming links that store the yellow and green 834 colors no longer exist. As a result, the yellow and green threads 835 would chase each other forever in the loop. 837 However, since we have the "extending with changing color" 838 mechanism, this does not actually happen. When a green thread is 839 received at R2, R2 extends the thread with changing color, i.e., 840 creates a new red thread and extends it. Similarly, when a yellow 841 thread is received at R1, R1 creates a new purple thread and extends 842 it. Thus, the thread loop is detected even after node G and node Y 843 withdraw threads. This ensures that a thread is extended around the 844 loop which has a color assigned by some node that is in the loop. 846 There is at least one case even the "extending with changing color" 847 mechanism cannot treat, that is, the "self-chasing" in which thread 848 extending and thread withdrawing with regard to the same thread 849 chase each other in a loop. This case would happen when a node 850 withdraw a thread immediately after extending it into an L3 loop. 852 A heuristics for self-chasing is to delay the execution of thread 853 withdrawing at an initiating node of the thread withdrawing. 854 Anyway, the thread TTL mechanism can eliminate any kind of thread 855 looping. 857 7. Loop prevention examples 859 In this section, we show two examples to show how the algorithm can 860 prevent LSP loops in given networks. 862 We assume that the ordered downstream-on-demand allocation is 863 employed, that all the LSPs are with regard to the same FEC, and 864 that all nodes are VC-merge capable. 866 7.1. First example 868 Consider an MPLS network shown in Fig.14 in which an L3 loop exists. 869 Each directed link represents the current next hop of the FEC at 870 each node. Now leaf nodes R1 and R6 initiate creation of an LSP. 872 R11 ------- R10 <-------------------- R9 873 | | ^ 874 | | | 875 | | | 876 v v | 877 R1 -------> R2 --------> R3 --------> R4 --------- R5 878 [leaf] ^ 879 | 880 | 881 | 882 R6 -------> R7 --------> R8 883 [leaf] 885 Fig. 14 Example MPLS network (1) 887 Assume that R1 and R6 send a label request message at the same time, 888 and that the initial thread TTL is 255. First we show an example of 889 how to prevent LSP loops. 891 A set of thread attributes is represented by (color, hop count, TTL). 893 The request from R1 and R6 contains (re,1,255) and (bl,1,255), 894 respectively. 896 Assume that R3 receives the request originated from R1 before 897 receiving the request originated from R6. When R3 receives the 898 first request with red thread, R3 forwards it with (re,3,253) 899 without changing thread color, since both the receiving incoming 900 link and the outgoing link are newly created. Then R3 receives the 901 second request with blue thread. In this time, the outgoing link is 902 already exists. Thus, R3 performs thread extending with changing 903 color, i.e., creates a new brown thread and forwards the request 904 with (br,4,255). 906 When R2 receives the request from R10 with (re,6,250), it finds that 907 the red thread forms a loop, and stalls the red thread. Then, R2 908 creates a purple thread of hop count unknown and extends it 909 downstream by sending a request with (pu,U,255) to R3, where "U" 910 represents "unknown". 912 After that, R2 receives another request from R10 with (br,7,252). 913 The brown thread is merged into purple thread. R2 sends no request 914 to R3. 916 On the other hand, the purple thread goes round without changing 917 color through existing links, and R2 finds the thread loop and 918 stalls the purple thread. Since the received thread hop count is 919 unknown, no thread is created any more. In this case no thread 920 rewinding occurs. The current state of the network is shown in 921 Fig.15. 923 *: location of thread stalling 925 (pu,U) 926 R11 ------- R10 <-------------------- R9 927 | | ^ 928 | |(pu,U)* | 929 | | |(pu,U) 930 v v | 931 R1 -------> R2 --------> R3 --------> R4 --------- R5 932 [leaf] (re,1) (pu,U) ^ (pu,U) 933 | 934 | (bl,3) 935 | 936 R6 -------> R7 --------> R8 937 [leaf] (bl,1) (bl,2) 939 Fig.15 The network state 941 Then R10 changes its next hop from R2 to R11. 943 Since R10 has a purple thread on the old downstream link, it first 944 sends a path teardown message to the old next hop R2 for withdrawing 945 the purple thread. Next, it creates a green thread of hop count 946 unknown and sends a request with (gr,U,255) to R11. 948 When R2 receives the teardown message from R10, R2 removes the 949 stalled incoming link between R10 and R2. 951 On the other hand, the green thread reaches R1 and Hmax is updated 952 from zero to unknown. In this case, R1 performs thread extending 953 with changing color since the thread is received on a new incoming 954 link but extended on the already existing outgoing link. As a 955 result, R1 creates an orange thread of hop count unknown and extend 956 it to R2. 958 The orange thread goes round through existing links without changing 959 color, and finally it is stalled at R1. 961 The state of the network is now shown in Fig.16. 963 *: location of thread stalling 965 (or,U) (or,U) 966 R11 <------ R10 <-------------------- R9 967 | | ^ 968 |(or,U)* | | 969 | | |(or,U) 970 v | | 971 R1 -------> R2 --------> R3 --------> R4 --------- R5 972 [leaf] (or,U) (or,U) ^ (or,U) 973 | 974 | (bl,3) 975 | 976 R6 -------> R7 --------> R8 977 [leaf] (bl,1) (bl,2) 979 Fig.16 The network state 981 Then R4 changes its next hop from R9 to R5. 983 Since R4 is extending an orange thread, it first sends a teardown 984 message to the old next hop R9 to withdraw the orange thread on the 985 old route. Next, it creates a yellow thread of hop count unknown, 986 and sends a request message with (ye,U,255) to R5. 988 Since R5 is the egress node, the yellow thread rewinding starts. R5 989 returns a label mapping message. The thread rewinding procedure is 990 performed at each node, as the label mapping message is returned 991 upstream hop-by-hop. 993 If R1 receives a label mapping message before receiving the orange 994 thread's withdrawal from R11, R1 returns a label mapping message to 995 R11. On receiving the orange thread's withdrawal, R1 will create a 996 transparent thread and extend it by sending an update message with 997 (tr,1,255) in order to notify downstream of the known hop count. 999 Otherwise, if R1 receives the orange thread's withdrawal before 1000 receiving a label mapping message, R1 removes the stalled incoming 1001 orange link and waits for rewinding of the outgoing orange thread. 1002 Finally, when R1 receives a label mapping message from R2, it 1003 creates a transparent thread (tr,1,255) and extend it downstream. 1005 In both cases, a merged LSP ((R1->R2),(R6->R7->R8))->R3->R4->R5) is 1006 established and every node obtains the correct link hop count. The 1007 final network state is shown in Fig.17. 1009 R11 <------ R10 <-------------------- R9 1010 | | | 1011 | | | 1012 | | | 1013 v | | 1014 R1 -------> R2 --------> R3 --------> R4 --------> R5 1015 [leaf] (tr,1) (tr,2) ^ (tr,4) (tr,5) 1016 | 1017 | (tr,3) 1018 | 1019 R6 -------> R7 --------> R8 1020 [leaf] (tr,1) (tr,2) 1022 Fig.17 The final network state 1024 7.2. Second example 1026 +----- R6----> R7-----+ 1027 | | 1028 | v 1029 R1---->R2 R4----->R5 1030 | ^ 1031 | | 1032 +--------->R3---------+ 1034 Fig.18 Example MPLS network (2) 1036 Assume that in Fig.18, there is an established LSP 1037 R1->R2->R3->R4->R5, and the next hop changes at R2 from R3 to R6. 1038 R2 sends a request to R6 with a red thread (re,2,255). When the 1039 request with (re,4,253) reaches R4, it extends the thread to R5 with 1040 changing color. Thus, a new green thread is created at R4 and 1041 extended to R5 by sending an update message with (gr,5,255). 1043 When R5 receives the update, it updates the incoming link hop count 1044 to 5 and returns an ack (or a notification message with a success 1045 code) for the update. When R4 receives the ack for the update, it 1046 returns a label mapping message to R7. 1048 When R2 receives the label mapping message on the new route, it 1049 sends a teardown message to R3. When R4 receives the teardown 1050 message, it does not sends an update to R5 since Hmax does not 1051 change. Now an established LSP R1->R2->R6->R7->R4->R5 is obtained. 1053 Then, the next hop changes again at R2 from R6 to R3. 1055 R2 sends a request with a blue thread (bl,2,255) to R3. R3 forwards 1056 the request with (bl,3,254) to R4. 1058 When R4 receives the request, it immediately returns a label mapping 1059 message to R3 since Hmax does not change. 1061 When R2 receives the label mapping message on the new route, it 1062 sends a teardown message to R6. The teardown message reaches R4, 1063 triggering an update message with a transparent thread (tr,4,255) to 1064 R5, since Hmax decreases from 4 to 3. R5 updates the incoming link 1065 hop count to 4 without returning an ack. 1067 8. Thread control block 1069 A thread control block (TCB) is maintained per LSP at each node and 1070 may contain the following information: 1072 - FEC 1073 - State 1074 - Incoming links 1075 Each incoming link has the following attributes: 1076 o neighbor: upstream neighbor node address 1077 o color: received thread color 1078 o hop count: received thread hop count 1079 o label 1080 o S-flag: indicates a stalled link 1081 - Outgoing links 1082 Each outgoing link has the following attributes: 1083 o neighbor: downstream neighbor node address 1084 o color: received thread color 1085 o hop count: received thread hop count 1086 o label 1087 o C-flag: indicates the link to the current next hop 1089 If a transparent thread is received on an incoming link for which no 1090 label is assigned yet or a non-transparent color is stored, discard 1091 the thread without entering the FSM. An error message may be 1092 returned to the sender. 1094 Whenever a thread is received on an incoming link, the following 1095 actions are taken before entering the FSM: (1) Store the received 1096 thread color and hop count on the link, replacing the old thread 1097 color and hop count, and (2) set the following flags that are used 1098 for an event switch within "Recv thread" event (see section 8.1). 1100 o Color flag (CL-flag): 1101 Set if the received thread is colored. 1102 o Loop flag (LP-flag): 1103 Set if the received thread forms a loop. 1104 o Arrived on new link flag (NL-flag): 1105 Set if the received thread arrives on a new incoming link. 1107 If LP-flag is set, there must be an incoming link L, other than the 1108 receiving link, which stores the same thread color as the received 1109 one. The TCB to which link L belongs is referred to as the 1110 "detecting TCB". If the receiving LSR is VC-merge capable, the 1111 detecting TCB and the receiving TCB is the same, otherwise, the two 1112 TCBs are different. 1114 Before performing a thread extending, the thread TTL is decremented 1115 by one. If the resulting TTL becomes zero, the thread is not 1116 extended but silently discarded. Otherwise, the thread is extended 1117 and the extended thread hop count and color are stored into the 1118 outgoing link. 1120 When a node receives a thread rewinding event, if the received 1121 thread color and the extending thread color are different, it 1122 discards the event without entering the FSM. 1124 8.1. Finite state machine 1126 An event which is "scheduled" by an action in an FSM must be passed 1127 immediately after the completion of the action. 1129 The following variables are used in the FSM: 1130 o Ni: number of unstalled incoming links 1131 o Hmax: largest incoming hop count 1132 o Hout: hop count of the outgoing link for the current next hop 1133 o Hrec: hop count of the received thread 1135 In the FSM, if Hmax=unknown, the value for (Hmax+1) becomes the 1136 value reserved for unknown hop count plus 1. For example, if 1137 Hmax=unknown=255, the value (Hmax+1) becomes 256. 1139 A TCB has three states; Null, Colored, and Transparent. When a TCB 1140 is in state Null, there is no outgoing link and Ni=0. The state 1141 Colored means that the node is extending a colored thread on the 1142 outgoing link for the current next hop. The state Transparent means 1143 that the node is the egress node or the outgoing link is 1144 transparent. 1146 The flag value "1" represents the flag is set, "0" represents the 1147 flag is not set, and "*" means the flag value is either 1 or 0. 1149 The FSM allows to have one transparent outgoing link on the old 1150 next hop and one colored outgoing link on the current next hop. 1151 However, it is not allowed to have a colored outgoing link on 1152 the old next hop. 1154 State Null: 1156 Event Action New state 1157 Recv thread 1158 Flags 1159 CL LP NL 1160 0 * * Do nothing. No change 1161 1 0 * If the node is egress, start thread rewinding Transparent 1162 and change the color of the receiving link to 1163 transparent. 1164 Otherwise, extend the received thread without Colored 1165 changing color. 1166 1 1 * Stall the received thread; if Hrec0 and HrecA----->B<---Y 1760 ^ | 1761 | v 1762 W--->D<-----C<---Z 1764 In this example, there is a loop A-B-C-D-A. However, there are also 1765 threads entering the loop from X, Y, Z, and W. Once the loop is 1766 detected, there really is no reason why any other thread should have 1767 to wrap around the loop. It would be better to simply mark presence 1768 of the loop in each node. 1770 To do this, we introduce the notion of the "unknown" hop count, U. 1771 This hop count value is regarded as being larger than any other hop 1772 count value. A thread with hop count U will be known as a 1773 "U-thread". 1775 A.12.1 When an incoming thread with a known hop count stalls, and there 1776 is an outgoing thread, we assign the hop count U to the outgoing 1777 thread, and we assign a new color to the outgoing thread as 1778 well. 1780 As a result, the next hop will then have an incoming U-thread, with 1781 the newly assigned color. This causes its outgoing thread in turn 1782 to be assigned hop count U and the new color. The rules we have 1783 already given will then cause each link in the loop to be assigned 1784 the new color and the hop count U. When this thread either reaches 1785 its originator, or any other node which already has an incoming 1786 thread of the same color, it stalls. 1788 In our example above, this will cause the links AB, BC, CD, and DA 1789 to be given hop count U. 1791 Now let's add one more rule: 1793 A.12.2 When a thread with a known hop count reaches a node that has a 1794 colored outgoing U-thread, the incoming thread merges into the 1795 outgoing thread. (Actually, this is just a consequence of a 1796 rule which has already been given, since U is greater than any 1797 known hop count.) 1799 Then if W, X, Y, or Z attempt to extend a thread to D, A, B, or C 1800 respectively, those threads will immediately stall. Once all the 1801 links are marked as being within a loop, no other threads are 1802 extended around the loop, i.e., no other setup messages will 1803 traverse the loop. 1805 Here is our example topology with the link hop counts that would 1806 exist during a loop: 1808 1 U 1 1809 X--->A----->B<---Y 1810 ^ | 1811 U | |U 1812 | v 1813 W--->D<-----C<---Z 1814 1 U 1 1816 A.13. Some Special Rules for Hop Count U 1818 When a U-thread encounters a thread with known hop count, the usual 1819 rules apply, remembering that U is larger than any known hop count 1820 value. 1822 However, we need to add a couple of special rules for the case when 1823 a U-thread encounters a U-thread. Since we can't tell which of the 1824 two U-threads is really the longer, we need to make sure that each 1825 of the U-threads is extended. 1827 A.13.1 If an incoming colored U-thread arrives at a node which already 1828 has an incoming U-thread of that color, or arrives at the node 1829 which created that U-thread, then the thread stalls. 1831 (Once a loop is detected, there is no need to further extend the 1832 thread.) 1834 A.13.2 If an incoming colored U-thread arrives at a node which has a 1835 transparent outgoing U-thread to its next hop, the incoming 1836 thread is extended. 1838 A.13.3 If an incoming colored U-thread arrives at a node which has a 1839 colored outgoing U-thread, and if the incoming link over which 1840 the thread was received was already an incoming link of the LSP, 1841 the thread is extended. 1843 A.13.4 If an incoming colored U-thread arrives at a node which has a 1844 colored outgoing U-thread, and if the incoming link over which 1845 the thread was received was NOT already an incoming link of the 1846 LSP, a new U-thread is created and extended. All the incoming 1847 threads are merged into it. This is known in the main body of 1848 this draft as "extending the thread with changing color". 1850 These rules ensure that an incoming U-thread is always extended (or 1851 merged into a new U-thread which then gets extended), unless it is 1852 already known to form a loop. 1854 What is the purpose of rule A.13.4? There are certain cases where a 1855 loop can form, but where the node which created the looping thread 1856 is not part of the loop. Rule A.13.4 ensures that when there is a 1857 loop, there will be a looping thread which was created by some node 1858 which is actually in the loop. This in turn ensures that the loop 1859 will be detected well before the thread TTL expires. 1861 The rule of "extending the thread with changing color" is also 1862 applied when extending a thread with a known hop count. 1864 A.13.5 When a received colored thread with a known hop count is 1865 extended, if the node has an outgoing thread, and if the 1866 incoming link over which the thread was received was NOT already 1867 an incoming link of the LSP, a new thread is created and 1868 extended. All the incoming threads are merged into it. This is 1869 an exceptional case of A.5.1. 1871 A.14. Recovering From a Loop 1873 Here is our example topology again, in the presence of a loop. 1875 1 U 1 1876 X--->A----->B<---Y 1877 ^ | 1878 U | |U 1879 | v 1880 W--->D<-----C<---Z 1881 1 U 1 1883 Suppose now that C's next hop changes from D to some other node E, 1884 thereby breaking the loop. For simplicity, we will assume that E is 1885 the egress node. 1887 C will withdraw its outgoing U-thread from D (9.1). It will also 1888 create a new thread (12.1), assign it a new color, assign it hop 1889 count U (the largest hop count of C's incoming threads), merge its 1890 two other incoming threads into the new thread (12.2), and extend 1891 the new thread to E, resulting the following configuration: 1893 1 U 1 1894 X--->A----->B<---Y 1895 ^ | 1896 U | |U 1897 | v 1898 W--->D C<---Z 1899 1 | 1 1900 U| 1901 v 1902 E 1904 When the thread from C to E rewinds, the merged threads also rewind 1905 (8.4). This process of rewinding can now proceed all the way back 1906 to the leafs. While this is happening, of course, D will note that 1907 its outgoing thread hop count should be 2, not U, and will make this 1908 change (9.3). As a result, A will note that its outgoing hop count 1909 should be 3, not U, and will make this change. So at some time in 1910 the future, we might see the following: 1912 1 3 1 1913 X--->A----->B<---Y 1914 ^ | 1915 2 | |U 1916 | v 1917 W--->D C<---Z 1918 1 | 1 1919 U| 1920 v 1921 E 1923 After a short period, we see the following: 1925 1 3 1 1926 X--->A----->B<---Y 1927 ^ | 1928 2 | |4 1929 | v 1930 W--->D C<---Z 1931 1 | 1 1932 5| 1933 v 1934 E 1936 with all threads transparent, and we have a fully set up non-looping 1937 path. 1939 A.15. Continuing to Use an Old Path 1941 Nothing in the above requires that any node withdraw a transparent 1942 thread. Existing transparent threads (established paths) can 1943 continue to be used, even while new paths are being set up. 1945 If this is done, then some node may have both a transparent outgoing 1946 thread (previous path) and a colored outgoing thread (new path being 1947 set up). This would happen only if the downstream links for the two 1948 threads are different. When the colored outgoing thread rewinds 1949 (and becomes transparent), the previous path should be withdrawn.