RFC 3063
MPLS Loop Prevention Mechanism
RFC 3063: MPLS Loop Prevention Mechanism 🎀
Okay bestie, here's the card first. ✨
- Number: RFC 3063
- Title: MPLS Loop Prevention Mechanism
- Authors: Y. Ohba and Y. Katsube (Toshiba), E. Rosen (Cisco Systems), P. Doolan (Ennovate Networks)
- Category: Experimental 🧪
- Date: February 2001 📅
- Obsoletes / Updates: This one doesn't obsolete or update anything. It's a fresh start. 🌱
Status of this Memo ✨
This memo defines an Experimental Protocol for the Internet community. 🧪 It is not an Internet standard of any kind, so don't treat it like one. The community is asking for discussion and suggestions for improvement, so go ahead and send them. 💌 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 VC merge, but it does not require it. 💅 It works with either the ordered downstream-on-demand allocation or the ordered downstream allocation. ✨
The amount of information that must be passed in a protocol message is tightly bounded, which means no path-vector is used. 📦 That's the magic part. 🪄 When a node needs to change its next hop, a distributed procedure runs, but only the nodes downstream of the change get involved. 🦋
Translation: the change is local, the cleanup is local, and nobody upstream gets dragged into the drama. 💀
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 ..................................... 441. 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. 🔁
Here's how it goes. 🎬 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. 🧵 Every thread gets its own unique "color", and no two threads in the network can share a color. 🌈
For a given LSP, once a thread is extended to a particular next hop, no other thread gets extended to that next hop unless the hop count changes at the furthest upstream node. 🚦 The only state that has to be tied to a particular next hop for a particular LSP is the thread color and the hop count. 💜
If there's a loop, some thread will come back around to an LSR it already passed through. 😱 Good news: that's easy to spot, because every thread has a unique color. 🕵️♀️
Sections 3 and 4 explain the procedures for figuring out that there is no loop. 🧠 Once that's confirmed, the threads get "rewound" back to the point where they started. ⏪ As they rewind, labels get assigned. 🏷️ So labels are not assigned until loop freedom is guaranteed. 🙅♀️ Patience, bestie. 🫶
While a thread is still extended, the LSRs it passes through have to remember its color and hop count. 📝 Once the thread has been rewound, they only need to remember the hop count. ✂️
The thread mechanism works whether 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 the ordered downstream unsolicited label allocation [2,3]. 🎁 The mechanism can also apply to loop detection, old path retention, and load-splitting. ⚖️
The state information that has to be carried in protocol messages, and maintained internally in state tables, is of fixed size, no matter how big the network is. 📏 That's why the thread mechanism is more scalable than the alternatives that require path-vectors to be carried. 📈👑
When a routing change happens and a new LSP needs to be set up, the thread mechanism only needs communication between nodes downstream of the point of change. 🎯 Nodes upstream of that point don't need to be contacted at all. 🙅♀️ That makes the thread mechanism more robust than alternatives that need a diffusion computation (see section 9). 💪
2. Basic definitions 📚
Let's get the vocab down before we go further. 🤓
LSP
We use the term LSP to mean a multipoint-to-point tree whose root is the egress node. 🌳 See section 3.5 of [3].
Below, we talk as if there were only a single LSP being set up in the network. 🫧 That lets us say "incoming" and "outgoing" links without repeating "for the same LSP" every single time. 💅
Incoming Link, Upstream Link Outgoing Link, Downstream Link
At a given node, a given LSP has one or more incoming (upstream) links and one outgoing (downstream) link. ⬅️➡️ A "link" is really an abstract relationship with an "adjacent" LSR. 🤝 It's an "edge" in the "tree", not necessarily a specific concrete thing like an "interface". 🔌
Leaf Node, Ingress Node
A node that has no upstream links. 🌱
Eligible Leaf Node
A node that is capable of being a leaf node. 🙌 For example, a node is not an eligible leaf node if it isn't 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 that is furthest upstream of it. 🏃♀️ At any node, the link hop count for the downstream link is one more than the largest of the hop counts on the upstream links. ➕1
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 zero. 0️⃣
Here's an example of link hop counts in Fig.1. 👀
1 2
A---B---C K
| |
|3 |1
| |
| 4 5 | 6 7
D---G---H---I---J
|
|2
1 |
E---FFig.1 Example of link hop counts 🍓
Next Hop Acquisition
Node N thought FEC F was unreachable, but now it has a next hop for it. 🎉
Next Hop Loss
Node N thought node A was the next hop for FEC F, but now it doesn't have a next hop for FEC F anymore. 💔 A node loses a next hop whenever that 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 from B. 🔄 A next hop change can be seen as a combination of a next hop loss on the old next hop and a next hop acquisition on the new one. 🧩 It's giving "swap". 💅
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 💖
okay so threads have three attributes 🧚 and they can all get packed into one single thread object, like this:
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 node starts a path control message, it gives that message a unique "color" 🎨. the color has to be unique in both time and space 🕰️. it's built from an IP address of the node concatenated with a unique event identifier, pulled from a numbering space that the node keeps track of. the path setup messages the node sends downstream carry this color. and when it sends one downstream, it remembers the color, and that color becomes the color of the downstream link.
when a colored message comes in, its color becomes the color of the incoming link. a thread made of messages of one certain color is known as a thread of that color.
the special color value "transparent" (=all 0's) is reserved, so it's off limits 🙅
one possible way to assign unique colors is to start the event identifier at its initial value and increment it by one (modulo its maximum value) each time a color gets assigned. with 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 🦋
we need to carry hop counts in the path control messages so we can maintain link hop counts 📏. for instance, a leaf node assigns a hop count of 1 to its downstream link and stores that value in the path setup message it sends downstream. when a path setup message is sent downstream, a node assigns a hop count that is one more than the largest of its incoming link hop counts to its downstream link, and stores that value in the path setup message it sends downstream. once the value is stored in a path control message, we can call it a "thread hop count" 💅
a special hop count value "unknown" (=0xff) is used when a loop is found, and it's larger than any other known value 🔁. once the thread hop count is "unknown", it doesn't get 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 on the message, and the TTL gets decremented at each hop. when the TTL reaches 0, the message isn't forwarded any more. unlike thread hop counts and thread colors, thread TTLs don't need to be stored on incoming links. 🫶
3.2. Thread loop 🔁
when the same colored thread is received on multiple incoming links, or when the received thread color was assigned by the receiving node itself, it's 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 that color. 👀
3.3. Primitive thread actions 🎬
five primitive actions are defined to prevent LSP loops by using threads: "extending", "rewinding", "withdrawing", "merging", and "stalling" 💜. this section only describes each primitive action on its own. it doesn't cover how these primitive actions get combined or how the algorithm works as a whole. the main body of the algorithm is described in section 4.
Thread Extending 🚀
when a node starts sending a path setup message to its next hop with a set of thread attributes, it's 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's 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 the link may have had before. 🔄
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 1, the thread color is set to the ingress node's address with an appropriate event identifier, and the thread TTL is set to 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) extends the thread with changing color. the received thread is extended with changing color if it's received on a new incoming link and extended on an already existing outgoing link. otherwise, it's extended without changing color. when a thread is extended with changing color, a new colored thread is created and extended. 🌈
thread creation doesn't only happen 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, and it isn't extending a colored thread, a transparent thread is extended. 🦋
Thread Merging 🫧
when a node that has a colored outgoing link receives a new thread, it doesn't necessarily extend the new thread. it may instead "merge" the new thread 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, those other incoming threads are considered to be merged into the new outgoing thread. 🤝
specifically, a received thread is merged if all of the following conditions hold:
- A colored thread is received by node N, AND
- The thread does not form a loop, AND
- N is not an egress node, AND
- N's outgoing link is colored, AND
- 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 that have been merged with it will rewind as well. 🔙
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 that only applies to threads forming a loop, and it's referred to as "thread stalling" 😤. the incoming link storing the stalled thread is called a "stalled incoming link". a distinction is made between stalled incoming links and unstalled incoming links. ⚖️
Thread Rewinding ⏪
when a thread reaches a node that satisfies a particular loop-free condition, the node returns an acknowledgment message back to the message initiator along the reverse path that the thread was extended on. sending these acknowledgment messages is the "rewinding" of the thread. 💫
the loop-free condition is:
- A colored thread is received by the egress node, OR
- 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 that was received on a particular link, it changes the color of that link to transparent. 🪄
if there's 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. in addition, M rewinds any other incoming thread that had been merged with the thread being rewound, including stalled threads. 🧶
each node can start label switching once the thread colors on all incoming and outgoing links have become transparent. 🏷️
note that transparent threads are threads that have already been rewound, so there's no such thing as rewinding a transparent thread. 🙅♀️
Thread Withdrawing 🧹
it's 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 "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:
- The incoming link hop count that was just removed had a larger hop count than any of the remaining incoming links, AND
- 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 ✨
Okay bestie, time for the pictures! 🦋 We're using a little notation here. A pair of thread attributes stored in each link is written as "(C,H)", where C is the thread color and H is the thread hop count. 🎀
A thread marked "+" is being created or received right now. A thread marked "-" is being withdrawn right now. 💅
A link with squared brackets, like "[a]", is an unstalled link. A link with braces, like "{a}", is a stalled link. 🌸
Fig. 2 shows a leaf node A creating a blue thread and extending it downstream. It's giving main character energy 💙
(bl,1)
A---[o1]--->
Fig.2 Thread extending at leaf nodeFig.3 shows a thread being extended without changing color at an intermediate node. We start with node B having no incoming or outgoing link at all. When B receives a blue thread with hop count 1 on a new incoming link i1, it extends the thread downstream and keeps the color the same (Fig.3(a)). Then B gets a red thread with an unknown hop count on incoming link i1 again (Fig.3(b)). The red thread also gets extended without a color change, because i1 and o1 both already exist. 🫶
(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 colorFig.4 shows a thread being extended with a color change. In Fig.4(a) there's a single incoming link i1 and a single outgoing link o1. Then a red thread with hop count 3 comes in on a new incoming link i2. Since o1 already exists, the received thread gets extended with a color change: a new green thread is created and extended (Fig.4(b)). Iconic. 🌈
(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 colorFig.5 shows thread merging. When node B receives a red thread with hop count 3, that thread does not get extended, because the hop count on the outgoing link is at least one greater than the hop count of the received thread. Both the red and the blue threads get rewound once the blue thread on outgoing link o1 is rewound. 🧚
(bl,3) (bl,4)
----[i1]--->B----[o1]--->
^
|
----[i2]----+
(re,3)+
Fig.5 Thread mergingFigs 6 and 7 show thread stalling. In Fig.6, node B receives a blue thread with hop count 10 on incoming link i2. B "stalls" that thread because the blue thread would form a loop. In Fig.7, a leaf node A finds the loop of its own thread. Loops are not it. 🙈
(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 thread rewinding. When the yellow thread that is currently being extended gets rewound (Fig.8(a)), the node changes the color of all its incoming and outgoing threads to transparent. It then propagates the rewinding to its upstream nodes (Fig.8(b)). Rewind era. 💀
(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 rewindingFig.9 shows thread withdrawing. In Fig.9(a), the red thread on incoming link i2 is withdrawn. Hmax then decreases from 3 to 1, so 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 thread withdrawing example. In Fig.10(a), the red thread on incoming link i3 is withdrawn. Here Hmax decreases from unknown to 1, but no thread gets extended, as Fig.10(b) shows. The reason is that the outgoing link already carries 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 one more thread withdrawing example. In Fig.11(a), the transparent thread on incoming link i3 is withdrawn. In this case a transparent thread does get extended (Fig.11(b)), because 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)4. Thread algorithm ✨
The algorithm here assumes ordered downstream-on-demand allocation. It can still be adapted to ordered downstream allocation, as shown in section 5. 🎀
In the algorithm, a next hop change event is split into two events, handled in this order: first a next hop loss event on the old next hop, then a next hop acquisition event on the new next hop. 💅
These notations are defined:
Hmax: the largest incoming link hop count
Ni: the number of unstalled incoming linksHere's how the thread algorithm works. 🧚
When a node acquires a new next hop, it creates a colored thread and extends it downstream.
When a node loses a next hop it has extended a thread to, it may withdraw that thread. As section 3 describes, 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 hop count of the received thread is not unknown, a colored thread with an unknown hop count is created and extended. If the hop count of the received thread 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 with hop count (Hmax+1) is extended downstream. 🌸
When a node that has a transparent outgoing link receives a transparent thread, and Hmax decreases, the node extends that thread downstream without changing its color. 🦋
5. Applicability of the algorithm 💜
The thread algorithm described in section 4 can be applied to various LSP management policies. 👑
5.1. LSP Loop prevention/detection
The same thread algorithm applies to both LSP loop prevention and LSP loop 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 gets sent until the thread rewinds. ✨
In loop detection mode, a node returns a label mapping message without a thread object immediately after it receives a colored thread. A node that receives a label mapping message without 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 keep using the old path if the new route is looping. This happens 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 also be adapted to ordered downstream allocation mode (or egress-initiated ordered control). To do that, you treat newly receiving a label mapping message [4] from the next hop as a next hop acquisition event. 🧚
A node that doesn't have an incoming link yet behaves as a leaf. When the tree is being built up for the first time (for example, right after the egress node has come up), each node in turn behaves as a leaf for a short period of time. ⭐
5.4. How to realize load splitting 🎀
okay so a leaf node can literally load split by setting up two different LSPs for the same FEC 💅 Then it just gives the downstream links for those two LSPs different colors. The thread algorithm now stops a loop in either path, but it also lets the two paths share a downstream node 🫶
if an intermediate node wants to load split, here's the tea 🍵 Say 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 split into n subsets, and each subset gets mapped to one distinct outgoing link 🦋
that gives you n LSPs for the FEC. Each one uses a distinct color for its outgoing link. The thread algorithm now stops a loop in any of the paths, and it also lets two or more of the paths share a downstream node 🌈
now here's where it gets spicy 🌶️ Picture node B in Fig.12 with two incoming links, i1 and i2, and two outgoing links, o1 and o2. i1 is mapped to o1, and i2 is mapped to o2 💜
+------------------...--------------------+
. (bl,3) (bl,4) |
. ----[i1]---+ +--[o1]---> .... --+
. \ /
. v /
| B
|
+-----------[i2]--->B----[o2]--->
(bl,10)+ (bl,11)
Fig.12 Load splitting at intermediate nodeso if a blue thread gets received on i1, extended on o1, and then comes back to node B on i2, it is not treated as forming a loop 🙈 Why? Because i1 and i2 belong to different subsets! Instead, the blue thread received on i2 gets extended on o2. And if the thread extended on o2 gets rewound, you end up with a single loop-free LSP that goes through node B twice ✨ iconic, honestly
there's another type of load splitting, where packets arriving on one incoming link can be label switched to any one of several outgoing links. ngl this one doesn't seem like a good load-splitting scheme, because the packet order within the same FEC isn't preserved 😬 So this document doesn't focus on it.
whether that's a good type of load splitting or not, the real issue is that ATM-LSRs can't 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 gets extended when a thread loop is detected. This cuts down the number of loop prevention 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 doesn't contain a loop when the outgoing link hop count is not "unknown"? 🤔
picture a sequence of LSRs <R1, ..., Rn>, where there's a loop going through the LSRs in that sequence. (So packets from R1 go to R2, then to R3, and so on, then to Rn, and then from Rn back to R1 🔁)
say the thread hop count of the link between R1 and R2 is k. By the procedures above, the hop counts between Rn and R1 have to be k+n-1. But the algorithm also makes sure that if a node has an incoming hop count of j, its outgoing link hop count has to be at least j+1. So if we assume the LSP made by rewinding a thread contains a loop, the hop counts between R1 and R2 have to be at least k+n. From that we get the absurd conclusion that n=0, so there's no such sequence of LSRs. Case closed, bestie 💖
6.2.1. Case2: LSP with unknown link hop counts
an established path also doesn't contain a loop when the outgoing link hop count is "unknown" 🫶 The reason is that 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's a loop, some node in that loop will be the last one to receive a thread over a new incoming link. That thread will always arrive back at that node without its color having changed. So the loop will always get caught by at least one of the nodes in it 🦋
6.4. Why L3 loop is not mis-detected 💅
since no node ever extends the same colored thread downstream twice, a thread loop is only detected if there actually is an L3 routing loop. No false alarms, periodt ✨
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) basically stays in the loop. That means a path reconfiguration (thread withdrawing on the old path and thread extending on the new path) can be issued from any node that might receive a route change event, so the loop gets broken 👑
6.6. Why different colored threads do not chase each other 🏃♀️
in the algorithm, multiple thread color and/or hop count updates can happen if several leaf nodes start extending threads at the same time. So how do we stop multiple threads from looping forever? 😭
first, when a node finds that a thread forms a loop, it creates a new thread with hop count "unknown". All the looping threads of a known hop count that later arrive at that node get merged into this thread. Such a thread acts like a thread absorber 🧽
second, the "thread extending with changing color" stops two threads from chasing each other. Imagine a received thread always got extended without changing color. Then we'd run into this situation:
G Y
| |
v v
R1------>R2
^ |
| v
R4<------R3
Fig.13 Example of thread chasingin Fig.13, (1) node G acquires R1 as a next hop and starts extending a green thread of hop count 1, (2) node Y acquires R2 as a next hop and starts extending a yellow thread of hop count 1, and (3) both node G and node Y withdraw their threads before the threads go round 😳
in that case, the yellow and green threads would go round and get back to R2 and R1, respectively. But when the threads get back to R2 and R1, the incoming links that store the yellow and green colors don't exist anymore. As a result, the yellow and green threads would chase each other forever around the loop 🌀
but since we have the "extending with changing color" mechanism, that doesn't actually happen 🙌 When a green thread is received at R2, R2 extends the thread with changing color, i.e., it creates a new red thread and extends that. Similarly, when a yellow thread is received at R1, R1 creates a new purple thread and extends it. So the thread loop is detected even after node G and node Y withdraw their threads ✨ This makes sure a thread gets extended around the loop with a color assigned by some node that is in the loop.
there's at least one case the "extending with changing color" mechanism still can't handle, and that's "self-chasing", where thread extending and thread withdrawing for the same thread chase each other around a loop. This happens when a node withdraws a thread right after extending it into an L3 loop 🙈
a heuristic for self-chasing is to delay the execution of thread withdrawing at the initiating node of that thread withdrawing. Either way, the thread TTL mechanism can eliminate any kind of thread looping 💜
7. Loop prevention examples 🍓
in this section, we show two examples of how the algorithm can prevent LSP loops in given networks 🧚♀️
we assume that 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 🦋
Okay bestie, picture an MPLS network with an L3 loop hiding inside it 👀. Each arrow is the current next hop of the FEC at each node. Then the leaf nodes R1 and R6 decide to build an LSP. Chaos incoming 💅
R11 ------- R10 <-------------------- R9
| | ^
| | |
| | |
v v |
R1 -------> R2 --------> R3 --------> R4 --------- R5
[leaf] ^
|
|
|
R6 -------> R7 --------> R8
[leaf]Fig.14 Example MPLS network (1)
Say R1 and R6 send a label request at the exact same time, and the initial thread TTL is 255. First up, we look at how to stop LSP loops from forming 🙌
We describe a set of thread attributes as (color, hop count, TTL). Super simple, very cute 🎀
The request from R1 contains (re,1,255), and the request from R6 contains (bl,1,255).
Now say R3 sees the request from R1 first, before the one from R6. When R3 gets that first red request, it forwards it as (re,3,253) and keeps the color red. Why? Because both the incoming link and the outgoing link are brand new, so there's no drama yet ✨ Then R3 gets the blue request. This time the outgoing link already exists, so R3 does thread extending and changes color. It makes a new brown thread and forwards the request as (br,4,255). Iconic color glow-up 🌈
When R2 gets the request from R10 carrying (re,6,250), it notices the red thread has formed a loop. So R2 stalls the red thread 🛑 Then R2 creates a purple thread with an unknown hop count, and extends it downstream by sending (pu,U,255) to R3. Here U means "unknown," in case you were wondering 🤓
Next, R2 gets another request from R10, this time (br,7,252). The brown thread gets merged into the purple thread, and R2 sends no request to R3. Efficient, and I respect it 💜
Meanwhile the purple thread keeps going around the loop without changing color through the existing links. Eventually R2 spots the thread loop and stalls the purple thread too. The received thread hop count is unknown, so no new thread gets created. In this case there's no thread rewinding at all 😌 Here's the network at this point:
*: 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 switches 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 to withdraw that purple thread. After that, R10 creates a green thread with an unknown hop count and sends (gr,U,255) to R11. Bye-bye, old route 👋
When R2 gets the teardown message from R10, it removes the stalled incoming link between R10 and R2. Clean ✨
Meanwhile the green thread reaches R1, and Hmax goes from zero to unknown. R1 does thread extending with a color change, because the thread arrived on a new incoming link but is being extended on a link that already exists. So R1 creates an orange thread with an unknown hop count and extends it to R2. Orange energy 🍊
The orange thread goes around the existing links without changing color, and it ends up stalled at R1. Here's the network now:
*: 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 that orange thread on the old route. Then R4 creates a yellow thread with an unknown hop count and sends (ye,U,255) to R5.
Because R5 is the egress node, the yellow thread rewinding starts right there 🎉 R5 returns a label mapping message. Thread rewinding happens at each node as the label mapping message travels back upstream, hop by hop.
Now, what happens at R1 depends on timing, and both paths are fine 💖
If R1 gets a label mapping message before it receives the orange thread's withdrawal from R11, R1 returns a label mapping message to R11. Once the withdrawal shows up, R1 creates a transparent thread and extends it by sending an update message with (tr,1,255). This tells downstream the hop count is now known.
Otherwise, if R1 gets the orange thread's withdrawal first, before any label mapping message, R1 removes the stalled incoming orange link and waits for the rewinding of the outgoing orange thread. Eventually R1 gets a label mapping message from R2, creates a transparent thread (tr,1,255), and extends it downstream.
Either way, we end up with a merged LSP, ((R1->R2),(R6->R7->R8))->R3->R4->R5, and every node learns the correct link hop count 🥳 The final network state looks like this:
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 🌸
Let's look at Fig.18. Assume there's an established LSP R1->R2->R3->R4->R5, and at R2 the next hop changes from R3 to R6 🔀
+----- R6----> R7-----+
| |
| v
R1---->R2 R4----->R5
| ^
| |
+--------->R3---------+Fig.18 Example MPLS network (2)
R2 sends a request to R6 with a red thread, (re,2,255). When the request arrives at R4 as (re,4,253), R4 extends the thread to R5 and changes the color. So a brand new green thread is born at R4, and R4 extends it to R5 by sending an update message with (gr,5,255) 🌿
When R5 gets the update, it updates the incoming link hop count to 5, then returns an ack (or a notification message with a success code) for the update ✅ When R4 gets that ack, it returns a label mapping message to R7.
Once R2 receives the label mapping message on the new route, it sends a teardown message to R3. When R4 gets the teardown message, it doesn't send an update to R5, since Hmax doesn't change. And just like that, we have an established LSP R1->R2->R6->R7->R4->R5 🎊
Plot twist: the next hop changes again at R2, this time from R6 to R3 😳
R2 sends a request with a blue thread, (bl,2,255), to R3. R3 forwards the request as (bl,3,254) to R4.
When R4 gets the request, it immediately returns a label mapping message to R3, because Hmax doesn't change. No drama 💅
When R2 gets the label mapping message on the new route, it sends a teardown message to R6. That teardown reaches R4 and triggers an update message carrying a transparent thread, (tr,4,255), to R5, because Hmax decreases from 4 to 3. R5 updates the incoming link hop count to 4, and it doesn't return an ack this time 🙈
8. Thread control block 🧠
A thread control block (TCB) is maintained per LSP at each node, and it may contain the following info:
- 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 hopIf a transparent thread gets received on an incoming link that has no label assigned yet, or on one that has a non-transparent color 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, these actions happen before entering the FSM:
- Store the received thread color and hop count on the link, replacing the old thread color and hop count.
- Set the following flags, which are used for an event switch within the "Recv thread" event (see section 8.1) 🚩
- Color flag (CL-flag): set if the received thread is colored.
- Loop flag (LP-flag): set if the received thread forms a loop.
- 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, that stores the same thread color as the received one. The TCB that link L belongs to is called the "detecting TCB". If the receiving LSR is VC-merge capable, the detecting TCB and the receiving TCB are the same. Otherwise, the two TCBs are different 🔍
Before performing thread extending, the thread TTL gets decremented by one. If the resulting TTL becomes zero, the thread isn't extended and is just silently discarded 🗑️ Otherwise, the thread is extended, and the extended thread hop count and color are stored on the outgoing link.
When a node receives a thread rewinding event and the received thread color and the extending thread color are different, it discards the event without entering the FSM 💀
8.1. Finite state machine ✨
okay so, an event that gets "scheduled" by an action in the FSM has to be passed immediately after that action finishes. no waiting around, bestie 💅
these are the variables the FSM uses:
- Ni: number of unstalled incoming links
- Hmax: largest incoming hop count
- Hout: hop count of the outgoing link for the current next hop
- Hrec: hop count of the received thread
in the FSM, if Hmax=unknown, then the value for (Hmax+1) becomes the value reserved for unknown hop count plus 1. for example, if Hmax=unknown=255, then (Hmax+1) becomes 256 🔢
a TCB has three states: Null, Colored, and Transparent. in state Null, there's no outgoing link and Ni=0. state Colored means the node is extending a colored thread on the outgoing link for the current next hop. state Transparent means the node is the egress node, or the outgoing link is transparent. it's giving "two very different vibes" 🦋
the flag value 1 means the flag is set, 0 means it isn't, and * means it can be either 1 or 0.
the FSM lets you have one transparent outgoing link on the old next hop and one colored outgoing link on the current next hop. BUT it's not allowed to have a colored outgoing link on the old next hop. so no, you can't have both 🙅♀️
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 Hrec<unknown, No change
schedule "Reset to unknown" event for the
detecting TCB.
Next hop If eligible-leaf, create a colored thread and Colored
acquisition extend it.
Others Silently ignore the event. No changeState Colored:
Event Action New state
Recv thread
Flags
CL LP NL
0 * * If Hmax+1<Hout<unknown, create a colored No change
thread and extend it. Otherwise, do nothing.
1 0 * If Hmax<Hout, merge the received thread. No change
Otherwise, extend the thread with (if NL=1)
or without (if NL=0) changing color.
1 1 * Stall the received thread.
If Ni=0 and the node is not an eligible leaf, Null
initiate thread withdrawing.
If Ni>0 and Hrec<unknown, schedule "Reset to No change
unknown" event for the detecting TCB.
Otherwise, do nothing. No change
Rewound Propagate thread rewinding to previous hops Transparent
that are extending a colored thread; change
the colors stored in all incoming and outgoing
links to transparent; if Hmax+1<Hout, extend
transparent thread. Withdraw the thread on
the outgoing link for which C-flag=0.
Withdrawn Remove the corresponding incoming link.
If Ni=0 and the node is not an eligible leaf, Null
propagate thread withdrawing to all next hops.
Otherwise, if Hmax+1<Hout<unknown, create No change
a colored thread and extend it.
Otherwise, do nothing. No change
Next hop If there is already an outgoing link for the Transparent
acquisition next hop, do nothing. (This case happens only
when the node retains the old path.)
Otherwise, create a colored thread and extend No change
it.
Next hop If the outgoing link is transparent and the No change
loss node is allowed to retain the link and the
next hop is alive, do nothing.
Otherwise, take the following actions.
Initiate thread withdrawing for the next hop;
if the node becomes a new egress, schedule
"Rewound" event for this TCB.
If Ni=0, move to Null. Null
Otherwise, do nothing. No change
Reset to Create a colored thread of hop count unknown No change
unknown and extend it.
Others Silently ignore the event. No changeState Transparent:
Event Action New state
Recv thread
Flags
CL LP NL
0 * * If Hmax+1<Hout, extend a transparent thread. No change
1 0 * If the node is egress or if Hmax<Hout, change No change
the color of the receiving link to transparent
and start thread rewinding.
Otherwise, extend the thread with (if NL=1) Colored
or without (if NL=0) changing color.
Withdrawn Remove the corresponding incoming link.
If Ni=0 and the node is not an eligible leaf, Null
propagate thread withdrawing to next hops.
Otherwise, if Hmax+1<Hout, create No change
a transparent thread and extend it.
Otherwise, do nothing. No change
Next hop Create a colored thread and extend it. Colored
acquisition
Next hop If the node is allowed to retain the outgoing No change
loss link and the next hop is alive, do nothing.
Otherwise, take the following actions.
Initiate thread withdrawing.
If Ni=0, move to Null. Null
Otherwise, do nothing. No change
Others Silently ignore the event. No change9. Comparison with path-vector/diffusion method 🧐
here's the tea on how the thread algorithm stacks up against the path-vector/diffusion method:
- okay so the path-vector gets bigger as the LSP gets longer 📈, but threads stay the same size no matter what. that means the messages in the thread algorithm don't care how big the network is or what it looks like. and thread merging cuts down on how many messages are floating around out there. so it scales way better, periodt ✨
- in the thread algorithm, a node that's switching its next hop for a particular LSP only has to talk to nodes sitting between it and the LSP egress on the new path. but with path-vector, the node has to start a diffusion computation that pulls in nodes that aren't between it and the egress at all 🙃
this makes the thread algorithm way more robust 💪. with a diffusion computation, misbehaving nodes that aren't even on the path can slow the path setup down. with threads, only the nodes actually on the path can delay setup.
- the thread algorithm works great with both ordered downstream-on-demand allocation and ordered downstream allocation 🎀. the path-vector/diffusion algorithm, though, is tightly coupled with ordered downstream allocation.
- the thread algorithm is retry-free, so path (re)configuration is super quick ⚡. the diffusion algorithm tends to drag out the reconfiguration time, since a node at the route change point has to check in with all of its upstream nodes 😩
- in the thread algorithm, the node can keep using the old path if there's an L3 loop on the new path, just like the path-vector algorithm does 🛟
10. Security Considerations 🔐
okay this one's short but it matters. using the procedures in this document doesn't add any security impact beyond whatever might generally show up when you use any MPLS procedures. so keep that in mind, bestie 🫶
11. Intellectual Property Considerations ⚖️
Toshiba and/or Cisco may seek patent or other intellectual property protection for some of the technologies in this document. if any standards that come out of this document are, or become, protected by one or more patents assigned to Toshiba and/or Cisco, then Toshiba and/or Cisco intend to disclose those patents and license them on reasonable and non-discriminatory terms.
12. Acknowledgments 💌
we'd like to thank Hiroshi Esaki, Bob Thomas, Eric Gray, and Joel Halpern for their comments. we love a supportive group chat 🥹
13. Authors' Addresses 📮
Yoshihiro Ohba Toshiba Corporation 1, Komukai-Toshiba-cho, Saiwai-ku Kawasaki 210-8582, Japan
EMail: yoshihiro.ohba@toshiba.co.jp
Yasuhiro Katsube Toshiba Corporation 1, Toshiba-cho, Fuchu-shi, Tokyo, 183-8511, Japan
EMail: yasuhiro.katsube@toshiba.co.jp
Eric Rosen Cisco Systems, Inc. 250 Apollo Drive Chelmsford, MA, 01824
EMail: erosen@cisco.com
Paul Doolan Ennovate Networks 330 Codman Hill Rd Marlborough MA 01719
EMail: pdoolan@ennovatenetworks.com
14. References 📚
[1] Callon, R., et al., "A Framework for Multiprotocol Label Switching", Work in Progress.
[2] Davie, B., Lawrence, J., McCloghrie, K., Rosen, E., Swallow, G., Rekhter, Y. and P. Doolan, "MPLS using LDP and ATM VC Switching", RFC 3035, January 2001.
[3] Rosen, E., et al., "A Proposed Architecture for MPLS", Work in Progress.
[4] Andersson, L., Doolan, P., Feldman, N., Fredette, A. and B. Thomas, "LDP Specification", RFC 3036, January 2001.
Appendix A - Further discussion of the algorithm 🧠
this appendix is the chill, tutorial version of the algorithm, and it explains some of the reasoning behind it 🌸. for the precise spec, the FSM is the one that's authoritative, so if the vibes and the FSM ever disagree, trust the FSM 💜
as in the main body, we talk like there's only one LSP. otherwise we'd be saying "... of the same LSP" every five seconds 🙈. we also only look at the case where the algorithm is used for loop prevention, not loop detection 🦋
A.1. Loop Prevention the Brute Force Way ✨
okay so let's start with the simplest idea, which we'll call "loop prevention by brute force" 💅 In this algorithm, every path setup attempt has to go all the way to the egress and then come all the way back before the path counts as set up. It's obviously loop-free, because the setup messages literally made it to the egress and back 🔁
Say there's an existing LSP B-C-D-E going to egress node E. Now node A wants to join it 🦋 In this algorithm, A sends a message to B, B sends one to C, C sends one to D, and D sends one to E. Then messages go from E back to A. The final message, from B to A, carries a label binding, and A can now join the LSP, knowing the path is loop-free 💖
So using our terminology, A created a thread and extended it downstream. The thread reached the egress, then rewound 🌸
We don't need A to be an ingress node for this to work. It can be any node that gets or changes its next hop for the LSP in question, and there could be nodes upstream of it that are also trying to join the LSP 🧚
Now, what happens if there's a loop? The thread never reaches the egress, so it never rewinds 😭 The path setup messages just keep going round and round the loop. If you keep a hop count in them, they can be stopped once that hop count hits a certain maximum value. In other words, when a node gets a path setup message carrying that maximum hop count value, it doesn't send a path setup message downstream 🙈
So how does a looping thread get fixed? For L3 routing to break the loop, some node in the loop MUST experience a next hop change. That node withdraws the thread from its old next hop and extends a thread down its new next hop. If the loop is gone, this thread now reaches the egress and gets rewound 🎀
A.2. What's Wrong with the Brute Force Method? 💀
Let's look at this setup:
A
|
B--D--E
|
CIf A and C both try to join the established B-D-E path, then B and D have to keep state for both setup attempts, the one from A and the one from C. So D has to keep track of two threads, the A-thread and the C-thread 😳 And in general there could be a LOT more nodes upstream of B trying to join the path, and D would have to track every single one of them.
If VC merge isn't being used, this isn't actually that bad. Without VC merge, D really must support one LSP for each upstream node anyway. But if VC merge is being used, supporting an LSP only requires keeping state for each upstream link. It would be way better if the loop prevention technique also made the amount of state a node keeps proportional to the number of upstream links it has, rather than the number of nodes upstream in the LSP 👑
The other problem is that if there's a loop, the setup messages keep looping forever. Even though a thread has already crossed some node twice, that node has no way to tell that the setup message it's receiving right now is part of the same thread as a setup message it got earlier 😵💫
So can we tweak the brute force scheme to fix both of these problems? We totally can ✨ To show how, we're going to introduce two notions: thread hop count, and thread color.
A.3. Thread Hop Count 🍓
Imagine every link in an LSP tree is labeled with the number of hops you'd travel if you went backwards (upstream) from that link to the leaf node that's furthest upstream of it.
For example, this tree would have its links labeled like so:
1 2
A---B---C K
| |
|3 |1
| |
| 4 5 | 6 7
D---G---H---I---J
|
|2
1 |
E---FCall these the "link hop counts" 🔢
Links AB, EF, and KH are labeled one, because you can only go one hop upstream from them. Links BC and FD are labeled 2, because you can go 2 hops upstream from them. Link DG is labeled 4, because you can travel 4 hops upstream from that link, and so on 🫶
Notice that at any node, the hop count on the downstream link is one more than the largest hop count on the upstream links. Iconic, right? 👑
Now let's look at how to keep these hop counts up to date 🧚
To maintain the link hop counts, we have to carry hop counts inside the path setup messages. For example, a node with no upstream links assigns a hop count of 1 to its downstream link, then stores that value in the path setup messages it sends downstream. Once that value is stored in a path setup message, we can call it a "thread hop count" 💜
When a path setup message comes in, its thread hop count gets stored as the link hop count of the upstream link it arrived on 📥
When a path setup message goes out downstream, the downstream link's hop count (and the thread hop count) is set to one more than the largest of the incoming link hop counts 📤
Now suppose a node N has some incoming links and an outgoing link, all with hop counts set properly, and then N gets a new incoming link. If, and only if, the new incoming link's hop count is bigger than all the existing incoming links' hop counts, the downstream link hop count must be changed. In that case, control messages must be sent downstream carrying the new, larger thread hop count 🚀
On the other hand, if N gets a new incoming link whose hop count is less than or equal to the hop count of every existing incoming link, the downstream link hop count stays the same, and no messages need to be sent downstream 🌈
And if N loses the incoming link that had the largest hop count of any incoming link, then the downstream link hop count must get smaller, and messages need to be sent downstream to show that 📉
Now, suppose we weren't worried about loop prevention and only cared about keeping the hop counts right. Then merge points would follow these rules:
A.3.1 When a new incoming thread is received, extend it downstream if and only if its hop count is the largest of all incoming threads.
A.3.2 Otherwise, rewind the thread.
A.3.3 An egress node would, of course, always rewind the thread.
A.4. Thread Color 🎨
Nodes create new threads whenever they change their next hop or acquire one 🌸 Let's say every time a node creates a thread, it gives that thread a unique "color" 💖 The color has to be unique in both time and space: it's made from the node's IP address put together with a unique event identifier from a numbering space the node maintains. The path setup messages the node sends downstream carry this color. When the node sends one of these messages downstream, it remembers the color, and that color becomes the color of the downstream link 🦋
When a colored message comes in, its color becomes the color of the incoming link. A thread made of messages of a certain color is known as a thread of that color 🌈
When a thread gets rewound (and a path is set up), the color is removed. The links become transparent, and sometimes we'll call an established LSP a "transparent thread" ✨
Heads up: packets can't be forwarded over a colored link. They can only be forwarded over a transparent link ⚠️
Now here's the clever bit. If a thread loops, some node will see a message come in over a particular incoming link with a color it has already seen before. Either the node started the thread of that color itself, or it has a different incoming link that already has that color. That fact can be used to stop control messages from looping 🔁 The catch is that the node would have to remember the colors of every thread passing through it that hasn't been rewound or withdrawn. (I.e., it would have to remember a color for each path setup in progress.) That's a lot of memory, bestie 🥲
A.5. The Relation between Color and Hop Count 💅
Put the color mechanism and the hop count mechanism together, and you can prevent loops without any node having to remember more than one color and one hop count per link for each LSP 🎀
Remember, to maintain the hop counts, a node only needs to extend the thread with the largest hop count of any incoming thread 🧠 Now we add this rule:
A.5.1 When an incoming thread is extended downstream, that thread's color gets passed downstream too (I.e., the downstream link's color will be the same as the color of the upstream link with the largest hop count.)
Here's the vibe: at a given node, the downstream link is either transparent, or it has one and only one color 💜
A.5.2 If a link changes color, there's no need to remember the old color. 🗑️
Next up is the idea of "thread merging" 🫶
A.5.2 Suppose a colored thread arrives at a node over an incoming link, the node already has an incoming thread with the same or a larger hop count, and the node has an outgoing colored thread. In this case, we can say the new incoming thread is "merged" into the outgoing thread 🦋
And the best part? When an incoming thread gets merged into an outgoing thread, no messages get sent downstream 🌸 Main character energy for sure ✨
A.6. Detecting Thread Loops ✨
okay so here's the big reveal 💅 if there's a loop, it's ALWAYS going to show up one of two ways: either some node gets two incoming threads of the same color, or the colored thread comes back to whoever started it. no cap, that's the whole trick 🔥 in this section we walk through a few examples so the loop detection actually clicks for you 🦋
1 2
A---B---C K
| |
|3 |1
| |
| 4 5 | 6 7
D---G---H---I---J
|
|2
1 |
E---Fso, back to that last example 🧚 what if H switched its next hop from I to E? H makes a brand new thread and gives it a new color, say, red. H has two incoming links, with hop counts 1 and 5, so it gives its new downstream link hop count 6 and tries a path setup through E.
E now has an incoming red thread with hop count 6. E's downstream link hop count is only 1 now, so E has to extend the red thread to F with hop count 7. F extends it to D with hop count 8, D extends it to G with hop count 9, and G extends it to H with hop count 10.
the red thread is back at its initiator, so the loop is detected 🙈 bestie, that's literally the whole point
but wait, what if, before the red thread makes it back to H, G changes its next hop from H to E? then G extends the red thread to E. but E already has an incoming red link (from H), so the loop is detected anyway 💜
okay now let's define a "stalled thread" 🌸 a stalled thread is a thread that gets merged into the outgoing thread, even though the outgoing thread has a smaller link hop count.
when a thread loop is detected, the thread becomes stalled ✨
A.6.1.
when a loop is detected because a thread of one particular color goes through some node twice, we say the thread is "stalled" at that node 🎀 more precisely, it's the second appearance of the thread that gets stalled. and we say a thread is going through a node twice if the node receives it on an incoming link, but either there's another incoming link with the same color, or the color is one the node assigned itself. iykyk 🫶
A.7. Preventing the Setup of Looping LSPS 💖
the way to stop looping LSPs from being set up should be pretty obvious by now 😌 if node M is node N's next hop, and N wants to set up an LSP (or merge into an LSP that already exists at M), then N extends a thread to M.
M checks first to see if the thread forms a loop (see Appendix A.6). if it does, the thread is stalled. if not, the following procedure happens 💅
A.7.1.
if M receives this thread, and M has a next hop, and either:
- M has no outgoing thread
- the incoming thread hop count is larger than the hop count of all other incoming threads,
then M must extend the thread downstream 🚀
A.7.2.
on the other hand, if M receives this thread, and M has a next hop, and there's another incoming thread with a larger hop count, then:
A.7.2.1.
if the outgoing thread is transparent, M rewinds the new incoming thread 🌈
A.7.2.2.
if the outgoing thread is colored, M merges the new incoming thread into the outgoing thread, but doesn't send any messages downstream 🤫
A.7.3.
if M hasn't already assigned a label to N, it will assign one when, and only when, M rewinds the thread that N extended to it 🍓
A.7.4.
if M merges the new thread into an existing colored outgoing thread, then the new incoming thread will rewind when, and only when, the outgoing thread rewinds 👑
A.8. Withdrawing Threads 🥀
A.8.1.
if a particular node has a colored outgoing thread, and it loses or changes its next hop, it withdraws the outgoing thread 😭
say node N is immediately upstream of node M, and N has extended a thread to M. now suppose N withdraws that thread.
A.8.2.
if M has another incoming thread with a larger hop count, then M doesn't send any messages downstream 🫠
A.8.3.
however, if the withdrawn thread had the largest hop count of any incoming thread, then M's outgoing thread won't have the right hop count and color anymore. so:
A.8.3.1.
M must now extend the incoming thread with the largest hop count downstream. (this makes it forget the old downstream link hop count and color 🧼)
A.8.3.2.
the other incoming threads are considered merged into the thread that gets extended 🤝
A.8.4.
when the last unstalled incoming thread is withdrawn, the outgoing thread must be withdrawn too 💀
A.9. Modifying Hop Counts and Colors of Existing Threads 🦋
we already saw how a withdrawn thread can cause hop count and color changes downstream. here's the thing though: if the hop count and/or color of an outgoing thread changes, then the hop count and color of the matching incoming thread at the next hop change too. and that can cause a color and/or next hop change on that outgoing thread at the next hop. it's a whole chain reaction, ngl 🔥
A.9.1.
whenever there's a hop count change for any incoming thread, a node has to figure out whether the "largest hop count of any incoming thread" changed because of it. if it did, the outgoing thread's hop count (and maybe its color) changes too, which means messages get sent downstream 💌
A.10. When There is No Next Hop 🙅♀️
A.10.1.
if a particular node has a colored incoming thread but no next hop (or it loses its next hop), the incoming thread is stalled 🧊
A.11. Next Hop Changes and Pre-existing Colored Incoming Threads 🌷
it's possible for a node to have a next hop change, or get a next hop for the first time, while it still has colored incoming threads. this happens when routing changes before path setup is finished 😵💫
A.11.1.
if a node has a next hop change or a next hop acquisition while it has colored incoming threads, it creates a thread with a new color. its hop count is one more than the largest of the incoming link hop counts. then it extends this thread downstream 🚀
A.11.2.
when this new thread gets created and extended downstream, all incoming threads get merged into it. any incoming threads that were stalled before are now considered "merged" instead of "stalled" 💜
so even though the outgoing thread has a different color than any incoming thread, the pre-existing incoming threads are all considered merged into the new outgoing thread. that means when the outgoing thread rewinds, the incoming threads rewind too ✨
Note: it is still required to distinguish stalled incoming links from unstalled incoming links when thread withdrawing is performed. don't skip this part, bestie 🙏
A.12. How Many Threads Run Around a Loop? 🎡
we saw that when a loop is detected, the looping thread stalls. but check out this topology 👀
X--->A----->B<---Y
^ |
| v
W--->D<-----C<---Zin this example there's a loop A-B-C-D-A. but there are also threads coming into the loop from X, Y, Z, and W. once the loop is detected, there's honestly no reason for any other thread to wrap all the way around it. it's way better to just mark the presence of the loop at each node 🧠
so we introduce the "unknown" hop count, U. this hop count value counts as larger than any other hop count value. a thread with hop count U is called a "U-thread" 🦄
A.12.1.
when an incoming thread with a known hop count stalls, and there's an outgoing thread, we assign hop count U to the outgoing thread, and we assign a new color to it too 🎨
so the next hop now has an incoming U-thread with the new color. that makes its outgoing thread get hop count U and the new color too. the rules we already gave then make every link in the loop get the new color and hop count U. when this thread either reaches its originator, or any other node that already has an incoming thread of the same color, it stalls 🛑
in our example above, this gives the links AB, BC, CD, and DA hop count U.
now let's add one more rule 💖
A.12.2.
when a thread with a known hop count reaches a node that has a colored outgoing U-thread, the incoming thread merges into the outgoing thread. (honestly this is just a consequence of a rule we already gave, since U is greater than any known hop count 🤓)
so if W, X, Y, or Z try to extend a thread to D, A, B, or C respectively, those threads stall right away. once all the links are marked as being within a loop, no other threads get extended around the loop. that means no other setup messages travel the loop 🙌
here's our example topology with the link hop counts that exist during a loop:
1 U 1
X--->A----->B<---Y
^ |
U | |U
| v
W--->D<-----C<---Z
1 U 1A.13. Some Special Rules for Hop Count U 🪩
when a U-thread runs into a thread with a known hop count, the usual rules apply, just remember that U is larger than any known hop count value 💅
but we need a couple of special rules for when a U-thread runs into another U-thread. since we can't tell which of the two U-threads is really the longer one, we have to make sure that each of the U-threads gets extended 😤
A.13.1.
if an incoming colored U-thread arrives at a node that already has an incoming U-thread of that color, or arrives at the node that created that U-thread, then the thread stalls 🧊
(once a loop is detected, there's no need to keep extending the thread 🙅♀️)
A.13.2.
if an incoming colored U-thread arrives at a node that has a transparent outgoing U-thread to its next hop, the incoming thread is extended 🚂
A.13.3.
if an incoming colored U-thread arrives at a node that has a colored outgoing U-thread, and the incoming link the thread was received on was already an incoming link of the LSP, the thread is extended 🛤️
A.13.4.
if an incoming colored U-thread arrives at a node that has a colored outgoing U-thread, and the incoming link the thread was received on was NOT already an incoming link of the LSP, a new U-thread is created and extended. all the incoming threads get merged into it. this is known in the main body of this document as "extending the thread with changing color" 🌈
these rules make sure an incoming U-thread is always extended (or merged into a new U-thread that then gets extended), unless it's already known to form a loop 🫶
so what's the point of rule A.13.4? 🤔 there are certain cases where a loop can form, but the node that created the looping thread isn't part of the loop. rule A.13.4 makes sure that when there's a loop, there's a looping thread that was created by some node actually in the loop. and that's what makes sure the loop gets detected well before the thread TTL runs out ⏰
the "extending the thread with changing color" rule also gets applied when extending a thread with a known hop count 💜
A.13.5.
when a received colored thread with a known hop count gets extended, if the node has an outgoing thread, and the incoming link the thread was received on was NOT already an incoming link of the LSP, a new thread is created and extended. all the incoming threads are merged into it. this is an exceptional case of A.5.1. 🎀
A.14. Recovering From a Loop ✨
Okay so here's our example topology again, but this time with the loop in it 🌀
1 U 1
X--->A----->B<---Y
^ |
U | |U
| v
W--->D<-----C<---Z
1 U 1Suppose now that C's next hop changes from D to some other node E, which breaks the loop 💅 For simplicity, we're going to assume that E is the egress node.
C will withdraw its outgoing U-thread from D (9.1). It will also create a new thread (12.1) and give it a new color. It assigns that thread hop count U, which is the largest hop count of C's incoming threads. Then it merges its two other incoming threads into the new thread (12.2) and extends the new thread to E. The result looks like this, bestie 🦋
1 U 1
X--->A----->B<---Y
^ |
U | |U
| v
W--->D C<---Z
1 | 1
U|
v
EWhen the thread from C to E rewinds, the merged threads also rewind (8.4). This rewinding can now keep going all the way back to the leafs 🌿 While all of this is happening, D will notice that its outgoing thread hop count should be 2, not U, and it will make that change (9.3). Then A notices that its outgoing hop count should be 3, not U, and it makes that change too. So at some point in the future, we might see this:
1 3 1
X--->A----->B<---Y
^ |
2 | |U
| v
W--->D C<---Z
1 | 1
U|
v
EAfter a short period, we see this:
1 3 1
X--->A----->B<---Y
^ |
2 | |4
| v
W--->D C<---Z
1 | 1
5|
v
EEvery thread is transparent now, and we have a fully set up non-looping path. Iconic 👑
A.15. Continuing to Use an Old Path 🧚
Nothing in the above requires any node to withdraw a transparent thread. Existing transparent threads (established paths) can keep being used, even while new paths are being set up. Main character energy, no notes 💜
If that happens, a node might have both a transparent outgoing thread (the previous path) and a colored outgoing thread (the new path being set up). This can only happen if the downstream links for the two threads are different 🤔 When the colored outgoing thread rewinds and becomes transparent, the previous path should be withdrawn. ✨
Full Copyright Statement
Copyright (C) The Internet Society (2001). All Rights Reserved.
This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.
The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Acknowledgement
Funding for the RFC Editor function is currently provided by the Internet Society. 🫶
📦 where this page comes from
- ietf: rfc3063 2001-02
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms