📄 rfc3063.txt
字号:
Ohba, et al. Experimental [Page 6]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
A special hop count value "unknown"(=0xff), which is larger than
any other known value, is used when a loop is found. Once the
thread hop count is "unknown", it is not increased any more as the
thread is extended.
Thread TTL
To avoid infinite looping of control messages in some cases, a
thread TTL is used. When a node creates a path control message
and sends it downstream, it sets a TTL to the message, and the TTL
is decremented at each hop. When the TTL reaches 0, the message
is not forwarded any more. Unlike the thread hop counts and the
thread colors, the thread TTLs do not needs to be stored in
incoming links.
3.2. Thread loop
When the same colored thread is received on multiple incoming links,
or the received thread color was assigned by the receiving node, it
is said that the thread forms a loop. A thread creator can tell
whether it assigned the received thread color by checking the IP
address part of the received thread color.
3.3. Primitive thread actions
Five primitive actions are defined in order to prevent LSP loops by
using threads: "extending", "rewinding", "withdrawing", "merging",
and "stalling". This section describes only each primitive action
and does not describe how these primitive actions are combined and
how the algorithm totally works. The main body of the algorithm is
described in section 4.
Thread Extending
When a node starts to send a path setup message to its next hop
with a set of thread attributes, it is said that "the node creates
a thread and extends it downstream". When a node receives a path
setup message from an upstream node with a set of thread
attributes and forwards it downstream, it is said that "the node
receives a thread and extends it downstream". The color and hop
count of the thread become the color and hop count of the outgoing
link. Whenever a thread is received on a particular link, the
color and hop count of that thread become the color and hop count
of that incoming link, replacing any color and hop count that the
link may have had previously.
Ohba, et al. Experimental [Page 7]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
For example, when an ingress node initiates a path setup, it
creates a thread and extends it downstream by sending a path setup
message. The thread hop count is set to be 1, and the thread
color is set to be the ingress node's address with an appropriate
event identifier, and the thread TTL is set to be its maximum
value.
When a node receives a thread and extends it downstream, the node
either (i) extends the thread without changing color, or (ii)
extend the thread with changing color. The received thread is
extended with changing color if it is received on a new incoming
link and extended on an already existing outgoing link, otherwise,
it is extended without changing color. When a thread is extended
with changing color, a new colored thread is created and extended.
Thread creation does not occur only at leaf nodes. If an
intermediate node has an incoming link, it will create and extend
a new thread whenever it acquires a new next hop.
When a node notifies a next hop node of a decrease of the link hop
count, if it is not extending a colored thread, a transparent
thread is extended.
Thread Merging
When a node which has a colored outgoing link receives a new
thread, it does not necessarily extend the new thread. It may
instead 'merge' the new threads into the existing outgoing thread.
In this case, no messages are sent downstream. Also, if a new
incoming thread is extended downstream, but there are already
other incoming threads, these other incoming threads are
considered to be merged into the new outgoing thread.
Specifically, a received thread is merged if all the following
conditions hold:
o A colored thread is received by node N, AND
o The thread does not form a loop, AND
o N is not an egress node, AND
o N's outgoing link is colored, AND
o N's outgoing link hop count is at least one greater than the
hop count of the newly received thread.
When an outgoing thread rewinds (see below), any incoming threads
which have been merged with it will rewind as well.
Ohba, et al. Experimental [Page 8]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
Thread Stalling
When a colored thread is received, if the thread forms a loop, the
received thread color and hop count are stored on the receiving
link without being extended. This is the special case of thread
merging applied only for threads forming a loop and referred to as
the "thread stalling", and the incoming link storing the stalled
thread is called "stalled incoming link". A distinction is made
between stalled incoming links and unstalled incoming links.
Thread Rewinding
When a thread reaches a node which satisfies a particular loop-
free condition, the node returns an acknowledgment message back to
the message initiator in the reverse path on which the thread was
extended. The transmission of the acknowledgment messages is the
"rewinding" of the thread.
The loop-free condition is:
o A colored thread is received by the egress node, OR
o All of the following conditions hold:
(a) A colored thread is received by node N, AND
(b) N's outgoing link is transparent, AND
(c) N's outgoing link hop count is at least one greater than
the hop count of the newly received thread.
When a node rewinds a thread which was received on a particular
link, it changes the color of that link to transparent.
If there is a link from node M to node N, and M has extended a
colored thread to N over that link, and M determines (by receiving
a message from N) that N has rewound that thread, then M sets the
color of its outgoing link to transparent. M then continues
rewinding the thread, and in addition, rewinds any other incoming
thread which had been merged with the thread being rewound,
including stalled threads.
Each node can start label switching after the thread colors in all
incoming and outgoing links becomes transparent.
Note that transparent threads are threads which have already been
rewound; hence there is no such thing as rewinding a transparent
thread.
Ohba, et al. Experimental [Page 9]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
Thread Withdrawing
It is possible for a node to tear down a path. A node tears down
the portion of the path downstream of itself by sending teardown
messages to its next hop. This process is known as the "thread
withdrawing".
For example, suppose a node is trying to set up a path, and then
experiences a next hop change or a next hop loss. It will
withdraw the thread that it had extended down its old next hop.
If node M has extended a thread to node N, and node M then
withdraws that thread, N now has one less incoming link than it
had before. If N now has no other unstalled incoming links and N
is not an eligible leaf node, it must withdraw its outgoing
thread. If N still has an unstalled incoming link or N is an
eligible leaf node, it may (or may not) need to change the hop
count of the outgoing link.
N needs to change the outgoing hop count if:
o The incoming link hop count that was just removed had a larger
hop count than any of the remaining incoming links, AND
o One of the following conditions holds:
(a) The outgoing link is transparent, OR
(b) The outgoing link has a known hop count.
If the outgoing link is transparent, it remains transparent, but
the new hop count needs to be sent downstream. If the outgoing
link is colored, a new thread (with a new color) needs to be
created and extended downstream.
3.4. Examples of primitive thread actions
The following notations are used to illustrate examples of primitive
actions defined for threads.
A pair of thread attributes stored in each link is represented by
"(C,H)", where C and H represent the thread color and thread hop
count, respectively.
A thread marked "+" indicates that it is created or received now. A
thread marked "-" indicates that it is withdrawn now.
A link labeled with squared brackets (e.g., "[a]") indicates that it
is an unstalled link. A link labeled with braces (e.g., "{a}")
indicates that it is a stalled link.
Ohba, et al. Experimental [Page 10]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
Fig. 2 shows an example in which a leaf node A creates a blue thread
and extends it downstream.
(bl,1)
A---[o1]--->
Fig.2 Thread extending at leaf node
Fig.3 shows an example of thread extending without changing color at
intermediate node. Assume that a node B has no incoming and outgoing
link before receiving a blue thread. When node B receives the blue
thread of hop count 1 on a new incoming link i1, it extends the
thread downstream without changing color (Fig.3(a)). After the blue
thread is extended, node B receives a red thread of hop count unknown
on incoming link i1 again (Fig.3(b)). The red thread is also
extended without changing its color, since both i1 and o1 already
exists.
(bl,1)+ (bl,2) (re,U)+ (re,U)
----[i1]--->B---[o1]----> ----[i1]--->B----[o1]--->
Fig.3(a) Fig.3(b)
Fig.3 Thread extending without changing color
Fig.4 shows an example of thread extending with changing color.
There are single incoming link i1 and single outgoing link o1 in
Fig.4(a). Then a red thread of hop count 3 is received on a new
incoming link i2. In this case, the received thread is extended with
changing color, i.e., a new green thread is created and extended
(Fig.4(b)), since o1 already exists.
(bl,1) (bl,2) (bl,1) (gr,4)
----[i1]--->B----[o1]---> ----[i1]--->B----[o1]--->
^
|
----[i2]----+
(re,3)+
Fig.4(a) Fig.4(b)
Fig.4 Thread extending with changing color
Fig.5 shows an example of thread merging. When a node B receives a
red thread of hop count 3, the received thread is not extended since
the outgoing link hop count is at least one greater than the received
thread hop count. Both the red and blue threads will be rewound when
the blue thread on outgoing link o1 is rewound.
Ohba, et al. Experimental [Page 11]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
(bl,3) (bl,4)
----[i1]--->B----[o1]--->
^
|
----[i2]----+
(re,3)+
Fig.5 Thread merging
Figs 6 and 7 show examples of thread stalling. When a node B
receives a blue thread of hop count 10 on incoming link i2 in Fig.6,
it "stalls" the received thread since the blue thread forms a loop.
In Fig.7, a leaf node A finds the loop of its own thread.
(bl,3) (bl,4)
----[i1]--->B----[o1]--->
^
|
----{i2}----+
(bl,10)+
Fig.6 Thread stalling (1)
(bl,10)+ (bl,1)
----{i1}--->A----[o1]--->
Fig.7 Thread stalling (2)
Fig.8 shows an example of thread rewinding. When the yellow thread
which is currently being extended is rewound (Fig.8(a)), the node
changes all the incoming and outgoing thread color to transparent,
and propagates thread rewinding to upstream nodes (Fig.8(b)).
(bl,1) (ye,2) (tr,1) (tr,2)
----[i2]--->B----[o1]---> ----[i2]--->B----[o1]--->
^ ^
| |
----[i3]----+ ----[i3]----+
(ye,1) (tr,1)
Fig.8(a) Fig.8(b)
Fig.8 Thread rewinding
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -