rfc2439.txt

xorp源码hg

Villamizar, et. al.         Standards Track                    [Page 16]

RFC 2439                 BGP Route Flap Damping            November 1998


   o  reuse index array (reuse-index-array[])

   For each decay rate specified, an array will be used to store the
   value of a computed parameter raised to the power of the index of
   each array element.  This is to speed computations.  The decay rate
   per tick is an intermediate value expressed as a real number and used
   to compute the values stored in the decay arrays.  The array size is
   computed from the decay memory limit configuration parameter
   expressed as an array size or as a maximum hold time.

   The decay array size must be of sufficient size to accommodate the
   specified decay memory given the time granularity, or sufficient to
   hold the number of array elements until integer rounding produces a
   zero result if that value is smaller, or a implementation imposed
   reasonable size to prevent configurations which use excessive memory.
   Implementations may chose to make the array size shorter and multiply
   more than once when decaying a long time interval to reduce storage.

   The reuse index arrays serve a similar purpose to the decay arrays.
   In BGP, a route is said to be "used" if it is considered the best
   route.  In this context, if the route is "used" it is placed in the
   RIB and is eligible for advertisement to BGP peers.  If a route is
   withdrawn (a BGP announcement is made by a peer indicating that it is
   no longer reachable), then it is no longer eligible for "use".  When
   a route becomes reachable it may not be "used" immediately if the
   figure of merit indicates that a recent instability has occurred.
   After the route remains stable and the figure of merit decays below
   the "reuse" threshhold, the route is said to be eligible to be
   "reused" (treated as truly reachable, placed in the RIB and
   advertised to peers).  The amount of time until a route can be reused
   can be determined using a array lookup.  The array can be built given
   the decay rate.  The array is indexed using a scaled integer
   proportional to the ratio between a current stability figure of merit
   value and the value needed for the route to be reused.

4.4.3 Per Route State

   Information must be maintained per some tuple representing a route.
   At the very minimum, the NLRI (BGP prefix and length) must be
   contained in the tuple.  Different BGP attributes may be included or
   excluded depending on the specific situation.  The AS path should
   also be contained in the tuple by default.  The tuple may also
   optionally contain other BGP attributes such as
   MULTI_EXIT_DISCRIMINATOR (MED).

   The tuple representing a route for the purpose of route flap damping
   is:




Villamizar, et. al.         Standards Track                    [Page 17]

RFC 2439                 BGP Route Flap Damping            November 1998


      tuple entry            default      options
      -------------------------------------------
      NLRI
        prefix               required
        length               required
      AS path                included     option to exclude
      last AS set in path    excluded     option to include
      next hop               excluded     option to include
      MED                    excluded     option to include
                                          in comparisons only

   The AS path is generally included in order to identify downstream
   instability which is not being damped or not being sufficiently
   damped and is alternating between a stable and an unstable path.
   Under rare circumstances it may be desirable to exclude AS path for
   all or a subset of prefixes.  If an AS path ends in an AS set, in
   practice the path is always for an aggregate.  Changes to the
   trailing AS set should be ignored.  Ideally the AS path comparison
   should insure that at least one AS has remained constant in the old
   and new AS set, but completely ignoring the contents of a trailing AS
   set is also acceptable.

   Including next hop and MED changes can help suppress the use of an AS
   which is internally unstable or avoid a next hop which is closer to
   an unstable IGP path in the adjacent AS. If a large number of MED
   values are used, the increase in the amount of state may become a
   problem.  For this reason MED is disabled by default and enabled only
   as part of the tuple comparison, using a single state entry
   regardless of MED value.  Including MED will suppress the use of the
   adjacent AS even though the change need not be propagated further.
   Using MED is only a safe practice if a path is known to exist through
   another AS or where there are enough peering sites with the adjacent
   AS such that routes heard at only a subset of the peering sites will
   be suppressed.

4.4.4 Data Structures per Route

   The following information must be maintained per route.  A route here
   is considered to be a tuple usually containing NLRI, next hop, and AS
   path as defined in Section 4.4.3.

     stability figure of merit (figure-of-merit)

        Each route must have a stability figure of merit per applicable
        parameter set.

     last time updated (time-update)




Villamizar, et. al.         Standards Track                    [Page 18]

RFC 2439                 BGP Route Flap Damping            November 1998


        The exact last time updated must be maintained to allow
        exponential decay of the accumulated figure of merit to be
        deferred until the route might reasonable be considered eligible
        for a change in status (having gone from unreachable to
        reachable or advancing within the reuse lists).

     config block pointer

        Any implementation that supports multiple parameter sets must
        provide a means of quickly identifying which set of parameters
        corresponds to the route currently being considered.  For
        implementations supporting only parameter sets where all routes
        must be treated the same, this pointer is not required.

     reuse list traversal pointers

        If doubly linked lists are used to implement reuse lists, then
        two pointers will be needed, previous and next.  Generally there
        is a double linked list which is unused when a route is
        suppressed from use that can be used for reuse list traversal
        eliminating the need for additional pointer storage.

4.5 Processing Configuration Parameters

        From the configuration parameters, it is possible to precompute
        a number of values that will be used repeatedly and retain these
        to speed later computations that will be required frequently.

        Scaling is usually dependent on the highest value that figure-
        of-merit can attain, referred to here as the ceiling.  The real
        number value of the ceiling will typically be determined by the
        following equation.  The ceiling can also be configured to a
        specific value, which in turn dictates T-hold.

            ceiling = reuse * (exp(T-hold/decay-half-life) * log(2))

        In the above equation, reuse is the reuse threshhold described
        in Section 4.2.

        The methods of scaled integer arithmetic are not described in
        detail here.  The methods of determining the real values are
        given.  Translation into scaled integer values and the details
        of scaled integer arithmetic are left up to the individual
        implementations.

     The ceiling value can be set to be the largest integer that can fit
     in half the bits available for an unsigned integer.  This will
     allow the scaled integers to be multiplied by the scaled decay



Villamizar, et. al.         Standards Track                    [Page 19]

RFC 2439                 BGP Route Flap Damping            November 1998


     value and then shifted down.  Implementations may prefer to use
     real numbers or may use any integer scaling deemed appropriate for
     their architecture.

     penalty value and thresholds (as proportional scaled integers)

        The figure of merit penalty for one route withdrawal and the
        cutoff values must be scaled according to the above scaling
        factor.

     decay rate per tick (decay[1])

        The decay value per increment of time as defined by the time
        granularity must be determined (at least initially as a floating
        point number).  The per tick decay is a number slightly less
        than one.  It is the Nth root of the one half where N is the
        half life divided by the time granularity.

          decay[1] = exp ((1 / (decay-half-life/delta-t)) * log (1/2))

     decay array size (decay-array-size)

        The decay array size is the decay memory divided by the time
        granularity.  If integer truncation brings the value of an array
        element to zero, the array can be made smaller.  An
        implementation should also impose a maximum reasonable array
        size or allow more than one multiplication.

                       decay-array-size = (Tmax/delta-t)

     decay array (decay[])

        Each i-th element of the decay array is the per tick delay
        raised to the i-th power.  This might be best done by successive
        floating point multiplies followed by scaling and integer
        rounding or truncation.  The array itself need only be computed
        at startup.

                            decay[i] = decay[1] ** i

4.6 Building the Reuse Index Arrays

   The reuse lists may be accessed quite frequently if a lot of routes
   are flapping sufficiently to be suppressed.  A method of speeding the
   determination of which reuse list to use for a given route is
   suggested.  This method is introduced in Section 4.2, its
   configuration described in Section 4.4.2 and the algorithms described
   in Section 4.8.6 and Section 4.8.7.  This section describes building



Villamizar, et. al.         Standards Track                    [Page 20]

RFC 2439                 BGP Route Flap Damping            November 1998


   the reuse list index arrays.

   A ratio of the figure of merit of the route under consideration to
   the cutoff value is used as the basis for an array lookup.  The ratio
   is scaled and truncated to an integer and used to index the array.
   The array entry is an integer used to determine which reuse list to
   use.

     reuse array maximum ratio (max-ratio)

        This is the maximum ratio between the current value of the
        stability figure of merit and the target reuse value that can be
        indexed by the reuse array.  It may be limited by the ceiling
        imposed by the maximum hold time or by the amount of time that
        the reuse lists cover.

          max-ratio = min(ceiling/reuse, exp((1 / (half-life/reuse-
       array-time)) * log(2)))

     reuse array scale factor ( scale-factor )

        Since the reuse array is an estimator, the reuse array scale
        factor has to be computed such that the full size of the reuse
        array is used.

            scale-factor = reuse-index-array-size / (max-ratio - 1)

     reuse index array (reuse-index-array[])

        Each reuse index array entry should contain an index into the
        reuse list array pointing to one of the list heads.  This index
        should corresponding to the reuse list that will be evaluated
        just after a route would be eligible for reuse given the ratio
        of current value of the stability figure of merit to target
        reuse value corresponding the the reuse array entry.

          reuse-index-array[j] = integer((decay-half-life / reuse-
       time-granularity) * log(1/(reuse * (1 + (j / scale-factor)))) /
       log(1/2))

   To determine which reuse queue to place a route which is being
   suppressed, the following procedure is used.  Divide the current
   figure of merit by the cutoff.  Subtract one.  Multiply by the scale
   factor.  This is the index into the reuse index array (reuse-index-
   array[]).  The value fetched from the reuse index array (reuse-
   index-array[]) is an index into the array of reuse lists (reuse-
   array[]).  If this index is off the end of the array use the last
   queue otherwise look in the array and pick the number of the queue



Villamizar, et. al.         Standards Track                    [Page 21]

RFC 2439                 BGP Route Flap Damping            November 1998


   from the array at that index.  This is quite fast and well worth the
   setup and storage required.

4.7 A Sample Configuration

   A simple example is presented here in which the space overhead is
   estimated for a set of configuration parameters.  The design here
   assumes:

   1.  there is a single parameter set used for all routes,

   2.  decay time for unreachable routes is slower than for reachable
       routes