draft-ietf-bmwg-conterm-03.txt   draft-ietf-bmwg-conterm-04.txt 
Benchmarking Working Group H.Berkowitz, Gett Communications Benchmarking Working Group H. Berkowitz
Internet Draft S.Hares, Nexthop Internet-Draft Gett Communications
Document: draft-ietf-bmwg-conterm-03.txt A.Retana, Cisco Expires: September 1, 2003 E. Davies (ed.)
Expires January 2003 P.Krishnaswamy, Consultant Nortel Networks
M.Lepp, Juniper Networks S. Hares
E.Davies, Nortel Networks Nexthop Technologies
July 2002 P. Krishnaswamy
SAIC
M. Lepp
Consultant
A. Retano
Cisco Systems, Inc.
March 3, 2003
Terminology for Benchmarking BGP Device Convergence Terminology for Benchmarking BGP Device Convergence in the Control
in the Control Plane Plane
draft-ietf-bmwg-conterm-04.txt
Status of this Memo Status of this Memo
This document is an Internet-Draft and is in full conformance with This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026 [1]. all provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that other Task Force (IETF), its areas, and its working groups. Note that other
groups may also distribute working documents as Internet-Drafts. groups may also distribute working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
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 The list of current Internet-Drafts can be accessed at http://
http://www.ietf.org/ietf/1id-abstracts.txt www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
A revised version of this draft document will be submitted to the RFC This Internet-Draft will expire on September 1, 2003.
editor as a Informational document for the Internet Community.
Discussion and suggestions for improvement are requested.
This document will expire before January 2003 . Distribution of this
draft is unlimited.
Copyright Notice Copyright Notice
Copyright (C) The Internet Society (2002). All Rights Reserved. Copyright (C) The Internet Society (2003). All Rights Reserved.
Abstract Abstract
This draft establishes terminology to standardize the description of This draft establishes terminology to standardize the description of
benchmarking methodology for measuring eBGP convergence in the benchmarking methodology for measuring eBGP convergence in the
control plane of a single BGP device. Future documents will address control plane of a single BGP device. Future documents will address
iBGP convergence, the initiation of forwarding based on converged iBGP convergence, the initiation of forwarding based on converged
control plane information and 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....................................................3
1.1 Overview and Roadmap.......................................3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Definition Format..........................................3 1.1 Overview and Roadmap . . . . . . . . . . . . . . . . . . . . 4
2. Constituent elements of a router or network of routers.........4 1.2 Definition Format . . . . . . . . . . . . . . . . . . . . . 5
2.1 BGP Instance or Device.....................................4 2. Components and characteristics of Routing information . . . 6
2.2 BGP Peer...................................................5 2.1 (Network) Prefix . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Default Route, Default Free Table, and Full Table..........5 2.2 Network Prefix Length . . . . . . . . . . . . . . . . . . . 6
2.4 Classes of BGP-Speaking Routers............................8 2.3 Route . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3. Routing Data Structures.........................................9 2.4 BGP Route . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1 Routing Information Base (RIB).............................9 2.5 Network Level Reachability Information (NLRI) . . . . . . . 8
3.2 Policy....................................................11 2.6 BGP UPDATE message . . . . . . . . . . . . . . . . . . . . . 8
3.3 Policy Information Base...................................11 3. Routing Data Structures and Route Categories . . . . . . . . 9
3.4 Forwarding Information Base (FIB).........................12 3.1 Routing Information Base (RIB) . . . . . . . . . . . . . . . 9
4. Components and characteristics of Routing information..........13 3.1.1 Adj-RIB-In and Adj-RIB-Out . . . . . . . . . . . . . . . . . 9
4.1 (Network) Prefix..........................................13 3.1.2 Loc-RIB . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.2 Network Prefix Length.....................................13 3.2 Routing Policy . . . . . . . . . . . . . . . . . . . . . . . 10
4.3 Route.....................................................14 3.3 Routing Policy Information Base . . . . . . . . . . . . . . 10
4.4 BGP Route.................................................14 3.4 Forwarding Information Base (FIB) . . . . . . . . . . . . . 11
4.5 BGP Route Attributes and BGP Timers.......................15 3.5 BGP Instance . . . . . . . . . . . . . . . . . . . . . . . . 12
4.6 Route Instance............................................16 3.6 BGP Device . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.7 Active Route..............................................17 3.7 BGP Session . . . . . . . . . . . . . . . . . . . . . . . . 13
4.8 Unique Route..............................................17 3.8 Active BGP Session . . . . . . . . . . . . . . . . . . . . . 13
4.9 Non-Unique Route..........................................17 3.9 BGP Peer . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.10 BGP UPDATE message.....................................17 3.10 BGP Neighbor . . . . . . . . . . . . . . . . . . . . . . . . 14
4.11 Characterization of sets of update messages............18 3.11 MinRouteAdvertisementInterval (MRAI) . . . . . . . . . . . . 14
4.12 Route Flap.............................................20 3.12 MinASOriginationInterval (MAOI) . . . . . . . . . . . . . . 15
5. Route Changes and Convergence..................................21 3.13 Active Route . . . . . . . . . . . . . . . . . . . . . . . . 15
5.1 Route Change Events.......................................21 3.14 Unique Route . . . . . . . . . . . . . . . . . . . . . . . . 16
5.2 Device Convergence in the Control Plane...................22 3.15 Non-Unique Route . . . . . . . . . . . . . . . . . . . . . . 16
6. BGP Operation Events...........................................23 3.16 Route Instance . . . . . . . . . . . . . . . . . . . . . . . 16
6.1 Hard reset................................................24 4. Constituent elements of a router or network of routers. . . 18
6.2 Soft reset................................................24 4.1 Default Route, Default Free Table, and Full Table . . . . . 18
7. Factors that impact the performance of the convergence process.24 4.1.1 Default Route . . . . . . . . . . . . . . . . . . . . . . . 18
7.1 General factors affecting device convergence..............24 4.1.2 Default Free Routing Table . . . . . . . . . . . . . . . . . 18
7.2 Implementation-specific and other factors affecting BGP 4.1.3 Full Default Free Table . . . . . . . . . . . . . . . . . . 19
convergence............................................26 4.1.4 Default-Free Zone . . . . . . . . . . . . . . . . . . . . . 19
8. Security Considerations........................................27 4.1.5 Full Provider-Internal Table . . . . . . . . . . . . . . . . 20
9. References.....................................................27 4.2 Classes of BGP-Speaking Routers . . . . . . . . . . . . . . 20
10. Acknowledgments...............................................28 4.2.1 Provider Edge Router . . . . . . . . . . . . . . . . . . . . 20
11. Author's Addresses............................................29 4.2.2 Subscriber Edge Router . . . . . . . . . . . . . . . . . . . 21
4.2.3 Inter-provider Border Router . . . . . . . . . . . . . . . . 21
4.2.4 Core Router . . . . . . . . . . . . . . . . . . . . . . . . 22
5. Characterization of sets of update messages . . . . . . . . 23
5.1 Route Packing . . . . . . . . . . . . . . . . . . . . . . . 23
5.2 Route Mixture . . . . . . . . . . . . . . . . . . . . . . . 23
5.3 Update Train . . . . . . . . . . . . . . . . . . . . . . . . 24
5.4 Randomness in Update Trains . . . . . . . . . . . . . . . . 25
5.5 Route Flap . . . . . . . . . . . . . . . . . . . . . . . . . 26
6. Route Changes and Convergence . . . . . . . . . . . . . . . 27
6.1 Route Change Events . . . . . . . . . . . . . . . . . . . . 27
6.2 Device Convergence in the Control Plane . . . . . . . . . . 28
7. BGP Operation Events . . . . . . . . . . . . . . . . . . . . 30
7.1 Hard reset . . . . . . . . . . . . . . . . . . . . . . . . . 30
7.2 Soft reset . . . . . . . . . . . . . . . . . . . . . . . . . 30
8. Factors that impact the performance of the convergence
process . . . . . . . . . . . . . . . . . . . . . . . . . . 32
8.1 General factors affecting device convergence . . . . . . . . 32
8.1.1 Number of peers . . . . . . . . . . . . . . . . . . . . . . 32
8.1.2 Number of routes per peer . . . . . . . . . . . . . . . . . 32
8.1.3 Policy processing/reconfiguration . . . . . . . . . . . . . 32
8.1.4 Interactions with other protocols . . . . . . . . . . . . . 32
8.1.5 Flap Damping . . . . . . . . . . . . . . . . . . . . . . . . 33
8.1.6 Churn . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
8.2 Implementation-specific and other factors affecting BGP
convergence . . . . . . . . . . . . . . . . . . . . . . . . 33
8.2.1 Forwarded traffic . . . . . . . . . . . . . . . . . . . . . 34
8.2.2 Timers . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
8.2.3 TCP parameters underlying BGP transport . . . . . . . . . . 34
8.2.4 Authentication . . . . . . . . . . . . . . . . . . . . . . . 34
9. Security Considerations . . . . . . . . . . . . . . . . . . 35
10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . 36
Normative References . . . . . . . . . . . . . . . . . . . . 37
Informative References . . . . . . . . . . . . . . . . . . . 38
For Internet Draft consistency purposes only . . . . . . . . 39
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . 39
Intellectual Property and Copyright Statements . . . . . . . 41
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 RFC1771 [1]). It is the first
part of a two document series, of which the subsequent document will part of a two document series, of which the subsequent document will
contain the associated tests and methodology. This terminology is contain the associated tests and methodology. This terminology is
applicable to both IPv4 and IPv6. Illustrative examples of each applicable to both IPv4 and IPv6. Illustrative examples of each
version are included where relevant. version are included where relevant. Although IPv6 will require the
use of MP-BGP, we will not deal with issues related to RFC 2283 [17]
in this draft.
The following observations underlie the approach adopted in this, and The following observations underlie the approach adopted in this, and
the companion document: the companion document:
- The principal objective is to derive methodologies to standardize
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.
- 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.
- 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
turned off. All variable parameters should be in their default
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
policy processing, simultaneous traffic on the control and data paths Multiprotocol Extensions for BGP-4, policy processing, simultaneous
within the DUT, and other realistic performance modifiers. traffic on the control and data paths within the DUT, and other
Convergence of Interior Gateway Protocols will also be considered in realistic performance modifiers. Convergence of Interior Gateway
separate drafts. Protocols will also be considered in separate drafts.
1.1 Overview and Roadmap 1.1 Overview and Roadmap
Characterizations of the BGP convergence performance of a device must Characterizations of the BGP convergence performance of a device must
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 two separate The necessary definitions are classified into separate categories:
categories:
- Descriptions of the constituent elements of a network or a router 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 that is undergoing convergence
- Descriptions of factors that impact convergence processes
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 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 [3], and is
repeated here for convenience: repeated here for convenience:
X.x Term to be defined. (e.g., Latency) X.x Term to be defined. (e.g., Latency)
Definition: Definition:
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 restrictions that there might be on measurement procedures.
procedures.
Measurement units: Measurement units:
The units used to report measurements of this term, if The units used to report measurements of this term, if applicable.
applicable.
Issues: Issues:
List of issues or conditions that could affect this term. List of issues or conditions that could affect this term.
See Also: See Also:
List of related terms that are relevant to the definition List of related terms that are relevant to the definition or
or discussion of this term. discussion of this term.
2. Constituent elements of a router or network of routers.
Many terms included in this list of definitions were originally 2. Components and characteristics of Routing information
described in previous standards or papers. They are included here
because of their pertinence to this discussion. Where relevant,
reference is made to these sources. An effort has been made to keep
this list complete with regard to the necessary concepts without over
definition.
2.1 BGP Instance or Device 2.1 (Network) Prefix
Definition: Definition:
A BGP instance is a process with a single Loc-RIB that "A network prefix is a contiguous set of bits at the more
runs on a BGP device. 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)", in [3].)
Discussion: Discussion:
We have chosen to use "device" as the general case, to In the CIDR context, the network prefix is the network component
deal with the understood [e.g. [9]] and yet-to-be-invented of an IP address.
cases where the control processing may be separate from
forwarding [12]. A BGP device may be a traditional
router, a route server, a BGP-aware traffic steering
device, a device using BGP to exchange topology
information with a GMPLS environment, etc. A device such
as a route server, for example, never forwards traffic, so
forwarding-based measurements would be meaningless for it.
Measurement units: N/A Measurement Units: N.A.
Issues: Issues:
See Also: See Also:
2.2 BGP Peer 2.2 Network Prefix Length
Definition: Definition:
A BGP peer is another BGP instance to which the Device The network prefix length is the number of bits out of the total
Under Test (DUT) has established a TCP connection over available in the address field, used to define the network prefix.
which a BGP session is active. In the test scenarios in
the methodology discussion that will follow this draft,
peers send BGP advertisements to the DUT and receive DUT-
originated advertisements.
Discussion: Discussion:
This is a protocol-specific definition, not to be confused A common alternative to using a bit-wise mask to communicate this
with another frequent usage, which refers to the component is the use of "slash (/) notation." Slash notation binds
business/economic definition for the exchange of routes the notion of network prefix length in bits to an IP address.
without financial compensation. E.g., 141.184.128.0/17 indicates the network component of this
IPv4 address is 17 bits wide. Similar notation is used for IPv6
network prefixes e.g. :FF02:20::/24
It is worth noting that a BGP peer, by this definition is When referring to groups of addresses, the network prefix length
associated with a BGP peering session, and there may be is often used as a means of describing groups of addresses as an
more than one such active session on a router or on a equivalence class. For example, 'one hundred /16 addresses'
tester. The peering sessions referred to here may exist refers to 100 addresses whose network prefix length is 16 bits.
between various classes of BGP routers (see section 2.3).
Measurement units: number of BGP peers Measurement units: bits
Issues: Issues:
See Also: See Also: network prefix
2.3 Default Route, Default Free Table, and Full Table 2.3 Route
An individual router's routing table may not necessarily contain a Definition:
default route. Not having a default route, however, is not In general, a 'route' is the n-tuple
synonymous with having a full default-free table(DFT). <prefix, nexthop, other routing or non-routing protocol
It should be noted that the references to number of routes in this attributes]>
section are to routes installed in the loc-RIB, not route instances,
and that the total number of route instances may be 4 to 10 times the
number of routes.
The actual path setup and forwarding of MPLS speaking routers are A route is not end-to-end, but is defined with respect to a
outside the scope of this document. A device that computes BGP specific next hop that will move traffic closer to the destination
routes, which a sub-IP device can use to set up paths, has its BGP defined by the prefix. In this usage, a route is the basic unit of
aspects within scope. information about a target destination distilled from routing
protocols.
2.3.1 Default Route 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: Definition:
A Default Route is a route entry that can match any A BGP route is an n-tuple
prefix. If a router does not have a route for a particular <prefix, nexthop, ASpath [, other BGP attributes]>.
packet's destination address, it forwards this packet to
the next hop in the default route entry, provided its
Forwarding Table (Forwarding Information Base (FIB)
contains one. The notation for a default route for IPv4 is
0.0.0.0/0 and for IPv6 it is 0:0:0:0:0:0:0:0 or ::/0.
Discussion: Discussion:
BGP Attributes, such as Nexthop or AS path are defined in RFC
1771[1], where they are known as Path Attributes, and are the
qualifying data that define the route.
Measurement units: N.A. 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: Issues:
See Also: default free routing table, route, route instance See Also: Route, prefix, Adj-RIB-in, NLRI.
2.3.2 Default Free Routing Table 2.5 Network Level Reachability Information (NLRI)
Definition: Definition:
A default free routing table has no default routes and is The NRLI consists of one or more network prefixes with the same
typically seen in routers in the core or top tier of set of path attributes.
routers in the network.
Discussion: Discussion:
The term originates from the concept that routers at the Each prefix in the NLRI is combined with the (common) path
core or top tier of the Internet will not be configured attributes to form a BGP route. The NLRI encapsulates a set of
with a default route (Notation in IPv4 0.0.0.0/0 and in destinations to which packets can be routed (from this point in
IPv6 0:0:0:0:0:0:0:0 or ::/0). Thus they will forward the network) along a common route described by the path
every prefix to a specific next hop based on the longest attributes.
match on the IP addresses.
Default free routing table size is commonly used as an Measurement Units: N.A.
indicator of the magnitude of reachable Internet address
space. However, default free routing tables may also
include routes internal to the router's AS.
Measurements: The number of routes Issues:
See Also: Full Default Free, Default Route See Also: Route Packing, Network Prefix, BGP Route, NLRI
2.3.3 Full Default Free Table 2.6 BGP UPDATE message
Definition: Definition:
A full default free table is a set of BGP routes generally An UPDATE message contains an advertisement of a single NLRI
accepted to be the complete set of BGP routes collectively field, possibly containing multiple prefixes, and multiple
announced by the complete set of autonomous systems making withdrawals of unfeasible routes. See RFC 1771 ([1]) for details.
up the public Internet. Due to the dynamic nature of the
Internet, the exact size and composition of this table may
vary slightly depending where and when it is observed.
Discussion: Discussion:
Several investigators ([17],[18],[19]) measure this on a From RFC 1771: "A variable length sequence of path attributes is
daily and/or weekly basis; June 2001 measurements put the present in every UPDATE. Each path attribute is a triple
table at approximately 105,000 routes, growing <attribute type, attribute length, attribute value> of variable
exponentially. length."
It is generally accepted that a full table, in this usage, Measurement Units: N.A.
does not contain the infrastructure routes or individual
sub-aggregates of routes that are otherwise aggregated by
the provider before announcement to other autonomous
systems.
Measurement Units: number of routes See Also
Issues: 3. Routing Data Structures and Route Categories
See Also: Routes, Route Instances, Default Route 3.1 Routing Information Base (RIB)
2.3.4 Full Provider Internal Table 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: Definition:
A full provider internal table is a superset of the full Adj-RIB-In and Adj-RIB-Out are "views" of routing information from
routing table that contains infrastructure and non- the perspective of individual peer routers.
aggregated routes.
Discussion: The Adj-RIB-In contains information advertised to the DUT by a
Experience has shown that this table can contain 1.3 to specific peer. The Adj-RIB-Out contains the information the DUT
1.5 times the number of routes in the externally visible will advertise to the peer.
full table. Tables of this size, therefore, are a real-
world requirement for key internal provider routers.
Measurement Units: number of routes See RFC 1771[1].
Issues: Discussion:
See Also: Routes, Route Instances, Default Route Issues:
2.4 Classes of BGP-Speaking Routers Measurement Units: Number of route instances
A given router may perform more than one of the following functions, See Also:
based on its logical location in the network. Route, BGP Route, Route Instance, Loc-RIB, FIB
2.4.1 Provider Edge Router 3.1.2 Loc-RIB
Definition: Definition:
A provider edge router is a router at the edge of a The Loc-RIB contains the set of best routes selected from the
provider's network, configured to speak BGP, which peers various Adj-RIBs, after applying local policies and the BGP route
with a BGP speaking router operated by the end-user. The selection algorithm.
traffic that transits this router may be destined to, or
originate from non-contiguous autonomous systems.
Discussion: Discussion:
Such a router will always speak eBGP and may speak iBGP. The separation implied between the various RIBs is logical. It
does not necessarily follow that these RIBs are distinct and
separate entities in any given implementation.
Measurement units: Types of routes can include internal BGP, external BGP, interface,
static and IGP routes.
Issues: Issues:
Measurement Units: Number of routes
See Also: See Also:
Route, BGP Route, Route Instance, Adj-RIB-in, Adj-RIB-out,FIB
2.4.2 Subscriber Edge Router 3.2 Routing Policy
Definition: Definition:
A subscriber edge router is a BGP-speaking router Routing Policy is "the ability to define conditions for accepting,
belonging to an end user organization that may be multi- rejecting, and modifying routes received in advertisements"[9].
homed, and which carries traffic only to and from that end
user AS.
Discussion: Discussion:
Such a router will always speak eBGP and may speak iBGP. RFC 1771 [1] further constrains policy to be within the hop-by-hop
routing paradigm. Policy is implemented using filters and
associated policy actions. Many AS's formulate and document their
policies using the Routing Policy Specification Language (RPSL)
[6] and then automatically generate configurations for the BGP
processes in their routers from the RPSL specifications.
Measurement units: Measurement Units: Number of policies; length of policies
Issues: Issues:
See Also: See Also: Routing Policy Information Base.
2.4.3 Inter-provider Border Router 3.3 Routing Policy Information Base
Definition: Definition:
An inter-provider border router is a BGP speaking router A routing policy information base is the set of incoming and
which maintains BGP sessions with another BGP speaking outgoing policies.
router in another provider AS. Traffic transiting this
router may be directed to or from another AS that has no
direct connectivity with this provider's AS.
Discussion: Discussion:
Such a router will always speak eBGP and may speak iBGP. All references to the phase of the BGP selection process below are
made with respect to RFC 1771 [1] definition of these phases.
Measurement units: 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
Phase 2 decision process. Outgoing Policies are applied in Phase
3 of the BGP process to the Adj-RIB-Out routes preceding route
(prefix and path attribute tuple) announcements to a specific
peer.
Policies in the Policy Information Base have matching and action
conditions. Common information to match include route prefixes,
AS paths, communities, etc. The action on match may be to drop
the update and not pass it to the Loc-RIB, or to modify the update
in some way, such as changing local preference (on input) or MED
(on output), adding or deleting communities, prepending the
current AS in the AS path, etc.
The amount of policy processing (both in terms of route maps and
filter/access lists) will impact the convergence time and
properties of the distributed BGP algorithm. The amount of policy
processing may vary from a simple policy which accepts all routes
and sends all routes to complex policy with a substantial fraction
of the prefixes being filtered by filter/access lists.
Measurement Units: Number and length of policies
Issues: Issues:
See Also: See Also:
2.4.4 Intra-provider Core Router 3.4 Forwarding Information Base (FIB)
Definition: Definition:
An intra-provider core router is a provider router As according to the definition in Appendix B of [4]: "The table
speaking iBGP to the provider's edge routers, other intra- containing the information necessary to forward IP Datagrams is
provider core routers, or the provider's inter-provider called the Forwarding Information Base. At minimum, this contains
border routers. the interface identifier and next hop information for each
reachable destination network prefix."
Discussion: Discussion:
Such a router will always speak iBGP and may speak eBGP. The forwarding information base describes a database indexing
network prefixes versus router port identifiers.
Measurement units: 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 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: Issues:
MPLS speaking routers are outside the scope of this
document. It is entirely likely, however, that core Label
Switched Routers, especially in the P router role of
RFC 2547 [10], may contain little or no BGP information.
See Also: See Also: Route, RIB
3. Routing Data Structures 3.5 BGP Instance
3.1 Routing Information Base (RIB) Definition:
A BGP instance is a process with a single Loc-RIB.
The RIB collectively consists of a set of logically (not necessarily Discussion:
literally) distinct databases, each of which is enumerated below. The For example, a BGP instance would run in routers or test
RIB contains all destination prefixes to which the router may equipment. A test generator acting as multiple peers will
forward, and one or more currently reachable next hop addresses for typically run more than one instance of BGP. A router would
them. typically run a single instance.
Routes included in this set potentially have been selected from Measurement units: N/A
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 Issues:
Definition: See Also:
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 3.6 BGP Device
by a specific peer. The Adj-RIB-Out contains the
information the DUT will advertise to the peer.
See RFC 1771[1]. 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: Discussion:
We have chosen to use "device" as the general case, to deal with
the understood [e.g. [9]] and yet-to-be-invented cases where the
control processing may be separate from forwarding [12]. A BGP
device may be a traditional router, a route server, a BGP-aware
traffic steering device or a non forwarding route reflector. BGP
instances such as route reflectors or servers, for example, never
forwards traffic, so forwarding-based measurements would be
meaningless for it.
Issues: Measurement units: N/A
Measurement Units: Number of route instances Issues:
See Also: Route, BGP Route, Route Instance, Loc-RIB, FIB See Also:
3.1.2 Loc-RIB 3.7 BGP Session
Definition: Definition:
The Loc-RIB contains the set of best routes selected from A BGP session is a session between two BGP instances.
the various Adj-RIBs, after applying local policies and
the BGP route selection algorithm.
Discussion: Discussion:
The separation implied between the various RIBs is
logical. It does not necessarily follow that these RIBs
are distinct and separate entities in any given
implementation.
Types of routes can include internal BGP, external Measurement units: N/A
BGP,interface, static and IGP routes.
Issues: Issues:
Measurement Units: Number of route instances. See Also:
See Also: Route, BGP Route, Route Instance, Adj-RIB-in,
Adj-RIB-out,FIB
3.2 Policy 3.8 Active BGP Session
Definition: Definition:
Policy is "the ability to define conditions for accepting, An active BGP session is one which is in the established state.
rejecting, and modifying routes received in (See RFC 1771 [1]).
advertisements"[9].
Discussion: Discussion:
RFC 1771 [1] further constrains policy to be within the
hop-by-hop routing paradigm. Policy is implemented using
filters and associated policy actions. Many AS's
formulate and document their policies using the Routing
Policy Specification Language (RPSL) [6] and then
automatically generate configurations for the BGP
processes in their routers from the RPSL specifications.
Measurement Units: Number of policies; length of policies Measurement units: N/A
Issues: Issues:
See Also: Policy Information Base. See Also:
3.3 Policy Information Base 3.9 BGP Peer
Definition: Definition:
A policy information base is the set of incoming and A BGP peer is another BGP instance to which the Device Under Test
outgoing policies. (DUT) is in the Established state. (See RFC 1771 [1]).
Discussion: Discussion:
All references to the phase of the BGP selection process In the test scenarios in the methodology discussion that will
below are made with respect to RFC 1771 [1] definition of follow this draft, peers send BGP advertisements to the DUT and
these phases. receive DUT-originated advertisements. We recommend that the
peering relation be established before tests are begun. It might
also be interesting to measure the time required to reach the
established state.
Incoming policies are applied in Phase 1 of the BGP This is a protocol-specific definition, not to be confused with
selection process [1] to the Adj-RIB-In routes to set the another frequent usage, which refers to the business/economic
metric for the Phase 2 decision process. Outgoing definition for the exchange of routes without financial
Policies are applied in Phase 3 of the BGP process to the compensation.
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 It is worth noting that a BGP peer, by this definition is
action conditions. Common information to match include associated with a BGP peering session, and there may be more than
route prefixes, AS paths, communities, etc. The action on one such active session on a router or on a tester. The peering
match may be to drop the update and not pass it to the sessions referred to here may exist between various classes of BGP
Loc-RIB, or to modify the update in some way, such as routers (see Section 4.2).
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 Measurement units: number of BGP peers
maps and filter/access lists) will impact the convergence
time and properties of the distributed BGP algorithm. The
amount of policy processing may vary from a simple policy
which accepts all routes and sends all routes to complex
policy with a substantial fraction of the prefixes being
filtered by filter/access lists.
Measurement Units: Number and length of policies Issues:
See Also:
3.10 BGP Neighbor
Definition:
A BGP neighbor is a device that can be configured as a BGP peer.
Discussion:
Measurement units:
Issues: Issues:
See Also: See Also:
3.4 Forwarding Information Base (FIB) 3.11 MinRouteAdvertisementInterval (MRAI)
Definition: Definition:
As according to the definition in Appendix B of [4]: (Paraphrased from 1771[1]) The MRAI timer determines the minimum
"The table containing the information necessary to forward time between advertisements of routes to a particular destination
IP Datagrams is called the Forwarding Information Base. (prefix) from a single BGP device. The timer is applied on a
At minimum, this contains the interface identifier and pre-prefix basis, although the timer is set on a per BGP device
next hop information for each reachable destination basis.
network prefix."
Discussion: Discussion:
The forwarding information base describes a database Given that a BGP instance may manage in excess of 100,000 routes,
indexing network prefixes versus router port identifiers. RFC 1771 allows for a degree of optimization in order to limit the
number of timers needed. The MRAI does not apply to routes
received from BGP speakers in the same AS or to explicit
withdrawals.
The forwarding information base is distinct from the RFC 1771 also recommends that random jitter is applied to MRAI in
"routing table" (the Routing Information Base or RIB), an attempt to avoid synchronization effects between the BGP
which holds all routing information received from routing instances in a network.
peers. The Forwarding Information Base is generated from
the RIB. For the purposes of this document, the FIB is
effectively the subset of the RIB used by the forwarding
plane to make per-packet forwarding decisions.
Most current implementations have full, non-cached FIBs In this document we define routing plane convergence by measuring
per router interface. All the route computation and the time an NLRI is advertised to the DUT to the time it is
convergence occurs before entries are downloaded into a advertised from the DUT. Clearly any delay inserted by the MRAI
FIB. will have a significant effect on this measurement.
Measurement units: N.A. Measurement Units: seconds.
Issues: Issues:
See Also: Route, RIB See Also: NLRI, BGP route
4. Components and characteristics of Routing information
4.1 (Network) Prefix 3.12 MinASOriginationInterval (MAOI)
Definition: Definition:
"A network prefix is . . . a contiguous set of bits at the The MAOI specifies the minimum interval between advertisements of
more significant end of the address that defines a set of locally originated routes from this BGP instance.
systems; host numbers select among those systems."
(This definition is taken directly from section 2.2.5.2,
"Classless Inter Domain Routing (CIDR)", in [3].)
Discussion: Discussion:
In the CIDR context, the network prefix is the network Random jitter is applied to MAOI in an attempt to avoid
component of an IP address. synchronization effects between BGP instances in a network.
Measurement Units: N.A. Measurement Units: seconds
Issues: Issues:
It is not known what, if any relationship exists between the
settings of MRAI and MAOI.
See Also See Also: MRAI, BGP route
4.2 Network Prefix Length 3.13 Active Route
Definition: Definition:
The network prefix length is the number of bits used to Route for which there is a FIB entry corresponding to a RIB entry.
define the network prefix.
Discussion: Discussion:
A common alternative to using a bit-wise mask to
communicate this component is the use of "slash (/)
notation." Slash notation binds the notion of network
prefix length (see 4.2) in bits to an IP address. E.g.,
141.184.128.0/17 indicates the network component of this
IPv4 address is 17 bits wide. Similar notation is used for
IPv6 network prefixes e.g. :FF02:20::/24
When referring to groups of addresses, the network prefix Measurement Units: Number of routes.
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: RIB.
3.14 Unique Route
Definition:
A unique route is a prefix for which there is just one route
instance across all Adj-Ribs-In.
Discussion:
Measurement Units: N.A.
Issues: Issues:
See Also: network prefix See Also: route, route instance
4.3 Route 3.15 Non-Unique Route
Definition: Definition:
In general, a 'route' is the n-tuple A Non-unique route is a prefix for which there is at least one
<prefix, nexthop[, other non-routing protocol attributes]> other route in a set including more than one Adj-RIB-in.
A route is not end-to-end, but is defined with respect to
a specific next hop that will move traffic closer to the
destination defined by the prefix. In this usage, a route
is the basic unit of information about a target
destination distilled from routing protocols.
Discussion: 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. Measurement Units: N.A.
Issues: None. Issues:
See Also: BGP route See Also:
route, route instance, unique active route.
4.4 BGP Route 3.16 Route Instance
Definition: Definition:
A BGP route is an n-tuple A route instance is one of several possible occurrences of a route
<prefix, nexthop, ASpath [, other BGP attributes]>. for a particular prefix.
Discussion: Discussion:
BGP Attributes, such as Nexthop or AS path are defined in When a router has multiple peers from which it accepts routes,
RFC 1771[1], where they are known as Path Attributes, and routes to the same prefix may be received from several peers. This
are the qualifying data that accompanies the network is then an example of multiple route instances.
prefixes in a BGP route UPDATE message. (An UPDATE message
may contain multiple prefixes that share a common set of
attributes).
From RFC 1771: " For purposes of this protocol a route is Each route instance is associated with a specific peer. The BGP
defined as a unit of information that pairs a destination selection algorithm may reject a specific route instance due to
with the attributes of a path to that destination... A local policy.
variable length sequence of path attributes is present in
every UPDATE. Each path attribute is a triple
<attribute type, attribute length, attribute value>
of variable length."
Measurement Units: N.A. Measurement Units: Number of route instances
Issues: Issues:
The number of route instances in the Adj-RIB-in bases will vary
based on the function to be performed by a router. An
inter-provider border router, located in the default free zone
(not defined) will likely receive more route instances than a
provider edge router, located closer to the end-users of the
network.
See Also: Route, prefix, Adj-RIB-in, NLRI. See Also:
4.5 BGP Route Attributes and BGP Timers 4. Constituent elements of a router or network of routers.
The definitions in this section refer to items that are originally Many terms included in this list of definitions were originally
defined in RFC 1771 [1] and are repeated here for convenience, and to described in previous standards or papers. They are included here
allow for some discussion beyond the definitions in RFC 1771. because of their pertinence to this discussion. Where relevant,
reference is made to these sources. An effort has been made to keep
this list complete with regard to the necessary concepts without over
definition.
4.5.1 Network Level Reachability Information (NLRI) 4.1 Default Route, Default Free Table, and Full Table
An individual router's routing table may not necessarily contain a
default route. Not having a default route, however, is not
synonymous with having a full default-free table(DFT).
It should be noted that the references to number of routes in this
section document are to routes installed in the loc-RIB and are
therefore unique routes, not route instances, and that the total
number of route instances may be 4 to 10 times the number of routes.
4.1.1 Default Route
Definition: Definition:
The NRLI consists of one or more network prefixes that A Default Route can match any destination address. If a router
share all other BGP path attributes and are distributed in does not have a more specific route for a particular packet's
the update portion (as opposed to the unfeasible routes destination address, it forwards this packet to the next hop in
portion) of a BGP UPDATE message. the default route entry, provided its Forwarding Table (Forwarding
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
::/0.
Discussion: Discussion:
Each prefix in the NLRI is combined with the (common)
path attributes in the UPDATE message 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. Measurement units: N.A.
Issues: Issues:
See Also: Route Packing, Network Prefix, BGP Route, NLRI See Also: default free routing table, route, route instance
4.5.2 MinRouteAdvertisementInterval (MRAI) 4.1.2 Default Free Routing Table
Definition: Definition:
(Paraphrased from 1771[1]) The MRAI timer determines the A default free routing table has no default routes and is
minimum time between advertisements of routes to a typically seen in routers in the core or top tier of routers in
particular destination (prefix) from a single BGP device. the network.
The timer is applied on a pre-prefix basis, although the
timer is set on a per BGP device basis.
Discussion: Discussion:
Given that a BGP instance may manage in excess of 100,000 The term originates from the concept that routers at the core or
routes, RFC 1771 allows for a degree of optimization in top tier of the Internet will not be configured with a default
order to limit the number of timers needed. The MRAI does route (Notation in IPv4 0.0.0.0/0 and in IPv6 0:0:0:0:0:0:0:0 or
not apply to routes received from BGP speakers in the same ::/0). Thus they will forward every packet to a specific next hop
AS or to explicit withdrawals. based on the longest match between the destination IP addresse
and the routes in the forwarding table.
RFC 1771 also recommends that random jitter is applied to Default free routing table size is commonly used as an indicator
MRAI in an attempt to avoid synchronization effects of the magnitude of reachable Internet address space. However,
between the BGP instances in a network. default free routing tables may also include routes internal to
the router's AS.
In this document we define RIB convergence by measuring Measurement Units: The number of routes
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 will have a significant effect on this
measurement.
Measurement Units: seconds. See Also: Full Default Free, Default Route
4.1.3 Full Default Free Table
Definition:
A full default free table is the union of all sets of default free
BGP routes collectively announced by the complete set of
autonomous systems making up the public Internet. Due to the
dynamic nature of the Internet, the exact size and composition of
this table may vary slightly depending where and when it is
observed.
Discussion:
It is generally accepted that a full table, in this usage, does
not contain the infrastructure routes or individual sub-aggregates
of routes that are otherwise aggregated by the provider before
announcement to other autonomous systems.
Measurement Units: number of routes
Issues: Issues:
See Also: NLRI, BGP route See Also: Routes, Route Instances, Default Route
4.5.3 MinASOriginationInterval (MAOI) 4.1.4 Default-Free Zone
Definition: Definition:
The MAOI specifies the minimum interval between The default-free zone is that part of the Internet backbone that
advertisements of locally originated routes from this BGP does not have a default route.
instance.
Discussion: Discussion:
Random jitter is applied to MAOI in an attempt to avoid
synchronization effects between BGP instances in a
network.
Measurement Units: seconds Measurement Units:
Issues: Issues:
See Also: MRAI, BGP route See Also: Default Route
4.6 Route Instance 4.1.5 Full Provider-Internal Table
Definition: Definition:
A route instance is a single occurrence of a route sent by A full provider-internal table is a superset of the full routing
a BGP Peer for a particular prefix. When a router has table that contains infrastructure and non- aggregated routes.
multiple peers from which it accepts routes, routes to the
same prefix may be received from several peers. This is
then an example of multiple route instances.
Discussion: Discussion:
Each route instance is associated with a specific peer. Experience has shown that this table can contain 1.3 to 1.5 times
The BGP selection algorithm may reject a specific route the number of routes in the externally visible full table. Tables
instance due to local policy. of this size, therefore, are a real-world requirement for key
internal provider routers.
Measurement Units: Number of route instances Measurement Units: number of routes
Issues: Issues:
The number of route instances in the Adj-RIB-in bases will
vary based on the function to be performed by a router. An
inter-provider router, located in the default free zone
will likely receive more route instances than a provider
edge router, located closer to the end-users of the
network.
See Also: See Also: Routes, Route Instances, Default Route
4.7 Active Route 4.2 Classes of BGP-Speaking Routers
A given router may perform more than one of the following functions,
based on its logical location in the network.
4.2.1 Provider Edge Router
Definition: Definition:
Route for which there is a FIB entry corresponding to a A provider edge router is a router at the edge of a provider's
RIB entry. network that speaks eBGP to a BGP speaker in another AS.
Discussion: Discussion:
The traffic that transits this router may be destined to, or
originate from non-contiguous autonomous systems.
Measurement Units: Number of routes. Such a router will always speak eBGP and may speak iBGP.
Measurement units:
Issues: Issues:
See also: RIB. See Also:
4.8 Unique Route 4.2.2 Subscriber Edge Router
Definition: Definition:
A unique route is a prefix for which there is just one A subscriber edge router is router at the edge of the subscriber's
route instance across all Adj-Ribs-In. network that speaks eBGP to its provider's AS(s).
Discussion: Discussion:
The router belongs to an end user organization that may be multi-
homed, and which carries traffic only to and from that end user
AS.
Measurement Units: N.A. Such a router will always speak eBGP and may speak iBGP.
Measurement units:
Issues: Issues:
See Also: route, route instance See Also:
4.9 Non-Unique Route 4.2.3 Inter-provider Border Router
Definition: Definition:
A Non-unique route is a prefix for which there is at least An inter-provider border router is a BGP speaking router which
one other route in a set including more than one Adj-RIB- maintains BGP sessions with otherBGP speaking routers in other
in. providers' ASs.
Discussion: Discussion:
Traffic transiting this router may be originated in or destined
for another AS that has no direct connectivity with this
provider's AS.
Measurement Units: N.A. Such a router will always speak eBGP and may speak iBGP.
Measurement units:
Issues: Issues:
See Also: route, route instance, unique active route. See Also:
4.10BGP UPDATE message 4.2.4 Core Router
Definition: Definition:
An UPDATE message is an advertisement of a single NLRI, An core router is a provider router Internal to the provider's
possibly containing multiple prefixes, and multiple net, speaking iBGP to that provider's edge routers, other intra-
withdrawals of unfeasible routes. See RFC 1771 ([1]) for provider core routers, or the provider's inter-provider border
details. routers.
Discussion: Discussion:
Such a router will always speak iBGP and may speak eBGP.
Measurement Units: N.A. Measurement units:
Issues: Issues:
Then by this definition they aren't core routers.
4.11Characterization of sets of update messages See Also:
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, a concept originally introduced by definition of an Update Train. The Packet train concept was
Jain and Routhier [11]. This is a formalization of the sort of test originally introduced by Jain and Routhier [11]. It is here adapted
stimulus that is expected as input to a DUT running BGP. This data to refer to a train of packets of interest in BGP performance
could be a well-characterized, ordered and timed set of hand-crafted testing.
BGP UPDATE packets. It could just as well be a set of BGP UPDATE
packets that have been captured from a live router. This is a formalization of the sort of test stimulus that is expected
as input to a DUT running BGP. This data could be a
well-characterized, ordered and timed set of hand-crafted BGP UPDATE
packets. It could just as well be a set of BGP UPDATE packets that
have been captured from a live router.
Characterization of route mixtures and Update Trains is an open area 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
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.
4.11.1 Route Packing 5.1 Route Packing
Definition: Definition:
Route packing is the number of route prefixes accommodated Route packing is the number of route prefixes accommodated in a
in a single Routing Protocol UPDATE Message either as single Routing Protocol UPDATE Message either as updates
updates (additions or modifications) or withdrawals. (additions or modifications) or withdrawals.
Discussion: Discussion:
In general, a routing protocol update may contain more In general, a routing protocol update may contain more than one
than one prefix. In BGP, a single UPDATE may contain two prefix. In BGP, a single UPDATE may contain two sets of multiple
sets of multiple network prefixes: one set of additions network prefixes: one set of additions and updates with identical
and updates with identical attributes (the NLRI) and one attributes (the NLRI) and one set of unfeasible routes to be
set of unfeasible routes to be withdrawn. withdrawn.
Measurement Units: Measurement Units:
Number of prefixes. Number of prefixes.
Issues: Issues:
See Also: route, BGP route, route instance, update train, NLRI. See Also:
route, BGP route, route instance, update train, NLRI.
4.11.2 Route Mixture
5.2 Route Mixture
Definition: Definition:
A collection of routes such as an NLRI, a set of UPDATE A route mixture is the demographics of a set of routes.
messages or a RIB.
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 particular route mixture used as input must be selected to suit
suit the question being asked of the benchmark. the question being asked of the benchmark. Data containing simple
Data containing simple route mixtures, such as 100,000 /32 route mixtures might be suitable to test the performance limits of
routes might test the performance limits of the BGP the BGP device.
device.
Using live data, or input that simulates live data, should Using live data, or input that simulates live data, should improve
improve understanding of how the BGP device will operate understanding of how the BGP device will operate in a live
in a live network. The data for this kind of test must be network. The data for this kind of test must be route mixtures
route mixtures that model the patterns of arriving control that model the patterns of arriving control traffic in the live
traffic in the live Internet. Internet.
To accomplish that kind of modeling it is necessary to To accomplish that kind of modeling it is necessary to identify
identify the key parameters that characterize a live the key parameters that characterize a live Internet route
Internet route mixture. The parameters and how they mixture. The parameters and how they interact is an open research
interact is an open research problem. However, we problem. However, we identify the following as affecting the
identify the following as affecting the route mixture: route mixture:
- Path length distribution
- Attribute distribution * Path length distribution
- Prefix distribution
- Packet packing * Attribute distribution
- Probability density function of inter-arrival times of
UPDATES Each of the items above is more * Prefix length distribution
complex than a singlenumber. For example, one could
consider the distribution of prefixes by AS or * Packet packing
* Probability density function of inter-arrival times of
UPDATES
Each of the items above is more complex than a single number. For
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.
4.11.3 Update Train 5.3 Update Train
Definition: Definition:
An update train is a set of Routing Protocol UPDATE An update train is a set of Routing Protocol UPDATE messages sent
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 The arrival pattern of UPDATEs can be influenced by many things,
things, including TCP parameters, hold-down timers, BGP including TCP parameters, hold-down timers, upsteam processing, a
header processing, a peer coming up or multiple peers peer coming up or multiple peers sending at the same time.
sending at the same time. Network conditions such as a Network conditions such as a local or remote peer flapping a link
local or remote peer flapping a link can also affect the can also affect the arrival pattern.
arrival pattern.
Measurement units: Measurement units:
Probability density function for the inter-arrival times Probability density function for the inter-arrival times of UPDATE
of UPDATE packets in the train. packets in the train.
Issues: Issues:
Characterizing the profiles of real world UPDATE trains is Characterizing the profiles of real world UPDATE trains is a
a matter for future research. In order to generate matter for future research. In order to generate realistic UPDATE
realistic UPDATE trains as test stimuli a formal trains as test stimuli a formal mathematical scheme or a proven
mathematical scheme or a proven heuristic is needed to heuristic is needed to drive the selection of prefixes. Whatever
drive the selection of prefixes. Whatever mechanism is mechanism is selected it must generate Update trains that have
selected it must generate Update trains that have similar similar characteristics to those measured in live networks.
characteristics to those measured from live routers.
See Also: Route Mixture, MRAI, MAOI See Also: Route Mixture, MRAI, MAOI
4.11.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:
- A route mixture randomized across o A route mixture randomized across
- NLRIs
- updates and withdrawals * NLRIs
- prefixes
- inter-arrival times of the UPDATEs * updates and withdrawals
* prefixes
* 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. favoring one vendor's implementation over another's. Specifically,
Specifically, the distribution of prefixes could be structured to the distribution of prefixes could be structured to favor the
favor the internal organization of the routes in a particular internal organization of the routes in a particular vendor's
vendor's databases. This is to be avoided. databases. This is to be avoided.
4.12Route Flap 5.5 Route Flap
Definition: Definition:
RIPE 210 [7] define a route flap as "the announcement and A route flap ia a change of state (withdrawal, announcement,
withdrawal of prefixes." For our purposes we define a attribute change) for a route.
route flap as the rapid withdrawal/announcement or
announcement/withdrawal of a prefix in the Adj-RIB-in. A
route flap is not a problem until a route is flapped
several times in close succession. This causes negative
repercussions throughout the internet.
Discussion: Discussion:
Route flapping can be considered a special and Route flapping can be considered a special and pathological case
pathological case of update trains. A practical of update trains. A practical interpretation of what may be
interpretation of what may be considered excessively rapid considered excessively rapid is the RIPE 229 [7], which contains
is the RIPE recommendation of "four flaps in a row". See current guidelines on flap damping parameters.
Section 6.1.5 on flap damping for further discussion.
Measurement units: Flapping events per unit time. Measurement units: Flapping events per unit time.
Issues: Issues:
Specific Flap events can be found in Section 5.1Route Specific Flap events can be found in Section 6.1. A bench-marker
Change Events. A bench-marker should use a mixture of should use a mixture of different route change events in testing.
different route change events in testing.
See Also: Route change events, flap damping, packet train See Also: Route change events, flap damping, packet train
5. Route Changes and Convergence 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.
5.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 [4] as well as Labovitz et al[5].
These papers describe BGP protocol-centric events, and event These papers describe BGP protocol-centric events, and event
sequences in the course of an analysis of network behavior. The sequences in the course of an analysis of network behavior. The
terminology in the two papers categorizes similar but slightly terminology in the two papers categorizes similar but slightly
different behaviors with some overlap. We would like to apply these different behaviors with some overlap. We would like to apply these
taxonomies to categorize the tests under definition where possible, taxonomies to categorize the tests under definition where possible,
because these tests must tie in to phenomena that arise in actual because these tests must tie in to phenomena that arise in actual
networks. We avail ourselves of, or may extend, this terminology as networks. We avail ourselves of, or may extend, this terminology as
necessary for this purpose. necessary for this purpose.
A route can be changed implicitly by replacing it with another route A route can be changed implicitly by replacing it with another route
or explicitly by withdrawal followed by the introduction of a new or explicitly by withdrawal followed by the introduction of a new
route. In either case the change may be an actual change, no change, route. In either case the change may be an actual change, no change,
or a duplicate. The notation and definition of individual or a duplicate. The notation and definition of individual
categorizable route change events is adopted from [5] and given categorizable route change events is adopted from [5] and given
below. below.
a) 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.
b) 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.
c) 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.
d) 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 definitions
of [5] to the following: of [5] to the following:
a) Tup (TDx): Route advertised to the DUT by Test Device x 1. Tup (TDx): Route advertised to the DUT by Test Device x
b) Tdown(TDx): Route being withdrawn by Device x
c) Tupinit(TDx): The initial announcement of a route to a unique 2. Tdown(TDx): Route being withdrawn by Device x
3. Tupinit(TDx): The initial announcement of a route to a unique
prefix prefix
d) 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 are
conveyed by the events above: conveyed by the events above:
a) Tup(1,TDx) means Device x sends 1 route 1. Tup(1,TDx) means Device x sends 1 route
b) Tup(S,TDx) means Device x sends a train, S, of routes
c) Tup(DFT,TDx) means Device x sends an approximation of a full 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
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 RFC1771, the router ID. As a consequence, this
memorandum uses the following descriptor events, which are routes memorandum uses the following descriptor events, which are routes
selected by the BGP selection process rather than simple updates: selected by the BGP selection process rather than simple updates:
a) Tbest -- The current best path. 1. Tbest -- The current best path.
b) Tbetter -- Advertise a path that is better than Tbest.
c) Tworse -- Advertise a path that is worse than Tbest.
5.2 Device Convergence in the Control Plane 2. Tbetter -- Advertise a path that is better than Tbest.
Definition 3. Tworse -- Advertise a path that is worse than Tbest.
A routing device is said to have converged at the point in
time when the DUT has performed all actions in the control 6.2 Device Convergence in the Control Plane
plane needed to react to changes in topology in the
context of the test condition. Definition:
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
to react to changes in topology in the context of the test
condition.
Discussion: Discussion:
For example, when considering BGP convergence, a change For example, when considering BGP convergence, the convergence
that alters the best route instance for a single prefix at resulting from a change that alters the best route instance for a
a router would be deemed to have converged when this route single prefix at a router would be deemed to have occurred when
is advertised to its downstream peers. Similarly, OSPF this route is advertised to its downstream peers. By way of
convergence concludes when SPF calculations have been contrast, OSPF convergence concludes when SPF calculations have
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 The convergence process, in general, can be subdivided into three
into three distinct phases: distinct phases:
- convergence across the entire Internet,
- convergence within an Autonomous System, * convergence across the entire Internet,
- convergence with respect to a single device.
* convergence within an Autonomous System,
* 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 the routing process(es), the
focus of this document.
It is the latter, convergence with regard to the routing * convergence with regard to data forwarding process(es)
process, that we describe in this and the methodology
documents. * convergence with regard to the routing process(es), the focus
of this document.
It is the latter, convergence with regard to the routing process,
that we describe in this and the methodology documents.
Because we are trying to benchmark the routing protocol Because we are trying to benchmark the routing protocol
performance which is only a part of the device overall, performance which is only a part of the device overall, this
this definition is intended (so far as is possible) to definition is intended (so far as is possible) to exclude any
exclude any additional time such as is needed to download additional time such as is needed to download and install the
and install the forwarding information base in the data forwarding information base in the data plane. This definition
plane. This definition should be usable for different should be usable for different families of protocols.
families of protocols.
It is of key importance to benchmark the performance of It is of key importance to benchmark the performance of each phase
each phase of convergence separately before proceeding to of convergence separately before proceeding to a composite
a composite characterization of routing convergence, where characterization of routing convergence, where
implementation-specific dependencies are allowed to implementation-specific dependencies are allowed to interact.
interact.
The time resolution needed to measure the device The time resolution needed to measure the device convergence
convergence depends to some extent on the types of the depends to some extent on the types of the interfaces on the
interfaces on the router. For modern routers with gigabit router. For modern routers with gigabit or faster interfaces, an
or faster interfaces, an individual UPDATE may be individual UPDATE may be processed and re-advertised in very much
processed and re-advertised in very much less than a less than a millisecond so that time measurements must be made to
millisecond so that time measurements must be made to a a resolution of hundreds to tens of microseconds or better.
resolution of hundreds to tens of microseconds or better.
Measurement Units: Measurement Units:
Time period. Time period.
Issues: Issues:
See Also: See Also:
6. BGP Operation Events 7. BGP Operation Events
The BGP speaker process(es) in a device restarts completely, for The BGP process(es) in a device might restart because operator
example, because of operator intervention or a power failure, or intervention or a power failure caused a complete shut-down. In this
fails partially because a TCP session has terminated for a particular case a hard reset is needed. A peering session could be lost, for
link. Until recently the BGP process would have to re-advertise all example, because of action on the part of the peer or a dropped tcp
relevant routes on reestablished links potentially triggering updates session. A device can reestablish its peers and re-advertise all
across the network. Recent work is focused on limiting the volume of relevant routes in a hard reset. However, if a peer is lost, but
updates due to operational events and the amount of processing the BGP process has not failed, BGP has mechanisms for a "soft
resulting from these events: This work includes soft refresh[12], a reset."
graceful restart mechanism [13] and cooperative route filtering
(e.g.[14]).
6.1 Hard reset 7.1 Hard reset
Definition: Definition:
An event which triggers a complete re-initialization of An event which triggers a complete re-initialization of the
the routing tables on one or more BGP sessions, resulting routing tables on one or more BGP sessions, resulting in exchange
in exchange of a full routing table on one or more links of a full routing table on one or more links to the router.
to the router.
Discussion: Discussion:
Measurement Units: N/A Measurement Units: N/A
Issues: Issues:
See Also: See Also:
6.2 Soft reset 7.2 Soft reset
Definition: Definition:
An event which results in a complete or partial restart of A soft reset is performed on a per-neighbor basis; it does not
the BGP session(s) on a BGP device, but which avoids the clear the BGP session while re-establishing the peering relation
exchange of a full table by maintaining state across the and does not stop the flow of traffic.
restart.
Discussion: Discussion:
There are two methods of performing a soft reset: Graceful restart
[13] where the BGP device that has lost a peer but continues to
forward traffic for a period of time before tearing down the
peer's routes. The alternative method is soft refresh [12], 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:
7. 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.
7.1 General factors affecting device convergence 8.1 General factors affecting device convergence
These factors are conditions of testing external to the router Device These factors are conditions of testing external to the router Device
Under Test (DUT). Under Test (DUT).
7.1.1 Number of peers 8.1.1 Number of peers
As the number of peers increases, the BGP route selection algorithm As the number of peers increases, the BGP route selection algorithm
is increasingly exercised. In addition, the phasing and frequency of is increasingly exercised. In addition, the phasing and frequency of
updates from the various peers will have an increasingly marked updates from the various peers will have an increasingly marked
effect on the convergence process on a router as the number of peers effect on the convergence process on a router as the number of peers
grows. Increasing the number of peers also increases the processing grows. Increasing the number of peers also increases the processing
workload for TCP and BGP keepalives. workload for TCP and BGP keepalives.
7.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 multiple
route instances and distinct routes being added or withdrawn by each route instances and distinct routes being added or withdrawn by each
peer will affect the convergence process, as will the mix of peer will affect the convergence process, as will the mix of
overlapping route instances, and IGP routes. overlapping route instances, and IGP routes.
7.1.3 Policy processing/reconfiguration 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
- Minimal Policy: receive all, send all,
- Extensive policy: up to 100% of the total routes have applicable o Minimal Policy: receive all, send all,
o Extensive policy: up to 100% of the total routes have applicable
policy. policy.
7.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.
7.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 [2] and discussed in RIPE-229 [7].
If this feature is in effect, it requires that the device keep If this feature is in effect, it requires that the device keep
additional state to carry out the damping, which can have a direct additional state to carry out the damping, which can have a direct
impact on the control plane due to increased processing. In impact on the control plane due to increased processing. In
addition, flap damping may delay the arrival of real changes in a addition, flap damping may delay the arrival of real changes in a
route, and affect convergence times route, and affect convergence times
7.1.6 Churn 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
keepalives and TCP processing. keepalives and TCP processing.
skipping to change at page 26, line 21 skipping to change at page 33, line 50
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 [16]. The goal of flap damping is to reduce the
contribution of flapping to churn. contribution of flapping to churn.
The effect of churn on overall convergence depends on the processing The effect of churn on overall convergence depends on the processing
power available to the control plane, and whether the same power available to the control plane, and whether the same
processor(s) are used for forwarding and for control. processor(s) are used for forwarding and for control.
7.2 Implementation-specific and other factors affecting BGP convergence 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
devices. devices.
7.2.1 Forwarded traffic 8.2.1 Forwarded traffic
The presence of actual traffic in the device may stress the control The presence of actual traffic in the device may stress the control
path in some fashion if both the offered load due to data and the path in some fashion if both the offered load due to data and the
control traffic (FIB updates and downloads as a consequence of control traffic (FIB updates and downloads as a consequence of
flaps)are excessive. The addition of data traffic presents a more flaps)are excessive. The addition of data traffic presents a more
accurate reflection of realistic operating scenarios than if only accurate reflection of realistic operating scenarios than if only
control traffic is present. control traffic is present.
7.2.2 Timers 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 should be reported if they use non-
default value. default value.
7.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: eg parameters characterizing the TCP sessions should be provided: e.g.
Slow start, max window size, maximum segment size, or timers. Slow start, max window size, maximum segment size, or timers.
7.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 [8]. The processing of the MD5 hash, particularly in devices
with a large number of BGP peers and a large amount of update traffic with a large number of BGP peers and a large amount of update traffic
can have an impact on the control plane of the device. can have an impact on the control plane of the device.
8. 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.
9. References 10. Acknowledgments
Normative
[1] Rekhter, Y. and Li, T., "A Border Gateway Thanks to Francis Ovenden for review and Abha Ahuja for
Protocol 4 (BGP-4)", RFC 1771, March 1995. encouragement. Much appreciation to Jeff Haas, Matt Richardson, and
Shane Wright at Nexthop for comments and input. Debby Stopp and Nick
Ambrose contributed the concept of route packing.
[2] Villamizar, C., Chandra, R. and Govindan, R., Normative References
"BGP Route Flap Damping", RFC 2439,
November 1998."
[3] Baker, F.,"Requirements for IP Version 4 [1] Rekhter, Y. and T. Li, "A Border Gateway Protocol 4 (BGP-4)",
Routers", RFC 1812. June 1995. RFC 1771, March 1995.
[4] Ahuja, A., Jahanian, F., Bose, A. and Labovitz, [2] Villamizar, C., Chandra, R. and R. Govindan , "BGP Route Flap
C., Damping", RFC 2439, November 1998.
"An Experimental Study of Delayed Internet
Routing Convergence", RIPE 37 - Routing WG.
[5] Labovitz, C., Malan, G.R. and Jahanian, F., [3] Baker, F., "Requirements for IP Version 4 Routers", RFC 1812,
"Origins of Internet Routing Instability," June 1995.
Infocom 99.
[6] Alaettinoglu, C., Villamizar, C., Gerich, E., [4] Ahuja, A., Jahanian, F., Bose, A. and C. Labovitz, "An
Kessens, D., Meyer, D., Bates, T., Karrenberg, Experimental Study of Delayed Internet Routing Convergence",
D. and Terpstra, M., "Routing Policy RIPE-37 Presentation to Routing WG, June 2000, <http://
Specification Language (RPSL)", RFC 2622, June www.ripe.net/ripe/meetings/archive/ripe-37/presentations/
1999. RIPE-37-convergence/>.
[7] Barber, T., Doran, S., Karrenberg, D., Panigl, [5] Labovitz, C., Malan, G. and F. Jahanian, "Origins of Internet
C., Schmitz, J., "RIPE Routing-WG Recommendation Routing Instability", Infocom 99, August 1999.
for coordinated route-flap damping parameters",
RIPE 210.
[8] Heffernan, A., "Protection of BGP Sessions via [6] Alaettinoglu, C., Villamizar, C., Gerich, E., Kessens, D.,
the TCP MD5 Signature Option", RFC 2385, August Meyer, D., Bates, T., Karrenberg, D. and M. Terpstra, "Routing
1998. Policy Specification Language (RPSL)", RFC 2622, June 1999.
[9] Juniper Networks,"Junos(tm) Internet Software [7] Panigl , C., Schmitz , J., Smith , P. and C. Vistoli, "RIPE
Configuration Guide Routing and Routing Routing-WG Recommendation for coordinated route-flap damping
Protocols, Release 4.2" parameters, version 2", RIPE 229, October 2001.
http://www.juniper.net/techpubs/software/junos42/
swconfig-routing42/html/glossary.html#1013039.
September 2000 (and other releases).
[10] Rosen, E. and Rekhter, Y., "BGP/MPLS VPNs", RFC [8] Heffernan, A., "Protection of BGP Sessions via the TCP MD5
2547, March 1999. Signature Option", RFC 2385, August 1998.
[11] Jain, R. and Routhier, S.A., "Packet trains -- [9] Juniper Networks, "Junos(tm) Internet Software Configuration
measurement and a new model for computer network Guide Routing and Routing Protocols, Release 4.2", Junos 4.2
traffic," IEEE Journal on Selected Areas in and other releases, September 2000, <http://www.juniper.net/
Communication, 4(6)September 1986. techpubs/software/junos42/swconfig-routing42/html/
glossary.html#1013039>.
Illustrative [10] Rosen, E. and Y. Rekhter, "BGP/MPLS VPNs", RFC 2547, March
1999.
[12] Chen, E., "Route Refresh for BGP-4", RFC 2918, [11] Jain, R. and S. Routhier, "Packet trains -- measurement and a
September 2000. new model for computer network traffic", IEEE Journal on
Selected Areas in Communication 4(6), September 1986.
[13] Ramachandra, S., Rekhter, Y., Fernando, R., Informative References
Scudder, J.G. and Chen, E.,
"Graceful Restart Mechanism for BGP",
draft-ietf-idr-restart-02.txt, January 2002,
work in progress.
[14] Chen, E. and Rekhter, Y, "Cooperative Route [12] Chen, E., "Route Refresh for BGP-4", RFC 2918, September 2000.
Filtering Capability for BGP-4",
draft-ietf-idr-route-filter-05.txt, January 2002,
work in progress.
[15] T. Anderson et al. "Requirements for Separation [13] Sangli, S., Rekhter, Y., Fernando, R., Scudder, J. and E. Chen,
of IP Control and Forwarding", "Graceful Restart Mechanism for BGP", draft-ietf-idr-restart-06
draft-ietf-forces-requirements-02.txt, (work in progress), January 2003.
February 2002, work in progress.
[16] McPherson, Gill, Walton, Retana, "BGP Persistent [14] Chen, E. and Y. Rekhter, "Cooperative Route Filtering
Route Oscillation Condition", Capability for BGP-4", draft-ietf-idr-route-filter-08 (work in
<draft-ietf-idr-route-oscillation-01.txt>, progress), January 2003.
February 2002, work In progress.
[17] Bates, T., "The CIDR Report", [15] Anderson, T. and H. Khosravi, "Requirements for Separation of
http://www.employees.org/~tbates/cidr-report.html IP Control and Forwarding", draft-ietf-forces-requirements-08
Internet statistics relevant to inter-domain (work in progress), January 2003.
routing updated daily.
[18] Smith, P. (designer), APNIC Routing Table [16] McPherson, D., Gill, V., Walton, D. and A. Retana, "Border
Statistics, http://www.apnic.net/stats/bgp/, Gateway Protocol (BGP) Persistent Route Oscillation Condition",
Statistics derived from a daily analysis of a RFC 3345, August 2002.
core router in Japan.
[19] Huston, G., Telstra BGP table statistics, [17] Bates, T., Rekhter, Y., Chandra, R. and D. Katz,
http://www.telstra.net/ops/bgp/index.html, "Multiprotocol Extensions for BGP-4", RFC 2283.
Statistics derived daily from the BGP tables of
Telstra and other AS's routers.
For Internet Draft consistency purposes only For Internet Draft consistency purposes only
[20] Bradner, S., "The Internet Standards Process -- [18] Bradner, S., "The Internet Standards Process -- Revision 3",
Revision 3", BCP 9, RFC 2026, October 1996 RFC 2026, BCP 9, October 1996.
10.Acknowledgments
Thanks to Francis Ovenden for review and Abha Ahuja for
encouragement. Much appreciation to Jeff Haas, Matt Richardson, and
Shane Wright at Nexthop for comments and input. Debby Stopp and Nick
Ambrose contributed the concept of route packing.
11.Author's Addresses 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
Phone: +1 703 998-5819 Phone: +1 703 998-5819
Fax: +1 703 998-5058 Fax: +1 703 998-5058
EMail: hcb@gettcomm.com EMail: hcb@gettcomm.com
Elwyn Davies Elwyn B. Davies
Nortel Networks Nortel Networks
Harlow Laboratories
London Road London Road
Harlow, Essex CM17 9NA Harlow, Essex CM17 9NA
UK UK
Phone: +44-1279-405498
Email: elwynd@nortelnetworks.com Phone: +44 1279 405 498
EMail: elwynd@nortelnetworks.com
Susan Hares Susan Hares
Nexthop Technologies Nexthop Technologies
517 W. William 517 W. William
Ann Arbor, Mi 48103 Ann Arbor, MI 48103
Phone: USA
Email: skh@nexthop.com
EMail: skh@nexthop.com
Padma Krishnaswamy Padma Krishnaswamy
Email: kri1@earthlink.net SAIC
331 Newman Springs Road
Red Bank, New Jersey 07701
USA
EMail: kri1@earthlink.net
Marianne Lepp Marianne Lepp
Juniper Networks Consultant
51 Sawyer Road
Waltham, MA 02453 EMail: mlepp@lepp.com
Phone: 617 645 9019
Email: mlepp@juniper.net
Alvaro Retana Alvaro Retana
Cisco Systems, Inc. Cisco Systems, Inc.
7025 Kit Creek Rd. 7025 Kit Creek Rd.
Research Triangle Park, NC 27709 Research Triangle Park, NC 27709
Email: aretana@cisco.com USA
EMail: aretana@cisco.com
Intellectual Property Statement
The IETF takes no position regarding the validity or scope of any
intellectual property or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; neither does it represent that it
has made any effort to identify any such rights. Information on the
IETF's procedures with respect to rights in standards-track and
standards-related documentation can be found in BCP-11. Copies of
claims of rights made available for publication and any assurances of
licenses to be made available, or the result of an attempt made to
obtain a general license or permission for the use of such
proprietary rights by implementors or users of this specification can
be obtained from the IETF Secretariat.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights which may cover technology that may be required to practice
this standard. Please address the information to the IETF Executive
Director.
Full Copyright Statement Full Copyright Statement
Copyright (C) The Internet Society (2002). All Rights Reserved. Copyright (C) The Internet Society (2003). All Rights Reserved.
This document and translations of it may be copied and furnished to This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than followed, or as required to translate it into languages other than
English. English.
The limited permissions granted above are perpetual and will not be The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns. revoked by the Internet Society or its successors or assignees.
This document and the information contained herein is provided on an This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDIN BUT TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Acknowledgement
Funding for the RFC Editor function is currently provided by the
Internet Society.
 End of changes. 

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