RFC 1322

A Unified Approach to Inter-Domain Routing

📅 published May 1992, from ietf

RFC 1322: A Unified Approach to Inter-Domain Routing 💖

Part 1 of 9 🎀

Okay bestie, this is RFC 1322, and it's titled A Unified Approach to Inter-Domain Routing 🦋. It was written in May 1992 by D. Estrin (USC), Y. Rekhter (IBM), and S. Hotz (USC). Ngl, that's a research dream team 😭✨. It's from the Network Working Group, and it's an informational doc, so it's giving "here's a perspective," not "here's a standard." The original title block doesn't list any Obsoletes or Updates line, so this one doesn't obsolete or update anything else 🙈.

Status of this Memo 🧚

This memo provides information for the Internet community. It does not specify an Internet standard. Distribution of this memo is unlimited 💅.

Abstract 🌸

This memo is an informational RFC that outlines one potential approach for inter-domain routing in future global internets. The focus is on scalability to very large networks and functionality, as well as scalability, to support routing in an environment of heterogeneous services, requirements, and route selection criteria 🌈.

Note: The work of D. Estrin and S. Hotz was supported by the National Science Foundation under contract number NCR-9011279, with matching funds from GTE Laboratories. The work of Y. Rekhter was supported by the Defense Advanced Research Projects Agency, under contract DABT63-91-C-0019. Views and conclusions expressed in this paper are not necessarily those of the Defense Advanced Research Projects Agency and National Science Foundation 🙏.

1.0 Motivation ✨

Okay so the global internet can be modeled as a collection of hosts connected through transmission and switching facilities 🌐. Control over those hosts and facilities isn't uniform. It's spread across multiple administrative authorities 👑. Resources under one administration form a domain. To support each domain's autonomy and heterogeneity, routing has two distinct components: intra-domain (interior) routing and inter-domain (exterior) routing 🧩.

Intra-domain routing supports data communication between hosts when the data traverses facilities within a single domain. Inter-domain routing supports data communication between hosts when the data traverses facilities spanning multiple domains. The entities that forward packets across domain boundaries are called border routers (BRs). The entities responsible for exchanging inter-domain routing information are called route servers (RSs). RSs and BRs may be colocated 💜.

As the global internet grows, both in size and in the diversity of routing requirements, inter-domain routing that can accommodate both of these factors becomes more and more crucial 📈. The number and diversity of routing requirements is increasing due to: (a) transit restrictions imposed by source, destination, and transit networks, (b) different types of services offered and required, and (c) the presence of multiple carriers with different charging schemes. The combinatorial explosion of mixing and matching these different criteria weighs heavily on the mechanisms provided by conventional hop-by-hop routing architectures ([ISIS10589, OSPF, Hedrick88, EGP]) 😵‍💫.

Current work on inter-domain routing within the Internet community has diverged in two directions. One is best represented by the Border Gateway Protocol (BGP)/Inter-Domain Routeing Protocol (IDRP) architectures ([BGP91, Honig90, IDRP91]), and another is best represented by the Inter-Domain Policy Routing (IDPR) architecture ([IDPR90, Clark90]). In this paper we suggest that the two architectures are quite complementary and should not be considered mutually exclusive 🫶.

We expect that over the next 5 to 10 years, the types of services available will keep evolving, and specialized facilities will be employed to provide new services 🚀. While the number and variety of routes provided by hop-by-hop routing architectures with type of service (TOS) support (i.e., multiple, tagged routes) may be sufficient for a large percentage of traffic, it is important that mechanisms be in place to support efficient routing of specialized traffic types via special routes. Examples of special routes are: (1) a route that travels through one or more transit domains that discriminate according to the source domain, and (2) a route that travels through transit domains that support a service that is not widely or regularly used. We refer to all other routes as generic 🍓.

Our desire to support special routes efficiently led us to investigate the dynamic installation of routes ([Breslau-Estrin91, Clark90, IDPR90]). In a previous paper ([Breslau-Estrin91]), we evaluated the algorithmic design choices for inter-domain policy routing, with specific attention to accommodating source-specific and other "special" routes. The conclusion was that special routes are best supported with source-routing and extended link-state algorithms. We refer to this approach as source-demand routing 🔍

[Footnote: The Inter-Domain Policy Routing (IDPR) architecture uses these techniques.]

However, a source-demand routing architecture, used as the only means of inter-domain routing, has scaling problems, because it does not lend itself to general hierarchical clustering and aggregation of routing and forwarding information 😬. For example, even if a particular route from an intermediate transit domain X to a destination domain Y is shared by 1,000 source-domains, IDPR requires that state for each of the 1,000 routes be set up and maintained in the transit border routers between X and Y 🥲.

In contrast, an alternative approach to inter-domain routing, based on hop-by-hop routing and a distributed route-computation algorithm (described later), provides extensive support for aggregation and abstraction of reachability, topology, and forwarding information 🧠. The Border Gateway Protocol (BGP) and Inter-Domain Routeing Protocol (IDRP) use these techniques ([BGP91, IDRP91]). While the BGP/IDRP architecture is capable of accommodating very large numbers of datagram networks, it does not provide support for specialized routing requirements as flexibly and efficiently as IDPR-style routing 💅.

1.1 Overview of the Unified Architecture 🦋

We want to support special routes, and we want to exploit aggregation when a special route is not needed 🙌. So our scalable inter-domain routing architecture consists of two major components: source-demand routing (SDR) and node routing (NR).

The NR component computes and installs routes that are shared by a significant number of sources. These generic routes are commonly used and warrant wide propagation, so aggregation of routing information is critical 📦. The SDR component computes and installs specialized routes that are not shared by enough sources to justify computation by NR [Footnote: Routes that are only needed sporadically (i.e., the demand for them is not continuous or otherwise predictable) are also candidates for SDR.]. The potentially large number of different specialized routes, combined with their sparse utilization, makes them too costly to support with the NR mechanism 💸.

A useful analogy here is the manufacturing of consumer products 🛍️. When predictable patterns of demand exist, firms produce objects and sell them as "off the shelf" consumer goods. In our architecture, NR provides off-the-shelf routes. If demand is not predictable, then firms accept special orders and produce what is demanded at the time it is needed. In addition, if a part is so specialized that only a single or small number of consumers need it, the consumer may repeatedly special order the part, even if it is needed in a predictable manner, because the consumer does not represent a big enough market for the producer to bother managing the item as part of its regular production. SDR provides such special order, on-demand routes 🧾.

By combining NR and SDR routing, we propose to support inter-domain routing in internets of practically unlimited size, while at the same time providing efficient support for specialized routing requirements 🌟.

The development of this architecture does assume that routing requirements will be diverse and that special routes will be needed. On the other hand, the architecture does not depend on assumptions about the particular types of routes demanded or on the distribution of that demand. Routing will adapt naturally over time to changing traffic patterns and new services by shifting computation and installation of particular types of routes between the two components of the hybrid architecture [Footnote: Before continuing with our explanation of this architecture, we wish to state up front that supporting highly specialized routes for all source-destination pairs in an internet, or even anything close to that number, is not feasible in any routing architecture that we can foresee. In other words, we do not believe that any foreseeable routing architecture can support unconstrained proliferation of user requirements and network services. At the same time, this is not necessarily a problem. The capabilities of the architecture may in fact exceed the requirements of the users. Moreover, some of the requirements that we regard as infeasible from the inter-domain routing point of view may be supported by means completely outside of routing. Nevertheless, the caveat is stated here to preempt unrealistic expectations.] 🫠.

While the packet forwarding functions of the NR and SDR components have little or no coupling with each other, the connectivity information exchange mechanism of the SDR component relies on services provided by the NR component 🔗.

1.2 Outline 🗺️

The remainder of this report is organized as follows. Section 2 outlines the requirements and priorities that guide the design of the NR and SDR components. Sections 3 and 4 describe the NR and SDR design choices, respectively, in light of these requirements. Section 5 describes protocol support for the unified architecture and briefly discusses transition issues. We conclude with a brief summary ✨.

2.0 Architectural Requirements and Priorities 👑

In order to justify our design choices for a scalable inter-domain routing architecture, we must articulate our evaluation criteria and priorities. This section defines complexity, abstraction, policy, and type of service requirements 📋.

2.1 Complexity 🧮

Inter-domain routing complexity must be evaluated on the basis of the following performance metrics: (1) storage overhead, (2) computational overhead, and (3) message overhead. This evaluation is essential to determining the scalability of any architecture 💖.

2.1.1 Storage Overhead ✨

okay so the storage overhead of any entity that takes part in inter-domain routing comes from two places 💅 the first is the Routing Information Base (RIB), which holds the routing info entities swap through the inter-domain routing protocol. the RIB is the input to route computation 🧠 the second is the Forwarding Information Base (FIB), which holds the info entities actually use to forward inter-domain traffic. the FIB is the output of route computation 🎀

for an acceptable amount of storage overhead, the info in both FIBs and RIBs SHOULD grow way slower than linearly (like close to logarithmically) as the total number of domains in an internet grows 📈 for the RIB, the architecture MUST provide mechanisms for either aggregating and abstracting routing and forwarding info, or retrieving just a subset of it on demand 🦋 for the FIB, the architecture MUST provide mechanisms for either aggregating the forwarding info (for the NR computed routes), or dynamically installing and tearing down that info (for the SDR computed routes) ✨

and bestie, storage overhead isn't just a standalone vibe, it totally affects computational and bandwidth complexity too 😭 unless computational complexity is fixed (and doesn't depend on the total number of domains), storage overhead directly hits computational complexity, because routing info is the input to route computation. and unless the architecture uses incremental updates, where only the changes to routing info get propagated, storage overhead directly hits bandwidth overhead too, since swapping routing info makes up most of the bandwidth overhead 🫶

2.1.2 Computational Overhead ✨

the NR component is going to rely mostly on precomputing routes 🧮 if inter-domain routing is ubiquitous, the precomputed routes include every reachable destination. even if policy constraints make fully ubiquitous routing impossible, the precomputed routes are still likely to cover a very large percentage of all reachable destinations 💖 so the complexity of this computation MUST be as small as possible. it's highly desirable that the architecture would employ some form of partial computation, where changes in topology need less than a complete recomputation. and even if complete recomputation is necessary, its complexity SHOULD be less than linear with the total number of domains.

the SDR component is going to use on-demand computation and caching, so its complexity can be somewhat higher 🔥 another reason SDR gets relaxed complexity requirements is that SDR is expected to compute routes to a smaller number of destinations than NR does (although SDR route computation may be invoked more frequently) 💅

under no circumstances is computational complexity allowed to become exponential, for either the NR or the SDR component 🙅‍♀️💀

2.1.3 Bandwidth Overhead ✨

the bandwidth used by routing info distribution SHOULD be limited 🌈 however, data compression and the increasing speed of network links make this less important than route computation and storage overhead. bandwidth overhead may be further contained by using incremental (rather than complete) exchange of routing info.

storage and bandwidth overhead may be interrelated 🧶 but if incremental updates are used, bandwidth overhead is negligible in the steady state (no topology changes) and is independent of storage overhead. so incremental updates basically tie bandwidth overhead to the dynamics of the internet 🦋 which means that improving the stability of physical links, combined with techniques to dampen the effect of topological instabilities, will make bandwidth overhead even less important 👑

2.2 Aggregation ✨

aggregation and abstraction of routing and forwarding info is a seriously powerful way to meet storage, computational, and bandwidth constraints 💪 the ability to aggregate, and then abstract, routing and forwarding info is essential to scaling the architecture [Footnote: While we can not prove that there are no other ways to achieve scaling, we are not aware of any mechanism other than clustering that allows information aggregation/abstraction. Therefore, the rest of the paper assumes that clustering is used for information aggregation/abstraction.]. this is especially true for the NR component, since the NR component MUST be capable of providing routes to all or almost all reachable destinations 🗺️

at the same time, preserving each domain's independence and autonomy is one of the crucial requirements of inter-domain routing, so the architecture MUST strive for the maximum flexibility of its aggregation scheme. that means imposing as few preconditions, and as little global coordination, as possible on the participating domains 🫶

the Routing Information Base (RIB) carries three types of info: (1) topology (i.e., the interconnections between domains or groups of domains), (2) network layer reachability, and (3) transit constraint. aggregation of routing info SHOULD provide a reduction of all three components 📉 aggregation of forwarding info will follow from reachability info aggregation.

clustering (by forming routing domain confederations) does three aggregation jobs: (1) it hides parts of the actual physical topology, so topological info gets abstracted, (2) it combines a set of reachable destination entities into a single entity, which cuts storage overhead, and (3) it lets you express transit constraints in terms of clusters rather than individual domains 🧁

as argued in [Breslau-Estrin91], the architecture MUST allow confederations to be formed and changed without extensive configuration and coordination. in particular, forming a confederation SHOULD NOT require global coordination (such as that required in ECMA ([ECMA89])). in addition, aggregation SHOULD NOT require explicit designation of the relative placement of each domain relative to another. i.e., domains or confederations of domains SHOULD NOT be required to agree on a partial ordering (i.e., who is above whom, etc.) 👑🙅‍♀️

