栏目搜索
 
 
 
 
你的位置:首页 > 协议大全 > RFC4098 - Terminology for Benchmarking BGP Device Convergence in the Control Plane >
 

RFC4098 - Terminology for Benchmarking BGP Device Convergence in the Control Plane

发布者:[本站编辑] | 来源:[]

RFC4098 - Terminology for Benchmarking BGP Device Convergence in the Control Plane_电脑维修资料库

network working group h. berkowitzrequest for comments: 4098 gett communications & cci trainingcategory: informational e. davies, ed.folly consultings. haresnexthop technologiesp. krishnaswamysaicm. leppconsultantjune 2005terminology for benchmarking bgp device convergencein the control planestatus of this memothis memo provides information for the internet community. it doesnot specify an internet standard of any kind. distribution of thismemo is unlimited.copyright noticecopyright (c) the internet society (2005).abstractthis document establishes terminology to standardize the descriptionof benchmarking methodology for measuring ebgp convergence in thecontrol plane of a single bgp device. future documents will addressibgp convergence, the initiation of forwarding based on convergedcontrol plane information and multiple interacting bgp devices. thisterminology is applicable to both ipv4 and ipv6. illustrativeexamples of each version are included where relevant.table of contents1. introduction ....................................................31.1. overview and road map ......................................41.2. definition format ..........................................52. components and characteristics of routing information ...........52.1. (network) prefix ...........................................52.2. network prefix length ......................................62.3. route ......................................................62.4. bgp route ..................................................72.5. network level reachability information (nlri) ..............72.6. bgp update message .........................................83. routing data structures and route categories ....................83.1. routing information base (rib) .............................83.1.1. adj-rib-in and adj-rib-out ..........................83.1.2. loc-rib .............................................93.2. prefix filtering ...........................................93.3. routing policy ............................................103.4. routing policy information base ...........................103.5. forwarding information base (fib) .........................113.6. bgp instance ..............................................123.7. bgp device ................................................123.8. bgp session ...............................................133.9. active bgp session ........................................133.10. bgp peer .................................................133.11. bgp neighbor .............................................143.12. minrouteadvertisementinterval (mrai) .....................143.13. minasoriginationinterval (maoi) ..........................153.14. active route .............................................153.15. unique route .............................................153.16. non-unique route .........................................163.17. route instance ...........................................164. constituent elements of a router or network of routers .........174.1. default route, default-free table, and full table .........174.1.1. default route ......................................174.1.2. default-free routing table .........................184.1.3. full default-free table ............................184.1.4. default-free zone ..................................194.1.5. full provider-internal table .......................194.2. classes of bgp-speaking routers ...........................194.2.1. provider edge router ...............................204.2.2. subscriber edge router .............................204.2.3. inter-provider border router .......................214.2.4. core router ........................................215. characterization of sets of update messages ....................225.1. route packing .............................................225.2. route mixture .............................................235.3. update train ..............................................245.4. randomness in update trains ...............................245.5. route flap ................................................256. route changes and convergence ..................................256.1. route change events .......................................256.2. device convergence in the control plane ...................277. bgp operation events ...........................................287.1. hard reset ................................................287.2. soft reset ................................................298. factors that impact the performance of the convergenceprocess ........................................................298.1. general factors affecting device convergence ..............298.1.1. number of peers ....................................298.1.2. number of routes per peer ..........................308.1.3. policy processing/reconfiguration ..................308.1.4. interactions with other protocols ..................308.1.5. flap damping .......................................308.1.6. churn ..............................................318.2. implementation-specific and other factors affecting bgp ...318.2.1. forwarded traffic ..................................318.2.2. timers .............................................328.2.3. tcp parameters underlying bgp transport ............328.2.4. authentication .....................................329. security considerations ........................................3210. acknowledgements ..............................................3211. references ....................................................3311.1. normative references ....................................3311.2. informative references ..................................341. introductionthis document defines terminology for use in characterizing theconvergence performance of bgp processes in routers or other devicesthat instantiate bgp functionality. (see 'a border gateway protocol4 (bgp-4)' , referred to as rfc 1771 in the remainder of thedocument.) it is the first part of a two-document series, of whichthe subsequent document will contain the associated tests andmethodology. this terminology is applicable to both ipv4 and ipv6.illustrative examples of each version are included where relevant.however, this document is primarily targeted for bgp-4 in ipv4networks. ipv6 will require the use of mp-bgp , asdescribed in rfc 2545 , but this document will not addressterminology or issues specific to these extensions of bgp-4. alsoterminology and issues specific to the extensions of bgp that supportvpns as described in rfc 2547 are out of scope for thisdocument.the following observations underlie the approach adopted in thisdocument, and in the companion document:o the principal objective is to derive methodologies thatstandardize conducting and reporting convergence-relatedmeasurements for bgp.o it is necessary to remove ambiguity from many frequently usedterms that arise in the context of these measurements.o as convergence characterization is a complex process, it isdesirable to restrict the initial focus in this set of documentsto specifying how to take basic control-plane measurements as afirst step in characterizing bgp convergence.for path-vector protocols, such as bgp, the primary initial focuswill therefore be on network and system control-plane activity consisting of the arrival, processing, and propagation ofrouting information.we note that for testing purposes, all optional parameters should beturned off. all variable parameters should be at their defaultsetting unless the test specifies otherwise.subsequent documents will explore the more intricate aspects ofconvergence measurement, such as the impacts of the presence ofmultiprotocol extensions for bgp-4, policy processing, simultaneoustraffic on the control and data paths within the device under test(dut), and other realistic performance modifiers. convergence ofinterior gateway protocols (igps) will also be considered in separatedocuments.1.1. overview and road mapcharacterizations of the bgp convergence performance of a devicemust-take into account all distinct stages and aspects of bgp.functionality. this requires that the relevant terms and metrics beas specifically defined as possible. such definition is the goal ofthis document.the necessary definitions are classified into separate categories:o components and characteristics of routing informationo routing data structures and route categorieso descriptions of the constituent elements of a network or a routerthat is undergoing convergenceo characterization of sets of update messages, types of route-changeevents, as well as some events specific to bgp operationo descriptions of factors that impact the performance of convergenceprocesses1.2. definition formatthe definition format is equivalent to that defined in 'requirementsfor ip version 4 routers' , and is repeated here forconvenience:x.x term to be defined (e.g., latency).definition:one or more sentences forming the body of the definition.discussion:a brief discussion of the term, its application, and anyrestrictions that there might be on measurement procedures.measurement units:the units used to report measurements of this term. this item maynot be applicable (n.a.).issues:list of issues or conditions that could affect this term.see also:list of related terms that are relevant to the definition ordiscussion of this term.2. components and characteristics of routing information2.1. (network) prefixdefinition:a network prefix is a contiguous set of bits at the moresignificant end of the address that collectively designates theset of systems within a network; host numbers select among thosesystems. (this definition is taken directly from section 2.2.5.2,classless inter domain routing (cidr), of rfc 1812.)discussion:in the cidr context, the network prefix is the network componentof an ip address. in ipv4 systems, the network component of acomplete address is known as the 'network part', and the remainingpart of the address is known as the 'host part'. in ipv6 systems,the network component of a complete address is known as the'subnet prefix', and the remaining part is known as the 'interfaceidentifier'.measurement units: n.a.issues:see also:2.2. network prefix lengthdefinition:the network prefix length is the number of bits, out of the totalconstituting the address field, that define the network prefixportion of the address.discussion:a common alternative to using a bit-wise mask to communicate thiscomponent is the use of slash (/) notation. this binds the notionof network prefix length in bits to an ip address. for example,141.184.128.0/17 indicates that the network component of this ipv4address is 17 bits wide. similar notation is used for ipv6network prefixes; e.g., 2001:db8:719f::/48. when referring togroups of addresses, the network prefix length is often used as ameans of describing groups of addresses as an equivalence class.for example, 'one hundred /16 addresses' refers to 100 addresseswhose network prefix length is 16 bits.measurement units:bits.issues:see also:network prefix.2.3. routedefinition:in general, a 'route' is the n-tuple . a route is notend-to-end, but is defined with respect to a specific next hopthat should take packets on the next step toward their destinationas defined by the prefix. in this usage, a route is the basicunit of information about a target destination distilled fromrouting protocols.discussion:this term refers to the concept of a route common to all routingprotocols. with reference to the definition above, typical non-routing-protocol attributes would be associated with diffserv ortraffic engineering.measurement units: n.a.issues:none.see also:bgp route.2.4. bgp routedefinition:a bgp route is an n-tuple .discussion:bgp attributes, such as nexthop or as path, are defined in rfc1771, where they are known as path attributes, and they are thequalifying data that define the route. from rfc 1771: forpurposes of this protocol a route is defined as a unit ofinformation that pairs a destination with the attributes of a pathto that destination.measurement units: n.a.issues:see also:route, prefix, adj-rib-in, network level reachability information(nlri)2.5. network level reachability information (nlri)definition:the nlri consists of one or more network prefixes with the sameset of path attributes.discussion:each prefix in the nlri is combined with the (common) pathattributes to form a bgp route. the nlri encapsulates a set ofdestinations to which packets can be routed (from this point inthe network) along a common route described by the pathattributes.measurement units: n.a.issues:see also:route packing, network prefix, bgp route, nlri.2.6. bgp update messagedefinition:an update message contains an advertisement of a single nlrifield, possibly containing multiple prefixes, and multiplewithdrawals of unfeasible routes. see rfc 1771 for details.discussion:from rfc 1771: a variable length sequence of path attributes ispresent in every update. each path attribute is a triple of variablelength.measurement units: n.a.see also:3. routing data structures and route categories3.1. routing information base (rib)the rib collectively consists of a set of logically (not necessarilyphysically) distinct databases, each of which is enumerated below.the rib contains all destination prefixes to which the router mayforward, and one or more currently reachable next hop addresses forthem.routes included in this set potentially have been selected fromseveral sources of information, including hardware status, interiorrouting protocols, and exterior routing protocols. rfc 1812 containsa basic set of route selection criteria relevant in an all-sourcecontext. many implementations impose additional criteria. a commonimplementation-specific criterion is the preference given todifferent routing information sources.3.1.1. adj-rib-in and adj-rib-outdefinition:adj-rib-in and adj-rib-out are views of routing information fromthe perspective of individual peer routers. the adj-rib-incontains information advertised to the dut by a specific peer.the adj-rib-out contains the information the dut will advertise tothe peer. see rfc 1771.discussion:issues:measurement units:number of route instances.see also:route, bgp route, route instance, loc-rib, fib.3.1.2. loc-ribdefinition:the loc-rib contains the set of best routes selected from thevarious adj-ribs, after applying local policies and the bgp routeselection algorithm.discussion:the separation implied among the various ribs is logical. it doesnot necessarily follow that these ribs are distinct and separateentities in any given implementation. types of routes that needto be considered include internal bgp, external bgp, interface,static, and igp routes.issues:measurement units:number of routes.see also:route, bgp route, route instance, adj-rib-in, adj-rib-out, fib.3.2. prefix filteringdefinition:prefix filtering is a technique for eliminating routes fromconsideration as candidates for entry into a rib by matching thenetwork prefix in a bgp route against a list of network prefixes.discussion:a bgp route is eliminated if, for any filter prefix from the list,the route prefix length is equal to or longer than the filterprefix length and the most significant bits of the two prefixesmatch over the length of the filter prefix. see 'cooperativeroute filtering capability for bgp-4' for examples ofusage.measurement units:number of filter prefixes; lengths of prefixes.issues:see also:bgp route, network prefix, network prefix length, routing policy,routing policy information base.3.3. routing policydefinition:routing policy is the ability to define conditions for accepting,rejecting, and modifying routes received in advertisements.discussion:rfc 1771 further constrains policy to be within the hop-by-hoprouting paradigm. policy is implemented using filters andassociated policy actions such as prefix filtering. many asesformulate and document their policies using the routing policyspecification language (rpsl) and then automaticallygenerate configurations for the bgp processes in their routersfrom the rpsl specifications.measurement units:number of policies; length of policies.issues:see also:routing policy information base, prefix filtering.3.4. routing policy information basedefinition:a routing policy information base is the set of incoming andoutgoing policies.discussion:all references to the phase of the bgp selection process below aremade with respect to rfc 1771 definition of these phases.incoming policies are applied in phase 1 of the bgp selectionprocess to the adj-rib-in routes to set the metric for the phase 2decision process. outgoing policies are applied in phase 3 of thebgp process to the adj-rib-out routes preceding route (prefix andpath attribute tuple) announcements to a specific peer. policiesin the policy information base have matching and actionconditions. common information to match includes route prefixes,as paths, communities, etc. the action on match may be to dropthe update and not to pass it to the loc-rib, or to modify theupdate in some way, such as changing local preference (on input)or med (on output), adding or deleting communities, prepending thecurrent as in the as path, etc. the amount of policy processing(both in terms of route maps and filter/access lists) will impactthe convergence time and properties of the distributed bgpalgorithm. the amount of policy processing may vary from a simplepolicy that accepts all routes and sends them according to acomplex policy with a substantial fraction of the prefixes beingfiltered by filter/access lists.measurement units:number and length of policies.issues:see also:3.5. forwarding information base (fib)definition:according to the definition in appendix b of ripe-37 :the table containing the information necessary to forward ipdatagrams is called the forwarding information base. at minimum,this contains the interface identifier and next hop informationfor each reachable destination network prefix.discussion:the forwarding information base describes a database indexingnetwork prefixes versus router port identifiers. the forwardinginformation base is distinct from the routing table (the routinginformation base or rib), which holds all routing informationreceived from routing peers. it is a data plane construct and isused for the forwarding of each packet. the forwardinginformation base is generated from the rib. for the purposes ofthis document, the fib is effectively the subset of the rib usedby the forwarding plane to make per-packet forwarding decisions.most current implementations have full, non-cached fibs per routerinterface. all the route computation and convergence occursbefore entries are downloaded into a fib.measurement units: n.a.issues:see also:route, rib.3.6. bgp instancedefinition:a bgp instance is a process with a single loc-rib.discussion:for example, a bgp instance would run in routers or testequipment. a test generator acting as multiple peers willtypically run more than one instance of bgp. a router wouldtypically run a single instance.measurement units: n.a.issues:see also:3.7. bgp devicedefinition:a bgp device is a system that has one or more bgp instancesrunning on it, each of which is responsible for executing the bgpstate machine.discussion:we have chosen to use device as the general case, to deal withthe understood (e.g., ) and yet-to-be-invented cases wherethe control processing may be separate from forwarding .a bgp device may be a traditional router, a route server, a bgp-aware traffic steering device, or a non-forwarding routereflector. bgp instances such as route reflectors or servers, forexample, never forward traffic, so forwarding-based measurementswould be meaningless for them.measurement units: n.a.issues:see also:3.8. bgp sessiondefinition:a bgp session is a session between two bgp instances.discussion:measurement units: n.a.issues:see also:3.9. active bgp sessiondefinition:an active bgp session is one that is in the established state.(see rfc 1771.)discussion:measurement units: n.a.issues:see also:3.10. bgp peerdefinition:a bgp peer is another bgp instance to which the dut is in theestablished state. (see rfc 1771.)discussion:in the test scenarios for the methodology discussion that willfollow this document, peers send bgp advertisements to the dut andreceive dut-originated advertisements. we recommend that thepeering relation be established before tests begin. it might alsobe interesting to measure the time required to reach theestablished state. this is a protocol-specific definition, not tobe confused with another frequent usage, which refers to thebusiness/economic definition for the exchange of routes withoutfinancial compensation. it is worth noting that a bgp peer, bythis definition, is associated with a bgp peering session, andthere may be more than one such active session on a router or on atester. the peering sessions referred to here may exist betweenvarious classes of bgp routers (see section 4.2).measurement units:number of bgp peers.issues:see also:3.11. bgp neighbordefinition:a bgp neighbor is a device that can be configured as a bgp peer.discussion:measurement units:issues:see also:3.12. minrouteadvertisementinterval (mrai)definition:(paraphrased from rfc 1771) the mrai timer determines the minimumtime between advertisements of routes to a particular destination(prefix) from a single bgp device. the timer is applied on apre-prefix basis, although the timer is set on a per-bgp devicebasis.discussion:given that a bgp instance may manage in excess of 100,000 routes,rfc 1771 allows for a degree of optimization in order to limit thenumber of timers needed. the mrai does not apply to routesreceived from bgp speakers in the same as or to explicitwithdrawals. rfc 1771 also recommends that random jitter isapplied to mrai in an attempt to avoid synchronization effectsbetween the bgp instances in a network. in this document, wedefine routing plane convergence by measuring from the time annlri is advertised to the dut to the time it is advertised fromthe dut. clearly any delay inserted by the mrai will have asignificant effect on this measurement.measurement units:seconds.issues:see also:nlri, bgp route.3.13. minasoriginationinterval (maoi)definition:the maoi specifies the minimum interval between advertisements oflocally originated routes from this bgp instance.discussion:random jitter is applied to maoi in an attempt to avoidsynchronization effects between bgp instances in a network.measurement units:seconds.issues:it is not known what, if any, relationship exists between thesettings of mrai and maoi.see also:mrai, bgp route.3.14. active routedefinition:route for which there is a fib entry corresponding to a rib entry.discussion:measurement units:number of routes.issues:see also:rib.3.15. unique routedefinition:a unique route is a prefix for which there is just one routeinstance across all adj-ribs-in.discussion:measurement units: n.a.issues:see also:route, route instance.3.16. non-unique routedefinition:a non-unique route is a prefix for which there is at least oneother route in a set including more than one adj-rib-in.discussion:measurement units: n.a.issues:see also:route, route instance, unique active route.3.17. route instancedefinition:a route instance is one of several possible occurrences of a routefor a particular prefix.discussion:when a router has multiple peers from which it accepts routes,routes to the same prefix may be received from several peers.this is then an example of multiple route instances. each routeinstance is associated with a specific peer. the bgp algorithmthat arbitrates between the available candidate route instancesmay reject a specific route instance due to local policy.measurement units:number of route instances.issues:the number of route instances in the adj-rib-in bases will varybased on the function to be performed by a router. an inter-provider border router, located in the default-free zone (seesection 4.1.4), will likely receive more route instances than aprovider edge router, located closer to the end-users of thenetwork.see also:4. constituent elements of a router or network of routersmany terms included in this list of definitions were originallydescribed in previous standards or papers. they are included herebecause of their pertinence to this discussion. where relevant,reference is made to these sources. an effort has been made to keepthis list complete with regard to the necessary concepts withoutover-definition.4.1. default route, default-free table, and full tablean individual router's routing table may not necessarily contain adefault route. not having a default route, however, is notsynonymous with having a full default-free table (dft). also, arouter that has a full set of routes as in a dft, but that also has a'discard' rule for a default route would not be considered defaultfree.note that in this section the references to number of routes are toroutes installed in the loc-rib, which are therefore unique routes,not route instances. also note that the total number of routeinstances may be 4 to 10 times the number of routes.4.1.1. default routedefinition:a default route can match any destination address. if a routerdoes not have a more specific route for a particular packet'sdestination address, it forwards this packet to the next hop inthe default route entry, provided that its forwarding table(forwarding information base, or fib, contains one). the notationfor a default route for ipv4 is 0.0.0.0/0 and for ipv6 it is0:0:0:0:0:0:0:0 or ::/0.discussion:measurement units: n.a.issues:see also:default-free routing table, route, route instance.4.1.2. default-free routing tabledefinition:a default-free routing table has no default routes and istypically seen in routers in the core or top tier of routers inthe network.discussion:the term originates from the concept that routers at the core ortop tier of the internet will not be configured with a defaultroute (notation in ipv4 0.0.0.0/0 and in ipv6 0:0:0:0:0:0:0:0 or::/0). thus they will forward every packet to a specific next hopbased on the longest match between the destination ip address andthe routes in the forwarding table.default-free routing table size is commonly used as an indicatorof the magnitude of reachable internet address space. however,default-free routing tables may also include routes internal tothe router's as.measurement units:the number of routes.see also:full default-free table, default route.4.1.3. full default-free tabledefinition:a full default-free table is the union of all sets of bgp routestaken from all the default-free bgp routing tables collectivelyannounced by the complete set of autonomous systems making up thepublic internet. due to the dynamic nature of the internet, theexact size and composition of this table may vary slightlydepending on where and when it is observed.discussion:it is generally accepted that a full table, in this usage, doesnot contain the infrastructure routes or individual sub-aggregatesof routes that are otherwise aggregated by the provider beforeannouncement to other autonomous systems.measurement units:number of routes.issues:the full default-free routing table is not the same as the unionof all reachable unicast addresses. the table simply does notcontain the default prefix (0/0) and does contain the union of allsets of bgp routes from default-free bgp routing tables.see also:routes, route instances, default route.4.1.4. default-free zonedefinition:the default-free zone is the part of the internet backbone thatdoes not have a default route.discussion:measurement units:issues:see also:default route.4.1.5. full provider-internal tabledefinition:a full provider-internal table is a superset of the full routingtable that contains infrastructure and non-aggregated routes.discussion:experience has shown that this table might contain 1.3 to 1.5times the number of routes in the externally visible full table.tables of this size, therefore, are a real-world requirement forkey internal provider routers.measurement units:number of routes.issues:see also:routes, route instances, default route.4.2. classes of bgp-speaking routersa given router may perform more than one of the following functions,based on its logical location in the network.4.2.1. provider edge routerdefinition:a provider edge router is a router at the edge of a provider'snetwork that speaks ebgp to a bgp speaker in another as.discussion:the traffic that transits this router may be destined to or mayoriginate from non-adjacent autonomous systems. in particular,the med values used in the provider edge router would not bevisible in the non-adjacent autonomous systems. such a routerwill always speak ebgp and may speak ibgp.measurement units:issues:see also:4.2.2. subscriber edge routerdefinition:a subscriber edge router is router at the edge of the subscriber'snetwork that speaks ebgp to its provider's as(s).discussion:the router belongs to an end user organization that may be multi-homed, and that carries traffic only to and from that end user as.such a router will always speak ebgp and may speak ibgp.measurement units:issues:this definition of an enterprise border router (which is what mostsubscriber edge routers are) is practical rather than rigorous.it is meant to draw attention to the reality that many enterprisesmay need a bgp speaker that advertises their own routes andaccepts either default alone or partial routes. in such cases,they may be interested in benchmarks that use a partial routingtable, to see whether a smaller control plane processor will meettheir needs.see also:4.2.3. inter-provider border routerdefinition:an inter-provider border router is a bgp speaking router thatmaintains bgp sessions with other bgp speaking routers in otherproviders' ases.discussion:traffic transiting this router may be originated in or destinedfor another as that has no direct connectivity with thisprovider's as. such a router will always speak ebgp and may speakibgp.measurement units:issues:see also:4.2.4. core routerdefinition:an core router is a provider router internal to the provider'snet, speaking ibgp to that provider's edge routers, other intra-provider core routers, or the provider's inter-provider borderrouters.discussion:such a router will always speak ibgp and may speak ebgp.measurement units:issues:by this definition, the duts that are ebgp routers aren't corerouters.see also:5. characterization of sets of update messagesthis section contains a sequence of definitions that build up to thedefinition of an update train. the packet train concept wasoriginally introduced by jain and routhier . it is hereadapted to refer to a train of packets of interest in bgp performancetesting.this is a formalization of the sort of test stimulus that is expectedas input to a dut running bgp. this data could be a well-characterized, ordered, and timed set of hand-crafted bgp updatepackets. it could just as well be a set of bgp update packets thathave been captured from a live router.characterization of route mixtures and update trains is an open areaof research. the particular question of interest for this work isthe identification of suitable update trains, modeled on or takenfrom live traces that reflect realistic sequences of updates andtheir contents.5.1. route packingdefinition:route packing is the number of route prefixes accommodated in asingle routing protocol update message, either as updates(additions or modifications) or as withdrawals.discussion:in general, a routing protocol update may contain more than oneprefix. in bgp, a single update may contain two sets of multiplenetwork prefixes: one set of additions and updates with identicalattributes (the nlri) and one set of unfeasible routes to bewithdrawn.measurement units:number of prefixes.issues:see also:route, bgp route, route instance, update train, nlri.5.2. route mixturedefinition:a route mixture is the demographics of a set of routes.discussion:a route mixture is the input data for the benchmark. theparticular route mixture used as input must be selected to suitthe question being asked of the benchmark. data containing simpleroute mixtures might be suitable to test the performance limits ofthe bgp device. using live data or input that simulates live datawill improve understanding of how the bgp device will operate in alive network. the data for this kind of test must be routemixtures that model the patterns of arriving control traffic inthe live internet. to accomplish this kind of modeling, it isnecessary to identify the key parameters that characterize a liveinternet route mixture. the parameters and how they interact isan open research problem. however, we identify the following asaffecting the route mixture:* path length distribution* attribute distribution* prefix length distribution* packet packing* probability density function of inter-arrival times of updateseach of the items above is more complex than a single number. forexample, one could consider the distribution of prefixes by as or bylength.measurement units:probability density functions.issues:see also:nlri, rib.5.3. update traindefinition:an update train is a set of routing protocol update messages sentby a router to a bgp peer.discussion:the arrival pattern of updates can be influenced by many things,including tcp parameters, hold-down timers, upstream processing, apeer coming up, or multiple peers sending at the same time.network conditions such as a local or remote peer flapping a linkcan also affect the arrival pattern.measurement units:probability density function for the inter-arrival times of updatepackets in the train.issues:characterizing the profiles of real-world update trains is amatter for future research. in order to generate realistic updatetrains as test stimuli, a formal mathematical scheme or a provenheuristic is needed to drive the selection of prefixes. whatevermechanism is selected, it must generate update trains that havesimilar characteristics to those measured in live networks.see also:route mixture, mrai, maoi.5.4. randomness in update trainsas we have seen from the previous sections, an update train used as atest stimulus has a considerable number of parameters that can bevaried, to a greater or lesser extent, randomly and independently.a random update train will contain a route mixture randomized across:* nlris* updates and withdrawals* prefixes* inter-arrival times of the updates and possibly across othervariables.this is intended to simulate the unpredictable asynchronous nature ofthe network, whereby update packets may have arbitrary contents andbe delivered at random times.it is important that the data set be randomized sufficiently to avoidfavoring one vendor's implementation over another's. specifically,the distribution of prefixes could be structured to favor theinternal organization of the routes in a particular vendor'sdatabases. this is to be avoided.5.5. route flapdefinition:a route flap is a change of state (withdrawal, announcement,attribute change) for a route.discussion:route flapping can be considered a special and pathological caseof update trains. a practical interpretation of what may beconsidered excessively rapid is the ripe 229 , whichcontains current guidelines on flap-damping parameters.measurement units:flapping events per unit time.issues:specific flap events can be found in section 6.1. a bench-markershould use a mixture of different route change events in testing.see also:route change events, flap damping, packet train6. route changes and convergencethe following two definitions are central to the benchmarking ofexternal routing convergence and are therefore singled out for moreextensive discussion.6.1. route change eventsa taxonomy characterizing routing information changes seen inoperational networks is proposed in ripe-37 and labovitz etal . these papers describe bgp protocol-centric events andevent sequences in the course of an analysis of network behavior.the terminology in the two papers categorizes similar but slightlydifferent behaviors with some overlap. we would like to apply thesetaxonomies to categorize the tests under definition where possible,because these tests must tie in to phenomena that arise in actualnetworks. we avail ourselves of, or may extend, this terminology asnecessary for this purpose.a route can be changed implicitly by replacing it with another routeor explicitly by withdrawal followed by the introduction of a newroute. in either case, the change may be an actual change, nochange, or a duplicate. the notation and definition of individualcategorizable route change events is adopted from andgiven below.1. aadiff: implicit withdrawal of a route and replacement by a routedifferent in some path attribute.2. aadup: implicit withdrawal of a route and replacement by routethat is identical in all path attributes.3. wadiff: explicit withdrawal of a route and replacement by adifferent route.4. wadup: explicit withdrawal of a route and replacement by a routethat is identical in all path attributes.to apply this taxonomy in the benchmarking context, we need terms todescribe the sequence of events from the update train perspective, aslisted above, and event indications in the time domain in order tomeasure activity from the perspective of the dut. with this in mind,we incorporate and extend the definitions of to thefollowing:1. tup (tdx): route advertised to the dut by test device x2. tdown(tdx): route being withdrawn by device x3. tupinit(tdx): the initial announcement of a route to a uniqueprefix4. twf(tdx): route fail over after an explicit withdrawal.but we need to take this a step further. each of these events caninvolve a single route, a short packet train, or a full routingtable. we further extend the notation to indicate how many routesare conveyed by the events above:1. tup(1,tdx) means device x sends 1 route2. tup(s,tdx) means device x sends a train, s, of routes3. tup(dft,tdx) means device x sends an approximation of a fulldefault-free table.the basic criterion for selecting a better route is the finaltiebreaker defined in rfc 1771, the router id. as a consequence,this memorandum uses the following descriptor events, which areroutes selected by the bgp selection process rather than simpleupdates:1. tbest -- the current best path.2. tbetter -- advertise a path that is better than tbest.3. tworse -- advertise a path that is worse than tbest.6.2. device convergence in the control planedefinition:a routing device is said to have converged at the point in timewhen the dut has performed all actions in the control plane neededto react to changes in topology in the context of the testcondition.discussion:for example, when considering bgp convergence, the convergenceresulting from a change that alters the best route instance for asingle prefix at a router would be deemed to have occurred whenthis route is advertised to its downstream peers. by way ofcontrast, ospf convergence concludes when spf calculations havebeen performed and the required link states are advertised onward.the convergence process, in general, can be subdivided into threedistinct phases:* convergence across the entire internet,* convergence within an autonomous system,* convergence with respect to a single device.convergence with respect to a single device can be* convergence with regard to data forwarding process(es)* convergence with regard to the routing process(es), the focusof this document.it is the latterthat we describe herein and in the methodology documents.because we are trying to benchmark the routing protocolperformance, which is only a part of the device overall, thisdefinition is intended (as far as is possible) to exclude anyadditional time needed to download and install theforwarding information base in the data plane. this definition isusable for different families of protocols.it is of key importance to benchmark the performance of each phaseof convergence separately before proceeding to a compositecharacterization of routing convergence, whereimplementation-specific dependencies are allowed to interact.care also needs to be taken to ensure that the convergence time isnot influenced by policy processing on downstream peers.the time resolution needed to measure the device convergencedepends to some extent on the types of the interfaces on therouter. for modern routers with gigabit or faster interfaces, anindividual update may be processed and re-advertised in very muchless than a millisecond so that time measurements must be made toa resolution of hundreds to tens of microseconds or better.measurement units:time period.issues:see also:7. bgp operation eventsthe bgp process(es) in a device might restart because operatorintervention or a power failure caused a complete shutdown. in thiscase, a hard reset is needed. a peering session could be lost, forexample, because of action on the part of the peer or a dropped tcpsession. a device can reestablish its peers and re-advertise allrelevant routes in a hard reset. however, if a peer is lost, butthe bgp process has not failed, bgp has mechanisms for a softreset.7.1. hard resetdefinition:an event that triggers a complete re-initialization of therouting tables on one or more bgp sessions, resulting in exchangeof a full routing table on one or more links to the router.discussion:measurement units: n.a.issues:see also:7.2. soft resetdefinition:a soft reset is performed on a per-neighbor basis; it does notclear the bgp session while re-establishing the peering relationand does not stop the flow of traffic.discussion:there are two methods of performing a soft reset: (1) gracefulrestart , wherein the bgp device that has lost apeer continues to forward traffic for a period of time beforetearing down the peer's routes and (2) softrefresh , wherein a bgp device can request a peer'sadj-rib-out.measurement units: n.a.issues:see also:8. factors that impact the performance of the convergence processalthough this is not a complete list, all the items discussed belowhave a significant effect on bgp convergence. not all of them can beaddressed in the baseline measurements described in this document.8.1. general factors affecting device convergencethese factors are conditions of testing external to the router deviceunder test (dut).8.1.1. number of peersas the number of peers increases, the bgp route selection algorithmis increasingly exercised. in addition, the phasing and frequency ofupdates from the various peers will have an increasingly markedeffect on the convergence process on a router as the number of peersgrows, depending on the quantity of updates generated by eachadditional peer. increasing the number of peers also increases theprocessing workload for tcp and bgp keepalives.8.1.2. number of routes per peerthe number of routes per bgp peer is an obvious stressor to theconvergence process. the number and relative proportion ofmultiple route instances and distinct routes being added or withdrawnby each peer will affect the convergence process, as will the mix ofoverlapping route instances and igp routes.8.1.3. policy processing/reconfigurationthe number of routes and attributes being filtered and set as afraction of the target route table size is another parameter thatwill affect bgp convergence.the following are extreme examples:o minimal policy: receive all, send all.o extensive policy: up to 100% of the total routes have applicablepolicy.8.1.4. interactions with other protocolsthere are interactions in the form of precedence, synchronization,duplication, and the addition of timers and route selection criteria.ultimately, understanding bgp4 convergence must include anunderstanding of the interactions with both the igps and theprotocols associated with the physical media, such as ethernet,sonet, and dwdm.8.1.5. flap dampinga router can use flap damping to respond to route flapping. use offlap damping is not mandatory, so the decision to enable the feature,and to change parameters associated with it, can be considered amatter of routing policy.the timers are defined by rfc 2439 and discussed in ripe-229 . if this feature is in effect, it requires that thedevice keep additional state to carry out the damping, which can havea direct impact on the control plane due to increased processing. inaddition, flap damping may delay the arrival of real changes in aroute and affect convergence times.8.1.6. churnin theory, a bgp device could receive a set of updates thatcompletely define the internet and could remain in a steady state,only sending appropriate keepalives. in practice, the internet willalways be changing.churn refers to control-plane processor activity caused byannouncements received and sent by the router. it does not includekeepalives and tcp processing.churn is caused by both normal and pathological events. for example,if an interface of the local router goes down and the associatedprefix is withdrawn, that withdrawal is a normal activity, althoughit contributes to churn. if the local device receives a withdrawalof a route it already advertises, or an announcement of a route itdid not previously know, and it re-advertises this information, theseare normal constituents of churn. routine updates can range fromsingle announcements or withdrawals, to announcements of an entiredefault-free table. the latter is completely reasonable as aninitialization condition.flapping routes are a pathological contributor to churn, as is medoscillation . the goal of flap damping is to reduce thecontribution of flapping to churn.the effect of churn on overall convergence depends on the processingpower available to the control plane, and on whether the sameprocessor(s) are used for forwarding and control.8.2. implementation-specific and other factors affecting bgpconvergencethese factors are conditions of testing internal to the device undertest (dut), although they may affect its interactions with testdevices.8.2.1. forwarded trafficthe presence of actual traffic in the device may stress the controlpath in some fashion if both the offered load (due to data) and thecontrol traffic (fib updates and downloads as a consequence of flaps)are excessive. the addition of data traffic presents a more accuratereflection of realistic operating scenarios than would be presentedif only control traffic were present.8.2.2. timerssettings of delay and hold-down timers at the link level, as well asfor bgp4, can introduce or ameliorate delays. as part of a testreport, all relevant timers must be reported if they use non-defaultvalues.8.2.3. tcp parameters underlying bgp transportbecause all bgp traffic and interactions occur over tcp, all relevantparameters characterizing the tcp sessions must be provided; e.g.,slow start, max window size, maximum segment size, or timers.8.2.4. authenticationauthentication in bgp is currently done using the tcp md5 signatureoption . the processing of the md5 hash, particularly indevices with a large number of bgp peers and a large amount of updatetraffic, can have an impact on the control plane of the device.9. security considerationsthe document explicitly considers authentication as a performance-affecting feature, but does not consider the overall security of therouting system.10. acknowledgementsthanks to francis ovenden for review and abha ahuja forencouragement. much appreciation to jeff haas, matt richardson, andshane wright at nexthop for comments and input. debby stopp and nickambrose contributed the concept of route packing.alvaro retana was a key member of the team that developed thisdocument, and made significant technical contributions regardingroute mixes. the team thanks him and regards him as a co-author inspirit.11. references11.1. normative references rekhter, y. and t. li, a border gateway protocol 4(bgp-4), rfc 1771, march 1995. villamizar, c., chandra, r., and r. govindan, bgp routeflap damping, rfc 2439, november 1998. baker, f., requirements for ip version 4 routers, rfc1812, june 1995. ahuja, a., jahanian, f., bose, a., and c. labovitz, anexperimental study of delayed internet routingconvergence, ripe-37 presentation to routing wg,november 2000,. labovitz, c., malan, g., and f. jahanian, origins ofinternet routing instability, infocom 99, august 1999. alaettinoglu, c., bates, t., gerich, e., karrenberg, d.,meyer, d., terpstra, m., and c. villamizar, routingpolicy specification language (rpsl), rfc 2280, january1998. panigl, c., schmitz, j., smith, p., and c. vistoli,ripe routing-wg recommendation for coordinated route-flap damping parameters, version 2, ripe 229, october2001. heffernan, a., protection of bgp sessions via the tcpmd5 signature option, rfc 2385, august 1998. juniper networks, junos(tm) internet softwareconfiguration guide routing and routing protocols,release 4.2, junos 4.2 and other releases, september2000,. rosen, e. and y. rekhter, bgp/mpls vpns, rfc 2547,march 1999. jain, r. and s. routhier, packet trains -- measurementand a new model for computer network traffic, ieeejournal on selected areas in communication 4(6),september 1986.11.2. informative references chen, e., route refresh capability for bgp-4, rfc2918, september 2000. sangli, s., rekhter, y., fernando, r., scudder, j., ande. chen, graceful restart mechanism for bgp, work inprogress, june 2004. chen, e. and y. rekhter, cooperative route filteringcapability for bgp-4, work in progress, march 2004. khosravi, h. and t. anderson, requirements forseparation of ip control and forwarding, rfc 3654,november 2003. mcpherson, d., gill, v., walton, d., and a. retana,border gateway protocol (bgp) persistent routeoscillation condition, rfc 3345, august 2002. bates, t., rekhter, y., chandra, r., and d. katz,multiprotocol extensions for bgp-4, rfc 2858, june2000. marques, p. and f. dupont, use of bgp-4 multiprotocolextensions for ipv6 inter-domain routing, rfc 2545,march 1999.authors' addresseshoward berkowitzgett communications & cci training5012 s. 25th starlington, va 22206usaphone: +1 703 998-5819fax: +1 703 998-5058email: hcb@gettcomm.comelwyn b. daviesfolly consultingthe follysohamcambs, cb7 5awukphone: +44 7889 488 335email: elwynd@dial.pipex.comsusan haresnexthop technologies825 victors wayann arbor, mi 48108usaphone: +1 734 222-1610email: skh@nexthop.compadma krishnaswamysaic331 newman springs roadred bank, new jersey 07701usaemail: padma.krishnaswamy@saic.commarianne leppconsultantemail: mlepp@lepp.comfull copyright statementcopyright (c) the internet society (2005).this document is subject to the rights, licenses and restrictionscontained in bcp 78, and except as set forth therein, the authorsretain all their rights.this document and the information contained herein are provided on anas is basis and the contributor, the organization he/she representsor is sponsored by (if any), the internet society and the internetengineering task force disclaim all warranties, express or implied,including but not limited to any warranty that the use of theinformation herein will not infringe any rights or any impliedwarranties of merchantability or fitness for a particular purpose.intellectual propertythe ietf takes no position regarding the validity or scope of anyintellectual property rights or other rights that might be claimed topertain to the implementation or use of the technology described inthis document or the extent to which any license under such rightsmight or might not be available; nor does it represent that it hasmade any independent effort to identify any such rights. informationon the procedures with respect to rights in rfc documents can befound in bcp 78 and bcp 79.copies of ipr disclosures made to the ietf secretariat and anyassurances of licenses to be made available, or the result of anattempt made to obtain a general license or permission for the use ofsuch proprietary rights by implementers or users of thisspecification can be obtained from the ietf on-line ipr repository athttp://www.ietf.org/ipr.the ietf invites any interested party to bring to its attention anycopyrights, patents or patent applications, or other proprietaryrights that may cover technology that may be required to implementthis standard. please address the information to the ietf at ietf-ipr@ietf.org.acknowledgementfunding for the rfc editor function is currently provided by theinternet society.</t