rfc1322.txt

来自「RFC 的详细文档！」· 文本 代码 · 共 1,352 行 · 第 1/5 页

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