From 4bfd864f10b68b71482b35c818559068ef8d5797 Mon Sep 17 00:00:00 2001 From: Thomas Voss Date: Wed, 27 Nov 2024 20:54:24 +0100 Subject: doc: Add RFC documents --- doc/rfc/rfc2791.txt | 1459 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1459 insertions(+) create mode 100644 doc/rfc/rfc2791.txt (limited to 'doc/rfc/rfc2791.txt') diff --git a/doc/rfc/rfc2791.txt b/doc/rfc/rfc2791.txt new file mode 100644 index 0000000..91c5240 --- /dev/null +++ b/doc/rfc/rfc2791.txt @@ -0,0 +1,1459 @@ + + + + + + +Network Working Group J. Yu +Request for Comments: 2791 CoSine Communications +Category: Informational July 2000 + + + Scalable Routing Design Principles + +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 Notice + + Copyright (C) The Internet Society (2000). All Rights Reserved. + +Abstract + + Routing is essential to a network. Routing scalability is essential + to a large network. When routing does not scale, there is a direct + impact on the stability and performance of a network. Therefore, + routing scalability is an important issue, especially for a large + network. This document identifies major factors affecting routing + scalability as well as basic principles of designing scalable routing + for large networks. + + + + + + + + + + + + + + + + + + + + + + + + + +Yu Informational [Page 1] + +RFC 2791 Scalable Routing Design Principles July 2000 + + +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. Without routing, packets cannot be + delivered to desired destinations and the network would be non- + functional. The challenge of designing the routing for a large + network, such as a large ISP backbone network, is not only to make it + work, but also to make it scale. Without a scalable routing system, a + network may suffer from severe performance penalties, as + unfortunately proven by disastrous events in large networks. This + document attempts to analyze routing scalability issues and define a + set of principles for designing scalable routing system for large + networks. + + The organization of this document is as follows: Section 2 describes + routing functions and design goals. Sections 3 and 4 discuss the + + + +Yu Informational [Page 2] + +RFC 2791 Scalable Routing Design Principles July 2000 + + + characteristics of today's large networks and the associated routing + scaling issues. Section 5 explores routing protocol scalability, and + Section 6 presents scalable routing design principles. Section 7 + provides a conclusion to the document. + +2. Common Routing Design Goals + + The basic goals a routing system should achieve are as follows: + + o Stability + o Redundancy and robustness + o Reasonable convergency time + o Routing information integrity + o Sensible and manageable routing policy + + The challenge of designing routing in a large network is not only to + achieve these basic goals but also to make the routing system scale. + +3. Characteristics of Today's Large Networks + + Today's large networks typically possess the following features: + + o They are composed of a large number of nodes (routers and/or + switches), typically in the hundreds. Some provider networks + include customer CPE routers within their administrative domain, + which increases the number of nodes to thousands. + + o They have rich connectivity to meet redundancy and robustness + requirements, and they consequently have complex topologies. + + o They are default-free; that is, they carry all the routes known + to the entire Internet. Currently, the total number is + approximately 70,000. + + o The customer aggregation routers inside the large networks + connect sometimes hundreds of customer routers. + + These characteristics impose a direct challenge to the routing + scalability of the network. + +4. Routing Scaling Issues + + Today, the main issues surrounding routing scaling are: i) excessive + router resource consumption, which can potentially increase routing + convergency difficulties thus destabilize a network; and ii) routing + complexity, resulting in poor management of network, producing low + service quality. + + + + +Yu Informational [Page 3] + +RFC 2791 Scalable Routing Design Principles July 2000 + + +4.1. Router Resource Consumption + + The routing process puts bursty loads on routers, especially under + unstable network conditions. In the extreme case, the routing process + takes all available resources from the routers, which results in slow + routing convergence or no convergence. A network is paralyzed when it + cannot converge internal routing information. + + It's worthy noting that routers with internal architectures that + tightly couple forwarding and routing processes tend to handle the + excessive routing load poorly. The emerging new generation of routers + with the architecture of separating resource used for forwarding and + routing could provide better routing scalability. + + Today, a large network typically employs IS-IS [1,2] or OSPF [3] as + an Interior Routing Protocol(IGP) and BGP [4] as an Exterior Routing + Protocol(EGP), respectively. The IGP calculates paths across the + interior of the network. BGP facilitates routing exchange between + routing domains, or Autonomous Systems (AS). BGP also processes and + propagates external routing information within the network. The + presence of a large number of routers and adjacencies in a network, + coupled with frequent topology changes due to link instability, will + contribute to excessive resource consumption by the interior routing. + In the case of exterior routing, a large quantity of routers in a BGP + system plus frequent routing updates (route flapping) would put a + heavy burden on the routers. Section 5 describes scaling issues with + IS-IS, OSPF and BGP in detail. + + In addition, having many destinations in a routing system, combined + with multiple paths associated with these routes, impose the + following scaling issues on BGP: + + o A large number of routes combined with multiple paths for each + increases the cost of routing processing for route selection, + routing policy application and filtering. + + o Too many routes combined with multiple paths requires large + amounts of memory on routers for storage. The demand is even + higher at InterExchange Points such as NAPs. + + o The larger the number of routes, the greater the chance route + flapping will occur and the more BGP routing updates will happen + as a result. Based on statistics collected by [5], thousands of + BGP updates in a measured 15 minute interval can occur on a + typical default-free router at a NAP. + + + + + + +Yu Informational [Page 4] + +RFC 2791 Scalable Routing Design Principles July 2000 + + + Route flapping refers to frequent routing updates occurring due + to network instability, for example, when the state of a + physical link in the network is fluctuating, or when a BGP + session is torn down and re-established numerous time within a + short period of time. + + To facilitate fast convergence, topology change information must + be propagated in a timely fashion. When a route becomes + unavailable and is withdrawn, the information is typically sent + immediately. If the affected routes have been announced to the + global Internet, the update information 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 this + consumes a tremendous amounts of the available resources. When a + local route or link is oscillating, interior routing is affected + as well by excessive topology information flooding and + subsequent shortest path calculations. However, OSPF (or IS-IS) + imposes rate limits on such activity to reduce the burden on the + routers. For example, OSPF specifies that an individual SLA can + be updated at most once every 5 seconds. This essentially + dampens the flapping. + + Moreover, large numbers of E-BGP sessions processed by a single + router create another potential scaling issue. Large networks usually + have huge customer subscriptions and connections. To scale the + hardware and the number of nodes in the network, providers tend to + dedicate a group of customer aggregation routers, each connecting as + many customer CPE routers as possible. As a result, it's not uncommon + for a customer aggregation router to handle hundreds of E-BGP + sessions, which imposes potential problems, such as BGP session + processing and maintenance, route processing, filtering and route + storage. + +4.2. Routing Complexity + + Routing complexity can lead to network management difficulties, which + will have an impact on trouble shooting and quick problem resolution. + It can result in a less than desirable service quality across the + network. Complicated routing policies and special cases or exceptions + in a routing design can contribute to routing complexity in a large + system. + + Routing Policy refers to the administrative criteria for handling + routing information, commonly in the form of routing path selection + and route filtering. The way routing information is handled has a + direct impact on traffic flow within a network and across domains. As + + + +Yu Informational [Page 5] + +RFC 2791 Scalable Routing Design Principles July 2000 + + + a result, it affects business agreements among different networks. + Therefore, the determination of routing policy is largely dominated + by non-technical concerns, such as business considerations. Routing + policy can be very complex, which would make management and + configuration an unscalable task. + + The keys to reducing routing complexity are systematic as well as + consistent routing scheme and a routing policy that is simple but + meets the requirement of administrative polices. + + Another factor contributing to the complexity of routing management + is prefix-based route filtering. As is well known, prefix-based + filtering is necessary in order to protect the integrity of the + routing system. This becomes a challenge when the number of routes + known to the Internet is as large as it is today. + +5. Routing Protocol Scalability + + Today's commonly deployed routing protocols are IS-IS or OSPF for + Interior routing (aka IGP) and BGP for exterior routing (aka EGP). In + terms of scaling and other aspects, these protocols are already an + improvement over the previous generation of protocols, such as RIP + and EGP. However, scalability is still a major issue when a network + is large, when a routing design is insensitive to scaling issues, or + the protocol implementation is inefficient. + +5.1. IS-IS and OSPF + + As described earlier in the document, IS-IS and OSPF are Link State + routing protocols. The basic components of a link state routing + protocol are i) generation and maintenance of a Link-State-DataBase + (LSDB) that describes the routing topology of a given routing area; + and ii) route calculation based on the topology information in the + database. Each node in a routing area is responsible for describing + its local routing topology in a Link State Advertisement or LSA (LSP + in the case of IS-IS.) Each individually generated LSA will be + distributed or flooded to all the routers in the area. Each router + receives LSAs from all the other routers, forming a link-state- + database that reflects the routing topology of the entire routing + area. + + The main associated scaling issues are the complexity of the link + state flooding and routing calculation, plus the size of the LSDB + which contributes to the cost of routing calculation and router + memory consumption. + + + + + + +Yu Informational [Page 6] + +RFC 2791 Scalable Routing Design Principles July 2000 + + + Flooding is the process by which a router distributes its self- + originated LSA to the rest of the routers in the area in case of any + link state change. A router will send the LSA via all its interfaces. + When receiving an LSA update, a router validates the information and + updates its local LSDB before sending it out via all its own + interfaces, except the one from which it received the original LSA + update. Given the nature of IS-IS or OSPF flooding, a full-mesh + network with N routers would have O(N^2) of LSAs flooded in the + network when a single link failure occurs. A single router outage + would cause LSA in the order of O(N^3) to be flooded in the system. + + In the case of OSPF, the protocol will refresh or flood every 30 + minutes even under stable network conditions, which could increase + the problem for an already highly loaded router. + + From the above discussion, one can easily observe that the more + routers and adjacencies in a Link State IGP routing area, the more + CPU burden there are for each router to bear. When a network is + unstable, the load will be amplified. + + A link-state protocol typically uses Dijkstra's Shortest Path First + (SPF) algorithm for route calculation. The Dijkstra algorithm scales + to the order of O(N^2), where N is the number of nodes. The algorithm + could be improved to the order of O(l*logN) where l is the number of + links in the network and N is the number of destinations or routers + [6]. + + Consequently, link state routing protocols do not scale to a network + topology with many routers and excessive adjacencies in an area. When + the network topology is unstable, the computation, processing and + bandwidth costs are magnified, which causes excessive consumption of + router resources. When the instability prevents IS-IS or OSPF from + maintaining adjacencies, a network routing meltdown occurs. + + Node adjacencies are discovered and maintained through the exchange + of HELLO messages sent periodically from each node. When a node fails + to receive HELLO messages from its neighbor within a certain period + of time (40 seconds for OSPF and less for IS-IS), it considers the + neighbor down. When heavy flooding, re-calculation and other + activities happen that make router CPU a scarce resource, a router + may not be able to allocate CPU time to send or process HELLO + packets. Routers in the network then lose adjacency, which magnifies + the instability. As a result, an isolated instability can escalate to + a routing failure across the entire network. + + Link-state IGPs also do not scale well to carry a large number of + routes such as the 70,000 routes known to the Internet today. Since + external routes are included in the link-state-database and in LSA + + + +Yu Informational [Page 7] + +RFC 2791 Scalable Routing Design Principles July 2000 + + + (LSP for IS-IS) updates, the link bandwidth and router memory + consumption will be tremendous. Moreover, due to the large size of + LSA updates, it would aggravate router resource consumption in the + process of LSA flooding, especially under unstable network condition. + + To summarize, a scalable design should avoid inclusion of too many + routers in an IGP routing area, a large external routes carried by + IGP and, more important, excessive adjacencies in the area. + +5.2. BGP + + BGP is an inter-domain routing protocol allowing the exchange of + routing or reachability information between different Autonomous- + System networks. Functionally, BGP is composed 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 as follows: + + o CPU consumption in BGP session establishment, route selection, + routing information processing, and handling of routing updates + + o Router memory to install routes and multiple paths associated + with the routes. + + The major scaling issue associated with BGP lie in the full mesh I- + BGP connections. Since it does not scale for an IGP to carry + externally learned prefixes, as mentioned in the previous section, + I-BGP assumes this duty. In order to prevent routing loops, prefixes + learned via I-BGP are prohibited from being advertised to another I- + BGP speaker. As a result, a full mesh of I-BGP sessions among the + routers within an AS is required. In an AS with N routers, each + router will have to establish I-BGP sessions with N-1 routers, and + the system complexity is in the order of O(N^2). Therefore, BGP + scales poorly when the number of routers involved in 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 these + routes. + + The large number of I-BGP sessions and routes consumes tremendous + resources from each router, especially during BGP session + establishment and during periods of heavy route flapping. + + + + + + +Yu Informational [Page 8] + +RFC 2791 Scalable Routing Design Principles July 2000 + + + 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. + This is a great improvement from EGP, in which the whole routing + table is 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. As a result, + network instability initiated anywhere in a network triggers updates + all over the Internet. This effect is magnified when large amounts of + routes are visible to the Internet, putting a heavy load on 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 will change the way that 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 implication of using such mechanism 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 + stability of the network 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 moreover should achieve it in a scalable fashion. + + 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. + + + + + + + + + +Yu Informational [Page 9] + +RFC 2791 Scalable Routing Design Principles July 2000 + + + Following is a set of design principles for making a large network + routing system more scalable: + + o Building hierarchy + o Compartmentalization + o Making proper trade-offs + o Reducing route processing burdens + o Defining scalable routing policies and implementation + o Utilizing out-of-band routing assistance + +6.1. Building Hierarchy + + As discussed in Section 5.1, OSPF and IS-IS scale poorly when a + network has a large number of routers and in particular, a large + quantity of adjacencies. This has unfortunately been proven by + networks that deploy IP over ATM with full mesh adjacencies among the + routers. The full mesh overlay design combined with the inefficient + protocol implementation led to disastrous network outages. A lesson + learned from this is to avoid full mesh overlay topology in a large + network with a large, flat network routing structure. + + Building hierarchical routing structures in the network is the key to + achieving routing scalability in a large network. As discussed + earlier in this document, large networks are usually composed of many + routers with a complex topology, which results in a large number of + adjacencies. As also discussed earlier, currently available routing + protocols scale poorly for handling a large number of routers in a + routing domain or many adjacencies among the routers. Therefore, it + is sensible to build a routing hierarchy to reduce the number of + routers as well as the number of adjacencies in a routing domain. + + The current common practice is to build a two-tiered hierarchy in a + network with a center component (or transit core network) to which a + number of outskirt components (or access networks) attach. The + transit core network covers the entire geographical area the network + serves; each access network (aka regional network) covers one region. + There are usually no direct link connections among the regional + components. Traffic from one regional network to another traverses + the transit core. Customer networks connect only to access or + regional networks. There are a number of ways to build a routing + hierarchy in the above described hierarchical network topology. + + 1) Completely Separate Routing Domains + + This design treats the transit core network and each regional + network as completely independent ASs with respect to routing, and + each AS runs an independent IGP. Each regional network E-BGP with + the transit core for exchanging routing knowledge. Full I-BGP + + + +Yu Informational [Page 10] + +RFC 2791 Scalable Routing Design Principles July 2000 + + + connections need to be established only within each component + network. With this design, the maximum number of routers in an IGP + domain is the total number of routers in each component. As a + result, the IGP processing load is reduced, and the number of + routers in an I-BGP mesh in the network routing system is + decreased dramatically. + + Another advantage of this design is that it compartmentalizes the + routing system so that instability in one such component has less + impact on the entire system. See the discussion in section 6.2. + + The main disadvantage of this scheme is that it inserts one extra + AS in the routing path when routes are advertised to the Internet + via BGP. This extra AS in the path may cause route selection + difficulties for other providers. + + 2) One Domain with IGP and BGP Hierarchy + + This method includes the transit core and each regional network + into one AS domain. The routing hierarchy is realized by utilizing + multi-level IS-IS or OSPF areas and either BGP Confederation or + I-BGP Reflector or a combination of the two. + + This mechanism avoids the introduction of an extra AS in the + routing path, which is an advantage over the method described in + Point 1). However, multi-area hierarchical IGP is rarely used + now-a-days in large networks since most of them are using IS-IS + for internal routing, which does not have sufficient multi-level + support. Although IS-IS supports multi-area routing, it imposes a + strict hierarchy between backbone and sub-areas and allows only + the advertisement of a default route from the backbone area to the + sub-areas instead of specific prefixes. This restriction may be + suitable for a network with a simple sub-area topology. A sub-area + in a large network, typically a regional or access network, itself + has a complicated topology. Receiving highly abstract routing + information, such as a default route, would affect the sub-area's + ability to make route selections required for traffic engineering. + It would also limit the information passed to external ASs, for + example, IGP-derived BGP Multi-Exit-Discriminator (MED) + information. + + Efforts are being made to modify the IS-IS protocol to allow the + distribution of specific route from backbone area to sub-areas. A + mechanism facilitates such distribution is specified in [15]. When + implementation of such mechanism become available, implementing + multi-level IGP will be an attractive option for building routing + hierarchy within a large network. + + + + +Yu Informational [Page 11] + +RFC 2791 Scalable Routing Design Principles July 2000 + + + 3) One IGP Area with BGP Hierarchy + + In lieu of multi-area IS-IS, the routing hierarchy could be + achieved by defining one IGP domain for the entire network while + employing a BGP hierarchy. Fortunately, the hierarchical topology + of the network in this case helps reduce adjacencies in the + routing domain (recall there are no connections among the second- + level network components). In addition, improvements could be made + to further reduce the adjacency by carefully arranging the + adjacencies to keep them at a minimum but still achieve good + redundancy. However, this is less than ideal since the number of + routers remains unchanged, which increases the load on the SPF + calculation. Moreover, instability within any regional network + would still affect the entire network (that is, there would be no + fault isolation). + + Even with one IGP domain, it is possible to build BGP hierarchy to + make I-BGP more scalable in the network. BGP Reflectors and BGP + Confederations are existing mechanisms to address the scaling + problem of full-mesh I-BGP. + + Further, a BGP reflector provides the ability to build more than + two levels of hierarchy, as long as the interactions among the + different levels of the hierarchy are carefully arranged to avoid + the possibility of creating routing loops. + + 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, such as a regional + network, grows too big for routing protocols to handle, either + another layer of hierarchy needs to be introduced or the sub-domain + needs to be split into multiple second-tiered sub-domains. + + Keeping two levels of hierarchy and adding more sub-domains appears + to be more manageable than adding another level to the hierarchy. + However, one concern is to avoid adding more nodes to the top-level + or transit core network to make it less scalable. Connecting the + split sub-areas to the same core router would eliminate the need to + add more nodes in the core area than is recommended. + + Having more than two levels of hierarchy would exceed the capability + of IGPs as they are defined today. In OSPF, for example, all the + areas must be connected via the backbone area, which eliminates the + possibility of having more than two levels of hierarchy. IS-IS has + the same limitation. Therefore, the protocols need to be redefined + should more than two hierarchical layers in IGP be desirable. + + + +Yu Informational [Page 12] + +RFC 2791 Scalable Routing Design Principles July 2000 + + + The complexity of protocols and management will increase with the + number of levels added to the hierarchy. According to [6], most of + the OSPF protocol bugs found over the years are related to routing + area support. Because the interaction among the multiple levels + increases management and debugging complexity, it is desirable to + keep the levels within a hierarchy to a minimum. + +6.2. Compartmentalization + + A scalable routing design of a large network should be able to + localize problems or failures, thus preventing them from spreading to + the entire network, consuming resources of network routers, and + causing network wide instability. This is compartmentalization. + Network compartmentalization makes fault isolation possible which + contributes the stability of a large network. + + To achieve compartmentalization in routing design for a large + network, one needs to avoid a design where the whole large network is + one flat routing system or routing domain. This is the reason for the + architecture of dividing interior and exterior routing in the global + routing system. Within a network, it is best to divide the network + into multiple routing domains or multiple routing areas. For example, + in OSPF, only summary route SLAs, rather than individual area routes, + are flooded beyond the area. When an area border router aggregates + the routes in its sub-area, instability of any route included in the + summary route would not cause flooding of SLAs to other areas. As a + result, router resources in other areas would not be consumed for + handling flooding and the SPF recalculation. In other words, + instability within each individual area would be prevented from + spreading to the entire routing domain. + + Since building a routing hierarchy essentially divides a big routing + area into smaller areas or domains, it help achieve the goal of + compartmentalization. + +6.3. Making Proper Trade-offs + + When designing routing for a large network, the overall goal should + be set with considerations of routing scalability and stability. The + trade-offs between conflicting goals should be taken into account. + Examples of such trade-offs are redundancy vs. scalability and + convergence vs. stability. + + Redundancy introduces complexity and increased adjacencies to the + network topology. Redundancy also imposes the need for as many + alternative paths as possible for each route, which increases route + + + + + +Yu Informational [Page 13] + +RFC 2791 Scalable Routing Design Principles July 2000 + + + processing and storage burdens. Because of these problems, it may be + necessary to sacrifice absolute redundancy in favor of a reasonable + level that scales better for the routing system. + + Fast convergence requires that changes in network topology be + propagated to the network as quickly as possible. Such action + increases routing updates and, consequently, the route processing + burden. The burden is aggravated when a network carries full Internet + routing information, as large networks usually do, and topology + changes happen frequently. Route dampening may be necessary to + achieve stability at the expense of absolute fast convergence. + +6.4. Reduce Burdens of Routing Information Processing + + The tasks of reducing routing processing burdens includes: i) + strategically place the routing intelligence within the network, ii) + avoid carrying unnecessary routing information and iii) reduce the + impact of route flapping. + +6.4.1. Routing Intelligence Placement + + A router that executes routing policies, performs route filtering and + dampening is said to posses routing intelligence. Routing + intelligence is needed for a network i) to enforce the business + agreement between network entities in the form of routing policies; + ii) to protect the integrity of the routing information within the + network and sometimes iii) to shield a network from instability + happening elsewhere in the Internet. + + The more routing intelligence a router has, the more resources of the + router are needed to perform those tasks. It is logical, then, to + place as little routing intelligence as possible on routers that + already are heavily burdened with other tasks. + + Usually, traffic is heavily concentrated in the core of the network. + Because traffic aggregates from the edge of the network toward the + core, traffic is less concentrated near the edge of the network. + Consequently, to build a scalable routing system, it is wise to place + routing intelligence at the edge of the network, especially in the + networks deployed with routers that do not sufficiently decouple + forwarding and routing. In addition, pushing routing intelligency as + close to the edge of the network as possible also serves the purpose + of distributing computational and configuration burdens across all + routers. + + It is also desirable to move the heavy burden of processing routes to + out-of-band processors, freeing more resources in network routers for + packet forwarding and handling. + + + +Yu Informational [Page 14] + +RFC 2791 Scalable Routing Design Principles July 2000 + + +6.4.2. Reduce Routes and Routing Information + + As discussed in Section 4.1, a large number of routes in the system + is one of the major culprits in route scaling problems. Therefore, it + is best to reduce the number of routes in the system without losing + necessary routing information. + +6.4.2.1. CIDR and Route Aggregation + + CIDR as specified in [10] provides a mechanism to aggregate routes + for efficiently utilizing IP address space as well as reducing the + number of routes in the global routing table. CIDR offers a way to + summarize routing information, which is one of the keys for routing + scalability in today's Internet. + + Route aggregation would not only help global Internet scalability but + would also contribute to scalability in local networks. The overall + goal is to keep the routes in the backbone to a minimum. + + To achieve better aggregation within the network; that is, to reduce + the number of routes in the network, a block of consecutive IP + addresses should be allocated to each access or regional network so + that when a regional network announces its routes to the transit core + network, they can be aggregated. This way, the core and other + regional networks would not need to know the specific prefixes of any + particular access network. Although assignment of customer addresses + from a provider block would have to be planned to support + aggregation, the effort would be worthwhile. + +6.4.2.2. Utilize Default Routing When Possible + + The use of a default route achieves ultimate route summarization, + which reduces routing information to minimum. Route summarization + also masks the instability associated with an individual route, for + example, in the case of route flapping. It's beneficial for a network + to utilize default routing when appropriate. For example, if a + second-tiered regional network is a stub and there is no connected + customer requesting full Internet routing information, the regional + network can simply point default to its connected core network. + However, over-summarization of routing information has the danger of + losing routing granularity and as a result, management of network + such as traffic engineering would be adversely affected. Therefore, + caution needs to be exercised when using default routing. + + + + + + + + +Yu Informational [Page 15] + +RFC 2791 Scalable Routing Design Principles July 2000 + + +6.4.2.3. Reduce Alternative Paths + + Due to the requirement of reliability, the connectivity in the + Internet is rich, resulting in many paths toward a particular + destination. In other words, there are many alternate paths in the + BGP routing table towards the same destination, which consumes router + memory and adds to the routing processing burden. + + To make routing scale, it is desirable to reduce alternate paths + while preserving reasonable redundancy. For example, on a given + border router (such as a NAP router), one primary path plus an + alternate path should provide reasonable redundancy. In this case, a + third or a fourth alternate route could be discarded for the sake of + scaling. This is a trade-off decision every network administrator + needs to make based on the particular needs of her network. + +6.4.3. Use Static Route at Edges + + As mentioned earlier, one of the scaling issues in large networks is + that a single router may fan out to hundreds of customer routers. As + a result, resource consumption will be very intensive if all the + customer routers communicate via BGP with the edge router. Is it + necessary for the edge router to BGP with all of its attached + customer routers? + + At first glance, it seems necessary for a customer network in a + different Autonomous System(AS) to exchange routing information with + the provider network via BGP. However, this is not necessarily the + case. When a customer network is single-homed (that is, if the sole + network connection for a customer is via its provider network), BGP + is not necessary and static routing can work. Since the customer + network is single-homed, static routing will not have any negative + impact on services. The advantages are that the customer aggregation + router will have fewer E-BGP sessions to handle, and no route + flapping can result from the statically configured customer routes. + + Configuration of the customer's static routes on the provider's + aggregation router may add management overhead, especially if a + customer advertises a large number of routes. On the other hand, the + set of routes a customer announces to the provider usually changes + infrequently; thus it requires low maintenance once it is configured. + +6.4.4. Minimize the Impact of Route Flapping + + As discussed earlier, route flapping is largely caused by link + instability and/or BGP session instability that results in excessive + routing updates across the Internet. Route flapping can originate + anywhere in the global Internet and affect every network in the + + + +Yu Informational [Page 16] + +RFC 2791 Scalable Routing Design Principles July 2000 + + + Internet routing mesh (BGP mesh). Given that there are over 70,000 + routes known to the Internet and there is little isolation for route + flapping, handling route flapping could be overwhelming to routers in + any network. + + One way to reduce the effect of route flapping is to turn on route + dampening as specified in [10]. Essentially, dampening suppresses an + unstable route until it becomes stable. The current practice is for + each ISP to enable route dampening on its border routers. This way, + excessive routing updates can be stopped at the border. + + An ideal model is to suppress the announcement of a flapping route + right at the source. One way to implement this is to have a router + recognize instability associated with its directly connected links + and suppress the announcement of the route. So far, there is no such + implementation. This approach should be explored. + + Route aggregation often masks route flapping since components of an + aggregated route (more specific routes) would not cause the + aggregated route to flap. Therefore using CIDR can also help to + alleviate route flapping. + +6.5. Scalable Routing Policy and Scalable Implementation + + Routing policy involves routing decisions about acceptance and + advertisement of certain routes to or from other networks and about + routing preference when more than one route becomes available. + Routing policy enforces business agreements between network entities + and is largely governed by non-technical criteria. In essence, + routing policy involves defining criteria for route filtering and + route selection. + + One aspect of route filtering has to do with traffic control between + routing domains or between different provider networks. Making policy + based on individual prefixes should be avoided in this case because, + with the large number of prefixes in the Internet, it does not scale. + Making policy based on ASs that administratively represent a set of + prefixes scales better. + + Another purpose of route filtering is to protect the integrity of + routing information by preventing the acceptance of falsely + advertised routing information that would lead traffic to 'black + holes'. In this case, only prefix-based filtering will sufficiently + achieve the goal. Prefix-based filtering needs to occur at the + borders between a network and its direct customers or peer networks. + The filtering is harder to manage at the boundary of the peer + networks since a peer network usually advertises a large amount of + prefixes. As mentioned earlier, there are about 70,000 routes known + + + +Yu Informational [Page 17] + +RFC 2791 Scalable Routing Design Principles July 2000 + + + to the Internet. This means 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. The + sheer amount of the prefixes to be filtered imposes challenges for + router configuration memory and configuration management. To make it + scale, one would need to rely on the help from 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 determines which path should be used to send + traffic toward a certain destination. This is important, for example, + when a network has two connections to another network and learns + routes from both connections. The decision involves which path to + select to send traffic to the customers behind the other network. The + choices are typically: + + o Directing traffic to the closest interconnection point for + traffic to exit the network. This policy is also known as Hot- + Potato-Routing + + o 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 + + o Always preferring routes advertised by directly connected + customers + + o Allowing other network or customer to determine the path + + When a policy is defined, its implications for scalable + implementation need to be considered. For example, if the policy + allows customers to determine which paths traffic follows, customers, + not the provider, should be required to set routing parameters to + make the 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 avoids putting such routing management + burdens solely on the provider. Distributing the routing management + burden makes the policy implementation more scalable. + + Another scaling measure is to avoid making complex policy. When + routing policy is complex, management, such as configuration of the + router and debugging, would be a problem. The ultimate goal is to + make the network manageable. + + The following basic principles would help scale the routing policy + management. + + + +Yu Informational [Page 18] + +RFC 2791 Scalable Routing Design Principles July 2000 + + + o Making policies as simple as possible but meet the requirements + + o Automating as much as possible to avoid error-prone manual work + + o Avoiding policy based on individual prefixes as much as possible + with the exception of prefix-based route filtering for + protecting routing integrity + + o Avoiding making exceptions + + o Using out-of-band routing policy processing where possible + +6.6. Out-of-Band Process + + A typical router assumes both routing and forwarding functions. + However, conceptually, routing and forwarding are two separate + processes. A router's ultimate task is to forward packets based on + its forwarding table, which is derived from routing information. One + of the main causes of route scaling problems is that routers run out + of processing power because routing requires too much processing. + While a router has to forward packets, it does not necessarily have + to exchange and process routing information or execute routing + policy; these tasks can be performed elsewhere. Thus the question + should be: Would it be possible to remove the routing process from a + router to reduce its burden? Moving the routing process from the + routers to other systems is referred to as out-of-band route + processing. + + Out-of-band route processes would, in short, perform 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. It also suggests other possible solutions. + +7. Conclusion and Discussion + + How routing scales has a direct impact on network stability and + performance. With the fast growth of the Internet and consequent + expansion of providers' networks, routing scaling become increasingly + + + + + +Yu Informational [Page 19] + +RFC 2791 Scalable Routing Design Principles July 2000 + + + an important issue to address. This document identifies the major + factors that affect route scalability and establishes basic + principles for designing scalable routing in large networks. + + The major routing scaling issues we are facing today are excessive + router resource consumption due to routing processing burdens causing + routing convergency difficulties thus introducing network + instability; and routing complexity resulting in difficulties of + management and trouble shooting causing 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. + + The use of out-of-band resources to assist routing processing is a + concept only been used in the Internet Exchange Points (IXPs). + However, it could potentially be used to advantage within a network + to help addressing routing scaling issues. This is a topic worthy of + further exploration. + + Routing protocols and/or their implementations can still be improved + or enhanced for better handling of the scaling issues. For example, + the IS-IS multiple level mechanism is needed in order to scale the + IGP in large network. 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 and thus is unlikely + to have a direct impact on security. + + However, 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 + it would help prevent such outages from spreading to the entire + network. + + + + + + +Yu Informational [Page 20] + +RFC 2791 Scalable Routing Design Principles July 2000 + + + Although the mechanisms described in this document do not enhance or + weaken the security aspect of routing protocols, it is worth + indicating here that security enhancement of routing protocols or + routing mechanisms may impact routing scalability. Therefore, when + applying security enhancement in routing, one has to be aware of the + implications on scalability. + + For example, TCP MD5 signature option is proposed to be a mechanism + to protect BGP sessions from being spoofed [13]. It is done on a + per-session basis and the overhead of MD-5 extensions are minimal + thus has no direct impact on scalability. There have been concerns + about doing per-prefix AS path verification as 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 which + gives very strong security but 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 like to thank Susan R. Harris for the much + needed polishing of English language in the document. + + The author was made aware after the publication of this document that + there is a relevant and independent presentation made by Enke Chen on + the subject. The presentation is thus referenced in [14]. + +10. References + + [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 + + + + +Yu Informational [Page 21] + +RFC 2791 Scalable Routing Design Principles July 2000 + + + [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 + + + + + + + + + + + + +Yu Informational [Page 22] + +RFC 2791 Scalable Routing Design Principles July 2000 + + +Appendix A. Out-of-Band Routing Processes + + The use of a Route Server(RS) at NAPs is an example of achieving + routing scalability through an out-of-band routing process. A NAP is + a public inter-connection point where ISP networks exchange traffic. + ISP routers at a NAP establish BGP peer sessions with each other. The + result is full mesh E-BGP peering with a complexity of O(N^2) system + wide. When the RS is in place, each router peers only with the RS + (and its backup) to obtain necessary routing information (or more + precisely, the necessary forwarding information). In addition, the RS + also filters routes and executes policy for each provider's router, + which further reduces the burden on all routers involved. + + The concept of the Route Server can also be used to help address + routing scalability in a large network. + + 1) RS Assisted Peering between Customer Aggregation Router and + Customer Routers + + Currently, in a typical large provider network, it's not unusual that + a customer aggregation router connects up to hundreds of customer + routers. That means the router has to handle hundreds of E-BGP + sessions and filter a large number of prefixes. These tasks impose a + heavy burden on the aggregation router. Reducing the number of + customer routers per aggregation router is not an optimal option, + since this would introduce more routers in the routing system of the + whole network, which is neither scalable for backbone routing, nor + cost efficient. Using an RS between customers and the providers' + customer aggregation router become an attractive option to reduce the + burden on the router. + + Figure 1 shows one way of incorporating an RS router between a + provider's customer aggregation router and customer routers. + + --------------------------- LAN Media in a POP + | | + ----- ----- + |CR | |RS | + ----- ----- + / | \ + / | \ + C1 C2..Cn + + + + Figure 1: RS serving customer aggregation router connecting + customer routers + + + + +Yu Informational [Page 23] + +RFC 2791 Scalable Routing Design Principles July 2000 + + + In a scenario without an RS, the customer aggregation router(CR) has + to peer with customer routers C1, C2 ... Cn (where n could be in the + hundreds). When an RS router is introduced, CR, C1, C2 ... Cn peer + with the RS router instead, and the RS passes the processed routing + information (or forwarding information) to all of them, according to + policy and filters. + + The advantages are obvious: + + o The customer aggregation router peers only with the RS router + instead of with hundreds of customer routers. + + o The customer aggregation router does not need to filter prefixes + or process routing policies, which frees resources for packet + forwarding and handling. + + One general concern with the use of an RS router is the possibility + of a mismatch of routing connectivity and the physical connectivity. + For example, if the link between the CR and C1 is down and if the RS + router is not aware of the outage, it will continue to pass routes + from C1 to the CR, and the traffic following these routes will be + black holed. However, this is not a problem in the specific + application described here. This is because the RS router has to go + through the CR to peer with C1, C2 ... Cn. When the link is down, C1 + is inaccessible from the RS router, and no routing information can be + exchanged between the two. Consequently, the RS will announce no + routes related to C1. + + Another concern is the creation of single point of failure. If the RS + router is down, no routing information can be exchanged between the + customer aggregation router and C1, C2 ... Cn, and no traffic will + flow between them. This problem could be addressed by adding a second + RS router as a backup. + + In this scenario, since RS peers with C1 ... Cn via CR, it requires + that when the RS router passes routing information to C1...Cn, it + designates the IP address of the CR 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. + + 2) Private RS Router at InterExchange Point + + A large provider network often has many BGP peers at the + Interexchange Point, NAP or private interconnection. This means a + border router has to handle many E-BGP sessions. Since an + + + + +Yu Informational [Page 24] + +RFC 2791 Scalable Routing Design Principles July 2000 + + + Interconnect points is usually the administrative boundary between + ISPs, policy and route filtering are very demanding. This imposes a + scaling problem on the border router. + + Deploying many routers to distribute the load among them is an + expensive solution: extra hardware and extra ports cost money. + Shifting the routing burden to an RS router is a promising + alternative solution. In the case of using RS for multiple peers at a + private interexchange point, the scenario is similar to RS used + between customer aggregation router and customer routers as described + in 1) above. In the case of such peering at a NAP, the private RS + could be placed either on the same NAP media or a private media + between the ISP's NAP router and the RS. + + 3) RS Routers at Each POP in a Large Network + + Even in a network with a hierarchical routing structure, a sub-area + may become too large, and I-BGP full meshing may impose a scaling + problem. One way to address this would be to split the sub-area or + add yet another tier of I-BGP reflector structure. Another possible + solution would be to use an RS router as an I-BGP Server. Depending + on the topology of a POP, this solution may or may not be suitable. + The use of RS routers at network POPs need to be investigated + further. + + + + + + + + + + + + + + + + + + + + + + + + + + + +Yu Informational [Page 25] + +RFC 2791 Scalable Routing Design Principles July 2000 + + +Full Copyright Statement + + Copyright (C) The Internet Society (2000). All Rights Reserved. + + This document and translations of it may be copied and furnished to + others, and derivative works that comment on or otherwise explain it + or assist in its implementation may be prepared, copied, published + and distributed, in whole or in part, without restriction of any + kind, provided that the above copyright notice and this paragraph are + included on all such copies and derivative works. However, this + document itself may not be modified in any way, such as by removing + the copyright notice or references to the Internet Society or other + Internet organizations, except as needed for the purpose of + developing Internet standards in which case the procedures for + copyrights defined in the Internet Standards process must be + followed, or as required to translate it into languages other than + English. + + The limited permissions granted above are perpetual and will not be + revoked by the Internet Society or its successors or assigns. + + This document and the information contained herein is provided on an + "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING + TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING + BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION + HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF + MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. + +Acknowledgement + + Funding for the RFC Editor function is currently provided by the + Internet Society. + + + + + + + + + + + + + + + + + + + +Yu Informational [Page 26] + -- cgit v1.2.3