rfc3063.txt

最新的RFC

      A special hop count value "unknown"(=0xff), which is larger than
      any other known value, is used when a loop is found.  Once the
      thread hop count is "unknown", it is not increased any more as the
      thread is extended.

   Thread TTL

      To avoid infinite looping of control messages in some cases, a
      thread TTL is used.  When a node creates a path control message
      and sends it downstream, it sets a TTL to the message, and the TTL
      is decremented at each hop.  When the TTL reaches 0, the message
      is not forwarded any more.  Unlike the thread hop counts and the
      thread colors, the thread TTLs do not needs to be stored in
      incoming links.

3.2.  Thread loop

   When the same colored thread is received on multiple incoming links,
   or the received thread color was assigned by the receiving node, it
   is said that the thread forms a loop.  A thread creator can tell
   whether it assigned the received thread color by checking the IP
   address part of the received thread color.

3.3.  Primitive thread actions

   Five primitive actions are defined in order to prevent LSP loops by
   using threads: "extending", "rewinding", "withdrawing", "merging",
   and "stalling".  This section describes only each primitive action
   and does not describe how these primitive actions are combined and
   how the algorithm totally works.  The main body of the algorithm is
   described in section 4.

   Thread Extending

      When a node starts to send a path setup message to its next hop
      with a set of thread attributes, it is said that "the node creates
      a thread and extends it downstream".  When a node receives a path
      setup message from an upstream node with a set of thread
      attributes and forwards it downstream, it is said that "the node
      receives a thread and extends it downstream".  The color and hop
      count of the thread become the color and hop count of the outgoing
      link.  Whenever a thread is received on a particular link, the
      color and hop count of that thread become the color and hop count
      of that incoming link, replacing any color and hop count that the
      link may have had previously.






Ohba, et al.                  Experimental                      [Page 7]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


      For example, when an ingress node initiates a path setup, it
      creates a thread and extends it downstream by sending a path setup
      message.  The thread hop count is set to be 1, and the thread
      color is set to be the ingress node's address with an appropriate
      event identifier, and the thread TTL is set to be its maximum
      value.

      When a node receives a thread and extends it downstream, the node
      either (i) extends the thread without changing color, or (ii)
      extend the thread with changing color.  The received thread is
      extended with changing color if it is received on a new incoming
      link and extended on an already existing outgoing link, otherwise,
      it is extended without changing color.  When a thread is extended
      with changing color, a new colored thread is created and extended.

      Thread creation does not occur only at leaf nodes.  If an
      intermediate node has an incoming link, it will create and extend
      a new thread whenever it acquires a new next hop.

      When a node notifies a next hop node of a decrease of the link hop
      count, if it is not extending a colored thread, a transparent
      thread is extended.

   Thread Merging

      When a node which has a colored outgoing link receives a new
      thread, it does not necessarily extend the new thread.  It may
      instead 'merge' the new threads into the existing outgoing thread.
      In this case, no messages are sent downstream.  Also, if a new
      incoming thread is extended downstream, but there are already
      other incoming threads, these other incoming threads are
      considered to be merged into the new outgoing thread.

      Specifically, a received thread is merged if all the following
      conditions hold:

      o  A colored thread is received by node N, AND
      o  The thread does not form a loop, AND
      o  N is not an egress node, AND
      o  N's outgoing link is colored, AND
      o  N's outgoing link hop count is at least one greater than the
         hop count of the newly received thread.

      When an outgoing thread rewinds (see below), any incoming threads
      which have been merged with it will rewind as well.






Ohba, et al.                  Experimental                      [Page 8]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


   Thread Stalling

      When a colored thread is received, if the thread forms a loop, the
      received thread color and hop count are stored on the receiving
      link without being extended.  This is the special case of thread
      merging applied only for threads forming a loop and referred to as
      the "thread stalling", and the incoming link storing the stalled
      thread is called "stalled incoming link".  A distinction is made
      between stalled incoming links and unstalled incoming links.

   Thread Rewinding

      When a thread reaches a node which satisfies a particular loop-
      free condition, the node returns an acknowledgment message back to
      the message initiator in the reverse path on which the thread was
      extended.  The transmission of the acknowledgment messages is the
      "rewinding" of the thread.

      The loop-free condition is:

      o  A colored thread is received by the egress node, OR
      o  All of the following conditions hold:
         (a) A colored thread is received by node N, AND
         (b) N's outgoing link is transparent, AND
         (c) N's outgoing link hop count is at least one greater than
             the hop count of the newly received thread.

      When a node rewinds a thread which was received on a particular
      link, it changes the color of that link to transparent.

      If there is a link from node M to node N, and M has extended a
      colored thread to N over that link, and M determines (by receiving
      a message from N) that N has rewound that thread, then M sets the
      color of its outgoing link to transparent.  M then continues
      rewinding the thread, and in addition, rewinds any other incoming
      thread which had been merged with the thread being rewound,
      including stalled threads.

      Each node can start label switching after the thread colors in all
      incoming and outgoing links becomes transparent.

      Note that transparent threads are threads which have already been
      rewound; hence there is no such thing as rewinding a  transparent
      thread.







Ohba, et al.                  Experimental                      [Page 9]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


   Thread Withdrawing

      It is possible for a node to tear down a path.  A node tears down
      the portion of the path downstream of itself by sending teardown
      messages to its next hop.  This process is known as the "thread
      withdrawing".

      For example, suppose a node is trying to set up a path, and then
      experiences a next hop change or a next hop loss.  It will
      withdraw the thread that it had extended down its old next hop.

      If node M has extended a thread to node N, and node M then
      withdraws that thread, N now has one less incoming link than it
      had before.  If N now has no other unstalled incoming links and N
      is not an eligible leaf node, it must withdraw its outgoing
      thread.  If N still has an unstalled incoming link or N is an
      eligible leaf node, it may (or may not) need to change the hop
      count of the outgoing link.

      N needs to change the outgoing hop count if:

      o  The incoming link hop count that was just removed had a larger
         hop count than any of the remaining incoming links, AND
      o  One of the following conditions holds:
         (a) The outgoing link is transparent, OR
         (b) The outgoing link has a known hop count.

      If the outgoing link is transparent, it remains transparent, but
      the new hop count needs to be sent downstream.  If the outgoing
      link is colored, a new thread (with a new color) needs to be
      created and extended downstream.

3.4.  Examples of primitive thread actions

   The following notations are used to illustrate examples of primitive
   actions defined for threads.

   A pair of thread attributes stored in each link is represented by
   "(C,H)", where C and H represent the thread color and thread hop
   count, respectively.

   A thread marked "+" indicates that it is created or received now.  A
   thread marked "-" indicates that it is withdrawn now.

   A link labeled with squared brackets (e.g., "[a]") indicates that it
   is an unstalled link.  A link labeled with braces (e.g., "{a}")
   indicates that it is a stalled link.




Ohba, et al.                  Experimental                     [Page 10]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


   Fig. 2 shows an example in which a leaf node A creates a blue thread
   and extends it downstream.

                                    (bl,1)
                                 A---[o1]--->

                 Fig.2    Thread extending at leaf node

   Fig.3 shows an example of thread extending without changing color at
   intermediate node.  Assume that a node B has no incoming and outgoing
   link before receiving a blue thread.  When node B receives the blue
   thread of hop count 1 on a new incoming link i1, it extends the
   thread downstream without changing color (Fig.3(a)).  After the blue
   thread is extended, node B receives a red thread of hop count unknown
   on incoming link i1 again (Fig.3(b)).  The red thread is also
   extended without changing its color, since both i1 and o1 already
   exists.

         (bl,1)+     (bl,2)            (re,U)+      (re,U)
      ----[i1]--->B---[o1]---->     ----[i1]--->B----[o1]--->

              Fig.3(a)                      Fig.3(b)

          Fig.3    Thread extending without changing color

   Fig.4 shows an example of thread extending with changing color.
   There are single incoming link i1 and single outgoing link o1 in
   Fig.4(a).  Then a red thread of hop count 3 is received on a new
   incoming link i2.  In this case, the received thread is extended with
   changing color, i.e., a new green thread is created and extended
   (Fig.4(b)), since o1 already exists.

       (bl,1)       (bl,2)          (bl,1)       (gr,4)
    ----[i1]--->B----[o1]--->    ----[i1]--->B----[o1]--->
                                             ^
                                             |
                                 ----[i2]----+
                                    (re,3)+

             Fig.4(a)                     Fig.4(b)

        Fig.4    Thread extending with changing color

   Fig.5 shows an example of thread merging.  When a node B receives a
   red thread of hop count 3, the received thread is not extended since
   the outgoing link hop count is at least one greater than the received
   thread hop count.  Both the red and blue threads will be rewound when
   the blue thread on outgoing link o1 is rewound.



Ohba, et al.                  Experimental                     [Page 11]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


                      (bl,3)       (bl,4)
                   ----[i1]--->B----[o1]--->
                               ^
                               |
                   ----[i2]----+
                      (re,3)+

                   Fig.5    Thread merging

   Figs 6 and 7 show examples of thread stalling.  When a node B
   receives a blue thread of hop count 10 on incoming link i2 in Fig.6,
   it "stalls" the received thread since the blue thread forms a loop.
   In Fig.7, a leaf node A finds the loop of its own thread.

                       (bl,3)       (bl,4)
                    ----[i1]--->B----[o1]--->
                                ^
                                |
                    ----{i2}----+
                       (bl,10)+

                   Fig.6    Thread stalling (1)


                      (bl,10)+      (bl,1)
                    ----{i1}--->A----[o1]--->

                   Fig.7    Thread stalling (2)

   Fig.8 shows an example of thread rewinding.  When the yellow thread
   which is currently being extended is rewound (Fig.8(a)), the node
   changes all the incoming and outgoing thread color to transparent,
   and propagates thread rewinding to upstream nodes (Fig.8(b)).

        (bl,1)       (ye,2)                  (tr,1)       (tr,2)
     ----[i2]--->B----[o1]--->            ----[i2]--->B----[o1]--->
                 ^                                    ^
                 |                                    |
     ----[i3]----+                        ----[i3]----+
        (ye,1)                               (tr,1)

            Fig.8(a)                              Fig.8(b)

                     Fig.8    Thread rewinding







Ohba, et al.                  Experimental                     [Page 12]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


   Fig.9 shows an example of thread withdrawing.  In Fig.9(a), the red
   thread on incoming link i2 is withdrawn.  Then Hmax decreases from 3
   to  1, and node B  creates a new  green thread and extends it
   downstream, as shown in Fig.9(b).

          (bl,1)      (re,4)           (bl,1)       (gr,2)+