Internet Draft

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
    ".".












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]