the architecture SHOULD allow different domains to use different methods of aggregation and abstraction 🎀 for example, a research collaborator at IBM might route to USC as a domain-level entity, so they can take advantage of some special TOS connectivity to, or even through, USC. whereas someone at Digital Equipment Corporation might see info at the level of the California Educational Institutions Confederation, and only know that USC is a member. alternatively, USC might see part of the internal structure within the IBM Confederation (at the domain's level), whereas UCLA may route based on the confederation of IBM domains as a whole 🌸

support for confederations SHOULD be flexible. specifically, the architecture SHOULD allow confederations to overlap without being nested. that means a single domain, or a group of domains, may be part of more than one confederation 🦋 for example, USC may be part of the California Educational Institutions Confederation AND part of the US R&D Institutions Confederation, and one is not a subset of the other 🙌 another example: T.J. Watson Research Center might be part of NYSERNET Confederation and part of IBM-R&D-US Confederation. while the examples above are cases where the overlap is a single domain, there may be other cases where multiple domains overlap. consider the set of domains that form the IBM Confederation, and another set of domains that form the DEC Confederation. within IBM there is a domain IBM-Research, and similarly within DEC there is a domain DEC-Research. both of these domains could be involved in some collaborative effort, and thus have established direct links. the architecture SHOULD allow restricted use of these direct links, so that other domains within the IBM Confederation would not be able to use them to talk to other domains within the DEC Confederation 🔒 a similar example exists when a multinational corporation forms a confederation, and the individual branches within each country also belong to their respective country confederations. the corporation may need to protect itself from being used as an inter-country transit domain (due to internal, or international, policy). all of the examples above show overlapping confederations, and it's necessary to control the traffic traversing the overlapping resources 💖

while flexible aggregation SHOULD be accommodated in any inter-domain architecture, how far this feature gets exploited will have a direct effect on the scalability associated with aggregation 📊 and that exploitation depends on the way addresses are assigned. specifically, scaling associated with forwarding info depends heavily on the assumption that there will be a general correspondence between the hierarchy of address registration authorities and the way routing domains and routing domain confederations are organized (see Section 2.6) 🧚

2.3 Routing Policies ✨

routing policies that the architecture MUST support may be broadly classified into transit policies and route selection policies [Breslau-Estrin 91, Estrin89] 🗂️

restrictions imposed via transit policies may be based on a variety of factors 💅 the architecture SHOULD be able to support restrictions based on the source, destination, type of services (TOS), user class identification (UCI), charging, and path [Estrin89 , Little89]. the architecture MUST allow expression of transit policies on all routes, both NR and SDR. even if NR routes are widely used and have fewer source or destination restrictions, NR routes may have some transit qualifiers (e.g., TOS, charging, or user-class restriction). if the most widely-usable route to a destination has policy qualifiers, it SHOULD be advertiseable by NR, and the transit constraints SHOULD be explicit 🔥

route selection policies let each domain select a particular route among multiple routes to the same destination 👑 to keep maximum autonomy and independence between domains, the architecture MUST support heterogeneous route selection policies, where each domain can establish its own criteria for selecting routes. this argument was made earlier with respect to source route selection ([IDPR90, Clark90, Breslau-Estrin91]). in addition, each intermediate transit domain MUST have the flexibility to apply its own selection criteria to the routes its neighbors make available to it. this is really just a corollary to the above: if we allow route selection policy to be expressed for NR routes, we can not assume all domains will apply the same policy 🙈 the support for dissimilar route selection policies is one of the key factors that distinguish inter-domain routing from intra-domain routing ([ECMA89, Estrin89]). however, it is a non-goal of the architecture to support all possible route selection policies. for more on unsupported route selection policies, see Section 2.3.2 below 🌈

2.3.1 Routing Information Hiding 🙈

Okay so the architecture should not require every domain inside an internet to reveal its connectivity and transit constraints to every other domain 🙅‍♀️. Domains should still be able to enforce their transit policies 💅, while keeping the advertising of their policy and connectivity info as limited as possible. That advertising should be driven by a "need to know" vibe 🔒. Like, why would you tell a domain about a transit policy it can't even use? Advertising a transit policy to domains that can not use it just makes the pile of routing info that has to be stored, processed, and propagated way bigger 📦😭. And honestly, it may be totally impractical for a router to keep the full inter-domain topology and policy info. Even worse, it may not even be permitted to get that info in the first place 💀.

2.3.2 Policies Not Supported 🚫

In this paper and the ones before it, we've been arguing that a global inter-domain routing architecture should support a wide range of policies 🌍. But here's the plot twist: this section lists several types of policy that we explicitly do not propose to support 🙅‍♀️. Our reasoning is pragmatic, not dramatic 🧠. We think these policy types are either super expensive in terms of overhead, or they may lead to routing instabilities 📉.

Route selection policies contingent on external behavior 🎯. The route selection process may be modeled by a function that assigns a non-negative integer to a route, denoting the degree of preference. Route selection applies this function to all feasible routes to a given destination, and selects the route with the highest value. To provide a stable environment, the preference function should not use as an input the status and attributes of other routes (either to the same or to a different destination).
Transit policies contingent on external behavior 🔁. To provide a stable environment, the domain's transit policies can not be automatically affected by any information external to the domain. Specifically, these policies can not be modified, automatically, in response to information about other domains' transit policies, or routes selected by local or other domains. Similarly, transit policies can not be automatically modified in response to information about performance characteristics of either local or external domains.
Policies contingent on external state (e.g., load) 📊. It is a non-goal of the architecture to support load-sensitive routing for generic routes. However, it is possible that some types of service may employ load information to select among alternate SDR routes.
Very large number of simultaneous SDR routes 🌪️. It is a non-goal of the architecture to support a very large number of simultaneous SDR routes through any single router. Specifically, the FIB storage overhead associated with SDR routes must be comparable with that of NR routes, and should always be bound by the complexity requirements outlined earlier [Foonote: As discussed earlier, theoretically the state overhead could grow O(N^2) with the number of domains in an internet. However, there is no evidence or intuition to suggest that this will be a limiting factor on the wide utilization of SDR, provided that NR is available to handle generic routes.].

2.4 Support for TOS Routing 🎀

Throughout this document we keep talking about support for type of service (TOS) routing, so let's get into it 🦋. There's a ton of research and development happening right now to explore network architectures and protocols for high-bandwidth, multimedia traffic 🎬. Some of that traffic is delay sensitive, and some of it needs high throughput ⚡. It's unrealistic to assume that a single communication fabric will be deployed homogeneously across the internet (including all metropolitan, regional, and backbone networks) and will support all types of traffic uniformly 🙃. So to support diverse traffic requirements in a heterogeneous environment, various resource management mechanisms will be used in different parts of the global internet (e.g., resource reservation of various kinds) [ST2-90, Zhang91] 🧚.

In this context, it's the job of routing protocols to locate routes that can potentially support the particular TOS requested 🗺️. It is explicitly not the job of the general routing protocols to locate routes that are guaranteed to have resources available at the particular time of the route request. In other words, it's not practical to assume that instantaneous resource availability will be known at all remote points in the global internet 🌍. Instead, once a TOS route has been identified, an application that needs particular service guarantees will attempt to use the route (e.g., using an explicit setup message if so required by the underlying networks) 📨. In Section 4 we describe additional services that may be provided to support more adaptive route selection for special TOS [Footnote: Adaptive route selection only means adaptability during the route selection process. Once a route is picked, it isn't going to be subject to any adaptations, except when it becomes infeasible.] 💜.

2.5 Commonality between Routing Components 🧩

While it is acceptable for the NR and SDR components to be dissimilar, we do recognize that such a solution is less desirable -- all other things being equal 🤷‍♀️. In theory, there are advantages to having the NR and SDR components use similar algorithms and mechanisms. Code and databases could be shared, and the architecture would be more manageable and comprehensible 📚. On the other hand, there may be some benefit (e.g., robustness) if the two parts of the architecture are heterogeneous and not completely inter-dependent 🛡️. In Section 5 we list several areas in which opportunities for increased commonality (unification) will be exploited 💜.

2.6 Interaction with Addressing 🏠

The proposed architecture should be applicable to various addressing schemes. There are no specific assumptions about a particular address structure, except that this structure should facilitate information aggregation, without forcing rigid hierarchical routing 🌷.

Beyond this requirement, most of the proposals for extending the IP address space, for example, can be used in conjunction with our architecture. But our architecture itself does not provide (or impose) a particular solution to the addressing problem 🫶.

3.0 Design Choices for Node Routing (NR) 👑

This section digs into the design choices made for the NR component, in light of the above architectural requirements and priorities. All of our discussion of NR assumes hop-by-hop routing. Source routing has different constraints and is used for the complementary SDR component ✨.

3.1 Overview of NR 🌸

Okay, so the NR component is designed and optimized for an environment where a large percentage of packets will travel over routes that can be shared by multiple sources and that have predictable traffic patterns 🌊. NR gets more efficient when a number of source domains share a particular route from some intermediate point to a destination 🤝. NR is also best suited to provide routing for inter-domain data traffic that is either steady enough to justify the existence of a route, or predictable, so that a route may be installed when needed (based on the prediction, rather than on the actual traffic). Routes like these lend themselves to distributed route computation and installation procedures 🧁.

Routes that are installed in routers, and the information the routers used to compute them, reflect the known operational state of the routing facilities (as well as the policy constraints) at the time of route computation 📸. Route computation is driven by changes in either operational status of routing facilities or policy constraints. The NR component supports route computation that is dynamically adaptable to both changes in topology and policy 🔄. It also allows time-dependent selection or deletion of routes 🕰️. However, time dependency must be predictable (e.g., advertising a certain route only after business hours), and routes should be used widely enough to warrant inclusion in NR 💅.

The proposed architecture assumes that most of the inter-domain conversations will be forwarded via routes computed and installed by the NR component 🚚.

Moreover, the exchange of routing information necessary for the SDR component depends on facilities provided by the NR component; i.e., NR policies must allow SDR reachability information to travel 🧳. Therefore, the architecture requires that all domains in an internet implement and participate in NR 🙌. Since scalability (with respect to the size of the internet) is one of the fundamental requirements for the NR component, it must provide multiple mechanisms with various degrees of sophistication for information aggregation and abstraction 📉.

The potential reduction of routing and forwarding information depends very heavily on the way addresses are assigned and how domains and their confederations are structured. Here's the big warning from the literature 👀: "If there is no correspondence between the address registration hierarchy and the organisation of routeing domains, then ... each and every routeing domain in the OSIE would need a table entry potentially at every boundary IS of every other routeing domain" ([Oran89]). Indeed, scaling in the NR component is almost entirely predicated on the assumption that there will be general correspondence between the hierarchy of address assignment authorities and the way routing domains are organised, so that the efficient and frequent aggregation of routing and forwarding information will be possible 💖. Therefore, given the nature of inter-domain routing in general, and the NR component in particular, scalability of the architecture depends very heavily on the flexibility of the scheme for information aggregation and abstraction, and on the preconditions that such a scheme imposes. Moreover, given a flexible architecture, the operational efficiency (scalability) of the global internet, or portions thereof, will depend on tradeoffs made between flexibility and aggregation 🫠.

While the NR component is optimized to satisfy the common case routing requirements for an extremely large population of users, this does not imply that routes produced by the NR component would not be used for different types of service (TOS). To the contrary, if a TOS becomes sufficiently widely used (i.e., by multiple domains and predictably over time), then it may warrant being computed by the NR component 🌈.

To summarize, the NR component is best suited to provide routes that are used by more than a single domain 🎀. That is, the efficiency of the NR component improves when a number of source domains share a particular route from some intermediate point to a destination. Moreover, NR is best suited to provide routing for inter-domain data traffic that is either steady enough to justify the existence of a route, or predictable, so that a route may be installed when needed, (based on the prediction, rather than on the actual traffic).

3.2 Routing Algorithm Choices for NR ✨

Okay bestie, so we already know NR needs to be hop-by-hop to do scalable, efficient inter-domain routing 🌸. Now the real question is which routing algorithm NR should use 🤔. The rest of this section digs into the fundamental design choices for that.

People usually argue about link state vs distance vector 💅. But simple distance vector protocols, like the Routing Information Protocol [Hedrick88], don't scale because of convergence problems 😭. Improved distance vector protocols, like the ones in [Jaffee82, Zaumen91, Shin87], try to fix that with synchronization mechanisms or extra path information ✨. For inter-domain routing, that extra path information is essential for supporting policy 🫶. So the algorithms we're considering for NR are link state and one we call path vector (PV) 🦋. Link state is pretty well understood already (see [Zaumen 91], for example), so we have to take a little detour to explain the newer PV concept 🧚 [Footnote: We assume that some form of SPF algorithm will be used to compute paths over the topology database when LS algorithms are used [Dijkstra59, OSPF]].

3.2.1 Path Vector Protocol Overview 🌈

The Border Gateway Protocol (BGP) (see [BGP91]) and the Inter Domain Routing Protocol (IDRP) (see [IDRP91]) are both examples of path vector (PV) protocols [Footnote: BGP is an inter-autonomous system routing protocol for TCP/IP internets. IDRP is an OSI inter-domain routing protocol that is being progressed toward standardization within ISO. Since in terms of functionality BGP represents a proper subset of IDRP, for the rest of the paper we will only consider IDRP.] 📚.

PV kinda looks like the classic Bellman-Ford routing algorithm 👀. Each border router (BR) tells its neighboring BRs which destinations it can reach 📣. The twist is that PV adds info describing the properties of the paths to those destinations 💅.

That info is written as path attributes 📝. To really show how tightly the reachable destinations and the path properties are linked 🔗, PV defines a route as a pairing between a destination and the attributes of the path to that destination 💖. That's where the name path-vector protocol comes from 🧚‍♀️: a BR receives a vector from its neighboring BR that contains paths to a set of destinations [Footnote: The term "path-vector protocol" bears an intentional similarity to the term "distance-vector protocol", where a BR receives from each of its neighbors a vector that contains distances to a set of destinations.]. The path, expressed in terms of the domains (or confederations) traversed so far, rides along in a special path attribute that records the sequence of routing domains the reachability info has passed through 🛤️. Loop suppression happens through this special path attribute 🔁. That's different from LS and distance vector, which use a globally-defined monotonically-increasing metric for route selection [Shin87] 📏.

Because PV doesn't require all routing domains to have homogeneous criteria (policies) for route selection, the route selection policies used by one routing domain aren't necessarily known to the others 🤷. To keep the maximum degree of autonomy and independence between routing domains, each domain which participates in PV may have its own view of what makes an optimal route 👑. That view is based solely on local route selection policies and the info carried in the path attributes of a route 🧠. PV standardizes only the results of the route selection procedure, and lets the selection policies that affect it stay non-standard 🎀 [Footnote: This succinct observation is attributed to Ross Callon (Digital Equipment Corporation).]

3.3 Complexity ⚖️

Now that we've got the PV description down, we can compare PV to LS algorithms using the three complexity parameters defined earlier 📊.

3.3.1 Storage Overhead 💾

Without any aggregation of routing info, and ignoring storage overhead tied to transit constraints, it is possible to show that under some rather general assumptions, the average case RIB storage overhead of the PV scheme for a single TOS ranges between O(N) and O(Nlog(N)), where N is the total number of routing domains ([Rekhter91]). The LS RIB, with no aggregation of routing info, no transit constraints, a single homogeneous route selection policy across all the domains, and a single TOS, needs a complete domain-level topology map whose size is O(N) 🗺️.

Supporting heterogeneous route selection and transit policies with hop-by-hop forwarding and LS requires each domain to know all other domains' route selection and transit policies 😬. This may significantly increase the amount of routing info that each domain must store. If the number of advertised policies grows with the number of domains, storage could become unsupportable 💀. PV is a whole different story 💁. Supporting heterogeneous route selection policies has no effect on its storage complexity, aside from simply storing the local policy info (obviously) 🙌. Transit constraints in PV mean routing info gets distributed in a more restricted way, which cuts storage overhead even further ✂️. LS can't do that trick, since each domain must know every other domain's transit policies 🙅. And last but not least, some transit constraints (like path-sensitive ones) can be expressed in a more concise form in PV (see the aggregation discussion below) 📝.

PV can restrict storage overhead even more 🔒, because route computation comes before routing info dissemination. Only the routing info associated with the routes a domain selected gets distributed to its adjacent domains 📤. LS is different. Its route selection is decoupled from the distribution of routing info, so it has no effect on that distribution 🙃.

In theory, routing info aggregation can reduce storage complexity in both LS and PV 📉, but only aggregating topological info would yield the same gain for both 🤏. Aggregating transit constraints with LS may result in either reduced connectivity or less information reduction, compared with PV 😵. Aggregating heterogeneous route selection policies in LS is highly problematic, at best 🙃. In PV, route selection policies aren't distributed, so aggregating them is a total non-issue ✅ [Footnote: Although a domain's selection policies are not explicitly distributed, they have an impact on the routes available to other domains. A route that may be preferred by a particular domain, and not prohibited by transit restrictions, may still be unavailable due to the selection policies of some intermediate domain. The ability to compute and install alternative routes that may be lost using hop-by-hop routing (either LS or PV) is the critical functionality provided by SDR.].

Supporting multiple TOSs hits storage overhead the same way for both LS and PV 🤝.

The LS FIB could potentially be smaller if routes are computed at each node on demand 🧩. But that gain depends heavily on traffic patterns, memory size, and caching strategy 🎲. Without a high degree of locality, severely degraded performance can result, thanks to excessive overall computation time and excessive computation delay when forwarding packets to a new destination 🐢. And if demand driven route computation isn't used for LS, then the size of the FIB would be the same for both LS and PV 🟰.

3.3.2 Route Computation Complexity 🧮

Even if all domains employ exactly the same route selection policy, PV's computational complexity is still smaller than LS's 🏆. PV computation consists of evaluating a newly arrived route and comparing it with the existing one [Footnote: Some additional checks are required when an update is received to ensure that a routing loop has not been created.]. Conventional LS computation, on the other hand, requires execution of an SPF algorithm such as Dijkstra's 🌀.

With PV, a topology change only results in recomputing the routes it affects, which is more efficient than complete recomputation 💪. Heads up, though: because each distance vector carries full path info, the effect of a topology change may propagate farther than in traditional distance vector algorithms 🌊. Still, the number of affected domains will be smaller with PV than with conventional LS hop-by-hop routing 🙌. With PV, only the domains whose routes are affected by the changes have to recompute, while with conventional LS hop-by-hop routing all domains must recompute 😤. It's also possible to employ partial recomputation with LS (i.e., when topology changes, only the affected routes are recomputed). But "studies suggest that with a very small number of link changes (perhaps 2) the expected computational complexity of the incremental update exceeds the complete recalculation" ([ANSI87-150R]). Even so, these checks are much simpler than executing a full SPF algorithm ✨.

Heterogeneous route selection policies have serious implications for computational complexity 😱. The major problem with supporting them in LS is the computational complexity of the route selection itself. We're not aware of any algorithm with less than exponential time complexity that would be capable of computing routes to all destinations with LS hop-by-hop routing and heterogeneous route selection policies 🥵. PV, on the other hand, lets each domain make its route selection autonomously, based only on local policies 🧘. So support for dissimilar route selection policies has no negative implications for the complexity of route computation in PV 💖. The same goes for path-sensitive transit policies: providing support for them in LS implies exponential computation, while in PV that support has no impact on the complexity of route computation 🫠.

In summary 🎯, because NR will rely primarily on precomputation of routes, aggregation is essential to the long-term scalability of the architecture 📈. To the extent aggregation is facilitated with PV, computational complexity is reduced too 🎉. Similar arguments may be made for LS, but the aggregation capabilities that can be achieved with LS are more problematic, because LS relies on consistent topology maps at each node 🫣. It's also not clear what additional computational complexity will be associated with aggregating transit constraints and heterogeneous route selection policies in LS 🤷‍♀️.

3.3.3 Bandwidth Overhead

okay so PV routing updates carry fully-expanded info 💅 a complete route for every supported TOS gets advertised 🎀. With LS, TOS only adds a factor increase per link advertised, which is WAY less than the number of complete routes 🔥. LS can encode TOSs more efficiently than PV, BUT link state info gets flooded to all domains, while PV routing updates only go to the domains that actually use them 🦋. So it's hard to say which scheme has more bandwidth overhead, all other factors being equal 🙈

Moreover, this is perhaps really not an important difference 🌸, since we care more about the number of messages than the number of bits (because of compression, greater link bandwidth, and the increased physical stability of links) ✨.

3.4 Aggregation

Forming confederations of domains for consistent, hop-by-hop LS route computation requires that domains within a confederation have consistent policies 🎀. LS confederation also requires that any lower level entity be a member of only one higher level entity 💀. In general, no intra-confederation information can be made visible outside of a confederation, or else routing loops may occur because different domains end up using an inconsistent map of the network 🙈. So the use of confederations with hop-by-hop LS is limited: each domain (or confederation) can only be a part of one higher level confederation and only export policies consistent with that confederation (see examples in Section 2.2) 😭. These restrictions are likely to impact the scaling capabilities of the architecture quite severely 💔.

In comparison, PV can accommodate different confederation definitions because looping is avoided by using full path information 💖. Consistent network maps aren't needed at each route server, since route computation precedes routing information dissemination 🧚. Consequently, PV confederations can be nested, disjoint, or overlapping 🌈. A domain (or confederation) can export different policies or TOS as part of different confederations, which gives the extreme flexibility that is crucial for the overall scaling and extensibility of the architecture 👑.

In summary, aggregation is essential to achieve acceptable complexity bounds, and flexibility is essential to achieve acceptable aggregation across the global, decentralized internet 🫶. PV's strongest advantage stems from its flexibility 💅✨.

3.5 Policy

The need to allow expression of transit policy constraints on any route (i.e., NR routes as well as SDR routes) can, by itself, be supported by either LS or PV 🦋. However, the complexities of supporting transit policy constraints are noticeably higher for LS than for PV 😵. That's because LS has to flood all transit policies, whereas PV controls transit policies through restricted distribution of routing information 🎀. The latter always imposes less overhead than flooding 💜.

All of the transit constraints that can be supported with LS can be supported with PV, but the reverse is not true 🔥. There are certain transit constraints (e.g., path-sensitive transit constraints) that are easily supported with PV and are prohibitively expensive (in terms of complexity) to support in LS 😭. For example, it is not clear how NR with LS could support something like ECMA-style policies based on hierarchical relations between domains, while support for such policies is straightforward with PV 🌸.

As indicated above, support for heterogeneous route selection policies is impractical with LS hop-by-hop routing, given its computational and storage complexity 🙈. PV, on the other hand, can accommodate heterogeneous route selection with little additional overhead 💖.

3.6 Information Hiding

PV has a clear advantage with respect to selective information hiding 👑. LS with hop-by-hop routing depends on all domains having exactly the same information, and that clearly contradicts the notion of selective information hiding 💀. In other words, the requirement to perform selective information hiding is unsatisfiable with LS hop-by-hop routing 🥲.

3.7 Commonality between NR and SDR Components

In [Breslau-Estrin91] we argued for using LS in conjunction with SDR, so there is some preference for using LS with NR 🧚. However, there are several reasons why NR and SDR wouldn't use exactly the same routing information, even if they used the same algorithm 🙈. There are also several opportunities for unifying the management (distribution and storage) of routing and forwarding information, even if dissimilar algorithms are used ✨.

In considering the differences between NR and SDR, we need to address several areas 💅:

Routing information and distribution protocol: LS for SDR is quite different from the LS in NR 🦋. For example, SDR LS need not aggregate domains; to the contrary, SDR LS requires detailed information to generate special routes 🎀.

In addition, consistency requirements (essential for NR) are unnecessary for the SDR component 🌸. Therefore, LS information for the SDR component can be retrieved on demand, while the NR component must use flooding of topology information 🫶.

Route computation algorithm: It isn't clear whether route computation algorithm(s) can be shared between the SDR and NR components, given the difficulty of supporting heterogeneous route selection policies in NR 🤔.
Forwarding information: Using dissimilar route computation algorithms doesn't preclude common handling of packet forwarding 💖. Even if LS were used for NR, the requirement would be the same: the forwarding agent must be able to determine whether to use an NR precomputed route or an SDR installed route to forward a particular data packet 🧚✨.

In conclusion, using similar algorithms and mechanisms for SDR and NR components would have benefits 🌈. However, those benefits don't dominate the other factors discussed before 🥹.

3.8 Summary

Given the performance complexity issues associated with global routing, aggregation of routing information is essential 😤. At the same time, we've argued that such aggregation must be flexible 💅. Given the difficulties of supporting LS hop-by-hop routing in the presence of (a) flexible aggregation, (b) heterogeneous route selection policies, and (c) incomplete or inconsistent routing information, we see no alternative but to employ PV for the NR component of our architecture 👑🔥.

Based on the above tradeoffs, our NR component employs a PV architecture, where route computation and installation is done in a distributed fashion by the routers participating in the NR component [Footnote: Packet forwarding along routes produced by the NR component can be accomplished by either source routing or hop-by-hop routing. The latter is the primary choice because it reduces the amount of state in routers (if route setup is employed), or avoids encoding an explicit source route in network layer packets. However, the architecture does not preclude the use of source routing (or route setup) along the routes computed, but not installed, by the NR component.] 🎀.

The distributed algorithm combines some of the features of link state with those of distance vector algorithms 🦋. In addition to next hop information, the NR component maintains path attributes for each route (e.g., the list of domains or routing domain confederations that the routing information has traversed so far) 🧚. The path attributes carried along with a route express a variety of routing policies and make the entire route to the destination explicit 💜. With aggregation, this is a superset of the domains that form the path to the destination 🌸✨.

4.0 Source-demand routing (SDR) ✨

okay bestie, so inter-domain routers in the SDR component forward packets using routing info that gets computed and installed by the domain that started the traffic (the source routing domain) 🦋

the source routing domain installing the route isn't a vibe choice, it's a necessity 💅 if a route is only used by a handful of domains (maybe just one!), it makes way more sense for the source to compute and install that special route itself. otherwise you'd be burdening the middle nodes with hunting for and picking a route with those specialized requirements, and nobody wants that energy 🙈 and if the demand is unpredictable, so only the source can know it's happening, then it should be up to the source to install the route. iykyk 🎀

the info SDR uses to compute source-demand routes reflects the administrative status of routing facilities (configured topology and policy), not the operational status 🌸 [Footnote: If SDR uses NR information then operational status could be considered in some route selection.] so it's totally possible for a source routing domain to compute a route that isn't operational when it's time to install it. no cap, that happens 💀 the SDR component tries to tell the source domain about failures when installation is attempted, and it also gives the source domain a way to get notified of failures along routes that were already installed and active ✨ so SDR is adaptive to topology changes, but that adaptability comes from the route installation and route management mechanisms doing their thing. this is different from NR, where status changes get propagated and taken in by nodes as soon as possible ⭐ so to adapt faster to changes in operational status, SDR lets the source domain switch to a route computed by NR if a failure along the source-demand route is detected (whether during installation or after the route is up), as long as policy allows using that NR route. main character glow-up 👑

the NR component groups domains into confederations to hit its scaling goals (see [IDRP91]) 🧚 SDR, on the other hand, lets an AD-level route be used by one individual domain without letting the whole confederation that domain belongs to use it too 💜 similarly, a single transit domain might support a policy or special TOS that the other domains in its confederation(s) don't. so basically the architecture uses SDR to support non-hierarchical, non-aggregated policies where and when they're needed 🫶 which means SDR by itself does not have the scaling properties of NR. in exchange, SDR doesn't need a complete, global domain map if parts of the world never get traversed or communicated with 🌈 because the routing structure is looser, SDR does not guarantee that a participating source routing domain will always have enough info to compute a route to a destination. and even if the domain does have enough info, the quantity might be big enough that storing it and/or computing the route in a timely way gets tricky 😭 still, it's a goal of the architecture to provide efficient methods so sources can obtain the info they need to compute desired routes, even with no guarantees [Footnote: The primary goal of policy or TOS routing is to compute a route that satisfies a set of specialized requirements, and these requirements take precedence over optimality. In other words, even if a routing domain that participates in SDR or NR has sufficient information to compute a route, given a particular set of requirements, the architecture does not guarantee that the computed route is optimal.]

the big assumption with SDR is that routes installed on demand get used sparingly 🍓 the architecture assumes that at any given moment, the set of all source-demand routes installed in an internet is a small fraction of the total number of source-demand routes that all the routing domains could potentially install. it's also assumed that the number of routes installed in a BR by the SDR component should be on the order of log N (where N is the total number of routing domains in the Internet), so SDR's scaling properties are comparable with NR's scaling properties 💖 NR gets this property from hierarchy ✨

now, the requirement doesn't mean only a few domains can join SDR, and it doesn't mean SDR routes have to have short lifetimes 🌸 what it does mean is that the product of the number of routes specified by SDR-participating domains and the average SDR-route lifetime is bounded. for example, the architecture allows either a small number of SDR routes with fairly long average lifetimes, or a large number of SDR routes with fairly short average lifetimes. but it clearly prohibits a large number of SDR routes with long average lifetimes 🚫 the number of SDR routes is a function of how many domains use SDR routes and how many routes each source domain uses 🧮

so in summary, SDR is a perfect fit for traffic that (1) isn't widely used enough (or isn't predictable or steady enough) to justify computation and maintenance by the NR component, and (2) lasts significantly longer than it takes to run the route installation procedure 🦋

4.1 Path Vector vs. Link State for SDR

it's feasible to use either a distance vector or a link state method of route computation together with source routing 🌷 you could imagine something like BGP, where the source uses the full AD path info it gets in routing updates to create a source route. that kind of protocol could fix some of the problems we've spotted with distance vector, hop-by-hop designs 💜 but we're not going to dig into it further, because there's less to gain from source routing without also using a link state scheme 🙅‍♀️ the power of source routing, in the context of inter-AD policy routing, is giving the source control over the entire route. that goal can't be fully realized when intermediate nodes control which legal routes get advertised to their neighbors, and therefore to a source 😤

so basically, intermediate nodes should be able to rule out using a route by expressing a transit policy 💅 but if a route isn't ruled out (meaning it's legal according to all the ADs in the route), it should be made available to the source no matter what an intermediate domain prefers for how its own traffic flows 🫶

therefore, the SDR component uses an IDPR-like architecture, where link-state style updates are distributed with explicit policy terms included in each update, along with the advertising node's connectivity 🧚 ✨

4.2 Distribution of Routing Information

by using a hop-by-hop NR component based on PV to complement the source-routing SDR component, we took a lot of pressure off aggregating SDR forwarding info 🎀 the big chunk of inter-domain traffic that any particular border router carries at the same time gets forwarded using aggregated NR forwarding info, so that part's handled 🙌 but NR doesn't solve the other major scaling problem with SDR, which is distributing, storing, and computing over a complete domain-level topology map 😭 this section describes some promising opportunities for making SDR's routing info distribution, storage, and computation scale better 🌈

