draft-ietf-bmwg-conterm-01.txt   draft-ietf-bmwg-conterm-02.txt 
Benchmarking Working Group H.Berkowitz, Gett Communications Benchmarking Working Group H.Berkowitz, Gett Communications
Internet Draft S.Hares, Next Hop Internet Draft S.Hares, Nexthop
Document: draft-ietf-bmwg-conterm-01.txt A.Retana, Cisco Document: draft-ietf-bmwg-conterm-02.txt A.Retana, Cisco
Expires August 2002 P.Krishnaswamy, Consultant Expires December 2002 P.Krishnaswamy, Consultant
M.Lepp, Juniper Networks M.Lepp, Juniper Networks
E.Davies, Nortel Networks E.Davies, Nortel Networks
February 2002 June 2002
Terminology for Benchmarking Terminology for Benchmarking BGP Device Convergence
External Routing Convergence Measurements in the Control Plane
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 other Task Force (IETF), its areas, and its working groups. Note that other
groups may also distribute working documents as Internet-Drafts. groups may also distribute working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
skipping to change at line 33 skipping to change at page 1, line 34
material or to cite them other than as "work in progress." 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 A revised version of this draft document will be submitted to the RFC
editor as a Informational document for the Internet Community. editor as a Informational document for the Internet Community.
Discussion and suggestions for improvement are requested. Discussion and suggestions for improvement are requested.
This document will expire before August 2002. Distribution of this This document will expire before December 2002. Distribution of this
draft is unlimited. draft is unlimited.
Copyright Notice
Copyright (C) The Internet Society (2002). All Rights Reserved.
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 benchmarking methodology for measuring eBGP convergence in the
control plane of a single BGP device. Future documents will address control plane of a single BGP device. Future documents will address
iBGP convergence, the initiation of forwarding based on converged iBGP convergence, the initiation of forwarding based on converged
control plane information and internet-wide convergence. control plane information and multiple interacting BGP devices. This
terminology is applicable to both IPv4 and IPv6. Illustrative
Conventions used in this document examples of each version are included where relevant.
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC-2119 [2].
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..........................................3 1.2 Definition Format..........................................3
2. Constituent elements of a router or network of routers.........4 2. Constituent elements of a router or network of routers.........4
2.1 BGP Peer...................................................4 2.1 BGP Instance or Device.....................................4
2.2 Default Route, Default Free Table, and Full Table..........5 2.2 BGP Peer...................................................5
2.3 Classes of BGP-Speaking Routers............................7 2.3 Default Route, Default Free Table, and Full Table..........5
2.4 Classes of BGP-Speaking Routers............................8
3. Routing Data Structures.........................................9 3. Routing Data Structures.........................................9
3.1 Routing Information Base (RIB).............................9 3.1 Routing Information Base (RIB).............................9
3.2 Policy....................................................10 3.2 Policy....................................................11
3.3 Policy Information Base...................................11 3.3 Policy Information Base...................................11
3.4 The Forwarding Information Base (FIB).....................12 3.4 Forwarding Information Base (FIB).........................12
4. Components and characteristics of Routing information..........12 4. Components and characteristics of Routing information..........13
4.1 Prefix....................................................12 4.1 (Network) Prefix..........................................13
4.2 Route.....................................................13 4.2 Network Prefix Length.....................................13
4.3 BGP Route.................................................13 4.3 Route.....................................................14
4.4 Route Instance............................................14 4.4 BGP Route.................................................14
4.5 Active Route..............................................14 4.5 BGP Route Attributes and BGP Timers.......................15
4.6 Unique Route..............................................14 4.6 Route Instance............................................16
4.7 Non-Unique Route..........................................15 4.7 Active Route..............................................17
4.8 Route Packing.............................................15 4.8 Unique Route..............................................17
4.9 Route Mixture.............................................15 4.9 Non-Unique Route..........................................17
4.10 Update Train...........................................16 4.10 BGP UPDATE message.....................................17
4.11 Route Flap.............................................18 4.11 Characterization of sets of update messages............18
5. Route Changes and Convergence..................................18 4.12 Route Flap.............................................20
5.1 Route Change Events.......................................18 5. Route Changes and Convergence..................................21
5.2 Convergence...............................................19 5.1 Route Change Events.......................................21
6. BGP Operation Events...........................................20 5.2 Device Convergence in the Control Plane...................22
6.1 Hard reset................................................20 6. BGP Operation Events...........................................23
6.2 Soft reset................................................21 6.1 Hard reset................................................24
7. Factors that impact the performance of the convergence process.21 6.2 Soft reset................................................24
7.1 General factors affecting BGP convergence.................21 7. Factors that impact the performance of the convergence process.24
7.1 General factors affecting device convergence..............24
7.2 Implementation-specific and other factors affecting BGP 7.2 Implementation-specific and other factors affecting BGP
convergence............................................22 convergence............................................26
8. Security Considerations........................................23 8. Security Considerations........................................27
9. References.....................................................24 9. References.....................................................27
10. Acknowledgments...............................................25 10. Acknowledgments...............................................28
11. Author's Addresses............................................25 11. Author's Addresses............................................29
Berkowitz, et al Expires: August 2002 2
1. Introduction 1. Introduction
This document defines terminology for use in characterizing the This document defines terminology for use in characterizing the
convergence performance of BGP processes in routers or other devices convergence performance of BGP processes in routers or other devices
that instantiate BGP functionality. It is the first part of a two that instantiate BGP functionality (see RFC1771 [1]). It is the first
document series, of which the subsequent document will contain the part of a two document series, of which the subsequent document will
associated tests and methodology. contain the associated tests and methodology. This terminology is
applicable to both IPv4 and IPv6. Illustrative examples of each
version are included where relevant.
The following observations underlie the approach adopted in this, and The following observations underlie the approach adopted in this, and
the companion document: the companion document:
- The principal objective is to derive methodologies to standardize - The principal objective is to derive methodologies to standardize
conducting and reporting convergence-related measurements for BGP. conducting and 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 arise in the context of such measurements. terms that arise in the context of such measurements.
- As convergence characterization is a complex process, it is - As convergence characterization is a complex process, it is
desirable to restrict the initial focus in this set of documents desirable to restrict the initial focus in this set of documents
to specifying how to take basic control plane measurements as a to specifying how to take basic control plane measurements as a
first step to characterizing BGP convergence. first step to characterizing BGP convergence.
For path vector protocols such as BGP, the primary initial focus will For path vector protocols, such as BGP, the primary initial focus
therefore be on network and system control-plane activity consisting will therefore be on network and system control-plane activity
of the arrival, processing, and propagation of routing information consisting of the arrival, processing, and propagation of routing
information
Subsequent drafts will explore the more intricate aspects of Subsequent drafts will explore the more intricate aspects of
convergence measurement, such as the impacts of the presence of convergence measurement, such as the impacts of the presence of
policy processing, simultaneous traffic on the control and data paths policy processing, simultaneous traffic on the control and data paths
within the DUT, and other realistic performance modifiers. within the DUT, and other realistic performance modifiers.
Convergence of Interior Gateway Protocols will also be considered in Convergence of Interior Gateway Protocols will also be considered in
separate drafts. separate drafts.
1.1 Overview and Roadmap 1.1 Overview and Roadmap
Characterizations of the BGP convergence performance of a device must Characterizations of the BGP convergence performance of a device must
skipping to change at line 138 skipping to change at page 3, line 53
this document. 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 router - Descriptions of the constituent elements of a network or a 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 [5], and is The definition format is equivalent to that defined in [3], and is
repeated here for convenience: 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 being defined.
Berkowitz, et al Expires: August 2002 3 One or more sentences forming the body of the definition.
Discussion: Discussion:
A brief discussion of the term, its application and any A brief discussion of the term, its application and any
restrictions that there might be on measurement restrictions that there might be on measurement
procedures. 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 could affect this term.
skipping to change at line 171 skipping to change at page 4, line 31
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 originally Many terms included in this list of definitions were originally
described 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 over this list complete with regard to the necessary concepts without over
definition. definition.
2.1 BGP Peer 2.1 BGP Instance or Device
Definition:
A BGP instance is a process with a single Loc-RIB that
runs on a BGP device.
Discussion:
We have chosen to use "device" as the general case, to
deal with the understood [e.g. [9]] and yet-to-be-invented
cases where the control processing may be separate from
forwarding [12]. A BGP device may be a traditional
router, a route server, a BGP-aware traffic steering
device, a device using BGP to exchange topology
information with a GMPLS environment, etc. A device such
as a route server, for example, never forwards traffic, so
forwarding-based measurements would be meaningless for it.
Measurement units: N/A
Issues:
See Also:
2.2 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 Device
Under Test (DUT) has established a TCP connection over Under Test (DUT) has established a TCP connection over
which a BGP session is active. In the test scenarios in which a BGP session is active. In the test scenarios in
the methodology discussion that will follow this draft, the methodology discussion that will follow this draft,
peers send BGP advertisements to the DUT and receive DUT- peers send BGP advertisements to the DUT and receive DUT-
originated advertisements. originated advertisements.
Discussion: Discussion:
skipping to change at line 199 skipping to change at page 5, line 33
more than one such active session on a router or on a more than one such active session on a router or on a
tester. The peering sessions referred to here may exist tester. The peering sessions referred to here may exist
between various classes of BGP routers (see section 2.3). 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.3 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 default route. Not having a default route, however, is not
synonymous with having a full default-free table(DFT). 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, 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 and that the total number of route instances may be 4 to 10 times the
number of routes. number of routes.
The actual path setup and forwarding of MPLS speaking routers are The actual path setup and forwarding of MPLS speaking routers are
outside the scope of this document. A device that computes BGP 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 routes, which a sub-IP device can use to set up paths, has its BGP
up paths, however, has its BGP aspects within scope. aspects within scope.
2.2.1 Default Route 2.3.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 router does not have a route for a particular prefix. If a router does not have a route for a particular
packet's destination address, it forwards this packet to packet's destination address, it forwards this packet to
the next hop in the default route entry, provided its the next hop in the default route entry, provided its
Forwarding Table (Forwarding Information Base (FIB) Forwarding Table (Forwarding Information Base (FIB)
contains one. The notation for a default route is contains one. The notation for a default route for IPv4 is
0.0.0.0/0 0.0.0.0/0 and for IPv6 it is 0:0:0:0:0:0:0:0 or ::/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.3.2 Default Free Routing Table
2.2.2 Default Free Routing Table
Definition: Definition:
A routing table with no default routes, as typically seen A default free routing table has no default routes and is
in routers in the core or top tier of routers in the typically seen in routers in the core or top tier of
network. routers in the network.
Discussion: Discussion:
The term originates from the concept that routers at the The term originates from the concept that routers at the
core or top tier of the Internet will not be configured core or top tier of the Internet will not be configured
with a default route (Notation 0.0.0.0/0). Thus they will with a default route (Notation in IPv4 0.0.0.0/0 and in
forward every prefix to a specific next hop based on the IPv6 0:0:0:0:0:0:0:0 or ::/0). Thus they will forward
longest match on the IP addresses. every prefix to a specific next hop based on the longest
match on the IP addresses.
Default free routing table size is commonly used as an Default free routing table size is commonly used as an
indicator of the magnitude of reachable Internet address indicator of the magnitude of reachable Internet address
space. However, default free routing tables may also space. However, default free routing tables may also
include routes internal to the router's AS. include routes internal to the router's AS.
Measurements: The number of routes Measurements: The number of routes
See Also: Full Default Free, Default Route See Also: Full Default Free, Default Route
2.2.3 Full Default Free Table 2.3.3 Full Default Free Table
Definition: Definition:
A set of BGP routes generally accepted to be the complete A full default free table is a set of BGP routes generally
set of BGP routes collectively announced by the complete accepted to be the complete set of BGP routes collectively
set of autonomous systems making up the public Internet. announced by the complete set of autonomous systems making
Due to the dynamic nature of the Internet, the exact size up the public Internet. Due to the dynamic nature of the
and composition of this table may vary slightly depending Internet, the exact size and composition of this table may
where and when it is observed. vary slightly depending where and when it is observed.
Discussion: Discussion:
Several investigators ([12],[13][14]) measure this on a Several investigators ([17],[18],[19]) measure this on a
daily and/or weekly basis; June 2001 measurements put the daily and/or weekly basis; June 2001 measurements put the
table at approximately 105,000 routes, growing table at approximately 105,000 routes, growing
exponentially. exponentially.
It is generally accepted that a full table, in this usage, It is generally accepted that a full table, in this usage,
does not contain the infrastructure routes or individual does not contain the infrastructure routes or individual
sub-aggregates of routes that are otherwise aggregated by sub-aggregates of routes that are otherwise aggregated by
the provider before announcement to other autonomous the provider before announcement to other autonomous
systems. 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.3.4 Full Provider Internal Table
2.2.4 Full Provider Internal Table
Definition: Definition:
A superset of the full routing table that contains A full provider internal table is a superset of the full
infrastructure and non-aggregated routes. routing table that contains infrastructure and 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 number of routes in the externally visible 1.5 times the number of routes in the externally visible
full table. Tables of this size, therefore, are a real- full table. Tables of this size, therefore, are a real-
world requirement for key internal provider routers. world requirement for key internal 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.4 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.4.1 Provider Edge Router
Definition: Definition:
A router at the edge of a provider's network, configured A provider edge router is a router at the edge of a
to speak BGP, which peers with a BGP speaking router provider's network, configured to speak BGP, which peers
operated by the end-user. The traffic that transits this with a BGP speaking router operated by the end-user. The
router may be destined to, or originate from traffic that transits this router may be destined to, or
non-contiguous autonomous systems. originate from 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.4.2 Subscriber Edge Router
2.3.2 Subscriber Edge Router
Definition: Definition:
A BGP-speaking router belonging to an end user A subscriber edge router is a BGP-speaking router
organization that may be multi-homed, which carries belonging to an end user organization that may be multi-
traffic only to and from that end user AS. homed, and which carries 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.4.3 Inter-provider Border Router
Definition: Definition:
A BGP speaking router which maintains BGP sessions with An inter-provider border router is a BGP speaking router
another BGP speaking router in another provider AS. which maintains BGP sessions with another BGP speaking
Traffic transiting this router may be directed to or from router in another provider AS. Traffic transiting this
another AS that has no direct connectivity with this router may be directed to or from another AS that has no
provider's AS. direct connectivity with this 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.4.4 Intra-provider Core Router
Definition: Definition:
A provider router speaking iBGP to the provider's edge An intra-provider core router is a provider router
routers, other intraprovider core routers, or the speaking iBGP to the provider's edge routers, other intra-
provider's interprovider border routers. provider core routers, or the provider's inter-provider
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 entirely likely, however, that core Label document. It is entirely likely, however, that core Label
Switched Routers, especially in the P router role of Switched Routers, especially in the P router role of
RFC 2547 [16], may contain little or no BGP information. RFC 2547 [10], may contain little or no BGP information.
See Also: See Also:
Berkowitz, et al Expires: August 2002 8
3. Routing Data Structures 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 RIB contains all destination prefixes to which the router may
forward, and one or more currently reachable next hop addresses for forward, and one or more currently reachable next hop addresses for
them. them.
skipping to change at line 417 skipping to change at page 10, line 16
Definition: Definition:
Adj-RIB-In and Adj-RIB-Out are "views" of routing Adj-RIB-In and Adj-RIB-Out are "views" of routing
information from the perspective of individual peer information from the perspective of individual peer
routers. routers.
The Adj-RIB-In contains information advertised to the DUT The Adj-RIB-In contains information advertised to the DUT
by a specific peer. The Adj-RIB-Out contains the by a specific peer. The Adj-RIB-Out contains the
information the DUT will advertise to the peer. information the DUT will advertise to the peer.
See RFC 1771[3]. See RFC 1771[1].
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 various Adj-RIBs, after applying local policies and
the BGP route 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 not necessarily follow that these RIBs logical. It does not necessarily follow that these RIBs
are distinct and separate entities in any given are distinct and separate entities in any given
implementation. implementation.
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 Types of routes can include internal BGP, external
BGP,interface, static and IGP routes. BGP,interface, static and IGP routes.
Issues:
Measurement Units: Number of route instances. Measurement Units: Number of route instances.
See Also: Route, BGP Route, Route Instance, Adj-RIB-in, See Also: Route, BGP Route, Route Instance, Adj-RIB-in,
Adj-RIB-out,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 rejecting, and modifying routes received in
advertisements"[15]. advertisements"[9].
Discussion: Discussion:
RFC 1771 [3] further constrains policy to be within the RFC 1771 [1] further constrains policy to be within the
hop-by-hop routing paradigm. Policy is implemented using hop-by-hop routing paradigm. Policy is implemented using
filters and associated policy actions. Many AS's use filters and associated policy actions. Many AS's
routing Policy Specification Language (RPSL) [8] to formulate and document their policies using the Routing
document their policies and automatically generate Policy Specification Language (RPSL) [6] and then
configurations for the BGP processes in their routers. automatically generate configurations for the BGP
processes in their routers from the RPSL specifications.
Measurement Units: Measurement Units: Number of policies; length of policies
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 policies. outgoing 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 [3] definition of below are made with respect to RFC 1771 [1] definition of
these phases. these phases.
Incoming policies are applied in Phase 1 of the BGP Incoming policies are applied in Phase 1 of the BGP
selection process [3] to the Adj-RIB-In routes to set the selection process [1] to the Adj-RIB-In routes to set the
metric for the Phase 2 decision process. Outgoing metric for the Phase 2 decision process. Outgoing
Policies are applied in Phase 3 of the BGP process to the Policies are applied in Phase 3 of the BGP process to the
Adj-RIB-Out routes preceding route (prefix and path Adj-RIB-Out routes preceding route (prefix and path
attribute tuple) announcements to a specific peer. attribute tuple) announcements to a specific peer.
Policies in the Policy Information Base have matching and Policies in the Policy Information Base have matching and
action conditions. Common information to match include action conditions. Common information to match include
route prefixes, AS paths, communities, etc. The action on route prefixes, AS paths, communities, etc. The action on
match may be to drop the update and not pass it to the 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 Loc-RIB, or to modify the update in some way, such as
skipping to change at line 513 skipping to change at page 12, line 13
in the AS path, etc. in the AS path, etc.
The amount of policy processing (both in terms of route The amount of policy processing (both in terms of route
maps and filter/access lists) will impact the convergence maps and filter/access lists) will impact the convergence
time and properties of the distributed BGP algorithm. The time and properties of the distributed BGP algorithm. The
amount of policy processing may vary from a simple policy amount of policy processing may vary from a simple policy
which accepts all routes and sends all routes to complex which accepts all routes and sends all routes to complex
policy with a substantial fraction of the prefixes being policy with a substantial fraction of the prefixes being
filtered by filter/access lists. filtered by filter/access lists.
Measurement Units: Measurement Units: Number and length of policies
Issues: Issues:
See Also: See Also:
Berkowitz, et al Expires: August 2002 11 3.4 Forwarding Information Base (FIB)
3.4 The Forwarding Information Base (FIB)
Definition: Definition:
The Forwarding Information Base is generated from the RIB. As according to the definition in Appendix B of [4]:
The FIB is referred to in [3] as well as [5] but not "The table containing the information necessary to forward
defined in either. For the purposes of this document, the IP Datagrams is called the Forwarding Information Base.
FIB is the subset of the RIB used by the forwarding plane At minimum, this contains the interface identifier and
to make per-packet forwarding decisions. next hop information for each reachable destination
network prefix."
Discussion: Discussion:
The forwarding information base describes a database
indexing network prefixes versus router port identifiers.
The forwarding information base is distinct from the
"routing table" (the Routing Information Base or RIB),
which holds all routing information received from routing
peers. The Forwarding Information Base is generated from
the RIB. For the purposes of this document, the FIB is
effectively the subset of the RIB used by the forwarding
plane to make per-packet forwarding decisions.
Most current implementations have full, non-cached FIBs Most current implementations have full, non-cached FIBs
per router interface. All the route computation and per router interface. All the route computation and
convergence occurs before a route is downloaded into a convergence occurs before entries are downloaded into a
FIB. 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 (Network) Prefix
Definition: Definition:
A destination address specified in CIDR format. Expressed "A network prefix is . . . a contiguous set of bits at the
as prefix/length. The definition in [5] is "A network more significant end of the address that defines a set of
prefix is a contiguous set of bits at the more significant systems; host numbers select among those systems."
end of the address that defines a set of systems; host (This definition is taken directly from section 2.2.5.2,
numbers select among those systems." "Classless Inter Domain Routing (CIDR)", in [3].)
Discussion: Discussion:
A prefix is expressed as a portion of an IP address In the CIDR context, the network prefix is the network
followed by the associated mask such as 10/8. component of an IP address.
Measurement Units: N.A. Measurement Units: N.A.
Issues: Issues:
See Also See Also
Berkowitz, et al Expires: August 2002 12 4.2 Network Prefix Length
4.2 Route Definition:
The network prefix length is the number of bits used to
define the network prefix.
Discussion:
A common alternative to using a bit-wise mask to
communicate this component is the use of "slash (/)
notation." Slash notation binds the notion of network
prefix length (see 4.2) in bits to an IP address. E.g.,
141.184.128.0/17 indicates the network component of this
IPv4 address is 17 bits wide. Similar notation is used for
IPv6 network prefixes e.g. :FF02:20::/24
When referring to groups of addresses, the network prefix
length is often used as a means of describing groups of
addresses as an equivalence class. For example,
'one hundred /16 addresses' refers to 100 addresses whose
network prefix length is 16 bits.
Measurement units: bits
Issues:
See Also: network prefix
4.3 Route
Definition: Definition:
In general, a 'route' is the n-tuple In general, a 'route' is the n-tuple
<prefix, nexthop[, other non-routing protocol attributes]> <prefix, nexthop[, other non-routing protocol attributes]>
A route is not end-to-end, but is defined with respect to A route is not end-to-end, but is defined with respect to
a specific next hop that will move traffic closer to the a specific next hop that will move traffic 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 is the basic unit of information about a target
destination distilled from routing protocols. destination distilled from routing protocols.
skipping to change at line 588 skipping to change at page 14, line 28
routing protocols. With reference to the definition above, routing protocols. With reference to the definition above,
typical non-routing-protocol attributes would be typical non-routing-protocol attributes would be
associated with diffserv or 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.4 BGP Route
Definition: Definition:
The n-tuple A BGP route is an 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 BGP Attributes, such as Nexthop or AS path are defined in
in RFC 1771[3], and are the qualifying data that RFC 1771[1], where they are known as Path Attributes, and
accompanies a prefix in a BGP route. From RFC 1771: " For are the qualifying data that accompanies the network
purposes of this protocol a route is defined as a unit of prefixes in a BGP route UPDATE message. (An UPDATE message
information that pairs a destination with the attributes may contain multiple prefixes that share a common set of
of a path to that destination... A variable length attributes).
sequence of path attributes is present in every UPDATE.
Each path attribute is a triple 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> <attribute type, attribute length, attribute value>
of variable length." 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, NLRI.
Berkowitz, et al Expires: August 2002 13 4.5 BGP Route Attributes and BGP Timers
4.4 Route Instance The definitions in this section refer to items that are originally
defined in RFC 1771 [1] and are repeated here for convenience, and to
allow for some discussion beyond the definitions in RFC 1771.
4.5.1 Network Level Reachability Information (NLRI)
Definition: Definition:
A single occurrence of a route sent by a BGP Peer for a The NRLI consists of one or more network prefixes that
particular prefix. When a router has multiple peers from share all other BGP path attributes and are distributed in
which it accepts routes, routes to the same prefix may be the update portion (as opposed to the unfeasible routes
received from several peers. This is then an example of portion) of a BGP UPDATE message.
multiple route instances.
Discussion: Discussion:
Each route instance is associated with a specific peer. A Each prefix in the NLRI is combined with the (common)
specific route instance may be rejected by the BGP path attributes in the UPDATE message to form a BGP route.
selection algorithm due to local policy. The NLRI encapsulates a set of destinations to which
packets can be routed (from this point in the network)
along a common route described by the path attributes.
Measurement Units: number of route instances Measurement Units: N.A.
Issues:
See Also: Route Packing, Network Prefix, BGP Route, NLRI
4.5.2 MinRouteAdvertisementInterval (MRAI)
Definition:
(Paraphrased from 1771[1]) The MRAI timer determines the
minimum time between advertisements of routes to a
particular destination (prefix) from a single BGP device.
The timer is applied on a pre-prefix basis, although the
timer is set on a per BGP device basis.
Discussion:
Given that a BGP instance may manage in excess of 100,000
routes, RFC 1771 allows for a degree of optimization in
order to limit the number of timers needed. The NRAI does
not apply to routes received from BGP speakers in the same
AS or to explicit withdrawals.
RFC 1771 also recommends that random jitter is applied to
MRAI in an attempt to avoid synchronization effects
between the BGP instances in a network.
In this document we define RIB convergence by measuring
the time an NRAI is advertised to the DUT to the time it
is advertised from the DUT. Clearly any delay inserted by
the MRAI will have a significant effect on this
measurement.
Measurement Units: seconds.
Issues:
See Also: NLRI, BGP route
4.5.3 MinASOriginationInterval (MAOI)
Definition:
The MAOI specifies the minimum interval between
advertisements of locally originated routes from this BGP
instance.
Discussion:
Random jitter is applied to MAOI in an attempt to avoid
synchronization effects between BGP instances in a
network.
Measurement Units: seconds
Issues:
See Also: MRAI, BGP route
4.6 Route Instance
Definition:
A route instance is 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.
Discussion:
Each route instance is associated with a specific peer.
The BGP selection algorithm may reject a specific route
instance due to local policy.
Measurement Units: Number of route instances
Issues: Issues:
The number of route instances in the Adj-RIB-in bases will The number of route instances in the Adj-RIB-in bases will
vary based on the function to be performed by a router. An vary based on the function to be performed by a router. An
inter-provider router, located in the default free zone inter-provider router, located in the default free zone
will likely receive more route instances than a provider will likely receive more route instances than a provider
edge router, located closer to the end-users of the edge router, located closer to the end-users of the
network. network.
See Also: See Also:
4.5 Active Route 4.7 Active Route
Definition: Definition:
Route for which there is a FIB entry corresponding to a Route for which there is a FIB entry corresponding to a
RIB entry. RIB entry.
Discussion: Discussion:
Measurement Units: Measurement Units: Number of routes.
Issues: Issues:
See also: RIB. See also: RIB.
4.6 Unique Route 4.8 Unique Route
Definition: Definition:
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
Berkowitz, et al Expires: August 2002 14 4.9 Non-Unique Route
4.7 Non-Unique Route
Definition: Definition:
A Non-unique route is a prefix for which there is at least 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- one other route in a set including more than one Adj-RIB-
in. 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.10BGP UPDATE message
Definition: Definition:
Number of route prefixes that exist in a single Routing An UPDATE message is an advertisement of a single NLRI,
Protocol UPDATE Message either as updates (additions or possibly containing multiple prefixes, and multiple
modifications) or withdrawals. withdrawals of unfeasible routes. See RFC 1771 ([1]) for
details.
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.
Measurement Units: N.A. Measurement Units: N.A.
Issues: Issues:
See Also: route, route instance, update train. 4.11Characterization of sets of update messages
4.9 Route Mixture This section contains a sequence of definitions that build up to the
definition of an Update Train, a concept originally introduced by
Jain and Routhier [11]. This is a formalization of the sort of test
stimulus that is expected as input to a DUT running BGP. This data
could be a well-characterized, ordered and timed set of hand-crafted
BGP UPDATE packets. It could just as well be a set of BGP UPDATE
packets that have been captured from a live router.
Characterization of route mixtures and Update Trains is an open area
of research. The particular question of interest for this work is
the identification of suitable Update Trains, modeled or taken from
live traces that reflect realistic sequences of UPDATEs and their
contents.
4.11.1 Route Packing
Definition: Definition:
A characterization of the routes in a collection of Route packing is the number of route prefixes accommodated
routes. Two profiles are used to characterize a in a single Routing Protocol UPDATE Message either as
collection of routes as a route mixture: updates (additions or modifications) or withdrawals.
- 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.
Discussion: Discussion:
Route mixtures are used to simulate the normal pattern of In general, a routing protocol update may contain more
prefix distribution that is seen in real world route than one prefix. In BGP, a single UPDATE may contain two
tables and update trains. As can be seen in the analyses sets of multiple network prefixes: one set of additions
of BGP tables and traffic (e.g. [12], [13] and [14]), the and updates with identical attributes (the NLRI) and one
characterizations of the tables in the routers and the set of unfeasible routes to be withdrawn.
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: Measurement Units:
Length profile: Probability distribution function on Number of prefixes.
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: Issues:
See Also: See Also: route, BGP route, route instance, update train, NLRI.
4.10 Update Train 4.11.2 Route Mixture
Definition: Definition:
A set of Routing Protocol UPDATE messages, containing one A collection of routes such as an NLRI, a set of UPDATE
or more route prefixes, which an external router desires messages or a RIB.
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 A route mixture is the input data for the benchmark. The
TCP and BGP header processing will be imposed on the particular route mixture used as input must be selected to
receiving router that is the DUT. An update train may be suit the question being asked of the benchmark.
caused by a variety of network conditions. For example, Data containing simple route mixtures, such as 100,000 /32
an update train could be caused by an influx of UPDATES routes might test the performance limits of the BGP
from different peers that have been received and moved to device.
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 Using live data, or input that simulates live data, should
may vary from essentially zero when the packets follow improve understanding of how the BGP device will operate
each other as closely as possible up to a situation where in a live network. The data for this kind of test must be
the time between packets exceeds MIN_ADVERT_TIME. Once route mixtures that model the patterns of arriving control
the packets are so widely spaced in time they can be traffic in the live Internet.
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: To accomplish that kind of modeling it is necessary to
identify the key parameters that characterize a live
Internet route mixture. The parameters and how they
interact is an open research problem. However, we
identify the following as affecting the route mixture:
- Path length distribution
- Attribute distribution
- Prefix distribution
- Packet packing
- Probability density function of inter-arrival times of
UPDATES Each of the items above is more
complex than a singlenumber. For example, one could
consider the distribution of prefixes by AS or
distribution of prefixes by length.
Berkowitz, et al Expires: August 2002 16 Measurement Units: Probability density functions
Number of prefixes and UPDATE packets in the train,
time spacing between packets in train
Issues: Issues:
See Also: See Also: NLRI, RIB.
4.10.1 Random Update Train 4.11.3 Update Train
Definition: Definition:
An Update Train which contains: An update train is a set of Routing Protocol UPDATE
- A random number of prefixes, selected according to messages sent by a router to a BGP peer.
- 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:
This is intended to simulate the unpredictable The arrival pattern of UPDATEs can be influenced by many
asynchronous nature of the network, whereby UPDATE packets things, including TCP parameters, hold-down timers, BGP
may have arbitrary contents and be delivered at random header processing, a peer coming up or multiple peers
times. A fully random update train can be considered to sending at the same time. Network conditions such as a
be a worst case in some senses and should stress parts of local or remote peer flapping a link can also affect the
the software: It may be desirable to test a router with arrival pattern.
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 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 Measurement units:
Probability density function for the inter-arrival times
of UPDATE packets in the train.
Issues: Issues:
Characterizing the profiles of real world UPDATE trains is
a matter for future research. In order to generate
realistic UPDATE trains as test stimuli a formal
mathematical scheme or a proven heuristic is needed to
drive the selection of prefixes. Whatever mechanism is
selected it must generate Update trains that have similar
characteristics to those measured from live routers.
See also: See Also: Route Mixture, MRAI, MAOI
Berkowitz, et al Expires: August 2002 17 4.11.4 Randomness in Update Trains
4.11 Route Flap As we have seen from the previous sections, an update train used as a
test stimulus has a considerable number of parameters that can be
varied, to a greater or lesser extent, randomly and independently.
A random Update Train will contain:
- A route mixture randomized across
- NLRIs
- updates and withdrawals
- prefixes
- inter-arrival times of the UPDATEs
and possibly across other variables.
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.
It is important that the data set be randomized sufficiently to avoid
favoring one vendor's implementation over another's.
Specifically, the distribution of prefixes could be structured to
favor the internal organization of the routes in a particular
vendor's databases. This is to be avoided.
4.12Route Flap
Definition: Definition:
RIPE 210 [9] define a route flap as "the announcement and RIPE 210 [7] define a route flap as "the announcement and
withdrawal of prefixes." For our purposes we define a withdrawal of prefixes." For our purposes we define a
route flap as the rapid withdrawal/announcement or route flap as the rapid withdrawal/announcement or
announcement/withdrawal of a prefix in the Adj-RIB-in. A announcement/withdrawal of a prefix in the Adj-RIB-in. A
route flap is not a problem until a route is flapped route flap is not a problem until a route is flapped
several times in close succession. This causes negative several times in close succession. This causes negative
repercussions throughout the internet. repercussions throughout the internet.
Discussion: Discussion:
Route flapping can be considered a special and Route flapping can be considered a special and
pathological case of update trains. A practical pathological case of update trains. A practical
skipping to change at line 872 skipping to change at page 21, line 30
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 external routing convergence, and so are singled out for more
extensive 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 [6] as well as Labovitz et al[7]. operational networks is proposed in [4] as well as Labovitz et al[5].
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 categorizes similar but slightly terminology in the two papers categorizes similar but slightly
different behaviors with some overlap. We would like to apply these different behaviors with some overlap. We would like to apply these
taxonomies to categorize the tests under definition where possible, taxonomies to categorize the tests under definition where possible,
because these tests must tie in to phenomena that arise in actual because these tests must tie in to phenomena that arise in actual
networks. We avail ourselves of, or may extend, this terminology as networks. We avail ourselves of, or may extend, this terminology as
necessary for this purpose. necessary for this purpose.
A route can be changed implicitly by replacing it with another route A route can be changed implicitly by replacing it with another route
or explicitly by withdrawal followed by the introduction of a new or explicitly by withdrawal followed by the introduction of a new
route. In either case the change may be an actual change, no change, route. In either case the change may be an actual change, no change,
or a duplicate. The notation and definition of individual or a duplicate. The notation and definition of individual
categorizable route change events is adopted from [7] and given categorizable route change events is adopted from [5] and given
below. below.
Berkowitz, et al Expires: August 2002 18
a) AADiff: Implicit withdrawal of a route and replacement by a route a) AADiff: Implicit withdrawal of a route and replacement by a route
different in some path attribute. 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 route d) WADup: Explicit withdrawal of a route and replacement by a 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 To apply this taxonomy in the benchmarking context, we need both
terms to describe the sequence of events from the update train terms to describe the sequence of events from the update train
perspective, as listed above, as well as event indications in the perspective, as listed above, and event indications in the time
time domain so as to be able to measure activity from the domain so as to be able to measure activity from the perspective of
perspective of the DUT. With this in mind, we incorporate and extend the DUT. With this in mind, we incorporate and extend the definitions
the definitions of [7] to the following: of [5] to the following:
a) Tup (TDx): Route advertised to the DUT by Test Device x a) Tup (TDx): Route advertised to the DUT by Test Device x
b) Tdown(TDx): Route being withdrawn by Device x b) Tdown(TDx): Route being withdrawn by Device x
c) Tupinit(TDx): The initial announcement of a route to a unique c) Tupinit(TDx): The initial announcement of a route to a unique
prefix prefix
d) TWF(TDx): Route fail over after an explicit withdrawal. d) TWF(TDx): Route fail over after an explicit withdrawal.
But we need to take this a step further. Each of these events can 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 involve a single route, a "short" packet train, or a "full" routing
table. We further extend the notation to indicate how many routes are table. We further extend the notation to indicate how many routes are
skipping to change at line 931 skipping to change at page 22, line 33
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, which are routes memorandum uses the following descriptor events, which are routes
selected by the BGP selection process rather than simple updates: 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 Device Convergence in the Control Plane
Definition: Definition
A router is said to have converged onto a route advertised A routing device is said to have converged at the point in
to it, given that the route is the best route instance for time when the DUT has performed all actions in the control
a prefix(if multiple choices exist for that prefix), when plane needed to react to changes in topology in the
this route is advertised to its downstream peers. context of the test condition.
Berkowitz, et al Expires: August 2002 19
Discussion: Discussion:
The convergence process can be subdivided into three For example, when considering BGP convergence, a change
distinct phases: that alters the best route instance for a single prefix at
a router would be deemed to have converged when this route
is advertised to its downstream peers. Similarly, OSPF
convergence concludes when SPF calculations have been
performed and the required link states advertised onwards.
The convergence process, in general, can be subdivided
into three 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 device.
Convergence with respect to a single router can be Convergence with respect to a single device can be
- convergence with regard to data forwarding process(es)
- convergence with regard to the routing process(es), the - 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).
It is the latter, convergence with regard to the routing
process, that we describe in this and the methodology
documents.
Because we are trying to benchmark the routing protocol
performance which is only a part of the device overall,
this definition is intended (so far as is possible) to
exclude any additional time such as is needed to download
and install the forwarding information base in the data
plane. This definition should be usable for different
families of protocols.
It is of key importance to benchmark the performance of It is of key importance to benchmark the performance of
each phase of convergence separately before proceeding to each phase of convergence separately before proceeding to
a composite characterization of routing convergence, where a composite characterization of routing convergence, where
implementation- specific dependencies are allowed to implementation- specific dependencies are allowed to
interact. interact.
The preferred route instance must be unambiguous during The time resolution needed to measure the device
test setup/definition. convergence depends to some extent on the types of the
interfaces on the router. For modern routers with gigabit
or faster interfaces, an individual UPDATE may be
processed and re-advertised in very much less than a
millisecond so that time measurements must be made to a
resolution of hundreds to tens of microseconds or better.
Measurement Units: N.A. Measurement Units:
Time period.
Issues: Issues:
See Also: See Also:
6. BGP Operation Events 6. BGP Operation Events
The BGP speaker process(es) in a router restart completely, for The BGP speaker process(es) in a device restarts completely, for
example, because of operator intervention or a power failure, or a example, because of operator intervention or a power failure, or
partially because a TCP session has terminated for a particular link. fails partially because a TCP session has terminated for a particular
Until recently the BGP process would have to readvertise all relevant link. Until recently the BGP process would have to re-advertise all
routes on reestablished links potentially triggering updates across relevant routes on reestablished links potentially triggering updates
the network. Recent work is focused on limiting the volume of across the network. Recent work is focused on limiting the volume of
updates generated by short term outages by providing a graceful updates due to operational events and the amount of processing
restart mechanism [17]. resulting from these events: This work includes soft refresh[12], a
graceful restart mechanism [13] and cooperative route filtering
(e.g.[14]).
6.1 Hard reset 6.1 Hard reset
Definition: Definition:
An event which triggers a complete reinitialization of the An event which triggers a complete re-initialization of
routing tables on one or more BGP sessions, resulting in the routing tables on one or more BGP sessions, resulting
exchange of a large number of UPDATEs on one or more links in exchange of a full routing table on one or more links
to the router. to the router.
Discussion: Discussion:
Measurement Units: N/A Measurement Units: N/A
Issues: Issues:
See Also: See Also:
Berkowitz, et al Expires: August 2002 20
6.2 Soft reset 6.2 Soft reset
Definition: Definition:
An event which results in a complete or partial restart of An event which results in a complete or partial restart of
the BGP session(s) on a router, but which avoids the the BGP session(s) on a BGP device, but which avoids the
exchange of a large number of UPDATEs by maintaining state exchange of a full table by maintaining state across the
across the restart. restart.
Discussion: Discussion:
Measurement Units: N/A Measurement Units: N/A
Issues: Issues:
See Also: See Also:
7. Factors that impact the performance of the convergence process 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.
7.1 General factors affecting BGP convergence 7.1 General factors affecting device 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).
7.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 updates from the various peers will have an increasingly marked
effect on the convergence process on a router as the number of peers effect on the convergence process on a router as the number of peers
grows. grows. Increasing the number of peers also increases the processing
workload for TCP and BGP keepalives.
7.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 multiple convergence process. The number, and relative proportion, of multiple
route instances and distinct routes being added or withdrawn by each route instances and distinct routes being added or withdrawn by each
peer will affect the convergence process, as will the mix of peer will affect the convergence process, as will the mix of
overlapping route instances, and IGP routes. overlapping route instances, and IGP routes.
7.1.3 Policy processing/reconfiguration 7.1.3 Policy processing/reconfiguration
The number of routes and attributes being filtered, and set, as a The number of routes and attributes being filtered, and set, as a
fraction of the target route table size is another parameter that fraction of the target route table size is another 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 have applicable - Extensive policy: up to 100% of the total routes have applicable
policy. policy.
Berkowitz, et al Expires: August 2002 21
7.1.4 Interactions with other protocols. 7.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 criteria. duplication and the addition of timers, and route selection criteria.
Ultimately, understanding BGP4 convergence must include understanding Ultimately, understanding BGP4 convergence must include understanding
of the interactions with both the IGPs and the protocols associated of the interactions with both the IGPs and the protocols associated
with the physical media, such as Ethernet, SONET, DWDM. with the physical media, such as Ethernet, SONET, DWDM.
7.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 and to change parameters associated with it, can be considered a
matter of routing policy. matter of routing policy.
The timers are defined by RFC 2439 [4] and discussed in RIPE-210 [9]. The timers are defined by RFC 2439 [2] and discussed in RIPE-229 [7].
If this feature is in effect, it requires that the router keep If this feature is in effect, it requires that the device 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 impact on the control plane due to increased processing. In
addition, flap damping may delay the arrival of real changes in a addition, flap damping may delay the arrival of real changes in a
route, and affect convergence times route, and affect convergence times
7.1.6 Churn 7.1.6 Churn
In theory, a BGP router could receive a set of updates that In theory, a BGP device could receive a set of updates that
completely defined the Internet, and could remain in a steady state, completely defined the Internet, and could remain in a steady state,
only sending appropriate KeepAlives. In practice, the Internet will only sending appropriate keepalives. In practice, the Internet will
always be changing. always be changing.
Churn refers to control plane processor activity caused by Churn refers to control plane processor activity caused by
announcements received and sent by the router. It does not include announcements received and sent by the router. It does not include
KeepAlives. keepalives and TCP processing.
Churn is caused by both normal and pathological events. For example, Churn is caused by both normal and pathological events. For example,
if an interface of the local router goes down and the associated if an interface of the local router goes down and the associated
prefix is withdrawn, that withdrawal is a normal activity, although prefix is withdrawn, that withdrawal is a normal activity, although
it contributes to churn. If the local router receives a withdrawal it contributes to churn. If the local device receives a withdrawal
of a route it already advertises, or an announcement of a route it of a route it already advertises, or an announcement of a route it
did not previously know, and readvertises this information, again did not previously know, and re-advertises this information, again
these are normal constituents of churn. Routine updates can range these are normal constituents of churn. Routine updates can range
from single announcement or withdrawals, to announcements of an from single announcement or withdrawals, to announcements of an
entire default-free table. The latter is completely reasonable as an entire default-free table. The latter is completely reasonable as an
initialization condition. 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 [11]. The goal of flap damping is to reduce the oscillation [16]. 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 power available to the control plane, and whether the same
processor(s) are used for forwarding and for control. processor(s) are used for forwarding and for control.
7.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 Device Under
These factors are conditions of testing internal to the router Device Test (DUT), although they may affect its interactions with test
Under Test (DUT), although they may affect its interactions with test
devices. devices.
7.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 device 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 scenarios than if only accurate reflection of realistic operating scenarios than if only
control traffic is present. control traffic is present.
7.2.2 Timers 7.2.2 Timers
Settings of delay and hold-down timers at the link level as well as 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 for BGP4, can introduce or ameliorate delays. As part of a test
report, all relevant timers should be reported if they use non- report, all relevant timers should be reported if they use non-
default value. Also, any variation in standard behavior, such as default value.
overriding TCP slow start, should be documented.
7.2.3 TCP parameters underlying BGP transport 7.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
window size, Maximum segment size, timers. Slow start, max window size, maximum segment size, or timers.
7.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 [10]. The processing of the MD5 hash, particularly in routers Option [8]. The processing of the MD5 hash, particularly in devices
with a large number of BGP peers and a large amount of update traffic 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. can have an impact on the control plane of the device.
8. 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 the affecting feature, but does not consider the overall security of the
routing system. routing system.
Berkowitz, et al Expires: August 2002 23
9. References 9. References
[1] Bradner, S., "The Internet Standards Process -- Normative
Revision 3", BCP 9, RFC 2026, October 1996
[2] Bradner, S., "Key words for use in RFCs to
Indicate Requirement Levels", BCP 14, RFC 2119,
March 1997
[3] Rekhter, Y. and Li, T., "A Border Gateway [1] Rekhter, Y. and Li, T., "A Border Gateway
Protocol 4 (BGP-4)", RFC 1771, . March 1995. Protocol 4 (BGP-4)", RFC 1771, March 1995.
[4] Villamizar, C., Chandra, R. and Govindan, R., [2] Villamizar, C., Chandra, R. and Govindan, R.,
"BGP Route Flap Damping", RFC 2439, "BGP Route Flap Damping", RFC 2439,
November 1998." November 1998."
[5] Baker, F.,"Requirements for IP Version 4 [3] Baker, F.,"Requirements for IP Version 4
Routers", RFC 1812. June 1995. Routers", RFC 1812. June 1995.
[6] Ahuja, A., Jahanian, F., Bose, A. and Labovitz, [4] Ahuja, A., Jahanian, F., Bose, A. and Labovitz,
C., C.,
"An Experimental Study of Delayed Internet "An Experimental Study of Delayed Internet
Routing Convergence", RIPE 37 - Routing WG. Routing Convergence", RIPE 37 - Routing WG.
[7] Labovitz, C., Malan, G.R. and Jahanian, F., [5] Labovitz, C., Malan, G.R. and Jahanian, F.,
"Origins of Internet Routing Instability," "Origins of Internet Routing Instability,"
Infocom 99, Infocom 99.
[8] Alaettinoglu, C., Villamizar, C., Gerich, E., [6] Alaettinoglu, C., Villamizar, C., Gerich, E.,
Kessens, D., Meyer, D., Bates, T., Karrenberg, Kessens, D., Meyer, D., Bates, T., Karrenberg,
D. and Terpstra, M., "Routing Policy D. and Terpstra, M., "Routing Policy
Specification Language (RPSL)", RFC 2622, June Specification Language (RPSL)", RFC 2622, June
1999. 1999.
[9] Barber, T., Doran, S., Karrenberg, D., Panigl, [7] Barber, T., Doran, S., Karrenberg, D., Panigl,
C., Schmitz, J., "RIPE Routing-WG Recommendation C., Schmitz, J., "RIPE Routing-WG Recommendation
for coordinated route-flap damping parameters", for coordinated route-flap damping parameters",
RIPE 210, RIPE 210.
[10] Heffernan, A., "Protection of BGP Sessions via [8] Heffernan, A., "Protection of BGP Sessions via
the TCP MD5 Signature Option", RFC 2385, August the TCP MD5 Signature Option", RFC 2385, August
1998. 1998.
[11] McPhersonm, Gill, Walton, Retana, "BGP [9] Juniper Networks,"Junos(tm) Internet Software
Persistent Route Oscillation Condition", <draft- Configuration Guide Routing and Routing
ietf-idr-route-oscillation-00.txt>, Work In Protocols, Release 4.2"
progress http://www.juniper.net/techpubs/software/junos42/
swconfig-routing42/html/glossary.html#1013039.
September 2000 (and other releases).
[12] Bates, T., "The CIDR Report", [10] Rosen, E. and Rekhter, Y., "BGP/MPLS VPNs", RFC
2547, March 1999.
[11] Jain, R. and Routhier, S.A., "Packet trains --
measurement and a new model for computer network
traffic," IEEE Journal on Selected Areas in
Communication, 4(6)September 1986.
Illustrative
[12] Chen, E., "Route Refresh for BGP-4", RFC 2918,
September 2000.
[13] 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.
[14] Chen, E. and Rekhter, Y, "Cooperative Route
Filtering Capability for BGP-4",
draft-ietf-idr-route-filter-05.txt, January 2002,
work in progress.
[15] T. Anderson et al. "Requirements for Separation
of IP Control and Forwarding",
draft-ietf-forces-requirements-02.txt,
February 2002, work in progress.
[16] McPherson, Gill, Walton, Retana, "BGP Persistent
Route Oscillation Condition",
<draft-ietf-idr-route-oscillation-01.txt>,
February 2002, work In progress.
[17] Bates, T., "The CIDR Report",
http://www.employees.org/~tbates/cidr-report.html http://www.employees.org/~tbates/cidr-report.html
Internet statistics relevant to inter-domain Internet statistics relevant to inter-domain
routing updated daily routing updated daily.
Berkowitz, et al Expires: August 2002 24 [18] Smith, P. (designer), APNIC Routing Table
[13] Smith, P. (designer), APNIC Routing Table
Statistics, http://www.apnic.net/stats/bgp/, Statistics, http://www.apnic.net/stats/bgp/,
Statistics derived from a daily analysis of a Statistics derived from a daily analysis of a
core router in Japan core router in Japan.
[14] Huston, G., Telstra BGP table statistics, [19] Huston, G., Telstra BGP table statistics,
http://www.telstra.net/ops/bgp/index.html, http://www.telstra.net/ops/bgp/index.html,
Statistics derived daily from the BGP tables of Statistics derived daily from the BGP tables of
Telstra and other AS's routers 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 For Internet Draft consistency purposes only
2547, March 1999
[17] Ramachandra, S., Rekhter, Y., Fernando, R., [20] Bradner, S., "The Internet Standards Process --
Scudder, J.G. and Chen, E., Revision 3", BCP 9, RFC 2026, October 1996
"Graceful Restart Mechanism for BGP",
draft-ietf-idr-restart-02.txt, January 2002, work
in progress.
10.Acknowledgments 10.Acknowledgments
Thanks to Francis Ovenden for review and Abha Ahuja for
Thanks to Francis Ovenden and Elwyn Davies for review and Abha Ahuja encouragement. Much appreciation to Jeff Haas, Matt Richardson, and
for encouragement. Much appreciation to Jeff Haas, Matt Richardson, Shane Wright at Nexthop for comments and input. Debby Stopp and Nick
and Shane Wright at Nexthop for comments and input. Debby Stopp and Ambrose contributed the concept of route packing.
Nick Ambrose contributed the concept of route packing.
11.Author's Addresses 11.Author's Addresses
Howard Berkowitz Howard Berkowitz
Gett Communications Gett Communications
5012 S. 25th St 5012 S. 25th St
Arlington VA 22206 Arlington VA 22206
Phone: +1 703 998-5819 Phone: +1 703 998-5819
Fax: +1 703 998-5058 Fax: +1 703 998-5058
EMail: hcb@gettcomm.com EMail: hcb@gettcomm.com
skipping to change at line 1257 skipping to change at page 29, line 30
Nortel Networks Nortel Networks
London Road London Road
Harlow, Essex CM17 9NA Harlow, Essex CM17 9NA
UK UK
Phone: +44-1279-405498 Phone: +44-1279-405498
Email: elwynd@nortelnetworks.com 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
Email: kri1@earthlink.net Email: kri1@earthlink.net
Marianne Lepp Marianne Lepp
Juniper Networks Juniper Networks
51 Sawyer Road 51 Sawyer Road
skipping to change at line 1285 skipping to change at page 29, line 56
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 (2002). 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 and or assist in its implementation may be prepared, copied, published
distributed, in whole or in part, without restriction of any kind, and distributed, in whole or in part, without restriction of any
provided that the above copyright notice and this paragraph are kind, provided that the above copyright notice and this paragraph 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 BUT TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDIN BUT
NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 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.25, available from http://www.levkowetz.com/ietf/tools/rfcdiff/