draft-ietf-bmwg-conterm-05.txt   draft-ietf-bmwg-conterm-06.txt 
Benchmarking Working Group H. Berkowitz Benchmarking Working Group H. Berkowitz
Internet-Draft Gett Communications Internet-Draft Gett Communications
Expires: December 29, 2003 E. Davies (ed.) Expires: January 17, 2005 E. Davies (ed.)
Nortel Networks Nortel Networks
S. Hares S. Hares
Nexthop Technologies Nexthop Technologies
P. Krishnaswamy P. Krishnaswamy
SAIC SAIC
M. Lepp M. Lepp
Consultant Consultant
June 30, 2003 July 19, 2004
Terminology for Benchmarking BGP Device Convergence in the Control Terminology for Benchmarking BGP Device Convergence in the Control
Plane Plane
draft-ietf-bmwg-conterm-05.txt draft-ietf-bmwg-conterm-06.txt
Status of this Memo Status of this Memo
This document is an Internet-Draft and is in full conformance with By submitting this Internet-Draft, I certify that any applicable
all provisions of Section 10 of RFC2026. patent or other IPR claims of which I am aware have been disclosed,
and any of which I become aware will be disclosed, in accordance with
RFC 3668.
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
groups may also distribute working documents as Internet-Drafts. other 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
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
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 http:// The list of current Internet-Drafts can be accessed at
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.
This Internet-Draft will expire on December 29, 2003. This Internet-Draft will expire on January 17, 2005.
Copyright Notice Copyright Notice
Copyright (C) The Internet Society (2003). All Rights Reserved. Copyright (C) The Internet Society (2004). All Rights Reserved.
Abstract Abstract
This draft establishes terminology to standardize the description of This document establishes terminology to standardize the description
benchmarking methodology for measuring eBGP convergence in the of 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 multiple interacting BGP devices. This control plane information and multiple interacting BGP devices. This
terminology is applicable to both IPv4 and IPv6. Illustrative terminology is applicable to both IPv4 and IPv6. Illustrative
examples of each version are included where relevant. examples of each version are included where relevant.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1 Overview and Roadmap . . . . . . . . . . . . . . . . . . . . 4 1.1 Overview and Roadmap . . . . . . . . . . . . . . . . . . . 4
1.2 Definition Format . . . . . . . . . . . . . . . . . . . . . 5 1.2 Definition Format . . . . . . . . . . . . . . . . . . . . 5
2. Components and Characteristics of Routing Information . . . 6 2. Components and Characteristics of Routing Information . . . . 6
2.1 (Network) Prefix . . . . . . . . . . . . . . . . . . . . . . 6 2.1 (Network) Prefix . . . . . . . . . . . . . . . . . . . . . 6
2.2 Network Prefix Length . . . . . . . . . . . . . . . . . . . 6 2.2 Network Prefix Length . . . . . . . . . . . . . . . . . . 6
2.3 Route . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 Route . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4 BGP Route . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.4 BGP Route . . . . . . . . . . . . . . . . . . . . . . . . 7
2.5 Network Level Reachability Information (NLRI) . . . . . . . 8 2.5 Network Level Reachability Information (NLRI) . . . . . . 7
2.6 BGP UPDATE Message . . . . . . . . . . . . . . . . . . . . . 8 2.6 BGP UPDATE Message . . . . . . . . . . . . . . . . . . . . 8
3. Routing Data Structures and Route Categories . . . . . . . . 9 3. Routing Data Structures and Route Categories . . . . . . . . . 9
3.1 Routing Information Base (RIB) . . . . . . . . . . . . . . . 9 3.1 Routing Information Base (RIB) . . . . . . . . . . . . . . 9
3.1.1 Adj-RIB-In and Adj-RIB-Out . . . . . . . . . . . . . . . . . 9 3.1.1 Adj-RIB-In and Adj-RIB-Out . . . . . . . . . . . . . . 9
3.1.2 Loc-RIB . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.1.2 Loc-RIB . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 Routing Policy . . . . . . . . . . . . . . . . . . . . . . . 10 3.2 Prefix Filtering . . . . . . . . . . . . . . . . . . . . . 10
3.3 Routing Policy Information Base . . . . . . . . . . . . . . 10 3.3 Routing Policy . . . . . . . . . . . . . . . . . . . . . . 10
3.4 Forwarding Information Base (FIB) . . . . . . . . . . . . . 11 3.4 Routing Policy Information Base . . . . . . . . . . . . . 10
3.5 BGP Instance . . . . . . . . . . . . . . . . . . . . . . . . 12 3.5 Forwarding Information Base (FIB) . . . . . . . . . . . . 11
3.6 BGP Device . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.6 BGP Instance . . . . . . . . . . . . . . . . . . . . . . . 12
3.7 BGP Session . . . . . . . . . . . . . . . . . . . . . . . . 13 3.7 BGP Device . . . . . . . . . . . . . . . . . . . . . . . . 12
3.8 Active BGP Session . . . . . . . . . . . . . . . . . . . . . 13 3.8 BGP Session . . . . . . . . . . . . . . . . . . . . . . . 12
3.9 BGP Peer . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.9 Active BGP Session . . . . . . . . . . . . . . . . . . . . 12
3.10 BGP Neighbor . . . . . . . . . . . . . . . . . . . . . . . . 14 3.10 BGP Peer . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.11 MinRouteAdvertisementInterval (MRAI) . . . . . . . . . . . . 14 3.11 BGP Neighbor . . . . . . . . . . . . . . . . . . . . . . . 13
3.12 MinASOriginationInterval (MAOI) . . . . . . . . . . . . . . 15 3.12 MinRouteAdvertisementInterval (MRAI) . . . . . . . . . . . 13
3.13 Active Route . . . . . . . . . . . . . . . . . . . . . . . . 15 3.13 MinASOriginationInterval (MAOI) . . . . . . . . . . . . . 14
3.14 Unique Route . . . . . . . . . . . . . . . . . . . . . . . . 16 3.14 Active Route . . . . . . . . . . . . . . . . . . . . . . . 14
3.15 Non-Unique Route . . . . . . . . . . . . . . . . . . . . . . 16 3.15 Unique Route . . . . . . . . . . . . . . . . . . . . . . . 14
3.16 Route Instance . . . . . . . . . . . . . . . . . . . . . . . 16 3.16 Non-Unique Route . . . . . . . . . . . . . . . . . . . . . 15
4. Constituent Elements of a Router or Network of Routers . . . 18 3.17 Route Instance . . . . . . . . . . . . . . . . . . . . . . 15
4.1 Default Route, Default Free Table, and Full Table . . . . . 18 4. Constituent Elements of a Router or Network of Routers . . . . 16
4.1.1 Default Route . . . . . . . . . . . . . . . . . . . . . . . 18 4.1 Default Route, Default Free Table, and Full Table . . . . 16
4.1.2 Default Free Routing Table . . . . . . . . . . . . . . . . . 18 4.1.1 Default Route . . . . . . . . . . . . . . . . . . . . 16
4.1.3 Full Default Free Table . . . . . . . . . . . . . . . . . . 19 4.1.2 Default Free Routing Table . . . . . . . . . . . . . . 16
4.1.4 Default-Free Zone . . . . . . . . . . . . . . . . . . . . . 20 4.1.3 Full Default Free Table . . . . . . . . . . . . . . . 17
4.1.5 Full Provider-Internal Table . . . . . . . . . . . . . . . . 20 4.1.4 Default-Free Zone . . . . . . . . . . . . . . . . . . 17
4.2 Classes of BGP-Speaking Routers . . . . . . . . . . . . . . 20 4.1.5 Full Provider-Internal Table . . . . . . . . . . . . . 17
4.2.1 Provider Edge Router . . . . . . . . . . . . . . . . . . . . 20 4.2 Classes of BGP-Speaking Routers . . . . . . . . . . . . . 18
4.2.2 Subscriber Edge Router . . . . . . . . . . . . . . . . . . . 21 4.2.1 Provider Edge Router . . . . . . . . . . . . . . . . . 18
4.2.3 Inter-provider Border Router . . . . . . . . . . . . . . . . 21 4.2.2 Subscriber Edge Router . . . . . . . . . . . . . . . . 18
4.2.4 Core Router . . . . . . . . . . . . . . . . . . . . . . . . 22 4.2.3 Inter-provider Border Router . . . . . . . . . . . . . 19
5. Characterization of Sets of Update Messages . . . . . . . . 23 4.2.4 Core Router . . . . . . . . . . . . . . . . . . . . . 19
5.1 Route Packing . . . . . . . . . . . . . . . . . . . . . . . 23 5. Characterization of Sets of Update Messages . . . . . . . . . 20
5.2 Route Mixture . . . . . . . . . . . . . . . . . . . . . . . 23 5.1 Route Packing . . . . . . . . . . . . . . . . . . . . . . 20
5.3 Update Train . . . . . . . . . . . . . . . . . . . . . . . . 24 5.2 Route Mixture . . . . . . . . . . . . . . . . . . . . . . 20
5.4 Randomness in Update Trains . . . . . . . . . . . . . . . . 25 5.3 Update Train . . . . . . . . . . . . . . . . . . . . . . . 21
5.5 Route Flap . . . . . . . . . . . . . . . . . . . . . . . . . 26 5.4 Randomness in Update Trains . . . . . . . . . . . . . . . 22
6. Route Changes and Convergence . . . . . . . . . . . . . . . 27 5.5 Route Flap . . . . . . . . . . . . . . . . . . . . . . . . 22
6.1 Route Change Events . . . . . . . . . . . . . . . . . . . . 27 6. Route Changes and Convergence . . . . . . . . . . . . . . . . 23
6.2 Device Convergence in the Control Plane . . . . . . . . . . 28 6.1 Route Change Events . . . . . . . . . . . . . . . . . . . 23
7. BGP Operation Events . . . . . . . . . . . . . . . . . . . . 30 6.2 Device Convergence in the Control Plane . . . . . . . . . 24
7.1 Hard Reset . . . . . . . . . . . . . . . . . . . . . . . . . 30 7. BGP Operation Events . . . . . . . . . . . . . . . . . . . . . 26
7.2 Soft Reset . . . . . . . . . . . . . . . . . . . . . . . . . 30 7.1 Hard Reset . . . . . . . . . . . . . . . . . . . . . . . . 26
7.2 Soft Reset . . . . . . . . . . . . . . . . . . . . . . . . 26
8. Factors that Impact the Performance of the Convergence 8. Factors that Impact the Performance of the Convergence
Process . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Process . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
8.1 General Factors Affecting Device Convergence . . . . . . . . 32 8.1 General Factors Affecting Device Convergence . . . . . . . 27
8.1.1 Number of Peers . . . . . . . . . . . . . . . . . . . . . . 32 8.1.1 Number of Peers . . . . . . . . . . . . . . . . . . . 27
8.1.2 Number of Routes per Peer . . . . . . . . . . . . . . . . . 32 8.1.2 Number of Routes per Peer . . . . . . . . . . . . . . 27
8.1.3 Policy Processing/Reconfiguration . . . . . . . . . . . . . 32 8.1.3 Policy Processing/Reconfiguration . . . . . . . . . . 27
8.1.4 Interactions with Other Protocols . . . . . . . . . . . . . 32 8.1.4 Interactions with Other Protocols . . . . . . . . . . 27
8.1.5 Flap Damping . . . . . . . . . . . . . . . . . . . . . . . . 33 8.1.5 Flap Damping . . . . . . . . . . . . . . . . . . . . . 28
8.1.6 Churn . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 8.1.6 Churn . . . . . . . . . . . . . . . . . . . . . . . . 28
8.2 Implementation-specific and other Factors Affecting BGP 8.2 Implementation-specific and other Factors Affecting
Convergence . . . . . . . . . . . . . . . . . . . . . . . . 34 BGP Convergence . . . . . . . . . . . . . . . . . . . . . 28
8.2.1 Forwarded Traffic . . . . . . . . . . . . . . . . . . . . . 34 8.2.1 Forwarded Traffic . . . . . . . . . . . . . . . . . . 29
8.2.2 Timers . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 8.2.2 Timers . . . . . . . . . . . . . . . . . . . . . . . . 29
8.2.3 TCP Parameters Underlying BGP Transport . . . . . . . . . . 34 8.2.3 TCP Parameters Underlying BGP Transport . . . . . . . 29
8.2.4 Authentication . . . . . . . . . . . . . . . . . . . . . . . 34 8.2.4 Authentication . . . . . . . . . . . . . . . . . . . . 29
9. Security Considerations . . . . . . . . . . . . . . . . . . 35 9. Security Considerations . . . . . . . . . . . . . . . . . . . 30
10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . 36 10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . 31
Normative References . . . . . . . . . . . . . . . . . . . . 37 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 32
Informative References . . . . . . . . . . . . . . . . . . . 38 11.1 Normative References . . . . . . . . . . . . . . . . . . . . 32
For Internet Draft consistency purposes only . . . . . . . . 39 11.2 Informative References . . . . . . . . . . . . . . . . . . . 33
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . 39 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 33
Intellectual Property and Copyright Statements . . . . . . . 41 Intellectual Property and Copyright Statements . . . . . . . . 35
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 (see RFC1771 [1]). It is the first that instantiate BGP functionality (see 'A Border Gateway Protocol 4
part of a two document series, of which the subsequent document will (BGP-4)'[RFC1771] referred to as RFC 1771 in the remainder of the
contain the associated tests and methodology. This terminology is document). It is the first part of a two document series, of which
applicable to both IPv4 and IPv6. Illustrative examples of each the subsequent document will contain the associated tests and
version are included where relevant. Although IPv6 will require the methodology. This terminology is applicable to both IPv4 and IPv6.
use of MP-BGP, we will not deal with issues related to RFC 2283 [17] Illustrative examples of each version are included where relevant.
in this draft. However this document is primarily targeted for BGP-4 in IPv4
networks. IPv6 will require the use of MP-BGP[RFC2858] as described
in RFC 2545[RFC2545] but this document will not address terminology
or issues specific to these extensions of BGP-4. Also terminology
and issues specific to the extensions of BGP which support VPNs as
described in RFC 2547[RFC2547] are out of scope for this document.
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:
o The principal objective is to derive methodologies to standardize o 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.
o It is necessary to remove ambiguity from many frequently used o 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.
o As convergence characterization is a complex process, it is o 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 For path vector protocols, such as BGP, the primary initial focus
will therefore be on network and system control-plane activity will therefore be on network and system control-plane activity
consisting of the arrival, processing, and propagation of routing consisting of the arrival, processing, and propagation of routing
information. information.
skipping to change at page 4, line 36 skipping to change at page 4, line 38
o As convergence characterization is a complex process, it is o 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 For path vector protocols, such as BGP, the primary initial focus
will therefore be on network and system control-plane activity will therefore be on network and system control-plane activity
consisting of the arrival, processing, and propagation of routing consisting of the arrival, processing, and propagation of routing
information. information.
We note that for testing purposes all optional parameters should be We note that for testing purposes all optional parameters SHOULD be
turned off. All variable parameters should be in their default turned off. All variable parameters SHOULD be at their default
setting unless specified by the test. setting unless specified by the test.
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
Multiprotocol Extensions for BGP-4, policy processing, simultaneous Multiprotocol Extensions for BGP-4, policy processing, simultaneous
traffic on the control and data paths within the Cevice Under Test traffic on the control and data paths within the Device Under Test
(DUT), and other realistic performance modifiers. Convergence of (DUT), and other realistic performance modifiers. Convergence of
Interior Gateway Protocols will also be considered in separate Interior Gateway Protocols will also be considered in separate
drafts. 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
take into account all distinct stages and aspects of BGP take into account all distinct stages and aspects of BGP
functionality. This requires that the relevant terms and metrics be functionality. This requires that the relevant terms and metrics be
as specifically defined as possible. Such definition is the goal of as specifically defined as possible. Such definition is the goal of
skipping to change at page 5, line 8 skipping to change at page 5, line 10
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
take into account all distinct stages and aspects of BGP take into account all distinct stages and aspects of BGP
functionality. This requires that the relevant terms and metrics be functionality. This requires that the relevant terms and metrics be
as specifically defined as possible. Such definition is the goal of as specifically defined as possible. Such definition is the goal of
this document. this document.
The necessary definitions are classified into separate categories: The necessary definitions are classified into separate categories:
o Components and characteristics of routing information o Components and characteristics of routing information
o Routing data structures and route categories o Routing data structures and route categories
o Descriptions of the constituent elements of a network or a router o Descriptions of the constituent elements of a network or a router
that is undergoing convergence that is undergoing convergence
o Characterization of sets of update messages, types of route change o Characterization of sets of update messages, types of route change
events, as well as some events specific to BGP operation events, as well as some events specific to BGP operation
o Descriptions of factors that impact the performance of o Descriptions of factors that impact the performance of
convergence processes convergence processes
1.2 Definition Format 1.2 Definition Format
The definition format is equivalent to that defined in [3], and is The definition format is equivalent to that defined in 'Requirements
repeated here for convenience: for IP Version 4 Routers'[RFC1812], and 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:
One or more sentences forming the body of the definition. 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 procedures. restrictions that there might be on measurement procedures.
Measurement units: Measurement units:
The units used to report measurements of this term, if applicable. The units used to report measurements of this term.
This item may not be applicable (N.A.).
Issues: Issues:
List of issues or conditions that could affect this term. List of issues or conditions that could affect this term.
See Also: See Also:
List of related terms that are relevant to the definition or List of related terms that are relevant to the definition or
discussion of this term. discussion of this term.
2. Components and Characteristics of Routing Information 2. Components and Characteristics of Routing Information
2.1 (Network) Prefix 2.1 (Network) Prefix
Definition: Definition:
"A network prefix is a contiguous set of bits at the more "A network prefix is a contiguous set of bits at the more
skipping to change at page 6, line 14 skipping to change at page 6, line 14
2. Components and Characteristics of Routing Information 2. Components and Characteristics of Routing Information
2.1 (Network) Prefix 2.1 (Network) Prefix
Definition: Definition:
"A network prefix is a contiguous set of bits at the more "A network prefix is a contiguous set of bits at the more
significant end of the address that collectively designates the significant end of the address that collectively designates the
set of systems within a network; host numbers select among those set of systems within a network; host numbers select among those
systems." (This definition is taken directly from section 2.2.5.2, systems." (This definition is taken directly from section 2.2.5.2,
"Classless Inter Domain Routing (CIDR)", in [3].) "Classless Inter Domain Routing (CIDR)", in RFC 1812.)
Discussion: Discussion:
In the CIDR context, the network prefix is the network component In the CIDR context, the network prefix is the network component
of an IP address. of an IP address.
In IPv4 systems the network component of a complete address is
known as the 'network part' and the remaining part of the address
is known as the 'host part'.
In IPv6 systems, the network component of a complete address is
known as the 'subnet prefix' and the remaining part is known as
the 'interface identifier'.
Measurement Units: N.A. Measurement Units: N.A.
Issues: Issues:
See Also: See Also:
2.2 Network Prefix Length 2.2 Network Prefix Length
Definition: Definition:
The network prefix length is the number of bits out of the total The network prefix length is the number of bits, out of the total
available in the address field, used to define the network prefix. constituting the address field, that defines the network prefix
portion of the address.
Discussion: Discussion:
A common alternative to using a bit-wise mask to communicate this A common alternative to using a bit-wise mask to communicate this
component is the use of "slash (/) notation." Slash notation binds component is the use of "slash (/) notation." Slash notation binds
the notion of network prefix length in bits to an IP address. the notion of network prefix length in bits to an IP address.
E.g., 141.184.128.0/17 indicates the network component of this 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 IPv4 address is 17 bits wide. Similar notation is used for IPv6
network prefixes e.g. 2001:db8:719f::/48 network prefixes e.g. 2001:db8:719f::/48
When referring to groups of addresses, the network prefix length When referring to groups of addresses, the network prefix length
is often used as a means of describing groups of addresses as an is often used as a means of describing groups of addresses as an
equivalence class. For example, 'one hundred /16 addresses' equivalence class. For example, 'one hundred /16 addresses'
refers to 100 addresses whose network prefix length is 16 bits. refers to 100 addresses whose network prefix length is 16 bits.
Measurement units: bits Measurement units: bits
Issues: Issues:
See Also: Network Prefix
See Also: network prefix
2.3 Route 2.3 Route
Definition: Definition:
In general, a 'route' is the n-tuple In general, a 'route' is the n-tuple
<prefix, nexthop [, other routing or non-routing protocol <prefix, nexthop [, other routing or non-routing protocol
attributes]> attributes]>
A route is not end-to-end, but is defined with respect to a A route is not end-to-end, but is defined with respect to a
specific next hop that should take packets on the next step specific next hop that should take packets on the next step
towards their destination as defined by the prefix. In this usage, towards their destination as defined by the prefix. In this
a route is the basic unit of information about a target usage, a route is the basic unit of information about a target
destination distilled from routing protocols. destination distilled from routing protocols.
Discussion: Discussion:
This term refers to the concept of a route common to all routing This term refers to the concept of a route common to all routing
protocols. With reference to the definition above, typical protocols. With reference to the definition above, typical
non-routing-protocol attributes would be associated with diffserv non-routing-protocol attributes would be associated with diffserv
or traffic engineering. or traffic engineering.
Measurement Units: N.A. Measurement Units: N.A.
Issues: None. Issues: None.
See Also: BGP route See Also: BGP route
2.4 BGP Route 2.4 BGP Route
Definition: Definition:
A BGP route is an n-tuple A BGP route is an n-tuple
<prefix, nexthop, ASpath [, other BGP attributes]>. <prefix, nexthop, ASpath [, other BGP attributes]>.
Discussion: Discussion:
BGP Attributes, such as Nexthop or AS path are defined in RFC BGP Attributes, such as Nexthop or AS path are defined in RFC
1771[1], where they are known as Path Attributes, and are the 1771, where they are known as Path Attributes, and are the
qualifying data that define the route. qualifying data that define the route.
From RFC 1771: "For purposes of this protocol a route is defined From RFC 1771: "For purposes of this protocol a route is defined
as a unit of information that pairs a destination with the as a unit of information that pairs a destination with the
attributes of a path to that destination" attributes of a path to that destination"
Measurement Units: N.A. Measurement Units: N.A.
Issues: Issues:
See Also: Route, prefix, Adj-RIB-in, NLRI. See Also: Route, prefix, Adj-RIB-in, NLRI.
2.5 Network Level Reachability Information (NLRI) 2.5 Network Level Reachability Information (NLRI)
Definition: Definition:
The NLRI consists of one or more network prefixes with the same The NLRI consists of one or more network prefixes with the same
set of path attributes. set of path attributes.
Discussion: Discussion:
Each prefix in the NLRI is combined with the (common) path Each prefix in the NLRI is combined with the (common) path
attributes to form a BGP route. The NLRI encapsulates a set of attributes to form a BGP route. The NLRI encapsulates a set of
destinations to which packets can be routed (from this point in destinations to which packets can be routed (from this point in
the network) along a common route described by the path the network) along a common route described by the path
attributes. attributes.
Measurement Units: N.A. Measurement Units: N.A.
Issues: Issues:
See Also: Route Packing, Network Prefix, BGP Route, NLRI See Also: Route Packing, Network Prefix, BGP Route, NLRI
2.6 BGP UPDATE Message 2.6 BGP UPDATE Message
Definition: Definition:
An UPDATE message contains an advertisement of a single NLRI An UPDATE message contains an advertisement of a single NLRI
field, possibly containing multiple prefixes, and multiple field, possibly containing multiple prefixes, and multiple
withdrawals of unfeasible routes. See RFC 1771 ([1]) for details. withdrawals of unfeasible routes. See RFC 1771 for details.
Discussion: Discussion:
From RFC 1771: "A variable length sequence of path attributes is From RFC 1771: "A variable length sequence of path attributes is
present in every UPDATE. Each path attribute is a triple present in every UPDATE. Each path attribute is a triple
<attribute type, attribute length, attribute value> of variable <attribute type, attribute length, attribute value> of variable
length." length."
Measurement Units: N.A. Measurement Units: N.A.
See Also See Also
3. Routing Data Structures and Route Categories 3. Routing Data Structures and Route Categories
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
physically) distinct databases, each of which is enumerated below. physically) distinct databases, each of which is enumerated below.
The RIB contains all destination prefixes to which the router may The 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
skipping to change at page 9, line 28 skipping to change at page 9, line 28
a basic set of route selection criteria relevant in an all-source a basic set of route selection criteria relevant in an all-source
context. Many implementations impose additional criteria. A common context. Many implementations impose additional criteria. A common
implementation-specific criterion is the preference given to implementation-specific criterion is the preference given to
different routing information sources. 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 routing information from Adj-RIB-In and Adj-RIB-Out are "views" of routing information from
the perspective of individual peer routers. the perspective of individual peer routers.
The Adj-RIB-In contains information advertised to the DUT by a The Adj-RIB-In contains information advertised to the DUT by a
specific peer. The Adj-RIB-Out contains the information the DUT specific peer. The Adj-RIB-Out contains the information the DUT
will advertise to the peer. will advertise to the peer.
See RFC 1771.
See RFC 1771[1].
Discussion: Discussion:
Issues: Issues:
Measurement Units: Number of route instances Measurement Units: Number of route instances
See Also: See Also:
Route, BGP Route, Route Instance, Loc-RIB, FIB Route, BGP Route, Route Instance, Loc-RIB, FIB
3.1.2 Loc-RIB 3.1.2 Loc-RIB
Definition: Definition:
The Loc-RIB contains the set of best routes selected from the The Loc-RIB contains the set of best routes selected from the
various Adj-RIBs, after applying local policies and the BGP route various Adj-RIBs, after applying local policies and the BGP route
selection algorithm. selection algorithm.
Discussion: Discussion:
The separation implied between the various RIBs is logical. It The separation implied between the various RIBs is logical. It
does not necessarily follow that these RIBs are distinct and does not necessarily follow that these RIBs are distinct and
separate entities in any given implementation. separate entities in any given implementation.
Types of routes that need to be considered include internal BGP, Types of routes that need to be considered include internal BGP,
external BGP, interface, static and IGP routes. external BGP, interface, static and IGP routes.
Issues: Issues:
Measurement Units: Number of routes Measurement Units: Number of routes
See Also: See Also:
Route, BGP Route, Route Instance, Adj-RIB-in, Adj-RIB-out, FIB Route, BGP Route, Route Instance, Adj-RIB-in, Adj-RIB-out, FIB
3.2 Routing Policy 3.2 Prefix Filtering
Definition: Definition:
Routing Policy is "the ability to define conditions for accepting, Prefix Filtering is a technique for eliminating routes from
rejecting, and modifying routes received in advertisements"[9]. consideration as candidates for entry into a RIB by matching the
network prefix in a BGP Route against a list of network prefixes.
Discussion:
A BGP Route is eliminated if, for any filter prefix from the list,
the Route prefix length is equal to or longer than the filter
prefix length and the most significant bits of the two prefixes
match over the length of the filter prefix. See 'Cooperative
Route Filtering Capability for BGP-4'[I-D.ietf-idr-route-filter]
for examples of usage.
Measurement Units: Number of filter prefixes; lengths of prefixes
Issues:
See Also: BGP Route, Network Prefix, Network Prefix Length, Routing
Policy, Routing Policy Information Base.
3.3 Routing Policy
Definition:
Routing Policy is "the ability to define conditions for accepting,
rejecting, and modifying routes received in
advertisements"[GLSSRY].
Discussion: Discussion:
RFC 1771 [1] further constrains policy to be within the hop-by-hop RFC 1771 further constrains policy to be within the hop-by-hop
routing paradigm. Policy is implemented using filters and routing paradigm. Policy is implemented using filters and
associated policy actions. Many AS's formulate and document their associated policy actions such as Prefix Filtering. Many AS's
policies using the Routing Policy Specification Language (RPSL) formulate and document their policies using the Routing Policy
[6] and then automatically generate configurations for the BGP Specification Language (RPSL)[RFC2622] and then automatically
processes in their routers from the RPSL specifications. generate configurations for the BGP processes in their routers
from the RPSL specifications.
Measurement Units: Number of policies; length of policies Measurement Units: Number of policies; length of policies
Issues: Issues:
See Also: Routing Policy Information Base, Prefix Filtering.
See Also: Routing Policy Information Base. 3.4 Routing Policy Information Base
3.3 Routing Policy Information Base
Definition: Definition:
A routing policy information base is the set of incoming and A routing 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 below are All references to the phase of the BGP selection process below are
made with respect to RFC 1771 [1] definition of these phases. made with respect to RFC 1771 definition of these phases.
Incoming policies are applied in Phase 1 of the BGP selection Incoming policies are applied in Phase 1 of the BGP selection
process [1] to the Adj-RIB-In routes to set the metric for the process to the Adj-RIB-In routes to set the metric for the Phase 2
Phase 2 decision process. Outgoing Policies are applied in Phase decision process. Outgoing Policies are applied in Phase 3 of the
3 of the BGP process to the Adj-RIB-Out routes preceding route BGP process to the Adj-RIB-Out routes preceding route (prefix and
(prefix and path attribute tuple) announcements to a specific path attribute tuple) announcements to a specific peer.
peer.
Policies in the Policy Information Base have matching and action Policies in the Policy Information Base have matching and action
conditions. Common information to match include route prefixes, conditions. Common information to match include route prefixes,
AS paths, communities, etc. The action on match may be to drop AS paths, communities, etc. The action on match may be to drop
the update and not pass it to the Loc-RIB, or to modify the update the update and not pass it to the Loc-RIB, or to modify the update
in some way, such as changing local preference (on input) or MED in some way, such as changing local preference (on input) or MED
(on output), adding or deleting communities, prepending the (on output), adding or deleting communities, prepending the
current AS in the AS path, etc. current AS in the AS path, etc.
The amount of policy processing (both in terms of route maps and The amount of policy processing (both in terms of route maps and
filter/access lists) will impact the convergence time and filter/access lists) will impact the convergence time and
properties of the distributed BGP algorithm. The amount of policy properties of the distributed BGP algorithm. The amount of policy
processing may vary from a simple policy which accepts all routes processing may vary from a simple policy which accepts all routes
and sends all routes to complex policy with a substantial fraction and sends all routes to complex policy with a substantial fraction
of the prefixes being filtered by filter/access lists. of the prefixes being filtered by filter/access lists.
Measurement Units: Number and length of policies Measurement Units: Number and length of policies
Issues: Issues:
See Also: See Also:
3.4 Forwarding Information Base (FIB) 3.5 Forwarding Information Base (FIB)
Definition: Definition:
As according to the definition in Appendix B of [4]: "The table As according to the definition in Appendix B of RIPE-37[RIPE37]:
containing the information necessary to forward IP Datagrams is "The table containing the information necessary to forward IP
called the Forwarding Information Base. At minimum, this contains Datagrams is called the Forwarding Information Base. At minimum,
the interface identifier and next hop information for each this contains the interface identifier and next hop information
reachable destination network prefix." for each reachable destination network prefix."
Discussion: Discussion:
The forwarding information base describes a database indexing The forwarding information base describes a database indexing
network prefixes versus router port identifiers. network prefixes versus router port identifiers.
The forwarding information base is distinct from the "routing The forwarding information base is distinct from the "routing
table" (the Routing Information Base or RIB), which holds all table" (the Routing Information Base or RIB), which holds all
routing information received from routing peers. It is a data routing information received from routing peers. It is a data
plane construct and used for the forwarding of each packet. The plane construct and used for the forwarding of each packet. The
Forwarding Information Base is generated from the RIB. For the Forwarding Information Base is generated from the RIB. For the
purposes of this document, the FIB is effectively the subset of purposes of this document, the FIB is effectively the subset of
the RIB used by the forwarding plane to make per-packet forwarding the RIB used by the forwarding plane to make per-packet forwarding
decisions. decisions.
Most current implementations have full, non-cached FIBs per router Most current implementations have full, non-cached FIBs per router
interface. All the route computation and convergence occurs before interface. All the route computation and convergence occurs
entries are downloaded into a FIB. before entries are downloaded into a FIB.
Measurement units: N.A. Measurement units: N.A.
Issues: Issues:
See Also: Route, RIB See Also: Route, RIB
3.5 BGP Instance 3.6 BGP Instance
Definition: Definition:
A BGP instance is a process with a single Loc-RIB. A BGP instance is a process with a single Loc-RIB.
Discussion: Discussion:
For example, a BGP instance would run in routers or test For example, a BGP instance would run in routers or test
equipment. A test generator acting as multiple peers will equipment. A test generator acting as multiple peers will
typically run more than one instance of BGP. A router would typically run more than one instance of BGP. A router would
typically run a single instance. typically run a single instance.
Measurement units: N/A Measurement units: N/A
Issues: Issues:
See Also: See Also:
3.6 BGP Device 3.7 BGP Device
Definition: Definition:
A BGP device is a system that has one or more BGP instances A BGP device is a system that has one or more BGP instances
running on it, each of which is responsible for executing the BGP running on it, each of which is responsible for executing the BGP
state machine. state machine.
Discussion: Discussion:
We have chosen to use "device" as the general case, to deal with 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 the understood (e.g. [GLSSRY]) and yet-to-be-invented cases where
control processing may be separate from forwarding [12]. A BGP the control processing may be separate from forwarding [RFC2918].
device may be a traditional router, a route server, a BGP-aware A BGP device may be a traditional router, a route server, a
traffic steering device or a non forwarding route reflector. BGP BGP-aware traffic steering device or a non forwarding route
instances such as route reflectors or servers, for example, never reflector. BGP instances such as route reflectors or servers, for
forwards traffic, so forwarding-based measurements would be example, never forwards traffic, so forwarding-based measurements
meaningless for it. would be meaningless for it.
Measurement units: N/A Measurement units: N/A
Issues: Issues:
See Also: See Also:
3.7 BGP Session 3.8 BGP Session
Definition: Definition:
A BGP session is a session between two BGP instances. A BGP session is a session between two BGP instances.
Discussion: Discussion:
Measurement units: N/A Measurement units: N/A
Issues: Issues:
See Also: See Also:
3.8 Active BGP Session 3.9 Active BGP Session
Definition: Definition:
An active BGP session is one which is in the established state. An active BGP session is one which is in the established state.
(See RFC 1771 [1]). (See RFC 1771).
Discussion: Discussion:
Measurement units: N/A Measurement units: N/A
Issues: Issues:
See Also: See Also:
3.9 BGP Peer 3.10 BGP Peer
Definition: Definition:
A BGP peer is another BGP instance to which the DUT is in the A BGP peer is another BGP instance to which the DUT is in the
Established state. (See RFC 1771 [1]). Established state. (See RFC 1771).
Discussion: Discussion:
In the test scenarios in the methodology discussion that will In the test scenarios in the methodology discussion that will
follow this draft, peers send BGP advertisements to the DUT and follow this document, peers send BGP advertisements to the DUT and
receive DUT-originated advertisements. We recommend that the receive DUT-originated advertisements. We recommend that the
peering relation be established before tests are begun. It might peering relation be established before tests are begun. It might
also be interesting to measure the time required to reach the also be interesting to measure the time required to reach the
established state. established state.
This is a protocol-specific definition, not to be confused with This is a protocol-specific definition, not to be confused with
another frequent usage, which refers to the business/economic another frequent usage, which refers to the business/economic
definition for the exchange of routes without financial definition for the exchange of routes without financial
compensation. compensation.
It is worth noting that a BGP peer, by this definition is It is worth noting that a BGP peer, by this definition is
associated with a BGP peering session, and there may be more than 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 one such active session on a router or on a tester. The peering
sessions referred to here may exist between various classes of BGP sessions referred to here may exist between various classes of BGP
routers (see Section 4.2). routers (see Section 4.2).
Measurement units: number of BGP peers Measurement units: number of BGP peers
Issues: Issues:
See Also: See Also:
3.10 BGP Neighbor 3.11 BGP Neighbor
Definition: Definition:
A BGP neighbor is a device that can be configured as a BGP peer. A BGP neighbor is a device that can be configured as a BGP peer.
Discussion: Discussion:
Measurement units: Measurement units:
Issues: Issues:
See Also: See Also:
3.11 MinRouteAdvertisementInterval (MRAI) 3.12 MinRouteAdvertisementInterval (MRAI)
Definition: Definition:
(Paraphrased from 1771[1]) The MRAI timer determines the minimum (Paraphrased from RFC 1771) The MRAI timer determines the minimum
time between advertisements of routes to a particular destination time between advertisements of routes to a particular destination
(prefix) from a single BGP device. The timer is applied on a (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 pre-prefix basis, although the timer is set on a per BGP device
basis. basis.
Discussion: Discussion:
Given that a BGP instance may manage in excess of 100,000 routes, 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 RFC 1771 allows for a degree of optimization in order to limit the
number of timers needed. The MRAI does not apply to routes number of timers needed. The MRAI does not apply to routes
received from BGP speakers in the same AS or to explicit received from BGP speakers in the same AS or to explicit
withdrawals. withdrawals.
RFC 1771 also recommends that random jitter is applied to MRAI in RFC 1771 also recommends that random jitter is applied to MRAI in
an attempt to avoid synchronization effects between the BGP an attempt to avoid synchronization effects between the BGP
instances in a network. instances in a network.
In this document we define routing plane convergence by measuring In this document we define routing plane convergence by measuring
the time an NLRI is advertised to the DUT to the time it is the time an NLRI is advertised to the DUT to the time it is
advertised from the DUT. Clearly any delay inserted by the MRAI advertised from the DUT. Clearly any delay inserted by the MRAI
will have a significant effect on this measurement. will have a significant effect on this measurement.
Measurement Units: seconds. Measurement Units: seconds.
Issues: Issues:
See Also: NLRI, BGP route See Also: NLRI, BGP route
3.12 MinASOriginationInterval (MAOI) 3.13 MinASOriginationInterval (MAOI)
Definition: Definition:
The MAOI specifies the minimum interval between advertisements of The MAOI specifies the minimum interval between advertisements of
locally originated routes from this BGP instance. locally originated routes from this BGP instance.
Discussion: Discussion:
Random jitter is applied to MAOI in an attempt to avoid Random jitter is applied to MAOI in an attempt to avoid
synchronization effects between BGP instances in a network. synchronization effects between BGP instances in a network.
Measurement Units: seconds Measurement Units: seconds
Issues: Issues:
It is not known what, if any relationship exists between the It is not known what, if any relationship exists between the
settings of MRAI and MAOI. settings of MRAI and MAOI.
See Also: MRAI, BGP route See Also: MRAI, BGP route
3.13 Active Route 3.14 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: Number of routes. Measurement Units: Number of routes.
Issues: Issues:
See also: RIB. See also: RIB.
3.14 Unique Route 3.15 Unique Route
Definition: Definition:
A unique route is a prefix for which there is just one route A unique route is a prefix for which there is just one route
instance across all Adj-Ribs-In. 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
3.15 Non-Unique Route 3.16 Non-Unique Route
Definition: Definition:
A Non-unique route is a prefix for which there is at least one A Non-unique route is a prefix for which there is at least one
other route in a set including more than one Adj-RIB-in. 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: See Also:
route, route instance, unique active route. route, route instance, unique active route.
3.16 Route Instance 3.17 Route Instance
Definition: Definition:
A route instance is one of several possible occurrences of a route A route instance is one of several possible occurrences of a route
for a particular prefix. for a particular prefix.
Discussion: Discussion:
When a router has multiple peers from which it accepts routes, When a router has multiple peers from which it accepts routes,
routes to the same prefix may be received from several peers. This routes to the same prefix may be received from several peers.
is then an example of multiple route instances. This is then an example of multiple route instances.
Each route instance is associated with a specific peer. The BGP Each route instance is associated with a specific peer. The BGP
algorithm that arbitrates between the available candidate route algorithm that arbitrates between the available candidate route
instances may reject a specific route instance due to local instances may reject a specific route instance due to local
policy. 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 The number of route instances in the Adj-RIB-in bases will vary
based on the function to be performed by a router. An based on the function to be performed by a router. An
inter-provider border router, located in the default-free zone inter-provider border router, located in the default-free zone
(see Section 4.1.4) will likely receive more route instances than (see Section 4.1.4) will likely receive more route instances than
a provider edge router, located closer to the end-users of the a provider edge router, located closer to the end-users of the
network. network.
See Also: See Also:
4. Constituent Elements of a Router or Network of Routers 4. 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.
skipping to change at page 18, line 23 skipping to change at page 16, line 23
4.1 Default Route, Default Free Table, and Full Table 4.1 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). Also, a synonymous with having a full default-free table(DFT). Also, a
router which has a full set of routes as in a DFT but also has a router which has a full set of routes as in a DFT but also has a
'discard' rule for a default route would not be considered as default 'discard' rule for a default route would not be considered as default
free. free.
It should be noted that the references to number of routes in this Note that the references to number of routes in this section document
section document are to routes installed in the loc-RIB and are are to routes installed in the loc-RIB and are therefore unique
therefore unique routes, not route instances, and that the total routes, not route instances, and that the total number of route
number of route instances may be 4 to 10 times the number of routes. instances may be 4 to 10 times the number of routes.
4.1.1 Default Route 4.1.1 Default Route
Definition: Definition:
A Default Route can match any destination address. If a router A Default Route can match any destination address. If a router
does not have a more specific route for a particular packet's does not have a more specific route for a particular packet's
destination address, it forwards this packet to the next hop in destination address, it forwards this packet to the next hop in
the default route entry, provided its Forwarding Table (Forwarding the default route entry, provided its Forwarding Table (Forwarding
Information Base (FIB) contains one). The notation for a default Information Base (FIB) contains one). The notation for a default
route for IPv4 is 0.0.0.0/0 and for IPv6 it is 0:0:0:0:0:0:0:0 or route for IPv4 is 0.0.0.0/0 and for IPv6 it is 0:0:0:0:0:0:0:0 or
skipping to change at page 18, line 38 skipping to change at page 16, line 38
4.1.1 Default Route 4.1.1 Default Route
Definition: Definition:
A Default Route can match any destination address. If a router A Default Route can match any destination address. If a router
does not have a more specific route for a particular packet's does not have a more specific route for a particular packet's
destination address, it forwards this packet to the next hop in destination address, it forwards this packet to the next hop in
the default route entry, provided its Forwarding Table (Forwarding the default route entry, provided its Forwarding Table (Forwarding
Information Base (FIB) contains one). The notation for a default Information Base (FIB) contains one). The notation for a default
route for IPv4 is 0.0.0.0/0 and for IPv6 it is 0:0:0:0:0:0:0:0 or route for IPv4 is 0.0.0.0/0 and for IPv6 it is 0:0:0:0:0:0:0:0 or
::/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
4.1.2 Default Free Routing Table 4.1.2 Default Free Routing Table
Definition: Definition:
A default free routing table has no default routes and is A default free routing table has no default routes and is
typically seen in routers in the core or top tier of routers in typically seen in routers in the core or top tier of routers in
the network. the network.
Discussion: Discussion:
The term originates from the concept that routers at the core or The term originates from the concept that routers at the core or
top tier of the Internet will not be configured with a default top tier of the Internet will not be configured with a default
route (Notation in IPv4 0.0.0.0/0 and in IPv6 0:0:0:0:0:0:0:0 or route (Notation in IPv4 0.0.0.0/0 and in IPv6 0:0:0:0:0:0:0:0 or
::/0). Thus they will forward every packet to a specific next hop ::/0). Thus they will forward every packet to a specific next hop
based on the longest match between the destination IP addresse based on the longest match between the destination IP address and
and the routes in the forwarding table. the routes in the forwarding table.
Default free routing table size is commonly used as an indicator Default free routing table size is commonly used as an indicator
of the magnitude of reachable Internet address space. However, of the magnitude of reachable Internet address space. However,
default free routing tables may also include routes internal to default free routing tables may also include routes internal to
the router's AS. the router's AS.
Measurement Units: The number of routes Measurement Units: The number of routes
See Also: Full Default Free Table, Default Route
See Also: Full Default Free, Default Route
4.1.3 Full Default Free Table 4.1.3 Full Default Free Table
Definition: Definition:
A full default free table is the union of all sets of default free A full default free table is the union of all sets of BGP routes
BGP routes collectively announced by the complete set of taken from all the default free BGP routing tables collectively
autonomous systems making up the public Internet. Due to the announced by the complete set of autonomous systems making up the
dynamic nature of the Internet, the exact size and composition of public Internet. Due to the dynamic nature of the Internet, the
this table may vary slightly depending where and when it is exact size and composition of this table may vary slightly
observed. depending where and when it is observed.
Discussion: Discussion:
It is generally accepted that a full table, in this usage, does It is generally accepted that a full table, in this usage, does
not contain the infrastructure routes or individual sub-aggregates not contain the infrastructure routes or individual sub-aggregates
of routes that are otherwise aggregated by the provider before of routes that are otherwise aggregated by the provider before
announcement to other autonomous systems. announcement to other autonomous systems.
Measurement Units: number of routes Measurement Units: number of routes
Issues: Issues:
Note: The full default-free routing table is not the same as as
the union of all reachable unicast addressesses. The table simply
does not contain the default prefix (0/0) and does contain the
union of all sets of BGP routes from default free BGP routing
tables.
See Also: Routes, Route Instances, Default Route See Also: Routes, Route Instances, Default Route
4.1.4 Default-Free Zone 4.1.4 Default-Free Zone
Definition: Definition:
The default-free zone is that part of the Internet backbone that The default-free zone is that part of the Internet backbone that
does not have a default route. does not have a default route.
Discussion: Discussion:
Measurement Units: Measurement Units:
Issues: Issues:
See Also: Default Route See Also: Default Route
4.1.5 Full Provider-Internal Table 4.1.5 Full Provider-Internal Table
Definition: Definition:
A full provider-internal table is a superset of the full routing A full provider-internal table is a superset of the full routing
table that contains infrastructure and non- aggregated routes. table that contains infrastructure and non- aggregated routes.
Discussion: Discussion:
Experience has shown that this table might contain 1.3 to 1.5 Experience has shown that this table might contain 1.3 to 1.5
times the number of routes in the externally visible full table. times the number of routes in the externally visible full table.
Tables of this size, therefore, are a real-world requirement for Tables of this size, therefore, are a real-world requirement for
key internal provider routers. 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
4.2 Classes of BGP-Speaking Routers 4.2 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.
4.2.1 Provider Edge Router 4.2.1 Provider Edge Router
Definition: Definition:
skipping to change at page 20, line 47 skipping to change at page 18, line 26
4.2 Classes of BGP-Speaking Routers 4.2 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.
4.2.1 Provider Edge Router 4.2.1 Provider Edge Router
Definition: Definition:
A provider edge router is a router at the edge of a provider's A provider edge router is a router at the edge of a provider's
network that speaks eBGP to a BGP speaker in another AS. network that speaks eBGP to a BGP speaker in another AS.
Discussion: Discussion:
The traffic that transits this router may be destined to, or The traffic that transits this router may be destined to, or
originate from non-adjacent autonomous systems. In particular the originate from non-adjacent autonomous systems. In particular the
MED values used in the Provider Edge Router would not be visible MED values used in the Provider Edge Router would not be visible
in the non-adjacent autonomous systems. in the non-adjacent autonomous systems.
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:
4.2.2 Subscriber Edge Router 4.2.2 Subscriber Edge Router
Definition: Definition:
A subscriber edge router is router at the edge of the subscriber's A subscriber edge router is router at the edge of the subscriber's
network that speaks eBGP to its provider's AS(s). network that speaks eBGP to its provider's AS(s).
Discussion: Discussion:
The router belongs to an end user organization that may be multi- The router belongs to an end user organization that may be multi-
homed, and which carries traffic only to and from that end user homed, and which carries traffic only to and from that end user
AS. AS.
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:
This definition of an enterprise border router (which is what most This definition of an enterprise border router (which is what most
Subscriber Edge Routers are) is practical rather than rigorous. It Subscriber Edge Routers are) is practical rather than rigorous.
is meant to draw attention to the reality that many enterprises It is meant to draw attention to the reality that many enterprises
may need a BGP speaker that advertises their own routes and may need a BGP speaker that advertises their own routes and
accepts either default alone or partial routes. In such cases, accepts either default alone or partial routes. In such cases,
they may be interested in benchmarks that use a partial routing they may be interested in benchmarks that use a partial routing
table, to see if a smaller control plane processor will meet their table, to see if a smaller control plane processor will meet their
needs. needs.
See Also: See Also:
4.2.3 Inter-provider Border Router 4.2.3 Inter-provider Border Router
Definition: Definition:
An inter-provider border router is a BGP speaking router which An inter-provider border router is a BGP speaking router which
maintains BGP sessions with other BGP speaking routers in other maintains BGP sessions with other BGP speaking routers in other
providers' ASs. providers' ASs.
Discussion: Discussion:
Traffic transiting this router may be originated in or destined Traffic transiting this router may be originated in or destined
for another AS that has no direct connectivity with this for another AS that has no direct connectivity with this
provider's AS. provider's AS.
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:
4.2.4 Core Router 4.2.4 Core Router
Definition: Definition:
An core router is a provider router Internal to the provider's An core router is a provider router Internal to the provider's
net, speaking iBGP to that provider's edge routers, other intra- net, speaking iBGP to that provider's edge routers, other intra-
provider core routers, or the provider's inter-provider border provider core routers, or the provider's inter-provider border
routers. 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:
Then by this definition the DUT's which are eBGP routers aren't Then by this definition the DUT's which are eBGP routers aren't
core routers. core routers.
See Also: See Also:
5. Characterization of Sets of Update Messages 5. Characterization of Sets of Update Messages
This section contains a sequence of definitions that build up to the This section contains a sequence of definitions that build up to the
definition of an Update Train. The Packet train concept was definition of an Update Train. The Packet train concept was
originally introduced by Jain and Routhier [11]. It is here adapted originally introduced by Jain and Routhier[PKTTRAIN]. It is here
to refer to a train of packets of interest in BGP performance adapted to refer to a train of packets of interest in BGP performance
testing. testing.
This is a formalization of the sort of test stimulus that is expected 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 as input to a DUT running BGP. This data could be a
well-characterized, ordered and timed set of hand-crafted BGP UPDATE 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 packets. It could just as well be a set of BGP UPDATE packets that
have been captured from a live router. have been captured from a live router.
Characterization of route mixtures and Update Trains is an open area Characterization of route mixtures and Update Trains is an open area
of research. The particular question of interest for this work is of research. The particular question of interest for this work is
skipping to change at page 23, line 31 skipping to change at page 20, line 31
the identification of suitable Update Trains, modeled or taken from the identification of suitable Update Trains, modeled or taken from
live traces that reflect realistic sequences of UPDATEs and their live traces that reflect realistic sequences of UPDATEs and their
contents. contents.
5.1 Route Packing 5.1 Route Packing
Definition: Definition:
Route packing is the number of route prefixes accommodated in a Route packing is the number of route prefixes accommodated in a
single Routing Protocol UPDATE Message either as updates single Routing Protocol UPDATE Message either as updates
(additions or modifications) or withdrawals. (additions or modifications) or withdrawals.
Discussion: Discussion:
In general, a routing protocol update may contain more than one In general, a routing protocol update may contain more than one
prefix. In BGP, a single UPDATE may contain two sets of multiple prefix. In BGP, a single UPDATE may contain two sets of multiple
network prefixes: one set of additions and updates with identical network prefixes: one set of additions and updates with identical
attributes (the NLRI) and one set of unfeasible routes to be attributes (the NLRI) and one set of unfeasible routes to be
withdrawn. withdrawn.
Measurement Units: Measurement Units:
Number of prefixes. Number of prefixes.
Issues: Issues:
See Also: See Also:
route, BGP route, route instance, update train, NLRI. route, BGP route, route instance, update train, NLRI.
5.2 Route Mixture 5.2 Route Mixture
Definition: Definition:
A route mixture is the demographics of a set of routes. A route mixture is the demographics of a set of routes.
Discussion: Discussion:
A route mixture is the input data for the benchmark. The A route mixture is the input data for the benchmark. The
particular route mixture used as input must be selected to suit particular route mixture used as input must be selected to suit
the question being asked of the benchmark. Data containing simple the question being asked of the benchmark. Data containing simple
route mixtures might be suitable to test the performance limits of route mixtures might be suitable to test the performance limits of
the BGP device. the BGP device.
Using live data, or input that simulates live data, should improve Using live data, or input that simulates live data, will improve
understanding of how the BGP device will operate in a live understanding of how the BGP device will operate in a live
network. The data for this kind of test must be route mixtures network. The data for this kind of test must be route mixtures
that model the patterns of arriving control traffic in the live that model the patterns of arriving control traffic in the live
Internet. Internet.
To accomplish that kind of modeling it is necessary to identify To accomplish that kind of modeling it is necessary to identify
the key parameters that characterize a live Internet route the key parameters that characterize a live Internet route
mixture. The parameters and how they interact is an open research mixture. The parameters and how they interact is an open research
problem. However, we identify the following as affecting the problem. However, we identify the following as affecting the
route mixture: route mixture:
* Path length distribution * Path length distribution
* Attribute distribution * Attribute distribution
* Prefix length distribution * Prefix length distribution
* Packet packing * Packet packing
* Probability density function of inter-arrival times of * Probability density function of inter-arrival times of
UPDATES UPDATES
Each of the items above is more complex than a single number. For Each of the items above is more complex than a single number. For
example, one could consider the distribution of prefixes by AS or example, one could consider the distribution of prefixes by AS or
distribution of prefixes by length. distribution of prefixes by length.
Measurement Units: Probability density functions Measurement Units: Probability density functions
Issues: Issues:
See Also: NLRI, RIB. See Also: NLRI, RIB.
5.3 Update Train 5.3 Update Train
Definition: Definition:
An update train is a set of Routing Protocol UPDATE messages sent An update train is a set of Routing Protocol UPDATE messages sent
by a router to a BGP peer. by a router to a BGP peer.
Discussion: Discussion:
The arrival pattern of UPDATEs can be influenced by many things, The arrival pattern of UPDATEs can be influenced by many things,
including TCP parameters, hold-down timers, upsteam processing, a including TCP parameters, hold-down timers, upsteam processing, a
peer coming up or multiple peers sending at the same time. peer coming up or multiple peers sending at the same time.
Network conditions such as a local or remote peer flapping a link Network conditions such as a local or remote peer flapping a link
can also affect the arrival pattern. can also affect the arrival pattern.
Measurement units: Measurement units:
Probability density function for the inter-arrival times of UPDATE Probability density function for the inter-arrival times of UPDATE
packets in the train. packets in the train.
Issues: Issues:
Characterizing the profiles of real world UPDATE trains is a Characterizing the profiles of real world UPDATE trains is a
matter for future research. In order to generate realistic UPDATE matter for future research. In order to generate realistic UPDATE
trains as test stimuli a formal mathematical scheme or a proven trains as test stimuli a formal mathematical scheme or a proven
heuristic is needed to drive the selection of prefixes. Whatever heuristic is needed to drive the selection of prefixes. Whatever
mechanism is selected it must generate Update trains that have mechanism is selected it must generate Update trains that have
similar characteristics to those measured in live networks. similar characteristics to those measured in live networks.
See Also: Route Mixture, MRAI, MAOI See Also: Route Mixture, MRAI, MAOI
5.4 Randomness in Update Trains 5.4 Randomness in Update Trains
As we have seen from the previous sections, an update train used as a 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 test stimulus has a considerable number of parameters that can be
varied, to a greater or lesser extent, randomly and independently. varied, to a greater or lesser extent, randomly and independently.
A random Update Train will contain: A random Update Train will contain:
o A route mixture randomized across o A route mixture randomized across
* NLRIs * NLRIs
* updates and withdrawals * updates and withdrawals
* prefixes * prefixes
* inter-arrival times of the UPDATEs * inter-arrival times of the UPDATEs
and possibly across other variables. and possibly across other variables.
This is intended to simulate the unpredictable asynchronous nature of This is intended to simulate the unpredictable asynchronous nature of
the network, whereby UPDATE packets may have arbitrary contents and the network, whereby UPDATE packets may have arbitrary contents and
be delivered at random times. be delivered at random times.
It is important that the data set be randomized sufficiently to avoid It is important that the data set be randomized sufficiently to avoid
favoring one vendor's implementation over another's. Specifically, favoring one vendor's implementation over another's. Specifically,
the distribution of prefixes could be structured to favor the the distribution of prefixes could be structured to favor the
internal organization of the routes in a particular vendor's internal organization of the routes in a particular vendor's
skipping to change at page 26, line 17 skipping to change at page 22, line 34
favoring one vendor's implementation over another's. Specifically, favoring one vendor's implementation over another's. Specifically,
the distribution of prefixes could be structured to favor the the distribution of prefixes could be structured to favor the
internal organization of the routes in a particular vendor's internal organization of the routes in a particular vendor's
databases. This is to be avoided. databases. This is to be avoided.
5.5 Route Flap 5.5 Route Flap
Definition: Definition:
A route flap ia a change of state (withdrawal, announcement, A route flap ia a change of state (withdrawal, announcement,
attribute change) for a route. attribute change) for a route.
Discussion: Discussion:
Route flapping can be considered a special and pathological case Route flapping can be considered a special and pathological case
of update trains. A practical interpretation of what may be of update trains. A practical interpretation of what may be
considered excessively rapid is the RIPE 229 [7], which contains considered excessively rapid is the RIPE 229[RIPE229], which
current guidelines on flap damping parameters. contains current guidelines on flap damping parameters.
Measurement units: Flapping events per unit time. Measurement units: Flapping events per unit time.
Issues: Issues:
Specific Flap events can be found in Section 6.1. A bench-marker Specific Flap events can be found in Section 6.1. A bench-marker
should use a mixture of different route change events in testing. SHOULD use a mixture of different route change events in testing.
See Also: Route change events, flap damping, packet train See Also: Route change events, flap damping, packet train
6. Route Changes and Convergence 6. 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.
6.1 Route Change Events 6.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 [4] as well as Labovitz et al[5]. operational networks is proposed in RIPE-37[RIPE37] as well as
These papers describe BGP protocol-centric events, and event Labovitz et al[INSTBLTY]. These papers describe BGP protocol-centric
sequences in the course of an analysis of network behavior. The events, and event sequences in the course of an analysis of network
terminology in the two papers categorizes similar but slightly behavior. The terminology in the two papers categorizes similar but
different behaviors with some overlap. We would like to apply these slightly different behaviors with some overlap. We would like to
taxonomies to categorize the tests under definition where possible, apply these taxonomies to categorize the tests under definition where
because these tests must tie in to phenomena that arise in actual possible, because these tests must tie in to phenomena that arise in
networks. We avail ourselves of, or may extend, this terminology as actual networks. We avail ourselves of, or may extend, this
necessary for this purpose. terminology as 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 [5] and given categorizable route change events is adopted from [INSTBLTY] and
below. given below.
1. AADiff: Implicit withdrawal of a route and replacement by a route 1. AADiff: Implicit withdrawal of a route and replacement by a route
different in some path attribute. different in some path attribute.
2. AADup: Implicit withdrawal of a route and replacement by route 2. AADup: Implicit withdrawal of a route and replacement by route
that is identical in all path attributes. that is identical in all path attributes.
3. WADiff: Explicit withdrawal of a route and replacement by a 3. WADiff: Explicit withdrawal of a route and replacement by a
different route. different route.
4. WADup: Explicit withdrawal of a route and replacement by a route 4. 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, and event indications in the time perspective, as listed above, and event indications in the time
domain so as to be able to measure activity from the perspective of domain so as to be able to measure activity from the perspective of
the DUT. With this in mind, we incorporate and extend the definitions the DUT. With this in mind, we incorporate and extend the
of [5] to the following: definitions of [INSTBLTY] to the following:
1. Tup (TDx): Route advertised to the DUT by Test Device x 1. Tup (TDx): Route advertised to the DUT by Test Device x
2. Tdown(TDx): Route being withdrawn by Device x 2. Tdown(TDx): Route being withdrawn by Device x
3. Tupinit(TDx): The initial announcement of a route to a unique 3. Tupinit(TDx): The initial announcement of a route to a unique
prefix prefix
4. TWF(TDx): Route fail over after an explicit withdrawal. 4. 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
conveyed by the events above: are conveyed by the events above:
1. Tup(1,TDx) means Device x sends 1 route 1. Tup(1,TDx) means Device x sends 1 route
2. Tup(S,TDx) means Device x sends a train, S, of routes 2. Tup(S,TDx) means Device x sends a train, S, of routes
3. Tup(DFT,TDx) means Device x sends an approximation of a full 3. Tup(DFT,TDx) means Device x sends an approximation of a full
default-free table. 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 RFC 1771, the router ID. As a consequence,
memorandum uses the following descriptor events, which are routes this memorandum uses the following descriptor events, which are
selected by the BGP selection process rather than simple updates: routes selected by the BGP selection process rather than simple
updates:
1. Tbest -- The current best path. 1. Tbest -- The current best path.
2. Tbetter -- Advertise a path that is better than Tbest. 2. Tbetter -- Advertise a path that is better than Tbest.
3. Tworse -- Advertise a path that is worse than Tbest. 3. Tworse -- Advertise a path that is worse than Tbest.
6.2 Device Convergence in the Control Plane 6.2 Device Convergence in the Control Plane
Definition: Definition:
A routing device is said to have converged at the point in time A routing device is said to have converged at the point in time
when the DUT has performed all actions in the control plane needed when the DUT has performed all actions in the control plane needed
to react to changes in topology in the context of the test to react to changes in topology in the context of the test
condition. condition.
Discussion: Discussion:
For example, when considering BGP convergence, the convergence For example, when considering BGP convergence, the convergence
resulting from a change that alters the best route instance for a resulting from a change that alters the best route instance for a
single prefix at a router would be deemed to have occurred when single prefix at a router would be deemed to have occurred when
this route is advertised to its downstream peers. By way of this route is advertised to its downstream peers. By way of
contrast, OSPF convergence concludes when SPF calculations have contrast, OSPF convergence concludes when SPF calculations have
been performed and the required link states advertised onwards. been performed and the required link states advertised onwards.
The convergence process, in general, can be subdivided into three The convergence process, in general, 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 device. * convergence with respect to a single device.
Convergence with respect to a single device can be Convergence with respect to a single device can be
* convergence with regard to data forwarding process(es) * convergence with regard to data forwarding process(es)
* convergence with regard to the routing process(es), the focus * convergence with regard to the routing process(es), the focus
of this document. of this document.
It is the latter, convergence with regard to the routing process, It is the latter, convergence with regard to the routing process,
that we describe in this and the methodology documents. that we describe in this and the methodology documents.
Because we are trying to benchmark the routing protocol Because we are trying to benchmark the routing protocol
performance which is only a part of the device overall, this performance which is only a part of the device overall, this
definition is intended (so far as is possible) to exclude any definition is intended (so far as is possible) to exclude any
additional time such as is needed to download and install the additional time such as is needed to download and install the
forwarding information base in the data plane. This definition forwarding information base in the data plane. This definition is
should be usable for different families of protocols. usable for different families of protocols.
It is of key importance to benchmark the performance of each phase It is of key importance to benchmark the performance of each phase
of convergence separately before proceeding to a composite of convergence separately before proceeding to a composite
characterization of routing convergence, where characterization of routing convergence, where
implementation-specific dependencies are allowed to interact. implementation-specific dependencies are allowed to interact.
Care also needs to be taken to ensure that the convergence time is Care also needs to be taken to ensure that the convergence time is
not influenced by policy processing on downstream peers. not influenced by policy processing on downstream peers.
The time resolution needed to measure the device convergence The time resolution needed to measure the device convergence
depends to some extent on the types of the interfaces on the depends to some extent on the types of the interfaces on the
router. For modern routers with gigabit or faster interfaces, an router. For modern routers with gigabit or faster interfaces, an
individual UPDATE may be processed and re-advertised in very much individual UPDATE may be processed and re-advertised in very much
less than a millisecond so that time measurements must be made to less than a millisecond so that time measurements must be made to
a resolution of hundreds to tens of microseconds or better. a resolution of hundreds to tens of microseconds or better.
Measurement Units: Measurement Units:
Time period. Time period.
Issues: Issues:
See Also: See Also:
7. BGP Operation Events 7. BGP Operation Events
The BGP process(es) in a device might restart because operator The BGP process(es) in a device might restart because operator
intervention or a power failure caused a complete shut-down. In this intervention or a power failure caused a complete shut-down. In this
case a hard reset is needed. A peering session could be lost, for case a hard reset is needed. A peering session could be lost, for
example, because of action on the part of the peer or a dropped tcp example, because of action on the part of the peer or a dropped tcp
session. A device can reestablish its peers and re-advertise all session. A device can reestablish its peers and re-advertise all
relevant routes in a hard reset. However, if a peer is lost, but relevant routes in a hard reset. However, if a peer is lost, but
skipping to change at page 30, line 22 skipping to change at page 26, line 22
relevant routes in a hard reset. However, if a peer is lost, but relevant routes in a hard reset. However, if a peer is lost, but
the BGP process has not failed, BGP has mechanisms for a "soft the BGP process has not failed, BGP has mechanisms for a "soft
reset." reset."
7.1 Hard Reset 7.1 Hard Reset
Definition: Definition:
An event which triggers a complete re-initialization of the An event which triggers a complete re-initialization of the
routing tables on one or more BGP sessions, resulting in exchange routing tables on one or more BGP sessions, resulting in exchange
of a full routing table on one or more links to the router. of a full routing table on one or more links to the router.
Discussion: Discussion:
Measurement Units: N/A Measurement Units: N/A
Issues: Issues:
See Also: See Also:
7.2 Soft Reset 7.2 Soft Reset
Definition: Definition:
A soft reset is performed on a per-neighbor basis; it does not A soft reset is performed on a per-neighbor basis; it does not
clear the BGP session while re-establishing the peering relation clear the BGP session while re-establishing the peering relation
and does not stop the flow of traffic. and does not stop the flow of traffic.
Discussion: Discussion:
There are two methods of performing a soft reset: Graceful restart There are two methods of performing a soft reset: Graceful
[13] where the BGP device that has lost a peer but continues to restart[I-D.ietf-idr-restart] where the BGP device that has lost a
forward traffic for a period of time before tearing down the peer but continues to forward traffic for a period of time before
peer's routes. The alternative method is soft refresh [12], where tearing down the peer's routes. The alternative method is soft
a BGP device can request a peer's Adj-RIB-Out. refresh[RFC2918], where a BGP device can request a peer's
Adj-RIB-Out.
Measurement Units: N/A Measurement Units: N/A
Issues: Issues:
See Also: See Also:
8. Factors that Impact the Performance of the Convergence Process 8. 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.
8.1 General Factors Affecting Device Convergence 8.1 General Factors Affecting Device Convergence
skipping to change at page 32, line 29 skipping to change at page 27, line 29
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, depending on the quantity of updates that is generated by each grows, depending on the quantity of updates that is generated by each
additional peer. Increasing the number of peers also increases the additional peer. Increasing the number of peers also increases the
processing workload for TCP and BGP keepalives. processing workload for TCP and BGP keepalives.
8.1.2 Number of Routes per Peer 8.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
route instances and distinct routes being added or withdrawn by each multiple route instances and distinct routes being added or withdrawn
peer will affect the convergence process, as will the mix of by each peer will affect the convergence process, as will the mix of
overlapping route instances, and IGP routes. overlapping route instances, and IGP routes.
8.1.3 Policy Processing/Reconfiguration 8.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
o Minimal Policy: receive all, send all, o Minimal Policy: receive all, send all,
o Extensive policy: up to 100% of the total routes have applicable o Extensive policy: up to 100% of the total routes have applicable
policy. policy.
8.1.4 Interactions with Other Protocols 8.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.
skipping to change at page 33, line 14 skipping to change at page 28, line 12
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.
8.1.5 Flap Damping 8.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 [2] and discussed in RIPE-229 [7]. The timers are defined by RFC 2439[RFC2439] and discussed in
If this feature is in effect, it requires that the device keep RIPE-229[RIPE229]. If this feature is in effect, it requires that
additional state to carry out the damping, which can have a direct the device keep additional state to carry out the damping, which can
impact on the control plane due to increased processing. In have a direct impact on the control plane due to increased
addition, flap damping may delay the arrival of real changes in a processing. In addition, flap damping may delay the arrival of real
route, and affect convergence times changes in a route, and affect convergence times
8.1.6 Churn 8.1.6 Churn
In theory, a BGP device 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
skipping to change at page 33, line 44 skipping to change at page 28, line 42
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 device 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 re-advertises 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 [16]. The goal of flap damping is to reduce the oscillation [RFC3345]. 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.
8.2 Implementation-specific and other Factors Affecting BGP Convergence 8.2 Implementation-specific and other Factors Affecting BGP Convergence
These factors are conditions of testing internal to the Device Under These factors are conditions of testing internal to the Device Under
Test (DUT), although they may affect its interactions with test Test (DUT), although they may affect its interactions with test
skipping to change at page 34, line 24 skipping to change at page 29, line 19
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 flaps) control traffic (FIB updates and downloads as a consequence of flaps)
are excessive. The addition of data traffic presents a more accurate are excessive. The addition of data traffic presents a more accurate
reflection of realistic operating scenarios than if only control reflection of realistic operating scenarios than if only control
traffic is present. traffic is present.
8.2.2 Timers 8.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 MUST be reported if they use non- default
default value. value.
8.2.3 TCP Parameters Underlying BGP Transport 8.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: e.g. parameters characterizing the TCP sessions MUST be provided: e.g.
Slow start, max window size, maximum segment size, or timers. Slow start, max window size, maximum segment size, or timers.
8.2.4 Authentication 8.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 [8]. The processing of the MD5 hash, particularly in devices Option [RFC2385]. The processing of the MD5 hash, particularly in
with a large number of BGP peers and a large amount of update traffic devices with a large number of BGP peers and a large amount of update
can have an impact on the control plane of the device. traffic can have an impact on the control plane of the device.
9. Security Considerations 9. 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.
10. Acknowledgments 10. Acknowledgments
Thanks to Francis Ovenden for review and Abha Ahuja for Thanks to Francis Ovenden for review and Abha Ahuja for
encouragement. Much appreciation to Jeff Haas, Matt Richardson, and encouragement. Much appreciation to Jeff Haas, Matt Richardson, and
Shane Wright at Nexthop for comments and input. Debby Stopp and Nick Shane Wright at Nexthop for comments and input. Debby Stopp and Nick
Ambrose contributed the concept of route packing. Ambrose contributed the concept of route packing.
Alvaro Retana was a key member of the team that developed this Alvaro Retana was a key member of the team that developed this
document, and made significant technical contributions regarding document, and made significant technical contributions regarding
route mixes. The team thanks him and regards him as a co-author in route mixes. The team thanks him and regards him as a co-author in
spirit. spirit.
Normative References 11. References
[1] Rekhter, Y. and T. Li, "A Border Gateway Protocol 4 (BGP-4)", 11.1 Normative References
RFC 1771, March 1995.
[2] Villamizar, C., Chandra, R. and R. Govindan , "BGP Route Flap [RFC1771] Rekhter, Y. and T. Li, "A Border Gateway Protocol 4
Damping", RFC 2439, November 1998. (BGP-4)", RFC 1771, March 1995.
[3] Baker, F., "Requirements for IP Version 4 Routers", RFC 1812, [RFC2439] Villamizar, C., Chandra, R. and R. Govindan, "BGP Route
June 1995. Flap Damping", RFC 2439, November 1998.
[4] Ahuja, A., Jahanian, F., Bose, A. and C. Labovitz, "An [RFC1812] Baker, F., "Requirements for IP Version 4 Routers", RFC
Experimental Study of Delayed Internet Routing Convergence", 1812, June 1995.
RIPE-37 Presentation to Routing WG, November 2000, <http://
www.ripe.net/ripe/meetings/archive/ripe-37/presentations/
RIPE-37-convergence/>.
[5] Labovitz, C., Malan, G. and F. Jahanian, "Origins of Internet [RIPE37] Ahuja, A., Jahanian, F., Bose, A. and C. Labovitz, "An
Routing Instability", Infocom 99, August 1999. Experimental Study of Delayed Internet Routing
Convergence", RIPE-37 Presentation to Routing WG, November
2000,
<http://www.ripe.net/ripe/meetings/archive/ripe-37/presentations/RIPE-37-convergence/>
.
[6] Alaettinoglu, C., Villamizar, C., Gerich, E., Kessens, D., [INSTBLTY]
Meyer, D., Bates, T., Karrenberg, D. and M. Terpstra, "Routing Labovitz, C., Malan, G. and F. Jahanian, "Origins of
Policy Specification Language (RPSL)", RFC 2622, June 1999. Internet Routing Instability", Infocom 99, August 1999.
[7] Panigl , C., Schmitz , J., Smith , P. and C. Vistoli, "RIPE [RFC2622] Alaettinoglu, C., Villamizar, C., Gerich, E., Kessens, D.,
Routing-WG Recommendation for coordinated route-flap damping Meyer, D., Bates, T., Karrenberg, D. and M. Terpstra,
parameters, version 2", RIPE 229, October 2001. "Routing Policy Specification Language (RPSL)", RFC 2622,
June 1999.
[8] Heffernan, A., "Protection of BGP Sessions via the TCP MD5 [RIPE229] Panigl , C., Schmitz , J., Smith , P. and C. Vistoli,
"RIPE Routing-WG Recommendation for coordinated route-flap
damping parameters, version 2", RIPE 229, October 2001.
[RFC2385] Heffernan, A., "Protection of BGP Sessions via the TCP MD5
Signature Option", RFC 2385, August 1998. Signature Option", RFC 2385, August 1998.
[9] Juniper Networks, "Junos(tm) Internet Software Configuration [GLSSRY] Juniper Networks, "Junos(tm) Internet Software
Guide Routing and Routing Protocols, Release 4.2", Junos 4.2 Configuration Guide Routing and Routing Protocols, Release
and other releases, September 2000, <http://www.juniper.net/ 4.2", Junos 4.2 and other releases, September 2000,
techpubs/software/junos42/swconfig-routing42/html/ <http://www.juniper.net/techpubs/software/junos/junos42/swcmdref42/html/glossary.html>
glossary.html#1013039>. .
[10] Rosen, E. and Y. Rekhter, "BGP/MPLS VPNs", RFC 2547, March [RFC2547] Rosen, E. and Y. Rekhter, "BGP/MPLS VPNs", RFC 2547, March
1999. 1999.
[11] Jain, R. and S. Routhier, "Packet trains -- measurement and a [PKTTRAIN]
new model for computer network traffic", IEEE Journal on Jain, R. and S. Routhier, "Packet trains -- measurement
Selected Areas in Communication 4(6), September 1986. and a new model for computer network traffic", IEEE
Journal on Selected Areas in Communication 4(6), September
Informative References 1986.
[12] Chen, E., "Route Refresh for BGP-4", RFC 2918, September 2000. 11.2 Informative References
[13] Sangli, S., Rekhter, Y., Fernando, R., Scudder, J. and E. Chen, [RFC2918] Chen, E., "Route Refresh Capability for BGP-4", RFC 2918,
"Graceful Restart Mechanism for BGP", draft-ietf-idr-restart-06 September 2000.
(work in progress), January 2003.
[14] Chen, E. and Y. Rekhter, "Cooperative Route Filtering [I-D.ietf-idr-restart]
Capability for BGP-4", draft-ietf-idr-route-filter-08 (work in Sangli, S., Rekhter, Y., Fernando, R., Scudder, J. and E.
progress), January 2003. Chen, "Graceful Restart Mechanism for BGP",
draft-ietf-idr-restart-10 (work in progress), June 2004.
[15] Anderson, T. and H. Khosravi, "Requirements for Separation of [I-D.ietf-idr-route-filter]
IP Control and Forwarding", draft-ietf-forces-requirements-08 Chen, E. and Y. Rekhter, "Cooperative Route Filtering
(work in progress), January 2003. Capability for BGP-4", draft-ietf-idr-route-filter-10
(work in progress), March 2004.
[16] McPherson, D., Gill, V., Walton, D. and A. Retana, "Border [RFC3654] Khosravi, H. and T. Anderson, "Requirements for Separation
Gateway Protocol (BGP) Persistent Route Oscillation Condition", of IP Control and Forwarding", RFC 3654, November 2003.
RFC 3345, August 2002.
[17] Bates, T., Rekhter, Y., Chandra, R. and D. Katz, [RFC3345] McPherson, D., Gill, V., Walton, D. and A. Retana, "Border
"Multiprotocol Extensions for BGP-4", RFC 2283. Gateway Protocol (BGP) Persistent Route Oscillation
Condition", RFC 3345, August 2002.
For Internet Draft consistency purposes only [RFC2858] Bates, T., Rekhter, Y., Chandra, R. and D. Katz,
"Multiprotocol Extensions for BGP-4", RFC 2858, June 2000.
[18] Bradner, S., "The Internet Standards Process -- Revision 3", [RFC2545] Marques, P. and F. Dupont, "Use of BGP-4 Multiprotocol
RFC 2026, BCP 9, October 1996. Extensions for IPv6 Inter-Domain Routing", RFC 2545, March
1999.
Authors' Addresses Authors' Addresses
Howard Berkowitz Howard Berkowitz
Gett Communications Gett Communications
5012 S. 25th St 5012 S. 25th St
Arlington, VA 22206 Arlington, VA 22206
USA USA
Phone: +1 703 998-5819 Phone: +1 703 998-5819
skipping to change at page 39, line 34 skipping to change at page 34, line 16
Harlow Laboratories Harlow Laboratories
London Road London Road
Harlow, Essex CM17 9NA Harlow, Essex CM17 9NA
UK UK
Phone: +44 1279 405 498 Phone: +44 1279 405 498
EMail: elwynd@nortelnetworks.com EMail: elwynd@nortelnetworks.com
Susan Hares Susan Hares
Nexthop Technologies Nexthop Technologies
517 W. William 825 Victors Way
Ann Arbor, MI 48103 Ann Arbor, MI 48108
USA USA
EMail: skh@nexthop.com EMail: skh@nexthop.com
Padma Krishnaswamy Padma Krishnaswamy
SAIC SAIC
331 Newman Springs Road 331 Newman Springs Road
Red Bank, New Jersey 07701 Red Bank, New Jersey 07701
USA USA
skipping to change at page 40, line 4 skipping to change at page 34, line 29
EMail: skh@nexthop.com EMail: skh@nexthop.com
Padma Krishnaswamy Padma Krishnaswamy
SAIC SAIC
331 Newman Springs Road 331 Newman Springs Road
Red Bank, New Jersey 07701 Red Bank, New Jersey 07701
USA USA
EMail: kri1@earthlink.net EMail: kri1@earthlink.net
Marianne Lepp Marianne Lepp
Consultant Consultant
EMail: mlepp@lepp.com EMail: mlepp@lepp.com
Intellectual Property Statement Intellectual Property Statement
The IETF takes no position regarding the validity or scope of any The IETF takes no position regarding the validity or scope of any
intellectual property or other rights that might be claimed to Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights this document or the extent to which any license under such rights
might or might not be available; neither does it represent that it might or might not be available; nor does it represent that it has
has made any effort to identify any such rights. Information on the made any independent effort to identify any such rights. Information
IETF's procedures with respect to rights in standards-track and on the procedures with respect to rights in RFC documents can be
standards-related documentation can be found in BCP-11. Copies of found in BCP 78 and BCP 79.
claims of rights made available for publication and any assurances of
licenses to be made available, or the result of an attempt made to Copies of IPR disclosures made to the IETF Secretariat and any
obtain a general license or permission for the use of such assurances of licenses to be made available, or the result of an
proprietary rights by implementors or users of this specification can attempt made to obtain a general license or permission for the use of
be obtained from the IETF Secretariat. such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary copyrights, patents or patent applications, or other proprietary
rights which may cover technology that may be required to practice rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF Executive this standard. Please address the information to the IETF at
Director. ietf-ipr@ietf.org.
Full Copyright Statement
Copyright (C) The Internet Society (2003). All Rights Reserved. Disclaimer of Validity
This document and translations of it may be copied and furnished to This document and the information contained herein are provided on an
others, and derivative works that comment on or otherwise explain it "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
or assist in its implementation may be prepared, copied, published OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
and distributed, in whole or in part, without restriction of any ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
kind, provided that the above copyright notice and this paragraph are INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
included on all such copies and derivative works. However, this INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
document itself may not be modified in any way, such as by removing WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be Copyright Statement
revoked by the Internet Society or its successors or assignees.
This document and the information contained herein is provided on an Copyright (C) The Internet Society (2004). This document is subject
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING to the rights, licenses and restrictions contained in BCP 78, and
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING except as set forth therein, the authors retain all their rights.
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Acknowledgement Acknowledgment
Funding for the RFC Editor function is currently provided by the Funding for the RFC Editor function is currently provided by the
Internet Society. Internet Society.
 End of changes. 

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