The MPLS WG Archive[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index][Thread Index][Author Index][Subject Index] Colored thread loop prevention
# $Id: loops_explanation.txt,v 1.4 1998/09/15 14:13:48 erosen Exp $
Since a number of folks have complained that the color/thread algorithm is
hard to understand, I'd like to see if I can give a fairly intuitive
explanation of it.
I have tried to explicitly call out and number all the rules, but have not
provided a state machine.
1. A FEW BASIC DEFINITIONS
Let's start with a few basic definitions just so that we can use certain
terms without confusion.
LSP
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 the architecture document.
Incoming Link, Upstream Link
Outgoing Link, Downstream Link
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 really an
abstract relationship with an "adjacent" LSR; it is an "edge" in the
"tree", and not necessarily a particular concrete entity like an
"interface".
Virtual Incoming Link
A node N is considered to have a virtual incoming link for a particular
LSP if it is capable of forwarding traffic on that LSP even if the
traffic was not delivered to it by any other LSR. (For example, the
node may be "directly attached" to some hosts, or it may itself generate
control or management traffic, and some such traffic is forwarded on the
LSP.)
Next Hop Change
At node N, the next hop for FEC F changes from node A to node B, where A
is different than B.
Next Hop Acquisition
Node N thought that FEC F was unreachable, but now has a next hop for
it.
Next Hop Loss
Node N thought that node A was the next hop for FEC F, but now no longer
has a next hop for FEC F.
Thread
Extending a Thread
Rewinding a Thread
Withdrawing a Thread
The sequence of messages used to set up an LSP, in the
"downstream-on-demand" (ingress-initiated ordered control) style.
For example, in conventional ATM path setup (without MPLS), the ingress
node creates a thread, and "extends" it along a path to the egress node.
When the thread reaches the egress node, it "rewinds". When it rewinds
all the way back to the ingress node, the path setup is complete.
One often thinks of path setup as requiring "setup" messages to be sent
from ingress to egress, and "acknowledgment" messages to be sent from
egress back to ingress. The transmission of the setup messages is the
"extension" of the thread; the transmission of the acknowledgment
messages is the "rewinding" of the thread.
In MPLS/ATM, any node in an LSP which has a next hop change or next hop
acquisition for that LSP can initiate a new path setup; path setups do
not always begin from the ingress. In this case, we say that the node
which had the next hop change or acquisition is creating the thread, and
extending it downstream.
In MPLS/ATM, we do not necessarily require that a thread, once created,
be extended to the egress. When VC merge is supported, a thread can
sometimes be rewound when it reaches a merge point.
It is possible for a node to tear down a path. A node tears down the
portion of the path downstream of itself by sending teardown messages
to its next hop. This process is known as "withdrawing a thread".
For example, suppose a node is trying to set up a path, and then
experiences a next hop change or a next hop loss. It will withdraw the
thread that it had extended down its old next hop.
When a thread is withdrawn, the teardown messages will travel exactly as
far downstream as was traveled by the setup messages that they are
canceling.
One more bit of terminology. In the following, we will speak as if there
were only a single LSP being set up in the network. This allows us to talk
of incoming and outgoing links without constantly saying something like "for
the same LSP".
2. LOOP PREVENTION THE BRUTE FORCE WAY
As a starting point, let's consider an algorithm which was first suggested
to me by Loa Andersson. 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
travelling around the loop. If one keeps a hop count in them, one can
ensure that they stop travelling 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.
3. WHY NOT USE 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 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
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.
4. 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
(other than the virtual upstream link) 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:
4.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.
4.2 Otherwise, rewind the thread.
4.3 An egress node would, of course, always rewind the thread.
5. 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 colorless, and we will sometimes speak of an established LSP as
being a "colorless thread".
Note that packets cannot be forwarded on a colored link, but only on a
colorless 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.)
6. 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:
6.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 colorless or it has
one and only one color.
6.2 If a link changes color, there is no need to remember the old color.
We now define the concept of "thread merging":
6.2 Suppose a colored thread arrives at a node over an incoming link, the
node already has an incoming thread with a 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.
7. 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.
A proof is sketched later on; 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 not
extended downstream, but it also is not merged into any outgoing thread.
When a thread loop is detected, the thread becomes stalled.
7.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.
8. 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.
8.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.
8.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:
8.2.1 if the outgoing thread is colorless, M rewinds the new incoming
thread
8.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.
8.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.
8.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.
9. WITHDRAWING THREADS
9.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.
9.2 If M has another incoming thread with a larger hop count, then M does
not send any messages downstream.
9.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:
9.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.)
9.3.2 The other incoming threads are considered to be merged into the
thread which is extended.
9.4 When the last incoming thread (including the virtual incoming thread) is
withdrawn, the outgoing thread must be withdrawn.
10. 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.
10.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.
11. WHEN THERE IS NO NEXT HOP
11.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.
12. 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.
12.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.
12.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.
13. 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".
13.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:
13.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
14. 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 in turn.
14.1 If an incoming colored U-thread arrives at a node which has a colorless
outgoing U-thread to its next hop, the incoming thread is extended.
In this case, the outgoing thread has already been extended and rewound, so
the incoming thread should be extended.
14.2 If an incoming colored U-thread arrives at a node which has a colored
outgoing U-thread, the incoming thread is stalled (NOT merged).
In this case, the outgoing thread has already been extended; the incoming
thread will be extended when the outgoing thread rewinds.
15. 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
where the paths YBCE and ZCE are already set up (i.e., colorless, because
the thread has rewound from the egress to C, Z, B, and Y), but with unknown
hop counts. The threads from X and W are still colored, though with known
hop counts. At this point, B rewinds it incoming thread to A, and also sets
its outgoing hop count to 4. 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 colorless, and we have a fully set up non-looping path.
16. CONTINUING TO USE AN OLD PATH
Nothing in the above requires that any node withdraw a colorless thread.
Existing colorless 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 colorless outgoing thread
and a colored outgoing thread. This would happen only if the downstream
links for the two threads are different.
17. THREAD TTL
Unfortunately, there are pathological cases in which two colored threads
(say, red and green) can chase each other around in a loop, with constantly
increasing hop count. A given node will at some time have a red incoming
thread and a red outgoing thread. Then the incoming thread turns green, and
the outgoing thread turns green. Then the incoming thread turns red, and
the outgoing thread turns red. Etc., etc.
This cycle would be broken if the incoming interface ever had a second
successive change of color before the message announcing the first change of
color was sent downstream. The cycle would also be broken if any of the
nodes in the loop had a second incoming link of the same color, or if any of
the nodes in the loop was the creator of that color.
To avoid infinite looping of control messages in such cases, a thread TTL is
used. When a node creates a thread, it sets a TTL, and the TTL is carried
in the message and decremented at each hop. When the TTL reaches 0, the
thread stalls.
18. EGRESS CONTROL
How does this apply to ordered control egress-initiated LSP setup (using VC
merge)?
In that paradigm, when a node changes its next hop or acquires a next hop,
it send a message downstream, just as in downstream-on-demand. If the next
hop has an outgoing thread (colored or colorless), the procedures are then
exactly the same as given above.
If the next hop does not have an outgoing thread, then the current node does
not attempt path setup immediately. Rather, it waits until the next hop
tells it to do so.
When it hears from the next hop, it should immediately begin the path setup
procedure (just like downstream-on-demand) if it has incoming links (other
than the virtual incoming link). Otherwise, it should delay for a fixed
amount of time before initiating the path setup. (Of course, it should also
pass the information about the existence of a route upstream in the normal
egress-control way.) The timer should be canceled if an incoming thread is
received, or if the node determines that it is a true leaf on the LSP.
This procedure will give upstream nodes an opportunity to initiate path
setup before the current node does so. This can result in an increase in
efficiency. Since this is merely a heuristic optimization, the use of the
timer is optional. It is also possible to achieve the effect by use of a
single timer, rather than one per LSP.
19. PROOFS
In this draft, just sketches.
19.1 An LSP with a loop cannot be established. That is, there can be no
cycle of colorless links.
Case 1: Assume a cycle of colorless links with known hop counts.
A reductio ad absurdum is given in the i-d.
Case 2: Assume a cycle of colorless links with at least one link having the
unknown hop count.
Lemma: A colorless link can never acquire the unknown hop count without
also acquiring a color.
Lemma: A colored link with unknown hop count can become a colorless
(without first transitioning to a new color) only if one of the
following two situations obtains:
a) it is an incoming link of the egress node
b) it is part of a thread which has been merged into an outgoing
U-thread, and that outgoing U-thread rewinds.
In case a there is obviously no loop, so let's look at case b.
Suppose a red U-thread is merged into a green U-thread, and the
green one rewinds. In order for the red thread to be merged into
the green one, the green thread must have been present at the
merge point before the red one. Since the green thread rewound,
we know that it did not encounter any colored U-threads;
otherwise it would have stalled. If there is a loop between the
green thread and the red thread, then when the green thread was
extended, it would have to have encountered another U-thread,
either the red thread itself or some other colored thread between
them. Therefore in case b, there is no loop.
19.2 If there is no loop, an LSP will be established.
In the absence of a loop, no thread ever stalls. Every incoming thread
is either merged or extended. Some thread will be extended all the way
to the egress, and will rewind. As it rewinds, all the merged threads
rewind.
19.3 A stalled thread eventually is either withdrawn, extended, or merged.
If stalled due to a loop, eventually some node in the loop must
withdraw the thread due to a next hop change or loss.
If a U-thread is stalled because it encountered a colored U-thread,
then it will extend when the colored U-thread it encountered is
withdrawn or rewound. So the only case we need to worry about is the
case where a sequence of colored U-threads forms a loop, such that each
U-thread is stalled waiting for the next one to rewind.
However, this can only happen if there is a routing loop. When the
loop is broken by L3 routing, some node in the loop will withdraw its
outgoing thread, and merge the incoming threads into a new outgoing
thread. If no further loop is encountered, this outgoing thread will
rewind, causing the incoming threads to rewind.
|
|