Network Working Group Y. Ohba Request for Comments: 3063 Y. Katsube Category: Experimental Toshiba E. Rosen Cisco Systems P. Doolan Ennovate Networks February 2001 MPLS Loop Prevention Mechanism Status of this Memo This memo defines an Experimental Protocol for the Internet community. It does not specify an Internet standard of any kind. Discussion and suggestions for improvement are requested. Distribution of this memo is unlimited. Copyright Notice Copyright (C) The Internet Society (2001). All Rights Reserved. Abstract This paper presents a simple mechanism, based on "threads", which can be used to prevent Multiprotocol Label Switching (MPLS) from setting up label switched path (LSPs) which have loops. The mechanism is compatible with, but does not require, VC merge. The mechanism can be used with either the ordered downstream-on-demand allocation or ordered downstream allocation. The amount of information that must be passed in a protocol message is tightly bounded (i.e., no path- vector is used). When a node needs to change its next hop, a distributed procedure is executed, but only nodes which are downstream of the change are involved. Ohba, et al. Experimental [Page 1] RFC 3063 MPLS Loop Prevention Mechanism February 2001 Table of Contents 1 Introduction .......................................... 2 2 Basic definitions ..................................... 3 3 Thread basics ......................................... 5 3.1 Thread attributes ..................................... 5 3.2 Thread loop ........................................... 7 3.3 Primitive thread actions .............................. 7 3.4 Examples of primitive thread actions ................. 10 4 Thread algorithm ...................................... 14 5 Applicability of the algorithm ........................ 14 5.1 LSP Loop prevention/detection ......................... 15 5.2 Using old path while looping on new path .............. 15 5.3 How to deal with ordered downstream allocation ........ 15 5.4 How to realize load splitting ......................... 15 6 Why this works ........................................ 16 6.1 Why a thread with unknown hop count is extended ....... 16 6.2 Why a rewound thread cannot contain a loop ............ 17 6.2.1 Case1: LSP with known link hop counts ................. 17 6.2.1 Case2: LSP with unknown link hop counts ............... 17 6.3 Why L3 loop is detected ............................... 17 6.4 Why L3 loop is not mis-detected ....................... 17 6.5 How a stalled thread automatically recovers from loop . 18 6.6 Why different colored threads do not chase each other . 18 7 Loop prevention examples .............................. 19 7.1 First example ......................................... 19 7.2 Second example ........................................ 23 8 Thread control block .................................. 24 8.1 Finite state machine .................................. 25 9 Comparison with path-vector/diffusion method .......... 28 10 Security Considerations ............................... 29 11 Intellectual Property Considerations .................. 29 12 Acknowledgments ....................................... 29 13 Authors' Addresses .................................... 30 14 References ............................................ 30 Appendix A Further discussion of the algorithm ............. 31 Full Copyright Statement ..................................... 44 1. Introduction This paper presents a simple mechanism, based on "threads", which can be used to prevent MPLS from setting up label switched paths (LSPs) which have loops. When an LSR finds that it has a new next hop for a particular FEC (Forwarding Equivalence Class) [1], it creates a thread and extends it downstream. Each such thread is assigned a unique "color", such that no two threads in the network can have the same color. Ohba, et al. Experimental [Page 2] RFC 3063 MPLS Loop Prevention Mechanism February 2001 For a given LSP, once a thread is extended to a particular next hop, no other thread is extended to that next hop unless there is a change in the hop count from the furthest upstream node. The only state information that needs to be associated with a particular next hop for a particular LSP is the thread color and hop count. If there is a loop, then some thread will arrive back at an LSR through which it has already passed. This is easily detected, since each thread has a unique color. Section 3 and 4 provide procedures for determining that there is no loop. When this is determined, the threads are "rewound" back to the point of creation. As they are rewound, labels get assigned. Thus labels are NOT assigned until loop freedom is guaranteed. While a thread is extended, the LSRs through which it passes must remember its color and hop count, but when the thread has been rewound, they need only remember its hop count. The thread mechanism works if some, all, or none of the LSRs in the LSP support VC-merge. It can also be used with either the ordered downstream on-demand label allocation or ordered downstream unsolicited label allocation [2,3]. The mechanism can also be applicable to loop detection, old path retention, and load-splitting. The state information which must be carried in protocol messages, and which must be maintained internally in state tables, is of fixed size, independent of the network size. Thus the thread mechanism is more scalable than alternatives which require that path-vectors be carried. To set up a new LSP after a routing change, the thread mechanism requires communication only between nodes which are downstream of the point of change. There is no need to communicate with nodes that are upstream of the point of change. Thus the thread mechanism is more robust than alternatives which require that a diffusion computation be performed (see section 9). 2. Basic definitions LSP We will use the term LSP to refer to a multipoint-to-point tree whose root is the egress node. See section 3.5 of [3]. Ohba, et al. Experimental [Page 3] RFC 3063 MPLS Loop Prevention Mechanism February 2001 In the following, we speak as if there were only a single LSP being set up in the network. This allows us to talk of incoming and outgoing links without constantly saying something like "for the same LSP. Incoming Link, Upstream Link Outgoing Link, Downstream Link At a given node, a given LSP will have one or more incoming, or upstream links, and one outgoing or downstream link. A "link" is really an abstract relationship with an "adjacent" LSR; it is an "edge" in the "tree", and not necessarily a particular concrete entity like an "interface". Leaf Node, Ingress Node A node which has no upstream links. Eligible Leaf Node A node which is capable of being a leaf node. For example, a node is not an eligible leaf node if it is not allowed to directly inject L3 packets created or received at the node into its outgoing link. Link Hop Count Every link is labeled with a "link hop count". This is the number of hops between the given link and the leaf node which is furthest upstream of the given link. At any node, the link hop count for the downstream link is one more than the largest of the hop counts associated with the upstream links. We define the quantity "Hmax" at a given node to be the maximum of all the incoming link hop counts. Note that, the link hop count of the downstream link is equal to Hmax+1. At a leaf node, Hmax is set to be zero. An an example of link hop counts is shown in Fig.1. Ohba, et al. Experimental [Page 4] RFC 3063 MPLS Loop Prevention Mechanism February 2001 1 2 A---B---C K | | |3 |1 | | | 4 5 | 6 7 D---G---H---I---J | |2 1 | E---F Fig.1 Example of link hop counts Next Hop Acquisition Node N thought that FEC F was unreachable, but now has a next hop for it. Next Hop Loss Node N thought that node A was the next hop for FEC F, but now no longer has the next hop for FEC F. A node loses a next hop whenever the next hop goes down. Next Hop Change At node N, the next hop for FEC F changes from node A to node B, where A is different than B. A next hop change event can be seen as a combination of a next hop loss event on the old next hop and a next hop acquisition event on the new next hop. 3. Thread basics A thread is a sequence of messages used to set up an LSP, in the "ordered downstream-on-demand" (ingress-initiated ordered control) style. 3.1. Thread attributes There are three attributes related to threads. They may be encoded into a single thread object as: Ohba, et al. Experimental [Page 5] RFC 3063 MPLS Loop Prevention Mechanism February 2001 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + Color + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Hop Count | TTL | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Thread Color Every time a path control message is initiated by a node, the node assigns a unique "color" to it. This color is to be unique in both time and space: its encoding consists of an IP address of the node concatenated with a unique event identifier from a numbering space maintained by the node. The path setup messages that the node sends downstream will contain this color. Also, when the node sends such a message downstream, it will remember the color, and this color becomes the color of the downstream link. When a colored message is received, its color becomes the color of the incoming link. The thread which consists of messages of a certain color will be known as a thread of that color. special color value "transparent"(=all 0's) is reserved. One possible method for unique color assignment is, starting the event identifier from its initial value, and incrementing it by one (modulo its maximum value) each time a color is assigned. In this method, the initial event identifier is either selected at random or assigned to be larger than the largest event identifier used on the previous system incarnation. Thread Hop Count In order to maintain link hop counts, we need to carry hop counts in the path control messages. For instance, a leaf node would assign a hop count of 1 to its downstream link, and would store that value into a path setup message it sends downstream. When a path setup message is sent downstream, a node would assign a hop count which is one more than the largest of the incoming link hop counts, to its downstream link, and would store that value into a path setup message it sends downstream. Once the value is stored in a path control message, we may refer to it has a "thread hop count". Ohba, et al. Experimental [Page 6] RFC 3063 MPLS Loop Prevention Mechanism February 2001 A special hop count value "unknown"(=0xff), which is larger than any other known value, is used when a loop is found. Once the thread hop count is "unknown", it is not increased any more as the thread is extended. Thread TTL To avoid infinite looping of control messages in some cases, a thread TTL is used. When a node creates a path control message and sends it downstream, it sets a TTL to the message, and the TTL is decremented at each hop. When the TTL reaches 0, the message is not forwarded any more. Unlike the thread hop counts and the thread colors, the thread TTLs do not needs to be stored in incoming links. 3.2. Thread loop When the same colored thread is received on multiple incoming links, or the received thread color was assigned by the receiving node, it is said that the thread forms a loop. A thread creator can tell whether it assigned the received thread color by checking the IP address part of the received thread color. 3.3. Primitive thread actions Five primitive actions are defined in order to prevent LSP loops by using threads: "extending", "rewinding", "withdrawing", "merging", and "stalling". This section describes only each primitive action and does not describe how these primitive actions are combined and how the algorithm totally works. The main body of the algorithm is described in section 4. Thread Extending When a node starts to send a path setup message to its next hop with a set of thread attributes, it is said that "the node creates a thread and extends it downstream". When a node receives a path setup message from an upstream node with a set of thread attributes and forwards it downstream, it is said that "the node receives a thread and extends it downstream". The color and hop count of the thread become the color and hop count of the outgoing link. Whenever a thread is received on a particular link, the color and hop count of that thread become the color and hop count of that incoming link, replacing any color and hop count that the link may have had previously. Ohba, et al. Experimental [Page 7] RFC 3063 MPLS Loop Prevention Mechanism February 2001 For example, when an ingress node initiates a path setup, it creates a thread and extends it downstream by sending a path setup message. The thread hop count is set to be 1, and the thread color is set to be the ingress node's address with an appropriate event identifier, and the thread TTL is set to be its maximum value. When a node receives a thread and extends it downstream, the node either (i) extends the thread without changing color, or (ii) extend the thread with changing color. The received thread is extended with changing color if it is received on a new incoming link and extended on an already existing outgoing link, otherwise, it is extended without changing color. When a thread is extended with changing color, a new colored thread is created and extended. Thread creation does not occur only at leaf nodes. If an intermediate node has an incoming link, it will create and extend a new thread whenever it acquires a new next hop. When a node notifies a next hop node of a decrease of the link hop count, if it is not extending a colored thread, a transparent thread is extended. Thread Merging When a node which has a colored outgoing link receives a new thread, it does not necessarily extend the new thread. It may instead 'merge' the new threads into the existing outgoing thread. In this case, no messages are sent downstream. Also, if a new incoming thread is extended downstream, but there are already other incoming threads, these other incoming threads are considered to be merged into the new outgoing thread. Specifically, a received thread is merged if all the following conditions hold: o A colored thread is received by node N, AND o The thread does not form a loop, AND o N is not an egress node, AND o N's outgoing link is colored, AND o N's outgoing link hop count is at least one greater than the hop count of the newly received thread. When an outgoing thread rewinds (see below), any incoming threads which have been merged with it will rewind as well. Ohba, et al. Experimental [Page 8] RFC 3063 MPLS Loop Prevention Mechanism February 2001 Thread Stalling When a colored thread is received, if the thread forms a loop, the received thread color and hop count are stored on the receiving link without being extended. This is the special case of thread merging applied only for threads forming a loop and referred to as the "thread stalling", and the incoming link storing the stalled thread is called "stalled incoming link". A distinction is made between stalled incoming links and unstalled incoming links. Thread Rewinding When a thread reaches a node which satisfies a particular loop- free condition, the node returns an acknowledgment message back to the message initiator in the reverse path on which the thread was extended. The transmission of the acknowledgment messages is the "rewinding" of the thread. The loop-free condition is: o A colored thread is received by the egress node, OR o All of the following conditions hold: (a) A colored thread is received by node N, AND (b) N's outgoing link is transparent, AND (c) N's outgoing link hop count is at least one greater than the hop count of the newly received thread. When a node rewinds a thread which was received on a particular link, it changes the color of that link to transparent. If there is a link from node M to node N, and M has extended a colored thread to N over that link, and M determines (by receiving a message from N) that N has rewound that thread, then M sets the color of its outgoing link to transparent. M then continues rewinding the thread, and in addition, rewinds any other incoming thread which had been merged with the thread being rewound, including stalled threads. Each node can start label switching after the thread colors in all incoming and outgoing links becomes transparent. Note that transparent threads are threads which have already been rewound; hence there is no such thing as rewinding a transparent thread. Ohba, et al. Experimental [Page 9] RFC 3063 MPLS Loop Prevention Mechanism February 2001 Thread Withdrawing It is possible for a node to tear down a path. A node tears down the portion of the path downstream of itself by sending teardown messages to its next hop. This process is known as the "thread withdrawing". For example, suppose a node is trying to set up a path, and then experiences a next hop change or a next hop loss. It will withdraw the thread that it had extended down its old next hop. If node M has extended a thread to node N, and node M then withdraws that thread, N now has one less incoming link than it had before. If N now has no other unstalled incoming links and N is not an eligible leaf node, it must withdraw its outgoing thread. If N still has an unstalled incoming link or N is an eligible leaf node, it may (or may not) need to change the hop count of the outgoing link. N needs to change the outgoing hop count if: o The incoming link hop count that was just removed had a larger hop count than any of the remaining incoming links, AND o One of the following conditions holds: (a) The outgoing link is transparent, OR (b) The outgoing link has a known hop count. If the outgoing link is transparent, it remains transparent, but the new hop count needs to be sent downstream. If the outgoing link is colored, a new thread (with a new color) needs to be created and extended downstream. 3.4. Examples of primitive thread actions The following notations are used to illustrate examples of primitive actions defined for threads. A pair of thread attributes stored in each link is represented by "(C,H)", where C and H represent the thread color and thread hop count, respectively. A thread marked "+" indicates that it is created or received now. A thread marked "-" indicates that it is withdrawn now. A link labeled with squared brackets (e.g., "[a]") indicates that it is an unstalled link. A link labeled with braces (e.g., "{a}") indicates that it is a stalled link. Ohba, et al. Experimental [Page 10] RFC 3063 MPLS Loop Prevention Mechanism February 2001 Fig. 2 shows an example in which a leaf node A creates a blue thread and extends it downstream. (bl,1) A---[o1]---> Fig.2 Thread extending at leaf node Fig.3 shows an example of thread extending without changing color at intermediate node. Assume that a node B has no incoming and outgoing link before receiving a blue thread. When node B receives the blue thread of hop count 1 on a new incoming link i1, it extends the thread downstream without changing color (Fig.3(a)). After the blue thread is extended, node B receives a red thread of hop count unknown on incoming link i1 again (Fig.3(b)). The red thread is also extended without changing its color, since both i1 and o1 already exists. (bl,1)+ (bl,2) (re,U)+ (re,U) ----[i1]--->B---[o1]----> ----[i1]--->B----[o1]---> Fig.3(a) Fig.3(b) Fig.3 Thread extending without changing color Fig.4 shows an example of thread extending with changing color. There are single incoming link i1 and single outgoing link o1 in Fig.4(a). Then a red thread of hop count 3 is received on a new incoming link i2. In this case, the received thread is extended with changing color, i.e., a new green thread is created and extended (Fig.4(b)), since o1 already exists. (bl,1) (bl,2) (bl,1) (gr,4) ----[i1]--->B----[o1]---> ----[i1]--->B----[o1]---> ^ | ----[i2]----+ (re,3)+ Fig.4(a) Fig.4(b) Fig.4 Thread extending with changing color Fig.5 shows an example of thread merging. When a node B receives a red thread of hop count 3, the received thread is not extended since the outgoing link hop count is at least one greater than the received thread hop count. Both the red and blue threads will be rewound when the blue thread on outgoing link o1 is rewound. Ohba, et al. Experimental [Page 11] RFC 3063 MPLS Loop Prevention Mechanism February 2001 (bl,3) (bl,4) ----[i1]--->B----[o1]---> ^ | ----[i2]----+ (re,3)+ Fig.5 Thread merging Figs 6 and 7 show examples of thread stalling. When a node B receives a blue thread of hop count 10 on incoming link i2 in Fig.6, it "stalls" the received thread since the blue thread forms a loop. In Fig.7, a leaf node A finds the loop of its own thread. (bl,3) (bl,4) ----[i1]--->B----[o1]---> ^ | ----{i2}----+ (bl,10)+ Fig.6 Thread stalling (1) (bl,10)+ (bl,1) ----{i1}--->A----[o1]---> Fig.7 Thread stalling (2) Fig.8 shows an example of thread rewinding. When the yellow thread which is currently being extended is rewound (Fig.8(a)), the node changes all the incoming and outgoing thread color to transparent, and propagates thread rewinding to upstream nodes (Fig.8(b)). (bl,1) (ye,2) (tr,1) (tr,2) ----[i2]--->B----[o1]---> ----[i2]--->B----[o1]---> ^ ^ | | ----[i3]----+ ----[i3]----+ (ye,1) (tr,1) Fig.8(a) Fig.8(b) Fig.8 Thread rewinding Ohba, et al. Experimental [Page 12] RFC 3063 MPLS Loop Prevention Mechanism February 2001 Fig.9 shows an example of thread withdrawing. In Fig.9(a), the red thread on incoming link i2 is withdrawn. Then Hmax decreases from 3 to 1, and node B creates a new green thread and extends it downstream, as shown in Fig.9(b). (bl,1) (re,4) (bl,1) (gr,2)+ ----[i1]--->B---[o1]---> ----[i1]--->B----[o1]---> ^ | ----[i2]----+ (re,3)- Fig.9(a) Fig.9(b) Fig.9 Thread withdrawing (1) Fig.10 shows another example of thread withdrawing. In Fig.10(a), the red thread on incoming link i3 is withdrawn. In this case, Hmax decreases from unknown to 1, however, no thread is extended as shown in Fig.10(b), since the outgoing link has a colored thread and the hop count is unknown. (bl,1) (re,U) (bl,1) (re,U) ----[i2]--->B----[o1]---> ----[i2]--->B----[o1]---> ^ | ----[i3]----+ (re,U)- Fig.10(a) Fig.10(b) Fig.10 Thread withdrawing (2) Fig.11 shows another example of thread withdrawing. In Fig.11(a), the transparent thread on incoming link i3 is withdrawn. In this case, a transparent thread is extended (Fig.11(b)), since Hmax decreases and the outgoing link is transparent. (tr,1) (tr,U) (tr,1) (tr,2)+ ----[i2]--->B----[o1]---> ----[i2]--->B----[o1]---> ^ | ----[i3]----+ (tr,U)- Fig.11(a) Fig.11(b) Fig.11 Thread withdrawing (3) Ohba, et al. Experimental [Page 13] RFC 3063 MPLS Loop Prevention Mechanism February 2001 4. Thread algorithm The ordered downstream-on-demand allocation is assumed here, however, the algorithm can be adapted to the ordered downstream allocation, as shown in section 5. In the algorithm, a next hop change event will be separated into two events: a next hop loss event on the old next hop and a next hop acquisition event on the new next hop, in this order. The following notations are defined: Hmax: the largest incoming link hop count Ni: the number of unstalled incoming links The thread algorithm is described as follows. When a node acquires a new next hop, it creates a colored thread and extends it downstream. When a node loses a next hop to which it has extended a thread, it may withdraw that thread. As described in section 3, this may or may not cause the next hop to take some action. Among the actions the next hop may take are withdrawing the thread from its own next hop, or extending a new thread to its own next hop. A received colored thread is either stalled, merged, rewound, or extended. A thread with TTL zero is never extended. When a received thread is stalled at a node, if Ni=0 and the node is not an eligible leaf node, initiate a thread withdrawing. Otherwise, if Ni>0 and the received thread hop count is not unknown, a colored thread of hop count unknown is created and extended. If the received thread hop count is unknown, no thread is extended and no further action is taken. When a thread being extended is rewound, if the thread hop count is greater than one more than Hmax, a transparent thread of hop count (Hmax+1) is extended downstream. When a node that has an transparent outgoing link receives a transparent thread, if Hmax decreases the node extends it downstream without changing color. 5. Applicability of the algorithm The thread algorithm described in section 4 can be applied to various LSP management policies. Ohba, et al. Experimental [Page 14] RFC 3063 MPLS Loop Prevention Mechanism February 2001 5.1. LSP Loop prevention/detection The same thread algorithm is applicable to both LSP loop prevention and detection. In loop prevention mode, a node transmits a label mapping (including a thread object) for a particular LSP only when it rewinds the thread for that LSP. No mapping message is sent until the thread rewinds. On the other hand, if a node operates in loop detection mode, it returns a label mapping message without a thread object immediately after receiving a colored thread. A node which receives a label mapping message that does not have a thread object will not rewind the thread. 5.2. Using old path while looping on new path When a route changes, one might want to continue to use the old path if the new route is looping. This is achieved simply by holding the label assigned to the downstream link on the old path until the thread being extended on the new route gets rewound. This is an implementation choice. 5.3. How to deal with ordered downstream allocation The thread mechanism can be also adapted to ordered downstream allocation mode (or the egress-initiated ordered control) by regarding the event of newly receiving of a label mapping message [4] from the next hop as a next hop acquisition event. Note that a node which doesn't yet have an incoming link behaves as a leaf. In the case where the tree is being initially built up (e.g., the egress node has just come up), each node in turn will behave as a leaf for a short period of time. 5.4. How to realize load splitting A leaf node can easily perform load splitting by setting up two different LSPs for the same FEC. The downstream links for the two LSPs are simply assigned different colors. The thread algorithm now prevents a loop in either path, but also allows the two paths to have a common downstream node. If some intermediate node wants to do load splitting, the following modification is made. Assume that there are multiple next hops for the same FEC. If there are n next hops for a particular FEC, the set of incoming links for that FEC's LSP can be partitioned into n subsets, where each subset can be mapped to a distinct outgoing link. Ohba, et al. Experimental [Page 15] RFC 3063 MPLS Loop Prevention Mechanism February 2001 This provides n LSPs for the FEC. Each such LSP uses a distinct color for its outgoing link. The thread algorithm now prevents a loop in any of the paths, but also allows two or more of the paths to have a common downstream node. In this case, an interesting situation may happen. Let's say that in Fig.12, node B has two incoming links, i1 and i2, and two outgoing links, o1 and o2, such that i1 is mapped to o1, while i2 is mapped to o2. If a blue thread received on i1 and extended on o1 is again received at node B on i2, the blue thread is not regarded as forming a loop, since i1 and i2 are regarded as belonging to different subsets. Instead, the blue thread received on i2 is extended on o2. If the thread extended on o2 is rewound, a single loop-free LSP which traverses node B twice is established. +------------------...--------------------+ . (bl,3) (bl,4) | . ----[i1]---+ +--[o1]---> .... --+ . \ / . v / | B | +-----------[i2]--->B----[o2]---> (bl,10)+ (bl,11) Fig.12 Load splitting at intermediate node There is another type of load splitting, in which packets arrived at single incoming link can be label switched to any one of multiple outgoing links. This case does not seem to be a good load-splitting scheme, since the packet order in the same FEC is not preserved. Thus, this document does not focus on this case. Whether that's a good type of load splitting or not, the fact remains that ATM-LSRs cannot load split like this because ATM switches just don't have the capability to make forwarding decisions on a per- packet basis. 6. Why this works 6.1. Why a thread with unknown hop count is extended In the algorithm, a thread of unknown hop count is extended when a thread loop is detected. This reduces the number of loop prevention Ohba, et al. Experimental [Page 16] RFC 3063 MPLS Loop Prevention Mechanism February 2001 messages by merging threads (of known hop count) that are flowing inside or outside the loop. See Appendix A.12. 6.2. Why a rewound thread cannot contain a loop 6.2.1. Case1: LSP with known link hop counts How can we be sure that an established path does not contain a loop when the outgoing link hop count is NOT "unknown"? Consider a sequence of LSRs , such that there is a loop traversing the LSRs in the sequence. (I.e., packets from R1 go to R2, then to R3, etc., then to Rn, and then from Rn to R1.) Suppose that the thread hop count of the link between R1 and R2 is k. Then by the above procedures, the hop counts between Rn and R1 must be k+n-1. But the algorithm also ensures that if a node has an incoming hop count of j, its outgoing link hop count must be at least of j+1. Hence, if we assume that the LSP established as a result of thread rewinding contains a loop, the hop counts between R1 and R2 must be at least k+n. From this we may derive the absurd conclusion that n=0, and we may therefore conclude that there is no such sequence of LSRs. 6.2.1. Case2: LSP with unknown link hop counts An established path does not contain a loop as well, when the outgoing link hop count is "unknown". This is because a colored thread of unknown hop count is never rewound unless it reaches egress. 6.3. Why L3 loop is detected Regardless of whether the thread hop count is known or unknown, if there is a loop, then some node in the loop will be the last node to receive a thread over a new incoming link. This thread will always arrive back at that node, without its color having changed. Hence the loop will always be detected by at least one of the nodes in the loop. 6.4. Why L3 loop is not mis-detected Since no node ever extends the same colored thread downstream twice, a thread loop is not detected unless there actually is an L3 routing loop. Ohba, et al. Experimental [Page 17] RFC 3063 MPLS Loop Prevention Mechanism February 2001 6.5. How a stalled thread automatically recovers from loop Once a thread is stalled in a loop, the thread (or the path setup request) effectively remains in the loop, so that a path reconfiguration (i.e., thread withdrawing on the old path and thread extending on the new path) can be issued from any node that may receive a route change event so as to break the loop. 6.6. Why different colored threads do not chase each other In the algorithm, multiple thread color and/or hop count updates may happen if several leaf nodes start extending threads at the same time. How can we prevent multiple threads from looping unlimitedly? First, when a node finds that a thread forms a loop, it creates a new thread of hop count "unknown". All the looping threads of a known hop count which later arrive at the node would be merged into this thread. Such a thread behaves like a thread absorber. Second, the "thread extending with changing color" prevents two threads from chasing each other. Suppose that a received thread were always extended without changing color. Then we would encounter the following situation. G Y | | v v R1------>R2 ^ | | v R4<------R3 Fig.13 Example of thread chasing In Fig.13, (1) node G acquires R1 as a next hop, and starts to extend a green thread of hop count 1, (2) node Y acquires R2 as a next hop, and starts to extend a yellow thread of hop count 1, and (3) both node G and node Y withdraws their threads before these threads go round. In this case, the yellow and green threads would go round and get back to R2 and R1, respectively. When the threads get back to R2 and R1, however, the incoming links that store the yellow and green colors no longer exist. As a result, the yellow and green threads would chase each other forever in the loop. Ohba, et al. Experimental [Page 18] RFC 3063 MPLS Loop Prevention Mechanism February 2001 However, since we have the "extending with changing color" mechanism, this does not actually happen. When a green thread is received at R2, R2 extends the thread with changing color, i.e., creates a new red thread and extends it. Similarly, when a yellow thread is received at R1, R1 creates a new purple thread and extends it. Thus, the thread loop is detected even after node G and node Y withdraw threads. This ensures that a thread is extended around the loop which has a color assigned by some node that is in the loop. There is at least one case even the "extending with changing color" mechanism cannot treat, that is, the "self-chasing" in which thread extending and thread withdrawing with regard to the same thread chase each other in a loop. This case would happen when a node withdraw a thread immediately after extending it into an L3 loop. A heuristics for self-chasing is to delay the execution of thread withdrawing at an initiating node of the thread withdrawing. Anyway, the thread TTL mechanism can eliminate any kind of thread looping. 7. Loop prevention examples In this section, we show two examples to show how the algorithm can prevent LSP loops in given networks. We assume that the ordered downstream-on-demand allocation is employed, that all the LSPs are with regard to the same FEC, and that all nodes are VC-merge capable. 7.1. First example Consider an MPLS network shown in Fig.14 in which an L3 loop exists. Each directed link represents the current next hop of the FEC at each node. Now leaf nodes R1 and R6 initiate creation of an LSP. R11 ------- R10 <-------------------- R9 | | ^ | | | | | | v v | R1 -------> R2 --------> R3 --------> R4 --------- R5 [leaf] ^ | | | R6 -------> R7 --------> R8 [leaf] Fig. 14 Example MPLS network (1) Ohba, et al. Experimental [Page 19] RFC 3063 MPLS Loop Prevention Mechanism February 2001 Assume that R1 and R6 send a label request message at the same time, and that the initial thread TTL is 255. First we show an example of how to prevent LSP loops. A set of thread attributes is represented by (color, hop count, TTL). The request from R1 and R6 contains (re,1,255) and (bl,1,255), respectively. Assume that R3 receives the request originated from R1 before receiving the request originated from R6. When R3 receives the first request with red thread, R3 forwards it with (re,3,253) without changing thread color, since both the receiving incoming link and the outgoing link are newly created. Then R3 receives the second request with blue thread. In this time, the outgoing link is already exists. Thus, R3 performs thread extending with changing color, i.e., creates a new brown thread and forwards the request with (br,4,255). When R2 receives the request from R10 with (re,6,250), it finds that the red thread forms a loop, and stalls the red thread. Then, R2 creates a purple thread of hop count unknown and extends it downstream by sending a request with (pu,U,255) to R3, where "U" represents "unknown". After that, R2 receives another request from R10 with (br,7,252). The brown thread is merged into purple thread. R2 sends no request to R3. On the other hand, the purple thread goes round without changing color through existing links, and R2 finds the thread loop and stalls the purple thread. Since the received thread hop count is unknown, no thread is created any more. In this case no thread rewinding occurs. The current state of the network is shown in Fig.15. Ohba, et al. Experimental [Page 20] RFC 3063 MPLS Loop Prevention Mechanism February 2001 *: location of thread stalling (pu,U) R11 ------- R10 <-------------------- R9 | | ^ | |(pu,U)* | | | |(pu,U) v v | R1 -------> R2 --------> R3 --------> R4 --------- R5 [leaf] (re,1) (pu,U) ^ (pu,U) | | (bl,3) | R6 -------> R7 --------> R8 [leaf] (bl,1) (bl,2) Fig.15 The network state Then R10 changes its next hop from R2 to R11. Since R10 has a purple thread on the old downstream link, it first sends a path teardown message to the old next hop R2 for withdrawing the purple thread. Next, it creates a green thread of hop count unknown and sends a request with (gr,U,255) to R11. When R2 receives the teardown message from R10, R2 removes the stalled incoming link between R10 and R2. On the other hand, the green thread reaches R1 and Hmax is updated from zero to unknown. In this case, R1 performs thread extending with changing color since the thread is received on a new incoming link but extended on the already existing outgoing link. As a result, R1 creates an orange thread of hop count unknown and extend it to R2. The orange thread goes round through existing links without changing color, and finally it is stalled at R1. The state of the network is now shown in Fig.16. Ohba, et al. Experimental [Page 21] RFC 3063 MPLS Loop Prevention Mechanism February 2001 *: location of thread stalling (or,U) (or,U) R11 <------ R10 <-------------------- R9 | | ^ |(or,U)* | | | | |(or,U) v | | R1 -------> R2 --------> R3 --------> R4 --------- R5 [leaf] (or,U) (or,U) ^ (or,U) | | (bl,3) | R6 -------> R7 --------> R8 [leaf] (bl,1) (bl,2) Fig.16 The network state Then R4 changes its next hop from R9 to R5. Since R4 is extending an orange thread, it first sends a teardown message to the old next hop R9 to withdraw the orange thread on the old route. Next, it creates a yellow thread of hop count unknown, and sends a request message with (ye,U,255) to R5. Since R5 is the egress node, the yellow thread rewinding starts. R5 returns a label mapping message. The thread rewinding procedure is performed at each node, as the label mapping message is returned upstream hop-by-hop. If R1 receives a label mapping message before receiving the orange thread's withdrawal from R11, R1 returns a label mapping message to R11. On receiving the orange thread's withdrawal, R1 will create a transparent thread and extend it by sending an update message with (tr,1,255) in order to notify downstream of the known hop count. Otherwise, if R1 receives the orange thread's withdrawal before receiving a label mapping message, R1 removes the stalled incoming orange link and waits for rewinding of the outgoing orange thread. Finally, when R1 receives a label mapping message from R2, it creates a transparent thread (tr,1,255) and extend it downstream. In both cases, a merged LSP ((R1->R2),(R6->R7->R8))->R3->R4->R5) is established and every node obtains the correct link hop count. The final network state is shown in Fig.17. Ohba, et al. Experimental [Page 22] RFC 3063 MPLS Loop Prevention Mechanism February 2001 R11 <------ R10 <-------------------- R9 | | | | | | | | | v | | R1 -------> R2 --------> R3 --------> R4 --------> R5 [leaf] (tr,1) (tr,2) ^ (tr,4) (tr,5) | | (tr,3) | R6 -------> R7 --------> R8 [leaf] (tr,1) (tr,2) Fig.17 The final network state 7.2. Second example +----- R6----> R7-----+ | | | v R1---->R2 R4----->R5 | ^ | | +--------->R3---------+ Fig.18 Example MPLS network (2) Assume that in Fig.18, there is an established LSP R1->R2->R3->R4- >R5, and the next hop changes at R2 from R3 to R6. R2 sends a request to R6 with a red thread (re,2,255). When the request with (re,4,253) reaches R4, it extends the thread to R5 with changing color. Thus, a new green thread is created at R4 and extended to R5 by sending an update message with (gr,5,255). When R5 receives the update, it updates the incoming link hop count to 5 and returns an ack (or a notification message with a success code) for the update. When R4 receives the ack for the update, it returns a label mapping message to R7. When R2 receives the label mapping message on the new route, it sends a teardown message to R3. When R4 receives the teardown message, it does not sends an update to R5 since Hmax does not change. Now an established LSP R1->R2->R6->R7->R4->R5 is obtained. Then, the next hop changes again at R2 from R6 to R3. Ohba, et al. Experimental [Page 23] RFC 3063 MPLS Loop Prevention Mechanism February 2001 R2 sends a request with a blue thread (bl,2,255) to R3. R3 forwards the request with (bl,3,254) to R4. When R4 receives the request, it immediately returns a label mapping message to R3 since Hmax does not change. When R2 receives the label mapping message on the new route, it sends a teardown message to R6. The teardown message reaches R4, triggering an update message with a transparent thread (tr,4,255) to R5, since Hmax decreases from 4 to 3. R5 updates the incoming link hop count to 4 without returning an ack. 8. Thread control block A thread control block (TCB) is maintained per LSP at each node and may contain the following information: - FEC - State - Incoming links Each incoming link has the following attributes: o neighbor: upstream neighbor node address o color: received thread color o hop count: received thread hop count o label o S-flag: indicates a stalled link - Outgoing links Each outgoing link has the following attributes: o neighbor: downstream neighbor node address o color: received thread color o hop count: received thread hop count o label o C-flag: indicates the link to the current next hop If a transparent thread is received on an incoming link for which no label is assigned yet or a non-transparent color is stored, discard the thread without entering the FSM. An error message may be returned to the sender. Whenever a thread is received on an incoming link, the following actions are taken before entering the FSM: (1) Store the received thread color and hop count on the link, replacing the old thread color and hop count, and (2) set the following flags that are used for an event switch within "Recv thread" event (see section 8.1). Ohba, et al. Experimental [Page 24] RFC 3063 MPLS Loop Prevention Mechanism February 2001 o Color flag (CL-flag): Set if the received thread is colored. o Loop flag (LP-flag): Set if the received thread forms a loop. o Arrived on new link flag (NL-flag): Set if the received thread arrives on a new incoming link. If LP-flag is set, there must be an incoming link L, other than the receiving link, which stores the same thread color as the received one. The TCB to which link L belongs is referred to as the "detecting TCB". If the receiving LSR is VC-merge capable, the detecting TCB and the receiving TCB is the same, otherwise, the two TCBs are different. Before performing a thread extending, the thread TTL is decremented by one. If the resulting TTL becomes zero, the thread is not extended but silently discarded. Otherwise, the thread is extended and the extended thread hop count and color are stored into the outgoing link. When a node receives a thread rewinding event, if the received thread color and the extending thread color are different, it discards the event without entering the FSM. 8.1. Finite state machine An event which is "scheduled" by an action in an FSM must be passed immediately after the completion of the action. The following variables are used in the FSM: o Ni: number of unstalled incoming links o Hmax: largest incoming hop count o Hout: hop count of the outgoing link for the current next hop o Hrec: hop count of the received thread In the FSM, if Hmax=unknown, the value for (Hmax+1) becomes the value reserved for unknown hop count plus 1. For example, if Hmax=unknown=255, the value (Hmax+1) becomes 256. A TCB has three states; Null, Colored, and Transparent. When a TCB is in state Null, there is no outgoing link and Ni=0. The state Colored means that the node is extending a colored thread on the outgoing link for the current next hop. The state Transparent means that the node is the egress node or the outgoing link is transparent. The flag value "1" represents the flag is set, "0" represents the flag is not set, and "*" means the flag value is either 1 or 0. Ohba, et al. Experimental [Page 25] RFC 3063 MPLS Loop Prevention Mechanism February 2001 The FSM allows to have one transparent outgoing link on the old next hop and one colored outgoing link on the current next hop. However, it is not allowed to have a colored outgoing link on the old next hop. State Null: Event Action New state Recv thread Flags CL LP NL 0 * * Do nothing. No change 1 0 * If the node is egress, start thread rewinding Transparent and change the color of the receiving link to transparent. Otherwise, extend the received thread without Colored changing color. 1 1 * Stall the received thread; if Hrec0 and Hrec