diff options
Diffstat (limited to 'doc/rfc/rfc1322.txt')
| -rw-r--r-- | doc/rfc/rfc1322.txt | 2131 |
1 files changed, 2131 insertions, 0 deletions
diff --git a/doc/rfc/rfc1322.txt b/doc/rfc/rfc1322.txt new file mode 100644 index 0000000..f420a3b --- /dev/null +++ b/doc/rfc/rfc1322.txt @@ -0,0 +1,2131 @@ + + + + + + +Network Working Group D. Estrin +Request for Comments: 1322 USC + Y. Rekhter + IBM + S. Hotz + USC + May 1992 + + + A Unified Approach to Inter-Domain Routing + +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 which 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 + + The global internet can be modeled as a collection of hosts + interconnected via transmission and switching facilities. Control + over the collection of hosts and the transmission and switching + facilities that compose the networking resources of the global + internet is not homogeneous, but is distributed among multiple + administrative authorities. Resources under control of a single + administration form a domain. In order to support each domain's + autonomy and heterogeneity, routing consists of two distinct + components: intra-domain (interior) routing, and inter-domain + (exterior) routing. Intra-domain routing provides support for data + communication between hosts where data traverses transmission and + switching facilities within a single domain. Inter-domain routing + provides support for data communication between hosts where data + + + +Estrin, Rekhter & Hotz [Page 1] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + + traverses transmission and switching 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, providing 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 continue to evolve and that 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, (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 + + + +Estrin, Rekhter & Hotz [Page 2] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + + [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 setup 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. Therefore, 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, consequently, 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, make them + too costly to support with the NR mechanism. + + A useful analogy to this approach 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 + + + +Estrin, Rekhter & Hotz [Page 3] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + + 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. + + + + + + + + +Estrin, Rekhter & Hotz [Page 4] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + +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 + + The storage overhead of an entity that participates in inter-domain + routing comes from two sources: Routing Information Base (RIB), and + Forwarding Information Base (FIB) overhead. The RIB contains the + routing information that entities exchange via the inter-domain + routing protocol; the RIB is the input to the route computation. The + FIB contains the information that the entities use to forward the + inter-domain traffic; the FIB is the output of the route computation. + For an acceptable level of storage overhead, the amount of + information in both FIBs and RIBs should grow significantly slower + than linearly (e.g., close to logarithmically) with the total number + of domains in an internet. To satisfy this requirement with respect + to the RIB, the architecture must provide mechanisms for either + aggregation and abstraction of routing and forwarding information, or + retrieval of a subset of this information on demand. To satisfy this + requirement with respect to the FIB, the architecture must provide + mechanisms for either aggregation of the forwarding information (for + the NR computed routes), or dynamic installation/tear down of this + information (for the SDR computed routes). + + Besides being an intrinsically important evaluation metric, storage + overhead has a direct impact on computational and bandwidth + complexity. Unless the computational complexity is fixed (and + independent of the total number of domains), the storage overhead has + direct impact on the computational complexity of the architecture + since the routing information is used as an input to route + computation. Moreover, unless the architecture employs incremental + updates, where only changes to the routing information are + propagated, the storage overhead has direct impact on the bandwidth + overhead of the architecture since the exchange of routing + information constitutes most of the bandwidth overhead. + + + + + +Estrin, Rekhter & Hotz [Page 5] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + +2.1.2 Computational Overhead + + The NR component will rely primarily on precomputation of routes. If + inter-domain routing is ubiquitous, then the precomputed routes + include all reachable destinations. Even if policy constraints make + fully ubiquitous routing impossible, the precomputed routes are + likely to cover a very large percentage of all reachable + destinations. Therefore the complexity of this computation must be + as small as possible. Specifically, it is highly desirable that the + architecture would employ some form of partial computation, where + changes in topology would require less than complete recomputation. + Even if complete recomputation is necessary, its complexity should be + less than linear with the total number of domains. + + The SDR component will use on-demand computation and caching. + Therefore the complexity of this computation can be somewhat higher. + Another reason for relaxed complexity requirements for SDR is that + SDR is expected to compute routes to a smaller number of destinations + than is NR (although SDR route computation may be invoked more + frequently). + + Under no circumstances is computational complexity allowed to become + exponential (for either the NR or SDR component). + +2.1.3 Bandwidth Overhead + + The bandwidth consumed by routing information distribution should be + limited. However, the possible use of data compression techniques + 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 information. + + While storage and bandwidth overhead may be interrelated, if + incremental updates are used then bandwidth overhead is negligible in + the steady state (no changes in topology), and is independent of the + storage overhead. In other words, use of incremental updates + constrains the bandwidth overhead to the dynamics of the internet. + Therefore, improvements in stability of the physical links, combined + with techniques to dampen the effect of topological instabilities, + will make the bandwidth overhead even less important. + +2.2 Aggregation + + Aggregation and abstraction of routing and forwarding information + provides a very powerful mechanism for satisfying storage, + computational, and bandwidth constraints. The ability to aggregate, + and subsequently abstract, routing and forwarding information is + + + +Estrin, Rekhter & Hotz [Page 6] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + + essential to the scaling of 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 with respect to the NR component, since the + NR component must be capable of providing routes to all or almost all + reachable destinations. + + At the same time, since preserving each domain's independence and + autonomy is one of the crucial requirements of inter-domain routing, + the architecture must strive for the maximum flexibility of its + aggregation scheme, i.e., impose as few preconditions, and as little + global coordination, as possible on the participating domains. + + The Routing Information Base (RIB) carries three types of + information: (1) topology (i.e., the interconnections between domains + or groups of domains), (2) network layer reachability, and (3) + transit constraint. Aggregation of routing information should + provide a reduction of all three components. Aggregation of + forwarding information will follow from reachability information + aggregation. + + Clustering (by forming routing domain confederations) serves the + following aggregation functions: (1) to hide parts of the actual + physical topology, thus abstracting topological information, (2) to + combine a set of reachable destination entities into a single entity + and reduce storage overhead, and (3) to 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.). + + + + + + + + + + + + +Estrin, Rekhter & Hotz [Page 7] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + + 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 in + order to take advantage of some special TOS connectivity to, or even + through, USC. Whereas, someone else at Digital Equipment Corporation + might see information at the level of the California Educational + Institutions Confederation, and know only 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, i.e., 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; 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 above examples describe cases where overlap consists of a single + domain, there may be other cases where multiple domains overlap. As + an example 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 it 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 above examples illustrate a + situation where confederations overlap, and it is necessary to + control the traffic traversing the overlapping resources. + + While flexible aggregation should be accommodated in any inter-domain + architecture, the extent to which this feature is exploited will have + direct a effect on the scalability associated with aggregation. At + the same time, the exploitation of this feature depends on the way + addresses are assigned. Specifically, scaling associated with + forwarding information depends heavily on the assumption that there + will be general correspondence between the hierarchy of address + registration authorities, and the way routing domains and routing + domain confederations are organized (see Section 2.6). + + + + +Estrin, Rekhter & Hotz [Page 8] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + +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 enable each domain to select a particular + route among multiple routes to the same destination. To maintain + 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 made available to it by its + neighbors. This is really just a corollary to the above; i.e., 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 + + The architecture should not require all domains within an internet to + reveal their connectivity and transit constraints to each other. + Domains should be able to enforce their transit policies while + limiting the advertisement of their policy and connectivity + information as much as possible; such advertisement will be driven by + a "need to know" criteria. Moreover, advertising a transit policy to + domains that can not use this policy will increase the amount of + routing information that must be stored, processed, and propagated. + Not only may it be impractical for a router to maintain full inter- + domain topology and policy information, it may not be permitted to + + + +Estrin, Rekhter & Hotz [Page 9] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + + obtain this information. + +2.3.2 Policies Not Supported + + In this and previous papers we have argued that a global inter-domain + routing architecture should support a wide range of policies. In + this section we identify several types of policy that we explicitly + do not propose to support. In general our reasoning is pragmatic; we + think such policy types are either very expensive in terms of + overhead, or may lead to routing instabilities. + + 1. 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). + + 2. 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. + + 3. 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. + + 4. 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.]. + + + +Estrin, Rekhter & Hotz [Page 10] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + +2.4 Support for TOS Routing + + Throughout this document we refer to support for type of service + (TOS) routing. There is a great deal of research and development + activity currently underway to explore network architectures and + protocols for high-bandwidth, multimedia traffic. Some of this + traffic is delay sensitive, while some requires high throughput. It + is unrealistic to assume that a single communication fabric will be + deployed homogeneously across the internet (including all + metropolitan, regional, and backbone networks) that will support all + types of traffic uniformly. 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 is 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 is not + practical to assume that instantaneous resource availability will be + known at all remote points in the global internet. Rather, once a + TOS route has been identified, an application requiring 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 implies adaptability only during the route + selection process. Once a route is selected, it is not going to be a + 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 in + 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 + + + +Estrin, Rekhter & Hotz [Page 11] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + + 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. + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Estrin, Rekhter & Hotz [Page 12] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + +3.0 Design Choices for Node Routing (NR) + + This section addresses 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 + is subject to different constraints and is used for the complementary + SDR component. + +3.1 Overview of NR + + 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. 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). Such routes lend themselves to distributed route + computation and installation procedures. + + Routes that are installed in routers, and information that was used + by the routers to compute these routes, 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. The NR + component 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. + + + + +Estrin, Rekhter & Hotz [Page 13] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + + 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. "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 + + Given that a NR component based on hop-by-hop routing is needed to + provide scalable, efficient inter-domain routing, the remainder of + this section considers the fundamental design choices for the NR + routing algorithm. + + Typically the debate surrounding routing algorithms focuses on link + state and distance vector protocols. However, simple distance vector + protocols (i.e., Routing Information Protocol [Hedrick88]), do not + scale because of convergence problems. Improved distance vector + + + +Estrin, Rekhter & Hotz [Page 14] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + + protocols, such as those discussed in [Jaffee82, Zaumen91, Shin87], + have been developed to address this issue using synchronization + mechanisms or additional path information. In the case of inter- + domain routing, having additional path information is essential to + supporting policy. Therefore, the algorithms we consider for NR are + link state and one we call path vector (PV). Whereas the + characteristics of link state algorithms are generally understood + (for example, [Zaumen 91]), we must digress from our evaluation + discussion to describe briefly the newer concept of the PV algorithm + [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 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.]. + + The routing algorithm employed by PV bears a certain resemblance to + the traditional Bellman-Ford routing algorithm in the sense that each + border router advertises the destinations it can reach to its + neighboring BRs. However,the PV routing algorithm augments the + advertisement of reachable destinations with information that + describes various properties of the paths to these destinations. + + This information is expressed in terms of path attributes. To + emphasize the tight coupling between the reachable destinations and + properties of the paths to these destinations, PV defines a route as + a pairing between a destination and the attributes of the path to + that destination. Thus the name, path-vector protocol, where a BR + receives from its neighboring BR a vector 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, is carried in a + special path attribute which records the sequence of routing domains + through which the reachability information has passed. Suppression + of routing loops is implemented via this special path attribute, in + contrast to LS and distance vector which use a globally-defined + monotonically-increasing metric for route selection [Shin87]. + + Because PV does not require all routing domains to have homogeneous + + + +Estrin, Rekhter & Hotz [Page 15] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + + criteria (policies) for route selection, route selection policies + used by one routing domain are not necessarily known to other routing + domains. To maintain the maximum degree of autonomy and independence + between routing domains, each domain which participates in PV may + have its own view of what constitutes an optimal route. This view is + based solely on local route selection policies and the information + carried in the path attributes of a route. PV standardizes only the + results of the route selection procedure, while allowing the + selection policies that affect the route selection to be non-standard + [Footnote: This succinct observation is attributed to Ross Callon + (Digital Equipment Corporation).]. + +3.3 Complexity + + Given the above description of PV algorithms, we can compare them to + LS algorithms in terms of the three complexity parameters defined + earlier. + +3.3.1 Storage Overhead + + Without any aggregation of routing information, and ignoring storage + overhead associated with 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 + information, no transit constraints, a single homogeneous route + selection policy across all the domains, and a single TOS, requires 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 information that must be stored by + each domain. If the number of policies advertised grows with the + number of domains, then the storage could become unsupportable. In + contrast, support for heterogeneous route selection policies has no + effect on the storage complexity of the PV scheme (aside from simply + storing the local policy information). The presence of transit + constraints in PV results in a restricted distribution of routing + information, thus further reducing storage overhead. In contrast, + with LS no such reduction is possible since each domain must know + every other domain's transit policies. Finally, some of the transit + constraints (e.g., path sensitive constraints) can be expressed in a + more concise form in PV (see aggregation discussion below). + + The ability to further restrict storage overhead is facilitated by + the PV routing algorithm, where route computation precedes routing + + + +Estrin, Rekhter & Hotz [Page 16] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + + information dissemination, and only routing information associated + with the routes selected by a domain is distributed to adjacent + domains. In contrast, route selection with LS is decoupled from the + distribution of routing information, and has no effect on such + distribution. + + While theoretically routing information aggregation can be used to + reduce storage complexity in both LS and PV, only aggregation of + topological information would yield the same gain for both. + Aggregating transit constraints with LS may result in either reduced + connectivity or less information reduction, as compared with PV. + Aggregating heterogeneous route selection policies in LS is highly + problematic, at best. In PV, route selection policies are not + distributed, thus making aggregation of route selection policies a + 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 of PV) is the + critical functionality provided by SDR.]. + + Support for multiple TOSs has the same impact on storage overhead for + both LS and for PV. + + Potentially the LS FIB may be smaller if routes are computed at each + node on demand. However, the gain of such a scheme depends heavily + on the traffic patterns, memory size, and caching strategy. If there + is not a high degree of locality, severely degraded performance can + result due to excessive overall computation time and excessive + computation delay when forwarding packets to a new destination. If + demand driven route computation is not used for LS, then the size of + the FIB would be the same for both LS and PV. + + + + + + + + + + + + + + + + + +Estrin, Rekhter & Hotz [Page 17] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + +3.3.2 Route Computation Complexity + + Even if all domains employ exactly the same route selection policy, + computational complexity of PV is smaller than that of LS. The 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 insure that a routing loop + has not been created.]. Whereas, conventional LS computation + requires execution of an SPF algorithm such as Dijkstra's. + + With PV, topology changes only result in the recomputation of routes + affected by these changes, which is more efficient than complete + recomputation. However, because of the inclusion of full path + information with each distance vector, the effect of a topology + change may propagate farther than in traditional distance vector + algorithms. On the other hand, the number of affected domains will + still be smaller with PV than with conventional LS hop-by-hop + routing. With PV, only those domains whose routes are affected by + the changes have to recompute, while with conventional LS hop-by-hop + routing all domains must recompute. While it is also possible to + employ partial recomputation with LS (i.e., when topology changes, + only the affected routes are recomputed), "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]). However these checks are + much simpler than executing a full SPF algorithm. + + Support for heterogeneous route selection policies has serious + implications for the computational complexity. The major problem + with supporting heterogeneous route selection policies with LS is the + computational complexity of the route selection itself. + Specifically, we are 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. In contrast, PV allows each domain to make + its route selection autonomously, based only on local policies. + Therefore support for dissimilar route selection policies has no + negative implications for the complexity of route computation in PV. + Similarly, providing support for path-sensitive transit policies in + LS implies exponential computation, while in PV such 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, so + is reduced computational complexity. While similar arguments may be + made for LS, the aggregation capabilities that can be achieved with + LS are more problematic because of LS' reliance on consistent + + + +Estrin, Rekhter & Hotz [Page 18] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + + topology maps at each node. It is also not clear what additional + computational complexity will be associated with aggregation of + transit constraints and heterogeneous route selection policies in LS. + +3.3.3 Bandwidth Overhead + + PV routing updates include fully-expanded information. A complete + route for each supported TOS is advertised. In LS, TOS only + contributes a factor increase per link advertised, which is much less + than the number of complete routes. Although TOSs may be encoded + more efficiently with LS than with PV, link state information is + flooded to all domains, while with PV, routing updates are + distributed only to the domains that actually use them. Therefore, + it is difficult to make a general statement about which scheme + imposes more bandwidth overhead, all other factors being equal. + + Moreover, this is perhaps really not an important difference, since + we are more concerned with the number of messages than with the + number of bits (because of compression and greater link bandwidth, as + well as the increased physical stability of links). + +3.4 Aggregation + + Forming confederations of domains, for the purpose of consistent, + hop-by-hop, LS route computation, requires that domains within a + confederation have consistent policies. In addition, LS + confederation 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 as a result of using an inconsistent map of + the network at different domains. Therefore, the use of + confederations with hop-by-hop LS is limited because 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 the use of full path information. + Consistent network maps are not 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, thus providing + the extreme flexibility that is crucial for the overall scaling and + extensibility of the architecture. + + In summary, aggregation is essential to achieve acceptable complexity + + + +Estrin, Rekhter & Hotz [Page 19] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + + 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), by itself, can be + supported by either LS or PV. However, the associated complexities + of supporting transit policy constraints are noticeably higher for LS + than for PV. This is due to the need to flood all transit policies + with LS, where with PV transit policies are controlled via restricted + distribution of routing information. The latter always imposes less + overhead than flooding. + + While all of the transit constraints that can be supported with LS + can be supported with PV, the reverse is not true. In other words, + 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 that are based on hierarchical relations between domains, + while support for such policies is straightforward with PV. + + As indicated above, support for heterogeneous route selection + policies, in view of its computational and storage complexity, is + impractical with LS hop-by-hop routing. In contrast, PV 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 hinges on the ability of all + domains to have exactly the same information; this clearly + contradicts the notion of selective information hiding. That is, 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 the use of LS in conjunction with + SDR. Therefore there is some preference for using LS with NR. + However, there are several reasons why NR and SDR would not use + exactly the same routing information, even if they did use the same + algorithm. Moreover, there are several opportunities for unifying + the management (distribution and storage) of routing and forwarding + information, even if dissimilar algorithms are used. + + + +Estrin, Rekhter & Hotz [Page 20] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + + In considering the differences between NR and SDR we must address + several areas: + + 1. 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. + + 2. Route computation algorithm: It is not 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. + + 3. Forwarding information: The use of dissimilar route computation + algorithms does not preclude common handling of packet + forwarding. Even if LS were used for NR, the requirement would + be the same, i.e., that the forwarding agent can determine + whether to use a 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, these benefits do not + dominate the other factors as discussed before. + + + + + + + + + + + + + + + + + + + + + + + +Estrin, Rekhter & Hotz [Page 21] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + +3.8 Summary + + Given the performance complexity issues associated with global + routing, aggregation of routing information is essential; at the same + time we have 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 that are carried along with a route express a variety of + routing policies, and make explicit the entire route to the + destination. With aggregation, this is a superset of the domains + that form the path to the destination. + + + + + + + + + + + + + + + + + + + +Estrin, Rekhter & Hotz [Page 22] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + +4.0 Source-demand routing (SDR) + + Inter-domain routers participating in the SDR component forward + packets according to routing information computed and installed by + the domain that originates the traffic (source routing domain). + + It is important to realize that requiring route installation by the + source routing domain is not a matter of choice, but rather a + necessity. If a particular route is used by a small number of + domains (perhaps only one) then it is more appropriate to have the + source compute and install the special route instead of burdening the + intermediate nodes with the task of looking for and selecting a route + with the specialized requirements. In addition, if the demand for + the route is unpredictable, and thus can be determined only by the + source, it should be up to the source to install the route. + + In general, information that is used by source routing domains for + computing source-demand routes reflects administrative (but not + operational) status of the routing facilities (i.e., configured + topology and policy) [Footnote: If SDR uses NR information then + operational status could be considered in some route selection.]. + Consequently, it is possible for a source routing domain to compute a + route that is not operational at route installation time. The SDR + component attempts to notify the source domain of failures when route + installation is attempted. Similarly, the SDR component provides + mechanisms for the source routing domain to be notified of failures + along previously-installed active routes. In other words, the SDR + component performs routing that is adaptive to topological changes; + however, the adaptability is achieved as a consequence of the route + installation and route management mechanisms. This is different from + the NR component, where status changes are propagated and + incorporated by nodes as soon as possible. Therefore, to allow + faster adaptation to changes in the operational status of routing + facilities, the SDR component allows the source domain to switch to a + route computed by the NR component, if failure along the source- + demand route is detected (either during the route installation phase, + or after the route is installed), and if policy permits use of the NR + route. + + The NR component will group domains into confederations to achieve + its scaling goals (see [IDRP91]). In contrast, SDR will allow an + AD-level route to be used by an individual domain without allowing + use by the entire confederation to which the domain belongs. + Similarly, a single transit domain may support a policy or special + TOS that is not supported by other domains in its confederation(s). + In other words, the architecture uses SDR to support non- + hierarchical, non-aggregated policies where and when needed. + Consequently, SDR by itself does not have the scaling properties of + + + +Estrin, Rekhter & Hotz [Page 23] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + + NR. In compensation, SDR does not require a complete, global domain + map if portions of the world are never traversed or communicated + with. As a result of the looser routing structure, SDR does not + guarantee that a participating source routing domain will always have + sufficient information to compute a route to a destination. In + addition, if the domain does have sufficient information, it is + possible that the quantity may be large enough to preclude storage + and/or route computation in a timely fashion. However, despite the + lack of guarantees, it is a goal of the architecture to provide + efficient methods whereby sources can obtain the information needed + to compute desired routes [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.]. + + Essential to SDR is the assumption that the routes installed on + demand will be used sparingly. The architecture assumes that at any + given moment the set of all source-demand routes installed in an + internet forms a small fraction of the total number of source-demand + routes that can potentially be installed by all the routing domains. + It is an assumption of the architecture 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 that the scaling properties of the SDR component are comparable + with the scaling properties of the NR component. The NR component + achieves this property as a result of hierarchy. + + Note that the above requirement does not imply that only a few + domains can participate in SDR, or that routes installed by the SDR + component must have short life times. What the requirement does + imply, is that the product of the number of routes specified by + domains that participate in SDR, times the average SDR-route life + time, is bounded. For example, the architecture allows either a + small number of SDR routes with relatively long average life times, + or a large number of SDR routes with relatively short average life + times. But the architecture clearly prohibits a large number of SDR + routes with relatively long average life times. The number of SDR + routes is a function of the number of domains using SDR routes and + the number of routes used per source domain. + + In summary, SDR is well suited for traffic that (1) is not widely- + used enough (or is not sufficiently predictable or steady) to justify + computation and maintenance by the NR component, and (2) whose + duration is significantly longer than the time it takes to perform + the route installation procedure. + + + +Estrin, Rekhter & Hotz [Page 24] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + + The architecture does not require all domains in the Internet to + participate in SDR. Therefore, issues of scalability (with respect + to the size of the Internet) become less crucial (though still + important) to the SDR component. Instead, the primary focus of the + SDR component is shifted towards the ability to compute routes that + satisfy specialized requirements, where we assume that the total + number of domains requiring special routes simultaneously through the + same part of the network is small relative to the total population. + +4.1 Path Vector vs. Link State for SDR + + It is feasible to use either a distance vector or link state method + of route computation along with source routing. One could imagine, + for instance, a protocol like BGP in which the source uses the full + AD path information it receives in routing updates to create a source + route. Such a protocol could address some of the deficiencies + identified with distance vector, hop-by-hop designs. However, we opt + against further discussion of such a protocol because there is less + to gain by using source routing without also using a link state + scheme. The power of source routing, in the context of inter-AD + policy routing, is in giving the source control over the entire + route. This goal cannot be realized fully when intermediate nodes + control which legal routes are advertised to neighbors, and therefore + to a source. + + In other words, intermediate nodes should be able to preclude the use + of a route by expressing a transit policy, but if a route is not + precluded (i.e., is legal according to all ADs in the route), the + route should be made available to the source independent of an + intermediate domain's preferences for how its own traffic flows. + + Therefore, the SDR component employs an IDPR-like architecture in + which 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 have alleviated the pressure to + aggregate SDR forwarding information; the large percentage of inter- + domain traffic carried, simultaneously, by any particular border + router will be forwarded using aggregated NR forwarding information. + However, the use of NR does not address the other major scaling + problem associated with SDR: that of distributing, storing, and + computing over a complete domain-level topology map. In this section + we describe promising opportunities for improving the scaling + properties of SDR routing information distribution, storage, and + + + +Estrin, Rekhter & Hotz [Page 25] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + + computation. + + Note that we do not propose to solve this problem in the same way + that we solve it for NR. A priori abstraction will not be employed + since different domains may require different methods of abstracting + the same routing information. For example, if we aggregate routing + information of domains that do not share the same policy and TOS + characteristics (i.e., services), then outside of the aggregate, only + those services that are offered by all domains in the aggregate will + be 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 are not offered by an + aggregate, full information about the component domains is used to + construct a route through those domains that do support the + particular characteristics. Consequently, we need some other, more + flexible, means of reducing the amount of information distributed and + held. We address two issues in turn: distribution of configured + topology and policy information, and distribution of dynamic status + information. + +4.2.1 Configured Information + + Information about the existence of inter-domain links, and policies + maintained by domains, changes slowly over time. This is referred to + as configured information. In the current IDPR specification + complete, global, configuration information is kept by a route server + in each domain. Route servers (RS) are the entities that compute + source routes. On startup a RS can download the connectivity + database from a neighbor RS; as domains, inter-domain links, or + policies change, the changes are flooded to a RS in each domain. + + We have not yet specified the exact mechanisms for distributing + configured connectivity information for SDR. However, unlike the + current IDPR specification, the SDR component will not flood all + configured information globally. Several alternate methods for + organizing and distributing information are under investigation. + + Configured information may be regularly distributed via an out-of- + band channel, e.g., CD/ROM. In a similar vein, this information + could be posted in several well-known locations for retrieval, e.g., + via FTP. Between these "major" updates, aggregated collections of + changes may be flooded globally. Moreover, limited flooding (e.g., + by hop-count) could be used as appropriate to the "importance" of the + change; while a policy change in a major backbone may still be + flooded globally, a new inter-regional link may be flooded only + within those regions, and information about an additional link to a + non-transit domain may not be available until the next regularly- + + + +Estrin, Rekhter & Hotz [Page 26] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + + scheduled "major" distribution. + + Changes that are not distributed as they occur will not necessarily + be discovered. However, a route server may learn pertinent + information by direct query of remote servers, or through error + messages resulting from traffic sent along failed routes. Complete + global flooding may be avoided by using some combination of these + mechanisms. + + Even if an initial implementation uses a simple global flood, we must + study the problem of structuring connectivity information such that + it can be retrieved or distributed in a more selective manner, while + still allowing sources to discover desired routes. For example, we + imagine RSs requesting filtered information from each other. How the + RSs should define filters that will get enough information to find + special routes, while also effectively limiting the information, is + an open question. Again, the question is how to effectively + anticipate and describe what information is needed in advance of + computing the route. + + The essential dilemma is that networks are not organized in a nicely + geographical or topologically consistent manner (e.g., it is not + effective to ask for all networks going east-west that are within a + certain north-south region of the target), hence a source domain does + not know what information 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 + information so that the potential paths that are most likely to be + useful are explored first, thereby reducing the time required for + route computation. + + One promising approach organizes information 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 information in a + manner useful for computing source-routes, and provides an index, + namely the destination, which facilitates on-demand reference and + retrieval of information pertinent to a particular route computation. + At this point, it is not clear how route fragments will affect SDR's + ability to discover non-hierarchical routes. + + + + +Estrin, Rekhter & Hotz [Page 27] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + +4.2.2 Dynamic Status Information + + Assuming a technique for global or partial distribution of configured + information, a second issue is whether, and how, to distribute + dynamic status information (i.e., whether an inter-domain connection + is up or down). + + In the current version of IDPR, dynamic status information is flooded + globally in addition to configuration information. We propose to + distribute status information based strictly on locality. First, + dynamic information will be advertised within a small hop-count + radius. This simple and low-overhead mechanism exploits topological + locality. In addition to flooding status updates to nearby nodes, we + also want to provide more accurate route information for long + distance communications that entails more than a few network hops. + Reverse path update (RPU) is a mechanism for sending dynamic status + information to nodes that are outside the k-hop radius used for + updates, but that nevertheless would obtain better service (fewer + failed setups) by having access to the dynamic information [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 distribution of 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; in any case + the overhead of the information about other links will be minimal. + + In this way, sources will receive status information from regions of + the network through which they maintain active routes, even if those + regions are more than k hops away. Using such a scheme, k could be + small to maximize efficiency, and RPU could be used to reduce the + incidence of failed routes resulting from inaccurate status + information. 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 + information). In such situations, flooding information to the source + of the long route would be inefficient because k would have to be + equal to the length of the route, and in almost all cases, the + percentage of nodes that would use the information decreases + significantly with larger k. + +4.3 Source-Demand Route Management + + SDR may be built either on top of the network layer supported by the + NR component, or in parallel with it. SDR forwarding will be + + + +Estrin, Rekhter & Hotz [Page 28] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + + supported via two techniques: loose source-routing and route setup. + + The first technique, loose source-routing, would allow the originator + of a packet to specify a sequence of domains that the packet should + traverse on its path to a destination. Forwarding such a packet + within a domain, or even between domains within a confederation, + would be left to intra-domain routing. This avoids per-connection + state and supports transaction traffic. + + The second technique, route setup, will be based on mechanisms + developed for IDPR and described in [IDPR90]. It is well suited to + conversations that persist significantly longer than a round-trip- + time. The setup protocol defines packet formats and the processing + of route installation request packets (i.e, setup packets). When a + source generates a setup packet, the first border router along the + specified source route checks the setup request, and if accepted, + installs routing information; this information includes a path ID, + the previous and next hops, and whatever other accounting-related + information the particular domain requires. The setup packet is + 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 is 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. That path ID is used to locate the appropriate next-hop + information for each packet. + + Border routers that support both the NR and the SDR components, must + be able to determine what forwarding mechanism to use. That is, when + presented with a network layer PDU, such a BR should be able to make + an unambiguous decision about whether forwarding of that PDU should + be handled by the NR or the SDR component. Discrimination mechanisms + are dependent 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 are forwarded to 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 are forwarded to + 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. + + + + +Estrin, Rekhter & Hotz [Page 29] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + + 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 a 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. + + + +Estrin, Rekhter & Hotz [Page 30] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + + In summary, when a route is first installed, the source has several + options (which are represented by flags in the route setup packet): + + 1. If an NR route is available that satisfies all local policy + and TOS, then use it. Otherwise... + + 2. Indicate whether the source wants to allow the setup to + default to a NR route if the SDR route setup fails. + + 3. Request notification of mapping to a NR route. + + 4. Request additional configured information on failure. + + 5. Request addition to a notification list for resource + re-availability. + + 6. Allow data packets to be rerouted to a NR route when failure + happens after setup (so long as no policy is violated). + + 7. Request notification of a reroute of data packets. + + 8. Request additional configured information on failure notice + when the route is active. + + 9. Request addition to a notification list if an active route + fails. + + + + + + + + + + + + + + + + + + + + + + + + + +Estrin, Rekhter & Hotz [Page 31] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + +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: + + 1. 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. + + 2. 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. + + 3. 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. + + 4. 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; the latter + is needed to make the routing decision. We should consider + obtaining the network reachability and domain information in + a unified manner. + + + + + + + +Estrin, Rekhter & Hotz [Page 32] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + +5.1 Applicability to Various Network Layer Protocols + + The proposed architecture is designed to accommodate such existing + network layer protocols as IP ([Postel81]), CLNP ([ISO-473-88]), and + ST-II ([ST2-90]). In addition, we intend for this architecture to + support future network layer mechanisms, e.g., Clark and Jacobson's + proposal or Braden and Casner's Integrated Services IP. However on + principal we can not make sweeping guarantees in advance of the + mechanisms themselves. In any case, not all of the mentioned + protocols will be able to utilize all of the capabilities provided by + the architecture. 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. That is, not all + components of the architecture will have equal importance for + different network layer protocols. On the other hand, this + architecture is designed to serve the future global internetworking + environment. The extensive research and development currently + underway to implement and evaluate network mechanisms for different + types of service suggests that future networks will offer such + services. + + One of the fundamental issues in the proposed architecture is the + issue of 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 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.]. + + + + +Estrin, Rekhter & Hotz [Page 33] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + +5.2 Transition + + The proposed architecture is not intended for full deployment in the + short term future. We are proposing this architecture as a goal + towards which we can begin guiding our operational and research + investment over the next 5 years. + + At the same time, the architecture does not require wholesale + overhaul of the existing Internet. 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 of the architecture needed to support + SDR include 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. + + + + + + + + + + + + + + + + + + + + + + + + + +Estrin, Rekhter & Hotz [Page 34] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + +6.0 Conclusions and Future Work + + In summary, 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; 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. + +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. + + + + + + + + + + + + + + + + + + + + + + + + +Estrin, Rekhter & Hotz [Page 35] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + +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. + + + + + +Estrin, Rekhter & Hotz [Page 36] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + + [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". + + + + + + + +Estrin, Rekhter & Hotz [Page 37] + +RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 + + +Security Considerations + + Security issues are not discussed in this memo. + +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 + + + + + + + + + + + + + + + + + + + + +Estrin, Rekhter & Hotz [Page 38] +
\ No newline at end of file |