rfc3063.txt

最新的RFC

Network Working Group                                            Y. Ohba
Request for Comments: 3063                                    Y. Katsube
Category: Experimental                                           Toshiba
                                                                E. Rosen
                                                           Cisco Systems
                                                               P. Doolan
                                                       Ennovate Networks
                                                           February 2001


                     MPLS Loop Prevention Mechanism

Status of this Memo

   This memo defines an Experimental Protocol for the Internet
   community.  It does not specify an Internet standard of any kind.
   Discussion and suggestions for improvement are requested.
   Distribution of this memo is unlimited.

Copyright Notice

   Copyright (C) The Internet Society (2001).  All Rights Reserved.

Abstract

   This paper presents a simple mechanism, based on "threads", which can
   be used to prevent Multiprotocol Label Switching (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 ordered downstream-on-demand allocation or
   ordered downstream allocation.  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.                  Experimental                      [Page 1]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


Table of Contents

   1      Introduction ..........................................  2
   2      Basic definitions .....................................  3
   3      Thread basics .........................................  5
   3.1    Thread attributes .....................................  5
   3.2    Thread loop ...........................................  7
   3.3    Primitive thread actions ..............................  7
   3.4    Examples of primitive thread actions  ................. 10
   4      Thread algorithm ...................................... 14
   5      Applicability of the algorithm ........................ 14
   5.1    LSP Loop prevention/detection ......................... 15
   5.2    Using old path while looping on new path .............. 15
   5.3    How to deal with ordered downstream allocation ........ 15
   5.4    How to realize load splitting ......................... 15
   6      Why this works ........................................ 16
   6.1    Why a thread with unknown hop count is extended ....... 16
   6.2    Why a rewound thread cannot contain a loop ............ 17
   6.2.1  Case1: LSP with known link hop counts ................. 17
   6.2.1  Case2: LSP with unknown link hop counts ............... 17
   6.3    Why L3 loop is detected ............................... 17
   6.4    Why L3 loop is not mis-detected ....................... 17
   6.5    How a stalled thread automatically recovers from loop . 18
   6.6    Why different colored threads do not chase each other . 18
   7      Loop prevention examples .............................. 19
   7.1    First example ......................................... 19
   7.2    Second example ........................................ 23
   8      Thread control block .................................. 24
   8.1    Finite state machine .................................. 25
   9      Comparison with path-vector/diffusion method .......... 28
   10     Security Considerations ............................... 29
   11     Intellectual Property Considerations .................. 29
   12     Acknowledgments ....................................... 29
   13     Authors' Addresses .................................... 30
   14     References ............................................ 30
   Appendix A   Further discussion of the algorithm ............. 31
   Full Copyright Statement ..................................... 44

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.

   When an LSR finds that it has a new next hop for a particular FEC
   (Forwarding Equivalence Class) [1], 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.



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


   For a given LSP, once a thread is extended to a particular next hop,
   no other thread is extended to that next hop unless there is a change
   in the hop count from the furthest upstream node.  The only state
   information that needs to be associated with a particular next hop
   for a particular LSP is the thread color and hop count.

   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 and 4 provide 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 hop count, but when the thread has been
   rewound, they need only remember its hop count.

   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 ordered
   downstream on-demand label allocation or ordered downstream
   unsolicited label allocation [2,3].  The mechanism can also be
   applicable to loop detection, old path retention, and load-splitting.

   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 network size.  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 (see section 9).

2. Basic definitions

   LSP

      We will use the term LSP to refer to a multipoint-to-point tree
      whose root is the egress node.  See section 3.5 of [3].







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


      In the following, we speak as if there were only a single LSP
      being set up in the network.  This allows us to talk of incoming
      and outgoing links without constantly saying something like "for
      the same LSP.

   Incoming Link, Upstream Link
   Outgoing Link, Downstream Link

      At a given node, a given LSP will have one or more incoming, or
      upstream links, and one outgoing or downstream link.  A "link" is
      really an abstract relationship with an "adjacent" LSR; it is an
      "edge" in the "tree", and not necessarily a particular concrete
      entity like an "interface".

   Leaf Node, Ingress Node

      A node which has no upstream links.

   Eligible Leaf Node

      A node which is capable of being a leaf node.  For example, a node
      is not an eligible leaf node if it is not allowed to directly
      inject L3 packets created or received at the node into its
      outgoing link.

   Link Hop Count

      Every link is labeled with a "link hop count".  This is the number
      of hops between the given link and the leaf node which is furthest
      upstream of the given link.  At any node, the link hop count for
      the downstream link is one more than the largest of the hop counts
      associated with the upstream links.

      We define the quantity "Hmax" at a given node to be the maximum of
      all the incoming link hop counts.  Note that, the link hop count
      of the downstream link is equal to Hmax+1.  At a leaf node, Hmax
      is set to be zero.

      An an example of link hop counts is shown in Fig.1.












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


                    1   2
                   A---B---C       K
                           |       |
                           |3      |1
                           |       |
                           | 4   5 | 6   7
                           D---G---H---I---J
                           |
                           |2
                         1 |
                       E---F

                 Fig.1  Example of link hop counts

   Next Hop Acquisition

      Node N thought that FEC F was unreachable, but now has a next hop
      for it.

   Next Hop Loss

      Node N thought that node A was the next hop for FEC F, but now no
      longer has the next hop for FEC F.  A node loses a next hop
      whenever the next hop goes down.

   Next Hop Change

      At node N, the next hop for FEC F changes from node A to node B,
      where A is different than B.  A next hop change event can be seen
      as a combination of a next hop loss event on the old next hop and
      a next hop acquisition event on the new next hop.

3. Thread basics

   A thread is a sequence of messages used to set up an LSP, in the
   "ordered downstream-on-demand" (ingress-initiated ordered control)
   style.

3.1.  Thread attributes

   There are three attributes related to threads.  They may be encoded
   into a single thread object as:









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


    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                             +
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   Hop Count   |      TTL      |           Reserved            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Thread Color

      Every time a path control message is initiated by a node, the node
      assigns a unique "color" to it.  This color is to be unique in
      both time and space: its encoding consists of an IP address of the
      node concatenated with a unique event identifier from a numbering
      space maintained by the node.  The path setup messages that the
      node sends downstream will contain this color.  Also, when the
      node sends such a message downstream, it will remember the color,
      and this color becomes the color of the downstream link.

      When a colored message is received, its color becomes the color of
      the incoming link.  The thread which consists of messages of a
      certain color will be known as a thread of that color.

      special color value "transparent"(=all 0's) is reserved.

      One possible method for unique color assignment is, starting the
      event identifier from its initial value, and incrementing it by
      one (modulo its maximum value) each time a color is assigned.  In
      this method, the initial event identifier is either selected at
      random or assigned to be larger than the largest event identifier
      used on the previous system incarnation.

   Thread Hop Count

      In order to maintain link hop counts, we need to carry hop counts
      in the path control messages.  For instance, a leaf node would
      assign a hop count of 1 to its downstream link, and would store
      that value into a path setup message it sends downstream.  When a
      path setup message is sent downstream, a node would assign a hop
      count which is one more than the largest of the incoming link hop
      counts, to its downstream link, and  would store that value into a
      path setup message it sends downstream.  Once the value is stored
      in a path control message, we may refer to it has a "thread hop
      count".






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