Internet Draft

Multi-Protocol Label Switching WG                         Yoshihiro Ohba
Internet-Draft                                          Yasuhiro Katsube
Expiration Date: January 1999                                    Toshiba
                                                                        
                                                              Eric Rosen
                                                           Cisco Systems

                                                             Paul Doolan
                                                       Ennovate Networks

                                                               July 1998


	             MPLS Loop Prevention Mechanism

                <draft-ohba-mpls-loop-prevention-01.txt>


Status of this Memo

    This document is an Internet-Draft.  Internet-Drafts are working
    documents of the Internet Engineering Task Force (IETF), its areas,
    and its working groups.  Note that other groups may also distribute
    working documents as Internet-Drafts.

    Internet-Drafts are draft documents valid for a maximum of six
    months and may be updated, replaced, or obsoleted by other documents
    at any time.  It is inappropriate to use Internet-Drafts as
    reference material or to cite them other than as "work in progress."

    To learn the current status of any Internet-Draft, please check the
    "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow
    Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
    munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or
    ftp.isi.edu (US West Coast).

    
Abstract

    This paper presents a simple mechanism, based on 'threads', which
    can be used to prevent MPLS from setting up label switched path
    (LSPs) which have loops.  The mechanism is compatible with, but does
    not require, VC merge.  The mechanism can be used with either the
    ingress-initiated ordered control or the egress-initiated ordered
    control.  The amount of information that must be passed in a
    protocol message is tightly bounded (i.e., no path-vector is used).
    When a node needs to change its next hop, a distributed procedure is
    executed, but only nodes which are downstream of the change are
    involved.
    






Ohba, et al.                                                    [Page 1]

Internet-Draft     draft-ohba-mpls-loop-prevention-01.txt      July 1998

Table of contents 

    1      Introduction ........................................  2
    2      Definitions .........................................  3
    3      Thread mechanism ....................................  4
    3.1    Thread  .............................................  4
    3.2    Loop prevention algorithm ...........................  5
    3.3    Why this works ......................................  6
    3.4    Using old path while looping on new path ............  7
    3.5    How to deal with egress-initiated ordered control ...  7
    3.6    How to realize load splitting from the ingress node .  8
    4      Modification to LDP specification ...................  8
    4.1    LDP objects .........................................  8
    4.2    Advertisement class messages ........................ 10
    5      Examples ............................................ 12
    5.1    First example ....................................... 12
    5.2    Second example ...................................... 16
    6      Comparison with path-vector/diffusion method ........ 16
    7      Security considerations ............................. 17
    8      Intellectual property considerations ................ 17
    9      References .......................................... 17


1.  Introduction

    This paper presents a simple mechanism, based on "threads", which
    can be used to prevent MPLS from setting up label switched paths
    (LSPs) which have loops.  The thread mechanism is a generalization
    of [1].

    When an LSR finds that it has a new next hop for a particular FEC,
    it creates a thread and extends it downstream.  Each such thread is
    assigned a unique "color", such that no two threads in the network
    can have the same color.

    Only a single thread for an LSP is ever extended to a particular
    next hop as long as the thread length does not change.  The only
    state information that needs to be associated with a particular next
    hop for a particular LSP is the thread color and length.

    The procedures for determining just how far downstream a thread must
    be extended are given in section 3.

    If there is a loop, then some thread will arrive back at an LSR
    through which it has already passed.  This is easily detected, since
    each thread has a unique color.  

    Section 3 provides procedures for determining that there is no loop.
    When this is determined, the threads are "rewound" back to the point
    of creation.  As they are rewound, labels get assigned.  Thus labels
    are NOT assigned until loop freedom is guaranteed.

    While a thread is extended, the LSRs through which it passes must
    remember its color and length, but when the thread has been rewound,

Ohba, et al.                                                    [Page 2]

Internet-Draft     draft-ohba-mpls-loop-prevention-01.txt      July 1998

    they need only remember its length.

    The thread mechanism works if some, all, or none of the LSRs in the
    LSP support VC-merge.  It can also be used with either the
    ingress-initiated ordered control or the egress-initiated ordered
    control [2,3].

    The state information which must be carried in protocol messages,
    and which must be maintained internally in state tables, is of fixed
    size, independent of the length of the LSP.  Thus the thread
    mechanism is more scalable than alternatives which require that
    path-vectors be carried.

    To set up a new LSP after a routing change, the thread mechanism
    requires communication only between nodes which are downstream of
    the point of change.  There is no need to communicate with nodes
    that are upstream of the point of change.  Thus the thread mechanism
    is more robust than alternatives which require that a diffusion
    computation be performed.

    The thread mechanism contains a number of significant improvements
    when compared to the mechanism described in the previous version of
    this internet draft.  In particular:

    o   The thread mechanism allows a node whose next hop changes to
        continue using the old LSP while setting up the new LSP (or
        while waiting for the L3 routing to stabilize, so that a new
        loop-free LSP can be set up)

    o   When a loop is detected, path setup is delayed, but it is
        automatically resumed when the L3 routing stabilizes and the
        loop disappears.  No retry timers are needed.

    o   "Color" only has to be remembered while a path is being set up.
        Once it is set up, the "color" (though not the length) can be
        forgotten.

    In this paper, we assume unicast LSPs.  The loop prevention for
    multicast LSPs is for further study.

    
2. Definitions

    An LSP for a particular Forwarding Equivalence Class (FEC) [4] can
    be thought of as a tree whose root is the egress LSR for that FEC.
    With respect to a given node in the tree, we can speak of its
    "downstream link" as the link which is closest to the root; the
    node's other edges are "upstream links".

    The term "link", as used here, refers to a particular relationship
    on the tree, rather than to a particular physical relationship.  In
    the remainder of this section, when we will speak of the upstream
    and downstream links of a node, we are speaking with reference to a
    single LSP tree for a single FEC.

Ohba, et al.                                                    [Page 3]

Internet-Draft     draft-ohba-mpls-loop-prevention-01.txt      July 1998


    In the case of non-VC-merging, multiple links of the same FEC
    between the neighboring nodes must be identified by identifiers that
    are locally assigned by the upstream node of the links.

    A leaf node is a node which has no upstream links.

    A "trigger node" is any node which (a) acquires a new next hop
    (i.e., either changes its next hop, or gets a next hop when it
    previously had none) for a particular FEC, and (b) needs to have an
    LSP for that FEC.

    An LSP length at a node is represented by a hop count from the
    furthest leaf node to that node.  The LSP length at a leaf node is
    zero.

    In the remainder of the paper, we assume the "downstream-on-demand"
    is used as the label allocation method between neighboring nodes,
    although the thread mechanism is applicable to the upstream
    allocation method.


3.  Thread mechanism

3.1.  Thread 

    A thread is an object used for representing a loop-prevention
    process which extends downstream.  The downstream end of a thread is
    referred to as the "thread head".

    A thread has a color that is assigned at the node that creates the
    thread.  The color is globally unique in the FEC.  

    A thread is always associated with a particular LSP (for a
    particular FEC).  The "length" of a thread is the number of hops
    from the thread head to the node which is furthest upstream of it on
    the LSP.  An "unknown" length which is greater than any other known
    length is used in a certain situation (see section 3.2).

    A thread has a TTL which is decremented by one (except for a special
    "infinity" value, see section 4) as the thread is extended without
    changing its color.  

    For a given LSP, at a given LSR, there can be one "incoming thread"
    for each upstream neighbor, and one "outgoing thread" to the
    downstream neighbor.  That is, one of the incoming threads is
    extended downstream.  If a node is the creator of a thread, the
    thread becomes a "virtual incoming thread" whose upstream neighbor
    is the node itself.  A non-virtual incoming thread is referred to as
    an "actual incoming thread".

    When a thread is extended, it retains its color, but its length
    becomes the maximum incoming thread length plus 1.


Ohba, et al.                                                    [Page 4]

Internet-Draft     draft-ohba-mpls-loop-prevention-01.txt      July 1998

    If a thread head of a given color reaches a node which already has a
    thread of that color, then a loop has been detected.

    When a node changes the color of its outgoing thread, it notifies
    its downstream neighbor by means of LDP messages.  The downstream
    neighbor must process these messages in order.


3.2.  Loop prevention algorithm 

    The ingress-initiated ordered control is assumed here, however, the
    algorithm can be adapted to egress-initiated ordered control (see
    section 3.4).

    When a trigger node requests a label assignment to its downstream
    neighbor, it creates a thread and extends it downstream.  

    The thread is given an initial length corresponding to the number of
    hops between the trigger node and the furthest upstream leaf.  It is
    given a color which consists of the trigger node's IP address,
    prepended to an event identifier which is assigned by the trigger
    node.  The trigger node will never reuse an event identifier until
    sufficient time has passed so that we can be sure that no other node
    in the network has any memory of the corresponding color.

    A colored thread is extended downstream until one of the following
    events occurs:

    (i) the thread head reaches an egress node;

    (ii) the thread head reaches a node where there is already an
        ESTABLISHED LSP for the thread, with a KNOWN length which is no
        less than the thread length;

    (iii) the thread head reaches a node which already has an actual or
        a virtual incoming thread of that color;

    (iv) the thread TTL becomes zero;

    (v) the thread head reaches a node where the maximum incoming thread
        length is not updated and there is another actual incoming
        thread.

    o   In the case of (i) or (ii), the thread is assured to reach the
        egress node without forming a loop.  Therefore the thread is
        "rewound".  When a thread is rewound, each node takes the
        following actions.  For each upstream link, it assigns a label
        to the LSP and distributes that label LSP upstream, if needed.
        It resets all incoming and outgoing thread colors to
        "transparent".  It sets the longest length among actual incoming
        threads to the LSP length.  If the outgoing thread length is
        "unknown" and the obtained LSP length becomes known, it notifies
        downstream of the LSP length (by using a "transparent" thread).


Ohba, et al.                                                    [Page 5]

Internet-Draft     draft-ohba-mpls-loop-prevention-01.txt      July 1998

        When the thread is rewound back to the trigger node, the LSP
        setup completes.

    o   In the case of (iii) and (iv), the thread is neither extended
        nor rewound.  It is blocked at the node.  In the case of (iii),
        the following actions are taken.  If the node is not the creator
        of the thread, it creates a new thread with "unknown" length and
        extends it downstream.  Otherwise, if it is not a leaf node and
        there is no other actual incoming thread, it withdraws the
        outgoing thread (this will cause a thread reconstruction, see
        section 3.3).

    o   In the case of (v), the received thread is "merged" into the
        outgoing thread and no message is sent to the downstream
        neighbor.  

    When a trigger node is attempting to set up a new LSP, it also tells
    its old next hop that it is withdrawing the thread that goes through
    it to the old next hop.  This will cause the old next hop to
    withdraw one of its incoming threads.  

    When an incoming thread is withdrawn, if there is no actual incoming
    thread, the outgoing thread is also withdrawn unless the node
    becomes a new leaf node.  Otherwise, if it is the one currently
    being extended, a new thread is created and extended. 

    A transparent thread is extended when a node notifies the downstream
    neighbor on an established LSP of an LSP length update or a thread
    withdrawal without releasing the LSP.  No rewinding is needed for
    transparent threads. 

    A virtual incoming thread is removed when the corresponding outgoing
    thread is replaced or withdrawn.


3.3.  Why this works

    The above procedures ensure that once a looping thread is detected, 
    path setup along the LSRs in that thread is effectively stalled
    until the L3 routing changes so as to remove the loop.

    How can we be sure that the any L3 loop will be detected by these
    procedures when a thread length is NOT "unknown"?

    Consider a sequence of LSRs , such that there is a loop
    traversing the LSRs in the sequence.  (I.e., packets from R1 go to
    R2, then to R3, etc., then to Rn, and then from Rn to R1.)

    Remember that after a routing change, a path cannot be set up (i.e.,
    labels cannot be assigned) until the thread resulting from the
    routing change is rewound, and the act of rewinding the thread
    causes the thread lengths to be set consistently along the path.

    Suppose that the thread length of the link between R1 and R2 is k.

Ohba, et al.                                                    [Page 6]

Internet-Draft     draft-ohba-mpls-loop-prevention-01.txt      July 1998

    Then by the above procedures, the length of the link between Rn and
    R1 must be k+n-1.  But the above procedures also ensure that if a
    node has an incoming thread of length j, its outgoing thread must be
    at least of length j+1.  Hence, if we assume that the loop is not
    detected by the above procedure, the thread length of the link
    between R1 and R2 must be at least k+n.  From this we may derive the
    absurd conclusion that n=0, and we may therefore conclude that there
    is no such sequence of LSRs.

    When a thread of "unknown" length gets into an L3 loop, however,
    there is a situation in which the thread is merged into another 
    thread of "unknown" length.  In this case, the L3 loop would not be
    explicitly detected, but the thread is effectively stalled in the
    loop until the L3 routing changes so as to remove the loop. 

    Inversely, how can we be sure that no loop detection occurs when 
    there is no loop?  

    Since every new path setup or release attempt that changes an LSP
    length causes the use of a new color, condition (iii) cannot obtain
    unless there actually is an L3 routing loop.  

    Next, why thread reconstructions are needed?  

    When a thread loop is detected, imagine a thread tree whose root is
    the thread head.  If there is a leaf which is not an LSP leaf in
    that tree, then the thread will not disappear even after all LSP
    leaf node withdraw their threads.  The thread reconstruction is
    performed to change the location of the thread head to the proper
    node where any leaf of the thread tree is an LSP leaf node.

    In the above procedure, multiple thread updates may happen if
    several leaf nodes start extending threads at the same time.  How
    can we prevent multiple threads from looping unlimitedly?

    In the procedure, when a node detects a thread loop by condition
    (iii), it creates a new thread of "unknown" length.  All the looping
    threads which later arrive at the node would be merged into this
    thread.  Such a thread of "unknown" length behaves like a thread
    absorber.  Furthermore, the thread TTL mechanism can eliminate any
    kind of thread looping.


3.4.  Using old path while looping on new path

    When a route changes, one might want to continue to use the old path
    if the new route is looping.  This is archived simply by holding the
    label assigned to the downstream link on the old path until the
    thread head on the new route returns.  This is an implementation
    choice.  


3.5.  How to deal with egress-initiated ordered control


Ohba, et al.                                                    [Page 7]

Internet-Draft     draft-ohba-mpls-loop-prevention-01.txt      July 1998

    The thread mechanism can be also adapted to the egress-initiated
    ordered control by originating a thread when a node newly receives
    an advertisement message [5] from the downstream node.

    Note that a node which has no upstream link for the LSP yet behaves
    as a leaf.  In the case where the tree is being initially built up
    (e.g., the egress node has just come up), each node in turn will
    behave as a leaf for a short period of time.


3.6.  How to realize load splitting from the ingress node 

    The load splitting from the ingress node can be easily realized by
    assigning a different colored thread to each downstream link.


4.  Modification to LDP specification

    A new advertisement class message, Update is added to the current
    specification [5].  In addition, two new objects, Thread object and
    Request ID object are defined.

    When a thread of a particular LSP is extended on a downstream link,
    if a label is not still allocated for that link, a Request message
    is used for carrying the thread as well as for requesting a label,
    otherwise, an Update message is used for extending the thread on the
    downstream link where a label already exists.

    When a node wants to withdraw an outgoing thread as well as 
    the downstream link, a Release message is used.

    When a Mapping message is returned to an upstream node in response
    to a Request message, it is treated as an indication of thread
    rewinding (i.e., acknowledgments for loop-prevention check).

    For an Update message, an ACK message is returned and treated as an
    indication of thread rewinding, except for an Update containing a
    special "transparent" thread. (See section 4.1.2.)


4.1. LDP objects

4.1.1.  Request ID object
    
   The object type of Request ID object is TBA.

   +-----------------------+-------+--------------------------+----------+
   | OBJECT                | Type  |  Subtype(s)              | Length   |
   +-----------------------+-------+--------------------------+----------+
   | Request ID            |  TBA  |  0x01  Default           |    4     |
   +-------------------------------+--------------------------+----------+

    The Request ID object contains the information for identifying
    multiple LSPs of the same SMD.

Ohba, et al.                                                    [Page 8]

Internet-Draft     draft-ohba-mpls-loop-prevention-01.txt      July 1998


   SubType = 0x01   Default
	
                        1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                         Request ID                            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    
    Request ID
        This four-octet quantity contains a request-id which is 
        locally assigned by an upstream neighbor of a link.  


4.1.2.  Thread object
    
   The object type of Loop Prevention object is TBA.

   +-----------------------+-------+--------------------------+----------+
   | OBJECT                | Type  |  Subtype(s)              | Length   |
   +-----------------------+-------+--------------------------+----------+
   | Thread                |  TBA  |  0x01  Default           |    12    |
   +-------------------------------+--------------------------+----------+

    The Thread object contains the information required for the thread 
    mechanism.

   SubType = 0x01   Default
	
                        1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   |                             Color                             |
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    Length     |      TTL      |           Reserved            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+    

    Color
        This eight-octet quantity contains a color of the thread.  The
        first four-octet is the thread creator's IP address.  The last
        four-octet is the local-id which is unique within the thread
        creator's IP address.

        If a node does not require a loop prevention check but only
        requires an LSP length update, the special color "transparent"
        is defined by setting all zero's to the Color field.  No
        acknowledgment is needed for transparent threads.  

    Length
        This one octet quantity contains a thread length which is 
        represented by a hop count from the furthest leaf node to the
        thread head.  The value 0xff is assigned for "unknown" thread

Ohba, et al.                                                    [Page 9]

Internet-Draft     draft-ohba-mpls-loop-prevention-01.txt      July 1998

	length.  

    TTL (Time To Live)
        This one octet quantity contains a thread TTL which is
        decremented by one (except for TTL="infinity") when a thread is
        extended without changing its color.  When the TTL becomes zero,
        the extending procedure must be stopped.  The value 0xff is
        assigned for "infinity" which is never decremented.


4.2  Advertisement class messages 

4.2.1.  Request message

   Mandatory Objects
   At least one of each mandatory object with associated object headers.

   +-----------------------+----------+
   | MANDATORY OBJECT      | Type     |
   +-----------------------+----------+
   | SMD                   | 0x02     |
   +-----------------------+----------+
   | Class of Service      | 0x04     |
   +-----------------------+----------+

   Optional Objects
   Zero or more optional objects with associated object headers.

   +-----------------------+----------+
   | OPTIONAL OBJECT       | Type     |
   +-----------------------+----------+
   | Request ID            | TBA      |
   +-----------------------+----------+
   | Thread                | TBA      |
   +-----------------------+----------+


4.2.2.  Mapping message

   Mandatory Objects
   At least one of each mandatory object with associated object headers.

   +-----------------------+----------+
   | MANDATORY OBJECT      | Type     |
   +-----------------------+----------+
   | SMD                   | 0x02     |
   +-----------------------+----------+
   | Label                 | 0x03     |
   +-----------------------+----------+

   Optional Objects
   Zero or more optional objects with associated object headers.



Ohba, et al.                                                   [Page 10]

Internet-Draft     draft-ohba-mpls-loop-prevention-01.txt      July 1998


   +-----------------------+----------+
   | OPTIONAL OBJECT       | Type     |
   +-----------------------+----------+
   | Class of Service      | 0x04     |
   +-----------------------+----------+
   | Hop Count             | 0x06     |
   +-----------------------+----------+
   | MTU                   | 0x07     |
   +-----------------------+----------+
   | Stack                 | 0x08     |
   +-----------------------+----------+
   | Request ID            | TBA      |
   +-----------------------+----------+


4.2.3.  Update message

   The message type of Update message is TBA.

   Mandatory Objects
   At least one of each mandatory object with associated object headers.

   +-----------------------+----------+
   | MANDATORY OBJECT      | Type     |
   +-----------------------+----------+
   | SMD                   | 0x02     |
   +-----------------------+----------+
   | Class of Service      | 0x04     |
   +-----------------------+----------+
   | Thread                | TBA      |
   +-----------------------+----------+

   Optional Objects
   Zero or more optional objects with associated object headers.

   +-----------------------+----------+
   | OPTIONAL OBJECT       | Type     |
   +-----------------------+----------+
   | Request ID            | TBA      |
   +-----------------------+----------+


