RFC3063 日本語訳
3063 MPLS Loop Prevention Mechanism. Y. Ohba, Y. Katsube, E. Rosen, P.Doolan. February 2001. (Format: TXT=93523 bytes) (Status: EXPERIMENTAL)
プログラムでの自動翻訳です。
英語原文
Network Working Group Y. Ohba
Request for Comments: 3063 Y. Katsube
Category: Experimental Toshiba
E. Rosen
Cisco Systems
P. Doolan
Ennovate Networks
February 2001
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
MPLS Loop Prevention Mechanism
Status of this Memo
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.
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 Notice
Copyright (C) The Internet Society (2001). All Rights Reserved.
Copyright (C) The Internet Society (2001). All Rights Reserved.
Abstract
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.
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
Ohba, et al. Experimental [Page 1] RFC 3063 MPLS Loop Prevention Mechanism February 2001
Table of Contents
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 .......................................... 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
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.
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.
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
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.
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.
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.
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.
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 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.
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).
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
2. Basic definitions
LSP
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].
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
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.
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
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".
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
Leaf Node, Ingress Node
A node which has no upstream links.
A node which has no upstream links.
Eligible Leaf Node
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.
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
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.
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.
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.
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
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
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
Fig.1 Example of link hop counts
Next Hop Acquisition
Next Hop Acquisition
Node N thought that FEC F was unreachable, but now has a next hop
for it.
Node N thought that FEC F was unreachable, but now has a next hop for it.
Next Hop Loss
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.
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
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.
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
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.
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
3.1. Thread attributes
There are three attributes related to threads. They may be encoded into a single thread object as:
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
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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
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
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.
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.
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.
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.
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
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".
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".
Ohba, et al. Experimental [Page 6] RFC 3063 MPLS Loop Prevention Mechanism February 2001
Ohba, et al. Experimental [Page 6] RFC 3063 MPLS Loop Prevention Mechanism February 2001
A special hop count value "unknown"(=0xff), which is larger than
any other known value, is used when a loop is found. Once the
thread hop count is "unknown", it is not increased any more as the
thread is extended.
A special hop count value "unknown"(=0xff), which is larger than any other known value, is used when a loop is found. Once the thread hop count is "unknown", it is not increased any more as the thread is extended.
Thread TTL
Thread TTL
To avoid infinite looping of control messages in some cases, a
thread TTL is used. When a node creates a path control message
and sends it downstream, it sets a TTL to the message, and the TTL
is decremented at each hop. When the TTL reaches 0, the message
is not forwarded any more. Unlike the thread hop counts and the
thread colors, the thread TTLs do not needs to be stored in
incoming links.
To avoid infinite looping of control messages in some cases, a thread TTL is used. When a node creates a path control message and sends it downstream, it sets a TTL to the message, and the TTL is decremented at each hop. When the TTL reaches 0, the message is not forwarded any more. Unlike the thread hop counts and the thread colors, the thread TTLs do not needs to be stored in incoming links.
3.2. Thread loop
3.2. Thread loop
When the same colored thread is received on multiple incoming links, or the received thread color was assigned by the receiving node, it is said that the thread forms a loop. A thread creator can tell whether it assigned the received thread color by checking the IP address part of the received thread color.
When the same colored thread is received on multiple incoming links, or the received thread color was assigned by the receiving node, it is said that the thread forms a loop. A thread creator can tell whether it assigned the received thread color by checking the IP address part of the received thread color.
3.3. Primitive thread actions
3.3. Primitive thread actions
Five primitive actions are defined in order to prevent LSP loops by using threads: "extending", "rewinding", "withdrawing", "merging", and "stalling". This section describes only each primitive action and does not describe how these primitive actions are combined and how the algorithm totally works. The main body of the algorithm is described in section 4.
Five primitive actions are defined in order to prevent LSP loops by using threads: "extending", "rewinding", "withdrawing", "merging", and "stalling". This section describes only each primitive action and does not describe how these primitive actions are combined and how the algorithm totally works. The main body of the algorithm is described in section 4.
Thread Extending
Thread Extending
When a node starts to send a path setup message to its next hop
with a set of thread attributes, it is said that "the node creates
a thread and extends it downstream". When a node receives a path
setup message from an upstream node with a set of thread
attributes and forwards it downstream, it is said that "the node
receives a thread and extends it downstream". The color and hop
count of the thread become the color and hop count of the outgoing
link. Whenever a thread is received on a particular link, the
color and hop count of that thread become the color and hop count
of that incoming link, replacing any color and hop count that the
link may have had previously.
When a node starts to send a path setup message to its next hop with a set of thread attributes, it is said that "the node creates a thread and extends it downstream". When a node receives a path setup message from an upstream node with a set of thread attributes and forwards it downstream, it is said that "the node receives a thread and extends it downstream". The color and hop count of the thread become the color and hop count of the outgoing link. Whenever a thread is received on a particular link, the color and hop count of that thread become the color and hop count of that incoming link, replacing any color and hop count that the link may have had previously.
Ohba, et al. Experimental [Page 7] RFC 3063 MPLS Loop Prevention Mechanism February 2001
Ohba, et al. Experimental [Page 7] RFC 3063 MPLS Loop Prevention Mechanism February 2001
For example, when an ingress node initiates a path setup, it
creates a thread and extends it downstream by sending a path setup
message. The thread hop count is set to be 1, and the thread
color is set to be the ingress node's address with an appropriate
event identifier, and the thread TTL is set to be its maximum
value.
For example, when an ingress node initiates a path setup, it creates a thread and extends it downstream by sending a path setup message. The thread hop count is set to be 1, and the thread color is set to be the ingress node's address with an appropriate event identifier, and the thread TTL is set to be its maximum value.
When a node receives a thread and extends it downstream, the node
either (i) extends the thread without changing color, or (ii)
extend the thread with changing color. The received thread is
extended with changing color if it is received on a new incoming
link and extended on an already existing outgoing link, otherwise,
it is extended without changing color. When a thread is extended
with changing color, a new colored thread is created and extended.
When a node receives a thread and extends it downstream, the node either (i) extends the thread without changing color, or (ii) extend the thread with changing color. The received thread is extended with changing color if it is received on a new incoming link and extended on an already existing outgoing link, otherwise, it is extended without changing color. When a thread is extended with changing color, a new colored thread is created and extended.
Thread creation does not occur only at leaf nodes. If an
intermediate node has an incoming link, it will create and extend
a new thread whenever it acquires a new next hop.
Thread creation does not occur only at leaf nodes. If an intermediate node has an incoming link, it will create and extend a new thread whenever it acquires a new next hop.
When a node notifies a next hop node of a decrease of the link hop
count, if it is not extending a colored thread, a transparent
thread is extended.
When a node notifies a next hop node of a decrease of the link hop count, if it is not extending a colored thread, a transparent thread is extended.
Thread Merging
Thread Merging
When a node which has a colored outgoing link receives a new
thread, it does not necessarily extend the new thread. It may
instead 'merge' the new threads into the existing outgoing thread.
In this case, no messages are sent downstream. Also, if a new
incoming thread is extended downstream, but there are already
other incoming threads, these other incoming threads are
considered to be merged into the new outgoing thread.
When a node which has a colored outgoing link receives a new thread, it does not necessarily extend the new thread. It may instead 'merge' the new threads into the existing outgoing thread. In this case, no messages are sent downstream. Also, if a new incoming thread is extended downstream, but there are already other incoming threads, these other incoming threads are considered to be merged into the new outgoing thread.
Specifically, a received thread is merged if all the following
conditions hold:
Specifically, a received thread is merged if all the following conditions hold:
o A colored thread is received by node N, AND
o The thread does not form a loop, AND
o N is not an egress node, AND
o N's outgoing link is colored, AND
o N's outgoing link hop count is at least one greater than the
hop count of the newly received thread.
o A colored thread is received by node N, AND o The thread does not form a loop, AND o N is not an egress node, AND o N's outgoing link is colored, AND o N's outgoing link hop count is at least one greater than the hop count of the newly received thread.
When an outgoing thread rewinds (see below), any incoming threads
which have been merged with it will rewind as well.
When an outgoing thread rewinds (see below), any incoming threads which have been merged with it will rewind as well.
Ohba, et al. Experimental [Page 8] RFC 3063 MPLS Loop Prevention Mechanism February 2001
Ohba, et al. Experimental [Page 8] RFC 3063 MPLS Loop Prevention Mechanism February 2001
Thread Stalling
Thread Stalling
When a colored thread is received, if the thread forms a loop, the
received thread color and hop count are stored on the receiving
link without being extended. This is the special case of thread
merging applied only for threads forming a loop and referred to as
the "thread stalling", and the incoming link storing the stalled
thread is called "stalled incoming link". A distinction is made
between stalled incoming links and unstalled incoming links.
When a colored thread is received, if the thread forms a loop, the received thread color and hop count are stored on the receiving link without being extended. This is the special case of thread merging applied only for threads forming a loop and referred to as the "thread stalling", and the incoming link storing the stalled thread is called "stalled incoming link". A distinction is made between stalled incoming links and unstalled incoming links.
Thread Rewinding
Thread Rewinding
When a thread reaches a node which satisfies a particular loop-
free condition, the node returns an acknowledgment message back to
the message initiator in the reverse path on which the thread was
extended. The transmission of the acknowledgment messages is the
"rewinding" of the thread.
When a thread reaches a node which satisfies a particular loop- free condition, the node returns an acknowledgment message back to the message initiator in the reverse path on which the thread was extended. The transmission of the acknowledgment messages is the "rewinding" of the thread.
The loop-free condition is:
The loop-free condition is:
o A colored thread is received by the egress node, OR
o All of the following conditions hold:
(a) A colored thread is received by node N, AND
(b) N's outgoing link is transparent, AND
(c) N's outgoing link hop count is at least one greater than
the hop count of the newly received thread.
o A colored thread is received by the egress node, OR o All of the following conditions hold: (a) A colored thread is received by node N, AND (b) N's outgoing link is transparent, AND (c) N's outgoing link hop count is at least one greater than the hop count of the newly received thread.
When a node rewinds a thread which was received on a particular
link, it changes the color of that link to transparent.
When a node rewinds a thread which was received on a particular link, it changes the color of that link to transparent.
If there is a link from node M to node N, and M has extended a
colored thread to N over that link, and M determines (by receiving
a message from N) that N has rewound that thread, then M sets the
color of its outgoing link to transparent. M then continues
rewinding the thread, and in addition, rewinds any other incoming
thread which had been merged with the thread being rewound,
including stalled threads.
If there is a link from node M to node N, and M has extended a colored thread to N over that link, and M determines (by receiving a message from N) that N has rewound that thread, then M sets the color of its outgoing link to transparent. M then continues rewinding the thread, and in addition, rewinds any other incoming thread which had been merged with the thread being rewound, including stalled threads.
Each node can start label switching after the thread colors in all
incoming and outgoing links becomes transparent.
Each node can start label switching after the thread colors in all incoming and outgoing links becomes transparent.
Note that transparent threads are threads which have already been
rewound; hence there is no such thing as rewinding a transparent
thread.
Note that transparent threads are threads which have already been rewound; hence there is no such thing as rewinding a transparent thread.
Ohba, et al. Experimental [Page 9] RFC 3063 MPLS Loop Prevention Mechanism February 2001
Ohba, et al. Experimental [Page 9] RFC 3063 MPLS Loop Prevention Mechanism February 2001
Thread Withdrawing
Thread Withdrawing
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 the "thread
withdrawing".
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 the "thread withdrawing".
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.
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.
If node M has extended a thread to node N, and node M then
withdraws that thread, N now has one less incoming link than it
had before. If N now has no other unstalled incoming links and N
is not an eligible leaf node, it must withdraw its outgoing
thread. If N still has an unstalled incoming link or N is an
eligible leaf node, it may (or may not) need to change the hop
count of the outgoing link.
If node M has extended a thread to node N, and node M then withdraws that thread, N now has one less incoming link than it had before. If N now has no other unstalled incoming links and N is not an eligible leaf node, it must withdraw its outgoing thread. If N still has an unstalled incoming link or N is an eligible leaf node, it may (or may not) need to change the hop count of the outgoing link.
N needs to change the outgoing hop count if:
N needs to change the outgoing hop count if:
o The incoming link hop count that was just removed had a larger
hop count than any of the remaining incoming links, AND
o One of the following conditions holds:
(a) The outgoing link is transparent, OR
(b) The outgoing link has a known hop count.
o The incoming link hop count that was just removed had a larger hop count than any of the remaining incoming links, AND o One of the following conditions holds: (a) The outgoing link is transparent, OR (b) The outgoing link has a known hop count.
If the outgoing link is transparent, it remains transparent, but
the new hop count needs to be sent downstream. If the outgoing
link is colored, a new thread (with a new color) needs to be
created and extended downstream.
If the outgoing link is transparent, it remains transparent, but the new hop count needs to be sent downstream. If the outgoing link is colored, a new thread (with a new color) needs to be created and extended downstream.
3.4. Examples of primitive thread actions
3.4. Examples of primitive thread actions
The following notations are used to illustrate examples of primitive actions defined for threads.
The following notations are used to illustrate examples of primitive actions defined for threads.
A pair of thread attributes stored in each link is represented by "(C,H)", where C and H represent the thread color and thread hop count, respectively.
A pair of thread attributes stored in each link is represented by "(C,H)", where C and H represent the thread color and thread hop count, respectively.
A thread marked "+" indicates that it is created or received now. A thread marked "-" indicates that it is withdrawn now.
A thread marked "+" indicates that it is created or received now. A thread marked "-" indicates that it is withdrawn now.
A link labeled with squared brackets (e.g., "[a]") indicates that it
is an unstalled link. A link labeled with braces (e.g., "{a}")
indicates that it is a stalled link.
A link labeled with squared brackets (e.g., "[a]") indicates that it is an unstalled link. A link labeled with braces (e.g., "{a}") indicates that it is a stalled link.
Ohba, et al. Experimental [Page 10] RFC 3063 MPLS Loop Prevention Mechanism February 2001
Ohba, et al. Experimental [Page 10] RFC 3063 MPLS Loop Prevention Mechanism February 2001
Fig. 2 shows an example in which a leaf node A creates a blue thread and extends it downstream.
Fig. 2 shows an example in which a leaf node A creates a blue thread and extends it downstream.
(bl,1)
A---[o1]--->
(bl,1) A---[o1]--->
Fig.2 Thread extending at leaf node
Fig.2 Thread extending at leaf node
Fig.3 shows an example of thread extending without changing color at intermediate node. Assume that a node B has no incoming and outgoing link before receiving a blue thread. When node B receives the blue thread of hop count 1 on a new incoming link i1, it extends the thread downstream without changing color (Fig.3(a)). After the blue thread is extended, node B receives a red thread of hop count unknown on incoming link i1 again (Fig.3(b)). The red thread is also extended without changing its color, since both i1 and o1 already exists.
Fig.3 shows an example of thread extending without changing color at intermediate node. Assume that a node B has no incoming and outgoing link before receiving a blue thread. When node B receives the blue thread of hop count 1 on a new incoming link i1, it extends the thread downstream without changing color (Fig.3(a)). After the blue thread is extended, node B receives a red thread of hop count unknown on incoming link i1 again (Fig.3(b)). The red thread is also extended without changing its color, since both i1 and o1 already exists.
(bl,1)+ (bl,2) (re,U)+ (re,U)
----[i1]--->B---[o1]----> ----[i1]--->B----[o1]--->
(bl,1)+ (bl,2) (re,U)+ (re,U) ----[i1]--->B---[o1]----> ----[i1]--->B----[o1]--->
Fig.3(a) Fig.3(b)
Fig.3(a) Fig.3(b)
Fig.3 Thread extending without changing color
Fig.3 Thread extending without changing color
Fig.4 shows an example of thread extending with changing color. There are single incoming link i1 and single outgoing link o1 in Fig.4(a). Then a red thread of hop count 3 is received on a new incoming link i2. In this case, the received thread is extended with changing color, i.e., a new green thread is created and extended (Fig.4(b)), since o1 already exists.
Fig.4 shows an example of thread extending with changing color. There are single incoming link i1 and single outgoing link o1 in Fig.4(a). Then a red thread of hop count 3 is received on a new incoming link i2. In this case, the received thread is extended with changing color, i.e., a new green thread is created and extended (Fig.4(b)), since o1 already exists.
(bl,1) (bl,2) (bl,1) (gr,4)
----[i1]--->B----[o1]---> ----[i1]--->B----[o1]--->
^
|
----[i2]----+
(re,3)+
(bl,1) (bl,2) (bl,1) (gr,4) ----[i1]--->B----[o1]---> ----[i1]--->B----[o1]---> ^ | ----[i2]----+ (re,3)+
Fig.4(a) Fig.4(b)
Fig.4(a) Fig.4(b)
Fig.4 Thread extending with changing color
Fig.4 Thread extending with changing color
Fig.5 shows an example of thread merging. When a node B receives a red thread of hop count 3, the received thread is not extended since the outgoing link hop count is at least one greater than the received thread hop count. Both the red and blue threads will be rewound when the blue thread on outgoing link o1 is rewound.
Fig.5 shows an example of thread merging. When a node B receives a red thread of hop count 3, the received thread is not extended since the outgoing link hop count is at least one greater than the received thread hop count. Both the red and blue threads will be rewound when the blue thread on outgoing link o1 is rewound.
Ohba, et al. Experimental [Page 11] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[11ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
(bl,3) (bl,4)
----[i1]--->B----[o1]--->
^
|
----[i2]----+
(re,3)+
(bl、3)(bl、4)----[i1]--->B----[o1]--->^| ----[i2]----+ (re、3)+
Fig.5 Thread merging
Fig.5 Thread合併
Figs 6 and 7 show examples of thread stalling. When a node B receives a blue thread of hop count 10 on incoming link i2 in Fig.6, it "stalls" the received thread since the blue thread forms a loop. In Fig.7, a leaf node A finds the loop of its own thread.
図6と7は、糸に関する例が失速するのを示します。 ノードBがFig.6の入って来るリンクi2でホップカウント10の青い糸を受けるとき、青い糸が輪を形成するので、それは容認された糸を「失速させます」。 Fig.7では、葉のノードAはそれ自身の糸の輪を見つけます。
(bl,3) (bl,4)
----[i1]--->B----[o1]--->
^
|
----{i2}----+
(bl,10)+
(bl、3)(bl、4)----[i1]--->B----[o1]--->^| ----i2----+ (bl、10)+
Fig.6 Thread stalling (1)
Fig.6 Threadエンスト(1)
(bl,10)+ (bl,1)
----{i1}--->A----[o1]--->
(bl、10)+(bl、1)----i1--->A----[o1]--->。
Fig.7 Thread stalling (2)
Fig.7 Threadエンスト(2)
Fig.8 shows an example of thread rewinding. When the yellow thread which is currently being extended is rewound (Fig.8(a)), the node changes all the incoming and outgoing thread color to transparent, and propagates thread rewinding to upstream nodes (Fig.8(b)).
Fig.8は糸の巻き戻しに関する例を示しています。 現在広げられている黄色糸が巻き戻されるとき(Fig.8(a))、ノードは、すべての送受信の糸の色を透明に変えて、糸の巻き戻しを上流のノードに伝播します。(Fig.8(b))。
(bl,1) (ye,2) (tr,1) (tr,2)
----[i2]--->B----[o1]---> ----[i2]--->B----[o1]--->
^ ^
| |
----[i3]----+ ----[i3]----+
(ye,1) (tr,1)
(bl、1)、(あれ、2(tr、1)(tr、2))----[i2]--->B----[o1]--->。----[i2]--->B----[o1]--->^ ^| | ----[i3]----+ ----[i3]----+、(あれ、1)(tr、1)
Fig.8(a) Fig.8(b)
Fig.8(a) Fig.8(b)
Fig.8 Thread rewinding
Fig.8 Thread巻き戻し
Ohba, et al. Experimental [Page 12] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[12ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
Fig.9 shows an example of thread withdrawing. In Fig.9(a), the red thread on incoming link i2 is withdrawn. Then Hmax decreases from 3 to 1, and node B creates a new green thread and extends it downstream, as shown in Fig.9(b).
Fig.9は、糸に関する例が引き下がるのを示します。 Fig.9(a)では、入って来るリンクi2の上の赤い糸はよそよそしいです。 次に、Hmaxが3〜1まで減少して、ノードBは、新しい緑色の糸を作成して、川下でそれを広げます、Fig.9(b)に示されるように。
(bl,1) (re,4) (bl,1) (gr,2)+
----[i1]--->B---[o1]---> ----[i1]--->B----[o1]--->
^
|
----[i2]----+
(re,3)-
(bl、1) (re、4)(bl、1)(gr、2)+----[i1]--->B---[o1]--->。----[i1]--->B----[o1]--->^| ----[i2]----+ (re、3)、-
Fig.9(a) Fig.9(b)
Fig.9(a) Fig.9(b)
Fig.9 Thread withdrawing (1)
Fig.9 Threadの引き下がること(1)
Fig.10 shows another example of thread withdrawing. In Fig.10(a), the red thread on incoming link i3 is withdrawn. In this case, Hmax decreases from unknown to 1, however, no thread is extended as shown in Fig.10(b), since the outgoing link has a colored thread and the hop count is unknown.
Fig.10は、糸に関する別の例が引き下がるのを示します。 Fig.10(a)では、入って来るリンクi3の上の赤い糸はよそよそしいです。 しかしながら、この場合、Hmaxは未知から1まで減少して、どんな糸もFig.10(b)に示されるように拡張されていません、出発しているリンクには有色の糸があって、ホップカウントが未知であるので。
(bl,1) (re,U) (bl,1) (re,U)
----[i2]--->B----[o1]---> ----[i2]--->B----[o1]--->
^
|
----[i3]----+
(re,U)-
(bl、1)(re、U)(bl、1)(re、U)----[i2]--->B----[o1]--->。----[i2]--->B----[o1]--->^| ----[i3]----+ (re、U)、-
Fig.10(a) Fig.10(b)
Fig.10(a) Fig.10(b)
Fig.10 Thread withdrawing (2)
Fig.10 Threadの引き下がること(2)
Fig.11 shows another example of thread withdrawing. In Fig.11(a), the transparent thread on incoming link i3 is withdrawn. In this case, a transparent thread is extended (Fig.11(b)), since Hmax decreases and the outgoing link is transparent.
Fig.11は、糸に関する別の例が引き下がるのを示します。 Fig.11(a)では、入って来るリンクi3の上の透明な糸はよそよそしいです。 この場合、透明な糸は拡張されています。(Hmaxが減少して、出発しているリンクが透明である時からFig.11(b))。
(tr,1) (tr,U) (tr,1) (tr,2)+
----[i2]--->B----[o1]---> ----[i2]--->B----[o1]--->
^
|
----[i3]----+
(tr,U)-
(tr、1) (tr、U)(tr、1)(tr、2)+----[i2]--->B----[o1]--->。----[i2]--->B----[o1]--->^| ----[i3]----+ (tr、U)、-
Fig.11(a) Fig.11(b)
Fig.11(a) Fig.11(b)
Fig.11 Thread withdrawing (3)
Fig.11 Threadの引き下がること(3)
Ohba, et al. Experimental [Page 13] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[13ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
4. Thread algorithm
4. 糸のアルゴリズム
The ordered downstream-on-demand allocation is assumed here, however, the algorithm can be adapted to the ordered downstream allocation, as shown in section 5.
しかしながら、ここで命令された川下要求次第の配分を想定して、命令された川下の配分にアルゴリズムを適合させることができます、セクション5で示されるように。
In the algorithm, a next hop change event will be separated into two events: a next hop loss event on the old next hop and a next hop acquisition event on the new next hop, in this order.
アルゴリズムで、次のホップ変化出来事は2回の出来事に切り離されるでしょう: 次の古いホップにおける次のホップ損失出来事とこのオーダーにおける次の新しいホップにおける次のホップ獲得出来事。
The following notations are defined:
以下の記法は定義されます:
Hmax: the largest incoming link hop count
Ni: the number of unstalled incoming links
Hmax: 最も大きい入って来るリンクホップカウントNi: 非失速している入って来るリンクの数
The thread algorithm is described as follows.
糸のアルゴリズムは以下の通り説明されます。
When a node acquires a new next hop, it creates a colored thread and extends it downstream.
ノードが次の新しいホップを取得するとき、それは、有色の糸を作成して、川下でそれを広げています。
When a node loses a next hop to which it has extended a thread, it may withdraw that thread. As described in section 3, this may or may not cause the next hop to take some action. Among the actions the next hop may take are withdrawing the thread from its own next hop, or extending a new thread to its own next hop.
ノードがそれが糸を広げた次のホップを失うと、それはその糸を引っ込めるかもしれません。 セクション3で説明されるように、次のホップはこれで何らかの行動を取るかもしれません。 動作の中では、次のホップはそれ自身の次のホップから糸を引っ込めるか、またはそれ自身のものへの新しい糸を広げているのに次のホップを取るかもしれません。
A received colored thread is either stalled, merged, rewound, or extended. A thread with TTL zero is never extended.
容認された有色の糸は、失速するか、合併されているか、巻き戻されるか、または広げられます。 TTLゼロがある糸は決して広げられません。
When a received thread is stalled at a node, if Ni=0 and the node is not an eligible leaf node, initiate a thread withdrawing. Otherwise, if Ni>0 and the received thread hop count is not unknown, a colored thread of hop count unknown is created and extended. If the received thread hop count is unknown, no thread is extended and no further action is taken.
容認された糸がNi=0であるならノードで失速して、ノードが適任の葉のノードでないときに、糸の引き下がることを開始してください。 さもなければ、>0と容認された糸のホップが数えるNiが未知でないなら、ホップカウント未知の有色の糸は、作成されて、広げられます。 容認された糸のホップカウントが未知であるなら、どんな糸も拡張していません、そして、さらなる行動を全く取りません。
When a thread being extended is rewound, if the thread hop count is greater than one more than Hmax, a transparent thread of hop count (Hmax+1) is extended downstream.
広げられる糸が糸のホップカウントがHmaxよりさらに1以上であるなら巻き戻されるとき、ホップカウント(Hmax+1)の透明な糸は川下で広げられます。
When a node that has an transparent outgoing link receives a transparent thread, if Hmax decreases the node extends it downstream without changing color.
透明な出発しているリンクを持っているノードが透明な糸を受けるとき、Hmaxが減少するなら、色を変えないで、ノードは川下でそれを広げます。
5. Applicability of the algorithm
5. アルゴリズムの適用性
The thread algorithm described in section 4 can be applied to various LSP management policies.
セクション4で説明された糸のアルゴリズムは様々なLSP経営政策に適用できます。
Ohba, et al. Experimental [Page 14] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[14ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
5.1. LSP Loop prevention/detection
5.1. LSP Loop防止/検出
The same thread algorithm is applicable to both LSP loop prevention and detection.
同じ糸のアルゴリズムはLSP輪の防止と検出の両方に適切です。
In loop prevention mode, a node transmits a label mapping (including a thread object) for a particular LSP only when it rewinds the thread for that LSP. No mapping message is sent until the thread rewinds.
そのLSPのために糸を巻き戻すときだけ、輪の防止モードで、ノードは特定のLSPのためにラベルマッピングを伝えます(糸の物を含んでいます)。 糸まで写像しているメッセージを全く送りません。巻き戻します。
On the other hand, if a node operates in loop detection mode, it returns a label mapping message without a thread object immediately after receiving a colored thread. A node which receives a label mapping message that does not have a thread object will not rewind the thread.
他方では、ノードが輪の検出モードで作動するなら、有色の糸を受ける直後それは糸の物なしでラベルマッピングメッセージを返します。 糸の物を持っていないラベルマッピングメッセージを受け取るノードは糸を巻き戻さないでしょう。
5.2. Using old path while looping on new path
5.2. 新しい経路で輪にしている間、古い経路を使用します。
When a route changes, one might want to continue to use the old path if the new route is looping. This is achieved simply by holding the label assigned to the downstream link on the old path until the thread being extended on the new route gets rewound. This is an implementation choice.
ルートが変化するとき、新しいルートが輪にされるなら、人は、古い経路を使用し続けたがっているかもしれません。 単に新しいルートで広げられる糸が巻き戻されるまでラベルが古い経路の川下のリンクに割り当てられるままにすることによって、これは達成されます。 これは実現選択です。
5.3. How to deal with ordered downstream allocation
5.3. 命令された川下の配分に対処する方法
The thread mechanism can be also adapted to ordered downstream allocation mode (or the egress-initiated ordered control) by regarding the event of newly receiving of a label mapping message [4] from the next hop as a next hop acquisition event.
また、次のホップ獲得出来事として次のホップからのメッセージ[4]を写像しながら、新たにラベルを受信する出来事を見なすことによって、規則正しい川下の配分モード(または、出口で開始している命令されたコントロール)に糸のメカニズムを適合させることができます。
Note that a node which doesn't yet have an incoming link behaves as a leaf. In the case where the tree is being initially built up (e.g., the egress node has just come up), each node in turn will behave as a leaf for a short period of time.
まだ入って来るリンクを持っていないノードが葉として振る舞うことに注意してください。 木が初めは確立される予定である(例えば、出口ノードはちょうど来たところです)場合では、各ノードは短期間の間、葉として順番に振る舞うでしょう。
5.4. How to realize load splitting
5.4. 負荷の分かれることがわかる方法
A leaf node can easily perform load splitting by setting up two different LSPs for the same FEC. The downstream links for the two LSPs are simply assigned different colors. The thread algorithm now prevents a loop in either path, but also allows the two paths to have a common downstream node.
葉のノードは、同じFECのために2異なったLSPsをセットアップすることによって、容易に負荷の分かれることを実行できます。 異なった色は単に2LSPsのための川下のリンクに割り当てられます。 糸のアルゴリズムで、現在どちらの経路でも輪を防ぎますが、2つの経路には一般的な川下のノードがまたあります。
If some intermediate node wants to do load splitting, the following modification is made. Assume that there are multiple next hops for the same FEC. If there are n next hops for a particular FEC, the set of incoming links for that FEC's LSP can be partitioned into n subsets, where each subset can be mapped to a distinct outgoing link.
するいくつかの中間的ノード必需品が分かれることをロードするなら、以下の変更をします。 同じFECのためのホップが次に複数であると仮定してください。 次のnホップが特定のFECのためにあれば、そのFECのLSPのための入って来るリンクのセットをn部分集合に仕切ることができます。そこでは、異なった出発しているリンクに各部分集合を写像できます。
Ohba, et al. Experimental [Page 15] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[15ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
This provides n LSPs for the FEC. Each such LSP uses a distinct color for its outgoing link. The thread algorithm now prevents a loop in any of the paths, but also allows two or more of the paths to have a common downstream node.
これはn LSPsをFECに供給します。 そのような各LSPは出発しているリンクに異なった色を使用します。 糸のアルゴリズムで、現在経路のどれかで輪を防ぎますが、2つ以上の経路には一般的な川下のノードがまたあります。
In this case, an interesting situation may happen. Let's say that in Fig.12, node B has two incoming links, i1 and i2, and two outgoing links, o1 and o2, such that i1 is mapped to o1, while i2 is mapped to o2.
この場合、おもしろい状況は起こるかもしれません。 Fig.12では、ノードBが2個の入って来るリンク、i1、i2、2個の出発しているリンク、o1、およびo2を持っていると言いましょう、i1がo1に写像されるように、i2はo2に写像されますが。
If a blue thread received on i1 and extended on o1 is again received at node B on i2, the blue thread is not regarded as forming a loop, since i1 and i2 are regarded as belonging to different subsets. Instead, the blue thread received on i2 is extended on o2. If the thread extended on o2 is rewound, a single loop-free LSP which traverses node B twice is established.
再びi2の上のノードBにi1に受け取られて、o1で広げられた青い糸を受け取るなら、青い糸を輪を形成すると見なしません、i1とi2が異なった部分集合に属すと見なされるので。 代わりに、i2に受け取られた青い糸はo2で広げられます。 o2で広げられた糸が巻き戻されるなら、二度ノードBを横断する無シングル・ループのLSPは設立されます。
+------------------...--------------------+
. (bl,3) (bl,4) |
. ----[i1]---+ +--[o1]---> .... --+
. \ /
. v /
| B
|
+-----------[i2]--->B----[o2]--->
(bl,10)+ (bl,11)
+------------------...--------------------+ . (bl、3)(bl、4)| . ----[i1]---+ +--[o1]--->… --+ . \/v/| B| +-----------[i2]--->B----[o2]--->(bl、10)+(bl、11)
Fig.12 Load splitting at intermediate node
中間的ノードで分かれるFig.12 Load
There is another type of load splitting, in which packets arrived at single incoming link can be label switched to any one of multiple outgoing links. This case does not seem to be a good load-splitting scheme, since the packet order in the same FEC is not preserved. Thus, this document does not focus on this case.
負荷の分かれることの別のタイプがあります。(そこでは、パケットがいずれかに切り換えられたラベルが複数の出発しているリンクの1つであったかもしれないなら単一の入って来るリンクに到着しました)。 本件は良い負荷が分かれる計画であるように思えません、同じFECのパケットオーダーが保存されないので。 したがって、このドキュメントは本件に焦点を合わせません。
Whether that's a good type of load splitting or not, the fact remains that ATM-LSRs cannot load split like this because ATM switches just don't have the capability to make forwarding decisions on a per- packet basis.
ATMスイッチには推進をaの決定にする能力がただないのでATM-LSRsが積み込むことができない事実の残りがそれが良いタイプについて負荷の分かれることであるか否かに関係なく、このように分かれた、-、パケット基礎。
6. Why this works
6. これが働いている理由
6.1. Why a thread with unknown hop count is extended
6.1. 未知のホップカウントがある糸が拡張されている理由
In the algorithm, a thread of unknown hop count is extended when a thread loop is detected. This reduces the number of loop prevention
糸ループが検出されるとき、アルゴリズムで、未知のホップカウントの糸は拡張されています。 これは輪の防止の数を減少させます。
Ohba, et al. Experimental [Page 16] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[16ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
messages by merging threads (of known hop count) that are flowing inside or outside the loop. See Appendix A.12.
輪の中、または、輪の外を流れている糸(知られているホップカウントの)を合併するのによるメッセージ。 付録A.12を見てください。
6.2. Why a rewound thread cannot contain a loop
6.2. 巻き戻された糸が輪を含むことができない理由
6.2.1. Case1: LSP with known link hop counts
6.2.1. Case1: 知られているリンクホップカウントがあるLSP
How can we be sure that an established path does not contain a loop when the outgoing link hop count is NOT "unknown"?
私たちは外向的なリンクホップカウントが「未知でない」ときに、確立した経路が輪を含まないのをどのように確信している場合がありますか?
Consider a sequence of LSRs <R1, ..., Rn>, such that there is a loop traversing the LSRs in the sequence. (I.e., packets from R1 go to R2, then to R3, etc., then to Rn, and then from Rn to R1.)
LSRs<R1の系列を考えてください…, Rn>、系列でLSRsを横断する輪があるようなもの。 (R1からのすなわち、パケットはそして、R2、そして、そして、RnへのR3など、およびRnからR1まで行きます。)
Suppose that the thread hop count of the link between R1 and R2 is k. Then by the above procedures, the hop counts between Rn and R1 must be k+n-1. But the algorithm also ensures that if a node has an incoming hop count of j, its outgoing link hop count must be at least of j+1. Hence, if we assume that the LSP established as a result of thread rewinding contains a loop, the hop counts between R1 and R2 must be at least k+n. From this we may derive the absurd conclusion that n=0, and we may therefore conclude that there is no such sequence of LSRs.
R1とR2とのリンクの糸のホップカウントがkであると仮定してください。 そして、上の手順によって、RnとR1の間のホップカウントはk+n-1であるに違いありません。 しかし、また、アルゴリズムは、ノードにjの入って来るホップカウントがあるなら、外向的なリンクホップカウントが少なくとも持っているに違いないことをj+1を確実にします。 したがって、私たちが、糸の巻き戻しの結果、設立されたLSPが輪を含むと思うなら、R1とR2の間のホップカウントは少なくともk+nであるに違いありません。 これから、私たちはn=0、および私たちがそうするかもしれないというとんでもない結論を引き出すかもしれません、したがって、LSRsのどんなそのような系列もないと結論を下してください。
6.2.1. Case2: LSP with unknown link hop counts
6.2.1. Case2: 未知のリンクホップカウントがあるLSP
An established path does not contain a loop as well, when the outgoing link hop count is "unknown". This is because a colored thread of unknown hop count is never rewound unless it reaches egress.
外向的なリンクホップカウントが「未知である」ときに、確立した経路はまた、輪を含んでいません。 これは出口に達しない場合未知のホップカウントの有色の糸が決して巻き戻されないからです。
6.3. Why L3 loop is detected
6.3. L3 loopが検出される理由
Regardless of whether the thread hop count is known or unknown, if there is a loop, then some node in the loop will be the last node to receive a thread over a new incoming link. This thread will always arrive back at that node, without its color having changed. Hence the loop will always be detected by at least one of the nodes in the loop.
糸のホップカウントが知られているか、または未知であることにかかわらず、輪があれば、輪の何らかのノードが新しい入って来るリンクの上に糸を受け取る最後のノードになるでしょう。 色なしで変化して、この糸はそのノードでいつも帰って来るでしょう。 したがって、輪は少なくとも輪のノードの1つでいつも検出されるでしょう。
6.4. Why L3 loop is not mis-detected
6.4. L3 loop誤検出されない理由
Since no node ever extends the same colored thread downstream twice, a thread loop is not detected unless there actually is an L3 routing loop.
どんなノードも川下で二度糸に着色された同じくらいを広げないので、L3ルーティング輪が実際にない場合、糸ループは検出されません。
Ohba, et al. Experimental [Page 17] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[17ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
6.5. How a stalled thread automatically recovers from loop
6.5. 失速している糸は輪からどう自動的に回収されるか。
Once a thread is stalled in a loop, the thread (or the path setup request) effectively remains in the loop, so that a path reconfiguration (i.e., thread withdrawing on the old path and thread extending on the new path) can be issued from any node that may receive a route change event so as to break the loop.
糸が輪でいったん失速すると、事実上、糸(または、経路セットアップ要求)は輪に残っています、輪を壊すためにルート変化イベントを受けるかもしれないどんなノードからも経路再構成(すなわち、新しい経路で広がりながら古い経路と糸の上に引き下がる糸)を発行できるように。
6.6. Why different colored threads do not chase each other
6.6. 異なった有色の糸が互いを追いかけない理由
In the algorithm, multiple thread color and/or hop count updates may happen if several leaf nodes start extending threads at the same time. How can we prevent multiple threads from looping unlimitedly?
アルゴリズムで、いくつかの葉のノードが同時に糸を広げ始めるなら、複数の糸の色、そして/または、ホップカウントアップデートは起こるかもしれません。 私たちは、複数の糸が限りなく輪にされるのをどうしたら防ぐことができますか?
First, when a node finds that a thread forms a loop, it creates a new thread of hop count "unknown". All the looping threads of a known hop count which later arrive at the node would be merged into this thread. Such a thread behaves like a thread absorber.
糸が輪を形成するのがノードによってわかるとき、まず最初に、それは「未知」でホップカウントの新しい糸を作成します。 後でノードに届く知られているホップカウントのすべてのループ糸がこの糸に合併されるでしょう。 そのような糸は糸の吸収装置のように反応します。
Second, the "thread extending with changing color" prevents two threads from chasing each other.
2番目に、「色を変えると共に広がる糸」は、2個の糸が互いを追いかけるのを防ぎます。
Suppose that a received thread were always extended without changing color. Then we would encounter the following situation.
容認された糸がいつも色を変えないで広げられたと仮定してください。 そして、私たちは以下の状況に遭遇するでしょう。
G Y
| |
v v
R1------>R2
^ |
| v
R4<------R3
G Y| | v R1に対して------>R2^| | R4<に対して------R3
Fig.13 Example of thread chasing
糸の追跡のFig.13 Example
In Fig.13, (1) node G acquires R1 as a next hop, and starts to extend a green thread of hop count 1, (2) node Y acquires R2 as a next hop, and starts to extend a yellow thread of hop count 1, and (3) both node G and node Y withdraws their threads before these threads go round.
(3) (1) Fig.13では、ノードGは、次のホップとしてR1を獲得して、ホップカウント1の緑色の糸を広げ始めます、そして、(2) ノードYは、次のホップとしてR2を獲得して、ホップカウント1の黄色い糸を広げ始めます、そして、これらの糸が回る前にノードGとノードYの両方がそれらの糸を引っ込めます。
In this case, the yellow and green threads would go round and get back to R2 and R1, respectively. When the threads get back to R2 and R1, however, the incoming links that store the yellow and green colors no longer exist. As a result, the yellow and green threads would chase each other forever in the loop.
この場合、黄色くて緑色の糸は、回って、それぞれR2とR1に戻るでしょう。 しかしながら、糸がR2とR1に戻るとき、黄色と緑色を格納する入って来るリンクはもう存在していません。 その結果、黄色くて緑色の糸はいつまでも、輪で互いを追いかけるでしょう。
Ohba, et al. Experimental [Page 18] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[18ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
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.
しかしながら、私たちには「色を変えると共に広がり」メカニズムがあるので、これは実際に起こりません。 R2に緑色の糸を受け取るとき、R2はすなわち、色を変えるのに糸を広げます。新しい赤の糸を作成して、それを広げています。 同様に、R1に黄色い糸を受け取るとき、R1は新しい紫色の糸を作成して、それを広げています。 したがって、ノードGとノードYが糸を引っ込めた後にさえ糸ループは検出されます。 これは、糸が輪にある何らかのノードで色を割り当てる輪の周りで広げられるのを確実にします。
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.
すなわち、「色を変えると共に広がり」メカニズムさえ扱うことができない少なくとも1つのケース、同じ糸に関して引き下がる糸の広がりと糸が輪で互いを追いかける「自己追跡」があります。 それを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.
自己追跡のための発見的教授法は糸の引き下がることの開始ノードで引き下がる糸の実行を遅らせることです。 とにかく、糸のTTLメカニズムはどんな種類の糸のループも排除できます。
7. Loop prevention examples
7. 輪の防止の例
In this section, we show two examples to show how the algorithm can prevent LSP loops in given networks.
このセクションで、私たちは、アルゴリズムが与えられたネットワークでどうLSP輪を防ぐことができるかを示しているために2つの例を示しています。
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.
私たちは命令された川下要求次第の配分が採用していて、同じFECに関してすべてのLSPsがあって、すべてのノードができるVC-マージであると思います。
7.1. First example
7.1. 最初の例
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.
L3 loopが存在するFig.14で見せられたMPLSネットワークを考えてください。 それぞれの指示されたリンクは各ノードにFECの次の現在のホップを表します。 今、葉のノードのR1とR6はLSPの創造を開始します。
R11 ------- R10 <-------------------- R9
| | ^
| | |
| | |
v v |
R1 -------> R2 --------> R3 --------> R4 --------- R5
[leaf] ^
|
|
|
R6 -------> R7 --------> R8
[leaf]
R11------- R10<。-------------------- R9| | ^ | | | | | | vに対して| R1------->R2-------->R3-------->R4--------- R5[葉]^| | | R6------->R7-------->R8[葉]
Fig. 14 Example MPLS network (1)
Example MPLSがネットワークでつなぐ図14(1)
Ohba, et al. Experimental [Page 19] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[19ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
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.
R1とR6が同時に、ラベル要求メッセージを送って、初期の糸のTTLが255歳であると仮定してください。 まず最初に、私たちは、どうLSPを防ぐかに関する例が輪にされるのを示します。
A set of thread attributes is represented by (color, hop count, TTL).
1セットの糸の属性は(色、ホップカウント、TTL)によって表されます。
The request from R1 and R6 contains (re,1,255) and (bl,1,255), respectively.
そして、R1とR6からの要求が(re、1,255)を含んでいる、(bl、1,255) それぞれ。
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).
R3が受け取る前にR1から溯源された要求を受け取ると仮定してください。 いつと共にR3が赤の糸で最初の要求を受け取って、R3がそれを進めるか、(re、受信の入って来るリンクと出発しているリンクの両方が新たに作成されるので糸の色を変えることのない3,253)。 そして、R3は青い糸で2番目の要求を受け取ります。 今回、出発しているリンクはそうです。既に、存在しています。 したがって、R3はすなわち、色を変えると共に広がるのが新しい茶色の糸を作成して、要求を転送する糸(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".
R2が(re、6,250)でR10から要求を受け取るとき、それは、赤い糸が輪を形成して、赤い糸を失速させるのがわかります。 次に、R2は、未知でホップカウントの紫色の糸を作成して、川下で(Pu、U、255)がある要求をR3に送ることによって、それを広げています。(そこでは、「U」が「未知」を表します)。
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.
その後に、R2は(Br、7,252)でR10から別の要求を受け取ります。 茶色の糸は紫色の糸に合併されています。 R2は要求を全く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.
糸ループと売店が紫色の糸であることが他方では、紫色の糸は存在するのによる色を変えないでリンクを一周させるために動いていて、R2は、わかります。 容認された糸のホップカウントが未知であるので、糸は全くそれ以上作成されません。 この場合、いいえは、巻き戻すのを縫うように通ります。起こります。 ネットワークの現状はFig.15に示されます。
Ohba, et al. Experimental [Page 20] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[20ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
*: 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)
(Pu、U) R11------- R10<。-------------------- R9| | ^ | |(Pu、U)* | | | |(Pu、U) vに対して| R1------->R2-------->R3-------->R4--------- R5[葉](re、1)(Pu、U)^(Pu、U)| | (bl、3) | R6------->R7-------->R8[葉](bl、1)(bl、2)
Fig.15 The network state
Fig.15はネットワーク状態です。
Then R10 changes its next hop from R2 to R11.
そして、R10は次のホップをR2から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.
R10が古い川下の紫色の糸をリンクさせるので、それは最初に、次の古いホップR2に経路分解メッセージを送ります。紫色の糸を引っ込めるために。 次に、それは、未知でホップカウントの緑色の糸を作成して、(gr、U、255)がある要求をR11に送ります。
When R2 receives the teardown message from R10, R2 removes the stalled incoming link between R10 and R2.
R2がR10から分解メッセージを受け取るとき、R2はR10と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.
他方では、緑色の糸はR1に達します、そして、ゼロ〜未知までHmaxをアップデートします。 この場合、R1は既に既存の出発しているリンクで新しい入って来るリンクの上に糸を受け取るので色を変えると共に広がっていますが、広げられた糸を実行します。 その結果、R1は未知でホップカウントのオレンジの糸を作成して、それをR2に広げています。
The orange thread goes round through existing links without changing color, and finally it is stalled at R1.
オレンジの糸は色を変えないで存在することでリンクを一周させるために動いています、そして、最終的にそれはR1で失速します。
The state of the network is now shown in Fig.16.
ネットワークの事情は現在、Fig.16に示されます。
Ohba, et al. Experimental [Page 21] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[21ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
*: 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)
または、または、(U)、(U)R11<。------ R10<。-------------------- R9| | ^ |または、(U)* | | | | |または、(U) v| | R1------->R2-------->R3-------->R4--------- または、または、または、R5[葉]、(U)、(U)^、(U)| | (bl、3) | R6------->R7-------->R8[葉](bl、1)(bl、2)
Fig.16 The network state
Fig.16はネットワーク状態です。
Then R4 changes its next hop from R9 to R5.
そして、R4は次のホップをR9から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.
R4がオレンジの糸を広げているので、それは最初に、古いルートの上のオレンジの糸を引っ込めるために次の古いホップR9に分解メッセージを送ります。 次に未知でホップカウントの黄色い糸を作成して、要求メッセージを送る、(あなた、U、255) 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.
R5が出口ノードであるので、黄色い糸の巻き戻しは始まります。 R5はラベルマッピングメッセージを返します。 ホップごとに上流へラベルマッピングメッセージを返すとき、各ノードで糸の巻き戻し手順を実行します。
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.
R11からオレンジのスレッドの退出を受ける前にR1がラベルマッピングメッセージを受け取るなら、R1はラベルマッピングメッセージをR11に返します。 オレンジのスレッドの退出を受けると、R1は、川下で知られているホップカウントについて通知するために(tr、1,255)で透明な糸を作成して、アップデートメッセージを送ることによって、それを広げるでしょう。
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.
さもなければ、ラベルマッピングメッセージを受け取る前にR1がオレンジのスレッドの退出を受けるなら、R1は失速している入って来るオレンジのリンクを取り外して、出発しているオレンジの糸の巻き戻しを待っています。 R1がR2からラベルマッピングメッセージを受け取るとき、最終的に、透明な糸(tr、1,255)を作成します、そして、川下でそれを広げてください。
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.
そして、どちらの場合も、合併しているLSP、(R1、-、>R2)、(R6->、R7、-、>R8)、-、>R3、-、>R4->、R5)、設立される、あらゆるノードが正しいリンクホップカウントを得ます。 最終的なネットワーク状態はFig.17で見せられます。
Ohba, et al. Experimental [Page 22] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[22ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
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)
R11<。------ R10<。-------------------- R9| | | | | | | | | v| | R1------->R2-------->R3-------->R4-------->R5[葉](tr、1)(tr、2)^(tr、4)(tr、5)| | (tr、3) | R6------->R7-------->R8[葉](tr、1)(tr、2)
Fig.17 The final network state
Fig.17は最終的なネットワーク状態です。
7.2. Second example
7.2. 2番目の例
+----- R6----> R7-----+
| |
| v
R1---->R2 R4----->R5
| ^
| |
+--------->R3---------+
+----- R6---->R7-----+ | | | R1に対して---->R2 R4----->R5| ^ | | +--------->R3---------+
Fig.18 Example MPLS network (2)
Fig.18 Example MPLSネットワーク(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).
確立したLSP R1->がFig.18に、あると仮定してください、R2->、R3、-、ホップがR2でR3から変化するR5、および次の>R4->、R6。 R2は赤い糸(re、2,255)で要求をR6に送ります。 R4、(re、4,253)範囲がある要求であるときに、それは色を変えるのに糸をR5に広げます。 したがって、新しい緑色の糸は、(gr、5,255)でアップデートメッセージを送ることによって、R4に作成されて、R5に広げられます。
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.
R5がアップデートを受けるとき、それは、入って来るリンクホップカウントを5にアップデートして、アップデートのために、ack(または、成功コードがある通知メッセージ)を返します。 R4がアップデートのためにackを受けるとき、それはラベルマッピングメッセージを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.
R2が新しいルートに関するラベルマッピングメッセージを受け取るとき、それは分解メッセージをR3に送ります。 いつR4は分解メッセージを受け取るか、そして、それは送りません。Hmaxが変化しないので、アップデートをR5に送ります。 現在の確立したLSP R1->、R2->、R6、-、>R7->、R4、->R5を入手します。
Then, the next hop changes again at R2 from R6 to R3.
そして、次のホップは再びR2でR6からR3に変化します。
Ohba, et al. Experimental [Page 23] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[23ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
R2 sends a request with a blue thread (bl,2,255) to R3. R3 forwards the request with (bl,3,254) to R4.
R2は青い糸(bl、2,255)で要求をR3に送ります。 R3は(bl、3,254)がある要求をR4に転送します。
When R4 receives the request, it immediately returns a label mapping message to R3 since Hmax does not change.
R4がすぐに要求を受け取るとき、Hmaxが変化しないので、それはラベルマッピングメッセージをR3に返します。
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.
R2が新しいルートに関するラベルマッピングメッセージを受け取るとき、それは分解メッセージをR6に送ります。 分解メッセージはR4に達します、透明な糸(tr、4,255)でアップデートメッセージのR5に引き金となって、Hmaxが4〜3まで減少するので。 ackを返さないで、R5は入って来るリンクホップカウントを4にアップデートします。
8. Thread control block
8. 糸の制御ブロック
A thread control block (TCB) is maintained per LSP at each node and may contain the following information:
糸の制御ブロック(TCB)は、各ノードでLSP単位で保守されて、以下の情報を含むかもしれません:
- 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
- 入って来るリンクEach入来がリンクするFEC(状態)は以下の属性を持っています: o 隣人: 上流の隣人ノードアドレスo色: 容認された糸の色のoホップカウント: 容認された糸のホップカウントoラベルo S-旗: aはリンクを失速させました--出発しているリンクEach出発しているリンクには以下の属性があるのを示します: o 隣人: 川下の隣人ノードアドレスo色: 容認された糸の色のoホップカウント: 容認された糸のホップカウントoラベルo C-旗: 次の現在のホップへのリンクを示します。
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.
ラベルなしがまだ割り当てられている入って来るリンクの上に透明な糸を受け取るか、または非透過の色を格納するなら、FSMに入らないで、糸を捨ててください。 エラーメッセージを送付者に返すかもしれません。
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 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).
入って来るリンクの上に糸を受け取るときはいつも、以下の動作はFSMに入るのに承認させられます: (1) (2) 古い糸の色とホップカウントを取り替えて、容認された糸の色とホップカウントをリンクに格納してください、そして、イベントスイッチに「Recv糸」出来事の中で使用される以下の旗を設定してください(セクション8.1を見てください)。
Ohba, et al. Experimental [Page 24] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[24ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
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.
o (CL-旗)に旗を着色してください: 容認された糸が有色であるなら、セットしてください。o Loopは(LP-旗)に旗を揚げさせます: 容認された糸が輪を形成するなら、セットしてください。新しいリンクの上のo Arrivedは(NL-旗)に旗を揚げさせます: 容認された糸が新しい入って来るリンクの上に届くなら、セットしてください。
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.
LP-旗が設定されるなら、入って来るリンクLがあるに違いありません、受信リンクを除いて。(それは、容認されたものと同じ糸の色を格納します)。 リンクLが属するTCBは「検出TCB」と呼ばれます。 TCBが受信LSRができるVC-マージと、検出しているTCBと受信であるなら同じである、さもなければ、2TCBsが異なっています。
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.
働く前に、糸が広がっていて、糸のTTLは1つ減少します。 結果として起こるTTLがゼロになるなら、糸は、広げられませんが、静かに捨てられます。 さもなければ、糸は拡張されています、そして、拡張糸のホップカウントと色は出発しているリンクに格納されます。
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.
容認された糸の色と広がっている糸の色が異なるならノードが糸の巻き戻し出来事を受けるとき、FSMに入らないで、それは出来事を捨てます。
8.1. Finite state machine
8.1. 有限状態機械
An event which is "scheduled" by an action in an FSM must be passed immediately after the completion of the action.
動作の完成直後FSMで動作で「計画をされる」出来事を流れなければなりません。
The following variables are used in the FSM:
以下の変数は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
o Ni: 非失速している入来の数はo Hmaxをリンクします: 最も大きい入って来るホップカウントo Hout: 次の現在のホップo Hrecのために出発しているリンクのカウントを飛び越してください: 容認された糸のホップカウント
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.
FSMでは、Hmaxが未知と等しいなら、(Hmax+1)のための値は未知のホップカウントプラス1のために予約された値になります。 例えば、未知の=Hmax=255であるなら、値(Hmax+1)は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.
TCBには、3つの州があります。 ヌルで、有色で、透明です。 TCBが州のNullにあるとき、出発しているリンクとNi=0が全くありません。 州のColoredは、ノードが次の現在のホップのために出発しているリンクの上の有色の糸を広げていることを意味します。 州の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.
旗の値、「1インチが表す、旗が設定される、「0インチが表す、旗は設定されません、そして、「*」 旗が評価する手段は1か0どちらかのです」。
Ohba, et al. Experimental [Page 25] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[25ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
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.
FSMは次の現在のホップの上に次の古いホップと1個の有色の出発しているリンクの上に1個の透明な出発しているリンクを持たせます。 しかしながら、それは次の古いホップの上に有色の出発しているリンクを持つことができません。
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.
イベントAction New州のRecv糸のFlags CL LP NL0**は何もしません。 変化がない、1 0、*、ノードが出口であるなら、糸はTransparentを巻き戻し始めてください、そして、透明への受信リンクの色を変えてください。 さもなければ、Coloredが色を変えないで、容認された糸を広げてください。 受け取られているのが糸を通す1 1*売店。 Hrec<未知であるなら、どんな変化スケジュールも検出しているTCBのために出来事を「未知には、リセットしませんでした」。
Next hop If eligible-leaf, create a colored thread and Colored acquisition extend it.
有色の糸を作成して、Ifが次にページをめくって適任の跳び、Colored獲得はそれを広げています。
Others Silently ignore the event. No change
他のものSilentlyは出来事を無視します。 変化がありません。
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
イベントAction New州のRecvは**Hmax+1<Hout<未知であるならFlags CL LP NL0に糸を通して、有色のいいえ変化糸を作成して、それを広げています。 さもなければ、何もしないでください。 1 0、*Hmax<Houtであるなら、容認された糸を合併してください。 または、いいえがOtherwiseを変えて、糸を広げている、(NL=1であるなら)、変化しないで(NL=0であるなら)、着色してください。 受け取られているのが糸を通す1 1*売店。 Ni=0であるなら、ノードは適任の葉、Null開始糸の引き下がることではありません。 Ni>0とHrec<未知であるなら、検出しているTCBのために「変化未知がないことへのリセット」出来事の計画をしてください。 さもなければ、何もしないでください。 変化がありません。
Ohba, et al. Experimental [Page 26] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[26ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
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.
巻き戻されたPropagateは有色の糸を広げているTransparentを前のホップに巻き戻しながら、縫うように通ります。 透明へのすべての送受信のリンクに格納された色を変えてください。 Hmax+1<Houtであるなら、透明な糸を広げてください。 どのC-旗=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
対応する入来がリンクするよそよそしいRemove。 Ni=0とノードが適任の葉でないなら、Nullは次のホップに引き下がる糸を伝播します。 さもなければ、Hmax+1<Hout<未知であるならaが糸に着色しなかった変化を全く引き起こしてください、そして、それを広げてください。 さもなければ、何もしないでください。 変化がありません。
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.
そこの次のホップIfは既に次の獲得が飛び越すTransparentのための出発しているリンクであり、何もしないでください。 (ノードが古い経路を保有するときだけ、本件は起こります。) さもなければ、有色の糸を作成してください、そして、変化を全く広げないでください。それ。
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
外向的なIfがリンクする次のホップは透明です、そして、いいえ変化損失ノードはリンクを保有できます、そして、次のホップは生きています、そして、何もしないでください。 さもなければ、以下の行動を取ってください。 次のホップのために引き下がる糸を開始してください。 ノードが新しい出口になるなら、スケジュールはこのTCBのために出来事を「巻き戻しました」。 Ni=0であるなら、Nullに動いてください。 ヌルOtherwise、何もしないでください。 変化がありません。
Reset to Create a colored thread of hop count unknown No change unknown and extend it.
ホップカウントの未知のいいえ変化未知の有色の糸をCreateにリセットしてください、そして、それを広げてください。
Others Silently ignore the event. No change
他のものSilentlyは出来事を無視します。 変化がありません。
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.
イベントAction New州のRecvはFlags CL LP NL0*に糸を通します。*Hmax+1<Houtであるなら、透明な糸を広げてください。 変化がない、1 0、*、ノードが出口であるかHmax<Hout、変化ノー、が透明、そして、スタート糸の巻き戻しへの受信リンクの色を変えるなら。 そうでなければ、着色されるか(NL=1であるなら)、または色を変えないで(NL=0であるなら)広げていて、糸を広げています。
Ohba, et al. Experimental [Page 27] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[27ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
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
対応する入来がリンクするよそよそしいRemove。 Ni=0とノードが適任の葉でないなら、Nullは次のホップに引き下がる糸を伝播します。 さもなければ、Hmax+1<Houtであるならどんな変化のa透明な糸も作成しないでください、そして、それを広げてください。 さもなければ、何もしないでください。 変化がありません。
Next hop Create a colored thread and extend it. Colored acquisition
aが着色した次のホップCreateはそれに糸を通して、広げています。 獲得に着色されます。
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
ノードが出発しているいいえ変化損失リンクと次のホップを保有できる次のホップIfは生きていて、何もしないでください。 さもなければ、以下の行動を取ってください。 糸の引き下がることを開始してください。 Ni=0であるなら、Nullに動いてください。 ヌルOtherwise、何もしないでください。 変化がありません。
Others Silently ignore the event. No change
他のものSilentlyは出来事を無視します。 変化がありません。
9. Comparison with path-vector/diffusion method
9. 経路ベクトル/拡散法との比較
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 LSPの長さに従って、経路ベクトルのサイズは増加しますが、糸のサイズは一定です。 したがって、糸のアルゴリズムで使用されるメッセージのサイズはネットワークの規模かトポロジーのそばで影響を受けないです。 さらに、能力を合併する糸は傑出しているメッセージの数を減少させます。 これらは改良されたスケーラビリティに通じます。
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.
o 糸のアルゴリズムで、特定のLSPのために次のホップを変えているノードは新しい経路にそれとLSP出口の間にないノードしか対話しなければなりません。 しかしながら、経路ベクトルアルゴリズムで、ノードがそれとLSP出口の間にないノードにかかわる拡散計算を開始するのが必要です。
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 糸のアルゴリズムは命令された川下要求次第の配分と命令された川下の配分の両方で使用によく合っています。 しかしながら、経路ベクトル/拡散アルゴリズムはしっかり命令された川下の配分に結びつけられます。
Ohba, et al. Experimental [Page 28] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[28ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
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 迅速な経路(re)構成を達成して、糸のアルゴリズムは再試行なしです。 拡散アルゴリズムは、すべての上流のノードを参照するためにルート変化ポイントのノードがそうしなければならなくて以来の経路再構成時間を遅らせる傾向があります。
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.
o 糸のアルゴリズムで、L3 loopが新しい経路にあれば、ノードは、古い経路を使用し続けることができます、経路ベクトルアルゴリズムのように。
10. Security Considerations
10. セキュリティ問題
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.
本書では指定された手順の使用には、一般に、どんなMPLS手順の使用でも存在するかもしれないそれ以外のどんなセキュリティ影響力もありません。
11. Intellectual Property Considerations
11. 知的所有権問題
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.
東芝、そして/または、シスコは本書では明らかにされた技術のいくつかのために特許か他の知的所有権保護を求めるかもしれません。 何かこのドキュメントから起こる規格が東芝、シスコ、東芝、そして/または、シスコに配属された1つ以上の特許であるか、または保護されるようになるなら、妥当で非差別している諸条件でそれらの特許を明らかにして、それらを認可するつもりであってください。
12. Acknowledgments
12. 承認
We would like to thank Hiroshi Esaki, Bob Thomas, Eric Gray, and Joel Halpern for their comments.
彼らのコメントについてHiroshi江崎、ボブ・トーマス、エリック・グレー、およびジョエル・アルペルンに感謝申し上げます。
Ohba, et al. Experimental [Page 29] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[29ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
13. Authors' Addresses
13. 作者のアドレス
Yoshihiro Ohba Toshiba Corporation 1, Komukai-Toshiba-cho, Saiwai-ku Kawasaki 210-8582, Japan
芳広オオバ東芝1、Komukai東芝町、川崎210-8582、幸区日本
EMail: yoshihiro.ohba@toshiba.co.jp
メール: yoshihiro.ohba@toshiba.co.jp
Yasuhiro Katsube Toshiba Corporation 1, Toshiba-cho, Fuchu-shi, Tokyo, 183-8511, Japan
Yasuhiro Katsube東芝1、東芝町、府中市、東京、183-8511、日本
EMail: yasuhiro.katsube@toshiba.co.jp
メール: yasuhiro.katsube@toshiba.co.jp
Eric Rosen Cisco Systems, Inc. 250 Apollo Drive Chelmsford, MA, 01824
Driveチェルムズフォード、エリックローゼンシスコシステムズInc.250アポロMA 01824
EMail: erosen@cisco.com
メール: erosen@cisco.com
Paul Doolan Ennovate Networks 330 Codman Hill Rd Marlborough MA 01719
ポールDoolan Ennovateネットワーク330Codmanヒルマールバラ第MA 01719
EMail: pdoolan@ennovatenetworks.com
メール: pdoolan@ennovatenetworks.com
14. References
14. 参照
[1] Callon, R., et al., "A Framework for Multiprotocol Label
Switching", Work in Progress.
[1]Callon、R.、他、「Multiprotocolラベルの切り換えのための枠組み」、ProgressのWork。
[2] Davie, B., Lawrence, J., McCloghrie, K., Rosen, E., Swallow, G.,
Rekhter, Y. and P. Doolan, "MPLS using LDP and ATM VC Switching",
RFC 3035, January 2001.
[2] デイビー、B.、ローレンス、J.、McCloghrie、K.、ローゼン、E.は飲み込まれます、Rekhter、Y.、およびP.Doolan、G.、「MPLSは自由民主党と気圧VCの切り換えを使用し」て、RFC3035、2001年1月。
[3] Rosen, E., et al., "A Proposed Architecture for MPLS", Work in
Progress.
[3] ローゼン、E.、他、「MPLSのための提案された構造」、ProgressのWork。
[4] Andersson, L., Doolan, P., Feldman, N., Fredette, A. and B.
Thomas, "LDP Specification", RFC 3036, January 2001.
[4] アンデションとL.とDoolanとP.とフェルドマンとN.とFredetteとA.とB.トーマス、「自由民主党仕様」、RFC3036、2001年1月。
Ohba, et al. Experimental [Page 30] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[30ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
Appendix A - Further discussion of the algorithm
付録A--アルゴリズムのさらなる議論
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.
この付録の目的は、アルゴリズムのより多くの非公式の、そして、家庭教師のプレゼンテーションをして、それに関する何らかの動機を提供することです。 アルゴリズムの正確な仕様において、FSMは正式であるとしてみなされるべきです。
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.
ドキュメントのボディーのように、まるで1LSPしかないかのように私たちは話します。 「そうでなく、私たちはいつも」 同じLSPの…を言っているでしょう。」 また、私たちはアルゴリズムが輪の検出よりむしろ輪の防止に使用されるケースだけを考えます。
A.1. Loop Prevention the Brute Force Way
A.1。 力任せの方法で防止を輪にしてください。
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.
考えてください、そして、例えば、現在の出口ノードE.への既存のLSP B C D EノードAは、LSPを接合するのを試みます。 最終的なメッセージはBからAまでラベル結合を含んでいます、そして、Aは今LSPを接合できます、経路が輪なしであることを知っていて。このアルゴリズムで、AはメッセージをBに送らなければなりません、BからC、CからD、E.へのD。ThenメッセージをEからA.に送って戻します。
Using our terminology, we say that A created a thread and extended it downstream. The thread reached the egress, and then rewound.
私たちの用語を使用して、私たちは、Aが糸を作成して、川下でそれを広げたと言います。 糸は、出口であって、次に、巻き戻されるのに達しました。
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.
私たちは、上記の例でAがイングレスノードであると思う必要はありません。 それは問題のLSPのために次のホップを取得するか、または変えるどんなノードであるかもしれません、そして、また、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.
輪があれば、糸が出口、それが巻き戻さないそうに決して達しないのは、明確です。 何が起こりますか? 経路セットアップメッセージはただ輪の周りを旅行し続けます。 1つがそれらにホップカウントを保つなら、1つは、彼らが、ホップカウントが、ある最大値に達すると輪の周りを旅行するのを止めるのを確実にすることができます。 すなわち、人がそれで経路セットアップメッセージを受け取るとき、最大のホップは値を数えて、1つは経路セットアップメッセージを川下に送りません。
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
1つはループ糸のこの状況からどのように回復しますか? L3ルーティングが輪を壊すように、輪の何らかのノードが次のホップ変化にならなければなりません。 このノードは糸を引っ込めるでしょう。
Ohba, et al. Experimental [Page 31] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[31ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
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?
A.2。 獣の力の方法のどこが問題ですか?
Consider this example:
この例を考えてください:
A
|
B--D--E
|
C
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.
AとCが、確立したB-D-E経路を接合するのをともに試みるなら、BとDは両方の経路セットアップ試みのために状態を維持しなければならなくて、AからのものとC.Thatからのものがあって、Dは2個の糸、A-糸、およびC-糸の動向をおさえなければなりません。 一般に、確立した経路を接合するのを試みているBのずっと多くのノード上流があるかもしれません、そして、Dはそれらの皆、動向をおさえる必要があるでしょう。
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.
VCマージが使用されていないなら、これは実際にそれほど悪くはありません。 VCマージがなければ、Dは本当にそれぞれの上流のノードあたり1LSPをとにかく支持しなければなりません。 しかしながら、VCマージが使用されているなら、LSPを支持するのは、1つがそれぞれの上流のリンクに状態を維持するだけであるのを必要とします。 また、輪の防止のテクニックも必要であるなら、ノードで維持された状態の量がLSPで上流であるノードの数にというよりむしろthenodeが持っている上流のリンクの数に比例しているのは、有利でしょう。
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.
私たちは、これらの2つの問題を解決するようにこの獣の力の計画を変更できますか? 私たちはそうすることができます。 どのようにこれをするかを示すために、私たちは2つの概念を紹介します: ホップカウント、および糸の色に糸を通してください。
A.3. Thread Hop Count
A.3。 糸のホップカウント
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.
後方に(上流へ)リンクで上流へ最も遠い葉のノードへのそのリンクから旅するつもりであったならLSP木のあらゆるリンクがあなたが横断するホップの数でラベルされると仮定してください。
For example, the following tree would have its links labeled as follows:
例えば、以下の木で、以下の通りとリンクをラベルするでしょう:
Ohba, et al. Experimental [Page 32] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[32ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
1 2
A---B---C K
| |
|3 |1
| |
| 4 5 | 6 7
D---G---H---I---J
|
|2
1 |
E---F
1 2---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.
リンクAB、EF、あなたがこれらのリンクからワンバウンドであるだけであるのに上流へなることができるので、KHは1つとラベルされます。 リンク紀元前、およびFDはそうです。2とラベルされて、あなたが行くことができるので、2はこれらのリンクから上流を飛び越します。 このリンクなどから4つのホップを上流へ旅行するのが可能であるので、リンクDGは4とラベルされます。
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.
川下のリンクに関連しているホップカウントがどんなノードの、十二分に最も大きいホップカウントが上流のリンクに関連づけた1つであることにも注意してください。
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".
リンクホップカウントを維持するために、私たちは、経路セットアップメッセージにおけるホップカウントを運ぶ必要があります。 例えば、どんな上流のリンクも持っていないノードは、1のホップカウントを川下のリンクに割り当てて、それが川下に送る経路セットアップメッセージにその値を格納するでしょう。 一度、値は経路セットアップメッセージに格納されて、私たちは言及するかもしれません。それには、「糸のホップカウント」があります。
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.
経路セットアップメッセージを川下に送るとき、最も大きい入って来るリンクがカウントを飛び越すよりさらに1であるように川下のリンクのホップカウント(そして、糸のホップカウント)を設定します。
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.
ノードNにはすべてが適切に設定するホップカウントとのいくつかの入って来るリンクと出発しているリンクがあると仮定してください。そうすれば、Nは現在、新しい入って来るリンクを入手します。 新しい入って来るリンクのリンクホップカウントが既存の入って来るリンク、川下のリンクホップカウントのすべてのものより単に大きい、変えなければなりません。 この場合、新しくて、より大きい糸のホップカウントを運びながら、コントロールメッセージを川下に送らなければなりません。
Ohba, et al. Experimental [Page 33] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[33ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
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.
他方では、Nが既存の入来がリンクするすべてのリンクホップよりカウント以下であるリンクホップカウントとの新しい入って来るリンクを入手するなら、川下のリンクホップカウントは変わりがありません、そして、メッセージを全く川下に送る必要はありません。
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.
Nが入って来るリンクのいずれでもホップカウントが最も大きかった入って来るリンクをなくすと仮定してください。 この場合、川下のリンクホップカウントをより小さくしなければなりません、そして、メッセージはこれを示すために川下に送られる必要があります。
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新しい入って来る糸が受け取られているA.3.1、川下でそれを広げてください、ホップカウントである場合にだけ、最も大きい入って来る糸はそうです。
A.3.2 Otherwise, rewind the thread.
A.3.2、さもなければ、糸を巻き戻してください。
A.3.3 An egress node would, of course, always rewind the thread.
A.3.3、出口ノードはもちろんいつも糸を巻き戻すでしょう。
A.4. Thread Color
A.4。 糸の色
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.
ノードは次のホップ変化か次のホップ獲得の結果、新しい糸を作成します。 糸がノードによって作成されるときはいつも、ノードがユニークな「色」をそれに割り当てると思いましょう。 この色は時間とスペースの両方で特有であることです: コード化はノードによって維持された付番スペースからのユニークな事象IDで連結されたノードのIPアドレスから成ります。 ノードが川下に発信するという経路セットアップメッセージはこの色を含むでしょう。 また、ノードがそのようなメッセージを川下に送るとき、色を覚えているでしょう、そして、この色は川下のリンクの色になります。
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".
糸を巻き戻すとき(経路はセットアップされました)、色を取り除きます。 リンクは透明になります、そして、私たちは「透明な糸」であるとして時々確立したLSPについて話すつもりです。
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
ノードが以前既に見たことがある色との特定の入って来るリンクの上に糸が輪にされると、何らかのノードがメッセージを見ることに注意してください。 ノードがその色の糸を溯源してしまうだろうか、または異なった入来はそれで既にどれをリンクするだろうか。
Ohba, et al. Experimental [Page 34] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[34ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
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
A.5。 色とホップカウントとの関係
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.
カラーメカニズムとホップカウントメカニズムを結合することによって、各LSPのために1リンクあたり1つ以上の色とワンバウンドのカウントを覚えているためにノードを必要としないで、私たちは輪を防ぐことができます。
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.)
入来を広げるとき、A.5.1は川下を縫うように通ります、また、スレッドの色が川下に通過されます。(すなわち、川下のリンクの色は最も大きいホップカウントとの上流のリンクの色と同じになるでしょう。)
Note that at a given node, the downstream link is either transparent or it has one and only one color.
与えられたノードでは、川下のリンクが透明であるか、またはそれには唯一無二の1つの色があることに注意してください。
A.5.2 If a link changes color, there is no need to remember the old color.
リンクが変化するなら、A.5.2は着色して、古い色を思い出す必要は全くありません。
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.
A.5.2は、有色の糸が入って来るリンクの上のノードに届くと思います、そして、同じであるか、より大きいホップがある入って来る糸はノードによって既に数えられます、そして、ノードには、出発している有色の糸があります。 この場合、私たちは、新しい入って来る糸が出発している糸に「合併される」と言うかもしれません。
Note that when an incoming thread is merged into an outgoing thread, no messages are sent downstream.
入って来る糸が出発している糸に合併されているとき、メッセージが全く川下に送られないことに注意してください。
A.6. Detecting Thread Loops
A.6。 糸ループを検出します。
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.
もう、輪があると、何らかのノードがいつもあるのをどれが同じ色の2個の入って来る糸を手に入れるか示すことができるか、または有色の糸は創始者に戻るでしょう。 このセクションでは、私たちは糸ループがどう検出されるかに関する直感的な理解を提供するかもしれないいくつかの例を出します。
Ohba, et al. Experimental [Page 35] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[35ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
1 2
A---B---C K
| |
|3 |1
| |
| 4 5 | 6 7
D---G---H---I---J
|
|2
1 |
E---F
1 2---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.
私たちの前の例に戻って、Hが次のホップをIからE.に変えるなら起こることを設定しましょう。Hは、今新しい糸を作成して、新しい色、たとえば赤をそれに割り当てます。 それぞれHにはホップカウント1と5との2の入って来るリンクがあるので、それは、ホップカウント6を新しい川下のリンクに割り当てて、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.
Eには、現在、ホップカウント6がある入って来る赤い糸があります。 現在Eの川下のリンクホップカウントが1にすぎないので、赤い糸をFまで広げなければなりません、ホップカウント7で。 次に、Fはホップカウント8で赤い糸をDに広げています、ホップカウント10があるホップカウント9、およびGからHがあるDからG。
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.
輪が検出されるために赤い糸でHからE.Then GまでH、G変化に次のホップを支持する前にそれが赤い糸をE.Butに広げますが、入って来る赤がEによって既にリンクされる(Hから)と仮定してください。
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.6.1は、糸がノードで「失速する」と言います。 より正確に、それは失速している糸の2番目の外観です。 私たちが、入って来るリンクの上にそのノードで糸を受け取るなら糸が二度ノードを横断していますが、同じ色との別の入って来るリンクがあるか、色がノード自体によって割り当てられたものであると言うことに注意してください。
Ohba, et al. Experimental [Page 36] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[36ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
A.7. Preventing the Setup of Looping LSPS
A.7。 ループ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.
ループLSPsのセットアップを防ぐのに使用されるべきメカニズムは現在、明白であるべきです。 ノードMがノードNの次のホップと、LSPをセットアップするというN願望(既にMで存在するLSPに溶け込むために)であるなら、Nは糸を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.
Mは最初に糸が輪を形成するかどうか(Appendix A.6を見てください)確認するためにチェックします、そして、そうだとすれば、糸は失速されています。 そうでなければ、以下の手順は従われています。
A.7.1 If M receives this thread, and M has a next hop, and either:
Mがこれを受けるなら、A.7.1は縫うように通ります、そして、Mには、次のホップ、およびどちらかがあります:
- M has no outgoing thread
- Mには、どんな出発している糸もありません。
- the incoming thread hop count is larger than the hop count of all
other incoming threads,
- 入って来る糸のホップカウントは他のすべての入って来る糸のホップカウントより大きいです。
then M must extend the thread downstream.
そして、Mは川下で糸を広げなければなりません。
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、他方では、Mがこの糸を受けるか、そして、Mには次のホップがあります、そして、別の入って来る糸が、より大きいホップカウントと共にあります、そして:
A.7.2.1 if the outgoing thread is transparent, M rewinds the new incoming thread.
外向的が縫うように通るならA.7.2.1が透明である、Mは新しい入って来る糸を巻き戻します。
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.2.2が有色である、Mは新しい入って来る糸を出発している糸に合併しますが、どんなメッセージも川下に送りません。
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.3はMであるなら既にラベルをNに割り当てていなくて、時といつだけを1つに割り当てるだろうか、そして、MはNがそれに広げた糸を巻き戻します。
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.
Mが新しい糸を存在に合併するなら、A.7.4は出発している糸を着色しました、次に、新しい入って来る糸が時といつだけを巻き戻すだろうか、糸が巻き戻す外向的。
A.8. Withdrawing Threads
A.8。 糸を引っ込めます。
A.8.1 If a particular node has a colored outgoing thread, and loses or changes its next hop, it withdraws the outgoing thread.
A.8.1は特定のノードであるなら次のホップを有色の出発している糸を持って、失うか、または変えて、それは出発している糸を引っ込めます。
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.
ノードNがすぐにノードMで上流であると仮定してください。そうすれば、M.Supposeへの拡張a糸がその時NでそのNを促進するのが糸を引っ込めます。
Ohba, et al. Experimental [Page 37] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[37ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
A.8.2 If M has another incoming thread with a larger hop count, then M does not send any messages downstream.
Mに別の入来があるなら、A.8.2は、より大きいホップカウントで縫うように通って、次に、Mはどんなメッセージも川下に送りません。
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、しかしながら、よそよそしい糸にどんな入って来る糸の最も大きいホップカウントもあったなら、Mの出発している糸には、もう、適切なホップカウントと色がないでしょう。 したがって:
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.1Mは今、川下で最も大きいホップカウントで入って来る糸を広げなければなりません。 (これで、それは古い川下のリンクホップカウントと色を忘れるでしょう。)
A.8.3.2 The other incoming threads are considered to be merged into the thread which is extended.
もう片方の入来が糸を通すA.8.3.2によって拡張糸に合併されると考えられます。
A.8.4 When the last unstalled incoming thread is withdrawn, the outgoing thread must be withdrawn.
最終が入って来る糸を非失速させたとき、A.8.4がよそよそしい、出発している糸を引っ込めなければなりません。
A.9. Modifying Hop Counts and Colors of Existing Threads
A.9。 既存の糸のホップカウントと色を変更します。
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.9.1はどんな入って来る糸のためにもお釣を数えます、と「どんな入って来る糸の最も大きいホップカウント」がその結果変化したか否かに関係なく、ノードは決定しなければなりません。 そうだとすれば、川下に送られるべきメッセージを引き起こすと、また、外向的なスレッドのホップカウント、およびことによると色は変化するでしょう。
A.10. When There is No Next Hop
A.10。 Thereが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.10.1には、特定のノードであるなら有色の入って来る糸を持っていますが、次のホップは全くなくて(または、次のホップを失います)、入って来る糸は失速されています。
A.11. Next Hop Changes and Pre-existing Colored Incoming Threads
A.11。 次のホップ変化と入って来る糸に着色された先在
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.
入って来る糸を着色しましたが、新しい色で糸を作成しますが、だれのホップが数えられるかが、1である時の次のホップ変化か次のホップ獲得がノードで入って来るリンクで十二分に最も大きくなるなら、A.11.1はカウントを飛び越します。 そして、それは川下でこの糸を広げるでしょう。
Ohba, et al. Experimental [Page 38] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[38ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
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".
この新しい糸が作成されて拡張している川下の、そして、入って来る糸であるときに、A.11.2はそれに合併されています。 現在、「失速する」より以前に失速したどんな入って来る糸によってもむしろ「合併される」と考えられます。
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?
A.12。 いくつの糸が輪を走り回りますか?
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
X--->A----->B<。---Y^| | 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.
この例には、輪のA B C D-Aがあります。 しかしながら、また、Xからループに入る糸があります、Y、Z、W.Onceは検出されて、本当にある輪をZです。いかなる他の糸も輪を巻きつけるはずでなければならない理由がありません。 単に各ノードでの輪の存在をマークしているほうがよいでしょう。
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".
これをするために、私たちは「未知」のホップカウントの概念を紹介して、U.Thisホップカウント価値はいかなる他のホップカウント価値よりも大きいと見なされます。 ホップカウントUがある糸は「U糸」として知られているでしょう。
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.
知られているホップがある入って来る糸であるときに、A.12.1は売店を数えます、そして、出発している糸があります、そして、ホップカウントUを出発している糸に割り当てます、そして、私たちはまた、出発している糸に新しい色を割り当てます。
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.
その結果、そして、次のホップには、新たに割り当てられた色の入って来るU-糸があるでしょう。 これは、ホップカウントUと新しい色が割り当てられるために順番に出発している糸を引き起こします。 次に、私たちが既に与えた規則で輪の各リンクに新しい色を割り当てるでしょう、そして、これが糸を通すホップカウントU.Whenは創始者、または既に同じ色の入って来る糸を持っているいかなる他のノードにも届きます、そして、それは失速します。
Ohba, et al. Experimental [Page 39] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[39ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
In our example above, this will cause the links AB, BC, CD, and DA to be given hop count U.
私たちの例では、上では、これはリンクのAB、紀元前、CD、およびDAにホップカウント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.)
知られているホップカウントがある糸であるときに、A.12.2は有色の出発しているU-糸を持っているノードに達して、入って来る糸は出発している糸に溶け込みます。 (実際に、これはただ既に与えられている規則の結果です、Uがどんな知られているホップカウントよりもすばらしいので。)
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.
そして、W、X、Y、またはZが、それぞれ糸をD、A、B、またはCまで広げるのを試みると、それらの糸はすぐに、失速するでしょう。 かつてのすべてのリンクが輪の中にあるとして示されます、他の糸は全く輪の周りで広げられません、すなわち、他のどんなセットアップメッセージも輪を横断しないでしょう。
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
1 U1X--->A----->B<。---Y^| U| |U| Wに対して--->D<。-----C<。---Z1U1
A.13. Some Special Rules for Hop Count U
A.13。 ホップカウント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.
U-糸が知られているホップカウントで糸に遭遇すると、普通の規則は適用されます、Uがどんな知られているホップカウント価値よりも大きいのを覚えていて。
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.
しかしながら、U-糸がU-糸に遭遇すると、私たちは、ケースのための2、3の特別な規則を加える必要があります。 言うことができないので、(2個のU-糸では本当により長いです)私たちは、それぞれのU-糸が拡張されているのを確実にする必要があります。
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.
入来がU-糸を着色したなら、A.13.1は既にその色の入って来るU-糸を持っているノードに到着するか、またはそのU-糸を作成したノードに到着して、次に、糸は失速します。
(Once a loop is detected, there is no need to further extend the thread.)
(輪がいったん検出されると、さらに糸を広げる必要は全くありません。)
Ohba, et al. Experimental [Page 40] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[40ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
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.
入来がU-糸を着色したなら、A.13.2は透明な出発しているU-糸を次のホップに持っているノードに到着して、入って来る糸は拡張されています。
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.
入来がU-糸を着色したなら、A.13.3は有色の出発しているU-糸を持っているノードに到着します、そして、糸が受け取られた入って来るリンクが既にLSPの入って来るリンクであったなら、糸は拡張されています。
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".
入来がU-糸を着色したならA.13.4が有色の出発しているU-糸を持っているノードに到着して、糸が受け取られた入って来るリンクが既にLSPの入って来るリンクでなかったなら、新しいU-糸は、作成されて、広げられます。 すべての入って来る糸がそれに合併されています。 これは「色を変えるのは糸を広げます」としてこのドキュメントの本体で知られています。
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.
これらの規則は、入って来るU-糸がいつも広げられるのを(または、次に広げられる新しいU-糸に溶け込みます)確実にします、輪を形成するのは既に知られない場合。
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.
規則A.13.4の目的は何ですか? 輪を形成できますが、ループ糸を作成したノードが輪の一部でない、あるケースがあります。 規則A.13.4は、輪があるとき、実際に輪にある何らかのノードによって作成されたループ糸があるのを確実にします。 これは、糸のTTLが期限が切れる前に輪がよく検出されるのを順番に確実にします。
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.13.5は拡張されています、ノードには出発している糸があって、新しい糸が糸が受け取られた入って来るリンクが既にLSPの入って来るリンクでなかったなら、作成されて、広げられるなら。 すべての入って来る糸がそれに合併されています。 これはA.5.1の例外的なそうです。
A.14. Recovering From a Loop
A.14。 輪から、回復します。
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
1 U1X--->A----->B<。---Y^| U| |U| Wに対して--->D<。-----C<。---Z1U1
Ohba, et al. Experimental [Page 41] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[41ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
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の次のホップがDからある他のノードEに変化して、思って、その結果、輪を壊してください。 簡単さのために、私たちは、Eが出口ノードであると思うつもりです。
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:
CはD(9.1)から出発しているU-糸を引っ込めるでしょう。 それは、また、新しい糸(12.1)を作成して、新しい色をそれに割り当てて、ホップカウントU(Cの入って来る糸の最も大きいホップカウント)をそれに割り当てて、新しい糸(12.2)に他の2個の入って来る糸を合併して、新しい糸をEまで広げて、結果になるのは以下の構成です:
1 U 1
X--->A----->B<---Y
^ |
U | |U
| v
W--->D C<---Z
1 | 1
U|
v
E
1 U1X--->A----->B<。---Y^| U| |U| Wに対して--->D C<。---Z1| 1 U| 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:
CからEが巻き戻す糸、合併している糸も(8.4)を巻き戻すとき。 巻き戻しのこの過程が現在いっぱいに前で続くことができる、ページをめくります。 もちろん、これが起こっている間、Dは外向的な糸のホップカウントがUではなく、2であるべきであり、この変更を(9.3)にすることに注意するでしょう。 その結果、Aは、外向的なホップカウントがUではなく、3であるべきであり、この変更を行うことに注意するでしょう。 それで、いつかこれから先、私たちは以下を見るかもしれません:
1 3 1
X--->A----->B<---Y
^ |
2 | |U
| v
W--->D C<---Z
1 | 1
U|
v
E
1 3 1、X--->A----->B<。---Y^| 2 | |U| Wに対して--->D C<。---Z1| 1 U| Eに対して
Ohba, et al. Experimental [Page 42] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[42ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
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
1 3 1、X--->A----->B<。---Y^| 2 | |4 | Wに対して--->D C<。---Z1| 1 5| Eに対して
with all threads transparent, and we have a fully set up non-looping path.
すべてが透明な状態で縫うように通ります、そして、私たちはaに非ループ経路を完全にセットアップさせます。
A.15. Continuing to Use an Old Path
A.15。 古い経路を使用し続けています。
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.
これが完了しているなら、何らかのノードには、透明な出発している糸(前の経路)と有色の出発している糸(セットアップされる新しい経路)の両方があるかもしれません。 2個の糸のための川下のリンクが異なる場合にだけ、これは起こるでしょう。 出発している糸が巻き戻す(そして、透明になります)有色、前の経路が引き下がるべきであるとき、引き下がってください。
Ohba, et al. Experimental [Page 43] RFC 3063 MPLS Loop Prevention Mechanism February 2001
オオバ、他 実験的な[43ページ]RFC3063MPLSは防止メカニズム2001年2月に輪にします。
Full Copyright Statement
完全な著作権宣言文
Copyright (C) The Internet Society (2001). All Rights Reserved.
Copyright(C)インターネット協会(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.
それに関するこのドキュメントと翻訳は、コピーして、それが批評するか、またはそうでなければわかる他のもの、および派生している作品に提供するか、または準備されているかもしれなくて、コピーされて、発行されて、全体か一部広げられた実現を助けるかもしれません、どんな種類の制限なしでも、上の版権情報とこのパラグラフがそのようなすべてのコピーと派生している作品の上に含まれていれば。 しかしながら、このドキュメント自体は何らかの方法で変更されないかもしれません、インターネット協会か他のインターネット組織の版権情報か参照を取り除くのなどように、それを英語以外の言語に翻訳するのが著作権のための手順がインターネットStandardsの過程で定義したどのケースに従わなければならないか、必要に応じてさもなければ、インターネット標準を開発する目的に必要であるのを除いて。
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 RFC Editor function is currently provided by the Internet Society.
RFC Editor機能のための基金は現在、インターネット協会によって提供されます。
Ohba, et al. Experimental [Page 44]
オオバ、他 実験的[44ページ]
一覧
スポンサーリンク
