📄 rfc3063.txt
字号:
Network Working Group Y. Ohba
Request for Comments: 3063 Y. Katsube
Category: Experimental Toshiba
E. Rosen
Cisco Systems
P. Doolan
Ennovate Networks
February 2001
MPLS Loop Prevention Mechanism
Status of this Memo
This memo defines an Experimental Protocol for the Internet
community. It does not specify an Internet standard of any kind.
Discussion and suggestions for improvement are requested.
Distribution of this memo is unlimited.
Copyright Notice
Copyright (C) The Internet Society (2001). All Rights Reserved.
Abstract
This paper presents a simple mechanism, based on "threads", which can
be used to prevent Multiprotocol Label Switching (MPLS) from setting
up label switched path (LSPs) which have loops. The mechanism is
compatible with, but does not require, VC merge. The mechanism can
be used with either the ordered downstream-on-demand allocation or
ordered downstream allocation. The amount of information that must
be passed in a protocol message is tightly bounded (i.e., no path-
vector is used). When a node needs to change its next hop, a
distributed procedure is executed, but only nodes which are
downstream of the change are involved.
Ohba, et al. Experimental [Page 1]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
Table of Contents
1 Introduction .......................................... 2
2 Basic definitions ..................................... 3
3 Thread basics ......................................... 5
3.1 Thread attributes ..................................... 5
3.2 Thread loop ........................................... 7
3.3 Primitive thread actions .............................. 7
3.4 Examples of primitive thread actions ................. 10
4 Thread algorithm ...................................... 14
5 Applicability of the algorithm ........................ 14
5.1 LSP Loop prevention/detection ......................... 15
5.2 Using old path while looping on new path .............. 15
5.3 How to deal with ordered downstream allocation ........ 15
5.4 How to realize load splitting ......................... 15
6 Why this works ........................................ 16
6.1 Why a thread with unknown hop count is extended ....... 16
6.2 Why a rewound thread cannot contain a loop ............ 17
6.2.1 Case1: LSP with known link hop counts ................. 17
6.2.1 Case2: LSP with unknown link hop counts ............... 17
6.3 Why L3 loop is detected ............................... 17
6.4 Why L3 loop is not mis-detected ....................... 17
6.5 How a stalled thread automatically recovers from loop . 18
6.6 Why different colored threads do not chase each other . 18
7 Loop prevention examples .............................. 19
7.1 First example ......................................... 19
7.2 Second example ........................................ 23
8 Thread control block .................................. 24
8.1 Finite state machine .................................. 25
9 Comparison with path-vector/diffusion method .......... 28
10 Security Considerations ............................... 29
11 Intellectual Property Considerations .................. 29
12 Acknowledgments ....................................... 29
13 Authors' Addresses .................................... 30
14 References ............................................ 30
Appendix A Further discussion of the algorithm ............. 31
Full Copyright Statement ..................................... 44
1. Introduction
This paper presents a simple mechanism, based on "threads", which can
be used to prevent MPLS from setting up label switched paths (LSPs)
which have loops.
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
it downstream. Each such thread is assigned a unique "color", such
that no two threads in the network can have the same color.
Ohba, et al. Experimental [Page 2]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
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 change
in the hop count from the furthest upstream node. The only state
information that needs to be associated with a particular next hop
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
through which it has already passed. This is easily detected, since
each thread has a unique color.
Section 3 and 4 provide procedures for determining that there is no
loop. When this is determined, the threads are "rewound" back to the
point of creation. As they are rewound, labels get assigned. Thus
labels are NOT assigned until loop freedom is guaranteed.
While a thread is extended, the LSRs through which it passes must
remember its color and hop count, but when the thread has been
rewound, they need only remember its hop count.
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
downstream on-demand label allocation or ordered downstream
unsolicited label allocation [2,3]. The mechanism can also be
applicable to loop detection, old path retention, and load-splitting.
The state information which must be carried in protocol messages, and
which must be maintained internally in state tables, is of fixed
size, independent of the network size. Thus the thread mechanism is
more scalable than alternatives which require that path-vectors be
carried.
To set up a new LSP after a routing change, the thread mechanism
requires communication only between nodes which are downstream of the
point of change. There is no need to communicate with nodes that are
upstream of the point of change. Thus the thread mechanism is more
robust than alternatives which require that a diffusion computation
be performed (see section 9).
2. Basic definitions
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 [3].
Ohba, et al. Experimental [Page 3]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
In the following, we 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.
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".
Leaf Node, Ingress Node
A node which has no upstream links.
Eligible Leaf 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 packets created or received at the node into its
outgoing link.
Link Hop Count
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
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
associated with the upstream links.
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 the downstream link is equal to Hmax+1. At a leaf node, Hmax
is set to be zero.
An an example of link hop counts is shown in Fig.1.
Ohba, et al. Experimental [Page 4]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
1 2
A---B---C K
| |
|3 |1
| |
| 4 5 | 6 7
D---G---H---I---J
|
|2
1 |
E---F
Fig.1 Example of link hop counts
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 the next hop for FEC F. A node loses a next hop
whenever the next hop goes down.
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. A next hop change event can be seen
as a combination of a next hop loss event on the old next hop and
a next hop acquisition event on the new next hop.
3. Thread basics
A thread is a sequence of messages used to set up an LSP, in the
"ordered downstream-on-demand" (ingress-initiated ordered control)
style.
3.1. Thread attributes
There are three attributes related to threads. They may be encoded
into a single thread object as:
Ohba, et al. Experimental [Page 5]
RFC 3063 MPLS Loop Prevention Mechanism February 2001
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 +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Hop Count | TTL | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Thread Color
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 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.
special color value "transparent"(=all 0's) is reserved.
One possible method for unique color assignment is, starting the
event identifier from its initial value, and incrementing it by
one (modulo its maximum value) each time a color is assigned. In
this method, the initial event identifier is either selected at
random or assigned to be larger than the largest event identifier
used on the previous system incarnation.
Thread Hop Count
In order to maintain link hop counts, we need to carry hop counts
in the path control messages. For instance, a leaf node would
assign a hop count of 1 to its downstream link, and would store
that value into a path setup message it sends downstream. When a
path setup message is sent downstream, a node would assign a hop
count which is one more than the largest of the incoming link hop
counts, to its downstream link, and would store that value into a
path setup message it sends downstream. Once the value is stored
in a path control message, we may refer to it has a "thread hop
count".
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -