rfc1992.txt

中、英文RFC文档大全打包下载完全版 .

Network Working Group                                      I. Castineyra
Request for Comments: 1992                                           BBN
Category: Informational                                       N. Chiappa
                                                           M. Steenstrup
                                                                     BBN
                                                             August 1996


                    The Nimrod Routing Architecture

Status of this Memo

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

Abstract

   We present a scalable internetwork routing architecture, called
   Nimrod.  The Nimrod architecture is designed to accommodate a dynamic
   internetwork of arbitrary size with heterogeneous service
   requirements and restrictions and to admit incremental deployment
   throughout an internetwork.  The key to Nimrod's scalability is its
   ability to represent and manipulate routing-related information at
   multiple levels of abstraction.

Table of Contents

   1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 2
   2. Overview of Nimrod . . . . . . . . . . . . . . . . . . . . . . . 3
     2.1 Constraints of the Internetworking Environment  . . . . . . . 3
     2.2 The Basic Routing Functions . . . . . . . . . . . . . . . . . 5
     2.3 Scalability Features  . . . . . . . . . . . . . . . . . . . . 6
       2.3.1 Clustering and Abstraction  . . . . . . . . . . . . . . . 6
       2.3.2 Restricting Information Distribution  . . . . . . . . . . 7
       2.3.3 Local Selection of Feasible Routes  . . . . . . . . . . . 8
       2.3.4 Caching . . . . . . . . . . . . . . . . . . . . . . . . . 8
       2.3.5 Limiting Forwarding Information . . . . . . . . . . . . . 8
   3. Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 8
     3.1 Endpoints   . . . . . . . . . . . . . . . . . . . . . . . . . 9
     3.2 Nodes and Adjacencies . . . . . . . . . . . . . . . . . . . . 9
     3.3 Maps  . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
       3.3.1 Connectivity Specifications  . . . . . . . . . . . . . . 10
     3.4  Locators  . . . . . . . . . . . . . . . . . . . . . . . . . 10
     3.5 Node Attributes  . . . . . . . . . . . . . . . . . . . . . . 11
       3.5.1 Adjacencies  . . . . . . . . . . . . . . . . . . . . . . 11
       3.5.2 Internal Maps  . . . . . . . . . . . . . . . . . . . . . 11
       3.5.3 Transit Connectivity . . . . . . . . . . . . . . . . . . 12



Castineyra, et. al.          Informational                      [Page 1]

RFC 1992              Nimrod Routing Architecture            August 1996


       3.5.4 Inbound Connectivity . . . . . . . . . . . . . . . . . . 12
       3.5.5 Outbound Connectivity  . . . . . . . . . . . . . . . . . 12
   4. Physical Realization  . . . . . . . . . . . . . . . . . . . . . 13
     4.1 Contiguity   . . . . . . . . . . . . . . . . . . . . . . . . 13
     4.2 An Example . . . . . . . . . . . . . . . . . . . . . . . . . 14
     4.3 Multiple Locator Assignment  . . . . . . . . . . . . . . . . 15
   5. Forwarding  . . . . . . . . . . . . . . . . . . . . . . . . . . 20
     5.1 Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
     5.2 Trust  . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
     5.3 Connectivity Specification (CSC) Mode  . . . . . . . . . . . 24
     5.4 Flow Mode  . . . . . . . . . . . . . . . . . . . . . . . . . 25
     5.5 Datagram Mode  . . . . . . . . . . . . . . . . . . . . . . . 25
     5.6 Connectivity Specification Sequence Mode . . . . . . . . . . 26
   6. Security Considerations . . . . . . . . . . . . . . . . . . . . 26
   7. References  . . . . . . . . . . . . . . . . . . . . . . . . . . 26
   7. Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . 27

1. Introduction

   Nimrod is a scalable routing architecture designed to accommodate a
   continually expanding and diversifying internetwork.  First suggested
   by Noel Chiappa, the Nimrod architecture has undergone revision and
   refinement through the efforts of the Nimrod working group of the
   IETF. In this document, we present a detailed description of this
   architecture.

   The goals of Nimrod are as follows:

   1. To support a dynamic internetwork of arbitrary size by
      providing mechanisms to control the amount of routing information
      that must be known throughout an internetwork.

   2. To provide service-specific routing in the presence of multiple
      constraints imposed by service providers and users.

   3. To admit incremental deployment throughout an internetwork.

   We have designed the Nimrod architecture to meet these goals.  The
   key features of this architecture include:

   1. Representation of internetwork connectivity and services in the
      form of maps at multiple levels of abstraction.

   2. User-controlled route generation and selection based on maps and
      traffic service requirements.

   3. User-directed packet forwarding along established paths.




Castineyra, et. al.          Informational                      [Page 2]

RFC 1992              Nimrod Routing Architecture            August 1996


   Nimrod is a general routing architecture that can be applied to
   routing both within a single routing domain and among multiple
   routing domains.  As a general internetwork routing architecture
   designed to deal with increased internetwork size and diversity,
   Nimrod is equally applicable to both the TCP/IP and OSI environments.

2. Overview of Nimrod

   Before describing the Nimrod architecture in detail, we provide an
   overview.  We begin with the internetworking requirements, followed
   by the routing functions, and concluding with Nimrod's scaling
   characteristics.

2.1 Constraints of the Internetworking Environment

   Internetworks are growing and evolving systems, in terms of number,
   diversity, and interconnectivity of service providers and users, and
   therefore require a routing architecture that can accommodate
   internetwork growth and evolution.  A complicated mix of factors such
   as technological advances, political alliances, and service supply
   and demand economics will determine how an internetwork will change
   over time.  However, correctly predicting all of these factors and
   all of their effects on an internetwork may not be possible.  Thus,
   the flexibility of an internetwork routing architecture is its key to
   handling unanticipated requirements.

   In developing the Nimrod architecture, we first assembled a list of
   internetwork environmental constraints that have implications for
   routing.  This list, enumerated below, includes observations about
   the present Internet; it also includes predictions about
   internetworks five to ten years in the future.

   1. The Internet will grow to include O(10^9) networks.

   2. The number of internetwork users may be unbounded.

   3. The capacity of internetwork resources is steadily increasing but
      so is the demand for these resources.

   4. Routers and hosts have finite processing capacity and finite
      memory, and networks have finite transmission capacity.

   5. Internetworks comprise different types of communications media --
      including wireline, optical and wireless, terrestrial and
      satellite, shared multiaccess and point-to-point -- with different
      service characteristics in terms of throughput, delay, error and
      loss distributions, and privacy.




Castineyra, et. al.          Informational                      [Page 3]

RFC 1992              Nimrod Routing Architecture            August 1996


   6. Internetwork elements -- networks, routers, hosts, and processes --
      may be mobile.

   7. Service providers will specify offered services and restrictions on
      access to those services.  Restrictions may be in terms of when a
      service is available, how much the service costs, which users may
      subscribe to the service and for what purposes, and how the user
      must shape its traffic in order to receive a service guarantee.

   8. Users will specify traffic service requirements which may vary
      widely among sessions.  These specifications may be in terms of
      requested qualities of service, the amounts they are willing to pay
      for these services, the times at which they want these services,
      and the providers they wish to use.

   9. A user traffic session may include m sources and n destinations,
      where m, n > or = 1.

   10. Service providers and users have a synergistic relationship.  That
       is, as users develop more applications with special service
       requirements, service providers will respond with the services to
       meet these demands.  Moreover, as service providers deliver more
       services, users will develop more applications that take advantage
       of these services.

   11. Support for varied and special services will require more
       processing, memory, and transmission bandwidth on the part of both
       the service providers offering these services and the users
       requesting these services.  Hence, many routing-related activities
       will likely be performed not by routers and hosts but rather by
       independent devices acting on their behalf to process, store, and
       distribute routing information.

   12. Users requiring specialized services (e.g., high guaranteed
       throughput) will usually be willing to pay more for these services
       and to incur some delay in obtaining them.

   13. Service providers are reluctant to introduce complicated protocols
       into their networks, because they are more difficult to manage.

   14. Vendors are reluctant to implement complicated protocols in their
       products, because they take longer to develop.

   Collectively, these constraints imply that a successful internetwork
   routing architecture must support special features, such as service-
   specific routing and component mobility in a large and changing
   internetwork, using simple procedures that consume a minimal amount
   of internetwork resources.  We believe that the Nimrod architecture



Castineyra, et. al.          Informational                      [Page 4]

RFC 1992              Nimrod Routing Architecture            August 1996


   meets these goals, and we justify this claim in the remainder of this
   document.

2.2 The Basic Routing Functions

   The basic routing functions provided by Nimrod are those provided by
   any routing system, namely:

   1. Collecting, assembling, and distributing the information necessary
      for route generation and selection.

   2. Generating and selecting routes based on this information.

   3. Establishing in routers information necessary for forwarding
      packets along the selected routes.

   4. Forwarding packets along the selected routes.

   The Nimrod approach to providing this routing functionality includes
   map distribution according to the "link-state" paradigm, localization
   of route generation and selection at traffic sources and
   destinations, and specification of packet forwarding through path
   establishment by the sources and destinations.

   Link-state map distribution permits each service provider to have
   control over the services it offers, through both distributing
   restrictions in and restricting distribution of its routing
   information.  Restricting distribution of routing information serves
   to reduce the amount of routing information maintained throughout an
   internetwork and to keep certain routing information private.
   However, it also leads to inconsistent routing information databases
   throughout an internetwork, as not all such databases will be
   complete or identical.  We expect routing information database
   inconsistencies to occur often in a large internetwork, regardless of
   whether privacy is an issue.  The reason is that we expect some
   devices to be incapable of maintaining the complete set of routing
   information for the internetwork.  These devices will select only
   some of the distributed routing information for storage in their
   databases.

   Route generation and selection, based on maps and traffic service
   requirements, may be completely controlled by the users or, more
   likely, by devices acting on their behalf and does not require global
   coordination among routers.  Thus these devices may generate routes
   specific to the users' needs, and only those users pay the cost of
   generating those routes.  Locally-controlled route generation allows
   incremental deployment of and experimentation with new route
   generation algorithms, as these algorithms need not be the same at



Castineyra, et. al.          Informational                      [Page 5]

RFC 1992              Nimrod Routing Architecture            August 1996


   each location in an internetwork.

   Packet forwarding according to paths may be completely controlled by
   the users or the devices acting on their behalf.  These paths may be
   specified in as much detail as the maps permit.  Such packet
   forwarding provides freedom from forwarding loops, even when routers
   in a path have inconsistent routing information.  The reason is that
   the forwarding path is a route computed by a single device and based
   on routing information maintained at a single device.

   We note that the Nimrod architecture and Inter-Domain Policy Routing
   (IDPR) [1] share in common link-state routing information
   distribution, localized route generation and path-oriented message
   forwarding.  In developing the Nimrod architecture, we have drawn
   upon experience gained in developing and experimenting with IDPR.

2.3 Scalability Features

   Nimrod must provide service-specific routing in arbitrarily large
   internetworks and hence must employ mechanisms that help to contain
   the amount of internetwork resources consumed by the routing
   functions.  We provide a brief synopsis of such mechanisms below,
   noting that arbitrary use of these mechanisms does not guarantee a
   scalable routing architecture.  Instead, these mechanisms must be
   used wisely, in order enable a routing architecture to scale with
   internetwork growth.

2.3.1 Clustering and Abstraction

   The Nimrod architecture is capable of representing an internetwork as
   clusters of entities at multiple levels of abstraction.  Clustering
   reduces the number of entities visible to routing.  Abstraction
   reduces the amount of information required to characterize an entity
   visible to routing.

   Clustering begins by aggregating internetwork elements such as hosts,
   routers, and networks according to some predetermined criteria.
   These elements may be clustered according to relationships among
   them, such as "managed by the same authority", or so as to satisfy
   some objective function, such as "minimize the expected amount of
   forwarding information stored at each router".  Nimrod does not
   mandate a particular cluster formation algorithm.

   New clusters may be formed by clustering together existing clusters.
   Repeated clustering of entities produces a hierarchy of clusters with
   a unique universal cluster that contains all others.  The same
   clustering algorithm need not be applied at each level in the
   hierarchy.



Castineyra, et. al.          Informational                      [Page 6]

RFC 1992              Nimrod Routing Architecture            August 1996


   All elements within a cluster must satisfy at least one relation,
   namely connectivity.  That is, if all elements within a cluster are
   operational, then any two of them must be connected by at least one
   route that lies entirely within that cluster.  This condition
   prohibits the formation of certain types of separated clusters, such
   as the following.  Suppose that a company has two branches located at
   opposite ends of a country and that these two branches must
   communicate over a public network not owned by the company.  Then the
   two branches cannot be members of the same cluster, unless that
   cluster also includes the public network connecting them.

   Once the clusters are formed, their connectivity and service
   information is abstracted to reduce the representation of cluster
   characteristics.  Example abstraction procedures include elimination
   of services provided by a small fraction of the elements in the
   cluster or expression of services in terms of average values.  Nimrod
   does not mandate a particular abstraction algorithm.  The same
   abstraction algorithm need not be applied to each cluster, and
   multiple abstraction algorithms may be applied to a single cluster.

   A particular combination of clustering and abstraction algorithms
   applied to an internetwork results in an organization related to but
   distinct from the physical organization of the component hosts,
   routers, and networks.  When a clustering is superimposed over the
   physical internetwork elements, the cluster boundaries may not
   necessarily coincide with host, router, or network boundaries.
   Nimrod performs its routing functions with respect to the hierarchy
   of entities resulting from clustering and abstraction, not with
   respect to the physical realization of the internetwork.  In fact,
   Nimrod need not even be aware of the physical elements of an
   internetwork.

2.3.2 Restricting Information Distribution

   The Nimrod architecture supports restricted distribution of routing
   information, both to reduce resource consumption associated with such
   distribution and to permit information hiding.  Each cluster