--- 1/draft-ietf-idr-route-damp-01.txt 2006-02-04 23:31:37.000000000 +0100 +++ 2/draft-ietf-idr-route-damp-02.txt 2006-02-04 23:31:37.000000000 +0100 @@ -1,18 +1,18 @@ Internet Engineering Task Force Curtis Villamizar INTERNET-DRAFT ANS -draft-ietf-idr-route-damp-01 Ravi Chandra +draft-ietf-idr-route-damp-02 Ravi Chandra Cisco Ramesh Govindan ISI - January 8, 1998 + February 15, 1998 BGP Route Flap Damping Status of this Memo This document is an Internet-Draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. @@ -405,24 +405,20 @@ 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. - 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 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. Using the reuse index array avoids the need to compute a logarithm to determine placement. One additional system wide parameter can be introduced. reuse index array size (reuse-index-array-size) @@ -450,31 +446,120 @@ 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 history. With the cutoff and reuse thresholds suggested by the dotted lines, routes would be suppressed after being declared unreachable 2-3 times and be used again after approximately 2 decay half life periods 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 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 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. + 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 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). In both Figure 1 and Figure 2, routes would be suppressed. Routes @@ -849,24 +926,20 @@ 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 - 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 o pointer - to a damping structure containing the following o integer - figure of merit + bit for state o integer - last time updated o pointer (optional) to configuration parameter block @@ -879,20 +952,67 @@ 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 where the route is reachable during 80% of the cycle. In all four cases, the route becomes suppressed after it becomes unreachable the second time. Once suppressed, it remains suppressed until some period after becoming stable. The routes which oscillate over a 4 minute pe- 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 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 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: