Debian Codegraph @

rfc2439.html

raw
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="&quot;A border gateway protocol 4 (BGP-4)&quot;">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="&quot;Application of the border gateway protocol in the internet&quot;">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="&quot;A border gateway protocol 4 (BGP-4)&quot;">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 &gt;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 &lt; cut ) {
1535
1536 use the route
1537
1538 }else if( suppressed and figure-of-merit&lt; 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 &gt; 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 | | | | | | &lt;-- 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&lt; 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>