Request for Comments: 4098 Gett Communications & CCI Training
Category: Informational E. Davies, Ed.
Folly Consulting
S. Hares
Nexthop Technologies
P. Krishnaswamy
SAIC
M. Lepp
Consultant
June 2005
Terminology for Benchmarking BGP Device Convergence
in the Control Plane
Status of This Memo
This memo provides information for the Internet community. It does
not specify an Internet standard of any kind. Distribution of this
memo is unlimited.
Copyright Notice
Copyright (C) The Internet Society (2005).
Abstract
This document establishes terminology to standardize the description
of benchmarking methodology for measuring eBGP convergence in the
control plane of a single BGP device. Future documents will address
iBGP convergence, the initiation of forwarding based on converged
control plane information and multiple interacting BGP devices. This
terminology is applicable to both IPv4 and IPv6. Illustrative
examples of each version are included where relevant.
Table of Contents
1. Introduction ....................................................3
1.1. Overview and Road Map ......................................4
1.2. Definition Format ..........................................5
2. Components and Characteristics of Routing Information ...........5
2.1. (Network) Prefix ...........................................5
2.2. Network Prefix Length ......................................6
2.3. Route ......................................................6
2.4. BGP Route ..................................................7
2.5. Network Level Reachability Information (NLRI) ..............7
2.6. BGP UPDATE Message .........................................8
3. Routing Data Structures and Route Categories ....................8
3.1. Routing Information Base (RIB) .............................8
3.1.1. Adj-RIB-In and Adj-RIB-Out ..........................8
3.1.2. Loc-RIB .............................................9
3.2. Prefix Filtering ...........................................9
3.3. Routing Policy ............................................10
3.4. Routing Policy Information Base ...........................10
3.5. Forwarding Information Base (FIB) .........................11
3.6. BGP Instance ..............................................12
3.7. BGP Device ................................................12
3.8. BGP Session ...............................................13
3.9. Active BGP Session ........................................13
3.10. BGP Peer .................................................13
3.11. BGP Neighbor .............................................14
3.12. MinRouteAdvertisementInterval (MRAI) .....................14
3.13. MinASOriginationInterval (MAOI) ..........................15
3.14. Active Route .............................................15
3.15. Unique Route .............................................15
3.16. Non-Unique Route .........................................16
3.17. Route Instance ...........................................16
4. Constituent Elements of a Router or Network of Routers .........17
4.1. Default Route, Default-Free Table, and Full Table .........17
4.1.1. Default Route ......................................17
4.1.2. Default-Free Routing Table .........................18
4.1.3. Full Default-Free Table ............................18
4.1.4. Default-Free Zone ..................................19
4.1.5. Full Provider-Internal Table .......................19
4.2. Classes of BGP-Speaking Routers ...........................19
4.2.1. Provider Edge Router ...............................20
4.2.2. Subscriber Edge Router .............................20
4.2.3. Inter-provider Border Router .......................21
4.2.4. Core Router ........................................21
5. Characterization of Sets of Update Messages ....................22
5.1. Route Packing .............................................22
5.2. Route Mixture .............................................23
5.3. Update Train ..............................................24
5.4. Randomness in Update Trains ...............................24
5.5. Route Flap ................................................25
6. Route Changes and Convergence ..................................25
6.1. Route Change Events .......................................25
6.2. Device Convergence in the Control Plane ...................27
7. BGP Operation Events ...........................................28
7.1. Hard Reset ................................................28
7.2. Soft Reset ................................................29
8. Factors That Impact the Performance of the Convergence
Process ........................................................29
8.1. General Factors Affecting Device Convergence ..............29
8.1.1. Number of Peers ....................................29
8.1.2. Number of Routes per Peer ..........................30
8.1.3. Policy Processing/Reconfiguration ..................30
8.1.4. Interactions with Other Protocols ..................30
8.1.5. Flap Damping .......................................30
8.1.6. Churn ..............................................31
8.2. Implementation-Specific and Other Factors Affecting BGP ...31
8.2.1. Forwarded Traffic ..................................31
8.2.2. Timers .............................................32
8.2.3. TCP Parameters Underlying BGP Transport ............32
8.2.4. Authentication .....................................32
9. Security Considerations ........................................32
10. Acknowledgements ..............................................32
11. References ....................................................33
11.1. Normative References ....................................33
11.2. Informative References ..................................34
1. Introduction
This document defines terminology for use in characterizing the
convergence performance of BGP processes in routers or other devices
that instantiate BGP functionality. (See ’A Border Gateway Protocol
4 (BGP-4)’ [RFC1771], referred to as RFC 1771 in the remainder of the
document.) It is the first part of a two-document series, of which
the subsequent document will contain the associated tests and
methodology. This terminology is applicable to both IPv4 and IPv6.
Illustrative examples of each version are included where relevant.
However, this document is primarily targeted for BGP-4 in 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 that support
VPNs as described in RFC 2547 [RFC2547] are out of scope for this
document.
The following observations underlie the approach adopted in this
document, and in the companion document:
o The principal objective is to derive methodologies that
standardize conducting and reporting convergence-related
measurements for BGP.
o It is necessary to remove ambiguity from many frequently used
terms that arise in the context of these measurements.
o As convergence characterization is a complex process, it is
desirable to restrict the initial focus in this set of documents
to specifying how to take basic control-plane measurements as a
first step in characterizing BGP convergence.
For path-vector protocols, such as BGP, the primary initial focus
will therefore be on network and system control-plane [RFC3654]
activity consisting of the arrival, processing, and propagation of
routing information.
We note that for testing purposes, all optional parameters SHOULD be
turned off. All variable parameters SHOULD be at their default
setting unless the test specifies otherwise.
Subsequent documents will explore the more intricate aspects of
convergence measurement, such as the impacts of the presence of
Multiprotocol Extensions for BGP-4, policy processing, simultaneous
traffic on the control and data paths within the Device Under Test
(DUT), and other realistic performance modifiers. Convergence of
Interior Gateway Protocols (IGPs) will also be considered in separate
documents.
1.1. Overview and Road Map
Characterizations of the BGP convergence performance of a device
must-take into account all distinct stages and aspects of BGP.
functionality. This requires that the relevant terms and metrics be
as specifically defined as possible. Such definition is the goal of
this document.
The necessary definitions are classified into separate categories:
o Components and characteristics of routing information
o Routing data structures and route categories
o Descriptions of the constituent elements of a network or a router
that is undergoing convergence
o Characterization of sets of update messages, types of route-change
events, as well as some events specific to BGP operation
o Descriptions of factors that impact the performance of convergence
processes
1.2. Definition Format
The definition format is equivalent to that defined in ’Requirements
for IP Version 4 Routers’ [RFC1812], and is repeated here for
convenience:
X.x Term to be defined (e.g., Latency).
Definition:
One or more sentences forming the body of the definition.
Discussion:
A brief discussion of the term, its application, and any
restrictions that there might be on measurement procedures.
Measurement units:
The units used to report measurements of this term. This item may
not be applicable (N.A.).
Issues:
List of issues or conditions that could affect this term.
See also:
List of related terms that are relevant to the definition or
discussion of this term.
2. Components and Characteristics of Routing Information
2.1. (Network) Prefix
Definition:
"A network prefix is a contiguous set of bits at the more
significant end of the address that collectively designates the
set of systems within a network; host numbers select among those
systems." (This definition is taken directly from section 2.2.5.2,
"Classless Inter Domain Routing (CIDR)", of RFC 1812.)
Discussion:
In the CIDR context, the network prefix is the network component
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.
Issues:
See also:
2.2. Network Prefix Length
Definition:
The network prefix length is the number of bits, out of the total
constituting the address field, that define the network prefix
portion of the address.
Discussion:
A common alternative to using a bit-wise mask to communicate this
component is the use of slash (/) notation. This binds the notion
of network prefix length in bits to an IP address. For example,
141.184.128.0/17 indicates that the network component of this IPv4
address is 17 bits wide. Similar notation is used for IPv6
network prefixes; e.g., 2001:db8:719f::/48. When referring to
groups of addresses, the network prefix length is often used as a
means of describing groups of addresses as an equivalence class.
For example, ’one hundred /16 addresses’ refers to 100 addresses
whose network prefix length is 16 bits.
Measurement units:
Bits.
Issues:
See also:
Network Prefix.
2.3. Route
Definition:
In general, a ’route’ is the n-tuple <prefix, nexthop [, other
routing or non-routing protocol attributes]>. 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 toward their destination
as defined by the prefix. In this usage, a route is the basic
unit of information about a target destination distilled from
routing protocols.
Discussion:
This term refers to the concept of a route common to all routing
protocols. With reference to the definition above, typical non-
routing-protocol attributes would be associated with diffserv or
traffic engineering.
Measurement units: N.A.
Issues:
None.
See also:
BGP Route.
2.4. BGP Route
Definition:
A BGP route is an n-tuple <prefix, nexthop, ASpath [, other BGP
attributes]>.
Discussion:
BGP Attributes, such as Nexthop or AS path, are defined in RFC
1771, where they are known as Path Attributes, and they are the
qualifying data that define the route. From RFC 1771: "For
purposes of this protocol a route is defined as a unit of
information that pairs a destination with the attributes of a path
to that destination."
Measurement units: N.A.
Issues:
See also:
Route, Prefix, Adj-RIB-In, Network Level Reachability Information
(NLRI)
2.5. Network Level Reachability Information (NLRI)
Definition:
The NLRI consists of one or more network prefixes with the same
set of path attributes.
Discussion:
Each prefix in the NLRI is combined with the (common) path
attributes to form a BGP route. The NLRI encapsulates a set of
destinations to which packets can be routed (from this point in
the network) along a common route described by the path
attributes.
Measurement units: N.A.
Issues:
See also:
Route Packing, Network Prefix, BGP Route, NLRI.
2.6. BGP UPDATE Message
Definition:
An UPDATE message contains an advertisement of a single NLRI
field, possibly containing multiple prefixes, and multiple
withdrawals of unfeasible routes. See RFC 1771 for details.
Discussion:
From RFC 1771: "A variable length sequence of path attributes is
present in every UPDATE. Each path attribute is a triple
<attribute type, attribute length, attribute value> of variable
length."
Measurement units: N.A.
See also:
3. Routing Data Structures and Route Categories
3.1. Routing Information Base (RIB)
The RIB collectively consists of a set of logically (not necessarily
physically) distinct databases, each of which is enumerated below.
The RIB contains all destination prefixes to which the router may
forward, and one or more currently reachable next hop addresses for
them.
Routes included in this set potentially have been selected from
several sources of information, including hardware status, interior
routing protocols, and exterior routing protocols. RFC 1812 contains
a basic set of route selection criteria relevant in an all-source
context. Many implementations impose additional criteria. A common
implementation-specific criterion is the preference given to
different routing information sources.
3.1.1. Adj-RIB-In and Adj-RIB-Out
Definition:
Adj-RIB-In and Adj-RIB-Out are "views" of routing information from
the perspective of individual peer routers. The Adj-RIB-In
contains information advertised to the DUT by a specific peer.
The Adj-RIB-Out contains the information the DUT will advertise to
the peer. See RFC 1771.
Discussion:
Issues:
Measurement units:
Number of route instances.
See also:
Route, BGP Route, Route Instance, Loc-RIB, FIB.
3.1.2. Loc-RIB
Definition:
The Loc-RIB contains the set of best routes selected from the
various Adj-RIBs, after applying local policies and the BGP route
selection algorithm.
Discussion:
The separation implied among the various RIBs is logical. It does
not necessarily follow that these RIBs are distinct and separate
entities in any given implementation. Types of routes that need
to be considered include internal BGP, external BGP, interface,
static, and IGP routes.
Issues:
Measurement units:
Number of routes.
See also:
Route, BGP Route, Route Instance, Adj-RIB-In, Adj-RIB-Out, FIB.
3.2. Prefix Filtering
Definition:
Prefix Filtering is a technique for eliminating routes from
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’ [BGP-4] 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:
RFC 1771 further constrains policy to be within the hop-by-hop
routing paradigm. Policy is implemented using filters and
associated policy actions such as Prefix Filtering. Many ASes
formulate and document their policies using the Routing Policy
Specification Language (RPSL) [RFC2622] and then automatically
generate configurations for the BGP processes in their routers
from the RPSL specifications.
Measurement units:
Number of policies; length of policies.
Issues:
See also:
Routing Policy Information Base, Prefix Filtering.
3.4. Routing Policy Information Base
Definition:
A routing policy information base is the set of incoming and
outgoing policies.
Discussion:
All references to the phase of the BGP selection process below are
made with respect to RFC 1771 definition of these phases.
Incoming policies are applied in Phase 1 of the BGP selection
process to the Adj-RIB-In routes to set the metric for the Phase 2
decision process. Outgoing Policies are applied in Phase 3 of the
BGP process to the Adj-RIB-Out routes preceding route (prefix and
path attribute tuple) announcements to a specific peer. Policies
in the Policy Information Base have matching and action
conditions. Common information to match includes route prefixes,
AS paths, communities, etc. The action on match may be to drop
the update and not to pass it to the Loc-RIB, or to modify the
update in some way, such as changing local preference (on input)
or MED (on output), adding or deleting communities, prepending the
current AS in the AS path, etc. The amount of policy processing
(both in terms of route maps and filter/access lists) will impact
the convergence time and properties of the distributed BGP
algorithm. The amount of policy processing may vary from a simple
policy that accepts all routes and sends them according to a
complex policy with a substantial fraction of the prefixes being
filtered by filter/access lists.
Measurement units:
Number and length of policies.
Issues:
See also:
3.5. Forwarding Information Base (FIB)
Definition:
According to the definition in Appendix B of RIPE-37 [RIPE37]:
"The table containing the information necessary to forward IP
Datagrams is called the Forwarding Information Base. At minimum,
this contains the interface identifier and next hop information
for each reachable destination network prefix."
Discussion:
The forwarding information base describes a database indexing
network prefixes versus router port identifiers. The forwarding
information base is distinct from the "routing table" (the Routing
Information Base or RIB), which holds all routing information
received from routing peers. It is a data plane construct and is
used for the forwarding of each packet. The Forwarding
Information Base is generated from the RIB. For the purposes of
this document, the FIB is effectively the subset of the RIB used
by the forwarding plane to make per-packet forwarding decisions.
Most current implementations have full, non-cached FIBs per router
interface. All the route computation and convergence occurs
before entries are downloaded into a FIB.
Measurement units: N.A.
Issues:
See also:
Route, RIB.
3.6. BGP Instance
Definition:
A BGP instance is a process with a single Loc-RIB.
Discussion:
For example, a BGP instance would run in routers or test
equipment. A test generator acting as multiple peers will
typically run more than one instance of BGP. A router would
typically run a single instance.
Measurement units: N.A.
Issues:
See also:
3.7. BGP Device
Definition:
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
state machine.
Discussion:
We have chosen to use "device" as the general case, to deal with