Multi-Protocol Label Switching WG Yoshihiro Ohba
Internet-Draft Yasuhiro Katsube
Expiration Date: September 1998 Toshiba
Eric Rosen
Cisco Systems
Paul Doolan
Ennovate Networks
March 1998
MPLS Loop Prevention Mechanism Using LSP-id and Hop Count
<draft-ohba-mpls-loop-prevention-00.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), ds.internic.net (US East Coast), or
ftp.isi.edu (US West Coast).
Abstract
This paper presents a simple mechanism, based on ''LSP-ids'', which
can be used to prevent MPLS from setting up label switched paths
(LSPs) which have loops. The mechanism is compatible with, but does
not require, VC merge. The mechanism can be used with either the
local control or the egress control methods of label distribution.
The amount of information that must be passed in protocol messages
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.
Table of contents
1 Introduction ............................................. 2
2 Loop prevention mechanism ................................ 3
2.1 Overview ................................................. 3
Ohba, et al. [Page 1]
Internet-Draft draft-ohba-mpls-loop-prevention-00.txt March 1998
2.1.1 Assigning LSP-ids ........................................ 3
2.1.2 Preventing looping LSPs .................................. 5
2.2 Messages ................................................ 5
2.3 Data structure .......................................... 6
2.4 Avoiding inconsistency during LSP modification ........... 7
2.5 Loop prevention algorithm ................................ 7
2.5.1 Algorithm for local control .............................. 8
2.5.2 Algorithm for egress control ............................. 11
2.6 Designated LSP-id management ............................. 11
3 Examples ................................................. 12
4 Enhancement of the algorithm ............................. 14
4.1 Enhancement for improving protocol performance ........... 14
4.1.1 How to deal with multiple SETUP messages ................. 14
4.1.2 How to deal with multiple UPDATE messages ................ 15
4.1.3 Interoperation of different message processing policies .. 17
4.2 Enhancement in route change .............................. 17
5 Comparison with path-vector/diffusion method ............. 18
6 Security considerations .................................. 19
7 Intellectual property considerations ..................... 19
8 References ............................................... 19
9 Authors' Addresses ....................................... 20
1. Introduction
This paper presents a simple mechanism, based on "LSP-ids", which
can be used to prevent MPLS from setting up label switched paths
(LSPs) which have loops. The LSP-id mechanism is a generalization
of [1].
The LSP-id mechanism works if some, all, or none of the LSRs in the
LSP support VC-merge. It can also be used with either the local
control or the egress control label distribution mechanism [2,3].
The LSP-id mechanism is conservative. It will always prevent the
formation of looping LSPs. During routing transients, however, it
may delay the formation of some non-looping LSPs.
The loop-prevention information which must be carried in the
protocol messages of the LSP-id mechanism is of fixed size,
independent of the length of the LSP. Thus the LSP-id mechanism is
more scalable than alternatives which require that path-vectors be
carried.
To set up a new LSP after a routing change, the LSP-id 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 LSP-id mechanism
is more robust than alternatives which require that a diffusion
computation be performed.
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
Ohba, et al. [Page 2]
Internet-Draft draft-ohba-mpls-loop-prevention-00.txt March 1998
"downstream link" as the link which is closest to the root; the
node's other edges are "upstream links".
The basis of the LSP-id scheme is the assignment of an "LSP-id" to
each link in an LSP tree. The assignment is done in such a way
that:
o in a steady-state loop-free environment, if some node has two
upstream links in the same LSP tree, each link will be assigned
a distinct LSP-id;
o if there is a looping LSP, then there will be some node which
has two upstream links in the same LSP tree, where the same
LSP-id has been assigned to each link.
Loops can then be prevented as follows. If a given node has an
upstream link in a particular LSP tree, with a particular LSP-id, it
must make sure that it does not acquire any other upstream link in
that LSP tree with the same LSP-id.
In this paper, we assume unicast LSPs. The loop prevention for
multicast LSPs is for further study.
2. Loop prevention mechanism
In the remainder of the paper, we assume the "downstream-on-demand"
is used as the label allocation method between neighboring nodes,
although the LSP-id mechanism is applicable to the upstream
allocation method.
2.1. Overview
2.1.1. Assigning LSP-ids
An LSP for a particular FEC 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.
A leaf node is a node which has no upstream links.
Every node is responsible for assigning an LSP-id and an "LSP-id hop
count" for each of its downstream links.
Each leaf node assigns an LSP-id to its downstream link as follows.
The LSP-id consists of two parts:
Ohba, et al. [Page 3]
Internet-Draft draft-ohba-mpls-loop-prevention-00.txt March 1998
o leaf-address: an L3 address of the leaf node itself, and
o leaf-local-id: a local identifier assigned by the leaf node.
The leaf-local-id must be chosen so that if the node in question is
a leaf on more than one tree for a given FEC, it uses different
LSP-ids for its downstream links on the respective trees. (If there
is no "load-splitting", i.e., there is only one LSP tree per FEC,
the identifier is not really needed.)
A leaf node also assigns an LSP-id hop count of zero to its
downstream link.
When a node assigns an LSP-id to its downstream link, it must inform
its downstream neighbor of the LSP-id and the LSP-id hop count
incremented by one. From the point of view of the downstream
neighbor, this LSP-id is now assigned to a particular one of its
upstream links.
A node which is not a leaf node assigns an LSP-id to its downstream
link as follows. It chooses, from among the LSP-ids assigned to its
upstream links, the one which has the largest LSP-id hop count. (If
the largest LSP-id hop count is shared by two or more LSP-ids, a
deterministic tie breaker is used to select a single LSP-id: the
numerically largest value chosen.) Once the LSP-id for the
downstream link is chosen, the associated hop count is incremented
by one, and the downstream neighbor is informed of the LSP-id and
LSP-id hop count.
If a particular node acquires a new upstream link, or loses an
existing upstream link, or if the LSP-id or LSP-id hop count of an
existing upstream link changes, the node needs to reevaluate its
choice of LSP-id and LSP-id hop count for its downstream link. If
it changes the LSP-id or LSP-id hop count for its downstream link,
it must so inform the downstream neighbor.
If a node acquires a new downstream link, it must assign an LSP-id
and LSP-id hop count, and so inform its new downstream neighbor.
When this procedure has been carried out, every link in an LSP tree
will have been assigned an LSP-id. The LSP-id for a particular link
will include an L3 address for a leaf node which is upstream of that
link. In particular, the LSP-id of a particular link will include
the L3 address of the leaf node which is furthest upstream of it
(modulo the tie breaker).
A routing change causes at least one node to change its next hop,
i.e., to acquire a new downstream link. This triggers a sequence of
LSP-id updates, proceeding downstream from the point of change.
However, change will not necessarily cause a change in the LSP-id of
every downstream link in the tree. The LSP-id updates only need to
percolate downstream until they reach a node which has a downstream
link whose LSP-id and LSP-id hop count do not have to change.
Ohba, et al. [Page 4]
Internet-Draft draft-ohba-mpls-loop-prevention-00.txt March 1998
2.1.2. Preventing looping LSPs
Suppose that node R1's next hop for some FEC changes from what it
was previously to node R2. That is, R1 would like to acquire a new
downstream link. R1 assigns an LSP-id and LSP-id hop count to that
link, according to the above procedures. R1 then informs R2 of the
LSP-id and LSP-id hop count. This begins an LSP-id updating process
which must percolate downstream.
If changing R1's next hop to R2 results in a loop, then, when the
LSP-id updating process is completed, there will be some node in the
tree which has two upstream links with the same LSP-id.
Loops can therefore be prevented as follows:
o R2 should not distribute a label for the tree to R1 unless and
until R2 has determined that the LSP-id updating process has
completed successfully. This requires a procedure in which
LSP-id updates percolate downstream, and acknowledgments to the
LSP-id updates percolate back upstream.
o If, at any point during the process, some node sees that it has
two upstream links with the same LSP-id, it should immediately
terminate the LSP-id updating process with an error. This
requires that there be negative acknowledgments as well as
positive acknowledgments.
2.2. Messages
In the LSP-id algorithm, the following messages are used: SETUP,
SETUP_ACK, SETUP_NACK, UPDATE, UPDATE_ACK, UPDATE_NACK, RELEASE,
RELEASE_ACK, RELEASE_NACK, and TRIGGER. (Note that the message
names might not yet be perfectly aligned with the work of the LDP
team.)
Each message contains (FEC-id,LSP-id,hop-count). FEC-id is the
identifier of the forwarding equivalence class carried by the LSP.
LSP-id is an identifier of the LSP, and composed of a leaf-address
which is an L3 address of a leaf node and a leaf-local-id which is
used for identifying different LSPs with the same leaf-address and
the same FEC-id. Multi-path LSPs may have different leaf-local-id's
for the same leaf-address and FEC-id. Hop-count is the number of
hops from the node represented by the LSP-id to the node that
receives the message.
A SETUP message is transmitted to the downstream neighbor in order
to request a label. A RELEASE message is transmitted to the
downstream neighbor in order to release a label. An UPDATE message
is transmitted to the downstream neighbor in order to update an
LSP-id and a hop-count.
Ohba, et al. [Page 5]
Internet-Draft draft-ohba-mpls-loop-prevention-00.txt March 1998
SETUP, UPDATE, and RELEASE message are acknowledged, either
positively or negatively. The SETUP_ACK, SETUP_NACK, UPDATE_ACK,
UPDATE_NACK, RELEASE_ACK, and RELEASE_NACK messages exist for this
purpose. (In some cases, RELEASE messages do not need to be
acknowledged. See Section 4.1.2.) However, if the receipt of a
SETUP, UPDATE, or RELEASE message causes an UPDATE message to be
sent downstream, the acknowledgment (positive or negative) of the
former message is deferred until an acknowledgment of the latter
message is received.
Note that there are two types of UPDATE messages; UPDATE messages
initiated by SETUP messages (referred to as UPDATE_ADD messages) and
UPDATE messages initiated by RELEASE messages (referred to as
UPDATE_DEL messages).
2.3. Data structure
A leaf node originates a SETUP message with
(FEC-id,LSP-id,hop-count) in which the hop-count is set to 1, the
leaf-address of the LSP-id is set to either the L3 address of its
output interface or its router id, and the leaf-local-id of the
LSP-id is set to a value which is unique in the same leaf-address
and the FEC-id.
For each upstream link of an LSP, a pair of (LSP-id,hop-count),
which is contained in the SETUP or the UPDATE message is maintained
by each node.
A downstream LSP-id is also maintained for a downstream link. The
upstream LSP-id which gives the maximum hop-count among all the
upstream LSP-id's is selected as the downstream LSP-id. If a number
of upstream LSP-id's all share the largest hop-count, the largest
LSP-id among them is selected as the downstream LSP-id. The
downstream LSP-id and hop-count are also referred to as the
designated LSP-id and the designated hop-count, respectively.
Any change in the upstream LSP-ids and/or the upstream LSP-id hop
counts may cause a change in the designated LSP-id.
An example of (LSP-id,hop-count) pairs assigned to each link of an
LSP is shown in Fig. 1, where an LSP-id is represented by
"<leaf-address>.<leaf-local-id>".
Ohba, et al. [Page 6]
Internet-Draft draft-ohba-mpls-loop-prevention-00.txt March 1998
(LSP-id,hop-count)
=(A.1,1) (B.3,4) (B.3,5)
A-------->R1-------->R2------->R3
^ ^
| (B.3,3) | (C.1,2)
(B.3,1) (B.3,2) | |
B------->R4-------->R5 R6
^
| (C.1,1)
|
C
Fig. 1. Example of LSP-id's in an LSP
2.4. Avoiding inconsistency during LSP modification
In order to ensure that all nodes on the LSP have consistent
information about the LSP-id and hop-count, events which modify the
LSP must be carefully treated.
A simple but conservative rule for avoiding inconsistency is to
ensure that at any given node, there is at most one outstanding
message per LSP at any one time.
In other words, when a node receives a SETUP, UPDATE or RELEASE
message about a particular LSP from one of its upstream neighbors,
it processes the message on the condition that (1) there is no
outstanding SETUP, UPDATE or RELEASE message for the same LSP which
is awaiting acknowledgment, or (2) processing the message does not
cause a change in the designated LSP-id or hop count.
If neither condition (1) nor (2) is satisfied, it blocks the message
(e.g., returns a {SETUP, UPDATE, RELEASE}_NACK message to the sender
or puts the message into a processing queue). We call this rule
"exclusive message processing".
Note that with the exclusive message processing, in the case where a
SETUP_NACK or a RELEASE_NACK message is returned after blocking, the
receiver of the NACK should retry to send the NACK'ed message.
It is however possible to allow multiple outstanding messages, as
long as the order of processing is preserved as the messages
percolate downstream. This is discussed in Section 4. This allows
the LSP modifications to complete more quickly, reducing the time it
takes to adapt to a routing change. There is, however, some cost in
simplicity.
2.5. Loop prevention algorithm
For simplicity, the algorithms for the exclusive message processing
Ohba, et al. [Page 7]
Internet-Draft draft-ohba-mpls-loop-prevention-00.txt March 1998
rule are shown here. See Section 4.1 for the multiple message
processing rule.
2.5.1. Algorithm for local control
o When a leaf node initiates creation of an LSP for a FEC, it
sends a SETUP message that contains the FEC-id for the FEC, the
downstream LSP-id, and a hop-count which is set to 1. The SETUP
message serves as the request for a label.
o When a node receives a SETUP message with regard to a FEC from
an upstream neighbor, one of the following actions is taken:
+ If the received hop-count reaches the allowable maximum
value, it returns a SETUP_NACK message.
+ Otherwise, if the received LSP-id has already been
registered (see below for the meaning of "registered"), for
a different upstream link which belongs to one of the LSPs
having the same FEC-id as the received one, or if the node
is the originator of the LSP-id, then loop freedom cannot be
guaranteed, and a SETUP_NACK is returned.
+ Otherwise, if it is the egress node, it registers the
received LSP-id and hop-count for the upstream link, assigns
a label to that link, and immediately returns a SETUP_ACK
message (thereby distributing the label to its upstream
neighbor).
+ Otherwise, if accepting the SETUP message does not change
the designated LSP-id (see Section 2.6), it registers the
received LSP-id and hop-count for the upstream link, assigns
a label to that link, and returns a SETUP_ACK message
(thereby distributing the label to its upstream neighbor).
+ Otherwise, if there is an outstanding message for the LSP,
it blocks the message.
+ Otherwise, if there is a downstream link for the LSP, it
sends an UPDATE_ADD message which contains the received
FEC-id, LSP-id, and hop-count incremented by one, to the
downstream neighbor. it also registers the received LSP-id
for the upstream link.
+ Otherwise, it sends a SETUP message which contains the
received FEC-id, LSP-id, and hop-count incremented by one,
to the downstream neighbor. It registers the received
LSP-id for the upstream link. If the optimistic mode [5] is
adopted, a SETUP_ACK message is returned. If the optimistic
mode is adopted, loops are not prevented, but any loop which
may be formed will soon be detected by the receipt of a
negative acknowledgment.
Ohba, et al. [Page 8]
Internet-Draft draft-ohba-mpls-loop-prevention-00.txt March 1998
o When a node receives an UPDATE_{ADD,DEL} message with regard to
an LSP, one of the following actions is taken:
+ If there is no corresponding upstream link or the received
hop-count reaches the allowable maximum value, it returns an
UPDATE_{ADD,DEL}_NACK message.
+ Otherwise, if the received LSP-id has already been
registered for a different upstream link which belongs to
one of the LSPs having the same FEC-id as the received one,
loop freedom cannot be guaranteed, so an UPDATE_ADD_NACK is
returned. This case won't happen for UPDATE_DEL messages.
+ Otherwise, if accepting the message changes neither the
designated LSP-id nor the designated hop-count (see Section
2.6), it registers the received LSP-id and hop-count for the
corresponding upstream link, and immediately returns an
UPDATE_{ADD,DEL}_ACK message.
+ Otherwise, if there is an outstanding message for the LSP,
it blocks the message.
+ Otherwise, if there is a downstream link allocated for the
LSP, it forwards the UPDATE_{ADD,DEL} message, with the
candidate for the designated LSP-id and the candidate for
the designated hop-count incremented by one, to the
downstream neighbor. If the received message is UPDATE_DEL,
the node also replaces the LSP-id and hop-count for the
corresponding upstream link with the received ones and
returns an UPDATE_DEL_ACK message to the upstream neighbor.
+ Otherwise, replaces the LSP-id and hop-count for the
corresponding upstream link with the received ones and
immediately returns an UPDATE_{ADD,DEL}_ACK message. If it
is not the egress node for the LSP, it must also send a
SETUP message to the downstream node.
o When a node receives a RELEASE message with regard to an LSP,
one of the following actions is taken:
+ If there is no upstream link for the LSP other than the one
to be released, it removes the upstream link and the
associated (LSP-id,hop-count) pair, returns a RELEASE_ACK
message, and sends a RELEASE message to the downstream
neighbor.
+ Otherwise, if accepting the message does not change the
designated LSP-id (see Section 2.6), it removes the upstream
link and the associated (LSP-id,hop-count) pair, and returns
a RELEASE_ACK message.
+ Otherwise, if there is an outstanding message for the same
LSP, it blocks the message.
Ohba, et al. [Page 9]
Internet-Draft draft-ohba-mpls-loop-prevention-00.txt March 1998
+ Otherwise, it removes the upstream link and the associated
(LSP-id,hop-count) pair, returns a RELEASE_ACK message. It
also sends an UPDATE_DEL message with the candidate for the
designated LSP-id and the candidate for the designated
hop-count incremented by one, to the downstream neighbor.
o When the route with regard to an LSP changes at a node, the node
sends a RELEASE message to the old downstream neighbor and a
SETUP message to the new downstream neighbor.
o When a node receives a SETUP_ACK message with regard to an LSP,
it returns a SETUP_ACK or an UPDATE_ADD_ACK message to the
upstream neighbor if needed. The designated LSP-id and
hop-count is set to the ACK'ed ones. When an UPDATE_ADD_ACK
message is returned to the upstream neighbor, the LSP-id and
hop-count being registered for the corresponding upstream link
are replaced with the ACK'ed ones. Now it is able to start
label switching. Note that received SETUP_ACK message contains
the label which was assigned by the downstream neighbor, and
that any SETUP_ACK message which is sent upstream must also
contain a newly assigned label.
o When a node receives a SETUP_NACK message with regard to an LSP,
instead of starting label switching, it returns a SETUP_ACK, a
SETUP_NACK or an UPDATE_ADD_ACK message to the upstream neighbor
depending on the operation policy. A halfway LSP is formed as a
result when a SETUP_ACK or an UPDATE_ADD_ACK message is
returned. When a SETUP_ACK or an UPDATE_ADD_ACK message is
returned to the upstream neighbor, it may retry to send a SETUP
message to its downstream neighbor. When a SETUP_NACK message
is returned to the upstream neighbor, it deletes the
corresponding upstream link. When an UPDATE_ADD_ACK message is
returned to the upstream neighbor, the LSP-id and hop-count
being registered for the corresponding upstream link are
replaced with the ACK'ed ones.
o When a node receives an UPDATE_{ADD,DEL}_ACK message with regard
to an LSP, it replaces the designated LSP-id and hop-count with
the ACK'ed ones. If the received message is UPDATE_ADD, it
returns a SETUP_ACK or an UPDATE_ADD_ACK message. When an
UPDATE_ADD_ACK is returned to the downstream neighbor, the the
LSP-id and hop-count being registered for the corresponding
upstream link are replaced with the ACK'ed ones.
o When a node receives an UPDATE_ADD_NACK message with regard to
an LSP, it returns a SETUP_NACK or an UPDATE_ADD_NACK message to
the upstream neighbor, without updating the designated LSP-id
and hop-count. When a SETUP_NACK is returned to the upstream
neighbor, the corresponding upstream link is deleted.
o When a node receives an UPDATE_DEL_NACK message with regard to
an LSP, it retries to send the UPDATE_DEL message to its
downstream neighbor.
Ohba, et al. [Page 10]
Internet-Draft draft-ohba-mpls-loop-prevention-00.txt March 1998
o When a node receives a RELEASE_ACK message with regard to an
LSP, it removes the downstream link.
o When a node receives a RELEASE_NACK message (due to, e.g.,
existence of an outstanding message) with regard to an LSP, it
retries to send a RELEASE message.
2.5.2. Algorithm for egress control
o An egress node, when it first comes up, issues a TRIGGER message
to all neighbors. Also, any node which creates a downstream
link for a particular LSP, sends a TRIGGER message to each
upstream neighbor for which there is no upstream link.
o Any node which gets a TRIGGER message (specifying a particular
FEC) from its next hop for that FEC will send a SETUP message,
which implicitly acknowledges the TRIGGER message.
o When a node receives a SETUP message, if neither it has a
corresponding downstream link nor it is the egress node, it
returns a SETUP_NACK message. Otherwise, if it is the egress
node or the current selection of the designated LSP-id and
hop-count does not change, it returns a SETUP_ACK message.
Otherwise, it sends an UPDATE message to its own next hop.
o For other events, nodes follow the same procedure as described
in Section 2.5.1.
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.
2.6. Designated LSP-id management
In the algorithm described in Section 2.5, a change in the
designated LSP-id and hop-count is needed in the following cases.
(a) When a node receives a SETUP message, if the designated LSP-id
does not exist, the designated LSP-id and hop-count need to be
set to the received ones.
(b) When a node receives a SETUP or an UPDATE_ADD message, if the
LSP-id being registered for the received upstream link is not
the current designated LSP-id, then if the received hop-count is
greater than the designated one, or if the received hop-count is
equal to the designated one and the received LSP-id is greater
than the designated one, the designated LSP-id and hop-count
needs to be updated to the received one.
(c) When a node receives an UPDATE_{ADD,DEL} message, if the LSP-id
being registered for the received upstream link is the current
Ohba, et al. [Page 11]
Internet-Draft draft-ohba-mpls-loop-prevention-00.txt March 1998
designated LSP-id, the designated LSP-id and hop-count need to
be updated. In this case, the node chooses the LSP-id which has
the largest LSP-id hop count from among the upstream LSP-ids
(the received LSP-id and hop-count are used for the received
upstream link) as the candidate for the designated LSP-id. If
the largest LSP-id hop count is shared by two or more LSP-ids, a
deterministic tie breaker is used to select a single LSP-id: the
numerically largest value chosen.
(d) When a node receives a RELEASE message, if the LSP-id being
registered for the received upstream link is the current
designated LSP-id, the designated LSP-id and hop-count need to
be updated. In this case, the node chooses the LSP-id which has
the largest LSP-id hop count from among the upstream LSP-ids
(excluding the one for the received upstream link) as the
candidate for the designated LSP-id. If the largest LSP-id hop
count is shared by two or more LSP-ids, a deterministic tie
breaker is used to select a single LSP-id: the numerically
largest value chosen.
3. Examples
Consider an MPLS network shown in Fig. 2 which employs local
control. Assume that an L3 loop exists for a FEC-id=F. Now leaf
nodes R1 and R6 initiates creation of an LSP. In this example, a
router id is used as a leaf-address, and leaf-local-id=0 is used
hence leaf-local-id is omitted. It is assumed that all nodes are
VC-merge capable, and operate in the conservative mode and allow
creation of halfway LSPs.
+<---------- R5 <---------+
| ^
| |
v |
R1 -------> R2 --------> R3 --------> R4
^
|
|
R6 -------> R7 --------> R8
Fig. 2 Example MPLS network
An example in which the loop is detected before the hop count
reaches the predetermined threshold is described below.
Assume that R1 sends a SETUP message before R6 does, and that the
maximum hop count is set to eight. First we show an example of how
to create an LSP.
The SETUP message from R1 contains (FEC-id,LSP-id,hop-count) =
Ohba, et al. [Page 12]
Internet-Draft draft-ohba-mpls-loop-prevention-00.txt March 1998
(F,R1,1). Then R2, R3, R4, and R5 send SETUP messages with
(FEC-id,LSP-id,hop-count) = (F,R1,2), (F,R1,3), (F,R1,4), (F,R1,5),
respectively. These nodes registers the received
(LSP-id,hop-count).
When R2 receives the SETUP message from R5, it finds that the
leaf-address R1 is already registered by the SETUP message sent by
R1, and thus returns a SETUP_NACK message to R5. R5 then returns a
SETUP_ACK message to R4. Similarly, SETUP_ACK messages are returned
from R4 to R3, R3 to R2, and finally R2 to R1. Then a halfway LSP
R1->R2->R3->R4->R5 is created without forming a loop. R5 also sets
a retry timer to send a new SETUP message to R6 after certain period
of time. Note that the all designated LSP-id's for R1, R2, R3, and
R4 are set to R1.
Then R6 starts to send a SETUP message to R7. The SETUP message
from R6 contains (FEC-id,LSP-id,hop-count) = (F,R6,1). Then R7 and
R8 send SETUP messages with (FEC-id,LSP-id,hop-count) = (F,R6,2) and
(F,R6,3) to R8 and R3, respectively. These nodes also registers the
received (LSP-id,hop-count).
When R3 receives the SETUP message from R8, the designated LSP-id
changes since the received hop-count(=3) is larger than the already
registered one(=2). Then R3 sends an UPDATE_ADD message to R4 with
(FEC-id,LSP-id,hop-count) = (F,R6,4). When R4 receives the UPDATE
message from R3, it also sends an UPDATE_ADD message to R5 with
(FEC-id,LSP-id,hop-count) = (F,R6,5), since the designated LSP-id
also changes.
When R5 receives the UPDATE_ADD message from R4, since it is the
current egress node, it returns an UPDATE_ADD_ACK message to R4. R4
then returns an UPDATE_ADD_ACK message to R3. R3 returns a
SETUP_ACK message to R8. Similarly, a SETUP_ACK message is returned
from R8 to R7, and finally R7 to R8. Then a halfway merged LSP
((R1->R2),(R6->R7->R8))->R3->R4->R5 is created. Note that the
designated LSP-id's for R1 and R2 are set to R1, and for other
nodes, to R6.
R5 also resends a SETUP message to R2 with (FEC-id,LSP-id,hop-count)
= (F,R6,6). When R2 receives the SETUP message from R5, since the
received LSP-id is not registered by any other upstream neighbors
and the received hop-count is less than the threshold, it registers
the received LSP-id and hop-count and sends an UPDATE_ADD message to
R3 with (FEC-id,LSP-id,hop-count) = (F,R6,7).
When R3 receives the UPDATE_ADD message from R2, it finds that the
leaf-address R6 is already registered for R8. Then it considers
that a loop is about to be formed and thus returns an
UPDATE_ADD_NACK message to R2. R2 returns a SETUP_NACK message to
R5. R5 does not returns any message to R4 since there is no
outstanding message. In this case the halfway merged LSP holds.
On the contrary, in the case that R6 sends a SETUP message before R1
does, the SETUP message originated by R1 does not trigger the
Ohba, et al. [Page 13]
Internet-Draft draft-ohba-mpls-loop-prevention-00.txt March 1998
transmission of an UPDATE_ADD message at R3 since the designated
LSP-id at R3 is not changed by setting up the upstream link from R2.
Next, an example of how to release an LSP is described by using
Fig. 2. Assume that a halfway merged LSP
((R1->R2),(R6->R7->R8))->R3->R4->R5 already exists.
If R6 sends a RELEASE message before R1 does, the RELEASE message is
forwarded until it reaches R3. R3 then issues an UPDATE_DEL message
since the designated LSP-id for R3 changes from R6 to R1. The
UPDATE_DEL message contains (FEC-id,LSP-id,hop-count) = (F,R1,3).
R4 returns an UPDATE_DEL_ACK to R3 and sends an UPDATE_DEL message
with (FEC-id,LSP-id,hop-count) = (F,R1,4) to R5. In this case, the
LSP is changed to R1->R2->R3->R4->R5.
On the contrary, if R1 sends a RELEASE message before R6 does, the
RELEASE message originated by R1 does not trigger the transmission
of an UPDATE_DEL message at R3 since the designated LSP-id for R3 is
not changed by releasing the upstream link between R2 and R3. In
this case, the LSP is changed to R6->R7->R8->R3->R4->R5.
4. Enhancement of the algorithm
The basic algorithm can be enhanced by the following two methods.
4.1. Enhancement for improving protocol performance
At some cost in simplicity, the time needed to adapt to a routing
change can be decreased by modifying the algorithms described in
Section 2.5. Instead of adhering to the exclusive processing rule,
we can allow a node to have multiple outstanding messages about the
same LSP, provided that certain conditions are met.
Since a RELEASE message is sent to the downstream neighbor only when
all the upstream link has been released, we consider dealing with
only multiple SETUP and UPDATE messages. In addition, for the
egress control, we need only consider the case of multiple UPDATE
messages since SETUP messages are transmitted from downstream to
upstream.
4.1.1. How to deal with multiple SETUP messages
When a node receives a SETUP message, it can forward the SETUP
message to the downstream neighbor even if there is an outstanding
SETUP message.
Each time a node receives a SETUP_ACK message for one of the
outstanding SETUP message(s) with regard to a FEC, the designated
LSP-id is replaced with the ACK'ed LSP-id if:
o the ACK'ed hop-count is greater than the designated hop-count,
Ohba, et al. [Page 14]
Internet-Draft draft-ohba-mpls-loop-prevention-00.txt March 1998
or
o the ACK'ed hop-count is equal to the designated hop-count and
the ACK'ed LSP-id is greater than the designated LSP-id.
If the designated LSP-id changes, the designated hop-count is also
updated.
The final result on the designated LSP-id and hop-count after
receiving all acknowledgments is independent of the message
processing order.
Note that during the multiple outstanding message processing, a node
may receive a SETUP message from upstream neighbor after returning a
SETUP_ACK message for other SETUP message. In this case, if the
received hop-count is greater than the one which is already
registered for the upstream link, or if the received hop-count is
equal to the registered one and the received LSP-id is greater than
the registered one, the registered values need to be replaced with
the received ones. If the replacement does not need to change the
designated LSP-id and hop-count, it executes the replacement and
immediately returns a SETUP_ACK message, otherwise, it sends an
UPDATE_ADD message to the downstream neighbor. If there is no need
to replace the registered values, it immediately returns a SETUP_ACK
message.
4.1.2. How to deal with multiple UPDATE messages
(a) Multiple UPDATE_ADD messages
UPDATE_ADD messages can be processed concurrently in the same manner
as multiple SETUP messages regardless of the sending order of the
UPDATE_ADD messages and receiving order of the UPDATE_ADD_ACK or
UPDATE_ADD_NACK messages.
(b) Multiple UPDATE_DEL messages
For the multiple UPDATE_DEL messages, however, message order must be
preserved. For example, in Fig. 3, assume that the current
designated LSP-id for R1 is B, and that R1 receives a RELEASE
message from B, then receives a RELEASE message from C.
Consider the case where R1 sends an UPDATE_DEL message with
(LSP-id,hop-count) = (C,2) as a result of B's removal and then sends
an UPDATE_DEL message with (LSP-id,hop-count) = (A,2) as a result of
C's removal.
If R2 processes the UPDATE_DEL message with (LSP-id,hop-count) =
(A,2) before the UPDATE_DEL message with (LSP-id,hop-count) = (C,2),
R2 may finally select C as the designated LSP-id. R1, however, will
have selected (A,1), since C is no longer a leaf of the tree. Thus
R1 and R2 have made inconsistent choices. Hence, the message order
must be preserved at all nodes in order to avoid inconsistency with
Ohba, et al. [Page 15]
Internet-Draft draft-ohba-mpls-loop-prevention-00.txt March 1998
multiple UPDATE_DEL messages.
A
| (LSP-id,hop-count)
| =(A,1)
v
B-------->R1-------->R2------->R3
(B,1) ^ (B,2) (B,3)
|
| (C,1)
C
Fig. 3. Example of multiple UPDATE_DEL messages
(c) A mixture of UPDATE_ADD and UPDATE_DEL messages
Similarly, message order must be preserved at all nodes when there
are multiple outstanding UPDATE_ADD and UPDATE_DEL messages.
For example, in Fig. 4, assume that the current designated LSP-id
for R2 is B, and that A sends a SETUP message. In this case, R2
sends an UPDATE_ADD message with (LSP-id,hop-count) = (A,3) to R3 as
a result of A's participation.
Consider the case where A sends a RELEASE message before receiving a
SETUP_ACK message. If R2 receives the RELEASE message initiated by
A before receiving an UPDATE_ADD_ACK message for the UPDATE_ADD
message, R2 sends an UPDATE_DEL message with (LSP-id,hop-count) =
(B,2) to R3.
If R3 processes the UPDATE_ADD and UPDATE_DEL messages from R2 in
reverse order, R3 may finally select A as the designated LSP-id,
despite the fact that A is no longer a leaf on the tree. To avoid
this problem, message order must also be preserved in this case.
A---------R1
|
|
|
v
B-------->R2-------->R3------->R4
(B,1) (B,2) (B,3)
Fig. 4. Example of a mixture of UPDATE_ADD and UPDATE_DEL messages
As a result of discussions in Section 4.1.1 and 4.1.2, it is
concluded that multiple outstanding message processing is possible
only if the message order is preserved at all nodes. This
Ohba, et al. [Page 16]
Internet-Draft draft-ohba-mpls-loop-prevention-00.txt March 1998
requirement would be satisfied if the protocol is (i) implemented
over a reliable transport such as TCP for message transfer between
neighboring nodes, and (ii) implemented in a way that messages are
processed in exactly the same as the received order. Note that if
both conditions (i) and (ii) are satisfied, RELEASE_ACK and
UPDATE_DEL_ACK messages are not necessary since a change toward hop
count decrease is always loop-free.
4.1.3. Interoperation of different message processing policies
Nodes with exclusive message processing policy and with multiple
message processing policy can interoperate by the following way. If
a node with exclusive message processing receives multiple SETUP or
UPDATE messages, it simply blocks the message. Since both types of
nodes have their own mechanism to handle blocking events, they can
coexist in the same network.
4.2. Enhancement in route change
Consider the case where a route changes at R1. With the basic
algorithm for local control, R1 sends a RELEASE message to R2, and
sends a SETUP message to R6. If the SETUP message reaches R4 before
the RELEASE message, the SETUP message is blocked since the LSP-id=A
is already registered at R4 for the upstream link on the old route.
This would occur during a transient state of the routing protocol
where a SETUP message and a RELEASE message may be transmitted in
parallel for the same LSP. In such a case, the request is refused
though there is actually no loop, and the blocked node has to wait
until the links on the old path are removed.
old route
==========> (A,4)
+----->R2----->R3-----+
| |
| v
A----->R1 R4----->R5
| ^ (A,5)
| |
+--------->R6---------+
new route
==========>
Fig. 5. Example of route change
The performance during the route change can be enhanced by
introducing an additional rule. That is, when a SETUP message is
received, if the same LSP-id as the received one is already
registered for a different upstream link but the received hop-count
Ohba, et al. [Page 17]
Internet-Draft draft-ohba-mpls-loop-prevention-00.txt March 1998
is less than or equal to the registered one, the node withdraws the
upstream link for the old path and accept the SETUP message for the
new path. For this purpose, an additional WITHDRAW message is used.
This modification does not violate the loop-free characteristics,
because the scheme still has the restriction against allowing a node
to have the same LSP-id registered for the same FEC by two different
neighbors.
Further enhancement can be expected by using not only hop count but
also routing metric information when a node makes a decision whether
the node replaces the old upstream link with the new one or not.
The use of routing metric is for further study.
Note that the nodes with and without this enhanced algorithm are
interoperable.
5. Comparison with path-vector/diffusion method
Advantages:
1. Whereas the size of the path-vector increases with the length of
the LSP, the sizes of the LSP-id and hop count are constant.
Thus the size of messages used by the LSP-id algorithm are
unaffected by the network size or topology. This leads to
improved scalability.
2. In the LSP-id 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 LSP-id 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 LSP-id
algorithm, the only nodes which can delay the path setup are
those nodes which are actually in the path.
3. The LSP-id algorithm is well suited for use with both the local
control and the egress control. The path-vector/diffusion
algorithm, however, is tightly coupled with the egress control
method.
Disadvantages:
1. When a particular node's next hop on a particular LSP tree
changes, the LSP-id algorithm does not necessarily allow the
node to continue using the old path while the new path is being
set up. If there is some node D which is downstream on both
paths, then it is not possible to have both paths set up at the
Ohba, et al. [Page 18]
Internet-Draft draft-ohba-mpls-loop-prevention-00.txt March 1998
same time; otherwise D would have two upstream links with the
same LSP-id. So in this case, the old path must be torn down
before the new path can be used.
So it is possible that during routing transients, there may be
periods when there is no LSP for a particular FEC. This
disadvantage is a consequence of the fact that the LSP-id
algorithm maintains only the LSP-id, not a complete path vector.
This reduction of information is thus the source both of the
advantages and the disadvantages of the LSP-id algorithm.
However, the enhanced mechanism described in section 4.2 can be
used to greatly reduce the effects of this disadvantage. That
mechanism allows one to leave the existing path set up while
initiating the setup of the new path. If it turns out that the
two paths have no downstream node in common, then the old path
need not be torn down until the new path is put into use. If,
on the other hand, the two paths have a node in common, and the
newer path is the better one (i.e., the newer path brings the
leafs closer to the egress), tear down of the old path will be
initiated by the node which is on both paths. This minimizes
the time during which there is no label switching for the given
FEC. If the new path is worse than the old path, this may cause
more delay in switching over. That seems inconsequential
though, since in this case data is likely not being delivered
along the old path anyway.
6. Security considerations
Security considerations are not discussed in this document.
7. 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.
8. 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] L. Andersson, et al., "LSP Specification," Internet Draft,
draft-mplsdt-ldp-spec-00.txt, Nov. 1997.
[3] E Rosen, et al., "A Proposed Architecture for MPLS,"
Internet Draft, draft-ietf-mpls-arch-00.txt, Aug. 1997.
Ohba, et al. [Page 19]
Internet-Draft draft-ohba-mpls-loop-prevention-00.txt March 1998
[4] R. Callon, et al., "A Framework for Multiprotocol Label
Switching," Internet Draft, draft-ietf-mpls-framework-02.txt,
Nov. 1997.
[5] B. Davie, et al., "Use of Label Switching With ATM,"
Internet Draft, draft-davie-mpls-atm-00.txt, Nov. 1997.
9. 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 20]