rfc3063.txt

最新的RFC

   outgoing link.

   When a node receives a thread rewinding event, if the received thread
   color and the extending thread color are different, it discards the
   event without entering the FSM.

8.1. Finite state machine

   An event which is "scheduled" by an action in an FSM must be passed
   immediately after the completion of the action.

   The following variables are used in the FSM:

      o  Ni: number of unstalled incoming links
      o  Hmax: largest incoming hop count
      o  Hout: hop count of the outgoing link for the current next hop
      o  Hrec: hop count of the received thread

   In the FSM, if Hmax=unknown, the value for (Hmax+1) becomes the value
   reserved for unknown hop count plus 1.  For example, if
   Hmax=unknown=255, the value (Hmax+1) becomes 256.

   A TCB has three states; Null, Colored, and Transparent.  When a TCB
   is in state Null, there is no outgoing link and Ni=0.  The state
   Colored means that the node is extending a colored thread on the
   outgoing link for the current next hop.  The state Transparent means
   that the node is the egress node or the outgoing link is transparent.

   The flag value "1" represents the flag is set, "0" represents the
   flag is not set, and "*" means the flag value is either 1 or 0.



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


   The FSM allows to have one transparent outgoing link on the old next
   hop and one colored outgoing link on the current next hop.  However,
   it is not allowed to have a colored outgoing link on the old next
   hop.

   State Null:

 Event         Action                                          New state
 Recv thread
   Flags
  CL LP NL
  0  *  *      Do nothing.                                     No change
  1  0  *      If the node is egress, start thread rewinding Transparent
               and change the color of the receiving link to
               transparent.
               Otherwise, extend the received thread without   Colored
               changing color.
  1  1  *      Stall the received thread; if Hrec<unknown,     No change
               schedule "Reset to unknown" event for the
               detecting TCB.

 Next hop      If eligible-leaf, create a colored thread and   Colored
 acquisition   extend it.

 Others        Silently ignore the event.                      No change

State Colored:

 Event         Action                                          New state
 Recv thread
     Flags
   CL LP NL
   0  *  *     If Hmax+1<Hout<unknown, create a colored        No change
               thread and extend it.  Otherwise, do nothing.
   1  0  *     If Hmax<Hout, merge the received thread.        No change
               Otherwise, extend the thread with (if NL=1)
               or without (if NL=0) changing color.
   1  1  *     Stall the received thread.
               If Ni=0 and the node is not an eligible leaf,   Null
               initiate thread withdrawing.
               If Ni>0 and Hrec<unknown, schedule "Reset to    No change
               unknown" event for the detecting TCB.
               Otherwise, do nothing.                          No change








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


 Rewound       Propagate thread rewinding to previous hops   Transparent
               that are extending a colored thread; change
               the colors stored in all incoming and outgoing
               links to transparent; if Hmax+1<Hout, extend
               transparent thread.  Withdraw the thread on
               the outgoing link for which C-flag=0.

 Withdrawn     Remove the corresponding incoming link.
               If Ni=0 and the node is not an eligible leaf,   Null
               propagate thread withdrawing to all next hops.
               Otherwise, if Hmax+1<Hout<unknown, create       No change
               a colored thread and extend it.
               Otherwise, do nothing.                          No change

 Next hop      If there is already an outgoing link for the  Transparent
 acquisition   next hop, do nothing.  (This case happens only
               when the node retains the old path.)
               Otherwise, create a colored thread and extend   No change
               it.

 Next hop      If the outgoing link is transparent and the     No change
 loss          node is allowed to retain the link and the
               next hop is alive, do nothing.
               Otherwise, take the following actions.
               Initiate thread withdrawing for the next hop;
               if the node becomes a new egress, schedule
               "Rewound" event for this TCB.
               If Ni=0, move to Null.                          Null
               Otherwise, do nothing.                          No change

 Reset to      Create a colored thread of hop count unknown    No change
 unknown       and extend it.

 Others        Silently ignore the event.                      No change

State Transparent:

 Event          Action                                         New state
 Recv thread
    Flags
   CL LP NL
   0  *  *     If Hmax+1<Hout, extend a transparent thread.    No change
   1  0  *     If the node is egress or if Hmax<Hout, change   No change
               the color of the receiving link to transparent
               and start thread rewinding.
               Otherwise, extend the thread with (if NL=1)     Colored
               or without (if NL=0) changing color.




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


 Withdrawn     Remove the corresponding incoming link.
               If Ni=0 and the node is not an eligible leaf,   Null
               propagate thread withdrawing to next hops.
               Otherwise, if Hmax+1<Hout, create               No change
               a transparent thread and extend it.
               Otherwise, do nothing.                          No change

 Next hop      Create a colored thread and extend it.          Colored
 acquisition

 Next hop      If the node is allowed to retain the outgoing   No change
 loss          link and the next hop is alive, do nothing.
               Otherwise, take the following actions.
               Initiate thread withdrawing.
               If Ni=0, move to Null.                          Null
               Otherwise, do nothing.                          No change

 Others        Silently ignore the event.                      No change

9.  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
      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
      ordered downstream-on-demand allocation and ordered downstream
      allocation.  The path-vector/diffusion algorithm, however, is
      tightly coupled with the ordered downstream allocation.






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


   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.

10.  Security Considerations

   The use of the procedures specified in this document does not have
   any security impact other than that which may generally be present
   in the use of any MPLS procedures.

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

12.  Acknowledgments

   We would like to thank Hiroshi Esaki, Bob Thomas, Eric Gray, and
   Joel Halpern for their comments.























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


13.  Authors' Addresses

   Yoshihiro Ohba
   Toshiba Corporation
   1, Komukai-Toshiba-cho, Saiwai-ku
   Kawasaki 210-8582, Japan

   EMail: [e-mail]


   Yasuhiro Katsube
   Toshiba Corporation
   1, Toshiba-cho, Fuchu-shi,
   Tokyo, 183-8511, Japan

   EMail: [e-mail]


   Eric Rosen
   Cisco Systems, Inc.
   250 Apollo Drive
   Chelmsford, MA, 01824

   EMail: [e-mail]


   Paul Doolan
   Ennovate Networks
   330 Codman Hill Rd
   Marlborough MA 01719

   EMail: [e-mail]

14.  References

   [1] Callon, R., et al., "A Framework for Multiprotocol Label
       Switching", Work in Progress.

   [2] Davie, B., Lawrence, J., McCloghrie, K., Rosen, E., Swallow, G.,
       Rekhter, Y. and P. Doolan, "MPLS using LDP and ATM VC Switching",
       RFC 3035, January 2001.

   [3] Rosen, E., et al., "A Proposed Architecture for MPLS", Work in
       Progress.

   [4] Andersson, L., Doolan, P., Feldman, N., Fredette, A. and B.
       Thomas, "LDP Specification", RFC 3036, January 2001.




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


Appendix A - Further discussion of the algorithm

   The purpose of this appendix is to give a more informal and tutorial
   presentation of the algorithm, and to provide some of the motivation
   for it.  For the precise specification of the algorithm, the FSM
   should be taken as authoritative.

   As in the body of the document, we speak as if there is only one LSP;
   otherwise we would always be saying "... of the same LSP".  We also
   consider only the case where the algorithm is used for loop
   prevention, rather than loop detection.

A.1. Loop Prevention the Brute Force Way

   As a starting point, let's consider an algorithm which we might call
   "loop prevention by brute force".  In this algorithm, every path
   setup attempt must go all the way to the egress and back in order for
   the path to be setup.  This algorithm is obviously loop-free, by
   virtue of the fact that the setup messages actually made it to the
   egress and back.

   Consider, for example, an existing LSP B-C-D-E to egress node E.  Now
   node A attempts to join the LSP.  In this algorithm, A must send a
   message to B, B to