Benchmarking Terminology Working Group		        H.Berkowitz              H.Berkowitz, Gett Communications
Internet Draft
draft-ietf-bmwg-conterm-00.txt				A.Retana                                         S.Hares, Next Hop
Document: draft-ietf-bmwg-conterm-01.txt                 A.Retana, Cisco
Expires August 2002                           P.Krishnaswamy, Consultant
                                                M.Lepp, Juniper Networks
                                               E.Davies, Nortel Networks
February 2002

                                                         July 2001

                      Terminology for Benchmarking
               External Routing Convergence Measurements

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.
   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted 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
   The list of Internet-Draft Shadow Directories can be accessed at

   A revised version of this draft document will be submitted to the RFC
   editor as a Informational document for the Internet Community.
   Discussion and suggestions for improvement are requested.
   This document will expire before August 2002. Distribution of this
   draft is unlimited.


   This draft establishes terminology to standardize the description of
   benchmarking methodology for measuring eBGP convergence in the
   control plane of a single router. BGP device. Future documents will address
   iBGP convergence, the initiation of forwarding based on converged
   control plane information and internet-wide convergence.

Conventions used in this document

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   document are to be interpreted as described in RFC-2119 [2].

 Berkowitz, et al                                                     1
   Table of Contents
1	Introduction							3
   1. Introduction....................................................3
      1.1  Overview and Roadmap						3 Roadmap.......................................3
      1.2  Definition Format						4
2 Format..........................................3
   2. Constituent elements of a router or network  of routers.	5 routers.........4
      2.1  BGP Peer							5 Peer...................................................4
      2.2  Default Route, Default Free Table, and Full Table		5
2.2.1	Default Route
	6			2.2.2	Default Free Routing Table
2.2.3	Full Default Free Table						7
2.2.4	Full Provider Internal Table					7 Table..........5
      2.3  Classes of BGP-Speaking Routers					8
2.3.1	Provider Edge Router						8
2.3.2	Subscriber Edge Router						8
2.3.3	Interprovider Border Router					9
2.3.4	Intraprovider Core Router					9
3 Routers............................7
   3. Routing Data Structures						9 Structures.........................................9
      3.1  Routing Information Base (RIB)					9
3.1.1	Adj-RIB-In and Adj-RIB-Out					10
3.1.2	Loc-RIB								10 (RIB).............................9
      3.2	Policy								11  Policy....................................................10
      3.3  Policy Information Base						11 Base...................................11
      3.4  The Forwarding Information Base (FIB)				12
4 (FIB).....................12
   4. Components and characteristics of Routing information		13 information..........12
      4.1	Prefix								13  Prefix....................................................12
      4.2	Route								13  Route.....................................................13
      4.3  BGP Route							14 Route.................................................13
      4.4  Route Instance							14 Instance............................................14
      4.5  Active Route							15 Route..............................................14
      4.6  Unique Route							15 Route..............................................14
      4.7  Non-Unique Route						15 Route..........................................15
      4.8  Route Packing							16 Packing.............................................15
      4.9	Update Train							16  Route Mixture.............................................15
      4.10    Update Train...........................................16
      4.11    Route Flap							16
5 Flap.............................................18
   5. Route Changes and Convergence					17 Convergence..................................18
      5.1  Route Change Events						17 Events.......................................18
      5.2	Convergence							18
6  Convergence...............................................19
   6. BGP Operation Events...........................................20
      6.1  Hard reset................................................20
      6.2  Soft reset................................................21
   7. Factors that impact the performance of the convergence process	19
6.1 process.21
      7.1  General factors affecting BGP convergence			19
6.1.1	Number of peers							19
6.1.2	Number of routes per peer					20
6.1.3	Policy processing/reconfiguration				20
6.1.4	Interactions with other protocols.				20
6.1.5	Flap Damping							20
6.1.6	Churn								21
6.2 convergence.................21
      7.2  Implementation-specific and other factors affecting BGP
	convergence							21
6.2.1	Forwarded  traffic						21
6.2.2	Timers								22
6.2.3	TCP parameters underlying BGP transport				22
6.2.4	Authentication							22
   8. Security Considerations						22
8	References							22
9	Acknowledgments							22
10 Considerations........................................23
   9. References.....................................................24
   10. Acknowledgments...............................................25
   11. Author's Addresses						23

1 Addresses............................................25

Berkowitz, et al            Expires: August 2002                      2

1. Introduction

   This document defines terminology for use in characterizing the
   convergence performance of BGP processes in routers or other devices
   that instantiate BGP functionality. It is the first part of a two
   document series, of which the subsequent document will contain the
   associated tests and methodology.

   The following observations underly underlie the approach adopted in this, and
   the companion document:

   -  The principal objective is to derive methodologies to standardize
      conducting and reporting convergence-related measurements for BGP.
   -  It is necessary to remove ambiguity from many frequently used
      terms that arise in the context of such measurements.
   -  As convergence characterization is a complex process, it is
      desirable to restrict the initial focus in this set of documents
      to specifying how to take basic control plane measurements towards as a
      first step to characterizing BGP convergence.

   For path vector protocols such as BGP, the primary initial focus will
   therefore be on network and system control-plane activity consisting
   of the arrival, processing, and propagation of routing information
   Subsequent drafts will explore the more intricate aspects of
   convergence measurement, such as the impacts of the presence of
   policy processing, simultaneous traffic on the control and data paths
   within the DUT, and other realistic performance modifiers.
   Convergence of Interior Gateway Protocols will also be considered in
   separate drafts.

1.1 Overview and Roadmap

A characterization

   Characterizations of the BGP convergence performance of a device must
   take into account all distinct stages and aspects of BGP
   functionality. This requires that the relevant terms and metrics be
   as specifically defined as possible. Such definition is the goal of
   this document.

   The necessary definitions are classified into two separate
   -  Descriptions of the constituent elements of a network or a router
      that is undergoing convergence
   -  Descriptions of factors that impact convergence processes

1.2 Definition Format

   The definition format is equivalent to that defined in [RFC1812], [5], and is
   repeated here for convenience:

   X.x Term to be defined. (e.g., Latency)

              The specific definition for the term. term being defined.

Berkowitz, et al            Expires: August 2002                      3
              A brief discussion about of the term, its application and any
              restrictions that there might be on measurement

   Measurement units:
              The units used to report measurements of this term, if
              List of issues or conditions that could affect this term.

   See Also:
              List of other related terms that are relevant to the definition
              or discussion of this term.


2. Constituent elements of a router or network  of routers.

   Many terms included in this list of definitions were described originally
   described 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 over

2.1 BGP Peer

              A BGP peer is another BGP instance to which the the Device
              Under Test (DUT) has established a TCP connection over
              which a BGP session is active.  In the test scenarios in
              the methodology discussion that will follow this draft,
              peers send BGP advertisements to the DUT and receive
DUT-originated DUT-
              originated advertisements.

              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.

              It is worth noting that a BGP peer, by this definition is
              associated with a BGP peering session, and there may be
              more than one such active session on a router or on a
              tester.  The peering sessions referred to here may exist
              between various classes of BGP routers (see section 2.3)
. 2.3).

   Measurement units: number of BGP peers


   See Also:

Berkowitz, et al            Expires: August 2002                      4

2.2 Default Route, Default Free Table, and Full Table

   An individual router's routing table may not necessarily contain a
   default route.  Not having a default route, however, is not
   synonymous with having a full default-free table. table(DFT).
   It should be noted that the references to number of routes in this
   section are to routes installed in the loc-RIB, not route instances,
   and that the total number of route instances may be 4 to 10 times the
   number of routes.

   The actual path setup and forwarding of MPLS speaking routers are
   outside the scope of this document document.  A device that computes BGP
   routes that may give a sub-IP device information that it uses to set
   up paths, however, has its BGP aspects within scope.

2.2.1 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, provided its
              Forwarding Table (Forwarding Information Base (FIB) )
              contains one. The notation for a default route is


   Measurement units: N.A.


   See Also: default free routing table, route, route instance

Berkowitz, et al            Expires: August 2002                      5

2.2.2 Default Free Routing Table

              A routing table with no default routes, as typically seen
              in routers at in the core or top tier. tier of routers in the

              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 Thus they will
              forward every prefix to a specific nexthop next hop based on the
              longest match on the IP addresses.

              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 router's AS.

   Measurements: The number of routes

   See Also: Full Default Free Free, Default Route

2.2.3 Full Default Free Table

              A set of BGP routes generally accepted to be the complete
              set of BGP routes collectively announced by all the complete
              set of autonomous systems to making up the public Internet.
              Due to the dynamic nature of the Internet, the exact size
              and composition of this table may vary slightly depending
              where and when it is observed.
              Several investigators [Bates, Smith] ([12],[13][14]) measure this on a
              daily and/or weekly basis; June 2001 measurements put the
              table at approximately 105,000 routes, growing

              It is generally accepted that a full table, in this usage,
              does not contain the infrastructure routes or individual subaggregates
              sub-aggregates of routes that are otherwise aggregated by
              the provider before announcement to other autonomous

   Measurement Units: number of routes


   See Also: Routes, Route Instances, Default Route

Berkowitz, et al            Expires: August 2002                      6

2.2.4 Full Provider Internal Table

              A superset of the full routing table that contains
              infrastructure and non-aggregated routes.

              Experience has shown that this table can contain 1.3 to
              1.5 times the number of routes in the externally visible
              full table.  Tables of this size, therefore, are a real-world real-
              world requirement for key internal provider routers.

   Measurement Units: number of routes


   See Also: Routes, Route Instances, Default Route

2.3 Classes of BGP-Speaking Routers

   A given router may perform more than one of the following functions,
   based on its logical location in the network.

2.3.1 Provider Edge Router

              A router at the edge of a provider's network, configured
              to speak BGP, which peers with a BGP speaking router
              operated by the end-user. The traffic that transits this
              router may be destined to, or originate from
              non-contiguous autonomous systems.

              Such a router will always speak eBGP and may speak iBGP.

   Measurement units:


   See Also:

Berkowitz, et al            Expires: August 2002                      7

2.3.2 Subscriber Edge Router

              A BGP-speaking router belonging to an end user
              organization that may be multi-homed, which carries
              traffic only to and from that end user AS.

              Such a router will always speak eBGP and may speak iBGP.

   Measurement units:


   See Also:

2.3.3 Interprovider Border Router

              A BGP speaking router that which maintains BGP sessions with
              another BGP speaking router in another provider AS.
              Traffic transiting this router may be directed to or from
              another AS that has no direct connectivity with this
              provider's AS.

              Such a router will always speak eBGP and may speak iBGP.

   Measurement units:


   See Also:

2.3.4 Intraprovider Core Router

              A provider router speaking iBGP to the provider's edge
              routers, other intraprovider core routers, or the
              provider's interprovider border routers.

              Such a router will always speak iBGP and may speak eBGP.

   Measurement units:

              MPLS speaking routers are outside the scope of this
              document.  It is entirely likely, however, that core Label
              Switched Routers, especially in the P router role of
              RFC 2547, 2547 [16], may contain little or no BGP information.

   See Also:

Berkowitz, et al            Expires: August 2002                      8

3. Routing Data Structures

3.1 Routing Information Base (RIB)

   The RIB collectively consists of a set of logically (not necessarily
   literally) distinct databases, each of which is enumerated below. The
   RIB contains all destination prefixes to which the router may
   forward, and one or more currently reachable next hop addresses for

   Routes included in this set potentially have been selected from
   several sources of information,including information, including hardware status, interior
   routing protocols, and exterior routing protocols. RFC 1812 contains
   a basic set of route selection criteria relevant in an all-source
   context. Many implementations impose additional criteria.  A common implementation-
   implementation-specific criterion is the preference given to
   different routing information sources.

3.1.1 Adj-RIB-In and Adj-RIB-Out

              Adj-RIB-In and Adj-RIB-Out are "views" of routing
              information from the perspective of individual peer

              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.

              See RFC 1771 1771[3].



   Measurement Units: Number of route instances

   See Also: Route, BGP Route, Route Instance, Loc-RIB, FIB

Berkowitz, et al            Expires: August 2002                      9

3.1.2 Loc-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.

              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

              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, static and IGP routes.

   Measurement Units: Number of route instances.

   See Also:  Route, BGP Route, Route Instance, Adj-RIB-in, Adj-RIB-out,

3.2 Policy

              Policy is "the ability to define conditions for accepting,
              rejecting, and modifying routes received in advertisements"[16]

              RFC 1771 [RFC1771] [3] further constrains policy to be within the
              hop-by-hop routing paradigm. Policy is implemented using
              filters and associated policy actions.  Many AS's use
              routing Policy Specification Language (RPSL) [8] to
              document their policies and automatically generate
              configurations for the BGP processes in their routers.

   Measurement Units:


   See Also: Policy Information Base.

Berkowitz, et al            Expires: August 2002                      10

3.3 Policy Information Base

              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 [RFC1771] [3] definition of
              these phases.

              Incoming policies are applied in Phase 1 of the BGP
              selection process [RFC1771]to [3] 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 preceding route (prefix and path
              attribute tuple) announcements to a specific peer.

              Policies in the Policy Information Base have matching and
              action conditions.  Common information to match include
              route prefixes, AS paths, communities, etc.  The action on
              match may be to drop the update and not pass it to the
              Loc-RIB, or to modify the update in some way, such as
              changing local preference (on input) or MED (on output),
              adding or deleting communities, prepending the current AS
              in the AS path, etc.

              The amount of policy processing (both in terms of route
              maps and filter/access lists) will impact the convergence
              time and properties of the distributed 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.

   Measurement Units:


   See Also:

Berkowitz, et al            Expires: August 2002                      11

3.4 The Forwarding Information Base (FIB)

              The Forwarding Information Base is generated from the RIB.
              The FIB is referred to in [RFC1771] [3] as well as [RFC1812] [5] but not
              defined in either. For the purposes of this document, the
              FIB is the subset of the RIB used by the forwarding plane
              to make per-packet forwarding decisions.

              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

   Measurement Units: N.A.


   See Also: Route, RIB


4. Components and characteristics of Routing information

4.1 Prefix

              A destination address specified in CIDR format. Expressed
              as prefix/length. The definition in [RFC1812] [5] 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."

              A prefix is expressed as a portion of an IP address
              followed by the associated mask such as 10/8.

   Measurement Units: N.A.


   See Also

Berkowitz, et al            Expires: August 2002                      12

4.2 Route

              In general, a 'route' is the n-tuple
              <prefix, nexthop [,other non-
routing nexthop[, other non-routing protocol attributes] >. attributes]>
              A route is not end-to-end, but is defined with respect to
              a specific next hop that will move traffic closer to the
              destination defined by the prefix. In this usage, a route
              is the basic unit of information about a target
              destination distilled from routing protocols.

              This term refers to the concept of a route common to all
              routing protocols. With reference to the definition above,
              typical non-routing-protocol attributes would be
              associated with diffserv or traffic engineering.

   Measurement Units: N.A.

   Issues: None.

   See Also: BGP route

4.3 BGP Route

              The n-tuple
              <prefix, nexthop, aspath [, other BGP attributes]>.

              Nexthop is one type of attribute.  Attributes are defined
              in RFC 1771
[RFC1771], 1771[3], and are the  qualifying data that
              accompanies a prefix in a BGP route. From RFC 1771: " 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
              <attribute type, attribute length, attribute value>
              of variable length."

   Measurement Units:N.A. Units: N.A.


   See Also: Route, prefix, Adj-RIB-in.

Berkowitz, et al            Expires: August 2002                      13

4.4 Route Instance

              A single occurrence of a route sent by a BGP Peer for a
              particular prefix. 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 route instance is associated with a specific peer. A
              specific route instance may be rejected by the BGP
              selection algorithm due to local policy.

   Measurement Units: number of route instances

              The number of route instances in the Adj-RIB-in bases will
              vary based on the function to be performed by a router. An interprovider
              inter-provider router, located in the default free zone
              will likely receive more route instances than an a provider
              edge router, located closer to the end-users of the

   See Also:

4.5 Active Route

              Route for which there is a FIB entry corresponding to a
              RIB entry.


   Measurement Units:


   See also: RIB.

4.6 Unique Route

D efinition:

              A unique route is a prefix for which there is just one
              route instance across all Adj-Ribs-In.


   Measurement Units: N.A.


   See Also: route, route instance

Berkowitz, et al            Expires: August 2002                      14

4.7 Non-Unique Route

              A Non-unique route is a prefix for which there is at least
              one other route in a set including more than one Adj-RIB-in. Adj-RIB-


   Measurement Units: N.A.


   See Also: route, route instance, unique active route.

4.8 Route Packing

              Number of route prefixes that exist in a single Routing
              Protocol Update UPDATE Message either as updates (additions or
              modifications) or Withdraw Message. withdrawals.

              In general, a routing protocol update MAY contain more
              than one prefix.  In BGP, a single  update UPDATE MAY contain
              multiple prefixes with identical attributes. Protocols
              that do not support such a concept implicitly have a Route
              Packing of 1. "

   Measurement Units: N.A.


   See Also: route, route instance, update train.

4.9	Update Train Route Mixture

              A set characterization of updates, containing one or more the routes in a collection of
              routes.  Two profiles are used to characterize a
              collection of routes as a route prefixes, mixture:
              -  The distribution of prefix lengths in the collection
              -  The clustering of prefixes around particular branches
                 the tree which an
external router desires can be used to send represent the totality
                 of possible prefixes.

              Route mixtures are used to simulate the DUT.  When there is more than one normal pattern of
              prefix distribution that is seen in the set, the multiple updates (including withdrawals) may real world route
              tables and update trains.  As can be seen in the analyses
              of BGP tables and traffic (e.g. [12], [13] and [14]), the
              characterizations of the tables in the routers and the
              network traffic appear to be different which has to be

Berkowitz, et al            Expires: August 2002                      15
              taken into account in designing test stimuli appropriate
              for particular types of testing.

   Measurement Units:
              Length profile:     Probability distribution function on
                                  possible discrete values of prefix
                                  length (i.e 0-32 for IPv4)
              Clustering profile: Probability distribution function on
                                  'distance' between successive prefixes
                                  which is a function of the prefix
                                  lengths and the separation of the
                                  branches of the address tree on which
                                  they lie (FFS)


   See Also:

4.10 Update Train

              A set of Routing Protocol UPDATE messages, containing one
              or more route prefixes, which an external router desires
              to send to the DUT.  When there is more than one prefix in
              the set, the multiple updates (including withdrawals) may
              be sent as individual BGP UPDATE packets, or as one or
              more BGP packets with multiple routes packed (q.v.) into
              them.  If multiple UPDATE packets make up a train, the
              time spacing of the packets needs to be specified.

              The more individual update UPDATE packets that are sent, the more
              TCP and BGP header processing will be imposed on the
              receiving router that is the DUT. An update train may be
              caused by a variety of network conditions.  For example,
              an update train could be caused by an influx of UPDATES
              from different peers that have been received and moved to
              RIB-out or caused by a peer coming up and advertising its
              routes, or by a local or remote peer flapping a link.
              Other causes are, of course, possible.

              The time intervals between the UPDATE packets in a train
              may vary from essentially zero when the packets follow
              each other as closely as possible up to a situation where
              the time between packets exceeds MIN_ADVERT_TIME.  Once
              the packets are so widely spaced in time they can be
              treated separately as single packet update trains since
              the router will be guaranteed to have propagated any
              adverts resulting from the previous UPDATE when the next
              one arrives (a slightly sweeping statement, but if adverts
              are arriving singly it would be a very inefficient router
              that was unable to keep up!)

   Measurement units:

Berkowitz, et al            Expires: August 2002                      16
              Number of prefixes and update UPDATE packets in the train,
              time spacing between packets in train


   See Also:

4.10.1 Random Update Train

              An Update Train which contains:
              -  A random number of prefixes, selected according to
              -  A random distribution from the possible updates and
                 withdrawals (depending on what routes are currently
                 installed in the route under test), distributed across
              -  A random number of UPDATE packets as both updates and
                 withdraws, in
              -  A random order which does not favor any of the
                 well-known algorithms used to manage the route
                 databases in BGP process, and specified for
              -  A random distribution of time spacings between
                 deliveries taken from the interval
                 [0, MIN_ADVERT_TIME].

              This is intended to simulate the unpredictable
              asynchronous nature of the network, whereby UPDATE packets
              may have arbitrary contents and be delivered at random
              times.  A fully random update train can be considered to
              be a worst case in some senses and should stress parts of
              the software: It may be desirable to test a router with
              less random cases, such as a not quite random update train
              in which everything is random except that the UPDATES are
              delivered as closely spaced as possible in time.

              The distribution used to control the selection of prefixes
              is a 'route mixture' (q.v.)
              When a router is used in a network of routers all from the
              same vendor, the distribution of prefixes emitted from a
              BGP router may well be structured in a way which
              particularly suits the internal organization of the routes
              in the databases.  It may be useful to test routers with
              update trains organized in this way as a closer emulation
              of the train. real world.  One might expect that the input of a
              vendor's router would be best suited to the ordering
              emitted by a similar router.

   Measurement Units: See Update Train


   See Also:
4.10 also:

Berkowitz, et al            Expires: August 2002                      17

4.11 Route Flap

              RIPE 210 [RIPE]define [9] define a route flap as "the announcement and
              withdrawal of prefixes."  For our purposes we define a
              route flap as the rapid withdrawal/announcement or announcement/withdrawal/
              announcement/withdrawal of a prefix in the Adj-RIB-in. A
              route flap is not a problem until a route is flapped
              several times in close succession. This causes negative
              repercussions throughout the internet.

              Route flapping can be considered a special and
              pathological case of update trains. A practical
              interpretation of what may be considered excessively rapid
              is the RIPE recommendation of "four flaps in a row". See
              Section 6.1.5 on flap damping for further discussion.

   Measurement units units: Flapping events per unit time.

              Specific Flap events can be found in Section 5.1Route
              Change Events.  A bench-marker should use a mixture of
              different route change events in testing.

   See Also: Route change events, flap damping, packet train


5. Route Changes and Convergence

   The following two definitions are central to  the benchmarking of
   external routing convergence, and so are singled out for more
   extensive discussion.

5.1 Route Change Events

   A taxonomy characterizing routing information changes seen in
   operational networks is proposed in [Ahuja et al] [6] as well as Labovitz et al[4]. al[7].
   These papers describe BGP protocol-centric events, and event
   sequences in the course of an analysis of  network behavior. The
   terminology in the two papers addresses categorizes similar but slightly
   different behaviors with some overlap. We would like to apply these
   taxonomies to categorize the tests under definition where possible,
   because these tests must tie in to phenomena that arise in actual
   networks. We avail ourselves of, or may extend, this terminology as
   necessary for this purpose.

   A route can be changed implicitly by replacing it with another route
   or explicitly by withdrawal followed by the introduction of a new
   route. In either case the change may be an actual change, no change,
   or a duplicate. The notation and definition of individual
   categorizable route change events is adopted from [Labovitz et al] [7] and given

Berkowitz, et al            Expires: August 2002                      18
   a) AADiff: Implicit withdrawal of a route and replacement by a route
      different in some path attribute.
   b) AADup: Implicit withdrawal of a route and replacement by route
      that is identical in all path attributes.
   c) WADiff: Explicit withdrawal of a route and replacement by a
      different route.
   d) WADup: Explicit withdrawal of a route and replacement by a route
      that is identical in all path attributes.

   To apply this taxonomy in the benchmarking context, we need both
   terms to describe the sequence of events from the update train
   perspective, as listed above, as well as event indications in the
   time domain so as to be able to measure activity  from the
   perspective of the DUT. With this in mind, we incorporate and extend
   the definitions of [4] [7] to the following:

   a) Tup (TRx): (TDx): Route advertised to the DUT by Test Router Device x
   b)	Tdown: Tdown(TDx): Route being withdrawn by Device x
   c)	Tupinit: Tupinit(TDx): The initial announcement of a route to a unique
   d)	TWF: TWF(TDx): Route fail over after an explicit withdrawal.

   But we need to take this a step further. Each of these events can
   involve a single route, a "short" packet train, or a "full" routing
   table. We further extend the notation to indicate how many routes are
   conveyed by the events above:

   a) Tup(1,TDx) means Device x sends 1 route
   b) Tup(S,TDx) means Device x sends a train, S, of routes
   c) Tup(DFT,TDx) means Device x sends an approximation of a full
      default-free table.

   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 following descriptor events.
   	a)Tbest events, which are routes
   selected by the BGP selection process rather than simple updates:

   a) Tbest   -- The current best path.
   b) Tbetter -- Advertise a path that is better than Tbest.
   c) Tworse  -- Advertise a path that is worse than Tbest.

5.2 Convergence

              A router is said to have converged onto a route advertised
              to it, given that the 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.

Berkowitz, et al            Expires: August 2002                      19
              The convergence process can be subdivided into three
              distinct phases:

              -  convergence across the entire Internet,
              -  convergence within an Autonomous System,
              -  convergence with respect to a single router.

              Convergence with respect to a single router can be
              -  convergence with regard to the routing process(es), the
                 focus of this document
              -  convergence with regard to data forwarding process(es).

              It is of key importance key importance to benchmark the performance of
              each phase of convergence separately before proceeding to
              a composite characterization of routing convergence, where
              implementation- specific dependencies are allowed to

              The preferred route instance must be unambiguous during
              test setup/definition.

   Measurement Units: N.A.


   See Also:

6. BGP Operation Events

   The BGP speaker process(es) in a router restart completely, for
   example, because of operator intervention or a power failure, or a
   partially because a TCP session has terminated for a particular link.
   Until recently the BGP process would have to readvertise all relevant
   routes on reestablished links potentially triggering updates across
   the network.  Recent work is focused on limiting the volume of
   updates generated by short term outages by providing a graceful
   restart mechanism [17].

6.1 Hard reset

              An event which triggers a complete reinitialization of the
              routing tables on one or more BGP sessions, resulting in
              exchange of a large number of UPDATEs on one or more links
              to benchmark the
    performance router.


   Measurement Units: N/A


   See Also:

Berkowitz, et al            Expires: August 2002                      20

6.2 Soft reset

              An event which results in a complete or partial restart of each phase
              the BGP session(s) on a router, but which avoids the
              exchange of convergence separately before proceeding
to a composite
    characterization large number of routing convergence, where implementation-
specific dependencies are
    allowed to interact.

    The preferred route
    instance must be unambiguous during test
    setup/definition. UPDATEs by maintaining state
              across the restart.


   Measurement Units: N.A. N/A


   See Also:


7. Factors that impact the performance of the convergence process

   While this is not a complete list, all of the items discussed below
   have a significant affect on BGP convergence.  Not all of them can be
   addressed in the baseline measurements described in this document.


7.1 General factors affecting BGP convergence

   These factors are conditions of testing external to the router Device
   Under Test (DUT).


7.1.1 Number of peers

   As the number of peers increases, the BGP route selection algorithm
   is increasingly exercised. In addition, the phasing and frequency of
   updates from the various peers will have an increasingly marked
   effect on the convergence process on a router as the number of peers


7.1.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, as will the mix of
   overlapping route instances, and IGP routes.


7.1.3 Policy processing/reconfiguration

   The number of routes and attributes being filtered, and set, as a
   fraction of the target route table size is another parameter that
   will affect BGP convergence.

   Extreme examples are

   -  Minimal Policy: receive all, send all,
   -  Extensive policy: up to 100% of the total routes have applicable


Berkowitz, et al            Expires: August 2002                      21

7.1.4 Interactions with other protocols.

   There are interactions in the form of precedence, synchronization,
   duplication and the addition of timers, and route selection criteria.
   Ultimately, understanding BGP4 convergence must include understanding
   of the interactions with both the IGPs and the protocols associated
   with the physical media, such as Ethernet, SONET, DWDM.

7.1.5 Flap Damping

   A router can use flap damping to  respond to route flapping.   Use of
   flap damping is not mandatory, so the decision to enable the feature,
   and to change parameters associated with it, can be considered a
   matter of routing policy.

   The timers are defined by RFC 2439 [RFC 2439] [4] and discussed in RIPE 210
[17]. RIPE-210 [9].
   If this feature is in effect, it requires that the router keep
   additional state to carry out the damping, which can have a direct
   impact on the control plane due to increased processing.  In
   addition, flap damping may delay the arrival of real changes in a
   route, and affect convergence times


7.1.6 Churn

   In theory, a BGP router could receive a set of updates that
   completely defined the Internet, and could remain in a steady state,
   only sending appropriate KeepAlives.  In practice, the Internet will
   always be changing.

   Churn refers to control plane processor activity caused by
   announcements received and sent by the router.  It does not include

   Churn is caused by both normal and pathological events.  For example,
   if an interface of the local router goes down and the associated
   prefix is withdrawn, that withdrawal is a normal activity, although
   it contributes to churn.  If the local router receives a withdrawal
   of a route it already advertises, or an announcement of a route it
   did not previously know, and readvertises this information, again
   these are normal constituents of churn. Routine updates can range
   from single announcement or withdrawals, to announcements of an
   entire default-free table.  The latter is completely reasonable as an
   initialization condition.

   Flapping routes are a pathological contributor to churn, as is MED
   oscillation [medosc]. [11].  The goal of flap damping is to reduce the
   contribution of flapping to churn.

   The effect of churn on overall convergence depends on the processing
   power available to the control plane, and whether the same
   processor(s) are used for forwarding and for control.


7.2 Implementation-specific and other factors affecting BGP convergence

Berkowitz, et al            Expires: August 2002                      22
   These factors are conditions of testing internal to the router Device
   Under Test (DUT), although they may affect its interactions with test


7.2.1 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
   control traffic (FIB updates and downloads as a consequence of
   flaps)are excessive. The addition of data traffic presents a more
   accurate reflection of realistic operating scenarios than if only
   control traffic is present

6.2.2 present.

7.2.2 Timers

   Settings of delay and hold-down timers at the link level as well as
   for BGP4, can introduce or ameliorate delays.  As part of a test
   report, all relevant timers should be reported if they use non-default non-
   default value.  Also, any variation in standard behavior, such as
   overriding TCP slow start, should be documented.


7.2.3 TCP parameters underlying BGP transport

   Since all BGP traffic and interactions occur over TCP, all relevant
   parameters characterizing the TCP sessions should be provided: eg Max
   window size, Maximum segment size, timers.


7.2.4 Authentication

   Authentication in BGP is currently done using the TCP MD5 Signature
   Option [Heff]. [10].  The processing of the MD5 hash, particularly in routers
   with a large number of BGP peers and a large amount of update traffic
   can have an impact on the control plane of the router.

8. Security Considerations

   The document explicitly considers authentication as a performance-
   affecting feature, but does not consider the overall security of the
   routing system.


Berkowitz, et al            Expires: August 2002                      23

9. References

1. [RFC 2026]Bradner,

     [1]            Bradner, S., "The Internet Standards Process --
                    Revision 3", BCP 9, RFC 2026, October 1996

2. [RFC 2119]Bradner,

     [2]            Bradner, S., "Key words for use in RFCs to
                    Indicate Requirement Levels", BCP 14, RFC 2119,
                    March 1997

3. [RFC 1771]"A

     [3]            Rekhter, Y. and Li, T., "A Border Gateway
                    Protocol 4 (BGP-4)", RFC 1771,  Y.
              Rekhter, T. Li. . March 1995.

4. [RFC 2539]""BGP

     [4]            Villamizar, C., Chandra, R. and Govindan, R.,
                    "BGP Route Flap Damping", RFC 2439, C. Villamizar, R.
              Chandra, R. Govindan.
                    November 1998."

