diff options
Diffstat (limited to 'doc/rfc/rfc2439.txt')
| -rw-r--r-- | doc/rfc/rfc2439.txt | 2075 |
1 files changed, 2075 insertions, 0 deletions
diff --git a/doc/rfc/rfc2439.txt b/doc/rfc/rfc2439.txt new file mode 100644 index 0000000..341e68f --- /dev/null +++ b/doc/rfc/rfc2439.txt @@ -0,0 +1,2075 @@ + + + + + + +Network Working Group C. Villamizar +Request for Comments: 2439 ANS +Category: Standards Track R. Chandra + Cisco + R. Govindan + ISI + November 1998 + + + BGP Route Flap Damping + +Status of this Memo + + This document specifies an Internet standards track protocol for the + Internet community, and requests discussion and suggestions for + improvements. Please refer to the current edition of the "Internet + Official Protocol Standards" (STD 1) for the standardization state + and status of this protocol. Distribution of this memo is unlimited. + +Copyright Notice + + Copyright (C) The Internet Society (1998). All Rights Reserved. + +Abstract + + A usage of the BGP routing protocol is described which is capable of + reducing the routing traffic passed on to routing peers and therefore + the load on these peers without adversely affecting route convergence + time for relatively stable routes. This technique has been + implemented in commercial products supporting BGP. The technique is + also applicable to IDRP. + + The overall goals are: + + o to provide a mechanism capable of reducing router processing load + caused by instability + + o in doing so prevent sustained routing oscillations + + o to do so without sacrificing route convergence time for generally + well behaved routes. + + This must be accomplished keeping other goals of BGP in mind: + + o pack changes into a small number of updates + + o preserve consistent routing + + + + +Villamizar, et. al. Standards Track [Page 1] + +RFC 2439 BGP Route Flap Damping November 1998 + + + o minimal addition space and computational overhead + + An excessive rate of update to the advertised reachability of a + subset of Internet prefixes has been widespread in the Internet. + This observation was made in the early 1990s by many people involved + in Internet operations and remains the case. These excessive updates + are not necessarily periodic so route oscillation would be a + misleading term. The informal term used to describe this effect is + "route flap". The techniques described here are now widely deployed + and are commonly referred to as "route flap damping". + +1 Overview + + To maintain scalability of a routed internet, it is necessary to + reduce the amount of change in routing state propagated by BGP in + order to limit processing requirements. The primary contributors of + processing load resulting from BGP updates are the BGP decision + process and adding and removing forwarding entries. + + Consider the following example. A widely deployed BGP implementation + may tend to fail due to high routing update volume. For example, it + may be unable to maintain it's BGP or IGP sessions if sufficiently + loaded. The failure of one router can further contribute to the load + on other routers. This additional load may cause failures in other + instances of the same implementation or other implementations with a + similar weakness. In the worst case, a stable oscillation could + result. Such worse cases have already been observed in practice. + + A BGP implementation must be prepared for a large volume of routing + traffic. A BGP implementation cannot rely upon the sender to + sufficiently shield it from route instabilities. The guidelines here + are designed to prevent sustained oscillations, but do not eliminate + the need for robust and efficient implementations. The mechanisms + described here allow routing instability to be contained at an AS + border router bordering the instability. + + Even where BGP implementations are highly robust, the performance of + the routing process is limited. Limiting the propagation of + unnecessary change then becomes an issue of maintaining reasonable + route change convergence time as a routing topology grows. + +2 Methods of Limiting Route Advertisement + + Two methods of controlling the frequency of route advertisement are + described here. The first involves fixed timers. The fixed timer + technique has no space overhead per route but has the disadvantage of + slowing route convergence for the normal case where a route does not + have a history of instability. The second method overcomes this + + + +Villamizar, et. al. Standards Track [Page 2] + +RFC 2439 BGP Route Flap Damping November 1998 + + + limitation at the expense of maintaining some additional space + overhead. The additional overhead includes a small amount of state + per route and a very small processing overhead. + + It is possible and desirable to combine both techniques. In + practice, fixed timers have been set to very short time intervals and + have proven useful to pack routes into a smaller number of updates + when routes arrive in separate updates. The BGP protocol refers to + this as packing Network Layer Reachability Information (NLRI) [5]. + + Seldom are fixed timers set to the tens of minutes to hours that + would be necessary to actually damp route flap. To do so would + produce the undesirable effect of severely limiting routing + convergence. + +2.1 Existing Fixed Timer Recommendations + + BGP-3 does not make specific recommendations in this area [1]. The + short section entitled "Frequency of Route Selection" simply + recommends that something be done and makes broad statements + regarding certain properties that are desirable or undesirable. + + BGP4 retains the "Frequency of Route Advertisement" section and adds + a "Frequency of Route Origination" section. BGP-4 describes a method + of limiting route advertisement involving a fixed (configurable) + MinRouteAdvertisementInterval timer and fixed + MinASOriginationInterval timer [5]. The recommended timer values of + MinRouteAdvertisementInterval is 30 seconds and + MinASOriginationInterval is 15 seconds. + +2.2 Desirable Properties of Damping Algorithms + + Before describing damping algorithms the objectives need to be + clearly defined. Some key properties are examined to clarify the + design rationale. + + The overall objective is to reduce the route update load without + limiting convergence time for well behaved routes. To accomplish + this, criteria must be defined for well behaved and poorly behaved + routes. An algorithm must be defined which allows poorly behaved + routes to be identified. Ideally, this measure would be a prediction + of the future stability of a route. + + Any delay in propagation of well behaved routes should be minimal. + Some delay is tolerable to support better packing of updates. Delay + of poorly behave routes should, if possible, be proportional to a + measure of the expected future instability of the route. Delay in + propagating an unstable route should cause the unstable route to be + + + +Villamizar, et. al. Standards Track [Page 3] + +RFC 2439 BGP Route Flap Damping November 1998 + + + suppressed until there is some degree of confidence that the route + has stabilized. + + If a large number of route changes are received in separate updates + over some very short period of time and these updates have the + potential to be combined into a single update then these should be + packed as efficiently as possible before propagating further. Some + small delay in propagating well behaved routes is tolerable and is + necessary to allow better packing of updates. + + Where routes are unstable, use and announcement of the routes should + be suppressed rather than suppressing their removal. Where one route + to a destination is stable, and another route to the same destination + is somewhat unstable, if possible, the unstable route should be + suppressed more aggressively than if there were no alternate path. + + Routing consistency within an AS is very important. Only very + minimal delay of internal BGP (IBGP) should be done. Routing + consistency across AS boundaries is also very important. It is + highly undesirable to advertise a route that is different from the + route that is being used, except for a very minimal time. It is more + desirable to suppress the acceptance of a route (and therefore the + use of that route in the IGP) rather than suppress only the + redistribution. + + It is clearly not possible to accurately predict the future stability + of a route. The recent history of stability is generally regarded as + a good basis for estimating the likelihood of future stability. The + criteria that is used to distinguish well behaved from poorly behaved + routes is therefore based on the recent history of stability of the + route. There is no simple quantitative expression of recent + stability so a figure of merit must be defined. Some desirable + characteristics of this figure of merit would be that the farther in + the past that instability occurred, the less it's affect on the + figure of merit and that the instability measure would be cumulative + rather than reflecting only the most recent event. + + The algorithms should behave such that for routes which have a + history of stability but make a few transitions, those transitions + should be made quickly. If transitions continue, advertisement of + the route should be suppressed. There should be some memory of prior + instability. The degree to which prior instability is considered + should be gradually reduced as long as the route remains announced + and stable. + + + + + + + +Villamizar, et. al. Standards Track [Page 4] + +RFC 2439 BGP Route Flap Damping November 1998 + + +2.3 Design Choices + + After routes have been accepted their readvertisement will be briefly + suppressed to improve packing of updates. There may be a lengthy + suppression of the acceptance of an external route. How long a route + will be suppressed is based on a figure of merit that is expected to + be correlated to the probability of future instability of a route. + Routes with high figure of merit values will be suppressed. An + exponential decay algorithm was chosen as the basis for reducing the + figure of merit over time. These choices should be viewed as + suggestions for implementation. + + An exponential decay function has the property that previous + instability can be remembered for a fairly long time. The rate at + which the instability figure of merit decays slows as time goes on. + Exponential decay has the following property. + + f(f(figure-of-merit, t1), t2) = f(figure-of-merit, t1+t2) + + This property allows the decay for a long period to be computed in a + single operation regardless of the current value (figure-of-merit). + As a performance optimization, the decay can be applied in fixed time + increments. Given a desired decay half life, the decay for a single + time increment can be computed ahead of time. The decay for multiple + time increments is expressed below. + + f(figure-of-merit, n*t0) = f(figure-of-merit, t0)**n = K**n + + The values of K ** n can be precomputed for a reasonable number of + "n" and stored in an array. The value of "K" is always less than + one. The array size can be bounded since the value quickly + approaches zero. This makes the decay easy to compute using an array + bound check, an array lookup and a single multiply regardless as to + how much time has elapsed. + +3 Limiting Route Advertisements using Fixed Timers + + This method of limiting route advertisements involves the use of + fixed timers applied to the process of sending routes. It's primary + purpose is to improve the packing of routes in BGP update messages. + The delay in advertising a stable route should be bounded and + minimal. The delay in advertising an unreachable need not be zero, + but should also be bounded and should probably have a separate bound + set less than or equal to the bound for a reachable advertisement. + + The BGP protocol defines the use of a Routing Information Base (RIB). + Routes that need to be readvertised can be marked in the RIB or an + external set of structures maintained, which references the RIB. + + + +Villamizar, et. al. Standards Track [Page 5] + +RFC 2439 BGP Route Flap Damping November 1998 + + + Periodically, a subset of the marked routes can be flushed. This is + fairly straightforward and accomplishes the objectives. Computation + for too simple an implementation may be order N squared. To avoid N + squared performance, some form of data structure is needed to group + routes with common attributes. + + An implementation should pack updates efficiently, provide a minimum + readvertisement delay, provide a bounds on the maximum + readvertisement delay that would be experienced solely as a result of + the algorithm used to provide a minimum delay, and must be + computationally efficient in the presence of a very large number of + candidates for readvertisement. + +4 Stability Sensitive Suppression of Route Advertisement + + This method of limiting route advertisements uses a measure of route + stability applied on a per route basis. This technique is applied + when receiving updates from external peers only (EBGP). Applying this + technique to IBGP learned routes or to advertisement to IBGP or EBGP + peers after making a route selection can result in routing loops. + + A figure of merit based on a measure of instability is maintained on + a per route basis. This figure of merit is used in the decision to + suppress the use of the route. Routes with high figure of merit are + suppressed. Each time a route is withdrawn, the figure of merit is + incremented. While the route is not changing the figure of merit + value is decayed exponentially with separate decay rates depending on + whether the route is stable and reachable or has been stable and + unreachable. The decay rate may be slower when the route is + unreachable, or the stability figure of merit could remain fixed (not + decay at all) while the route remains unreachable. Whether to decay + unreachable routes at the same rate, a slower rate, or not at all is + an implementation choice. Decaying at a slower rate is recommended. + + A very efficient implementation is suggested in the following + sections. The implementation only requires computation for the + routes contained in an update, when an update is received or + withdrawn (as opposed to the simplistic approach of periodically + decaying each route). The suggested implementation involves only a + small number of simple operations, and can be implemented using + scaled integers. + + The behavior of unstable routes is fairly predictable. Severely + flapping routes will often be advertised and withdrawn at regular + time intervals corresponding to the timers of a particular protocol + (the IGP or exterior protocol in use where the problem exists). + Marginal circuits or mild congestion can result in a long term + pattern of occasional brief route withdrawal or occasional brief + + + +Villamizar, et. al. Standards Track [Page 6] + +RFC 2439 BGP Route Flap Damping November 1998 + + + connectivity. + +4.1 Single vs. Multiple Configuration Parameter Sets + + The behavior of the algorithm is modified by a number of configurable + parameters. It is possible to configure separate sets of parameters + designed to handle short term severe route flap and chronic milder + route flap (a pattern of occasional drops over a long time period). + The former would require a fast decay and low threshold (allowing a + small number of consecutive flaps to cause a route to be suppressed, + but allowing it to be reused after a relatively short period of + stability). The latter would require a very slow decay and a higher + threshold and might be appropriate for routes for which there was an + alternate path of similar bandwidth. + + It may also be desirable to configure different thresholds for routes + with roughly equivalent alternate paths than for routes where the + alternate paths have a lower bandwidth or tend to be congested. This + can be solved by associating a different set of parameters with + different ranges of preference values. Parameter selection could be + based on BGP LOCAL_PREF. + + Parameter selection could also be based on whether an alternate route + was known. A route would be considered if, for any applicable + parameter set, an alternate route with the specified preference value + existed and the figure of merit associated with the parameter set did + not indicate a need to suppress the route. A less aggressive + suppression would be applied to the case where no alternate route at + all existed. In the simplest case, a more aggressive suppression + would be applied if any alternate route existed. Only the highest + preference (most preferred) value needs to be specified, since the + ranges may overlap. + + It might also be desirable to configure a different set of thresholds + for routes which rely on switched services and may disconnect at + times to reduce connect charges. Such routes might be expected to + change state somewhat more often, but should be suppressed if + continuous state changes indicate instability. + + While not essential, it might be desirable to be able to configure + multiple sets of configuration parameters per route. It may also be + desirable to be able to configure sets of parameters that only + correspond to a set of routes (identified by AS path, peer router, + specific destinations or other means). Experience may dictate how + much flexibility is needed and how to best to set the parameters. + Whether to allow different damping parameter sets for different + routes, and whether to allow multiple figures of merit per route is + an implementation choice. + + + +Villamizar, et. al. Standards Track [Page 7] + +RFC 2439 BGP Route Flap Damping November 1998 + + + Parameter selection can also be based on prefix length. The + rationale is that longer prefixes tend to reach less end systems and + are less important and these less important prefixes can be damped + more aggressively. This technique is in fairly widespread use. + Small sites or those with dense address allocation who are multihomed + are often reachable by long prefixes which are not easily aggregated. + These sites tend to dispute the choice of prefix length for parameter + selection. Advocates of the technique point out that it encourages + better aggregation. + +4.2 Configuration Parameters + + At configuration time, a number of parameters may be specified by the + user. The configuration parameters are expressed in units meaningful + to the user. These differ from the parameters used at run time which + are in unit convenient for computation. The run time parameters are + derived from the configuration parameters. Suggested configuration + parameters are listed below. + + cutoff threshold (cut) + + This value is expressed as a number of route withdrawals. It is + the value above which a route advertisement will be suppressed. + + reuse threshold (reuse) + + This value is expressed as a number of route withdrawals. It is + the value below which a suppressed route will now be used again. + + maximum hold down time (T-hold) + + This value is the maximum time a route can be suppressed no + matter how unstable it has been prior to this period of + stability. + + decay half life while reachable (decay-ok) + + This value is the time duration in minutes or seconds during + which the accumulated stability figure of merit will be reduced + by half if the route if considered reachable (whether suppressed + or not). + + decay half life while unreachable (decay-ng) + + This value is the time duration in minutes or seconds during + which the accumulated stability figure of merit will be reduced + by half if the route if considered unreachable. If not + specified or set to zero, no decay will occur while a route + + + +Villamizar, et. al. Standards Track [Page 8] + +RFC 2439 BGP Route Flap Damping November 1998 + + + remains unreachable. + + decay memory limit (Tmax-ok or Tmax-ng) + + This is the maximum time that any memory of previous instability + will be retained given that the route's state remains unchanged, + whether reachable or unreachable. This parameter is generally + used to determine array sizes. + + There may be multiple sets of the parameters above as described in + Section 4.1. The configuration parameters listed below would be + applied system wide. These include the time granularity of all + computations, and the parameters used to control reevaluation of + routes that have previously been suppressed. + + time granularity (delta-t) + + This is the time granularity in seconds used to perform all + decay computations. + + reuse list time granularity (delta-reuse) + + This is the time interval between evaluations of the reuse + lists. Each reuse lists corresponds to an additional time + increment. + + reuse list memory reuse-list-max + + This is the time value corresponding to the last reuse list. + This may be the maximum value of T-hold for all parameter sets + of may be configured. + + number of reuse lists (reuse-list-size) + + This is the number of reuse lists. It may be determined from + reuse-list-max or set explicitly. + + A recommended optimization is described in Section 4.8.6 that + involves an array referred to as the "reuse index array". A reuse + index array is needed for each decay rate in use. The reuse index + array is used to estimate which reuse list to place a route when it + is suppressed. Proper placement avoids the need to periodically + evaluate decay to determine if a route can be reused or when storage + can be recovered. Using the reuse index array avoids the need to + compute a logarithm to determine placement. One additional system + wide parameter can be introduced. + + + + + +Villamizar, et. al. Standards Track [Page 9] + +RFC 2439 BGP Route Flap Damping November 1998 + + + reuse index array size (reuse-index-array-size) + + This is the size of reuse index arrays. This size determines + the accuracy with which suppressed routes can be placed within + the set of reuse lists when suppressed for a long time. + +4.3 Guidelines for Setting Parameters + + The decay half life should be set to a time considerably longer than + the period of the route flap it is intended to address. For example, + if the decay is set to ten minutes and a route is withdrawn and + readvertised exactly every ten minutes, the route would continue to + flap if the cutoff was set to a value of 2 or above. + + The stability figure of merit itself is an accumulated time decayed + total. This must be kept in mind in setting the decay time, cutoff + values and reuse values. The figure of merit is increased each time + a route transitions from reachable to unreachable. The figure of + merit is decayed at a rate proportional to its current value. + Increasing the rate of route flap therefore increments the figure of + merit more often and reaches a given threshhold in a shorter amount + of time. When the response to a constant rate route flap is plotted + this looks like a sawtooth with an abrupt rising edge and a decaying + falling edge. Since the absolute decay amount is proportional to the + figure of merit, at a continuous constant flap rate the baseline of + the sawtooth will tend to stop rising and converge if not clipped by + a ceiling value. + + If clipped by a ceiling value, the sawtooth baseline will simply + reach the ceiling faster at a higher rate of route flap. For + example, if flapping at four times the decay rate the following + progression occurs. When the route becomes unreachable the first + time the value becomes 1. When the next flap occurs, one is added to + the previous value, which has been decreased by the fourth root of 2 + (the amount of decay that would occur in 1/4 of the half life time if + decay is exponential). The sequence is 1, 1.84, 2.55, 3.14, 3.64, + 4.06, 4.42, 4.71, 4.96, 5.17, ..., converging at about 6.285. If a + route flaps at four times the decay rate, it will reach 3 in 4 + cycles, 4 in 6 cycles, 5 in 10 cycles, and will converge at about + 6.3. At twice the decay time, it will reach 3 in 7 cycles, and + converge at a value of less than 3.5. + + Figure 1 shows the stability figure of merit for route flap at a + constant rate. The time axis is labeled in multiples of the decay + half life. The plots represent route flap with a period of 1/2, 1/3, + 1/4, and 1/8 times the decay half life. A ceiling of 4.5 was set, + which can be seen to affect three of the plots, effectively limiting + the time it takes to readvertise the route regardless of the prior + + + +Villamizar, et. al. Standards Track [Page 10] + +RFC 2439 BGP Route Flap Damping November 1998 + + + history. With cutoff and reuse thresholds of 1.5 and 0.75, routes + would be suppressed after being declared unreachable 2-3 times and be + used again after approximately 2 decay half life periods of + stability. + + This function can be expressed formally. Reachability of a route can + be represented by a variable "R" with possible values of 0 and 1 + representing unreachable and reachable. At a discrete time R can + only have one value. The figure of merit is increased by 1 at each + transition from R=1 to R=0 and clipped to a ceiling value. The decay + in figure of merit can then be expressed over a set of discrete times + as follows. + + figure-of-merit(t) = K * figure-of-merit(t - delta-t) + K = K1 for R=0 K=K2 for R=1 + + The four plots are presented vertically. Due to space limitations, + only a limited set of points along the time axis are shown. The + value of the figure of merit is given. Along side each value is a + very low resolution strip chart made up of ASCII dots. This is just + intended to give a rough feel for the rise and fall of the values. + The strip charts are not displayed on an overlapping set of axes + because the sawtooth waveforms cross each other quite frequently. At + the very low resolution of these plots, the rise and fall of the + baseline is evident, but the sawtooth nature is only observed in the + printed value. + + From the maximum hold time value (T-hold), a ratio of the reuse value + to a ceiling can be determined. An integer value for the ceiling can + then be chosen such that overflow will not be a problem and all other + values can be scaled accordingly. If both cutoffs are specified or + if multiple parameter sets are used the highest ceiling will be used. + + + + + + + + + + + + + + + + + + + +Villamizar, et. al. Standards Track [Page 11] + +RFC 2439 BGP Route Flap Damping November 1998 + + + time figure-of-merit as a function of time (in minutes) + + 0.00 0.000 . 0.000 . 0.000 . 0.000 . + 0.08 0.000 . 0.000 . 0.000 . 0.000 . + 0.16 0.000 . 0.000 . 0.000 . 0.973 . + 0.24 0.000 . 0.000 . 0.000 . 0.920 . + 0.32 0.000 . 0.000 . 0.946 . 1.817 . + 0.40 0.000 . 0.953 . 0.895 . 2.698 . + 0.48 0.000 . 0.901 . 0.847 . 2.552 . + 0.56 0.953 . 0.853 . 1.754 . 3.367 . + 0.64 0.901 . 0.807 . 1.659 . 4.172 . + 0.72 0.853 . 1.722 . 1.570 . 3.947 . + 0.80 0.807 . 1.629 . 2.444 . 4.317 . + 0.88 0.763 . 1.542 . 2.312 . 4.469 . + 0.96 0.722 . 1.458 . 2.188 . 4.228 . + 1.04 1.649 . 2.346 . 3.036 . 4.347 . + 1.12 1.560 . 2.219 . 2.872 . 4.112 . + 1.20 1.476 . 2.099 . 2.717 . 4.257 . + 1.28 1.396 . 1.986 . 3.543 . 4.377 . + 1.36 1.321 . 2.858 . 3.352 . 4.141 . + 1.44 1.250 . 2.704 . 3.171 . 4.287 . + 1.52 2.162 . 2.558 . 3.979 . 4.407 . + 1.60 2.045 . 2.420 . 3.765 . 4.170 . + 1.68 1.935 . 3.276 . 3.562 . 4.317 . + 1.76 1.830 . 3.099 . 4.356 . 4.438 . + 1.84 1.732 . 2.932 . 4.121 . 4.199 . + 1.92 1.638 . 2.774 . 3.899 . 3.972 . + 2.00 1.550 . 2.624 . 3.688 . 3.758 . + 2.08 1.466 . 2.483 . 3.489 . 3.555 . + 2.16 1.387 . 2.349 . 3.301 . 3.363 . + 2.24 1.312 . 2.222 . 3.123 . 3.182 . + 2.32 1.242 . 2.102 . 2.955 . 3.010 . + 2.40 1.175 . 1.989 . 2.795 . 2.848 . + 2.48 1.111 . 1.882 . 2.644 . 2.694 . + 2.56 1.051 . 1.780 . 2.502 . 2.549 . + 2.64 0.995 . 1.684 . 2.367 . 2.411 . + 2.72 0.941 . 1.593 . 2.239 . 2.281 . + 2.80 0.890 . 1.507 . 2.118 . 2.158 . + 2.88 0.842 . 1.426 . 2.004 . 2.042 . + 2.96 0.797 . 1.349 . 1.896 . 1.932 . + 3.04 0.754 . 1.276 . 1.794 . 1.828 . + 3.12 0.713 . 1.207 . 1.697 . 1.729 . + 3.20 0.675 . 1.142 . 1.605 . 1.636 . + 3.28 0.638 . 1.081 . 1.519 . 1.547 . + 3.36 0.604 . 1.022 . 1.437 . 1.464 . + 3.44 0.571 . 0.967 . 1.359 . 1.385 . + + Figure 1: Instability figure of merit for flap at a constant rate + + + +Villamizar, et. al. Standards Track [Page 12] + +RFC 2439 BGP Route Flap Damping November 1998 + + + time figure-of-merit as a function of time (in minutes) + + 0.00 0.000 . 0.000 . 0.000 . + 0.20 0.000 . 0.000 . 0.000 . + 0.40 0.000 . 0.000 . 0.000 . + 0.60 0.000 . 0.000 . 0.000 . + 0.80 0.000 . 0.000 . 0.000 . + 1.00 0.999 . 0.999 . 0.999 . + 1.20 0.971 . 0.971 . 0.929 . + 1.40 0.945 . 0.945 . 0.809 . + 1.60 0.919 . 0.865 . 0.704 . + 1.80 0.894 . 0.753 . 0.613 . + 2.00 1.812 . 1.657 . 1.535 . + 2.20 1.762 . 1.612 . 1.428 . + 2.40 1.714 . 1.568 . 1.244 . + 2.60 1.667 . 1.443 . 1.083 . + 2.80 1.622 . 1.256 . 0.942 . + 3.00 1.468 . 1.094 . 0.820 . + 3.20 2.400 . 2.036 . 1.694 . + 3.40 2.335 . 1.981 . 1.475 . + 3.60 2.271 . 1.823 . 1.284 . + 3.80 2.209 . 1.587 . 1.118 . + 4.00 1.999 . 1.381 . 0.973 . + 4.20 2.625 . 2.084 . 1.727 . + 4.40 2.285 . 1.815 . 1.503 . + 4.60 1.990 . 1.580 . 1.309 . + 4.80 1.732 . 1.375 . 1.139 . + 5.00 1.508 . 1.197 . 0.992 . + 5.20 1.313 . 1.042 . 0.864 . + 5.40 1.143 . 0.907 . 0.752 . + 5.60 0.995 . 0.790 . 0.654 . + 5.80 0.866 . 0.688 . 0.570 . + 6.00 0.754 . 0.599 . 0.496 . + 6.20 0.656 . 0.521 . 0.432 . + 6.40 0.571 . 0.454 . 0.376 . + 6.60 0.497 . 0.395 . 0.327 . + 6.80 0.433 . 0.344 . 0.285 . + 7.00 0.377 . 0.299 . 0.248 . + 7.20 0.328 . 0.261 . 0.216 . + 7.40 0.286 . 0.227 . 0.188 . + 7.60 0.249 . 0.197 . 0.164 . + 7.80 0.216 . 0.172 . 0.142 . + 8.00 0.188 . 0.150 . 0.124 . + + Figure 2: Separate decay constants when unreachable + + + + + + +Villamizar, et. al. Standards Track [Page 13] + +RFC 2439 BGP Route Flap Damping November 1998 + + + Figure 2 shows the effect of configuring separate decay rates to be + used when the route is reachable or unreachable. The decay rate is 5 + times slower when the route is unreachable. In the three case shown, + the period of the route flap is equal to the decay half life but the + route is reachable 1/8 of the time in one, reachable 1/2 the time in + one, and reachable 7/8 of the time in the other. In the last case + the route is not suppressed until after the third unreachable (when + it is above the top threshold after becoming reachable again). + + The main point of Figure 2 is to show the effect of changing the duty + cycle of the square wave in the variable "R" for a fixed frequency of + the square wave. If the decay constants are chosen such that decay + is slower when R=0 (the route is unreachable), then the figure of + merit rises more slowly (more accurately, the baseline of the + sawtooth waveform rises more slowly) if the route is reachable a + larger percentage of the time. The effect when the route becomes + persistently reachable again can be fairly negligible if the sawtooth + is clipped by a ceiling value, but is more significant if a slow + route flap rate or short interval of route flapping is such that the + sawtooth does not reach the ceiling value. In Figure 2 the interval + in which the routes are unstable is short enough that the ceiling + value is not reached, therefore, the routes that are reachable for a + greater percentage of the route flap cycle are reused (placed in the + RIB and advertised to peers) sooner than others after the route + becomes stable again ("R" becomes 1, indicating the announced state + goes to reachable and remains there). + + In both Figure 1 and Figure 2, routes would be suppressed. Routes + flapping at the decay half life or less would be withdrawn two or + three times and then remain withdrawn until they had remained stably + announced and stable for on the order of 1 1/2 to 2 1/2 times the + decay half life (given the ceiling in the example). + + The purpose of damping BGP route flap is to reduce the processor + burden at the immediate router and the processor burden to downstream + routers (BGP peer routers and peers of peers that will see the route + announcements advertised by the immediate router). Computing a + figure of merit at each discrete time interval using figure-of- + merit(t) = K * figure-of-merit(t - delta-t) would be very inefficient + and defeat the purpose. This problem is addressed by defering + computation as long as possible and doing a single simple computation + to compensate for the decay during the time that has elapsed since + the figure of merit was last updated. The use of decay arrays + provides the single simple calculation. The use of reuse lists + (described later) provide a means to defer calculations. A route + becomes usable if there was not further change for a period of time + and the route is unreachable. The data structure storage is + recovered if the route's state has not changed for a period of time + + + +Villamizar, et. al. Standards Track [Page 14] + +RFC 2439 BGP Route Flap Damping November 1998 + + + and it has been unreachable. The reuse arrays provide a means to + estimate how long a computation can be deferred if there is no + further change. + + A larger time granularity will keep table storage down. The time + granularity should be less than a minimal reasonable time between + expected worse case route flaps. It might be reasonable to fix this + parameter at compile time or set a default and strongly recommend + that the user leave it alone. With an exponential decay, array size + can be greatly reduced by setting a period of complete stability + after which the decayed total will be considered zero rather than + retaining a tiny quantity. Alternately, very long decays can be + implemented by multiplying more than once if array bounds are + exceeded. + + The reuse lists hold suppressed routes grouped according to how long + it will be before the routes are eligible for reuse. Periodically + each list will be advanced by one position and one list removed as + described in Section 4.8.7. All of the suppressed routes in the + removed list will be reevaluated and either used or placed in another + list according to how much additional time must elapse before the + route can be reused. The last list will always contain all the + routes which will not be advertised for more time than is appropriate + for the remaining list heads. When the last list advances to the + front, some of the routes will not be ready to be used and will have + to be requeued. The time interval for reconsidering suppressed + routes and number of list heads should be configurable. Reasonable + defaults might be 30 seconds and 64 list heads. A route suppressed + for a long time would need to be reevaluated every 32 minutes. + +4.4 Run Time Data Structures + + A fixed small amount of per system storage will be required. Where + sets of multiple configuration parameters are used, storage will be + required per set of parameters. A small amount of per route storage + is required. A set of list heads is needed. These list heads are + used to arrange suppressed routes according to the time remaining + until they can be reused. + + A separate reuse list can be used to hold unreachable routes for the + purpose of later recovering storage if they remain unreachable too + long. This might be more accurately described as a recycling list. + The advantage this would provide is making free data structures + available as soon as possible. Alternately, the data structures can + simply be placed on a queue and the storage recovered when the route + hits the front of the queue and if storage is needed. The latter is + less optimal but simple. + + + + +Villamizar, et. al. Standards Track [Page 15] + +RFC 2439 BGP Route Flap Damping November 1998 + + + If multiple sets of configuration parameters are allowed per route, + there is a need for some means of associating more than one figure of + merit and set of parameters with each route. Building a linked list + of these objects seems like one of a number of reasonable + implementations. Similarly, a means of associating a route to a + reuse list is required. A small overhead will be required for the + pointers needed to implement whatever data structure is chosen for + the reuse lists. The suggested implementation uses a double linked + lists and so requires two pointers per figure of merit. + + Each set of configuration parameters can reference decay arrays and + reuse arrays. These arrays should be shared among multiple sets of + parameters since their storage requirement is not negligible. There + will be only one set of reuse list heads for the entire router. + +4.4.1 Data Structures for Configuration Parameter Sets + + Based on the configuration parameters described in the previous + section, the following values can be computed as scaled integers + directly from the corresponding configuration parameters. + + o decay array scale factor (decay-array-scale-factor) + + o cutoff value (cut) + + o reuse value (reuse) + + o figure of merit ceiling (ceiling) + + Each configuration parameter set will reference one or two decay + arrays and one or two reuse arrays. Only one array will be needed if + the decay rate is the same while a route is unreachable as while it + is reachable, or if the stability figure of merit does not decay + while a route is unreachable. + +4.4.2 Data Structures per Decay Array and Reuse Index Array + + The following are also computed from the configuration parameters + though not as directly. The computation is described in Section 4.5. + + o decay rate per tick (decay-delta-t) + + o decay array size (decay-array-size) + + o decay array (decay[]) + + o reuse index array size (reuse-index-array-size) + + + + +Villamizar, et. al. Standards Track [Page 16] + +RFC 2439 BGP Route Flap Damping November 1998 + + + o reuse index array (reuse-index-array[]) + + For each decay rate specified, an array will be used to store the + value of a computed parameter raised to the power of the index of + each array element. This is to speed computations. The decay rate + per tick is an intermediate value expressed as a real number and used + to compute the values stored in the decay arrays. The array size is + computed from the decay memory limit configuration parameter + expressed as an array size or as a maximum hold time. + + The decay array size must be of sufficient size to accommodate the + specified decay memory given the time granularity, or sufficient to + hold the number of array elements until integer rounding produces a + zero result if that value is smaller, or a implementation imposed + reasonable size to prevent configurations which use excessive memory. + Implementations may chose to make the array size shorter and multiply + more than once when decaying a long time interval to reduce storage. + + The reuse index arrays serve a similar purpose to the decay arrays. + In BGP, a route is said to be "used" if it is considered the best + route. In this context, if the route is "used" it is placed in the + RIB and is eligible for advertisement to BGP peers. If a route is + withdrawn (a BGP announcement is made by a peer indicating that it is + no longer reachable), then it is no longer eligible for "use". When + a route becomes reachable it may not be "used" immediately if the + figure of merit indicates that a recent instability has occurred. + After the route remains stable and the figure of merit decays below + the "reuse" threshhold, the route is said to be eligible to be + "reused" (treated as truly reachable, placed in the RIB and + advertised to peers). The amount of time until a route can be reused + can be determined using a array lookup. The array can be built given + the decay rate. The array is indexed using a scaled integer + proportional to the ratio between a current stability figure of merit + value and the value needed for the route to be reused. + +4.4.3 Per Route State + + Information must be maintained per some tuple representing a route. + At the very minimum, the NLRI (BGP prefix and length) must be + contained in the tuple. Different BGP attributes may be included or + excluded depending on the specific situation. The AS path should + also be contained in the tuple by default. The tuple may also + optionally contain other BGP attributes such as + MULTI_EXIT_DISCRIMINATOR (MED). + + The tuple representing a route for the purpose of route flap damping + is: + + + + +Villamizar, et. al. Standards Track [Page 17] + +RFC 2439 BGP Route Flap Damping November 1998 + + + tuple entry default options + ------------------------------------------- + NLRI + prefix required + length required + AS path included option to exclude + last AS set in path excluded option to include + next hop excluded option to include + MED excluded option to include + in comparisons only + + The AS path is generally included in order to identify downstream + instability which is not being damped or not being sufficiently + damped and is alternating between a stable and an unstable path. + Under rare circumstances it may be desirable to exclude AS path for + all or a subset of prefixes. If an AS path ends in an AS set, in + practice the path is always for an aggregate. Changes to the + trailing AS set should be ignored. Ideally the AS path comparison + should insure that at least one AS has remained constant in the old + and new AS set, but completely ignoring the contents of a trailing AS + set is also acceptable. + + Including next hop and MED changes can help suppress the use of an AS + which is internally unstable or avoid a next hop which is closer to + an unstable IGP path in the adjacent AS. If a large number of MED + values are used, the increase in the amount of state may become a + problem. For this reason MED is disabled by default and enabled only + as part of the tuple comparison, using a single state entry + regardless of MED value. Including MED will suppress the use of the + adjacent AS even though the change need not be propagated further. + Using MED is only a safe practice if a path is known to exist through + another AS or where there are enough peering sites with the adjacent + AS such that routes heard at only a subset of the peering sites will + be suppressed. + +4.4.4 Data Structures per Route + + The following information must be maintained per route. A route here + is considered to be a tuple usually containing NLRI, next hop, and AS + path as defined in Section 4.4.3. + + stability figure of merit (figure-of-merit) + + Each route must have a stability figure of merit per applicable + parameter set. + + last time updated (time-update) + + + + +Villamizar, et. al. Standards Track [Page 18] + +RFC 2439 BGP Route Flap Damping November 1998 + + + The exact last time updated must be maintained to allow + exponential decay of the accumulated figure of merit to be + deferred until the route might reasonable be considered eligible + for a change in status (having gone from unreachable to + reachable or advancing within the reuse lists). + + config block pointer + + Any implementation that supports multiple parameter sets must + provide a means of quickly identifying which set of parameters + corresponds to the route currently being considered. For + implementations supporting only parameter sets where all routes + must be treated the same, this pointer is not required. + + reuse list traversal pointers + + If doubly linked lists are used to implement reuse lists, then + two pointers will be needed, previous and next. Generally there + is a double linked list which is unused when a route is + suppressed from use that can be used for reuse list traversal + eliminating the need for additional pointer storage. + +4.5 Processing Configuration Parameters + + From the configuration parameters, it is possible to precompute + a number of values that will be used repeatedly and retain these + to speed later computations that will be required frequently. + + Scaling is usually dependent on the highest value that figure- + of-merit can attain, referred to here as the ceiling. The real + number value of the ceiling will typically be determined by the + following equation. The ceiling can also be configured to a + specific value, which in turn dictates T-hold. + + ceiling = reuse * (exp(T-hold/decay-half-life) * log(2)) + + In the above equation, reuse is the reuse threshhold described + in Section 4.2. + + The methods of scaled integer arithmetic are not described in + detail here. The methods of determining the real values are + given. Translation into scaled integer values and the details + of scaled integer arithmetic are left up to the individual + implementations. + + The ceiling value can be set to be the largest integer that can fit + in half the bits available for an unsigned integer. This will + allow the scaled integers to be multiplied by the scaled decay + + + +Villamizar, et. al. Standards Track [Page 19] + +RFC 2439 BGP Route Flap Damping November 1998 + + + value and then shifted down. Implementations may prefer to use + real numbers or may use any integer scaling deemed appropriate for + their architecture. + + penalty value and thresholds (as proportional scaled integers) + + The figure of merit penalty for one route withdrawal and the + cutoff values must be scaled according to the above scaling + factor. + + decay rate per tick (decay[1]) + + The decay value per increment of time as defined by the time + granularity must be determined (at least initially as a floating + point number). The per tick decay is a number slightly less + than one. It is the Nth root of the one half where N is the + half life divided by the time granularity. + + decay[1] = exp ((1 / (decay-half-life/delta-t)) * log (1/2)) + + decay array size (decay-array-size) + + The decay array size is the decay memory divided by the time + granularity. If integer truncation brings the value of an array + element to zero, the array can be made smaller. An + implementation should also impose a maximum reasonable array + size or allow more than one multiplication. + + decay-array-size = (Tmax/delta-t) + + decay array (decay[]) + + Each i-th element of the decay array is the per tick delay + raised to the i-th power. This might be best done by successive + floating point multiplies followed by scaling and integer + rounding or truncation. The array itself need only be computed + at startup. + + decay[i] = decay[1] ** i + +4.6 Building the Reuse Index Arrays + + The reuse lists may be accessed quite frequently if a lot of routes + are flapping sufficiently to be suppressed. A method of speeding the + determination of which reuse list to use for a given route is + suggested. This method is introduced in Section 4.2, its + configuration described in Section 4.4.2 and the algorithms described + in Section 4.8.6 and Section 4.8.7. This section describes building + + + +Villamizar, et. al. Standards Track [Page 20] + +RFC 2439 BGP Route Flap Damping November 1998 + + + the reuse list index arrays. + + A ratio of the figure of merit of the route under consideration to + the cutoff value is used as the basis for an array lookup. The ratio + is scaled and truncated to an integer and used to index the array. + The array entry is an integer used to determine which reuse list to + use. + + reuse array maximum ratio (max-ratio) + + This is the maximum ratio between the current value of the + stability figure of merit and the target reuse value that can be + indexed by the reuse array. It may be limited by the ceiling + imposed by the maximum hold time or by the amount of time that + the reuse lists cover. + + max-ratio = min(ceiling/reuse, exp((1 / (half-life/reuse- + array-time)) * log(2))) + + reuse array scale factor ( scale-factor ) + + Since the reuse array is an estimator, the reuse array scale + factor has to be computed such that the full size of the reuse + array is used. + + scale-factor = reuse-index-array-size / (max-ratio - 1) + + reuse index array (reuse-index-array[]) + + Each reuse index array entry should contain an index into the + reuse list array pointing to one of the list heads. This index + should corresponding to the reuse list that will be evaluated + just after a route would be eligible for reuse given the ratio + of current value of the stability figure of merit to target + reuse value corresponding the the reuse array entry. + + reuse-index-array[j] = integer((decay-half-life / reuse- + time-granularity) * log(1/(reuse * (1 + (j / scale-factor)))) / + log(1/2)) + + To determine which reuse queue to place a route which is being + suppressed, the following procedure is used. Divide the current + figure of merit by the cutoff. Subtract one. Multiply by the scale + factor. This is the index into the reuse index array (reuse-index- + array[]). The value fetched from the reuse index array (reuse- + index-array[]) is an index into the array of reuse lists (reuse- + array[]). If this index is off the end of the array use the last + queue otherwise look in the array and pick the number of the queue + + + +Villamizar, et. al. Standards Track [Page 21] + +RFC 2439 BGP Route Flap Damping November 1998 + + + from the array at that index. This is quite fast and well worth the + setup and storage required. + +4.7 A Sample Configuration + + A simple example is presented here in which the space overhead is + estimated for a set of configuration parameters. The design here + assumes: + + 1. there is a single parameter set used for all routes, + + 2. decay time for unreachable routes is slower than for reachable + routes + + 3. the arrays must be full size, rather than allow more than one + multiply per decay operation to reduce the array size. + + This example is used in later sections. The use of multiple + parameter sets complicates the examples somewhat. Where multiple + parameter sets are allowed for a single route, the decay portion of + the algorithm is repeated for each parameter set. If different + routes are allowed to have different parameter sets, the routes must + have pointers to the parameter sets to keep the time to locate to a + minimum, but the algorithms are otherwise unchanged. + + A sample set of configuration parameters and a sample set of + implementation parameters are provided in in the two following lists. + + 1. Configuration Parameters + + o cut = 1.25 + + o reuse = 0.5 + + o T-hold = 15 mins + + o decay-ok = 5 min + + o decay-ng = 15 min + + o Tmax-ok, Tmax-ng = 15, 30 mins + + 2. Implementation Parameters + + o delta-t = 1 sec + + o delta-reuse = 15 sec + + + + +Villamizar, et. al. Standards Track [Page 22] + +RFC 2439 BGP Route Flap Damping November 1998 + + + o reuse-list-size = 256 + + o reuse-index-array-size = 1,024 + + Using these configuration and implementation parameters and the + equations in Section 4.5, the space overhead can be computed. There + is a fixed space overhead that is independent of the number of + routes. There is a space requirement associated with a stable route. + There is a larger space requirement associated with an unstable + route. The space requirements for the parameters above are provide + in the lists below. + + 1. fixed overhead (using parameters from previous example) + + o 900 * integer - decay array + + o 1,800 * integer - decay array + + o 120 * pointer - reuse list-heads + + o 2,048 * integer - reuse index arrays + + 2. overhead per stable route + + o pointer - containing null entry + + 3. overhead per unstable route + + o pointer - to a damping structure containing the following + + o integer - figure of merit + bit for state + + o integer - last time updated + + o 2 * pointer - reuse list pointers (prev, next) + + The decay arrays are sized acording to delta-t and Tmax-ok or Tmax- + ng. The number of reuse list-heads is based on delta-reuse and the + greater of Tmax-ok or Tmax-ng. There are two reuse index arrays + whose size is a configured parameter. + + Figure 3 shows the behavior of the algorithm with the parameters + given above. Four cases are given in this example. In all four, + there is a twelve minute period of route oscillations. Two periods + of oscillation are used, 2 minutes and 4 minutes. Two duty cycles + are used, one in which the route is reachable during 20% of the cycle + and the other where the route is reachable during 80% of the cycle. + In all four cases, the route becomes suppressed after it becomes + + + +Villamizar, et. al. Standards Track [Page 23] + +RFC 2439 BGP Route Flap Damping November 1998 + + + unreachable the second time. Once suppressed, it remains suppressed + until some period after becoming stable. The routes which oscillate + over a 4 minute period are no longer suppressed within 9-11 minutes + after becoming stable. The routes with a 2 minute period of + oscillation are suppressed for nearly the maximum 15 minute period + after becoming stable. + +4.8 Processing Routing Protocol Activity + + The prior sections concentrate on configuration parameters and their + relationship to the parameters and arrays used at run time and + provide the algorithms for initializing run time storage. This + section provides the steps taken in processing routing events and + timer events when running. + + The routing events are: + + 1. A BGP peer or new route comes up for the first time (or after + an extended down time) (Section 4.8.1) + + 2. A route becomes unreachable (Section 4.8.2) + + 3. A route becomes reachable again (Section 4.8.3) + + 4. A route changes (Section 4.8.4) + + 5. A peer goes down (Section 4.8.5) + + + + + + + + + + + + + + + + + + + + + + + + +Villamizar, et. al. Standards Track [Page 24] + +RFC 2439 BGP Route Flap Damping November 1998 + + + time figure-of-merit as a function of time (in minutes) + + 0.00 0.000 . 0.000 . 0.000 . 0.000 . + 0.62 0.000 . 0.000 . 0.000 . 0.000 . + 1.25 0.000 . 0.000 . 0.000 . 0.000 . + 1.88 0.000 . 0.000 . 0.000 . 0.000 . + 2.50 0.977 . 0.968 . 0.000 . 0.000 . + 3.12 0.949 . 0.888 . 0.000 . 0.000 . + 3.75 0.910 . 0.814 . 0.000 . 0.000 . + 4.37 1.846 . 1.756 . 0.983 . 0.983 . + 5.00 1.794 . 1.614 . 0.955 . 0.935 . + 5.63 1.735 . 1.480 . 0.928 . 0.858 . + 6.25 2.619 . 2.379 . 0.901 . 0.786 . + 6.88 2.544 . 2.207 . 0.876 . 0.721 . + 7.50 2.472 . 2.024 . 0.825 . 0.661 . + 8.13 3.308 . 2.875 . 1.761 . 1.608 . + 8.75 3.213 . 2.698 . 1.711 . 1.562 . + 9.38 3.122 . 2.474 . 1.662 . 1.436 . + 10.00 3.922 . 3.273 . 1.615 . 1.317 . + 10.63 3.810 . 3.107 . 1.569 . 1.207 . + 11.25 3.702 . 2.849 . 1.513 . 1.107 . + 11.88 3.498 . 2.613 . 1.388 . 1.015 . + 12.50 3.904 . 3.451 . 2.312 . 1.953 . + 13.13 3.580 . 3.164 . 2.120 . 1.791 . + 13.75 3.283 . 2.902 . 1.944 . 1.643 . + 14.38 3.010 . 2.661 . 1.783 . 1.506 . + 15.00 2.761 . 2.440 . 1.635 . 1.381 . + 15.63 2.532 . 2.238 . 1.499 . 1.267 . + 16.25 2.321 . 2.052 . 1.375 . 1.161 . + 16.88 2.129 . 1.882 . 1.261 . 1.065 . + 17.50 1.952 . 1.725 . 1.156 . 0.977 . + 18.12 1.790 . 1.582 . 1.060 . 0.896 . + 18.75 1.641 . 1.451 . 0.972 . 0.821 . + 19.38 1.505 . 1.331 . 0.891 . 0.753 . + 20.00 1.380 . 1.220 . 0.817 . 0.691 . + 20.62 1.266 . 1.119 . 0.750 . 0.633 . + 21.25 1.161 . 1.026 . 0.687 . 0.581 . + 21.87 1.064 . 0.941 . 0.630 . 0.533 . + 22.50 0.976 . 0.863 . 0.578 . 0.488 . + 23.12 0.895 . 0.791 . 0.530 . 0.448 . + 23.75 0.821 . 0.725 . 0.486 . 0.411 . + 24.37 0.753 . 0.665 . 0.446 . 0.377 . + 25.00 0.690 . 0.610 . 0.409 . 0.345 . + + Figure 3: Some fairly long route flap cycles, repeated for 12 minutes, + followed by a period of stability. + + + + + +Villamizar, et. al. Standards Track [Page 25] + +RFC 2439 BGP Route Flap Damping November 1998 + + + The reuse list is used to provide a means of fast evaluation of route + that had been suppressed, but had been stable long enough to be + reused again or had been suppressed long enough that it can be + treated as a new route. The following two operations are described. + + 1. Inserting into a reuse list (Section 4.8.6) + + 2. Reuse list processing every delta-t seconds (Section 4.8.7) + +4.8.1 Processing a New Peer or New Routes + + When a peer comes up, no action is required if the routes had no + previous history of instability, for example if this is the first + time the peer is coming up and announcing these routes. For each + route, the pointer to the damping structure would be zeroed and route + used. The same action is taken for a new route or a route that has + been down long enough that the figure of merit reached zero and the + damping structure was deleted. + +4.8.2 Processing Unreachable Messages + + When a route is withdrawn or changed (Section 4.8.4 describes how a + change is handled), the following procedure is used. + + If there is no previous stability history (the damping structure + pointer is zero), then: + + 1. allocate a damping structure + + 2. set figure-of-merit = 1 + + 3. withdraw the route + + Otherwise, if there is an existing damping structure, then: + + 1. set t-diff = t-now - t-updated + + 2. if (t-diff puts you off the end of the array) { + + setfigure-of-merit =1 + + }else { + + setfigure-of-merit =figure-of-merit *decay-array-ok [t-diff ]+ 1 + + if(figure-of-merit >ceiling) { + + setfigure-of-merit =ceiling + + + +Villamizar, et. al. Standards Track [Page 26] + +RFC 2439 BGP Route Flap Damping November 1998 + + + } + + } + + 3. remove the route from a reuse list if it is on one + + 4. withdraw the route unless it is already suppressed + + In either case then: + + 1. set t-updated = t-now + + 2. insert into a reuse list (see Section 4.8.6) + + If there was a stability history, the previous value of the stability + figure of merit is decayed. This is done using the decay array + (decay-array). The index is determined by subtracting the current + time and the last time updated, then dividing by the time + granularity. If the index is zero, the figure of merit is unchanged + (no decay). If it is greater than the array size, it is zeroed. + Otherwise use the index to fetch a decay array element and multiply + the figure of merit by the array element. If using the suggested + scaled integer method, shift down half an integer. Add the scaled + penalty for one more unreachable (shown above as 1). If the result + is above the ceiling replace it with the ceiling value. Now update + the last time updated field (preferably taking into account how much + time was truncated before doing the decay calculation). + + When a route becomes unreachable, alternate paths must be considered. + This process is complicated slightly if different configuration + parameters are used in the presence or absence of viable alternate + paths. If all of these alternate paths have been suppressed because + there had previously been an alternate route and the new route + withdrawal changes that condition, the suppressed alternate paths + must be reevaluated. They should be reevaluated in order of normal + route preference. When one of these alternate routes is encountered + that had been suppressed but is now usable since there is no + alternate route, no further routes need to be reevaluated. This only + applies if routes are given two different reuse thresholds, one for + use when there is an alternate path and a higher threshold to use + when suppressing the route would result in making the destination + completely unreachable. + +4.8.3 Processing Route Advertisements + + When a route is readvertised if there is no damping structure, then + the procedure is the same as in Section 4.8.1. + + + + +Villamizar, et. al. Standards Track [Page 27] + +RFC 2439 BGP Route Flap Damping November 1998 + + + 1. don't create a new damping structure + + 2. use the route + + If an damping structure exists, the figure of merit is decayed and + the figure of merit and last time updated fields are updated. A + decision is now made as to whether the route can be used immediately + or needs to be suppressed for some period of time. + + 1. set t-diff = t-now - t-updated + + 2. if (t-diff puts you off the end of the array) { + + set figure-of-merit =0 + + }else { + + set figure-of-merit= figure-of-merit* decay-array-ng[t-diff] + + } + + 3. if ( not suppressed and figure-of-merit < cut ) { + + use the route + + }else if( suppressed and figure-of-merit< reuse) { + + set state tonot suppressed + + remove the route from a reuse list + + use the route + + }else { + + set state to suppressed + + don't use the route + + insert into a reuse list (see Section 4.8.6) + + } + + 4. if ( figure-of-merit > 0 ) { + + set t-updated= t-now + + }else { + + + +Villamizar, et. al. Standards Track [Page 28] + +RFC 2439 BGP Route Flap Damping November 1998 + + + recover memory for damping struct + + zero pointer to damping struct + + } + + If the route is deemed usable, a search for the current best route + must be made. The newly reachable route is then evaluated according + to the BGP protocol rules for route selection. + + If the new route is usable, the previous best route is examined. + Prior to route comparisons, the current best route may have to be + reevaluated if separate parameter sets are used depending on the + presence or absence of an alternate route. If there had been no + alternate the previous best route may be suppressed. + + If the new route is to be suppressed it is placed on a reuse list + only if it would have been preferred to the current best route had + the new route been accepted as stable. There is no reason to queue a + route on a reuse list if after the route becomes usable it would not + be used anyway due to the existence of a more preferred route. Such + a route would not have to be reevaluated unless the preferred route + became unreachable. As specified here, the less preferred route + would be reevaluated and potentially used or potentially added to a + reuse list when processing the withdrawal of a more preferred best + route. + +4.8.4 Processing Route Changes + + If a route is replaced by a peer router by supplying a new path, the + route that is being replaced should be treated as if an unreachable + were received (see Section 4.8.2). This will occur when a peer + somewhere back in the AS path is continuously switching between two + AS paths and that peer is not damping route flap (or applying less + damping). There is no way to determine if one AS path is stable and + the other is flapping, or if they are both flapping. If the cycle is + sufficiently short compared to convergence times neither route + through that peer will deliver packets very reliably. Since there is + no way to affect the peer such that it chooses the stable of the two + AS paths, the only viable option is to penalize both routes by + considering each change as an unreachable followed by a route + advertisement. + +4.8.5 Processing A Peer Router Loss + + When a peer routing session is broken, either all individual routes + advertised by that peer may be marked as unstable, or the peering + session itself may be marked as unstable. Marking the peer will save + + + +Villamizar, et. al. Standards Track [Page 29] + +RFC 2439 BGP Route Flap Damping November 1998 + + + considerable memory. Since the individual routes are advertised as + unreachable to routers beyond the immediate problem, per route state + will be incurred beyond the peer immediately adjacent to the BGP + session that went down. If the instability continues, the + immediately adjacent router need only keep track of the peer + stability history. The routers beyond that point will receive no + further advertisements or withdrawal of routes and will dispose of + the damping structure over time. + + BGP notification through an optional transitive attribute that + damping will already be applied may be considered in the future to + reduce the number of routers that incur damping structure storage + overhead. + +4.8.6 Inserting into the Reuse Timer List + + The reuse lists are used to provide a means of fast evaluation of + route that had been suppressed, but had been stable long enough to be + reused again. The data structure consists of a series of list heads. + Each list contains a set of routes that are scheduled for + reevaluation at approximately the same time. The set of reuse list + heads are treated as a circular array. Refer to Figure 4. + + A simple implementation of the circular array of list heads would be + an array containing the list heads. An offset is used when accessing + the array. The offset would identify the first list. The Nth list + would be at the index corresponding to N plus the offset modulo the + number of list heads. This design will be assumed in the examples + that follow. + + A key requirement is to be able to insert an entry in the most + appropriate queue with a minimum of computation. The computation is + given only the current value of figure-of-merit. Instead of a + computation which would involve a logarithm, the reuse array (reuse- + array[]) described in Section 4.6 is used. The array, scale, and + bounds are precomputed to map figure-of-merit to the nearest list + head without requiring a logarithm to be computed (see Section 4.5). + + + + + + + + + + + + + + +Villamizar, et. al. Standards Track [Page 30] + +RFC 2439 BGP Route Flap Damping November 1998 + + + +-+ +-+ +-+ non-empty linked list means + | | | | | | <-- that there are routes with + +-+ +-+ +-+ defered action to be taken + ^ ^ ^ N * delta-reuse seconds later. + | | | + +------+------+------+------+------+ +------+ + | list | list | list | list | list | ... | list | + | head | head | head | head | head | ... | head | + +------+------+------+------+------+ +------+ + ^ ^ ^ ^ ^ ^ + Nth 1st 2nd 3rd 4th N-1 + | + offset to first list + (the offset is incremented every delta-reuse seconds) + + Figure 4: Reuse List Data Structures + + Note that in the following sections the operator prefix notation + "modulo a b" means "b % a" in C language algebraic operator notation. + For example, "modulo 16 1023" would be 15. + + 1. scale figure-of-merit for the index array lookup producing + index + + 2. check index against the array bound + + 3. if (within the array bound) { + + set index =reuse-array [index ] + + }else { + + set index =reuse-list-size -1 + + } + + 4. insert into the list + + reuse-list[ moduloreuse-list-size (index +offset )] + + Choosing the correct reuse list involves only a multiply and shift to + do the scaling, an integer truncation, then an array lookup in the + reuse array (reuse-array[]). The value retrieved from the reuse + array is used to select a reuse list. The reuse list is a circular + list. The most common method of implementing a circular list is to + use an array and apply an offset and modulo operation to pick the + correct array entry. The offset is incremented to rotate the + circular list. + + + +Villamizar, et. al. Standards Track [Page 31] + +RFC 2439 BGP Route Flap Damping November 1998 + + +4.8.7 Handling Reuse Timer Events + + The granularity of the reuse timer should be more coarse than that of + the decay timer. As a result, when the reuse timer fires, suppressed + routes should be decayed by multiple increments of decay time. Some + computation can be avoided by always inserting into the reuse list + corresponding to one time increment past reuse eligibility. In cases + where the reuse lists have a longer "memory" than the "decay memory" + (described above), all of the routes in the first queue will be + available for immediate reuse if reachable or the history entry could + be disposed of if unreachable. + + When it is time to advance the lists, the first queue on the reuse + list must be processed and the circular queue must be rotated. Using + an array and an offset as a circular array (as described in Section + 4.8.6), the algorithm below is repeated every delta-reuse seconds. + + 1. save a pointer to the current zeroth queue head and zero the + list head entry + + 2. set offset = modulo reuse-list-size ( offset + 1 ), thereby + rotating the circular queue of list-heads + + 3. if ( the saved list head pointer is non-empty ) + + for each entry { + + sett-diff =t-now -t-updated + + set figure-of-merit =figure-of-merit *decay-array-ok [t-diff ] + + sett-updated =t-now + + if( figure-of-merit< reuse) + + reuse the route + + else + + re-insert into another list (seeSection 4.8.6) + + } + + The value of the zeroth list head would be saved and the array entry + itself zeroed. The list heads would then be advanced by incrementing + the offset. Starting with the saved head of the old zeroth list, + each route would be reevaluated and used, disposed of entirely or + requeued if it were not ready for reuse. If a route is used, it must + + + +Villamizar, et. al. Standards Track [Page 32] + +RFC 2439 BGP Route Flap Damping November 1998 + + + be treated as if it were a new route advertisement as described in + Section 4.8.3. + +5 Implementation Experience + + The first implementations of "route flap damping" were the route + server daemon (rsd) coding by Ramesh Govindan (ISI) and the Cisco IOS + implementation by Ravi Chandra. Both implementations first became + available in 1995 and have been used extensively. The rsd + implementation has been in use in route servers at the NSF funded + Network Access Points (NAPs) and at other major Internet + interconnects. The Cisco IOS version has been in use by Internet + Service Providers worldwide. The rsd implementation has been + integrated in releases of gated (see http://www.gated.org) and is + available in commercial routers using gated. + + There are now more than 2 years of BGP route damping deployment + experience. Some problems have occurred in deployment. So far these + are solvable by careful implementation of the algorithm and by + careful deployment. In some topologies coordinated deployment can be + helpful and in all cases disclosure of the use of route damping and + the parameters used is highly beneficial in debugging connectivity + problems. + + Some of the problems have occurred due to subtle implementation + errors. Route damping should never be applied on IBGP learned + routes. To do so can open the possibility for persistent route + loops. When IBGP routes within an AS are inconsistent, route loops + can easily form. Suppressing IBGP learned routes causes such + inconsistencies. Implementations should disallow configuration of + route damping on IBGP peers. + + Penalties for instability should only be applied when a route is + removed or replaced and not when a route is added. If damping + parameters are applied consistently, this implementation constraint + will result in a stable secondary path being preferred over an + unstable primary path due to damping of the primary path near the + source. + + In topologies where multiple AS paths to a given destination exist + flapping of the primary path can result in suppression of the + secondary path. This can occur if no damping is being done near the + cause of the route flap or if damping is being applied more + aggressively by a distant AS. This problem can be solved in one of + two ways. Damping can be done near the source of the route flap and + the damping parameters can be made consistent. Alternately, a + distant AS which insists on more aggressive damping parameters can + disable penalizing routes on AS path change, penalizing routes only + + + +Villamizar, et. al. Standards Track [Page 33] + +RFC 2439 BGP Route Flap Damping November 1998 + + + if they are withdrawn completely. In order to do so, the + implementation must support this option (as described in Section + 4.4.3). + + Route flap should be damped near the source. Single homed + destinations can be covered by static routes. Aggregation provides + another means of damping. Providers should damp their own internal + problems, however damping on IGP link state origination is not yet + implemented by router vendors. Providers which use multiple AS + within their own topology should damp between their own AS. Providers + should damp adjacent providers AS. + + Damping provides a means to limit propagation excessive route change + when connectivity is highly intermittent. Once a problem is + corrected, damping state corresponding to the prefixes known to be + damped due to the problem just fixed can be manually cleared. In + order to determine where damping may have occurred after connectivity + problems, providers should publish their damping parameters. + Providers should be willing to manually clear damping on specific + prefixes or AS paths at the request of other providers when the + request is accompanied by credible assurance that the problem has + truly been addressed. + + By damping their own routing information, providers can reduce their + own need to make requests of other providers to clear damping state + after correcting a problem. Providers should be pro-active and + monitor what prefixes and paths are suppressed in addition to + monitoring link states and BGP session state. + +Acknowledgements + + This work and this document may not have been completed without the + advise, comments and encouragement of Yakov Rekhter (Cisco). Dennis + Ferguson (MCI) provided a description of the algorithms in the gated + BGP implementation and many valuable comments and insights. David + Bolen (ANS) and Jordan Becker (ANS) provided valuable comments, + particularly regarding early simulations. Over four years elapsed + between the initial draft presented to the BGP WG (October 1993) and + this iteration. At the time of this writing there is significant + experience with two implementations, each having been deployed since + 1995. One was led by Ramesh Govindan (ISI) for the NSF Routing + Arbiter project. The second was led by Ravi Chandra (Cisco). Sean + Doran (Sprintlink) and Serpil Bayraktar (ANS) were among the early + independent testers of the Cisco pre-beta implementation. Valuable + comments and implementation feedback were shared by many individuals + on the IETF IDR WG and the RIPE Routing Work Group and in NANOG and + IEPG. + + + + +Villamizar, et. al. Standards Track [Page 34] + +RFC 2439 BGP Route Flap Damping November 1998 + + + Thanks also to Rob Coltun (Fore Systems), Sanjay Wadhwa (Fore), John + Scudder (IENG), Eric Bennet (IENG) and Jayesh Bhatt (Bay Networks) + for pointing out errors in the math uncovered during coding of more + recent implementations. These errors appeared in the details of the + implementation suggestion sections written after the first two + implementations were completed. Thanks also to Vern Paxson for a + very thorough review resulting in numerous clarifications to the + document. + +References + + [1] Gross, P., and Y. Rekhter, "Application of the border gateway + protocol in the internet", RFC 1268, October 1991. + + [2] ISO/IEC. Iso/iec 10747 - information technology - telecommuni- + cations and information exchange between systems - protocol for + exchange of inter-domain routeing information among intermediate + systems to support forwarding of iso 8473 pdus. Technical + report, International Organization for Standardization, August + 1994. ftp://merit.edu/pub/iso/idrp.ps.gz. + + [3] Lougheed, K., and Y. Rekhter, "A border gateway protocol 3 (BGP- + 3)", RFC 1267, October 1991. + + [4] Rekhter, Y., and P. Gross, "Application of the border gateway + protocol in the internet", RFC 1772, March 1995. + + [5] Rekhter, Y., and T. Li, "A border gateway protocol 4 (BGP-4)", + RFC 1771, March 1995. + + [6] Rekhter, Y., and C. Topolcic,"Exchanging routing information + across provider boundaries in the CIDR environment", RFC 1520, + September 1993. + + [7] Traina, P., "BGP-4 protocol analysis", RFC 1774, March 1995. + + [8] Traina, P., "Experience with the BGP-4 protocol", RFC 1773, March + 1995. + +Security Considerations + + The practices outlined in this document do not further weaken the + security of the routing protocols. Denial of service is possible in + an already insecure routing environment but these practices only + contribute to the persistence of such attacks and do not impact the + methods of prevention and the methods of determining the source. + + + + + +Villamizar, et. al. Standards Track [Page 35] + +RFC 2439 BGP Route Flap Damping November 1998 + + +Authors' Addresses + + Curtis Villamizar + ANS + + EMail: curtis@ans.net + + + Ravi Chandra + Cisco Systems + + EMail: rchandra@cisco.com + + + Ramesh Govindan + ISI + + EMail: govindan@isi.edu + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Villamizar, et. al. Standards Track [Page 36] + +RFC 2439 BGP Route Flap Damping November 1998 + + +Full Copyright Statement + + Copyright (C) The Internet Society (1998). All Rights Reserved. + + This document and translations of it may be copied and furnished to + others, and derivative works that comment on or otherwise explain it + or assist in its implementation may be prepared, copied, published + and distributed, in whole or in part, without restriction of any + kind, provided that the above copyright notice and this paragraph are + included on all such copies and derivative works. However, this + document itself may not be modified in any way, such as by removing + the copyright notice or references to the Internet Society or other + Internet organizations, except as needed for the purpose of + developing Internet standards in which case the procedures for + copyrights defined in the Internet Standards process must be + followed, or as required to translate it into languages other than + English. + + The limited permissions granted above are perpetual and will not be + revoked by the Internet Society or its successors or assigns. + + This document and the information contained herein is provided on an + "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING + TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING + BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION + HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF + MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. + + + + + + + + + + + + + + + + + + + + + + + + +Villamizar, et. al. Standards Track [Page 37] + |