idnits 2.17.1 draft-berkowitz-bgpcon-01.txt: -(134): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(327): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** 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? == There are 3 instances of lines with non-ascii characters in the document. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 1 longer page, the longest (page 1) being 1145 lines Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** 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 an Authors' Addresses Section. ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 5 instances of too long lines in the document, the longest one being 4 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 77 has weird spacing: '...rwarded traff...' == Line 154 has weird spacing: '...istinct stage...' == Line 213 has weird spacing: '...onfused with...' == Line 214 has weird spacing: '... to the busin...' == Line 294 has weird spacing: '...pt that route...' == (25 more instances...) == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- 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 (March 2000) is 8800 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) -- Missing reference section? '1' on line 119 looks like a reference -- Missing reference section? '2' on line 46 looks like a reference -- Missing reference section? '3' on line 808 looks like a reference -- Missing reference section? '4' on line 862 looks like a reference -- Missing reference section? '12' on line 311 looks like a reference -- Missing reference section? '10' on line 514 looks like a reference -- Missing reference section? '13' on line 520 looks like a reference -- Missing reference section? '14' on line 628 looks like a reference -- Missing reference section? '15' on line 633 looks like a reference Summary: 7 errors (**), 0 flaws (~~), 11 warnings (==), 11 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Network Working Group H.Berkowitz 2 Internet Draft A.Retana 3 Expires August 2001 S.Hares 4 P.Krishnaswamy 5 draft-berkowitz-bgpcon-01.txt March 2000 7 Benchmarking Methodology for Exterior Routing Convergence 9 Status of this Memo 11 This document is an Internet-Draft and is in full conformance with 12 all provisions of Section 10 of RFC2026 [1]. 14 Internet-Drafts are working documents of the Internet Engineering 15 Task Force (IETF), its areas, and its working groups. Note that 16 other groups may also distribute working documents as Internet- 17 Drafts. 19 Internet-Drafts are draft documents valid for a maximum of six 20 months and may be updated, replaced, or made obsolete by other 21 documents at any time. It is inappropriate to use Internet- Drafts 22 as reference material or to cite them other than as "work in 23 progress." 25 The list of current Internet-Drafts can be accessed at 26 http://www.ietf.org/ietf/1id-abstracts.txt. 28 The list of Internet-Draft Shadow Directories can be accessed at 29 http://www.ietf.org/shadow.html. 31 Abstract 32 This is an update of an individual contribution that has been 33 accepted as a work item by the Benchmarking Methodology Working 34 Group, and will split into two BMWG documents. It is being posted 35 for information. T This document defines a specific set of tests that 36 router implementers can use to measure and report the convergence 37 performance of BGP-4 processes. It doe not consider the forwarding 38 performance of such routers once they have converged, or the convergence 39 characteristics of the global routing system. 41 Conventions used in this document 43 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 44 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in 45 this document are to be interpreted as described in RFC-2119 [2]. 47 Table of Contents 48 1. Introduction.....................................................2 49 1.1 Overview and Roadmap...........................................3 50 1.2 Definition Format..............................................3 51 2. Definitions of convergence-related router and network states or 52 components............................................................4 53 2.1 BGP Peer.......................................................4 54 2.2 The routing information Base (RIB) and its constituents Adj-Rib- 55 In, Adj-Rib-Out, Loc-RIB............................................4 56 2.3 The Forwarding Information Base or FIB.........................5 57 2.4 Default Free routing tables....................................6 59 Berkowitz et al Expires January 2001 1 60 Benchmarking Methodology for Exterior Routing Convergence 62 2.5 Prefix.........................................................6 63 2.6 Route..........................................................6 64 2.7 BGP Route......................................................7 65 2.8 Default Route..................................................7 66 2.9 Route Instance.................................................7 67 2.10 Unique Route.................................................8 68 2.11 Route Views..................................................8 69 2.12 Policy.......................................................8 70 2.13 Policy Information Base......................................9 71 2.14 Route Flap...................................................9 72 2.15 Convergence.................................................11 73 3. Factors that impact the performance of the convergence process..11 74 3.1 Number of peers...............................................11 75 3.2 Number of routes per peer.....................................11 76 3.3 Policy processing/reconfiguration.............................11 77 3.4 Forwarded traffic............................................11 78 3.5 Flap dampening................................................12 79 3.6 Authentication................................................12 80 3.7 MBGP Processing...............................................12 81 4. Test Configuration..............................................12 82 5. Test setup and methodology......................................13 83 5.1.1. Stages of convergence and events triggering reconvergence 13 84 6. Tests measuring Full Initial convergence with a single peer.....14 85 7. Incremental Reconvergence.......................................15 86 7.1 Route Announcements...........................................15 87 7.1.1. Explicit announce of single new route (Tupinit)[3,4]....15 88 7.1.2. Implicit withdraw of single route and replace by new 89 announced route (AAdiff)..........................................15 90 7.1.3. Duplicate announcments (AAdup)...........................16 91 7.2 Route withdrawal..............................................16 92 7.2.1. Explicit withdraw of single route (Tdown)................16 93 7.2.2. Explicit Withdrawal followed by an reannounce (WAdup)....16 94 7.2.3. Failover to existing Alternate Path after Explicit 95 Withdrawal (no announce WF).......................................17 96 7.2.4. Explicit withdraw of an existing route followed by announce 97 of a different route (WAdiff).....................................17 98 7.3 Repetitive route updates (flaps)..............................17 99 8. Multiple Peers..................................................18 100 8.1 Initial Convergence...........................................18 101 9. References......................................................18 102 10. Acknowledgments................................................19 104 1. Introduction 105 This document describes a specific set of tests aimed at 106 characterizing the convergence performance of BGP-4 processes in 107 routers or other boxes that incorporate BGP functionality. A key 108 objective is to propose methodology that will facilitate the 109 conducting and reporting of convergence-related measurements in a 110 standard fashion. Although both convergence and forwarding are 111 essential to basic router operation, this document does not consider 112 the forwarding performance,if applicable, in the Device Under Test 113 (DUT),for two reasons. Forwarding performance is the primary focus 114 in [1] and it is expected that it will be dealt with in work that 116 Berkowitz et al Expires January 2001 2 117 Benchmarking Methodology for Exterior Routing Convergence 119 ensues from [1]; further, as convergence characterization is a 120 complex process, we would deliberately like to restrict the initial 121 focus in this document to specifying how to take basic measurements 122 towards this objective. 124 Subsequent drafts will explore the more intricate aspects of 125 convergence measurement, e.g. in the presence of policy processing 126 and other realistic performance modifiers such as simultaneous 127 traffic on the control and data paths within the DUT. Convergence in 128 Interior Gateway Protocols will also be dealt with in separate 129 drafts. 131 1.1 Overview and Roadmap 133 In general, measurements of routing protocol convergence can be 134 classified either as �internal�, with time-stamped tables indicating 135 the time of completion of convergence (such as those described in 136 [4], or �external�. In an external measurement, a process in the 137 Device Under Test (DUT) is inferred to have converged after a 138 downstream measurement device indicates the corresponding 139 advertisement has been received by it. An alternative type of 140 external measurement is to test for data forwarded to the downstream 141 device that relies upon the route that the Device Under Test just 142 converged upon. The external technique is more readily applicable 143 than the internal technique at present since the requisite NTP 144 timestamp hooks may not yet be in products. However, the external 145 technique is less accurate as it also includes the time to advertise 146 the new route downstream and transmission times for the 147 advertisement. If data forwarding were to feature in the measurement 148 methodology it too would include some extraneous latency- that of 149 the forwarding lookup process in the DUT at the minimum. This 150 document deals only with external measurements limited to route 151 propagation. 153 A characterization of the BGP convergence performance of a device 154 must take into account, if not also time, all distinct stages and 155 aspects of BGP functionality. This requires that the relevant terms 156 and metrics be as specific as possible. Consequently the first step 157 taken here towards detailing measurements of convergence performance 158 will be to define all the relevant terms and concepts. 160 The necessary definitions are classified into two separate 161 categories: 162 . Descriptions of the constituent elements of a network or a 163 router that is undergoing convergence 164 . Descriptions of factors that impact convergence processes 165 which will influence measurements on convergence. 167 1.2 Definition Format 169 The definition format is the equivalent to that defined in [12], 170 and is repeated here for convenience: 172 Berkowitz et al Expires January 2001 3 173 Benchmarking Methodology for Exterior Routing Convergence 175 X.x Term to be defined. (e.g., Latency) 177 Definition: 178 The specific definition for the term. 180 Discussion: 181 A brief discussion about the term, its application and any 182 restrictions on measurement procedures. 184 Measurement units: 185 The units used to report measurements of this term, if 186 applicable. 188 Issues: 190 List of issues or conditions that affect this term. 192 See Also: 193 List of other terms that are relevant to the discussion of 194 this term. 196 2. Definitions of convergence-related router and network states or 197 components 198 Many terms included in this list of definitions were described 199 originally in previous standards or papers. They are included here 200 because of their pertinence to this discussion. Where relevant, 201 reference is made to these sources. An effort has been made to keep 202 this list complete with regard to the necessary concepts without 203 overdefinition. 205 2.1 BGP Peer 207 Definition: 208 A BGP peer is another BGP process to which the DUT has established a 209 TCP connection over which a BGP session is active. Peers send BGP 210 advertisements to the DUT and receive DUT-originated advertisements. 212 Discussion: 213 This is a protocol-specific definition, not to be confused with 214 another frequent usage, which refers to the business/economic 215 definition for the exchange of routes without financial 216 compensation. 218 Measurement units: 220 Issues: 222 See Also: 224 2.2 The routing information Base (RIB) and its constituents Adj-Rib-In, 225 Adj-Rib-Out, Loc-RIB 227 Berkowitz et al Expires January 2001 4 228 Benchmarking Methodology for Exterior Routing Convergence 230 Definition: 232 These terms were defined in [10]. The RIB contains all 233 destination prefixes to which the router may forward, and one or 234 more currently reachable next hop addresses for them. Routes 235 included in this table potentially have been selected from several 236 sources of information, including hardware status, interior routing 237 protocols, and exterior routing protocols. RFC 1812 [12] contains a 238 basic set of route selection criteria relevant in an all-source 239 context. Many implementations impose additional criteria. A common 240 implementation-specific criterion is the preference given to 241 different routing information sources. 243 The Forwarding Information Base (see next item) is generated from 244 the RIB.The Loc-RIB contains the set of best routes selected from 245 the various Adj-RIBs,after applying local policies and the BGP route 246 selection algorithm.Adj-RIB-In and Adj-RIB-Out are "views" of 247 routing information from the perspective of individual peer routers. 248 The Adj-RIB-In contains information advertised to the DUT by a 249 specific peer. The Adj-RIB-Out contains the information the DUT 250 will advertise to the peer. 252 Discussion: 253 The separation implied between the various RIBs is logical. It does 254 not necessarily follow that these RIBs are distinct and separate 255 entities in any given implementation. 257 Measurement Units: 258 Number of route instances 260 Issues: 261 Specifying the RIB is important because the types and relative 262 proportions of routes in it can affect the convergence efficiency. 263 Types of routes can include internal BGP, external BGP, interface 264 and IGP routes. 266 See Also: Route, BGP Route, Route Instance 268 2.3 The Forwarding Information Base or FIB 270 Definition: The FIB is referred to in [10] as well as [12] but not 271 defined in either. For the purposes of this document, the FIB is the 272 last lookup on the router data path, based on which a next hop is 273 selected for forwarding each packet. 275 Discussion: Most current implementations have full, non-cached FIBs 276 per router interface. All the route computation and convergence 277 occurs before a route is downloaded into a FIB. 279 Measurement Units: N.A. 281 Issues: 283 Berkowitz et al Expires January 2001 5 284 Benchmarking Methodology for Exterior Routing Convergence 286 See Also: Route 288 2.4 Default Free routing tables 290 Definition: 291 The size of routing tables in the default free zone of the Internet. 293 Discussion: 294 The term originates from the concept that routers at the core or 295 top tier of the Internet will not be configured with a default route 296 (Notation 0.0.0.0/0). Thus they will forward every prefix to a 297 specific nexthop based upon the longest match. 298 Default free routing table size is commonly used as an indicator of 299 the magnitude of reachable Internet address space. However,default 300 free routing tables may also include routes internal to the 301 infrastructural net that a router is part of. 303 Measurement Units: number of routes 305 Issues: 306 See Also: Routes,Route Instances, Default Route 308 2.5 Prefix 310 Definition: A destination address in CIDR format. 311 Expressed as prefix/length. The definition in [12] is "A 312 network prefix is..a contiguous set of bits at the more significant 313 end of the address that defines a set of systems;host numbers select 314 among those systems." 316 Discussion: A prefix is expressed as a portion of an IP address 317 followed by the associated mask such as 10/8. 319 Measurement Units: N.A. 321 Issues: 323 See Also: 325 2.6 Route 327 Definition: In general, a �route� is the tuple . If 328 MPLS is supported the tuple may include 330 Discussion: This term refers to the concept of a route common to all 331 routing protocols. 333 Measurement Units: N.A. 335 Issues: None. 337 Berkowitz et al Expires January 2001 6 338 Benchmarking Methodology for Exterior Routing Convergence 340 See Also: BGP route 342 2.7 BGP Route 344 Definition: The tuple [10] 346 Discussion: Attributes are mentioned in [10], and are by inference, 347 qualifying data that accompanies a prefix in a BGP route." For 348 purposes of this protocol a route is defined as a unit of 349 information that pairs a destination with the attributes of a path 350 to 351 that destination... A variable length sequence of path attributes is 352 present in every UPDATE. Each path attribute is a triple of variable length." Nexthop 354 is one type of attribute. 356 Measurement Units:N.A. 358 Issues: 360 See Also: Route, prefix. 362 2.8 Default Route 363 A Default Route is a route entry that can match any prefix. If a 364 router does not have a route for a particular packet's destination 365 address, it forwards this packet to the next hop in the default 366 route entry if its FIB contains one. The notation for a default 367 route is 0.0.0.0/0 369 Discussion: Core routers do not contain default routes. Access and 370 edge routers are likely to have default route entries. 372 Measurement units: N.A. 374 Issues: 376 See Also: default free routing table, route, route instance 378 2.9 Route Instance 380 This term is used in the context of a BGP Adj RIB In. 382 Definition: 384 Single occurrence of route sent by BGP Peer for a particular prefix. 385 When a router has multiple peers from which it accepts routes, 386 routes to the same prefix may recur in the various Adj-Ribs-In. This 387 is then a case of multiple route instances. 389 Discussion 391 Berkowitz et al Expires January 2001 7 392 Benchmarking Methodology for Exterior Routing Convergence 394 Route instances may not be selected by the BGP selection algorithm 395 due to local policy. 397 Measurement Units:number of instances 399 Issues: the number of route instances in the Adj-Rib-in bases will 400 vary based on the function to be performed by a router. A core 401 router will likely receive more route instances than an access 402 router. A core router is situated in the default-free zone. 404 See Also: 406 2.10 Unique Route 407 Definition: A unique route is a prefix for which there is just one 408 route instance. 409 Discussion: 410 Measurement Units:N.A. 411 Issues: 412 See Also: route, route instance 414 2.11 Route Views 416 Definition: 418 Route views must be further specified as incoming or outgoing. An 419 incoming route view is AFI/SAFI and peer specific and is the Adj- 420 Rib-In for that peer and AFI/SAFI. An outgoing route view is also 421 peer and AFi/SAFI specific and is the Adj-Rib-Out for that peer, for 422 a given AFI/SAFI combination. 424 Discussion: 426 Measurement Units: N.A. 428 Issues: 430 See Also: 432 2.12 Policy 434 Definition: 435 Policy is "the ability to define conditions for accepting, 436 rejecting, and modifying routes received in advertisements"[16] 437 Policy processing is the set of actions performed by the BGP route 438 selection algorithm that influences route selection in the presence 439 of attributes in the route updates received from peers, or policy 440 actions configured to influence outbound BGP route advertisements. 442 Discussion:RFC 1771 [10] further defines policy constraints in the 443 hop-by-hop routing paradigm. 445 Berkowitz et al Expires January 2001 8 446 Benchmarking Methodology for Exterior Routing Convergence 448 Measurement Units: 450 Issues: Policy is implemented using filters . 452 See Also: Policy Information Base. 454 2.13 Policy Information Base 456 Definition: 458 A policy information base is the set of incoming and outgoing 459 policies. All references to the phase of the BGP selection process 460 here are made with respect to RFC 1771 [10] definition of these 461 phases. 462 Incoming policies are applied in Phase 1 of the BGP selection 463 process [10]to the Adj-Rib-In routes to set the metric for the Phase 464 2 decision process. Outgoing Policies are applied in Phase 3 of 465 the BGP process to the Adj-Rib-Out routes to allow route (prefix and 466 path attribute tuple) to be announced out to a specific peer. 468 Discussion: 470 Policies in the Policy information base often instantiated as "route 471 maps" and filter/access lists. The "route maps" often operate on or 472 use the "path attribute" portion of the BGP route. On incoming 473 policy, these "route maps" may set a metric to be compared in Phase 474 2 of the BGP process.[10] On the outgoing policy, the "route maps" 475 may also set outgoing path attributes to the route sent to the peer. 477 The filter lists/access lists track the route prefixes. 479 The amount of policy processing (both in terms of route maps and 480 filter/access lists) will impact the convergence time of the BGP 481 algorithm. The amount of policy processing may vary from a simple 482 policy which accepts all routes and sends all routes to complex 483 policy with a substantial fraction of the prefixes being filtered by 484 filter/access lists. 486 For this first round of tests for BGP convergence, we recommend that 487 the tests be run under the simple policy of "accept all routes and 488 and send all routes." 490 2.14 Route Flap 492 Definition: 494 RFC 2439 [13]refers to route flapping as 496 "An excessive rate of update to the advertised reachability 497 of a subset of Internet prefixes.." 499 Berkowitz et al Expires January 2001 9 500 Benchmarking Methodology for Exterior Routing Convergence 502 We would like to refine this description for the purpose of 503 benchmark specification to be: 505 "Repeated excessive updates to route instances in the Adj- 506 Rib-In on the DUT." 508 Discussion: 510 These repeated updates can be either 511 a) Implicit replaces of routes [10] categorized in [4] as: 512 either AADiff or AAdup. 514 b) Explicit replaces of routes [10] categorized by [4] as 515 either: WADiff, WAdup, 517 c)Erroneous Duplicate Withdrawals for the same route as 518 categorized in [4] as WWDup. 520 The threshold that can be declared excessive by RFC 2439 [13] is 521 configured by each network on the basis of: 523 "cutoff threshold (cut) 525 This value is expressed as a number of route withdrawals. 526 It is the value above which a route advertisement will be 527 suppressed. 529 reuse threshold (reuse) 531 This value is expressed as a number of route withdrawals. 532 It is the value below which a suppressed route will now be used 533 again. " 535 Measurement units 537 Flapping events per unit time. 539 Specific Flap events are: 541 1) AADiff 542 2) AADup 543 3) WADiff 544 4) WADup 545 5) WWDup 547 The Flapping event sequence can be characterized as mixture of 548 these events with a percentage per type. An example of this would 549 be: 551 20% AADiff, 40% AAdup, 30% WADiff 10% WWdup at 100 flap 552 events per second. 554 Berkowitz et al Expires January 2001 10 555 Benchmarking Methodology for Exterior Routing Convergence 557 2.15 Convergence 559 Definition: A router is said to have converged onto a route 560 advertised to it, given that route is the best route instance for a 561 prefix, (if multiple choices exist for that prefix) when this route 562 is advertised to its downstream peers. 564 Discussion: The best route instance should be set so as to be 565 unambiguous during test setup/definition. This document does not 566 consider forwarding-dependent illustrations of convergence. 568 Measurement Units: N.A. 570 Issues: 572 See Also: 574 3. Factors that impact the performance of the convergence process 576 Some of these factors will not be incorporated into the tests in 577 this document. This is because, as mentioned earlier, specifying 578 characterization methodology will be undertaken in stages according 579 to complexity starting with the more baseline tests. 581 3.1 Number of peers 583 As the number of peers increases, the BGP route selection algorithm 584 is increasingly exercised. The phasing and frequency of updates from 585 the various peers will have a marked effect on the convergence 586 process on a router. 588 3.2 Number of routes per peer 589 The number of routes per BGP peer is an obvious stressor to the 590 convergence process. The number, and relative proportion, of 591 multiple route instances and distinct routes being added or 592 withdrawn by each peer will affect the convergence process. So will 593 the mix of overlapping route instances, and IGP routes. 595 3.3 Policy processing/reconfiguration 596 The number of routes and attributes being filtered for, and 597 set,as a fraction of the target route table size is another 598 parameter that will affect BGP convergence. 599 The two extremes are: 601 Minimal Policy 602 Extensive policy--. For example, upto 80 % of the total routes 603 must have applicable 604 policy. 606 3.4 Forwarded traffic 608 The presence of actual traffic in the router may stress the control 609 path in some fashion if both the offered load due to data and the 611 Berkowitz et al Expires January 2001 11 612 Benchmarking Methodology for Exterior Routing Convergence 614 control traffic (FIB updates and downloads as a consequence of 615 flaps)are excessive. This is implementation dependent. This 616 condition is a more accurate reflection of realistic operating 617 scenarios than if no data traffic is present. 619 3.5 Flap dampening 620 Flap Damping occurs in response to frequent alterations in the 621 route instances input to the DUT. If this is in effect, it requires 622 that the router keep additional state to carry out the damping, 623 which has a direct impact on the control plane due to increased 624 processing. 626 3.6 Authentication 627 Authentication in BGP is currently done using the TCP MD5 Signature 628 Option [14]. The processing of the MD5 hash, specially in routers 629 with a large number of BGP peers and a large ammount of update 630 traffic may have an impact on the control plane of the router. 632 3.7 MBGP Processing 633 Multiprotocol extension for BGP are defined in [15], giving BGP the 634 ability to carry routing information for multiple address families 635 (not only IPv4 unicast). Processing of different protocol 636 information encoded using these multiprotocol extensions may have an 637 impact on the convergence of any one protocol. The tests presented 638 in this document may be applicable to any specific address family. 640 4. Test Configuration 642 Figure 1 illustrates the single peer test case: 644 TR1==========+---------+==========TR3 645 | | | 646 D | | 647 | | DUT | 648 TR2==========| | 649 +---------+ 651 D is a prefix reachable by both TR1 and TR2. It is assumed that 652 neither TR1 or TR2 is the AS of origin for the announcement of D. 653 For all test routers and the DUT, all routes fed in as part of this 654 test process are EBGP routes. 656 More complex peering arrangements will involve up to n Test Routers, 657 as shown in Figure 2. It is recommended that the Figure 1 658 configuration always be tested as a baseline, and then additional 659 reports made that show the effect on performance of increasing the 660 number of peers. All tests defined in this document use the topology 661 shown unless explicitly noted. 663 TR1==========+---------+==========TR3 664 | | | 665 D | | 666 | | DUT | 668 Berkowitz et al Expires January 2001 12 669 Benchmarking Methodology for Exterior Routing Convergence 671 TR2==========| | 672 | | 673 ... 674 TRn==========+---------+ 676 Interface speeds must be specified as part of the test report. At 677 least a 100 Mbps speed link and a full duplex MAC layer between all 678 connected devices are recommended. 679 In the absence of other route selection criteria, TR1 shall have an 680 IP address that makes it most preferred. 682 5. Test setup and methodology 684 'Test routers' will be providing the test traffic to the Device 685 Under Test and collecting the evidence of convergence from it, if 686 any. The only traffic in the cases described here is route 687 updates/withdrawals. The requisite TCP sessions will have to be 688 established between all test routers and the DUT. Any other 689 equipment required to trace the flow of BGP messages between the 690 devices actually participating in the test will need to be 691 transparent to these sessions. It is also desirable that the 'Test 692 routers' be able to generate protocol message sequences at settable 693 rates. 695 5.1.1. Stages of convergence and events triggering reconvergence 697 5.1.1.1 Full Initialization 699 The DUT establishes a TCP connection, then a BGP session, with a peer, 700 and accepts routes from it. Full initialization of this sort is 701 expected to be relatively infrequent compared with incremental 702 convergence. 704 5.1.1.2 Incremental Convergence 705 There are several distinct operations which could be categorized as 706 incremental convergence. 707 A taxonomy characterising routing information changes seen in 708 operational networks is described in [3] as well as [4]. These 709 papers describe BGP protocol-centric events, or event sequences in 710 the course of an analysis of network behavior. The terminology in 711 the two papers addresses similar but slightly different events. The 712 former refers to Tup,T ,T , and Tlong indicating the 714 down short , 715 occurrence of a route first coming up, being withdrawn,and routes with 716 shorter or 717 longer ASPATHs respectively. The first two denote explicit events. The 718 last two refer to implicit re-announces of a shorter or longer 719 route. 720 In [4],the notation used was WADiff (explicit), WADup, AADiff,which 721 is implicit and AADup, also implicit. 723 With regard to the benchmarking methodology under discussion, we 724 would like to apply the foregoing taxonomies to categorise the tests 726 Berkowitz et al Expires January 2001 13 727 Benchmarking Methodology for Exterior Routing Convergence 729 under definition where possible, because these tests must tie in to 730 phenomena that arise in actual networks. We avail of, or extend, 731 this terminology as necessary for this purpose. In this document, 732 the meaning of Tup and Tdown are preserved and extended from [3]. 733 The notation Tup(TRx) stands for a Tup event advertised to the 734 router being tested (i.e., DUT). We also introduce Tupinit to indicate 735 the initial announcement of a route to a unique prefix. 737 {is this used?}The sense of the Tshort and Tlong events is also 738 preserved, but the basic criterion for selecting a "better" route is 739 the final tiebreaker defined in RFC1771, the router ID. As a 740 consequence, this memorandum uses the events Tbetter, Tworse, and 741 Tbest. They are defined as: 742 Tbest -- The current best path. 743 Tbetter -- Advertise a path that is better than Tbest. 744 T -- Advertise a path that is worst than Tbest. 745 worst 747 Categories of incremental convergence: 748 These tests list basic operations that occur on a single router in 749 response to route updates / withdrawals typical of network 750 instabilities. Only the fundamental operations are selected because 751 they form the basis of all more intricate responses. Longer 752 sequences of protocol updates require a compounding of the responses 753 listed here. In addition the arrival rate as well as pattern of 754 route updates/withdrawals is an important factor in the stress 755 testing of a router's convergence. 757 --Add single route (Tupinit) 758 --Delete single route (Tdown) 759 --Add/deletes of multiple routes in increments until the full table 760 is advertised or withdrawn at once . This could include 761 repetitions of the basic operations of Tupinit 763 , 764 WAdiff,WAdup,AAdup,AAdiff 765 --Delete Peer/Readd 766 This causes a full convergence type of operation. The test 767 router terminates the TCP connection and BGP session with the 768 peer, then reestablishes the BGP session. When the session is 769 reestablished, routing information must be exchanged again. 770 --Delete multiple peers and readd. 771 When multiple peers are sending or receiving routes from the 772 DUT, the percentage of route instances, unique routes, and the total 773 number of routes from or to each peer. 774 --Failover to an existing less preferred route on withdrawal of 775 preferred route (Wf) 777 6. Tests measuring Full Initial convergence with a single peer 779 Procedure: 780 Initialize the test scenario by establishing an eBGP session between 781 the DUT and TR3. No routing information is exchanged. Initialize TR1 782 with a predetermined number of prefixes. Suggested fractions are 784 Berkowitz et al Expires January 2001 14 785 Benchmarking Methodology for Exterior Routing Convergence 787 10%,20%,50% and 100% of the full routing table. The physical link 788 between TR1 and the DUT should also be active at this time. 790 Establish an eBGP session between TR1 and the DUT; all the prefixes in 791 TR1 should be advertised at this time to the DUT. 793 The convergence time measurement should start when the first OPEN 794 message is exchanged between TR1 and the DUT. The end of the 795 convergence period is marked when TR3 receives the last UPDATE from the 796 DUT. 798 It is expected that the DUT will install the routes in its FIB. 799 However, this test will neither check for, nor verify this. 801 7. Incremental Reconvergence 803 This set of tests measures the convergence after the initial full 804 BGP table has been transmitted to and processed by the DUT.The test 805 procedures are based on the cases described in section 4. 807 7.1 Route Announcements 808 7.1.1. Explicit announce of single new route (Tupinit)[3,4] 809 This test measures the time required to add a route newly advertised by 810 a peer (Tup(TRx)). Such a route does not exist in the DUT's RIB, and 811 will not displace a route in the RIB. 813 Procedure : 815 Initialize the test scenario by establishing an eBGP session between 816 the DUT and TR1 and between the DUT and TR3. TR1 should advertise a 817 predetermined number of routes to the DUT, which in turn should 818 advertise it to TR3. 820 -Advertise a route originated in TR1; Tup(TR1,D). 822 --The reconvergence time measurement should start when 823 TR1 sends the UPDATE containing the route D. The end of the 824 reconvergence period is marked when TR3 has received the UPDATE 825 containing D. 827 7.1.2. Implicit withdraw of single route and replace by new announced 828 route (AAdiff) 830 This test measures the time required to replace an existing route with 831 one that is preferred (Tbetter(TRx)). Such a route exists in the DUT's 832 RIB, and will be replaced by the new advertisement. 834 Procedure : 836 Initialize the test scenario by establishing an eBGP session between 837 the DUT and TR1 and between the DUT and TR3. TR1 should advertise a 838 predetermined number of routes to the DUT, which in turn should 840 Berkowitz et al Expires January 2001 15 841 Benchmarking Methodology for Exterior Routing Convergence 843 advertise it to TR3. The set of routes advertised by TR1 should 844 contain the test route D. 846 -Advertise a replacement route for D from TR1; 847 Tbetter(TR1,D). 849 This route should have LOCAL_PREF value that is preferred over 850 the original advertisement for D. 852 --The reconvergence time measurement should start when TR1 sends the 853 UPDATE containing the replacement route. The end of the 854 reconvergence period is marked when TR3 has received the new UPDATE 855 containing the replacement. 857 Variations to this test may consist in selecting other attributes to 858 replace in a consecutive update.The attribute used should be indicated 859 in the results and no filters should be used. 861 7.1.3. Duplicate announcments (AAdup) 862 From [4], this type of event occurs and may be caused by policy 863 changes or flaps within the "MinRouteAdvertisementInterval" of 30 864 seconds. 865 7.2 Route withdrawal 867 7.2.1. Explicit withdraw of single route (Tdown) 869 This test measures the time required to withdraw a route advertised by 870 a peer (Tdown(TRx)). Such a route exists in the DUT's RIB, and will be 871 removed. 873 Procedure 875 Initialize the test scenario by establishing an eBGP session between 876 the DUT and TR1 and between the DUT and TR3. TR1 should advertise a 877 predetermined number of routes to the DUT, which in turn should 878 advertise them to TR3. 880 Withdraw a route previously originated in TR1; Tdown(TR1,D). 882 The reconvergence time measurement should start then TR1 sends the 883 withdraw message containing the route D. The end of the 884 reconvergence period is marked when TR3 has received the 885 corresponding withdraw message. 887 7.2.2. Explicit Withdrawal followed by an reannounce (WAdup) 889 This test combines 6.2 and 6.3.1.and measures the time required to 890 withdraw ((Tdown(TRx)) and reinstall (Tup(TRx)) a route advertised 891 by a peer. Such a route initially exists in the DUT's RIB, it will 892 be removed and then reinstalled. 894 Procedure: 896 Berkowitz et al Expires January 2001 16 897 Benchmarking Methodology for Exterior Routing Convergence 899 Initialize the test scenario by establishing an eBGP session between 900 the DUT and TR1 and between the DUT and TR3. TR1 should advertise a 901 predetermined number of routes to the DUT, which in turn should 902 advertise them to TR3. 904 Withdraw a route previously advertised by TR1; Tdown(TR1). 906 After a predetermined ammount of time, TR1 readvertises the same 907 withdrawn route (Tup(TR1)) to the DUT. 909 The reconvergence time measurement should start then TR1 sends the 910 withdraw message containing the route D. The end of the 911 reconvergence period is marked when TR3 has received the UPDATE 912 containing D. 914 7.2.3. Failover to existing Alternate Path after Explicit Withdrawal 915 (no announce WF) 917 This test measures the time to replace a path with an existing 918 alternate after an explicit withdraw (Tdown(TRx)) of the current best 919 path (Tbest). 921 Procedure: 923 Initialize TR1 and TR2 with a predetermined number of routes. These 924 routes should be for the same prefixes. 926 Initialize the test scenario by establishing an eBGP session between 927 the DUT and TR1, TR2 and TR3. TR1 and TR2 should advertise their 928 routes and the DUT should advertise the best path to TR3. 930 The routes advertised by TR1 and TR2 should be such that the DUT 931 selects the path through TR1 as the best. The decision should be made 932 by comparing the LOCAL_PREF between the two available paths. At this 933 point the DUT should have a path from both TR1 and TR2 for every 934 prefix. 936 TR1 sends a withdraw for a specific route (D); Tdown (TR1,D). 938 The reconvergence time measurement should start when TR1 sends the 939 withdraw message for D. The end of the reconvergence period is 940 marked when TR3 receives the new UPDATE containing the path through 941 TR2. 943 This test may also be executed by increasing the number of routes 944 withdrawn by TR1 or by increasing the number of alternate paths 945 available(increase the test routers up to TRn). 947 7.2.4. Explicit withdraw of an existing route followed by announce of 948 a different route (WAdiff) 950 7.3 Repetitive route updates (flaps) 952 Berkowitz et al Expires January 2001 17 953 Benchmarking Methodology for Exterior Routing Convergence 955 Once the basic protocol update responses have been calibrated,longer 956 event sequences must be tested for. These sequences may look like 957 AwAdiffwadupAAdup..and occur at, eg, 300 per second.Announces will 958 be more overhead intensive than withdraws. 960 8. Multiple Peers 962 8.1 Initial Convergence 964 This test is similar to the single peer initial convergence time, but 965 the number of external peers should increase. All peers are expected 966 to advertise the same number of routes to the DUT. 968 A ratio of n paths per prefix may be considered such that the first n 969 neighbors must advertise the exact same prefixes (only the AS_PATH 970 should be different). If the number of eBGP peers tested goes beyond 971 n, then the routes should be distributed among all the peers so that 972 the ratio is maintained and all advertise the same number of routes. 974 Procedure: 976 Initialize the test scenario by establishing an eBGP session between 977 the DUT and TR3. No routing information is exchanged. 979 Initialize TR1 and up to TRn with a predetermined number of prefixes 980 such that such that the ratio is maintained. The physical link 981 between TR1 thru TRn and the DUT should also be active at this time. 983 Establish an eBGP session between TR1 thru TRn and the DUT. Each TR 984 router should belong to a different AS. All the prefixes in TR1 thru 985 TRn should be advertised at this time to the DUT. 987 The convergence time measurement should start when the first OPEN 988 message is exchanged between any TR and the DUT. The end of the 989 convergence period is marked when all the TR routers have advertised 990 all the paths to the DUT, and TR3 has received the last UPDATE. 992 The number of test routers should be increased in equal intervals 993 until the maximum number under test is reached. 995 It is expected that the DUT will install the routes in its FIB. 996 However, this test will not test for this. 998 9. References 1000 1 Bradner, S., "The Internet Standards Process -- Revision 1001 3", BCP 9, RFC 2026, October 1996. 1002 2 Bradner, S., "Key words for use in RFCs to Indicate 1003 Requirement Levels", BCP 14, RFC 2119, March 1997. 1004 3 "An Experimental Study of Delayed Internet Routing 1005 Convergence." Abha Ahuja, Farnam Jahanian, Abhijit Bose, 1006 Craig Labovitz, RIPE 37 - Routing WG. 1008 Berkowitz et al Expires January 2001 18 1009 Benchmarking Methodology for Exterior Routing Convergence 1011 4 "Origins of Internet Routing Instability," Infocom 99 1012 Craig Labovitz, G. Robert Malan, Farnam Jahanian], 1013 5 "BGP Route Flap Damping" C. Villamizar, R.Chandra, R. 1014 Govindan, RFC 2539 November 1998. 1015 6 "Benchmarking Methodology for Network Interconnect 1016 Devices",RFC 2544, S. Bradner, J. McQuaid. March 1999. 1017 7 Routing Policy Specification Language (RPSL), RFC 2622, " 1018 C.Alaettinoglu, C. Villamizar, E. Gerich, D. Kessens, D. 1019 Meyer, T.Bates, D. Karrenberg, M. Terpstra. June 1999. 1020 8 "Route Refresh Capability for BGP-4", RFC 2928, E. Chen. 1021 9 "Terminology for Forwarding Information Based (FIB)based 1022 Router Performance Benchmarking", Work in Progress, 1023 IETF,draft-ietf-bmwg-fib-term-00.txt 1024 10 "A Border Gateway Protocol 4 (BGP-4)", RFC 1771, Y. 1025 Rekhter, T. Li. March 1995. 1026 11 "Benchmarking Terminology for Network Interconnection 1027 Devices",RFC 1242, S. Bradner. July 1991. 1028 12 "Requirements for IP Version 4 Routers", RFC 1812, F. 1029 Baker. June 1995. 1030 13 "BGP Route Flap Damping", RFC 2439, C. Villamizar, R. 1031 Chandra, R. Govindan. November 1998. 1032 14 "Protection of BGP Sessions via the TCP MD5 Signature 1033 Option", RFC 2385, A. Heffernan. August 1998. 1034 15 "Multiprotocol Extensions for BGP-4", RFC 2858, T. 1035 Bates,Y. Rekhter, R. Chandra, D. Katz. June 2000. 1036 16 Junos 4.2 Software Routing Guide 1037 17 RIPE 178, "RIPE Routing-WG Recommendation for coordinated 1038 route-flap damping parameters, Tony Barber, Sean Doran, 1039 Daniel Karrenberg, Christian Panigl, Joachim Schmitz 1041 10. Acknowledgments 1042 Thanks to Francis Ovenden for review and Abha Ahuja for 1043 encouragement.Much appreciation to Jeff Haas, Matt Richardson, and 1044 Shane Wright at Nexthop for comments and input. 1046 9 Author's Addresses 1048 Howard Berkowitz 1049 Nortel Networks 1050 5012 S. 25th St 1051 PO Box 6897 1052 Arlington VA 22206 1054 Phone: +1 703 998-5819 (ESN 451-5819) 1055 Fax: +1 703 998-5058 1056 EMail: hberkowi@nortelnetworks.com 1057 hcb@clark.net 1059 Alvaro Retana 1060 Cisco Systems, Inc. 1061 7025 Kit Creek Rd. 1063 Berkowitz et al Expires January 2001 19 1064 Benchmarking Methodology for Exterior Routing Convergence 1066 Research Triangle Park, NC 27709 1067 Email: aretana@cisco.com 1069 Susan Hares 1070 Nexthop Technologies 1071 517 W. William 1072 Ann Arbor, Mi 48103 1073 Phone: 1074 Email: skh@nexthop.com 1076 Padma Krishnaswamy 1077 Nexthop Technologies 1078 517 W William 1079 Ann Arbor, Mi 48103 1080 Phone: 1081 Email: kri@nexthop.com 1083 Full Copyright Statement 1085 Copyright (C) The Internet Society (2000). All Rights Reserved. 1087 This document and translations of it may be copied and furnished 1088 to others, and derivative works that comment on or otherwise explain 1089 it or assist in its implmentation may be prepared, copied, published 1090 and distributed, in whole or in part, without restriction of any 1091 kind, provided that the above copyright notice and this paragraph 1092 are included on all such copies and derivative works. However, this 1093 document itself may not be modified in any way, such as by removing 1094 the copyright notice or references to the Internet Society or other 1095 Internet organizations, except as needed for the purpose of 1096 developing Internet standards in which case the procedures for 1097 copyrights defined in the Internet Standards process must be 1098 followed, or as required to translate it into languages other than 1099 English. 1101 The limited permissions granted above are perpetual and will not 1102 be revoked by the Internet Society or its successors or assigns. 1104 This document and the information contained herein is provided on 1105 an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET 1106 ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, 1107 INCLUDIN BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 1108 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1109 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1111 ----- End forwarded message -----