Network Working Group H.Berkowitz Internet Draft A.Retana Expires August 2001 S.Hares P.Krishnaswamy draft-berkowitz-bgpcon-01.txt March 2000 Benchmarking Methodology for Exterior Routing Convergence Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026 [1]. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or made obsolete by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract This is an update of an individual contribution that has been accepted as a work item by the Benchmarking Methodology Working Group, and will split into two BMWG documents. It is being posted for information. T This document defines a specific set of tests that router implementers can use to measure and report the convergence performance of BGP-4 processes. It doe not consider the forwarding performance of such routers once they have converged, or the convergence characteristics of the global routing system. Conventions used in this document The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC-2119 [2]. Table of Contents 1. Introduction.....................................................2 1.1 Overview and Roadmap...........................................3 1.2 Definition Format..............................................3 2. Definitions of convergence-related router and network states or components............................................................4 2.1 BGP Peer.......................................................4 2.2 The routing information Base (RIB) and its constituents Adj-Rib- In, Adj-Rib-Out, Loc-RIB............................................4 2.3 The Forwarding Information Base or FIB.........................5 2.4 Default Free routing tables....................................6 Berkowitz et al Expires January 2001 1 Benchmarking Methodology for Exterior Routing Convergence 2.5 Prefix.........................................................6 2.6 Route..........................................................6 2.7 BGP Route......................................................7 2.8 Default Route..................................................7 2.9 Route Instance.................................................7 2.10 Unique Route.................................................8 2.11 Route Views..................................................8 2.12 Policy.......................................................8 2.13 Policy Information Base......................................9 2.14 Route Flap...................................................9 2.15 Convergence.................................................11 3. Factors that impact the performance of the convergence process..11 3.1 Number of peers...............................................11 3.2 Number of routes per peer.....................................11 3.3 Policy processing/reconfiguration.............................11 3.4 Forwarded traffic............................................11 3.5 Flap dampening................................................12 3.6 Authentication................................................12 3.7 MBGP Processing...............................................12 4. Test Configuration..............................................12 5. Test setup and methodology......................................13 5.1.1. Stages of convergence and events triggering reconvergence 13 6. Tests measuring Full Initial convergence with a single peer.....14 7. Incremental Reconvergence.......................................15 7.1 Route Announcements...........................................15 7.1.1. Explicit announce of single new route (Tupinit)[3,4]....15 7.1.2. Implicit withdraw of single route and replace by new announced route (AAdiff)..........................................15 7.1.3. Duplicate announcments (AAdup)...........................16 7.2 Route withdrawal..............................................16 7.2.1. Explicit withdraw of single route (Tdown)................16 7.2.2. Explicit Withdrawal followed by an reannounce (WAdup)....16 7.2.3. Failover to existing Alternate Path after Explicit Withdrawal (no announce WF).......................................17 7.2.4. Explicit withdraw of an existing route followed by announce of a different route (WAdiff).....................................17 7.3 Repetitive route updates (flaps)..............................17 8. Multiple Peers..................................................18 8.1 Initial Convergence...........................................18 9. References......................................................18 10. Acknowledgments................................................19 1. Introduction This document describes a specific set of tests aimed at characterizing the convergence performance of BGP-4 processes in routers or other boxes that incorporate BGP functionality. A key objective is to propose methodology that will facilitate the conducting and reporting of convergence-related measurements in a standard fashion. Although both convergence and forwarding are essential to basic router operation, this document does not consider the forwarding performance,if applicable, in the Device Under Test (DUT),for two reasons. Forwarding performance is the primary focus in [1] and it is expected that it will be dealt with in work that Berkowitz et al Expires January 2001 2 Benchmarking Methodology for Exterior Routing Convergence ensues from [1]; further, as convergence characterization is a complex process, we would deliberately like to restrict the initial focus in this document to specifying how to take basic measurements towards this objective. Subsequent drafts will explore the more intricate aspects of convergence measurement, e.g. in the presence of policy processing and other realistic performance modifiers such as simultaneous traffic on the control and data paths within the DUT. Convergence in Interior Gateway Protocols will also be dealt with in separate drafts. 1.1 Overview and Roadmap In general, measurements of routing protocol convergence can be classified either as æinternalÆ, with time-stamped tables indicating the time of completion of convergence (such as those described in [4], or æexternalÆ. In an external measurement, a process in the Device Under Test (DUT) is inferred to have converged after a downstream measurement device indicates the corresponding advertisement has been received by it. An alternative type of external measurement is to test for data forwarded to the downstream device that relies upon the route that the Device Under Test just converged upon. The external technique is more readily applicable than the internal technique at present since the requisite NTP timestamp hooks may not yet be in products. However, the external technique is less accurate as it also includes the time to advertise the new route downstream and transmission times for the advertisement. If data forwarding were to feature in the measurement methodology it too would include some extraneous latency- that of the forwarding lookup process in the DUT at the minimum. This document deals only with external measurements limited to route propagation. A characterization of the BGP convergence performance of a device must take into account, if not also time, all distinct stages and aspects of BGP functionality. This requires that the relevant terms and metrics be as specific as possible. Consequently the first step taken here towards detailing measurements of convergence performance will be to define all the relevant terms and concepts. The necessary definitions are classified into two separate categories: . Descriptions of the constituent elements of a network or a router that is undergoing convergence . Descriptions of factors that impact convergence processes which will influence measurements on convergence. 1.2 Definition Format The definition format is the equivalent to that defined in [12], and is repeated here for convenience: Berkowitz et al Expires January 2001 3 Benchmarking Methodology for Exterior Routing Convergence X.x Term to be defined. (e.g., Latency) Definition: The specific definition for the term. Discussion: A brief discussion about the term, its application and any restrictions on measurement procedures. Measurement units: The units used to report measurements of this term, if applicable. Issues: List of issues or conditions that affect this term. See Also: List of other terms that are relevant to the discussion of this term. 2. Definitions of convergence-related router and network states or components Many terms included in this list of definitions were described originally in previous standards or papers. They are included here because of their pertinence to this discussion. Where relevant, reference is made to these sources. An effort has been made to keep this list complete with regard to the necessary concepts without overdefinition. 2.1 BGP Peer Definition: A BGP peer is another BGP process to which the DUT has established a TCP connection over which a BGP session is active. Peers send BGP advertisements to the DUT and receive DUT-originated advertisements. Discussion: This is a protocol-specific definition, not to be confused with another frequent usage, which refers to the business/economic definition for the exchange of routes without financial compensation. Measurement units: Issues: See Also: 2.2 The routing information Base (RIB) and its constituents Adj-Rib-In, Adj-Rib-Out, Loc-RIB Berkowitz et al Expires January 2001 4 Benchmarking Methodology for Exterior Routing Convergence Definition: These terms were defined in [10]. The RIB contains all destination prefixes to which the router may forward, and one or more currently reachable next hop addresses for them. Routes included in this table potentially have been selected from several sources of information, including hardware status, interior routing protocols, and exterior routing protocols. RFC 1812 [12] contains a basic set of route selection criteria relevant in an all-source context. Many implementations impose additional criteria. A common implementation-specific criterion is the preference given to different routing information sources. The Forwarding Information Base (see next item) is generated from the RIB.The Loc-RIB contains the set of best routes selected from the various Adj-RIBs,after applying local policies and the BGP route selection algorithm.Adj-RIB-In and Adj-RIB-Out are "views" of routing information from the perspective of individual peer routers. The Adj-RIB-In contains information advertised to the DUT by a specific peer. The Adj-RIB-Out contains the information the DUT will advertise to the peer. Discussion: The separation implied between the various RIBs is logical. It does not necessarily follow that these RIBs are distinct and separate entities in any given implementation. Measurement Units: Number of route instances Issues: Specifying the RIB is important because the types and relative proportions of routes in it can affect the convergence efficiency. Types of routes can include internal BGP, external BGP, interface and IGP routes. See Also: Route, BGP Route, Route Instance 2.3 The Forwarding Information Base or FIB Definition: The FIB is referred to in [10] as well as [12] but not defined in either. For the purposes of this document, the FIB is the last lookup on the router data path, based on which a next hop is selected for forwarding each packet. Discussion: Most current implementations have full, non-cached FIBs per router interface. All the route computation and convergence occurs before a route is downloaded into a FIB. Measurement Units: N.A. Issues: Berkowitz et al Expires January 2001 5 Benchmarking Methodology for Exterior Routing Convergence See Also: Route 2.4 Default Free routing tables Definition: The size of routing tables in the default free zone of the Internet. Discussion: The term originates from the concept that routers at the core or top tier of the Internet will not be configured with a default route (Notation 0.0.0.0/0). Thus they will forward every prefix to a specific nexthop based upon the longest match. Default free routing table size is commonly used as an indicator of the magnitude of reachable Internet address space. However,default free routing tables may also include routes internal to the infrastructural net that a router is part of. Measurement Units: number of routes Issues: See Also: Routes,Route Instances, Default Route 2.5 Prefix Definition: A destination address in CIDR format. Expressed as prefix/length. The definition in [12] is "A network prefix is..a contiguous set of bits at the more significant end of the address that defines a set of systems;host numbers select among those systems." Discussion: A prefix is expressed as a portion of an IP address followed by the associated mask such as 10/8. Measurement Units: N.A. Issues: See Also: 2.6 Route Definition: In general, a ærouteÆ is the tuple . If MPLS is supported the tuple may include Discussion: This term refers to the concept of a route common to all routing protocols. Measurement Units: N.A. Issues: None. Berkowitz et al Expires January 2001 6 Benchmarking Methodology for Exterior Routing Convergence See Also: BGP route 2.7 BGP Route Definition: The tuple [10] Discussion: Attributes are mentioned in [10], and are by inference, qualifying data that accompanies a prefix in a BGP route." For purposes of this protocol a route is defined as a unit of information that pairs a destination with the attributes of a path to that destination... A variable length sequence of path attributes is present in every UPDATE. Each path attribute is a triple of variable length." Nexthop is one type of attribute. Measurement Units:N.A. Issues: See Also: Route, prefix. 2.8 Default Route A Default Route is a route entry that can match any prefix. If a router does not have a route for a particular packet's destination address, it forwards this packet to the next hop in the default route entry if its FIB contains one. The notation for a default route is 0.0.0.0/0 Discussion: Core routers do not contain default routes. Access and edge routers are likely to have default route entries. Measurement units: N.A. Issues: See Also: default free routing table, route, route instance 2.9 Route Instance This term is used in the context of a BGP Adj RIB In. Definition: Single occurrence of route sent by BGP Peer for a particular prefix. When a router has multiple peers from which it accepts routes, routes to the same prefix may recur in the various Adj-Ribs-In. This is then a case of multiple route instances. Discussion Berkowitz et al Expires January 2001 7 Benchmarking Methodology for Exterior Routing Convergence Route instances may not be selected by the BGP selection algorithm due to local policy. Measurement Units:number of instances Issues: the number of route instances in the Adj-Rib-in bases will vary based on the function to be performed by a router. A core router will likely receive more route instances than an access router. A core router is situated in the default-free zone. See Also: 2.10 Unique Route Definition: A unique route is a prefix for which there is just one route instance. Discussion: Measurement Units:N.A. Issues: See Also: route, route instance 2.11 Route Views Definition: Route views must be further specified as incoming or outgoing. An incoming route view is AFI/SAFI and peer specific and is the Adj- Rib-In for that peer and AFI/SAFI. An outgoing route view is also peer and AFi/SAFI specific and is the Adj-Rib-Out for that peer, for a given AFI/SAFI combination. Discussion: Measurement Units: N.A. Issues: See Also: 2.12 Policy Definition: Policy is "the ability to define conditions for accepting, rejecting, and modifying routes received in advertisements"[16] Policy processing is the set of actions performed by the BGP route selection algorithm that influences route selection in the presence of attributes in the route updates received from peers, or policy actions configured to influence outbound BGP route advertisements. Discussion:RFC 1771 [10] further defines policy constraints in the hop-by-hop routing paradigm. Berkowitz et al Expires January 2001 8 Benchmarking Methodology for Exterior Routing Convergence Measurement Units: Issues: Policy is implemented using filters . See Also: Policy Information Base. 2.13 Policy Information Base Definition: A policy information base is the set of incoming and outgoing policies. All references to the phase of the BGP selection process here are made with respect to RFC 1771 [10] definition of these phases. Incoming policies are applied in Phase 1 of the BGP selection process [10]to the Adj-Rib-In routes to set the metric for the Phase 2 decision process. Outgoing Policies are applied in Phase 3 of the BGP process to the Adj-Rib-Out routes to allow route (prefix and path attribute tuple) to be announced out to a specific peer. Discussion: Policies in the Policy information base often instantiated as "route maps" and filter/access lists. The "route maps" often operate on or use the "path attribute" portion of the BGP route. On incoming policy, these "route maps" may set a metric to be compared in Phase 2 of the BGP process.[10] On the outgoing policy, the "route maps" may also set outgoing path attributes to the route sent to the peer. The filter lists/access lists track the route prefixes. The amount of policy processing (both in terms of route maps and filter/access lists) will impact the convergence time of the BGP algorithm. The amount of policy processing may vary from a simple policy which accepts all routes and sends all routes to complex policy with a substantial fraction of the prefixes being filtered by filter/access lists. For this first round of tests for BGP convergence, we recommend that the tests be run under the simple policy of "accept all routes and and send all routes." 2.14 Route Flap Definition: RFC 2439 [13]refers to route flapping as "An excessive rate of update to the advertised reachability of a subset of Internet prefixes.." Berkowitz et al Expires January 2001 9 Benchmarking Methodology for Exterior Routing Convergence We would like to refine this description for the purpose of benchmark specification to be: "Repeated excessive updates to route instances in the Adj- Rib-In on the DUT." Discussion: These repeated updates can be either a) Implicit replaces of routes [10] categorized in [4] as: either AADiff or AAdup. b) Explicit replaces of routes [10] categorized by [4] as either: WADiff, WAdup, c)Erroneous Duplicate Withdrawals for the same route as categorized in [4] as WWDup. The threshold that can be declared excessive by RFC 2439 [13] is configured by each network on the basis of: "cutoff threshold (cut) This value is expressed as a number of route withdrawals. It is the value above which a route advertisement will be suppressed. reuse threshold (reuse) This value is expressed as a number of route withdrawals. It is the value below which a suppressed route will now be used again. " Measurement units Flapping events per unit time. Specific Flap events are: 1) AADiff 2) AADup 3) WADiff 4) WADup 5) WWDup The Flapping event sequence can be characterized as mixture of these events with a percentage per type. An example of this would be: 20% AADiff, 40% AAdup, 30% WADiff 10% WWdup at 100 flap events per second. Berkowitz et al Expires January 2001 10 Benchmarking Methodology for Exterior Routing Convergence 2.15 Convergence Definition: A router is said to have converged onto a route advertised to it, given that route is the best route instance for a prefix, (if multiple choices exist for that prefix) when this route is advertised to its downstream peers. Discussion: The best route instance should be set so as to be unambiguous during test setup/definition. This document does not consider forwarding-dependent illustrations of convergence. Measurement Units: N.A. Issues: See Also: 3. Factors that impact the performance of the convergence process Some of these factors will not be incorporated into the tests in this document. This is because, as mentioned earlier, specifying characterization methodology will be undertaken in stages according to complexity starting with the more baseline tests. 3.1 Number of peers As the number of peers increases, the BGP route selection algorithm is increasingly exercised. The phasing and frequency of updates from the various peers will have a marked effect on the convergence process on a router. 3.2 Number of routes per peer The number of routes per BGP peer is an obvious stressor to the convergence process. The number, and relative proportion, of multiple route instances and distinct routes being added or withdrawn by each peer will affect the convergence process. So will the mix of overlapping route instances, and IGP routes. 3.3 Policy processing/reconfiguration The number of routes and attributes being filtered for, and set,as a fraction of the target route table size is another parameter that will affect BGP convergence. The two extremes are: Minimal Policy Extensive policy--. For example, upto 80 % of the total routes must have applicable policy. 3.4 Forwarded traffic The presence of actual traffic in the router may stress the control path in some fashion if both the offered load due to data and the Berkowitz et al Expires January 2001 11 Benchmarking Methodology for Exterior Routing Convergence control traffic (FIB updates and downloads as a consequence of flaps)are excessive. This is implementation dependent. This condition is a more accurate reflection of realistic operating scenarios than if no data traffic is present. 3.5 Flap dampening Flap Damping occurs in response to frequent alterations in the route instances input to the DUT. If this is in effect, it requires that the router keep additional state to carry out the damping, which has a direct impact on the control plane due to increased processing. 3.6 Authentication Authentication in BGP is currently done using the TCP MD5 Signature Option [14]. The processing of the MD5 hash, specially in routers with a large number of BGP peers and a large ammount of update traffic may have an impact on the control plane of the router. 3.7 MBGP Processing Multiprotocol extension for BGP are defined in [15], giving BGP the ability to carry routing information for multiple address families (not only IPv4 unicast). Processing of different protocol information encoded using these multiprotocol extensions may have an impact on the convergence of any one protocol. The tests presented in this document may be applicable to any specific address family. 4. Test Configuration Figure 1 illustrates the single peer test case: TR1==========+---------+==========TR3 | | | D | | | | DUT | TR2==========| | +---------+ D is a prefix reachable by both TR1 and TR2. It is assumed that neither TR1 or TR2 is the AS of origin for the announcement of D. For all test routers and the DUT, all routes fed in as part of this test process are EBGP routes. More complex peering arrangements will involve up to n Test Routers, as shown in Figure 2. It is recommended that the Figure 1 configuration always be tested as a baseline, and then additional reports made that show the effect on performance of increasing the number of peers. All tests defined in this document use the topology shown unless explicitly noted. TR1==========+---------+==========TR3 | | | D | | | | DUT | Berkowitz et al Expires January 2001 12 Benchmarking Methodology for Exterior Routing Convergence TR2==========| | | | ... TRn==========+---------+ Interface speeds must be specified as part of the test report. At least a 100 Mbps speed link and a full duplex MAC layer between all connected devices are recommended. In the absence of other route selection criteria, TR1 shall have an IP address that makes it most preferred. 5. Test setup and methodology 'Test routers' will be providing the test traffic to the Device Under Test and collecting the evidence of convergence from it, if any. The only traffic in the cases described here is route updates/withdrawals. The requisite TCP sessions will have to be established between all test routers and the DUT. Any other equipment required to trace the flow of BGP messages between the devices actually participating in the test will need to be transparent to these sessions. It is also desirable that the 'Test routers' be able to generate protocol message sequences at settable rates. 5.1.1. Stages of convergence and events triggering reconvergence 5.1.1.1 Full Initialization The DUT establishes a TCP connection, then a BGP session, with a peer, and accepts routes from it. Full initialization of this sort is expected to be relatively infrequent compared with incremental convergence. 5.1.1.2 Incremental Convergence There are several distinct operations which could be categorized as incremental convergence. A taxonomy characterising routing information changes seen in operational networks is described in [3] as well as [4]. These papers describe BGP protocol-centric events, or event sequences in the course of an analysis of network behavior. The terminology in the two papers addresses similar but slightly different events. The former refers to Tup,T ,T , and Tlong indicating the down short , occurrence of a route first coming up, being withdrawn,and routes with shorter or longer ASPATHs respectively. The first two denote explicit events. The last two refer to implicit re-announces of a shorter or longer route. In [4],the notation used was WADiff (explicit), WADup, AADiff,which is implicit and AADup, also implicit. With regard to the benchmarking methodology under discussion, we would like to apply the foregoing taxonomies to categorise the tests Berkowitz et al Expires January 2001 13 Benchmarking Methodology for Exterior Routing Convergence under definition where possible, because these tests must tie in to phenomena that arise in actual networks. We avail of, or extend, this terminology as necessary for this purpose. In this document, the meaning of Tup and Tdown are preserved and extended from [3]. The notation Tup(TRx) stands for a Tup event advertised to the router being tested (i.e., DUT). We also introduce Tupinit to indicate the initial announcement of a route to a unique prefix. {is this used?}The sense of the Tshort and Tlong events is also preserved, but the basic criterion for selecting a "better" route is the final tiebreaker defined in RFC1771, the router ID. As a consequence, this memorandum uses the events Tbetter, Tworse, and Tbest. They are defined as: Tbest -- The current best path. Tbetter -- Advertise a path that is better than Tbest. T -- Advertise a path that is worst than Tbest. worst Categories of incremental convergence: These tests list basic operations that occur on a single router in response to route updates / withdrawals typical of network instabilities. Only the fundamental operations are selected because they form the basis of all more intricate responses. Longer sequences of protocol updates require a compounding of the responses listed here. In addition the arrival rate as well as pattern of route updates/withdrawals is an important factor in the stress testing of a router's convergence. --Add single route (Tupinit) --Delete single route (Tdown) --Add/deletes of multiple routes in increments until the full table is advertised or withdrawn at once . This could include repetitions of the basic operations of Tupinit , WAdiff,WAdup,AAdup,AAdiff --Delete Peer/Readd This causes a full convergence type of operation. The test router terminates the TCP connection and BGP session with the peer, then reestablishes the BGP session. When the session is reestablished, routing information must be exchanged again. --Delete multiple peers and readd. When multiple peers are sending or receiving routes from the DUT, the percentage of route instances, unique routes, and the total number of routes from or to each peer. --Failover to an existing less preferred route on withdrawal of preferred route (Wf) 6. Tests measuring Full Initial convergence with a single peer Procedure: Initialize the test scenario by establishing an eBGP session between the DUT and TR3. No routing information is exchanged. Initialize TR1 with a predetermined number of prefixes. Suggested fractions are Berkowitz et al Expires January 2001 14 Benchmarking Methodology for Exterior Routing Convergence 10%,20%,50% and 100% of the full routing table. The physical link between TR1 and the DUT should also be active at this time. Establish an eBGP session between TR1 and the DUT; all the prefixes in TR1 should be advertised at this time to the DUT. The convergence time measurement should start when the first OPEN message is exchanged between TR1 and the DUT. The end of the convergence period is marked when TR3 receives the last UPDATE from the DUT. It is expected that the DUT will install the routes in its FIB. However, this test will neither check for, nor verify this. 7. Incremental Reconvergence This set of tests measures the convergence after the initial full BGP table has been transmitted to and processed by the DUT.The test procedures are based on the cases described in section 4. 7.1 Route Announcements 7.1.1. Explicit announce of single new route (Tupinit)[3,4] This test measures the time required to add a route newly advertised by a peer (Tup(TRx)). Such a route does not exist in the DUT's RIB, and will not displace a route in the RIB. Procedure : Initialize the test scenario by establishing an eBGP session between the DUT and TR1 and between the DUT and TR3. TR1 should advertise a predetermined number of routes to the DUT, which in turn should advertise it to TR3. -Advertise a route originated in TR1; Tup(TR1,D). --The reconvergence time measurement should start when TR1 sends the UPDATE containing the route D. The end of the reconvergence period is marked when TR3 has received the UPDATE containing D. 7.1.2. Implicit withdraw of single route and replace by new announced route (AAdiff) This test measures the time required to replace an existing route with one that is preferred (Tbetter(TRx)). Such a route exists in the DUT's RIB, and will be replaced by the new advertisement. Procedure : Initialize the test scenario by establishing an eBGP session between the DUT and TR1 and between the DUT and TR3. TR1 should advertise a predetermined number of routes to the DUT, which in turn should Berkowitz et al Expires January 2001 15 Benchmarking Methodology for Exterior Routing Convergence advertise it to TR3. The set of routes advertised by TR1 should contain the test route D. -Advertise a replacement route for D from TR1; Tbetter(TR1,D). This route should have LOCAL_PREF value that is preferred over the original advertisement for D. --The reconvergence time measurement should start when TR1 sends the UPDATE containing the replacement route. The end of the reconvergence period is marked when TR3 has received the new UPDATE containing the replacement. Variations to this test may consist in selecting other attributes to replace in a consecutive update.The attribute used should be indicated in the results and no filters should be used. 7.1.3. Duplicate announcments (AAdup) From [4], this type of event occurs and may be caused by policy changes or flaps within the "MinRouteAdvertisementInterval" of 30 seconds. 7.2 Route withdrawal 7.2.1. Explicit withdraw of single route (Tdown) This test measures the time required to withdraw a route advertised by a peer (Tdown(TRx)). Such a route exists in the DUT's RIB, and will be removed. Procedure Initialize the test scenario by establishing an eBGP session between the DUT and TR1 and between the DUT and TR3. TR1 should advertise a predetermined number of routes to the DUT, which in turn should advertise them to TR3. Withdraw a route previously originated in TR1; Tdown(TR1,D). The reconvergence time measurement should start then TR1 sends the withdraw message containing the route D. The end of the reconvergence period is marked when TR3 has received the corresponding withdraw message. 7.2.2. Explicit Withdrawal followed by an reannounce (WAdup) This test combines 6.2 and 6.3.1.and measures the time required to withdraw ((Tdown(TRx)) and reinstall (Tup(TRx)) a route advertised by a peer. Such a route initially exists in the DUT's RIB, it will be removed and then reinstalled. Procedure: Berkowitz et al Expires January 2001 16 Benchmarking Methodology for Exterior Routing Convergence Initialize the test scenario by establishing an eBGP session between the DUT and TR1 and between the DUT and TR3. TR1 should advertise a predetermined number of routes to the DUT, which in turn should advertise them to TR3. Withdraw a route previously advertised by TR1; Tdown(TR1). After a predetermined ammount of time, TR1 readvertises the same withdrawn route (Tup(TR1)) to the DUT. The reconvergence time measurement should start then TR1 sends the withdraw message containing the route D. The end of the reconvergence period is marked when TR3 has received the UPDATE containing D. 7.2.3. Failover to existing Alternate Path after Explicit Withdrawal (no announce WF) This test measures the time to replace a path with an existing alternate after an explicit withdraw (Tdown(TRx)) of the current best path (Tbest). Procedure: Initialize TR1 and TR2 with a predetermined number of routes. These routes should be for the same prefixes. Initialize the test scenario by establishing an eBGP session between the DUT and TR1, TR2 and TR3. TR1 and TR2 should advertise their routes and the DUT should advertise the best path to TR3. The routes advertised by TR1 and TR2 should be such that the DUT selects the path through TR1 as the best. The decision should be made by comparing the LOCAL_PREF between the two available paths. At this point the DUT should have a path from both TR1 and TR2 for every prefix. TR1 sends a withdraw for a specific route (D); Tdown (TR1,D). The reconvergence time measurement should start when TR1 sends the withdraw message for D. The end of the reconvergence period is marked when TR3 receives the new UPDATE containing the path through TR2. This test may also be executed by increasing the number of routes withdrawn by TR1 or by increasing the number of alternate paths available(increase the test routers up to TRn). 7.2.4. Explicit withdraw of an existing route followed by announce of a different route (WAdiff) 7.3 Repetitive route updates (flaps) Berkowitz et al Expires January 2001 17 Benchmarking Methodology for Exterior Routing Convergence Once the basic protocol update responses have been calibrated,longer event sequences must be tested for. These sequences may look like AwAdiffwadupAAdup..and occur at, eg, 300 per second.Announces will be more overhead intensive than withdraws. 8. Multiple Peers 8.1 Initial Convergence This test is similar to the single peer initial convergence time, but the number of external peers should increase. All peers are expected to advertise the same number of routes to the DUT. A ratio of n paths per prefix may be considered such that the first n neighbors must advertise the exact same prefixes (only the AS_PATH should be different). If the number of eBGP peers tested goes beyond n, then the routes should be distributed among all the peers so that the ratio is maintained and all advertise the same number of routes. Procedure: Initialize the test scenario by establishing an eBGP session between the DUT and TR3. No routing information is exchanged. Initialize TR1 and up to TRn with a predetermined number of prefixes such that such that the ratio is maintained. The physical link between TR1 thru TRn and the DUT should also be active at this time. Establish an eBGP session between TR1 thru TRn and the DUT. Each TR router should belong to a different AS. All the prefixes in TR1 thru TRn should be advertised at this time to the DUT. The convergence time measurement should start when the first OPEN message is exchanged between any TR and the DUT. The end of the convergence period is marked when all the TR routers have advertised all the paths to the DUT, and TR3 has received the last UPDATE. The number of test routers should be increased in equal intervals until the maximum number under test is reached. It is expected that the DUT will install the routes in its FIB. However, this test will not test for this. 9. References 1 Bradner, S., "The Internet Standards Process -- Revision 3", BCP 9, RFC 2026, October 1996. 2 Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. 3 "An Experimental Study of Delayed Internet Routing Convergence." Abha Ahuja, Farnam Jahanian, Abhijit Bose, Craig Labovitz, RIPE 37 - Routing WG. Berkowitz et al Expires January 2001 18 Benchmarking Methodology for Exterior Routing Convergence 4 "Origins of Internet Routing Instability," Infocom 99 Craig Labovitz, G. Robert Malan, Farnam Jahanian], 5 "BGP Route Flap Damping" C. Villamizar, R.Chandra, R. Govindan, RFC 2539 November 1998. 6 "Benchmarking Methodology for Network Interconnect Devices",RFC 2544, S. Bradner, J. McQuaid. March 1999. 7 Routing Policy Specification Language (RPSL), RFC 2622, " C.Alaettinoglu, C. Villamizar, E. Gerich, D. Kessens, D. Meyer, T.Bates, D. Karrenberg, M. Terpstra. June 1999. 8 "Route Refresh Capability for BGP-4", RFC 2928, E. Chen. 9 "Terminology for Forwarding Information Based (FIB)based Router Performance Benchmarking", Work in Progress, IETF,draft-ietf-bmwg-fib-term-00.txt 10 "A Border Gateway Protocol 4 (BGP-4)", RFC 1771, Y. Rekhter, T. Li. March 1995. 11 "Benchmarking Terminology for Network Interconnection Devices",RFC 1242, S. Bradner. July 1991. 12 "Requirements for IP Version 4 Routers", RFC 1812, F. Baker. June 1995. 13 "BGP Route Flap Damping", RFC 2439, C. Villamizar, R. Chandra, R. Govindan. November 1998. 14 "Protection of BGP Sessions via the TCP MD5 Signature Option", RFC 2385, A. Heffernan. August 1998. 15 "Multiprotocol Extensions for BGP-4", RFC 2858, T. Bates,Y. Rekhter, R. Chandra, D. Katz. June 2000. 16 Junos 4.2 Software Routing Guide 17 RIPE 178, "RIPE Routing-WG Recommendation for coordinated route-flap damping parameters, Tony Barber, Sean Doran, Daniel Karrenberg, Christian Panigl, Joachim Schmitz 10. Acknowledgments Thanks to Francis Ovenden for review and Abha Ahuja for encouragement.Much appreciation to Jeff Haas, Matt Richardson, and Shane Wright at Nexthop for comments and input. 9 Author's Addresses Howard Berkowitz Nortel Networks 5012 S. 25th St PO Box 6897 Arlington VA 22206 Phone: +1 703 998-5819 (ESN 451-5819) Fax: +1 703 998-5058 EMail: hberkowi@nortelnetworks.com hcb@clark.net Alvaro Retana Cisco Systems, Inc. 7025 Kit Creek Rd. Berkowitz et al Expires January 2001 19 Benchmarking Methodology for Exterior Routing Convergence Research Triangle Park, NC 27709 Email: aretana@cisco.com Susan Hares Nexthop Technologies 517 W. William Ann Arbor, Mi 48103 Phone: Email: skh@nexthop.com Padma Krishnaswamy Nexthop Technologies 517 W William Ann Arbor, Mi 48103 Phone: Email: kri@nexthop.com Full Copyright Statement Copyright (C) The Internet Society (2000). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implmentation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDIN BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. ----- End forwarded message -----