RFC 2791

Scalable Routing Design Principles

📅 published July 2000, from ietf

RFC 2791: Scalable Routing Design Principles 🎀

okay so bestie, this is RFC 2791, titled Scalable Routing Design Principles 💖. It was written by J. Yu from CoSine Communications and published in July 2000 as part of the Network Working Group series. It's Informational 🧚, which means it's sharing knowledge with the internet community and isn't an actual standard. It doesn't list any obsoletes or updates in its header, so it's just doing its own thing ✨.

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.

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

Abstract 🦋

Okay, so routing is literally essential to a network, and routing scalability is essential to a big network too 😭. When routing doesn't scale, it directly messes with how stable and fast the network is, so scalability is a huge deal, especially for large networks 🔥. This document is all about the major things that affect routing scalability, plus the basic principles for designing scalable routing in large networks 👑.

Table of Contents 🌸

1           Introduction  ..................................      2
2           Common Routing Design Goals  ...................      3
3           Characteristics of Today's Large Networks  .....      3
4           Routing Scaling Issues  ..........................    3
4.1         Router Resource Consumption  .....................    4
4.2         Routing Complexity  ..............................    5
5           Routing Protocol Scalability .....................    6
5.1         IS-IS and OSPF  ..................................    6
5.2         BGP  .............................................    8
6           Scalable Routing Design Principles  ..............    9
6.1         Building Hierarchy  ..............................   10
6.2         Compartmentalization  ............................   13
6.3         Making Proper Trade-offs  ........................   13
6.4         Reduce Burdens of Routing Information Process  ...   14
6.4.1       Routing Intelligence Placement  ..................   14
6.4.2       Reduce Routes and Routing Information  ...........   15
6.4.2.1     CIDR and Route Aggregation  ......................   15
6.4.2.2     Utilize Default Routing where it's Possible  .....   15
6.4.2.3     Reduce Alternative Paths  ........................   16
6.4.3       Use Static Route at Edge  .........................  16
6.4.4       Minimize the Impact of Route Flapping  ............  16
6.5         Scalable Routing Policy and Scalable Implementation  17
6.6         Out-of-band Process  ..............................  19
7           Conclusion and Discussion  ........................  19
8           Security Considerations  ..........................  20
9           Acknowledgement  ..................................  21
10          References  .......................................  21
Author's Address ..............................................  22
Appendix A  Out-of-Band Routing Processes  ....................  23
Full Copyright Statement  .....................................  26

1. Introduction ✨

Routing is essential to a network, bestie 💅. Without routing, packets can't get to where they're supposed to go, and the network is basically non-functional 😭. Designing routing for a large network (think a big ISP backbone) isn't just about making it work, it's also about making it scale 📈. Without a scalable routing system, a network can take severe performance hits, and we've literally seen this happen in big networks with disastrous results 💀. This document digs into routing scalability issues and sets out a bunch of principles for designing scalable routing systems for large networks 🫶.

Here's how the document is laid out 🗺️. Section 2 covers routing functions and design goals. Sections 3 and 4 look at what today's large networks are like and the routing scaling issues that come with them. Section 5 explores routing protocol scalability, and Section 6 gives the scalable routing design principles. Section 7 wraps everything up with a conclusion 🎀.

2. Common Routing Design Goals 🌈

These are the basic goals a routing system should hit ⭐:

  • Stability
  • Redundancy and robustness
  • Reasonable convergency time
  • Routing information integrity
  • Sensible and manageable routing policy

The tricky part is that designing routing for a large network means hitting all of these and making the system scale 🧠.

3. Characteristics of Today's Large Networks 🍓

Today's large networks usually have these features 👑:

  • They're made up of a large number of nodes (routers and/or switches), usually in the hundreds. Some provider networks also include customer CPE routers in their administrative domain, which pushes the node count into the thousands 😳.
  • They have rich connectivity to meet redundancy and robustness needs, so their topologies end up being complex 🕸️.
  • They're default-free, which means they carry all the routes known to the entire Internet. Right now, that's approximately 70,000 routes 🤯.
  • The customer aggregation routers inside these big networks sometimes connect hundreds of customer routers 🙈.

These characteristics are a direct challenge to the routing scalability of the network, no cap 🔥.

4. Routing Scaling Issues 🦋

So the main routing scaling issues right now are: i) excessive router resource consumption, which can make routing convergence harder and destabilize the network; and ii) routing complexity, which leads to poor network management and low service quality 😩.

4.1. Router Resource Consumption 💻

The routing process puts bursty loads on routers, especially when network conditions are unstable 😖. In the extreme case, the routing process eats up all the available resources on the routers, and that results in slow routing convergence or no convergence at all. When a network can't converge its internal routing information, it's basically paralyzed 💀.

It's worth noting that routers whose internal architectures tightly couple the forwarding and routing processes tend to handle excessive routing load poorly 🙅. The newer generation of routers, which separate the resources used for forwarding from the resources used for routing, could offer better routing scalability ✨.

Today, a large network usually runs IS-IS [1,2] or OSPF [3] as an Interior Routing Protocol (IGP), and BGP [4] as an Exterior Routing Protocol (EGP). The IGP calculates paths across the interior of the network. BGP handles routing exchange between routing domains, or Autonomous Systems (AS), and it also processes and propagates external routing information within the network 🌐. A large number of routers and adjacencies, combined with frequent topology changes from link instability, will drive up resource consumption by interior routing 📉. For exterior routing, having a big pile of routers in a BGP system plus frequent routing updates (route flapping) puts a heavy burden on the routers 😵. Section 5 goes into detail on the scaling issues with IS-IS, OSPF and BGP 📚.

On top of that, having many destinations in a routing system, along with multiple paths for those routes, creates these scaling issues for BGP 💅:

  • A large number of routes combined with multiple paths for each one increases the cost of routing processing for route selection, routing policy application and filtering 🧮.
  • Too many routes combined with multiple paths needs a lot of router memory for storage. The demand is even higher at InterExchange Points such as NAPs 🏢.
  • The more routes there are, the greater the chance route flapping will happen, and the more BGP routing updates will follow as a result 🌊. Based on statistics collected by [5], thousands of BGP updates in a measured 15 minute interval can happen on a typical default-free router at a NAP 😱.

Route flapping refers to frequent routing updates caused by network instability, for example when the state of a physical link is fluctuating, or when a BGP session is torn down and re-established numerous times within a short period 🎢.

To get fast convergence, topology change information has to be propagated in a timely fashion ⏩. When a route becomes unavailable and is withdrawn, the information is typically sent immediately. If the affected routes were announced to the global Internet, the update is likely to be propagated to the entire Internet 🌍.

Route flapping has a profound impact on routers running BGP 🥺. The routers have to process routing information frequently, and that eats a tremendous amount of available resources. When a local route or link is oscillating, interior routing gets affected too, because of excessive topology information flooding and the subsequent shortest path calculations 🌀. That said, OSPF (or IS-IS) puts rate limits on this activity to reduce the burden on routers 🛑. For example, OSPF specifies that an individual SLA can be updated at most once every 5 seconds. This basically dampens the flapping 🫧.

Lastly, having large numbers of E-BGP sessions handled by a single router creates another potential scaling issue 🧩. Large networks usually have huge customer subscriptions and connections. To scale the hardware and the number of nodes, providers tend to dedicate a group of customer aggregation routers, each connecting as many customer CPE routers as possible. So it's not unusual for one customer aggregation router to handle hundreds of E-BGP sessions 😭. That creates potential problems with BGP session processing and maintenance, route processing, filtering and route storage 🗂️.

4.2. Routing Complexity 🧠

Routing complexity can lead to network management difficulties, which then hurt troubleshooting and quick problem resolution 🛠️. It can also drag service quality across the network down to less-than-desirable levels 📉. Complicated routing policies, plus special cases or exceptions in a routing design, can add a lot of routing complexity to a large system 🌀.

Routing policy refers to the administrative criteria for handling routing information, usually in the form of routing path selection and route filtering 🧭. How routing information gets handled directly affects traffic flow within a network and across domains. That also means it affects business agreements between different networks 🤝. So the routing policy is largely shaped by non-technical concerns, like business considerations 💼. Routing policy can get super complex, which makes management and configuration an unscalable task 😵‍💫.

The keys to reducing routing complexity are a systematic and consistent routing scheme, and a routing policy that's simple but still meets administrative requirements 🔑.

Another factor adding to the complexity of routing management is prefix-based route filtering 🚧. As is well known, prefix-based filtering is necessary to protect the integrity of the routing system. It becomes a real challenge when the number of routes known to the Internet is as huge as it is today 🫠.

5. Routing Protocol Scalability 💅

Okay so the protocols everyone's actually running today are IS-IS or OSPF for interior routing (aka IGP), and BGP for exterior routing (aka EGP). Compared to the older generation like RIP and EGP, these are a whole glow-up 🦋. But scalability is still a major issue when the network is large, when the routing design doesn't care about scaling, or when the implementation is inefficient 😭.

5.1. IS-IS and OSPF

As we talked about earlier in the doc, IS-IS and OSPF are Link State routing protocols 🧚. The basic pieces are i) building and keeping a Link-State-DataBase (LSDB) that describes the routing topology of one routing area, and ii) doing route calculation based on the topology info in that database. Every node in the area describes its own local topology in a Link State Advertisement, or LSA (it's an LSP in IS-IS land 💜). Each LSA gets distributed, or flooded, to every router in the area, so each router hears from all the others and ends up with a link-state-database that mirrors the whole area's topology.

The main scaling problems are the complexity of link state flooding and route calculation, plus the size of the LSDB, which drives the cost of routing calculation and router memory use.

Flooding is how a router pushes its self-originated LSA out to the rest of the area whenever a link state changes 📣. It sends the LSA out every interface. When a router gets an LSA update, it checks the info, updates its local LSDB, then forwards it out all its own interfaces except the one it came in on. Because of how IS-IS and OSPF flooding works, a full-mesh network of N routers would have O(N^2) LSAs flooded when a single link fails. A single router outage would make LSAs on the order of O(N^3) flood through the system 💀.

For OSPF, the protocol refreshes and floods every 30 minutes even when the network is stable, which can make things worse for a router that's already super loaded 🙈.

Honestly, it's just math: the more routers and adjacencies in a link state IGP area, the more CPU each router has to carry. And when the network is unstable, that load gets amplified 🔥.

A link-state protocol typically uses Dijkstra's Shortest Path First (SPF) algorithm for route calculation. Dijkstra scales to O(N^2), where N is the number of nodes. The algorithm could be improved to O(l*logN), where l is the number of links in the network and N is the number of destinations or routers [6].

So yeah, link state protocols don't scale to a topology with lots of routers and excessive adjacencies in one area. When the topology is unstable, the computation, processing and bandwidth costs get magnified, which eats up router resources. If the instability stops IS-IS or OSPF from maintaining adjacencies, a network routing meltdown happens 🫠.

Node adjacencies are discovered and kept alive through HELLO messages sent periodically from each node. If a node doesn't hear HELLOs from a neighbor within a certain time (40 seconds for OSPF, and less for IS-IS), it decides the neighbor is down. When heavy flooding, recalculation and other activities make router CPU a scarce resource, a router might not get CPU time to send or process HELLO packets. Then the routers lose adjacency, which makes the instability worse. So an isolated blip can escalate into a routing failure across the entire network 😱.

Link-state IGPs also don't scale well when carrying a big pile of routes, like the roughly 70,000 routes known to the Internet today. External routes get included in the LSDB and in LSA (LSP for IS-IS) updates, so link bandwidth and router memory consumption get huge. Plus, the large size of LSA updates makes router resource consumption worse during flooding, especially when the network is unstable 🌪️.

To sum up: a scalable design should avoid putting too many routers in one IGP area, avoid carrying a large number of external routes in the IGP, and, most importantly, avoid excessive adjacencies in the area 👑.

5.2. BGP

BGP is an inter-domain routing protocol that lets routing or reachability information get swapped between different Autonomous-System networks 🌐. Functionally, BGP is made of External BGP (E-BGP) and Internal BGP (I-BGP). E-BGP is used for exchanging external routes, while I-BGP is typically used for distributing externally learned routes within an AS.

The general costs of BGP are:

  • CPU consumption in BGP session establishment, route selection, routing information processing, and handling of routing updates
  • Router memory to install routes and the multiple paths associated with the routes

The major scaling issue with BGP is the full mesh of I-BGP connections 🕸️. Since an IGP can't scale to carry externally learned prefixes (we just covered that), I-BGP takes on that duty. To prevent routing loops, prefixes learned via I-BGP are not allowed to be advertised to another I-BGP speaker. So a full mesh of I-BGP sessions among the routers within an AS is required. In an AS with N routers, each router has to establish I-BGP sessions with N-1 routers, and the system complexity is O(N^2). Therefore, BGP scales poorly when the number of routers in the I-BGP mesh is large 🙈.

A large network normally learns all the routes known to the Internet, which is approximately 70,000. I-BGP will need to carry all of these routes.

The large number of I-BGP sessions and routes eats up tons of resources from each router, especially during BGP session establishment and during periods of heavy route flapping.

Frequent routing updates are another potential scaling problem in large networks. BGP uses incremental updates and sends out routing information about unreachable routes quickly for fast convergence. That's a huge improvement over EGP, where the whole routing table was updated at a fixed time interval. However, when a network is unstable, the updates, especially those containing route withdrawals, are sent immediately, causing global BGP updates. So network instability started anywhere can trigger updates all over the Internet. This effect gets magnified when large amounts of routes are visible to the Internet, putting a heavy load on the routers that participate in BGP 🌪️.

The introduction of a routing hierarchy in BGP, through I-BGP Route Reflectors [7] and BGP Confederations [8], for example, will help alleviate the scaling problem caused by the requirement of full mesh I-BGP establishment 🧩.

Another potential solution is to avoid the requirement of full mesh pairwise I-BGP connections. This would change how BGP distributes routing information among the I-BGP peers. Mechanisms worth considering are using multicast to distribute information, or adopting flooding mechanisms similar to those used in IS-IS or OSPF. Further investigation of the implications of using such mechanisms for BGP route distribution is needed 🔍.

Route dampening [9] is one way to reduce excessive updates triggered by route flapping. The trade-off between fast convergence and network stability should be considered, as discussed in section 6.3.

6. Scalable Routing Design Principles ✨

The routing design for a large-scale network should achieve the basic goals of accuracy, stability, redundancy and convergence, as described in Section 2, and should achieve them in a scalable fashion too 🎀.

How routing scales is influenced by protocol design decisions, protocol implementation decisions, and network design decisions. A network engineer has direct control over network design decisions and can have substantial influence over protocol design and implementation. The focus of this document is network design decisions 💜.

Here's the set of design principles for making a large network routing system more scalable:

  • Building hierarchy
  • Compartmentalization
  • Making proper trade-offs
  • Reducing route processing burdens
  • Defining scalable routing policies and implementation
  • Utilizing out-of-band routing assistance

6.1. Building Hierarchy 🏗️

okay so bestie, remember Section 5.1? OSPF and IS-IS get really clunky when a network has tons of routers, and especially a huge pile of adjacencies 😭. We literally learned this the hard way from networks running IP over ATM with full mesh adjacencies between every router. That full mesh overlay plus the inefficient protocol implementation led to disastrous network outages 💀. The lesson? Don't use a full mesh overlay topology in a big network with a large, flat routing structure. Not me saying "never ever touch a mesh" again 🙈

Building hierarchical routing structures is the key to routing scalability in a large network ✨. As we talked about earlier in this document, big networks are usually made of many routers in a complex topology, so you end up with a huge number of adjacencies. And as also discussed earlier, the routing protocols we have today don't scale well when there are lots of routers in one routing domain or lots of adjacencies among them. So it makes total sense to build a routing hierarchy that cuts down on both the number of routers and the number of adjacencies in a routing domain 💅.

The usual move right now is a two-tiered hierarchy 🌈. You've got a center piece (the transit core network) with a bunch of outskirt pieces (the access networks) plugged into it. The transit core covers the whole geographic area the network serves, and each access network (a.k.a. regional network) covers one region. Regional networks usually don't have direct links to each other, so any traffic going from one regional network to another has to travel through the transit core 🦋. Customer networks only connect to access or regional networks. There are a few different ways to build a routing hierarchy on top of this two-tier topology, so let's go through them 👑.

1) Completely Separate Routing Domains

This design treats the transit core network and each regional network as completely independent ASs when it comes to routing, and every AS runs its own independent IGP. Each regional network E-BGP with the transit core to swap routing knowledge. Full I-BGP connections only need to be set up inside each component network 🎀. That means the biggest IGP domain is just the total number of routers in each component, so the IGP processing load drops and the I-BGP mesh in the routing system shrinks dramatically 📉.

Another perk here is compartmentalization: the routing system gets split up so that instability in one component hits the whole system way less. Check out the discussion in section 6.2 for more on that ✨.

The main downside is that this scheme adds one extra AS to the routing path whenever routes get advertised to the Internet via BGP. That extra AS can cause route selection headaches for other providers 😬.

2) One Domain with IGP and BGP Hierarchy

This method puts the transit core and every regional network into one AS domain 🌸. The hierarchy comes from multi-level IS-IS or OSPF areas, plus either BGP Confederation or I-BGP Reflector, or a mix of the two.

This avoids sneaking in an extra AS in the routing path, which is a big win over Point 1) 💖. BUT, multi-area hierarchical IGP is rarely used nowadays in large networks, since most of them use IS-IS for internal routing, and IS-IS doesn't have enough multi-level support 😭. Even though IS-IS does support multi-area routing, it enforces a strict hierarchy between the backbone and the sub-areas, and it only lets the backbone area advertise a default route to the sub-areas instead of specific prefixes 🙃. That restriction could be fine for a network with a simple sub-area topology. But a sub-area in a large network (typically a regional or access network) can have a seriously complicated topology itself 🧩. If it only gets super abstract routing info like a default route, its ability to make the route selections needed for traffic engineering gets hurt. It would also limit the information passed to external ASs, like IGP-derived BGP Multi-Exit-Discriminator (MED) information 🫶.

People are working on changing IS-IS so the backbone area can distribute specific routes to sub-areas. A mechanism that helps with that distribution is specified in [15]. Once that becomes available, multi-level IGP will be a really attractive option for building a routing hierarchy inside a large network 🔥.

3) One IGP Area with BGP Hierarchy

Instead of multi-area IS-IS, you could get your hierarchy by making the whole network one IGP domain and then layering a BGP hierarchy on top 🧚. Luckily, the hierarchical topology of the network in this case helps cut down on adjacencies in the routing domain (remember, there are no connections among the second-level network components 💜). You can also carefully arrange the adjacencies to keep them at a minimum while still getting good redundancy 🍓. BUT this is less than ideal, because the number of routers stays the same, which bumps up the load on the SPF calculation 😵. Plus, instability in any regional network would still affect the entire network. In other words, there's no fault isolation 💀.

Even with one IGP domain, you can build a BGP hierarchy to make I-BGP more scalable 💅. BGP Reflectors and BGP Confederations are existing mechanisms made to tackle the scaling problem of full-mesh I-BGP ✨.

And here's a bonus: a BGP reflector lets you build more than two levels of hierarchy, as long as the interactions between the different levels are carefully arranged so they can't create routing loops 🔁.

Now, the questions worth asking are: "Are two levels of routing hierarchy sufficient for handling scaling issues?" "Is there really a need for more than two levels of hierarchy?" 🤔

When a second-tier sub-domain of a large network (like a regional network) gets too big for routing protocols to handle, you either need to add another layer of hierarchy or split the sub-domain into multiple second-tier sub-domains 🌿.

Keeping two levels of hierarchy and adding more sub-domains seems more manageable than adding another level. One thing to watch out for, though, is not piling more nodes onto the top-level or transit core network, because that makes it less scalable 🙈. Connecting the split sub-areas to the same core router would avoid adding more nodes to the core area than is recommended 🎀.

More than two levels of hierarchy would go beyond what IGPs can do as they're defined today 😤. In OSPF, for example, all the areas have to be connected through the backbone area, which rules out more than two levels of hierarchy. IS-IS has the same limitation. So if you want more than two hierarchical layers in an IGP, the protocols would need to be redefined 🛠️.

The complexity of protocols and management goes up with every level you add to the hierarchy 📈. According to [6], most of the OSPF protocol bugs found over the years are related to routing area support 🐛. Since the interaction among multiple levels makes management and debugging harder, it's desirable to keep the levels in a hierarchy to a minimum 🫶.

6.2. Compartmentalization 🧱

A scalable routing design for a large network should be able to localize problems or failures 🎯. That way they don't spread across the whole network, eat up the resources of network routers, and cause network-wide instability. This is compartmentalization ✨. It makes fault isolation possible, and that's what contributes to the stability of a large network 💖.

To get compartmentalization in a large network's routing design, you need to avoid making the whole large network one flat routing system or routing domain 🚫. That's the reason behind dividing interior and exterior routing in the global routing system 🌍. Inside a network, it's best to split things into multiple routing domains or multiple routing areas 🍰. For example, in OSPF, only summary route SLAs (rather than individual area routes) get flooded beyond the area 🌊. When an area border router aggregates the routes in its sub-area, instability in any route included in the summary route won't cause SLAs to be flooded to other areas 🙌. So router resources in other areas aren't used up on flooding and SPF recalculation 💅. In other words, instability within each individual area gets stopped from spreading to the entire routing domain 🛑.

Since building a routing hierarchy basically chops a big routing area into smaller areas or domains, it helps achieve the goal of compartmentalization 🦋.

6.3. Making Proper Trade-offs ⚖️

When you're designing routing for a large network, the overall goal should be set with routing scalability and stability in mind 🧠. You have to take the trade-offs between conflicting goals into account. Examples of these trade-offs are redundancy vs. scalability and convergence vs. stability 🎀.

Redundancy adds complexity and more adjacencies to the network topology 😩. It also means you want as many alternative paths as possible for each route, which makes route processing and storage burdens go up 📦. Because of these problems, it may be necessary to give up absolute redundancy in favor of a reasonable level that scales better for the routing system 💜.

Fast convergence requires that changes in network topology get propagated to the network as quickly as possible 🏎️. But that action increases routing updates and, in turn, the route processing burden 📈. It gets worse when a network carries full Internet routing information (which large networks usually do) and topology changes keep happening 😵‍💫. Route dampening may be necessary to get stability, even if it means giving up some absolute fast convergence 🧊.

6.4. Reduce Burdens of Routing Information Processing 🧹

The tasks for reducing routing processing burdens include: i) strategically placing the routing intelligence within the network, ii) avoiding carrying unnecessary routing information, and iii) reducing the impact of route flapping 🌈. Honestly, that's the cleanup checklist for keeping routers from drowning 💖✨.

6.4.1. Routing Intelligence Placement ✨

okay so a router that runs routing policies, does route filtering, and does dampening is said to possess routing intelligence 🧠 Bestie, routing intelligence is needed for three things: i) enforcing business agreements between network entities as routing policies, ii) protecting the integrity of the routing information inside the network, and sometimes iii) shielding a network from instability happening somewhere else on the Internet 💅

The more routing intelligence a router has, the more of its resources those jobs eat up. So it makes total sense to put as little routing intelligence as possible on routers that are already overloaded with other stuff 😭

Traffic is usually heavily concentrated in the core of the network. Traffic gathers up from the edge toward the core, so it's less concentrated near the edge. So if you want a scalable routing system, it's smart to put routing intelligence at the edge 🌸 This matters extra in networks built with routers that don't properly separate forwarding from routing. Pushing routing intelligence out to the edge as much as possible also spreads the computational and configuration burdens across all the routers, which is iconic 👑

It's also desirable to move the heavy work of processing routes onto out-of-band processors. That frees up more of the network routers' resources for forwarding and handling packets 🦋

6.4.2. Reduce Routes and Routing Information 💜

Remember from Section 4.1 that a huge number of routes in the system is one of the main culprits behind route scaling problems 😩 So the move is to cut down the number of routes in the system without losing the routing information you actually need 🫶

6.4.2.1. CIDR and Route Aggregation 🎀

CIDR, as specified in [10], gives us a way to aggregate routes. That helps use IP address space efficiently and cuts the number of routes in the global routing table. CIDR lets you summarize routing information, and that's one of the keys to routing scalability on today's Internet, literally a main character move ✨

Route aggregation doesn't just help global Internet scalability either. It helps scalability in local networks too. The big goal is to keep the routes in the backbone to a minimum 🌈

To get better aggregation inside the network, meaning fewer routes in the network overall, each access or regional network should be given a block of consecutive IP addresses. That way, when a regional network announces its routes to the transit core network, they can be aggregated 💖 Then the core and the other regional networks don't need to know the specific prefixes of any particular access network. Yes, planning customer address assignment out of a provider block so it supports aggregation takes effort, but it's totally worth it 🍓

6.4.2.2. Utilize Default Routing When Possible 🧚

A default route gives you the ultimate in route summarization, shrinking routing information down to the bare minimum 🤏 Summarization also hides the instability of an individual route, like when a route is flapping 🙈 So it's really beneficial for a network to use default routing when it's appropriate.

For example, say a second-tiered regional network is a stub, and no connected customer is asking for full Internet routing information. Then the regional network can just point its default route at the core network it's connected to 💅

BUT (and this is important) over-summarizing routing information can lose routing granularity. When that happens, managing the network, like traffic engineering, gets worse 💀 So you have to be careful when you use default routing ⚠️

6.4.2.3. Reduce Alternative Paths 🌸

The Internet is richly connected because reliability is a requirement. So there are usually a lot of paths to any particular destination 🛣️ In other words, the BGP routing table can hold many alternate paths to the same destination, and those eat up router memory and pile onto the routing processing burden 😮‍💨

To make routing scale, it's desirable to reduce alternate paths while still keeping reasonable redundancy. For example, on a given border router, such as a NAP router, one primary path plus one alternate path gives you reasonable redundancy. In that case, a third or fourth alternate route could be thrown away for the sake of scaling 🧹 This is a trade-off every network administrator has to make based on what her network actually needs 👑

