idnits 2.17.1 draft-ohba-mpls-loop-prevention-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-25) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. 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. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == No 'Intended status' indicated for this document; assuming Proposed Standard 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 10 instances of too long lines in the document, the longest one being 2 characters in excess of 72. ** There are 4 instances of lines with control characters in the document. ** 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 498: '... | OPTIONAL OBJECT | Type ...' RFC 2119 keyword, line 522: '... | OPTIONAL OBJECT | Type ...' RFC 2119 keyword, line 556: '... | OPTIONAL OBJECT | Type ...' RFC 2119 keyword, line 575: '... | OPTIONAL OBJECT | Type ...' RFC 2119 keyword, line 600: '... | OPTIONAL OBJECT | Type ...' Miscellaneous warnings: ---------------------------------------------------------------------------- -- 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 (July 1998) is 9416 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: Normative reference to a draft: ref. '1' -- Possible downref: Normative reference to a draft: ref. '2' == Outdated reference: A later version (-07) exists of draft-ietf-mpls-arch-01 == Outdated reference: A later version (-05) exists of draft-ietf-mpls-framework-02 -- Possible downref: Normative reference to a draft: ref. '4' -- No information found for draft-mpls-ldp-spec - is the name correct? -- Possible downref: Normative reference to a draft: ref. '5' Summary: 10 errors (**), 0 flaws (~~), 3 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Multi-Protocol Label Switching WG Yoshihiro Ohba 2 Internet-Draft Yasuhiro Katsube 3 Expiration Date: January 1999 Toshiba 5 Eric Rosen 6 Cisco Systems 8 Paul Doolan 9 Ennovate Networks 11 July 1998 13 MPLS Loop Prevention Mechanism 15 17 Status of this Memo 19 This document is an Internet-Draft. Internet-Drafts are working 20 documents of the Internet Engineering Task Force (IETF), its areas, 21 and its working groups. Note that other groups may also distribute 22 working documents as Internet-Drafts. 24 Internet-Drafts are draft documents valid for a maximum of six 25 months and may be updated, replaced, or obsoleted by other documents 26 at any time. It is inappropriate to use Internet-Drafts as 27 reference material or to cite them other than as "work in progress." 29 To learn the current status of any Internet-Draft, please check the 30 "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow 31 Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), 32 munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or 33 ftp.isi.edu (US West Coast). 35 Abstract 37 This paper presents a simple mechanism, based on 'threads', which 38 can be used to prevent MPLS from setting up label switched path 39 (LSPs) which have loops. The mechanism is compatible with, but does 40 not require, VC merge. The mechanism can be used with either the 41 ingress-initiated ordered control or the egress-initiated ordered 42 control. The amount of information that must be passed in a 43 protocol message is tightly bounded (i.e., no path-vector is used). 44 When a node needs to change its next hop, a distributed procedure is 45 executed, but only nodes which are downstream of the change are 46 involved. 48 Table of contents 50 1 Introduction ........................................ 2 51 2 Definitions ......................................... 3 52 3 Thread mechanism .................................... 4 53 3.1 Thread ............................................. 4 54 3.2 Loop prevention algorithm ........................... 5 55 3.3 Why this works ...................................... 6 56 3.4 Using old path while looping on new path ............ 7 57 3.5 How to deal with egress-initiated ordered control ... 7 58 3.6 How to realize load splitting from the ingress node . 8 59 4 Modification to LDP specification ................... 8 60 4.1 LDP objects ......................................... 8 61 4.2 Advertisement class messages ........................ 10 62 5 Examples ............................................ 12 63 5.1 First example ....................................... 12 64 5.2 Second example ...................................... 16 65 6 Comparison with path-vector/diffusion method ........ 16 66 7 Security considerations ............................. 17 67 8 Intellectual property considerations ................ 17 68 9 References .......................................... 17 70 1. Introduction 72 This paper presents a simple mechanism, based on "threads", which 73 can be used to prevent MPLS from setting up label switched paths 74 (LSPs) which have loops. The thread mechanism is a generalization 75 of [1]. 77 When an LSR finds that it has a new next hop for a particular FEC, 78 it creates a thread and extends it downstream. Each such thread is 79 assigned a unique "color", such that no two threads in the network 80 can have the same color. 82 Only a single thread for an LSP is ever extended to a particular 83 next hop as long as the thread length does not change. The only 84 state information that needs to be associated with a particular next 85 hop for a particular LSP is the thread color and length. 87 The procedures for determining just how far downstream a thread must 88 be extended are given in section 3. 90 If there is a loop, then some thread will arrive back at an LSR 91 through which it has already passed. This is easily detected, since 92 each thread has a unique color. 94 Section 3 provides procedures for determining that there is no loop. 95 When this is determined, the threads are "rewound" back to the point 96 of creation. As they are rewound, labels get assigned. Thus labels 97 are NOT assigned until loop freedom is guaranteed. 99 While a thread is extended, the LSRs through which it passes must 100 remember its color and length, but when the thread has been rewound, 101 they need only remember its length. 103 The thread mechanism works if some, all, or none of the LSRs in the 104 LSP support VC-merge. It can also be used with either the 105 ingress-initiated ordered control or the egress-initiated ordered 106 control [2,3]. 108 The state information which must be carried in protocol messages, 109 and which must be maintained internally in state tables, is of fixed 110 size, independent of the length of the LSP. Thus the thread 111 mechanism is more scalable than alternatives which require that 112 path-vectors be carried. 114 To set up a new LSP after a routing change, the thread mechanism 115 requires communication only between nodes which are downstream of 116 the point of change. There is no need to communicate with nodes 117 that are upstream of the point of change. Thus the thread mechanism 118 is more robust than alternatives which require that a diffusion 119 computation be performed. 121 The thread mechanism contains a number of significant improvements 122 when compared to the mechanism described in the previous version of 123 this internet draft. In particular: 125 o The thread mechanism allows a node whose next hop changes to 126 continue using the old LSP while setting up the new LSP (or 127 while waiting for the L3 routing to stabilize, so that a new 128 loop-free LSP can be set up) 130 o When a loop is detected, path setup is delayed, but it is 131 automatically resumed when the L3 routing stabilizes and the 132 loop disappears. No retry timers are needed. 134 o "Color" only has to be remembered while a path is being set up. 135 Once it is set up, the "color" (though not the length) can be 136 forgotten. 138 In this paper, we assume unicast LSPs. The loop prevention for 139 multicast LSPs is for further study. 141 2. Definitions 143 An LSP for a particular Forwarding Equivalence Class (FEC) [4] can 144 be thought of as a tree whose root is the egress LSR for that FEC. 145 With respect to a given node in the tree, we can speak of its 146 "downstream link" as the link which is closest to the root; the 147 node's other edges are "upstream links". 149 The term "link", as used here, refers to a particular relationship 150 on the tree, rather than to a particular physical relationship. In 151 the remainder of this section, when we will speak of the upstream 152 and downstream links of a node, we are speaking with reference to a 153 single LSP tree for a single FEC. 155 In the case of non-VC-merging, multiple links of the same FEC 156 between the neighboring nodes must be identified by identifiers that 157 are locally assigned by the upstream node of the links. 159 A leaf node is a node which has no upstream links. 161 A "trigger node" is any node which (a) acquires a new next hop 162 (i.e., either changes its next hop, or gets a next hop when it 163 previously had none) for a particular FEC, and (b) needs to have an 164 LSP for that FEC. 166 An LSP length at a node is represented by a hop count from the 167 furthest leaf node to that node. The LSP length at a leaf node is 168 zero. 170 In the remainder of the paper, we assume the "downstream-on-demand" 171 is used as the label allocation method between neighboring nodes, 172 although the thread mechanism is applicable to the upstream 173 allocation method. 175 3. Thread mechanism 177 3.1. Thread 179 A thread is an object used for representing a loop-prevention 180 process which extends downstream. The downstream end of a thread is 181 referred to as the "thread head". 183 A thread has a color that is assigned at the node that creates the 184 thread. The color is globally unique in the FEC. 186 A thread is always associated with a particular LSP (for a 187 particular FEC). The "length" of a thread is the number of hops 188 from the thread head to the node which is furthest upstream of it on 189 the LSP. An "unknown" length which is greater than any other known 190 length is used in a certain situation (see section 3.2). 192 A thread has a TTL which is decremented by one (except for a special 193 "infinity" value, see section 4) as the thread is extended without 194 changing its color. 196 For a given LSP, at a given LSR, there can be one "incoming thread" 197 for each upstream neighbor, and one "outgoing thread" to the 198 downstream neighbor. That is, one of the incoming threads is 199 extended downstream. If a node is the creator of a thread, the 200 thread becomes a "virtual incoming thread" whose upstream neighbor 201 is the node itself. A non-virtual incoming thread is referred to as 202 an "actual incoming thread". 204 When a thread is extended, it retains its color, but its length 205 becomes the maximum incoming thread length plus 1. 207 If a thread head of a given color reaches a node which already has a 208 thread of that color, then a loop has been detected. 210 When a node changes the color of its outgoing thread, it notifies 211 its downstream neighbor by means of LDP messages. The downstream 212 neighbor must process these messages in order. 214 3.2. Loop prevention algorithm 216 The ingress-initiated ordered control is assumed here, however, the 217 algorithm can be adapted to egress-initiated ordered control (see 218 section 3.4). 220 When a trigger node requests a label assignment to its downstream 221 neighbor, it creates a thread and extends it downstream. 223 The thread is given an initial length corresponding to the number of 224 hops between the trigger node and the furthest upstream leaf. It is 225 given a color which consists of the trigger node's IP address, 226 prepended to an event identifier which is assigned by the trigger 227 node. The trigger node will never reuse an event identifier until 228 sufficient time has passed so that we can be sure that no other node 229 in the network has any memory of the corresponding color. 231 A colored thread is extended downstream until one of the following 232 events occurs: 234 (i) the thread head reaches an egress node; 236 (ii) the thread head reaches a node where there is already an 237 ESTABLISHED LSP for the thread, with a KNOWN length which is no 238 less than the thread length; 240 (iii) the thread head reaches a node which already has an actual or 241 a virtual incoming thread of that color; 243 (iv) the thread TTL becomes zero; 245 (v) the thread head reaches a node where the maximum incoming thread 246 length is not updated and there is another actual incoming 247 thread. 249 o In the case of (i) or (ii), the thread is assured to reach the 250 egress node without forming a loop. Therefore the thread is 251 "rewound". When a thread is rewound, each node takes the 252 following actions. For each upstream link, it assigns a label 253 to the LSP and distributes that label LSP upstream, if needed. 254 It resets all incoming and outgoing thread colors to 255 "transparent". It sets the longest length among actual incoming 256 threads to the LSP length. If the outgoing thread length is 257 "unknown" and the obtained LSP length becomes known, it notifies 258 downstream of the LSP length (by using a "transparent" thread). 260 When the thread is rewound back to the trigger node, the LSP 261 setup completes. 263 o In the case of (iii) and (iv), the thread is neither extended 264 nor rewound. It is blocked at the node. In the case of (iii), 265 the following actions are taken. If the node is not the creator 266 of the thread, it creates a new thread with "unknown" length and 267 extends it downstream. Otherwise, if it is not a leaf node and 268 there is no other actual incoming thread, it withdraws the 269 outgoing thread (this will cause a thread reconstruction, see 270 section 3.3). 272 o In the case of (v), the received thread is "merged" into the 273 outgoing thread and no message is sent to the downstream 274 neighbor. 276 When a trigger node is attempting to set up a new LSP, it also tells 277 its old next hop that it is withdrawing the thread that goes through 278 it to the old next hop. This will cause the old next hop to 279 withdraw one of its incoming threads. 281 When an incoming thread is withdrawn, if there is no actual incoming 282 thread, the outgoing thread is also withdrawn unless the node 283 becomes a new leaf node. Otherwise, if it is the one currently 284 being extended, a new thread is created and extended. 286 A transparent thread is extended when a node notifies the downstream 287 neighbor on an established LSP of an LSP length update or a thread 288 withdrawal without releasing the LSP. No rewinding is needed for 289 transparent threads. 291 A virtual incoming thread is removed when the corresponding outgoing 292 thread is replaced or withdrawn. 294 3.3. Why this works 296 The above procedures ensure that once a looping thread is detected, 297 path setup along the LSRs in that thread is effectively stalled 298 until the L3 routing changes so as to remove the loop. 300 How can we be sure that the any L3 loop will be detected by these 301 procedures when a thread length is NOT "unknown"? 303 Consider a sequence of LSRs , such that there is a loop 304 traversing the LSRs in the sequence. (I.e., packets from R1 go to 305 R2, then to R3, etc., then to Rn, and then from Rn to R1.) 307 Remember that after a routing change, a path cannot be set up (i.e., 308 labels cannot be assigned) until the thread resulting from the 309 routing change is rewound, and the act of rewinding the thread 310 causes the thread lengths to be set consistently along the path. 312 Suppose that the thread length of the link between R1 and R2 is k. 314 Then by the above procedures, the length of the link between Rn and 315 R1 must be k+n-1. But the above procedures also ensure that if a 316 node has an incoming thread of length j, its outgoing thread must be 317 at least of length j+1. Hence, if we assume that the loop is not 318 detected by the above procedure, the thread length of the link 319 between R1 and R2 must be at least k+n. From this we may derive the 320 absurd conclusion that n=0, and we may therefore conclude that there 321 is no such sequence of LSRs. 323 When a thread of "unknown" length gets into an L3 loop, however, 324 there is a situation in which the thread is merged into another 325 thread of "unknown" length. In this case, the L3 loop would not be 326 explicitly detected, but the thread is effectively stalled in the 327 loop until the L3 routing changes so as to remove the loop. 329 Inversely, how can we be sure that no loop detection occurs when 330 there is no loop? 332 Since every new path setup or release attempt that changes an LSP 333 length causes the use of a new color, condition (iii) cannot obtain 334 unless there actually is an L3 routing loop. 336 Next, why thread reconstructions are needed? 338 When a thread loop is detected, imagine a thread tree whose root is 339 the thread head. If there is a leaf which is not an LSP leaf in 340 that tree, then the thread will not disappear even after all LSP 341 leaf node withdraw their threads. The thread reconstruction is 342 performed to change the location of the thread head to the proper 343 node where any leaf of the thread tree is an LSP leaf node. 345 In the above procedure, multiple thread updates may happen if 346 several leaf nodes start extending threads at the same time. How 347 can we prevent multiple threads from looping unlimitedly? 349 In the procedure, when a node detects a thread loop by condition 350 (iii), it creates a new thread of "unknown" length. All the looping 351 threads which later arrive at the node would be merged into this 352 thread. Such a thread of "unknown" length behaves like a thread 353 absorber. Furthermore, the thread TTL mechanism can eliminate any 354 kind of thread looping. 356 3.4. Using old path while looping on new path 358 When a route changes, one might want to continue to use the old path 359 if the new route is looping. This is archived simply by holding the 360 label assigned to the downstream link on the old path until the 361 thread head on the new route returns. This is an implementation 362 choice. 364 3.5. How to deal with egress-initiated ordered control 365 The thread mechanism can be also adapted to the egress-initiated 366 ordered control by originating a thread when a node newly receives 367 an advertisement message [5] from the downstream node. 369 Note that a node which has no upstream link for the LSP yet behaves 370 as a leaf. In the case where the tree is being initially built up 371 (e.g., the egress node has just come up), each node in turn will 372 behave as a leaf for a short period of time. 374 3.6. How to realize load splitting from the ingress node 376 The load splitting from the ingress node can be easily realized by 377 assigning a different colored thread to each downstream link. 379 4. Modification to LDP specification 381 A new advertisement class message, Update is added to the current 382 specification [5]. In addition, two new objects, Thread object and 383 Request ID object are defined. 385 When a thread of a particular LSP is extended on a downstream link, 386 if a label is not still allocated for that link, a Request message 387 is used for carrying the thread as well as for requesting a label, 388 otherwise, an Update message is used for extending the thread on the 389 downstream link where a label already exists. 391 When a node wants to withdraw an outgoing thread as well as 392 the downstream link, a Release message is used. 394 When a Mapping message is returned to an upstream node in response 395 to a Request message, it is treated as an indication of thread 396 rewinding (i.e., acknowledgments for loop-prevention check). 398 For an Update message, an ACK message is returned and treated as an 399 indication of thread rewinding, except for an Update containing a 400 special "transparent" thread. (See section 4.1.2.) 402 4.1. LDP objects 404 4.1.1. Request ID object 406 The object type of Request ID object is TBA. 408 +-----------------------+-------+--------------------------+----------+ 409 | OBJECT | Type | Subtype(s) | Length | 410 +-----------------------+-------+--------------------------+----------+ 411 | Request ID | TBA | 0x01 Default | 4 | 412 +-------------------------------+--------------------------+----------+ 414 The Request ID object contains the information for identifying 415 multiple LSPs of the same SMD. 417 SubType = 0x01 Default 419 1 2 3 420 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 421 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 422 | Request ID | 423 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 425 Request ID 426 This four-octet quantity contains a request-id which is 427 locally assigned by an upstream neighbor of a link. 429 4.1.2. Thread object 431 The object type of Loop Prevention object is TBA. 433 +-----------------------+-------+--------------------------+----------+ 434 | OBJECT | Type | Subtype(s) | Length | 435 +-----------------------+-------+--------------------------+----------+ 436 | Thread | TBA | 0x01 Default | 12 | 437 +-------------------------------+--------------------------+----------+ 439 The Thread object contains the information required for the thread 440 mechanism. 442 SubType = 0x01 Default 444 1 2 3 445 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 446 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 447 | | 448 | Color | 449 | | 450 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 451 | Length | TTL | Reserved | 452 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 454 Color 455 This eight-octet quantity contains a color of the thread. The 456 first four-octet is the thread creator's IP address. The last 457 four-octet is the local-id which is unique within the thread 458 creator's IP address. 460 If a node does not require a loop prevention check but only 461 requires an LSP length update, the special color "transparent" 462 is defined by setting all zero's to the Color field. No 463 acknowledgment is needed for transparent threads. 465 Length 466 This one octet quantity contains a thread length which is 467 represented by a hop count from the furthest leaf node to the 468 thread head. The value 0xff is assigned for "unknown" thread 470 length. 472 TTL (Time To Live) 473 This one octet quantity contains a thread TTL which is 474 decremented by one (except for TTL="infinity") when a thread is 475 extended without changing its color. When the TTL becomes zero, 476 the extending procedure must be stopped. The value 0xff is 477 assigned for "infinity" which is never decremented. 479 4.2 Advertisement class messages 481 4.2.1. Request message 483 Mandatory Objects 484 At least one of each mandatory object with associated object headers. 486 +-----------------------+----------+ 487 | MANDATORY OBJECT | Type | 488 +-----------------------+----------+ 489 | SMD | 0x02 | 490 +-----------------------+----------+ 491 | Class of Service | 0x04 | 492 +-----------------------+----------+ 494 Optional Objects 495 Zero or more optional objects with associated object headers. 497 +-----------------------+----------+ 498 | OPTIONAL OBJECT | Type | 499 +-----------------------+----------+ 500 | Request ID | TBA | 501 +-----------------------+----------+ 502 | Thread | TBA | 503 +-----------------------+----------+ 505 4.2.2. Mapping message 507 Mandatory Objects 508 At least one of each mandatory object with associated object headers. 510 +-----------------------+----------+ 511 | MANDATORY OBJECT | Type | 512 +-----------------------+----------+ 513 | SMD | 0x02 | 514 +-----------------------+----------+ 515 | Label | 0x03 | 516 +-----------------------+----------+ 518 Optional Objects 519 Zero or more optional objects with associated object headers. 521 +-----------------------+----------+ 522 | OPTIONAL OBJECT | Type | 523 +-----------------------+----------+ 524 | Class of Service | 0x04 | 525 +-----------------------+----------+ 526 | Hop Count | 0x06 | 527 +-----------------------+----------+ 528 | MTU | 0x07 | 529 +-----------------------+----------+ 530 | Stack | 0x08 | 531 +-----------------------+----------+ 532 | Request ID | TBA | 533 +-----------------------+----------+ 535 4.2.3. Update message 537 The message type of Update message is TBA. 539 Mandatory Objects 540 At least one of each mandatory object with associated object headers. 542 +-----------------------+----------+ 543 | MANDATORY OBJECT | Type | 544 +-----------------------+----------+ 545 | SMD | 0x02 | 546 +-----------------------+----------+ 547 | Class of Service | 0x04 | 548 +-----------------------+----------+ 549 | Thread | TBA | 550 +-----------------------+----------+ 552 Optional Objects 553 Zero or more optional objects with associated object headers. 555 +-----------------------+----------+ 556 | OPTIONAL OBJECT | Type | 557 +-----------------------+----------+ 558 | Request ID | TBA | 559 +-----------------------+----------+ 561 4.2.4. Release message 563 Mandatory Objects 564 At least one of each mandatory object with associated object headers. 566 +-----------------------+----------+ 567 | MANDATORY OBJECT | Type | 568 +-----------------------+----------+ 569 | SMD | 0x02 | 570 +-----------------------+----------+ 571 Optional Objects 572 Zero or more optional objects with associated object headers. 574 +-----------------------+----------+ 575 | OPTIONAL OBJECT | Type | 576 +-----------------------+----------+ 577 | Label | 0x03 | 578 +-----------------------+----------+ 579 | Request ID | TBA | 580 +-----------------------+----------+ 582 4.2.5. Ack/Nak message 584 Mandatory Objects 585 At least one of each mandatory object with associated object headers. 587 +-----------------------+----------+ 588 | MANDATORY OBJECT | Type | 589 +-----------------------+----------+ 590 | SMD | 0x02 | 591 +-----------------------+----------+ 592 | Error | 0x01 | 593 +-----------------------+----------+ 595 Optional Objects 597 Zero or more optional objects with associated object headers. 599 +-----------------------+----------+ 600 | OPTIONAL OBJECT | Type | 601 +-----------------------+----------+ 602 | Label | 0x03 | 603 +-----------------------+----------+ 604 | Request ID | TBA | 605 +-----------------------+----------+ 607 5. Examples 609 In the following examples, we assume that the ingress-initiated 610 ordered control is employed, that all the LSPs are with regard to 611 the same FEC, and that all nodes are VC-merge capable. 613 5.1. First example 615 Consider an MPLS network shown in Fig. 1 in which an L3 loop exists. 616 Each directed link represents the current next hop of the FEC at 617 each node. Now leaf nodes R1 and R6 initiate creation of an LSP. 619 R11 -------- R10 <-------------------- R9 620 | | ^ 621 | | | 622 v v | 623 R1 -------> R2 --------> R3 --------> R4 ---------- R5 624 (leaf) ^ 625 | 626 | 627 R6 -------> R7 --------> R8 628 (leaf) 630 Fig. 1 Example MPLS network (1) 632 Assume that R1 and R6 sends Request messages at the same time, and 633 that the initial thread TTL is 254 (255 represents "infinity"). 634 First we show an example of how to prevent LSP loops before thread 635 TTL becomes zero. 637 The Request message from R1 contains a thread of (red,1,254), where 638 a thread is identified by (color,length,TTL). The Request message 639 from R6 contains a thread of (blue,1,254). 641 Assume that R3 receives the Request originated from R1 before the 642 Request originated from R6. Then R3 forwards the Request with the 643 thread of (red,3,252) and then the Request with (blue,4,251) in this 644 order. 646 When R2 receives the Request from R10 with the thread of 647 (red,6,249), it detects a loop of the red thread. In this case, R2 648 creates a new purple thread of "unknown" length and extends it 649 downstream by sending a Request with (purple,?,254) to R3, where "?" 650 represents "unknown". 652 After that, R2 receives another Request for the same LSP from R10 653 with (blue,7,248). The blue thread is merged into the purple thread 654 since the purple thread length (="unknown") is longer than the blue 655 thread length (=7). R2 sends nothing to R3. 657 On the other hand, the purple thread goes round and R2 detects 658 the loop of its own purple thread. 660 In this case, neither a thread is rewound nor a Mapping is returned. 661 The current state of the network is shown in Fig. 2. Note that 662 thread TTL information is not shown here. 664 Bl(L): blue thread with length L 665 Re(L): red thread with length L 666 Pu(L): purple thread with length L 667 *: position of thread head 669 Pu(?) 670 R11 -------- R10 <------------------- R9 671 | | ^ 672 | | Pu*(?) | Pu(?) 673 v v | 674 R1 -------> R2 -------> R3 --------> R4 --------- R5 675 (leaf) Re(1) Pu(?) ^ Pu(?) 676 | Bl(3) 677 | 678 R6 -------> R7 -------> R8 679 (leaf) Bl(1) Bl(2) 681 Fig. 2 The network state 683 Then R10 changes its next hop from R2 to R11. 685 Since R10 has a purple thread on the old downstream link, it first 686 sends a Release message to the old next hop R2 for removing the 687 purple thread. Next, it creates a new green thread for which the 688 purple thread length(="unknown") is used, and sends a Request with 689 (green,?,254) to R11. 691 When R2 receives the Release from R10, the upstream link between R10 692 and R2 is removed. 694 On the other hand, the green thread goes round to R10 without 695 being merged. 697 When R10 receives the green thread, it sends a Release message to 698 R11 to withdraw the green thread, since it is the creator of the 699 green thread and there is no other actual incoming thread. 701 When R1 removes the green thread, it creates a new orange thread and 702 resends a Request with (orange,0,254) to R2. The orange thread goes 703 round to R1, replacing the green thread on the path. Finally, R1 704 detects the loop of its own orange thread. 706 The state of the network is now shown in Fig. 3. 708 Or(L): orange thread with length L 709 Bl(L): blue thread with length L 710 *: position of thread head 712 Or(7) Or(6) 713 R11 <------- R10 <------------------- R9 714 | | ^ 715 | Or*(8) | | Or(5) 716 v | | 717 R1 -------> R2 -------> R3 --------> R4 --------- R5 718 (leaf) Or(1) Or(2) ^ Or(4) 719 | Bl(3) 720 | 721 R6 -------> R7 -------> R8 722 (leaf) Bl(1) Bl(2) 724 Fig. 3 The network state 726 Then R4 changes its next hop from R9 to R5. 728 Since R4 has the orange thread, it first sends a Release message to 729 the old next hop R9 to withdraw the orange thread on the old route. 730 Next, it creates a yellow thread of length 4, and sends a Request 731 with (yellow,5,254) to R5. 733 Since R5 is the egress node, the received thread is assured to be 734 loop-free, and R5 returns a Mapping message with a label. R5 sets 735 the LSP length to 5. 737 The thread rewiding procedure is performed at each node, as the 738 Mapping is returned upstream hop-by-hop. 740 Finally, when each of R1 and R6 receives a Mapping message, a merged 741 LSP ((R1->R2),(R6->R7->R8))->R3->R4->R5) is established and all the 742 colored threads disappear from the network. 744 5.2. Second example 746 +----- R6----> R7-----+ 747 | | 748 | v 749 R1---->R2 R4----->R5 750 | ^ 751 | | 752 +--------->R3---------+ 754 Fig. 4. Example MPLS network (2) 756 Assume that in Fig. 4, there is an established LSP 757 R1->R2->R3->R4->R5, and the next hop changes at R2 from R3 to R6. 758 R2 sends a Request to R6 with (red,2,254). When the Request with 759 (red,4,252) reaches R4, it sends an Update message to R5 with 760 (red,5,251) since the received thread length (=4) is longer than the 761 current LSP length (=3). 763 When R5 receives the Update, it updates the LSP length to 5 and 764 returns an ACK for the Update. When R4 receives the ACK for the 765 Update, it returns an Mapping to R7. 767 When R2 receives the Mapping on the new route, it sends a Release to 768 R3. When R4 receives the Release, it does not sends an Update to R5 769 since the LSP length does not change. Now an established LSP 770 R1->R2->R6->R7->R4->R5 is obtained. 772 Then, the next hop changes again at R2 from R6 to R3. 774 R1 sends a Request with (blue,2,254) to R3. R3 forwards the Request 775 with (blue,3,253) to R4. 777 When R4 receives the Request, it immediately returns a Mapping to R3 778 since the received thread length (=3) is not longer than the current 779 LSP length (=4). 781 When R2 receives the Mapping on the new route, it sends a Release to 782 R6. The Release reaches R4, triggering an Update message with a 783 transparent thread (0,4,255) to R5, since the LSP length at R4 784 decreases from 4 to 3. R5 updates the LSP length to 4 without 785 returning an ACK. 787 6. Comparison with path-vector/diffusion method 789 o Whereas the size of the path-vector increases with the length of 790 the LSP, the sizes of the threads are constant. Thus the size 791 of messages used by the thread algorithm are unaffected by the 792 network size or topology. In addition, the thread merging 793 capability reduces the number of outstanding messages. These 794 lead to improved scalability. 796 o In the thread algorithm, a node which is changing its next hop 797 for a particular LSP must interact only with nodes that are 798 between it and the LSP egress on the new path. In the 799 path-vector algorithm, however, it is necessary for the node to 800 initiate a diffusion computation that involves nodes which do 801 not lie between it and the LSP egress. 803 This characteristic makes the thread algorithm more robust. If 804 a diffusion computation is used, misbehaving nodes which aren't 805 even in the path can delay the path setup. In the thread 806 algorithm, the only nodes which can delay the path setup are 807 those nodes which are actually in the path. 809 o The thread algorithm is well suited for use with both the 810 ingress-initiated ordered control and the egress-initiated 811 ordered control. The path-vector/diffusion algorithm, however, 812 is tightly coupled with the egress-initiated ordered control. 814 o The thread algorithm is retry-free, achieving quick path 815 (re)configuration. The diffusion algorithm tends to delay the 816 path reconfiguration time, since a node at the route change 817 point must to consult all its upstream nodes. 819 o In the thread algorithm, the node can continue to use the old 820 path if there is an L3 loop on the new path, as in the 821 path-vector algorithm. 823 7. Security considerations 825 Security considerations are not discussed in this document. 827 8. Intellectual property considerations 829 Toshiba and/or Cisco may seek patent or other intellectual property 830 protection for some of the technologies disclosed in this document. 831 If any standards arising from this document are or become protected 832 by one or more patents assigned to Toshiba and/or Cisco, Toshiba 833 and/or Cisco intend to disclose those patents and license them on 834 reasonable and non-discriminatory terms. 836 9. References 838 [1] Y. Ohba, et al., "Flow Attribute Notification Protocol Version 2 839 (FANPv2) Ingress Control Mode," Internet Draft, 840 draft-ohba-csr-fanpv2-icmode-00.txt, Dec. 1997. 842 [2] B. Davie, et al., "Use of Label Switching With ATM," Internet Draft, 843 draft-davie-mpls-atm-01.txt, July 1998. 845 [3] E. Rosen, et al., "A Proposed Architecture for MPLS," 846 Internet Draft, draft-ietf-mpls-arch-01.txt, July 1998. 848 [4] R. Callon, et al., "A Framework for Multiprotocol Label 849 Switching," Internet Draft, draft-ietf-mpls-framework-02.txt, 850 Nov. 1997. 852 [5] L. Andersson, et al., "Label Distribution Protocol," Internet Draft, 853 draft-mpls-ldp-spec-00.txt, March 1998. 855 Authors' Addresses 857 Yoshihiro Ohba 858 R&D Center, Toshiba Corp. 859 1, Komukai-Toshiba-cho, Saiwai-ku 860 Kawasaki, 210, Japan 861 Email: ohba@csl.rdc.toshiba.co.jp 863 Yasuhiro Katsube 864 R&D Center, Toshiba Corp. 865 1, Komukai-Toshiba-cho, Saiwai-ku 866 Kawasaki, 210, Japan 867 Email: katsube@isl.rdc.toshiba.co.jp 869 Eric Rosen 870 Cisco Systems, Inc. 871 250 Apollo Drive 872 Chelmsford, MA, 01824 873 Email: erosen@cisco.com 875 Paul Doolan 876 Ennovate Networks 877 330 Codman Hill Road 878 Boxborough, MA 879 Email: pdoolan@ennovatenetworks.com