RFC 3221

Commentary on Inter-Domain Routing in the Internet

📅 published December 2001, from ietf

RFC 3221: Commentary on Inter-Domain Routing in the Internet 🎀✨

Network Working Group 🌸 Request for Comments: 3221 Author: G. Huston Published by: Internet Architecture Board Category: Informational (📖 for the Internet community, not a standard!) Date: December 2001

This doc is literally a commentary, so it doesn't set any official rules. It just shares info. It also doesn't list any Obsoletes or Updates in its header, so it doesn't replace or change any other RFCs. 💅

Status of this Memo 🦋

Okay so this memo gives info to the Internet community. It is not an Internet standard of any kind. Anyone can share it freely, with no limits on distribution. 🫶

Copyright (C) The Internet Society (2001). All Rights Reserved.

Abstract ✨

This doc looks at the big long-term trends you can spot in the Internet's BGP table. It also finds a bunch of operational habits and protocol factors that feed into those trends. Then it digs into how all of that could affect how well the inter-domain routing space scales. 🔥

This doc is the result of a teamwork project from the Internet Architecture Board. 👑

Table of Contents 🧚

1.   Introduction.................................................  2
2.   Network Scaling and Inter-Domain Routing  ...................  2
3.   Measurements of the total size of the BGP Table  ............  4
4.   Related Measurements derived from BGP Table  ................  7
5.   Current State of inter-AS routing in the Internet  .......... 11
6.   Future Requirements for the Exterior Routing System  ........ 14
7.   Architectural Approaches to a scalable Exterior
       Routing Protocol........................................... 15
8.   Directions for Further Activity  ............................ 21
9.   Security Considerations  .................................... 22
10.  References  ................................................. 23
11.  Acknowledgements  ........................................... 24
12.  Author's Address  ........................................... 24
13.  Full Copyright Statement  ................................... 25

1. Introduction 🌈

Okay bestie, so this doc takes a long, hard look at the big long-term trends in the Internet's BGP table. It also calls out the operational practices and protocol factors that push those trends along. Then it checks how all of that affects the scaling properties of the inter-domain routing space. Main character energy 💅

The impacts are honestly wild. They include the chance that the existing Autonomous System number space could run out 😭, routes taking longer to settle on stable backup paths after an announcement gets withdrawn, how stable the table entries are, and the average prefix length of entries in the BGP table. The bigger issue underneath all of it is the increasingly dense mesh of connections between ASes. That makes inter-domain policy way more granular and gives operators finer control over inter-domain traffic engineering. It's a lot, ngl 🙈

Some ways to refine the inter-domain routing protocol and the operating practices around it might scale better. The doc flags those as something to look into further. 🔍

This doc is the result of a collaborative exercise from the Internet Architecture Board. 🫶

2. Network Scaling and Inter-Domain Routing 💖

So the big question is: are there built-in scaling limits in the Internet's technology or how it's deployed that could stop it from keeping up with the demand that keeps climbing? 😳 There are a few places to look. They include the capacity of transmission systems, packet switching capacity, whether protocol addresses keep being available, and whether the routing system can produce a stable view of the overall network topology. This study focuses on that last one, with the goal of finding some parts of the Internet's routing system's scaling properties. 🧠

Here's the basic structure. The Internet is a bunch of networks, or Autonomous Systems (ASes), that are linked together to form one connected domain. Each AS uses an interior routing system to keep a coherent picture of its own topology. It also uses an exterior routing system to keep track of adjacency with neighboring ASes, which builds a picture of how the whole system connects. 🌸

That network-wide connectivity lives in the routing table used by the BGP4 protocol, which is called the Routing Information Base, or RIB. Each entry in the table is one distinct route. The route's attributes, along with local policy constraints, decide the best path from the local AS to the AS that originated the route. "Best path" here means picking whichever routing advertisement, plus its next hop address, the local AS likes most. 🎯

Inside each local BGP-speaking router, that preferred route gets loaded into the local RIB, called the Loc-RIB. That's combined with info from the local copy of the interior routing protocol to build a Forwarding Information Base, or FIB, which the router's forwarding engine uses. Honestly so clean 🍓

BGP doesn't know the finer details of the network's topology link by link, either inside the local AS or inside any remote AS. From that angle, BGP is an inter-AS connectivity maintenance protocol. It is not a link-level topology management protocol. The BGP routing table works as a picture of the Internet's current connectivity, using an AS as the basic unit. 💜

There's also a policy side to the routing table. When an AS advertises a route to a neighboring AS, it's basically saying "I'll accept traffic from you that's headed to the addresses in this route." If the local AS didn't originate the route, that suggests the local AS is willing to act as a transit provider for that traffic on behalf of some third party. 🤝

An AS can also choose whether to accept a route from a neighbor. Accepting a route means that, under certain conditions set by the local route selection parameters, the local AS will use the neighboring AS to reach the addresses covered by that route. 🛣️

The BGP routing domain tries to keep a coherent picture of the inter-AS domain's connectivity. The connectivity is expressed as a preference for "shortest paths" to any destination address, adjusted by the connectivity policies each AS sets. Coherence is a global rule that none of the paths can have loops or dead ends. 🔄

The parts of the BGP routing domain are routing entries, each one a span of addresses. All addresses advertised inside a routing entry share a common origin AS and a common connectivity policy. So the total size of the BGP table is basically a count of how many distinct routes exist on the Internet, where each route covers a contiguous set of addresses that share an origin AS and a reachability policy. Cute, right? 🎀

