idnits 2.17.1 draft-ietf-idr-route-damp-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-18) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. ** The document is more than 15 pages and seems to lack a Table of Contents. == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 10 instances of too long lines in the document, the longest one being 6 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (October 30, 1997) is 9667 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Unused Reference: '2' is defined on line 1175, but no explicit reference was found in the text == Unused Reference: '3' is defined on line 1182, but no explicit reference was found in the text == Unused Reference: '4' is defined on line 1187, but no explicit reference was found in the text == Unused Reference: '6' is defined on line 1197, but no explicit reference was found in the text == Unused Reference: '7' is defined on line 1201, but no explicit reference was found in the text == Unused Reference: '8' is defined on line 1205, but no explicit reference was found in the text ** Obsolete normative reference: RFC 1268 (ref. '1') (Obsoleted by RFC 1655) -- Possible downref: Non-RFC (?) normative reference: ref. '2' ** Downref: Normative reference to an Historic RFC: RFC 1267 (ref. '3') ** Obsolete normative reference: RFC 1771 (ref. '5') (Obsoleted by RFC 4271) ** Downref: Normative reference to an Historic RFC: RFC 1520 (ref. '6') ** Downref: Normative reference to an Informational RFC: RFC 1774 (ref. '7') ** Downref: Normative reference to an Informational RFC: RFC 1773 (ref. '8') Summary: 16 errors (**), 0 flaws (~~), 7 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Engineering Task Force Curtis Villamizar 3 INTERNET-DRAFT ANS 4 draft-ietf-idr-route-damp-00 Ravi Chandra 5 Cisco 6 Ramesh Govindan 7 ISI 8 October 30, 1997 10 BGP Route Flap Damping 12 Status of this Memo 14 This document is an Internet-Draft. Internet-Drafts are working 15 documents of the Internet Engineering Task Force (IETF), its areas, 16 and its working groups. Note that other groups may also distribute 17 working documents as Internet-Drafts. 19 Internet-Drafts are draft documents valid for a maximum of six months 20 and may be updated, replaced, or obsoleted by other documents at any 21 time. It is inappropriate to use Internet- Drafts as reference 22 material or to cite them other than as ``work in progress.'' 24 To view the entire list of current Internet-Drafts, please check the 25 ``1id-abstracts.txt'' listing contained in the Internet-Drafts Shadow 26 Directories on ftp.is.co.za (Africa), ftp.nordu.net (Europe), 27 munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or 28 ftp.isi.edu (US West Coast). 30 Abstract 32 A usage of the BGP routing protocol is described which is capable of 33 reducing the routing traffic passed on to routing peers and therefore 34 the load on these peers without adversely affecting route convergence 35 time for relatively stable routes. This technique has been 36 implemented in commercial products supporting BGP. The technique is 37 also applicable to IDRP. 39 The overall goals are: 41 o to provide a mechanism capable of reducing router processing load 42 caused by instability 44 o in doing so prevent sustained routing oscillations 46 o to do so without sacrificing route convergence time for generally 47 well behaved routes. 49 This must be accomplished keeping other goals of BGP in mind: 51 o pack changes into a small number of updates 53 o preserve consistent routing 55 o minimal addition space and computational overhead 57 Excessive updates to reachability state has been widespread in the 58 Internet. This observation was made in the early 1990s by many people 59 involved in Internet operations and remains to case to date. These 60 excessive updates are not necessarily periodic so route oscillation 61 would be a misleading term. The informal term used to describe this 62 effect is ``route flap''. The techniques described here are now 63 widely deployed and are commonly referred to as ``route flap 64 damping''. 66 1 Overview 68 It is necessary to reduce the amount of routing traffic (the number of 69 update message) generated by BGP in order to limit processing 70 requirements. The primary contributors of processing load resulting 71 from BGP updates are the BGP decision process and adding and removing 72 forwarding entries. 74 Consider the following example. A widely deployed BGP implementation 75 may tend to fail due to high routing update volume. For example, it 76 may be unable to maintain it's BGP or IGP sessions if sufficiently 77 loaded. The failure of one router can further contribute to the load 78 on other routers. This additional load may cause failures in other 79 instances of the same implementation or other implementations with a 80 similar weakness. In the worst case, a stable oscillation could 81 result. Such worse cases have already been observed in practice. 83 A BGP implementation must be prepared for a large volume of routing 84 traffic. A BGP implementation cannot rely upon the sender to 85 sufficiently shield it from route instabilities. The guidelines here 86 are designed to prevent sustained oscillations, but do not eliminate 87 the need for robust and efficient implementations. The mechanisms 88 described here allow routing instability to be contained at an AS 89 border router bordering the instability. 91 2 Methods of Limiting Route Advertisement 93 Two methods of controlling the frequency of route advertisement are 94 described here. The first involves fixed timers. The fixed timer 95 technique has no space overhead per route but has the disadvantage of 96 slowing route convergence for the normal case where a route does not 97 have a history of instability. The second method overcomes this 98 limitation at the expense of maintaining some additional space 99 overhead. The additional overhead includes a small amount of state 100 per route and a very small processing overhead. 102 It is possible and desirable to combine both techniques. In practice, 103 fixed timers have been set to very short time intervals and have 104 proven useful to pack routes (NLRI) into a smaller number of updates 105 when routes arrive in separate updates. 107 Seldom are fixed timers set to the tens of minutes to hours that would 108 be necessary to actually damp route flap. To do so would produce the 109 undesirable effect of severely limiting routing convergence. 111 2.1 Existing Fixed Timer Recommendations 113 BGP-3 does not make specific recommendations in this area [1]. The 114 short section entitled ``Frequency of Route Selection'' simply 115 recommends that something be done and makes broad statements regarding 116 certain properties that are desirable or undesirable. 118 BGP4 retains the ``Frequency of Route Advertisement'' section and adds 119 a ``Frequency of Route Origination'' section. BGP-4 describes a 120 method of limiting route advertisement involving a fixed 121 (configurable) MinRouteAdvertisementInterval timer and fixed 122 MinASOriginationInterval timer [5]. The recommended timer values of 123 MinRouteAdvertisementInterval is 30 seconds and 124 MinASOriginationInterval is 15 seconds. 126 2.2 Desirable Properties of Damping Algorithms 128 Before describing damping algorithms the objectives need to be clearly 129 defined. Some key properties are examined to clarify the design 130 rationale. 132 The overall objective is to reduce the route update load without 133 limiting convergence time for well behaved routes. To accomplish 134 this, criteria must be defined for well behaved and poorly behaved 135 routes. An algorithm must be defined which allows poorly behaved 136 routes to be identified. Ideally, this measure would be a prediction 137 of the future stability of a route. 139 Any delay in propagation of well behaved routes should be minimal. 140 Some delay is tolerable to support better packing of updates. Delay 141 of poorly behave routes should, if possible, be proportional to a 142 measure of the expected future instability of the route. Delay in 143 propagating an unstable route should cause the unstable route to be 144 suppressed until there is some degree of confidence that the route has 145 stabilized. 147 If a large number of route changes are received in separate updates 148 over some very short period of time and these updates have the 149 potential to be combined into a single update then these should be 150 packed as efficiently as possible before propagating further. Some 151 small delay in propagating well behaved routes is tolerable and is 152 necessary to allow better packing of updates. 154 Where routes are unstable, use and announcement of the routes should 155 be suppressed rather than suppressing their removal. Where one route 156 to a destination is stable, and another route to the same destination 157 is somewhat unstable, if possible, the unstable route should be 158 suppressed more aggressively than if there were no alternate path. 160 Routing consistency within an AS is very important. Only very minimal 161 delay of internal BGP (IBGP) should be done. Routing consistency 162 across AS boundaries is also very important. It is highly undesirable 163 to advertise a route that is different from the route that is being 164 used, except for a very minimal time. It is more desirable to 165 suppress the acceptance of a route (and therefore the use of that 166 route in the IGP) rather than suppress only the redistribution. 168 It is clearly not possible to accurately predict the future stability 169 of a route. The recent history of stability is generally regarded as 170 a good basis for estimating the likelihood of future stability. The 171 criteria that is used to distinguish well behaved from poorly behaved 172 routes is therefore based on the recent history of stability of the 173 route. There is no simple direct quantitative expression of recent 174 stability so a figure of merit must be defined. Some desirable 175 characteristics of this figure of merit would be that the farther in 176 the past that instability occurred, the less it's affect on the figure 177 of merit and that the instability measure would be cumulative rather 178 than reflecting only the most recent event. 180 The algorithms should behave such that for routes which have a history 181 of stability but make a few transitions, those transitions should be 182 made quickly. If transitions continue, advertisement of the route 183 should be suppressed. There should be some memory of prior instabil- 184 ity. The degree to which prior instability is considered should be 185 gradually reduced as long as the route remains announced and stable. 187 2.3 Design Choices 189 After routes have been accepted their readvertisement will be briefly 190 suppressed to improve packing of updates. There may be a lengthy 191 suppression of the acceptance of an external route. How long a route 192 will be suppressed is based on a figure of merit that is expected to 193 be loosely correlated to the probability of future instability of a 194 route. Routes with high figure of merit values will be suppressed. 195 An exponential decay algorithm was chosen as the basis for reducing 196 the figure of merit over time. These choices should be viewed as 197 suggestions for implementation. 199 An exponential decay function has the property that previous 200 instability can be remembered for a fairly long time. The rate at 201 which the instability figure of merit decays slows as time goes on. 202 Exponential decay is a transitive function. 204 f(f(figure-of-merit, t1), t2) = f(figure-of-merit, t1+t2) 206 This transitive property allows the decay for a long period to be 207 computed in a single operation regardless of the current value 208 (figure-of-merit). As a performance optimization, the decay can be 209 applied in fixed time increments. Given a desired decay half life, 210 the decay for a single time increment can be computed ahead of time. 211 The decay for multiple time increments is expressed below. 213 f(figure-of-merit, n * t0) = f(figure-of-merit, t0) ** n = K 214 ** n 216 The values of K ** n can be precomputed for a reasonable number of 217 ``n'' and stored in an array. The value of ``K'' is always less than 218 one. The array size can be bounded since the value quickly approaches 219 zero. This makes the decay easy to compute using an array bound 220 check, an array lookup and a single multiply regardless as to how much 221 time has elapsed. 223 3 Limiting Route Advertisements using Fixed Timers 225 This method of limiting route advertisements involves the use of fixed 226 timers applied to the process of sending routes. It's primary purpose 227 is to improve the packing of routes in BGP update messages. The delay 228 in advertising a stable route should be bounded and minimal. The 229 delay in advertising an unreachable need not be zero, but should also 230 be bounded and should probably have a separate bound set less than or 231 equal to the bound for a reachable advertisement. 233 Routes that need to be readvertised can be marked in the RIB or an 234 external set of structures maintained, which references the RIB. 235 Periodically, a subset of the marked routes can be flushed. This is 236 fairly straightforward and accomplishes the objectives. Computation 237 for too simple an implementation may be order N squared. To avoid N 238 squared performance, some form of data structure is needed to group 239 routes with common attributes. 241 Any implementation should packs updates efficiently, provide a minimum 242 readvertisement delay, provide a bounds on the maximum readvertisement 243 delay that would be experienced solely as a result of the algorithm 244 used to provide a minimum delay, and must be computationally efficient 245 in the presence of a very large number of candidates for 246 readvertisement. 248 4 Stability Sensitive Suppression of Route Advertisement 250 This method of limiting route advertisements uses a measure of route 251 stability applied on a per route basis. This technique is applied 252 when receiving updates from external peers only (EBGP). Applying this 253 technique to IBGP learned routes or to advertisement to IBGP or EBGP 254 peers after making a route selection can result in routing loops. 256 A figure of merit based on a measure of instability is maintained on a 257 per route basis. This figure of merit is used in the decision to 258 suppress the use of the route. Routes with high figure of merit are 259 suppressed. Each time a route is withdrawn, the figure of merit is 260 incremented. While the route is not changing the figure of merit 261 value is decayed exponentially with separate decay rates depending on 262 whether the route is stable and reachable or has been stable and 263 unreachable. The decay rate may be slower when the route is unreach- 264 able, or the stability figure of merit could remain fixed (not decay 265 at all) while the route remains unreachable. Whether to decay un- 266 reachable routes at the same rate, a slower rate, or not at all is an im- 267 plementation choice. Decaying at a slower rate is recommended. 269 An very efficient implementation is suggested in the following 270 sections. The implementation only requires computation for the routes 271 contained in an update, when an update is received or withdrawn (as 272 opposed to the simplistic approach of periodically decaying each 273 route). The suggested implementation involves only a small number of 274 simple operations, and can be implemented using scaled integers. 276 The behavior of unstable routes is believed to be fairly predictable. 277 Severely flapping routes will often be advertised and withdrawn at 278 regular time intervals corresponding to the timers of a particular 279 protocol (the IGP or exterior protocol in use where the problem 280 exists). Marginal circuits or mild congestion can result in a long 281 term pattern of occasional brief route withdrawal or occasional brief 282 connectivity. 284 4.1 Single vs. Multiple Configuration Parameter Sets 286 The behavior of the algorithm is modified by a number of configurable 287 parameters. It is possible to configure separate sets of parameters 288 designed to handle short term severe route flap and chronic milder 289 route flap (a pattern of occasional drops over a long time period). 290 The former would require a fast decay and low threshold (allowing a 291 small number of consecutive flaps to cause a route to be suppressed, 292 but allowing it to be reused after a relatively short period of 293 stability). The latter would require a very slow decay and a higher 294 threshold and might be appropriate for routes for which there was an 295 alternate path of similar bandwidth. 297 It may also be desirable to configure different thresholds for routes 298 with roughly equivalent alternate paths than for routes where the 299 alternate paths have a lower bandwidth or tend to be congested. This 300 can be solved by associating a different set of parameters with 301 different ranges of preference values. Parameter selection could be 302 based on BGP LOCAL_PREF. 304 Parameter selection could also be based on whether an alternate route 305 was known. A route would be considered if, for any applicable 306 parameter set, an alternate route with the specified preference value 307 existed and the figure of merit associated with the parameter set did 308 not indicate a need to suppress the route. A less aggressive 309 suppression would be applied to the case where no alternate route at 310 all existed. In the simplest case, a more aggressive suppression 311 would be applied if any alternate route existed. Only the highest 312 preference (most preferred) value needs to be specified, since the 313 ranges may overlap. 315 It might also be desirable to configure a different set of thresholds 316 for routes which rely on switched services and may disconnect at times 317 to reduce connect charges. Such routes might be expected to change 318 state somewhat more often, but should be suppressed if continuous 319 state changes indicate instability. 321 While not essential, it might be desirable to be able to configure 322 multiple sets of configuration parameters per route. It may also be 323 desirable to be able to configure sets of parameters that only 324 correspond to a set of routes (identified by AS path, peer router, 325 specific destinations or other means). Experience may dictate how 326 much flexibility is needed and how to best to set the parameters. 327 Whether to allow different damping parameter sets for different 328 routes, and whether to allow multiple figures of merit per route is an 329 implementation choice. 331 Parameter selection can also be based on prefix length. The rationale 332 is that longer prefixes tend to reach less end systems and are less 333 important and these less important prefixes can be damped more 334 aggressively. This technique is in fairly widespread use. Small 335 sites or those with dense address allocation who are multihomed are 336 often reachable by long prefixes which are not easily aggregated. 337 These sites tend to dispute the choice of prefix length for parameter 338 selection. Advocates of the technique point out that it encourages 339 better aggregation. 341 4.2 Configuration Parameters 343 At configuration time, a number of parameters may be specified by the 344 user. The configuration parameters are expressed in units meaningful 345 to the user. These differ from the parameters used at run time which 346 are in unit convenient for computation. The run time parameters are 347 derived from the configuration parameters. Suggested configuration 348 parameters are listed below. 350 cutoff threshold (cut) 352 This value is expressed as a number of route withdrawals. It is 353 the value above which a route advertisement will be suppressed. 355 reuse threshold (reuse) 357 This value is expressed as a number of route withdrawals. It is 358 the value below which a suppressed route will now be used again. 360 maximum hold down time (T-hold) 362 This value is the maximum time a route can be suppressed no matter 363 how unstable it has been prior to this period of stability. 365 decay half life while reachable (decay-ok) 366 This value is the time duration in minutes or seconds during which 367 the accumulated stability figure of merit will be reduced by half 368 if the route if considered reachable (whether suppressed or not). 370 decay half life while unreachable (decay-ng) 372 This value is the time duration in minutes or seconds during which 373 the accumulated stability figure of merit will be reduced by half 374 if the route if considered unreachable. If not specified or set to 375 zero, no decay will occur while a route remains unreachable. 377 decay memory limit (Tmax-ok or Tmax-ng) 379 This is the maximum time that any memory of previous instability 380 will be retained given that the route's state remains unchanged, 381 whether reachable or unreachable. This parameter is generally used 382 to determine array sizes. 384 There may be multiple sets of the parameters above as described in 385 Section 4.1. The configuration parameters listed below would be 386 applied system wide. These include the time granularity of all 387 computations, and the parameters used to control reevaluation of 388 routes that have previously been suppressed. 390 time granularity (delta-t) 392 This is the time granularity in seconds used to perform all decay 393 computations. 395 reuse list time granularity (delta-reuse) 397 This is the time interval between evaluations of the reuse lists. 398 Each reuse lists corresponds to an additional time increment. 400 reuse list memory reuse-list-max 402 This is the time value corresponding to the last reuse list. This 403 may be the maximum value of T-hold for all parameter sets of may be 404 configured. 406 number of reuse lists (reuse-list-size) 408 This is the number of reuse lists. It may be determined from 409 reuse-list-max or set explicitly. 411 A necessary optimization is described in Section 4.8.6 that involves 412 an array referred to as the ``reuse index array''. A reuse index 413 Figure 1: Instability figure of merit for flap at a constant rate 415 array is needed for each decay rate in use. The reuse index array is 416 used to estimate which reuse list to place a route when it is 417 suppressed. Proper placement avoids the need to periodically evaluate 418 decay to determine if a route can be reused. Using the reuse index 419 array avoids the need to compute a logarithm to determine placement. 420 One additional system wide parameter can be introduced. 422 reuse index array size (reuse-index-array-size) 424 This is the size of reuse index arrays. This size determines the 425 accuracy with which suppressed routes can be placed within the set 426 of reuse lists when suppressed for a long time. 428 4.3 Guidelines for Setting Parameters 430 The decay half life should be set to a time considerably longer than 431 the period of the route flap it is intended to address. If for 432 example, the decay is set to ten minutes and a route is withdrawn and 433 readvertised exactly every ten minutes, the route would continue to 434 flap if the cutoff was set to a value of 2 or above. 436 The stability figure of merit itself is an accumulated time decayed 437 total. This must be kept in mind in setting the decay time, cutoff 438 values and reuse values. For example, if a route flaps at four times 439 the decay rate, it will reach 3 in 4 cycles, 4 in 6 cycles, 5 in 10 440 cycles, and will converge at about 6.3. At twice the decay time, it 441 will reach 3 in 7 cycles, and converge at a value of less than 3.5. 443 Figure 1 shows the stability figure of merit for route flap at a 444 constant rate. The time axis is labeled in multiples of the decay 445 half life. The plots represent route flap with a period of 1/2, 1/3, 446 1/4, and 1/8 times the decay half life. A ceiling of 4.5 was set, 447 which can be seen to affect three of the plots, effectively limiting 448 the time it takes to readvertise the route regardless of the prior 449 history. With the cutoff and reuse thresholds suggested by the dotted 450 lines, routes would be suppressed after being declared unreachable 2-3 451 times and be used again after approximately 2 decay half life periods 452 of stability. 454 From either maximum hold time value (Tmax-ok or Tmax-ng), a ratio of 455 the cutoff to a ceiling can be determined. An integer value for the 456 ceiling can then be chosen such that overflow will not be a problem 457 and all other values can be scaled accordingly. If both cutoffs are 458 specified or if multiple parameter sets are used the highest ceiling 459 Figure 2: Separate decay constants when unreachable 461 will be used. 463 Figure 2 show the effect of configuring separate decay rates to be 464 used when the route is reachable or unreachable. The decay rate is 465 5 times slower when the route is unreachable. In the three case 466 shown, the period of the route flap is equal to the decay half life 467 but the route is reachable 1/8 of the time in one, reachable 1/2 the 468 time in one, and reachable 7/8 of the time in the other. In the last 469 case the route is not suppressed until after the third unreachable 470 (when it is above the top threshold after becoming reachable again). 472 In both Figure 1 and Figure 2, routes would be suppressed. Routes 473 flapping at the decay half life or less would be withdrawn two or 474 three times and then remain withdrawn until they had remained stably 475 announced and stable for on the order of 1 1/2 to 2 1/2 times the 476 decay half life (given the ceiling in the example). 478 A larger time granularity will keep table storage down. The time 479 granularity should be less than a minimal reasonable time between 480 expected worse case route flaps. It might be reasonable to fix this 481 parameter at compile time or set a default and strongly recommend that 482 the user leave it alone. With an exponential decay, array size can be 483 greatly reduced by setting a period of complete stability after which 484 the decayed total will be considered zero rather than retaining a tiny 485 quantity. Alternately, very long decays can be implemented by 486 multiplying more than once if array bounds are exceeded. 488 The reuse lists hold suppressed routes grouped according to how long 489 it will be before the routes are eligible for reuse. Periodically 490 each list will be advanced by one position and one list removed as de- 491 scribed in Section 4.8.7. All of the suppressed routes in the removed 492 list will be reevaluated and either used or placed in another list 493 according to how much additional time must elapse before the route can 494 be reused. The last list will always contain all the routes which 495 will not be advertised for more time than is appropriate for the re- 496 maining list heads. When the last list advances to the front, some of 497 the routes will not be ready to be used and will have to be requeued. 498 The time interval for reconsidering suppressed routes and number of list 499 heads should be configurable. Reasonable defaults might be 30 seconds and 500 64 list heads. A route suppressed for a long time would need to be reeval- 501 uated every 32 minutes. 503 4.4 Run Time Data Structures 505 A fixed small amount of per system storage will be required. Where 506 sets of multiple configuration parameters are used, storage will be 507 required per set of parameters. A small amount of per route storage 508 is required. A set of list heads is needed. These list heads are 509 used to arrange suppressed routes according to the time remaining 510 until they can be reused. 512 If multiple sets of configuration parameters are allowed per route, 513 there is a need for some means of associating more than one figure of 514 merit and set of parameters with each route. Building a linked list 515 of these objects seems like one of a number of reasonable 516 implementations. Similarly, a means of associating a route to a reuse 517 list is required. A small overhead will be required for the pointers 518 needed to implement whatever data structure is chosen for the reuse 519 lists. The suggested implementation uses a double linked lists and so 520 requires two pointers per figure of merit. 522 Each set of configuration parameters can reference decay arrays and 523 reuse arrays. These arrays should be shared among multiple sets of 524 parameters since their storage requirement is not negligible. There 525 will be only one set of reuse list heads for the entire router. 527 4.4.1 Data Structures for Configuration Parameter Sets 529 Based on the configuration parameters described in the previous 530 section, the following values can be computed as scaled integers 531 directly from the corresponding configuration parameters. 533 o decay array scale factor (decay-array-scale-factor) 535 o cutoff value (cut) 537 o reuse value (reuse) 539 o figure of merit ceiling (ceiling) 541 Each configuration parameter set will reference one or two decay 542 arrays and one or two reuse arrays. Only one array will be needed if 543 the decay rate is the same while a route is unreachable as while it is 544 reachable, or if the stability figure of merit does not decay while a 545 route is unreachable. 547 4.4.2 Data Structures per Decay Array and Reuse Index Array 549 The following are also computed from the configuration parameters 550 though not as directly. 552 o decay rate per tick (decay-delta-t) 554 o decay array size (decay-array-size) 556 o decay array (decay) 558 o reuse index array size (reuse-index-array-size) 560 o reuse index array (reuse-index-array) 562 For each decay rate specified, an array will be used to store the 563 value of a computed parameter raised to the power of the index of each 564 array element. This is to speed computations. The decay rate per 565 tick is an intermediate value expressed as a real number and used to 566 compute the values stored in the decay arrays. The array size is 567 computed from the decay memory limit configuration parameter expressed 568 as an array size or as a maximum hold time. 570 The decay array size must be of sufficient size to accommodate the 571 specified decay memory given the time granularity, or sufficient to 572 hold the number of array elements until integer rounding produces a 573 zero result if that value is smaller, or a implementation imposed 574 reasonable size to prevent configurations which use excessive memory. 575 Implementations may chose to make the array size shorter and multiply 576 more than once when decaying a long time interval to reduce storage. 578 The reuse index arrays serve a similar purpose to the decay arrays. 579 The amount of time until a route can be reused can be determined using 580 a array lookup. The array can be built given the decay rate. The 581 array is indexed using a scaled integer proportional to the ratio 582 between a current stability figure of merit value and the value needed 583 for the route to be reused. 585 4.4.3 Data Structures per Route 587 The following information must be maintained per route. A route here 588 is considered to be a tuple containing at least NLRI prefix, next hop, 589 and AS path. The tuple may also contain other BGP attributes such as 590 MULTI_EXIT_DISCRIMINATOR (MED). 592 stability figure of merit (figure-of-merit) 594 Each route must have a stability figure of merit per applicable 595 parameter set. 597 last time updated (time-update) 598 The exact last time updated must be maintained to allow exponential 599 decay of the accumulated figure of merit to be deferred until the 600 route might reasonable be considered eligible for a change in 601 status (having gone from unreachable to reachable or advancing 602 within the reuse lists). 604 config block pointer 606 Any implementation that supports multiple parameter sets must 607 provide a means of quickly identifying which set of parameters 608 corresponds to the route currently being considered. For 609 implementations supporting only parameter sets where all routes 610 must be treated the same, this pointer is not required. 612 reuse list traversal pointers 614 If doubly linked lists are used to implement reuse lists, then two 615 pointers will be needed, previous and next. Generally there is a 616 double linked list which is unused when a route is suppressed from 617 use that can be used for reuse list traversal eliminating the need 618 for additional pointer storage. 620 4.5 Processing Configuration Parameters 622 From the configuration parameters, it is possible to precompute a 623 number of values that will be used repeatedly and retain these to 624 speed later computations that will be required frequently. 626 The methods of scaled integer arithmetic are not described in detail 627 here. The methods of determining the real values are given. 628 Translation into scaled integer values and the details of scaled 629 integer arithmetic are left up to the individual implementations. 631 figure of merit scale factor ( scale-figure-of-merit ) 633 The ceiling value can be set to be the largest integer that can fit 634 in half the bits available for an unsigned integer. This will 635 allow the scaled integers to be multiplied by the scaled decay 636 value and then shifted down. Implementations may prefer to use 637 real numbers or may use any integer scaling deemed appropriate for 638 their architecture. 640 penalty value and thresholds (as proportional scaled integers) 642 The figure of merit penalty for one route withdrawal and the cutoff 643 values must be scaled according to the above scaling factor. 645 decay rate per tick (decay[1]) 646 The decay value per increment of time as defined by the time 647 granularity must be determined (at least initially as a floating 648 point number). The per tick decay is a number slightly less than 649 one. It is the Nth root of the one half where N is the half life 650 divided by the time granularity. 652 decay[1] = exp ((1 / (decay-rate/delta-t)) * log (1/2)) 654 decay array size (decay-array-size) 656 The decay array size is the decay memory divided by the time 657 granularity. If integer truncation brings the value of an array 658 element to zero, the array can be made smaller. An implementation 659 should also impose a maximum reasonable array size or allow more 660 than one multiplication. 662 decay-array-size = (Tmax/delta-t) 664 decay array (decay[]) 666 Each i-th element of the decay array is the per tick delay raised 667 to the i-th power. This might be best done by successive floating 668 point multiplies followed by scaling and integer rounding or 669 truncation. The array itself need only be computed at startup. 671 decay[i] = decay[1] ** i 673 4.6 Building the Reuse Index Arrays 675 The reuse lists may be accessed quite frequently if a lot of routes 676 are flapping sufficiently to be suppressed. A method of speeding the 677 determination of which reuse list to use for a given route is 678 suggested. This method is introduced in Section 4.2, its 679 configuration described in Section 4.4.2 and the algorithms described 680 in Section 4.8.6 and Section 4.8.7. This section describes building 681 the reuse list index arrays. 683 A ratio of the figure of merit of the route under consideration to the 684 cutoff value is used as the basis for an array lookup. The ratio is 685 scaled and truncated to an integer and used to index the array. The 686 array entry is an integer used to determine which reuse list to use. 688 reuse array maximum ratio (max-ratio) 689 This is the maximum ratio between the current value of the 690 stability figure of merit and the target reuse value that can be 691 indexed by the reuse array. It may be limited by the ceiling 692 imposed by the maximum hold time or by the amount of time that the 693 reuse lists cover. 695 max-ratio = min(ceiling/reuse, exp((1 / 696 (half-life/reuse-array-time)) * log(1/2))) 698 reuse array scale factor ( scale-factor ) 700 Since the reuse array is an estimator, the reuse array scale factor 701 has to be computed such that the full size of the reuse array is 702 used. 704 scale-factor = (max-ratio - 1) / reuse-array-size 706 reuse index array (reuse) 708 Each reuse index array entry should contain an index into the reuse 709 list array pointing to one of the list heads. This index should 710 corresponding to the reuse list that will be evaluated just after a 711 route would be eligible for reuse given the ratio of current value 712 of the stability figure of merit to target reuse value 713 corresponding the the reuse array entry. 715 reuse-array[j] = integer(log(1 / (1 + ((j+1) * 716 (max-ratio-1)))) / reuse-time-granularity) 718 To determine which reuse queue to place a route which is being 719 suppressed, the following procedure is used. Divide the current 720 figure of merit by the cutoff. Subtract one. Multiply by the scale 721 factor. This is the array index. If it is off the end of the array 722 use the last queue otherwise look in the array and pick the number of 723 the queue from the array at that index. This is quite fast and well 724 worth the setup and storage required. 726 4.7 A Sample Configuration 728 A simple example is presented here in which the space overhead is 729 estimated for a set of configuration parameters. The design here 730 assumes: 732 1. there is a single parameter set used for all routes, 734 2. decay time for unreachable routes is slower than for reachable 735 routes 737 3. the arrays must be full size, rather than allow more than one 738 multiply per decay operation to reduce the array size. 740 This example is used in later sections. The use of multiple parameter 741 sets complicates the examples somewhat. Where multiple parameter sets 742 are allowed for a single route, the decay portion of the algorithm is 743 repeated for each parameter set. If different routes are allowed to 744 have different parameter sets, the routes must have pointers to the 745 parameter sets to keep the time to locate to a minimum, but the 746 algorithms are otherwise unchanged. 748 A sample set of configuration parameters and a sample set of 749 implementation parameters are provided in in the two following list. 751 1. Configuration Parameters 753 o cut = 1.25 755 o reuse = 0.5 757 o T-hold = 15 mins 759 o decay-ok = 5 min 761 o decay-ng = 15 min 763 o Tmax-ok, Tmax-ng = 15, 30 mins 765 2. Implementation Parameters 767 o delta-t = 1 sec 769 o delta-reuse 771 o reuse-list-size = 256 773 o reuse-index-array-size = 1,024 775 Using these configuration and implementation parameters and the 776 equations in Section 4.5, the space overhead can be computed. There 777 Figure 3: Some fairly long route flap cycles, repeated for 12 778 minutes, followed by a period of stability. 780 is a fixed space overhead that is independent of the number of routes. 781 There is an space requirement associated with a stable route. There 782 is a larger space requirement associated with an unstable route. The 783 space requirements for the parameters above are provide in the lists 784 below. 786 1. fixed overhead (using parameters from previous example) 788 o 900 * integer - decay array 790 o 1,800 * integer - decay array 792 o 120 * pointer - reuse list-heads 794 o 2,048 * integer - reuse index arrays 796 2. overhead per stable route 798 o pointer - containing null entry 800 3. overhead per unstable route 802 o pointer - to a damping structure containing the following 804 o integer - figure of merit + bit for state 806 o integer - last time updated 808 o pointer (optional) to configuration parameter block 810 o 2 * pointer - reuse list pointers (prev, next) 812 Figure 3 shows the behavior of the algorithm with the parameters given 813 above. Four cases are given in this example. In all four, there is a 814 twelve minute period of route oscillations. Two periods of oscilla- 815 tion are used, 2 minutes and 4 minutes. Two duty cycles are used, one 816 in which the route is reachable during 20% of the cycle and the other 817 where the route is reachable during 80% of the cycle. In all four 818 cases, the route becomes suppressed after it becomes unreachable the 819 second time. Once suppressed, it remains suppressed until some period 820 after becoming stable. The routes which oscillate over a 4 minute pe- 821 riod are no longer suppressed within 9-11 minutes after becoming sta- 822 ble. The routes with a 2 minute period of oscillation are suppressed for 823 nearly the maximum 15 minute period after becoming stable. 825 4.8 Processing Routing Protocol Activity 827 The prior sections concentrate on configuration parameters and their 828 relationship to the parameters and arrays used at run time and provide 829 the algorithms for initializing run time storage. This section 830 provides the steps taken in processing routing events and timer events 831 when running. 833 The routing events are: 835 1. A BGP peer or new route comes up for the first time (or after an 836 extended down time) (Section 4.8.1) 838 2. A route becomes unreachable (Section 4.8.2) 840 3. A route becomes reachable again (Section 4.8.3) 842 4. A route changes (Section 4.8.4) 844 5. A peer goes down (Section 4.8.5) 846 The reuse list is used to provide a means of fast evaluation of route 847 that had been suppressed, but had been stable long enough to be reused 848 again. The following two operations are described. 850 1. Inserting into a reuse list (Section 4.8.6) 852 2. Reuse list processing every delta-t seconds (Section 4.8.7) 854 4.8.1 Processing a New Peer or New Routes 856 When a peer comes up, no action is required if the routes had no 857 previous history of instability, for example if this is the first time 858 the peer is coming up and announcing these routes. For each route, 859 the pointer to the damping structure would be zeroed and route used. 860 The same action is taken for a new route or a route that has been down 861 long enough that the figure of merit reached zero and the damping 862 structure was deleted. 864 4.8.2 Processing Unreachable Messages 866 When a route is withdrawn or changed (Section 4.8.4 describes how a 867 change is handled), the following procedure is used. 869 If there is no previous stability history (the damping structure 870 pointer is zero), then: 872 1. allocate a damping structure 874 2. set figure-of-merit = 1 876 3. withdraw the route 878 Otherwise, if there is an existing damping structure, then: 880 1. set t-diff = t-now - t-updated 882 2. if (t-diff puts you off the end of the array) { 884 setfigure-of-merit =1 886 }else { 888 setfigure-of-merit =figure-of-merit *decay-array-ok [t-diff ]+ 1 890 if(figure-of-merit >ceiling) { 892 setfigure-of-merit =ceiling 894 } 896 } 898 3. remove the route from a reuse list if it is on one 900 4. withdraw the route unless it is already suppressed 902 In either case then: 904 1. set t-updated = t-now 906 2. insert into a reuse list (see Section 4.8.6) 907 If there was a stability history, the previous value of the stability 908 figure of merit is decayed. This is done using the decay array 909 (decay-array). The index is determined by subtracting the current 910 time and the last time updated, then dividing by the time granularity. 911 If the index is zero, the figure of merit is unchanged (no decay). If 912 it is greater than the array size, it is zeroed. Otherwise use the 913 index to fetch a decay array element and multiply the figure of merit 914 by the array element. If using the suggested scaled integer method, 915 shift down half an integer. Add the scaled penalty for one more un- 916 reachable (shown above as 1). If the result is above the ceiling re- 917 place it with the ceiling value. Now update the last time updated field 918 (preferably taking into account how much time was truncated before doing 919 the decay calculation). 921 When a route becomes unreachable, alternate paths must be considered. 922 This process is complicated slightly if different configuration param- 923 eters are used in the presence or absence of viable alternate paths. 924 If all of these alternate paths have been suppressed because there had 925 previously been an alternate route and the new route withdrawal 926 changes that condition, the suppressed alternate paths must be reeval- 927 uated. They should be reevaluated in order of normal route prefer- 928 ence. When one of these alternate routes is encountered that had been 929 suppressed but is now usable since there is no alternate route, no 930 further routes need to be reevaluated. This only applies if routes 931 are given two different reuse thresholds, one for use when there is an al- 932 ternate path and a higher threshold to use when suppressing the route would 933 result in making the destination completely unreachable. 935 4.8.3 Processing Route Advertisements 937 When a route is readvertised if there is no damping structure, then 938 the procedure is the same as in Section 4.8.1. 940 1. don't create a new damping structure 942 2. use the route 944 If an damping structure exists, the figure of merit is decayed and the 945 figure of merit and last time updated fields are updated. A decision 946 is now made as to whether the route can be used immediately or needs 947 to be suppressed for some period of time. 949 1. set t-diff = t-now - t-updated 951 2. if (t-diff puts you off the end of the array) { 952 setfigure-of-merit =0 954 }else { 956 set figure-of-merit= figure-of-merit* decay-array-ng[t-diff] 958 } 960 3. if ( not suppressed and figure-of-merit < cut ) { 962 usethe route 964 }else if( suppressedand figure-of-merit< reuse) { 966 setstate tonot suppressed 968 removethe routefrom areuse listif itis on one 970 usethe route 972 }else { 974 setstate tosuppressed 976 don'tuse theroute 978 insertinto areuse list(see Section4.8.6) 980 } 982 4. if ( figure-of-merit > 0 ) { 984 set t-updated= t-now 986 }else { 988 recovermemory fordamping struct 990 zeropointer todamping struct 992 } 994 If the route is deemed usable, a search for the current best route 995 must be made. The newly reachable route is then evaluated according 996 to the BGP protocol rules for route selection. 998 If the new route is usable, the previous best route is examined. 999 Prior to coute comparisons, the current best route may have to be 1000 reevaluated if separate parameter sets are used depending on the 1001 presence or absence of an alternate route. If there had been no 1002 alternate the previous best route may be suppressed. 1004 If the new route is to be suppressed it is placed on a reuse list only 1005 if it would have been preferred to the current best route had the new 1006 route been accepted as stable. There is no reason to queue a route on 1007 a reuse list if after the route becomes usable it would not be used 1008 anyway due to the existence of a more preferred route. Such a route 1009 would not have to be reevaluated unless the preferred route became 1010 unreachable. As specified here, the less preferred route would be 1011 reevaluated and potentially used or potentially added to a reuse list 1012 when processing the withdrawal of a more preferred best route. 1014 4.8.4 Processing Route Changes 1016 If a route is replaced by a peer router by supplying a new path, the 1017 route that is being replaced should be treated as if an unreachable 1018 were received (see Section 4.8.2). This will occur when a peer 1019 somewhere back in the AS path is continuously switching between two AS 1020 paths and that peer is not damping route flap (or applying less 1021 damping). There is no way to determine if one AS path is stable and 1022 the other is flapping, or if they are both flapping. If the cycle is 1023 sufficiently short compared to convergence times neither route through 1024 that peer will deliver packets very reliably. Since there is no way 1025 to affect the peer such that it choses the stable of the two AS paths, 1026 the only viable option is to penalize both routes by considering each change 1027 as an unreachable followed by a route advertisement. 1029 4.8.5 Processing A Peer Router Loss 1031 When a peer routing session is broken, either all individual routes 1032 advertised by that peer may be marked as unstable, or the peering 1033 session itself may be marked as unstable. Marking the peer will save 1034 considerable memory. Since the individual routes are advertised as 1035 unreachable to routers beyond the immediate problem, per route state 1036 will be incurred beyond the peer immediately adjacent to the BGP 1037 session that went down. If the instability continues, the immediately 1038 adjacent router need only keep track of the peer stability history. 1039 The routers beyond that point will receive no further advertisements 1040 or withdrawal of routes and will dispose of the damping structure over 1041 time. 1043 BGP notification through an optional transitive attribute that damping 1044 will already be applied may be considered in the future to reduce the 1045 number of routers that incur damping structure storage overhead. 1047 4.8.6 Inserting into the Reuse Timer List 1049 The reuse lists are used to provide a means of fast evaluation of 1050 route that had been suppressed, but had been stable long enough to be 1051 reused again. The data structure consists of a series of list heads. 1052 Each list contains a set of routes that are scheduled for reevaluation 1053 at approximately the same time. The set of reuse list heads are 1054 treated as a circular array. 1056 A simple implementation of the circular array of list heads would be 1057 an array containing the list heads with an offset. The offset would 1058 identify the first list. The Nth list would be at the index 1059 corresponding to N plus the offset modulo the number of list heads. 1060 This design will be assumed in the examples that follow. 1062 A key requirement is to be able to insert an entry in the most 1063 appropriate queue with a minimum of computation. The computation is 1064 given only the current value of figure-of-merit. The array, scale, 1065 and bounds are precomputed to map figure-of-merit to the nearest list 1066 head without requiring a logarithm to be computed (see Section 4.5). 1068 1. scale figure-of-merit for the index array lookup producing index 1070 2. check index against the array bound 1072 3. if (within the array bound) { 1074 setindex =reuse-array [index ] 1076 }else { 1078 setindex =reuse-list-size -1 1080 } 1082 4. insertinto thelist 1084 reuse-list[ moduloreuse-list-size (index +offset )] 1086 Choosing the correct reuse list involves only a multiply and shift to 1087 do the scaling, an integer truncation, then an array lookup. The most 1088 common method of implementing a circular array is to use an array and 1089 apply an offset and modulo operation to pick the correct array entry. 1090 The offset is incremented to rotate the the circular array. 1092 4.8.7 Handling Reuse Timer Events 1094 The granularity of the reuse timer should be more course that that of 1095 the decay timer. As a result, when the reuse timer fires, suppressed 1096 routes should be decayed by multiple increments of decay time. Some 1097 computation can be avoided by always inserting into the reuse list 1098 corresponding to one time increment past reuse eligibility. In cases 1099 where the reuse lists have a longer ``memory'' than the ``decay 1100 memory'' (described above), all of the routes in the first queue will 1101 be available for immediate reuse. 1103 When it is time to advance the lists, the first queue on the reuse 1104 list must be processed and the circular queue must be rotated. Using 1105 an array and an offset as a circular array (as described in 1106 Section 4.8.6), the algorithm below is repeated every t-reuse seconds. 1108 1. save a pointer to the current zeroth queue head and zero the list 1109 head entry 1111 2. set offset = modulo reuse-list-size ( offset + 1 ), thereby 1112 rotating the circular queue of list-heads 1114 3. if ( the saved list head pointer is non-empty ) 1116 foreach entry { 1118 sett-diff =t-now -t-updated 1120 setfigure-of-merit =figure-of-merit *decay-array-ok [t-diff ] 1122 sett-updated =t-now 1124 if( figure-of-merit< reuse) 1126 reusethe route 1128 else 1130 re-insertinto anotherlist (seeSection 4.8.6) 1132 } 1134 The value of the zeroth list head would be saved and the array entry 1135 itself zeroed. The list heads would then be advanced by incrementing 1136 the offset. Starting with the saved head of the old zeroth list, each 1137 route would be reevaluated and used or requeued if it were not ready 1138 for reuse. If a route is used, it must be treated as if it were a new 1139 route advertisement as described in Section 4.8.3. 1141 5 Implementation Experience 1143 The first implementations of ``route flap damping'' were the route 1144 server daemon (rsd) coding by Ramesh Govindan (ISI) and the Cisco IOS 1145 implementation by Ravi Chandra. Both implementations first became 1146 available in 1995 and have been used extensively. The rsd 1147 implementation has been in use in route servers at the NSF funded 1148 Network Access Points (NAPs) and at other major Internet 1149 interconnects. The Cisco IOS version has been in use by Internet 1150 Service Providers worldwide. The rsd implementation has been 1151 integrated in releases of gated (see http://www.gated.org) and is 1152 available in commercial routers using gated. 1154 Acknowledgements 1156 This work and this document may not have been completed without the 1157 advise, comments and encouragement of Yakov Rekhter (Cisco). Dennis 1158 Ferguson (MCI) provided a description of the algorithms in the gated 1159 BGP implementation and many valuable comments and insights. David 1160 Bolen (ANS) and Jordan Becker (ANS) provided valuable comments, 1161 particularly regarding early simulations. At the time of this writing 1162 two implementations exists. One was led by Ramesh Govindan (ISI) for 1163 the NSF Routing Arbiter project. The second was led by Ravi Chandra 1164 (Cisco). Sean Doran (Sprintlink) and Serpil Bayraktar (ANS) were 1165 among the early independent testers of the Cisco pre-beta 1166 implementation. 1168 References 1170 [1] P. Gross and Y. Rekhter. Application of the border gateway proto- 1171 col in 1172 the internet. Request for Comments (Draft Standard) RFC 1268, In- 1173 ternet Engineering Task Force, October 1991. (Obsoletes RFC1164); 1174 (Obsoleted by RFC1655). ftp://ds.internic.net/rfc/rfc1268.txt. 1175 [2] ISO/IEC. Iso/iec 10747 - information technology - telecommunica- 1176 tions and information exchange between systems - protocol for 1177 exchange of inter-domain routeing information among intermediate 1178 systems to support forwarding of iso 1179 8473 pdus. Technical report, International Organization for Stan- 1180 dardization, August 1994. ftp://merit.edu/pub/iso/idrp.ps.gz. 1182 [3] K. Lougheed and Y. Rekhter. A border gateway protocol 3 (BGP-3). 1183 Request for Comments (Draft Standard) RFC 1267, In- 1184 ternet Engineering Task Force, October 1991. (Obsoletes RFC1163). 1185 ftp://ds.internic.net/rfc/rfc1267.txt. 1187 [4] Y. Rekhter and P. Gross. Application of the border gateway proto- 1188 col in the internet. Request for Comments (Draft Standard) 1189 RFC 1772, Internet Engineering Task Force, March 1995. (Obsoletes 1190 RFC1655). ftp://ds.internic.net/rfc/rfc1772.txt. 1192 [5] Y. Rekhter and T. Li. A border 1193 gateway protocol 4 (BGP-4). Request for Comments (Draft Standard) 1194 RFC 1771, Internet Engineering Task Force, March 1995. (Obsoletes 1195 RFC1654). ftp://ds.internic.net/rfc/rfc1771.txt. 1197 [6] Y. Rekhter and C. Topolcic. Exchanging routing information across 1198 provider boundaries in the CIDR environment. Request for Comments 1199 (Informational) RFC 1520, Internet Engineering Task Force, 1200 September 1993. ftp://ds.internic.net/rfc/rfc1520.txt. 1201 [7] P. Traina. BGP-4 protocol analysis. Request for Comments (Infor- 1202 mational) RFC 1774, Internet Engineering Task Force, March 1995. 1203 ftp://ds.internic.net/rfc/rfc1774.txt. 1205 [8] P. Traina. Experience with the BGP-4 protocol. Request for Com- 1206 ments (Informational) RFC 1773, 1207 Internet Engineering Task Force, March 1995. (Obsoletes RFC1656). 1208 ftp://ds.internic.net/rfc/rfc1773.txt. 1210 Security Considerations 1212 The practices outlined in this document do not further weaken the 1213 security of the routing protocols. Denial of service is possible in 1214 an already insecure routing environment but these practices only 1215 contribute to the persistence of such attacks and do not impact the 1216 methods of prevention and the methods of determining the source. 1218 Author's Addresses 1220 Curtis Villamizar 1222 ANS Communications 1224 1226 Ravi Chandra 1228 Cisco Systems 1229 1231 Ramesh Govindan 1233 ISI 1235