📄 rfc2439.txt
字号:
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.
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
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -