idnits 2.17.1 draft-ietf-bmwg-conterm-01.txt: 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 Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 25 longer pages, the longest (page 2) being 59 lines 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. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 55 has weird spacing: '...network of ro...' == Line 161 has weird spacing: '...network of ro...' == Line 586 has weird spacing: '...are the quali...' == Line 852 has weird spacing: '...tral to the b...' == Line 861 has weird spacing: '...ysis of netwo...' == (3 more instances...) -- 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 (February 2002) is 8105 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: '15' is defined on line 1198, but no explicit reference was found in the text ** Obsolete normative reference: RFC 1771 (ref. '3') (Obsoleted by RFC 4271) -- Possible downref: Non-RFC (?) normative reference: ref. '6' -- Possible downref: Non-RFC (?) normative reference: ref. '7' -- Possible downref: Non-RFC (?) normative reference: ref. '9' ** Obsolete normative reference: RFC 2385 (ref. '10') (Obsoleted by RFC 5925) -- Possible downref: Non-RFC (?) normative reference: ref. '11' -- Possible downref: Non-RFC (?) normative reference: ref. '12' -- Possible downref: Non-RFC (?) normative reference: ref. '13' -- Possible downref: Non-RFC (?) normative reference: ref. '14' -- Possible downref: Non-RFC (?) normative reference: ref. '15' ** Obsolete normative reference: RFC 2547 (ref. '16') (Obsoleted by RFC 4364) == Outdated reference: A later version (-13) exists of draft-ietf-idr-restart-02 Summary: 8 errors (**), 0 flaws (~~), 11 warnings (==), 10 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Benchmarking Working Group H.Berkowitz, Gett Communications 3 Internet Draft S.Hares, Next Hop 4 Document: draft-ietf-bmwg-conterm-01.txt A.Retana, Cisco 5 Expires August 2002 P.Krishnaswamy, Consultant 6 M.Lepp, Juniper Networks 7 E.Davies, Nortel Networks 8 February 2002 10 Terminology for Benchmarking 11 External Routing Convergence Measurements 13 Status of this Memo 15 This document is an Internet-Draft and is in full conformance with 16 all provisions of Section 10 of RFC2026 [1]. 17 Internet-Drafts are working documents of the Internet Engineering 18 Task Force (IETF), its areas, and its working groups. Note that other 19 groups may also distribute working documents as Internet-Drafts. 20 Internet-Drafts are draft documents valid for a maximum of six months 21 and may be updated, replaced, or obsoleted by other documents at any 22 time. It is inappropriate to use Internet- Drafts as reference 23 material or to cite them other than as "work in progress." 25 The list of current Internet-Drafts can be accessed at 26 http://www.ietf.org/ietf/1id-abstracts.txt 27 The list of Internet-Draft Shadow Directories can be accessed at 28 http://www.ietf.org/shadow.html. 30 A revised version of this draft document will be submitted to the RFC 31 editor as a Informational document for the Internet Community. 32 Discussion and suggestions for improvement are requested. 33 This document will expire before August 2002. Distribution of this 34 draft is unlimited. 36 Abstract 38 This draft establishes terminology to standardize the description of 39 benchmarking methodology for measuring eBGP convergence in the 40 control plane of a single BGP device. Future documents will address 41 iBGP convergence, the initiation of forwarding based on converged 42 control plane information and internet-wide convergence. 44 Conventions used in this document 46 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 47 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 48 document are to be interpreted as described in RFC-2119 [2]. 50 Berkowitz, et al 1 51 Table of Contents 52 1. Introduction....................................................3 53 1.1 Overview and Roadmap.......................................3 54 1.2 Definition Format..........................................3 55 2. Constituent elements of a router or network of routers.........4 56 2.1 BGP Peer...................................................4 57 2.2 Default Route, Default Free Table, and Full Table..........5 58 2.3 Classes of BGP-Speaking Routers............................7 59 3. Routing Data Structures.........................................9 60 3.1 Routing Information Base (RIB).............................9 61 3.2 Policy....................................................10 62 3.3 Policy Information Base...................................11 63 3.4 The Forwarding Information Base (FIB).....................12 64 4. Components and characteristics of Routing information..........12 65 4.1 Prefix....................................................12 66 4.2 Route.....................................................13 67 4.3 BGP Route.................................................13 68 4.4 Route Instance............................................14 69 4.5 Active Route..............................................14 70 4.6 Unique Route..............................................14 71 4.7 Non-Unique Route..........................................15 72 4.8 Route Packing.............................................15 73 4.9 Route Mixture.............................................15 74 4.10 Update Train...........................................16 75 4.11 Route Flap.............................................18 76 5. Route Changes and Convergence..................................18 77 5.1 Route Change Events.......................................18 78 5.2 Convergence...............................................19 79 6. BGP Operation Events...........................................20 80 6.1 Hard reset................................................20 81 6.2 Soft reset................................................21 82 7. Factors that impact the performance of the convergence process.21 83 7.1 General factors affecting BGP convergence.................21 84 7.2 Implementation-specific and other factors affecting BGP 85 convergence............................................22 86 8. Security Considerations........................................23 87 9. References.....................................................24 88 10. Acknowledgments...............................................25 89 11. Author's Addresses............................................25 91 Berkowitz, et al Expires: August 2002 2 92 1. Introduction 94 This document defines terminology for use in characterizing the 95 convergence performance of BGP processes in routers or other devices 96 that instantiate BGP functionality. It is the first part of a two 97 document series, of which the subsequent document will contain the 98 associated tests and methodology. 100 The following observations underlie the approach adopted in this, and 101 the companion document: 102 - The principal objective is to derive methodologies to standardize 103 conducting and reporting convergence-related measurements for BGP. 104 - It is necessary to remove ambiguity from many frequently used 105 terms that arise in the context of such measurements. 106 - As convergence characterization is a complex process, it is 107 desirable to restrict the initial focus in this set of documents 108 to specifying how to take basic control plane measurements as a 109 first step to characterizing BGP convergence. 111 For path vector protocols such as BGP, the primary initial focus will 112 therefore be on network and system control-plane activity consisting 113 of the arrival, processing, and propagation of routing information 114 Subsequent drafts will explore the more intricate aspects of 115 convergence measurement, such as the impacts of the presence of 116 policy processing, simultaneous traffic on the control and data paths 117 within the DUT, and other realistic performance modifiers. 118 Convergence of Interior Gateway Protocols will also be considered in 119 separate drafts. 121 1.1 Overview and Roadmap 123 Characterizations of the BGP convergence performance of a device must 124 take into account all distinct stages and aspects of BGP 125 functionality. This requires that the relevant terms and metrics be 126 as specifically defined as possible. Such definition is the goal of 127 this document. 129 The necessary definitions are classified into two separate 130 categories: 131 - Descriptions of the constituent elements of a network or a router 132 that is undergoing convergence 133 - Descriptions of factors that impact convergence processes 135 1.2 Definition Format 137 The definition format is equivalent to that defined in [5], and is 138 repeated here for convenience: 140 X.x Term to be defined. (e.g., Latency) 142 Definition: 143 The specific definition for the term being defined. 145 Berkowitz, et al Expires: August 2002 3 146 Discussion: 147 A brief discussion of the term, its application and any 148 restrictions that there might be on measurement 149 procedures. 151 Measurement units: 152 The units used to report measurements of this term, if 153 applicable. 154 Issues: 155 List of issues or conditions that could affect this term. 157 See Also: 158 List of related terms that are relevant to the definition 159 or discussion of this term. 161 2. Constituent elements of a router or network of routers. 163 Many terms included in this list of definitions were originally 164 described in previous standards or papers. They are included here 165 because of their pertinence to this discussion. Where relevant, 166 reference is made to these sources. An effort has been made to keep 167 this list complete with regard to the necessary concepts without over 168 definition. 170 2.1 BGP Peer 172 Definition: 173 A BGP peer is another BGP instance to which the Device 174 Under Test (DUT) has established a TCP connection over 175 which a BGP session is active. In the test scenarios in 176 the methodology discussion that will follow this draft, 177 peers send BGP advertisements to the DUT and receive DUT- 178 originated advertisements. 180 Discussion: 181 This is a protocol-specific definition, not to be confused 182 with another frequent usage, which refers to the 183 business/economic definition for the exchange of routes 184 without financial compensation. 186 It is worth noting that a BGP peer, by this definition is 187 associated with a BGP peering session, and there may be 188 more than one such active session on a router or on a 189 tester. The peering sessions referred to here may exist 190 between various classes of BGP routers (see section 2.3). 192 Measurement units: number of BGP peers 194 Issues: 196 See Also: 198 Berkowitz, et al Expires: August 2002 4 199 2.2 Default Route, Default Free Table, and Full Table 201 An individual router's routing table may not necessarily contain a 202 default route. Not having a default route, however, is not 203 synonymous with having a full default-free table(DFT). 204 It should be noted that the references to number of routes in this 205 section are to routes installed in the loc-RIB, not route instances, 206 and that the total number of route instances may be 4 to 10 times the 207 number of routes. 209 The actual path setup and forwarding of MPLS speaking routers are 210 outside the scope of this document. A device that computes BGP 211 routes that may give a sub-IP device information that it uses to set 212 up paths, however, has its BGP aspects within scope. 214 2.2.1 Default Route 216 Definition: 217 A Default Route is a route entry that can match any 218 prefix. If a router does not have a route for a particular 219 packet's destination address, it forwards this packet to 220 the next hop in the default route entry, provided its 221 Forwarding Table (Forwarding Information Base (FIB) 222 contains one. The notation for a default route is 223 0.0.0.0/0 225 Discussion: 227 Measurement units: N.A. 229 Issues: 231 See Also: default free routing table, route, route instance 233 Berkowitz, et al Expires: August 2002 5 234 2.2.2 Default Free Routing Table 236 Definition: 237 A routing table with no default routes, as typically seen 238 in routers in the core or top tier of routers in the 239 network. 241 Discussion: 242 The term originates from the concept that routers at the 243 core or top tier of the Internet will not be configured 244 with a default route (Notation 0.0.0.0/0). Thus they will 245 forward every prefix to a specific next hop based on the 246 longest match on the IP addresses. 248 Default free routing table size is commonly used as an 249 indicator of the magnitude of reachable Internet address 250 space. However, default free routing tables may also 251 include routes internal to the router's AS. 253 Measurements: The number of routes 255 See Also: Full Default Free, Default Route 257 2.2.3 Full Default Free Table 259 Definition: 260 A set of BGP routes generally accepted to be the complete 261 set of BGP routes collectively announced by the complete 262 set of autonomous systems making up the public Internet. 263 Due to the dynamic nature of the Internet, the exact size 264 and composition of this table may vary slightly depending 265 where and when it is observed. 266 Discussion: 267 Several investigators ([12],[13][14]) measure this on a 268 daily and/or weekly basis; June 2001 measurements put the 269 table at approximately 105,000 routes, growing 270 exponentially. 272 It is generally accepted that a full table, in this usage, 273 does not contain the infrastructure routes or individual 274 sub-aggregates of routes that are otherwise aggregated by 275 the provider before announcement to other autonomous 276 systems. 278 Measurement Units: number of routes 280 Issues: 282 See Also: Routes, Route Instances, Default Route 284 Berkowitz, et al Expires: August 2002 6 285 2.2.4 Full Provider Internal Table 287 Definition: 288 A superset of the full routing table that contains 289 infrastructure and non-aggregated routes. 291 Discussion: 292 Experience has shown that this table can contain 1.3 to 293 1.5 times the number of routes in the externally visible 294 full table. Tables of this size, therefore, are a real- 295 world requirement for key internal provider routers. 297 Measurement Units: number of routes 299 Issues: 301 See Also: Routes, Route Instances, Default Route 303 2.3 Classes of BGP-Speaking Routers 305 A given router may perform more than one of the following functions, 306 based on its logical location in the network. 308 2.3.1 Provider Edge Router 310 Definition: 311 A router at the edge of a provider's network, configured 312 to speak BGP, which peers with a BGP speaking router 313 operated by the end-user. The traffic that transits this 314 router may be destined to, or originate from 315 non-contiguous autonomous systems. 317 Discussion: 318 Such a router will always speak eBGP and may speak iBGP. 320 Measurement units: 322 Issues: 324 See Also: 326 Berkowitz, et al Expires: August 2002 7 327 2.3.2 Subscriber Edge Router 329 Definition: 330 A BGP-speaking router belonging to an end user 331 organization that may be multi-homed, which carries 332 traffic only to and from that end user AS. 334 Discussion: 335 Such a router will always speak eBGP and may speak iBGP. 337 Measurement units: 339 Issues: 341 See Also: 343 2.3.3 Interprovider Border Router 345 Definition: 346 A BGP speaking router which maintains BGP sessions with 347 another BGP speaking router in another provider AS. 348 Traffic transiting this router may be directed to or from 349 another AS that has no direct connectivity with this 350 provider's AS. 352 Discussion: 353 Such a router will always speak eBGP and may speak iBGP. 355 Measurement units: 357 Issues: 359 See Also: 361 2.3.4 Intraprovider Core Router 363 Definition: 364 A provider router speaking iBGP to the provider's edge 365 routers, other intraprovider core routers, or the 366 provider's interprovider border routers. 368 Discussion: 369 Such a router will always speak iBGP and may speak eBGP. 371 Measurement units: 373 Issues: 374 MPLS speaking routers are outside the scope of this 375 document. It is entirely likely, however, that core Label 376 Switched Routers, especially in the P router role of 377 RFC 2547 [16], may contain little or no BGP information. 379 See Also: 381 Berkowitz, et al Expires: August 2002 8 382 3. Routing Data Structures 384 3.1 Routing Information Base (RIB) 386 The RIB collectively consists of a set of logically (not necessarily 387 literally) distinct databases, each of which is enumerated below. The 388 RIB contains all destination prefixes to which the router may 389 forward, and one or more currently reachable next hop addresses for 390 them. 392 Routes included in this set potentially have been selected from 393 several sources of information, including hardware status, interior 394 routing protocols, and exterior routing protocols. RFC 1812 contains 395 a basic set of route selection criteria relevant in an all-source 396 context. Many implementations impose additional criteria. A common 397 implementation-specific criterion is the preference given to 398 different routing information sources. 400 3.1.1 Adj-RIB-In and Adj-RIB-Out 402 Definition: 403 Adj-RIB-In and Adj-RIB-Out are "views" of routing 404 information from the perspective of individual peer 405 routers. 407 The Adj-RIB-In contains information advertised to the DUT 408 by a specific peer. The Adj-RIB-Out contains the 409 information the DUT will advertise to the peer. 411 See RFC 1771[3]. 413 Discussion: 415 Issues: 417 Measurement Units: Number of route instances 419 See Also: Route, BGP Route, Route Instance, Loc-RIB, FIB 421 Berkowitz, et al Expires: August 2002 9 422 3.1.2 Loc-RIB 424 Definition: 425 The Loc-RIB contains the set of best routes selected from 426 the various Adj-RIBs, after applying local policies and 427 the BGP route selection algorithm. 429 Discussion: 430 The separation implied between the various RIBs is 431 logical. It does not necessarily follow that these RIBs 432 are distinct and separate entities in any given 433 implementation. 435 Issues: 436 Specifying the RIB is important because the types and 437 relative proportions of routes in it can affect the 438 convergence efficiency. 440 Types of routes can include internal BGP, external 441 BGP,interface, static and IGP routes. 443 Measurement Units: Number of route instances. 445 See Also: Route, BGP Route, Route Instance, Adj-RIB-in, 446 Adj-RIB-out,FIB 448 3.2 Policy 450 Definition: 451 Policy is "the ability to define conditions for accepting, 452 rejecting, and modifying routes received in 453 advertisements"[15]. 455 Discussion: 456 RFC 1771 [3] further constrains policy to be within the 457 hop-by-hop routing paradigm. Policy is implemented using 458 filters and associated policy actions. Many AS's use 459 routing Policy Specification Language (RPSL) [8] to 460 document their policies and automatically generate 461 configurations for the BGP processes in their routers. 463 Measurement Units: 465 Issues: 467 See Also: Policy Information Base. 469 Berkowitz, et al Expires: August 2002 10 470 3.3 Policy Information Base 472 Definition: 473 A policy information base is the set of incoming and 474 outgoing policies. 476 Discussion: 477 All references to the phase of the BGP selection process 478 here are made with respect to RFC 1771 [3] definition of 479 these phases. 481 Incoming policies are applied in Phase 1 of the BGP 482 selection process [3] to the Adj-RIB-In routes to set the 483 metric for the Phase 2 decision process. Outgoing 484 Policies are applied in Phase 3 of the BGP process to the 485 Adj-RIB-Out routes preceding route (prefix and path 486 attribute tuple) announcements to a specific peer. 488 Policies in the Policy Information Base have matching and 489 action conditions. Common information to match include 490 route prefixes, AS paths, communities, etc. The action on 491 match may be to drop the update and not pass it to the 492 Loc-RIB, or to modify the update in some way, such as 493 changing local preference (on input) or MED (on output), 494 adding or deleting communities, prepending the current AS 495 in the AS path, etc. 497 The amount of policy processing (both in terms of route 498 maps and filter/access lists) will impact the convergence 499 time and properties of the distributed BGP algorithm. The 500 amount of policy processing may vary from a simple policy 501 which accepts all routes and sends all routes to complex 502 policy with a substantial fraction of the prefixes being 503 filtered by filter/access lists. 505 Measurement Units: 507 Issues: 509 See Also: 511 Berkowitz, et al Expires: August 2002 11 512 3.4 The Forwarding Information Base (FIB) 514 Definition: 515 The Forwarding Information Base is generated from the RIB. 516 The FIB is referred to in [3] as well as [5] but not 517 defined in either. For the purposes of this document, the 518 FIB is the subset of the RIB used by the forwarding plane 519 to make per-packet forwarding decisions. 521 Discussion: 522 Most current implementations have full, non-cached FIBs 523 per router interface. All the route computation and 524 convergence occurs before a route is downloaded into a 525 FIB. 527 Measurement Units: N.A. 529 Issues: 531 See Also: Route, RIB 533 4. Components and characteristics of Routing information 535 4.1 Prefix 537 Definition: 538 A destination address specified in CIDR format. Expressed 539 as prefix/length. The definition in [5] is "A network 540 prefix is a contiguous set of bits at the more significant 541 end of the address that defines a set of systems; host 542 numbers select among those systems." 544 Discussion: 545 A prefix is expressed as a portion of an IP address 546 followed by the associated mask such as 10/8. 548 Measurement Units: N.A. 550 Issues: 552 See Also 554 Berkowitz, et al Expires: August 2002 12 555 4.2 Route 557 Definition: 558 In general, a 'route' is the n-tuple 559 560 A route is not end-to-end, but is defined with respect to 561 a specific next hop that will move traffic closer to the 562 destination defined by the prefix. In this usage, a route 563 is the basic unit of information about a target 564 destination distilled from routing protocols. 566 Discussion: 567 This term refers to the concept of a route common to all 568 routing protocols. With reference to the definition above, 569 typical non-routing-protocol attributes would be 570 associated with diffserv or traffic engineering. 572 Measurement Units: N.A. 574 Issues: None. 576 See Also: BGP route 578 4.3 BGP Route 580 Definition: 581 The n-tuple 582 . 584 Discussion: 585 Nexthop is one type of attribute. Attributes are defined 586 in RFC 1771[3], and are the qualifying data that 587 accompanies a prefix in a BGP route. From RFC 1771: " For 588 purposes of this protocol a route is defined as a unit of 589 information that pairs a destination with the attributes 590 of a path to that destination... A variable length 591 sequence of path attributes is present in every UPDATE. 592 Each path attribute is a triple 593 594 of variable length." 596 Measurement Units: N.A. 598 Issues: 600 See Also: Route, prefix, Adj-RIB-in. 602 Berkowitz, et al Expires: August 2002 13 603 4.4 Route Instance 605 Definition: 606 A single occurrence of a route sent by a BGP Peer for a 607 particular prefix. When a router has multiple peers from 608 which it accepts routes, routes to the same prefix may be 609 received from several peers. This is then an example of 610 multiple route instances. 612 Discussion: 613 Each route instance is associated with a specific peer. A 614 specific route instance may be rejected by the BGP 615 selection algorithm due to local policy. 617 Measurement Units: number of route instances 619 Issues: 620 The number of route instances in the Adj-RIB-in bases will 621 vary based on the function to be performed by a router. An 622 inter-provider router, located in the default free zone 623 will likely receive more route instances than a provider 624 edge router, located closer to the end-users of the 625 network. 627 See Also: 629 4.5 Active Route 631 Definition: 632 Route for which there is a FIB entry corresponding to a 633 RIB entry. 635 Discussion: 637 Measurement Units: 639 Issues: 641 See also: RIB. 643 4.6 Unique Route 645 Definition: 646 A unique route is a prefix for which there is just one 647 route instance across all Adj-Ribs-In. 649 Discussion: 651 Measurement Units: N.A. 653 Issues: 655 See Also: route, route instance 657 Berkowitz, et al Expires: August 2002 14 658 4.7 Non-Unique Route 660 Definition: 661 A Non-unique route is a prefix for which there is at least 662 one other route in a set including more than one Adj-RIB- 663 in. 665 Discussion: 667 Measurement Units: N.A. 669 Issues: 671 See Also: route, route instance, unique active route. 673 4.8 Route Packing 675 Definition: 676 Number of route prefixes that exist in a single Routing 677 Protocol UPDATE Message either as updates (additions or 678 modifications) or withdrawals. 680 Discussion: 681 In general, a routing protocol update MAY contain more 682 than one prefix. In BGP, a single UPDATE MAY contain 683 multiple prefixes with identical attributes. Protocols 684 that do not support such a concept implicitly have a Route 685 Packing of 1. 687 Measurement Units: N.A. 689 Issues: 691 See Also: route, route instance, update train. 693 4.9 Route Mixture 695 Definition: 696 A characterization of the routes in a collection of 697 routes. Two profiles are used to characterize a 698 collection of routes as a route mixture: 699 - The distribution of prefix lengths in the collection 700 - The clustering of prefixes around particular branches 701 the tree which can be used to represent the totality 702 of possible prefixes. 704 Discussion: 705 Route mixtures are used to simulate the normal pattern of 706 prefix distribution that is seen in real world route 707 tables and update trains. As can be seen in the analyses 708 of BGP tables and traffic (e.g. [12], [13] and [14]), the 709 characterizations of the tables in the routers and the 710 network traffic appear to be different which has to be 712 Berkowitz, et al Expires: August 2002 15 713 taken into account in designing test stimuli appropriate 714 for particular types of testing. 716 Measurement Units: 717 Length profile: Probability distribution function on 718 possible discrete values of prefix 719 length (i.e 0-32 for IPv4) 720 Clustering profile: Probability distribution function on 721 'distance' between successive prefixes 722 which is a function of the prefix 723 lengths and the separation of the 724 branches of the address tree on which 725 they lie (FFS) 727 Issues: 729 See Also: 731 4.10 Update Train 733 Definition: 734 A set of Routing Protocol UPDATE messages, containing one 735 or more route prefixes, which an external router desires 736 to send to the DUT. When there is more than one prefix in 737 the set, the multiple updates (including withdrawals) may 738 be sent as individual BGP UPDATE packets, or as one or 739 more BGP packets with multiple routes packed (q.v.) into 740 them. If multiple UPDATE packets make up a train, the 741 time spacing of the packets needs to be specified. 743 Discussion: 744 The more individual UPDATE packets that are sent, the more 745 TCP and BGP header processing will be imposed on the 746 receiving router that is the DUT. An update train may be 747 caused by a variety of network conditions. For example, 748 an update train could be caused by an influx of UPDATES 749 from different peers that have been received and moved to 750 RIB-out or caused by a peer coming up and advertising its 751 routes, or by a local or remote peer flapping a link. 752 Other causes are, of course, possible. 754 The time intervals between the UPDATE packets in a train 755 may vary from essentially zero when the packets follow 756 each other as closely as possible up to a situation where 757 the time between packets exceeds MIN_ADVERT_TIME. Once 758 the packets are so widely spaced in time they can be 759 treated separately as single packet update trains since 760 the router will be guaranteed to have propagated any 761 adverts resulting from the previous UPDATE when the next 762 one arrives (a slightly sweeping statement, but if adverts 763 are arriving singly it would be a very inefficient router 764 that was unable to keep up!) 766 Measurement units: 768 Berkowitz, et al Expires: August 2002 16 769 Number of prefixes and UPDATE packets in the train, 770 time spacing between packets in train 772 Issues: 774 See Also: 776 4.10.1 Random Update Train 778 Definition: 779 An Update Train which contains: 780 - A random number of prefixes, selected according to 781 - A random distribution from the possible updates and 782 withdrawals (depending on what routes are currently 783 installed in the route under test), distributed across 784 - A random number of UPDATE packets as both updates and 785 withdraws, in 786 - A random order which does not favor any of the 787 well-known algorithms used to manage the route 788 databases in BGP process, and specified for 789 - A random distribution of time spacings between 790 deliveries taken from the interval 791 [0, MIN_ADVERT_TIME]. 793 Discussion: 794 This is intended to simulate the unpredictable 795 asynchronous nature of the network, whereby UPDATE packets 796 may have arbitrary contents and be delivered at random 797 times. A fully random update train can be considered to 798 be a worst case in some senses and should stress parts of 799 the software: It may be desirable to test a router with 800 less random cases, such as a not quite random update train 801 in which everything is random except that the UPDATES are 802 delivered as closely spaced as possible in time. 804 The distribution used to control the selection of prefixes 805 is a 'route mixture' (q.v.) 806 When a router is used in a network of routers all from the 807 same vendor, the distribution of prefixes emitted from a 808 BGP router may well be structured in a way which 809 particularly suits the internal organization of the routes 810 in the databases. It may be useful to test routers with 811 update trains organized in this way as a closer emulation 812 of the real world. One might expect that the input of a 813 vendor's router would be best suited to the ordering 814 emitted by a similar router. 816 Measurement Units: See Update Train 818 Issues: 820 See also: 822 Berkowitz, et al Expires: August 2002 17 823 4.11 Route Flap 825 Definition: 826 RIPE 210 [9] define a route flap as "the announcement and 827 withdrawal of prefixes." For our purposes we define a 828 route flap as the rapid withdrawal/announcement or 829 announcement/withdrawal of a prefix in the Adj-RIB-in. A 830 route flap is not a problem until a route is flapped 831 several times in close succession. This causes negative 832 repercussions throughout the internet. 834 Discussion: 835 Route flapping can be considered a special and 836 pathological case of update trains. A practical 837 interpretation of what may be considered excessively rapid 838 is the RIPE recommendation of "four flaps in a row". See 839 Section 6.1.5 on flap damping for further discussion. 841 Measurement units: Flapping events per unit time. 843 Issues: 844 Specific Flap events can be found in Section 5.1Route 845 Change Events. A bench-marker should use a mixture of 846 different route change events in testing. 848 See Also: Route change events, flap damping, packet train 850 5. Route Changes and Convergence 852 The following two definitions are central to the benchmarking of 853 external routing convergence, and so are singled out for more 854 extensive discussion. 856 5.1 Route Change Events 858 A taxonomy characterizing routing information changes seen in 859 operational networks is proposed in [6] as well as Labovitz et al[7]. 860 These papers describe BGP protocol-centric events, and event 861 sequences in the course of an analysis of network behavior. The 862 terminology in the two papers categorizes similar but slightly 863 different behaviors with some overlap. We would like to apply these 864 taxonomies to categorize the tests under definition where possible, 865 because these tests must tie in to phenomena that arise in actual 866 networks. We avail ourselves of, or may extend, this terminology as 867 necessary for this purpose. 869 A route can be changed implicitly by replacing it with another route 870 or explicitly by withdrawal followed by the introduction of a new 871 route. In either case the change may be an actual change, no change, 872 or a duplicate. The notation and definition of individual 873 categorizable route change events is adopted from [7] and given 874 below. 876 Berkowitz, et al Expires: August 2002 18 877 a) AADiff: Implicit withdrawal of a route and replacement by a route 878 different in some path attribute. 879 b) AADup: Implicit withdrawal of a route and replacement by route 880 that is identical in all path attributes. 881 c) WADiff: Explicit withdrawal of a route and replacement by a 882 different route. 883 d) WADup: Explicit withdrawal of a route and replacement by a route 884 that is identical in all path attributes. 886 To apply this taxonomy in the benchmarking context, we need both 887 terms to describe the sequence of events from the update train 888 perspective, as listed above, as well as event indications in the 889 time domain so as to be able to measure activity from the 890 perspective of the DUT. With this in mind, we incorporate and extend 891 the definitions of [7] to the following: 893 a) Tup (TDx): Route advertised to the DUT by Test Device x 894 b) Tdown(TDx): Route being withdrawn by Device x 895 c) Tupinit(TDx): The initial announcement of a route to a unique 896 prefix 897 d) TWF(TDx): Route fail over after an explicit withdrawal. 899 But we need to take this a step further. Each of these events can 900 involve a single route, a "short" packet train, or a "full" routing 901 table. We further extend the notation to indicate how many routes are 902 conveyed by the events above: 904 a) Tup(1,TDx) means Device x sends 1 route 905 b) Tup(S,TDx) means Device x sends a train, S, of routes 906 c) Tup(DFT,TDx) means Device x sends an approximation of a full 907 default-free table. 909 The basic criterion for selecting a "better" route is the final 910 tiebreaker defined in RFC1771, the router ID. As a consequence, this 911 memorandum uses the following descriptor events, which are routes 912 selected by the BGP selection process rather than simple updates: 914 a) Tbest -- The current best path. 915 b) Tbetter -- Advertise a path that is better than Tbest. 916 c) Tworse -- Advertise a path that is worse than Tbest. 918 5.2 Convergence 920 Definition: 921 A router is said to have converged onto a route advertised 922 to it, given that the route is the best route instance for 923 a prefix(if multiple choices exist for that prefix), when 924 this route is advertised to its downstream peers. 926 Berkowitz, et al Expires: August 2002 19 927 Discussion: 928 The convergence process can be subdivided into three 929 distinct phases: 930 - convergence across the entire Internet, 931 - convergence within an Autonomous System, 932 - convergence with respect to a single router. 934 Convergence with respect to a single router can be 935 - convergence with regard to the routing process(es), the 936 focus of this document 937 - convergence with regard to data forwarding process(es). 939 It is of key importance to benchmark the performance of 940 each phase of convergence separately before proceeding to 941 a composite characterization of routing convergence, where 942 implementation- specific dependencies are allowed to 943 interact. 945 The preferred route instance must be unambiguous during 946 test setup/definition. 948 Measurement Units: N.A. 950 Issues: 952 See Also: 954 6. BGP Operation Events 956 The BGP speaker process(es) in a router restart completely, for 957 example, because of operator intervention or a power failure, or a 958 partially because a TCP session has terminated for a particular link. 959 Until recently the BGP process would have to readvertise all relevant 960 routes on reestablished links potentially triggering updates across 961 the network. Recent work is focused on limiting the volume of 962 updates generated by short term outages by providing a graceful 963 restart mechanism [17]. 965 6.1 Hard reset 967 Definition: 968 An event which triggers a complete reinitialization of the 969 routing tables on one or more BGP sessions, resulting in 970 exchange of a large number of UPDATEs on one or more links 971 to the router. 973 Discussion: 975 Measurement Units: N/A 977 Issues: 979 See Also: 981 Berkowitz, et al Expires: August 2002 20 982 6.2 Soft reset 984 Definition: 985 An event which results in a complete or partial restart of 986 the BGP session(s) on a router, but which avoids the 987 exchange of a large number of UPDATEs by maintaining state 988 across the restart. 990 Discussion: 992 Measurement Units: N/A 994 Issues: 996 See Also: 998 7. Factors that impact the performance of the convergence process 1000 While this is not a complete list, all of the items discussed below 1001 have a significant affect on BGP convergence. Not all of them can be 1002 addressed in the baseline measurements described in this document. 1004 7.1 General factors affecting BGP convergence 1006 These factors are conditions of testing external to the router Device 1007 Under Test (DUT). 1009 7.1.1 Number of peers 1011 As the number of peers increases, the BGP route selection algorithm 1012 is increasingly exercised. In addition, the phasing and frequency of 1013 updates from the various peers will have an increasingly marked 1014 effect on the convergence process on a router as the number of peers 1015 grows. 1017 7.1.2 Number of routes per peer 1019 The number of routes per BGP peer is an obvious stressor to the 1020 convergence process. The number, and relative proportion, of multiple 1021 route instances and distinct routes being added or withdrawn by each 1022 peer will affect the convergence process, as will the mix of 1023 overlapping route instances, and IGP routes. 1025 7.1.3 Policy processing/reconfiguration 1027 The number of routes and attributes being filtered, and set, as a 1028 fraction of the target route table size is another parameter that 1029 will affect BGP convergence. 1031 Extreme examples are 1032 - Minimal Policy: receive all, send all, 1033 - Extensive policy: up to 100% of the total routes have applicable 1034 policy. 1036 Berkowitz, et al Expires: August 2002 21 1037 7.1.4 Interactions with other protocols. 1039 There are interactions in the form of precedence, synchronization, 1040 duplication and the addition of timers, and route selection criteria. 1041 Ultimately, understanding BGP4 convergence must include understanding 1042 of the interactions with both the IGPs and the protocols associated 1043 with the physical media, such as Ethernet, SONET, DWDM. 1045 7.1.5 Flap Damping 1047 A router can use flap damping to respond to route flapping. Use of 1048 flap damping is not mandatory, so the decision to enable the feature, 1049 and to change parameters associated with it, can be considered a 1050 matter of routing policy. 1052 The timers are defined by RFC 2439 [4] and discussed in RIPE-210 [9]. 1053 If this feature is in effect, it requires that the router keep 1054 additional state to carry out the damping, which can have a direct 1055 impact on the control plane due to increased processing. In 1056 addition, flap damping may delay the arrival of real changes in a 1057 route, and affect convergence times 1059 7.1.6 Churn 1061 In theory, a BGP router could receive a set of updates that 1062 completely defined the Internet, and could remain in a steady state, 1063 only sending appropriate KeepAlives. In practice, the Internet will 1064 always be changing. 1066 Churn refers to control plane processor activity caused by 1067 announcements received and sent by the router. It does not include 1068 KeepAlives. 1070 Churn is caused by both normal and pathological events. For example, 1071 if an interface of the local router goes down and the associated 1072 prefix is withdrawn, that withdrawal is a normal activity, although 1073 it contributes to churn. If the local router receives a withdrawal 1074 of a route it already advertises, or an announcement of a route it 1075 did not previously know, and readvertises this information, again 1076 these are normal constituents of churn. Routine updates can range 1077 from single announcement or withdrawals, to announcements of an 1078 entire default-free table. The latter is completely reasonable as an 1079 initialization condition. 1081 Flapping routes are a pathological contributor to churn, as is MED 1082 oscillation [11]. The goal of flap damping is to reduce the 1083 contribution of flapping to churn. 1085 The effect of churn on overall convergence depends on the processing 1086 power available to the control plane, and whether the same 1087 processor(s) are used for forwarding and for control. 1089 7.2 Implementation-specific and other factors affecting BGP convergence 1091 Berkowitz, et al Expires: August 2002 22 1092 These factors are conditions of testing internal to the router Device 1093 Under Test (DUT), although they may affect its interactions with test 1094 devices. 1096 7.2.1 Forwarded traffic 1098 The presence of actual traffic in the router may stress the control 1099 path in some fashion if both the offered load due to data and the 1100 control traffic (FIB updates and downloads as a consequence of 1101 flaps)are excessive. The addition of data traffic presents a more 1102 accurate reflection of realistic operating scenarios than if only 1103 control traffic is present. 1105 7.2.2 Timers 1107 Settings of delay and hold-down timers at the link level as well as 1108 for BGP4, can introduce or ameliorate delays. As part of a test 1109 report, all relevant timers should be reported if they use non- 1110 default value. Also, any variation in standard behavior, such as 1111 overriding TCP slow start, should be documented. 1113 7.2.3 TCP parameters underlying BGP transport 1115 Since all BGP traffic and interactions occur over TCP, all relevant 1116 parameters characterizing the TCP sessions should be provided: eg Max 1117 window size, Maximum segment size, timers. 1119 7.2.4 Authentication 1121 Authentication in BGP is currently done using the TCP MD5 Signature 1122 Option [10]. The processing of the MD5 hash, particularly in routers 1123 with a large number of BGP peers and a large amount of update traffic 1124 can have an impact on the control plane of the router. 1126 8. Security Considerations 1128 The document explicitly considers authentication as a performance- 1129 affecting feature, but does not consider the overall security of the 1130 routing system. 1132 Berkowitz, et al Expires: August 2002 23 1133 9. References 1135 [1] Bradner, S., "The Internet Standards Process -- 1136 Revision 3", BCP 9, RFC 2026, October 1996 1138 [2] Bradner, S., "Key words for use in RFCs to 1139 Indicate Requirement Levels", BCP 14, RFC 2119, 1140 March 1997 1142 [3] Rekhter, Y. and Li, T., "A Border Gateway 1143 Protocol 4 (BGP-4)", RFC 1771, . March 1995. 1145 [4] Villamizar, C., Chandra, R. and Govindan, R., 1146 "BGP Route Flap Damping", RFC 2439, 1147 November 1998." 1149 [5] Baker, F.,"Requirements for IP Version 4 1150 Routers", RFC 1812. June 1995. 1152 [6] Ahuja, A., Jahanian, F., Bose, A. and Labovitz, 1153 C., 1154 "An Experimental Study of Delayed Internet 1155 Routing Convergence", RIPE 37 - Routing WG. 1157 [7] Labovitz, C., Malan, G.R. and Jahanian, F., 1158 "Origins of Internet Routing Instability," 1159 Infocom 99, 1161 [8] Alaettinoglu, C., Villamizar, C., Gerich, E., 1162 Kessens, D., Meyer, D., Bates, T., Karrenberg, 1163 D. and Terpstra, M., "Routing Policy 1164 Specification Language (RPSL)", RFC 2622, June 1165 1999. 1167 [9] Barber, T., Doran, S., Karrenberg, D., Panigl, 1168 C., Schmitz, J., "RIPE Routing-WG Recommendation 1169 for coordinated route-flap damping parameters", 1170 RIPE 210, 1172 [10] Heffernan, A., "Protection of BGP Sessions via 1173 the TCP MD5 Signature Option", RFC 2385, August 1174 1998. 1176 [11] McPhersonm, Gill, Walton, Retana, "BGP 1177 Persistent Route Oscillation Condition", , Work In 1179 progress 1181 [12] Bates, T., "The CIDR Report", 1182 http://www.employees.org/~tbates/cidr-report.html 1183 Internet statistics relevant to inter-domain 1184 routing updated daily 1186 Berkowitz, et al Expires: August 2002 24 1188 [13] Smith, P. (designer), APNIC Routing Table 1189 Statistics, http://www.apnic.net/stats/bgp/, 1190 Statistics derived from a daily analysis of a 1191 core router in Japan 1193 [14] Huston, G., Telstra BGP table statistics, 1194 http://www.telstra.net/ops/bgp/index.html, 1195 Statistics derived daily from the BGP tables of 1196 Telstra and other AS's routers 1198 [15] Juniper Networks,"Junos(tm) Internet Software 1199 Configuration Guide Routing and Routing 1200 Protocols, Release 4.2" 1201 http://www.juniper.net/techpubs/software/junos42/ 1202 swconfig-routing42/html/glossary.html#1013039. 1203 September 2000 (and other releases). 1205 [16] Rosen, E. and Rekhter, Y., "BGP/MPLS VPNs", RFC 1206 2547, March 1999 1208 [17] Ramachandra, S., Rekhter, Y., Fernando, R., 1209 Scudder, J.G. and Chen, E., 1210 "Graceful Restart Mechanism for BGP", 1211 draft-ietf-idr-restart-02.txt, January 2002, work 1212 in progress. 1214 10.Acknowledgments 1216 Thanks to Francis Ovenden and Elwyn Davies for review and Abha Ahuja 1217 for encouragement. Much appreciation to Jeff Haas, Matt Richardson, 1218 and Shane Wright at Nexthop for comments and input. Debby Stopp and 1219 Nick Ambrose contributed the concept of route packing. 1221 11.Author's Addresses 1223 Howard Berkowitz 1224 Gett Communications 1225 5012 S. 25th St 1226 Arlington VA 22206 1227 Phone: +1 703 998-5819 1228 Fax: +1 703 998-5058 1229 EMail: hcb@gettcomm.com 1231 Elwyn Davies 1232 Nortel Networks 1233 London Road 1234 Harlow, Essex CM17 9NA 1235 UK 1236 Phone: +44-1279-405498 1237 Email: elwynd@nortelnetworks.com 1239 Susan Hares 1240 Nexthop Technologies 1241 517 W. William 1243 Berkowitz, et al Expires: August 2002 25 1244 Ann Arbor, Mi 48103 1245 Phone: 1246 Email: skh@nexthop.com 1248 Padma Krishnaswamy 1249 Email: kri1@earthlink.net 1251 Marianne Lepp 1252 Juniper Networks 1253 51 Sawyer Road 1254 Waltham, MA 02453 1255 Phone: 617 645 9019 1256 Email: mlepp@juniper.net 1258 Alvaro Retana 1259 Cisco Systems, Inc. 1260 7025 Kit Creek Rd. 1261 Research Triangle Park, NC 27709 1262 Email: aretana@cisco.com 1264 Full Copyright Statement 1266 Copyright (C) The Internet Society (2002). All Rights Reserved. 1268 This document and translations of it may be copied and furnished to 1269 others, and derivative works that comment on or otherwise explain it 1270 or assist in its implmentation may be prepared, copied, published and 1271 distributed, in whole or in part, without restriction of any kind, 1272 provided that the above copyright notice and this paragraph are 1273 included on all such copies and derivative works. However, this 1274 document itself may not be modified in any way, such as by removing 1275 the copyright notice or references to the Internet Society or other 1276 Internet organizations, except as needed for the purpose of 1277 developing Internet standards in which case the procedures for 1278 copyrights defined in the Internet Standards process must be 1279 followed, or as required to translate it into languages other than 1280 English. 1282 The limited permissions granted above are perpetual and will not be 1283 revoked by the Internet Society or its successors or assigns. 1285 This document and the information contained herein is provided on an 1286 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 1287 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDIN BUT 1288 NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN 1289 WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF 1290 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1292 Berkowitz, et al Expires: August 2002 26