now, we're not going to solve this the same way we solve it for NR 🙅‍♀️ a priori abstraction won't be used, because different domains might need different ways of abstracting the same routing info. for example, if you aggregate routing info from domains that don't share the same policy and TOS characteristics (aka services), then outside of the aggregate, only the services offered by all the domains in the aggregate get advertised 💀 in order to locate special routes, SDR only uses aggregates when the component domains (and in turn the aggregate) advertise the required TOS and policy descriptions. when the required TOS or policy characteristics aren't offered by an aggregate, full info about the component domains is used to build a route through those domains that do support the particular characteristics 🦋 so we need some other, more flexible way of reducing how much info gets distributed and held 💖 we'll address two issues in turn: distribution of configured topology and policy info, and distribution of dynamic status info ✨

4.2.1 Configured Information ✨

okay so, info about which inter-domain links exist and what policies each domain has? it changes slowly over time 🐢. this is what we call configured information 📚. in the current IDPR spec, complete, global configuration info gets kept by a route server in each domain. route servers (RS) are the entities that compute source routes 👑. on startup, an RS can download the connectivity database from a neighbor RS ✨. and as domains, inter-domain links, or policies change, those changes get flooded to an RS in each domain 🌊.

we haven't specified the exact mechanisms for distributing configured connectivity info for SDR yet 🫶. but unlike the current IDPR spec, the SDR component is not going to flood all configured info globally 🙅‍♀️. a few alternate ways of organizing and distributing the info are still being investigated 🔍.

configured info may get distributed regularly over an out-of-band channel, e.g., CD/ROM 💿. same energy here, this info could be posted in several well-known locations for retrieval, e.g., via FTP 📂. between these "major" updates, aggregated bundles of changes may get flooded globally 🌍. limited flooding (e.g., by hop-count) could also be used depending on how "important" a change is 🎯. like, a policy change in a major backbone may still get flooded globally, but a new inter-regional link may only get flooded within those regions 🗺️. and info about an additional link to a non-transit domain might not be available until the next regularly-scheduled "major" distribution 🗓️. ngl, that's a lot of nuance 💅.

changes that aren't distributed as they occur won't necessarily get discovered 😬. but a route server may still learn pertinent info by directly querying remote servers, or through error messages that come back from traffic sent along failed routes 💌. using some combo of these mechanisms can help avoid complete global flooding ✨.

even if an initial implementation uses a simple global flood, we still have to study how to structure connectivity info so it can be retrieved or distributed in a more selective way, while still letting sources discover desired routes 🔎. for example, we imagine RSs requesting filtered info from each other 🤳. how RSs should define filters that get enough info to find special routes, while also effectively limiting the info, is an open question 🤔. again, the question is how to effectively anticipate and describe what info is needed before computing the route 🧠.

the essential dilemma is that networks aren't organized in a nicely geographical or topologically consistent manner 🌀 (e.g., it's not effective to ask for all networks going east-west that are within a certain north-south region of the target). so a source domain doesn't know what info it needs (or should ask for) until it searches for, and discovers, the actual path 😩. even with a central database, techniques are needed to structure configuration info so the potential paths that are most likely to be useful get explored first, thereby reducing the time required for route computation ⏱️.

one promising approach organizes info using route fragments (partial paths) [Footnote: Route fragments were first suggested by Dave Clark and Noel Chiappa.]. although the number of route fragments grows faster than the number of domains (at least O(N^2)), we can selectively choose those that will be useful to compute routes 🧩. in particular, for each stub domain, fragments would be constructed to several well-known backbones [Footnote: Route fragments may be computed by a destination's route server and either made available via information service queries or global flooding. In addition, NR computed routes may be used as SDR route fragments.]. among its benefits, this approach aggregates domain info in a manner useful for computing source-routes, and provides an index, namely the destination, which facilitates on-demand reference and retrieval of info pertinent to a particular route computation 🪄. at this point, it's not clear how route fragments will affect SDR's ability to discover non-hierarchical routes 🤷‍♀️.

4.2.2 Dynamic Status Information 🦋

assuming a technique for global or partial distribution of configured info is in place, the next question is whether, and how, to distribute dynamic status info (i.e., whether an inter-domain connection is up or down) 🔌.

in the current version of IDPR, dynamic status info gets flooded globally on top of config info. we propose distributing status info strictly based on locality 📍. first, dynamic info will be advertised within a small hop-count radius. this simple, low-overhead mechanism exploits topological locality 🧲. on top of flooding status updates to nearby nodes, we also want to provide more accurate route info for long-distance communications that involve more than a few network hops ✈️. reverse path update (RPU) is a mechanism for sending dynamic status info to nodes that are outside the k-hop radius used for updates, but that would still get better service (fewer failed setups) by having access to the dynamic info [Estrin-etal91] 🔁.

RPU uses the existing active routes (represented by installed setup state or by a cache of the most recent source routes sent via the node in question) as a hint for distributing event notifications 💡. instead of reporting only the status of the route being used, RPU reports the status of the domain's other inter-domain connections 👀. if source routing exhibits route locality, the source is more likely to use other routes going through the node in question, and in any case the overhead of the info about other links will be minimal 💖.

this way, sources receive status info from regions of the network they maintain active routes through, even if those regions are more than k hops away 🌐. with a scheme like this, k could be small to maximize efficiency, and RPU could be used to reduce the incidence of failed routes resulting from inaccurate status info 🙌. this will be useful if long-path communication exhibits route locality with respect to regions that are closer to the destination (and therefore outside the k hop radius of flooded info) 🎯. in those situations, flooding info to the source of the long route would be inefficient, because k would have to equal the length of the route, and in almost all cases, the percentage of nodes that would use the info drops off significantly with larger k 📉✨.

4.3 Source-Demand Route Management 🎀

okay so SDR can be built right on top of the network layer that the NR component supports, or it can run in parallel with it 🦋 Either way, SDR forwarding gets two techniques: loose source-routing and route setup 💅

The first one, loose source-routing, lets whoever originates a packet name a sequence of domains that the packet should traverse on its way to a destination 🧚 Forwarding that packet within a domain, or even between domains within a confederation, gets left to intra-domain routing. bestie, this means there's no per-connection state, which is so good for transaction traffic 😭

The second one, route setup, is based on mechanisms developed for IDPR and described in [IDPR90] ✨ It's giving best for conversations that persist way longer than a round-trip-time 🫶 The setup protocol defines packet formats and how route installation request packets (i.e., setup packets) get processed. When a source generates a setup packet, the first border router along the specified source route checks the setup request, and if it's accepted, that BR installs routing information. This info includes a path ID, the previous and next hops, and whatever other accounting-related information the particular domain requires. The setup packet then gets passed on to the next BR in the domain-level source route, and the same procedure is carried out [Footnote: The setup packet may be forwarded optimistically, i.e., before checks are completed, to reduce latency.]. When the setup packet reaches the destination, an accept message gets propagated back hop by hop, and each BR en route activates its routing information 🌸 Subsequent data packets traveling along the same path to the destination include a path ID in the packet, and that path ID is how each packet finds the right next-hop information 🔥

Border routers that support both the NR and the SDR components must be able to determine what forwarding mechanism to use. Like, when a BR is handed a network layer PDU, it should be able to make an unambiguous decision about whether that PDU gets handled by the NR or the SDR component 👑 The discrimination mechanisms depend on whether the new network layer introduced by the SDR component is built on top of, or in parallel with, the network layers supported by the NR component. Once the discrimination is made, packets that have to be forwarded via routes installed by the SDR component go out the exit port associated with the particular Path ID in the packet header. Packets that have to be forwarded via routes installed by the NR component go out the exit port associated with the particular destination and Type of Service parameters (if present) in their packet headers 🧚

Next, we describe the primary differences between the IDPR setup procedure previously specified and the procedure we propose to develop for this hybrid architecture 🦋

During route installation, if a BR on the path finds that the remainder of the indicated route from the BR to the destination is identical to the NR route from the BR to the destination, then the BR can turn off the SDR route at that point and map it onto the NR route ✨ For this to occur, the specifications of the SDR route must completely match those of the NR route. In addition, the entire forward route must be equivalent (i.e., the remaining hops to the destination) 💅

Moreover, if the NR route changes during the course of an active SDR route, and the new NR route does not match the SDR route, then the SDR route must be installed for the remainder of the way to the destination. Consequently, when an SDR route is mapped onto an NR route, the original setup packet must be saved 🫶 A packet traveling from a source to destination may therefore traverse both an SDR and an NR route segment. However, a packet will not traverse another SDR segment after traveling over an NR segment. However, during transient periods packets could traverse the wrong route, and therefore this must be an optional and controllable feature 🙈

A source can also request notification if a previously-down link or node returns to operation some time after a requested route setup fails 💜 If a BR on the route discovers that the requested next-hop BR is not available, the BR can add the source to a notification list, and when the next-hop BR becomes reachable, a notification can be sent back to the source. This provides a means of flushing out bad news when it is no longer true 😭 For example, a domain might decide to route through a secondary route when its preferred route fails. The notification mechanism would inform the source in a timely manner when its preferred route is available again 🌈

A third option addresses adaptation after route installation 🔥 During packet forwarding along an active SDR route, if a BR finds that the SDR route has failed, it may redirect the traffic along an existing NR route to the destination. This adaptation is allowed only if use of the NR route does not violate policy. For example, it may provide a less desirable type of service. This is done only if the source selects the option at route setup time. It is also up to the source whether it is to be notified of such actions 👑

When an SDR route does fail, the detecting BR sends notification to the source(s) of the active routes that are affected 💀 Optionally, the detecting BR may include additional information about the state of other BRs in the same domain. In particular, the BR can include its domain's most recent "update" indicating that domain's inter-domain links and policy. This can be helpful to the extent there is communication locality, i.e., if alternative routes might be used that traverse the domain in question but avoid the failed BR 🧚

In summary, when a route is first installed, the source has several options, which are represented by flags in the route setup packet 🎀

If an NR route is available that satisfies all local policy and TOS, then use it. Otherwise...
Indicate whether the source wants to allow the setup to default to a NR route if the SDR route setup fails.
Request notification of mapping to a NR route.
Request additional configured information on failure.
Request addition to a notification list for resource re-availability.
Allow data packets to be rerouted to a NR route when failure happens after setup (so long as no policy is violated).
Request notification of a reroute of data packets.
Request additional configured information on failure notice when the route is active.
Request addition to a notification list if an active route fails.

5.0 The Unified Architecture ✨

In addition to further evaluation and implementation of the proposed architecture, future research must investigate opportunities for increased unification of the two components of our architecture 🌸 We are investigating several opportunities for additional commonality:

Routing Information Base: Perhaps a single RIB could be shared by both NR and SDR. NR routes can be represented as a directed graph labeled with flags (on the nodes or links) corresponding to the generic transit constraints. SDR requires that this graph be augmented by links with non-generic policies that have been discovered and maintained for computing special routes. In addition, special policy flags may be added to links already maintained by the NR component 💅
Information Distribution: The NR path vectors could include address(es) of repositories for SDR-update information for each AD (or confederation) to assist the SDR component in retrieving selective information on demand. For domains with minimal policies, where the space required for policy information is smaller than the space required for a repository address (e.g., if the policies for the domain listed are all wildcard), the NR path vectors could include a flag to that effect 🫶
Packet Forwarding: We should consider replacing the current IDPR-style network layer (which contains a global path identifier used in forwarding data packets to the next policy gateway on an IDPR route) with a standard header (e.g., IP or CLNP), augmented with some option fields. This would unify the packet header parsing and forwarding functions for SDR and NR, and possibly eliminate some encapsulation overhead 🔥
Reachability Information: Currently IDRP distributes network reachability information within updates, whereas IDPR only distributes domain reachability information. IDPR uses a domain name service function to map network numbers to domain numbers, and the latter is needed to make the routing decision. We should consider obtaining the network reachability and domain information in a unified manner 🌈

5.1. Applicability to Various Network Layer Protocols 🦋

okay so this architecture is designed to work with the existing network layer protocols like IP ([Postel81]), CLNP ([ISO-473-88]), and ST-II ([ST2-90]) 💖. We also intend for it to support future network layer mechanisms, e.g., Clark and Jacobson's proposal or Braden and Casner's Integrated Services IP. BUT on principal we can not make sweeping guarantees in advance of the mechanisms themselves 🙈. not every protocol on that list will be able to use every capability the architecture offers, ngl. For instance, unless the increase in the number of different types of services offered is matched by the ability of a particular network layer protocol to unambiguously express requests for such different types of services, the capability of the architecture to support routing in the presence of a large number of different types of service is largely academic 💀. So not all components will matter equally to every network layer protocol. On the other hand, this architecture is built for the future global internetworking environment 🌍, and all the research and development happening right now to implement and evaluate network mechanisms for different types of service suggests future networks will offer those services ✨.

One of the fundamental issues here is single versus multiple protocols 👀. The architecture does not make any assumptions about whether each network layer is going to have its own inter-domain routing protocol, or whether a single inter-domain routing protocol will be able to cover multiple network layers [Footnote: Similar issue already arose with respect to the intra-domain routing protocol, which generated sufficient amount of controversy within the Internet community. It is our opinion, that the issue of single versus multiple protocols is more complex for the inter-domain routing than for the intra-domain routing.]. That is, the proposed architecture can be realized either by a single inter-domain routing protocol covering multiple network layers, or by multiple inter-domain routing protocols (with the same architecture) tailored to a specific network layer [Footnote: If the single protocol strategy is adopted, then it is likely that IDRP will be used as a base for the NR component. Since presently IDRP is targeted towards CLNP, further work is needed to augment it to support IP and ST-II. If the multiple protocol strategy is adopted, then it is likely that BGP will be used as a base for the NR component for IP, and IDRP will be used as a base for the NR component for CLNP. Further work is needed to specify protocol in support for the NR component for ST-II. Additional work may be needed to specify new features that may be added to BGP.].

5.2. Transition 🚀

The proposed architecture is not intended for full deployment in the short term future 🌷. Think of it as a goal we can aim for, so we can start steering our operational and research investment over the next 5 years 🧭.

At the same time, the architecture does not require a wholesale overhaul of the existing Internet, which is a huge relief 😭. The NR component may be phased in gradually. For example, the NR component for IP may be phased in by replacing existing EGP-2 routing with BGP routing. Once the NR component is in place, it can be augmented by the facilities provided by the SDR component ✨.

The most critical components needed to support SDR are route installation and packet forwarding in the routers that support SDR 🔥. Participation as a transit routing domain requires that the domain can distribute local configuration information (LCI) and that some of its routers implement the route installation and route management protocols. Participation as a source requires that the domain have access to a RS to compute routes, and that the source domain has a router that implements the route installation and route management protocols. In addition, a network management entity must describe local configuration information and send it to the central repository(ies). A collection and distribution mechanism must be put in place, even if it is centralized 🧚.

6.0. Conclusions and Future Work ✨

So, to sum it all up 💅: the proposed architecture combines hop-by-hop path-vector, and source-routed link-state, protocols, and uses each for that which it is best suited. NR uses PV and multiple, flexible, levels of confederations to support efficient routing of generic packets over generic routes. SDR uses LS computation over a database of configured and dynamic information to route special traffic over special routes 🛣️. In the past, the community has viewed these two as mutually exclusive, but to the contrary, they are quite complementary, and it is fortunate that we, as a community, have pursued both paths in parallel 🌈. Together these two approaches will flexibly and efficiently support TOS and policy routing in very large global internets 👑.

It is now time to consider the issues associated with combining and integrating the two 🎀. We must go back and look at both architectures and their constituent protocols, eliminate redundancies, fill in new holes, and provide seamless integration. Main character work, honestly 😤🔥.

7.0. Acknowledgments 🫶

We would like to thank Hans-Werner Braun (San Diego Supercomputer Center), Lee Breslau (USC), Scott Brim (Cornell University), Tony Li (cisco Systems), Doug Montgomery (NIST), Tassos Nakassis (NIST), Martha Steenstrup (BBN), and Daniel Zappala (USC) for their comments on a previous draft. The best people 💖.

8.0. References 📚

[ANSI 87-150R] "Intermediate System to Intermediate System Intra-Domain Routing Exchange Protocol", ANSI X3S3.3/87-150R.

[BGP 91] Lougheed, K., and Y. Rekhter, "A Border Gateway Protocol 3 (BGP-3)", RFC 1267, cisco Systems, T.J. Watson Research Center, IBM Corp., October 1991.

[Breslau-Estrin 91] Breslau, L., and D. Estrin, "Design and Evaluation of Inter-Domain Policy Routing Protocols", To appear in Journal of Internetworking Research and Experience, 1991. (Earlier version appeared in ACM Sigcomm 1990.)

[Clark 90] Clark, D., "Policy Routing in Internetworks", Journal of Internetworking Research and Experience, Vol. 1, pp. 35-52, 1990.

[Dijkstra 59] Dijkstra, E., "A Note on Two Problems in Connection with Graphs", Numer. Math., Vol. 1, 1959, pp. 269-271.

[ECMA89] "Inter-Domain Intermediate Systems Routing", Draft Technical Report ECMA TR/ISR, ECMA/TC32-TG 10/89/56, May 1989.

[EGP] Rosen, E., "Exterior Gateway Protocol (EGP)", RFC 827, BBN, October 1982.

[Estrin 89] Estrin, D., "Policy Requirements for Inter Administrative Domain Routing", RFC 1125, USC Computer Science Department, November 1989.

[Estrin-etal91] Estrin, D., Breslau, L., and L. Zhang, "Protocol Mechanisms for Adaptive Routing in Global Multimedia Internets", University of Southern California, Computer Science Department Technical Report, CS-SYS-91-04, November 1991.

[Hedrick 88] Hedrick, C., "Routing Information Protocol", RFC 1058, Rutgers University, June 1988.

[Honig 90] Honig, J., Katz, D., Mathis, M., Rekhter, Y., and J. Yu, "Application of the Border Gateway Protocol in the Internet", RFC 1164, Cornell Univ. Theory Center, Merit/NSFNET, Pittsburgh Supercomputing Center, T.J. Watson Research Center, IBM Corp., June 1990.

[IDPR90] Steenstrup, M., "Inter-Domain Policy Routing Protocol Specification and Usage: Version 1", Work in Progress, February 1991.

[IDRP91] "Intermediate System to Intermediate System Inter-domain Routeing Exchange Protocol", ISO/IEC/ JTC1/SC6 CD10747.

[ISIS10589] "Information Processing Systems - Telecommunications and Information Exchange between Systems - Intermediate System to Intermediate System Intra-Domain Routing Exchange Protocol for use in Conjunction with the protocol for providing the Connectionless-mode Network Service (ISO 8473)", ISO/IEC 10589.

[ISO-473 88] "Protocol for providing the connectionless-mode network service", ISO 8473, 1988.

[Jaffee 82] Jaffee, J., and F. Moss, "A Responsive Distributed Routing Algorithm for Computer Networks", IEEE Transactions on Communications, July 1982.

[Little 89] Little, M., "Goals and Functional Requirements for Inter-Autonomous System Routing", RFC 1126, SAIC, October 1989.

[Oran 89] Oran, D., "Expert's Paper: The Relationship between Addressing and Routeing", ISO/JTC1/SC6/WG2, 1989.

[OSPF] Moy, J., "The Open Shortest Path First (OSPF) Specification", RFC 1131, Proteon, October 1989.

[Postel 81] Postel, J., "Internet Protocol", RFC 791, DARPA, September 1981.

[Rekhter 91] Rekhter, Y., "IDRP protocol analysis: storage complexity", IBM Research Report RC17298(#76515), October 1991.

[Shin87] Shin, K., and M. Chen, "Performance Analysis of Distributed Routing Strategies Free of Ping-Pong-Type Looping", IEEE Transactions on Computers, February 1987.

[ST2-90] Topolcic, C., "Experimental Internet Stream Protocol, version 2 (ST II)", RFC 1190, CIP Working Group, October 1990.

[Zaumen 91] Zaumen, W., and J. Garcia-Luna-Aceves, "Dynamics of Link State and Loop-free Distance-Vector Routing Algorithms", ACM Sigcomm '91, Zurich, Switzerland, September 1991.

[Zhang 91] Zhang, L., "Virtual Clock: A New Traffic Control Algorithm for Packet Switching Networks".

Security Considerations 🔒😱

Security issues are not discussed in this memo. Yes, that's really the whole section, and it's a lot to sit with, so handle your security planning with extra care 💀.

Authors' Addresses 📮

Deborah Estrin University of Southern California Computer Science Department, MC 0782 Los Angeles, California 90089-0782

Phone: (310) 740-4524 EMail: estrin@usc.edu

Yakov Rekhter IBM T.J. Watson Research Center P.O. Box 218 Yorktown Heights, New York 10598

Phone: (914) 945-3896 EMail: yakov@ibm.com

Steven Hotz University of Southern California Computer Science Department, MC 0782 Los Angeles, California 90089-0782

Phone: (310) 822-1511 EMail: hotz@usc.edu

the end, bestie 🌈✨💜

📦 where this page comes from

ietf: rfc1322 1992-05
💖 girlified by claude-haiku-5-5 on 2026-10-15: a language model's rewrite of the original, under its terms