rfc2439.txt

xorp源码hg

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


   time      figure-of-merit as a function of time (in minutes)

  0.00    0.000 .         0.000 .         0.000 .         0.000 .
  0.08    0.000 .         0.000 .         0.000 .         0.000 .
  0.16    0.000 .         0.000 .         0.000 .         0.973  .
  0.24    0.000 .         0.000 .         0.000 .         0.920  .
  0.32    0.000 .         0.000 .         0.946  .        1.817    .
  0.40    0.000 .         0.953  .        0.895  .        2.698     .
  0.48    0.000 .         0.901  .        0.847  .        2.552     .
  0.56    0.953  .        0.853  .        1.754    .      3.367      .
  0.64    0.901  .        0.807  .        1.659   .       4.172        .
  0.72    0.853  .        1.722    .      1.570   .       3.947        .
  0.80    0.807  .        1.629   .       2.444     .     4.317        .
  0.88    0.763  .        1.542   .       2.312     .     4.469        .
  0.96    0.722  .        1.458   .       2.188    .      4.228        .
  1.04    1.649   .       2.346     .     3.036      .    4.347        .
  1.12    1.560   .       2.219    .      2.872      .    4.112        .
  1.20    1.476   .       2.099    .      2.717     .     4.257        .
  1.28    1.396   .       1.986    .      3.543       .   4.377        .
  1.36    1.321   .       2.858      .    3.352      .    4.141        .
  1.44    1.250   .       2.704     .     3.171      .    4.287        .
  1.52    2.162    .      2.558     .     3.979        .  4.407        .
  1.60    2.045    .      2.420     .     3.765       .   4.170        .
  1.68    1.935    .      3.276      .    3.562       .   4.317        .
  1.76    1.830    .      3.099      .    4.356        .  4.438        .
  1.84    1.732    .      2.932      .    4.121        .  4.199        .
  1.92    1.638   .       2.774     .     3.899       .   3.972        .
  2.00    1.550   .       2.624     .     3.688       .   3.758       .
  2.08    1.466   .       2.483     .     3.489       .   3.555       .
  2.16    1.387   .       2.349     .     3.301      .    3.363      .
  2.24    1.312   .       2.222    .      3.123      .    3.182      .
  2.32    1.242   .       2.102    .      2.955      .    3.010      .
  2.40    1.175   .       1.989    .      2.795     .     2.848      .
  2.48    1.111  .        1.882    .      2.644     .     2.694     .
  2.56    1.051  .        1.780    .      2.502     .     2.549     .
  2.64    0.995  .        1.684   .       2.367     .     2.411     .
  2.72    0.941  .        1.593   .       2.239    .      2.281     .
  2.80    0.890  .        1.507   .       2.118    .      2.158    .
  2.88    0.842  .        1.426   .       2.004    .      2.042    .
  2.96    0.797  .        1.349   .       1.896    .      1.932    .
  3.04    0.754  .        1.276   .       1.794    .      1.828    .
  3.12    0.713  .        1.207   .       1.697    .      1.729    .
  3.20    0.675  .        1.142   .       1.605   .       1.636   .
  3.28    0.638  .        1.081  .        1.519   .       1.547   .
  3.36    0.604  .        1.022  .        1.437   .       1.464   .
  3.44    0.571  .        0.967  .        1.359   .       1.385   .

   Figure 1: Instability figure of merit for flap at a constant rate



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


  time      figure-of-merit as a function of time (in minutes)

  0.00    0.000 .         0.000 .         0.000 .
  0.20    0.000 .         0.000 .         0.000 .
  0.40    0.000 .         0.000 .         0.000 .
  0.60    0.000 .         0.000 .         0.000 .
  0.80    0.000 .         0.000 .         0.000 .
  1.00    0.999  .        0.999  .        0.999  .
  1.20    0.971  .        0.971  .        0.929  .
  1.40    0.945  .        0.945  .        0.809  .
  1.60    0.919  .        0.865  .        0.704  .
  1.80    0.894  .        0.753  .        0.613  .
  2.00    1.812    .      1.657   .       1.535   .
  2.20    1.762    .      1.612   .       1.428   .
  2.40    1.714    .      1.568   .       1.244   .
  2.60    1.667   .       1.443   .       1.083  .
  2.80    1.622   .       1.256   .       0.942  .
  3.00    1.468   .       1.094  .        0.820  .
  3.20    2.400     .     2.036    .      1.694    .
  3.40    2.335     .     1.981    .      1.475   .
  3.60    2.271     .     1.823    .      1.284   .
  3.80    2.209    .      1.587   .       1.118  .
  4.00    1.999    .      1.381   .       0.973  .
  4.20    2.625     .     2.084    .      1.727    .
  4.40    2.285     .     1.815    .      1.503   .
  4.60    1.990    .      1.580   .       1.309   .
  4.80    1.732    .      1.375   .       1.139   .
  5.00    1.508   .       1.197   .       0.992  .
  5.20    1.313   .       1.042  .        0.864  .
  5.40    1.143   .       0.907  .        0.752  .
  5.60    0.995  .        0.790  .        0.654  .
  5.80    0.866  .        0.688  .        0.570  .
  6.00    0.754  .        0.599  .        0.496 .
  6.20    0.656  .        0.521 .         0.432 .
  6.40    0.571  .        0.454 .         0.376 .
  6.60    0.497 .         0.395 .         0.327 .
  6.80    0.433 .         0.344 .         0.285 .
  7.00    0.377 .         0.299 .         0.248 .
  7.20    0.328 .         0.261 .         0.216 .
  7.40    0.286 .         0.227 .         0.188 .
  7.60    0.249 .         0.197 .         0.164 .
  7.80    0.216 .         0.172 .         0.142 .
  8.00    0.188 .         0.150 .         0.124 .

          Figure 2: Separate decay constants when unreachable






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


   Figure 2 shows the effect of configuring separate decay rates to be
   used when the route is reachable or unreachable.  The decay rate is 5
   times slower when the route is unreachable.  In the three case shown,
   the period of the route flap is equal to the decay half life but the
   route is reachable 1/8 of the time in one, reachable 1/2 the time in
   one, and reachable 7/8 of the time in the other.  In the last case
   the route is not suppressed until after the third unreachable (when
   it is above the top threshold after becoming reachable again).

   The main point of Figure 2 is to show the effect of changing the duty
   cycle of the square wave in the variable "R" for a fixed frequency of
   the square wave.  If the decay constants are chosen such that decay
   is slower when R=0 (the route is unreachable), then the figure of
   merit rises more slowly (more accurately, the baseline of the
   sawtooth waveform rises more slowly) if the route is reachable a
   larger percentage of the time.  The effect when the route becomes
   persistently reachable again can be fairly negligible if the sawtooth
   is clipped by a ceiling value, but is more significant if a slow
   route flap rate or short interval of route flapping is such that the
   sawtooth does not reach the ceiling value.  In Figure 2 the interval
   in which the routes are unstable is short enough that the ceiling
   value is not reached, therefore, the routes that are reachable for a
   greater percentage of the route flap cycle are reused (placed in the
   RIB and advertised to peers) sooner than others after the route
   becomes stable again ("R" becomes 1, indicating the announced state
   goes to reachable and remains there).

   In both Figure 1 and Figure 2, routes would be suppressed.  Routes
   flapping at the decay half life or less would be withdrawn two or
   three times and then remain withdrawn until they had remained stably
   announced and stable for on the order of 1 1/2 to 2 1/2 times the
   decay half life (given the ceiling in the example).

   The purpose of damping BGP route flap is to reduce the processor
   burden at the immediate router and the processor burden to downstream
   routers (BGP peer routers and peers of peers that will see the route
   announcements advertised by the immediate router).  Computing a
   figure of merit at each discrete time interval using  figure-of-
   merit(t) = K * figure-of-merit(t - delta-t) would be very inefficient
   and defeat the purpose.  This problem is addressed by defering
   computation as long as possible and doing a single simple computation
   to compensate for the decay during the time that has elapsed since
   the figure of merit was last updated.  The use of decay arrays
   provides the single simple calculation.  The use of reuse lists
   (described later) provide a means to defer calculations.  A route
   becomes usable if there was not further change for a period of time
   and the route is unreachable.  The data structure storage is
   recovered if the route's state has not changed for a period of time



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


   and it has been unreachable.  The reuse arrays provide a means to
   estimate how long a computation can be deferred if there is no
   further change.

   A larger time granularity will keep table storage down.  The time
   granularity should be less than a minimal reasonable time between
   expected worse case route flaps.  It might be reasonable to fix this
   parameter at compile time or set a default and strongly recommend
   that the user leave it alone.  With an exponential decay, array size
   can be greatly reduced by setting a period of complete stability
   after which the decayed total will be considered zero rather than
   retaining a tiny quantity.  Alternately, very long decays can be
   implemented by multiplying more than once if array bounds are
   exceeded.

   The reuse lists hold suppressed routes grouped according to how long
   it will be before the routes are eligible for reuse.  Periodically
   each list will be advanced by one position and one list removed as
   described in Section 4.8.7.  All of the suppressed routes in the
   removed list will be reevaluated and either used or placed in another
   list according to how much additional time must elapse before the
   route can be reused.  The last list will always contain all the
   routes which will not be advertised for more time than is appropriate
   for the remaining list heads.  When the last list advances to the
   front, some of the routes will not be ready to be used and will have
   to be requeued.  The time interval for reconsidering suppressed
   routes and number of list heads should be configurable.  Reasonable
   defaults might be 30 seconds and 64 list heads.  A route suppressed
   for a long time would need to be reevaluated every 32 minutes.