When people studied the Internet's scaling in the early 1990s, the two critical factors they found were, surprise surprise, routing and addressing [2]. As more devices connect, they use up addresses and also need reachability info kept for those addresses. If the number of distinct provider networks and distinct connectivity policies keeps growing, the routing tables have to keep getting bigger. 📈

Studying the limits of the 32 bit IPv4 address space led to a few outcomes. One was the specification of IPv6 [3]. Another was refining network address translation techniques [4], meant to allow some level of transparent interaction between two networks using different address realms. 🌐

Those approaches don't directly deal with routing growth, though. The routing space is basically the cross product of three things: the complexity of the network's inter-AS topology, the number of distinct connectivity policies, and how fragmented the address space is. NAT, for example, might reduce pressure on the number of public addresses one connected network needs. It doesn't automatically mean that network's connectivity policies can be rolled up into a single upstream provider's aggregated policy. 🙃

When an AS advertises a block of addresses into the exterior routing space, that entry is usually carried across the whole exterior routing domain of the Internet. To measure the common characteristics of the global routing table, you have to pick a point in the default-free part of the exterior routing domain and look at the BGP routing table visible from that point. 👀

3. Measurements of the total size of the BGP Table 📊

At first, measurements of the routing table size were kind of sporadic. Merit [5] took measurements at roughly monthly intervals from 1988 until 1992. In 1994, Erik-Jan Bos at Surfnet in the Netherlands picked it back up, measuring the size of the BGP table at hourly intervals starting in 1994. In 1997, the author adopted this measurement technique, using a measurement point at the edge of AS 1221 at Telstra in Australia, again with an hourly interval. 🇳🇱🇦🇺

The early measurements counted the routing entries inside the set of selected best paths. Later on, they grew to include the number of AS numbers, the number of AS paths, and a set of measurements about the prefix size of routing table entries. 🧩

This data gives a view of how the Internet's routing table has grown over 13 years in total. It includes a very detailed view of the most recent seven years [6]. Just looking at the total size of the BGP routing table across this period, you can spot four distinct phases of inter-AS routing practice on the Internet. Four phases, bestie, that's a whole arc 🎬

3.1. Pre-CIDR Growth 🌱

The routing table size from 1988 until April 1994 shows clear signs of exponential growth. If that growth had kept going unchecked, the available BGP routing table space in the non-default routers of the time would have saturated within a few years. 😬

Estimates of when this would've happened varied a lot from study to study. Still, the overall theme was the same: the BGP routing table was growing faster than the hardware and software capabilities of the deployed network. At some point in the mid-1990s, the BGP table would have gotten bigger than the available equipment could support. Yikes 💀

3.2. CIDR Deployment 🚀

okay so the engineering community was like "we need a hierarchy in inter-domain routing," and that was the glow-up 🧚 The whole point was to let a provider squish all of its customers' routes into ONE routing entry that covered its entire customer base 💅 In practice, that meant new routing protocols that stopped needing the Class A, B and C address split and swapped it for an address prefix plus an associated prefix length 🎀 This approach got called Classless Inter-Domain Routing (CIDR) [5]. iconic 👑

Then in 1994 and 1995 there was a seriously concerted push to deploy CIDR routing across the Internet 💪 It was built on getting people to adopt the CIDR-capable version of BGP, which is BGP4 [7] 🦋

The idea behind CIDR was hierarchical provider address aggregation. A network provider got an address block from an address registry, then announced that whole block into the exterior routing domain as a single entry with a single routing policy 🌸 Customers were encouraged to take a sub-allocation out of the provider's block, and the provider aggregated those smaller routing pieces so they never got passed straight into the exterior routing domain 🫶 During 1994 the routing table stayed pretty flat at around 20,000 entries. More providers were announcing blocks, but that was balanced out by fewer address announcements thanks to CIDR aggregation ⚖️✨

3.3. CIDR Growth 📈

From then until the start of 1998, CIDR was lowkey working, slowing down unconstrained growth in the BGP routing table 🧚 During this stretch the BGP table grew at an approximate linear rate, adding some 10,000 entries per year 💖

If you look closely, the routing system was way more stable at this time 👀 The short term (hourly) variation in the number of announced routes went down, both as a percentage of the announced routes and in absolute terms 📉 Using large aggregate address blocks had another perk: instability at the edge of the network wasn't immediately passed into the routing core 🛡️ Instability at the last hop got absorbed wherever an aggregate route was used in place of a bunch of more specific routes. Put that together with the widespread adoption of BGP route flap damping and the short term instability in the routing space really got tamed during this period 🫧

3.4. Current Growth 💥

okay plot twist: in late 1998 the growth trend in BGP table size changed radically 😭 The growth for 1998 - 2000 is again showing all the signs of re-establishing a growth trend that correlates strongly with an exponential growth model 🔥 This change suggests that pressure to use hierarchical address allocations and CIDR couldn't keep pace with how fast the Internet was growing, and some other factors affecting BGP table size became more prominent 💀 The result is a growth pattern in the total BGP table size that looks more like a compound growth model than a linear one. For January 1999 until December 2000, a compound growth model with 42% growth per year fits the data well 📊

First observation: this growth pattern points to some weakening of the hierarchical model of connectivity and routing within the Internet 🙈 To figure out what's going on with this recent trend, we need to look at several related characteristics of the routing table 🔍

BGP table size data for the first half of 2001 looks different depending on where you measure in the Internet 🌈 Some measurement points, where the local AS has a relatively larger number of more specific routes, show a steady state with no appreciable growth in the first half of 2001. Others, where the local AS has fewer more specific routes, initially show table size still growing. There are some commonly observed discontinuities in the 2001 data, matching events where a significant number of more specific entries got replaced by an encompassing aggregate prefix ✨

The engineers wanted to figure out what's driving this growth and whether it hits some limit on how big the routing space can get, so they kept digging into the BGP routing table 🕵️‍♀️ The analysis now includes counting the ASes in the routing system, the number of distinct AS paths, the range of addresses spanned by the table, and the average span of each routing entry 💅

4.1. AS Number Consumption 🔢

Any network that is multi-homed within the Internet's topology and wants a distinct external routing policy must use a unique AS number to tie its advertised addresses to that policy 🎀 Usually each network has a single AS, and the number of ASes in the default-free routing table tracks how many entities have unique routing policies. There are exceptions, like large global transit providers with varying regional policies, where one network has multiple ASes. Those are pretty uncommon though 🙃

The number of unique ASes in the BGP table has been tracked since late 1996. Over the past four years, AS number deployment has also followed a compound growth model, at 51% per year 📈 As of the start of May 2001 there were some 10,700 ASes visible in the BGP table. If growth keeps going at 51% p.a., the 16 bit AS number space will be fully deployed by August 2005 😱 The IETF is working on modifying BGP to carry AS numbers in a 32-bit field [8]. The protocol changes are relatively straightforward, but the big responsibility sits with the operations community, who need to come up with a transition plan for a gradual move into that larger AS number space 🫶

4.2. Address Consumption 🏠

You can also track the total amount of address space advertised in the BGP routing table. At the start of 2001 the table covered 1,081,131,733 addresses, which is some 25.17% of the total IPv4 address space, or 25.4% of the usable unicast public address space 🌍 By September 2001 that had grown to 1,123,124,472 addresses, or some 26% of the IPv4 address space. It was 1,019,484,655 addresses back in November 1999. BUT, there are a number of /8 prefixes that get announced and withdrawn from the BGP table on a regular basis. If you remove their effects, a compound growth model fit against the previous 12 months of this metric gives a best fit of 7% growth per year in the total number of addresses spanned by the routing table 🤯

Compared to the 42% growth in the number of routing advertisements, the growth in address space is way lower 👀 One possible explanation is that a lot of the growth in connected devices is happening behind various forms of NAT gateways 📱 Looking back at the finite address space concern from just under a decade ago, this explanation suggests the Internet has so far embraced NATs, no matter their various perceived functional shortcomings [9]. Honestly, that's a whole vibe 💅 The explanation also fits with the observation of smaller address fragments supporting distinct policies in the BGP table, since those small blocks can cover arbitrarily large networks sitting behind one or more NAT gateways 🧩 There are other explanations for the gap between table growth and address space growth too, including a trend toward discrete exterior routing policies being applied to finer address blocks 🌸

4.3. Granularity of Table Entries 🔬

The whole point of CIDR aggregation was to support large aggregate address announcements in the BGP routing table. So to check whether that's still the case, the average span of each BGP announcement has been tracked for the past 12 months 👀 The data shows the average span dropping from 16,000 individual addresses in November 1999 to 12,100 in December 2000. As of September 2001 it's down further to an average of 10,700 individual addresses per routing entry 📉 That lines up with the average prefix length going from /18.03 to /18.44 by December 2000, and then to /18.6 by September 2001. Separate observations of the average prefix length used to route traffic in operational networks in late 2000 put it at 18.1 [11]. This trend toward finer-grained entries is potentially cause for concern 😬 It means traffic is spreading across more and more smaller forwarding table entries, and that has implications for the design of high speed core routers, especially when a small number of very high speed cached forwarding entries inside a router's switching subsystem get a lot of use 🔥

A similar pattern shows up in the number of addresses advertised per AS. In December 1999 each AS advertised an average of 161,900 addresses (equivalent to a prefix length of /14.69). By January 2001 that average had dropped to 115,800 addresses, an equivalent prefix length of /15.18 🫧

All of this points to increasingly finer levels of routing detail being announced into the global routing domain 💖 That supports the idea that the efficiencies of hierarchical routing structures are no longer fully realized in the deployed Internet. Instead, finer and finer routing detail is being announced globally in the BGP tables 🧚 The most likely cause is an increasingly dense interconnection mesh, where more networks move from a single-homed connection with hierarchical addressing and routing into multi-homed connections with no hierarchical structure at all 🕸️ The spur for this denser connectivity mesh may well be the declining unit costs of communications bearer services, combined with a common perception that richer sets of adjacencies give greater levels of service resilience 💜✨

4.4. Prefix Length Distribution ✨

Okay so, besides the average prefix length, the analysis also counts how many advertisements there are for each prefix length 🔍

Back in the mid-nineties there was a big push to stop leaning so hard on Class C space 🙅‍♀️ and to get providers advertising bigger address blocks instead, as part of the CIDR effort 💖 The address registries backed this up by handing out provider allocation blocks that match a /19 prefix length and, more recently, a /20 🎀

These measures started in the mid-90's, when the BGP table had some 20,000 - 30,000 entries 🌸 Fast forward about six years to April 2001, and out of the 108,000 entries in the routing table, some 59,000 have a /24 prefix 😭 In absolute terms, the /24 set is the fastest growing set in the BGP routing table 📈 Those smaller blocks also see way more change on an hourly basis 🙈 Plenty of BGP speakers do route flap damping, but there's still a super high level of announcements and withdrawals in that area when you look at route updates per prefix length 💀 With the small prefixes growing so fast, there's some concern that the total BGP flux (announcements and withdrawals per second) might be going up anyway, even with flap damping pushing back 😬 This ties into the point that, for BGP stability under scaling pressure, the thing that really matters isn't the absolute size of the table, but the rate of dynamic path re-computations that happen after announcements and withdrawals 🧠 Withdrawals are the biggest worry because of how many transient intermediate states the BGP distance vector algorithm passes through while it processes one 🌀 Current experimental observations put a typical convergence time at some 2 minutes to propagate a route withdrawal across the BGP domain. [10]

An increase in the density of the BGP mesh, paired with a higher rate of these dynamic changes, has some seriously big implications for keeping the BGP system stable as it keeps growing 🚨 The registry allocation policies also had a hand in the prefix distribution 🗂️ The original registry practice was a minimum allocation unit of a /19, and the 10,000 prefix entries in the /17 to /19 range are a direct result of that policy call 💅 More recently, the allocation policy allows a minimum allocation unit of a /20 prefix, and the /20 prefix is used by some 4,300 entries as of January 2001. In relative terms, it's one of the fastest growing prefix sets 🚀 The number of entries for very small address blocks (smaller than a /24) is small as a share of the total BGP routing table, but in relative terms it's the fastest growing group 🌱 The number of /25 through /32 prefixes in the routing table is growing faster, in percentage change, than any other area of the table 🔥

If prefix length filtering were in widespread use, announcing a very small address block with a distinct routing policy wouldn't really do much good 🙅 The block wouldn't be passed throughout the global BGP routing domain, so the propagation of that policy would be limited in scope 🛑 The growth in these small address blocks, plus the variety of AS paths attached to those routing entries, suggests that prefix length filtering isn't used much in today's Internet 🤔 Without some corrective pressure in the form of widespread adoption of prefix length filtering, the very rapid growth of global announcements for very small address blocks is likely to keep going 📈 In percentage terms, the /25 to /32 set shows the largest growth rates 💜

4.5. Aggregation and Holes 🕳️

With the CIDR routing structure, you can advertise a more specific prefix of an existing aggregate 💫 The point of that more specific announcement is to punch a 'hole' in the policy of the bigger aggregate announcement, creating a different policy for that specific address prefix 🎯

Another use of this trick is a rudimentary form of load balancing and mutual backup for multi-homed networks 🔁 In this model, a network advertises the same aggregate along each connection, then advertises a set of specific advertisements for each connection, tweaking them so the load on each connection is roughly balanced ⚖️ You can spot the two kinds of holes in the routing table pretty easily: policy differentiation uses an AS path that's different from the aggregate advertisement, while load balancing and mutual backup use the same AS path for both the aggregate and the specific advertisements 👀 It's hard to tell whether these more specific advertisements were meant to be an exception to a general rule within the original intent of CIDR deployment 🤷‍♀️ Still, this mechanism is clearly used a lot in the routing table 🙌 Some 59,000 advertisements, or 55% of the total number of routing table entries, are punching policy holes in existing aggregate announcements 😱 Of these, the overall majority (some 42,000 routes) use distinct AS paths, which does look like evidence of finer-grained connection policy in a densely interconnected space 🧩 Long term data isn't available for how these advertisements compare as a proportion of the full routing table, but the growth level strongly suggests that fine-level policy differentiation within existing provider aggregates is a major driver of overall table growth 🚀

5. Current State of inter-AS routing in the Internet 🌐

The comeback of compound growth in the BGP table, plus the finer granularity of routing entries that comes with it, is solid grounds for looking at possible refinements to the Internet's exterior routing protocols 🛠️ It's also grounds for looking at refinements to how inter-AS connectivity is currently operated ⚙️ Apart from the 16 bit AS number space, there's no particular finite limit on any aspect of the BGP table 🔢 The reason this matters is that a long-term pattern of continued growth at current rates could once again create a situation where the capacity of the available processors gets exceeded by some aspect of the Internet routing table 😰

5.1. A denser interconnectivity mesh 🕸️

The falling unit cost of communications bearers in many parts of the Internet is creating a fast-growing market for exchange points and other forms of inter-provider peering 💸 Extensive interconnection at the edges of the Internet is quickly replacing the model of a single-homed network with a single upstream provider 🔄 The underlying deployment model of CIDR assumed a single-homed network, which allowed for a strict hierarchy of supply providers 🏛️ The business reasons driving this denser mesh are huge, and the casualty is the CIDR-induced dampened growth of the BGP routing table 💔

5.2. Multi-Homed small networks and service resiliency 🛡️

It looks like one of the major drivers of recent BGP table growth is small networks, advertised as /24 prefix entries in the routing table, multi-homing with a bunch of peers and upstream providers 📡 Where there are several networks in relatively close proximity, using peer relationships can cut total connectivity costs compared with a single upstream service provider 💰 Just as important, multi-homing with several upstream providers is seen as a way to improve the overall availability of the service 💪 Basically, multi-homing is treated as an acceptable stand-in for upstream service resiliency 🫶 Here's the side effect: when multi-homing is seen as a better substitute for upstream provider resiliency, the upstream provider can't charge a price premium for proving resiliency as a feature of its service 😤 So it has little economic incentive to spend the extra money needed to engineer resiliency into its network 📉 The actions of multi-homed clients then become self-fulfilling 🔮 One way to put it is that service resiliency on the Internet is becoming the customer's responsibility, not the service provider's 🙃

In that environment, resiliency still exists, but instead of coming from the bearer or switching subsystem, it's provided by the BGP routing system 🧵 The question isn't whether this is feasible or desirable in an individual case. The real question is whether the BGP routing system can scale well enough to keep doing that job 🤔

5.3. Traffic Engineering via Routing 🧭

Another thing feeding this growth is selective advertisement of smaller prefixes along different paths, as a way of doing traffic engineering in a multi-homed environment 🛣️ There's lots of effort going into traffic engineering tools inside a single network, using MPLS as the base flow management tool ✨ Inter-provider tools that achieve similar outcomes are a lot more complicated when you use those switching techniques 😵‍💫

Right now, the only tool being used for inter-provider traffic engineering is the BGP routing table 🎯 That use of BGP appears to put extra fine-grained prefixes into the routing table 📌 This makes the growth and stability pressures on the BGP routing domain even worse 😩

5.4. Lack of Common Operational Practices 🤹

There's a lot of evidence that operational practices aren't uniform across the inter-domain routing space 🌀 That covers how prefix filters get used and set, how route damping parameters get used and set, and how much verification is done on BGP advertisements by both the advertiser and the recipient 🔍 There's also some 'noise' in the routing table, where advertisements seem to spread well beyond their intended domain of applicability 📢 Withdrawals and advertisements aren't always damped close to the origin of the route flap either 🌊 This variety of operating practices also extends to policies for accepting advertisements that are more specific than existing provider blocks 🧩

5.5. CIDR and Hierarchical Routing 🎀

Okay so the growth stuff happening in the BGP table is not easily fixed by another round of CIDR deployment pressure in the operator community 💅. The denser interconnectivity mesh, more multi-homing with smaller address prefixes, BGP being stretched to handle inter-domain traffic engineering, and the lack of common operating practices all point to the same thing: the total size of the BGP routing table keeps growing 📈. The growth is most visible with advertisements of smaller address blocks, and these small advertisements are increasingly punching a connectivity policy 'hole' in an existing provider aggregate advertisement 🕳️. Main character energy, but make it chaotic 😭

It may be appropriate to consider how to operate an Internet with a BGP routing table that has millions of small entries 🤯, rather than the expectation of a hierarchical routing space with at most tens of thousands of larger entries in the global routing table 🧚.

6. Future Requirements for the Exterior Routing System ✨

It is beyond the scope of this document to define a scalable inter-domain routing environment, plus the routing protocols and operating practices that go with it 🙅‍♀️. A more modest goal is to look at the attributes of routing systems as they're understood, and pick out the aspects that may be applicable to the inter-domain environment. The end result is a potential set of requirements for inter-domain routing tools 🛠️🌸.

6.1. Scalability 📏

The overall intent is scalability of the routing environment 💜. Scalability can be expressed in lots of dimensions, including the number of discrete network layer reachability entries, the number of discrete route policy entries, the level of dynamic change over a unit of time of these entries, the time to converge to a coherent view of the connectivity of the network following changes, and so on 🤓.

The basic objective behind this requirement for scalability is that the most likely near-to-medium trend in the structure of the Internet is a continuation of the pattern of dense interconnectivity between a large number of discrete network entities, with little impetus behind hierarchical aggregating structures 🕸️. It is not an objective to place any particular metrics on scalability in this examination of requirements 🙅. The only thing it says is that a prudent view would encompass a scale of connectivity in the inter-domain space that is at least two orders of magnitude larger than comparable metrics of the current environment 📈🔥.

6.2. Stability and Predictability 🧊

Any routing system should behave in a stable and predictable fashion 💖. Predictability means that under identical environmental conditions, the routing system should converge to the same state 🎯. Stability means the routing state should be maintained for as long as the environmental conditions remain constant 🔒. It also means that minor variations in the network's state should not cause large scale instability across the entire network while a new stable routing state is reached 🙏. Instead, routing changes should only be propagated as far as necessary to reach a new stable state, so the global requirement for stability implies some degree of locality in the behavior of the system 🫶.

6.3. Convergence ⏱️

Any routing system should have adequate convergence properties 🌈. "Adequate" here means that within a finite time after a change in the external environment, the routing system will have reached a shared common description of the network's topology that accurately describes the current state of the network and is stable ✅. Finite time means a time limit bounded by some upper limit, and that upper limit reflects the requirements of the routing system 🧮. For the Internet, convergence is currently on the order of hundreds of seconds as an upper bound 😩. This long convergence time is perceived as having a negative impact on various applications, especially the time-critical ones 🚨. A more useful upper bound for convergence is on the order of seconds or lower, if we want to support a broad range of application classes 🦋.

It is not a requirement to be able to undertake full convergence of the inter-domain routing system on the sub-second timescale 🙅‍♀️.

6.4. Routing Overhead 📦

The more information passed within the routing system, and the more often those information exchanges happen, the higher the expectation that the routing system can maintain an accurate view of the network's connectivity 👀. But it works the other way too: the more information passed, and the higher the frequency of exchange, the more overhead the operation of the routing system eats up 🍔. So there's an element of design compromise here 🤹. The routing system has to pass enough information across it for each routing element to have adequate local information and reach a coherent local view of the network, yet still keep the total routing overhead low ⚖️.

7. Architectural approaches to a scalable Exterior Routing Protocol 🏛️

This document does not try to define an inter-domain routing protocol that has all the attributes listed above 🙈. It can, however, identify a number of architectural considerations that would form an integral part of the protocol design process 🧠💜.

7.1. Policy opaqueness vs. policy transparency 🫣

The two major approaches to routing protocols are distance vector and link state 🧩.

In a distance vector protocol, a routing node gathers information from its neighbors, applies local policy to that information, and then distributes the updated information to its neighbors 📬. In this model, the local policy applied to routing information isn't necessarily visible to the node's neighbors 🙊. The process of turning received route advertisements into advertised route advertisements uses a local policy process whose rules are not visible externally 🔐. This can be described as 'policy opaque' 🫥. The side effect is that a third party cannot remotely compute which routes a network may accept, or which may be re-advertised to each neighbor 🤷‍♀️.

In link state protocols, a routing node effectively broadcasts its local adjacencies, and the policies it has with respect to those adjacencies, to all nodes within the link state domain 📢. Every node can perform an identical computation on this set of adjacencies and associated policies, in order to compute its local forwarding table 🗺️. The essential attribute of this environment is that the routing node has to announce its routing policies, so a remote node can compute which routes will be accepted from which neighbor, which routes will be advertised to each neighbor, and what attributes, if any, are placed on the advertisement 📣. Within an interior routing domain, local policies are in effect metrics of each link, and these policies can be announced within the routing domain without any consequent impact 💅.

In the exterior routing domain, it is not the case that interconnection policies between networks are always fully transparent 🙃. Various permutations of supplier/customer relationships and peering relationships have associated policy qualifications that are not publicly announced, for business competitive reasons 💼. The current diversity of interconnection arrangements seems to be built on policy opaqueness, and mandating a change to a model of open interconnection policies may clash with operational business imperatives 😬.

An inter-domain routing tool should be able to support models of interconnection where the policy associated with the interconnection is not visible to any third party 🔒💖. If the architectural choice is a constrained one between distance vector and link state, this consideration would seem to favor continued use of a distance vector approach to inter-domain routing 🐢. That choice, in turn, has implications for the convergence properties and stability of the inter-domain routing environment ⏳. If there is a broader spectrum of choice, the considerations of policy-opaqueness would still apply 🫶.

7.2. The number of routing objects 🧮

The current issues with the trend behaviors of the BGP space can be roughly summed up as two things: the growth in the number of distinct routing objects, and the increased level of dynamic behavior of these objects, in the form of announcements and withdrawals 📈📉.

So we need to evaluate possible measures that address the growth rate in the number of objects in the inter-domain routing table, and separately examine measures that can reduce the level of dynamic change in the routing table 🧐. The current routing architecture defines a basic unit of a route object as an originating AS number and an address prefix 🔢.

When looking at the growth rate in the number of route objects, the salient observation is that the number of route objects is a byproduct of the density of the interconnection mesh, and of the number of discrete points where policy is imposed on route objects 🕸️. One approach to reducing the growth in the number of objects is to allow each object to describe larger segments of infrastructure 🧱. Such an approach could use a single route object to describe a set of address prefixes, a collection of ASs, or a combination of the two 🎁. The most direct form of extension would be to preserve the assumption that each routing object represents an indivisible policy entity 🫧. However, one of the drivers of the increasing number of route objects is the proliferation of discrete route objects themselves, so it isn't immediately obvious that this form of aggregation will be capable of addressing the growth 🤔.

If single route objects are going to encompass a set of address prefixes and a collection of ASs, then it appears necessary to define additional attributes within the route object 🛠️. Those attributes would further qualify the policies associated with the object in terms of specific prefixes, specific ASs, and specific policy semantics that may be considered policy exceptions to the overall aggregate 🎀.

Another approach to reducing the number of route objects is to reduce the scope of advertisement of each routing object 🔍. This would let the object be removed and proxy aggregated into some larger object once the logical scope of the object has been reached 🌷. This approach would entail adding route attributes that could define the circumstances where a specific route object would be subsumed by an aggregate route object without impacting the policy objectives associated with the original set of advertisements 💅✨.

7.3. Inter-domain Traffic Engineering 🦋

okay so bestie, the whole reason people want more detail inside route objects is that BGP is doing two jobs at once 💅 It keeps the connections between networks alive, AND it quietly acts as a traffic engineering tool 🙈 That double life is the drama here ✨

Right now, when an AS advertises more specific prefixes with their own policy but the same origin AS, it's usually trying to do traffic engineering. The goal is to balance incoming traffic across multiple paths 🛣️ The originating AS ends up controlling the relative load profile, which is so iconic for them 👑 How? They use a bit of knowledge about how a remote AS picks its routes and use that to limit how many egress choices the remote AS actually has. The most common route selection habit out there is preferring more specific prefixes over larger address blocks 🎯 So by advertising specific prefixes along specific neighbor AS connections, with specific route attributes, traffic headed to those addresses gets pushed through the chosen transit paths. The originating AS basically overrides everyone else's policy choices and sets its import policies higher up than the remote AS's egress policies. Not me going "main character energy" 💖

There's another option too 🌸 You attach a class of traffic engineering attributes to an aggregate route object, so each remote AS responds the way it would to more specific advertisements, but without advertising those specific routes at all. The catch? It still uses route objects to carry traffic engineering policy, so the risk is still there: the route table ends up hauling fine-grained traffic path policies around 😭

Then there's the approach I'm lowkey obsessed with 🧚 Split the jobs apart. Let the routing protocol find a bunch of viable paths from a source AS to a destination AS, and then use a separate set of traffic engineering tools so the traffic source AS can pick the egress path that matches the service profile it wants 🦋

Here's the big difference between intra-domain and inter-domain traffic engineering, and it's a whole plot twist ✨ Inside a domain, the ingress network element picks the path to the egress point. Between domains, it's flipped: a downstream AS (or egress point) is trying to influence the path choice of an upstream AS (or ingress point) 🙃 If explicit traffic engineering actually happened between domains, the current structure would very likely change. Instead of the downstream element trying to constrain the upstream element's choices, a likely approach is for the downstream element to hand over a set of advisory constraints. The upstream element then mixes those constraints with dynamic path service information and its own local policies to make the egress choice 💜

From the inter-domain routing point of view, all of this could mean we get to stop advertising specific routes just for traffic engineering 🎀 BUT, and this is a big but 🫶, we'd still need to add traffic engineering information into the advertised route blocks, which means defining the syntax and semantics of traffic engineering attributes that can ride along on route objects 🔥

7.4. Hierarchical Routing Models 🌈

so the CIDR routing model was built on a hierarchy of providers 🏰 At every level, the routing policies and address space of the lower-level networks got absorbed by the next level up, the 'upstream' provider 💅 The connectivity policy followed the same hierarchical vibe: horizontal connections within one level weren't visible past the two networks involved in them 🙈

But a few outside forces are making interconnection way denser 🌐 Communications services keep getting cheaper per unit, and exchange points are more and more common, adding point-to-multi-point facilities on top of the usual point-to-point connections ✨

The result? The inter-domain space has become a lot less hierarchical 😭 People are kinda worried about this, because hierarchies are a go-to tool for scaling routing systems. BGP is part of that group, and it leans on hierarchies in the address space to keep the number of independently routing objects under control 🧠 The side effect is that every multi-homed network on the Internet ends up with more and more distinct route policies attached to it. Literally a policy explosion 💀

One way to stop that from spreading across the whole inter-domain space is to attach attributes to advertisements that spell out the conditions under which a remote transit AS may proxy-aggregate this route object with other route objects 🫧

7.5. Extend or Replace BGP 🔮

okay, final question, and this one is a whole debate 💖 Can these requirements be met best by a set of upward-compatible extensions to BGP, or by replacing BGP entirely? No recommendation is made here, and it's flagged as something that needs more investigation 🔍 Not me being indecisive, the question is genuinely open 🌸

Extending BGP would mostly mean supporting more transitive route attributes 🎀 That gives the route originator more say over how far the route propagates and what it's supposed to do in terms of policy and traffic engineering. It might also mean letting BGP sessions negotiate extra features meant to improve convergence behavior ⭐ Whether any of that adds up to something scalable and useful for inter-domain routing is still an open question 🤷‍♀️

A replacement protocol could be built on link-state behavior 🧩 We already talked about the policy opaqueness and link-state issues above. The other big problem is limiting how far link state flooding spreads. The inter-domain space would need extra levels of imposed structure, kind of like intra-domain areas 🏗️ That structure might also call for a new set of operator relationships, like mutual transit, and adapting existing practices to that could be really hard 😬

And there's a third option, which is honestly the glow-up I'm rooting for 🦋 Keep BGP for what it already does well, which is propagating route objects along with their AS paths and other attributes. Then add one or more overlay protocols to handle inter-domain traffic engineering and other forms of inter-domain policy negotiation 🧚 This could give the huge installed base running BGP4 a path to transition, since extra functionality lives in the overlays and the basic functionality of BGP4 stays exactly as it is 💜 The catch is the interdependencies between BGP and the overlay protocols, which would need really careful attention, because that's the most critical part of this whole approach ⚠️

8. Directions for Further Activity ✨

okay so bestie, this section is basically the "what do we do next?" part of the RFC 🔥. It starts by admitting that there are short term tricks, like giving network operators incentives to clean up redundant or messy entries in the BGP routing table 🧹. But these are just palliative measures, which is a fancy way of saying bandaids 🩹. They don't actually fix the need for a scalable inter-domain routing protocol in the long run 🥺.

One potential short term protocol refinement is proxy aggregation 💖. The idea is to take a set of bit-wise aligned routing entries that have matching route attributes and, under certain well identified circumstances, squash them into a single re-advertised aggregate routing entry ✨. It's giving tidy closet energy 🧺. The catch is that this technique removes information from the routing system, so you have to be careful to define proxy aggregation conditions that do not materially alter the flow of traffic, or the ability of originating ASes to announce routing policy 🙈. No messing up the vibe for the people who actually own the routes!

A further refinement is to define the syntax and semantics of some additional route attributes 🎀. These could say how far a specific route advertisement should be propagated in the inter-domain space, so that it gets subsumed by a larger aggregate advertisement at the boundary of a domain 🦋. This could form part of the preconditions for automated proxy aggregation of specific routes, and it could also limit how far announcements and withdrawals spread across the routing domain 🌸.

It is unclear that such measures would result in substantial longer term changes to the scaling and convergence properties of BGP4. So don't get too excited yet 😭.

Taking the requirement set enumerated in section 6 of this document, one approach to the longer term requirements may be to preserve a number of attributes of the current BGP protocol, while refining other aspects of the protocol to improve its scaling and convergence properties 💅. A minimal set of alterations could keep the Autonomous System concept so there are boundaries for information summarization 🧚, and keep the approach of associating each prefix advertisement with an originating AS 💜. Policy opaqueness would also stick around, meaning each AS accepts a set of route advertisements, applies local policy constraints, and re-advertises only the ones permitted by those constraints 🫶. It could be feasible to tweak the distance vector path selection algorithm, especially for the intermediate states that happen while a route withdrawal is being processed 🔥. It's also feasible to look at compound route attributes, where a route object can include an aggregate route plus a number of specifics of that aggregate, and attach attributes that apply to the aggregate or to a specific address prefix 👑. These could help support multi-homing and inter-domain traffic engineering mechanisms 🌈. The overall intent is to meet the major requirements of the inter-domain routing space without relying on an ever-growing set of globally propagated specific route objects 💀.

A potential applied research topic is figuring out whether inter-domain connectivity management can be de-coupled from the application of policy constraints and from the sender- and/or receiver-managed traffic engineering requirements 🔬. One approach could use a link-state protocol to keep a consistent view of the inter-domain network topology, use an overlay protocol to negotiate the policy requirements of each AS, and use another overlay to support inter-domain traffic engineering requirements 🦋. The underlying assumption is that by splitting the functional role of inter-domain routing into distinct components, each component will have superior scaling and convergence properties, which in turn should result in superior properties for the entire routing system ✨. Obviously, this assumption requires some testing 🙈.

Research topics with potential longer term application include drawing a distinction between a network's identity, a network's location relative to other networks, and a feasible path between a source and destination network that satisfies various policy and traffic engineering constraints 🧚. Again, the intent is to split the current routing function into a number of distinct scalable components 💖.

9. Security Considerations 🔐

Any adopted inter-domain routing protocol needs to be secure against disruption 🚨. Disruption comes from two primary sources:

  • Accidental misconfiguration 🙃
  • Malicious attacks 😈

Given past experience with routing protocols, both can be significant sources of harm 💀.

Given that it is not reasonable to guarantee the security of all the routers involved in the global Internet inter-domain routing system, there is also every reason to believe that malicious attacks may come from peer routers, in addition to coming from external sources 😱.

A protocol design should therefore consider how to minimize the damage to the overall routing computation that can be caused by a single or small set of misbehaving routers 🛡️.

The routing system itself needs to be resilient against accidental or malicious advertisements of a route object by a route server not entitled to generate such an advertisement 🚫. This implies several things, including the need for cryptographic validation of announcements, cryptographic protection of various critical routing messages, and an accurate and trusted database of routing assignments via which authorization can be checked 🔐. This is literally the most important part of the whole doc, so please don't skip it 😭🫶.

10. References 📚

  • [1] Bradner, S., "The Internet Standards Process -- Revision 3", BCP 9, RFC 2026, October 1996.
  • [2] Clark, D., Chapin, L., Cerf, V., Braden, R. and R. Hobby, "Towards the Future Internet Architecture", RFC 1287, December 1991.
  • [3] Deering, S. and R. Hinden, "Internet Protocol, Version 6 (IPv6) Specification, RFC 2460, December 1998.
  • [4] Srisuresh, P. and K. Egevang, "Traditional IP Network Address Translator (Traditional NAT)", RFC 3022, January 2001.
  • [5] Fuller, V., Li, T., Yu, J. and K. Varadhan, "Classless Inter-Domain Routing (CIDR): an Address Assignment and Aggregation Strategy", RFC 1519, September 1993.
  • [6] Huston, G., "The BGP Routing Table", The Internet Protocol Journal, vol. 4, No. 1, March 2001.
  • [7] Rekhter, Y. and T. Li, "A Border Gateway Protocol 4 (BGP-4)", RFC 1771, March 1995.
  • [8] Vohara, Q. and E. Chen, "BGP support for four-octet AS number space", Work in Progress.
  • [9] Hain, T., "Architectural Implications of NAT", RFC 2993, November 2000.
  • [10] Labovitz, C., Ahuja, A., Bose, A. and J. Jahanian, "Delayed Internet Routing Convergence", Proceedings ACM SIGCOMM 2000, August 2000.
  • [11] Lothberg, P., personal communication, December 2000.

11. Acknowledgements 🫶

This document is the outcome of a collaborative effort of the IAB, and the editor acknowledges the contributions of the members of the IAB in the preparation of the document 🌸. The contributions of John Leslie, Thomas Narten and Abha Ahuja in reviewing this document are also acknowledged 💜.

12. Author 🎀

Internet Architecture Board Email: iab@ietf.org

Geoff Huston Telstra 5/490 Northbourne Ave Dickson ACT 2602 Australia

EMail: gih@telstra.net

Copyright (C) The Internet Society (2001). All Rights Reserved.

This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.

The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.

This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS 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.

Acknowledgement 💖

Funding for the RFC Editor function is currently provided by the Internet Society ✨.

📦 where this page comes from