the understood (e.g., [GLSSRY]) and yet-to-be-invented cases where
the control processing may be separate from forwarding [RFC2918].
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 forward traffic, so forwarding-based measurements
would be meaningless for them.
Measurement units: N.A.
Issues:
See also:
3.8. BGP Session
Definition:
A BGP session is a session between two BGP instances.
Discussion:
Measurement units: N.A.
Issues:
See also:
3.9. Active BGP Session
Definition:
An active BGP session is one that is in the established state.
(See RFC 1771.)
Discussion:
Measurement units: N.A.
Issues:
See also:
3.10. BGP Peer
Definition:
A BGP peer is another BGP instance to which the DUT is in the
Established state. (See RFC 1771.)
Discussion:
In the test scenarios for the methodology discussion that will
follow this document, peers send BGP advertisements to the DUT and
receive DUT-originated advertisements. We recommend that the
peering relation be established before tests begin. It might also
be interesting to measure the time required to reach the
established state. This is a protocol-specific definition, not to
be confused with another frequent usage, which refers to the
business/economic definition for the exchange of routes without
financial compensation. It is worth noting that a BGP peer, by
this definition, is associated with a BGP peering session, and
there may be more than one such active session on a router or on a
tester. The peering sessions referred to here may exist between
various classes of BGP routers (see Section 4.2).
Measurement units:
Number of BGP peers.
Issues:
See also:
3.11. BGP Neighbor
Definition:
A BGP neighbor is a device that can be configured as a BGP peer.
Discussion:
Measurement units:
Issues:
See also:
3.12. MinRouteAdvertisementInterval (MRAI)
Definition:
(Paraphrased from RFC 1771) The MRAI timer determines the minimum
time between advertisements of routes to a particular destination
(prefix) from a single BGP device. The timer is applied on a
pre-prefix basis, although the timer is set on a per-BGP device
basis.
Discussion:
Given that a BGP instance may manage in excess of 100,000 routes,
RFC 1771 allows for a degree of optimization in order to limit the
number of timers needed. The MRAI does not apply to routes
received from BGP speakers in the same AS or to explicit
withdrawals. RFC 1771 also recommends that random jitter is
applied to MRAI in an attempt to avoid synchronization effects
between the BGP instances in a network. In this document, we
define routing plane convergence by measuring from 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.
Issues:
See also:
NLRI, BGP Route.
3.13. MinASOriginationInterval (MAOI)
Definition:
The MAOI specifies the minimum interval between advertisements of
locally originated routes from this BGP instance.
Discussion:
Random jitter is applied to MAOI in an attempt to avoid
synchronization effects between BGP instances in a network.
Measurement units:
Seconds.
Issues:
It is not known what, if any, relationship exists between the
settings of MRAI and MAOI.
See also:
MRAI, BGP Route.
3.14. Active Route
Definition:
Route for which there is a FIB entry corresponding to a RIB entry.
Discussion:
Measurement units:
Number of routes.
Issues:
See also:
RIB.
3.15. 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:
See also:
Route, Route Instance.
3.16. Non-Unique Route
Definition:
A non-unique route is a prefix for which there is at least one
other route in a set including more than one Adj-RIB-In.
Discussion:
Measurement units: N.A.
Issues:
See also:
Route, Route Instance, Unique Active Route.
3.17. Route Instance
Definition:
A route instance is one of several possible occurrences of a route
for a particular prefix.
Discussion:
When a router has multiple peers from which it accepts routes,
routes to the same prefix may be received from several peers.
This is then an example of multiple route instances. Each route
instance is associated with a specific peer. The BGP algorithm
that arbitrates between the available candidate route instances
may reject a specific route instance due to local policy.
Measurement units:
Number of route instances.
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 (see
Section 4.1.4), will likely receive more route instances than a
provider edge router, located closer to the end-users of the
network.
See also:
4. Constituent Elements of a Router or Network of Routers
Many terms included in this list of definitions were originally
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.
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). Also, a
router that has a full set of routes as in a DFT, but that also has a
’discard’ rule for a default route would not be considered default
free.
Note that in this section the references to number of routes are to
routes installed in the loc-RIB, which are therefore unique routes,
not route instances. Also note that the total number of route
instances may be 4 to 10 times the number of routes.
4.1.1. Default Route
Definition:
A default route can match any destination address. If a router
does not have a more specific route for a particular packet’s
destination address, it forwards this packet to the next hop in
the default route entry, provided that its Forwarding Table
(Forwarding Information Base, or 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:
Measurement units: N.A.
Issues:
See also:
Default-Free Routing Table, Route, Route Instance.
4.1.2. Default-Free Routing Table
Definition:
A default-free routing table has no default routes and is
typically seen in routers in the core or top tier of routers in
the network.
Discussion:
The term originates from the concept that routers at the core or
top tier of the Internet will not be configured with a default
route (Notation in IPv4 0.0.0.0/0 and in IPv6 0:0:0:0:0:0:0:0 or
::/0). Thus they will forward every packet to a specific next hop
based on the longest match between the destination IP address and
the routes in the forwarding table.
Default-free routing table size is commonly used as an indicator
of the magnitude of reachable Internet address space. However,
default-free routing tables may also include routes internal to
the router’s AS.
Measurement units:
The number of routes.
See also:
Full Default-Free Table, Default Route.
4.1.3. Full Default-Free Table
Definition:
A full default-free table is the union of all sets of BGP routes
taken from all the default-free BGP routing tables 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 on 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:
The full default-free routing table is not the same as the union
of all reachable unicast addresses. The table simply does not
contain the default prefix (0/0) and does contain the union of all
sets of BGP routes from default-free BGP routing tables.
See also:
Routes, Route Instances, Default Route.
4.1.4. Default-Free Zone
Definition:
The default-free zone is the part of the Internet backbone that
does not have a default route.
Discussion:
Measurement units:
Issues:
See also:
Default Route.
4.1.5. Full Provider-Internal Table
Definition:
A full provider-internal table is a superset of the full routing
table that contains infrastructure and non-aggregated routes.
Discussion:
Experience has shown that this table might contain 1.3 to 1.5
times the number of routes in the externally visible full table.
Tables of this size, therefore, are a real-world requirement for
key internal provider routers.
Measurement units:
Number of routes.
Issues:
See also:
Routes, Route Instances, Default 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:
A provider edge router is a router at the edge of a provider’s
network that speaks eBGP to a BGP speaker in another AS.
Discussion:
The traffic that transits this router may be destined to or may
originate from non-adjacent autonomous systems. In particular,
the MED values used in the Provider Edge Router would not be
visible in the non-adjacent autonomous systems. Such a router
will always speak eBGP and may speak iBGP.
Measurement units:
Issues:
See also:
4.2.2. Subscriber Edge Router
Definition:
A subscriber edge router is router at the edge of the subscriber’s
network that speaks eBGP to its provider’s AS(s).
Discussion:
The router belongs to an end user organization that may be multi-
homed, and that carries traffic only to and from that end user AS.
Such a router will always speak eBGP and may speak iBGP.
Measurement units:
Issues:
This definition of an enterprise border router (which is what most
Subscriber Edge Routers are) is practical rather than rigorous.
It is meant to draw attention to the reality that many enterprises
may need a BGP speaker that advertises their own routes and
accepts either default alone or partial routes. In such cases,
they may be interested in benchmarks that use a partial routing
table, to see whether a smaller control plane processor will meet
their needs.
See also:
4.2.3. Inter-provider Border Router
Definition:
An inter-provider border router is a BGP speaking router that
maintains BGP sessions with other BGP speaking routers in other
providers’ ASes.
Discussion:
Traffic transiting this router may be originated in or destined
for another AS that has no direct connectivity with this
provider’s AS. Such a router will always speak eBGP and may speak
iBGP.
Measurement units:
Issues:
See also:
4.2.4. Core Router
Definition:
An core router is a provider router internal to the provider’s
net, speaking iBGP to that provider’s edge routers, other intra-
provider core routers, or the provider’s inter-provider border
routers.
Discussion:
Such a router will always speak iBGP and may speak eBGP.
Measurement units:
Issues:
By this definition, the DUTs that are eBGP routers aren’t core
routers.
See also:
5. Characterization of Sets of Update Messages
This section contains a sequence of definitions that build up to the
definition of an update train. The packet train concept was
originally introduced by Jain and Routhier [PKTTRAIN]. It is here
adapted to refer to a train of packets of interest in BGP performance
testing.
This is a formalization of the sort of test stimulus that is expected
as input to a DUT running BGP. This data could be a well-
characterized, ordered, and timed set of hand-crafted BGP UPDATE
packets. It could just as well be a set of BGP UPDATE packets that
have been captured from a live router.
Characterization of route mixtures and update trains is an open area
of research. The particular question of interest for this work is
the identification of suitable update trains, modeled on or taken
from live traces that reflect realistic sequences of UPDATEs and
their contents.
5.1. Route Packing
Definition:
Route packing is the number of route prefixes accommodated in a
single Routing Protocol UPDATE Message, either as updates
(additions or modifications) or as withdrawals.
Discussion:
In general, a routing protocol update may contain more than one
prefix. In BGP, a single UPDATE may contain two sets of multiple
network prefixes: one set of additions and updates with identical
attributes (the NLRI) and one set of unfeasible routes to be
withdrawn.
Measurement units:
Number of prefixes.
Issues:
See also:
Route, BGP Route, Route Instance, Update Train, NLRI.
5.2. Route Mixture
Definition:
A route mixture is the demographics of a set of routes.
Discussion:
A route mixture is the input data for the benchmark. The
particular route mixture used as input must be selected to suit
the question being asked of the benchmark. Data containing simple
route mixtures might be suitable to test the performance limits of
the BGP device. Using live data or input that simulates live data
will improve understanding of how the BGP device will operate in a
live network. The data for this kind of test must be route
mixtures that model the patterns of arriving control traffic in
the live Internet. To accomplish this kind of modeling, it is
necessary to identify the key parameters that characterize a live
Internet route mixture. The parameters and how they interact is
an open research problem. However, we identify the following as
affecting the route mixture:
* Path length distribution
* Attribute distribution
* Prefix length distribution
* 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 by
length.
Measurement units:
Probability density functions.
Issues:
See also:
NLRI, RIB.
5.3. Update Train
Definition:
An update train is a set of Routing Protocol UPDATE messages sent
by a router to a BGP peer.
Discussion:
The arrival pattern of UPDATEs can be influenced by many things,
including TCP parameters, hold-down timers, upstream processing, a
peer coming up, or multiple peers sending at the same time.
Network conditions such as a local or remote peer flapping a link
can also affect the arrival pattern.
Measurement units:
Probability density function for the inter-arrival times of UPDATE
packets in the train.
Issues:
Characterizing the profiles of real-world UPDATE trains is a
matter for future research. In order to generate realistic UPDATE
trains as test stimuli, a formal mathematical scheme or a proven
heuristic is needed to drive the selection of prefixes. Whatever
mechanism is selected, it must generate update trains that have
similar characteristics to those measured in live networks.
See also:
Route Mixture, MRAI, MAOI.
5.4. Randomness in Update Trains
As we have seen from the previous sections, an update train used as a
test stimulus has a considerable number of parameters that can be
varied, to a greater or lesser extent, randomly and independently.
A random update train will contain a route mixture randomized across:
* NLRIs
* updates and withdrawals
* prefixes
* inter-arrival times of the UPDATEs and possibly across other
variables.
This is intended to simulate the unpredictable asynchronous nature of
the network, whereby UPDATE packets may have arbitrary contents and
be delivered at random times.
It is important that the data set be randomized sufficiently to avoid
favoring one vendor’s implementation over another’s. Specifically,
the distribution of prefixes could be structured to favor the
internal organization of the routes in a particular vendor’s
databases. This is to be avoided.
5.5. Route Flap
Definition:
A route flap is a change of state (withdrawal, announcement,
attribute change) for a route.
Discussion:
Route flapping can be considered a special and pathological case
of update trains. A practical interpretation of what may be
considered excessively rapid is the RIPE 229 [RIPE229], which
contains current guidelines on flap-damping parameters.
Measurement units:
Flapping events per unit time.
Issues:
Specific Flap events can be found in Section 6.1. A bench-marker
SHOULD use a mixture of different route change events in testing.
See also:
Route Change Events, Flap Damping, Packet Train
6. Route Changes and Convergence
The following two definitions are central to the benchmarking of
external routing convergence and are therefore singled out for more
extensive discussion.
6.1. Route Change Events
A taxonomy characterizing routing information changes seen in
operational networks is proposed in RIPE-37 [RIPE37] and Labovitz et
al [INSTBLTY]. These papers describe BGP protocol-centric events and
event sequences in the course of an analysis of network behavior.
The terminology in the two papers categorizes similar but slightly
different behaviors with some overlap. We would like to apply these
taxonomies to categorize the tests under definition where possible,
because these tests must tie in to phenomena that arise in actual
networks. We avail ourselves of, or may extend, this terminology as
necessary for this purpose.
A route can be changed implicitly by replacing it with another route
or explicitly by withdrawal followed by the introduction of a new
route. In either case, the change may be an actual change, no
change, or a duplicate. The notation and definition of individual
categorizable route change events is adopted from [INSTBLTY] and
given below.
1. AADiff: Implicit withdrawal of a route and replacement by a route
different in some path attribute.
2. AADup: Implicit withdrawal of a route and replacement by route
that is identical in all path attributes.
3. WADiff: Explicit withdrawal of a route and replacement by a
different route.
4. WADup: Explicit withdrawal of a route and replacement by a route
that is identical in all path attributes.
To apply this taxonomy in the benchmarking context, we need terms to
describe the sequence of events from the update train perspective, as
listed above, and event indications in the time domain in order to
measure activity from the perspective of the DUT. With this in mind,
we incorporate and extend the definitions of [INSTBLTY] to the
following:
1. Tup (TDx): Route advertised to the DUT by Test Device x
2. Tdown(TDx): Route being withdrawn by Device x
3. Tupinit(TDx): The initial announcement of a route to a unique
prefix
4. TWF(TDx): Route fail over after an explicit withdrawal.
But we need to take this a step further. Each of these events can
involve a single route, a "short" packet train, or a "full" routing
table. We further extend the notation to indicate how many routes
are conveyed by the events above:
1. Tup(1,TDx) means Device x sends 1 route
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.
The basic criterion for selecting a "better" route is the final
tiebreaker defined in RFC 1771, the router ID. As a consequence,
this memorandum uses the following descriptor events, which are
routes selected by the BGP selection process rather than simple
updates:
1. Tbest -- The current best path.
2. Tbetter -- Advertise a path that is better than Tbest.
3. Tworse -- Advertise a path that is worse than Tbest.
6.2. Device Convergence in the Control Plane
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:
For example, when considering BGP convergence, the convergence
resulting from a change that alters the best route instance for a
single prefix at a router would be deemed to have occurred when
this route is advertised to its downstream peers. By way of
contrast, OSPF convergence concludes when SPF calculations have
been performed and the required link states are advertised onward.
The convergence process, in general, can be subdivided into three
distinct phases:
* convergence across the entire Internet,
* convergence within an Autonomous System,
* convergence with respect to a single device.
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
that we describe herein and in the methodology documents.