RFC 4984
Report from the IAB Workshop on Routing and Addressing
RFC 4984: Report from the IAB Workshop on Routing and Addressing 🎀
Part 1 of 9 💅 (the rest of the tea is coming)
Okay bestie, let's get into it. This is a report, not a rulebook. 📝
Authors: D. Meyer (Ed.), L. Zhang (Ed.), K. Fall (Ed.) 💜 Category: Informational ✨ (it gives "here's what we learned," not "you MUST do this") Date: September 2007 📅 Obsoletes / Updates: the title block doesn't list anything for either, so this one isn't replacing or changing any other RFC 🦋
Network Working Group is the group that put it out, and the memo is for information only. It does not specify an Internet standard of any kind, and distribution is unlimited 🌸
Status of This Memo ✨
This memo provides information for the Internet community. It does not specify an Internet standard of any kind. Distribution of this memo is unlimited.
Abstract 🔥
So the IAB ran a Routing and Addressing Workshop in Amsterdam, Netherlands, on October 18-19, 2006 🇳🇱. The main goal was to get everyone on the same page about the problems big backbone operators are having with how well today's Internet routing system scales. The key findings cover the major factors pushing routing table growth, the limits of router tech, and the limits of today's Internet addressing architecture 😭. The hope is that these findings feed into the IETF community and help figure out next steps toward real fixes 🫶
Also, this doc is a report on what happened at the workshop. The views and positions in it belong to the workshop participants, not the IAB 🙈. And the work is still ongoing, so this doc does not try to capture every newer insight or walk through every possible solution that might come out of it 💀
Table of Contents 🧚
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Key Findings from the Workshop . . . . . . . . . . . . . . . . 4
2.1. Problem #1: The Scalability of the Routing System . . . . 4
2.1.1. Implications of DFZ RIB Growth . . . . . . . . . . . . 5
2.1.2. Implications of DFZ FIB Growth . . . . . . . . . . . . 6
2.2. Problem #2: The Overloading of IP Address Semantics . . . 6
2.3. Other Concerns . . . . . . . . . . . . . . . . . . . . . . 7
2.4. How Urgent Are These Problems? . . . . . . . . . . . . . . 8
3. Current Stresses on the Routing and Addressing System . . . . 8
3.1. Major Factors Driving Routing Table Growth . . . . . . . . 8
3.1.1. Avoiding Renumbering . . . . . . . . . . . . . . . . . 9
3.1.2. Multihoming . . . . . . . . . . . . . . . . . . . . . 10
3.1.3. Traffic Engineering . . . . . . . . . . . . . . . . . 10
3.2. IPv6 and Its Potential Impact on Routing Table Size . . . 11
4. Implications of Moore's Law on the Scaling Problem . . . . . . 11
4.1. Moore's Law . . . . . . . . . . . . . . . . . . . . . . . 12
4.1.1. DRAM . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.1.2. Off-chip SRAM . . . . . . . . . . . . . . . . . . . . 13
4.2. Forwarding Engines . . . . . . . . . . . . . . . . . . . . 13
4.3. Chip Costs . . . . . . . . . . . . . . . . . . . . . . . . 14
4.4. Heat and Power . . . . . . . . . . . . . . . . . . . . . . 14
4.5. Summary . . . . . . . . . . . . . . . . . . . . . . . . . 15
5. What Is on the Horizon . . . . . . . . . . . . . . . . . . . . 15
5.1. Continual Growth . . . . . . . . . . . . . . . . . . . . . 15
5.2. Large Numbers of Mobile Networks . . . . . . . . . . . . . 16
5.3. Orders of Magnitude Increase in Mobile Edge Devices . . . 16
6. What Approaches Have Been Investigated . . . . . . . . . . . . 17
6.1. Lessons from MULTI6 . . . . . . . . . . . . . . . . . . . 17
6.2. SHIM6: Pros and Cons . . . . . . . . . . . . . . . . . . . 18
6.3. GSE/Indirection Solutions: Costs and Benefits . . . . . . 19
6.4. Future for Indirection . . . . . . . . . . . . . . . . . . 20
7. Problem Statements . . . . . . . . . . . . . . . . . . . . . . 21
7.1. Problem #1: Routing Scalability . . . . . . . . . . . . . 21
7.2. Problem #2: The Overloading of IP Address Semantics . . . 22
7.2.1. Definition of Locator and Identifier . . . . . . . . . 22
7.2.2. Consequence of Locator and Identifier Overloading . . 23
7.2.3. Traffic Engineering and IP Address Semantics
Overload . . . . . . . . . . . . . . . . . . . . . . . 24
7.3. Additional Issues . . . . . . . . . . . . . . . . . . . . 24
7.3.1. Routing Convergence . . . . . . . . . . . . . . . . . 24
7.3.2. Misaligned Costs and Benefits . . . . . . . . . . . . 25
7.3.3. Other Concerns . . . . . . . . . . . . . . . . . . . . 25
7.4. Problem Recognition . . . . . . . . . . . . . . . . . . . 26
8. Criteria for Solution Development . . . . . . . . . . . . . . 26
8.1. Criteria on Scalability . . . . . . . . . . . . . . . . . 26
8.2. Criteria on Incentives and Economics . . . . . . . . . . . 27
8.3. Criteria on Timing . . . . . . . . . . . . . . . . . . . . 28
8.4. Consideration on Existing Systems . . . . . . . . . . . . 28
8.5. Consideration on Security . . . . . . . . . . . . . . . . 29
8.6. Other Criteria . . . . . . . . . . . . . . . . . . . . . . 29
8.7. Understanding the Tradeoff . . . . . . . . . . . . . . . . 29
9. Workshop Recommendations . . . . . . . . . . . . . . . . . . . 30
10. Security Considerations . . . . . . . . . . . . . . . . . . . 31
11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 31
12. Informative References . . . . . . . . . . . . . . . . . . . . 31
Appendix A. Suggestions for Specific Steps . . . . . . . . . . . 35
Appendix B. Workshop Participants . . . . . . . . . . . . . . . . 35
Appendix C. Workshop Agenda . . . . . . . . . . . . . . . . . . . 36
Appendix D. Presentations . . . . . . . . . . . . . . . . . . . . 371. Introduction 🌈
Okay so it's pretty widely known that today's Internet routing and addressing system has some seriously big scaling problems 😩. The user population keeps growing, and there are a bunch of other factors too: multi-homing, traffic engineering, and policy routing. Together they've been pushing the Default Free Zone (DFZ) routing table size up at a rate that's getting kinda alarming 📈 [DFZ][BGT04]. People have known for a long time that the existing routing architecture might have serious scalability issues, but nobody has found, built, and deployed effective fixes yet 💀
So as a first step, the IAB held a "Routing and Addressing Workshop" in Amsterdam, Netherlands, on October 18-19, 2006 🇳🇱. The main goals were to figure out the existing and potential factors that majorly affect routing scalability, and to write a concise problem statement that could feed into a set of follow-on activities 🧠. This document is the write-up of what came out of that workshop ✨
Here's how the rest of the doc is laid out 🗺️. Section 2 gives an executive summary of the findings. Section 3 covers where the stress in the current global routing and addressing system comes from. Section 4 talks about how Moore's law relates to our ability to build big routers. Section 5 describes a few foreseeable things that could make the problems from Section 2 worse. Section 6 covers earlier work in this area. Section 7 goes deeper into the problem statements, and Section 8 covers the criteria that limit the solution space. Last but not least, Section 9 sums up the recommendations the workshop participants made 💅
The workshop participant list is in Appendix B 🎀. The agenda is in Appendix C, and Appendix D has pointers to the presentations from the workshop 🦋
One more thing, and it's important 🙈: this doc is a report on the workshop's outcome. It's not an official IAB document, so any opinions in it belong to the workshop participants and not the IAB 💜
2. Key Findings from the Workshop 👑
This section is the concise version of the key findings ✨. The workshop discussed a lot of different aspects of routing and addressing systems, but the first two problems covered here were the ones the participants thought mattered most 🔥
The clear, highest-priority takeaway is that we need to build a scalable routing and addressing system 🫶. It has to be scalable even with multihoming, and it has to support a wide range of traffic engineering (TE) requirements. A bunch of scalability problems in the current systems came up, and most of them are tied to the size of the DFZ routing table, which people often call the Routing Information Base (RIB) 📚. The implications included (but weren't limited to) the sizes of the DFZ RIB and FIB (the Forwarding Information Base), the cost of recomputing the FIB, worries about BGP convergence times as RIB and FIB sizes grow, and the cost and power (which means heat dissipation too) of the hardware needed to route traffic in the core of the Internet 🌡️⚡
2.1. Problem #1: The Scalability of the Routing System 🍓
The shape of the DFZ RIB growth curve has been a hot topic of research and discussion since the early days of the Internet [H03]. People have had all kinds of hypotheses about where this growth comes from 🤔. The workshop pinned down these as the main driving forces behind the rapid growth of the DFZ RIB:
- Multihoming,
- Traffic engineering,
- Non-aggregatable address allocations (a big portion of which is inherited from historical allocations), and
- Business events, such as mergers and acquisitions.
All of these can lead to prefix de-aggregation and/or the injection of unaggregatable prefixes into the DFZ RIB 😵💫. De-aggregation makes DFZ RIB growth uncontrolled because, unless we have some non-topologically based routing technology (for example, Routing On Flat Labels [ROFL] or any name-independent compact routing algorithm, e.g., [CNIR]), topological aggregation is the only practical approach we know of for controlling DFZ RIB growth 🧩. That's the whole vibe, and the next section goes over what the workshop discussed about what all this DFZ RIB growth actually means 🦋
Part 1 of 9 done 💖
2.1.1. Implications of DFZ RIB Growth ✨
okay so the workshop folks showed that the DFZ RIB has been growing faster than linearly for several years now [DFZ] 📈💅. Obviously that's a big deal for how much RIB and FIB memory we need 🧠. But the growth driven by prefix de-aggregation is the real tea. It exposes the core of the network to the super dynamic edges, because de-aggregation means more BGP UPDATE messages get injected into the DFZ. People call this "UPDATE churn" 🌪️. So the routers have to do extra work to keep state for the longer prefixes and to update the FIB 💦.
Here's the part that's lowkey wild. The RIB size is capped by the address space and the number of reachable hosts. For IPv4 that's O(m*2^32), where <m> is the average number of peers each BGP router may have 🤯. But the amount of protocol activity needed to spread dynamic topology changes has no cap at all. So the UPDATE churn the network can experience is basically unbounded 😭. The workshop also noted that the UPDATE churn, as it's measured today, is heavy-tailed [ATNAC2006]. That means a small number of Autonomous Systems (ASs) or prefixes cause a disproportionately large share of the churn we see right now 👑.
Even more, a lot of that churn might be unnecessary info 🙈. It could come from edge ASs that are unstable and getting injected into the global routing system [DynPrefix], or from arbitrage around some bandwidth pricing model. See [GIH] for example, or the discussion of how AS 9121 behaved in [BGP2005] 💸.
Finally, the workshop participants pointed out that the UPDATE churn situation may get worse because of current Regional Internet Registry (RIR) policy. End sites get Provider-Independent (PI) addresses under that policy. Those addresses can't be topologically aggregated, so they drag the churn problem described above right into the core routing system 🌀. Of course, as several participants noted, the RIRs don't really have a choice here. Lots of enterprises demand PI addresses so they can multihome without the "provider lock" that Provider-Allocated (PA) [PIPA] address space creates 🔒. Some enterprises also think the renumbering cost that comes with PA assignments is unacceptable 😤.
2.1.2. Implications of DFZ FIB Growth 🧚
This one was a surprise. Tony Li made an observation at the workshop about the relationship between "Moore's Law" [ML] and our ability to build cost-effective, high-performance routers (see Appendix D) 🤯. "Moore's Law" is the empirical observation that the transistor density of integrated circuits, measured against minimum component cost, doubles roughly every 24 months 📊. People often assumed Moore's Law would save the day by making sure technology keeps scaling at historical rates that beat the growth of routing information handled by core router hardware 🦸♀️. But Li pointed out that Moore's Law does not apply to building high-end routers when it comes to cost 💀.
Moore's Law applies specifically to the high-volume part of the semiconductor industry. The low-volume, customized silicon used in core routing is way off Moore's Law's cost curve 📉. Off-chip SRAM is commonly used to store FIB data, and the driver for low-latency, high-capacity SRAM used to be PC cache memory. But cache memory has recently been moving directly onto the processor die, and now cell phones are the main driver for off-chip SRAM 📱. Cell phones need low-power, small-capacity parts that don't fit high-end routers. So the SRAMs that routers prefer are not volume parts, and they don't track with Moore's Law 😩.
2.2. Problem #2: The Overloading of IP Address Semantics 🎀
One of the core assumptions behind routing system scalability was stated beautifully by Yakov Rekhter (sometimes called "Rekhter's Law"). It goes like this 💖:
"Addressing can follow topology or topology can follow addressing. Choose one."
Mike O'Dell had the same idea when he designed an alternate address architecture for ipv6 [GSE]. The address structure was designed specifically to enable "aggressive topological aggregation" and scale the routing system 🌸. Noel Chiappa has also written extensively on this topic (see, e.g., [EID]) ✍️.
Here's the catch. It's hard to create (and maintain) the kind of congruence Rekhter's Law imagines in today's Internet 😵💫. The problem is that addressing gets overloaded with the semantics of both "who" (the endpoint identifier used by the transport layer) and "where" (the locators for the routing system). Some folks would also add that IP addresses are overloaded with "how" too [GIH] 🤷♀️. Either way, this overloading is felt to have had deep implications for the scalability of the global routing system 💜.
So a refinement to Rekhter's Law is that, for the Internet routing system to scale, an IP address must be assigned so that it is congruent with the Internet's topology 🗺️. But identifiers are typically assigned based on organizational (not topological) structure, and stability is a desirable property for them. That creates a "natural incongruence" 🙃. As a result, it is difficult (if not impossible) to make a single number space serve both purposes efficiently 💅.
Following that logic, the workshop participants concluded that the so-called "locator/identifier overload" of IP address semantics is one of the causes of the routing scalability problem we see today 🔥. That makes a "split" seem necessary to scale the routing system. How to actually architect and implement that split was not explored in detail though 🫠.
2.3. Other Concerns 🌈
Besides the issues in Section 2.1 and Section 2.2, the workshop participants identified three more pressing but "second tier" issues 👀.
The first is a general concern with IPv6 deployment. People commonly believe the IPv4 address space has put an effective constraint on IPv4 RIB growth. Once IPv6 deployment lifts that constraint, and without a scalable routing strategy, the rapid DFZ RIB growth problem could get even worse because IPv6's address space is so much larger 😱. Today, the only routing paradigm available for IPv6 is a combination of Classless Inter-Domain Routing (CIDR) [RFC4632] and Provider-Independent (PI) address allocation strategies [PIPA]. SHIM6 [SHIM6] might also join when that technology is developed and deployed. So there's a real opportunity to create a "swamp" (unaggregatable address space) that could be many orders of magnitude larger than what we faced with IPv4 🐊. Basically, IPv6 and its bigger address space make the concerns in Section 2.1 hit harder, and they underscore how important it is to resolve the architectural issue in Section 2.2 ⭐.
The second issue is slow routing convergence. The concern here is that as the number of routes service providers must carry keeps growing, routing convergence becomes a significant problem 🐌.
The third issue is the misalignment of costs and benefits in today's routing system. The IETF doesn't usually consider the "business model" impacts of technology choices. But many participants felt it might be time to rethink that philosophy 🧐.
2.4. How Urgent Are These Problems? ⏰
Almost everyone at the workshop agreed that the problems in Section 2.1 and Section 2.2 need immediate attention 🚨. The reason isn't that anyone saw a looming, well-defined "hit the wall" date. It's that these are hard problems that have resisted solutions so far, they're likely to get more unwieldy as IPv6 deployment goes on, and building and deploying an effective solution will take at least a few years 🕰️.
3. Current Stresses on the Routing and Addressing System 💫
The main concern the workshop participants raised about today's routing system was the rapid growth of the DFZ RIB 📚. The number of entries in 2005 ranged from about 150,000 to 175,000 [BGP2005]. That number reached 200,000 as of October 2006 [CIDRRPT], and it's projected to hit 370,000 or more within 5 years [Fuller] 🚀. Some participants projected the DFZ could reach 2 million entries within 15 years, and there might be as many as 10 million multihomed sites by 2050 😳.
Another related concern is how many prefixes get changed, added, and withdrawn over time (i.e., BGP UPDATE churn) 🔄. That hurts routing convergence, because UPDATEs often force a re-computation and download of the FIB. For example, a BGP router may see up to 500,000 BGP updates in a single day [DynPrefix], with peak arrival rates over 1000 updates per second ⚡. And this isn't just a DFZ problem. The number of internal routes carried by large ISPs also threatens convergence times, since those internal routes include more specifics, Virtual Private Network (VPN) routes, and other routes that don't show up in the DFZ [ATNAC2006] 🫨.
3.1. Major Factors Driving Routing Table Growth 🍓
The DFZ RIB grows because more prefixes get added to the table. Some of that growth is organic, meaning it just comes from the Internet growing 🌱. But a large chunk comes from de-aggregation of address prefixes (i.e., more specific prefixes). In this section we dig into why that trend is speeding up and why it might be a cause for concern 👀.
An increasing fraction of the more-specific prefixes in the DFZ come from deliberate action by operators [ATNAC2006]. Operators have a few motivations for advertising these more-specifics:
- Traffic Engineering, where load is balanced across multiple links by selectively advertising more-specific routes on different links, to adjust how much traffic each one receives; and
- Attempts to prevent prefix-hijacking by other operators, who might advertise more-specifics to steer traffic toward themselves. There are several known instances of this behavior today [BHB06] 🕵️♀️💅
3.1.1. Avoiding Renumbering 🎀
okay so the workshop crew noticed that customers generally prefer to have PI address space 🦋. It gives them extra agility when picking an ISP and helps them dodge renumbering. Lots of end-systems use DHCP to grab addresses, so a quick glance might make it look like renumbering only means touching a modest number of routers and servers (maybe not even end hosts) at a site that got forced to renumber. bestie, it's not that simple 💀.
In reality, renumbering can be way more cumbersome 😭 because IP addresses are often used for other stuff too, like access control lists. They also get hard-coded into applications in environments where a DNS failure would be catastrophic (think some remote monitoring apps). Renumbering can be a mild inconvenience for some sites, and there are guidelines for renumbering a network without a flag day [RFC4192] 📖. But for others, the changes are so hard that renumbering is effectively impossible. not me... 🙈
So yeah, a growing number of customers are seeking PI address space ✨. Current RIR policy reflects this trend, and their policy is to allocate PI prefixes to all customers who claim a need 👑. Routing PI prefixes needs extra entries in the DFZ routing and forwarding tables. Right now ISPs don't typically charge to route PI prefixes 💸. That means the "costs" of the extra prefixes (routing table entries and processing overhead) get born by the global routing system as a whole, not directly by the people using PI space. The workshop folks observed that no strong disincentive exists to discourage the growing use of PI address space. it's giving tragedy of the commons 😭💅
3.1.2. Multihoming 🌸
Multihoming just means a site is served by more than one ISP [RFC4116] 🧚. There are a few reasons it's been increasing, like how much we all rely on the Internet for mission- and business-critical apps, and the general drop in what it costs to get Internet connectivity 📉. Multihoming gives you backup routing (Internet connection redundancy), and in some cases it's mandatory because of a contract or law ⚖️. You can do multihoming with either PI or PA address space, and multihomed sites usually have their own AS numbers (though some don't, usually when those customers are statically routed) 🦋.
Here's the tea ☕. A multihomed site using PI address space has its prefixes sitting in the forwarding and routing tables of each of its providers. For PA space, each prefix allocated from one provider's address allocation is aggregatable for that provider but not the others. If the addresses come from a 'primary' ISP (the one the site uses for routing unless something fails), then the extra routing table entries only show up during path failures to that primary ISP 🔍. The problem shows up when a customer's PA IP prefixes are advertised by AS(es) other than their 'primary' ISP's. Because of the longest-matching prefix forwarding rule, the customer's traffic gets directed through the non-primary AS(s) 😩. So the primary ISP is forced to de-aggregate the customer's prefix just to keep the traffic flowing through it instead of the non-primary AS(s). it's chaotic but make it make sense 💀
3.1.3. Traffic Engineering 🍓
Traffic engineering (TE) is the act of arranging for certain Internet traffic to use or avoid certain network paths. (TE puts traffic where capacity exists, or where some set of path parameters is more favorable to the traffic being placed there 🎯.) TE is done by both ISPs and customer networks, for three main reasons:
- First, as mentioned above, to match traffic with network capacity, or to spread the traffic load across multiple links (often called "load balancing") ⚖️.
- Second, to reduce costs by shifting traffic to lower-cost paths, or by balancing incoming and outgoing traffic volume to keep appropriate peering relations 💰.
- Finally, TE is sometimes deployed to enforce certain forms of policy (e.g., Canadian government traffic may not be permitted to transit through the United States) 🍁🚫.
Honestly there are very few tools for inter-domain traffic engineering today 😩. Network operators usually achieve it by "tweaking" how routing protocols get processed to get the results they want 🔧. At the BGP level, if the address range that needs TE is a portion of a larger PA address aggregate, operators doing TE are forced to de-aggregate prefixes that could otherwise be aggregated, just to steer that address range's traffic onto specific paths 🌀.
In today's super competitive environment, providers need TE to keep performance good and costs low 💅. However, the current practice of TE deployment grows the DFZ RIB. Individual operators might gain from doing TE, but it leads to an overall increased cost for the Internet routing infrastructure as a whole 💔.
3.2. IPv6 and Its Potential Impact on Routing Table Size 🌈
Because IPv6 addresses are bigger than IPv4 addresses, a full, immediate transition to IPv6 is estimated to make the RIB and FIB sizes grow by a factor of about four 📈. The size of the routing table under a more realistic assumption (parallel IPv4 and IPv6 routing for many years) is less clear 🤷♀️. An increasing amount of allocated IPv6 prefixes is in PI space. ARIN [ARIN] has relaxed its policy for allocating such space and has been allocating /48 prefixes when customers request PI prefixes 🧾. So the same pressures that affect IPv4 address allocations also affect IPv6 allocations. it's the same story, new outfit 👗
4. Implications of Moore's Law on the Scaling Problem ✨
[Editor's note: The information in this section is gathered from presentations given at the workshop. The presentation slides can be retrieved from the pointer provided in Appendix D. It is worth noting that this information has generated quite a bit of discussion since the workshop, and as such requires further community input.]
The workshop heard from Tony Li about the relationship between Moore's law and the ability to build cost-effective, high-performance routers 🤓. The scalability of the current routing subsystem shows up in the forwarding table (FIB) and routing table (RIB) of routers in the core of the Internet. FIB storage options are on-chip SRAM, off-chip SRAM, or DRAM, and DRAM is commonly used in lower-end devices. RIB storage is done via DRAM 💾.
[Editor's note: The exact implementation of a high-performance router's RIB and FIB memories is the subject of much debate; it is also possible that alternative designs may appear in the future.]
So the scalability question becomes whether these memory technologies can scale faster than the size of the full routing table 🏃♀️. Baked into that question is the assumption that core routers will be continually and indefinitely upgraded on a periodic basis to keep up with the technology curve, and that the costs of those upgrades get passed along to the general Internet community 💸.
4.1. Moore's Law 🧠
In 1965, Gordon Moore projected that the density of transistors in integrated circuits could double every two years, with respect to minimum component cost. The period was later adjusted to be between 18-24 months, and this conjecture became known as Moore's Law [ML] 📜. The semiconductor industry has been following this density trend for the last 40 or so years 🏭.
The commonly held wisdom is that Moore's law will save the day by making sure technology keeps scaling at the historical rate, one that will surpass the growth rate of routing information 🦸♀️. But it's vital to understand that Moore's law comes out of the high-volume portion of the semiconductor industry, where silicon costs are dominated by the actual fabrication costs. The customized silicon used in core routers is produced in far lower volume, typically 1,000-10,000 parts per year, whereas microprocessors run in the tens of millions per year 📦. That places router silicon well off the cost curve, where economies of scale aren't directly inherited and yield improvements aren't directly inherited from the best current practices. So router silicon benefits from the technological advances made in semiconductors, but it does not follow Moore's law from a cost perspective 💔.
To date, this cost difference hasn't shown up clearly 👀. But the growth in Internet bandwidth and the steady climb in the speed of individual links has forced router manufacturers to apply more sophisticated silicon technology continuously 🔥. A new generation of router hardware has grown at about 4x the bandwidth every three years, and increases in routing table size have been absorbed by the new generations of hardware 🚀. Now that router hardware is nearing the practical limits of per-lambda bandwidth, it's possible that upgrades solely for meeting forwarding table scaling will become more visible 👑.
4.1.1. DRAM 💜
In routers, DRAM is used for storing the RIB and, in lower-end routers, is also used for storing the FIB. Historically, DRAM capacity grows at about 4x every 3.3 years. This translates to 2.4x every 2 years, so DRAM capacity actually grows faster than Moore's law would suggest 📊. DRAM speed, however, only grows about 10% per year, or 1.2x every 2 years [DRAM] [Molinero] 🐢. This is an issue, because BGP convergence time is limited by DRAM access speeds ⚠️. When processing a BGP update, a BGP speaker receives a path and must compare it to all of the other paths it has stored for the prefix. It then iterates over all of the prefixes in the update stream. This results in a memory access pattern that has proven to limit the effectiveness of processor caching 🙃. As a result, BGP convergence time degrades at the routing table growth rate, divided by the speed improvement rate of DRAM. In the long run, this is likely to become a significant issue 😬.
4.1.2. Off-chip SRAM 🦋
Storing the FIB in off-chip SRAM is a popular design decision 🔌. For high-speed interfaces, this requires low-latency, high-capacity parts. The driver for this type of SRAM used to be PC cache memory. However, that cache memory has recently been migrating directly onto the processor die, so volumes of cache memory have fallen off 📉. Today, the primary driver for off-chip SRAM is cell phones, which need low-power, small-capacity parts that aren't applicable to high-end router design 📱. As a result, the SRAMs favored for router design aren't volume parts. They've fallen off the cost curve and don't track with Moore's law 🫶.
4.2. Forwarding Engines ✨
okay so for ages router companies have been building their own special-purpose silicon to forward packets super fast 🔥. this was necessary bc general purpose CPUs are just architecturally not built for the high-bandwidth, low latency, low-jitter I/O interface you need to make high speed forwarding decisions 💀.
so the forwarding engines in high-end routers are some of the most sophisticated Application-specific Integrated Circuits (ASICs) out there, and they're only about one technological step behind general-purpose CPUs 👑. this has been mostly driven by bandwidth growth, and it has already pushed the tech way past the knee in the price/performance curve. since this level of tech is already required to hit the performance goals, using on-chip SRAM is an interesting design option 🧚. if you go that way, then growth in the available FIB is tightly coupled to process technology improvements, which are driven by the general-purpose CPU market. while that growth rate should be enough, in general, the forwarding engine market is decidedly off the high-volume price curve, so the costs to support basic forwarding just keep spiraling 😭.
and here's the scary part 🙈: if Moore's law changes or processor tech evolution slows down, the forwarding engine could quickly become the technological leader of silicon tech. that would rapidly make forwarding tech prohibitively expensive 💸.
4.3. Chip Costs 💅
every process technology step in chip development comes with higher costs 💖. the milestone where you send a finished chip design to a fabricator for manufacturing is called 'tapeout', and that's the point where the designer pays the fixed overhead of putting the chip into production 🎀. tapeout costs have been rising about 1.5x every 2 years, driven by new process tech.
the actual design and development costs have been rising in a similar way, because each new generation of tech increases the device count by roughly a factor of 2 🌸. that allows new features and chip architectures, which inevitably mean more complexity and more labor costs. if new chip development were only driven by the need to scale up memory, and if memory structures scaled, then we'd expect labor costs to stay fixed. unfortunately, memory structures typically do not seem to scale linearly 🙃. individual memory controllers have a non-negligible cost, which leads to the design of an internal on-chip interconnect of memories. the net result is that chip development costs will keep escalating roughly in line with tapeout costs, so the cost curve is about 1.5x every 2 years, forever 😩. since each technology step roughly doubles memory, that means if demand grows faster than about (2x/1.5x) = 1.3x per year, then technology refresh won't be able to stay on a constant cost curve 📈.
4.4. Heat and Power 🔥
transistors eat power both when they're idle ("leakage current") and when they're switching ⚡. the smaller and hotter the transistors get, the bigger the leakage current. the overall power consumption doesn't grow linearly with the density increase, so as we need more powerful routers, cooling tech gets more and more stressed 🥵. right now the existing air cooling system is starting to be a limiting factor for scaling high-performance routers 🧊.
a key metric for evaluating a system is now the unit of forwarding bandwidth per Watt: [(Mb/s)/W] 💜. about 60% of the power goes to the forwarding engine circuits, and the rest is split between the memories, route processors, and interconnect. using parallelization to hit higher bandwidths can make things worse, because of the increased power and cooling demands 😤.
[Editor's note: Many in the community have commented that heat, power consumption, and the attendant heat dissipation, along with size limitations of fabrication processes for high speed parallel I/O interfaces, are the current limiting factors.] 🫶
4.5. Summary 🎀
okay real talk, given how uncontrolled the growth rate is, there's some concern about the long-term health and cost of the routing subsystem of the Internet 😬. the ongoing growth will force periodic technology refreshes. however, the growth rate could possibly exceed what can be supported at constant cost, based on the development costs seen in the router industry. high-end routing is based on low-volume tech, so the cost advantages the bulk of the broader computing industry sees from Moore's law aren't directly inherited 🙅♀️. this leads to a sustainable growth rate of 1.3x/2yrs for the forwarding table and 1.2x/2yrs for the routing table. and since the current baseline growth is at 1.3x/2yrs [CIDRRPT], with bursts that even exceed Moore's law, the trend is that the costs of technology refresh keep growing indefinitely, even in constant dollars 💀💸.
5. What Is on the Horizon 🦋
routing and addressing are two fundamental pieces of the Internet architecture, so any changes to them will likely impact almost all of the "IP stack", from applications all the way down to packet forwarding 🌈. when it comes to resolving the routing scalability problems, as the workshop attendees agreed, we should aim for a long-term solution 🎯. that requires a clear understanding of the trends in the foreseeable future: the growth in Internet user population, the applications, and the technology 🔮.
5.1. Continual Growth 📈
the backbone operators expect the current Internet user population to keep expanding. that growth is measured by traffic volume, the number of hosts connected to the Internet, the number of customer networks, and the number of regional providers 🌍.
5.2. Large Numbers of Mobile Networks ✈️
Boeing's Connexion service pioneered commercial mobile networks that may change their attachment points to the Internet on a global scale 🛫. it's believed that in-flight Internet connectivity will likely become commonplace in the not-too-distant future. when that happens, there could be multiple thousands of airplane networks in the air at any given time 😮.
given that today's DFZ RIB already handles over 200,000 prefixes [CIDRRPT], several thousands of mobile networks, each represented by a single prefix announcement, may not necessarily raise serious routing scalability or stability concerns 🙌. however, there's an open question about whether this number could get substantially larger if other types of mobile networks, like networks on trains or ships, come into play 🚂🚢. if those mobile networks become commonplace, then their impact on the global routing system needs to be assessed 🔍.
5.3. Orders of Magnitude Increase in Mobile Edge Devices 📱
today's tech trends suggest billions of hand-held gadgets may come online in the next several years 🤯. people had different opinions on whether this would, or wouldn't, have a significant impact on global routing scalability 🤷♀️. the current solutions for mobile hosts, namely Mobile IP (e.g., [RFC3775]), handle mobility with one level of indirection through home agents. from a routing perspective, mobile hosts don't look any different than stationary hosts 🏠. if we follow the same approach, new mobile devices shouldn't present challenges beyond the increase in the size of the host population 💅.
the workshop participants recognized that the increase in mobile devices can be significant. they also agreed that if a scalable routing system supporting generic identity-locator separation were developed and introduced, billions of mobile gadgets could be supported without causing undue impact on global routing scalability and stability 🙏✨.
further investigation is needed to fully understand the implications for the global routing system of connecting many new mobile hand-held devices (including mobile sensor networks) to the Internet 🔬.
6. What Approaches Have Been Investigated 🌸
over the years there have been many efforts to investigate scalable inter-domain routing for the Internet [IDR-REQS] 📚. to learn from the insights of these past results, the workshop reviewed several major previous and ongoing IETF efforts:
- The MULTI6 working group's exploration of the solution space and the lessons learned,
- The solution to multihoming being developed by the SHIM6 Working Group, and its pros and cons,
- The GSE proposal made by O'Dell in 1997, and its pros and cons, and
- Map-and-Encap [RFC1955], a general indirection-based solution to scalable multihoming support 🫧.
6.1. Lessons from MULTI6 ✨
okay so the MULTI6 working group had a whole mission: figure out how to do scalable IPv6 multihoming 🌸 they collected a ton of proposals, and they basically sorted them into two big buckets. bucket one fixes the conflict by using provider-independent address assignments. bucket two gives each multihomed site multiple address prefixes, one for each of its providers, so all the addresses can still be topologically aggregatable 🦋
the first bucket had two ideas. idea (1) was just allocating provider-independent address space, which is basically what people already do 💅 idea (2) was assigning IP addresses based on where customers are located geographically. idea (1) doesn't scale, and idea (2) is a huge change to the Internet routing system and its economic model. it also puts undue constraints on ISPs 😭 and honestly both were incomplete, because they never fixed the new problems they created.
most of the proposals landed in bucket two: multiple address blocks per site. here's the tricky part 🧩 IP addresses are already used as identifiers by higher-level protocols and applications, so these proposals have to make a fundamental design decision. which layer is responsible for mapping the multiple locators (the multiple addresses you get from your ISPs) to an identifier? there's also the question of which nodes handle the multiple addresses. you could do it at each individual host, at the edge routers of a site, or at both 🫶
edge routers are great because they can control the traffic flow of the entire site. hosts are great in a different way, since each host gets to choose its own provider-selection policies 💜 but then every host in the multihomed site has to change, which is a lot of work bestie 🙈
while evaluating all the proposals, the group learned two big lessons:
- changing anything in the current practice is hard 😩 for example, inserting an additional header into the protocol would impact IP fragmentation processing, and the current congestion control assumes that each TCP connection follows a single routing path. operators also want to do traffic engineering on a per-site basis, and specifying site policy is often tangled up with the IP address structure.
- the IP address has been used as an identifier, and it's been baked into tons of Internet applications 🔥 some of those apps manipulate IP addresses directly, and others put IP addresses inside the application layer data stream. IP addresses are also used as identifiers when configuring network policies. so changing what an IP address means, like using only the last 64-bit as identifiers the way GSE proposed, would mean changing all those applications and network devices. ngl that's a lot of chaos 💀
6.2. SHIM6: Pros and Cons 🎀
the SHIM6 working group took the second approach from the MULTI6 investigation, which means supporting multihoming through multiple addresses 🦋 they went with a host-based approach. the host's IP stack includes a "shim" that shows a stable "upper layer identifier" (ULID) to the upper layer protocols. the shim can rewrite the IP packets being sent and received so that a currently working IP address gets used. when it's needed, a SHIM6 header is also included in the packet itself, so the remote stack knows what's going on 🧚
with SHIM6, protocols above the IP layer use the ULID to identify endpoints (for example, for TCP connections). the current design suggests picking one of the locators to be the ULID, which means borrowing a locator to act as an identifier. this makes the implementation compatible with existing IPv6 upper layer protocol implementations and applications, and that's a big win, because lots of those apps inherited the long-standing habit of using IP addresses as identifiers 🌈
SHIM6 can isolate upper layer protocols from multiple IP layer addresses. that means a multihomed site can use provider-allocated prefixes, one from each of its providers, to support provider-based prefix aggregation ✨ but this gain comes with several significant costs 😬
first, SHIM6 requires modifications to all host stack implementations so they can do shim processing. second, the shim layer has to maintain the mapping between the identifier and the multiple locators returned from AAAA name resolution, and it must take responsibility for trying multiple locators if failures happen during end-to-end communication. right now the host has little information for figuring out what order to try the locators in when reaching a multihomed destination. there's ongoing effort on that, though 🫶
SHIM6 is also a host-based approach, so it gives the service provider very little control over effective traffic engineering 💅 on top of that, it adds state information on the host about the multiple locators of the remote end. for individual user hosts that's not really a big deal, but it can lead to much larger resource demands on large application servers that handle hundreds of thousands of simultaneous TCP connections 😭
another major issue with SHIM6 is renumbering when a site changes providers 🥀 even though a multihomed site is assigned multiple address blocks, none of them can be treated as a persistent identifier for the site. when the site changes one of its providers, it has to purge that provider's address block from the entire site. the current practice of using the IP address as both an identifier and a locator has also been strengthened by IP addresses showing up in access control lists on policy-enforcement devices (like firewalls). so if SHIM6's ULIDs are going to be used for policy enforcement, switching providers could mean reconfiguring a whole bunch of those devices 🙈
6.3. GSE/Indirection Solutions: Costs and Benefits 🌸
indirection for scalable multihoming came up at the workshop, including the GSE [GSE] approach and indirection approaches like Map-and-Encap [RFC1955] in general 🦋 GSE changes the IPv6 address structure so it carries the meaning of both an identifier and a locator. the first n bytes of the 16-byte IPv6 address are called the Routing Goop (RG), and the routing system uses them exclusively as a locator 💜 the last 8 bytes specify an interface on an end-system. the middle (16 - n - 8) bytes are used to identify site local topology 🧩
the border routers of a site do some clever rewriting. they rewrite the source RG of each outgoing packet so the source address becomes part of the source provider's address aggregation. they also rewrite the destination RG of each incoming packet so the site's RG stays hidden from all the internal routers and hosts 🫣 GSE designates the lower 8 bytes of the IPv6 address as identifiers, but how compatible GSE could be with the increasingly popular cryptographically-generated addresses (CGA) is still to be determined [dGSE] ✨
every identifier/locator split proposal needs a mapping service that can return a set of locators for a given identifier. these proposals also have to solve the problem of detecting locator failures and redirecting data flows to the remaining locators for a multihomed site 😤 Map-and-Encap never addressed these issues. GSE proposed using DNS for the mapping service, but it didn't offer an effective way to recover from locator failure 💀 GSE also requires host stack modifications, because the upper layers and applications are only allowed to use the lower 8 bytes, rather than the entire IPv6 address 🎀
6.4. Future for Indirection 🔮
as the saying goes, "There is no problem in computer science that cannot be solved by an extra level of indirection" 👑 GSE can be seen as one specific version of a whole class of indirection-based solutions to scalable multihoming. Map-and-Encap [RFC1955] is a more general form of that indirection solution. instead of locator rewriting, it uses tunneling to cross the DFZ and support provider-based prefix aggregation 🦋
this class of solutions avoids the provider and customer conflicts around PA and PI prefixes by putting each one in a separate name space. that way ISPs can use topologically aggregatable addresses, while customers can keep their globally unique and provider-independent identifiers 💖 so it supports scalable multihoming and requires no changes to the end systems when the encapsulation is done by the border routers of a site. it also requires no changes to the current practice of applications or backbone operations ✨
BUT (and it's a big but) every gain from an effective solution comes with associated costs 😩 as stated earlier in this section, a mapping service must be provided. that mapping service doesn't just bring complexity and cost. it also adds another point of failure and could be a potential target for malicious attacks 🙈 any solution to routing scalability is necessarily a cost/benefit tradeoff. given how high the potential gains are, this indirection approach deserves special attention in our search for scalable routing solutions 🌈
7. Problem Statements 💅
the fundamental goal of this workshop was to develop a prioritized problem statement about the routing and addressing problems we're facing today, and the workshop spent a considerable amount of time getting there 🫶 this section describes that prioritized problem statement, along with elaborations on both the rationale and the open issues 📝
the workshop participants noted that the Internet community has different classes of stakeholders, and they view today's global routing system from different angles. they also assign different priorities to different aspects of the problem set 🦋 the prioritized problem statement in this section is the consensus of the participants in this workshop, which mostly represented large network operators and a few router vendors. a different group of participants would probably produce a different list, or the same list with different priorities 💜 for example, freedom to change providers without renumbering might be at the very top of the priority list from a workshop of end users and enterprise network operators 🎀
7.1. Problem #1: Routing Scalability ✨
okay so the workshop crew was super clear that routing scalability is the most important problem facing the Internet today 🔥 and it must be solved 💅. nobody really pinned down the time frame for when those solutions need to show up though 🙈. this problem covers the size of the DFZ RIB and FIB 📦, what growing RIB and FIB sizes do to routing convergence times ⏱️, and the cost, power (and hence heat dissipation 🌡️), and ASIC real estate requirements of core router hardware 💻.
It is commonly believed that IPv4 RIB growth has been constrained by the limited IPv4 address space 🤔. however, even under that constraint, the DFZ IPv4 RIB has been growing at what appears to be an accelerating rate [DFZ] 📈. the IPv6 routing architecture is the same as the IPv4 architecture (just with a substantially larger address space) 🌈, so if/when IPv6 becomes widely deployed, it's natural to predict that routing table growth for IPv6 will only exacerbate the situation 😭.
The increasing deployment of Virtual Private Network/Virtual Routing and Forwarding (VPN/VRF) is considered another major factor driving the routing system growth 🚀. there are different views on whether this factor has, or does not have, a direct impact to the DFZ RIB 🤷♀️. a common practice is to delegate specific routers to handle VPN connections, so backbone routers don't necessarily hold state for individual VPNs 🧚. nevertheless, VPNs do represent scalability challenges in network operations 💜.
7.2. Problem #2: The Overloading of IP Address Semantics 🎀
okay this one is my favourite 🫶. as we have reported in Section 3, multihoming, along with traffic engineering, appear to be the major factors driving the growth of the DFZ RIB 👑. below, we break down their impact on the DFZ RIB 🔍.
7.2.1. Definition of Locator and Identifier 🗺️
roughly speaking, the Internet is made of a large number of transit networks and an even larger number of customer networks 🌐. the customer networks contain hosts that are attached to the backbone. if you view the Internet as a graph, transit networks have branches, and customer networks with hosts hang at the edges as leaves 🍃.
as its name suggests, a locator identifies a location in the topology, and a network's or host's locator should be topologically constrained by its present position 📍. identifiers, in principle, should be network-topology independent 💖. that means even though a network or host may need to change its locator when it's moved to a different set of attachment points in the Internet, its identifier should stay constant 💎.
from an ISP's viewpoint, identifiers identify customer networks and customer hosts 🧾. note that the word "identifier" here is defined in the context of the Internet routing system, and the definition may well be different when the word is used in other contexts 🙃. as an example, a non-routable, provider-independent IP prefix for an enterprise network could serve as an identifier for that enterprise 🏢. this block of IP addresses can be used to route packets inside the enterprise network. however, these addresses are independent from the DFZ topology, which is why they are not globally routable on the Internet 🚫.
in cases like that last example, the definition of locators and identifiers can be context-dependent 🌸. following the example further, a PI address may be routable in an enterprise but not in the global network 🔄. if such addresses were allowed to be visible in the global network, they might act as identifiers from a backbone operator's point of view but as locators from an enterprise operator's point of view 🤯.
7.2.2. Consequence of Locator and Identifier Overloading 💥
in today's Internet architecture, IP addresses have been used as both locators and identifiers 😬. combine that with the use of CIDR to perform route aggregation, and a problem shows up for providers or customers (or both) 🥲.
consider, for example, a campus network C that received the prefix x.y.z/24 from provider P1 🏫. when C multihomes with a second provider, P2, both P1 and P2 must announce x.y.z/24 so that C can be reached through both providers 📡. in this example, the prefix x.y.z/24 serves both as an identifier for C and as a (non-aggregatable) locator for C's two attachment points to the transit system 🧩.
as far as the DFZ RIB is concerned, this example shows that customer multihoming blurs the distinction between PA and PI prefixes 🌫️. even though C received a PA prefix x.y.z/24 from P1, C's multihoming forced this prefix to be announced globally (equivalent to a PI prefix). it also forced the prefix's original owner, provider P1, to de-aggregate 😵💫. as a result, today's multihoming practice grows the routing table size in proportion to the number of multihomed customers 📊. the only practical way to scale a routing system today is topological aggregation, and customer multihoming destroys that 💔.
even though multihoming may blur the PA/PI distinction, there's a big difference between PA and PI prefixes when a customer changes its provider(s) 🔀. if the customer used a PA prefix from a former provider P1, that prefix is supposed to be returned to P1 once the change is complete. the customer is supposed to get a new prefix from its new provider, which means renumbering its network 📝. providers need to reclaim their PA prefixes from former customers so they can keep the topological aggregatiblity of their prefixes 🔐. on the other hand, renumbering is considered very painful, if not impossible, by many Internet users, especially large enterprise customers 😩. it's not uncommon for IP addresses in these enterprises to penetrate deeply into various parts of the networking infrastructure, from applications all the way to network management (e.g., policy databases, firewall configurations, etc.) 🕸️. this shows how fragile the system gets when IP addresses are overloaded as both locators and identifiers. significant enterprise operations could be disrupted by the otherwise simple act of switching IP address prefix assignment 🫠.
7.2.3. Traffic Engineering and IP Address Semantics Overload 🎯
in today's practice, traffic engineering (TE) is achieved by de-aggregating IP prefixes 🛣️. you can effectively adjust the traffic volume along specific routing paths by adjusting the prefix lengths and the number of prefixes announced through those paths 🎛️. so the very means of TE practice directly conflicts with constraining routing table growth 🥴.
on the surface, traffic engineering induced prefix de-aggregation seems orthogonal to the locator-identifier overloading problem 🙂. however, this may not necessarily be true. had all the IP prefixes been topologically aggregatable to start with, re-aggregation would have been possible, or at least easier, once the finer-granularity prefix announcements propagated further away from their origins 🔁✨.
7.3. Additional Issues 🧃
7.3.1. Routing Convergence ⏳
there are two kinds of routing convergence issues: eBGP (global routing) convergence and IGP (enterprise or provider) routing convergence 🌍. upon isolated topological events, eBGP convergence doesn't suffer from extensive path explorations in most cases [PathExp], and convergence delay is largely determined by the minimum route advertisement interval (MRAI) timer [RFC4098]. the exception is when a route is withdrawn 🙅♀️. route withdrawals tend to suffer from path explorations and so converge slowly. one participant's experience suggests the withdrawal delays often last up to a couple of minutes 😱. one could argue that if the destination becomes unreachable, a long convergence delay wouldn't cause further damage to applications 🤷♀️. however, there are often cases where a more specific route (a longer prefix) has failed, yet the destination can still be reached through an aggregated route (a shorter prefix) 🧭. in these cases, the long convergence delay does impact application performance 🥺.
IGPs are designed to converge more quickly than BGP might, and they do 🏃♀️. still, the workshop participants were concerned that, in addition to the various special purpose routes that IGPs must carry, the rapid growth of the DFZ RIB size can effectively slow down IGP convergence 🐢. the IGP convergence delay can be due to multiple factors, including:
- Delays in detecting physical failures,
- The delay in loading updated information into the FIB, and
- The large size of the internal RIB, often twice as big as the DFZ RIB, which can lead to both longer route computation time and longer FIB loading time 📚.
the workshop participants hold different views on (1) how severe the routing convergence problem is, and (2) whether it's an architectural problem or an implementation issue 🤔. still, people generally agree that solving the routing scalability problem will certainly help reduce the convergence delay, or at least make it a much easier problem to handle, because there are fewer routes to process 🥳💜.
7.3.2. Misaligned Costs and Benefits 💸
today's rapid growth of the DFZ RIB is driven by a few major factors, including multihoming and traffic engineering, along with the organic growth of the Internet's user base 🌱. there's a powerful incentive to deploy each of these features, since they bring direct benefits to the parties who use them 🎁. however, the beneficiaries may not bear the direct costs of the resulting routing table size increase, and there's no measurable or enforceable constraint to limit that increase 😤.
for example, suppose a service provider has two bandwidth-constrained transoceanic links and wants to split its prefix announcements so it can fully load each link 🌊. the origin AS benefits from performing the de-aggregation. but if the de-aggregated announcements propagate globally, the cost is born by all other ASs 🫤. in other words, the costs of this type of TE practice are not contained to the beneficiaries. multihoming is a similar example: the multihomed site achieves a benefit, but the global Internet incurs the cost of carrying the additional prefix(es) 📦💅.
the misalignment of cost and benefit in the current routing system has been a driver for accelerating the growth of the routing system size 🚀💀.
7.3.3. Other Concerns 🌈
mobility was among the most frequently mentioned issues at the workshop 📱. it's expected that billions of mobile gadgets may be connected to the Internet in the near future 🤯. there was also a discussion on network mobility as deployed in the Connexion service provided by Boeing over the last few years ✈️. however, at this time it seems unclear (1) whether Boeing-like network mobility support would cause a scaling issue in the routing system, and (2) exactly what impact billions of mobile hosts would have on the global routing system 🫣. these discussions were covered in Section 5 of this report 📖.
routing security is another issue that came up a number of times during the workshop 🔐. the consensus from the workshop participants was that, however important routing security may be, it was out of scope for this workshop, whose main goal was to produce a problem statement about addressing and routing scalability 🎯. it was duly considered that security must be one of the top design goals when we get to the solution development stage 🛡️. it was also noted that if we keep letting the routing table grow indefinitely, it may become impossible to add security enhancements in the future 😭🔥.
7.4. Problem Recognition ✨
Okay so step one in solving a problem is noticing it exists AND that it matters 🧐. The tea is that recognizing how serious the routing scaling issue is can be lowkey hard, because there's no specific hard limit on routing system scalability that you can easily demonstrate 🙃. There's also no specific answer to how much time we have to come up with a solution ⏳. Still, the general consensus among the workshop participants is that we seem to be running out of time 😭. Current RIB scaling leads to accelerated hardware cost increases, as explained in Section 4 💸, and it also creates pressure for shorter depreciation cycles, which in turn translates to more cost increases 🥲.
8. Criteria for Solution Development 💅
Any common problem statement may admit multiple different solutions 🦋. This section gives us a set of considerations the workshop talked through over the solution space. Given how diverse customers and providers of the global Internet are, and how elastic the problem is, none of these considerations should inherently preclude any specific solution 🌈. So even though these were first treated as constraints on solutions, we decided to call them 'criteria' instead, to guide solution evaluations 🎀.
8.1. Criteria on Scalability 📈
Clearly, any proposed solution must solve the problem at hand, and our number one problem is the scalability of the Internet's routing and addressing system(s), as outlined in previous sections 👑. Assuming continued growth of the Internet user population, continued increases of multihoming, and RFC 2547 VPN [RFC2547] deployment, the solution must enable the routing system to scale gracefully. That gets measured by the number of:
- DFZ Internet routes, and
- Internal routes.
Also, scalable support for traffic engineering (TE) must be considered a business necessity, not an option 💼. Capacity planning places circuits based on traffic demand over a relatively long time scale, while TE has to work more immediately to match the traffic load to the existing capacity and to match the routing policy requirements ⚡.
Different parties on the Internet may have different specific TE requirements, and that's totally valid 🫶. For example:
- End site TE: based on locally determined performance or cost policies, end sites may wish to control the traffic volume exiting to, or entering from, specific providers 🛍️.
- Small ISP to transit ISP TE: operators may face tight resource constraints and wish to influence the volume of entering traffic from both customers and providers along specific routing paths, so they can best utilize the limited resources 🥺.
- Large ISP TE: given the densely connected nature of the Internet topology, a given destination normally can be reached through different routing paths. An operator may wish to adjust the traffic volume sent to each of its peers based on business relations with its neighbor ASs 🧠.
At this time, it remains an open issue whether a scalable TE solution would necessarily have to live inside the routing protocol, or whether it can be accomplished through means that are external to the routing system 🤔.
8.2. Criteria on Incentives and Economics 💸
The workshop attendees concluded that one important reason for uncontrolled routing growth was the misalignment of incentives 🙄. New entries get added to the routing system to benefit specific parties, but the cost gets born by everyone in the global routing system. The consensus of the workshop was that any proposed solution should strive to reward practices that reduce the overall system cost, and to push back on the "bad" behavior that imposes undue burden on the global system 🚫.
Given the global scale and distributed nature of the Internet, there can no longer (ever) be a flag day on the Internet 😤. To bootstrap the deployment of new solutions, the solutions should provide incentives to first movers. That is, even when a single party starts to deploy the new solution, there should be measurable benefits to balance the costs 🏆.
Whatever kind of solutions the IETF develops, if any, it is unlikely the resulting routing system would stay constant in size 📦. Instead, the workshop participants believed the routing system will keep growing, and that ISPs will keep going through system and hardware upgrade cycles 🔄. Many attendees expressed a desire that the scaling properties of the system let the hardware keep up with Internet growth at a rate comparable to current costs. For example, that would let you keep a 5-year hardware depreciation cycle, as opposed to a situation where scaling leads to accelerated cost increases 💅.
8.3. Criteria on Timing ⏰
There isn't a specific hard deadline, but the unanimous consensus among the workshop participants is that solution development must start now 🚨. If one assumes the solution specification can get ready within a 1 - 2 year time frame, that will be followed by another 2-year certification cycle. So even in the best case scenario, we're facing a 3 - 5 year time frame to get the solutions deployed 😩.
8.4. Consideration on Existing Systems 🧩
The routing scalability problem is a shared one between IPv4 and IPv6, since IPv6 simply inherited IPv4's CIDR-style "Provider-based Addressing" 🔁. The proposed solutions should, and are also expected to, solve the problem for both IPv4 and IPv6 🙌.
Backwards compatibility with the existing IPv4 and IPv6 protocol stack is a necessity 🫡. Even though wide deployment of IPv6 is yet to happen, various parties have already invested substantially in IPv6 implementation and deployment. IPv6 is considered a legacy with shipped code 📱. So a highly desired feature of any proposed solution is to avoid imposing backwards-incompatible changes on end hosts (either IPv4 or IPv6) 🖥️.
In the routing system itself, the solutions must allow incremental changes from the current operational Internet 🪜. The solutions should be backward compatible with the routing protocols in use today, including BGP, OSPF, IS-IS, and others, possibly with incremental enhancements 🔧.
The above backward-compatibility considerations should not constrain the exploration of the solution space 🌌. We need to first find the right solutions, and only after that look into their backward-compatibility issues. This way we get a full understanding of the tradeoffs, and of what potential gains, if any, we might achieve by relaxing the backward-compatibility concerns 🧐.
As a rule of thumb for successful deployment, for any new design, its chance of success is higher if it makes fewer changes to the existing system 💖.
8.5. Consideration on Security 🔐
Security should be considered from day one of solution development. This is non-negotiable, bestie 😤.
If nothing else, the solutions must not make securing the routing system any worse than the situation today. It is highly desirable to have a solution that makes it more difficult to inject false routing information, and makes it easier to filter out DoS traffic 🛡️.
However, securing the routing system is not considered a requirement for solution development. Security is important, but having a working system in the first place is even more important 🥹.
8.6. Other Criteria 📋
A bunch of other criteria were also raised, falling into various different categories. They're summarized below 💌.
- Site renumbering forced by the routing system should be avoided.
- Site reconfiguration driven by the routing system should be minimized.
- The solutions should not force ISPs to reveal internal topology.
- Routing convergence delay must be under control.
- End-to-end data delivery paths should be stable enough for good Voice over IP (VoIP) performance 📞.
8.7. Understanding the Tradeoff ⚖️
As the old saying goes, every coin has two sides 🪙. If we let the routing table keep growing at its present rate, rapid hardware and software upgrade and replacement cycles for deployed core routing equipment may become cost prohibitive 💀. In the worst case, routing table growth may exceed our ability to engineer the global routing system in a cost-effective way. On the other hand, solutions for stopping or substantially slowing down the growth of the Internet routing table will necessarily bring their own costs, perhaps showing up elsewhere and in different forms 🌀. Section 6 has examples of these tradeoffs, where we looked at the gains and costs of a few different approaches to scalable multihoming support (SHIM6, GSE, and a general tunneling approach) 🔍. A major task in solution development is to understand who may have to give up what, and whether that makes a worthy tradeoff 🤝.
Before we wrap up the solution criteria, I have to mention the shortest presentation at the workshop, given by Tony Li (the presentation slides can be found in Appendix D) 🎤. He asked a fundamental question: what is at stake? The answer is the Internet itself 🌍. If the routing system doesn't scale with the continued growth of the Internet, costs might eventually spiral out of control, the digital divide could widen, and Internet growth could slow down, stop, or retreat 😭. Compared to this problem, he considered none of the criteria mentioned so far (except solving the problem) important enough to block the development and deployment of an effective solution 👑✨.
9. Workshop Recommendations ✨
okay so the workshop folks had some big recs, and they're lowkey important 🫶 First, they wanted to say again how much the routing scalability problem matters 💅 The worry about scalability and flexibility in the routing and addressing system has been around for ages, and the DFZ RIB is growing faster than we can engineer the routing infrastructure in an economically feasible way 😭 So we need a long-term solution that can last for the foreseeable future 🔥
Second, most of the people in the room were big service providers and major router vendors 🏢 So the participants recommend that the IAB/IESG run more workshops or find other ways to reach out to other stakeholders, like content providers, retail providers, and enterprise operators. The goal is to share what came out of this workshop, and also to ask those folks what routing and addressing problems they're dealing with today and what they need from a solution 🎀
Third, they want the solution developed in an open, transparent way, with lots of people from the wider networking community involved 🌈 A majority of participants said they're willing to put resources toward building a solution ✨ The research community should be invited in too 🧚 The locator-identifier split is a fundamental architectural issue, so the IAB should lead the work on understanding how to make that architectural change and what its overall impact would be 👑
Fourth, since the long-term solution is the goal, and development and deployment take time, it may be helpful (or even necessary) to buy some time with short- or intermediate-term solutions that are engineeringly feasible, like FIB compression 🍓
Fifth, the participants think the next step is a roadmap from here to solution deployment 🗺️ The IAB and IESG are expected to lead that roadmap effort and ride the momentum from this really successful workshop to move quickly 🚀 The roadmap should set clearly defined short-, medium-, and long-term objectives so the whole community can move in an orchestrated way and see exactly where we're headed while engineering the necessary short-term fixes 💖
Finally, the participants made a bunch of suggestions the IETF might consider when looking at the solution space 🦋 Those are captured in Appendix A, so go check them out 💜
10. Security Considerations 🔐
okay real talk, the security of the routing system is a HUGE deal 😤 But this document doesn't introduce any new protocol or protocol usage, so it doesn't present any new security issues 🫶 Phew 💀
11. Acknowledgments 🎀
Huge thanks to Jari Arkko, Vince Fuller, Darrel Lewis, Tony Li, Eric Rescorla, and Ted Seely, who gave lots of insightful comments on earlier versions of this document 🌸 And a special shoutout to Wouter Wijngaards for the amazing notes he took during the workshop 📝✨
12. Informative References 📚
[RFC1955] Hinden, R., "New Scheme for Internet Routing and
Addressing (ENCAPS) for IPNG", RFC 1955, June 1996.
[RFC2547] Rosen, E. and Y. Rekhter, "BGP/MPLS VPNs", RFC 2547,
March 1999.
[RFC3775] Johnson, D., Perkins, C., and J. Arkko, "Mobility
Support in IPv6", RFC 3775, June 2004.
[RFC4098] Berkowitz, H., Davies, E., Hares, S., Krishnaswamy, P.,
and M. Lepp, "Terminology for Benchmarking BGP Device
Convergence in the Control Plane", RFC 4098, June 2005.
[RFC4116] Abley, J., Lindqvist, K., Davies, E., Black, B., and V.
Gill, "IPv4 Multihoming Practices and Limitations",
RFC 4116, July 2005.
[RFC4192] Baker, F., Lear, E., and R. Droms, "Procedures for
Renumbering an IPv6 Network without a Flag Day",
RFC 4192, September 2005.
[RFC4632] Fuller, V. and T. Li, "Classless Inter-domain Routing
(CIDR): The Internet Address Assignment and Aggregation
Plan", BCP 122, RFC 4632, August 2006.
[IDR-REQS] Doria, A. and E. Davies, "Analysis of IDR requirements
and History", Work in Progress, February 2007.
[ARIN] "American Registry for Internet Numbers",
http://www.arin.net/index.shtml.
[PIPA] Karrenberg, D., "IPv4 Address Allocation and Assignment
Policies for the RIPE NCC Service Region",
RIPE-387 http://www.ripe.net/docs/ipv4-policies.html,
2006.
[SHIM6] "Site Multihoming by IPv6 Intermediation (shim6)",
http://www.ietf.org/html.charters/shim6-charter.html.
[EID] Chiappa, J., "Endpoints and Endpoint Names: A Proposed
Enhancement to the Internet Architecture",
http://www.chiappa.net/~jnc/tech/endpoints.txt, 1999.
[GSE] O'Dell, M., "GSE - An Alternate Addressing Architecture
for IPv6", Work in Progress, 1997.
[dGSE] Zhang, L., "An Overview of Multihoming and Open Issues
in GSE", IETF Journal, http://www.isoc.org/tools/blogs/
ietfjournal/?p=98#more-98, 2006.
[PathExp] Oliveira, R. and et. al., "Quantifying Path Exploration
in the Internet", Internet Measurement Conference (IMC)
2006, http://www.cs.ucla.edu/~rveloso/papers/
imc175f-oliveira.pdf.
[DynPrefix] Oliveira, R. and et. al., "Measurement of Highly Active
Prefixes in BGP", IEEE GLOBECOM 2005
http://www.cs.ucla.edu/~rveloso/papers/activity.pdf.
[BHB06] Boothe, P., Hielbert, J., and R. Bush, "Short-Lived
Prefix Hijacking on the Internet", NANOG 36
http://www.nanog.org/mtg-0602/pdf/boothe.pdf, 2006.
[ROFL] Caesar, M. and et. al., "ROFL: Routing on Flat Labels",
SIGCOMM 2006, http://www.sigcomm.org/sigcomm2006/
discussion/showpaper.php?paper_id=34, 2006.
[CNIR] Abraham, I. and et. al., "Compact Name-Independent
Routing with Minimum Stretch", ACM Symposium on Parallel
Algorithms and Architectures,
http://citeseer.ist.psu.edu/710757.html, 2004.
[BGT04] Bu, T., Gao, L., and D. Towsley, "On Characterizing BGP
Routing Table Growth", J. Computer and Telecomm
Networking V45N1, 2004.
[Fuller] Fuller, V., "Scaling issues with ipv6 routing+
multihoming", http://www.iab.org/about/workshops/
routingandaddressing/vaf-iab-raws.pdf, 2006.
[H03] Huston, G., "Analyzing the Internet's BGP Routing
Table", http://www.potaroo.net/papers/ipj/
2001-v4-n1-bgp/bgp.pdf, 2003.
[BGP2005] Huston, G., "2005 -- A BGP Year in Review", http://
www.apnic.net/meetings/21/docs/sigs/routing/
routing-pres-huston-routing-update.pdf.
[DFZ] Huston, G., "Growth of the BGP Table - 1994 to Present",
http://bgp.potaroo.net, 2006.
[GIH] Huston, G., "Wither Routing?",
http://www.potaroo.net/ispcol/2006-11/raw.html, 2006.
[ATNAC2006] Huston, G. and G. Armitage, "Projecting Future IPv4
Router Requirements from Trends in Dynamic BGP
Behaviour", http://www.potaroo.net/papers/phd/
atnac-2006/bgp-atnac2006.pdf, 2006.
[CIDRRPT] "The CIDR Report", http://www.cidr-report.org.
[ML] "Moore's Law",
Wikipedia http://en.wikipedia.org/wiki/Moore's_law,
2006.
[Molinero] Molinero-Fernandez, P., "Technology trends in routers
and switches", PhD thesis, Stanford University http://
klamath.stanford.edu/~molinero/thesis/html/
pmf_thesis_node5.html, 2005.
[DRAM] Landler, P., "DRAM Productivity and Capacity/Demand
Model", Global Economic Workshop http://
www.sematech.org/meetings/archives/GES/19990514/docs/
07_econ.pdf, 1999.Appendix A. Suggestions for Specific Steps 🪜
at the end of the workshop there was a super lively round-table about specific steps the IETF could take toward a quick solution, plus some potential issues to dodge 🙈 The steps were:
- Finding a home (mailing list) to keep the discussion from the workshop going with wider participation. [Editor's note: Done -- This action has been completed. The list is ram@iab.org.] ✅
- Considering a special process to fast-track solution development so we skip the long protocol standardization cycles. For example, the IESG could charter special design teams for the solution investigation 🏎️
- If a working group gets formed, the charter needs to be narrow and specific enough to allow quick progress, and the WG chair has to be forceful enough to keep the WG activity focused 📋 There was also a discussion about which area the new WG should belong to. Both the routing area ADs and the Internet area ADs are willing to host it 🤝
- It's desirable that solutions get developed in an open environment and free from any Intellectual Property Right claims 🕊️
Finally, given how severe the problem looks, the workshop participants trust that the IAB/IESG/IETF will take prompt action 🫡 But if that doesn't happen, operators and vendors would most likely act on their own and get a solution deployed 😬
Appendix B. Workshop Participants 🎀
Loa Anderson (IAB)
Jari Arkko (IESG)
Ron Bonica
Ross Callon (IESG)
Brian Carpenter (IAB)
David Conrad (IANA)
Leslie Daigle (IAB Chair)
Elwyn Davies (IAB)
Terry Davis
Weisi Dong
Aaron Falk (IRTF Chair)
Kevin Fall (IAB)
Dino Farinacci
Vince Fuller
Vijay Gill
Russ Housley (IESG)
Geoff Huston
Daniel Karrenberg
Dorian Kim
Olaf Kolkman (IAB)
Darrel Lewis
Tony Li
Kurtis Lindqvist (IAB)
Peter Lothberg
David Meyer (IAB)
Christopher Morrow
Dave Oran (IAB)
Phil Roberts (IAB Executive Director)
Jason Schiller
Peter Schoenmaker
Ted Seely
Mark Townsley (IESG)
Iljitsch van Beijnum
Ruediger Volk
Magnus Westerlund (IESG)
Lixia Zhang (IAB)Appendix C. Workshop Agenda 🗓️
okay so the agenda is giving very organized, and the goal for day 1 is literally to collect as many scalability problems in routing and addressing as possible 🔥 here's the schedule, verbatim, bc the times matter 💅
IAB Routing and Addressing Workshop Agenda
October 18-19
Amsterdam, Netherlands
DAY 1: the proposed goal is to collect, as complete as possible, a
set of scalability problems in the routing and addressing area facing
the Internet today.
0815-0900: Welcome, framing up for the 2 days
Moderator: Leslie Daigle
0900-1200: Morning session
Moderator: Elwyn Davies
Strawman topics for the morning session:
- Scalability
- Multihoming support
- Traffic Engineering
- Routing Table Size: Rate of growth, Dynamics
(this is not limited to DFZ, include iBGP)
- Causes of the growth
- Pains from the growth
(perhaps "Impact on routers" can come here?)
- How big a problem is BGP slow convergence?
1015-1030: Coffee Break
1200-1300: Lunch
1330-1730: Afternoon session: What are the top 3 routing problems
in your network?
Moderator: Kurt Erik Lindqvist
1500-1530: Coffee Break
Dinner at Indrapura (http://www.indrapura.nl), sponsored by Cisco
---------
DAY 2: The proposed goal is to formulate a problem statement
0800-0830: Welcome
0830-1000: Morning session: What's on the table
Moderator: Elwyn Davies
- shim6
- GSE
1000-1030: Coffee Break
1030-1200: Problem Statement session #1: document the problems
Moderator: David Meyer
1200-1300: Lunch
1300-1500: Problem Statement session # 2, cont;
Moderator: Dino Farinacci
- Constraints on solutions
1500-1530: Coffee Break
1530-1730: Summary and Wrap-up
Moderator: Leslie DaigleDay 1 is all about the problem hunt 🦋 Day 2 flips it and turns those problems into a proper problem statement, which is so iconic of the process, honestly 🫶
Appendix D. Presentations 🎀
the presentations from the workshop live at this link, so go be a little detective and check them out 🕵️♀️
http://www.iab.org/about/workshops/routingandaddressing
Authors' Addresses 💌
David Meyer (editor) 💜 dmm@1-4-5.net
Lixia Zhang (editor) 🌸 lixia@cs.ucla.edu
Kevin Fall (editor) 🧚 kfall@intel.com
Full Copyright Statement ⚖️
Copyright (C) The IETF Trust (2007).
This document is subject to the rights, licenses and restrictions contained in BCP 78. Except as set forth in BCP 78, the authors keep all of their rights.
This document and the information in it are provided "AS IS". THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST 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 takes no position on the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document, or on whether any license under such rights might or might not be available. It also doesn't claim to have made any independent effort to identify any such rights. Info on how rights work for RFC documents is in BCP 78 and BCP 79 💅
Copies of IPR disclosures made to the IETF Secretariat, any assurances of licenses to be made available, or the result of an attempt to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be found in the IETF online IPR repository:
The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Send that info to the IETF at:
ietf-ipr@ietf.org
And that's the whole vibe, bestie! 🌈✨ Thanks for hanging with me through the whole workshop 💖
📦 where this page comes from
- ietf: rfc4984 2007-09
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms