📄 rfc3063.txt
字号:
colors no longer exist. As a result, the yellow and green threads
would chase each other forever in the loop.
Ohba, et al. Experimental [Page 18]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
However, since we have the "extending with changing color" mechanism,
this does not actually happen. When a green thread is received at
R2, R2 extends the thread with changing color, i.e., creates a new
red thread and extends it. Similarly, when a yellow thread is
received at R1, R1 creates a new purple thread and extends it. Thus,
the thread loop is detected even after node G and node Y withdraw
threads. This ensures that a thread is extended around 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"
mechanism cannot treat, that is, the "self-chasing" in which thread
extending and thread withdrawing with regard to the same thread chase
each other in a loop. This case would happen when a node withdraw a
thread immediately after extending it into an L3 loop.
A heuristics for self-chasing is to delay the execution of thread
withdrawing at an initiating node of the thread withdrawing. Anyway,
the thread TTL mechanism can eliminate any kind of thread looping.
7. Loop prevention examples
In this section, we show two examples to show how the algorithm can
prevent LSP loops in given networks.
We assume that the ordered downstream-on-demand allocation is
employed, that all the LSPs are with regard to the same FEC, and that
all nodes are VC-merge capable.
7.1. First example
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
node. Now leaf nodes R1 and R6 initiate creation of an LSP.
R11 ------- R10 <-------------------- R9
| | ^
| | |
| | |
v v |
R1 -------> R2 --------> R3 --------> R4 --------- R5
[leaf] ^
|
|
|
R6 -------> R7 --------> R8
[leaf]
Fig. 14 Example MPLS network (1)
Ohba, et al. Experimental [Page 19]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
Assume that R1 and R6 send a label request message at the same time,
and that the initial thread TTL is 255. First we show an example of
how to prevent LSP loops.
A set of thread attributes is represented by (color, hop count, TTL).
The request from R1 and R6 contains (re,1,255) and (bl,1,255),
respectively.
Assume that R3 receives the request originated from R1 before
receiving the request originated from R6. When R3 receives the first
request with red thread, R3 forwards it with (re,3,253) without
changing thread color, since both the receiving incoming link and the
outgoing link are newly created. Then R3 receives the second request
with blue thread. In this time, the outgoing link is already exists.
Thus, R3 performs thread extending with changing color, i.e., creates
a new brown thread and forwards the request with (br,4,255).
When R2 receives the request from R10 with (re,6,250), it finds that
the red thread forms a loop, and stalls the red thread. Then, R2
creates a purple thread of hop count unknown and extends it
downstream by sending a request with (pu,U,255) to R3, where "U"
represents "unknown".
After that, R2 receives another request from R10 with (br,7,252).
The brown thread is merged into purple thread. R2 sends no request
to R3.
On the other hand, the purple thread goes round without changing
color through existing links, and R2 finds the thread loop and stalls
the purple thread. Since the received thread hop count is unknown,
no thread is created any more. In this case no thread rewinding
occurs. The current state of the network is shown in Fig.15.
Ohba, et al. Experimental [Page 20]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
*: location of thread stalling
(pu,U)
R11 ------- R10 <-------------------- R9
| | ^
| |(pu,U)* |
| | |(pu,U)
v v |
R1 -------> R2 --------> R3 --------> R4 --------- R5
[leaf] (re,1) (pu,U) ^ (pu,U)
|
| (bl,3)
|
R6 -------> R7 --------> R8
[leaf] (bl,1) (bl,2)
Fig.15 The network state
Then R10 changes its next hop from R2 to R11.
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
the purple thread. Next, it creates a green thread of hop count
unknown and sends a request with (gr,U,255) to R11.
When R2 receives the teardown message from R10, R2 removes the
stalled incoming link between R10 and R2.
On the other hand, the green thread reaches R1 and Hmax is updated
from zero to unknown. In this case, R1 performs thread extending
with changing color since the thread is received on a new incoming
link but extended on the already existing outgoing link. As a
result, R1 creates an orange thread of hop count unknown and extend
it to R2.
The orange thread goes round through existing links without changing
color, and finally it is stalled at R1.
The state of the network is now shown in Fig.16.
Ohba, et al. Experimental [Page 21]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
*: location of thread stalling
(or,U) (or,U)
R11 <------ R10 <-------------------- R9
| | ^
|(or,U)* | |
| | |(or,U)
v | |
R1 -------> R2 --------> R3 --------> R4 --------- R5
[leaf] (or,U) (or,U) ^ (or,U)
|
| (bl,3)
|
R6 -------> R7 --------> R8
[leaf] (bl,1) (bl,2)
Fig.16 The network state
Then R4 changes its next hop from R9 to R5.
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
old route. Next, it creates a yellow thread of hop count unknown,
and sends a request message with (ye,U,255) to R5.
Since R5 is the egress node, the yellow thread rewinding starts. R5
returns a label mapping message. The thread rewinding procedure is
performed at each node, as the label mapping message is returned
upstream hop-by-hop.
If R1 receives a label mapping message before receiving the orange
thread's withdrawal from R11, R1 returns a label mapping message to
R11. On receiving the orange thread's withdrawal, R1 will create a
transparent thread and extend it by sending an update message with
(tr,1,255) in order to notify downstream of the known hop count.
Otherwise, if R1 receives the orange thread's withdrawal before
receiving a label mapping message, R1 removes the stalled incoming
orange link and waits for rewinding of the outgoing orange thread.
Finally, when R1 receives a label mapping message from R2, it creates
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
established and every node obtains the correct link hop count. The
final network state is shown in Fig.17.
Ohba, et al. Experimental [Page 22]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
R11 <------ R10 <-------------------- R9
| | |
| | |
| | |
v | |
R1 -------> R2 --------> R3 --------> R4 --------> R5
[leaf] (tr,1) (tr,2) ^ (tr,4) (tr,5)
|
| (tr,3)
|
R6 -------> R7 --------> R8
[leaf] (tr,1) (tr,2)
Fig.17 The final network state
7.2. Second example
+----- R6----> R7-----+
| |
| v
R1---->R2 R4----->R5
| ^
| |
+--------->R3---------+
Fig.18 Example MPLS network (2)
Assume that in Fig.18, there is an established LSP R1->R2->R3->R4-
>R5, and the next hop changes at R2 from R3 to R6. R2 sends a
request to R6 with a red thread (re,2,255). When the request with
(re,4,253) reaches R4, it extends the thread to R5 with changing
color. Thus, a new green thread is created at R4 and extended to R5
by sending an update message with (gr,5,255).
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
code) for the update. When R4 receives the ack for the update, it
returns a label mapping message to R7.
When R2 receives the label mapping message on the new route, it sends
a teardown message to R3. When R4 receives the teardown message, it
does not sends an update to R5 since Hmax does not change. Now an
established LSP R1->R2->R6->R7->R4->R5 is obtained.
Then, the next hop changes again at R2 from R6 to R3.
Ohba, et al. Experimental [Page 23]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
R2 sends a request with a blue thread (bl,2,255) to R3. R3 forwards
the request with (bl,3,254) to R4.
When R4 receives the request, it immediately returns a label mapping
message to R3 since Hmax does not change.
When R2 receives the label mapping message on the new route, it sends
a teardown message to R6. The teardown message reaches R4,
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
hop count to 4 without returning an ack.
8. Thread control block
A thread control block (TCB) is maintained per LSP at each node and
may contain the following information:
- FEC
- State
- Incoming links
Each incoming link has the following attributes:
o neighbor: upstream neighbor node address
o color: received thread color
o hop count: received thread hop count
o label
o S-flag: indicates a stalled link
- Outgoing links
Each outgoing link has the following attributes:
o neighbor: downstream neighbor node address
o color: received thread color
o hop count: received thread hop count
o label
o C-flag: indicates the link to the current next hop
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
the thread without entering the FSM. An error message may be
returned to the sender.
Whenever a thread is received on an incoming link, the following
actions are taken before entering the FSM: (1) Store the received
thread color and hop count on the link, replacing the old thread
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -