HTTP/1.1 200 OK Date: Tue, 09 Apr 2002 10:34:09 GMT Server: Apache/1.3.20 (Unix) Last-Modified: Tue, 17 Mar 1998 10:32:19 GMT ETag: "2e6af3-cd93-350e5133" Accept-Ranges: bytes Content-Length: 52627 Connection: close Content-Type: text/plain 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 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 ".". 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]