4.2.4.  Release message

   Mandatory Objects
   At least one of each mandatory object with associated object headers.

   +-----------------------+----------+
   | MANDATORY OBJECT      | Type     |
   +-----------------------+----------+
   | SMD                   | 0x02     |
   +-----------------------+----------+


Ohba, et al.                                                   [Page 11]

Internet-Draft     draft-ohba-mpls-loop-prevention-01.txt      July 1998


   Optional Objects
   Zero or more optional objects with associated object headers.

   +-----------------------+----------+
   | OPTIONAL OBJECT       | Type     |
   +-----------------------+----------+
   | Label                 | 0x03     |
   +-----------------------+----------+
   | Request ID            | TBA      |
   +-----------------------+----------+


4.2.5. Ack/Nak message

   Mandatory Objects
   At least one of each mandatory object with associated object headers.

   +-----------------------+----------+
   | MANDATORY OBJECT      | Type     |
   +-----------------------+----------+
   | SMD                   | 0x02     |
   +-----------------------+----------+
   | Error                 | 0x01     |
   +-----------------------+----------+

   Optional Objects

   Zero or more optional objects with associated object headers.

   +-----------------------+----------+
   | OPTIONAL OBJECT       | Type     |
   +-----------------------+----------+
   | Label                 | 0x03     |
   +-----------------------+----------+
   | Request ID            | TBA      |
   +-----------------------+----------+


5.  Examples

    In the following examples, we assume that the ingress-initiated
    ordered control is employed, that all the LSPs are with regard to
    the same FEC, and that all nodes are VC-merge capable.

5.1.  First example    

    Consider an MPLS network shown in Fig. 1 in which an L3 loop exists.
    Each directed link represents the current next hop of the FEC at
    each node.  Now leaf nodes R1 and R6 initiate creation of an LSP.



                                            

Ohba, et al.                                                   [Page 12]

Internet-Draft     draft-ohba-mpls-loop-prevention-01.txt      July 1998

            R11 -------- R10 <-------------------- R9
             |           |                         ^
             |           |                         | 
             v           v                         | 
             R1 -------> R2 --------> R3 --------> R4 ---------- R5
           (leaf)                     ^        
                                      | 
                                      |
             R6 -------> R7 --------> R8
           (leaf)                  

                    Fig. 1   Example MPLS network (1)


    Assume that R1 and R6 sends Request messages at the same time, and
    that the initial thread TTL is 254 (255 represents "infinity").
    First we show an example of how to prevent LSP loops before thread
    TTL becomes zero.

    The Request message from R1 contains a thread of (red,1,254), where
    a thread is identified by (color,length,TTL).  The Request message
    from R6 contains a thread of (blue,1,254).

    Assume that R3 receives the Request originated from R1 before the
    Request originated from R6.  Then R3 forwards the Request with the
    thread of (red,3,252) and then the Request with (blue,4,251) in this
    order.

    When R2 receives the Request from R10 with the thread of
    (red,6,249), it detects a loop of the red thread.  In this case, R2
    creates a new purple thread of "unknown" length and extends it
    downstream by sending a Request with (purple,?,254) to R3, where "?"
    represents "unknown".

    After that, R2 receives another Request for the same LSP from R10
    with (blue,7,248).  The blue thread is merged into the purple thread
    since the purple thread length (="unknown") is longer than the blue
    thread length (=7).  R2 sends nothing to R3.

    On the other hand, the purple thread goes round and R2 detects
    the loop of its own purple thread.

    In this case, neither a thread is rewound nor a Mapping is returned.
    The current state of the network is shown in Fig. 2.  Note that
    thread TTL information is not shown here.










Ohba, et al.                                                   [Page 13]