6.4.3. Use Static Route at Edges 🦋

Like we said earlier, one of the scaling issues in big networks is that a single router might fan out to hundreds of customer routers. So if every one of those customer routers talks BGP with the edge router, resource consumption gets super intense 🥵 So the real question is: does the edge router really need to BGP with all of its attached customer routers? 🤔

At first glance, it seems like a customer network in a different Autonomous System (AS) has to exchange routing information with the provider network over BGP. But that's not always true 🙅‍♀️ When a customer network is single-homed (meaning the provider network is the customer's only network connection), BGP isn't necessary and static routing can work just fine ✨ Since the customer is single-homed, static routing won't hurt any services. The perks are that the customer aggregation router has fewer E-BGP sessions to handle, and no route flapping can come from the statically configured customer routes 🎉

Configuring the customer's static routes on the provider's aggregation router can add management overhead, especially if the customer announces a lot of routes 😵 But the set of routes a customer announces to the provider usually changes infrequently, so once it's configured, it needs low maintenance 🫶

6.4.4. Minimize the Impact of Route Flapping 🌊

Route flapping, as we talked about earlier, is mostly caused by link instability and/or BGP session instability, which leads to excessive routing updates across the Internet 😩 Route flapping can start anywhere on the global Internet and affect every network in the Internet routing mesh (BGP mesh) 🌐 There are over 70,000 routes known to the Internet and very little isolation for route flapping, so handling it could be overwhelming for routers in any network 😭

One way to reduce the effect of route flapping is to turn on route dampening as specified in [10] ✨ Basically, dampening suppresses an unstable route until it becomes stable again. The current practice is for each ISP to enable route dampening on its border routers. That way, excessive routing updates can be stopped right at the border 🚧

The ideal model is to suppress the announcement of a flapping route right at the source 🎯 One way to do that would be for a router to recognize instability on its directly connected links and suppress the announcement of the route. But so far, there's no such implementation, and this approach should be explored 👀

Route aggregation often masks route flapping, since the components of an aggregated route (the more specific routes) won't cause the aggregated route to flap. So using CIDR can also help ease route flapping 🦋

6.5. Scalable Routing Policy and Scalable Implementation ✨

okay so routing policy is basically the part where networks decide what routes they'll accept or pass along to other networks, and which path they like best when more than one shows up 💅 it's about business deals between network entities, so it's mostly non-technical stuff. the core of it is defining rules for route filtering and route selection 🎀

one piece of filtering is traffic control between routing domains or between different provider networks. making policy based on individual prefixes should be avoided here, because there are so many prefixes on the Internet that it just doesn't scale 🙈 making policy based on ASs that administratively represent a set of prefixes scales way better 💖

another reason to filter is protecting the integrity of routing information, so falsely advertised routes can't lead traffic into 'black holes' 💀 for this one, only prefix-based filtering will actually get the job done. it needs to happen at the borders between a network and its direct customers or peer networks. it gets harder at peer boundaries, since a peer usually advertises a huge pile of prefixes 😭 like we said earlier, there are about 70,000 routes known to the Internet. so a large default-free network would need to filter on the order of hundred of thousands of prefixes or even more, since a route could be advertised by more than one sources. that many prefixes is a real challenge for router configuration memory and configuration management 🫠 to make it scale, you'd need an out-of-band process to sort out which prefixes should be accepted or denied from which source. IRR [11] and DNS [12] are among the current proposed mechanisms for implementing prefix-based filtering 🧚

route selection policy decides which path should be used to send traffic toward a certain destination. it matters a lot when a network has two connections to another network and learns routes from both. the decision is about which path to pick for sending traffic to the customers behind the other network 👑 the choices are typically:

  • Directing traffic to the closest interconnection point for traffic to exit the network. This policy is also known as Hot-Potato-Routing 🔥
  • Directing traffic to the optimal network exit point. The optimal exit point is determined based on certain criteria by the network administrator and is not necessary the closest exit point 🌸
  • Always preferring routes advertised by directly connected customers 💜
  • Allowing other network or customer to determine the path 🦋

when you define a policy, you have to think about what it means for scalable implementation 🧠 for example, if the policy lets customers pick which paths traffic follows, then customers, not the provider, should be the ones setting routing parameters to make routing favor their preferred path. customers can use the BGP community or mechanisms such as MED to set routing preferences in a much more scalable way 🌈 this keeps the routing management burden from landing solely on the provider. spreading that burden around is what makes the policy implementation more scalable 🫶

another scaling move is avoiding complex policy 😤 when routing policy gets complicated, things like router configuration and debugging become a nightmare. the ultimate goal is to make the network manageable, and that's the whole point ✨

the following basic principles would help scale routing policy management:

  • Making policies as simple as possible but meet the requirements
  • Automating as much as possible to avoid error-prone manual work
  • Avoiding policy based on individual prefixes as much as possible with the exception of prefix-based route filtering for protecting routing integrity
  • Avoiding making exceptions
  • Using out-of-band routing policy processing where possible

6.6. Out-of-Band Process 🦋

a typical router does both routing and forwarding, but conceptually those are two separate jobs 💅 a router's ultimate task is forwarding packets based on its forwarding table, and that table is derived from routing information. one of the main causes of route scaling problems is that routers run out of processing power because routing takes way too much of it 😩 a router has to forward packets, but it doesn't necessarily have to exchange and process routing information or execute routing policy. those tasks can be done somewhere else. so the question becomes: would it be possible to remove the routing process from a router to reduce its burden? moving routing off the routers and onto other systems is what's called out-of-band route processing 🧚

out-of-band route processes would, in short, do the heavy-duty routing tasks 💪 they would build a forwarding table for the router, select routes based on pre-defined policy, filter routes, and shield the router from route flapping attacks 🛡️

the shortcomings of out-of-band route processing are the possible introduction of delays in routing changes, the de-coupling of routing and forwarding paths (which could introduce inaccurate routing information), and the cost of extra equipment 🥲

Appendix A presents a current example of out-of-band route processing, and it also suggests other possible solutions 🌷

7. Conclusion and Discussion 🎀

how routing scales has a direct impact on network stability and performance, bestie 😭 with the fast growth of the Internet and the expansion of providers' networks, routing scaling is becoming increasingly an important issue to address. this document identifies the major factors that affect route scalability and sets out basic principles for designing scalable routing in large networks ✨

the major routing scaling issues we face today are excessive router resource consumption due to routing processing burdens, which causes routing convergency difficulties and thus network instability; and routing complexity, which makes management and trouble shooting difficult and causes degradation of service 💀

the outlined principles for designing a scalable routing system are building routing hierarchy; introducing fault isolation; reducing routing processing burden where possible; defining manageable routing policies; and using the assistance of available out-of-band routing process 🍓

using out-of-band resources to help with routing processing is a concept that has only been used in Internet Exchange Points (IXPs) 🌈 however, it could potentially be used to advantage within a network to help address routing scaling issues. this is a topic worthy of further exploration 🔍

routing protocols and/or their implementations can still be improved or enhanced to handle scaling issues better 🔧 for example, the IS-IS multiple level mechanism is needed in order to scale the IGP in large networks. also, using multicast or a reliable flooding mechanism for I-BGP updates instead of pairwise full mesh peering is something worth investigating 👀

it is our belief that even with the deployment of new technologies such as DWDM, MPLS and others in the future, the fundamental routing scheme will remain the current IGP/BGP paradigm. therefore, the scalable routing design principles outlined in this document should still apply with the deployment of new technologies 💖

8. Security Considerations 🔐

this document deals with routing scaling issues, so it's unlikely to have a direct impact on security 🙂

BUT (and this is a big but 😤) certain routing scaling improvement mechanisms suggested in the document, such as network compartmentalization, will possibly alleviate network outages caused by denial-of-service attacks, since they help keep those outages from spreading to the entire network 🛡️💜

although the mechanisms described in this document do not enhance or weaken the security aspect of routing protocols, security enhancement of routing protocols or routing mechanisms may impact routing scalability. so when you apply security enhancements to routing, you have to be aware of what they do to scalability 🚨

for example, the TCP MD5 signature option is proposed as a mechanism to protect BGP sessions from being spoofed [13] 🔑 it's done on a per-session basis, and the overhead of MD-5 extensions is minimal, so it has no direct impact on scalability. there have been concerns about doing per-prefix AS path verification, because any one ISP along a path could have forged or modified information, maliciously or not 😬 one extreme solution is to have a signature for each prefix. that gives very strong security, but it presents enormous scaling issues in terms of processing, memory and administrative overhead 🥵

9. Acknowledgement 🫶

special thanks to Curtis Villamizar and Dave Katz for the extensive review of the document and many helpful comments 🙌 many thanks to Yakov Rekhter, Noel Chiappa and Rob Coltun for their insightful comments 🤓 the author also likes to thank Susan R. Harris for the much needed polishing of the English language in the document 💅

the author was made aware, after publication of this document, that there is a relevant and independent presentation made by Enke Chen on the subject. the presentation is referenced in [14] 🎀

10. References ✨

Okay, the references are where the receipts live, bestie 📚

[1] "Intermediate System to Intermediate System Intra-Domain Routeing Exchange Protocol for use in Conjunction with the Protocol for Providing the Connectionless-mode Network Service (ISO 8473)", ISO DP 10589, February 1990.

[2] Callon, R., "Use of OSI IS-IS for Routing in TCP/IP and Dual Environments", RFC 1195, December 1990.

[3] Moy, J., "OSPF Version 2", RFC 2328, April 1998.

[4] Rekhter, Y. and T. Li, "A Border Gateway Protocol 4 (BGP-4)", RFC 1771, March 1995.

[5] C. Labovitz, R. Malan, F. Jahanian, "Origins of Internet Routing Instability," in the Proceedings of INFOCOM99, New York, NY, June, 1999

[6] J. Moy, "OSPF-Anatomy of an Internet Routing Protocol", Addison-Wesley, January 1998.

[7] Bates, T., Chandra, R. and E. Chen, "BGP Route Reflection - An alternative to full mesh IBGP", RFC 2796, April 2000.

[8] Traina, P., "Autonomous System Confederation Approach to Solving the I-BGP Scaling Problem", RFC 1965, June 1996.

[9] Curtis, V., Chandra, R. and R. Govindan, "BGP Route Flap Damping", RFC 2439, November 1998.

[10] Fuller, V., Li, T., Yu, J. and K. Varadhan "Classless Inter-Domain Routing (CIDR): an Address Assignment and Aggregation Strategy", RFC 1519, September 1993.

[11] Villamizar, C., Alaettinoglu, C., Govindan, R. and D. Meyer, "Routing Policy System Replication", RFC 2769, February 2000.

[12] Bates, T., Bush, R., Li, T. and Y. Rekhter, "DNS-based NLRI origin AS verification in BGP", Work in Progress.

[13] Heffernan, A., "Protection of BGP Sessions via the TCP MD5 Signature Option", RFC 2385, August 1998.

[14] E. Chen, "Routing Scalability in Backbone Networks." Nanog Presentation: http://www.nanog.org/mtg-9901/ppt/enke/index.htm

[15] T. Li, T. Przygienda, H. Smit, "Domain-wide Prefix Distribution with Two-Level IS-IS", Work in Progress.

Author's Address 💌

Jieyun (Jessica) Yu
CoSine Communications
1200 Bridge Parkway
Redwood City, CA  94065

EMail: jyy@cosinecom.com

Appendix A. Out-of-Band Routing Processes 🧚

Okay, this appendix is giving "offload the drama to someone else" energy 💅 The use of a Route Server (RS) at NAPs is the classic example of getting routing scalability through an out-of-band routing process. A NAP is a public inter-connection point where ISP networks swap traffic. ISP routers at a NAP set up BGP peer sessions with each other, which means full mesh E-BGP peering with a complexity of O(N^2) across the whole system. Scary, right? 😭 When the RS shows up, each router only peers with the RS (plus its backup) to get the routing information it needs (or, more precisely, the forwarding information). The RS also filters routes and runs policy for each provider's router, which takes even more weight off everyone 🫶

The Route Server idea can also help with routing scalability in a large network, and there are a few ways to slay it:

  1. RS Assisted Peering between Customer Aggregation Router and Customer Routers

Real talk, in a typical large provider network it's not unusual for one customer aggregation router to connect to hundreds of customer routers. So that router ends up handling hundreds of E-BGP sessions and filtering a huge pile of prefixes 😩 Cutting down the number of customer routers per aggregation router isn't the move, because that just adds more routers to the routing system of the whole network, which doesn't scale for backbone routing and isn't cost efficient either. So using an RS between the customers and the provider's customer aggregation router becomes a super attractive option to lighten the load 💖

Figure 1 shows one way to drop an RS router between a provider's customer aggregation router and its customer routers:

            ---------------------------  LAN Media in a POP
                    |           |
                  -----        -----
                  |CR |        |RS |
                  -----        -----
                  / | \
                 /  |  \
                C1  C2..Cn



     Figure 1: RS serving customer aggregation router connecting
               customer routers

Without an RS, the customer aggregation router (CR) has to peer with customer routers C1, C2 ... Cn (where n could be in the hundreds). With an RS router in the mix, CR, C1, C2 ... Cn all peer with the RS router instead, and the RS passes the processed routing information (or forwarding information) to every one of them, according to policy and filters ✨

The advantages are obvious:

  • The customer aggregation router peers only with the RS router instead of with hundreds of customer routers.
  • The customer aggregation router does not need to filter prefixes or process routing policies, which frees up resources for packet forwarding and handling.

Now, one general concern with an RS router is a possible mismatch between routing connectivity and physical connectivity. For example, if the link between the CR and C1 is down and the RS router isn't aware of the outage, it will keep passing routes from C1 to the CR, and the traffic following those routes will be black holed 💀 BUT this isn't a problem in the specific application described here 🙌 The RS router has to go through the CR to peer with C1, C2 ... Cn. When the link is down, C1 is unreachable from the RS router, so no routing information can be exchanged between the two. As a result, the RS will announce no routes related to C1.

Another concern is a single point of failure. If the RS router goes down, no routing information can be exchanged between the customer aggregation router and C1, C2 ... Cn, and no traffic will flow between them. This can be fixed by adding a second RS router as a backup 🦋

Heads up, bestie: because the RS peers with C1 ... Cn via CR, when the RS router passes routing information to C1 ... Cn, it requires that the IP address of the CR is designated as the next hop. Likewise, when the RS router passes routes from each customer router to the customer aggregation router, it needs to place the correct next hop on the route. Modifications need to be made to the RS code to include this function.
  1. Private RS Router at InterExchange Point

A large provider network often has many BGP peers at the Interexchange Point, NAP or private interconnection. That means one border router has to handle a ton of E-BGP sessions. Since an Interconnect points is usually the administrative boundary between ISPs, policy and route filtering are super demanding, and this creates a scaling problem for the border router 😤

Deploying a bunch of routers to spread the load is an expensive move, since extra hardware and extra ports cost money. Shifting the routing burden onto an RS router is a promising alternative 🍓 When using an RS for multiple peers at a private interexchange point, the setup is similar to the RS between a customer aggregation router and customer routers described in 1) above. For peering at a NAP, the private RS could sit either on the same NAP media or on a private media between the ISP's NAP router and the RS.

  1. RS Routers at Each POP in a Large Network

Even in a network with a hierarchical routing structure, a sub-area can get too large, and I-BGP full meshing may create a scaling problem. One fix would be to split the sub-area or add yet another tier of I-BGP reflector structure. Another possible solution is to use an RS router as an I-BGP Server. Depending on the topology of a POP, this may or may not be suitable. Using RS routers at network POPs needs to be investigated further 🔍

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

Okay, the legal bit, but make it cute 🌸 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. Thank you, Internet Society, for keeping the lights on 💜✨

📦 where this page comes from