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
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)
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.
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
}
}
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.
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 {
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
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).
+-+ +-+ +-+ 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.
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
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
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.
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", RFC1268, 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)", RFC1267, October 1991.
[4] Rekhter, Y., and P. Gross, "Application of the border gateway
protocol in the internet", RFC1772, March 1995.
[5] Rekhter, Y., and T. Li, "A border gateway protocol 4 (BGP-4)",
RFC1771, March 1995.
[6] Rekhter, Y., and C. Topolcic,"Exchanging routing information
across provider boundaries in the CIDR environment", RFC1520,
September 1993.
[7] Traina, P., "BGP-4 protocol analysis", RFC1774, March 1995.
[8] Traina, P., "Experience with the BGP-4 protocol", RFC1773, 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.
Authors' Addresses
Curtis Villamizar
ANS
EMail: curtis@ans.net
Ravi Chandra
Cisco Systems
EMail: rchandra@cisco.com
Ramesh Govindan
ISI
EMail: govindan@isi.edu
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.