4.4 Run Time Data Structures

   A fixed small amount of per system storage will be required.  Where
   sets of multiple configuration parameters are used, storage will be
   required per set of parameters.  A small amount of per route storage
   is required.  A set of list heads is needed.  These list heads are
   used to arrange suppressed routes according to the time remaining
   until they can be reused.

   A separate reuse list can be used to hold unreachable routes for the
   purpose of later recovering storage if they remain unreachable too
   long.  This might be more accurately described as a recycling list.
   The advantage this would provide is making free data structures
   available as soon as possible.  Alternately, the data structures can
   simply be placed on a queue and the storage recovered when the route
   hits the front of the queue and if storage is needed.  The latter is
   less optimal but simple.




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


   If multiple sets of configuration parameters are allowed per route,
   there is a need for some means of associating more than one figure of
   merit and set of parameters with each route.  Building a linked list
   of these objects seems like one of a number of reasonable
   implementations.  Similarly, a means of associating a route to a
   reuse list is required.  A small overhead will be required for the
   pointers needed to implement whatever data structure is chosen for
   the reuse lists.  The suggested implementation uses a double linked
   lists and so requires two pointers per figure of merit.

   Each set of configuration parameters can reference decay arrays and
   reuse arrays.  These arrays should be shared among multiple sets of
   parameters since their storage requirement is not negligible.  There
   will be only one set of reuse list heads for the entire router.

4.4.1 Data Structures for Configuration Parameter Sets

   Based on the configuration parameters described in the previous
   section, the following values can be computed as scaled integers
   directly from the corresponding configuration parameters.

   o  decay array scale factor (decay-array-scale-factor)

   o  cutoff value (cut)

   o  reuse value (reuse)

   o  figure of merit ceiling (ceiling)

   Each configuration parameter set will reference one or two decay
   arrays and one or two reuse arrays.  Only one array will be needed if
   the decay rate is the same while a route is unreachable as while it
   is reachable, or if the stability figure of merit does not decay
   while a route is unreachable.

4.4.2 Data Structures per Decay Array and Reuse Index Array

   The following are also computed from the configuration parameters
   though not as directly.  The computation is described in Section 4.5.

   o  decay rate per tick (decay-delta-t)

   o  decay array size (decay-array-size)

   o  decay array (decay[])

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