As per Relevance of the word incoming, we have this rfc below:
Network Working Group Y.
Request for Comments: 3063 Y.
Category: Experimental
E.
Cisco
P.
Ennovate
February 2001
MPLS Loop Prevention
Status of this
This memo defines an Experimental Protocol for the
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
Copyright (C) The Internet Society (2001). All Rights Reserved
This paper presents a simple mechanism, based on "threads", which
be used to prevent Multiprotocol Label Switching (MPLS) from
up label switched path (LSPs) which have loops. The mechanism
compatible with, but does not require, VC merge. The mechanism
be used with either the ordered downstream-on-demand allocation
ordered downstream allocation. The amount of information that
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,
distributed procedure is executed, but only nodes which
downstream of the change are involved
Ohba, et al. Experimental [Page 1]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
Table of
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.
This paper presents a simple mechanism, based on "threads", which
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
(Forwarding Equivalence Class) [1], it creates a thread and
it downstream. Each such thread is assigned a unique "color",
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
in the hop count from the furthest upstream node. The only
information that needs to be associated with a particular next
for a particular LSP is the thread color and hop count
If there is a loop, then some thread will arrive back at an
through which it has already passed. This is easily detected,
each thread has a unique color
Section 3 and 4 provide procedures for determining that there is
loop. When this is determined, the threads are "rewound" back to
point of creation. As they are rewound, labels get assigned.
labels are NOT assigned until loop freedom is guaranteed
While a thread is extended, the LSRs through which it passes
remember its color and hop count, but when the thread has
rewound, they need only remember its hop count
The thread mechanism works if some, all, or none of the LSRs in
LSP support VC-merge. It can also be used with either the
downstream on-demand label allocation or ordered
unsolicited label allocation [2,3]. The mechanism can also
applicable to loop detection, old path retention, and load-splitting
The state information which must be carried in protocol messages,
which must be maintained internally in state tables, is of
size, independent of the network size. Thus the thread mechanism
more scalable than alternatives which require that path-vectors
carried
To set up a new LSP after a routing change, the thread
requires communication only between nodes which are downstream of
point of change. There is no need to communicate with nodes that
upstream of the point of change. Thus the thread mechanism is
robust than alternatives which require that a diffusion
be performed (see section 9).
2. Basic
We will use the term LSP to refer to a multipoint-to-point
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
being set up in the network. This allows us to talk of
and outgoing links without constantly saying something like "
the same LSP
Incoming Link, Upstream
Outgoing Link, Downstream
At a given node, a given LSP will have one or more incoming,
upstream links, and one outgoing or downstream link. A "link"
really an abstract relationship with an "adjacent" LSR; it is
"edge" in the "tree", and not necessarily a particular
entity like an "interface".
Leaf Node, Ingress
A node which has no upstream links
Eligible Leaf
A node which is capable of being a leaf node. For example, a
is not an eligible leaf node if it is not allowed to
inject L3 packets created or received at the node into
outgoing link
Link Hop
Every link is labeled with a "link hop count". This is the
of hops between the given link and the leaf node which is
upstream of the given link. At any node, the link hop count
the downstream link is one more than the largest of the hop
associated with the upstream links
We define the quantity "Hmax" at a given node to be the maximum
all the incoming link hop counts. Note that, the link hop
of the downstream link is equal to Hmax+1. At a leaf node,
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
| |
|3 |1
| |
| 4 5 | 6 7
D---G---H---I---
|
|2
1 |
E---
Fig.1 Example of link hop
Next Hop
Node N thought that FEC F was unreachable, but now has a next
for it
Next Hop
Node N thought that node A was the next hop for FEC F, but now
longer has the next hop for FEC F. A node loses a next
whenever the next hop goes down
Next Hop
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
as a combination of a next hop loss event on the old next hop
a next hop acquisition event on the new next hop
3. Thread
A thread is a sequence of messages used to set up an LSP, in
"ordered downstream-on-demand" (ingress-initiated ordered control
style
3.1. Thread
There are three attributes related to threads. They may be
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
Every time a path control message is initiated by a node, the
assigns a unique "color" to it. This color is to be unique
both time and space: its encoding consists of an IP address of
node concatenated with a unique event identifier from a
space maintained by the node. The path setup messages that
node sends downstream will contain this color. Also, when
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
the incoming link. The thread which consists of messages of
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
event identifier from its initial value, and incrementing it
one (modulo its maximum value) each time a color is assigned.
this method, the initial event identifier is either selected
random or assigned to be larger than the largest event
used on the previous system incarnation
Thread Hop
In order to maintain link hop counts, we need to carry hop
in the path control messages. For instance, a leaf node
assign a hop count of 1 to its downstream link, and would
that value into a path setup message it sends downstream. When
path setup message is sent downstream, a node would assign a
count which is one more than the largest of the incoming link
counts, to its downstream link, and would store that value into
path setup message it sends downstream. Once the value is
in a path control message, we may refer to it has a "thread
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
any other known value, is used when a loop is found. Once
thread hop count is "unknown", it is not increased any more as
thread is extended
Thread
To avoid infinite looping of control messages in some cases,
thread TTL is used. When a node creates a path control
and sends it downstream, it sets a TTL to the message, and the
is decremented at each hop. When the TTL reaches 0, the
is not forwarded any more. Unlike the thread hop counts and
thread colors, the thread TTLs do not needs to be stored
incoming links
3.2. Thread
When the same colored thread is received on multiple incoming links
or the received thread color was assigned by the receiving node,
is said that the thread forms a loop. A thread creator can
whether it assigned the received thread color by checking the
address part of the received thread color
3.3. Primitive thread
Five primitive actions are defined in order to prevent LSP loops
using threads: "extending", "rewinding", "withdrawing", "merging",
and "stalling". This section describes only each primitive
and does not describe how these primitive actions are combined
how the algorithm totally works. The main body of the algorithm
described in section 4.
Thread
When a node starts to send a path setup message to its next
with a set of thread attributes, it is said that "the node
a thread and extends it downstream". When a node receives a
setup message from an upstream node with a set of
attributes and forwards it downstream, it is said that "the
receives a thread and extends it downstream". The color and
count of the thread become the color and hop count of the
link. Whenever a thread is received on a particular link,
color and hop count of that thread become the color and hop
of that incoming link, replacing any color and hop count that
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,
creates a thread and extends it downstream by sending a path
message. The thread hop count is set to be 1, and the
color is set to be the ingress node's address with an
event identifier, and the thread TTL is set to be its
value
When a node receives a thread and extends it downstream, the
either (i) extends the thread without changing color, or (ii
extend the thread with changing color. The received thread
extended with changing color if it is received on a new
link and extended on an already existing outgoing link, otherwise
it is extended without changing color. When a thread is
with changing color, a new colored thread is created and extended
Thread creation does not occur only at leaf nodes. If
intermediate node has an incoming link, it will create and
a new thread whenever it acquires a new next hop
When a node notifies a next hop node of a decrease of the link
count, if it is not extending a colored thread, a
thread is extended
Thread
When a node which has a colored outgoing link receives a
thread, it does not necessarily extend the new thread. It
instead 'merge' the new threads into the existing outgoing thread
In this case, no messages are sent downstream. Also, if a
incoming thread is extended downstream, but there are
other incoming threads, these other incoming threads
considered to be merged into the new outgoing thread
Specifically, a received thread is merged if all the
conditions hold
o A colored thread is received by node N,
o The thread does not form a loop,
o N is not an egress node,
o N's outgoing link is colored,
o N's outgoing link hop count is at least one greater than
hop count of the newly received thread
When an outgoing thread rewinds (see below), any incoming
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
When a colored thread is received, if the thread forms a loop,
received thread color and hop count are stored on the
link without being extended. This is the special case of
merging applied only for threads forming a loop and referred to
the "thread stalling", and the incoming link storing the
thread is called "stalled incoming link". A distinction is
between stalled incoming links and unstalled incoming links
Thread
When a thread reaches a node which satisfies a particular loop
free condition, the node returns an acknowledgment message back
the message initiator in the reverse path on which the thread
extended. The transmission of the acknowledgment messages is
"rewinding" of the thread
The loop-free condition is
o A colored thread is received by the egress node,
o All of the following conditions hold
(a) A colored thread is received by node N,
(b) N's outgoing link is transparent,
(c) N's outgoing link hop count is at least one greater
the hop count of the newly received thread
When a node rewinds a thread which was received on a
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
colored thread to N over that link, and M determines (by
a message from N) that N has rewound that thread, then M sets
color of its outgoing link to transparent. M then
rewinding the thread, and in addition, rewinds any other
thread which had been merged with the thread being rewound
including stalled threads
Each node can start label switching after the thread colors in
incoming and outgoing links becomes transparent
Note that transparent threads are threads which have already
rewound; hence there is no such thing as rewinding a
thread
Ohba, et al. Experimental [Page 9]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
Thread
It is possible for a node to tear down a path. A node tears
the portion of the path downstream of itself by sending
messages to its next hop. This process is known as the "
withdrawing".
For example, suppose a node is trying to set up a path, and
experiences a next hop change or a next hop loss. It
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
withdraws that thread, N now has one less incoming link than
had before. If N now has no other unstalled incoming links and
is not an eligible leaf node, it must withdraw its
thread. If N still has an unstalled incoming link or N is
eligible leaf node, it may (or may not) need to change the
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
hop count than any of the remaining incoming links,
o One of the following conditions holds
(a) The outgoing link is transparent,
(b) The outgoing link has a known hop count
If the outgoing link is transparent, it remains transparent,
the new hop count needs to be sent downstream. If the
link is colored, a new thread (with a new color) needs to
created and extended downstream
3.4. Examples of primitive thread
The following notations are used to illustrate examples of
actions defined for threads
A pair of thread attributes stored in each link is represented
"(C,H)", where C and H represent the thread color and thread
count, respectively
A thread marked "+" indicates that it is created or received now.
thread marked "-" indicates that it is withdrawn now
A link labeled with squared brackets (e.g., "[a]") indicates that
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
and extends it downstream
(bl,1)
A---[o1]--->
Fig.2 Thread extending at leaf
Fig.3 shows an example of thread extending without changing color
intermediate node. Assume that a node B has no incoming and
link before receiving a blue thread. When node B receives the
thread of hop count 1 on a new incoming link i1, it extends
thread downstream without changing color (Fig.3(a)). After the
thread is extended, node B receives a red thread of hop count
on incoming link i1 again (Fig.3(b)). The red thread is
extended without changing its color, since both i1 and o1
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
Fig.4 shows an example of thread extending with changing color
There are single incoming link i1 and single outgoing link o1
Fig.4(a). Then a red thread of hop count 3 is received on a
incoming link i2. In this case, the received thread is extended
changing color, i.e., a new green thread is created and
(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
Fig.5 shows an example of thread merging. When a node B receives
red thread of hop count 3, the received thread is not extended
the outgoing link hop count is at least one greater than the
thread hop count. Both the red and blue threads will be rewound
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
Figs 6 and 7 show examples of thread stalling. When a node
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
which is currently being extended is rewound (Fig.8(a)), the
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
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
thread on incoming link i2 is withdrawn. Then Hmax decreases from 3
to 1, and node B creates a new green thread and extends
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,
decreases from unknown to 1, however, no thread is extended as
in Fig.10(b), since the outgoing link has a colored thread and
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
case, a transparent thread is extended (Fig.11(b)), since
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
The ordered downstream-on-demand allocation is assumed here, however
the algorithm can be adapted to the ordered downstream allocation,
shown in section 5.
In the algorithm, a next hop change event will be separated into
events: a next hop loss event on the old next hop and a next
acquisition event on the new next hop, in this order
The following notations are defined
Hmax: the largest incoming link hop
Ni: the number of unstalled incoming
The thread algorithm is described as follows
When a node acquires a new next hop, it creates a colored thread
extends it downstream
When a node loses a next hop to which it has extended a thread,
may withdraw that thread. As described in section 3, this may or
not cause the next hop to take some action. Among the actions
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,
extended. A thread with TTL zero is never extended
When a received thread is stalled at a node, if Ni=0 and the node
not an eligible leaf node, initiate a thread withdrawing. Otherwise
if Ni>0 and the received thread hop count is not unknown, a
thread of hop count unknown is created and extended. If the
thread hop count is unknown, no thread is extended and no
action is taken
When a thread being extended is rewound, if the thread hop count
greater than one more than Hmax, a transparent thread of hop
(Hmax+1) is extended downstream
When a node that has an transparent outgoing link receives
transparent thread, if Hmax decreases the node extends it
without changing color
5. Applicability of the
The thread algorithm described in section 4 can be applied to
LSP management policies
Ohba, et al. Experimental [Page 14]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
5.1. LSP Loop prevention/
The same thread algorithm is applicable to both LSP loop
and detection
In loop prevention mode, a node transmits a label mapping (
a thread object) for a particular LSP only when it rewinds the
for that LSP. No mapping message is sent until the thread rewinds
On the other hand, if a node operates in loop detection mode,
returns a label mapping message without a thread object
after receiving a colored thread. A node which receives a
mapping message that does not have a thread object will not
the thread
5.2. Using old path while looping on new
When a route changes, one might want to continue to use the old
if the new route is looping. This is achieved simply by holding
label assigned to the downstream link on the old path until
thread being extended on the new route gets rewound. This is
implementation choice
5.3. How to deal with ordered downstream
The thread mechanism can be also adapted to ordered
allocation mode (or the egress-initiated ordered control)
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
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
leaf for a short period of time
5.4. How to realize load
A leaf node can easily perform load splitting by setting up
different LSPs for the same FEC. The downstream links for the
LSPs are simply assigned different colors. The thread algorithm
prevents a loop in either path, but also allows the two paths to
a common downstream node
If some intermediate node wants to do load splitting, the
modification is made. Assume that there are multiple next hops
the same FEC. If there are n next hops for a particular FEC, the
of incoming links for that FEC's LSP can be partitioned into
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
color for its outgoing link. The thread algorithm now prevents
loop in any of the paths, but also allows two or more of the paths
have a common downstream node
In this case, an interesting situation may happen. Let's say that
Fig.12, node B has two incoming links, i1 and i2, and two
links, o1 and o2, such that i1 is mapped to o1, while i2 is mapped
o2.
If a blue thread received on i1 and extended on o1 is again
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
thread extended on o2 is rewound, a single loop-free LSP
traverses node B twice is established
+------------------...--------------------+
. (bl,3) (bl,4) |
. ----[i1]---+ +--[o1]---> .... --+
. \ /
. v /
|
|
+-----------[i2]--->B----[o2]--->
(bl,10)+ (bl,11)
Fig.12 Load splitting at intermediate
There is another type of load splitting, in which packets arrived
single incoming link can be label switched to any one of
outgoing links. This case does not seem to be a good load-
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
that ATM-LSRs cannot load split like this because ATM switches
don't have the capability to make forwarding decisions on a per
packet basis
6. Why this
6.1. Why a thread with unknown hop count is
In the algorithm, a thread of unknown hop count is extended when
thread loop is detected. This reduces the number of loop
Ohba, et al. Experimental [Page 16]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
messages by merging threads (of known hop count) that are
inside or outside the loop. See Appendix A.12.
6.2. Why a rewound thread cannot contain a
6.2.1. Case1: LSP with known link hop
How can we be sure that an established path does not contain a
when the outgoing link hop count is NOT "unknown"?
Consider a sequence of LSRs , such that there is a
traversing the LSRs in the sequence. (I.e., packets from R1 go
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
be k+n-1. But the algorithm also ensures that if a node has
incoming hop count of j, its outgoing link hop count must be at
of j+1. Hence, if we assume that the LSP established as a result
thread rewinding contains a loop, the hop counts between R1 and R
must be at least k+n. From this we may derive the absurd
that n=0, and we may therefore conclude that there is no
sequence of LSRs
6.2.1. Case2: LSP with unknown link hop
An established path does not contain a loop as well, when
outgoing link hop count is "unknown". This is because a
thread of unknown hop count is never rewound unless it
egress
6.3. Why L3 loop is
Regardless of whether the thread hop count is known or unknown,
there is a loop, then some node in the loop will be the last node
receive a thread over a new incoming link. This thread will
arrive back at that node, without its color having changed.
the loop will always be detected by at least one of the nodes in
loop
6.4. Why L3 loop is not mis-
Since no node ever extends the same colored thread downstream twice
a thread loop is not detected unless there actually is an L3
loop
Ohba, et al. Experimental [Page 17]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
6.5. How a stalled thread automatically recovers from
Once a thread is stalled in a loop, the thread (or the path
request) effectively remains in the loop, so that a
reconfiguration (i.e., thread withdrawing on the old path and
extending on the new path) can be issued from any node that
receive a route change event so as to break the loop
6.6. Why different colored threads do not chase each
In the algorithm, multiple thread color and/or hop count updates
happen if several leaf nodes start extending threads at the
time. How can we prevent multiple threads from looping unlimitedly
First, when a node finds that a thread forms a loop, it creates a
thread of hop count "unknown". All the looping threads of a
hop count which later arrive at the node would be merged into
thread. Such a thread behaves like a thread absorber
Second, the "thread extending with changing color" prevents
threads from chasing each other
Suppose that a received thread were always extended without
color. Then we would encounter the following situation
G
| |
v
R1------>R
^ |
|
R4<------R
Fig.13 Example of thread
In Fig.13, (1) node G acquires R1 as a next hop, and starts to
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)
node G and node Y withdraws their threads before these threads
round
In this case, the yellow and green threads would go round and
back to R2 and R1, respectively. When the threads get back to R2
R1, however, the incoming links that store the yellow and
colors no longer exist. As a result, the yellow and green
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
R2, R2 extends the thread with changing color, i.e., creates a
red thread and extends it. Similarly, when a yellow thread
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
threads. This ensures that a thread is extended around the
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
extending and thread withdrawing with regard to the same thread
each other in a loop. This case would happen when a node withdraw
thread immediately after extending it into an L3 loop
A heuristics for self-chasing is to delay the execution of
withdrawing at an initiating node of the thread withdrawing. Anyway
the thread TTL mechanism can eliminate any kind of thread looping
7. Loop prevention
In this section, we show two examples to show how the algorithm
prevent LSP loops in given networks
We assume that the ordered downstream-on-demand allocation
employed, that all the LSPs are with regard to the same FEC, and
all nodes are VC-merge capable
7.1. First
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
node. Now leaf nodes R1 and R6 initiate creation of an LSP
R11 ------- R10 <-------------------- R
| | ^
| | |
| | |
v v |
R1 -------> R2 --------> R3 --------> R4 --------- R
[leaf] ^
|
|
|
R6 -------> R7 --------> R
[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
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
receiving the request originated from R6. When R3 receives the
request with red thread, R3 forwards it with (re,3,253)
changing thread color, since both the receiving incoming link and
outgoing link are newly created. Then R3 receives the second
with blue thread. In this time, the outgoing link is already exists
Thus, R3 performs thread extending with changing color, i.e.,
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
the red thread forms a loop, and stalls the red thread. Then, R
creates a purple thread of hop count unknown and extends
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
to R3.
On the other hand, the purple thread goes round without
color through existing links, and R2 finds the thread loop and
the purple thread. Since the received thread hop count is unknown
no thread is created any more. In this case no thread
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
(pu,U
R11 ------- R10 <-------------------- R
| | ^
| |(pu,U)* |
| | |(pu,U
v v |
R1 -------> R2 --------> R3 --------> R4 --------- R
[leaf] (re,1) (pu,U) ^ (pu,U
|
| (bl,3)
|
R6 -------> R7 --------> R
[leaf] (bl,1) (bl,2)
Fig.15 The network
Then R10 changes its next hop from R2 to R11.
Since R10 has a purple thread on the old downstream link, it
sends a path teardown message to the old next hop R2 for
the purple thread. Next, it creates a green thread of hop
unknown and sends a request with (gr,U,255) to R11.
When R2 receives the teardown message from R10, R2 removes
stalled incoming link between R10 and R2.
On the other hand, the green thread reaches R1 and Hmax is
from zero to unknown. In this case, R1 performs thread
with changing color since the thread is received on a new
link but extended on the already existing outgoing link. As
result, R1 creates an orange thread of hop count unknown and
it to R2.
The orange thread goes round through existing links without
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
(or,U) (or,U
R11 <------ R10 <-------------------- R
| | ^
|(or,U)* | |
| | |(or,U
v | |
R1 -------> R2 --------> R3 --------> R4 --------- R
[leaf] (or,U) (or,U) ^ (or,U
|
| (bl,3)
|
R6 -------> R7 --------> R
[leaf] (bl,1) (bl,2)
Fig.16 The network
Then R4 changes its next hop from R9 to R5.
Since R4 is extending an orange thread, it first sends a
message to the old next hop R9 to withdraw the orange thread on
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. R
returns a label mapping message. The thread rewinding procedure
performed at each node, as the label mapping message is
upstream hop-by-hop
If R1 receives a label mapping message before receiving the
thread's withdrawal from R11, R1 returns a label mapping message
R11. On receiving the orange thread's withdrawal, R1 will create
transparent thread and extend it by sending an update message
(tr,1,255) in order to notify downstream of the known hop count
Otherwise, if R1 receives the orange thread's withdrawal
receiving a label mapping message, R1 removes the stalled
orange link and waits for rewinding of the outgoing orange thread
Finally, when R1 receives a label mapping message from R2, it
a transparent thread (tr,1,255) and extend it downstream
In both cases, a merged LSP ((R1->R2),(R6->R7->R8))->R3->R4->R5)
established and every node obtains the correct link hop count.
final network state is shown in Fig.17.
Ohba, et al. Experimental [Page 22]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
R11 <------ R10 <-------------------- R
| | |
| | |
| | |
v | |
R1 -------> R2 --------> R3 --------> R4 --------> R
[leaf] (tr,1) (tr,2) ^ (tr,4) (tr,5)
|
| (tr,3)
|
R6 -------> R7 --------> R
[leaf] (tr,1) (tr,2)
Fig.17 The final network
7.2. Second
+----- R6----> R7-----+
| |
|
R1---->R2 R4----->R
| ^
| |
+--------->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
request to R6 with a red thread (re,2,255). When the request
(re,4,253) reaches R4, it extends the thread to R5 with
color. Thus, a new green thread is created at R4 and extended to R
by sending an update message with (gr,5,255).
When R5 receives the update, it updates the incoming link hop
to 5 and returns an ack (or a notification message with a
code) for the update. When R4 receives the ack for the update,
returns a label mapping message to R7.
When R2 receives the label mapping message on the new route, it
a teardown message to R3. When R4 receives the teardown message,
does not sends an update to R5 since Hmax does not change. Now
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
the request with (bl,3,254) to R4.
When R4 receives the request, it immediately returns a label
message to R3 since Hmax does not change
When R2 receives the label mapping message on the new route, it
a teardown message to R6. The teardown message reaches R4,
triggering an update message with a transparent thread (tr,4,255)
R5, since Hmax decreases from 4 to 3. R5 updates the incoming
hop count to 4 without returning an ack
8. Thread control
A thread control block (TCB) is maintained per LSP at each node
may contain the following information
-
-
- Incoming
Each incoming link has the following attributes
o neighbor: upstream neighbor node
o color: received thread
o hop count: received thread hop
o
o S-flag: indicates a stalled
- Outgoing
Each outgoing link has the following attributes
o neighbor: downstream neighbor node
o color: received thread
o hop count: received thread hop
o
o C-flag: indicates the link to the current next
If a transparent thread is received on an incoming link for which
label is assigned yet or a non-transparent color is stored,
the thread without entering the FSM. An error message may
returned to the sender
Whenever a thread is received on an incoming link, the
actions are taken before entering the FSM: (1) Store the
thread color and hop count on the link, replacing the old
color and hop count, and (2) set the following flags that are
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
receiving link, which stores the same thread color as the
one. The TCB to which link L belongs is referred to as
"detecting TCB". If the receiving LSR is VC-merge capable,
detecting TCB and the receiving TCB is the same, otherwise, the
TCBs are different
Before performing a thread extending, the thread TTL is
by one. If the resulting TTL becomes zero, the thread is
extended but silently discarded. Otherwise, the thread is
and the extended thread hop count and color are stored into
outgoing link
When a node receives a thread rewinding event, if the received
color and the extending thread color are different, it discards
event without entering the FSM
8.1. Finite state
An event which is "scheduled" by an action in an FSM must be
immediately after the completion of the action
The following variables are used in the FSM
o Ni: number of unstalled incoming
o Hmax: largest incoming hop
o Hout: hop count of the outgoing link for the current next
o Hrec: hop count of the received
In the FSM, if Hmax=unknown, the value for (Hmax+1) becomes the
reserved for unknown hop count plus 1. For example,
Hmax=unknown=255, the value (Hmax+1) becomes 256.
A TCB has three states; Null, Colored, and Transparent. When a
is in state Null, there is no outgoing link and Ni=0. The
Colored means that the node is extending a colored thread on
outgoing link for the current next hop. The state Transparent
that the node is the egress node or the outgoing link is transparent
The flag value "1" represents the flag is set, "0" represents
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
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
hop
State Null
Event Action New
Recv
CL LP
0 * * Do nothing. No
1 0 * If the node is egress, start thread rewinding
and change the color of the receiving link
transparent
Otherwise, extend the received thread without
changing color
1 1 * Stall the received thread; if Hrec
schedule "Reset to unknown" event for
detecting TCB
Next hop If eligible-leaf, create a colored thread and
acquisition extend it
Others Silently ignore the event. No
State Colored
Event Action New
Recv
CL LP
0 * * If Hmax+1
thread and extend it. Otherwise, do nothing
1 0 * If Hmaxreceived thread. No
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,
initiate thread withdrawing
If Ni>0 and Hrecschedule "Reset to No
unknown" event for the detecting TCB
Otherwise, do nothing. No
Ohba, et al. Experimental [Page 26]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
Rewound Propagate thread rewinding to previous hops
that are extending a colored thread;
the colors stored in all incoming and
links to transparent; if Hmax+1
transparent thread. Withdraw the thread
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,
propagate thread withdrawing to all next hops
Otherwise, if Hmax+1
a colored thread and extend it
Otherwise, do nothing. No
Next hop If there is already an outgoing link for the
acquisition next hop, do nothing. (This case happens
when the node retains the old path.)
Otherwise, create a colored thread and extend No
it
Next hop If the outgoing link is transparent and the No
loss node is allowed to retain the link and
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,
"Rewound" event for this TCB
If Ni=0, move to Null.
Otherwise, do nothing. No
Reset to Create a colored thread of hop count unknown No
unknown and extend it
Others Silently ignore the event. No
State Transparent
Event Action New
Recv
CL LP
0 * * If Hmax+1transparent thread. No
1 0 * If the node is egress or if Hmax
the color of the receiving link to
and start thread rewinding
Otherwise, extend the thread with (if NL=1)
or without (if NL=0) changing color
Ohba, et al. Experimental [Page 27]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
Withdrawn Remove the corresponding incoming link
If Ni=0 and the node is not an eligible leaf,
propagate thread withdrawing to next hops
Otherwise, if Hmax+1
a transparent thread and extend it
Otherwise, do nothing. No
Next hop Create a colored thread and extend it.
Next hop If the node is allowed to retain the outgoing No
loss link and the next hop is alive, do nothing
Otherwise, take the following actions
Initiate thread withdrawing
If Ni=0, move to Null.
Otherwise, do nothing. No
Others Silently ignore the event. No
9. Comparison with path-vector/diffusion
o Whereas the size of the path-vector increases with the length
the LSP, the sizes of the threads are constant. Thus the
of messages used by the thread algorithm are unaffected by
network size or topology. In addition, the thread
capability reduces the number of outstanding messages.
lead to improved scalability
o In the thread algorithm, a node which is changing its next
for a particular LSP must interact only with nodes that
between it and the LSP egress on the new path. In
path-vector algorithm, however, it is necessary for the node
initiate a diffusion computation that involves nodes which
not lie between it and the LSP egress
This characteristic makes the thread algorithm more robust.
a diffusion computation is used, misbehaving nodes which aren'
even in the path can delay the path setup. In the
algorithm, the only nodes which can delay the path setup
those nodes which are actually in the path
o The thread algorithm is well suited for use with both
ordered downstream-on-demand allocation and ordered
allocation. The path-vector/diffusion algorithm, however,
tightly coupled with the ordered downstream allocation
Ohba, et al. Experimental [Page 28]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
o The thread algorithm is retry-free, achieving quick
(re)configuration. The diffusion algorithm tends to delay
path reconfiguration time, since a node at the route
point must to consult all its upstream nodes
o In the thread algorithm, the node can continue to use the
path if there is an L3 loop on the new path, as in
path-vector algorithm
10. Security
The use of the procedures specified in this document does not
any security impact other than that which may generally be
in the use of any MPLS procedures
11. Intellectual Property
Toshiba and/or Cisco may seek patent or other intellectual
protection for some of the technologies disclosed in this document
If any standards arising from this document are or become
by one or more patents assigned to Toshiba and/or Cisco,
and/or Cisco intend to disclose those patents and license them
reasonable and non-discriminatory terms
12.
We would like to thank Hiroshi Esaki, Bob Thomas, Eric Gray,
Joel Halpern for their comments
Ohba, et al. Experimental [Page 29]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
13. Authors'
Yoshihiro
Toshiba
1, Komukai-Toshiba-cho, Saiwai-
Kawasaki 210-8582,
EMail: yoshihiro.ohba@toshiba.co.
Yasuhiro
Toshiba
1, Toshiba-cho, Fuchu-shi
Tokyo, 183-8511,
EMail: yasuhiro.katsube@toshiba.co.
Eric
Cisco Systems, Inc
250 Apollo
Chelmsford, MA, 01824
EMail: erosen@cisco.
Paul
Ennovate
330 Codman Hill
Marlborough MA 01719
EMail: pdoolan@ennovatenetworks.
14.
[1] Callon, R., et al., "A Framework for Multiprotocol
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
Progress
[4] Andersson, L., Doolan, P., Feldman, N., Fredette, A. and B
Thomas, "LDP Specification", RFC 3036, January 2001.
Ohba, et al. Experimental [Page 30]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
Appendix A - Further discussion of the
The purpose of this appendix is to give a more informal and
presentation of the algorithm, and to provide some of the
for it. For the precise specification of the algorithm, the
should be taken as authoritative
As in the body of the document, we speak as if there is only one LSP
otherwise we would always be saying "... of the same LSP". We
consider only the case where the algorithm is used for
prevention, rather than loop detection
A.1. Loop Prevention the Brute Force
As a starting point, let's consider an algorithm which we might
"loop prevention by brute force". In this algorithm, every
setup attempt must go all the way to the egress and back in order
the path to be setup. This algorithm is obviously loop-free,
virtue of the fact that the setup messages actually made it to
egress and back
Consider, for example, an existing LSP B-C-D-E to egress node E.
node A attempts to join the LSP. In this algorithm, A must send
message to B, B to C, C to D, D to E. Then messages are sent from
back to A. The final message, from B to A, contains a label binding
and A can now join the LSP, knowing that the path is loop-free
Using our terminology, we say that A created a thread and extended
downstream. The thread reached the egress, and then rewound
We needn't assume, in the above example, that A is an ingress node
It can be any node which acquires or changes its next hop for the
in question, and there may be nodes upstream of it which are
trying to join the LSP
It is clear that if there is a loop, the thread never reaches
egress, so it does not rewind. What does happen? The path
messages just keep traveling around the loop. If one keeps a
count in them, one can ensure that they stop traveling around
loop when the hop count reaches a certain maximum value. That is
when one receives a path setup message with that the maximum
count value, one doesn't send a path setup message downstream
How does one recover from this situation of a looping thread?
order for L3 routing to break the loop, some node in the loop
experience a next hop change. This node will withdraw the
Ohba, et al. Experimental [Page 31]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
from its old next hop, and extend a thread down its new next hop.
there is no longer a loop, this thread now reaches the egress,
gets rewound
A.2. What's Wrong with the Brute Force Method
Consider this example
|
B--D--
|
If A and C both attempt to join the established B-D-E path, then
and D must keep state for both path setup attempts, the one from
and the one from C. That is, D must keep track of two threads,
A-thread and the C-thread. In general, there may be many more
upstream of B who are attempting to join the established path, and
would need to keep track of them all
If VC merge is not being used, this isn't actually so bad.
VC merge, D really must support one LSP for each upstream
anyway. If VC merge is being used, however, supporting an
requires only that one keep state for each upstream link. It
be advantageous if the loop prevention technique also required
the amount of state kept by a node be proportional to the number
upstream links which thenode has, rather than to the number of
which are upstream in the LSP
Another problem is that if there is a loop, the setup messages
looping. Even though a thread has traversed some node twice,
node has no way to tell that a setup message it is
receiving is part of the same thread as some setup message
received in the past
Can we modify this brute force scheme to eliminate these
problems? We can. To show how to do this, we introduce two notions
thread hop count, and thread color
A.3. Thread Hop
Suppose every link in an LSP tree is labeled with the number of
you would traverse if you were to travel backwards (upstream)
that link to the leaf node which is furthest upstream of the link
For example, the following tree would have its links labeled
follows
Ohba, et al. Experimental [Page 32]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
1 2
A---B---C
| |
|3 |1
| |
| 4 5 | 6 7
D---G---H---I---
|
|2
1 |
E---
Call these the "link hop counts".
Links AB, EF, KH are labeled one, because you can go only one
upstream from these links. Links BC, and FD are labeled 2,
you can go 2 hops upstream from these links. Link DG is labeled 4,
because it is possible to travel 4 hops upstream from this link, etc
Note that at any node, the hop count associated with the
link is one more than the largest of the hop counts associated
the upstream links
Let's look at a way to maintain these hop counts
In order to maintain the link hop counts, we need to carry hop
in the path setup messages. For instance, a node which has
upstream links would assign a hop count of 1 to its downstream link
and would store that value into the path setup messages it
downstream. Once the value is stored in a path setup message, we
refer to it has a "thread hop count".
When a path setup message is received, the thread hop count is
as the link hop count of the upstream link over which the message
received
When a path setup message is sent downstream, the downstream link'
hop count (and the thread hop count) is set to be one more than
largest of the incoming link hop counts
Suppose a node N has some incoming links and an outgoing link,
hop counts all set properly, and N now acquires a new incoming link
If, and only if, the link hop count of the new incoming link
greater than that of all of the existing incoming links,
downstream link hop count must be changed. In this case,
messages must be sent downstream carrying the new, larger thread
count
Ohba, et al. Experimental [Page 33]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
If, on the other hand, N acquires a new incoming link with a link
count that is less than or equal to the link hop count of
existing incoming links, the downstream link hop count
unchanged, and no messages need be sent downstream
Suppose N loses the incoming link whose hop count was the largest
any of the incoming links. In this case, the downstream link
count must be made smaller, and messages need to be sent
to indicate this
Suppose we were not concerned with loop prevention, but only with
maintenance of the hop counts. Then we would adopt the
rules to be used by merge points
A.3.1 When a new incoming thread is received, extend it downstream
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
Nodes create new threads as a result of next hop changes or next
acquisitions. Let's suppose that every time a thread is created by
node, the node assigns a unique "color" to it. This color is to
unique in both time and space: its encoding consists of an IP
of the node concatenated with a unique event identifier from
numbering space maintained by the node. The path setup messages
the node sends downstream will contain this color. Also, when
node sends such a message downstream, it will remember the color,
this color becomes the color of the downstream link
When a colored message is received, its color becomes the color
the incoming link. The thread which consists of messages of
certain color will be known as a thread of that color
When a thread is rewound (and a path set up), the color is removed
The links become transparent, and we will sometimes speak of
established LSP as being a "transparent thread".
Note that packets cannot be forwarded on a colored link, but only
a transparent link
Note that if a thread loops, some node will see a message, over
particular incoming link, with a color that the node has already
before. Either the node will have originated the thread of
color, or it will have a different incoming link which already
Ohba, et al. Experimental [Page 34]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
that color. This fact can be used to prevent control messages
looping. However, the node would be required to remember the
of all the threads passing through it which have not been rewound
withdrawn. (I.e., it would have to remember a color for each
setup in progress.)
A.5. The Relation between Color and Hop
By combining the color mechanism and the hop count mechanism, we
prevent loops without requiring any node to remember more than
color and one hop count per link for each LSP
We have already stated that in order to maintain the hop counts,
node needs to extend only the thread which has the largest hop
of any incoming thread. Now we add the following rule
A.5.1 When extending an incoming thread downstream, that thread'
color is also passed downstream (I.e., the downstream link's
will be the same as the color of the upstream link with largest <