Internet-Draft     draft-ohba-mpls-loop-prevention-01.txt      July 1998

	Bl(L): blue thread with length L 
        Re(L): red thread with length L 
        Pu(L): purple thread with length L 
        *: position of thread head 


                                      Pu(?)
            R11 -------- R10 <------------------- R9
             |            |                        ^ 
             |            | Pu*(?)                 | Pu(?)
             v            v                        | 
             R1 -------> R2 -------> R3 --------> R4 --------- R5
           (leaf)  Re(1)      Pu(?)   ^    Pu(?)
                                      | Bl(3)
                                      |
             R6 -------> R7 -------> R8
           (leaf)  Bl(1)       Bl(2)


                         Fig. 2  The network state 


    Then R10 changes its next hop from R2 to R11.

    Since R10 has a purple thread on the old downstream link, it first
    sends a Release message to the old next hop R2 for removing the
    purple thread.  Next, it creates a new green thread for which the
    purple thread length(="unknown") is used, and sends a Request with
    (green,?,254) to R11.

    When R2 receives the Release from R10, the upstream link between R10
    and R2 is removed.

    On the other hand, the green thread goes round to R10 without 
    being merged.  

    When R10 receives the green thread, it sends a Release message to
    R11 to withdraw the green thread, since it is the creator of the
    green thread and there is no other actual incoming thread.

    When R1 removes the green thread, it creates a new orange thread and
    resends a Request with (orange,0,254) to R2.  The orange thread goes
    round to R1, replacing the green thread on the path.  Finally, R1
    detects the loop of its own orange thread.

    The state of the network is now shown in Fig. 3.









Ohba, et al.                                                   [Page 14]

Internet-Draft     draft-ohba-mpls-loop-prevention-01.txt      July 1998

        Or(L): orange thread with length L 
	Bl(L): blue thread with length L 
        *: position of thread head 


                 Or(7)               Or(6)
            R11 <------- R10 <------------------- R9
             |            |                        ^ 
             | Or*(8)     |                        | Or(5)
             v            |                        | 
             R1 -------> R2 -------> R3 --------> R4 --------- R5
           (leaf)  Or(1)       Or(2)  ^    Or(4)
                                      | Bl(3)
                                      |
             R6 -------> R7 -------> R8
           (leaf)  Bl(1)       Bl(2)


                         Fig. 3  The network state 


    Then R4 changes its next hop from R9 to R5.

    Since R4 has the orange thread, it first sends a Release message to
    the old next hop R9 to withdraw the orange thread on the old route.
    Next, it creates a yellow thread of length 4, and sends a Request
    with (yellow,5,254) to R5.

    Since R5 is the egress node, the received thread is assured to be
    loop-free, and R5 returns a Mapping message with a label.  R5 sets
    the LSP length to 5.

    The thread rewiding procedure is performed at each node, as the
    Mapping is returned upstream hop-by-hop.

    Finally, when each of R1 and R6 receives a Mapping message, a merged
    LSP ((R1->R2),(R6->R7->R8))->R3->R4->R5) is established and all the
    colored threads disappear from the network.

















Ohba, et al.                                                   [Page 15]

Internet-Draft     draft-ohba-mpls-loop-prevention-01.txt      July 1998

5.2.  Second example    

                                        
                       +----- R6----> R7-----+
                       |                     |
                       |                     v
                R1---->R2                    R4----->R5
                       |                     ^ 
                       |                     |
                       +--------->R3---------+


                Fig. 4.  Example MPLS network (2)


    Assume that in Fig. 4, there is an established LSP
    R1->R2->R3->R4->R5, and the next hop changes at R2 from R3 to R6.
    R2 sends a Request to R6 with (red,2,254). When the Request with
    (red,4,252) reaches R4, it sends an Update message to R5 with
    (red,5,251) since the received thread length (=4) is longer than the
    current LSP length (=3).

    When R5 receives the Update, it updates the LSP length to 5 and
    returns an ACK for the Update.  When R4 receives the ACK for the
    Update, it returns an Mapping to R7.

    When R2 receives the Mapping on the new route, it sends a Release to
    R3.  When R4 receives the Release, it does not sends an Update to R5
    since the LSP length does not change.  Now an established LSP
    R1->R2->R6->R7->R4->R5 is obtained.

    Then, the next hop changes again at R2 from R6 to R3.  

    R1 sends a Request with (blue,2,254) to R3.  R3 forwards the Request
    with (blue,3,253) to R4.

    When R4 receives the Request, it immediately returns a Mapping to R3
    since the received thread length (=3) is not longer than the current
    LSP length (=4).  

    When R2 receives the Mapping on the new route, it sends a Release to
    R6.  The Release reaches R4, triggering an Update message with a
    transparent thread (0,4,255) to R5, since the LSP length at R4
    decreases from 4 to 3.  R5 updates the LSP length to 4 without
    returning an ACK.


