9. Comparison with path-vector/diffusion method
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
of messages used by the thread algorithm are unaffected by the
network size or topology. In addition, the thread merging
capability reduces the number of outstanding messages. These
lead to improved scalability.
o In the thread algorithm, a node which is changing its next hop
for a particular LSP must interact only with nodes that are
between it and the LSP egress on the new path. In the
path-vector algorithm, however, it is necessary for the node to
initiate a diffusion computation that involves nodes which do
not lie between it and the LSP egress.
This characteristic makes the thread algorithm more robust. If
a diffusion computation is used, misbehaving nodes which aren't
even in the path can delay the path setup. In the thread
algorithm, the only nodes which can delay the path setup are
those nodes which are actually in the path.
o The thread algorithm is well suited for use with both the
ordered downstream-on-demand allocation and ordered downstream
allocation. The path-vector/diffusion algorithm, however, is
tightly coupled with the ordered downstream allocation.
o The thread algorithm is retry-free, achieving quick path
(re)configuration. The diffusion algorithm tends to delay the
path reconfiguration time, since a node at the route change
point must to consult all its upstream nodes.
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-vector algorithm.
10. Security Considerations
The use of the procedures specified in this document does not have
any security impact other than that which may generally be present
in the use of any MPLS procedures.
11. Intellectual Property Considerations
Toshiba and/or Cisco may seek patent or other intellectual property
protection for some of the technologies disclosed in this document.
If any standards arising from this document are or become protected
by one or more patents assigned to Toshiba and/or Cisco, Toshiba
and/or Cisco intend to disclose those patents and license them on
reasonable and non-discriminatory terms.
12. Acknowledgments
We would like to thank Hiroshi Esaki, Bob Thomas, Eric Gray, and
Joel Halpern for their comments.
13. Authors' Addresses
Yoshihiro Ohba
Toshiba Corporation
1, Komukai-Toshiba-cho, Saiwai-ku
Kawasaki 210-8582, Japan
EMail: yoshihiro.ohba@toshiba.co.jp
Yasuhiro Katsube
Toshiba Corporation
1, Toshiba-cho, Fuchu-shi,
Tokyo, 183-8511, Japan
EMail: yasuhiro.katsube@toshiba.co.jp
Eric Rosen
Cisco Systems, Inc.
250 Apollo Drive
Chelmsford, MA, 01824
EMail: erosen@cisco.com
Paul Doolan
Ennovate Networks
330 Codman Hill Rd
Marlborough MA 01719
EMail: pdoolan@ennovatenetworks.com
14. References
[1] Callon, R., et al., "A Framework for Multiprotocol Label
Switching", Work in Progress.
[2] Davie, B., Lawrence, J., McCloghrie, K., Rosen, E., Swallow, G.,
Rekhter, Y. and P. Doolan, "MPLS using LDP and ATM VC Switching",
RFC3035, January 2001.
[3] Rosen, E., et al., "A Proposed Architecture for MPLS", Work in
Progress.
[4] Andersson, L., Doolan, P., Feldman, N., Fredette, A. and B.
Thomas, "LDP Specification", RFC3036, January 2001.
Appendix A - Further discussion of the algorithm
The purpose of this appendix is to give a more informal and tutorial
presentation of the algorithm, and to provide some of the motivation
for it. For the precise specification of the algorithm, the FSM
should be taken as authoritative.
As in the body of the document, we speak as if there is only one LSP;
otherwise we would always be saying "... of the same LSP". We also
consider only the case where the algorithm is used for loop
prevention, rather than loop detection.
A.1. Loop Prevention the Brute Force Way
As a starting point, let's consider an algorithm which we might call
"loop prevention by brute force". In this algorithm, every path
setup attempt must go all the way to the egress and back in order for
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
egress and back.
Consider, for example, an existing LSP B-C-D-E to egress node E. Now
node A attempts to join the LSP. In this algorithm, A must send a
message to B, B to C, C to D, D to E. Then messages are sent from E
back to A. The final message, from B to A, contains a label binding,
and A can now join the LSP, knowing that the path is loop-free.
Using our terminology, we say that A created a thread and extended it
downstream. The thread reached the egress, and then rewound.
We needn't assume, in the above example, that A is an ingress node.
It can be any node which acquires or changes its next hop for the LSP
in question, and there may be nodes upstream of it which are also
trying to join the LSP.
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
messages just keep traveling around the loop. If one keeps a hop
count in them, one can ensure that they stop traveling around the
loop when the hop count reaches a certain maximum value. That is,
when one receives a path setup message with that the maximum hop
count value, one doesn't send a path setup message downstream.
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
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. If
there is no longer a loop, this thread now reaches the egress, and
gets rewound.
A.2. What's Wrong with the Brute Force Method?
Consider this example:
A
|
B--D--E
|
C
If A and C both attempt to join the established B-D-E path, then B
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
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
would need to keep track of them all.
If VC merge is not being used, this isn't actually so bad. Without
VC merge, D really must support one LSP for each upstream node
anyway. If VC merge is being used, however, supporting an LSP
requires only that one keep state for each upstream link. It would
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.
Another problem is that if there is a loop, the setup messages keep
looping. Even though a thread has traversed some node twice, the
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
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
that link to the leaf node which is furthest upstream of the link.
For example, the following tree would have its links labeled as
follows:
1 2
A---B---C K
| |
|3 |1
| |
| 4 5 | 6 7
D---G---H---I---J
|
|2
1 |
E---F
Call these the "link hop counts".
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
you can go 2 hops upstream from these links. Link DG is labeled 4,
because it is possible to travel 4 hops upstream from this link, etc.
Note that at any node, the hop count associated with the downstream
link is one more than the largest of the hop counts associated with
the upstream links.
Let's look at a way to maintain these hop counts.
In order to maintain the link hop counts, we need to carry hop counts
in the path setup messages. For instance, a node which has no
upstream links would assign a hop count of 1 to its downstream link,
and would store that value into the path setup messages it sends
downstream. Once the value is stored in a path setup message, we may
refer to it has a "thread hop count".
When a path setup message is received, the thread hop count is stored
as the link hop count of the upstream link over which the message was
received.
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
largest of the incoming link hop counts.
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.
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
downstream link hop count must be changed. In this case, control
messages must be sent downstream carrying the new, larger thread hop
count.
If, on the other hand, N acquires a new incoming link with a link hop
count that is less than or equal to the link hop count of all
existing incoming links, the downstream link hop count remains
unchanged, and no messages need be sent downstream.
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
count must be made smaller, and messages need to be sent downstream
to indicate this.
Suppose we were not concerned with loop prevention, but only with the
maintenance of the hop counts. Then we would adopt the following
rules to be used by merge points:
A.3.1 When a new incoming thread is received, extend it downstream if
and only if its hop count is the largest of all incoming threads.
A.3.2 Otherwise, rewind the thread.
A.3.3 An egress node would, of course, always rewind the thread.
A.4. Thread Color
Nodes create new threads as a result of next hop changes or next hop
acquisitions. Let's suppose that every time a thread is created by a
node, the node assigns a unique "color" to it. This color is to be
unique in both time and space: its encoding consists of an IP address
of the node concatenated with a unique event identifier from a
numbering space maintained by the node. The path setup messages that
the node sends downstream will contain this color. Also, when the
node sends such a message downstream, it will remember the color, and
this color becomes the color of the downstream link.
When a colored message is received, its color becomes the color of
the incoming link. The thread which consists of messages of a
certain color will be known as a thread of that color.
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
established LSP as being a "transparent thread".
Note that packets cannot be forwarded on a colored link, but only on
a transparent link.
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 seen
before. Either the node will have originated the thread of that
color, or it will have a different incoming link which already has
that color. This fact can be used to prevent control messages from
looping. However, the node would be required to remember the colors
of all the threads passing through it which have not been rewound or
withdrawn. (I.e., it would have to remember a color for each path
setup in progress.)
A.5. The Relation between Color and Hop Count
By combining the color mechanism and the hop count mechanism, we can
prevent loops without requiring any node to remember more than one
color and one hop count per link for each LSP.
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
of any incoming thread. Now we add the following rule:
A.5.1 When extending an incoming thread downstream, that thread's
color is also passed downstream (I.e., the downstream link's color
will be the same as the color of the upstream link with largest hop
count.)
Note that at a given node, the downstream link is either transparent
or it has one and only one color.
A.5.2 If a link changes color, there is no need to remember the old
color.
We now define the concept of "thread merging":
A.5.2 Suppose a colored thread arrives at a node over an incoming
link, the node already has an incoming thread with the same or larger
hop count, and the node has an outgoing colored thread. In this
case, we may say that the new incoming thread is "merged" into the
outgoing thread.
Note that when an incoming thread is merged into an outgoing thread,
no messages are sent downstream.
A.6. Detecting Thread Loops
It can now be shown that if there is a loop, there will always either
be some node which gets two incoming threads of the same color, or
the colored thread will return to its initiator. In this section, we
give several examples that may provide an intuitive understanding of
how the thread loops are detected.
1 2
A---B---C K
| |
|3 |1
| |
| 4 5 | 6 7
D---G---H---I---J
|
|2
1 |
E---F
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
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
new downstream link, and attempts a path setup through E.
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
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
10.
The red thread has now returned to its initiator, and the loop is
detected.
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
to E. But E already has an incoming red link (from H), so the loop
is detected.
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 the
outgoing thread has a smaller link hop count.
When a thread loop is detected, the thread becomes stalled.
A.6.1 When a loop is detected due to a thread of a particular color
traversing some node twice, we will say that the thread is "stalled"
at the node. More precisely, it is the second appearance of the
thread which is stalled. Note that we say that a thread is
traversing a node twice if the thread is received by that node on an
incoming link, but either there is another incoming link with the
same color, or the color is one that was assigned by the node itself.
A.7. 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
to set up an LSP (or to merge into an LSP which already exists at M),
then N extends a thread to M.
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 is
followed.
A.7.1 If M receives this thread, and M has a next hop, and either:
- M has no outgoing thread
- the incoming thread hop count is larger than the hop count of all
other incoming threads,
then M must extend the thread downstream.
A.7.2 On the other hand, if M receives this thread, and M has a next
hop and there is another incoming thread with a larger hop count,
then:
A.7.2.1 if the outgoing thread is transparent, M rewinds the new
incoming thread.
A.7.2.2 if the outgoing thread is colored, M merges the new incoming
thread into the outgoing thread, but does not send any messages
downstream.
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 to it.
A.7.4 If M merges the new thread into an existing colored outgoing
thread, then the new incoming thread will rewind when, and only when,
the outgoing thread rewinds.
A.8. Withdrawing Threads
A.8.1 If a particular node has a colored outgoing thread, and loses or
changes its next hop, it withdraws the outgoing thread.
Suppose that node N is immediately upstream of node M, and that N has
extended a thread to M. Suppose further that N then withdraws the
thread.
A.8.2 If M has another incoming thread with a larger hop count, then M
does not send any messages downstream.
A.8.3 However, if the withdrawn thread had the largest hop count of
any incoming thread, then M's outgoing thread will no longer have the
proper hop count and color. Therefore:
A.8.3.1 M must now extend downstream the incoming thread with the
largest hop count. (This will cause it to forget the old downstream
link hop count and color.)
A.8.3.2 The other incoming threads are considered to be merged into the
thread which is extended.
A.8.4 When the last unstalled incoming thread is withdrawn, the
outgoing thread must be withdrawn.
A.9. Modifying Hop Counts and Colors of Existing Threads
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
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
change. This may result in a color and/or next hop change of the
outgoing thread at that next hop.
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 incoming
thread" has changed as a result. If so, the outgoing thread's hop
count, and possibly color, will change as well, causing messages to
be sent downstream.
A.10. When There is No Next Hop
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 stalled.
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
next hop acquisition at a time when it has colored incoming threads.
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
time when it has colored incoming threads, it will create a thread
with a new color, but whose hop count is one more than the largest of
the incoming link hop counts. It will then extend this thread
downstream.
A.11.2 When this new thread is created and extended downstream, all
incoming threads are merged into it. Any incoming threads that were
previously stalled are now considered to be "merged" rather than
"stalled".
That is, even though the outgoing thread has a different color than
any of the incoming threads, the pre-existing incoming threads are
all considered to have been merged into the new outgoing thread.
This means that when the outgoing thread rewinds, the incoming
threads will too.
Note: it is still required to distinguish stalled incoming links from
unstalled incoming links when thread withdrawing is performed.
A.12. How Many Threads Run Around a Loop?
We have seen that when a loop is detected, the looping thread stalls.
However, considering the following topology:
X--->A----->B<---Y
^ |
| v
W--->D<-----C<---Z
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
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
of the loop in each node.
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
count value. A thread with hop count U will be known as a "U-
thread".
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
thread, and we assign a new color to the outgoing thread as well.
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 to
be assigned hop count U and the new color. The rules we have already
given will then cause each link in the loop to be assigned the new
color and the hop count U. When this thread either reaches its
originator, or any other node which already has an incoming thread of
the same color, it stalls.
In our example above, this will cause the links AB, BC, CD, and DA to
be given hop count U.
Now let's add one more rule:
A.12.2 When a thread with a known hop count reaches a node that has a
colored outgoing U-thread, the incoming thread merges into the
outgoing thread. (Actually, this is just a consequence of a rule
which has already been given, since U is greater than any known hop
count.)
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
links are marked as being within a loop, no other threads are
extended around the loop, i.e., no other setup messages will traverse
the loop.
Here is our example topology with the link hop counts that would
exist during a loop:
1 U 1
X--->A----->B<---Y
^ |
U | |U
| v
W--->D<-----C<---Z
1 U 1
A.13. Some Special Rules for Hop Count U
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
value.
However, we need to add a couple of special rules for the case when a
U-thread encounters a U-thread. Since we can't tell which of the two
U-threads is really the longer, we need to make sure that each of the
U-threads is extended.
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 which
created that U-thread, then the thread stalls.
(Once a loop is detected, there is no need to further extend the
thread.)
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 thread is
extended.
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 the
thread was received was already an incoming link of the LSP, the
thread is extended.
A.13.4 If an incoming colored U-thread arrives at a node which has a
colored outgoing U-thread, and if the incoming link over which the
thread was received was NOT already an incoming link of the LSP, a
new U-thread is created and extended. All the incoming threads are
merged into it. This is known in the main body of this document as
"extending the thread with changing color".
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
already known to form a loop.
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 is
not part of the loop. Rule A.13.4 ensures that when there is a loop,
there will be a looping thread which was created by some node which
is actually in the loop. This in turn ensures that the loop will be
detected well before the thread TTL expires.
The rule of "extending the thread with changing color" is also
applied when extending a thread with a known hop count.
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 incoming
link over which the thread was received was NOT already an incoming
link of the LSP, a new thread is created and extended. All the
incoming threads are merged into it. This is an exceptional case of
A.5.1.
A.14. Recovering From a Loop
Here is our example topology again, in the presence of a loop.
1 U 1
X--->A----->B<---Y
^ |
U | |U
| v
W--->D<-----C<---Z
1 U 1
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
the egress node.
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
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 the
new thread to E, resulting the following configuration:
1 U 1
X--->A----->B<---Y
^ |
U | |U
| v
W--->D C<---Z
1 | 1
U|
v
E
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 to
the leafs. While this is happening, of course, D will note that its
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
should be 3, not U, and will make this change. So at some time in
the future, we might see the following:
1 3 1
X--->A----->B<---Y
^ |
2 | |U
| v
W--->D C<---Z
1 | 1
U|
v
E
After a short period, we see the following:
1 3 1
X--->A----->B<---Y
^ |
2 | |4
| v
W--->D C<---Z
1 | 1
5|
v
E
with all threads transparent, and we have a fully set up non-looping
path.
A.15. Continuing to Use an Old Path
Nothing in the above requires that any node withdraw a transparent
thread. Existing transparent threads (established paths) can
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
thread (previous path) and a colored outgoing thread (new path being
set up). This would happen only if the downstream links for the two
threads are different. When the colored outgoing thread rewinds (and
becomes transparent), the previous path should be withdrawn.
Full Copyright Statement
Copyright (C) The Internet Society (2001). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Acknowledgement
Funding for the RFCEditor function is currently provided by the
Internet Society.