RFC 4098
Terminology for Benchmarking BGP Device Convergence in the Control Plane
RFC 4098: Terminology for Benchmarking BGP Device Convergence in the Control Plane 💖
- Written by: H. Berkowitz (Gett Communications & CCI Training), E. Davies, Ed. (Folly Consulting), S. Hares (Nexthop Technologies), P. Krishnaswamy (SAIC), and M. Lepp (Consultant) ✨
- Category: Informational 📚
- Date: June 2005 🗓️
- Obsoletes / Updates: the header doesn't list any RFCs that this one obsoletes or updates 🤷♀️
Status of This Memo 📮
Okay so this memo is here to give the Internet community some info 💅 It does not specify an Internet standard of any kind. Distribution of this memo is unlimited 🌸
Copyright Notice 🔐
Copyright (C) The Internet Society (2005).
Abstract 🦋
This doc sets up terminology so everyone describes benchmarking methodology the same way when measuring eBGP convergence in the control plane of a single BGP device 🧠 Future docs will cover iBGP convergence, starting to forward traffic based on converged control plane info, and multiple BGP devices interacting with each other 🔜 The terminology works for both IPv4 and IPv6, and illustrative examples of each version are included where relevant ✨
Table of Contents 🧾
1. Introduction ....................................................3
1.1. Overview and Road Map ......................................4
1.2. Definition Format ..........................................5
2. Components and Characteristics of Routing Information ...........5
2.1. (Network) Prefix ...........................................5
2.2. Network Prefix Length ......................................6
2.3. Route ......................................................6
2.4. BGP Route ..................................................7
2.5. Network Level Reachability Information (NLRI) ..............7
2.6. BGP UPDATE Message .........................................8
3. Routing Data Structures and Route Categories ....................8
3.1. Routing Information Base (RIB) .............................8
3.1.1. Adj-RIB-In and Adj-RIB-Out ..........................8
3.1.2. Loc-RIB .............................................9
3.2. Prefix Filtering ...........................................9
3.3. Routing Policy ............................................10
3.4. Routing Policy Information Base ...........................10
3.5. Forwarding Information Base (FIB) .........................11
3.6. BGP Instance ..............................................12
3.7. BGP Device ................................................12
3.8. BGP Session ...............................................13
3.9. Active BGP Session ........................................13
3.10. BGP Peer .................................................13
3.11. BGP Neighbor .............................................14
3.12. MinRouteAdvertisementInterval (MRAI) .....................14
3.13. MinASOriginationInterval (MAOI) ..........................15
3.14. Active Route .............................................15
3.15. Unique Route .............................................15
3.16. Non-Unique Route .........................................16
3.17. Route Instance ...........................................16
4. Constituent Elements of a Router or Network of Routers .........17
4.1. Default Route, Default-Free Table, and Full Table .........17
4.1.1. Default Route ......................................17
4.1.2. Default-Free Routing Table .........................18
4.1.3. Full Default-Free Table ............................18
4.1.4. Default-Free Zone ..................................19
4.1.5. Full Provider-Internal Table .......................19
4.2. Classes of BGP-Speaking Routers ...........................19
4.2.1. Provider Edge Router ...............................20
4.2.2. Subscriber Edge Router .............................20
4.2.3. Inter-provider Border Router .......................21
4.2.4. Core Router ........................................21
5. Characterization of Sets of Update Messages ....................22
5.1. Route Packing .............................................22
5.2. Route Mixture .............................................23
5.3. Update Train ..............................................24
5.4. Randomness in Update Trains ...............................24
5.5. Route Flap ................................................25
6. Route Changes and Convergence ..................................25
6.1. Route Change Events .......................................25
6.2. Device Convergence in the Control Plane ...................27
7. BGP Operation Events ...........................................28
7.1. Hard Reset ................................................28
7.2. Soft Reset ................................................29
8. Factors That Impact the Performance of the Convergence
Process ........................................................29
8.1. General Factors Affecting Device Convergence ..............29
8.1.1. Number of Peers ....................................29
8.1.2. Number of Routes per Peer ..........................30
8.1.3. Policy Processing/Reconfiguration ..................30
8.1.4. Interactions with Other Protocols ..................30
8.1.5. Flap Damping .......................................30
8.1.6. Churn ..............................................31
8.2. Implementation-Specific and Other Factors Affecting BGP ...31
8.2.1. Forwarded Traffic ..................................31
8.2.2. Timers .............................................32
8.2.3. TCP Parameters Underlying BGP Transport ............32
8.2.4. Authentication .....................................32
9. Security Considerations ........................................32
10. Acknowledgements ..............................................32
11. References ....................................................33
11.1. Normative References ....................................33
11.2. Informative References ..................................341. Introduction ✨
This doc defines terminology for describing how well the BGP processes in routers (or other devices running BGP) converge 💫 (See 'A Border Gateway Protocol 4 (BGP-4)' [RFC1771], referred to as RFC 1771 in the remainder of the document.) It's the first part of a two-document series, and the next doc will have the tests and methodology 🧪 Again, this terminology works for both IPv4 and IPv6, with illustrative examples of each version where relevant. BUT, real talk, this doc is mainly aimed at BGP-4 in IPv4 networks 🌐 IPv6 will need MP-BGP [RFC2858], as described in RFC 2545 [RFC2545], and this doc won't cover terminology or issues specific to those extensions of BGP-4 🙅♀️ Also, terminology and issues for the BGP extensions that support VPNs, as described in RFC 2547 [RFC2547], are out of scope here 🚫
The following observations are the foundation of the approach in this doc and the companion doc:
- The main goal is to come up with methodologies that standardize how convergence-related measurements for BGP are conducted and reported 📊
- We have to remove ambiguity from lots of frequently used terms that come up when doing these measurements 🧹
- Convergence characterization is a complex process, so it's smart to keep the early focus on specifying how to take basic control-plane measurements as a first step in characterizing BGP convergence 🪜
For path-vector protocols, such as BGP, the main initial focus is therefore on network and system control-plane [RFC3654] activity, which means the arrival, processing, and propagation of routing information 🛣️
We note that for testing purposes, all optional parameters SHOULD be turned off. All variable parameters SHOULD be at their default setting unless the test specifies otherwise 🎛️
Later docs will dig into the more intricate parts of convergence measurement, like the effects of Multiprotocol Extensions for BGP-4, policy processing, simultaneous traffic on the control and data paths within the Device Under Test (DUT), and other realistic performance modifiers 🧩 Convergence of Interior Gateway Protocols (IGPs) will also get its own separate docs 🌈
1.1. Overview and Road Map 🗺️
Characterizing the BGP convergence performance of a device must take into account all distinct stages and aspects of BGP functionality 💅 This means the relevant terms and metrics need to be defined as specifically as possible, and that's the whole goal of this doc 🎯
The necessary definitions are sorted into separate categories:
- Components and characteristics of routing information 📦
- Routing data structures and route categories 🗃️
- Descriptions of the constituent elements of a network or a router that is undergoing convergence 🏗️
- Characterization of sets of update messages, types of route-change events, and some events specific to BGP operation 🔁
- Descriptions of factors that impact the performance of convergence processes ⚡
1.2. Definition Format 📝
The definition format is the same as the one defined in 'Requirements for IP Version 4 Routers' [RFC1812], and it's repeated here for convenience 💖
X.x Term to be defined (e.g., Latency).
Definition:
One or more sentences forming the body of the definition.
Discussion:
A brief discussion of the term, its application, and any
restrictions that there might be on measurement procedures.
Measurement units:
The units used to report measurements of this term. This item may
not be applicable (N.A.).
Issues:
List of issues or conditions that could affect this term.
See also:
List of related terms that are relevant to the definition or
discussion of this term.2. Components and Characteristics of Routing Information 🧚
2.1. (Network) Prefix 💖
Definition: okay so the official vibe is "A network prefix is a contiguous set of bits at the more significant end of the address that collectively designates the set of systems within a network; host numbers select among those systems." (This definition is taken directly from section 2.2.5.2, "Classless Inter Domain Routing (CIDR)", of RFC 1812. 🎀)
Discussion: in the CIDR context, the network prefix is the network component of an IP address 🌸. In IPv4 systems, that network component is called the 'network part', and the remaining part of the address is the 'host part'. In IPv6 systems, the network component is called the 'subnet prefix', and the rest is the 'interface identifier' ✨.
Measurement units: N.A.
Issues:
See also:
2.2. Network Prefix Length 🦋
Definition: the network prefix length is the number of bits, out of the total constituting the address field, that define the network prefix portion of the address.
Discussion: a super common alternative to a bit-wise mask is slash (/) notation 💅. It binds the notion of network prefix length in bits to an IP address. For example, 141.184.128.0/17 tells you the network component of this IPv4 address is 17 bits wide. Similar notation is used for IPv6 network prefixes, e.g., 2001:db8:719f::/48 🌈. When people talk about groups of addresses, the network prefix length is often used to describe them as an equivalence class. So 'one hundred /16 addresses' refers to 100 addresses whose network prefix length is 16 bits 🍓.
Measurement units: Bits.
Issues:
See also: Network Prefix.
2.3. Route 🚗
Definition: in general, a 'route' is the n-tuple <prefix, nexthop [, other routing or non-routing protocol attributes]>. A route is not end-to-end. It's defined with respect to a specific next hop that should take packets on the next step toward their destination, as defined by the prefix 👑. In this usage, a route is the basic unit of information about a target destination distilled from routing protocols.
Discussion: this term refers to the concept of a route that's common to all routing protocols ✨. Looking at the definition above, typical non-routing-protocol attributes would be associated with diffserv or traffic engineering.
Measurement units: N.A.
Issues: None.
See also: BGP Route.
2.4. BGP Route 🛤️
Definition: a BGP route is an n-tuple <prefix, nexthop, ASpath [, other BGP attributes]>.
Discussion: BGP Attributes, like Nexthop or AS path, are defined in RFC 1771, where they're called Path Attributes 🫶. They're the qualifying data that define the route. From RFC 1771: "For purposes of this protocol a route is defined as a unit of information that pairs a destination with the attributes of a path to that destination."
Measurement units: N.A.
Issues:
See also: Route, Prefix, Adj-RIB-In, Network Level Reachability Information (NLRI).
2.5. Network Level Reachability Information (NLRI) 🧚
Definition: the NLRI consists of one or more network prefixes with the same set of path attributes.
Discussion: each prefix in the NLRI gets combined with the (common) path attributes to form a BGP route 💜. The NLRI encapsulates a set of destinations that packets can be routed to (from this point in the network) along a common route described by the path attributes.
Measurement units: N.A.
Issues:
See also: Route Packing, Network Prefix, BGP Route, NLRI.
2.6. BGP UPDATE Message 📨
Definition: an UPDATE message contains an advertisement of a single NLRI field, possibly containing multiple prefixes, and multiple withdrawals of unfeasible routes. See RFC 1771 for details.
Discussion: from RFC 1771: "A variable length sequence of path attributes is present in every UPDATE. Each path attribute is a triple <attribute type, attribute length, attribute value> of variable length." 🙈
Measurement units: N.A.
See also:
3. Routing Data Structures and Route Categories 🌈
3.1. Routing Information Base (RIB) 📚
The RIB collectively consists of a set of logically (not necessarily physically) distinct databases, each of which is enumerated below. The RIB contains all destination prefixes to which the router may forward, and one or more currently reachable next hop addresses for them 🗺️.
Routes in this set may 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. Lots of implementations add their own criteria on top of that. A common implementation-specific criterion is the preference given to different routing information sources 💅.
3.1.1. Adj-RIB-In and Adj-RIB-Out 🦋
Definition: Adj-RIB-In and Adj-RIB-Out are "views" of routing information from the perspective of individual peer routers. The Adj-RIB-In contains information advertised to the DUT by a specific peer.
The Adj-RIB-Out contains the information the DUT will advertise to the peer. See RFC 1771.
Discussion:
Issues:
Measurement units: Number of route instances.
See also: Route, BGP Route, Route Instance, Loc-RIB, FIB.
3.1.2. Loc-RIB 🌸
Definition: the Loc-RIB contains the set of best routes selected from the various Adj-RIBs, after applying local policies and the BGP route selection algorithm 👑.
Discussion: the separation implied among the various RIBs is logical. It does not necessarily follow that these RIBs are distinct and separate entities in any given implementation 🤷♀️. Types of routes that need to be considered include internal BGP, external BGP, interface, static, and IGP routes.
Issues:
Measurement units: Number of routes.
See also: Route, BGP Route, Route Instance, Adj-RIB-In, Adj-RIB-Out, FIB.
3.2. Prefix Filtering 🚫
Definition: Prefix Filtering is a technique for eliminating routes from consideration as candidates for entry into a RIB by matching the network prefix in a BGP Route against a list of network prefixes 🧹.
Discussion: a BGP Route gets eliminated if, for any filter prefix from the list, the Route prefix length is equal to or longer than the filter prefix length, and the most significant bits of the two prefixes match over the length of the filter prefix. See 'Cooperative Route Filtering Capability for BGP-4' [BGP-4] for examples of usage.
Measurement units: Number of filter prefixes; lengths of prefixes.
Issues:
See also: BGP Route, Network Prefix, Network Prefix Length, Routing Policy, Routing Policy Information Base.
3.3. Routing Policy 📜
Definition: Routing Policy is "the ability to define conditions for accepting, rejecting, and modifying routes received in advertisements" [GLSSRY]. ✨
Discussion: RFC 1771 further constrains policy to stay within the hop-by-hop routing paradigm 🦋. Policy is implemented using filters and associated policy actions, such as Prefix Filtering. Many ASes formulate and document their policies using the Routing Policy Specification Language (RPSL) [RFC2622], and then automatically generate configurations for the BGP processes in their routers from the RPSL specifications 🤖.
Measurement units: Number of policies; length of policies.
Issues:
See also: Routing Policy Information Base, Prefix Filtering.
3.4. Routing Policy Information Base 🗂️
Definition: a routing policy information base is the set of incoming and outgoing policies.
Discussion: all references to the phases of the BGP selection process below are made with respect to the RFC 1771 definition of these phases 📖. Incoming policies are applied in Phase 1 of the BGP selection process to the Adj-RIB-In routes, to set the metric for the Phase 2 decision process. Outgoing policies are applied in Phase 3 of the BGP process to the Adj-RIB-Out routes preceding route (prefix and path attribute tuple) announcements to a specific peer.
Policies in the Policy Information Base have matching and action conditions. Common information to match includes route prefixes, AS paths, communities, etc. The action on a 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. It can range from a simple policy that accepts all routes and sends them along, to a complex policy with a substantial fraction of the prefixes being filtered by filter/access lists 😭.
Measurement units: Number and length of policies.
Issues:
See also:
3.5. Forwarding Information Base (FIB) 🚀
Definition: according to the definition in Appendix B of RIPE-37 [RIPE37]: "The table containing the information necessary to forward IP Datagrams is called the Forwarding Information Base. At minimum, this contains the interface identifier and next hop information for each reachable destination network prefix." 💫
Discussion: the forwarding information base describes a database that indexes network prefixes against router port identifiers 🔌. The FIB is distinct from the "routing table" (the Routing Information Base or RIB), which holds all routing information received from routing peers. It's a data plane construct and is used for forwarding each packet. The FIB is generated from the RIB. For the purposes of this document, the FIB is effectively the subset of the RIB that the forwarding plane uses to make per-packet forwarding decisions. Most current implementations have full, non-cached FIBs per router interface. All the route computation and convergence happens before entries are downloaded into a FIB 🌟.
Measurement units: N.A.
Issues:
See also: Route, RIB.
3.6. BGP Instance 🧪
Definition: a BGP instance is a process with a single Loc-RIB.
Discussion: for example, a BGP instance would run in routers or test equipment 🖥️. A test generator acting as multiple peers will typically run more than one instance of BGP. A router would typically run a single instance.
Measurement units: N.A.
Issues:
See also:
3.7. BGP Device 🧚
Definition: A BGP device is a system that has one or more BGP instances running on it, each of which is responsible for executing the BGP state machine.
Discussion: Okay so we picked "device" as the general term on purpose 💅 It covers the cases people already know about (see [GLSSRY]) and the ones nobody's invented yet, where the control processing is separate from forwarding [RFC2918]. A BGP device could be a traditional router, a route server, a BGP-aware traffic steering device, or a non-forwarding route reflector. 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 coming up after 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 how long it takes to reach the established state ⏱️
Quick heads up, this is a protocol-specific definition, so don't mix it up with the other usage, the business/economic meaning of exchanging routes without financial compensation 💀 Also, a BGP peer (by this definition) is tied to a BGP peering session, and there can be more than one active session on a router or a tester at once. The peering sessions 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 sets the minimum time between advertisements of routes to a particular destination (prefix) from a single BGP device. The timer applies on a per-prefix basis, but it's set per BGP device 🍓
Discussion: So a BGP instance can juggle more than 100,000 routes, and RFC 1771 lets you optimize a bit so you don't need a ton of timers 🧠 The MRAI doesn't apply to routes received from BGP speakers in the same AS, or to explicit withdrawals. RFC 1771 also recommends random jitter on MRAI, to stop the BGP instances in a network from syncing up with each other 🌸 In this document, we measure routing plane convergence from the time an NLRI is advertised to the DUT until the time it's advertised from the DUT. And yes, any delay the MRAI adds will totally show up in that measurement 😭
Measurement units: Seconds.
Issues:
See also: NLRI, BGP Route.
3.13. MinASOriginationInterval (MAOI) 🌷
Definition: The MAOI sets the minimum interval between advertisements of locally originated routes from this BGP instance.
Discussion: Random jitter gets applied to MAOI too, so BGP instances in a network don't all sync up 🫠
Measurement units: Seconds.
Issues: Honestly, nobody knows if MRAI and MAOI are related at all 🤷♀️
See also: MRAI, BGP Route.
3.14. Active Route ✅
Definition: A route that has 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 with exactly 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 where at least one other route sits in a set that includes 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 several peers it accepts routes from, routes to the same prefix can show up from multiple peers. That's an example of multiple route instances, and each one is tied to a specific peer ✨ The BGP algorithm that picks between the candidate route instances can reject a specific one because of local policy 🙅♀️
Measurement units: Number of route instances.
Issues: How many route instances end up in the Adj-RIB-In bases depends on what the router is doing. An inter-provider border router, sitting in the default-free zone (see Section 4.1.4), will probably get way more route instances than a provider edge router, which is closer to the end users of the network 🌍
See also:
4. Constituent Elements of a Router or Network of Routers 🧩
Lots of the terms in this list of definitions were first described in earlier standards or papers. They're included here because they matter to this discussion, and where it's relevant, we point to those sources. We tried to keep the list complete on the concepts that matter without going overboard on definitions 💅
4.1. Default Route, Default-Free Table, and Full Table 🌈
An individual router's routing table doesn't necessarily have a default route. But not having one isn't the same thing as having a full default-free table (DFT). Also, a router with a full set of routes like a DFT that also has a 'discard' rule for a default route would not count as default free 🙈
Heads up that in this section, the route counts refer to routes installed in the loc-RIB. Those are unique routes, not route instances. Also, the total number of route instances can 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 doesn't have a more specific route for a packet's destination address, it forwards that packet to the next hop in the default route entry, as long as 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's 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 usually found in routers in the core or top tier of the network 👑
Discussion: The term comes from the idea that routers at the core or top tier of the Internet aren't configured with a default route (in IPv4 that's 0.0.0.0/0, and in IPv6 it's 0:0:0:0:0:0:0:0 or ::/0). So they 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 🎯
The size of a default-free routing table is commonly used as a rough gauge of how much reachable Internet address space there is. But default-free routing tables can 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 the sets of BGP routes from all the default-free BGP routing tables that the complete set of autonomous systems making up the public Internet announce collectively. Because the Internet is so dynamic, the exact size and makeup of this table can shift a bit depending on where and when you look at it 🌊
Discussion: It's generally accepted that a full table, in this sense, doesn't include the infrastructure routes or the individual sub-aggregates of routes that the provider aggregates before announcing 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 just doesn't contain the default prefix (0/0), and it 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 doesn't 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 also contains infrastructure and non-aggregated routes.
Discussion: Experience has shown this table can hold 1.3 to 1.5 times the number of routes in the externally visible full table. Tables that size 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, depending on its logical location in the network.
4.2.1. Provider Edge Router 🌐
Definition: A provider edge router sits at the edge of a provider's network and speaks eBGP to a BGP speaker in another AS.
Discussion: Traffic going through this router may be destined for, or may originate from, non-adjacent autonomous systems. In particular, the MED values used on the Provider Edge Router wouldn't be visible in those non-adjacent autonomous systems 👀 A router like this will always speak eBGP, and it may speak iBGP too ✨
Measurement units:
Issues:
See also:
4.2.2. Subscriber Edge Router ✨
Definition: okay so a subscriber edge router is a router sitting at the edge of the subscriber's network, and it speaks eBGP to its provider's AS(s) 💖
Discussion: this router belongs to an end user organization that may be multi-homed 🫶 and it only carries traffic 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 (aka what most Subscriber Edge Routers are) is practical rather than rigorous 🙈 It's meant to point out that lots of enterprises need a BGP speaker that advertises their own routes and accepts either default alone or partial routes. In those cases they might be interested in benchmarks that use a partial routing table, to see whether a smaller control plane processor will do the job 💅
See also:
4.2.3. Inter-provider Border Router 🦋
Definition: an inter-provider border router is a BGP speaking router that keeps BGP sessions going 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: a 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. Not them being core, iykyk 🙈
See also:
5. Characterization of Sets of Update Messages 💜
This section is 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's been adapted here to refer to a train of packets of interest in BGP performance testing 🚂
This is a formalization of the sort of test stimulus that's 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 pull that off, it's necessary to identify the key parameters that characterize a live Internet route mixture. The parameters and how they interact is an open research problem. Still, 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. 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've 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, where UPDATE packets may have arbitrary contents and be delivered at random times 🎰
It's important that the data set be randomized enough 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. That is something to avoid 🚫
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 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, so they get extra attention here 💅
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'd 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 🔥
- AADiff: implicit withdrawal of a route and replacement by a route different in some path attribute.
- AADup: implicit withdrawal of a route and replacement by route that is identical in all path attributes.
- WADiff: explicit withdrawal of a route and replacement by a different route.
- 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, so we can measure activity from the perspective of the DUT. With this in mind, we incorporate and extend the definitions of [INSTBLTY] to the following 🧩
Tup (TDx): route advertised to the DUT by Test Device xTdown(TDx): route being withdrawn by Device xTupinit(TDx): the initial announcement of a route to a unique prefixTWF(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 🍓
Tup(1,TDx)means Device x sends 1 routeTup(S,TDx)means Device x sends a train, S, of routesTup(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 🏆
Tbest-- The current best path.Tbetter-- Advertise a path that is better than Tbest.Tworse-- Advertise a path that is worse than Tbest.
6.2. Device Convergence in the Control Plane 💅
Definition: A routing device has converged at the moment the DUT has finished every control-plane action it needs to react to topology changes, in the context of the test condition. 🎀
Discussion: Okay so, for BGP, a change that swaps the best route instance for a single prefix at a router counts as converged once that route gets advertised to its downstream peers. 🦋 OSPF is different. Its convergence wraps up once the SPF calculations are done and the required link states are advertised onward. ✨
Convergence in general can be split 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.
This is the one we describe here and in the methodology documents. 🌸 We're benchmarking routing protocol performance, which is only one part of the whole device, so this definition is meant to exclude (as far as is possible) any extra time spent downloading and installing the forwarding information base in the data plane. It's built to work across different families of protocols, so it's giving versatile. 💜
It's super important to benchmark each phase of convergence separately before you move on to a composite characterization of routing convergence, where implementation-specific dependencies are allowed to interact. 🧚 You also have to be careful that convergence time isn't influenced by policy processing on downstream peers. 🙈 And the time resolution you need for measuring device convergence depends a bit on the types of interfaces on the router. For modern routers with gigabit or faster interfaces, a single UPDATE may get processed and re-advertised in way less than a millisecond. So your time measurements need a resolution of hundreds to tens of microseconds, or better. ⭐
Measurement units: Time period.
Issues:
See also:
7. BGP Operation Events 🦋
The BGP process(es) in a device might restart because an operator intervened or a power failure caused a complete shutdown. 💀 In that case, a hard reset is needed. A peering session could also be lost, for example because of something the peer did or a dropped TCP session. A device can reestablish its peers and re-advertise all relevant routes in a hard reset. 🌈 But if a peer is lost and the BGP process hasn't failed, BGP has mechanisms for a "soft reset." 🫶
7.1. Hard Reset 🔥
Definition: An event that triggers a complete re-initialization of the routing tables on one or more BGP sessions, which results in a full routing table being exchanged on one or more links to the router. 👑
Discussion:
Measurement units: N.A.
Issues:
See also:
7.2. Soft Reset 🌸
Definition: A soft reset is performed on a per-neighbor basis. It doesn't clear the BGP session while the peering relation is re-established, and it doesn't stop the flow of traffic. ✨
Discussion: There are two ways to do a soft reset. 💅 The first is graceful restart [GRMBGP], where the BGP device that lost a peer keeps forwarding traffic for a while before tearing down that peer's routes. The second is soft refresh [RFC2918], where a BGP device can request a peer's Adj-RIB-Out. 🧚
Measurement units: N.A.
Issues:
See also:
8. Factors That Impact the Performance of the Convergence Process 🎀
Not a complete list, but every item below has a significant effect on BGP convergence. 😭 Not all of them can be addressed in the baseline measurements described in this document. 🍓
8.1. General Factors Affecting Device Convergence 🌈
These factors are conditions of testing external to the router Device Under Test (DUT). 🌍
8.1.1. Number of Peers 👯
As the number of peers goes up, the BGP route selection algorithm gets exercised more and more. ✨ On top of that, the phasing and frequency of updates from the various peers have a growing effect on convergence as the peer count rises, depending on how many updates each extra peer generates. Adding peers also piles on more processing work for TCP and BGP keepalives. 💖
8.1.2. Number of Routes per Peer 🦋
The number of routes per BGP peer is an obvious stressor on the convergence process. 🔥 How many multiple route instances and distinct routes each peer adds or withdraws matters, and so does the relative proportion of those. The mix of overlapping route instances and IGP routes matters too. 💜
8.1.3. Policy Processing/Reconfiguration 🙈
The number of routes and attributes being filtered and set, as a fraction of the target route table size, is another parameter that affects BGP convergence. 🧠
The following are extreme examples:
- Minimal policy: receive all, send all.
- Extensive policy: up to 100% of the total routes have applicable policy.
8.1.4. Interactions with Other Protocols 🍓
There are interactions in the form of precedence, synchronization, duplication, and the addition of timers and route selection criteria. 🌸 Honestly, to understand BGP4 convergence you have to understand how it interacts with both the IGPs and the protocols tied to the physical media, like Ethernet, SONET, and DWDM. 🔌
8.1.5. Flap Damping ⏸️
A router can use flap damping to respond to route flapping. Use of flap damping is not mandatory, so deciding whether to enable it, and what parameters to change, can be treated as a matter of routing policy. 🧚
The timers are defined by RFC 2439 [RFC2439] and discussed in RIPE-229 [RIPE229]. ✨ If this feature is in effect, the device has to keep additional state to carry out the damping. That can directly hit the control plane through extra processing. 😬 Flap damping may also delay the arrival of real changes in a route, and that can affect convergence times. ⏳
8.1.6. Churn 🌪️
In theory, a BGP device could receive a set of updates that completely define the Internet, then sit in a steady state, only sending the appropriate keepalives. 😌 In practice, the Internet is always changing. 💅
Churn refers to control-plane processor activity caused by announcements received and sent by the router. It does not include keepalives and TCP processing. 🎀
Churn is caused by both normal and pathological events. 🫶 For example, if an interface on the local router goes down and its prefix gets withdrawn, that withdrawal is normal activity, though it still contributes to churn. If the local device receives a withdrawal of a route it already advertises, or an announcement of a route it didn't previously know, and then re-advertises that information, those are normal parts of churn too. Routine updates can range from single announcements or withdrawals all the way to announcements of an entire default-free table. That last one is completely reasonable as an initialization condition. 🌈
Flapping routes are a pathological contributor to churn, and so is MED oscillation [RFC3345]. 🙃 The goal of flap damping is to reduce how much flapping adds to churn. 🦋
The effect of churn on overall convergence depends on how much processing power the control plane has, and on whether the same processor(s) handle both forwarding and control. ⚡
8.2. Implementation-Specific and Other Factors Affecting BGP Convergence 🛠️
These factors are conditions of testing internal to the Device Under Test (DUT), though they may still affect its interactions with test devices. 👀
8.2.1. Forwarded Traffic 🚚
Actual traffic in the device may stress the control path in some fashion if both the offered load (from data) and the control traffic (FIB updates and downloads as a consequence of flaps) are excessive. 💥 Adding data traffic gives a more accurate picture of realistic operating scenarios than control traffic alone would. 🌷
8.2.2. Timers ⏰
Settings of delay and hold-down timers at the link level, as well as for BGP4, can introduce delays or ameliorate them. 🕰️ As part of a test report, all relevant timers MUST be reported if they use non-default values. 📝🫶
8.2.3. TCP Parameters Underlying BGP Transport 🧵
All BGP traffic and interactions happen over TCP, so all relevant parameters characterizing the TCP sessions MUST be provided. 🎀 Examples include slow start, max window size, maximum segment size, or timers. 💖
8.2.4. Authentication 🔐
Authentication in BGP is currently done using the TCP MD5 Signature Option [RFC2385]. 🔑 Processing the MD5 hash, especially on devices 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. 😵💫
9. Security Considerations 🚨
⚠️ Serious business here, bestie. 💀
The document explicitly considers authentication as a performance-affecting feature. 🔐 It does not, however, consider the overall security of the routing system. 😱 That's a whole other mountain, and it is not covered here. 🏔️
10. Acknowledgements 🫶
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. 🎀
Alvaro Retana was a key member of the team that developed this document, and made significant technical contributions regarding route mixes. 👑 The team thanks him and regards him as a co-author in spirit. 🥹✨
11. References 📚
11.1. Normative References
okay bestie, we're at the reading list 📚✨ these are the docs the spec needs you to have read first, no skipping 💅
- [RFC1771] Rekhter, Y. and T. Li, "A Border Gateway Protocol 4 (BGP-4)", RFC 1771, March 1995.
- [RFC2439] Villamizar, C., Chandra, R., and R. Govindan, "BGP Route Flap Damping", RFC 2439, November 1998.
- [RFC1812] Baker, F., "Requirements for IP Version 4 Routers", RFC 1812, June 1995.
- [RIPE37] Ahuja, A., Jahanian, F., Bose, A., and C. Labovitz, "An Experimental Study of Delayed Internet Routing Convergence", RIPE-37 Presentation to Routing WG, November 2000,
http://www.ripe.net/ripe/meetings/archive/ripe-37/presentations/RIPE-37-convergence/ - [INSTBLTY] Labovitz, C., Malan, G., and F. Jahanian, "Origins of Internet Routing Instability", Infocom 99, August 1999.
- [RFC2622] Alaettinoglu, C., Bates, T., Gerich, E., Karrenberg, D., Meyer, D., Terpstra, M., and C. Villamizar, "Routing Policy Specification Language (RPSL)", RFC 2280, January 1998.
- [RIPE229] Panigl, C., Schmitz, J., Smith, P., and C. Vistoli, "RIPE Routing-WG Recommendation for coordinated route-flap damping parameters, version 2", RIPE 229, October 2001.
- [RFC2385] Heffernan, A., "Protection of BGP Sessions via the TCP MD5 Signature Option", RFC 2385, August 1998.
- [GLSSRY] Juniper Networks, "Junos(tm) Internet Software Configuration Guide Routing and Routing Protocols, Release 4.2", Junos 4.2 and other releases, September 2000,
http://www.juniper.net/techpubs/software/junos/junos42/swcmdref42/html/glossary.html - [RFC2547] Rosen, E. and Y. Rekhter, "BGP/MPLS VPNs", RFC 2547, March 1999.
- [PKTTRAIN] Jain, R. and S. Routhier, "Packet trains -- measurement and a new model for computer network traffic", IEEE Journal on Selected Areas in Communication 4(6), September 1986.
11.2. Informative References
these ones are the extra-credit reading 🧠 super useful for context, but the spec doesn't hinge on them 🌸
- [RFC2918] Chen, E., "Route Refresh Capability for BGP-4", RFC 2918, September 2000.
- [GRMBGP] Sangli, S., Rekhter, Y., Fernando, R., Scudder, J., and E. Chen, "Graceful Restart Mechanism for BGP", Work in Progress, June 2004.
- [BGP-4] Chen, E. and Y. Rekhter, "Cooperative Route Filtering Capability for BGP-4", Work in Progress, March 2004.
- [RFC3654] Khosravi, H. and T. Anderson, "Requirements for Separation of IP Control and Forwarding", RFC 3654, November 2003.
- [RFC3345] McPherson, D., Gill, V., Walton, D., and A. Retana, "Border Gateway Protocol (BGP) Persistent Route Oscillation Condition", RFC 3345, August 2002.
- [RFC2858] Bates, T., Rekhter, Y., Chandra, R., and D. Katz, "Multiprotocol Extensions for BGP-4", RFC 2858, June 2000.
- [RFC2545] Marques, P. and F. Dupont, "Use of BGP-4 Multiprotocol Extensions for IPv6 Inter-Domain Routing", RFC 2545, March 1999.
Authors' Addresses
meet the squad 🎀 these are the humans who wrote this, so you can slide into their inboxes (politely!) 💌
Howard Berkowitz
Gett Communications & CCI Training
5012 S. 25th St
Arlington, VA 22206
USA
Phone: +1 703 998-5819
Fax: +1 703 998-5058
EMail: hcb@gettcomm.comElwyn B. Davies
Folly Consulting
The Folly
Soham
Cambs, CB7 5AW
UK
Phone: +44 7889 488 335
EMail: elwynd@dial.pipex.comSusan Hares
Nexthop Technologies
825 Victors Way
Ann Arbor, MI 48108
USA
Phone: +1 734 222-1610
EMail: skh@nexthop.comPadma Krishnaswamy
SAIC
331 Newman Springs Road
Red Bank, New Jersey 07701
USA
EMail: padma.krishnaswamy@saic.comMarianne Lepp
Consultant
EMail: mlepp@lepp.comFull Copyright Statement
the legal bit, but make it cute 🦋
Copyright (C) The Internet Society (2005).
this doc is covered by the rights, licenses and restrictions in BCP 78, and unless that says otherwise, the authors keep all their rights 🔒
this document and the info in it are given "AS IS", and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Intellectual Property
the IETF is basically like "not our problem to figure out who owns what" 💅 but here's how it works:
The IETF takes no position on the validity or scope of any Intellectual Property Rights or other rights that someone might claim apply to implementing or using the technology in this document, or on whether any license under those rights might be available. It also doesn't claim to have made any independent effort to find such rights. Info about how rights work for RFC documents lives in BCP 78 and BCP 79 📜
copies of IPR disclosures sent to the IETF Secretariat, plus any assurances of licenses, or the result of trying to get a general license or permission to use those proprietary rights for implementers or users of this spec, can be found in the IETF on-line IPR repository at http://www.ietf.org/ipr 🔍
the IETF also invites anyone who knows about copyrights, patents, patent applications, or other proprietary rights that might cover technology needed to implement this standard to tell them. send that info to ietf-ipr@ietf.org 💌
Acknowledgement
and last but not least, the shoutout 🌈
Funding for the RFC Editor function is currently provided by the Internet Society. ✨🫶
📦 where this page comes from
- ietf: rfc4098 2005-06
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms