Multi-Protocol Label Switching WG Yoshihiro Ohba
Internet-Draft Yasuhiro Katsube
Expiration Date: January 1999 Toshiba
Eric Rosen
Cisco Systems
Paul Doolan
Ennovate Networks
July 1998
MPLS Loop Prevention Mechanism
<draft-ohba-mpls-loop-prevention-01.txt>
Status of this Memo
This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other documents
at any time. It is inappropriate to use Internet-Drafts as
reference material or to cite them other than as "work in progress."
To learn the current status of any Internet-Draft, please check the
"1id-abstracts.txt" listing contained in the Internet-Drafts Shadow
Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or
ftp.isi.edu (US West Coast).
Abstract
This paper presents a simple mechanism, based on 'threads', which
can be used to prevent 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
ingress-initiated ordered control or the egress-initiated ordered
control. 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. [Page 1]
Internet-Draft draft-ohba-mpls-loop-prevention-01.txt July 1998
Table of contents
1 Introduction ........................................ 2
2 Definitions ......................................... 3
3 Thread mechanism .................................... 4
3.1 Thread ............................................. 4
3.2 Loop prevention algorithm ........................... 5
3.3 Why this works ...................................... 6
3.4 Using old path while looping on new path ............ 7
3.5 How to deal with egress-initiated ordered control ... 7
3.6 How to realize load splitting from the ingress node . 8
4 Modification to LDP specification ................... 8
4.1 LDP objects ......................................... 8
4.2 Advertisement class messages ........................ 10
5 Examples ............................................ 12
5.1 First example ....................................... 12
5.2 Second example ...................................... 16
6 Comparison with path-vector/diffusion method ........ 16
7 Security considerations ............................. 17
8 Intellectual property considerations ................ 17
9 References .......................................... 17
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. The thread mechanism is a generalization
of [1].
When an LSR finds that it has a new next hop for a particular FEC,
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.
Only a single thread for an LSP is ever extended to a particular
next hop as long as the thread length does not change. The only
state information that needs to be associated with a particular next
hop for a particular LSP is the thread color and length.
The procedures for determining just how far downstream a thread must
be extended are given in section 3.
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 provides 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 length, but when the thread has been rewound,
Ohba, et al. [Page 2]
Internet-Draft draft-ohba-mpls-loop-prevention-01.txt July 1998
they need only remember its length.
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
ingress-initiated ordered control or the egress-initiated ordered
control [2,3].
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 length of the LSP. 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.
The thread mechanism contains a number of significant improvements
when compared to the mechanism described in the previous version of
this internet draft. In particular:
o The thread mechanism allows a node whose next hop changes to
continue using the old LSP while setting up the new LSP (or
while waiting for the L3 routing to stabilize, so that a new
loop-free LSP can be set up)
o When a loop is detected, path setup is delayed, but it is
automatically resumed when the L3 routing stabilizes and the
loop disappears. No retry timers are needed.
o "Color" only has to be remembered while a path is being set up.
Once it is set up, the "color" (though not the length) can be
forgotten.
In this paper, we assume unicast LSPs. The loop prevention for
multicast LSPs is for further study.
2. Definitions
An LSP for a particular Forwarding Equivalence Class (FEC) [4] can
be thought of as a tree whose root is the egress LSR for that FEC.
With respect to a given node in the tree, we can speak of its
"downstream link" as the link which is closest to the root; the
node's other edges are "upstream links".
The term "link", as used here, refers to a particular relationship
on the tree, rather than to a particular physical relationship. In
the remainder of this section, when we will speak of the upstream
and downstream links of a node, we are speaking with reference to a
single LSP tree for a single FEC.
Ohba, et al. [Page 3]
Internet-Draft draft-ohba-mpls-loop-prevention-01.txt July 1998
In the case of non-VC-merging, multiple links of the same FEC
between the neighboring nodes must be identified by identifiers that
are locally assigned by the upstream node of the links.
A leaf node is a node which has no upstream links.
A "trigger node" is any node which (a) acquires a new next hop
(i.e., either changes its next hop, or gets a next hop when it
previously had none) for a particular FEC, and (b) needs to have an
LSP for that FEC.
An LSP length at a node is represented by a hop count from the
furthest leaf node to that node. The LSP length at a leaf node is
zero.
In the remainder of the paper, we assume the "downstream-on-demand"
is used as the label allocation method between neighboring nodes,
although the thread mechanism is applicable to the upstream
allocation method.
3. Thread mechanism
3.1. Thread
A thread is an object used for representing a loop-prevention
process which extends downstream. The downstream end of a thread is
referred to as the "thread head".
A thread has a color that is assigned at the node that creates the
thread. The color is globally unique in the FEC.
A thread is always associated with a particular LSP (for a
particular FEC). The "length" of a thread is the number of hops
from the thread head to the node which is furthest upstream of it on
the LSP. An "unknown" length which is greater than any other known
length is used in a certain situation (see section 3.2).
A thread has a TTL which is decremented by one (except for a special
"infinity" value, see section 4) as the thread is extended without
changing its color.
For a given LSP, at a given LSR, there can be one "incoming thread"
for each upstream neighbor, and one "outgoing thread" to the
downstream neighbor. That is, one of the incoming threads is
extended downstream. If a node is the creator of a thread, the
thread becomes a "virtual incoming thread" whose upstream neighbor
is the node itself. A non-virtual incoming thread is referred to as
an "actual incoming thread".
When a thread is extended, it retains its color, but its length
becomes the maximum incoming thread length plus 1.
Ohba, et al. [Page 4]
Internet-Draft draft-ohba-mpls-loop-prevention-01.txt July 1998
If a thread head of a given color reaches a node which already has a
thread of that color, then a loop has been detected.
When a node changes the color of its outgoing thread, it notifies
its downstream neighbor by means of LDP messages. The downstream
neighbor must process these messages in order.
3.2. Loop prevention algorithm
The ingress-initiated ordered control is assumed here, however, the
algorithm can be adapted to egress-initiated ordered control (see
section 3.4).
When a trigger node requests a label assignment to its downstream
neighbor, it creates a thread and extends it downstream.
The thread is given an initial length corresponding to the number of
hops between the trigger node and the furthest upstream leaf. It is
given a color which consists of the trigger node's IP address,
prepended to an event identifier which is assigned by the trigger
node. The trigger node will never reuse an event identifier until
sufficient time has passed so that we can be sure that no other node
in the network has any memory of the corresponding color.
A colored thread is extended downstream until one of the following
events occurs:
(i) the thread head reaches an egress node;
(ii) the thread head reaches a node where there is already an
ESTABLISHED LSP for the thread, with a KNOWN length which is no
less than the thread length;
(iii) the thread head reaches a node which already has an actual or
a virtual incoming thread of that color;
(iv) the thread TTL becomes zero;
(v) the thread head reaches a node where the maximum incoming thread
length is not updated and there is another actual incoming
thread.
o In the case of (i) or (ii), the thread is assured to reach the
egress node without forming a loop. Therefore the thread is
"rewound". When a thread is rewound, each node takes the
following actions. For each upstream link, it assigns a label
to the LSP and distributes that label LSP upstream, if needed.
It resets all incoming and outgoing thread colors to
"transparent". It sets the longest length among actual incoming
threads to the LSP length. If the outgoing thread length is
"unknown" and the obtained LSP length becomes known, it notifies
downstream of the LSP length (by using a "transparent" thread).
Ohba, et al. [Page 5]
Internet-Draft draft-ohba-mpls-loop-prevention-01.txt July 1998
When the thread is rewound back to the trigger node, the LSP
setup completes.
o In the case of (iii) and (iv), the thread is neither extended
nor rewound. It is blocked at the node. In the case of (iii),
the following actions are taken. If the node is not the creator
of the thread, it creates a new thread with "unknown" length and
extends it downstream. Otherwise, if it is not a leaf node and
there is no other actual incoming thread, it withdraws the
outgoing thread (this will cause a thread reconstruction, see
section 3.3).
o In the case of (v), the received thread is "merged" into the
outgoing thread and no message is sent to the downstream
neighbor.
When a trigger node is attempting to set up a new LSP, it also tells
its old next hop that it is withdrawing the thread that goes through
it to the old next hop. This will cause the old next hop to
withdraw one of its incoming threads.
When an incoming thread is withdrawn, if there is no actual incoming
thread, the outgoing thread is also withdrawn unless the node
becomes a new leaf node. Otherwise, if it is the one currently
being extended, a new thread is created and extended.
A transparent thread is extended when a node notifies the downstream
neighbor on an established LSP of an LSP length update or a thread
withdrawal without releasing the LSP. No rewinding is needed for
transparent threads.
A virtual incoming thread is removed when the corresponding outgoing
thread is replaced or withdrawn.
3.3. Why this works
The above procedures ensure that once a looping thread is detected,
path setup along the LSRs in that thread is effectively stalled
until the L3 routing changes so as to remove the loop.
How can we be sure that the any L3 loop will be detected by these
procedures when a thread length 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.)
Remember that after a routing change, a path cannot be set up (i.e.,
labels cannot be assigned) until the thread resulting from the
routing change is rewound, and the act of rewinding the thread
causes the thread lengths to be set consistently along the path.
Suppose that the thread length of the link between R1 and R2 is k.
Ohba, et al. [Page 6]
Internet-Draft draft-ohba-mpls-loop-prevention-01.txt July 1998
Then by the above procedures, the length of the link between Rn and
R1 must be k+n-1. But the above procedures also ensure that if a
node has an incoming thread of length j, its outgoing thread must be
at least of length j+1. Hence, if we assume that the loop is not
detected by the above procedure, the thread length of the link
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.
When a thread of "unknown" length gets into an L3 loop, however,
there is a situation in which the thread is merged into another
thread of "unknown" length. In this case, the L3 loop would not be
explicitly detected, but the thread is effectively stalled in the
loop until the L3 routing changes so as to remove the loop.
Inversely, how can we be sure that no loop detection occurs when
there is no loop?
Since every new path setup or release attempt that changes an LSP
length causes the use of a new color, condition (iii) cannot obtain
unless there actually is an L3 routing loop.
Next, why thread reconstructions are needed?
When a thread loop is detected, imagine a thread tree whose root is
the thread head. If there is a leaf which is not an LSP leaf in
that tree, then the thread will not disappear even after all LSP
leaf node withdraw their threads. The thread reconstruction is
performed to change the location of the thread head to the proper
node where any leaf of the thread tree is an LSP leaf node.
In the above procedure, multiple thread updates may happen if
several leaf nodes start extending threads at the same time. How
can we prevent multiple threads from looping unlimitedly?
In the procedure, when a node detects a thread loop by condition
(iii), it creates a new thread of "unknown" length. All the looping
threads which later arrive at the node would be merged into this
thread. Such a thread of "unknown" length behaves like a thread
absorber. Furthermore, the thread TTL mechanism can eliminate any
kind of thread looping.
3.4. Using old path while looping on new path
When a route changes, one might want to continue to use the old path
if the new route is looping. This is archived simply by holding the
label assigned to the downstream link on the old path until the
thread head on the new route returns. This is an implementation
choice.
3.5. How to deal with egress-initiated ordered control
Ohba, et al. [Page 7]
Internet-Draft draft-ohba-mpls-loop-prevention-01.txt July 1998
The thread mechanism can be also adapted to the egress-initiated
ordered control by originating a thread when a node newly receives
an advertisement message [5] from the downstream node.
Note that a node which has no upstream link for the LSP yet 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.
3.6. How to realize load splitting from the ingress node
The load splitting from the ingress node can be easily realized by
assigning a different colored thread to each downstream link.
4. Modification to LDP specification
A new advertisement class message, Update is added to the current
specification [5]. In addition, two new objects, Thread object and
Request ID object are defined.
When a thread of a particular LSP is extended on a downstream link,
if a label is not still allocated for that link, a Request message
is used for carrying the thread as well as for requesting a label,
otherwise, an Update message is used for extending the thread on the
downstream link where a label already exists.
When a node wants to withdraw an outgoing thread as well as
the downstream link, a Release message is used.
When a Mapping message is returned to an upstream node in response
to a Request message, it is treated as an indication of thread
rewinding (i.e., acknowledgments for loop-prevention check).
For an Update message, an ACK message is returned and treated as an
indication of thread rewinding, except for an Update containing a
special "transparent" thread. (See section 4.1.2.)
4.1. LDP objects
4.1.1. Request ID object
The object type of Request ID object is TBA.
+-----------------------+-------+--------------------------+----------+
| OBJECT | Type | Subtype(s) | Length |
+-----------------------+-------+--------------------------+----------+
| Request ID | TBA | 0x01 Default | 4 |
+-------------------------------+--------------------------+----------+
The Request ID object contains the information for identifying
multiple LSPs of the same SMD.
Ohba, et al. [Page 8]
Internet-Draft draft-ohba-mpls-loop-prevention-01.txt July 1998
SubType = 0x01 Default
1 2 3
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Request ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Request ID
This four-octet quantity contains a request-id which is
locally assigned by an upstream neighbor of a link.
4.1.2. Thread object
The object type of Loop Prevention object is TBA.
+-----------------------+-------+--------------------------+----------+
| OBJECT | Type | Subtype(s) | Length |
+-----------------------+-------+--------------------------+----------+
| Thread | TBA | 0x01 Default | 12 |
+-------------------------------+--------------------------+----------+
The Thread object contains the information required for the thread
mechanism.
SubType = 0x01 Default
1 2 3
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 |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Length | TTL | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Color
This eight-octet quantity contains a color of the thread. The
first four-octet is the thread creator's IP address. The last
four-octet is the local-id which is unique within the thread
creator's IP address.
If a node does not require a loop prevention check but only
requires an LSP length update, the special color "transparent"
is defined by setting all zero's to the Color field. No
acknowledgment is needed for transparent threads.
Length
This one octet quantity contains a thread length which is
represented by a hop count from the furthest leaf node to the
thread head. The value 0xff is assigned for "unknown" thread
Ohba, et al. [Page 9]
Internet-Draft draft-ohba-mpls-loop-prevention-01.txt July 1998
length.
TTL (Time To Live)
This one octet quantity contains a thread TTL which is
decremented by one (except for TTL="infinity") when a thread is
extended without changing its color. When the TTL becomes zero,
the extending procedure must be stopped. The value 0xff is
assigned for "infinity" which is never decremented.
4.2 Advertisement class messages
4.2.1. Request message
Mandatory Objects
At least one of each mandatory object with associated object headers.
+-----------------------+----------+
| MANDATORY OBJECT | Type |
+-----------------------+----------+
| SMD | 0x02 |
+-----------------------+----------+
| Class of Service | 0x04 |
+-----------------------+----------+
Optional Objects
Zero or more optional objects with associated object headers.
+-----------------------+----------+
| OPTIONAL OBJECT | Type |
+-----------------------+----------+
| Request ID | TBA |
+-----------------------+----------+
| Thread | TBA |
+-----------------------+----------+
4.2.2. Mapping message
Mandatory Objects
At least one of each mandatory object with associated object headers.
+-----------------------+----------+
| MANDATORY OBJECT | Type |
+-----------------------+----------+
| SMD | 0x02 |
+-----------------------+----------+
| Label | 0x03 |
+-----------------------+----------+
Optional Objects
Zero or more optional objects with associated object headers.
Ohba, et al. [Page 10]
Internet-Draft draft-ohba-mpls-loop-prevention-01.txt July 1998
+-----------------------+----------+
| OPTIONAL OBJECT | Type |
+-----------------------+----------+
| Class of Service | 0x04 |
+-----------------------+----------+
| Hop Count | 0x06 |
+-----------------------+----------+
| MTU | 0x07 |
+-----------------------+----------+
| Stack | 0x08 |
+-----------------------+----------+
| Request ID | TBA |
+-----------------------+----------+
4.2.3. Update message
The message type of Update message is TBA.
Mandatory Objects
At least one of each mandatory object with associated object headers.
+-----------------------+----------+
| MANDATORY OBJECT | Type |
+-----------------------+----------+
| SMD | 0x02 |
+-----------------------+----------+
| Class of Service | 0x04 |
+-----------------------+----------+
| Thread | TBA |
+-----------------------+----------+
Optional Objects
Zero or more optional objects with associated object headers.
+-----------------------+----------+
| OPTIONAL OBJECT | Type |
+-----------------------+----------+
| Request ID | TBA |
+-----------------------+----------+
4.2.4. Release message
Mandatory Objects
At least one of each mandatory object with associated object headers.
+-----------------------+----------+
| MANDATORY OBJECT | Type |
+-----------------------+----------+
| SMD | 0x02 |
+-----------------------+----------+
Ohba, et al. [Page 11]
Internet-Draft draft-ohba-mpls-loop-prevention-01.txt July 1998
Optional Objects
Zero or more optional objects with associated object headers.
+-----------------------+----------+
| OPTIONAL OBJECT | Type |
+-----------------------+----------+
| Label | 0x03 |
+-----------------------+----------+
| Request ID | TBA |
+-----------------------+----------+
4.2.5. Ack/Nak message
Mandatory Objects
At least one of each mandatory object with associated object headers.
+-----------------------+----------+
| MANDATORY OBJECT | Type |
+-----------------------+----------+
| SMD | 0x02 |
+-----------------------+----------+
| Error | 0x01 |
+-----------------------+----------+
Optional Objects
Zero or more optional objects with associated object headers.
+-----------------------+----------+
| OPTIONAL OBJECT | Type |
+-----------------------+----------+
| Label | 0x03 |
+-----------------------+----------+
| Request ID | TBA |
+-----------------------+----------+
5. Examples
In the following examples, we assume that the ingress-initiated
ordered control is employed, that all the LSPs are with regard to
the same FEC, and that all nodes are VC-merge capable.
5.1. First example
Consider an MPLS network shown in Fig. 1 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.
Ohba, et al. [Page 12]
Internet-Draft draft-ohba-mpls-loop-prevention-01.txt July 1998
R11 -------- R10 <-------------------- R9
| | ^
| | |
v v |
R1 -------> R2 --------> R3 --------> R4 ---------- R5
(leaf) ^
|
|
R6 -------> R7 --------> R8
(leaf)
Fig. 1 Example MPLS network (1)
Assume that R1 and R6 sends Request messages at the same time, and
that the initial thread TTL is 254 (255 represents "infinity").
First we show an example of how to prevent LSP loops before thread
TTL becomes zero.
The Request message from R1 contains a thread of (red,1,254), where
a thread is identified by (color,length,TTL). The Request message
from R6 contains a thread of (blue,1,254).
Assume that R3 receives the Request originated from R1 before the
Request originated from R6. Then R3 forwards the Request with the
thread of (red,3,252) and then the Request with (blue,4,251) in this
order.
When R2 receives the Request from R10 with the thread of
(red,6,249), it detects a loop of the red thread. In this case, R2
creates a new purple thread of "unknown" length and extends it
downstream by sending a Request with (purple,?,254) to R3, where "?"
represents "unknown".
After that, R2 receives another Request for the same LSP from R10
with (blue,7,248). The blue thread is merged into the purple thread
since the purple thread length (="unknown") is longer than the blue
thread length (=7). R2 sends nothing to R3.
On the other hand, the purple thread goes round and R2 detects
the loop of its own purple thread.
In this case, neither a thread is rewound nor a Mapping is returned.
The current state of the network is shown in Fig. 2. Note that
thread TTL information is not shown here.
Ohba, et al. [Page 13]
Internet-Draft draft-ohba-mpls-loop-prevention-01.txt July 1998
Bl(L): blue thread with length L
Re(L): red thread with length L
Pu(L): purple thread with length L
*: position of thread head
Pu(?)
R11 -------- R10 <------------------- R9
| | ^
| | Pu*(?) | Pu(?)
v v |
R1 -------> R2 -------> R3 --------> R4 --------- R5
(leaf) Re(1) Pu(?) ^ Pu(?)
| Bl(3)
|
R6 -------> R7 -------> R8
(leaf) Bl(1) Bl(2)
Fig. 2 The network state
Then R10 changes its next hop from R2 to R11.
Since R10 has a purple thread on the old downstream link, it first
sends a Release message to the old next hop R2 for removing the
purple thread. Next, it creates a new green thread for which the
purple thread length(="unknown") is used, and sends a Request with
(green,?,254) to R11.
When R2 receives the Release from R10, the upstream link between R10
and R2 is removed.
On the other hand, the green thread goes round to R10 without
being merged.
When R10 receives the green thread, it sends a Release message to
R11 to withdraw the green thread, since it is the creator of the
green thread and there is no other actual incoming thread.
When R1 removes the green thread, it creates a new orange thread and
resends a Request with (orange,0,254) to R2. The orange thread goes
round to R1, replacing the green thread on the path. Finally, R1
detects the loop of its own orange thread.
The state of the network is now shown in Fig. 3.
Ohba, et al. [Page 14]
Internet-Draft draft-ohba-mpls-loop-prevention-01.txt July 1998
Or(L): orange thread with length L
Bl(L): blue thread with length L
*: position of thread head
Or(7) Or(6)
R11 <------- R10 <------------------- R9
| | ^
| Or*(8) | | Or(5)
v | |
R1 -------> R2 -------> R3 --------> R4 --------- R5
(leaf) Or(1) Or(2) ^ Or(4)
| Bl(3)
|
R6 -------> R7 -------> R8
(leaf) Bl(1) Bl(2)
Fig. 3 The network state
Then R4 changes its next hop from R9 to R5.
Since R4 has the orange thread, it first sends a Release message to
the old next hop R9 to withdraw the orange thread on the old route.
Next, it creates a yellow thread of length 4, and sends a Request
with (yellow,5,254) to R5.
Since R5 is the egress node, the received thread is assured to be
loop-free, and R5 returns a Mapping message with a label. R5 sets
the LSP length to 5.
The thread rewiding procedure is performed at each node, as the
Mapping is returned upstream hop-by-hop.
Finally, when each of R1 and R6 receives a Mapping message, a merged
LSP ((R1->R2),(R6->R7->R8))->R3->R4->R5) is established and all the
colored threads disappear from the network.
Ohba, et al. [Page 15]
Internet-Draft draft-ohba-mpls-loop-prevention-01.txt July 1998
5.2. Second example
+----- R6----> R7-----+
| |
| v
R1---->R2 R4----->R5
| ^
| |
+--------->R3---------+
Fig. 4. Example MPLS network (2)
Assume that in Fig. 4, 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 (red,2,254). When the Request with
(red,4,252) reaches R4, it sends an Update message to R5 with
(red,5,251) since the received thread length (=4) is longer than the
current LSP length (=3).
When R5 receives the Update, it updates the LSP length to 5 and
returns an ACK for the Update. When R4 receives the ACK for the
Update, it returns an Mapping to R7.
When R2 receives the Mapping on the new route, it sends a Release to
R3. When R4 receives the Release, it does not sends an Update to R5
since the LSP length does not change. Now an established LSP
R1->R2->R6->R7->R4->R5 is obtained.
Then, the next hop changes again at R2 from R6 to R3.
R1 sends a Request with (blue,2,254) to R3. R3 forwards the Request
with (blue,3,253) to R4.
When R4 receives the Request, it immediately returns a Mapping to R3
since the received thread length (=3) is not longer than the current
LSP length (=4).
When R2 receives the Mapping on the new route, it sends a Release to
R6. The Release reaches R4, triggering an Update message with a
transparent thread (0,4,255) to R5, since the LSP length at R4
decreases from 4 to 3. R5 updates the LSP length to 4 without
returning an ACK.
6. Comparison with path-vector/diffusion method
o Whereas the size of the path-vector increases with the length of
the LSP, the sizes of the threads are constant. Thus the size
of messages used by the thread algorithm are unaffected by the
network size or topology. In addition, the thread merging
Ohba, et al. [Page 16]
Internet-Draft draft-ohba-mpls-loop-prevention-01.txt July 1998
capability reduces the number of outstanding messages. These
lead to improved scalability.
o In the thread algorithm, a node which is changing its next hop
for a particular LSP must interact only with nodes that are
between it and the LSP egress on the new path. In the
path-vector algorithm, however, it is necessary for the node to
initiate a diffusion computation that involves nodes which do
not lie between it and the LSP egress.
This characteristic makes the thread algorithm more robust. If
a diffusion computation is used, misbehaving nodes which aren't
even in the path can delay the path setup. In the thread
algorithm, the only nodes which can delay the path setup are
those nodes which are actually in the path.
o The thread algorithm is well suited for use with both the
ingress-initiated ordered control and the egress-initiated
ordered control. The path-vector/diffusion algorithm, however,
is tightly coupled with the egress-initiated ordered control.
o The thread algorithm is retry-free, achieving quick path
(re)configuration. The diffusion algorithm tends to delay the
path reconfiguration time, since a node at the route change
point must to consult all its upstream nodes.
o In the thread algorithm, the node can continue to use the old
path if there is an L3 loop on the new path, as in the
path-vector algorithm.
7. Security considerations
Security considerations are not discussed in this document.
8. Intellectual property considerations
Toshiba and/or Cisco may seek patent or other intellectual property
protection for some of the technologies disclosed in this document.
If any standards arising from this document are or become protected
by one or more patents assigned to Toshiba and/or Cisco, Toshiba
and/or Cisco intend to disclose those patents and license them on
reasonable and non-discriminatory terms.
9. References
[1] Y. Ohba, et al., "Flow Attribute Notification Protocol Version 2
(FANPv2) Ingress Control Mode," Internet Draft,
draft-ohba-csr-fanpv2-icmode-00.txt, Dec. 1997.
[2] B. Davie, et al., "Use of Label Switching With ATM," Internet Draft,
draft-davie-mpls-atm-01.txt, July 1998.
Ohba, et al. [Page 17]
Internet-Draft draft-ohba-mpls-loop-prevention-01.txt July 1998
[3] E. Rosen, et al., "A Proposed Architecture for MPLS,"
Internet Draft, draft-ietf-mpls-arch-01.txt, July 1998.
[4] R. Callon, et al., "A Framework for Multiprotocol Label
Switching," Internet Draft, draft-ietf-mpls-framework-02.txt,
Nov. 1997.
[5] L. Andersson, et al., "Label Distribution Protocol," Internet Draft,
draft-mpls-ldp-spec-00.txt, March 1998.
Authors' Addresses
Yoshihiro Ohba
R&D Center, Toshiba Corp.
1, Komukai-Toshiba-cho, Saiwai-ku
Kawasaki, 210, Japan
Email: ohba@csl.rdc.toshiba.co.jp
Yasuhiro Katsube
R&D Center, Toshiba Corp.
1, Komukai-Toshiba-cho, Saiwai-ku
Kawasaki, 210, Japan
Email: katsube@isl.rdc.toshiba.co.jp
Eric Rosen
Cisco Systems, Inc.
250 Apollo Drive
Chelmsford, MA, 01824
Email: erosen@cisco.com
Paul Doolan
Ennovate Networks
330 Codman Hill Road
Boxborough, MA
Email: pdoolan@ennovatenetworks.com
Ohba, et al. [Page 18]