draft-ietf-mpls-loop-prevention-03.txt   rfc3063.txt 
Network Working Group Yoshihiro Ohba Network Working Group Y. Ohba
Internet-Draft Yasuhiro Katsube Request for Comments: 3063 Y. Katsube
Expiration Date: October 2000 Toshiba Category: Experimental Toshiba
E. Rosen
Eric Rosen
Cisco Systems Cisco Systems
P. Doolan
Paul Doolan
Ennovate Networks Ennovate Networks
February 2001
April 2000 MPLS Loop Prevention Mechanism
MPLS Loop Prevention Mechanism
<draft-ietf-mpls-loop-prevention-03.txt>
Status of this Memo Status of this Memo
This document is an Internet-Draft and is in full conformance with This memo defines an Experimental Protocol for the Internet
all provisions of Section 10 of RFC2026. community. It does not specify an Internet standard of any kind.
Discussion and suggestions for improvement are requested.
Internet-Drafts are working documents of the Internet Engineering Distribution of this memo is unlimited.
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other documents
at any time. It is inappropriate to use Internet-Drafts as
reference material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at Copyright Notice
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at Copyright (C) The Internet Society (2001). All Rights Reserved.
http://www.ietf.org/shadow.html.
Abstract Abstract
This paper presents a simple mechanism, based on "threads", which This paper presents a simple mechanism, based on "threads", which can
can be used to prevent MPLS from setting up label switched path be used to prevent Multiprotocol Label Switching (MPLS) from setting
(LSPs) which have loops. The mechanism is compatible with, but does up label switched path (LSPs) which have loops. The mechanism is
not require, VC merge. The mechanism can be used with either the compatible with, but does not require, VC merge. The mechanism can
ordered downstream-on-demand allocation or ordered downstream be used with either the ordered downstream-on-demand allocation or
allocation. The amount of information that must be passed in a ordered downstream allocation. The amount of information that must
protocol message is tightly bounded (i.e., no path-vector is used). be passed in a protocol message is tightly bounded (i.e., no path-
When a node needs to change its next hop, a distributed procedure is vector is used). When a node needs to change its next hop, a
executed, but only nodes which are downstream of the change are distributed procedure is executed, but only nodes which are
involved. downstream of the change are involved.
Table of contents Table of Contents
1 Introduction .......................................... 3 1 Introduction .......................................... 2
2 Basic definitions ..................................... 4 2 Basic definitions ..................................... 3
3 Thread basics ......................................... 5 3 Thread basics ......................................... 5
3.1 Thread attributes ..................................... 5 3.1 Thread attributes ..................................... 5
3.2 Thread loop ........................................... 6 3.2 Thread loop ........................................... 7
3.3 Primitive thread actions .............................. 7 3.3 Primitive thread actions .............................. 7
3.4 Examples of primitive thread actions ................. 9 3.4 Examples of primitive thread actions ................. 10
4 Thread algorithm ...................................... 13 4 Thread algorithm ...................................... 14
5 Applicability of the algorithm ........................ 14 5 Applicability of the algorithm ........................ 14
5.1 LSP Loop prevention/detection ......................... 14 5.1 LSP Loop prevention/detection ......................... 15
5.2 Using old path while looping on new path .............. 14 5.2 Using old path while looping on new path .............. 15
5.3 How to deal with ordered downstream allocation ........ 14 5.3 How to deal with ordered downstream allocation ........ 15
5.4 How to realize load splitting ......................... 14 5.4 How to realize load splitting ......................... 15
6 Why this works ........................................ 16 6 Why this works ........................................ 16
6.1 Why a thread with unknown hop count is extended ....... 16 6.1 Why a thread with unknown hop count is extended ....... 16
6.2 Why a rewound thread cannot contain a loop ............ 16 6.2 Why a rewound thread cannot contain a loop ............ 17
6.2.1 Case1: LSP with known link hop counts ................. 16 6.2.1 Case1: LSP with known link hop counts ................. 17
6.2.1 Case2: LSP with unknown link hop counts ............... 16 6.2.1 Case2: LSP with unknown link hop counts ............... 17
6.3 Why L3 loop is detected ............................... 16 6.3 Why L3 loop is detected ............................... 17
6.4 Why L3 loop is not mis-detected ....................... 16 6.4 Why L3 loop is not mis-detected ....................... 17
6.5 How a stalled thread automatically recovers from loop . 17 6.5 How a stalled thread automatically recovers from loop . 18
6.6 Why different colored threads do not chase each other . 17 6.6 Why different colored threads do not chase each other . 18
7 Loop prevention examples .............................. 18 7 Loop prevention examples .............................. 19
7.1 First example ......................................... 18 7.1 First example ......................................... 19
7.2 Second example ........................................ 22 7.2 Second example ........................................ 23
8 Thread control block .................................. 23 8 Thread control block .................................. 24
8.1 Finite state machine .................................. 24 8.1 Finite state machine .................................. 25
9 Comparison with path-vector/diffusion method .......... 27 9 Comparison with path-vector/diffusion method .......... 28
10 Security considerations ............................... 27 10 Security Considerations ............................... 29
11 Intellectual property considerations .................. 27 11 Intellectual Property Considerations .................. 29
12 Acknowledgments ....................................... 28 12 Acknowledgments ....................................... 29
13 Authors' Addresses .................................... 28 13 Authors' Addresses .................................... 30
14 References ............................................ 28 14 References ............................................ 30
Appendix A Further discussion of the algorithm ............. 29 Appendix A Further discussion of the algorithm ............. 31
Full Copyright Statement ..................................... 44
1. Introduction 1. Introduction
This paper presents a simple mechanism, based on "threads", which This paper presents a simple mechanism, based on "threads", which can
can be used to prevent MPLS from setting up label switched paths be used to prevent MPLS from setting up label switched paths (LSPs)
(LSPs) which have loops. which have loops.
When an LSR finds that it has a new next hop for a particular FEC 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 (Forwarding Equivalence Class) [1], it creates a thread and extends
it downstream. Each such thread is assigned a unique "color", such it downstream. Each such thread is assigned a unique "color", such
that no two threads in the network can have the same color. that no two threads in the network can have the same color.
For a given LSP, once a thread is extended to a particular next hop, 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 no other thread is extended to that next hop unless there is a change
change in the hop count from the furthest upstream node. The only in the hop count from the furthest upstream node. The only state
state information that needs to be associated with a particular next information that needs to be associated with a particular next hop
hop for a particular LSP is the thread color and hop count. for a particular LSP is the thread color and hop count.
If there is a loop, then some thread will arrive back at an LSR If there is a loop, then some thread will arrive back at an LSR
through which it has already passed. This is easily detected, since through which it has already passed. This is easily detected, since
each thread has a unique color. each thread has a unique color.
Section 3 and 4 provide procedures for determining that there is no Section 3 and 4 provide procedures for determining that there is no
loop. When this is determined, the threads are "rewound" back to loop. When this is determined, the threads are "rewound" back to the
the point of creation. As they are rewound, labels get assigned. point of creation. As they are rewound, labels get assigned. Thus
Thus labels are NOT assigned until loop freedom is guaranteed. labels are NOT assigned until loop freedom is guaranteed.
While a thread is extended, the LSRs through which it passes must While a thread is extended, the LSRs through which it passes must
remember its color and hop count, but when the thread has been remember its color and hop count, but when the thread has been
rewound, they need only remember its hop count. rewound, they need only remember its hop count.
The thread mechanism works if some, all, or none of the LSRs in the The thread mechanism works if some, all, or none of the LSRs in the
LSP support VC-merge. It can also be used with either the ordered LSP support VC-merge. It can also be used with either the ordered
downstream on-demand label allocation or ordered downstream downstream on-demand label allocation or ordered downstream
unsolicited label allocation [2,3]. The mechanism can also be unsolicited label allocation [2,3]. The mechanism can also be
applicable to loop detection, old path retention, and applicable to loop detection, old path retention, and load-splitting.
load-splitting.
The state information which must be carried in protocol messages, The state information which must be carried in protocol messages, and
and which must be maintained internally in state tables, is of fixed which must be maintained internally in state tables, is of fixed
size, independent of the network size. Thus the thread mechanism is size, independent of the network size. Thus the thread mechanism is
more scalable than alternatives which require that path-vectors be more scalable than alternatives which require that path-vectors be
carried. carried.
To set up a new LSP after a routing change, the thread mechanism To set up a new LSP after a routing change, the thread mechanism
requires communication only between nodes which are downstream of requires communication only between nodes which are downstream of the
the point of change. There is no need to communicate with nodes point of change. There is no need to communicate with nodes that are
that are upstream of the point of change. Thus the thread mechanism upstream of the point of change. Thus the thread mechanism is more
is more robust than alternatives which require that a diffusion robust than alternatives which require that a diffusion computation
computation be performed (see section 9). be performed (see section 9).
2. Basic definitions 2. Basic definitions
LSP LSP
We will use the term LSP to refer to a multipoint-to-point tree We will use the term LSP to refer to a multipoint-to-point tree
whose root is the egress node. See section 3.5 of [3]. whose root is the egress node. See section 3.5 of [3].
In the following, we speak as if there were only a single LSP being In the following, we speak as if there were only a single LSP
set up in the network. This allows us to talk of incoming and being set up in the network. This allows us to talk of incoming
outgoing links without constantly saying something like "for the and outgoing links without constantly saying something like "for
same LSP. the same LSP.
Incoming Link, Upstream Link Incoming Link, Upstream Link
Outgoing Link, Downstream Link Outgoing Link, Downstream Link
At a given node, a given LSP will have one or more incoming, or At a given node, a given LSP will have one or more incoming, or
upstream links, and one outgoing or downstream link. A "link" is upstream links, and one outgoing or downstream link. A "link" is
really an abstract relationship with an "adjacent" LSR; it is an really an abstract relationship with an "adjacent" LSR; it is an
"edge" in the "tree", and not necessarily a particular concrete "edge" in the "tree", and not necessarily a particular concrete
entity like an "interface". entity like an "interface".
Leaf Node, Ingress Node Leaf Node, Ingress Node
A node which has no upstream links. A node which has no upstream links.
Eligible Leaf Node Eligible Leaf Node
A node which is capable of being a leaf node. For example, a node A node which is capable of being a leaf node. For example, a node
is not an eligible leaf node if it is not allowed to directly inject L3 is not an eligible leaf node if it is not allowed to directly
packets created or received at the node into its outgoing link. inject L3 packets created or received at the node into its
outgoing link.
Link Hop Count Link Hop Count
Every link is labeled with a "link hop count". This is the number Every link is labeled with a "link hop count". This is the number
of hops between the given link and the leaf node which is furthest of hops between the given link and the leaf node which is furthest
upstream of the given link. At any node, the link hop count for upstream of the given link. At any node, the link hop count for
the downstream link is one more than the largest of the hop counts the downstream link is one more than the largest of the hop counts
associated with the upstream links. associated with the upstream links.
We define the quantity "Hmax" at a given node to be the maximum of 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 all the incoming link hop counts. Note that, the link hop count
the downstream link is equal to Hmax+1. At a leaf node, Hmax is of the downstream link is equal to Hmax+1. At a leaf node, Hmax
set to be zero. is set to be zero.
An an example of link hop counts is shown in Fig.1. An an example of link hop counts is shown in Fig.1.
1 2 1 2
A---B---C K A---B---C K
| | | |
|3 |1 |3 |1
| | | |
| 4 5 | 6 7 | 4 5 | 6 7
D---G---H---I---J D---G---H---I---J
| |
|2 |2
1 | 1 |
E---F E---F
Fig.1 Example of link hop counts Fig.1 Example of link hop counts
Next Hop Acquisition Next Hop Acquisition
Node N thought that FEC F was unreachable, but now has a next hop Node N thought that FEC F was unreachable, but now has a next hop
for it. for it.
Next Hop Loss Next Hop Loss
Node N thought that node A was the next hop for FEC F, but now no Node N thought that node A was the next hop for FEC F, but now no
longer has the next hop for FEC F. A node loses a next hop whenever longer has the next hop for FEC F. A node loses a next hop
the next hop goes down. whenever the next hop goes down.
Next Hop Change Next Hop Change
At node N, the next hop for FEC F changes from node A to node B, At node N, the next hop for FEC F changes from node A to node B,
where A is different than B. A next hop change event can be seen as where A is different than B. A next hop change event can be seen
a combination of a next hop loss event on the old next hop and a as a combination of a next hop loss event on the old next hop and
next hop acquisition event on the new next hop. a next hop acquisition event on the new next hop.
3. Thread basics 3. Thread basics
A thread is a sequence of messages used to set up an LSP, in the A thread is a sequence of messages used to set up an LSP, in the
"ordered downstream-on-demand" (ingress-initiated ordered control) "ordered downstream-on-demand" (ingress-initiated ordered control)
style. style.
3.1. Thread attributes 3.1. Thread attributes
There are three attributes related to threads. They may be encoded There are three attributes related to threads. They may be encoded
into a single thread object as: into a single thread object as:
1 2 3
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 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 + + Color +
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Hop Count | TTL | Reserved | | Hop Count | TTL | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Thread Color Thread Color
Every time a path control message is initiated by a node, the node Every time a path control message is initiated by a node, the node
assigns a unique "color" to it. This color is to be unique in both assigns a unique "color" to it. This color is to be unique in
time and space: its encoding consists of an IP address of the node both time and space: its encoding consists of an IP address of the
concatenated with a unique event identifier from a numbering space node concatenated with a unique event identifier from a numbering
maintained by the node. The path setup messages that the node sends space maintained by the node. The path setup messages that the
downstream will contain this color. Also, when the node sends such node sends downstream will contain this color. Also, when the
a message downstream, it will remember the color, and this color node sends such a message downstream, it will remember the color,
becomes the color of the downstream link. and this color becomes the color of the downstream link.
When a colored message is received, its color becomes the color of When a colored message is received, its color becomes the color of
the incoming link. The thread which consists of messages of a the incoming link. The thread which consists of messages of a
certain color will be known as a thread of that color. certain color will be known as a thread of that color.
A special color value "transparent"(=all 0's) is reserved. special color value "transparent"(=all 0's) is reserved.
One possible method for unique color assignment is, starting the One possible method for unique color assignment is, starting the
event identifier from its initial value, and incrementing it by one event identifier from its initial value, and incrementing it by
(modulo its maximum value) each time a color is assigned. In this one (modulo its maximum value) each time a color is assigned. In
method, the initial event identifier is either selected at random or this method, the initial event identifier is either selected at
assigned to be larger than the largest event identifier used on the random or assigned to be larger than the largest event identifier
previous system incarnation. used on the previous system incarnation.
Thread Hop Count Thread Hop Count
In order to maintain link hop counts, we need to carry hop counts in In order to maintain link hop counts, we need to carry hop counts
the path control messages. For instance, a leaf node would assign a in the path control messages. For instance, a leaf node would
hop count of 1 to its downstream link, and would store that value assign a hop count of 1 to its downstream link, and would store
into a path setup message it sends downstream. When a path setup that value into a path setup message it sends downstream. When a
message is sent downstream, a node would assign a hop count which is path setup message is sent downstream, a node would assign a hop
one more than the largest of the incoming link hop counts, to its count which is one more than the largest of the incoming link hop
downstream link, and would store that value into a path setup counts, to its downstream link, and would store that value into a
message it sends downstream. Once the value is stored in a path path setup message it sends downstream. Once the value is stored
control message, we may refer to it has a "thread hop count". in a path control message, we may refer to it has a "thread hop
count".
A special hop count value "unknown"(=0xff), which is larger than any A special hop count value "unknown"(=0xff), which is larger than
other known value, is used when a loop is found. Once the thread any other known value, is used when a loop is found. Once the
hop count is "unknown", it is not increased any more as the thread thread hop count is "unknown", it is not increased any more as the
is extended. thread is extended.
Thread TTL Thread TTL
To avoid infinite looping of control messages in some cases, a To avoid infinite looping of control messages in some cases, a
thread TTL is used. When a node creates a path control message and thread TTL is used. When a node creates a path control message
sends it downstream, it sets a TTL to the message, and the TTL is and sends it downstream, it sets a TTL to the message, and the TTL
decremented at each hop. When the TTL reaches 0, the message is not is decremented at each hop. When the TTL reaches 0, the message
forwarded any more. Unlike the thread hop counts and the thread is not forwarded any more. Unlike the thread hop counts and the
colors, the thread TTLs do not needs to be stored in incoming links. thread colors, the thread TTLs do not needs to be stored in
incoming links.
3.2. Thread loop 3.2. Thread loop
When the same colored thread is received on multiple incoming links, When the same colored thread is received on multiple incoming links,
or the received thread color was assigned by the receiving node, it 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 is said that the thread forms a loop. A thread creator can tell
whether it assigned the received thread color by checking the IP whether it assigned the received thread color by checking the IP
address part of the received thread color. address part of the received thread color.
3.3. Primitive thread actions 3.3. Primitive thread actions
Five primitive actions are defined in order to prevent LSP loops by Five primitive actions are defined in order to prevent LSP loops by
using threads: "extending", "rewinding", "withdrawing", "merging", using threads: "extending", "rewinding", "withdrawing", "merging",
and "stalling". This section describes only each primitive action and "stalling". This section describes only each primitive action
and does not describe how these primitive actions are combined and and does not describe how these primitive actions are combined and
how the algorithm totally works. The main body of the algorithm is how the algorithm totally works. The main body of the algorithm is
described in section 4. described in section 4.
Thread Extending Thread Extending
When a node starts to send a path setup message to its next hop with When a node starts to send a path setup message to its next hop
a set of thread attributes, it is said that "the node creates a with a set of thread attributes, it is said that "the node creates
thread and extends it downstream". When a node receives a path a thread and extends it downstream". When a node receives a path
setup message from an upstream node with a set of thread attributes setup message from an upstream node with a set of thread
and forwards it downstream, it is said that "the node receives a attributes and forwards it downstream, it is said that "the node
thread and extends it downstream". The color and hop count of the receives a thread and extends it downstream". The color and hop
thread become the color and hop count of the outgoing link. count of the thread become the color and hop count of the outgoing
Whenever a thread is received on a particular link, the color and link. Whenever a thread is received on a particular link, the
hop count of that thread become the color and hop count of that color and hop count of that thread become the color and hop count
incoming link, replacing any color and hop count that the link may of that incoming link, replacing any color and hop count that the
have had previously. link may have had previously.
For example, when an ingress node initiates a path setup, it creates For example, when an ingress node initiates a path setup, it
a thread and extends it downstream by sending a path setup message. creates a thread and extends it downstream by sending a path setup
The thread hop count is set to be 1, and the thread color is set to message. The thread hop count is set to be 1, and the thread
be the ingress node's address with an appropriate event identifier, color is set to be the ingress node's address with an appropriate
and the thread TTL is set to be its maximum value. 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 When a node receives a thread and extends it downstream, the node
either (i) extends the thread without changing color, or (ii) extend either (i) extends the thread without changing color, or (ii)
the thread with changing color. The received thread is extended extend the thread with changing color. The received thread is
with changing color if it is received on a new incoming link and extended with changing color if it is received on a new incoming
extended on an already existing outgoing link, otherwise, it is link and extended on an already existing outgoing link, otherwise,
extended without changing color. When a thread is extended with it is extended without changing color. When a thread is extended
changing color, a new colored thread is created and extended. with changing color, a new colored thread is created and extended.
Thread creation does not occur only at leaf nodes. If an Thread creation does not occur only at leaf nodes. If an
intermediate node has an incoming link, it will create and extend a intermediate node has an incoming link, it will create and extend
new thread whenever it acquires a new next hop. 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 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 count, if it is not extending a colored thread, a transparent
is extended. thread is extended.
Thread Merging Thread Merging
When a node which has a colored outgoing link receives a new thread, When a node which has a colored outgoing link receives a new
it does not necessarily extend the new thread. It may instead 'merge' thread, it does not necessarily extend the new thread. It may
the new threads into the existing outgoing thread. In this case, no instead 'merge' the new threads into the existing outgoing thread.
messages are sent downstream. Also, if a new incoming thread is In this case, no messages are sent downstream. Also, if a new
extended downstream, but there are already other incoming threads, incoming thread is extended downstream, but there are already
these other incoming threads are considered to be merged into the other incoming threads, these other incoming threads are
new outgoing thread. considered to be merged into the new outgoing thread.
Specifically, a received thread is merged if all the following Specifically, a received thread is merged if all the following
conditions hold: conditions hold:
o A colored thread is received by node N, AND o A colored thread is received by node N, AND
o The thread does not form a loop, AND o The thread does not form a loop, AND
o N is not an egress node, AND o N is not an egress node, AND
o N's outgoing link is colored, AND o N's outgoing link is colored, AND
o N's outgoing link hop count is at least one greater than the hop o N's outgoing link hop count is at least one greater than the
count of the newly received thread. hop count of the newly received thread.
When an outgoing thread rewinds (see below), any incoming threads When an outgoing thread rewinds (see below), any incoming threads
which have been merged with it will rewind as well. which have been merged with it will rewind as well.
Thread Stalling Thread Stalling
When a colored thread is received, if the thread forms a loop, the 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 received thread color and hop count are stored on the receiving
without being extended. This is the special case of thread merging link without being extended. This is the special case of thread
applied only for threads forming a loop and referred to as the merging applied only for threads forming a loop and referred to as
"thread stalling", and the incoming link storing the stalled thread the "thread stalling", and the incoming link storing the stalled
is called "stalled incoming link". A distinction is made between thread is called "stalled incoming link". A distinction is made
stalled incoming links and unstalled incoming links. between stalled incoming links and unstalled incoming links.
Thread Rewinding Thread Rewinding
When a thread reaches a node which satisfies a particular loop-free When a thread reaches a node which satisfies a particular loop-
condition, the node returns an acknowledgment message back to the free condition, the node returns an acknowledgment message back to
message initiator in the reverse path on which the thread was the message initiator in the reverse path on which the thread was
extended. The transmission of the acknowledgment messages is the extended. The transmission of the acknowledgment messages is the
"rewinding" of the thread. "rewinding" of the thread.
The loop-free condition is: The loop-free condition is:
o A colored thread is received by the egress node, OR o A colored thread is received by the egress node, OR
o All of the following conditions hold: o All of the following conditions hold:
(a) A colored thread is received by node N, AND (a) A colored thread is received by node N, AND
(b) N's outgoing link is transparent, AND (b) N's outgoing link is transparent, AND
(c) N's outgoing link hop count is at least one greater than the (c) N's outgoing link hop count is at least one greater than
hop count of the newly received thread. the hop count of the newly received thread.
When a node rewinds a thread which was received on a particular When a node rewinds a thread which was received on a particular
link, it changes the color of that link to transparent. 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 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 colored thread to N over that link, and M determines (by receiving
message from N) that N has rewound that thread, then M sets the a message from N) that N has rewound that thread, then M sets the
color of its outgoing link to transparent. M then continues color of its outgoing link to transparent. M then continues
rewinding the thread, and in addition, rewinds any other incoming rewinding the thread, and in addition, rewinds any other incoming
thread which had been merged with the thread being rewound, thread which had been merged with the thread being rewound,
including stalled threads. including stalled threads.
Each node can start label switching after the thread colors in all Each node can start label switching after the thread colors in all
incoming and outgoing links becomes transparent. incoming and outgoing links becomes transparent.
Note that transparent threads are threads which have already been Note that transparent threads are threads which have already been
rewound; hence there is no such thing as rewinding a transparent rewound; hence there is no such thing as rewinding a transparent
thread. thread.
Thread Withdrawing Thread Withdrawing
It is possible for a node to tear down a path. A node tears down 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 the portion of the path downstream of itself by sending teardown
messages to its next hop. This process is known as the "thread messages to its next hop. This process is known as the "thread
withdrawing". withdrawing".
For example, suppose a node is trying to set up a path, and then 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 experiences a next hop change or a next hop loss. It will
the thread that it had extended down its old next hop. 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 If node M has extended a thread to node N, and node M then
that thread, N now has one less incoming link than it had before. If withdraws that thread, N now has one less incoming link than it
N now has no other unstalled incoming links and N is not an eligible had before. If N now has no other unstalled incoming links and N
leaf node, it must withdraw its outgoing thread. If N still has an is not an eligible leaf node, it must withdraw its outgoing
unstalled incoming link or N is an eligible leaf node, it may (or thread. If N still has an unstalled incoming link or N is an
may not) need to change the hop count of the outgoing link. 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: N needs to change the outgoing hop count if:
o The incoming link hop count that was just removed had a larger o The incoming link hop count that was just removed had a larger
hop count than any of the remaining incoming links, AND hop count than any of the remaining incoming links, AND
o One of the following conditions holds: o One of the following conditions holds:
(a) The outgoing link is transparent, OR (a) The outgoing link is transparent, OR
(b) The outgoing link has a known hop count. (b) The outgoing link has a known hop count.
If the outgoing link is transparent, it remains transparent, but the If the outgoing link is transparent, it remains transparent, but
new hop count needs to be sent downstream. If the outgoing link is the new hop count needs to be sent downstream. If the outgoing
colored, a new thread (with a new color) needs to be created and link is colored, a new thread (with a new color) needs to be
extended downstream. created and extended downstream.
3.4. Examples of primitive thread actions 3.4. Examples of primitive thread actions
The following notations are used to illustrate examples of primitive The following notations are used to illustrate examples of primitive
actions defined for threads. actions defined for threads.
A pair of thread attributes stored in each link is represented by 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 "(C,H)", where C and H represent the thread color and thread hop
count, respectively. count, respectively.
A thread marked "+" indicates that it is created or received now. A A thread marked "+" indicates that it is created or received now. A
thread marked "-" indicates that it is withdrawn now. thread marked "-" indicates that it is withdrawn now.
A link labeled with squared brackets (e.g., "[a]") indicates that it A link labeled with squared brackets (e.g., "[a]") indicates that it
is an unstalled link. A link labeled with braces (e.g., "{a}") is an unstalled link. A link labeled with braces (e.g., "{a}")
indicates that it is a stalled link. indicates that it is a stalled link.
Fig. 2 shows an example in which a leaf node A creates a blue Fig. 2 shows an example in which a leaf node A creates a blue thread
thread and extends it downstream. and extends it downstream.
(bl,1) (bl,1)
A---[o1]---> A---[o1]--->
Fig.2 Thread extending at leaf node Fig.2 Thread extending at leaf node
Fig.3 shows an example of thread extending without changing color at Fig.3 shows an example of thread extending without changing color at
intermediate node. Assume that a node B has no incoming and intermediate node. Assume that a node B has no incoming and outgoing
outgoing link before receiving a blue thread. When node B receives link before receiving a blue thread. When node B receives the blue
the blue thread of hop count 1 on a new incoming link i1, it extends thread of hop count 1 on a new incoming link i1, it extends the
the thread downstream without changing color (Fig.3(a)). After the thread downstream without changing color (Fig.3(a)). After the blue
blue thread is extended, node B receives a red thread of hop count thread is extended, node B receives a red thread of hop count unknown
unknown on incoming link i1 again (Fig.3(b)). The red thread is on incoming link i1 again (Fig.3(b)). The red thread is also
also extended without changing its color, since both i1 and o1 extended without changing its color, since both i1 and o1 already
already exists. exists.
(bl,1)+ (bl,2) (re,U)+ (re,U) (bl,1)+ (bl,2) (re,U)+ (re,U)
----[i1]--->B---[o1]----> ----[i1]--->B----[o1]---> ----[i1]--->B---[o1]----> ----[i1]--->B----[o1]--->
Fig.3(a) Fig.3(b) Fig.3(a) Fig.3(b)
Fig.3 Thread extending without changing color Fig.3 Thread extending without changing color
Fig.4 shows an example of thread extending with 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 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 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 incoming link i2. In this case, the received thread is extended with
with changing color, i.e., a new green thread is created and changing color, i.e., a new green thread is created and extended
extended (Fig.4(b)), since o1 already exists. (Fig.4(b)), since o1 already exists.
(bl,1) (bl,2) (bl,1) (gr,4) (bl,1) (bl,2) (bl,1) (gr,4)
----[i1]--->B----[o1]---> ----[i1]--->B----[o1]---> ----[i1]--->B----[o1]---> ----[i1]--->B----[o1]--->
^ ^
| |
----[i2]----+ ----[i2]----+
(re,3)+ (re,3)+
Fig.4(a) Fig.4(b) Fig.4(a) Fig.4(b)
Fig.4 Thread extending with changing color Fig.4 Thread extending with changing color
Fig.5 shows an example of thread merging. When a node B receives a 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 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 the outgoing link hop count is at least one greater than the received
received thread hop count. Both the red and blue threads will be thread hop count. Both the red and blue threads will be rewound when
rewound when the blue thread on outgoing link o1 is rewound. the blue thread on outgoing link o1 is rewound.
(bl,3) (bl,4) (bl,3) (bl,4)
----[i1]--->B----[o1]---> ----[i1]--->B----[o1]--->
^ ^
| |
----[i2]----+ ----[i2]----+
(re,3)+ (re,3)+
Fig.5 Thread merging Fig.5 Thread merging
Figs 6 and 7 show examples of thread stalling. When a node B 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, 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. 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. In Fig.7, a leaf node A finds the loop of its own thread.
(bl,3) (bl,4) (bl,3) (bl,4)
----[i1]--->B----[o1]---> ----[i1]--->B----[o1]--->
^ ^
| |
----{i2}----+ ----{i2}----+
(bl,10)+ (bl,10)+
Fig.6 Thread stalling (1) Fig.6 Thread stalling (1)
(bl,10)+ (bl,1) (bl,10)+ (bl,1)
----{i1}--->A----[o1]---> ----{i1}--->A----[o1]--->
Fig.7 Thread stalling (2) Fig.7 Thread stalling (2)
Fig.8 shows an example of thread rewinding. When the yellow thread Fig.8 shows an example of thread rewinding. When the yellow thread
which is currently being extended is rewound (Fig.8(a)), the node which is currently being extended is rewound (Fig.8(a)), the node
changes all the incoming and outgoing thread color to transparent, changes all the incoming and outgoing thread color to transparent,
and propagates thread rewinding to upstream nodes (Fig.8(b)). and propagates thread rewinding to upstream nodes (Fig.8(b)).
(bl,1) (ye,2) (tr,1) (tr,2) (bl,1) (ye,2) (tr,1) (tr,2)
----[i2]--->B----[o1]---> ----[i2]--->B----[o1]---> ----[i2]--->B----[o1]---> ----[i2]--->B----[o1]--->
^ ^ ^ ^
| | | |
----[i3]----+ ----[i3]----+ ----[i3]----+ ----[i3]----+
(ye,1) (tr,1) (ye,1) (tr,1)
Fig.8(a) Fig.8(b) Fig.8(a) Fig.8(b)
Fig.8 Thread rewinding Fig.8 Thread rewinding
Fig.9 shows an example of thread withdrawing. In Fig.9(a), the red Fig.9 shows an example of thread withdrawing. In Fig.9(a), the red
thread on incoming link i2 is withdrawn. Then Hmax decreases from 3 thread on incoming link i2 is withdrawn. Then Hmax decreases from 3
to 1, and node B creates a new green thread and extends it to 1, and node B creates a new green thread and extends it
downstream, as shown in Fig.9(b). downstream, as shown in Fig.9(b).
(bl,1) (re,4) (bl,1) (gr,2)+ (bl,1) (re,4) (bl,1) (gr,2)+
----[i1]--->B---[o1]---> ----[i1]--->B----[o1]---> ----[i1]--->B---[o1]---> ----[i1]--->B----[o1]--->
^ ^
| |
----[i2]----+ ----[i2]----+
(re,3)- (re,3)-
Fig.9(a) Fig.9(b) Fig.9(a) Fig.9(b)
Fig.9 Thread withdrawing (1) Fig.9 Thread withdrawing (1)
Fig.10 shows another example of thread withdrawing. In Fig.10(a), Fig.10 shows another example of thread withdrawing. In Fig.10(a),
the red thread on incoming link i3 is withdrawn. In this case, Hmax the red thread on incoming link i3 is withdrawn. In this case, Hmax
decreases from unknown to 1, however, no thread is extended as shown decreases from unknown to 1, however, no thread is extended as shown
in Fig.10(b), since the outgoing link has a colored thread and the in Fig.10(b), since the outgoing link has a colored thread and the
hop count is unknown. hop count is unknown.
(bl,1) (re,U) (bl,1) (re,U) (bl,1) (re,U) (bl,1) (re,U)
----[i2]--->B----[o1]---> ----[i2]--->B----[o1]---> ----[i2]--->B----[o1]---> ----[i2]--->B----[o1]--->
^ ^
| |
----[i3]----+ ----[i3]----+
(re,U)- (re,U)-
Fig.10(a) Fig.10(b) Fig.10(a) Fig.10(b)
Fig.10 Thread withdrawing (2) Fig.10 Thread withdrawing (2)
Fig.11 shows another example of thread withdrawing. In Fig.11(a), Fig.11 shows another example of thread withdrawing. In Fig.11(a),
the transparent thread on incoming link i3 is withdrawn. In this the transparent thread on incoming link i3 is withdrawn. In this
case, a transparent thread is extended (Fig.11(b)), since Hmax case, a transparent thread is extended (Fig.11(b)), since Hmax
decreases and the outgoing link is transparent. decreases and the outgoing link is transparent.
(tr,1) (tr,U) (tr,1) (tr,2)+ (tr,1) (tr,U) (tr,1) (tr,2)+
----[i2]--->B----[o1]---> ----[i2]--->B----[o1]---> ----[i2]--->B----[o1]---> ----[i2]--->B----[o1]--->
^ ^
| |
----[i3]----+ ----[i3]----+
(tr,U)- (tr,U)-
Fig.11(a) Fig.11(b) Fig.11(a) Fig.11(b)
Fig.11 Thread withdrawing (3) Fig.11 Thread withdrawing (3)
4. Thread algorithm 4. Thread algorithm
The ordered downstream-on-demand allocation is assumed here, The ordered downstream-on-demand allocation is assumed here, however,
however, the algorithm can be adapted to the ordered downstream the algorithm can be adapted to the ordered downstream allocation, as
allocation, as shown in section 5. shown in section 5.
In the algorithm, a next hop change event will be separated into two In the algorithm, a next hop change event will be separated into two
events: a next hop loss event on the old next hop and a next hop events: a next hop loss event on the old next hop and a next hop
acquisition event on the new next hop, in this order. acquisition event on the new next hop, in this order.
The following notations are defined: The following notations are defined:
Hmax: the largest incoming link hop count Hmax: the largest incoming link hop count
Ni: the number of unstalled incoming links Ni: the number of unstalled incoming links
The thread algorithm is described as follows. The thread algorithm is described as follows.
When a node acquires a new next hop, it creates a colored thread and When a node acquires a new next hop, it creates a colored thread and
extends it downstream. extends it downstream.
When a node loses a next hop to which it has extended a thread, it When a node loses a next hop to which it has extended a thread, it
may withdraw that thread. As described in section 3, this may or may withdraw that thread. As described in section 3, this may or may
may not cause the next hop to take some action. Among the actions not cause the next hop to take some action. Among the actions the
the next hop may take are withdrawing the thread from its own next next hop may take are withdrawing the thread from its own next hop,
hop, or extending a new thread to its own next hop. or extending a new thread to its own next hop.
A received colored thread is either stalled, merged, rewound, or A received colored thread is either stalled, merged, rewound, or
extended. A thread with TTL zero is never extended. extended. A thread with TTL zero is never extended.
When a received thread is stalled at a node, if Ni=0 and the node When a received thread is stalled at a node, if Ni=0 and the node is
is not an eligible leaf node, initiate a thread withdrawing. not an eligible leaf node, initiate a thread withdrawing. Otherwise,
Otherwise, if Ni>0 and the received thread hop count is not unknown, if Ni>0 and the received thread hop count is not unknown, a colored
a colored thread of hop count unknown is created and extended. If thread of hop count unknown is created and extended. If the received
the received thread hop count is unknown, no thread is extended and thread hop count is unknown, no thread is extended and no further
no further action is taken. action is taken.
When a thread being extended is rewound, if the thread hop count is When a thread being extended is rewound, if the thread hop count is
greater than one more than Hmax, a transparent thread of hop count greater than one more than Hmax, a transparent thread of hop count
(Hmax+1) is extended downstream. (Hmax+1) is extended downstream.
When a node that has an transparent outgoing link receives a When a node that has an transparent outgoing link receives a
transparent thread, if Hmax decreases the node extends it transparent thread, if Hmax decreases the node extends it downstream
downstream without changing color. without changing color.
5. Applicability of the algorithm 5. Applicability of the algorithm
The thread algorithm described in section 4 can be applied to The thread algorithm described in section 4 can be applied to various
various LSP management policies. LSP management policies.
5.1. LSP Loop prevention/detection 5.1. LSP Loop prevention/detection
The same thread algorithm is applicable to both LSP loop prevention The same thread algorithm is applicable to both LSP loop prevention
and detection. and detection.
In loop prevention mode, a node transmits a label mapping (including In loop prevention mode, a node transmits a label mapping (including
a thread object) for a particular LSP only when it rewinds the a thread object) for a particular LSP only when it rewinds the thread
thread for that LSP. No mapping message is sent until the thread for that LSP. No mapping message is sent until the thread rewinds.
rewinds.
On the other hand, if a node operates in loop detection mode, it On the other hand, if a node operates in loop detection mode, it
returns a label mapping message without a thread object immediately returns a label mapping message without a thread object immediately
after receiving a colored thread. A node which receives a label after receiving a colored thread. A node which receives a label
mapping message that does not have a thread object will not rewind mapping message that does not have a thread object will not rewind
the thread. the thread.
5.2. Using old path while looping on new path 5.2. Using old path while looping on new path
When a route changes, one might want to continue to use the old path When a route changes, one might want to continue to use the old path
if the new route is looping. This is achieved simply by holding the if the new route is looping. This is achieved simply by holding the
label assigned to the downstream link on the old path until the label assigned to the downstream link on the old path until the
thread being extended on the new route gets rewound. This is an thread being extended on the new route gets rewound. This is an
implementation choice. implementation choice.
5.3. How to deal with ordered downstream allocation 5.3. How to deal with ordered downstream allocation
The thread mechanism can be also adapted to ordered downstream The thread mechanism can be also adapted to ordered downstream
allocation mode (or the egress-initiated ordered control) by allocation mode (or the egress-initiated ordered control) by
regarding the event of newly receiving of a label mapping message regarding the event of newly receiving of a label mapping message [4]
[4] from the next hop as a next hop acquisition event. from the next hop as a next hop acquisition event.
Note that a node which doesn't yet have an incoming link behaves as Note that a node which doesn't yet have an incoming link behaves as a
a leaf. In the case where the tree is being initially built up leaf. In the case where the tree is being initially built up (e.g.,
(e.g., the egress node has just come up), each node in turn will the egress node has just come up), each node in turn will behave as a
behave as a leaf for a short period of time. leaf for a short period of time.
5.4. How to realize load splitting 5.4. How to realize load splitting
A leaf node can easily perform load splitting by setting up two A leaf node can easily perform load splitting by setting up two
different LSPs for the same FEC. The downstream links for the two different LSPs for the same FEC. The downstream links for the two
LSPs are simply assigned different colors. The thread algorithm now LSPs are simply assigned different colors. The thread algorithm now
prevents a loop in either path, but also allows the two paths to prevents a loop in either path, but also allows the two paths to have
have a common downstream node. a common downstream node.
If some intermediate node wants to do load splitting, the following If some intermediate node wants to do load splitting, the following
modification is made. Assume that there are multiple next hops for modification is made. Assume that there are multiple next hops for
the same FEC. If there are n next hops for a particular FEC, the the same FEC. If there are n next hops for a particular FEC, the set
set of incoming links for that FEC's LSP can be partitioned into n of incoming links for that FEC's LSP can be partitioned into n
subsets, where each subset can be mapped to a distinct outgoing subsets, where each subset can be mapped to a distinct outgoing link.
link. This provides n LSPs for the FEC. Each such LSP uses a
distinct color for its outgoing link. The thread algorithm now
prevents a loop in any of the paths, but also allows two or more of
the paths to have a common downstream node.
In this case, an interesting situation may happen. Let's say that This provides n LSPs for the FEC. Each such LSP uses a distinct
in Fig.12, node B has two incoming links, i1 and i2, and two color for its outgoing link. The thread algorithm now prevents a
outgoing links, o1 and o2, such that i1 is mapped to o1, while i2 is loop in any of the paths, but also allows two or more of the paths to
mapped to o2. have a common downstream node.
If a blue thread received on i1 and extended on o1 is again received In this case, an interesting situation may happen. Let's say that in
at node B on i2, the blue thread is not regarded as forming a loop, Fig.12, node B has two incoming links, i1 and i2, and two outgoing
since i1 and i2 are regarded as belonging to different subsets. links, o1 and o2, such that i1 is mapped to o1, while i2 is mapped to
Instead, the blue thread received on i2 is extended on o2. If the o2.
thread extended on o2 is rewound, a single loop-free LSP which
traverses node B twice is established.
+------------------...--------------------+ If a blue thread received on i1 and extended on o1 is again received
. (bl,3) (bl,4) | at node B on i2, the blue thread is not regarded as forming a loop,
. ----[i1]---+ +--[o1]---> .... --+ since i1 and i2 are regarded as belonging to different subsets.
. \ / Instead, the blue thread received on i2 is extended on o2. If the
. v / thread extended on o2 is rewound, a single loop-free LSP which
| B traverses node B twice is established.
|
+-----------[i2]--->B----[o2]--->
(bl,10)+ (bl,11)
Fig.12 Load splitting at intermediate node +------------------...--------------------+
. (bl,3) (bl,4) |
. ----[i1]---+ +--[o1]---> .... --+
. \ /
. v /
| B
|
+-----------[i2]--->B----[o2]--->
(bl,10)+ (bl,11)
There is another type of load splitting, in which packets arrived at Fig.12 Load splitting at intermediate node
single incoming link can be label switched to any one of multiple
outgoing links. This case does not seem to be a good load-splitting
scheme, since the packet order in the same FEC is not preserved.
Thus, this draft does not focus on this case.
Whether that's a good type of load splitting or not, the fact There is another type of load splitting, in which packets arrived at
remains that ATM-LSRs cannot load split like this because ATM single incoming link can be label switched to any one of multiple
switches just don't have the capability to make forwarding decisions outgoing links. This case does not seem to be a good load-splitting
on a per-packet basis. scheme, since the packet order in the same FEC is not preserved.
Thus, this document does not focus on this case.
Whether that's a good type of load splitting or not, the fact remains
that ATM-LSRs cannot load split like this because ATM switches just
don't have the capability to make forwarding decisions on a per-
packet basis.
6. Why this works 6. Why this works
6.1. Why a thread with unknown hop count is extended 6.1. Why a thread with unknown hop count is extended
In the algorithm, a thread of unknown hop count is extended when a In the algorithm, a thread of unknown hop count is extended when a
thread loop is detected. This reduces the number of loop prevention thread loop is detected. This reduces the number of loop prevention
messages by merging threads (of known hop count) that are flowing messages by merging threads (of known hop count) that are flowing
inside or outside the loop. See Appendix A.12. inside or outside the loop. See Appendix A.12.
6.2. Why a rewound thread cannot contain a loop 6.2. Why a rewound thread cannot contain a loop
6.2.1. Case1: LSP with known link hop counts 6.2.1. Case1: LSP with known link hop counts
How can we be sure that an established path does not contain a loop How can we be sure that an established path does not contain a loop
when the outgoing link hop count is NOT "unknown"? when the outgoing link hop count is NOT "unknown"?
Consider a sequence of LSRs <R1, ..., Rn>, such that there is a loop Consider a sequence of LSRs <R1, ..., Rn>, such that there is a loop
traversing the LSRs in the sequence. (I.e., packets from R1 go to traversing the LSRs in the sequence. (I.e., packets from R1 go to
R2, then to R3, etc., then to Rn, and then from Rn to R1.) 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 Suppose that the thread hop count of the link between R1 and R2 is k.
k. Then by the above procedures, the hop counts between Rn and R1 Then by the above procedures, the hop counts between Rn and R1 must
must be k+n-1. But the algorithm also ensures that if a node has an be k+n-1. But the algorithm also ensures that if a node has an
incoming hop count of j, its outgoing link hop count must be at incoming hop count of j, its outgoing link hop count must be at least
least of j+1. Hence, if we assume that the LSP established as a of j+1. Hence, if we assume that the LSP established as a result of
result of thread rewinding contains a loop, the hop counts between thread rewinding contains a loop, the hop counts between R1 and R2
R1 and R2 must be at least k+n. From this we may derive the absurd must be at least k+n. From this we may derive the absurd conclusion
conclusion that n=0, and we may therefore conclude that there is no that n=0, and we may therefore conclude that there is no such
such sequence of LSRs. sequence of LSRs.
6.2.1. Case2: LSP with unknown link hop counts 6.2.1. Case2: LSP with unknown link hop counts
An established path does not contain a loop as well, when the An established path does not contain a loop as well, when the
outgoing link hop count is "unknown". This is because a colored outgoing link hop count is "unknown". This is because a colored
thread of unknown hop count is never rewound unless it reaches thread of unknown hop count is never rewound unless it reaches
egress. egress.
6.3. Why L3 loop is detected 6.3. Why L3 loop is detected
Regardless of whether the thread hop count is known or unknown, if Regardless of whether the thread hop count is known or unknown, if
there is a loop, then some node in the loop will be the last node to there is a loop, then some node in the loop will be the last node to
receive a thread over a new incoming link. This thread will always receive a thread over a new incoming link. This thread will always
arrive back at that node, without its color having changed. Hence arrive back at that node, without its color having changed. Hence
the loop will always be detected by at least one of the nodes in the the loop will always be detected by at least one of the nodes in the
loop. loop.
6.4. Why L3 loop is not mis-detected 6.4. Why L3 loop is not mis-detected
Since no node ever extends the same colored thread downstream twice, Since no node ever extends the same colored thread downstream twice,
a thread loop is not detected unless there actually is an L3 routing a thread loop is not detected unless there actually is an L3 routing
loop. loop.
6.5. How a stalled thread automatically recovers from loop 6.5. How a stalled thread automatically recovers from loop
Once a thread is stalled in a loop, the thread (or the path setup Once a thread is stalled in a loop, the thread (or the path setup
request) effectively remains in the loop, so that a path request) effectively remains in the loop, so that a path
reconfiguration (i.e., thread withdrawing on the old path and thread reconfiguration (i.e., thread withdrawing on the old path and thread
extending on the new path) can be issued from any node that may extending on the new path) can be issued from any node that may
receive a route change event so as to break the loop. receive a route change event so as to break the loop.
6.6. Why different colored threads do not chase each other 6.6. Why different colored threads do not chase each other
In the algorithm, multiple thread color and/or hop count updates may In the algorithm, multiple thread color and/or hop count updates may
happen if several leaf nodes start extending threads at the same happen if several leaf nodes start extending threads at the same
time. How can we prevent multiple threads from looping unlimitedly? time. How can we prevent multiple threads from looping unlimitedly?
First, when a node finds that a thread forms a loop, it creates a First, when a node finds that a thread forms a loop, it creates a new
new thread of hop count "unknown". All the looping threads of a thread of hop count "unknown". All the looping threads of a known
known hop count which later arrive at the node would be merged into hop count which later arrive at the node would be merged into this
this thread. Such a thread behaves like a thread absorber. thread. Such a thread behaves like a thread absorber.
Second, the "thread extending with changing color" prevents two Second, the "thread extending with changing color" prevents two
threads from chasing each other. threads from chasing each other.
Suppose that a received thread were always extended without changing Suppose that a received thread were always extended without changing
color. Then we would encounter the following situation. color. Then we would encounter the following situation.
G Y G Y
| | | |
v v v v
R1------>R2 R1------>R2
^ | ^ |
| v | v
R4<------R3 R4<------R3
Fig.13 Example of thread chasing Fig.13 Example of thread chasing
In Fig.13, (1) node G acquires R1 as a next hop, and starts to In Fig.13, (1) node G acquires R1 as a next hop, and starts to extend
extend a green thread of hop count 1, (2) node Y acquires R2 as a a green thread of hop count 1, (2) node Y acquires R2 as a next hop,
next hop, and starts to extend a yellow thread of hop count 1, and and starts to extend a yellow thread of hop count 1, and (3) both
(3) both node G and node Y withdraws their threads before these node G and node Y withdraws their threads before these threads go
threads go round. round.
In this case, the yellow and green threads would go round and get In this case, the yellow and green threads would go round and get
back to R2 and R1, respectively. When the threads get back to R2 back to R2 and R1, respectively. When the threads get back to R2 and
and R1, however, the incoming links that store the yellow and green R1, however, the incoming links that store the yellow and green
colors no longer exist. As a result, the yellow and green threads colors no longer exist. As a result, the yellow and green threads
would chase each other forever in the loop. would chase each other forever in the loop.
However, since we have the "extending with changing color" However, since we have the "extending with changing color" mechanism,
mechanism, this does not actually happen. When a green thread is this does not actually happen. When a green thread is received at
received at R2, R2 extends the thread with changing color, i.e., R2, R2 extends the thread with changing color, i.e., creates a new
creates a new red thread and extends it. Similarly, when a yellow red thread and extends it. Similarly, when a yellow thread is
thread is received at R1, R1 creates a new purple thread and extends received at R1, R1 creates a new purple thread and extends it. Thus,
it. Thus, the thread loop is detected even after node G and node Y the thread loop is detected even after node G and node Y withdraw
withdraw threads. This ensures that a thread is extended around the threads. This ensures that a thread is extended around the loop
loop which has a color assigned by some node that is in the loop. which has a color assigned by some node that is in the loop.
There is at least one case even the "extending with changing color" There is at least one case even the "extending with changing color"
mechanism cannot treat, that is, the "self-chasing" in which thread mechanism cannot treat, that is, the "self-chasing" in which thread
extending and thread withdrawing with regard to the same thread extending and thread withdrawing with regard to the same thread chase
chase each other in a loop. This case would happen when a node each other in a loop. This case would happen when a node withdraw a
withdraw a thread immediately after extending it into an L3 loop. thread immediately after extending it into an L3 loop.
A heuristics for self-chasing is to delay the execution of thread A heuristics for self-chasing is to delay the execution of thread
withdrawing at an initiating node of the thread withdrawing. withdrawing at an initiating node of the thread withdrawing. Anyway,
Anyway, the thread TTL mechanism can eliminate any kind of thread the thread TTL mechanism can eliminate any kind of thread looping.
looping.
7. Loop prevention examples 7. Loop prevention examples
In this section, we show two examples to show how the algorithm can In this section, we show two examples to show how the algorithm can
prevent LSP loops in given networks. prevent LSP loops in given networks.
We assume that the ordered downstream-on-demand allocation is We assume that the ordered downstream-on-demand allocation is
employed, that all the LSPs are with regard to the same FEC, and employed, that all the LSPs are with regard to the same FEC, and that
that all nodes are VC-merge capable. all nodes are VC-merge capable.
7.1. First example 7.1. First example
Consider an MPLS network shown in Fig.14 in which an L3 loop exists. Consider an MPLS network shown in Fig.14 in which an L3 loop exists.
Each directed link represents the current next hop of the FEC at Each directed link represents the current next hop of the FEC at each
each node. Now leaf nodes R1 and R6 initiate creation of an LSP. node. Now leaf nodes R1 and R6 initiate creation of an LSP.
R11 ------- R10 <-------------------- R9 R11 ------- R10 <-------------------- R9
| | ^ | | ^
| | | | | |
| | | | | |
v v | v v |
R1 -------> R2 --------> R3 --------> R4 --------- R5 R1 -------> R2 --------> R3 --------> R4 --------- R5
[leaf] ^ [leaf] ^
| |
| |
| |
R6 -------> R7 --------> R8 R6 -------> R7 --------> R8
[leaf] [leaf]
Fig. 14 Example MPLS network (1) Fig. 14 Example MPLS network (1)
Assume that R1 and R6 send a label request message at the same time, Assume that R1 and R6 send a label request message at the same time,
and that the initial thread TTL is 255. First we show an example of and that the initial thread TTL is 255. First we show an example of
how to prevent LSP loops. how to prevent LSP loops.
A set of thread attributes is represented by (color, hop count, TTL). 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), The request from R1 and R6 contains (re,1,255) and (bl,1,255),
respectively. respectively.
Assume that R3 receives the request originated from R1 before Assume that R3 receives the request originated from R1 before
receiving the request originated from R6. When R3 receives the receiving the request originated from R6. When R3 receives the first
first request with red thread, R3 forwards it with (re,3,253) request with red thread, R3 forwards it with (re,3,253) without
without changing thread color, since both the receiving incoming changing thread color, since both the receiving incoming link and the
link and the outgoing link are newly created. Then R3 receives the outgoing link are newly created. Then R3 receives the second request
second request with blue thread. In this time, the outgoing link is with blue thread. In this time, the outgoing link is already exists.
already exists. Thus, R3 performs thread extending with changing Thus, R3 performs thread extending with changing color, i.e., creates
color, i.e., creates a new brown thread and forwards the request a new brown thread and forwards the request with (br,4,255).
with (br,4,255).
When R2 receives the request from R10 with (re,6,250), it finds that When R2 receives the request from R10 with (re,6,250), it finds that
the red thread forms a loop, and stalls the red thread. Then, R2 the red thread forms a loop, and stalls the red thread. Then, R2
creates a purple thread of hop count unknown and extends it creates a purple thread of hop count unknown and extends it
downstream by sending a request with (pu,U,255) to R3, where "U" downstream by sending a request with (pu,U,255) to R3, where "U"
represents "unknown". represents "unknown".
After that, R2 receives another request from R10 with (br,7,252). After that, R2 receives another request from R10 with (br,7,252).
The brown thread is merged into purple thread. R2 sends no request The brown thread is merged into purple thread. R2 sends no request
to R3. to R3.
On the other hand, the purple thread goes round without changing On the other hand, the purple thread goes round without changing
color through existing links, and R2 finds the thread loop and color through existing links, and R2 finds the thread loop and stalls
stalls the purple thread. Since the received thread hop count is the purple thread. Since the received thread hop count is unknown,
unknown, no thread is created any more. In this case no thread no thread is created any more. In this case no thread rewinding
rewinding occurs. The current state of the network is shown in occurs. The current state of the network is shown in Fig.15.
Fig.15.
*: location of thread stalling *: location of thread stalling
(pu,U) (pu,U)
R11 ------- R10 <-------------------- R9 R11 ------- R10 <-------------------- R9
| | ^ | | ^
| |(pu,U)* | | |(pu,U)* |
| | |(pu,U) | | |(pu,U)
v v | v v |
R1 -------> R2 --------> R3 --------> R4 --------- R5 R1 -------> R2 --------> R3 --------> R4 --------- R5
[leaf] (re,1) (pu,U) ^ (pu,U) [leaf] (re,1) (pu,U) ^ (pu,U)
| |
| (bl,3) | (bl,3)
| |
R6 -------> R7 --------> R8 R6 -------> R7 --------> R8
[leaf] (bl,1) (bl,2) [leaf] (bl,1) (bl,2)
Fig.15 The network state Fig.15 The network state
Then R10 changes its next hop from R2 to R11. Then R10 changes its next hop from R2 to R11.
Since R10 has a purple thread on the old downstream link, it first Since R10 has a purple thread on the old downstream link, it first
sends a path teardown message to the old next hop R2 for withdrawing sends a path teardown message to the old next hop R2 for withdrawing
the purple thread. Next, it creates a green thread of hop count the purple thread. Next, it creates a green thread of hop count
unknown and sends a request with (gr,U,255) to R11. unknown and sends a request with (gr,U,255) to R11.
When R2 receives the teardown message from R10, R2 removes the When R2 receives the teardown message from R10, R2 removes the
stalled incoming link between R10 and R2. stalled incoming link between R10 and R2.
On the other hand, the green thread reaches R1 and Hmax is updated On the other hand, the green thread reaches R1 and Hmax is updated
from zero to unknown. In this case, R1 performs thread extending from zero to unknown. In this case, R1 performs thread extending
with changing color since the thread is received on a new incoming with changing color since the thread is received on a new incoming
link but extended on the already existing outgoing link. As a link but extended on the already existing outgoing link. As a
result, R1 creates an orange thread of hop count unknown and extend result, R1 creates an orange thread of hop count unknown and extend
it to R2. it to R2.
The orange thread goes round through existing links without changing The orange thread goes round through existing links without changing
color, and finally it is stalled at R1. color, and finally it is stalled at R1.
The state of the network is now shown in Fig.16. The state of the network is now shown in Fig.16.
*: location of thread stalling *: location of thread stalling
(or,U) (or,U) (or,U) (or,U)
R11 <------ R10 <-------------------- R9 R11 <------ R10 <-------------------- R9
| | ^ | | ^
|(or,U)* | | |(or,U)* | |
| | |(or,U) | | |(or,U)
v | | v | |
R1 -------> R2 --------> R3 --------> R4 --------- R5 R1 -------> R2 --------> R3 --------> R4 --------- R5
[leaf] (or,U) (or,U) ^ (or,U) [leaf] (or,U) (or,U) ^ (or,U)
| |
| (bl,3) | (bl,3)
| |
R6 -------> R7 --------> R8 R6 -------> R7 --------> R8
[leaf] (bl,1) (bl,2) [leaf] (bl,1) (bl,2)
Fig.16 The network state Fig.16 The network state
Then R4 changes its next hop from R9 to R5. Then R4 changes its next hop from R9 to R5.
Since R4 is extending an orange thread, it first sends a teardown Since R4 is extending an orange thread, it first sends a teardown
message to the old next hop R9 to withdraw the orange thread on the message to the old next hop R9 to withdraw the orange thread on the
old route. Next, it creates a yellow thread of hop count unknown, old route. Next, it creates a yellow thread of hop count unknown,
and sends a request message with (ye,U,255) to R5. and sends a request message with (ye,U,255) to R5.
Since R5 is the egress node, the yellow thread rewinding starts. R5 Since R5 is the egress node, the yellow thread rewinding starts. R5
returns a label mapping message. The thread rewinding procedure is returns a label mapping message. The thread rewinding procedure is
performed at each node, as the label mapping message is returned performed at each node, as the label mapping message is returned
upstream hop-by-hop. upstream hop-by-hop.
If R1 receives a label mapping message before receiving the orange If R1 receives a label mapping message before receiving the orange
thread's withdrawal from R11, R1 returns a label mapping message to thread's withdrawal from R11, R1 returns a label mapping message to
R11. On receiving the orange thread's withdrawal, R1 will create a R11. On receiving the orange thread's withdrawal, R1 will create a
transparent thread and extend it by sending an update message with transparent thread and extend it by sending an update message with
(tr,1,255) in order to notify downstream of the known hop count. (tr,1,255) in order to notify downstream of the known hop count.
Otherwise, if R1 receives the orange thread's withdrawal before Otherwise, if R1 receives the orange thread's withdrawal before
receiving a label mapping message, R1 removes the stalled incoming receiving a label mapping message, R1 removes the stalled incoming
orange link and waits for rewinding of the outgoing orange thread. orange link and waits for rewinding of the outgoing orange thread.
Finally, when R1 receives a label mapping message from R2, it Finally, when R1 receives a label mapping message from R2, it creates
creates a transparent thread (tr,1,255) and extend it downstream. a transparent thread (tr,1,255) and extend it downstream.
In both cases, a merged LSP ((R1->R2),(R6->R7->R8))->R3->R4->R5) is In both cases, a merged LSP ((R1->R2),(R6->R7->R8))->R3->R4->R5) is
established and every node obtains the correct link hop count. The established and every node obtains the correct link hop count. The
final network state is shown in Fig.17. final network state is shown in Fig.17.
R11 <------ R10 <-------------------- R9 R11 <------ R10 <-------------------- R9
| | | | | |
| | | | | |
| | | | | |
v | | v | |
R1 -------> R2 --------> R3 --------> R4 --------> R5 R1 -------> R2 --------> R3 --------> R4 --------> R5
[leaf] (tr,1) (tr,2) ^ (tr,4) (tr,5) [leaf] (tr,1) (tr,2) ^ (tr,4) (tr,5)
| |
| (tr,3) | (tr,3)
| |
R6 -------> R7 --------> R8 R6 -------> R7 --------> R8
[leaf] (tr,1) (tr,2) [leaf] (tr,1) (tr,2)
Fig.17 The final network state Fig.17 The final network state
7.2. Second example 7.2. Second example
+----- R6----> R7-----+ +----- R6----> R7-----+
| | | |
| v | v
R1---->R2 R4----->R5 R1---->R2 R4----->R5
| ^ | ^
| | | |
+--------->R3---------+ +--------->R3---------+
Fig.18 Example MPLS network (2) Fig.18 Example MPLS network (2)
Assume that in Fig.18, there is an established LSP Assume that in Fig.18, there is an established LSP R1->R2->R3->R4-
R1->R2->R3->R4->R5, and the next hop changes at R2 from R3 to R6. >R5, and the next hop changes at R2 from R3 to R6. R2 sends a
R2 sends a request to R6 with a red thread (re,2,255). When the request to R6 with a red thread (re,2,255). When the request with
request with (re,4,253) reaches R4, it extends the thread to R5 with (re,4,253) reaches R4, it extends the thread to R5 with changing
changing color. Thus, a new green thread is created at R4 and color. Thus, a new green thread is created at R4 and extended to R5
extended to R5 by sending an update message with (gr,5,255). by sending an update message with (gr,5,255).
When R5 receives the update, it updates the incoming link hop count When R5 receives the update, it updates the incoming link hop count
to 5 and returns an ack (or a notification message with a success to 5 and returns an ack (or a notification message with a success
code) for the update. When R4 receives the ack for the update, it code) for the update. When R4 receives the ack for the update, it
returns a label mapping message to R7. returns a label mapping message to R7.
When R2 receives the label mapping message on the new route, it When R2 receives the label mapping message on the new route, it sends
sends a teardown message to R3. When R4 receives the teardown a teardown message to R3. When R4 receives the teardown message, it
message, it does not sends an update to R5 since Hmax does not does not sends an update to R5 since Hmax does not change. Now an
change. Now an established LSP R1->R2->R6->R7->R4->R5 is obtained. established LSP R1->R2->R6->R7->R4->R5 is obtained.
Then, the next hop changes again at R2 from R6 to R3. Then, the next hop changes again at R2 from R6 to R3.
R2 sends a request with a blue thread (bl,2,255) to R3. R3 forwards R2 sends a request with a blue thread (bl,2,255) to R3. R3 forwards
the request with (bl,3,254) to R4. the request with (bl,3,254) to R4.
When R4 receives the request, it immediately returns a label mapping When R4 receives the request, it immediately returns a label mapping
message to R3 since Hmax does not change. message to R3 since Hmax does not change.
When R2 receives the label mapping message on the new route, it When R2 receives the label mapping message on the new route, it sends
sends a teardown message to R6. The teardown message reaches R4, a teardown message to R6. The teardown message reaches R4,
triggering an update message with a transparent thread (tr,4,255) to triggering an update message with a transparent thread (tr,4,255) to
R5, since Hmax decreases from 4 to 3. R5 updates the incoming link R5, since Hmax decreases from 4 to 3. R5 updates the incoming link
hop count to 4 without returning an ack. hop count to 4 without returning an ack.
8. Thread control block 8. Thread control block
A thread control block (TCB) is maintained per LSP at each node and A thread control block (TCB) is maintained per LSP at each node and
may contain the following information: may contain the following information:
- FEC - FEC
- State - State
- Incoming links - Incoming links
Each incoming link has the following attributes: Each incoming link has the following attributes:
o neighbor: upstream neighbor node address o neighbor: upstream neighbor node address
o color: received thread color o color: received thread color
o hop count: received thread hop count o hop count: received thread hop count
o label o label
o S-flag: indicates a stalled link o S-flag: indicates a stalled link
- Outgoing links - Outgoing links
Each outgoing link has the following attributes: Each outgoing link has the following attributes:
o neighbor: downstream neighbor node address o neighbor: downstream neighbor node address
o color: received thread color o color: received thread color
o hop count: received thread hop count o hop count: received thread hop count
o label o label
o C-flag: indicates the link to the current next hop o C-flag: indicates the link to the current next hop
If a transparent thread is received on an incoming link for which no If a transparent thread is received on an incoming link for which no
label is assigned yet or a non-transparent color is stored, discard label is assigned yet or a non-transparent color is stored, discard
the thread without entering the FSM. An error message may be the thread without entering the FSM. An error message may be
returned to the sender. returned to the sender.
Whenever a thread is received on an incoming link, the following Whenever a thread is received on an incoming link, the following
actions are taken before entering the FSM: (1) Store the received actions are taken before entering the FSM: (1) Store the received
thread color and hop count on the link, replacing the old thread thread color and hop count on the link, replacing the old thread
color and hop count, and (2) set the following flags that are used color and hop count, and (2) set the following flags that are used
for an event switch within "Recv thread" event (see section 8.1). for an event switch within "Recv thread" event (see section 8.1).
o Color flag (CL-flag): o Color flag (CL-flag):
Set if the received thread is colored. Set if the received thread is colored.
o Loop flag (LP-flag): o Loop flag (LP-flag):
Set if the received thread forms a loop. Set if the received thread forms a loop.
o Arrived on new link flag (NL-flag): o Arrived on new link flag (NL-flag):
Set if the received thread arrives on a new incoming link. 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 If LP-flag is set, there must be an incoming link L, other than the
receiving link, which stores the same thread color as the received receiving link, which stores the same thread color as the received
one. The TCB to which link L belongs is referred to as the one. The TCB to which link L belongs is referred to as the
"detecting TCB". If the receiving LSR is VC-merge capable, the "detecting TCB". If the receiving LSR is VC-merge capable, the
detecting TCB and the receiving TCB is the same, otherwise, the two detecting TCB and the receiving TCB is the same, otherwise, the two
TCBs are different. TCBs are different.
Before performing a thread extending, the thread TTL is decremented Before performing a thread extending, the thread TTL is decremented
by one. If the resulting TTL becomes zero, the thread is not by one. If the resulting TTL becomes zero, the thread is not
extended but silently discarded. Otherwise, the thread is extended extended but silently discarded. Otherwise, the thread is extended
and the extended thread hop count and color are stored into the and the extended thread hop count and color are stored into the
outgoing link. outgoing link.
When a node receives a thread rewinding event, if the received When a node receives a thread rewinding event, if the received thread
thread color and the extending thread color are different, it color and the extending thread color are different, it discards the
discards the event without entering the FSM. event without entering the FSM.
8.1. Finite state machine 8.1. Finite state machine
An event which is "scheduled" by an action in an FSM must be passed An event which is "scheduled" by an action in an FSM must be passed
immediately after the completion of the action. immediately after the completion of the action.
The following variables are used in the FSM: The following variables are used in the FSM:
o Ni: number of unstalled incoming links
o Hmax: largest incoming hop count
o Hout: hop count of the outgoing link for the current next hop
o Hrec: hop count of the received thread
In the FSM, if Hmax=unknown, the value for (Hmax+1) becomes the o Ni: number of unstalled incoming links
value reserved for unknown hop count plus 1. For example, if o Hmax: largest incoming hop count
Hmax=unknown=255, the value (Hmax+1) becomes 256. o Hout: hop count of the outgoing link for the current next hop
o Hrec: hop count of the received thread
A TCB has three states; Null, Colored, and Transparent. When a TCB In the FSM, if Hmax=unknown, the value for (Hmax+1) becomes the value
is in state Null, there is no outgoing link and Ni=0. The state reserved for unknown hop count plus 1. For example, if
Colored means that the node is extending a colored thread on the Hmax=unknown=255, the value (Hmax+1) becomes 256.
outgoing link for the current next hop. The state Transparent means
that the node is the egress node or the outgoing link is
transparent.
The flag value "1" represents the flag is set, "0" represents the A TCB has three states; Null, Colored, and Transparent. When a TCB
flag is not set, and "*" means the flag value is either 1 or 0. is in state Null, there is no outgoing link and Ni=0. The state
Colored means that the node is extending a colored thread on the
outgoing link for the current next hop. The state Transparent means
that the node is the egress node or the outgoing link is transparent.
The FSM allows to have one transparent outgoing link on the old The flag value "1" represents the flag is set, "0" represents the
next hop and one colored outgoing link on the current next hop. flag is not set, and "*" means the flag value is either 1 or 0.
However, it is not allowed to have a colored outgoing link on
the old next hop.
State Null: The FSM allows to have one transparent outgoing link on the old next
hop and one colored outgoing link on the current next hop. However,
it is not allowed to have a colored outgoing link on the old next
hop.
State Null:
Event Action New state Event Action New state
Recv thread Recv thread
Flags Flags
CL LP NL CL LP NL
0 * * Do nothing. No change 0 * * Do nothing. No change
1 0 * If the node is egress, start thread rewinding Transparent 1 0 * If the node is egress, start thread rewinding Transparent
and change the color of the receiving link to and change the color of the receiving link to
transparent. transparent.
Otherwise, extend the received thread without Colored Otherwise, extend the received thread without Colored
changing color. changing color.
1 1 * Stall the received thread; if Hrec<unknown, No change 1 1 * Stall the received thread; if Hrec<unknown, No change
schedule "Reset to unknown" event for the schedule "Reset to unknown" event for the
detecting TCB. detecting TCB.
Next hop If eligible-leaf, create a colored thread and Colored Next hop If eligible-leaf, create a colored thread and Colored
acquisition extend it. acquisition extend it.
skipping to change at page 25, line 23 skipping to change at page 27, line 5
1 0 * If Hmax<Hout, merge the received thread. No change 1 0 * If Hmax<Hout, merge the received thread. No change
Otherwise, extend the thread with (if NL=1) Otherwise, extend the thread with (if NL=1)
or without (if NL=0) changing color. or without (if NL=0) changing color.
1 1 * Stall the received thread. 1 1 * Stall the received thread.
If Ni=0 and the node is not an eligible leaf, Null If Ni=0 and the node is not an eligible leaf, Null
initiate thread withdrawing. initiate thread withdrawing.
If Ni>0 and Hrec<unknown, schedule "Reset to No change If Ni>0 and Hrec<unknown, schedule "Reset to No change
unknown" event for the detecting TCB. unknown" event for the detecting TCB.
Otherwise, do nothing. No change Otherwise, do nothing. No change
Rewound Propagate thread rewinding to previous hops Transparent Rewound Propagate thread rewinding to previous hops Transparent
that are extending a colored thread; change that are extending a colored thread; change
the colors stored in all incoming and outgoing the colors stored in all incoming and outgoing
links to transparent; if Hmax+1<Hout, extend links to transparent; if Hmax+1<Hout, extend
transparent thread. Withdraw the thread on transparent thread. Withdraw the thread on
the outgoing link for which C-flag=0. the outgoing link for which C-flag=0.
Withdrawn Remove the corresponding incoming link. Withdrawn Remove the corresponding incoming link.
If Ni=0 and the node is not an eligible leaf, Null If Ni=0 and the node is not an eligible leaf, Null
propagate thread withdrawing to all next hops. propagate thread withdrawing to all next hops.
Otherwise, if Hmax+1<Hout<unknown, create No change Otherwise, if Hmax+1<Hout<unknown, create No change
a colored thread and extend it. a colored thread and extend it.
Otherwise, do nothing. No change Otherwise, do nothing. No change
Next hop If there is already an outgoing link for the Transparent Next hop If there is already an outgoing link for the Transparent
acquisition next hop, do nothing. (This case happens only acquisition next hop, do nothing. (This case happens only
when the node retains the old path.) when the node retains the old path.)
Otherwise, create a colored thread and extend No change Otherwise, create a colored thread and extend No change
it. it.
Next hop If the outgoing link is transparent and the No change Next hop If the outgoing link is transparent and the No change
loss node is allowed to retain the link and the loss node is allowed to retain the link and the
next hop is alive, do nothing. next hop is alive, do nothing.
Otherwise, take the following actions. Otherwise, take the following actions.
Initiate thread withdrawing for the next hop; Initiate thread withdrawing for the next hop;
if the node becomes a new egress, schedule if the node becomes a new egress, schedule
skipping to change at page 26, line 23 skipping to change at page 28, line 10
the color of the receiving link to transparent the color of the receiving link to transparent
and start thread rewinding. and start thread rewinding.
Otherwise, extend the thread with (if NL=1) Colored Otherwise, extend the thread with (if NL=1) Colored
or without (if NL=0) changing color. or without (if NL=0) changing color.
Withdrawn Remove the corresponding incoming link. Withdrawn Remove the corresponding incoming link.
If Ni=0 and the node is not an eligible leaf, Null If Ni=0 and the node is not an eligible leaf, Null
propagate thread withdrawing to next hops. propagate thread withdrawing to next hops.
Otherwise, if Hmax+1<Hout, create No change Otherwise, if Hmax+1<Hout, create No change
a transparent thread and extend it. a transparent thread and extend it.
Otherwise, do nothing. No change Otherwise, do nothing. No change
Next hop Create a colored thread and extend it. Colored Next hop Create a colored thread and extend it. Colored
acquisition acquisition
Next hop If the node is allowed to retain the outgoing No change Next hop If the node is allowed to retain the outgoing No change
loss link and the next hop is alive, do nothing. loss link and the next hop is alive, do nothing.
Otherwise, take the following actions. Otherwise, take the following actions.
Initiate thread withdrawing. Initiate thread withdrawing.
If Ni=0, move to Null. Null If Ni=0, move to Null. Null
Otherwise, do nothing. No change Otherwise, do nothing. No change
Others Silently ignore the event. No change Others Silently ignore the event. No change
9. Comparison with path-vector/diffusion method 9. Comparison with path-vector/diffusion method
o Whereas the size of the path-vector increases with the length of o Whereas the size of the path-vector increases with the length of
the LSP, the sizes of the threads are constant. Thus the size the LSP, the sizes of the threads are constant. Thus the size
of messages used by the thread algorithm are unaffected by the of messages used by the thread algorithm are unaffected by the
network size or topology. In addition, the thread merging network size or topology. In addition, the thread merging
capability reduces the number of outstanding messages. These capability reduces the number of outstanding messages. These
lead to improved scalability. lead to improved scalability.
o In the thread algorithm, a node which is changing its next hop o In the thread algorithm, a node which is changing its next hop
for a particular LSP must interact only with nodes that are for a particular LSP must interact only with nodes that are
between it and the LSP egress on the new path. In the between it and the LSP egress on the new path. In the
path-vector algorithm, however, it is necessary for the node to path-vector algorithm, however, it is necessary for the node to
initiate a diffusion computation that involves nodes which do initiate a diffusion computation that involves nodes which do
not lie between it and the LSP egress. not lie between it and the LSP egress.
This characteristic makes the thread algorithm more robust. If This characteristic makes the thread algorithm more robust. If
a diffusion computation is used, misbehaving nodes which aren't a diffusion computation is used, misbehaving nodes which aren't
even in the path can delay the path setup. In the thread even in the path can delay the path setup. In the thread
algorithm, the only nodes which can delay the path setup are algorithm, the only nodes which can delay the path setup are
those nodes which are actually in the path. those nodes which are actually in the path.
o The thread algorithm is well suited for use with both the o The thread algorithm is well suited for use with both the
ordered downstream-on-demand allocation and ordered downstream ordered downstream-on-demand allocation and ordered downstream
allocation. The path-vector/diffusion algorithm, however, is allocation. The path-vector/diffusion algorithm, however, is
tightly coupled with the ordered downstream allocation. tightly coupled with the ordered downstream allocation.
o The thread algorithm is retry-free, achieving quick path o The thread algorithm is retry-free, achieving quick path
(re)configuration. The diffusion algorithm tends to delay the (re)configuration. The diffusion algorithm tends to delay the
path reconfiguration time, since a node at the route change path reconfiguration time, since a node at the route change
point must to consult all its upstream nodes. point must to consult all its upstream nodes.
o In the thread algorithm, the node can continue to use the old o In the thread algorithm, the node can continue to use the old
path if there is an L3 loop on the new path, as in the path if there is an L3 loop on the new path, as in the
path-vector algorithm. path-vector algorithm.
10. Security considerations 10. Security Considerations
The use of the procedures specified in this document does not have The use of the procedures specified in this document does not have
any security impact other than that which may generally be present any security impact other than that which may generally be present
in the use of any MPLS procedures. in the use of any MPLS procedures.
11. Intellectual property considerations 11. Intellectual Property Considerations
Toshiba and/or Cisco may seek patent or other intellectual property Toshiba and/or Cisco may seek patent or other intellectual property
protection for some of the technologies disclosed in this document. protection for some of the technologies disclosed in this document.
If any standards arising from this document are or become protected If any standards arising from this document are or become protected
by one or more patents assigned to Toshiba and/or Cisco, Toshiba by one or more patents assigned to Toshiba and/or Cisco, Toshiba
and/or Cisco intend to disclose those patents and license them on and/or Cisco intend to disclose those patents and license them on
reasonable and non-discriminatory terms. reasonable and non-discriminatory terms.
12. Acknowledgments 12. Acknowledgments
We would like to thank Hiroshi Esaki, Bob Thomas, Eric Gray, and We would like to thank Hiroshi Esaki, Bob Thomas, Eric Gray, and
Joel Halpern for their comments. Joel Halpern for their comments.
13. Authors' Addresses 13. Authors' Addresses
Yoshihiro Ohba Yoshihiro Ohba
Toshiba Corporation Toshiba Corporation
1, Komukai-Toshiba-cho, Saiwai-ku 1, Komukai-Toshiba-cho, Saiwai-ku
Kawasaki 210-8582, Japan Kawasaki 210-8582, Japan
email: yoshihiro.ohba@toshiba.co.jp
EMail: yoshihiro.ohba@toshiba.co.jp
Yasuhiro Katsube Yasuhiro Katsube
Toshiba Corporation Toshiba Corporation
3-1-1, Asahigaoka 1, Toshiba-cho, Fuchu-shi,
Hino 191-8555, Japan Tokyo, 183-8511, Japan
email: yasuhiro.katsube@toshiba.co.jp
EMail: yasuhiro.katsube@toshiba.co.jp
Eric Rosen Eric Rosen
Cisco Systems, Inc. Cisco Systems, Inc.
250 Apollo Drive 250 Apollo Drive
Chelmsford, MA, 01824 Chelmsford, MA, 01824
email: erosen@cisco.com
EMail: erosen@cisco.com
Paul Doolan Paul Doolan
Ennovate Networks Ennovate Networks
330 Codman Hill Rd 330 Codman Hill Rd
Marlborough MA 01719 Marlborough MA 01719
email: pdoolan@ennovatenetworks.com
EMail: pdoolan@ennovatenetworks.com
14. References 14. References
[1] R. Callon, et al., "A Framework for Multiprotocol Label Switching", [1] Callon, R., et al., "A Framework for Multiprotocol Label
Work in Progress, November 1997. Switching", Work in Progress.
[2] B. Davie, et al., "MPLS using LDP and ATM VC Switching", Work in [2] Davie, B., Lawrence, J., McCloghrie, K., Rosen, E., Swallow, G.,
Progress, April 1999. Rekhter, Y. and P. Doolan, "MPLS using LDP and ATM VC Switching",
RFC 3035, January 2001.
[3] E. Rosen, et al., "A Proposed Architecture for MPLS", Work in [3] Rosen, E., et al., "A Proposed Architecture for MPLS", Work in
Progress, April 1999. Progress.
[4] L. Andersson, et al., "Label Distribution Protocol", Work in [4] Andersson, L., Doolan, P., Feldman, N., Fredette, A. and B.
Progress, May 1999. Thomas, "LDP Specification", RFC 3036, January 2001.
Appendix A - Further discussion of the algorithm Appendix A - Further discussion of the algorithm
The purpose of this appendix is to give a more informal and tutorial The purpose of this appendix is to give a more informal and tutorial
presentation of the algorithm, and to provide some of the motivation presentation of the algorithm, and to provide some of the motivation
for it. For the precise specification of the algorithm, the FSM for it. For the precise specification of the algorithm, the FSM
should be taken as authoritative. should be taken as authoritative.
As in the body of the draft, we speak as if there is only one LSP; 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 also otherwise we would always be saying "... of the same LSP". We also
consider only the case where the algorithm is used for loop consider only the case where the algorithm is used for loop
prevention, rather than loop detection. prevention, rather than loop detection.
A.1. Loop Prevention the Brute Force Way A.1. Loop Prevention the Brute Force Way
As a starting point, let's consider an algorithm which we might call As a starting point, let's consider an algorithm which we might call
"loop prevention by brute force". In this algorithm, every path "loop prevention by brute force". In this algorithm, every path
setup attempt must go all the way to the egress and back in order setup attempt must go all the way to the egress and back in order for
for the path to be setup. This algorithm is obviously loop-free, by the path to be setup. This algorithm is obviously loop-free, by
virtue of the fact that the setup messages actually made it to the virtue of the fact that the setup messages actually made it to the
egress and back. egress and back.
Consider, for example, an existing LSP B-C-D-E to egress node E. Consider, for example, an existing LSP B-C-D-E to egress node E. Now
Now node A attempts to join the LSP. In this algorithm, A must send node A attempts to join the LSP. In this algorithm, A must send a
a message to B, B to C, C to D, D to E. Then messages are sent from message to B, B to C, C to D, D to E. Then messages are sent from E
E back to A. The final message, from B to A, contains a label back to A. The final message, from B to A, contains a label binding,
binding, and A can now join the LSP, knowing that the path is and A can now join the LSP, knowing that the path is loop-free.
loop-free.
Using our terminology, we say that A created a thread and extended Using our terminology, we say that A created a thread and extended it
it downstream. The thread reached the egress, and then rewound. downstream. The thread reached the egress, and then rewound.
We needn't assume, in the above example, that A is an ingress node. 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 It can be any node which acquires or changes its next hop for the LSP
LSP in question, and there may be nodes upstream of it which are in question, and there may be nodes upstream of it which are also
also trying to join the LSP. trying to join the LSP.
It is clear that if there is a loop, the thread never reaches the It is clear that if there is a loop, the thread never reaches the
egress, so it does not rewind. What does happen? The path setup egress, so it does not rewind. What does happen? The path setup
messages just keep traveling around the loop. If one keeps a hop messages just keep traveling around the loop. If one keeps a hop
count in them, one can ensure that they stop traveling around the count in them, one can ensure that they stop traveling around the
loop when the hop count reaches a certain maximum value. That is, loop when the hop count reaches a certain maximum value. That is,
when one receives a path setup message with that the maximum hop when one receives a path setup message with that the maximum hop
count value, one doesn't send a path setup message downstream. count value, one doesn't send a path setup message downstream.
How does one recover from this situation of a looping thread? In How does one recover from this situation of a looping thread? In
order for L3 routing to break the loop, some node in the loop MUST order for L3 routing to break the loop, some node in the loop MUST
experience a next hop change. This node will withdraw the thread experience a next hop change. This node will withdraw the thread
from its old next hop, and extend a thread down its new next hop. from its old next hop, and extend a thread down its new next hop. If
If there is no longer a loop, this thread now reaches the egress, there is no longer a loop, this thread now reaches the egress, and
and gets rewound. gets rewound.
A.2. What's Wrong with the Brute Force Method? A.2. What's Wrong with the Brute Force Method?
Consider this example:
A Consider this example:
|
B--D--E
|
C
If A and C both attempt to join the established B-D-E path, then B A
and D must keep state for both path setup attempts, the one from A |
and the one from C. That is, D must keep track of two threads, the B--D--E
A-thread and the C-thread. In general, there may be many more nodes |
upstream of B who are attempting to join the established path, and D C
would need to keep track of them all.
If VC merge is not being used, this isn't actually so bad. Without If A and C both attempt to join the established B-D-E path, then B
VC merge, D really must support one LSP for each upstream node and D must keep state for both path setup attempts, the one from A
anyway. If VC merge is being used, however, supporting an LSP and the one from C. That is, D must keep track of two threads, the
requires only that one keep state for each upstream link. It would A-thread and the C-thread. In general, there may be many more nodes
be advantageous if the loop prevention technique also required that upstream of B who are attempting to join the established path, and D
the amount of state kept by a node be proportional to the number of would need to keep track of them all.
upstream links which the node has, rather than to the number of
nodes which are upstream in the LSP.
Another problem is that if there is a loop, the setup messages keep If VC merge is not being used, this isn't actually so bad. Without
looping. Even though a thread has traversed some node twice, the VC merge, D really must support one LSP for each upstream node
node has no way to tell that a setup message it is currently anyway. If VC merge is being used, however, supporting an LSP
receiving is part of the same thread as some setup message it requires only that one keep state for each upstream link. It would
received in the past. be advantageous if the loop prevention technique also required that
the amount of state kept by a node be proportional to the number of
upstream links which thenode has, rather than to the number of nodes
which are upstream in the LSP.
Can we modify this brute force scheme to eliminate these two Another problem is that if there is a loop, the setup messages keep
problems? We can. To show how to do this, we introduce two looping. Even though a thread has traversed some node twice, the
notions: thread hop count, and thread color. node has no way to tell that a setup message it is currently
receiving is part of the same thread as some setup message it
received in the past.
Can we modify this brute force scheme to eliminate these two
problems? We can. To show how to do this, we introduce two notions:
thread hop count, and thread color.
A.3. Thread Hop Count A.3. Thread Hop Count
Suppose every link in an LSP tree is labeled with the number of hops Suppose every link in an LSP tree is labeled with the number of hops
you would traverse if you were to travel backwards (upstream) from you would traverse if you were to travel backwards (upstream) from
that link to the leaf node which is furthest upstream of the link. that link to the leaf node which is furthest upstream of the link.
For example, the following tree would have its links labeled as For example, the following tree would have its links labeled as
follows: follows:
1 2 1 2
A---B---C K A---B---C K
| | | |
|3 |1 |3 |1
| | | |
| 4 5 | 6 7 | 4 5 | 6 7
D---G---H---I---J D---G---H---I---J
| |
|2 |2
1 | 1 |
E---F E---F
Call these the "link hop counts". Call these the "link hop counts".
Links AB, EF, KH are labeled one, because you can go only one hop Links AB, EF, KH are labeled one, because you can go only one hop
upstream from these links. Links BC, and FD are labeled 2, because upstream from these links. Links BC, and FD are labeled 2, because
you can go 2 hops upstream from these links. Link DG is labeled 4, 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, because it is possible to travel 4 hops upstream from this link, etc.
etc.
Note that at any node, the hop count associated with the downstream Note that at any node, the hop count associated with the downstream
link is one more than the largest of the hop counts associated with link is one more than the largest of the hop counts associated with
the upstream links. the upstream links.
Let's look at a way to maintain these hop counts. 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 order to maintain the link hop counts, we need to carry hop counts
counts in the path setup messages. For instance, a node which has in the path setup messages. For instance, a node which has no
no upstream links would assign a hop count of 1 to its downstream upstream links would assign a hop count of 1 to its downstream link,
link, and would store that value into the path setup messages it and would store that value into the path setup messages it sends
sends downstream. Once the value is stored in a path setup message, downstream. Once the value is stored in a path setup message, we may
we may refer to it has a "thread hop count". refer to it has a "thread hop count".
When a path setup message is received, the thread hop count is When a path setup message is received, the thread hop count is stored
stored as the link hop count of the upstream link over which the as the link hop count of the upstream link over which the message was
message was received. received.
When a path setup message is sent downstream, the downstream link's When a path setup message is sent downstream, the downstream link's
hop count (and the thread hop count) is set to be one more than the hop count (and the thread hop count) is set to be one more than the
largest of the incoming link hop counts. largest of the incoming link hop counts.
Suppose a node N has some incoming links and an outgoing link, with Suppose a node N has some incoming links and an outgoing link, with
hop counts all set properly, and N now acquires a new incoming 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 is If, and only if, the link hop count of the new incoming link is
greater than that of all of the existing incoming links, the greater than that of all of the existing incoming links, the
downstream link hop count must be changed. In this case, control downstream link hop count must be changed. In this case, control
messages must be sent downstream carrying the new, larger thread hop messages must be sent downstream carrying the new, larger thread hop
count. count.
If, on the other hand, N acquires a new incoming link with a link If, on the other hand, N acquires a new incoming link with a link hop
hop count that is less than or equal to the link hop count of all count that is less than or equal to the link hop count of all
existing incoming links, the downstream link hop count remains existing incoming links, the downstream link hop count remains
unchanged, and no messages need be sent downstream. unchanged, and no messages need be sent downstream.
Suppose N loses the incoming link whose hop count was the largest of Suppose N loses the incoming link whose hop count was the largest of
any of the incoming links. In this case, the downstream link hop any of the incoming links. In this case, the downstream link hop
count must be made smaller, and messages need to be sent downstream count must be made smaller, and messages need to be sent downstream
to indicate this. to indicate this.
Suppose we were not concerned with loop prevention, but only with Suppose we were not concerned with loop prevention, but only with the
the maintenance of the hop counts. Then we would adopt the maintenance of the hop counts. Then we would adopt the following
following rules to be used by merge points: rules to be used by merge points:
A.3.1 When a new incoming thread is received, extend it downstream if 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 and only if its hop count is the largest of all incoming threads.
threads.
A.3.2 Otherwise, rewind the thread. A.3.2 Otherwise, rewind the thread.
A.3.3 An egress node would, of course, always rewind the thread. A.3.3 An egress node would, of course, always rewind the thread.
A.4. Thread Color A.4. Thread Color
Nodes create new threads as a result of next hop changes or next hop Nodes create new threads as a result of next hop changes or next hop
acquisitions. Let's suppose that every time a thread is created by acquisitions. Let's suppose that every time a thread is created by a
a node, the node assigns a unique "color" to it. This color is to node, the node assigns a unique "color" to it. This color is to be
be unique in both time and space: its encoding consists of an IP unique in both time and space: its encoding consists of an IP address
address of the node concatenated with a unique event identifier from of the node concatenated with a unique event identifier from a
a numbering space maintained by the node. The path setup messages numbering space maintained by the node. The path setup messages that
that the node sends downstream will contain this color. Also, when the node sends downstream will contain this color. Also, when the
the node sends such a message downstream, it will remember the node sends such a message downstream, it will remember the color, and
color, and this color becomes the color of the downstream link. this color becomes the color of the downstream link.
When a colored message is received, its color becomes the color of When a colored message is received, its color becomes the color of
the incoming link. The thread which consists of messages of a the incoming link. The thread which consists of messages of a
certain color will be known as a thread of that color. 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. When a thread is rewound (and a path set up), the color is removed.
The links become transparent, and we will sometimes speak of an The links become transparent, and we will sometimes speak of an
established LSP as being a "transparent thread". established LSP as being a "transparent thread".
Note that packets cannot be forwarded on a colored link, but only on Note that packets cannot be forwarded on a colored link, but only on
a transparent link. a transparent link.
Note that if a thread loops, some node will see a message, over a Note that if a thread loops, some node will see a message, over a
particular incoming link, with a color that the node has already particular incoming link, with a color that the node has already seen
seen before. Either the node will have originated the thread of before. Either the node will have originated the thread of that
that color, or it will have a different incoming link which already color, or it will have a different incoming link which already has
has that color. This fact can be used to prevent control messages that color. This fact can be used to prevent control messages from
from looping. However, the node would be required to remember the looping. However, the node would be required to remember the colors
colors of all the threads passing through it which have not been of all the threads passing through it which have not been rewound or
rewound or withdrawn. (I.e., it would have to remember a color for withdrawn. (I.e., it would have to remember a color for each path
each path setup in progress.) setup in progress.)
A.5. The Relation between Color and Hop Count A.5. The Relation between Color and Hop Count
By combining the color mechanism and the hop count mechanism, we can By combining the color mechanism and the hop count mechanism, we can
prevent loops without requiring any node to remember more than one prevent loops without requiring any node to remember more than one
color and one hop count per link for each LSP. color and one hop count per link for each LSP.
We have already stated that in order to maintain the hop counts, a We have already stated that in order to maintain the hop counts, a
node needs to extend only the thread which has the largest hop count node needs to extend only the thread which has the largest hop count
of any incoming thread. Now we add the following rule: of any incoming thread. Now we add the following rule:
A.5.1 When extending an incoming thread downstream, that thread's A.5.1 When extending an incoming thread downstream, that thread's
color is also passed downstream (I.e., the downstream link's color is also passed downstream (I.e., the downstream link's color
color will be the same as the color of the upstream link with will be the same as the color of the upstream link with largest hop
largest hop count.) count.)
Note that at a given node, the downstream link is either transparent Note that at a given node, the downstream link is either transparent
or it has one and only one color. or it has one and only one color.
A.5.2 If a link changes color, there is no need to remember the old A.5.2 If a link changes color, there is no need to remember the old
color. color.
We now define the concept of "thread merging": We now define the concept of "thread merging":
A.5.2 Suppose a colored thread arrives at a node over an incoming 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 link, the node already has an incoming thread with the same or larger
larger hop count, and the node has an outgoing colored thread. hop count, and the node has an outgoing colored thread. In this
In this case, we may say that the new incoming thread is case, we may say that the new incoming thread is "merged" into the
"merged" into the outgoing thread. outgoing thread.
Note that when an incoming thread is merged into an outgoing thread, Note that when an incoming thread is merged into an outgoing thread,
no messages are sent downstream. no messages are sent downstream.
A.6. Detecting Thread Loops A.6. Detecting Thread Loops
It can now be shown that if there is a loop, there will always It can now be shown that if there is a loop, there will always either
either be some node which gets two incoming threads of the same be some node which gets two incoming threads of the same color, or
color, or the colored thread will return to its initiator. In this the colored thread will return to its initiator. In this section, we
section, we give several examples that may provide an intuitive give several examples that may provide an intuitive understanding of
understanding of how the thread loops are detected. how the thread loops are detected.
1 2 1 2
A---B---C K A---B---C K
| | | |
|3 |1 |3 |1
| | | |
| 4 5 | 6 7 | 4 5 | 6 7
D---G---H---I---J D---G---H---I---J
| |
|2 |2
1 | 1 |
E---F E---F
Returning to our previous example, let's set what would happen if H Returning to our previous example, let's set what would happen if H
changed its next hop from I to E. H now creates a new thread, and changed its next hop from I to E. H now creates a new thread, and
assigns it a new color, say, red. Since H has two incoming link, assigns it a new color, say, red. Since H has two incoming link,
with hop counts 1 and 5 respectively, it assigns hop count 6 to its with hop counts 1 and 5 respectively, it assigns hop count 6 to its
new downstream link, and attempts a path setup through E. new downstream link, and attempts a path setup through E.
E now has an incoming red thread with hop count 6. Since E's E now has an incoming red thread with hop count 6. Since E's
downstream link hop count is now only 1, it must extend the red downstream link hop count is now only 1, it must extend the red
thread to F, with hop count 7. F then extends the red thread to D thread to F, with hop count 7. F then extends the red thread to D
with hop count 8, D to G with hop count 9, and G to H with hop count with hop count 8, D to G with hop count 9, and G to H with hop count
10. 10.
The red thread has now returned to its initiator, and the loop is The red thread has now returned to its initiator, and the loop is
detected. detected.
Suppose though that before the red thread makes it back to H, G Suppose though that before the red thread makes it back to H, G
changes its next hop from H to E. Then G will extend the red thread changes its next hop from H to E. Then G will extend the red thread
to E. But E already has an incoming red link (from H), so the loop to E. But E already has an incoming red link (from H), so the loop
is detected. is detected.
Let's now define the notion of a "stalled thread". A stalled thread Let's now define the notion of a "stalled thread". A stalled thread
is a thread which is merged into the outgoing thread, even though is a thread which is merged into the outgoing thread, even though the
the outgoing thread has a smaller link hop count. outgoing thread has a smaller link hop count.
When a thread loop is detected, the thread becomes stalled. When a thread loop is detected, the thread becomes stalled.
A.6.1 When a loop is detected due to a thread of a particular color A.6.1 When a loop is detected due to a thread of a particular color
traversing some node twice, we will say that the thread is traversing some node twice, we will say that the thread is "stalled"
"stalled" at the node. More precisely, it is the second at the node. More precisely, it is the second appearance of the
appearance of the thread which is stalled. Note that we say thread which is stalled. Note that we say that a thread is
that a thread is traversing a node twice if the thread is traversing a node twice if the thread is received by that node on an
received by that node on an incoming link, but either there is incoming link, but either there is another incoming link with the
another incoming link with the same color, or the color is one same color, or the color is one that was assigned by the node itself.
that was assigned by the node itself.
A.7. Preventing the Setup of Looping LSPS A.7. Preventing the Setup of Looping LSPS
The mechanism to be used for preventing the setup of looping LSPs The mechanism to be used for preventing the setup of looping LSPs
should now be obvious. If node M is node N's next hop, and N wishes should now be obvious. If node M is node N's next hop, and N wishes
to set up an LSP (or to merge into an LSP which already exists at to set up an LSP (or to merge into an LSP which already exists at M),
M), then N extends a thread to M. then N extends a thread to M.
M first checks to see if the thread forms a loop (see Appendix A.6), M first checks to see if the thread forms a loop (see Appendix A.6),
and if so, the thread is stalled. If not, the following procedure and if so, the thread is stalled. If not, the following procedure is
is followed. followed.
A.7.1 If M receives this thread, and M has a next hop, and either: A.7.1 If M receives this thread, and M has a next hop, and either:
- M has no outgoing thread - M has no outgoing thread
- the incoming thread hop count is larger than the hop count of - the incoming thread hop count is larger than the hop count of all
all other incoming threads, other incoming threads,
then M must extend the thread downstream. then M must extend the thread downstream.
A.7.2 On the other hand, if M receives this thread, and M has a next A.7.2 On the other hand, if M receives this thread, and M has a next
hop and there is another incoming thread with a larger hop hop and there is another incoming thread with a larger hop count,
count, then: then:
A.7.2.1 if the outgoing thread is transparent, M rewinds the new A.7.2.1 if the outgoing thread is transparent, M rewinds the new
incoming thread. incoming thread.
A.7.2.2 if the outgoing thread is colored, M merges the new A.7.2.2 if the outgoing thread is colored, M merges the new incoming
incoming thread into the outgoing thread, but does not thread into the outgoing thread, but does not send any messages
send any messages downstream. downstream.
A.7.3 If M has not already assigned a label to N, it will assign one A.7.3 If M has not already assigned a label to N, it will assign one
when, and only when, M rewinds the thread which N has extended when, and only when, M rewinds the thread which N has extended to it.
to it.
A.7.4 If M merges the new thread into an existing colored outgoing 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 thread, then the new incoming thread will rewind when, and only when,
when, the outgoing thread rewinds. the outgoing thread rewinds.
A.8. Withdrawing Threads A.8. Withdrawing Threads
A.8.1 If a particular node has a colored outgoing thread, and loses or A.8.1 If a particular node has a colored outgoing thread, and loses or
changes its next hop, it withdraws the outgoing thread. changes its next hop, it withdraws the outgoing thread.
Suppose that node N is immediately upstream of node M, and that N Suppose that node N is immediately upstream of node M, and that N has
has extended a thread to M. Suppose further that N then withdraws extended a thread to M. Suppose further that N then withdraws the
the thread. thread.
A.8.2 If M has another incoming thread with a larger hop count, then M A.8.2 If M has another incoming thread with a larger hop count, then M
does not send any messages downstream. does not send any messages downstream.
A.8.3 However, if the withdrawn thread had the largest hop count of A.8.3 However, if the withdrawn thread had the largest hop count of
any incoming thread, then M's outgoing thread will no longer any incoming thread, then M's outgoing thread will no longer have the
have the proper hop count and color. Therefore: proper hop count and color. Therefore:
A.8.3.1 M must now extend downstream the incoming thread with A.8.3.1 M must now extend downstream the incoming thread with the
the largest hop count. (This will cause it to forget largest hop count. (This will cause it to forget the old downstream
the old downstream link hop count and color.) link hop count and color.)
A.8.3.2 The other incoming threads are considered to be merged A.8.3.2 The other incoming threads are considered to be merged into the
into the thread which is extended. thread which is extended.
A.8.4 When the last unstalled incoming thread is withdrawn, the A.8.4 When the last unstalled incoming thread is withdrawn, the
outgoing thread must be withdrawn. outgoing thread must be withdrawn.
A.9. Modifying Hop Counts and Colors of Existing Threads A.9. Modifying Hop Counts and Colors of Existing Threads
We have seen the way in which the withdrawal of a thread may cause We have seen the way in which the withdrawal of a thread may cause
hop count and color changes downstream. Note that if the hop count hop count and color changes downstream. Note that if the hop count
and/or color of an outgoing thread changes, then the hop count and and/or color of an outgoing thread changes, then the hop count and
color of the corresponding incoming thread at the next hop will also color of the corresponding incoming thread at the next hop will also
change. This may result in a color and/or next hop change of the change. This may result in a color and/or next hop change of the
outgoing thread at that next hop. outgoing thread at that next hop.
A.9.1 Whenever there is a hop count change for any incoming thread, a A.9.1 Whenever there is a hop count change for any incoming thread, a
node must determine whether the "largest hop count of any node must determine whether the "largest hop count of any incoming
incoming thread" has changed as a result. If so, the outgoing thread" has changed as a result. If so, the outgoing thread's hop
thread's hop count, and possibly color, will change as well, count, and possibly color, will change as well, causing messages to
causing messages to be sent downstream. be sent downstream.
A.10. When There is No Next Hop A.10. When There is No Next Hop
A.10.1 If a particular node has a colored incoming thread, but has no A.10.1 If a particular node has a colored incoming thread, but has no
next hop (or loses its next hop), the incoming thread is next hop (or loses its next hop), the incoming thread is stalled.
stalled.
A.11. Next Hop Changes and Pre-existing Colored Incoming Threads A.11. Next Hop Changes and Pre-existing Colored Incoming Threads
It is possible that a node will experience a next hop change or a It is possible that a node will experience a next hop change or a
next hop acquisition at a time when it has colored incoming threads. next hop acquisition at a time when it has colored incoming threads.
This happens when routing changes before path setup is complete. This happens when routing changes before path setup is complete.
A.11.1 If a node has a next hop change or a next hop acquisition at a A.11.1 If a node has a next hop change or a next hop acquisition at a
time when it has colored incoming threads, it will create a time when it has colored incoming threads, it will create a thread
thread with a new color, but whose hop count is one more than with a new color, but whose hop count is one more than the largest of
the largest of the incoming link hop counts. It will then the incoming link hop counts. It will then extend this thread
extend this thread downstream. downstream.
A.11.2 When this new thread is created and extended downstream, all A.11.2 When this new thread is created and extended downstream, all
incoming threads are merged into it. Any incoming threads that incoming threads are merged into it. Any incoming threads that were
were previously stalled are now considered to be "merged" rather previously stalled are now considered to be "merged" rather than
than "stalled". "stalled".
That is, even though the outgoing thread has a different color than That is, even though the outgoing thread has a different color than
any of the incoming threads, the pre-existing incoming threads are any of the incoming threads, the pre-existing incoming threads are
all considered to have been merged into the new outgoing thread. all considered to have been merged into the new outgoing thread.
This means that when the outgoing thread rewinds, the incoming This means that when the outgoing thread rewinds, the incoming
threads will too. threads will too.
Note: it is still required to distinguish stalled incoming links Note: it is still required to distinguish stalled incoming links from
from unstalled incoming links when thread withdrawing is performed. unstalled incoming links when thread withdrawing is performed.
A.12. How Many Threads Run Around a Loop? A.12. How Many Threads Run Around a Loop?
We have seen that when a loop is detected, the looping thread We have seen that when a loop is detected, the looping thread stalls.
stalls. However, considering the following topology: However, considering the following topology:
X--->A----->B<---Y X--->A----->B<---Y
^ | ^ |
| v | v
W--->D<-----C<---Z W--->D<-----C<---Z
In this example, there is a loop A-B-C-D-A. However, there are also In this example, there is a loop A-B-C-D-A. However, there are also
threads entering the loop from X, Y, Z, and W. Once the loop is threads entering the loop from X, Y, Z, and W. Once the loop is
detected, there really is no reason why any other thread should have detected, there really is no reason why any other thread should have
to wrap around the loop. It would be better to simply mark presence to wrap around the loop. It would be better to simply mark presence
of the loop in each node. of the loop in each node.
To do this, we introduce the notion of the "unknown" hop count, U. To do this, we introduce the notion of the "unknown" hop count, U.
This hop count value is regarded as being larger than any other hop This hop count value is regarded as being larger than any other hop
count value. A thread with hop count U will be known as a count value. A thread with hop count U will be known as a "U-
"U-thread". thread".
A.12.1 When an incoming thread with a known hop count stalls, and there A.12.1 When an incoming thread with a known hop count stalls, and there
is an outgoing thread, we assign the hop count U to the outgoing is an outgoing thread, we assign the hop count U to the outgoing
thread, and we assign a new color to the outgoing thread as thread, and we assign a new color to the outgoing thread as well.
well.
As a result, the next hop will then have an incoming U-thread, with As a result, the next hop will then have an incoming U-thread, with
the newly assigned color. This causes its outgoing thread in turn the newly assigned color. This causes its outgoing thread in turn to
to be assigned hop count U and the new color. The rules we have be assigned hop count U and the new color. The rules we have already
already given will then cause each link in the loop to be assigned given will then cause each link in the loop to be assigned the new
the new color and the hop count U. When this thread either reaches color and the hop count U. When this thread either reaches its
its originator, or any other node which already has an incoming originator, or any other node which already has an incoming thread of
thread of the same color, it stalls. the same color, it stalls.
In our example above, this will cause the links AB, BC, CD, and DA In our example above, this will cause the links AB, BC, CD, and DA to
to be given hop count U. be given hop count U.
Now let's add one more rule: Now let's add one more rule:
A.12.2 When a thread with a known hop count reaches a node that has a 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 colored outgoing U-thread, the incoming thread merges into the
outgoing thread. (Actually, this is just a consequence of a outgoing thread. (Actually, this is just a consequence of a rule
rule which has already been given, since U is greater than any which has already been given, since U is greater than any known hop
known hop count.) count.)
Then if W, X, Y, or Z attempt to extend a thread to D, A, B, or C Then if W, X, Y, or Z attempt to extend a thread to D, A, B, or C
respectively, those threads will immediately stall. Once all the respectively, those threads will immediately stall. Once all the
links are marked as being within a loop, no other threads are links are marked as being within a loop, no other threads are
extended around the loop, i.e., no other setup messages will extended around the loop, i.e., no other setup messages will traverse
traverse the loop. the loop.
Here is our example topology with the link hop counts that would Here is our example topology with the link hop counts that would
exist during a loop: exist during a loop:
1 U 1 1 U 1
X--->A----->B<---Y X--->A----->B<---Y
^ | ^ |
U | |U U | |U
| v | v
W--->D<-----C<---Z W--->D<-----C<---Z
1 U 1 1 U 1
A.13. Some Special Rules for Hop Count U A.13. Some Special Rules for Hop Count U
When a U-thread encounters a thread with known hop count, the usual When a U-thread encounters a thread with known hop count, the usual
rules apply, remembering that U is larger than any known hop count rules apply, remembering that U is larger than any known hop count
value. value.
However, we need to add a couple of special rules for the case when However, we need to add a couple of special rules for the case when a
a U-thread encounters a U-thread. Since we can't tell which of the U-thread encounters a U-thread. Since we can't tell which of the two
two U-threads is really the longer, we need to make sure that each U-threads is really the longer, we need to make sure that each of the
of the U-threads is extended. U-threads is extended.
A.13.1 If an incoming colored U-thread arrives at a node which already A.13.1 If an incoming colored U-thread arrives at a node which already
has an incoming U-thread of that color, or arrives at the node has an incoming U-thread of that color, or arrives at the node which
which created that U-thread, then the thread stalls. created that U-thread, then the thread stalls.
(Once a loop is detected, there is no need to further extend the (Once a loop is detected, there is no need to further extend the
thread.) thread.)
A.13.2 If an incoming colored U-thread arrives at a node which has a A.13.2 If an incoming colored U-thread arrives at a node which has a
transparent outgoing U-thread to its next hop, the incoming transparent outgoing U-thread to its next hop, the incoming thread is
thread is extended. extended.
A.13.3 If an incoming colored U-thread arrives at a node which has a A.13.3 If an incoming colored U-thread arrives at a node which has a
colored outgoing U-thread, and if the incoming link over which colored outgoing U-thread, and if the incoming link over which the
the thread was received was already an incoming link of the LSP, thread was received was already an incoming link of the LSP, the
the thread is extended. thread is extended.
A.13.4 If an incoming colored U-thread arrives at a node which has a A.13.4 If an incoming colored U-thread arrives at a node which has a
colored outgoing U-thread, and if the incoming link over which colored outgoing U-thread, and if the incoming link over which the
the thread was received was NOT already an incoming link of the thread was received was NOT already an incoming link of the LSP, a
LSP, a new U-thread is created and extended. All the incoming new U-thread is created and extended. All the incoming threads are
threads are merged into it. This is known in the main body of merged into it. This is known in the main body of this document as
this draft as "extending the thread with changing color". "extending the thread with changing color".
These rules ensure that an incoming U-thread is always extended (or These rules ensure that an incoming U-thread is always extended (or
merged into a new U-thread which then gets extended), unless it is merged into a new U-thread which then gets extended), unless it is
already known to form a loop. already known to form a loop.
What is the purpose of rule A.13.4? There are certain cases where a What is the purpose of rule A.13.4? There are certain cases where a
loop can form, but where the node which created the looping thread loop can form, but where the node which created the looping thread is
is not part of the loop. Rule A.13.4 ensures that when there is a not part of the loop. Rule A.13.4 ensures that when there is a loop,
loop, there will be a looping thread which was created by some node there will be a looping thread which was created by some node which
which is actually in the loop. This in turn ensures that the loop is actually in the loop. This in turn ensures that the loop will be
will be detected well before the thread TTL expires. detected well before the thread TTL expires.
The rule of "extending the thread with changing color" is also The rule of "extending the thread with changing color" is also
applied when extending a thread with a known hop count. applied when extending a thread with a known hop count.
A.13.5 When a received colored thread with a known hop count is A.13.5 When a received colored thread with a known hop count is
extended, if the node has an outgoing thread, and if the extended, if the node has an outgoing thread, and if the incoming
incoming link over which the thread was received was NOT already link over which the thread was received was NOT already an incoming
an incoming link of the LSP, a new thread is created and link of the LSP, a new thread is created and extended. All the
extended. All the incoming threads are merged into it. This is incoming threads are merged into it. This is an exceptional case of
an exceptional case of A.5.1. A.5.1.
A.14. Recovering From a Loop A.14. Recovering From a Loop
Here is our example topology again, in the presence of a loop. Here is our example topology again, in the presence of a loop.
1 U 1 1 U 1
X--->A----->B<---Y X--->A----->B<---Y
^ | ^ |
U | |U U | |U
| v | v
W--->D<-----C<---Z W--->D<-----C<---Z
1 U 1 1 U 1
Suppose now that C's next hop changes from D to some other node E, Suppose now that C's next hop changes from D to some other node E,
thereby breaking the loop. For simplicity, we will assume that E is thereby breaking the loop. For simplicity, we will assume that E is
the egress node. the egress node.
C will withdraw its outgoing U-thread from D (9.1). It will also C will withdraw its outgoing U-thread from D (9.1). It will also
create a new thread (12.1), assign it a new color, assign it hop create a new thread (12.1), assign it a new color, assign it hop
count U (the largest hop count of C's incoming threads), merge its count U (the largest hop count of C's incoming threads), merge its
two other incoming threads into the new thread (12.2), and extend two other incoming threads into the new thread (12.2), and extend the
the new thread to E, resulting the following configuration: new thread to E, resulting the following configuration:
1 U 1 1 U 1
X--->A----->B<---Y X--->A----->B<---Y
^ | ^ |
U | |U U | |U
| v | v
W--->D C<---Z W--->D C<---Z
1 | 1 1 | 1
U| U|
v v
E E
When the thread from C to E rewinds, the merged threads also rewind When the thread from C to E rewinds, the merged threads also rewind
(8.4). This process of rewinding can now proceed all the way back (8.4). This process of rewinding can now proceed all the way back to
to the leafs. While this is happening, of course, D will note that the leafs. While this is happening, of course, D will note that its
its outgoing thread hop count should be 2, not U, and will make this outgoing thread hop count should be 2, not U, and will make this
change (9.3). As a result, A will note that its outgoing hop count change (9.3). As a result, A will note that its outgoing hop count
should be 3, not U, and will make this change. So at some time in should be 3, not U, and will make this change. So at some time in
the future, we might see the following: the future, we might see the following:
1 3 1 1 3 1
X--->A----->B<---Y X--->A----->B<---Y
^ | ^ |
2 | |U 2 | |U
| v | v
W--->D C<---Z W--->D C<---Z
1 | 1 1 | 1
U| U|
v v
E E
After a short period, we see the following: After a short period, we see the following:
1 3 1 1 3 1
X--->A----->B<---Y X--->A----->B<---Y
^ | ^ |
2 | |4 2 | |4
| v | v
W--->D C<---Z W--->D C<---Z
1 | 1 1 | 1
5| 5|
v v
E E
with all threads transparent, and we have a fully set up non-looping with all threads transparent, and we have a fully set up non-looping
path. path.
A.15. Continuing to Use an Old Path A.15. Continuing to Use an Old Path
Nothing in the above requires that any node withdraw a transparent Nothing in the above requires that any node withdraw a transparent
thread. Existing transparent threads (established paths) can thread. Existing transparent threads (established paths) can
continue to be used, even while new paths are being set up. continue to be used, even while new paths are being set up.
If this is done, then some node may have both a transparent outgoing If this is done, then some node may have both a transparent outgoing
thread (previous path) and a colored outgoing thread (new path being thread (previous path) and a colored outgoing thread (new path being
set up). This would happen only if the downstream links for the two set up). This would happen only if the downstream links for the two
threads are different. When the colored outgoing thread rewinds threads are different. When the colored outgoing thread rewinds (and
(and becomes transparent), the previous path should be withdrawn. 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.
 End of changes. 339 change blocks. 
1316 lines changed or deleted 1301 lines changed or added

This html diff was produced by rfcdiff 1.41. The latest version is available from http://tools.ietf.org/tools/rfcdiff/