| 1 |
<pre>Network Working Group C. Villamizar |
| 2 |
Request for Comments: 2439 ANS |
| 3 |
Category: Standards Track R. Chandra |
| 4 |
Cisco |
| 5 |
R. Govindan |
| 6 |
ISI |
| 7 |
November 1998 |
| 8 |
|
| 9 |
|
| 10 |
<span class="h1">BGP Route Flap Damping</span> |
| 11 |
|
| 12 |
Status of this Memo |
| 13 |
|
| 14 |
This document specifies an Internet standards track protocol for the |
| 15 |
Internet community, and requests discussion and suggestions for |
| 16 |
improvements. Please refer to the current edition of the "Internet |
| 17 |
Official Protocol Standards" (STD 1) for the standardization state |
| 18 |
and status of this protocol. Distribution of this memo is unlimited. |
| 19 |
|
| 20 |
Copyright Notice |
| 21 |
|
| 22 |
Copyright (C) The Internet Society (1998). All Rights Reserved. |
| 23 |
|
| 24 |
Abstract |
| 25 |
|
| 26 |
A usage of the BGP routing protocol is described which is capable of |
| 27 |
reducing the routing traffic passed on to routing peers and therefore |
| 28 |
the load on these peers without adversely affecting route convergence |
| 29 |
time for relatively stable routes. This technique has been |
| 30 |
implemented in commercial products supporting BGP. The technique is |
| 31 |
also applicable to IDRP. |
| 32 |
|
| 33 |
The overall goals are: |
| 34 |
|
| 35 |
o to provide a mechanism capable of reducing router processing load |
| 36 |
caused by instability |
| 37 |
|
| 38 |
o in doing so prevent sustained routing oscillations |
| 39 |
|
| 40 |
o to do so without sacrificing route convergence time for generally |
| 41 |
well behaved routes. |
| 42 |
|
| 43 |
This must be accomplished keeping other goals of BGP in mind: |
| 44 |
|
| 45 |
o pack changes into a small number of updates |
| 46 |
|
| 47 |
o preserve consistent routing |
| 48 |
|
| 49 |
|
| 50 |
|
| 51 |
|
| 52 |
<span class="grey">Villamizar, et. al. Standards Track [Page 1]</span></pre> |
| 53 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-2" ></span> |
| 54 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 55 |
|
| 56 |
|
| 57 |
o minimal addition space and computational overhead |
| 58 |
|
| 59 |
An excessive rate of update to the advertised reachability of a |
| 60 |
subset of Internet prefixes has been widespread in the Internet. |
| 61 |
This observation was made in the early 1990s by many people involved |
| 62 |
in Internet operations and remains the case. These excessive updates |
| 63 |
are not necessarily periodic so route oscillation would be a |
| 64 |
misleading term. The informal term used to describe this effect is |
| 65 |
"route flap". The techniques described here are now widely deployed |
| 66 |
and are commonly referred to as "route flap damping". |
| 67 |
|
| 68 |
<span class="h2"><a class="selflink" id="section-1" href="#section-1">1</a> Overview</span> |
| 69 |
|
| 70 |
To maintain scalability of a routed internet, it is necessary to |
| 71 |
reduce the amount of change in routing state propagated by BGP in |
| 72 |
order to limit processing requirements. The primary contributors of |
| 73 |
processing load resulting from BGP updates are the BGP decision |
| 74 |
process and adding and removing forwarding entries. |
| 75 |
|
| 76 |
Consider the following example. A widely deployed BGP implementation |
| 77 |
may tend to fail due to high routing update volume. For example, it |
| 78 |
may be unable to maintain it's BGP or IGP sessions if sufficiently |
| 79 |
loaded. The failure of one router can further contribute to the load |
| 80 |
on other routers. This additional load may cause failures in other |
| 81 |
instances of the same implementation or other implementations with a |
| 82 |
similar weakness. In the worst case, a stable oscillation could |
| 83 |
result. Such worse cases have already been observed in practice. |
| 84 |
|
| 85 |
A BGP implementation must be prepared for a large volume of routing |
| 86 |
traffic. A BGP implementation cannot rely upon the sender to |
| 87 |
sufficiently shield it from route instabilities. The guidelines here |
| 88 |
are designed to prevent sustained oscillations, but do not eliminate |
| 89 |
the need for robust and efficient implementations. The mechanisms |
| 90 |
described here allow routing instability to be contained at an AS |
| 91 |
border router bordering the instability. |
| 92 |
|
| 93 |
Even where BGP implementations are highly robust, the performance of |
| 94 |
the routing process is limited. Limiting the propagation of |
| 95 |
unnecessary change then becomes an issue of maintaining reasonable |
| 96 |
route change convergence time as a routing topology grows. |
| 97 |
|
| 98 |
<span class="h2"><a class="selflink" id="section-2" href="#section-2">2</a> Methods of Limiting Route Advertisement</span> |
| 99 |
|
| 100 |
Two methods of controlling the frequency of route advertisement are |
| 101 |
described here. The first involves fixed timers. The fixed timer |
| 102 |
technique has no space overhead per route but has the disadvantage of |
| 103 |
slowing route convergence for the normal case where a route does not |
| 104 |
have a history of instability. The second method overcomes this |
| 105 |
|
| 106 |
|
| 107 |
|
| 108 |
<span class="grey">Villamizar, et. al. Standards Track [Page 2]</span></pre> |
| 109 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-3" ></span> |
| 110 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 111 |
|
| 112 |
|
| 113 |
limitation at the expense of maintaining some additional space |
| 114 |
overhead. The additional overhead includes a small amount of state |
| 115 |
per route and a very small processing overhead. |
| 116 |
|
| 117 |
It is possible and desirable to combine both techniques. In |
| 118 |
practice, fixed timers have been set to very short time intervals and |
| 119 |
have proven useful to pack routes into a smaller number of updates |
| 120 |
when routes arrive in separate updates. The BGP protocol refers to |
| 121 |
this as packing Network Layer Reachability Information (NLRI) [<a href="#ref-5" title=""A border gateway protocol 4 (BGP-4)"">5</a>]. |
| 122 |
|
| 123 |
Seldom are fixed timers set to the tens of minutes to hours that |
| 124 |
would be necessary to actually damp route flap. To do so would |
| 125 |
produce the undesirable effect of severely limiting routing |
| 126 |
convergence. |
| 127 |
|
| 128 |
<span class="h3"><a class="selflink" id="section-2.1" href="#section-2.1">2.1</a> Existing Fixed Timer Recommendations</span> |
| 129 |
|
| 130 |
BGP-3 does not make specific recommendations in this area [<a href="#ref-1" title=""Application of the border gateway protocol in the internet"">1</a>]. The |
| 131 |
short section entitled "Frequency of Route Selection" simply |
| 132 |
recommends that something be done and makes broad statements |
| 133 |
regarding certain properties that are desirable or undesirable. |
| 134 |
|
| 135 |
BGP4 retains the "Frequency of Route Advertisement" section and adds |
| 136 |
a "Frequency of Route Origination" section. BGP-4 describes a method |
| 137 |
of limiting route advertisement involving a fixed (configurable) |
| 138 |
MinRouteAdvertisementInterval timer and fixed |
| 139 |
MinASOriginationInterval timer [<a href="#ref-5" title=""A border gateway protocol 4 (BGP-4)"">5</a>]. The recommended timer values of |
| 140 |
MinRouteAdvertisementInterval is 30 seconds and |
| 141 |
MinASOriginationInterval is 15 seconds. |
| 142 |
|
| 143 |
<span class="h3"><a class="selflink" id="section-2.2" href="#section-2.2">2.2</a> Desirable Properties of Damping Algorithms</span> |
| 144 |
|
| 145 |
Before describing damping algorithms the objectives need to be |
| 146 |
clearly defined. Some key properties are examined to clarify the |
| 147 |
design rationale. |
| 148 |
|
| 149 |
The overall objective is to reduce the route update load without |
| 150 |
limiting convergence time for well behaved routes. To accomplish |
| 151 |
this, criteria must be defined for well behaved and poorly behaved |
| 152 |
routes. An algorithm must be defined which allows poorly behaved |
| 153 |
routes to be identified. Ideally, this measure would be a prediction |
| 154 |
of the future stability of a route. |
| 155 |
|
| 156 |
Any delay in propagation of well behaved routes should be minimal. |
| 157 |
Some delay is tolerable to support better packing of updates. Delay |
| 158 |
of poorly behave routes should, if possible, be proportional to a |
| 159 |
measure of the expected future instability of the route. Delay in |
| 160 |
propagating an unstable route should cause the unstable route to be |
| 161 |
|
| 162 |
|
| 163 |
|
| 164 |
<span class="grey">Villamizar, et. al. Standards Track [Page 3]</span></pre> |
| 165 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-4" ></span> |
| 166 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 167 |
|
| 168 |
|
| 169 |
suppressed until there is some degree of confidence that the route |
| 170 |
has stabilized. |
| 171 |
|
| 172 |
If a large number of route changes are received in separate updates |
| 173 |
over some very short period of time and these updates have the |
| 174 |
potential to be combined into a single update then these should be |
| 175 |
packed as efficiently as possible before propagating further. Some |
| 176 |
small delay in propagating well behaved routes is tolerable and is |
| 177 |
necessary to allow better packing of updates. |
| 178 |
|
| 179 |
Where routes are unstable, use and announcement of the routes should |
| 180 |
be suppressed rather than suppressing their removal. Where one route |
| 181 |
to a destination is stable, and another route to the same destination |
| 182 |
is somewhat unstable, if possible, the unstable route should be |
| 183 |
suppressed more aggressively than if there were no alternate path. |
| 184 |
|
| 185 |
Routing consistency within an AS is very important. Only very |
| 186 |
minimal delay of internal BGP (IBGP) should be done. Routing |
| 187 |
consistency across AS boundaries is also very important. It is |
| 188 |
highly undesirable to advertise a route that is different from the |
| 189 |
route that is being used, except for a very minimal time. It is more |
| 190 |
desirable to suppress the acceptance of a route (and therefore the |
| 191 |
use of that route in the IGP) rather than suppress only the |
| 192 |
redistribution. |
| 193 |
|
| 194 |
It is clearly not possible to accurately predict the future stability |
| 195 |
of a route. The recent history of stability is generally regarded as |
| 196 |
a good basis for estimating the likelihood of future stability. The |
| 197 |
criteria that is used to distinguish well behaved from poorly behaved |
| 198 |
routes is therefore based on the recent history of stability of the |
| 199 |
route. There is no simple quantitative expression of recent |
| 200 |
stability so a figure of merit must be defined. Some desirable |
| 201 |
characteristics of this figure of merit would be that the farther in |
| 202 |
the past that instability occurred, the less it's affect on the |
| 203 |
figure of merit and that the instability measure would be cumulative |
| 204 |
rather than reflecting only the most recent event. |
| 205 |
|
| 206 |
The algorithms should behave such that for routes which have a |
| 207 |
history of stability but make a few transitions, those transitions |
| 208 |
should be made quickly. If transitions continue, advertisement of |
| 209 |
the route should be suppressed. There should be some memory of prior |
| 210 |
instability. The degree to which prior instability is considered |
| 211 |
should be gradually reduced as long as the route remains announced |
| 212 |
and stable. |
| 213 |
|
| 214 |
|
| 215 |
|
| 216 |
|
| 217 |
|
| 218 |
|
| 219 |
|
| 220 |
<span class="grey">Villamizar, et. al. Standards Track [Page 4]</span></pre> |
| 221 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-5" ></span> |
| 222 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 223 |
|
| 224 |
|
| 225 |
<span class="h3"><a class="selflink" id="section-2.3" href="#section-2.3">2.3</a> Design Choices</span> |
| 226 |
|
| 227 |
After routes have been accepted their readvertisement will be briefly |
| 228 |
suppressed to improve packing of updates. There may be a lengthy |
| 229 |
suppression of the acceptance of an external route. How long a route |
| 230 |
will be suppressed is based on a figure of merit that is expected to |
| 231 |
be correlated to the probability of future instability of a route. |
| 232 |
Routes with high figure of merit values will be suppressed. An |
| 233 |
exponential decay algorithm was chosen as the basis for reducing the |
| 234 |
figure of merit over time. These choices should be viewed as |
| 235 |
suggestions for implementation. |
| 236 |
|
| 237 |
An exponential decay function has the property that previous |
| 238 |
instability can be remembered for a fairly long time. The rate at |
| 239 |
which the instability figure of merit decays slows as time goes on. |
| 240 |
Exponential decay has the following property. |
| 241 |
|
| 242 |
f(f(figure-of-merit, t1), t2) = f(figure-of-merit, t1+t2) |
| 243 |
|
| 244 |
This property allows the decay for a long period to be computed in a |
| 245 |
single operation regardless of the current value (figure-of-merit). |
| 246 |
As a performance optimization, the decay can be applied in fixed time |
| 247 |
increments. Given a desired decay half life, the decay for a single |
| 248 |
time increment can be computed ahead of time. The decay for multiple |
| 249 |
time increments is expressed below. |
| 250 |
|
| 251 |
f(figure-of-merit, n*t0) = f(figure-of-merit, t0)**n = K**n |
| 252 |
|
| 253 |
The values of K ** n can be precomputed for a reasonable number of |
| 254 |
"n" and stored in an array. The value of "K" is always less than |
| 255 |
one. The array size can be bounded since the value quickly |
| 256 |
approaches zero. This makes the decay easy to compute using an array |
| 257 |
bound check, an array lookup and a single multiply regardless as to |
| 258 |
how much time has elapsed. |
| 259 |
|
| 260 |
<span class="h2"><a class="selflink" id="section-3" href="#section-3">3</a> Limiting Route Advertisements using Fixed Timers</span> |
| 261 |
|
| 262 |
This method of limiting route advertisements involves the use of |
| 263 |
fixed timers applied to the process of sending routes. It's primary |
| 264 |
purpose is to improve the packing of routes in BGP update messages. |
| 265 |
The delay in advertising a stable route should be bounded and |
| 266 |
minimal. The delay in advertising an unreachable need not be zero, |
| 267 |
but should also be bounded and should probably have a separate bound |
| 268 |
set less than or equal to the bound for a reachable advertisement. |
| 269 |
|
| 270 |
The BGP protocol defines the use of a Routing Information Base (RIB). |
| 271 |
Routes that need to be readvertised can be marked in the RIB or an |
| 272 |
external set of structures maintained, which references the RIB. |
| 273 |
|
| 274 |
|
| 275 |
|
| 276 |
<span class="grey">Villamizar, et. al. Standards Track [Page 5]</span></pre> |
| 277 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-6" ></span> |
| 278 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 279 |
|
| 280 |
|
| 281 |
Periodically, a subset of the marked routes can be flushed. This is |
| 282 |
fairly straightforward and accomplishes the objectives. Computation |
| 283 |
for too simple an implementation may be order N squared. To avoid N |
| 284 |
squared performance, some form of data structure is needed to group |
| 285 |
routes with common attributes. |
| 286 |
|
| 287 |
An implementation should pack updates efficiently, provide a minimum |
| 288 |
readvertisement delay, provide a bounds on the maximum |
| 289 |
readvertisement delay that would be experienced solely as a result of |
| 290 |
the algorithm used to provide a minimum delay, and must be |
| 291 |
computationally efficient in the presence of a very large number of |
| 292 |
candidates for readvertisement. |
| 293 |
|
| 294 |
<span class="h2"><a class="selflink" id="section-4" href="#section-4">4</a> Stability Sensitive Suppression of Route Advertisement</span> |
| 295 |
|
| 296 |
This method of limiting route advertisements uses a measure of route |
| 297 |
stability applied on a per route basis. This technique is applied |
| 298 |
when receiving updates from external peers only (EBGP). Applying this |
| 299 |
technique to IBGP learned routes or to advertisement to IBGP or EBGP |
| 300 |
peers after making a route selection can result in routing loops. |
| 301 |
|
| 302 |
A figure of merit based on a measure of instability is maintained on |
| 303 |
a per route basis. This figure of merit is used in the decision to |
| 304 |
suppress the use of the route. Routes with high figure of merit are |
| 305 |
suppressed. Each time a route is withdrawn, the figure of merit is |
| 306 |
incremented. While the route is not changing the figure of merit |
| 307 |
value is decayed exponentially with separate decay rates depending on |
| 308 |
whether the route is stable and reachable or has been stable and |
| 309 |
unreachable. The decay rate may be slower when the route is |
| 310 |
unreachable, or the stability figure of merit could remain fixed (not |
| 311 |
decay at all) while the route remains unreachable. Whether to decay |
| 312 |
unreachable routes at the same rate, a slower rate, or not at all is |
| 313 |
an implementation choice. Decaying at a slower rate is recommended. |
| 314 |
|
| 315 |
A very efficient implementation is suggested in the following |
| 316 |
sections. The implementation only requires computation for the |
| 317 |
routes contained in an update, when an update is received or |
| 318 |
withdrawn (as opposed to the simplistic approach of periodically |
| 319 |
decaying each route). The suggested implementation involves only a |
| 320 |
small number of simple operations, and can be implemented using |
| 321 |
scaled integers. |
| 322 |
|
| 323 |
The behavior of unstable routes is fairly predictable. Severely |
| 324 |
flapping routes will often be advertised and withdrawn at regular |
| 325 |
time intervals corresponding to the timers of a particular protocol |
| 326 |
(the IGP or exterior protocol in use where the problem exists). |
| 327 |
Marginal circuits or mild congestion can result in a long term |
| 328 |
pattern of occasional brief route withdrawal or occasional brief |
| 329 |
|
| 330 |
|
| 331 |
|
| 332 |
<span class="grey">Villamizar, et. al. Standards Track [Page 6]</span></pre> |
| 333 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-7" ></span> |
| 334 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 335 |
|
| 336 |
|
| 337 |
connectivity. |
| 338 |
|
| 339 |
<span class="h3"><a class="selflink" id="section-4.1" href="#section-4.1">4.1</a> Single vs. </span>Multiple Configuration Parameter Sets |
| 340 |
|
| 341 |
The behavior of the algorithm is modified by a number of configurable |
| 342 |
parameters. It is possible to configure separate sets of parameters |
| 343 |
designed to handle short term severe route flap and chronic milder |
| 344 |
route flap (a pattern of occasional drops over a long time period). |
| 345 |
The former would require a fast decay and low threshold (allowing a |
| 346 |
small number of consecutive flaps to cause a route to be suppressed, |
| 347 |
but allowing it to be reused after a relatively short period of |
| 348 |
stability). The latter would require a very slow decay and a higher |
| 349 |
threshold and might be appropriate for routes for which there was an |
| 350 |
alternate path of similar bandwidth. |
| 351 |
|
| 352 |
It may also be desirable to configure different thresholds for routes |
| 353 |
with roughly equivalent alternate paths than for routes where the |
| 354 |
alternate paths have a lower bandwidth or tend to be congested. This |
| 355 |
can be solved by associating a different set of parameters with |
| 356 |
different ranges of preference values. Parameter selection could be |
| 357 |
based on BGP LOCAL_PREF. |
| 358 |
|
| 359 |
Parameter selection could also be based on whether an alternate route |
| 360 |
was known. A route would be considered if, for any applicable |
| 361 |
parameter set, an alternate route with the specified preference value |
| 362 |
existed and the figure of merit associated with the parameter set did |
| 363 |
not indicate a need to suppress the route. A less aggressive |
| 364 |
suppression would be applied to the case where no alternate route at |
| 365 |
all existed. In the simplest case, a more aggressive suppression |
| 366 |
would be applied if any alternate route existed. Only the highest |
| 367 |
preference (most preferred) value needs to be specified, since the |
| 368 |
ranges may overlap. |
| 369 |
|
| 370 |
It might also be desirable to configure a different set of thresholds |
| 371 |
for routes which rely on switched services and may disconnect at |
| 372 |
times to reduce connect charges. Such routes might be expected to |
| 373 |
change state somewhat more often, but should be suppressed if |
| 374 |
continuous state changes indicate instability. |
| 375 |
|
| 376 |
While not essential, it might be desirable to be able to configure |
| 377 |
multiple sets of configuration parameters per route. It may also be |
| 378 |
desirable to be able to configure sets of parameters that only |
| 379 |
correspond to a set of routes (identified by AS path, peer router, |
| 380 |
specific destinations or other means). Experience may dictate how |
| 381 |
much flexibility is needed and how to best to set the parameters. |
| 382 |
Whether to allow different damping parameter sets for different |
| 383 |
routes, and whether to allow multiple figures of merit per route is |
| 384 |
an implementation choice. |
| 385 |
|
| 386 |
|
| 387 |
|
| 388 |
<span class="grey">Villamizar, et. al. Standards Track [Page 7]</span></pre> |
| 389 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-8" ></span> |
| 390 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 391 |
|
| 392 |
|
| 393 |
Parameter selection can also be based on prefix length. The |
| 394 |
rationale is that longer prefixes tend to reach less end systems and |
| 395 |
are less important and these less important prefixes can be damped |
| 396 |
more aggressively. This technique is in fairly widespread use. |
| 397 |
Small sites or those with dense address allocation who are multihomed |
| 398 |
are often reachable by long prefixes which are not easily aggregated. |
| 399 |
These sites tend to dispute the choice of prefix length for parameter |
| 400 |
selection. Advocates of the technique point out that it encourages |
| 401 |
better aggregation. |
| 402 |
|
| 403 |
<span class="h3"><a class="selflink" id="section-4.2" href="#section-4.2">4.2</a> Configuration Parameters</span> |
| 404 |
|
| 405 |
At configuration time, a number of parameters may be specified by the |
| 406 |
user. The configuration parameters are expressed in units meaningful |
| 407 |
to the user. These differ from the parameters used at run time which |
| 408 |
are in unit convenient for computation. The run time parameters are |
| 409 |
derived from the configuration parameters. Suggested configuration |
| 410 |
parameters are listed below. |
| 411 |
|
| 412 |
cutoff threshold (cut) |
| 413 |
|
| 414 |
This value is expressed as a number of route withdrawals. It is |
| 415 |
the value above which a route advertisement will be suppressed. |
| 416 |
|
| 417 |
reuse threshold (reuse) |
| 418 |
|
| 419 |
This value is expressed as a number of route withdrawals. It is |
| 420 |
the value below which a suppressed route will now be used again. |
| 421 |
|
| 422 |
maximum hold down time (T-hold) |
| 423 |
|
| 424 |
This value is the maximum time a route can be suppressed no |
| 425 |
matter how unstable it has been prior to this period of |
| 426 |
stability. |
| 427 |
|
| 428 |
decay half life while reachable (decay-ok) |
| 429 |
|
| 430 |
This value is the time duration in minutes or seconds during |
| 431 |
which the accumulated stability figure of merit will be reduced |
| 432 |
by half if the route if considered reachable (whether suppressed |
| 433 |
or not). |
| 434 |
|
| 435 |
decay half life while unreachable (decay-ng) |
| 436 |
|
| 437 |
This value is the time duration in minutes or seconds during |
| 438 |
which the accumulated stability figure of merit will be reduced |
| 439 |
by half if the route if considered unreachable. If not |
| 440 |
specified or set to zero, no decay will occur while a route |
| 441 |
|
| 442 |
|
| 443 |
|
| 444 |
<span class="grey">Villamizar, et. al. Standards Track [Page 8]</span></pre> |
| 445 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-9" ></span> |
| 446 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 447 |
|
| 448 |
|
| 449 |
remains unreachable. |
| 450 |
|
| 451 |
decay memory limit (Tmax-ok or Tmax-ng) |
| 452 |
|
| 453 |
This is the maximum time that any memory of previous instability |
| 454 |
will be retained given that the route's state remains unchanged, |
| 455 |
whether reachable or unreachable. This parameter is generally |
| 456 |
used to determine array sizes. |
| 457 |
|
| 458 |
There may be multiple sets of the parameters above as described in |
| 459 |
<a href="#section-4.1">Section 4.1</a>. The configuration parameters listed below would be |
| 460 |
applied system wide. These include the time granularity of all |
| 461 |
computations, and the parameters used to control reevaluation of |
| 462 |
routes that have previously been suppressed. |
| 463 |
|
| 464 |
time granularity (delta-t) |
| 465 |
|
| 466 |
This is the time granularity in seconds used to perform all |
| 467 |
decay computations. |
| 468 |
|
| 469 |
reuse list time granularity (delta-reuse) |
| 470 |
|
| 471 |
This is the time interval between evaluations of the reuse |
| 472 |
lists. Each reuse lists corresponds to an additional time |
| 473 |
increment. |
| 474 |
|
| 475 |
reuse list memory reuse-list-max |
| 476 |
|
| 477 |
This is the time value corresponding to the last reuse list. |
| 478 |
This may be the maximum value of T-hold for all parameter sets |
| 479 |
of may be configured. |
| 480 |
|
| 481 |
number of reuse lists (reuse-list-size) |
| 482 |
|
| 483 |
This is the number of reuse lists. It may be determined from |
| 484 |
reuse-list-max or set explicitly. |
| 485 |
|
| 486 |
A recommended optimization is described in <a href="#section-4.8.6">Section 4.8.6</a> that |
| 487 |
involves an array referred to as the "reuse index array". A reuse |
| 488 |
index array is needed for each decay rate in use. The reuse index |
| 489 |
array is used to estimate which reuse list to place a route when it |
| 490 |
is suppressed. Proper placement avoids the need to periodically |
| 491 |
evaluate decay to determine if a route can be reused or when storage |
| 492 |
can be recovered. Using the reuse index array avoids the need to |
| 493 |
compute a logarithm to determine placement. One additional system |
| 494 |
wide parameter can be introduced. |
| 495 |
|
| 496 |
|
| 497 |
|
| 498 |
|
| 499 |
|
| 500 |
<span class="grey">Villamizar, et. al. Standards Track [Page 9]</span></pre> |
| 501 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-10" ></span> |
| 502 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 503 |
|
| 504 |
|
| 505 |
reuse index array size (reuse-index-array-size) |
| 506 |
|
| 507 |
This is the size of reuse index arrays. This size determines |
| 508 |
the accuracy with which suppressed routes can be placed within |
| 509 |
the set of reuse lists when suppressed for a long time. |
| 510 |
|
| 511 |
<span class="h3"><a class="selflink" id="section-4.3" href="#section-4.3">4.3</a> Guidelines for Setting Parameters</span> |
| 512 |
|
| 513 |
The decay half life should be set to a time considerably longer than |
| 514 |
the period of the route flap it is intended to address. For example, |
| 515 |
if the decay is set to ten minutes and a route is withdrawn and |
| 516 |
readvertised exactly every ten minutes, the route would continue to |
| 517 |
flap if the cutoff was set to a value of 2 or above. |
| 518 |
|
| 519 |
The stability figure of merit itself is an accumulated time decayed |
| 520 |
total. This must be kept in mind in setting the decay time, cutoff |
| 521 |
values and reuse values. The figure of merit is increased each time |
| 522 |
a route transitions from reachable to unreachable. The figure of |
| 523 |
merit is decayed at a rate proportional to its current value. |
| 524 |
Increasing the rate of route flap therefore increments the figure of |
| 525 |
merit more often and reaches a given threshhold in a shorter amount |
| 526 |
of time. When the response to a constant rate route flap is plotted |
| 527 |
this looks like a sawtooth with an abrupt rising edge and a decaying |
| 528 |
falling edge. Since the absolute decay amount is proportional to the |
| 529 |
figure of merit, at a continuous constant flap rate the baseline of |
| 530 |
the sawtooth will tend to stop rising and converge if not clipped by |
| 531 |
a ceiling value. |
| 532 |
|
| 533 |
If clipped by a ceiling value, the sawtooth baseline will simply |
| 534 |
reach the ceiling faster at a higher rate of route flap. For |
| 535 |
example, if flapping at four times the decay rate the following |
| 536 |
progression occurs. When the route becomes unreachable the first |
| 537 |
time the value becomes 1. When the next flap occurs, one is added to |
| 538 |
the previous value, which has been decreased by the fourth root of 2 |
| 539 |
(the amount of decay that would occur in 1/4 of the half life time if |
| 540 |
decay is exponential). The sequence is 1, 1.84, 2.55, 3.14, 3.64, |
| 541 |
4.06, 4.42, 4.71, 4.96, 5.17, ..., converging at about 6.285. If a |
| 542 |
route flaps at four times the decay rate, it will reach 3 in 4 |
| 543 |
cycles, 4 in 6 cycles, 5 in 10 cycles, and will converge at about |
| 544 |
6.3. At twice the decay time, it will reach 3 in 7 cycles, and |
| 545 |
converge at a value of less than 3.5. |
| 546 |
|
| 547 |
Figure 1 shows the stability figure of merit for route flap at a |
| 548 |
constant rate. The time axis is labeled in multiples of the decay |
| 549 |
half life. The plots represent route flap with a period of 1/2, 1/3, |
| 550 |
1/4, and 1/8 times the decay half life. A ceiling of 4.5 was set, |
| 551 |
which can be seen to affect three of the plots, effectively limiting |
| 552 |
the time it takes to readvertise the route regardless of the prior |
| 553 |
|
| 554 |
|
| 555 |
|
| 556 |
<span class="grey">Villamizar, et. al. Standards Track [Page 10]</span></pre> |
| 557 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-11" ></span> |
| 558 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 559 |
|
| 560 |
|
| 561 |
history. With cutoff and reuse thresholds of 1.5 and 0.75, routes |
| 562 |
would be suppressed after being declared unreachable 2-3 times and be |
| 563 |
used again after approximately 2 decay half life periods of |
| 564 |
stability. |
| 565 |
|
| 566 |
This function can be expressed formally. Reachability of a route can |
| 567 |
be represented by a variable "R" with possible values of 0 and 1 |
| 568 |
representing unreachable and reachable. At a discrete time R can |
| 569 |
only have one value. The figure of merit is increased by 1 at each |
| 570 |
transition from R=1 to R=0 and clipped to a ceiling value. The decay |
| 571 |
in figure of merit can then be expressed over a set of discrete times |
| 572 |
as follows. |
| 573 |
|
| 574 |
figure-of-merit(t) = K * figure-of-merit(t - delta-t) |
| 575 |
K = K1 for R=0 K=K2 for R=1 |
| 576 |
|
| 577 |
The four plots are presented vertically. Due to space limitations, |
| 578 |
only a limited set of points along the time axis are shown. The |
| 579 |
value of the figure of merit is given. Along side each value is a |
| 580 |
very low resolution strip chart made up of ASCII dots. This is just |
| 581 |
intended to give a rough feel for the rise and fall of the values. |
| 582 |
The strip charts are not displayed on an overlapping set of axes |
| 583 |
because the sawtooth waveforms cross each other quite frequently. At |
| 584 |
the very low resolution of these plots, the rise and fall of the |
| 585 |
baseline is evident, but the sawtooth nature is only observed in the |
| 586 |
printed value. |
| 587 |
|
| 588 |
From the maximum hold time value (T-hold), a ratio of the reuse value |
| 589 |
to a ceiling can be determined. An integer value for the ceiling can |
| 590 |
then be chosen such that overflow will not be a problem and all other |
| 591 |
values can be scaled accordingly. If both cutoffs are specified or |
| 592 |
if multiple parameter sets are used the highest ceiling will be used. |
| 593 |
|
| 594 |
|
| 595 |
|
| 596 |
|
| 597 |
|
| 598 |
|
| 599 |
|
| 600 |
|
| 601 |
|
| 602 |
|
| 603 |
|
| 604 |
|
| 605 |
|
| 606 |
|
| 607 |
|
| 608 |
|
| 609 |
|
| 610 |
|
| 611 |
|
| 612 |
<span class="grey">Villamizar, et. al. Standards Track [Page 11]</span></pre> |
| 613 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-12" ></span> |
| 614 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 615 |
|
| 616 |
|
| 617 |
time figure-of-merit as a function of time (in minutes) |
| 618 |
|
| 619 |
0.00 0.000 . 0.000 . 0.000 . 0.000 . |
| 620 |
0.08 0.000 . 0.000 . 0.000 . 0.000 . |
| 621 |
0.16 0.000 . 0.000 . 0.000 . 0.973 . |
| 622 |
0.24 0.000 . 0.000 . 0.000 . 0.920 . |
| 623 |
0.32 0.000 . 0.000 . 0.946 . 1.817 . |
| 624 |
0.40 0.000 . 0.953 . 0.895 . 2.698 . |
| 625 |
0.48 0.000 . 0.901 . 0.847 . 2.552 . |
| 626 |
0.56 0.953 . 0.853 . 1.754 . 3.367 . |
| 627 |
0.64 0.901 . 0.807 . 1.659 . 4.172 . |
| 628 |
0.72 0.853 . 1.722 . 1.570 . 3.947 . |
| 629 |
0.80 0.807 . 1.629 . 2.444 . 4.317 . |
| 630 |
0.88 0.763 . 1.542 . 2.312 . 4.469 . |
| 631 |
0.96 0.722 . 1.458 . 2.188 . 4.228 . |
| 632 |
1.04 1.649 . 2.346 . 3.036 . 4.347 . |
| 633 |
1.12 1.560 . 2.219 . 2.872 . 4.112 . |
| 634 |
1.20 1.476 . 2.099 . 2.717 . 4.257 . |
| 635 |
1.28 1.396 . 1.986 . 3.543 . 4.377 . |
| 636 |
1.36 1.321 . 2.858 . 3.352 . 4.141 . |
| 637 |
1.44 1.250 . 2.704 . 3.171 . 4.287 . |
| 638 |
1.52 2.162 . 2.558 . 3.979 . 4.407 . |
| 639 |
1.60 2.045 . 2.420 . 3.765 . 4.170 . |
| 640 |
1.68 1.935 . 3.276 . 3.562 . 4.317 . |
| 641 |
1.76 1.830 . 3.099 . 4.356 . 4.438 . |
| 642 |
1.84 1.732 . 2.932 . 4.121 . 4.199 . |
| 643 |
1.92 1.638 . 2.774 . 3.899 . 3.972 . |
| 644 |
2.00 1.550 . 2.624 . 3.688 . 3.758 . |
| 645 |
2.08 1.466 . 2.483 . 3.489 . 3.555 . |
| 646 |
2.16 1.387 . 2.349 . 3.301 . 3.363 . |
| 647 |
2.24 1.312 . 2.222 . 3.123 . 3.182 . |
| 648 |
2.32 1.242 . 2.102 . 2.955 . 3.010 . |
| 649 |
2.40 1.175 . 1.989 . 2.795 . 2.848 . |
| 650 |
2.48 1.111 . 1.882 . 2.644 . 2.694 . |
| 651 |
2.56 1.051 . 1.780 . 2.502 . 2.549 . |
| 652 |
2.64 0.995 . 1.684 . 2.367 . 2.411 . |
| 653 |
2.72 0.941 . 1.593 . 2.239 . 2.281 . |
| 654 |
2.80 0.890 . 1.507 . 2.118 . 2.158 . |
| 655 |
2.88 0.842 . 1.426 . 2.004 . 2.042 . |
| 656 |
2.96 0.797 . 1.349 . 1.896 . 1.932 . |
| 657 |
3.04 0.754 . 1.276 . 1.794 . 1.828 . |
| 658 |
3.12 0.713 . 1.207 . 1.697 . 1.729 . |
| 659 |
3.20 0.675 . 1.142 . 1.605 . 1.636 . |
| 660 |
3.28 0.638 . 1.081 . 1.519 . 1.547 . |
| 661 |
3.36 0.604 . 1.022 . 1.437 . 1.464 . |
| 662 |
3.44 0.571 . 0.967 . 1.359 . 1.385 . |
| 663 |
|
| 664 |
Figure 1: Instability figure of merit for flap at a constant rate |
| 665 |
|
| 666 |
|
| 667 |
|
| 668 |
<span class="grey">Villamizar, et. al. Standards Track [Page 12]</span></pre> |
| 669 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-13" ></span> |
| 670 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 671 |
|
| 672 |
|
| 673 |
time figure-of-merit as a function of time (in minutes) |
| 674 |
|
| 675 |
0.00 0.000 . 0.000 . 0.000 . |
| 676 |
0.20 0.000 . 0.000 . 0.000 . |
| 677 |
0.40 0.000 . 0.000 . 0.000 . |
| 678 |
0.60 0.000 . 0.000 . 0.000 . |
| 679 |
0.80 0.000 . 0.000 . 0.000 . |
| 680 |
1.00 0.999 . 0.999 . 0.999 . |
| 681 |
1.20 0.971 . 0.971 . 0.929 . |
| 682 |
1.40 0.945 . 0.945 . 0.809 . |
| 683 |
1.60 0.919 . 0.865 . 0.704 . |
| 684 |
1.80 0.894 . 0.753 . 0.613 . |
| 685 |
2.00 1.812 . 1.657 . 1.535 . |
| 686 |
2.20 1.762 . 1.612 . 1.428 . |
| 687 |
2.40 1.714 . 1.568 . 1.244 . |
| 688 |
2.60 1.667 . 1.443 . 1.083 . |
| 689 |
2.80 1.622 . 1.256 . 0.942 . |
| 690 |
3.00 1.468 . 1.094 . 0.820 . |
| 691 |
3.20 2.400 . 2.036 . 1.694 . |
| 692 |
3.40 2.335 . 1.981 . 1.475 . |
| 693 |
3.60 2.271 . 1.823 . 1.284 . |
| 694 |
3.80 2.209 . 1.587 . 1.118 . |
| 695 |
4.00 1.999 . 1.381 . 0.973 . |
| 696 |
4.20 2.625 . 2.084 . 1.727 . |
| 697 |
4.40 2.285 . 1.815 . 1.503 . |
| 698 |
4.60 1.990 . 1.580 . 1.309 . |
| 699 |
4.80 1.732 . 1.375 . 1.139 . |
| 700 |
5.00 1.508 . 1.197 . 0.992 . |
| 701 |
5.20 1.313 . 1.042 . 0.864 . |
| 702 |
5.40 1.143 . 0.907 . 0.752 . |
| 703 |
5.60 0.995 . 0.790 . 0.654 . |
| 704 |
5.80 0.866 . 0.688 . 0.570 . |
| 705 |
6.00 0.754 . 0.599 . 0.496 . |
| 706 |
6.20 0.656 . 0.521 . 0.432 . |
| 707 |
6.40 0.571 . 0.454 . 0.376 . |
| 708 |
6.60 0.497 . 0.395 . 0.327 . |
| 709 |
6.80 0.433 . 0.344 . 0.285 . |
| 710 |
7.00 0.377 . 0.299 . 0.248 . |
| 711 |
7.20 0.328 . 0.261 . 0.216 . |
| 712 |
7.40 0.286 . 0.227 . 0.188 . |
| 713 |
7.60 0.249 . 0.197 . 0.164 . |
| 714 |
7.80 0.216 . 0.172 . 0.142 . |
| 715 |
8.00 0.188 . 0.150 . 0.124 . |
| 716 |
|
| 717 |
Figure 2: Separate decay constants when unreachable |
| 718 |
|
| 719 |
|
| 720 |
|
| 721 |
|
| 722 |
|
| 723 |
|
| 724 |
<span class="grey">Villamizar, et. al. Standards Track [Page 13]</span></pre> |
| 725 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-14" ></span> |
| 726 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 727 |
|
| 728 |
|
| 729 |
Figure 2 shows the effect of configuring separate decay rates to be |
| 730 |
used when the route is reachable or unreachable. The decay rate is 5 |
| 731 |
times slower when the route is unreachable. In the three case shown, |
| 732 |
the period of the route flap is equal to the decay half life but the |
| 733 |
route is reachable 1/8 of the time in one, reachable 1/2 the time in |
| 734 |
one, and reachable 7/8 of the time in the other. In the last case |
| 735 |
the route is not suppressed until after the third unreachable (when |
| 736 |
it is above the top threshold after becoming reachable again). |
| 737 |
|
| 738 |
The main point of Figure 2 is to show the effect of changing the duty |
| 739 |
cycle of the square wave in the variable "R" for a fixed frequency of |
| 740 |
the square wave. If the decay constants are chosen such that decay |
| 741 |
is slower when R=0 (the route is unreachable), then the figure of |
| 742 |
merit rises more slowly (more accurately, the baseline of the |
| 743 |
sawtooth waveform rises more slowly) if the route is reachable a |
| 744 |
larger percentage of the time. The effect when the route becomes |
| 745 |
persistently reachable again can be fairly negligible if the sawtooth |
| 746 |
is clipped by a ceiling value, but is more significant if a slow |
| 747 |
route flap rate or short interval of route flapping is such that the |
| 748 |
sawtooth does not reach the ceiling value. In Figure 2 the interval |
| 749 |
in which the routes are unstable is short enough that the ceiling |
| 750 |
value is not reached, therefore, the routes that are reachable for a |
| 751 |
greater percentage of the route flap cycle are reused (placed in the |
| 752 |
RIB and advertised to peers) sooner than others after the route |
| 753 |
becomes stable again ("R" becomes 1, indicating the announced state |
| 754 |
goes to reachable and remains there). |
| 755 |
|
| 756 |
In both Figure 1 and Figure 2, routes would be suppressed. Routes |
| 757 |
flapping at the decay half life or less would be withdrawn two or |
| 758 |
three times and then remain withdrawn until they had remained stably |
| 759 |
announced and stable for on the order of 1 1/2 to 2 1/2 times the |
| 760 |
decay half life (given the ceiling in the example). |
| 761 |
|
| 762 |
The purpose of damping BGP route flap is to reduce the processor |
| 763 |
burden at the immediate router and the processor burden to downstream |
| 764 |
routers (BGP peer routers and peers of peers that will see the route |
| 765 |
announcements advertised by the immediate router). Computing a |
| 766 |
figure of merit at each discrete time interval using figure-of- |
| 767 |
merit(t) = K * figure-of-merit(t - delta-t) would be very inefficient |
| 768 |
and defeat the purpose. This problem is addressed by defering |
| 769 |
computation as long as possible and doing a single simple computation |
| 770 |
to compensate for the decay during the time that has elapsed since |
| 771 |
the figure of merit was last updated. The use of decay arrays |
| 772 |
provides the single simple calculation. The use of reuse lists |
| 773 |
(described later) provide a means to defer calculations. A route |
| 774 |
becomes usable if there was not further change for a period of time |
| 775 |
and the route is unreachable. The data structure storage is |
| 776 |
recovered if the route's state has not changed for a period of time |
| 777 |
|
| 778 |
|
| 779 |
|
| 780 |
<span class="grey">Villamizar, et. al. Standards Track [Page 14]</span></pre> |
| 781 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-15" ></span> |
| 782 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 783 |
|
| 784 |
|
| 785 |
and it has been unreachable. The reuse arrays provide a means to |
| 786 |
estimate how long a computation can be deferred if there is no |
| 787 |
further change. |
| 788 |
|
| 789 |
A larger time granularity will keep table storage down. The time |
| 790 |
granularity should be less than a minimal reasonable time between |
| 791 |
expected worse case route flaps. It might be reasonable to fix this |
| 792 |
parameter at compile time or set a default and strongly recommend |
| 793 |
that the user leave it alone. With an exponential decay, array size |
| 794 |
can be greatly reduced by setting a period of complete stability |
| 795 |
after which the decayed total will be considered zero rather than |
| 796 |
retaining a tiny quantity. Alternately, very long decays can be |
| 797 |
implemented by multiplying more than once if array bounds are |
| 798 |
exceeded. |
| 799 |
|
| 800 |
The reuse lists hold suppressed routes grouped according to how long |
| 801 |
it will be before the routes are eligible for reuse. Periodically |
| 802 |
each list will be advanced by one position and one list removed as |
| 803 |
described in <a href="#section-4.8.7">Section 4.8.7</a>. All of the suppressed routes in the |
| 804 |
removed list will be reevaluated and either used or placed in another |
| 805 |
list according to how much additional time must elapse before the |
| 806 |
route can be reused. The last list will always contain all the |
| 807 |
routes which will not be advertised for more time than is appropriate |
| 808 |
for the remaining list heads. When the last list advances to the |
| 809 |
front, some of the routes will not be ready to be used and will have |
| 810 |
to be requeued. The time interval for reconsidering suppressed |
| 811 |
routes and number of list heads should be configurable. Reasonable |
| 812 |
defaults might be 30 seconds and 64 list heads. A route suppressed |
| 813 |
for a long time would need to be reevaluated every 32 minutes. |
| 814 |
|
| 815 |
<span class="h3"><a class="selflink" id="section-4.4" href="#section-4.4">4.4</a> Run Time Data Structures</span> |
| 816 |
|
| 817 |
A fixed small amount of per system storage will be required. Where |
| 818 |
sets of multiple configuration parameters are used, storage will be |
| 819 |
required per set of parameters. A small amount of per route storage |
| 820 |
is required. A set of list heads is needed. These list heads are |
| 821 |
used to arrange suppressed routes according to the time remaining |
| 822 |
until they can be reused. |
| 823 |
|
| 824 |
A separate reuse list can be used to hold unreachable routes for the |
| 825 |
purpose of later recovering storage if they remain unreachable too |
| 826 |
long. This might be more accurately described as a recycling list. |
| 827 |
The advantage this would provide is making free data structures |
| 828 |
available as soon as possible. Alternately, the data structures can |
| 829 |
simply be placed on a queue and the storage recovered when the route |
| 830 |
hits the front of the queue and if storage is needed. The latter is |
| 831 |
less optimal but simple. |
| 832 |
|
| 833 |
|
| 834 |
|
| 835 |
|
| 836 |
<span class="grey">Villamizar, et. al. Standards Track [Page 15]</span></pre> |
| 837 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-16" ></span> |
| 838 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 839 |
|
| 840 |
|
| 841 |
If multiple sets of configuration parameters are allowed per route, |
| 842 |
there is a need for some means of associating more than one figure of |
| 843 |
merit and set of parameters with each route. Building a linked list |
| 844 |
of these objects seems like one of a number of reasonable |
| 845 |
implementations. Similarly, a means of associating a route to a |
| 846 |
reuse list is required. A small overhead will be required for the |
| 847 |
pointers needed to implement whatever data structure is chosen for |
| 848 |
the reuse lists. The suggested implementation uses a double linked |
| 849 |
lists and so requires two pointers per figure of merit. |
| 850 |
|
| 851 |
Each set of configuration parameters can reference decay arrays and |
| 852 |
reuse arrays. These arrays should be shared among multiple sets of |
| 853 |
parameters since their storage requirement is not negligible. There |
| 854 |
will be only one set of reuse list heads for the entire router. |
| 855 |
|
| 856 |
<span class="h4"><a class="selflink" id="section-4.4.1" href="#section-4.4.1">4.4.1</a> Data Structures for Configuration Parameter Sets</span> |
| 857 |
|
| 858 |
Based on the configuration parameters described in the previous |
| 859 |
section, the following values can be computed as scaled integers |
| 860 |
directly from the corresponding configuration parameters. |
| 861 |
|
| 862 |
o decay array scale factor (decay-array-scale-factor) |
| 863 |
|
| 864 |
o cutoff value (cut) |
| 865 |
|
| 866 |
o reuse value (reuse) |
| 867 |
|
| 868 |
o figure of merit ceiling (ceiling) |
| 869 |
|
| 870 |
Each configuration parameter set will reference one or two decay |
| 871 |
arrays and one or two reuse arrays. Only one array will be needed if |
| 872 |
the decay rate is the same while a route is unreachable as while it |
| 873 |
is reachable, or if the stability figure of merit does not decay |
| 874 |
while a route is unreachable. |
| 875 |
|
| 876 |
<span class="h4"><a class="selflink" id="section-4.4.2" href="#section-4.4.2">4.4.2</a> Data Structures per Decay Array and Reuse Index Array</span> |
| 877 |
|
| 878 |
The following are also computed from the configuration parameters |
| 879 |
though not as directly. The computation is described in <a href="#section-4.5">Section 4.5</a>. |
| 880 |
|
| 881 |
o decay rate per tick (decay-delta-t) |
| 882 |
|
| 883 |
o decay array size (decay-array-size) |
| 884 |
|
| 885 |
o decay array (decay[]) |
| 886 |
|
| 887 |
o reuse index array size (reuse-index-array-size) |
| 888 |
|
| 889 |
|
| 890 |
|
| 891 |
|
| 892 |
<span class="grey">Villamizar, et. al. Standards Track [Page 16]</span></pre> |
| 893 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-17" ></span> |
| 894 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 895 |
|
| 896 |
|
| 897 |
o reuse index array (reuse-index-array[]) |
| 898 |
|
| 899 |
For each decay rate specified, an array will be used to store the |
| 900 |
value of a computed parameter raised to the power of the index of |
| 901 |
each array element. This is to speed computations. The decay rate |
| 902 |
per tick is an intermediate value expressed as a real number and used |
| 903 |
to compute the values stored in the decay arrays. The array size is |
| 904 |
computed from the decay memory limit configuration parameter |
| 905 |
expressed as an array size or as a maximum hold time. |
| 906 |
|
| 907 |
The decay array size must be of sufficient size to accommodate the |
| 908 |
specified decay memory given the time granularity, or sufficient to |
| 909 |
hold the number of array elements until integer rounding produces a |
| 910 |
zero result if that value is smaller, or a implementation imposed |
| 911 |
reasonable size to prevent configurations which use excessive memory. |
| 912 |
Implementations may chose to make the array size shorter and multiply |
| 913 |
more than once when decaying a long time interval to reduce storage. |
| 914 |
|
| 915 |
The reuse index arrays serve a similar purpose to the decay arrays. |
| 916 |
In BGP, a route is said to be "used" if it is considered the best |
| 917 |
route. In this context, if the route is "used" it is placed in the |
| 918 |
RIB and is eligible for advertisement to BGP peers. If a route is |
| 919 |
withdrawn (a BGP announcement is made by a peer indicating that it is |
| 920 |
no longer reachable), then it is no longer eligible for "use". When |
| 921 |
a route becomes reachable it may not be "used" immediately if the |
| 922 |
figure of merit indicates that a recent instability has occurred. |
| 923 |
After the route remains stable and the figure of merit decays below |
| 924 |
the "reuse" threshhold, the route is said to be eligible to be |
| 925 |
"reused" (treated as truly reachable, placed in the RIB and |
| 926 |
advertised to peers). The amount of time until a route can be reused |
| 927 |
can be determined using a array lookup. The array can be built given |
| 928 |
the decay rate. The array is indexed using a scaled integer |
| 929 |
proportional to the ratio between a current stability figure of merit |
| 930 |
value and the value needed for the route to be reused. |
| 931 |
|
| 932 |
<span class="h4"><a class="selflink" id="section-4.4.3" href="#section-4.4.3">4.4.3</a> Per Route State</span> |
| 933 |
|
| 934 |
Information must be maintained per some tuple representing a route. |
| 935 |
At the very minimum, the NLRI (BGP prefix and length) must be |
| 936 |
contained in the tuple. Different BGP attributes may be included or |
| 937 |
excluded depending on the specific situation. The AS path should |
| 938 |
also be contained in the tuple by default. The tuple may also |
| 939 |
optionally contain other BGP attributes such as |
| 940 |
MULTI_EXIT_DISCRIMINATOR (MED). |
| 941 |
|
| 942 |
The tuple representing a route for the purpose of route flap damping |
| 943 |
is: |
| 944 |
|
| 945 |
|
| 946 |
|
| 947 |
|
| 948 |
<span class="grey">Villamizar, et. al. Standards Track [Page 17]</span></pre> |
| 949 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-18" ></span> |
| 950 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 951 |
|
| 952 |
|
| 953 |
tuple entry default options |
| 954 |
------------------------------------------- |
| 955 |
NLRI |
| 956 |
prefix required |
| 957 |
length required |
| 958 |
AS path included option to exclude |
| 959 |
last AS set in path excluded option to include |
| 960 |
next hop excluded option to include |
| 961 |
MED excluded option to include |
| 962 |
in comparisons only |
| 963 |
|
| 964 |
The AS path is generally included in order to identify downstream |
| 965 |
instability which is not being damped or not being sufficiently |
| 966 |
damped and is alternating between a stable and an unstable path. |
| 967 |
Under rare circumstances it may be desirable to exclude AS path for |
| 968 |
all or a subset of prefixes. If an AS path ends in an AS set, in |
| 969 |
practice the path is always for an aggregate. Changes to the |
| 970 |
trailing AS set should be ignored. Ideally the AS path comparison |
| 971 |
should insure that at least one AS has remained constant in the old |
| 972 |
and new AS set, but completely ignoring the contents of a trailing AS |
| 973 |
set is also acceptable. |
| 974 |
|
| 975 |
Including next hop and MED changes can help suppress the use of an AS |
| 976 |
which is internally unstable or avoid a next hop which is closer to |
| 977 |
an unstable IGP path in the adjacent AS. If a large number of MED |
| 978 |
values are used, the increase in the amount of state may become a |
| 979 |
problem. For this reason MED is disabled by default and enabled only |
| 980 |
as part of the tuple comparison, using a single state entry |
| 981 |
regardless of MED value. Including MED will suppress the use of the |
| 982 |
adjacent AS even though the change need not be propagated further. |
| 983 |
Using MED is only a safe practice if a path is known to exist through |
| 984 |
another AS or where there are enough peering sites with the adjacent |
| 985 |
AS such that routes heard at only a subset of the peering sites will |
| 986 |
be suppressed. |
| 987 |
|
| 988 |
<span class="h4"><a class="selflink" id="section-4.4.4" href="#section-4.4.4">4.4.4</a> Data Structures per Route</span> |
| 989 |
|
| 990 |
The following information must be maintained per route. A route here |
| 991 |
is considered to be a tuple usually containing NLRI, next hop, and AS |
| 992 |
path as defined in <a href="#section-4.4.3">Section 4.4.3</a>. |
| 993 |
|
| 994 |
stability figure of merit (figure-of-merit) |
| 995 |
|
| 996 |
Each route must have a stability figure of merit per applicable |
| 997 |
parameter set. |
| 998 |
|
| 999 |
last time updated (time-update) |
| 1000 |
|
| 1001 |
|
| 1002 |
|
| 1003 |
|
| 1004 |
<span class="grey">Villamizar, et. al. Standards Track [Page 18]</span></pre> |
| 1005 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-19" ></span> |
| 1006 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 1007 |
|
| 1008 |
|
| 1009 |
The exact last time updated must be maintained to allow |
| 1010 |
exponential decay of the accumulated figure of merit to be |
| 1011 |
deferred until the route might reasonable be considered eligible |
| 1012 |
for a change in status (having gone from unreachable to |
| 1013 |
reachable or advancing within the reuse lists). |
| 1014 |
|
| 1015 |
config block pointer |
| 1016 |
|
| 1017 |
Any implementation that supports multiple parameter sets must |
| 1018 |
provide a means of quickly identifying which set of parameters |
| 1019 |
corresponds to the route currently being considered. For |
| 1020 |
implementations supporting only parameter sets where all routes |
| 1021 |
must be treated the same, this pointer is not required. |
| 1022 |
|
| 1023 |
reuse list traversal pointers |
| 1024 |
|
| 1025 |
If doubly linked lists are used to implement reuse lists, then |
| 1026 |
two pointers will be needed, previous and next. Generally there |
| 1027 |
is a double linked list which is unused when a route is |
| 1028 |
suppressed from use that can be used for reuse list traversal |
| 1029 |
eliminating the need for additional pointer storage. |
| 1030 |
|
| 1031 |
<span class="h3"><a class="selflink" id="section-4.5" href="#section-4.5">4.5</a> Processing Configuration Parameters</span> |
| 1032 |
|
| 1033 |
From the configuration parameters, it is possible to precompute |
| 1034 |
a number of values that will be used repeatedly and retain these |
| 1035 |
to speed later computations that will be required frequently. |
| 1036 |
|
| 1037 |
Scaling is usually dependent on the highest value that figure- |
| 1038 |
of-merit can attain, referred to here as the ceiling. The real |
| 1039 |
number value of the ceiling will typically be determined by the |
| 1040 |
following equation. The ceiling can also be configured to a |
| 1041 |
specific value, which in turn dictates T-hold. |
| 1042 |
|
| 1043 |
ceiling = reuse * (exp(T-hold/decay-half-life) * log(2)) |
| 1044 |
|
| 1045 |
In the above equation, reuse is the reuse threshhold described |
| 1046 |
in <a href="#section-4.2">Section 4.2</a>. |
| 1047 |
|
| 1048 |
The methods of scaled integer arithmetic are not described in |
| 1049 |
detail here. The methods of determining the real values are |
| 1050 |
given. Translation into scaled integer values and the details |
| 1051 |
of scaled integer arithmetic are left up to the individual |
| 1052 |
implementations. |
| 1053 |
|
| 1054 |
The ceiling value can be set to be the largest integer that can fit |
| 1055 |
in half the bits available for an unsigned integer. This will |
| 1056 |
allow the scaled integers to be multiplied by the scaled decay |
| 1057 |
|
| 1058 |
|
| 1059 |
|
| 1060 |
<span class="grey">Villamizar, et. al. Standards Track [Page 19]</span></pre> |
| 1061 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-20" ></span> |
| 1062 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 1063 |
|
| 1064 |
|
| 1065 |
value and then shifted down. Implementations may prefer to use |
| 1066 |
real numbers or may use any integer scaling deemed appropriate for |
| 1067 |
their architecture. |
| 1068 |
|
| 1069 |
penalty value and thresholds (as proportional scaled integers) |
| 1070 |
|
| 1071 |
The figure of merit penalty for one route withdrawal and the |
| 1072 |
cutoff values must be scaled according to the above scaling |
| 1073 |
factor. |
| 1074 |
|
| 1075 |
decay rate per tick (decay[1]) |
| 1076 |
|
| 1077 |
The decay value per increment of time as defined by the time |
| 1078 |
granularity must be determined (at least initially as a floating |
| 1079 |
point number). The per tick decay is a number slightly less |
| 1080 |
than one. It is the Nth root of the one half where N is the |
| 1081 |
half life divided by the time granularity. |
| 1082 |
|
| 1083 |
decay[1] = exp ((1 / (decay-half-life/delta-t)) * log (1/2)) |
| 1084 |
|
| 1085 |
decay array size (decay-array-size) |
| 1086 |
|
| 1087 |
The decay array size is the decay memory divided by the time |
| 1088 |
granularity. If integer truncation brings the value of an array |
| 1089 |
element to zero, the array can be made smaller. An |
| 1090 |
implementation should also impose a maximum reasonable array |
| 1091 |
size or allow more than one multiplication. |
| 1092 |
|
| 1093 |
decay-array-size = (Tmax/delta-t) |
| 1094 |
|
| 1095 |
decay array (decay[]) |
| 1096 |
|
| 1097 |
Each i-th element of the decay array is the per tick delay |
| 1098 |
raised to the i-th power. This might be best done by successive |
| 1099 |
floating point multiplies followed by scaling and integer |
| 1100 |
rounding or truncation. The array itself need only be computed |
| 1101 |
at startup. |
| 1102 |
|
| 1103 |
decay[i] = decay[1] ** i |
| 1104 |
|
| 1105 |
<span class="h3"><a class="selflink" id="section-4.6" href="#section-4.6">4.6</a> Building the Reuse Index Arrays</span> |
| 1106 |
|
| 1107 |
The reuse lists may be accessed quite frequently if a lot of routes |
| 1108 |
are flapping sufficiently to be suppressed. A method of speeding the |
| 1109 |
determination of which reuse list to use for a given route is |
| 1110 |
suggested. This method is introduced in <a href="#section-4.2">Section 4.2</a>, its |
| 1111 |
configuration described in <a href="#section-4.4.2">Section 4.4.2</a> and the algorithms described |
| 1112 |
in <a href="#section-4.8.6">Section 4.8.6</a> and <a href="#section-4.8.7">Section 4.8.7</a>. This section describes building |
| 1113 |
|
| 1114 |
|
| 1115 |
|
| 1116 |
<span class="grey">Villamizar, et. al. Standards Track [Page 20]</span></pre> |
| 1117 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-21" ></span> |
| 1118 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 1119 |
|
| 1120 |
|
| 1121 |
the reuse list index arrays. |
| 1122 |
|
| 1123 |
A ratio of the figure of merit of the route under consideration to |
| 1124 |
the cutoff value is used as the basis for an array lookup. The ratio |
| 1125 |
is scaled and truncated to an integer and used to index the array. |
| 1126 |
The array entry is an integer used to determine which reuse list to |
| 1127 |
use. |
| 1128 |
|
| 1129 |
reuse array maximum ratio (max-ratio) |
| 1130 |
|
| 1131 |
This is the maximum ratio between the current value of the |
| 1132 |
stability figure of merit and the target reuse value that can be |
| 1133 |
indexed by the reuse array. It may be limited by the ceiling |
| 1134 |
imposed by the maximum hold time or by the amount of time that |
| 1135 |
the reuse lists cover. |
| 1136 |
|
| 1137 |
max-ratio = min(ceiling/reuse, exp((1 / (half-life/reuse- |
| 1138 |
array-time)) * log(2))) |
| 1139 |
|
| 1140 |
reuse array scale factor ( scale-factor ) |
| 1141 |
|
| 1142 |
Since the reuse array is an estimator, the reuse array scale |
| 1143 |
factor has to be computed such that the full size of the reuse |
| 1144 |
array is used. |
| 1145 |
|
| 1146 |
scale-factor = reuse-index-array-size / (max-ratio - 1) |
| 1147 |
|
| 1148 |
reuse index array (reuse-index-array[]) |
| 1149 |
|
| 1150 |
Each reuse index array entry should contain an index into the |
| 1151 |
reuse list array pointing to one of the list heads. This index |
| 1152 |
should corresponding to the reuse list that will be evaluated |
| 1153 |
just after a route would be eligible for reuse given the ratio |
| 1154 |
of current value of the stability figure of merit to target |
| 1155 |
reuse value corresponding the the reuse array entry. |
| 1156 |
|
| 1157 |
reuse-index-array[j] = integer((decay-half-life / reuse- |
| 1158 |
time-granularity) * log(1/(reuse * (1 + (j / scale-factor)))) / |
| 1159 |
log(1/2)) |
| 1160 |
|
| 1161 |
To determine which reuse queue to place a route which is being |
| 1162 |
suppressed, the following procedure is used. Divide the current |
| 1163 |
figure of merit by the cutoff. Subtract one. Multiply by the scale |
| 1164 |
factor. This is the index into the reuse index array (reuse-index- |
| 1165 |
array[]). The value fetched from the reuse index array (reuse- |
| 1166 |
index-array[]) is an index into the array of reuse lists (reuse- |
| 1167 |
array[]). If this index is off the end of the array use the last |
| 1168 |
queue otherwise look in the array and pick the number of the queue |
| 1169 |
|
| 1170 |
|
| 1171 |
|
| 1172 |
<span class="grey">Villamizar, et. al. Standards Track [Page 21]</span></pre> |
| 1173 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-22" ></span> |
| 1174 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 1175 |
|
| 1176 |
|
| 1177 |
from the array at that index. This is quite fast and well worth the |
| 1178 |
setup and storage required. |
| 1179 |
|
| 1180 |
<span class="h3"><a class="selflink" id="section-4.7" href="#section-4.7">4.7</a> A Sample Configuration</span> |
| 1181 |
|
| 1182 |
A simple example is presented here in which the space overhead is |
| 1183 |
estimated for a set of configuration parameters. The design here |
| 1184 |
assumes: |
| 1185 |
|
| 1186 |
1. there is a single parameter set used for all routes, |
| 1187 |
|
| 1188 |
2. decay time for unreachable routes is slower than for reachable |
| 1189 |
routes |
| 1190 |
|
| 1191 |
3. the arrays must be full size, rather than allow more than one |
| 1192 |
multiply per decay operation to reduce the array size. |
| 1193 |
|
| 1194 |
This example is used in later sections. The use of multiple |
| 1195 |
parameter sets complicates the examples somewhat. Where multiple |
| 1196 |
parameter sets are allowed for a single route, the decay portion of |
| 1197 |
the algorithm is repeated for each parameter set. If different |
| 1198 |
routes are allowed to have different parameter sets, the routes must |
| 1199 |
have pointers to the parameter sets to keep the time to locate to a |
| 1200 |
minimum, but the algorithms are otherwise unchanged. |
| 1201 |
|
| 1202 |
A sample set of configuration parameters and a sample set of |
| 1203 |
implementation parameters are provided in in the two following lists. |
| 1204 |
|
| 1205 |
1. Configuration Parameters |
| 1206 |
|
| 1207 |
o cut = 1.25 |
| 1208 |
|
| 1209 |
o reuse = 0.5 |
| 1210 |
|
| 1211 |
o T-hold = 15 mins |
| 1212 |
|
| 1213 |
o decay-ok = 5 min |
| 1214 |
|
| 1215 |
o decay-ng = 15 min |
| 1216 |
|
| 1217 |
o Tmax-ok, Tmax-ng = 15, 30 mins |
| 1218 |
|
| 1219 |
2. Implementation Parameters |
| 1220 |
|
| 1221 |
o delta-t = 1 sec |
| 1222 |
|
| 1223 |
o delta-reuse = 15 sec |
| 1224 |
|
| 1225 |
|
| 1226 |
|
| 1227 |
|
| 1228 |
<span class="grey">Villamizar, et. al. Standards Track [Page 22]</span></pre> |
| 1229 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-23" ></span> |
| 1230 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 1231 |
|
| 1232 |
|
| 1233 |
o reuse-list-size = 256 |
| 1234 |
|
| 1235 |
o reuse-index-array-size = 1,024 |
| 1236 |
|
| 1237 |
Using these configuration and implementation parameters and the |
| 1238 |
equations in <a href="#section-4.5">Section 4.5</a>, the space overhead can be computed. There |
| 1239 |
is a fixed space overhead that is independent of the number of |
| 1240 |
routes. There is a space requirement associated with a stable route. |
| 1241 |
There is a larger space requirement associated with an unstable |
| 1242 |
route. The space requirements for the parameters above are provide |
| 1243 |
in the lists below. |
| 1244 |
|
| 1245 |
1. fixed overhead (using parameters from previous example) |
| 1246 |
|
| 1247 |
o 900 * integer - decay array |
| 1248 |
|
| 1249 |
o 1,800 * integer - decay array |
| 1250 |
|
| 1251 |
o 120 * pointer - reuse list-heads |
| 1252 |
|
| 1253 |
o 2,048 * integer - reuse index arrays |
| 1254 |
|
| 1255 |
2. overhead per stable route |
| 1256 |
|
| 1257 |
o pointer - containing null entry |
| 1258 |
|
| 1259 |
3. overhead per unstable route |
| 1260 |
|
| 1261 |
o pointer - to a damping structure containing the following |
| 1262 |
|
| 1263 |
o integer - figure of merit + bit for state |
| 1264 |
|
| 1265 |
o integer - last time updated |
| 1266 |
|
| 1267 |
o 2 * pointer - reuse list pointers (prev, next) |
| 1268 |
|
| 1269 |
The decay arrays are sized acording to delta-t and Tmax-ok or Tmax- |
| 1270 |
ng. The number of reuse list-heads is based on delta-reuse and the |
| 1271 |
greater of Tmax-ok or Tmax-ng. There are two reuse index arrays |
| 1272 |
whose size is a configured parameter. |
| 1273 |
|
| 1274 |
Figure 3 shows the behavior of the algorithm with the parameters |
| 1275 |
given above. Four cases are given in this example. In all four, |
| 1276 |
there is a twelve minute period of route oscillations. Two periods |
| 1277 |
of oscillation are used, 2 minutes and 4 minutes. Two duty cycles |
| 1278 |
are used, one in which the route is reachable during 20% of the cycle |
| 1279 |
and the other where the route is reachable during 80% of the cycle. |
| 1280 |
In all four cases, the route becomes suppressed after it becomes |
| 1281 |
|
| 1282 |
|
| 1283 |
|
| 1284 |
<span class="grey">Villamizar, et. al. Standards Track [Page 23]</span></pre> |
| 1285 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-24" ></span> |
| 1286 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 1287 |
|
| 1288 |
|
| 1289 |
unreachable the second time. Once suppressed, it remains suppressed |
| 1290 |
until some period after becoming stable. The routes which oscillate |
| 1291 |
over a 4 minute period are no longer suppressed within 9-11 minutes |
| 1292 |
after becoming stable. The routes with a 2 minute period of |
| 1293 |
oscillation are suppressed for nearly the maximum 15 minute period |
| 1294 |
after becoming stable. |
| 1295 |
|
| 1296 |
<span class="h3"><a class="selflink" id="section-4.8" href="#section-4.8">4.8</a> Processing Routing Protocol Activity</span> |
| 1297 |
|
| 1298 |
The prior sections concentrate on configuration parameters and their |
| 1299 |
relationship to the parameters and arrays used at run time and |
| 1300 |
provide the algorithms for initializing run time storage. This |
| 1301 |
section provides the steps taken in processing routing events and |
| 1302 |
timer events when running. |
| 1303 |
|
| 1304 |
The routing events are: |
| 1305 |
|
| 1306 |
1. A BGP peer or new route comes up for the first time (or after |
| 1307 |
an extended down time) (<a href="#section-4.8.1">Section 4.8.1</a>) |
| 1308 |
|
| 1309 |
2. A route becomes unreachable (<a href="#section-4.8.2">Section 4.8.2</a>) |
| 1310 |
|
| 1311 |
3. A route becomes reachable again (<a href="#section-4.8.3">Section 4.8.3</a>) |
| 1312 |
|
| 1313 |
4. A route changes (<a href="#section-4.8.4">Section 4.8.4</a>) |
| 1314 |
|
| 1315 |
5. A peer goes down (<a href="#section-4.8.5">Section 4.8.5</a>) |
| 1316 |
|
| 1317 |
|
| 1318 |
|
| 1319 |
|
| 1320 |
|
| 1321 |
|
| 1322 |
|
| 1323 |
|
| 1324 |
|
| 1325 |
|
| 1326 |
|
| 1327 |
|
| 1328 |
|
| 1329 |
|
| 1330 |
|
| 1331 |
|
| 1332 |
|
| 1333 |
|
| 1334 |
|
| 1335 |
|
| 1336 |
|
| 1337 |
|
| 1338 |
|
| 1339 |
|
| 1340 |
<span class="grey">Villamizar, et. al. Standards Track [Page 24]</span></pre> |
| 1341 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-25" ></span> |
| 1342 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 1343 |
|
| 1344 |
|
| 1345 |
time figure-of-merit as a function of time (in minutes) |
| 1346 |
|
| 1347 |
0.00 0.000 . 0.000 . 0.000 . 0.000 . |
| 1348 |
0.62 0.000 . 0.000 . 0.000 . 0.000 . |
| 1349 |
1.25 0.000 . 0.000 . 0.000 . 0.000 . |
| 1350 |
1.88 0.000 . 0.000 . 0.000 . 0.000 . |
| 1351 |
2.50 0.977 . 0.968 . 0.000 . 0.000 . |
| 1352 |
3.12 0.949 . 0.888 . 0.000 . 0.000 . |
| 1353 |
3.75 0.910 . 0.814 . 0.000 . 0.000 . |
| 1354 |
4.37 1.846 . 1.756 . 0.983 . 0.983 . |
| 1355 |
5.00 1.794 . 1.614 . 0.955 . 0.935 . |
| 1356 |
5.63 1.735 . 1.480 . 0.928 . 0.858 . |
| 1357 |
6.25 2.619 . 2.379 . 0.901 . 0.786 . |
| 1358 |
6.88 2.544 . 2.207 . 0.876 . 0.721 . |
| 1359 |
7.50 2.472 . 2.024 . 0.825 . 0.661 . |
| 1360 |
8.13 3.308 . 2.875 . 1.761 . 1.608 . |
| 1361 |
8.75 3.213 . 2.698 . 1.711 . 1.562 . |
| 1362 |
9.38 3.122 . 2.474 . 1.662 . 1.436 . |
| 1363 |
10.00 3.922 . 3.273 . 1.615 . 1.317 . |
| 1364 |
10.63 3.810 . 3.107 . 1.569 . 1.207 . |
| 1365 |
11.25 3.702 . 2.849 . 1.513 . 1.107 . |
| 1366 |
11.88 3.498 . 2.613 . 1.388 . 1.015 . |
| 1367 |
12.50 3.904 . 3.451 . 2.312 . 1.953 . |
| 1368 |
13.13 3.580 . 3.164 . 2.120 . 1.791 . |
| 1369 |
13.75 3.283 . 2.902 . 1.944 . 1.643 . |
| 1370 |
14.38 3.010 . 2.661 . 1.783 . 1.506 . |
| 1371 |
15.00 2.761 . 2.440 . 1.635 . 1.381 . |
| 1372 |
15.63 2.532 . 2.238 . 1.499 . 1.267 . |
| 1373 |
16.25 2.321 . 2.052 . 1.375 . 1.161 . |
| 1374 |
16.88 2.129 . 1.882 . 1.261 . 1.065 . |
| 1375 |
17.50 1.952 . 1.725 . 1.156 . 0.977 . |
| 1376 |
18.12 1.790 . 1.582 . 1.060 . 0.896 . |
| 1377 |
18.75 1.641 . 1.451 . 0.972 . 0.821 . |
| 1378 |
19.38 1.505 . 1.331 . 0.891 . 0.753 . |
| 1379 |
20.00 1.380 . 1.220 . 0.817 . 0.691 . |
| 1380 |
20.62 1.266 . 1.119 . 0.750 . 0.633 . |
| 1381 |
21.25 1.161 . 1.026 . 0.687 . 0.581 . |
| 1382 |
21.87 1.064 . 0.941 . 0.630 . 0.533 . |
| 1383 |
22.50 0.976 . 0.863 . 0.578 . 0.488 . |
| 1384 |
23.12 0.895 . 0.791 . 0.530 . 0.448 . |
| 1385 |
23.75 0.821 . 0.725 . 0.486 . 0.411 . |
| 1386 |
24.37 0.753 . 0.665 . 0.446 . 0.377 . |
| 1387 |
25.00 0.690 . 0.610 . 0.409 . 0.345 . |
| 1388 |
|
| 1389 |
Figure 3: Some fairly long route flap cycles, repeated for 12 minutes, |
| 1390 |
followed by a period of stability. |
| 1391 |
|
| 1392 |
|
| 1393 |
|
| 1394 |
|
| 1395 |
|
| 1396 |
<span class="grey">Villamizar, et. al. Standards Track [Page 25]</span></pre> |
| 1397 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-26" ></span> |
| 1398 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 1399 |
|
| 1400 |
|
| 1401 |
The reuse list is used to provide a means of fast evaluation of route |
| 1402 |
that had been suppressed, but had been stable long enough to be |
| 1403 |
reused again or had been suppressed long enough that it can be |
| 1404 |
treated as a new route. The following two operations are described. |
| 1405 |
|
| 1406 |
1. Inserting into a reuse list (<a href="#section-4.8.6">Section 4.8.6</a>) |
| 1407 |
|
| 1408 |
2. Reuse list processing every delta-t seconds (<a href="#section-4.8.7">Section 4.8.7</a>) |
| 1409 |
|
| 1410 |
<span class="h4"><a class="selflink" id="section-4.8.1" href="#section-4.8.1">4.8.1</a> Processing a New Peer or New Routes</span> |
| 1411 |
|
| 1412 |
When a peer comes up, no action is required if the routes had no |
| 1413 |
previous history of instability, for example if this is the first |
| 1414 |
time the peer is coming up and announcing these routes. For each |
| 1415 |
route, the pointer to the damping structure would be zeroed and route |
| 1416 |
used. The same action is taken for a new route or a route that has |
| 1417 |
been down long enough that the figure of merit reached zero and the |
| 1418 |
damping structure was deleted. |
| 1419 |
|
| 1420 |
<span class="h4"><a class="selflink" id="section-4.8.2" href="#section-4.8.2">4.8.2</a> Processing Unreachable Messages</span> |
| 1421 |
|
| 1422 |
When a route is withdrawn or changed (<a href="#section-4.8.4">Section 4.8.4</a> describes how a |
| 1423 |
change is handled), the following procedure is used. |
| 1424 |
|
| 1425 |
If there is no previous stability history (the damping structure |
| 1426 |
pointer is zero), then: |
| 1427 |
|
| 1428 |
1. allocate a damping structure |
| 1429 |
|
| 1430 |
2. set figure-of-merit = 1 |
| 1431 |
|
| 1432 |
3. withdraw the route |
| 1433 |
|
| 1434 |
Otherwise, if there is an existing damping structure, then: |
| 1435 |
|
| 1436 |
1. set t-diff = t-now - t-updated |
| 1437 |
|
| 1438 |
2. if (t-diff puts you off the end of the array) { |
| 1439 |
|
| 1440 |
setfigure-of-merit =1 |
| 1441 |
|
| 1442 |
}else { |
| 1443 |
|
| 1444 |
setfigure-of-merit =figure-of-merit *decay-array-ok [t-diff ]+ 1 |
| 1445 |
|
| 1446 |
if(figure-of-merit >ceiling) { |
| 1447 |
|
| 1448 |
setfigure-of-merit =ceiling |
| 1449 |
|
| 1450 |
|
| 1451 |
|
| 1452 |
<span class="grey">Villamizar, et. al. Standards Track [Page 26]</span></pre> |
| 1453 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-27" ></span> |
| 1454 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 1455 |
|
| 1456 |
|
| 1457 |
} |
| 1458 |
|
| 1459 |
} |
| 1460 |
|
| 1461 |
3. remove the route from a reuse list if it is on one |
| 1462 |
|
| 1463 |
4. withdraw the route unless it is already suppressed |
| 1464 |
|
| 1465 |
In either case then: |
| 1466 |
|
| 1467 |
1. set t-updated = t-now |
| 1468 |
|
| 1469 |
2. insert into a reuse list (see <a href="#section-4.8.6">Section 4.8.6</a>) |
| 1470 |
|
| 1471 |
If there was a stability history, the previous value of the stability |
| 1472 |
figure of merit is decayed. This is done using the decay array |
| 1473 |
(decay-array). The index is determined by subtracting the current |
| 1474 |
time and the last time updated, then dividing by the time |
| 1475 |
granularity. If the index is zero, the figure of merit is unchanged |
| 1476 |
(no decay). If it is greater than the array size, it is zeroed. |
| 1477 |
Otherwise use the index to fetch a decay array element and multiply |
| 1478 |
the figure of merit by the array element. If using the suggested |
| 1479 |
scaled integer method, shift down half an integer. Add the scaled |
| 1480 |
penalty for one more unreachable (shown above as 1). If the result |
| 1481 |
is above the ceiling replace it with the ceiling value. Now update |
| 1482 |
the last time updated field (preferably taking into account how much |
| 1483 |
time was truncated before doing the decay calculation). |
| 1484 |
|
| 1485 |
When a route becomes unreachable, alternate paths must be considered. |
| 1486 |
This process is complicated slightly if different configuration |
| 1487 |
parameters are used in the presence or absence of viable alternate |
| 1488 |
paths. If all of these alternate paths have been suppressed because |
| 1489 |
there had previously been an alternate route and the new route |
| 1490 |
withdrawal changes that condition, the suppressed alternate paths |
| 1491 |
must be reevaluated. They should be reevaluated in order of normal |
| 1492 |
route preference. When one of these alternate routes is encountered |
| 1493 |
that had been suppressed but is now usable since there is no |
| 1494 |
alternate route, no further routes need to be reevaluated. This only |
| 1495 |
applies if routes are given two different reuse thresholds, one for |
| 1496 |
use when there is an alternate path and a higher threshold to use |
| 1497 |
when suppressing the route would result in making the destination |
| 1498 |
completely unreachable. |
| 1499 |
|
| 1500 |
<span class="h4"><a class="selflink" id="section-4.8.3" href="#section-4.8.3">4.8.3</a> Processing Route Advertisements</span> |
| 1501 |
|
| 1502 |
When a route is readvertised if there is no damping structure, then |
| 1503 |
the procedure is the same as in <a href="#section-4.8.1">Section 4.8.1</a>. |
| 1504 |
|
| 1505 |
|
| 1506 |
|
| 1507 |
|
| 1508 |
<span class="grey">Villamizar, et. al. Standards Track [Page 27]</span></pre> |
| 1509 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-28" ></span> |
| 1510 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 1511 |
|
| 1512 |
|
| 1513 |
1. don't create a new damping structure |
| 1514 |
|
| 1515 |
2. use the route |
| 1516 |
|
| 1517 |
If an damping structure exists, the figure of merit is decayed and |
| 1518 |
the figure of merit and last time updated fields are updated. A |
| 1519 |
decision is now made as to whether the route can be used immediately |
| 1520 |
or needs to be suppressed for some period of time. |
| 1521 |
|
| 1522 |
1. set t-diff = t-now - t-updated |
| 1523 |
|
| 1524 |
2. if (t-diff puts you off the end of the array) { |
| 1525 |
|
| 1526 |
set figure-of-merit =0 |
| 1527 |
|
| 1528 |
}else { |
| 1529 |
|
| 1530 |
set figure-of-merit= figure-of-merit* decay-array-ng[t-diff] |
| 1531 |
|
| 1532 |
} |
| 1533 |
|
| 1534 |
3. if ( not suppressed and figure-of-merit < cut ) { |
| 1535 |
|
| 1536 |
use the route |
| 1537 |
|
| 1538 |
}else if( suppressed and figure-of-merit< reuse) { |
| 1539 |
|
| 1540 |
set state tonot suppressed |
| 1541 |
|
| 1542 |
remove the route from a reuse list |
| 1543 |
|
| 1544 |
use the route |
| 1545 |
|
| 1546 |
}else { |
| 1547 |
|
| 1548 |
set state to suppressed |
| 1549 |
|
| 1550 |
don't use the route |
| 1551 |
|
| 1552 |
insert into a reuse list (see <a href="#section-4.8.6">Section 4.8.6</a>) |
| 1553 |
|
| 1554 |
} |
| 1555 |
|
| 1556 |
4. if ( figure-of-merit > 0 ) { |
| 1557 |
|
| 1558 |
set t-updated= t-now |
| 1559 |
|
| 1560 |
}else { |
| 1561 |
|
| 1562 |
|
| 1563 |
|
| 1564 |
<span class="grey">Villamizar, et. al. Standards Track [Page 28]</span></pre> |
| 1565 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-29" ></span> |
| 1566 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 1567 |
|
| 1568 |
|
| 1569 |
recover memory for damping struct |
| 1570 |
|
| 1571 |
zero pointer to damping struct |
| 1572 |
|
| 1573 |
} |
| 1574 |
|
| 1575 |
If the route is deemed usable, a search for the current best route |
| 1576 |
must be made. The newly reachable route is then evaluated according |
| 1577 |
to the BGP protocol rules for route selection. |
| 1578 |
|
| 1579 |
If the new route is usable, the previous best route is examined. |
| 1580 |
Prior to route comparisons, the current best route may have to be |
| 1581 |
reevaluated if separate parameter sets are used depending on the |
| 1582 |
presence or absence of an alternate route. If there had been no |
| 1583 |
alternate the previous best route may be suppressed. |
| 1584 |
|
| 1585 |
If the new route is to be suppressed it is placed on a reuse list |
| 1586 |
only if it would have been preferred to the current best route had |
| 1587 |
the new route been accepted as stable. There is no reason to queue a |
| 1588 |
route on a reuse list if after the route becomes usable it would not |
| 1589 |
be used anyway due to the existence of a more preferred route. Such |
| 1590 |
a route would not have to be reevaluated unless the preferred route |
| 1591 |
became unreachable. As specified here, the less preferred route |
| 1592 |
would be reevaluated and potentially used or potentially added to a |
| 1593 |
reuse list when processing the withdrawal of a more preferred best |
| 1594 |
route. |
| 1595 |
|
| 1596 |
<span class="h4"><a class="selflink" id="section-4.8.4" href="#section-4.8.4">4.8.4</a> Processing Route Changes</span> |
| 1597 |
|
| 1598 |
If a route is replaced by a peer router by supplying a new path, the |
| 1599 |
route that is being replaced should be treated as if an unreachable |
| 1600 |
were received (see <a href="#section-4.8.2">Section 4.8.2</a>). This will occur when a peer |
| 1601 |
somewhere back in the AS path is continuously switching between two |
| 1602 |
AS paths and that peer is not damping route flap (or applying less |
| 1603 |
damping). There is no way to determine if one AS path is stable and |
| 1604 |
the other is flapping, or if they are both flapping. If the cycle is |
| 1605 |
sufficiently short compared to convergence times neither route |
| 1606 |
through that peer will deliver packets very reliably. Since there is |
| 1607 |
no way to affect the peer such that it chooses the stable of the two |
| 1608 |
AS paths, the only viable option is to penalize both routes by |
| 1609 |
considering each change as an unreachable followed by a route |
| 1610 |
advertisement. |
| 1611 |
|
| 1612 |
<span class="h4"><a class="selflink" id="section-4.8.5" href="#section-4.8.5">4.8.5</a> Processing A Peer Router Loss</span> |
| 1613 |
|
| 1614 |
When a peer routing session is broken, either all individual routes |
| 1615 |
advertised by that peer may be marked as unstable, or the peering |
| 1616 |
session itself may be marked as unstable. Marking the peer will save |
| 1617 |
|
| 1618 |
|
| 1619 |
|
| 1620 |
<span class="grey">Villamizar, et. al. Standards Track [Page 29]</span></pre> |
| 1621 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-30" ></span> |
| 1622 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 1623 |
|
| 1624 |
|
| 1625 |
considerable memory. Since the individual routes are advertised as |
| 1626 |
unreachable to routers beyond the immediate problem, per route state |
| 1627 |
will be incurred beyond the peer immediately adjacent to the BGP |
| 1628 |
session that went down. If the instability continues, the |
| 1629 |
immediately adjacent router need only keep track of the peer |
| 1630 |
stability history. The routers beyond that point will receive no |
| 1631 |
further advertisements or withdrawal of routes and will dispose of |
| 1632 |
the damping structure over time. |
| 1633 |
|
| 1634 |
BGP notification through an optional transitive attribute that |
| 1635 |
damping will already be applied may be considered in the future to |
| 1636 |
reduce the number of routers that incur damping structure storage |
| 1637 |
overhead. |
| 1638 |
|
| 1639 |
<span class="h4"><a class="selflink" id="section-4.8.6" href="#section-4.8.6">4.8.6</a> Inserting into the Reuse Timer List</span> |
| 1640 |
|
| 1641 |
The reuse lists are used to provide a means of fast evaluation of |
| 1642 |
route that had been suppressed, but had been stable long enough to be |
| 1643 |
reused again. The data structure consists of a series of list heads. |
| 1644 |
Each list contains a set of routes that are scheduled for |
| 1645 |
reevaluation at approximately the same time. The set of reuse list |
| 1646 |
heads are treated as a circular array. Refer to Figure 4. |
| 1647 |
|
| 1648 |
A simple implementation of the circular array of list heads would be |
| 1649 |
an array containing the list heads. An offset is used when accessing |
| 1650 |
the array. The offset would identify the first list. The Nth list |
| 1651 |
would be at the index corresponding to N plus the offset modulo the |
| 1652 |
number of list heads. This design will be assumed in the examples |
| 1653 |
that follow. |
| 1654 |
|
| 1655 |
A key requirement is to be able to insert an entry in the most |
| 1656 |
appropriate queue with a minimum of computation. The computation is |
| 1657 |
given only the current value of figure-of-merit. Instead of a |
| 1658 |
computation which would involve a logarithm, the reuse array (reuse- |
| 1659 |
array[]) described in <a href="#section-4.6">Section 4.6</a> is used. The array, scale, and |
| 1660 |
bounds are precomputed to map figure-of-merit to the nearest list |
| 1661 |
head without requiring a logarithm to be computed (see <a href="#section-4.5">Section 4.5</a>). |
| 1662 |
|
| 1663 |
|
| 1664 |
|
| 1665 |
|
| 1666 |
|
| 1667 |
|
| 1668 |
|
| 1669 |
|
| 1670 |
|
| 1671 |
|
| 1672 |
|
| 1673 |
|
| 1674 |
|
| 1675 |
|
| 1676 |
<span class="grey">Villamizar, et. al. Standards Track [Page 30]</span></pre> |
| 1677 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-31" ></span> |
| 1678 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 1679 |
|
| 1680 |
|
| 1681 |
+-+ +-+ +-+ non-empty linked list means |
| 1682 |
| | | | | | <-- that there are routes with |
| 1683 |
+-+ +-+ +-+ defered action to be taken |
| 1684 |
^ ^ ^ N * delta-reuse seconds later. |
| 1685 |
| | | |
| 1686 |
+------+------+------+------+------+ +------+ |
| 1687 |
| list | list | list | list | list | ... | list | |
| 1688 |
| head | head | head | head | head | ... | head | |
| 1689 |
+------+------+------+------+------+ +------+ |
| 1690 |
^ ^ ^ ^ ^ ^ |
| 1691 |
Nth 1st 2nd 3rd 4th N-1 |
| 1692 |
| |
| 1693 |
offset to first list |
| 1694 |
(the offset is incremented every delta-reuse seconds) |
| 1695 |
|
| 1696 |
Figure 4: Reuse List Data Structures |
| 1697 |
|
| 1698 |
Note that in the following sections the operator prefix notation |
| 1699 |
"modulo a b" means "b % a" in C language algebraic operator notation. |
| 1700 |
For example, "modulo 16 1023" would be 15. |
| 1701 |
|
| 1702 |
1. scale figure-of-merit for the index array lookup producing |
| 1703 |
index |
| 1704 |
|
| 1705 |
2. check index against the array bound |
| 1706 |
|
| 1707 |
3. if (within the array bound) { |
| 1708 |
|
| 1709 |
set index =reuse-array [index ] |
| 1710 |
|
| 1711 |
}else { |
| 1712 |
|
| 1713 |
set index =reuse-list-size -1 |
| 1714 |
|
| 1715 |
} |
| 1716 |
|
| 1717 |
4. insert into the list |
| 1718 |
|
| 1719 |
reuse-list[ moduloreuse-list-size (index +offset )] |
| 1720 |
|
| 1721 |
Choosing the correct reuse list involves only a multiply and shift to |
| 1722 |
do the scaling, an integer truncation, then an array lookup in the |
| 1723 |
reuse array (reuse-array[]). The value retrieved from the reuse |
| 1724 |
array is used to select a reuse list. The reuse list is a circular |
| 1725 |
list. The most common method of implementing a circular list is to |
| 1726 |
use an array and apply an offset and modulo operation to pick the |
| 1727 |
correct array entry. The offset is incremented to rotate the |
| 1728 |
circular list. |
| 1729 |
|
| 1730 |
|
| 1731 |
|
| 1732 |
<span class="grey">Villamizar, et. al. Standards Track [Page 31]</span></pre> |
| 1733 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-32" ></span> |
| 1734 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 1735 |
|
| 1736 |
|
| 1737 |
<span class="h4"><a class="selflink" id="section-4.8.7" href="#section-4.8.7">4.8.7</a> Handling Reuse Timer Events</span> |
| 1738 |
|
| 1739 |
The granularity of the reuse timer should be more coarse than that of |
| 1740 |
the decay timer. As a result, when the reuse timer fires, suppressed |
| 1741 |
routes should be decayed by multiple increments of decay time. Some |
| 1742 |
computation can be avoided by always inserting into the reuse list |
| 1743 |
corresponding to one time increment past reuse eligibility. In cases |
| 1744 |
where the reuse lists have a longer "memory" than the "decay memory" |
| 1745 |
(described above), all of the routes in the first queue will be |
| 1746 |
available for immediate reuse if reachable or the history entry could |
| 1747 |
be disposed of if unreachable. |
| 1748 |
|
| 1749 |
When it is time to advance the lists, the first queue on the reuse |
| 1750 |
list must be processed and the circular queue must be rotated. Using |
| 1751 |
an array and an offset as a circular array (as described in <a href="#section-4.8.6">Section</a> |
| 1752 |
<a href="#section-4.8.6">4.8.6</a>), the algorithm below is repeated every delta-reuse seconds. |
| 1753 |
|
| 1754 |
1. save a pointer to the current zeroth queue head and zero the |
| 1755 |
list head entry |
| 1756 |
|
| 1757 |
2. set offset = modulo reuse-list-size ( offset + 1 ), thereby |
| 1758 |
rotating the circular queue of list-heads |
| 1759 |
|
| 1760 |
3. if ( the saved list head pointer is non-empty ) |
| 1761 |
|
| 1762 |
for each entry { |
| 1763 |
|
| 1764 |
sett-diff =t-now -t-updated |
| 1765 |
|
| 1766 |
set figure-of-merit =figure-of-merit *decay-array-ok [t-diff ] |
| 1767 |
|
| 1768 |
sett-updated =t-now |
| 1769 |
|
| 1770 |
if( figure-of-merit< reuse) |
| 1771 |
|
| 1772 |
reuse the route |
| 1773 |
|
| 1774 |
else |
| 1775 |
|
| 1776 |
re-insert into another list (see<a href="#section-4.8.6">Section 4.8.6</a>) |
| 1777 |
|
| 1778 |
} |
| 1779 |
|
| 1780 |
The value of the zeroth list head would be saved and the array entry |
| 1781 |
itself zeroed. The list heads would then be advanced by incrementing |
| 1782 |
the offset. Starting with the saved head of the old zeroth list, |
| 1783 |
each route would be reevaluated and used, disposed of entirely or |
| 1784 |
requeued if it were not ready for reuse. If a route is used, it must |
| 1785 |
|
| 1786 |
|
| 1787 |
|
| 1788 |
<span class="grey">Villamizar, et. al. Standards Track [Page 32]</span></pre> |
| 1789 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-33" ></span> |
| 1790 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 1791 |
|
| 1792 |
|
| 1793 |
be treated as if it were a new route advertisement as described in |
| 1794 |
<a href="#section-4.8.3">Section 4.8.3</a>. |
| 1795 |
|
| 1796 |
<span class="h2"><a class="selflink" id="section-5" href="#section-5">5</a> Implementation Experience</span> |
| 1797 |
|
| 1798 |
The first implementations of "route flap damping" were the route |
| 1799 |
server daemon (rsd) coding by Ramesh Govindan (ISI) and the Cisco IOS |
| 1800 |
implementation by Ravi Chandra. Both implementations first became |
| 1801 |
available in 1995 and have been used extensively. The rsd |
| 1802 |
implementation has been in use in route servers at the NSF funded |
| 1803 |
Network Access Points (NAPs) and at other major Internet |
| 1804 |
interconnects. The Cisco IOS version has been in use by Internet |
| 1805 |
Service Providers worldwide. The rsd implementation has been |
| 1806 |
integrated in releases of gated (see <a href="http://www.gated.org">http://www.gated.org</a>) and is |
| 1807 |
available in commercial routers using gated. |
| 1808 |
|
| 1809 |
There are now more than 2 years of BGP route damping deployment |
| 1810 |
experience. Some problems have occurred in deployment. So far these |
| 1811 |
are solvable by careful implementation of the algorithm and by |
| 1812 |
careful deployment. In some topologies coordinated deployment can be |
| 1813 |
helpful and in all cases disclosure of the use of route damping and |
| 1814 |
the parameters used is highly beneficial in debugging connectivity |
| 1815 |
problems. |
| 1816 |
|
| 1817 |
Some of the problems have occurred due to subtle implementation |
| 1818 |
errors. Route damping should never be applied on IBGP learned |
| 1819 |
routes. To do so can open the possibility for persistent route |
| 1820 |
loops. When IBGP routes within an AS are inconsistent, route loops |
| 1821 |
can easily form. Suppressing IBGP learned routes causes such |
| 1822 |
inconsistencies. Implementations should disallow configuration of |
| 1823 |
route damping on IBGP peers. |
| 1824 |
|
| 1825 |
Penalties for instability should only be applied when a route is |
| 1826 |
removed or replaced and not when a route is added. If damping |
| 1827 |
parameters are applied consistently, this implementation constraint |
| 1828 |
will result in a stable secondary path being preferred over an |
| 1829 |
unstable primary path due to damping of the primary path near the |
| 1830 |
source. |
| 1831 |
|
| 1832 |
In topologies where multiple AS paths to a given destination exist |
| 1833 |
flapping of the primary path can result in suppression of the |
| 1834 |
secondary path. This can occur if no damping is being done near the |
| 1835 |
cause of the route flap or if damping is being applied more |
| 1836 |
aggressively by a distant AS. This problem can be solved in one of |
| 1837 |
two ways. Damping can be done near the source of the route flap and |
| 1838 |
the damping parameters can be made consistent. Alternately, a |
| 1839 |
distant AS which insists on more aggressive damping parameters can |
| 1840 |
disable penalizing routes on AS path change, penalizing routes only |
| 1841 |
|
| 1842 |
|
| 1843 |
|
| 1844 |
<span class="grey">Villamizar, et. al. Standards Track [Page 33]</span></pre> |
| 1845 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-34" ></span> |
| 1846 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 1847 |
|
| 1848 |
|
| 1849 |
if they are withdrawn completely. In order to do so, the |
| 1850 |
implementation must support this option (as described in <a href="#section-4.4.3">Section</a> |
| 1851 |
<a href="#section-4.4.3">4.4.3</a>). |
| 1852 |
|
| 1853 |
Route flap should be damped near the source. Single homed |
| 1854 |
destinations can be covered by static routes. Aggregation provides |
| 1855 |
another means of damping. Providers should damp their own internal |
| 1856 |
problems, however damping on IGP link state origination is not yet |
| 1857 |
implemented by router vendors. Providers which use multiple AS |
| 1858 |
within their own topology should damp between their own AS. Providers |
| 1859 |
should damp adjacent providers AS. |
| 1860 |
|
| 1861 |
Damping provides a means to limit propagation excessive route change |
| 1862 |
when connectivity is highly intermittent. Once a problem is |
| 1863 |
corrected, damping state corresponding to the prefixes known to be |
| 1864 |
damped due to the problem just fixed can be manually cleared. In |
| 1865 |
order to determine where damping may have occurred after connectivity |
| 1866 |
problems, providers should publish their damping parameters. |
| 1867 |
Providers should be willing to manually clear damping on specific |
| 1868 |
prefixes or AS paths at the request of other providers when the |
| 1869 |
request is accompanied by credible assurance that the problem has |
| 1870 |
truly been addressed. |
| 1871 |
|
| 1872 |
By damping their own routing information, providers can reduce their |
| 1873 |
own need to make requests of other providers to clear damping state |
| 1874 |
after correcting a problem. Providers should be pro-active and |
| 1875 |
monitor what prefixes and paths are suppressed in addition to |
| 1876 |
monitoring link states and BGP session state. |
| 1877 |
|
| 1878 |
Acknowledgements |
| 1879 |
|
| 1880 |
This work and this document may not have been completed without the |
| 1881 |
advise, comments and encouragement of Yakov Rekhter (Cisco). Dennis |
| 1882 |
Ferguson (MCI) provided a description of the algorithms in the gated |
| 1883 |
BGP implementation and many valuable comments and insights. David |
| 1884 |
Bolen (ANS) and Jordan Becker (ANS) provided valuable comments, |
| 1885 |
particularly regarding early simulations. Over four years elapsed |
| 1886 |
between the initial draft presented to the BGP WG (October 1993) and |
| 1887 |
this iteration. At the time of this writing there is significant |
| 1888 |
experience with two implementations, each having been deployed since |
| 1889 |
1995. One was led by Ramesh Govindan (ISI) for the NSF Routing |
| 1890 |
Arbiter project. The second was led by Ravi Chandra (Cisco). Sean |
| 1891 |
Doran (Sprintlink) and Serpil Bayraktar (ANS) were among the early |
| 1892 |
independent testers of the Cisco pre-beta implementation. Valuable |
| 1893 |
comments and implementation feedback were shared by many individuals |
| 1894 |
on the IETF IDR WG and the RIPE Routing Work Group and in NANOG and |
| 1895 |
IEPG. |
| 1896 |
|
| 1897 |
|
| 1898 |
|
| 1899 |
|
| 1900 |
<span class="grey">Villamizar, et. al. Standards Track [Page 34]</span></pre> |
| 1901 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-35" ></span> |
| 1902 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 1903 |
|
| 1904 |
|
| 1905 |
Thanks also to Rob Coltun (Fore Systems), Sanjay Wadhwa (Fore), John |
| 1906 |
Scudder (IENG), Eric Bennet (IENG) and Jayesh Bhatt (Bay Networks) |
| 1907 |
for pointing out errors in the math uncovered during coding of more |
| 1908 |
recent implementations. These errors appeared in the details of the |
| 1909 |
implementation suggestion sections written after the first two |
| 1910 |
implementations were completed. Thanks also to Vern Paxson for a |
| 1911 |
very thorough review resulting in numerous clarifications to the |
| 1912 |
document. |
| 1913 |
|
| 1914 |
References |
| 1915 |
|
| 1916 |
[<a id="ref-1">1</a>] Gross, P., and Y. Rekhter, "Application of the border gateway |
| 1917 |
protocol in the internet", <a href="./rfc1268">RFC 1268</a>, October 1991. |
| 1918 |
|
| 1919 |
[<a id="ref-2">2</a>] ISO/IEC. Iso/iec 10747 - information technology - telecommuni- |
| 1920 |
cations and information exchange between systems - protocol for |
| 1921 |
exchange of inter-domain routeing information among intermediate |
| 1922 |
systems to support forwarding of iso 8473 pdus. Technical |
| 1923 |
report, International Organization for Standardization, August |
| 1924 |
1994. <a href="ftp://merit.edu/pub/iso/idrp.ps.gz">ftp://merit.edu/pub/iso/idrp.ps.gz</a>. |
| 1925 |
|
| 1926 |
[<a id="ref-3">3</a>] Lougheed, K., and Y. Rekhter, "A border gateway protocol 3 (BGP- |
| 1927 |
3)", <a href="./rfc1267">RFC 1267</a>, October 1991. |
| 1928 |
|
| 1929 |
[<a id="ref-4">4</a>] Rekhter, Y., and P. Gross, "Application of the border gateway |
| 1930 |
protocol in the internet", <a href="./rfc1772">RFC 1772</a>, March 1995. |
| 1931 |
|
| 1932 |
[<a id="ref-5">5</a>] Rekhter, Y., and T. Li, "A border gateway protocol 4 (BGP-4)", |
| 1933 |
<a href="./rfc1771">RFC 1771</a>, March 1995. |
| 1934 |
|
| 1935 |
[<a id="ref-6">6</a>] Rekhter, Y., and C. Topolcic,"Exchanging routing information |
| 1936 |
across provider boundaries in the CIDR environment", <a href="./rfc1520">RFC 1520</a>, |
| 1937 |
September 1993. |
| 1938 |
|
| 1939 |
[<a id="ref-7">7</a>] Traina, P., "BGP-4 protocol analysis", <a href="./rfc1774">RFC 1774</a>, March 1995. |
| 1940 |
|
| 1941 |
[<a id="ref-8">8</a>] Traina, P., "Experience with the BGP-4 protocol", <a href="./rfc1773">RFC 1773</a>, March |
| 1942 |
1995. |
| 1943 |
|
| 1944 |
Security Considerations |
| 1945 |
|
| 1946 |
The practices outlined in this document do not further weaken the |
| 1947 |
security of the routing protocols. Denial of service is possible in |
| 1948 |
an already insecure routing environment but these practices only |
| 1949 |
contribute to the persistence of such attacks and do not impact the |
| 1950 |
methods of prevention and the methods of determining the source. |
| 1951 |
|
| 1952 |
|
| 1953 |
|
| 1954 |
|
| 1955 |
|
| 1956 |
<span class="grey">Villamizar, et. al. Standards Track [Page 35]</span></pre> |
| 1957 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-36" ></span> |
| 1958 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 1959 |
|
| 1960 |
|
| 1961 |
Authors' Addresses |
| 1962 |
|
| 1963 |
Curtis Villamizar |
| 1964 |
ANS |
| 1965 |
|
| 1966 |
EMail: [email protected] |
| 1967 |
|
| 1968 |
|
| 1969 |
Ravi Chandra |
| 1970 |
Cisco Systems |
| 1971 |
|
| 1972 |
EMail: [email protected] |
| 1973 |
|
| 1974 |
|
| 1975 |
Ramesh Govindan |
| 1976 |
ISI |
| 1977 |
|
| 1978 |
EMail: [email protected] |
| 1979 |
|
| 1980 |
|
| 1981 |
|
| 1982 |
|
| 1983 |
|
| 1984 |
|
| 1985 |
|
| 1986 |
|
| 1987 |
|
| 1988 |
|
| 1989 |
|
| 1990 |
|
| 1991 |
|
| 1992 |
|
| 1993 |
|
| 1994 |
|
| 1995 |
|
| 1996 |
|
| 1997 |
|
| 1998 |
|
| 1999 |
|
| 2000 |
|
| 2001 |
|
| 2002 |
|
| 2003 |
|
| 2004 |
|
| 2005 |
|
| 2006 |
|
| 2007 |
|
| 2008 |
|
| 2009 |
|
| 2010 |
|
| 2011 |
|
| 2012 |
<span class="grey">Villamizar, et. al. Standards Track [Page 36]</span></pre> |
| 2013 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-37" ></span> |
| 2014 |
<span class="grey"><a href="./rfc2439">RFC 2439</a> BGP Route Flap Damping November 1998</span> |
| 2015 |
|
| 2016 |
|
| 2017 |
Full Copyright Statement |
| 2018 |
|
| 2019 |
Copyright (C) The Internet Society (1998). All Rights Reserved. |
| 2020 |
|
| 2021 |
This document and translations of it may be copied and furnished to |
| 2022 |
others, and derivative works that comment on or otherwise explain it |
| 2023 |
or assist in its implementation may be prepared, copied, published |
| 2024 |
and distributed, in whole or in part, without restriction of any |
| 2025 |
kind, provided that the above copyright notice and this paragraph are |
| 2026 |
included on all such copies and derivative works. However, this |
| 2027 |
document itself may not be modified in any way, such as by removing |
| 2028 |
the copyright notice or references to the Internet Society or other |
| 2029 |
Internet organizations, except as needed for the purpose of |
| 2030 |
developing Internet standards in which case the procedures for |
| 2031 |
copyrights defined in the Internet Standards process must be |
| 2032 |
followed, or as required to translate it into languages other than |
| 2033 |
English. |
| 2034 |
|
| 2035 |
The limited permissions granted above are perpetual and will not be |
| 2036 |
revoked by the Internet Society or its successors or assigns. |
| 2037 |
|
| 2038 |
This document and the information contained herein is provided on an |
| 2039 |
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING |
| 2040 |
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING |
| 2041 |
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION |
| 2042 |
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF |
| 2043 |
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. |
| 2044 |
|
| 2045 |
|
| 2046 |
|
| 2047 |
|
| 2048 |
|
| 2049 |
|
| 2050 |
|
| 2051 |
|
| 2052 |
|
| 2053 |
|
| 2054 |
|
| 2055 |
|
| 2056 |
|
| 2057 |
|
| 2058 |
|
| 2059 |
|
| 2060 |
|
| 2061 |
|
| 2062 |
|
| 2063 |
|
| 2064 |
|
| 2065 |
|
| 2066 |
|
| 2067 |
|
| 2068 |
Villamizar, et. al. Standards Track [Page 37] |
| 2069 |
</pre> |