📄 rfc3063.txt
字号:
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).
Ohba, et al. Experimental [Page 24]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
o Color flag (CL-flag):
Set if the received thread is colored.
o Loop flag (LP-flag):
Set if the received thread forms a loop.
o Arrived on new link flag (NL-flag):
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
receiving link, which stores the same thread color as the received
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 and the receiving TCB is the same, otherwise, the two
TCBs are different.
Before performing a thread extending, the thread TTL is decremented
by one. If the resulting TTL becomes zero, the thread is not
extended but silently discarded. Otherwise, the thread is extended
and the extended thread hop count and color are stored into the
outgoing link.
When a node receives a thread rewinding event, if the received thread
color and the extending thread color are different, it discards the
event without entering the FSM.
8.1. Finite state machine
An event which is "scheduled" by an action in an FSM must be passed
immediately after the completion of the action.
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 value
reserved for unknown hop count plus 1. For example, if
Hmax=unknown=255, the value (Hmax+1) becomes 256.
A TCB has three states; Null, Colored, and Transparent. When a TCB
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 flag value "1" represents the flag is set, "0" represents the
flag is not set, and "*" means the flag value is either 1 or 0.
Ohba, et al. Experimental [Page 25]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
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
Recv thread
Flags
CL LP NL
0 * * Do nothing. No change
1 0 * If the node is egress, start thread rewinding Transparent
and change the color of the receiving link to
transparent.
Otherwise, extend the received thread without Colored
changing color.
1 1 * Stall the received thread; if Hrec<unknown, No change
schedule "Reset to unknown" event for the
detecting TCB.
Next hop If eligible-leaf, create a colored thread and Colored
acquisition extend it.
Others Silently ignore the event. No change
State Colored:
Event Action New state
Recv thread
Flags
CL LP NL
0 * * If Hmax+1<Hout<unknown, create a colored No change
thread and extend it. Otherwise, do nothing.
1 0 * If Hmax<Hout, merge the received thread. No change
Otherwise, extend the thread with (if NL=1)
or without (if NL=0) changing color.
1 1 * Stall the received thread.
If Ni=0 and the node is not an eligible leaf, Null
initiate thread withdrawing.
If Ni>0 and Hrec<unknown, schedule "Reset to No change
unknown" event for the detecting TCB.
Otherwise, do nothing. No change
Ohba, et al. Experimental [Page 26]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
Rewound Propagate thread rewinding to previous hops Transparent
that are extending a colored thread; change
the colors stored in all incoming and outgoing
links to transparent; if Hmax+1<Hout, extend
transparent thread. Withdraw the thread on
the outgoing link for which C-flag=0.
Withdrawn Remove the corresponding incoming link.
If Ni=0 and the node is not an eligible leaf, Null
propagate thread withdrawing to all next hops.
Otherwise, if Hmax+1<Hout<unknown, create No change
a colored thread and extend it.
Otherwise, do nothing. No change
Next hop If there is already an outgoing link for the Transparent
acquisition next hop, do nothing. (This case happens only
when the node retains the old path.)
Otherwise, create a colored thread and extend No change
it.
Next hop If the outgoing link is transparent and the No change
loss node is allowed to retain the link and the
next hop is alive, do nothing.
Otherwise, take the following actions.
Initiate thread withdrawing for the next hop;
if the node becomes a new egress, schedule
"Rewound" event for this TCB.
If Ni=0, move to Null. Null
Otherwise, do nothing. No change
Reset to Create a colored thread of hop count unknown No change
unknown and extend it.
Others Silently ignore the event. No change
State Transparent:
Event Action New state
Recv thread
Flags
CL LP NL
0 * * If Hmax+1<Hout, extend a transparent thread. No change
1 0 * If the node is egress or if Hmax<Hout, change No change
the color of the receiving link to transparent
and start thread rewinding.
Otherwise, extend the thread with (if NL=1) Colored
or without (if NL=0) changing color.
Ohba, et al. Experimental [Page 27]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
Withdrawn Remove the corresponding incoming link.
If Ni=0 and the node is not an eligible leaf, Null
propagate thread withdrawing to next hops.
Otherwise, if Hmax+1<Hout, create No change
a transparent thread and extend it.
Otherwise, do nothing. No change
Next hop Create a colored thread and extend it. Colored
acquisition
Next hop If the node is allowed to retain the outgoing No change
loss link and the next hop is alive, do nothing.
Otherwise, take the following actions.
Initiate thread withdrawing.
If Ni=0, move to Null. Null
Otherwise, do nothing. No change
Others Silently ignore the event. No change
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.
Ohba, et al. Experimental [Page 28]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
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.
Ohba, et al. Experimental [Page 29]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
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] ⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -