draft-ietf-bmwg-conterm-00.txt   draft-ietf-bmwg-conterm-01.txt 
Benchmarking Terminology Working Group H.Berkowitz
Internet Draft
S.Hares
draft-ietf-bmwg-conterm-00.txt A.Retana
Expires February 2002 Benchmarking Working Group H.Berkowitz, Gett Communications
P.Krishnaswamy Internet Draft S.Hares, Next Hop
M.Lepp Document: draft-ietf-bmwg-conterm-01.txt A.Retana, Cisco
Expires August 2002 P.Krishnaswamy, Consultant
July 2001 M.Lepp, Juniper Networks
E.Davies, Nortel Networks
February 2002
Terminology for Benchmarking External Routing Convergence Measurements Terminology for Benchmarking
External Routing Convergence Measurements
Status of this Memo Status of this Memo
This document is an Internet-Draft and is in full conformance with This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026 [1]. all provisions of Section 10 of RFC2026 [1].
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that other
other groups may also distribute working documents as Internet- groups may also distribute working documents as Internet-Drafts.
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
Internet-Drafts are draft documents valid for a maximum of six time. It is inappropriate to use Internet- Drafts as reference
months and may be updated, replaced, or obsoleted by other documents material or to cite them other than as "work in progress."
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 current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt. http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
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.
Abstract Abstract
This draft establishes terminology to standardize the description of This draft establishes terminology to standardize the description of
benchmarking methodology for measuring eBGP convergence in the control benchmarking methodology for measuring eBGP convergence in the
plane of a single router. Future documents will address iBGP control plane of a single BGP device. Future documents will address
convergence, the initiation of forwarding based on converged control iBGP convergence, the initiation of forwarding based on converged
plane information and internet-wide convergence. control plane information and internet-wide convergence.
Conventions used in this document Conventions used in this document
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
this document are to be interpreted as described in RFC-2119 [2]. document are to be interpreted as described in RFC-2119 [2].
Berkowitz, et al 1
Table of Contents Table of Contents
1 Introduction 3 1. Introduction....................................................3
1.1 Overview and Roadmap 3 1.1 Overview and Roadmap.......................................3
1.2 Definition Format 4 1.2 Definition Format..........................................3
2 Constituent elements of a router or network of routers. 5 2. Constituent elements of a router or network of routers.........4
2.1 BGP Peer 5 2.1 BGP Peer...................................................4
2.2 Default Route, Default Free Table, and Full Table 5 2.2 Default Route, Default Free Table, and Full Table..........5
2.2.1 Default Route 2.3 Classes of BGP-Speaking Routers............................7
6 2.2.2 Default Free Routing Table 3. Routing Data Structures.........................................9
6 3.1 Routing Information Base (RIB).............................9
2.2.3 Full Default Free Table 7 3.2 Policy....................................................10
2.2.4 Full Provider Internal Table 7 3.3 Policy Information Base...................................11
2.3 Classes of BGP-Speaking Routers 8 3.4 The Forwarding Information Base (FIB).....................12
2.3.1 Provider Edge Router 8 4. Components and characteristics of Routing information..........12
2.3.2 Subscriber Edge Router 8 4.1 Prefix....................................................12
2.3.3 Interprovider Border Router 9 4.2 Route.....................................................13
2.3.4 Intraprovider Core Router 9 4.3 BGP Route.................................................13
3 Routing Data Structures 9 4.4 Route Instance............................................14
3.1 Routing Information Base (RIB) 9 4.5 Active Route..............................................14
3.1.1 Adj-RIB-In and Adj-RIB-Out 10 4.6 Unique Route..............................................14
3.1.2 Loc-RIB 10 4.7 Non-Unique Route..........................................15
3.2 Policy 11 4.8 Route Packing.............................................15
3.3 Policy Information Base 11 4.9 Route Mixture.............................................15
3.4 The Forwarding Information Base (FIB) 12 4.10 Update Train...........................................16
4 Components and characteristics of Routing information 13 4.11 Route Flap.............................................18
4.1 Prefix 13 5. Route Changes and Convergence..................................18
4.2 Route 13 5.1 Route Change Events.......................................18
4.3 BGP Route 14 5.2 Convergence...............................................19
4.4 Route Instance 14 6. BGP Operation Events...........................................20
4.5 Active Route 15 6.1 Hard reset................................................20
4.6 Unique Route 15 6.2 Soft reset................................................21
4.7 Non-Unique Route 15 7. Factors that impact the performance of the convergence process.21
4.8 Route Packing 16 7.1 General factors affecting BGP convergence.................21
4.9 Update Train 16 7.2 Implementation-specific and other factors affecting BGP
4.10 Route Flap 16 convergence............................................22
5 Route Changes and Convergence 17 8. Security Considerations........................................23
5.1 Route Change Events 17 9. References.....................................................24
5.2 Convergence 18 10. Acknowledgments...............................................25
6 Factors that impact the performance of the convergence process 19 11. Author's Addresses............................................25
6.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 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
7 Security Considerations 22
8 References 22
9 Acknowledgments 22
10 Author's Addresses 23
1 Introduction Berkowitz, et al Expires: August 2002 2
This document defines terminology for use in characterizing the 1. Introduction
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 the approach adopted in this, and the This document defines terminology for use in characterizing the
companion document: 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 underlie the approach adopted in this, and
the companion document:
-The principal objective is to derive methodologies to standardize -The principal objective is to derive methodologies to standardize
conducting and conducting and reporting convergence-related measurements for BGP.
reporting convergence-related measurements for BGP. - It is necessary to remove ambiguity from many frequently used
-It is necessary to remove ambiguity from many frequently used terms that terms that arise in the context of such measurements.
arise in - As convergence characterization is a complex process, it is
the context of such measurements. desirable to restrict the initial focus in this set of documents
-As convergence characterization is a complex process, it is desirable to to specifying how to take basic control plane measurements as a
restrict the initial focus in this set of documents to specifying how to first step to characterizing BGP convergence.
take basic control plane measurements towards 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 For path vector protocols such as BGP, the primary initial focus will
measurement, such as the impacts of the presence of policy processing, therefore be on network and system control-plane activity consisting
simultaneous traffic on the control and data paths within the DUT, and other of the arrival, processing, and propagation of routing information
realistic performance modifiers. Convergence of Subsequent drafts will explore the more intricate aspects of
Interior Gateway Protocols will also be considered in separate drafts. 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 1.1 Overview and Roadmap
A characterization of the BGP convergence performance of a device must take Characterizations of the BGP convergence performance of a device must
into account take into account all distinct stages and aspects of BGP
all distinct stages and aspects of BGP functionality. This requires that the functionality. This requires that the relevant terms and metrics be
relevant terms as specifically defined as possible. Such definition is the goal of
and metrics be as specifically defined as possible. Such definition is the this document.
goal of this document.
The necessary definitions are classified into two separate The necessary definitions are classified into two separate
categories: categories:
. Descriptions of the constituent elements of a network or a - Descriptions of the constituent elements of a network or a router
router that is undergoing convergence that is undergoing convergence
. Descriptions of factors that impact convergence processes - Descriptions of factors that impact convergence processes
1.2 Definition Format 1.2 Definition Format
The definition format is equivalent to that defined in [RFC1812], The definition format is equivalent to that defined in [5], and is
and repeated here for convenience:
is repeated here for convenience:
X.x Term to be defined. (e.g., Latency) X.x Term to be defined. (e.g., Latency)
Definition: Definition:
The specific definition for the term. The specific definition for the term being defined.
Berkowitz, et al Expires: August 2002 3
Discussion: Discussion:
A brief discussion about the term, its application and any A brief discussion of the term, its application and any
restrictions on measurement procedures. restrictions that there might be on measurement
procedures.
Measurement units: Measurement units:
The units used to report measurements of this term, if The units used to report measurements of this term, if
applicable. applicable.
Issues: Issues:
List of issues or conditions that could affect this term.
List of issues or conditions that affect this term.
See Also: See Also:
List of other terms that are relevant to the discussion of List of related terms that are relevant to the definition
this term. or discussion of this term.
2 Constituent elements of a router or network of routers. 2. Constituent elements of a router or network of routers.
Many terms included in this list of definitions were described Many terms included in this list of definitions were originally
originally in previous standards or papers. They are included here described in previous standards or papers. They are included here
because of their pertinence to this discussion. Where relevant, because of their pertinence to this discussion. Where relevant,
reference is made to these sources. An effort has been made to keep reference is made to these sources. An effort has been made to keep
this list complete with regard to the necessary concepts without this list complete with regard to the necessary concepts without over
over definition. definition.
2.1 BGP Peer 2.1 BGP Peer
Definition: Definition:
A BGP peer is another BGP instance to which the Device
A BGP peer is another BGP instance to which the the Device Under Test Under Test (DUT) has established a TCP connection over
(DUT) has established a TCP connection over which a BGP session is which a BGP session is active. In the test scenarios in
active. In the test scenarios in the methodology discussion that will the methodology discussion that will follow this draft,
follow this draft, peers send BGP advertisements to the DUT and receive peers send BGP advertisements to the DUT and receive DUT-
DUT-originated advertisements. originated advertisements.
Discussion: Discussion:
This is a protocol-specific definition, not to be confused
with another frequent usage, which refers to the
business/economic definition for the exchange of routes
without financial compensation.
This is a protocol-specific definition, not to be confused with It is worth noting that a BGP peer, by this definition is
another frequent usage, which refers to the business/economic associated with a BGP peering session, and there may be
definition for the exchange of routes without financial more than one such active session on a router or on a
compensation. tester. The peering sessions referred to here may exist
between various classes of BGP routers (see section 2.3).
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)
.
Measurement units: number of BGP peers Measurement units: number of BGP peers
Issues: Issues:
See Also: See Also:
Berkowitz, et al Expires: August 2002 4
2.2 Default Route, Default Free Table, and Full Table 2.2 Default Route, Default Free Table, and Full Table
An individual router's routing table may not necessarily contain a An individual router's routing table may not necessarily contain a
default route. Not having a default route, however, is not synonymous default route. Not having a default route, however, is not
with having a full default-free table. synonymous with having a full default-free table(DFT).
It should be noted that the references to number of routes in this 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 section are to routes installed in the loc-RIB, not route instances,
that the total number of route instances may be 4 to 10 times the number and that the total number of route instances may be 4 to 10 times the
of routes. number of routes.
MPLS speaking routers are outside the scope of this document
The actual path setup and forwarding of MPLS speaking routers are
outside the scope of this 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 2.2.1 Default Route
Definition: Definition:
A Default Route is a route entry that can match any
A Default Route is a route entry that can match any prefix. If a prefix. If a router does not have a route for a particular
router does not have a route for a particular packet's destination packet's destination address, it forwards this packet to
address, it forwards this packet to the next hop in the default the next hop in the default route entry, provided its
route entry, provided its Forwarding Table (Forwarding Information Forwarding Table (Forwarding Information Base (FIB)
Base (FIB) ) contains one. The notation for a default contains one. The notation for a default route is
route is 0.0.0.0/0 0.0.0.0/0
Discussion: Discussion:
Measurement units: N.A. Measurement units: N.A.
Issues: Issues:
See Also: default free routing table, route, route instance See Also: default free routing table, route, route instance
Berkowitz, et al Expires: August 2002 5
2.2.2 Default Free Routing Table 2.2.2 Default Free Routing Table
Definition:
A routing table with no default routes, as typically seen in routers at Definition:
the core or top tier. A routing table with no default routes, as typically seen
in routers in the core or top tier of routers in the
network.
Discussion: Discussion:
The term originates from the concept that routers at the
core or top tier of the Internet will not be configured
with a default route (Notation 0.0.0.0/0). Thus they will
forward every prefix to a specific next hop based on the
longest match on the IP addresses.
The term originates from the concept that routers at the core or Default free routing table size is commonly used as an
top tier of the Internet will not be configured with a default route indicator of the magnitude of reachable Internet address
(Notation 0.0.0.0/0). Thus they will forward every prefix to a space. However, default free routing tables may also
specific nexthop based on the longest match on the IP addresses. include routes internal to the router's AS.
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 Measurements: The number of routes
See Also: Full Default Free See Also: Full Default Free, Default Route
2.2.3 Full Default Free Table 2.2.3 Full Default Free Table
Definition: Definition:
A set of BGP routes generally accepted to be the complete
A set of BGP routes generally accepted to be the complete set of set of BGP routes collectively announced by the complete
BGP routes announced by all autonomous systems to the public set of autonomous systems making up the public Internet.
Internet. Due to the dynamic nature of the Internet, the exact Due to the dynamic nature of the Internet, the exact size
size and composition of this table may vary slightly depending where and composition of this table may vary slightly depending
it is observed. where and when it is observed.
Discussion: Discussion:
Several investigators ([12],[13][14]) measure this on a
daily and/or weekly basis; June 2001 measurements put the
table at approximately 105,000 routes, growing
exponentially.
Several investigators [Bates, Smith] measure this It is generally accepted that a full table, in this usage,
on a weekly basis; June 2001 measurements put the table at does not contain the infrastructure routes or individual
approximately 105,000 routes, growing exponentially. sub-aggregates of routes that are otherwise aggregated by
the provider before announcement to other autonomous
It is generally accepted that a full table, in this usage, does not systems.
contain the infrastructure routes or individual subaggregates of routes
that are otherwise aggregated by the provider before announcement to
other autonomous systems.
Measurement Units: number of routes Measurement Units: number of routes
Issues: Issues:
See Also: Routes, Route Instances, Default Route See Also: Routes, Route Instances, Default Route
Berkowitz, et al Expires: August 2002 6
2.2.4 Full Provider Internal Table 2.2.4 Full Provider Internal Table
Definition: Definition:
A superset of the full routing table that contains
A superset of the full routing table that contains infrastructure and infrastructure and non-aggregated routes.
non-aggregated routes.
Discussion: Discussion:
Experience has shown that this table can contain 1.3 to
Experience has shown that this table can contain 1.3 to 1.5 times the 1.5 times the number of routes in the externally visible
number of routes in the externally visible full table. Tables of full table. Tables of this size, therefore, are a real-
this size, therefore, are a real-world requirement for key internal world requirement for key internal provider routers.
provider routers.
Measurement Units: number of routes Measurement Units: number of routes
Issues: Issues:
See Also: Routes, Route Instances, Default Route See Also: Routes, Route Instances, Default Route
2.3 Classes of BGP-Speaking Routers 2.3 Classes of BGP-Speaking Routers
A given router may perform more than one of the following functions, A given router may perform more than one of the following functions,
based on its logical location in the network. based on its logical location in the network.
2.3.1 Provider Edge Router 2.3.1 Provider Edge Router
Definition: Definition:
A router at the edge of a provider's network, configured
A router at the edge of a provider's network, configured to speak BGP, to speak BGP, which peers with a BGP speaking router
which peers with a BGP speaking router operated by the end-user. The operated by the end-user. The traffic that transits this
traffic that transits this router may be destined to, or originate from router may be destined to, or originate from
non-contiguous autonomous systems. non-contiguous autonomous systems.
Discussion: Discussion:
Such a router will always speak eBGP and may speak iBGP. Such a router will always speak eBGP and may speak iBGP.
Measurement units: Measurement units:
Issues: Issues:
See Also: See Also:
Berkowitz, et al Expires: August 2002 7
2.3.2 Subscriber Edge Router 2.3.2 Subscriber Edge Router
Definition: Definition:
A BGP-speaking router belonging to an end user
A BGP-speaking router belonging to an end user organization that may be organization that may be multi-homed, which carries
multi-homed, which carries traffic only to and from that end user AS. traffic only to and from that end user AS.
Discussion: Discussion:
Such a router will always speak eBGP and may speak iBGP. Such a router will always speak eBGP and may speak iBGP.
Measurement units: Measurement units:
Issues: Issues:
See Also: See Also:
2.3.3 Interprovider Border Router 2.3.3 Interprovider Border Router
Definition: Definition:
A BGP speaking router which maintains BGP sessions with
A BGP speaking router that maintains BGP sessions with another BGP another BGP speaking router in another provider AS.
speaking router in another provider AS. Traffic transiting this router Traffic transiting this router may be directed to or from
may be directed to or from another AS that has no direct connectivity another AS that has no direct connectivity with this
with this provider's AS. provider's AS.
Discussion: Discussion:
Such a router will always speak eBGP and may speak iBGP. Such a router will always speak eBGP and may speak iBGP.
Measurement units: Measurement units:
Issues: Issues:
See Also: See Also:
2.3.4 Intraprovider Core Router 2.3.4 Intraprovider Core Router
skipping to change at line 377 skipping to change at line 368
Such a router will always speak eBGP and may speak iBGP. Such a router will always speak eBGP and may speak iBGP.
Measurement units: Measurement units:
Issues: Issues:
See Also: See Also:
2.3.4 Intraprovider Core Router 2.3.4 Intraprovider Core Router
Definition: A provider router speaking iBGP to the provider's edge Definition:
routers, other intraprovider core routers, or the provider's A provider router speaking iBGP to the provider's edge
interprovider border routers. routers, other intraprovider core routers, or the
provider's interprovider border routers.
Discussion: Discussion:
Such a router will always speak iBGP and may speak eBGP. Such a router will always speak iBGP and may speak eBGP.
Measurement units: Measurement units:
Issues: Issues:
MPLS speaking routers are outside the scope of this
MPLS speaking routers are outside the scope of this document. It is document. It is entirely likely, however, that core Label
entirely likely, however, that core Label Switched Routers, especially Switched Routers, especially in the P router role of
in the P router role of RFC 2547, may contain little or no BGP RFC 2547 [16], may contain little or no BGP information.
information.
See Also: See Also:
3 Routing Data Structures
Berkowitz, et al Expires: August 2002 8
3. Routing Data Structures
3.1 Routing Information Base (RIB) 3.1 Routing Information Base (RIB)
The RIB collectively consists of a set of logically (not necessarily The RIB collectively consists of a set of logically (not necessarily
literally) distinct databases, each of which is enumerated below. The literally) distinct databases, each of which is enumerated below. The
RIB contains all destination prefixes to which the router may forward, RIB contains all destination prefixes to which the router may
and one or more currently reachable next hop addresses for them. forward, and one or more currently reachable next hop addresses for
Routes included in this set potentially have been selected from several them.
sources of information,including hardware status, interior routing
protocols, and exterior routing protocols. RFC 1812 contains a basic set Routes included in this set potentially have been selected from
of route selection criteria relevant in an all-source context. Many several sources of information, including hardware status, interior
implementations impose additional criteria. A common implementation- routing protocols, and exterior routing protocols. RFC 1812 contains
specific criterion is the preference given to different routing a basic set of route selection criteria relevant in an all-source
information sources. context. Many implementations impose additional criteria. A common
implementation-specific criterion is the preference given to
different routing information sources.
3.1.1 Adj-RIB-In and Adj-RIB-Out 3.1.1 Adj-RIB-In and Adj-RIB-Out
Definition: Definition:
Adj-RIB-In and Adj-RIB-Out are "views" of Adj-RIB-In and Adj-RIB-Out are "views" of routing
routing information from the perspective of individual peer routers. information from the perspective of individual peer
The Adj-RIB-In contains information advertised to the DUT by a routers.
specific peer. The Adj-RIB-Out contains the information the DUT
will advertise to the 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[3].
See RFC 1771
Discussion: Discussion:
Issues: Issues:
Measurement Units: Number of route instances Measurement Units: Number of route instances
See Also: Route, BGP Route, Route Instance, Loc-RIB, FIB See Also: Route, BGP Route, Route Instance, Loc-RIB, FIB
Berkowitz, et al Expires: August 2002 9
3.1.2 Loc-RIB 3.1.2 Loc-RIB
Definition: Definition:
The Loc-RIB contains the set of best routes selected from The Loc-RIB contains the set of best routes selected from
the various Adj-RIBs, after applying local policies and the BGP route the various Adj-RIBs, after applying local policies and
selection algorithm. the BGP route selection algorithm.
Discussion: Discussion:
The separation implied between the various RIBs is
The separation implied between the various RIBs is logical. It does logical. It does not necessarily follow that these RIBs
not necessarily follow that these RIBs are distinct and separate are distinct and separate entities in any given
entities in any given implementation. implementation.
Issues: Issues:
Specifying the RIB is important because the types and
relative proportions of routes in it can affect the
convergence efficiency.
Types of routes can include internal BGP, external
BGP,interface, static and IGP routes.
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. Measurement Units: Number of route instances.
See Also: Route, BGP Route, Route Instance, Adj-RIB-in, Adj-RIB-out, See Also: Route, BGP Route, Route Instance, Adj-RIB-in,
FIB Adj-RIB-out,FIB
3.2 Policy 3.2 Policy
Definition: Definition:
Policy is "the ability to define conditions for accepting, Policy is "the ability to define conditions for accepting,
rejecting, and modifying routes received in advertisements"[16] rejecting, and modifying routes received in
advertisements"[15].
Discussion: Discussion:
RFC 1771 [3] further constrains policy to be within the
RFC 1771 [RFC1771] further constrains policy to be within the hop-by-hop routing paradigm. Policy is implemented using
hop-by-hop routing paradigm. filters and associated policy actions. Many AS's use
Policy is implemented using filters and associated policy routing Policy Specification Language (RPSL) [8] to
actions. document their policies and automatically generate
configurations for the BGP processes in their routers.
Measurement Units: Measurement Units:
Issues: Issues:
See Also: Policy Information Base. See Also: Policy Information Base.
Berkowitz, et al Expires: August 2002 10
3.3 Policy Information Base 3.3 Policy Information Base
Definition: Definition:
A policy information base is the set of incoming and
A policy information base is the set of incoming and outgoing outgoing policies.
policies.
Discussion: Discussion:
All references to the phase of the BGP selection process All references to the phase of the BGP selection process
here are made with respect to RFC 1771 [RFC1771] definition of these here are made with respect to RFC 1771 [3] definition of
phases. these phases.
Incoming policies are applied in Phase 1 of the BGP selection
process [RFC1771]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 Incoming policies are applied in Phase 1 of the BGP
conditions. Common information to match include route prefixes, AS paths, selection process [3] to the Adj-RIB-In routes to set the
communities, metric for the Phase 2 decision process. Outgoing
etc. The action on match may be to drop the update and not pass it to the Policies are applied in Phase 3 of the BGP process to the
Loc-RIB, or Adj-RIB-Out routes preceding route (prefix and path
to modify the update in some way, such as changing local preference (on attribute tuple) announcements to a specific peer.
input) or MED
(on output), adding or deleting communities, prepending AS in the AS path,
etc.
The amount of policy processing (both in terms of route maps and Policies in the Policy Information Base have matching and
filter/access lists) will impact the convergence time and properties action conditions. Common information to match include
of the distributed BGP algorithm. The amount of policy processing may route prefixes, AS paths, communities, etc. The action on
vary from a simple policy which accepts all routes and sends all routes match may be to drop the update and not pass it to the
to complex Loc-RIB, or to modify the update in some way, such as
policy with a substantial fraction of the prefixes being filtered by changing local preference (on input) or MED (on output),
filter/access lists. 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:
Issues:
See Also:
Berkowitz, et al Expires: August 2002 11
3.4 The Forwarding Information Base (FIB) 3.4 The Forwarding Information Base (FIB)
Definition: Definition:
The Forwarding Information Base is generated from the RIB.
The Forwarding Information Base is generated from The FIB is referred to in [3] as well as [5] but not
the RIB. The FIB is referred to in [RFC1771] as well as [RFC1812] but defined in either. For the purposes of this document, the
not defined in either. For the purposes of this document, the FIB is the FIB is the subset of the RIB used by the forwarding plane
subset of the RIB used by the forwarding plane to make per-packet to make per-packet forwarding decisions.
forwarding decisions.
Discussion: Discussion:
Most current implementations have full, non-cached FIBs Most current implementations have full, non-cached FIBs
per router interface. All the route computation and convergence per router interface. All the route computation and
occurs before a route is downloaded into a FIB. convergence occurs before a route is downloaded into a
FIB.
Measurement Units: N.A. Measurement Units: N.A.
Issues: Issues:
See Also: Route, RIB See Also: Route, RIB
4 Components and characteristics of Routing information 4. Components and characteristics of Routing information
4.1 Prefix 4.1 Prefix
Definition: Definition:
A destination address specified in CIDR format. Expressed
A destination address in CIDR format. as prefix/length. The definition in [5] is "A network
Expressed as prefix/length. The definition in [RFC1812] is "A prefix is a contiguous set of bits at the more significant
network prefix is a contiguous set of bits at the more significant end of the address that defines a set of systems; host
end of the address that defines a set of systems; host numbers select numbers select among those systems."
among those systems."
Discussion: Discussion:
A prefix is expressed as a portion of an IP address
A prefix is expressed as a portion of an IP address followed by the followed by the associated mask such as 10/8.
associated mask such as 10/8.
Measurement Units: N.A. Measurement Units: N.A.
Issues: Issues:
See Also See Also
Berkowitz, et al Expires: August 2002 12
4.2 Route 4.2 Route
Definition: Definition:
In general, a 'route' is the n-tuple
In general, a 'route' is the n-tuple <prefix, nexthop [,other non- <prefix, nexthop[, other non-routing protocol attributes]>
routing protocol attributes] >. A route is not end-to-end, but is A route is not end-to-end, but is defined with respect to
defined with respect to a specific next hop that will move traffic a specific next hop that will move traffic closer to the
closer to the destination defined by the prefix. In this usage, a route destination defined by the prefix. In this usage, a route
is the basic unit of information about a target destination distilled is the basic unit of information about a target
from routing protocols. destination distilled from routing protocols.
Discussion: Discussion:
This term refers to the concept of a route common to all This term refers to the concept of a route common to all
routing protocols. With reference to the definition above, typical routing protocols. With reference to the definition above,
non-routing-protocol attributes would be associated with diffserv or typical non-routing-protocol attributes would be
traffic engineering. associated with diffserv or traffic engineering.
Measurement Units: N.A. Measurement Units: N.A.
Issues: None. Issues: None.
See Also: BGP route See Also: BGP route
4.3 BGP Route 4.3 BGP Route
Definition: Definition:
The n-tuple
The n-tuple <prefix, nexthop, aspath [, other BGP attributes]>. <prefix, nexthop, aspath [, other BGP attributes]>.
Discussion: Discussion:
Nexthop is one type of attribute. Attributes are defined
in RFC 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."
Nexthop is one type of attribute. Attributes are defined in RFC 1771
[RFC1771], 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. Measurement Units:N.A.
Issues: Issues:
See Also: Route, prefix, Adj-RIB-in. See Also: Route, prefix, Adj-RIB-in.
Berkowitz, et al Expires: August 2002 13
4.4 Route Instance 4.4 Route Instance
Definition: Definition:
A single occurrence of a route sent by a BGP Peer for a
A single occurrence of a route sent by a BGP Peer for a particular particular prefix. When a router has multiple peers from
prefix. When a router has multiple peers from which it accepts routes, which it accepts routes, routes to the same prefix may be
routes to the same prefix may be received from several peers. This received from several peers. This is then an example of
is then an example of multiple route instances. multiple route instances.
Discussion: Discussion:
Each route instance is associated with a specific peer. A
Each route instance is associated with a specific peer. specific route instance may be rejected by the BGP
A specific route instance may be rejected by the BGP selection algorithm selection algorithm due to local policy.
due to local policy.
Measurement Units: number of route instances Measurement Units: number of route instances
Issues: Issues:
The number of route instances in the Adj-RIB-in bases will vary based The number of route instances in the Adj-RIB-in bases will
on the function to be performed by a router. An interprovider router, vary based on the function to be performed by a router. An
located in the default free zone will likely receive more route inter-provider router, located in the default free zone
instances than an provider edge router, located closer to the end-users will likely receive more route instances than a provider
of the network. edge router, located closer to the end-users of the
network.
See Also: See Also:
4.5 Active Route 4.5 Active Route
Definition: Definition:
Route for which there is a FIB entry corresponding to a RIB entry. Route for which there is a FIB entry corresponding to a
RIB entry.
Discussion: Discussion:
Measurement Units: Measurement Units:
Issues: Issues:
See also: RIB. See also: RIB.
4.6 Unique Route 4.6 Unique Route
D efinition: D efinition:
A unique route is a prefix for which there is just one A unique route is a prefix for which there is just one
route instance across all Adj-Ribs-In. route instance across all Adj-Ribs-In.
Discussion: Discussion:
Measurement Units: N.A. Measurement Units: N.A.
Issues: Issues:
See Also: route, route instance See Also: route, route instance
skipping to change at line 648 skipping to change at line 668
route instance across all Adj-Ribs-In. route instance across all Adj-Ribs-In.
Discussion: Discussion:
Measurement Units: N.A. Measurement Units: N.A.
Issues: Issues:
See Also: route, route instance See Also: route, route instance
Berkowitz, et al Expires: August 2002 14
4.7 Non-Unique Route 4.7 Non-Unique Route
Definition: Definition:
A Non-unique route is a prefix for which there is at least one other A Non-unique route is a prefix for which there is at least
route in a set including more than one Adj-RIB-in. one other route in a set including more than one Adj-RIB-
in.
Discussion: Discussion:
Measurement Units: N.A. Measurement Units: N.A.
Issues: Issues:
See Also: route, route instance, unique active route. See Also: route, route instance, unique active route.
4.8 Route Packing 4.8 Route Packing
Definition:
Definition:
Number of route prefixes that exist in a single Routing Number of route prefixes that exist in a single Routing
Protocol Update or Withdraw Message. Protocol UPDATE Message either as updates (additions or
modifications) or withdrawals.
Discussion: Discussion:
In general, a routing protocol update MAY contain more
than one prefix. In BGP, a single UPDATE MAY contain
multiple prefixes with identical attributes. Protocols
that do not support such a concept implicitly have a Route
Packing of 1.
In general, a routing protocol update MAY contain more than one Measurement Units: N.A.
prefix. In BGP, a single update MAY contain multiple prefixes with
identical attributes.
Protocols that do not support such a concept implicitly have a Route Issues:
Packing of 1. "
See Also: route, route instance, update train.
4.9 Route Mixture
4.9 Update Train
Definition: Definition:
A characterization of the routes in a collection of
routes. Two profiles are used to characterize a
collection of routes as a route mixture:
- The distribution of prefix lengths in the collection
- The clustering of prefixes around particular branches
the tree which can be used to represent the totality
of possible prefixes.
A set of updates, containing one or more route prefixes, which an Discussion:
external router desires to send to the DUT. When there is more than one Route mixtures are used to simulate the normal pattern of
prefix in the set, the multiple updates (including withdrawals) may be prefix distribution that is seen in real world route
sent as individual BGP UPDATE packets, or as one or more BGP packets tables and update trains. As can be seen in the analyses
with multiple routes packed (q.v.) into them. 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)
Issues:
See Also:
4.10 Update Train
Definition:
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.
Discussion: Discussion:
The more individual update packets that are sent, the more TCP and The more individual UPDATE packets that are sent, the more
BGP header processing will be imposed on the receiving router that is TCP and BGP header processing will be imposed on the
the DUT. 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.
An update train may be caused by a variety of network conditions. For The time intervals between the UPDATE packets in a train
example, an update train could be caused by an influx of UPDATES from may vary from essentially zero when the packets follow
different peers that have been received and moved to RIB-out or caused each other as closely as possible up to a situation where
by a peer coming up and advertising its routes, or by a local or remote the time between packets exceeds MIN_ADVERT_TIME. Once
peer flapping a link. Other causes are, of course, possible. 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 packets in the train,
time spacing between packets in train
Measurement units: Number of prefixes and update packets in the train.
Issues: Issues:
See Also: See Also:
4.10 Route Flap
Definition: RIPE 210 [RIPE]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/ of a prefix in
the Adj-RIB-in.
A route flap is not a problem until a route is flapped several times in 4.10.1 Random Update Train
close succession. This causes negative repercussions throughout the
internet. Definition:
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].
Discussion: Discussion:
Route flapping can be considered a special and pathological case of This is intended to simulate the unpredictable
update trains. 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.
A practical interpretation of what may be considered excessively The distribution used to control the selection of prefixes
rapid is the RIPE recommendation of "four flaps in a row". See 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 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
Issues:
See also:
Berkowitz, et al Expires: August 2002 17
4.11 Route Flap
Definition:
RIPE 210 [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 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.
Discussion:
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. Section 6.1.5 on flap damping for further discussion.
Measurement units Measurement units: Flapping events per unit time.
Flapping events per unit time.
Issues: Issues:
Specific Flap events can be found in Section 5.1Route Change Events. A Specific Flap events can be found in Section 5.1Route
bench-marker should use a mixture of different route change events in Change Events. A bench-marker should use a mixture of
testing. different route change events in testing.
See Also: Route change events, flap damping, packet train See Also: Route change events, flap damping, packet train
5 Route Changes and Convergence 5. Route Changes and Convergence
The following two definitions are central to the benchmarking of The following two definitions are central to the benchmarking of
external routing convergence, and so are singled out for more extensive external routing convergence, and so are singled out for more
discussion. extensive discussion.
5.1 Route Change Events 5.1 Route Change Events
A taxonomy characterizing routing information changes seen in A taxonomy characterizing routing information changes seen in
operational networks is proposed in [Ahuja et al] as well as Labovitz operational networks is proposed in [6] as well as Labovitz et al[7].
et al[4]. These papers describe BGP protocol-centric events, and event These papers describe BGP protocol-centric events, and event
sequences in the course of an analysis of network behavior. The sequences in the course of an analysis of network behavior. The
terminology in the two papers addresses similar but slightly different terminology in the two papers categorizes similar but slightly
behaviors with some overlap. We would like to apply these taxonomies to different behaviors with some overlap. We would like to apply these
categorize the tests under definition where possible, because these taxonomies to categorize the tests under definition where possible,
tests must tie in to phenomena that arise in actual networks. We avail because these tests must tie in to phenomena that arise in actual
of, or may extend, this terminology as necessary for this purpose. 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 A route can be changed implicitly by replacing it with another route
explicitly by withdrawal followed by the introduction of a new route. or explicitly by withdrawal followed by the introduction of a new
In either case the change may be an actual change, no change, or a route. In either case the change may be an actual change, no change,
duplicate. The notation and definition of individual categorizable route or a duplicate. The notation and definition of individual
change events is adopted from [Labovitz et al] and given below. categorizable route change events is adopted from [7] and given
below.
a) AADiff: Implicit withdrawal of a route and replacement by a Berkowitz, et al Expires: August 2002 18
route different in some path attribute. 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 b) AADup: Implicit withdrawal of a route and replacement by route
that is identical in all path attributes. that is identical in all path attributes.
c) WADiff: Explicit withdrawal of a route and replacement by a c) WADiff: Explicit withdrawal of a route and replacement by a
different route. different route.
d) WADup: Explicit withdrawal of a route and replacement by a d) WADup: Explicit withdrawal of a route and replacement by a route
route that is identical in all path attributes. 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 To apply this taxonomy in the benchmarking context, we need both
listed above, as well as event indications in the time domain so as to terms to describe the sequence of events from the update train
be able to measure activity from the perspective of the DUT. perspective, as listed above, as well as event indications in the
With this in mind, we incorporate and extend the definitions of [4] to time domain so as to be able to measure activity from the
the following: perspective of the DUT. With this in mind, we incorporate and extend
a) Tup (TRx): Route advertised to the DUT by Test Router x the definitions of [7] to the following:
b) Tdown: Route being withdrawn
c) Tupinit: The initial announcement of a route to a unique prefix a) Tup (TDx): Route advertised to the DUT by Test Device x
d) TWF: Route fail over after an explicit withdrawal. b) Tdown(TDx): Route being withdrawn by Device x
c) Tupinit(TDx): The initial announcement of a route to a unique
prefix
d) 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 The basic criterion for selecting a "better" route is the final
tiebreaker defined in RFC1771, the router ID. As a consequence, this tiebreaker defined in RFC1771, the router ID. As a consequence, this
memorandum uses the following descriptor events. memorandum uses the following descriptor events, which are routes
selected by the BGP selection process rather than simple updates:
a)Tbest -- The current best path. a)Tbest -- The current best path.
b)Tbetter -- Advertise a path that is better than Tbest. b)Tbetter -- Advertise a path that is better than Tbest.
c)Tworse -- Advertise a path that is worse than Tbest. c)Tworse -- Advertise a path that is worse than Tbest.
5.2 Convergence 5.2 Convergence
Definition: Definition:
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.
A router is said to have converged onto a route Berkowitz, et al Expires: August 2002 19
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.
Discussion: Discussion:
The convergence process can be subdivided into three
The convergence process can be subdivided into three distinct phases: distinct phases:
-convergence across the entire Internet, -convergence across the entire Internet,
-convergence within an Autonomous System, -convergence within an Autonomous System,
-convergence with respect to a single router. -convergence with respect to a single router.
Convergence with respect to a single router can be Convergence with respect to a single router can be
-convergence with regard to the routing process(es), the -convergence with regard to the routing process(es), the
focus of this document focus of this document
-convergence with regard to data forwarding process(es). -convergence with regard to data forwarding process(es).
It is of key importance to benchmark the It is of key importance to benchmark the performance of
performance of each phase of convergence separately before proceeding each phase of convergence separately before proceeding to
to a composite a composite characterization of routing convergence, where
characterization of routing convergence, where implementation- implementation- specific dependencies are allowed to
specific dependencies are interact.
allowed to interact.
The preferred route The preferred route instance must be unambiguous during
instance must be unambiguous during test test setup/definition.
setup/definition.
Measurement Units: N.A. Measurement Units: N.A.
Issues: Issues:
See Also: See Also:
6 Factors that impact the performance of the convergence process 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
Definition:
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 the router.
Discussion:
Measurement Units: N/A
Issues:
See Also:
Berkowitz, et al Expires: August 2002 20
6.2 Soft reset
Definition:
An event which results in a complete or partial restart of
the BGP session(s) on a router, but which avoids the
exchange of a large number of UPDATEs by maintaining state
across the restart.
Discussion:
Measurement Units: N/A
Issues:
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 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 have a significant affect on BGP convergence. Not all of them can be
addressed in the baseline measurements described in this document. addressed in the baseline measurements described in this document.
6.1 General factors affecting BGP convergence 7.1 General factors affecting BGP convergence
These factors are conditions of testing external to the router Device These factors are conditions of testing external to the router Device
Under Test (DUT). Under Test (DUT).
6.1.1 Number of peers 7.1.1 Number of peers
As the number of peers increases, the BGP route selection algorithm As the number of peers increases, the BGP route selection algorithm
is increasingly exercised. In addition, the phasing and frequency of is increasingly exercised. In addition, the phasing and frequency of
updates from the various peers will have an increasingly marked effect updates from the various peers will have an increasingly marked
on the convergence process on a router as the number of peers grows. effect on the convergence process on a router as the number of peers
grows.
6.1.2 Number of routes per peer 7.1.2 Number of routes per peer
The number of routes per BGP peer is an obvious stressor to the The number of routes per BGP peer is an obvious stressor to the
convergence process. The number, and relative proportion, of convergence process. The number, and relative proportion, of multiple
multiple route instances and distinct routes being added or route instances and distinct routes being added or withdrawn by each
withdrawn by each peer will affect the convergence process, as will peer will affect the convergence process, as will the mix of
the mix of overlapping route instances, and IGP routes. overlapping route instances, and IGP routes.
6.1.3 Policy processing/reconfiguration 7.1.3 Policy processing/reconfiguration
The number of routes and attributes being filtered, and The number of routes and attributes being filtered, and set, as a
set, as a fraction of the target route table size is another fraction of the target route table size is another parameter that
parameter that will affect BGP convergence. will affect BGP convergence.
Extreme examples are
Extreme examples are
-Minimal Policy: receive all, send all, -Minimal Policy: receive all, send all,
-Extensive policy: up to 100% of the total routes - Extensive policy: up to 100% of the total routes have applicable
have applicable policy. policy.
Berkowitz, et al Expires: August 2002 21
7.1.4 Interactions with other protocols.
6.1.4 Interactions with other protocols.
There are interactions in the form of precedence, synchronization, There are interactions in the form of precedence, synchronization,
duplication and the addition of timers, and route selection duplication and the addition of timers, and route selection criteria.
criteria. Ultimately, understanding BGP4 convergence must include Ultimately, understanding BGP4 convergence must include understanding
understanding of the interactions with both the IGPs and the of the interactions with both the IGPs and the protocols associated
protocols associated with the physical media, such as Ethernet, with the physical media, such as Ethernet, SONET, DWDM.
SONET, DWDM.
6.1.5 Flap Damping 7.1.5 Flap Damping
A router can use flap damping to respond to route flapping. Use of 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, flap damping is not mandatory, so the decision to enable the feature,
and to change parameters associated with it, can be considered a matter and to change parameters associated with it, can be considered a
of routing policy. matter of routing policy.
The timers are defined by RFC 2439 [RFC 2439] and discussed in RIPE 210 The timers are defined by RFC 2439 [4] and discussed in RIPE-210 [9].
[17].
If this feature is in effect, it requires that the router keep If this feature is in effect, it requires that the router keep
additional state to carry out the damping, which can have a direct additional state to carry out the damping, which can have a direct
impact on the control plane due to increased processing. In addition, impact on the control plane due to increased processing. In
flap damping may delay the arrival of real changes in a route, and addition, flap damping may delay the arrival of real changes in a
affect convergence times route, and affect convergence times
6.1.6 Churn 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 In theory, a BGP router could receive a set of updates that
received and sent by the router. It does not include KeepAlives. completely defined the Internet, and could remain in a steady state,
only sending appropriate KeepAlives. In practice, the Internet will
always be changing.
Churn is caused by both normal and pathological events. For example, if Churn refers to control plane processor activity caused by
an interface of the local router goes down and the associated prefix is announcements received and sent by the router. It does not include
withdrawn, that withdrawal is a normal activity, although it contributes KeepAlives.
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 Churn is caused by both normal and pathological events. For example,
know, and readvertises this information, again these are normal if an interface of the local router goes down and the associated
constituents of churn. Routine updates can range from single prefix is withdrawn, that withdrawal is a normal activity, although
announcement or withdrawals, to announcements of an entire default-free it contributes to churn. If the local router receives a withdrawal
table. The latter is completely reasonable as an initialization of a route it already advertises, or an announcement of a route it
condition. 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 Flapping routes are a pathological contributor to churn, as is MED
oscillation [medosc]. The goal of flap damping is to reduce the oscillation [11]. The goal of flap damping is to reduce the
contribution of flapping to churn. contribution of flapping to churn.
The effect of churn on overall convergence depends on the processing The effect of churn on overall convergence depends on the processing
power available to the control plane, and whether the same processor(s) power available to the control plane, and whether the same
are used for forwarding and for control. processor(s) are used for forwarding and for control.
6.2 Implementation-specific and other factors affecting BGP convergence 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 These factors are conditions of testing internal to the router Device
Under Test (DUT), although they may affect its interactions with test Under Test (DUT), although they may affect its interactions with test
devices. devices.
6.2.1 Forwarded traffic 7.2.1 Forwarded traffic
The presence of actual traffic in the router may stress the control 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 path in some fashion if both the offered load due to data and the
control traffic (FIB updates and downloads as a consequence of control traffic (FIB updates and downloads as a consequence of
flaps)are excessive. The addition of data traffic presents a more flaps)are excessive. The addition of data traffic presents a more
accurate reflection of realistic operating accurate reflection of realistic operating scenarios than if only
scenarios than if only control traffic is present control traffic is present.
6.2.2 Timers 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 Settings of delay and hold-down timers at the link level as well as
relevant timers should be reported if they use non-default value. Also, for BGP4, can introduce or ameliorate delays. As part of a test
any variation in standard behavior, such as overriding TCP slow start, report, all relevant timers should be reported if they use non-
should be documented. 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
6.2.3 TCP parameters underlying BGP transport
Since all BGP traffic and interactions occur over TCP, all relevant Since all BGP traffic and interactions occur over TCP, all relevant
parameters characterizing the TCP sessions should be provided: eg Max parameters characterizing the TCP sessions should be provided: eg Max
window size, Maximum segment size, timers. window size, Maximum segment size, timers.
6.2.4 Authentication 7.2.4 Authentication
Authentication in BGP is currently done using the TCP MD5 Signature Authentication in BGP is currently done using the TCP MD5 Signature
Option [Heff]. The processing of the MD5 hash, particularly in routers Option [10]. The processing of the MD5 hash, particularly in routers
with a large number of BGP peers and a large amount of update with a large number of BGP peers and a large amount of update traffic
traffic can have an impact on the control plane of the router. can have an impact on the control plane of the router.
7 Security Considerations
8. Security Considerations
The document explicitly considers authentication as a performance- The document explicitly considers authentication as a performance-
affecting feature, but does not consider the overall security of affecting feature, but does not consider the overall security of the
the routing system. routing system.
8 References Berkowitz, et al Expires: August 2002 23
1. [RFC 2026]Bradner, S., "The Internet Standards Process -- Revision 9. References
3", BCP 9, RFC 2026, October 1996
2. [RFC 2119]Bradner, S., "Key words for use in RFCs to Indicate [1] Bradner, S., "The Internet Standards Process --
Requirement Levels", BCP 14, RFC 2119, March 1997 Revision 3", BCP 9, RFC 2026, October 1996
3. [RFC 1771]"A Border Gateway Protocol 4 (BGP-4)", RFC 1771, Y. [2] Bradner, S., "Key words for use in RFCs to
Rekhter, T. Li. March 1995. Indicate Requirement Levels", BCP 14, RFC 2119,
March 1997
4. [RFC 2539]""BGP Route Flap Damping", RFC 2439, C. Villamizar, R. [3] Rekhter, Y. and Li, T., "A Border Gateway
Chandra, R. Govindan. November 1998." Protocol 4 (BGP-4)", RFC 1771, . March 1995.
5. [RFC 1812]"Requirements for IP Version 4 Routers", RFC 1812, F. [4] Villamizar, C., Chandra, R. and Govindan, R.,
Baker. June 1995. "BGP Route Flap Damping", RFC 2439,
November 1998."
6. [Ahuja et al]"An Experimental Study of Delayed Internet Routing [5] Baker, F.,"Requirements for IP Version 4
Convergence." Abha Ahuja, Farnam Jahanian, Abhijit Bose, Routers", RFC 1812. June 1995.
Craig Labovitz, RIPE 37 - Routing WG.
7. [Labovitz et al] "Origins of Internet Routing Instability," Infocom 99
Craig Labovitz, G. Robert Malan, Farnam Jahanian],
8.[RPSL] Routing Policy Specification Language (RPSL), RFC 2622, " [6] Ahuja, A., Jahanian, F., Bose, A. and Labovitz,
C.Alaettinoglu, C. Villamizar, E. Gerich, D. Kessens, D. C.,
Meyer, T.Bates, D. Karrenberg, M. Terpstra. June 1999. "An Experimental Study of Delayed Internet
Routing Convergence", RIPE 37 - Routing WG.
9.[RIPE]RIPE 210, "RIPE Routing-WG Recommendation for coordinated [7] Labovitz, C., Malan, G.R. and Jahanian, F.,
route-flap damping parameters, Tony Barber, Sean Doran, "Origins of Internet Routing Instability,"
Daniel Karrenberg, Christian Panigl, Joachim Schmitz Infocom 99,
10.[Heff]"Protection of BGP Sessions via the TCP MD5 Signature
Option", RFC 2385, A. Heffernan. August 1998.
11. [medosc]<draft-ietf-idr-route-oscillation-00.txt>, BGP Persistent Route [8] Alaettinoglu, C., Villamizar, C., Gerich, E.,
Oscillation Condition,McPhersonm, Gill, Walton, Retana Kessens, D., Meyer, D., Bates, T., Karrenberg,
D. and Terpstra, M., "Routing Policy
Specification Language (RPSL)", RFC 2622, June
1999.
9 Acknowledgments [9] Barber, T., Doran, S., Karrenberg, D., Panigl,
Thanks to Francis Ovenden and Elwyn Davies for review and Abha Ahuja for C., Schmitz, J., "RIPE Routing-WG Recommendation
encouragement. Much appreciation to Jeff Haas, Matt Richardson, and for coordinated route-flap damping parameters",
Shane Wright at Nexthop for comments and input. Debby Stopp and Nick RIPE 210,
Ambrose contributed the concept of route packing.
10 Author's Addresses [10] Heffernan, A., "Protection of BGP Sessions via
the TCP MD5 Signature Option", RFC 2385, August
1998.
[11] McPhersonm, Gill, Walton, Retana, "BGP
Persistent Route Oscillation Condition", <draft-
ietf-idr-route-oscillation-00.txt>, Work In
progress
[12] Bates, T., "The CIDR Report",
http://www.employees.org/~tbates/cidr-report.html
Internet statistics relevant to inter-domain
routing updated daily
Berkowitz, et al Expires: August 2002 24
[13] Smith, P. (designer), APNIC Routing Table
Statistics, http://www.apnic.net/stats/bgp/,
Statistics derived from a daily analysis of a
core router in Japan
[14] Huston, G., Telstra BGP table statistics,
http://www.telstra.net/ops/bgp/index.html,
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"
http://www.juniper.net/techpubs/software/junos42/
swconfig-routing42/html/glossary.html#1013039.
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.
10.Acknowledgments
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.
11.Author's Addresses
Howard Berkowitz Howard Berkowitz
Nortel Networks Gett Communications
5012 S. 25th St 5012 S. 25th St
Arlington VA 22206 Arlington VA 22206
Phone: +1 703 998-5819 (ESN 451-5819) Phone: +1 703 998-5819
Fax: +1 703 998-5058 Fax: +1 703 998-5058
EMail: hberkowi@nortelnetworks.com EMail: hcb@gettcomm.com
Elwyn Davies
Nortel Networks
London Road
Harlow, Essex CM17 9NA
UK
Phone: +44-1279-405498
Email: elwynd@nortelnetworks.com
Susan Hares Susan Hares
Nexthop Technologies Nexthop Technologies
517 W. William 517 W. William
Berkowitz, et al Expires: August 2002 25
Ann Arbor, Mi 48103 Ann Arbor, Mi 48103
Phone: Phone:
Email: skh@nexthop.com Email: skh@nexthop.com
Padma Krishnaswamy Padma Krishnaswamy
Nexthop Technologies Email: kri1@earthlink.net
517 W William
Ann Arbor, Mi 48103
Phone: 734 973 2200
Email: kri@nexthop.com
Marianne Lepp Marianne Lepp
Juniper Networks Juniper Networks
51 Sawyer Road 51 Sawyer Road
Waltham, MA 02453 Waltham, MA 02453
Phone: 617 645 9019 Phone: 617 645 9019
Email: mlepp@juniper.net Email: mlepp@juniper.net
Alvaro Retana Alvaro Retana
Cisco Systems, Inc. Cisco Systems, Inc.
7025 Kit Creek Rd. 7025 Kit Creek Rd.
Research Triangle Park, NC 27709 Research Triangle Park, NC 27709
Email: aretana@cisco.com Email: aretana@cisco.com
Full Copyright Statement Full Copyright Statement
Copyright (C) The Internet Society (2000). All Rights Reserved. Copyright (C) The Internet Society (2002). All Rights Reserved.
This document and translations of it may be copied and furnished to This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it others, and derivative works that comment on or otherwise explain it
or assist in its implmentation may be prepared, copied, published or assist in its implmentation may be prepared, copied, published and
and distributed, in whole or in part, without restriction of any distributed, in whole or in part, without restriction of any kind,
kind, provided that the above copyright notice and this paragraph provided that the above copyright notice and this paragraph are
are included on all such copies and derivative works. However, this included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than followed, or as required to translate it into languages other than
English. English.
The limited permissions granted above are perpetual and will not be The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns. revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDIN TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDIN BUT
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Berkowitz, et al Expires: August 2002 26
 End of changes. 

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/