draft-ietf-idr-route-damp-01.txt   draft-ietf-idr-route-damp-02.txt 
Internet Engineering Task Force Curtis Villamizar Internet Engineering Task Force Curtis Villamizar
INTERNET-DRAFT ANS INTERNET-DRAFT ANS
draft-ietf-idr-route-damp-01 Ravi Chandra draft-ietf-idr-route-damp-02 Ravi Chandra
Cisco Cisco
Ramesh Govindan Ramesh Govindan
ISI ISI
January 8, 1998 February 15, 1998
BGP Route Flap Damping BGP Route Flap Damping
Status of this Memo Status of this Memo
This document is an Internet-Draft. Internet-Drafts are working This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas, documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts. working documents as Internet-Drafts.
skipping to change at page 10, line 5 skipping to change at page 10, line 5
This is the time value corresponding to the last reuse list. This 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 may be the maximum value of T-hold for all parameter sets of may be
configured. configured.
number of reuse lists (reuse-list-size) number of reuse lists (reuse-list-size)
This is the number of reuse lists. It may be determined from This is the number of reuse lists. It may be determined from
reuse-list-max or set explicitly. reuse-list-max or set explicitly.
FIGURES ARE FOUND IN THE POSTSCRIPT AND HTML VERSIONS ONLY
Figure 1: Instability figure of merit for flap at a constant rate
A necessary optimization is described in Section 4.8.6 that involves A necessary optimization is described in Section 4.8.6 that involves
an array referred to as the ``reuse index array''. A reuse index 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 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 used to estimate which reuse list to place a route when it is
suppressed. Proper placement avoids the need to periodically evaluate suppressed. Proper placement avoids the need to periodically evaluate
decay to determine if a route can be reused. Using the reuse index decay to determine if a route can be reused. Using the reuse index
array avoids the need to compute a logarithm to determine placement. array avoids the need to compute a logarithm to determine placement.
One additional system wide parameter can be introduced. One additional system wide parameter can be introduced.
reuse index array size (reuse-index-array-size) reuse index array size (reuse-index-array-size)
skipping to change at page 11, line 5 skipping to change at page 10, line 46
constant rate. The time axis is labeled in multiples of the decay 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, 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, 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 which can be seen to affect three of the plots, effectively limiting
the time it takes to readvertise the route regardless of the prior the time it takes to readvertise the route regardless of the prior
history. With the cutoff and reuse thresholds suggested by the dotted history. With the cutoff and reuse thresholds suggested by the dotted
lines, routes would be suppressed after being declared unreachable 2-3 lines, routes would be suppressed after being declared unreachable 2-3
times and be used again after approximately 2 decay half life periods times and be used again after approximately 2 decay half life periods
of stability. of stability.
FIGURES ARE FOUND IN THE POSTSCRIPT AND HTML VERSIONS ONLY
Figure 2: Separate decay constants when unreachable
From either maximum hold time value (Tmax-ok or Tmax-ng), a ratio of From either maximum hold time value (Tmax-ok or Tmax-ng), a ratio of
the cutoff to a ceiling can be determined. An integer value for the the cutoff to a ceiling can be determined. An integer value for the
ceiling can then be chosen such that overflow will not be a problem 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 and all other values can be scaled accordingly. If both cutoffs are
specified or if multiple parameter sets are used the highest ceiling specified or if multiple parameter sets are used the highest ceiling
will be used. will be used.
time figure-of-merit as a function of time
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
time figure-of-merit as a function of time
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
Figure 2 show the effect of configuring separate decay rates to be Figure 2 show the effect of configuring separate decay rates to be
used when the route is reachable or unreachable. The decay rate is used when the route is reachable or unreachable. The decay rate is
5 times slower when the route is unreachable. In the three case 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 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 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 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 case the route is not suppressed until after the third unreachable
(when it is above the top threshold after becoming reachable again). (when it is above the top threshold after becoming reachable again).
In both Figure 1 and Figure 2, routes would be suppressed. Routes In both Figure 1 and Figure 2, routes would be suppressed. Routes
skipping to change at page 20, line 4 skipping to change at page 21, line 23
o 1,800 * integer - decay array o 1,800 * integer - decay array
o 120 * pointer - reuse list-heads o 120 * pointer - reuse list-heads
o 2,048 * integer - reuse index arrays o 2,048 * integer - reuse index arrays
2. overhead per stable route 2. overhead per stable route
o pointer - containing null entry o pointer - containing null entry
FIGURES ARE FOUND IN THE POSTSCRIPT AND HTML VERSIONS ONLY
Figure 3: Some fairly long route flap cycles, repeated for 12
minutes, followed by a period of stability.
3. overhead per unstable route 3. overhead per unstable route
o pointer - to a damping structure containing the following o pointer - to a damping structure containing the following
o integer - figure of merit + bit for state o integer - figure of merit + bit for state
o integer - last time updated o integer - last time updated
o pointer (optional) to configuration parameter block o pointer (optional) to configuration parameter block
skipping to change at page 20, line 34 skipping to change at page 22, line 5
tion are used, 2 minutes and 4 minutes. Two duty cycles are used, one tion 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 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 where the route is reachable during 80% of the cycle. In all four
cases, the route becomes suppressed after it becomes unreachable the cases, the route becomes suppressed after it becomes unreachable the
second time. Once suppressed, it remains suppressed until some period second time. Once suppressed, it remains suppressed until some period
after becoming stable. The routes which oscillate over a 4 minute pe- after becoming stable. The routes which oscillate over a 4 minute pe-
riod are no longer suppressed within 9-11 minutes after becoming sta- riod are no longer suppressed within 9-11 minutes after becoming sta-
ble. The routes with a 2 minute period of oscillation are suppressed for ble. The routes with a 2 minute period of oscillation are suppressed for
nearly the maximum 15 minute period after becoming stable. nearly the maximum 15 minute period after becoming stable.
time figure-of-merit as a function of time
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.
4.8 Processing Routing Protocol Activity 4.8 Processing Routing Protocol Activity
The prior sections concentrate on configuration parameters and their The prior sections concentrate on configuration parameters and their
relationship to the parameters and arrays used at run time and provide relationship to the parameters and arrays used at run time and provide
the algorithms for initializing run time storage. This section the algorithms for initializing run time storage. This section
provides the steps taken in processing routing events and timer events provides the steps taken in processing routing events and timer events
when running. when running.
The routing events are: The routing events are:
 End of changes. 

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/