5. [RFC 1812]"Requirements

     [5]            Baker, F.,"Requirements for IP Version 4
                    Routers", RFC 1812, F.
              Baker. 1812. June 1995.

6.  [Ahuja et al]"An

     [6]            Ahuja, A., Jahanian, F., Bose, A. and Labovitz,
                    "An Experimental Study of Delayed Internet
              Convergence." Abha Ahuja, Farnam Jahanian, Abhijit Bose,
              Craig Labovitz, Convergence", RIPE 37 - Routing WG.
7. [Labovitz et al]

     [7]            Labovitz, C., Malan, G.R. and Jahanian, F.,
                    "Origins of Internet Routing Instability,"
                    Infocom 99
              Craig Labovitz, G. Robert Malan, Farnam Jahanian],

8.[RPSL] Routing Policy Specification Language (RPSL), RFC 2622, "
              C.Alaettinoglu, C. 99,

     [8]            Alaettinoglu, C., Villamizar, E. C., Gerich, D. E.,
                    Kessens, D. D.,  Meyer, T.Bates, D. D., Bates, T., Karrenberg, M. Terpstra.
                    D. and Terpstra, M., "Routing Policy
                    Specification Language (RPSL)", RFC 2622, June

9.[RIPE]RIPE 210,

     [9]            Barber, T., Doran, S., Karrenberg, D., Panigl,
                    C., Schmitz, J., "RIPE Routing-WG Recommendation
                    for coordinated route-flap damping parameters, Tony Barber, Sean Doran,
              Daniel Karrenberg, Christian Panigl, Joachim Schmitz
10.[Heff]"Protection parameters",
                    RIPE 210,

     [10]           Heffernan, A., "Protection of BGP Sessions via
                    the TCP MD5 Signature Option", RFC 2385, A. Heffernan. August

11. [medosc]<draft-ietf-idr-route-oscillation-00.txt>, BGP

     [11]           McPhersonm, Gill, Walton, Retana,  "BGP
                    Persistent Route Oscillation Condition,McPhersonm, Gill, Walton, Retana

9	Acknowledgments Condition", <draft-
                    ietf-idr-route-oscillation-00.txt>, Work In

     [12]           Bates, T., "The CIDR Report",
                    Internet statistics relevant to inter-domain
                    routing updated daily

Berkowitz, et al            Expires: August 2002                      24
     [13]           Smith, P. (designer), APNIC Routing Table
                    Statistics derived from a daily analysis of a
                    core router in Japan

     [14]           Huston, G., Telstra BGP table statistics,
                    Statistics derived daily from the BGP tables of
                    Telstra and other AS's routers

     [15]           Juniper Networks,"Junos(tm) Internet Software
                    Configuration Guide Routing and Routing
                    Protocols, Release 4.2"
                    September 2000 (and other releases).

     [16]           Rosen, E. and Rekhter, Y., "BGP/MPLS VPNs", RFC
                    2547, March 1999

     [17]           Ramachandra, S., Rekhter, Y., Fernando, R.,
                    Scudder, J.G. and Chen, E.,
                    "Graceful Restart Mechanism for BGP",
                    draft-ietf-idr-restart-02.txt, January 2002, work
                    in progress.


   Thanks to Francis Ovenden and Elwyn Davies for review and Abha Ahuja
   for encouragement. Much appreciation to Jeff Haas, Matt Richardson,
   and Shane Wright at Nexthop for comments and input. Debby Stopp and
   Nick Ambrose contributed the concept of route packing.

10	Author's

11.Author's Addresses

   Howard Berkowitz
    Nortel Networks
   Gett Communications
   5012 S. 25th St
   Arlington VA 22206
   Phone: +1 703 998-5819 (ESN 451-5819)
   Fax:   +1 703 998-5058

   Elwyn Davies
   Nortel Networks
   London Road
   Harlow, Essex CM17 9NA
   Phone: +44-1279-405498

   Susan Hares
   Nexthop Technologies
   517 W. William

Berkowitz, et al            Expires: August 2002                      25
   Ann Arbor, Mi 48103

   Padma Krishnaswamy
    Nexthop  Technologies
    517 W William
    Ann Arbor, Mi 48103
    Phone: 734 973 2200

   Marianne Lepp
   Juniper Networks
   51 Sawyer Road
   Waltham, MA 02453
   Phone: 617 645 9019

   Alvaro Retana
   Cisco Systems, Inc.
   7025 Kit Creek Rd.
   Research Triangle Park, NC 27709

Full Copyright Statement

   Copyright (C) The Internet Society (2000). (2002). 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

   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

Berkowitz, et al            Expires: August 2002                      26