File: rfc2439.txt

package info (click to toggle)
doc-rfc 20181229-2
  • links: PTS, VCS
  • area: non-free
  • in suites: buster
  • size: 570,944 kB
  • sloc: xml: 285,646; sh: 107; python: 90; perl: 42; makefile: 14
file content (2075 lines) | stat: -rw-r--r-- 86,402 bytes parent folder | download | duplicates (7)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
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]