rfc2439.txt

xorp源码hg

   3.  the arrays must be full size, rather than allow more than one
       multiply per decay operation to reduce the array size.

   This example is used in later sections.  The use of multiple
   parameter sets complicates the examples somewhat.  Where multiple
   parameter sets are allowed for a single route, the decay portion of
   the algorithm is repeated for each parameter set.  If different
   routes are allowed to have different parameter sets, the routes must
   have pointers to the parameter sets to keep the time to locate to a
   minimum, but the algorithms are otherwise unchanged.

   A sample set of configuration parameters and a sample set of
   implementation parameters are provided in in the two following lists.

     1.  Configuration Parameters

        o cut = 1.25

        o reuse = 0.5

        o T-hold = 15 mins

        o decay-ok = 5 min

        o decay-ng = 15 min

        o Tmax-ok, Tmax-ng = 15, 30 mins

     2.  Implementation Parameters

        o delta-t = 1 sec

        o delta-reuse = 15 sec




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


        o reuse-list-size = 256

        o reuse-index-array-size = 1,024

   Using these configuration and implementation parameters and the
   equations in Section 4.5, the space overhead can be computed.  There
   is a fixed space overhead that is independent of the number of
   routes.  There is a space requirement associated with a stable route.
   There is a larger space requirement associated with an unstable
   route.  The space requirements for the parameters above are provide
   in the lists below.

     1.  fixed overhead (using parameters from previous example)

        o 900 * integer - decay array

        o 1,800 * integer - decay array

        o 120 * pointer - reuse list-heads

        o 2,048 * integer - reuse index arrays

     2.  overhead per stable route

        o pointer - containing null entry

     3.  overhead per unstable route

        o pointer - to a damping structure containing the following

        o integer - figure of merit  + bit for state

        o integer - last time updated

        o 2 * pointer - reuse list pointers (prev, next)

   The decay arrays are sized acording to delta-t and Tmax-ok or Tmax-
   ng.  The number of reuse list-heads is based on delta-reuse and the
   greater of Tmax-ok or Tmax-ng.  There are two reuse index arrays
   whose size is a configured parameter.

   Figure 3 shows the behavior of the algorithm with the parameters
   given above.  Four cases are given in this example.  In all four,
   there is a twelve minute period of route oscillations.  Two periods
   of oscillation are used, 2 minutes and 4 minutes.  Two duty cycles
   are used, one in which the route is reachable during 20% of the cycle
   and the other where the route is reachable during 80% of the cycle.
   In all four cases, the route becomes suppressed after it becomes



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


   unreachable the second time.  Once suppressed, it remains suppressed
   until some period after becoming stable.  The routes which oscillate
   over a 4 minute period are no longer suppressed within 9-11 minutes
   after becoming stable.  The routes with a 2 minute period of
   oscillation are suppressed for nearly the maximum 15 minute period
   after becoming stable.

4.8 Processing Routing Protocol Activity

   The prior sections concentrate on configuration parameters and their
   relationship to the parameters and arrays used at run time and
   provide the algorithms for initializing run time storage.  This
   section provides the steps taken in processing routing events and
   timer events when running.

   The routing events are:

     1.  A BGP peer or new route comes up for the first time (or after
         an extended down time) (Section 4.8.1)

     2.  A route becomes unreachable (Section 4.8.2)

     3.  A route becomes reachable again (Section 4.8.3)

     4.  A route changes (Section 4.8.4)

     5.  A peer goes down (Section 4.8.5)
























Villamizar, et. al.         Standards Track                    [Page 24]

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.62    0.000 .         0.000 .         0.000 .         0.000 .
     1.25    0.000 .         0.000 .         0.000 .         0.000 .
     1.88    0.000 .         0.000 .         0.000 .         0.000 .
     2.50    0.977  .        0.968  .        0.000 .         0.000 .
     3.12    0.949  .        0.888  .        0.000 .         0.000 .
     3.75    0.910  .        0.814  .        0.000 .         0.000 .
     4.37    1.846    .      1.756    .      0.983  .        0.983  .
     5.00    1.794    .      1.614    .      0.955  .        0.935  .
     5.63    1.735    .      1.480   .       0.928  .        0.858  .
     6.25    2.619      .    2.379     .     0.901  .        0.786  .
     6.88    2.544      .    2.207     .     0.876  .        0.721  .
     7.50    2.472     .     2.024     .     0.825  .        0.661  .
     8.13    3.308       .   2.875      .    1.761    .      1.608    .
     8.75    3.213       .   2.698      .    1.711    .      1.562    .
     9.38    3.122       .   2.474     .     1.662    .      1.436   .
    10.00    3.922        .  3.273       .   1.615    .      1.317   .
    10.63    3.810        .  3.107       .   1.569    .      1.207   .
    11.25    3.702        .  2.849      .    1.513    .      1.107   .
    11.88    3.498       .   2.613      .    1.388   .       1.015   .
    12.50    3.904        .  3.451       .   2.312     .     1.953    .
    13.13    3.580        .  3.164       .   2.120     .     1.791    .
    13.75    3.283       .   2.902      .    1.944    .      1.643    .
    14.38    3.010       .   2.661      .    1.783    .      1.506    .
    15.00    2.761      .    2.440     .     1.635    .      1.381   .
    15.63    2.532      .    2.238     .     1.499   .       1.267   .
    16.25    2.321     .     2.052     .     1.375   .       1.161   .
    16.88    2.129     .     1.882    .      1.261   .       1.065   .
    17.50    1.952    .      1.725    .      1.156   .       0.977  .
    18.12    1.790    .      1.582    .      1.060   .       0.896  .
    18.75    1.641    .      1.451   .       0.972  .        0.821  .
    19.38    1.505    .      1.331   .       0.891  .        0.753  .
    20.00    1.380   .       1.220   .       0.817  .        0.691  .
    20.62    1.266   .       1.119   .       0.750  .        0.633  .
    21.25    1.161   .       1.026   .       0.687  .        0.581  .
    21.87    1.064   .       0.941  .        0.630  .        0.533  .
    22.50    0.976  .        0.863  .        0.578  .        0.488 .
    23.12    0.895  .        0.791  .        0.530  .        0.448 .
    23.75    0.821  .        0.725  .        0.486 .         0.411 .
    24.37    0.753  .        0.665  .        0.446 .         0.377 .
    25.00    0.690  .        0.610  .        0.409 .         0.345 .

 Figure 3: Some fairly long route flap cycles, repeated for 12 minutes,
                   followed by a period of stability.





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


   The reuse list is used to provide a means of fast evaluation of route
   that had been suppressed, but had been stable long enough to be
   reused again or had been suppressed long enough that it can be
   treated as a new route.  The following two operations are described.

     1.  Inserting into a reuse list (Section 4.8.6)

     2.  Reuse list processing every delta-t seconds (Section 4.8.7)

4.8.1 Processing a New Peer or New Routes

   When a peer comes up, no action is required if the routes had no
   previous history of instability, for example if this is the first
   time the peer is coming up and announcing these routes.  For each
   route, the pointer to the damping structure would be zeroed and route
   used.  The same action is taken for a new route or a route that has
   been down long enough that the figure of merit reached zero and the
   damping structure was deleted.

4.8.2 Processing Unreachable Messages

   When a route is withdrawn or changed (Section 4.8.4 describes how a
   change is handled), the following procedure is used.

   If there is no previous stability history (the damping structure
   pointer is zero), then:

     1.  allocate a damping structure

     2.  set figure-of-merit = 1

     3.  withdraw the route

   Otherwise, if there is an existing damping structure, then:

     1.  set t-diff = t-now - t-updated

     2.  if (t-diff puts you off the end of the array) {

      setfigure-of-merit =1

    }else {

      setfigure-of-merit =figure-of-merit *decay-array-ok [t-diff ]+ 1

      if(figure-of-merit >ceiling) {

        setfigure-of-merit =ceiling



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


      }

    }

     3.  remove the route from a reuse list if it is on one

     4.  withdraw the route unless it is already suppressed

   In either case then:

     1.  set t-updated = t-now

     2.  insert into a reuse list (see Section 4.8.6)

   If there was a stability history, the previous value of the stability
   figure of merit is decayed.  This is done using the decay array
   (decay-array).  The index is determined by subtracting the current
   time and the last time updated, then dividing by the time
   granularity.  If the index is zero, the figure of merit is unchanged
   (no decay).  If it is greater than the array size, it is zeroed.
   Otherwise use the index to fetch a decay array element and multiply
   the figure of merit by the array element.  If using the suggested
   scaled integer method, shift down half an integer.  Add the scaled
   penalty for one more unreachable (shown above as 1).  If the result
   is above the ceiling replace it with the ceiling value.  Now update
   the last time updated field (preferably taking into account how much
   time was truncated before doing the decay calculation).

   When a route becomes unreachable, alternate paths must be considered.
   This process is complicated slightly if different configuration
   parameters are used in t