rfc2439.txt

xorp源码hg

4 Stability Sensitive Suppression of Route Advertisement

   This method of limiting route advertisements uses a measure of route
   stability applied on a per route basis.  This technique is applied
   when receiving updates from external peers only (EBGP). Applying this
   technique to IBGP learned routes or to advertisement to IBGP or EBGP
   peers after making a route selection can result in routing loops.

   A figure of merit based on a measure of instability is maintained on
   a per route basis.  This figure of merit is used in the decision to
   suppress the use of the route.  Routes with high figure of merit are
   suppressed.  Each time a route is withdrawn, the figure of merit is
   incremented.  While the route is not changing the figure of merit
   value is decayed exponentially with separate decay rates depending on
   whether the route is stable and reachable or has been stable and
   unreachable.  The decay rate may be slower when the route is
   unreachable, or the stability figure of merit could remain fixed (not
   decay at all) while the route remains unreachable.  Whether to decay
   unreachable routes at the same rate, a slower rate, or not at all is
   an implementation choice.  Decaying at a slower rate is recommended.

   A very efficient implementation is suggested in the following
   sections.  The implementation only requires computation for the
   routes contained in an update, when an update is received or
   withdrawn (as opposed to the simplistic approach of periodically
   decaying each route).  The suggested implementation involves only a
   small number of simple operations, and can be implemented using
   scaled integers.

   The behavior of unstable routes is fairly predictable.  Severely
   flapping routes will often be advertised and withdrawn at regular
   time intervals corresponding to the timers of a particular protocol
   (the IGP or exterior protocol in use where the problem exists).
   Marginal circuits or mild congestion can result in a long term
   pattern of occasional brief route withdrawal or occasional brief



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


   connectivity.

4.1 Single vs.  Multiple Configuration Parameter Sets

   The behavior of the algorithm is modified by a number of configurable
   parameters.  It is possible to configure separate sets of parameters
   designed to handle short term severe route flap and chronic milder
   route flap (a pattern of occasional drops over a long time period).
   The former would require a fast decay and low threshold (allowing a
   small number of consecutive flaps to cause a route to be suppressed,
   but allowing it to be reused after a relatively short period of
   stability).  The latter would require a very slow decay and a higher
   threshold and might be appropriate for routes for which there was an
   alternate path of similar bandwidth.

   It may also be desirable to configure different thresholds for routes
   with roughly equivalent alternate paths than for routes where the
   alternate paths have a lower bandwidth or tend to be congested.  This
   can be solved by associating a different set of parameters with
   different ranges of preference values.  Parameter selection could be
   based on BGP LOCAL_PREF.

   Parameter selection could also be based on whether an alternate route
   was known.  A route would be considered if, for any applicable
   parameter set, an alternate route with the specified preference value
   existed and the figure of merit associated with the parameter set did
   not indicate a need to suppress the route.  A less aggressive
   suppression would be applied to the case where no alternate route at
   all existed.  In the simplest case, a more aggressive suppression
   would be applied if any alternate route existed.  Only the highest
   preference (most preferred) value needs to be specified, since the
   ranges may overlap.

   It might also be desirable to configure a different set of thresholds
   for routes which rely on switched services and may disconnect at
   times to reduce connect charges.  Such routes might be expected to
   change state somewhat more often, but should be suppressed if
   continuous state changes indicate instability.

   While not essential, it might be desirable to be able to configure
   multiple sets of configuration parameters per route.  It may also be
   desirable to be able to configure sets of parameters that only
   correspond to a set of routes (identified by AS path, peer router,
   specific destinations or other means).  Experience may dictate how
   much flexibility is needed and how to best to set the parameters.
   Whether to allow different damping parameter sets for different
   routes, and whether to allow multiple figures of merit per route is
   an implementation choice.



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


   Parameter selection can also be based on prefix length.  The
   rationale is that longer prefixes tend to reach less end systems and
   are less important and these less important prefixes can be damped
   more aggressively.  This technique is in fairly widespread use.
   Small sites or those with dense address allocation who are multihomed
   are often reachable by long prefixes which are not easily aggregated.
   These sites tend to dispute the choice of prefix length for parameter
   selection.  Advocates of the technique point out that it encourages
   better aggregation.

4.2 Configuration Parameters

   At configuration time, a number of parameters may be specified by the
   user.  The configuration parameters are expressed in units meaningful
   to the user.  These differ from the parameters used at run time which
   are in unit convenient for computation.  The run time parameters are
   derived from the configuration parameters.  Suggested configuration
   parameters are listed below.

     cutoff threshold (cut)

        This value is expressed as a number of route withdrawals.  It is
        the value above which a route advertisement will be suppressed.

     reuse threshold (reuse)

        This value is expressed as a number of route withdrawals.  It is
        the value below which a suppressed route will now be used again.

     maximum hold down time (T-hold)

        This value is the maximum time a route can be suppressed no
        matter how unstable it has been prior to this period of
        stability.

     decay half life while reachable (decay-ok)

        This value is the time duration in minutes or seconds during
        which the accumulated stability figure of merit will be reduced
        by half if the route if considered reachable (whether suppressed
        or not).

     decay half life while unreachable (decay-ng)

        This value is the time duration in minutes or seconds during
        which the accumulated stability figure of merit will be reduced
        by half if the route if considered unreachable.  If not
        specified or set to zero, no decay will occur while a route



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


        remains unreachable.

     decay memory limit (Tmax-ok or Tmax-ng)

        This is the maximum time that any memory of previous instability
        will be retained given that the route's state remains unchanged,
        whether reachable or unreachable.  This parameter is generally
        used to determine array sizes.

   There may be multiple sets of the parameters above as described in
   Section 4.1.  The configuration parameters listed below would be
   applied system wide.  These include the time granularity of all
   computations, and the parameters used to control reevaluation of
   routes that have previously been suppressed.

     time granularity (delta-t)

        This is the time granularity in seconds used to perform all
        decay computations.

     reuse list time granularity (delta-reuse)

        This is the time interval between evaluations of the reuse
        lists.  Each reuse lists corresponds to an additional time
        increment.

     reuse list memory reuse-list-max

        This is the time value corresponding to the last reuse list.
        This may be the maximum value of T-hold for all parameter sets
        of may be configured.

     number of reuse lists (reuse-list-size)

        This is the number of reuse lists.  It may be determined from
        reuse-list-max or set explicitly.

   A recommended optimization is described in Section 4.8.6 that
   involves an array referred to as the "reuse index array".  A reuse
   index array is needed for each decay rate in use.  The reuse index
   array is used to estimate which reuse list to place a route when it
   is suppressed.  Proper placement avoids the need to periodically
   evaluate decay to determine if a route can be reused or when storage
   can be recovered.  Using the reuse index array avoids the need to
   compute a logarithm to determine placement.  One additional system
   wide parameter can be introduced.





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


     reuse index array size (reuse-index-array-size)

        This is the size of reuse index arrays.  This size determines
        the accuracy with which suppressed routes can be placed within
        the set of reuse lists when suppressed for a long time.

4.3 Guidelines for Setting Parameters

   The decay half life should be set to a time considerably longer than
   the period of the route flap it is intended to address.  For example,
   if the decay is set to ten minutes and a route is withdrawn and
   readvertised exactly every ten minutes, the route would continue to
   flap if the cutoff was set to a value of 2 or above.

   The stability figure of merit itself is an accumulated time decayed
   total.  This must be kept in mind in setting the decay time, cutoff
   values and reuse values.  The figure of merit is increased each time
   a route transitions from reachable to unreachable.  The figure of
   merit is decayed at a rate proportional to its current value.
   Increasing the rate of route flap therefore increments the figure of
   merit more often and reaches a given threshhold in a shorter amount
   of time.  When the response to a constant rate route flap is plotted
   this looks like a sawtooth with an abrupt rising edge and a decaying
   falling edge.  Since the absolute decay amount is proportional to the
   figure of merit, at a continuous constant flap rate the baseline of
   the sawtooth will tend to stop rising and converge if not clipped by
   a ceiling value.

   If clipped by a ceiling value, the sawtooth baseline will simply
   reach the ceiling faster at a higher rate of route flap.  For
   example, if flapping at four times the decay rate the following
   progression occurs.  When the route becomes unreachable the first
   time the value becomes 1.  When the next flap occurs, one is added to
   the previous value, which has been decreased by the fourth root of 2
   (the amount of decay that would occur in 1/4 of the half life time if
   decay is exponential).  The sequence is 1, 1.84, 2.55, 3.14, 3.64,
   4.06, 4.42, 4.71, 4.96, 5.17, ..., converging at about 6.285.  If a
   route flaps at four times the decay rate, it will reach 3 in 4
   cycles, 4 in 6 cycles, 5 in 10 cycles, and will converge at about
   6.3.  At twice the decay time, it will reach 3 in 7 cycles, and
   converge at a value of less than 3.5.

   Figure 1 shows the stability figure of merit for route flap at a
   constant rate.  The time axis is labeled in multiples of the decay
   half life.  The plots represent route flap with a period of 1/2, 1/3,
   1/4, and 1/8 times the decay half life.  A ceiling of 4.5 was set,
   which can be seen to affect three of the plots, effectively limiting
   the time it takes to readvertise the route regardless of the prior



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


   history.  With cutoff and reuse thresholds of 1.5 and 0.75,  routes
   would be suppressed after being declared unreachable 2-3 times and be
   used again after approximately 2 decay half life periods of
   stability.

   This function can be expressed formally.  Reachability of a route can
   be represented by a variable "R" with possible values of 0 and 1
   representing unreachable and reachable.  At a discrete time R can
   only have one value.  The figure of merit is increased by 1 at each
   transition from R=1 to R=0 and clipped to a ceiling value.  The decay
   in figure of merit can then be expressed over a set of discrete times
   as follows.

      figure-of-merit(t) = K * figure-of-merit(t - delta-t) 
      K = K1 for R=0 K=K2 for R=1

   The four plots are presented vertically.  Due to space limitations,
   only a limited set of points along the time axis are shown.  The
   value of the figure of merit is given.  Along side each value is a
   very low resolution strip chart made up of ASCII dots.  This is just
   intended to give a rough feel for the rise and fall of the values.
   The strip charts are not displayed on an overlapping set of axes
   because the sawtooth waveforms cross each other quite frequently.  At
   the very low resolution of these plots, the rise and fall of the
   baseline is evident, but the sawtooth nature is only observed in the
   printed value.

   From the maximum hold time value (T-hold), a ratio of the reuse value
   to a ceiling can be determined.  An integer value for the ceiling can
   then be chosen such that overflow will not be a problem and all other
   values can be scaled accordingly.  If both cutoffs are specified or
   if multiple parameter sets are used the highest ceiling will be used.