6.  Comparison with path-vector/diffusion method


    o   Whereas the size of the path-vector increases with the length of
        the LSP, the sizes of the threads are constant.  Thus the size
        of messages used by the thread algorithm are unaffected by the
        network size or topology.  In addition, the thread merging

Ohba, et al.                                                   [Page 16]

Internet-Draft     draft-ohba-mpls-loop-prevention-01.txt      July 1998

        capability reduces the number of outstanding messages.  These
        lead to improved scalability.

    o   In the thread algorithm, a node which is changing its next hop
        for a particular LSP must interact only with nodes that are
        between it and the LSP egress on the new path.  In the
        path-vector algorithm, however, it is necessary for the node to
        initiate a diffusion computation that involves nodes which do
        not lie between it and the LSP egress.

        This characteristic makes the thread algorithm more robust.  If
        a diffusion computation is used, misbehaving nodes which aren't
        even in the path can delay the path setup.  In the thread
        algorithm, the only nodes which can delay the path setup are
        those nodes which are actually in the path.

    o   The thread algorithm is well suited for use with both the
        ingress-initiated ordered control and the egress-initiated
        ordered control.  The path-vector/diffusion algorithm, however,
        is tightly coupled with the egress-initiated ordered control.

    o   The thread algorithm is retry-free, achieving quick path
        (re)configuration.  The diffusion algorithm tends to delay the
        path reconfiguration time, since a node at the route change
        point must to consult all its upstream nodes.

    o   In the thread algorithm, the node can continue to use the old
        path if there is an L3 loop on the new path, as in the
        path-vector algorithm.


7.  Security considerations

    Security considerations are not discussed in this document.


8.  Intellectual property considerations

    Toshiba and/or Cisco may seek patent or other intellectual property
    protection for some of the technologies disclosed in this document.
    If any standards arising from this document are or become protected
    by one or more patents assigned to Toshiba and/or Cisco, Toshiba
    and/or Cisco intend to disclose those patents and license them on
    reasonable and non-discriminatory terms.


9.  References

[1] Y. Ohba, et al., "Flow Attribute Notification Protocol Version 2
    (FANPv2) Ingress Control Mode," Internet Draft, 
    draft-ohba-csr-fanpv2-icmode-00.txt, Dec. 1997.

[2] B. Davie, et al., "Use of Label Switching With ATM," Internet Draft,
    draft-davie-mpls-atm-01.txt, July 1998.

Ohba, et al.                                                   [Page 17]

Internet-Draft     draft-ohba-mpls-loop-prevention-01.txt      July 1998


[3] E. Rosen, et al., "A Proposed Architecture for MPLS," 
    Internet Draft, draft-ietf-mpls-arch-01.txt, July 1998.

[4] R. Callon, et al., "A Framework for Multiprotocol Label
    Switching," Internet Draft, draft-ietf-mpls-framework-02.txt, 
    Nov. 1997.

[5] L. Andersson, et al., "Label Distribution Protocol," Internet Draft, 
    draft-mpls-ldp-spec-00.txt, March 1998.


Authors' Addresses

    Yoshihiro Ohba
    R&D Center, Toshiba Corp.
    1, Komukai-Toshiba-cho, Saiwai-ku
    Kawasaki, 210, Japan 
    Email: ohba@csl.rdc.toshiba.co.jp 

    Yasuhiro Katsube
    R&D Center, Toshiba Corp.
    1, Komukai-Toshiba-cho, Saiwai-ku
    Kawasaki, 210, Japan 
    Email: katsube@isl.rdc.toshiba.co.jp 

    Eric Rosen
    Cisco Systems, Inc.
    250 Apollo Drive
    Chelmsford, MA, 01824
    Email: erosen@cisco.com

    Paul Doolan
    Ennovate Networks
    330 Codman Hill Road
    Boxborough, MA
    Email: pdoolan@ennovatenetworks.com


















Ohba, et al.                                                   [Page 18]