rfc1992.txt

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

   determines the portions of its routing information to distribute and
   the set of entities to which to distribute this information.
   Moreover, recipients of routing information are selective in which
   information they retain.  Some examples are as follows.  Each cluster
   might automatically advertise its routing information to its siblings
   (i.e., those clusters with a common parent cluster).  In response to
   requests, a cluster might advertise information about specific
   portions of the cluster or information that applies only to specific
   users.  A cluster might only retain routing information from clusters
   that provide universal access to their services.




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


2.3.3 Local Selection of Feasible Routes

   Generating routes that satisfy multiple constraints is usually an
   NP-complete problem and hence a computationally intensive procedure.
   With Nimrod, only those entities that require routes with special
   constraints need assume the computational load associated with
   generation and selection of such routes.  Moreover, the Nimrod
   architecture allows individual entities to choose their own route
   generation and selection algorithms and hence the amount of resources
   to devote to these functions.

2.3.4 Caching

   The Nimrod architecture encourages caching of acquired routing
   information in order to reduce the amount of resources consumed and
   delay incurred in obtaining the information in the future.  The set
   of routes generated as a by-product of generating a particular route
   is an example of routing information that is amenable to caching;
   future requests for any of these routes may be satisfied directly
   from the route cache.  However, as with any caching scheme, the
   cached information may become stale and its use may result in poor
   quality routes.  Hence, the routing information's expected duration
   of usefulness must be considered when determining whether to cache
   the information and for how long.

2.3.5 Limiting Forwarding Information

   The Nimrod architecture supports two separate approaches for
   containing the amount of forwarding information that must be
   maintained per router.  The first approach is to multiplex, over a
   single path (or tree, for multicast), multiple traffic flows with
   similar service requirements.  The second approach is to install and
   retain forwarding information only for active traffic flows.

   With Nimrod, the service providers and users share responsibility for
   the amount of forwarding information in an internetwork.  Users have
   control over the establishment of paths, and service providers have
   control over the maintenance of paths.  This approach is different
   from that of the current Internet, where forwarding information is
   established in routers independent of demand for this information.

3. Architecture

   Nimrod is a hierarchical, map-based routing architecture that has
   been designed to support a wide range of user requirements and to
   scale to very large dynamic internets.  Given a traffic stream's
   description and requirements (both quality of service requirements
   and usage-restriction requirements), Nimrod's main function is to



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


   manage in a scalable fashion how much information about the
   internetwork is required to choose a route for that stream, in other
   words, to manage the trade-off between amount of information about
   the internetwork and the quality of the computed route.  Nimrod is
   implemented as a set of protocols and distributed databases.  The
   following sections describe the basic architectural concepts used in
   Nimrod.  The protocols and databases are specified in other
   documents.

3.1 Endpoints

   The basic entity in Nimrod is the endpoint.  An endpoint represents a
   user of the internetwork layer: for example, a transport connection.
   Each endpoint has at least one endpoint identifier (EID). Any given
   EID corresponds to a single endpoint.  EIDs are globally unique,
   relatively short "computer-friendly" bit strings---for example, small
   multiples of 64 bits.  EIDs have no topological significance
   whatsoever.  For ease of management, EIDs might be organized
   hierarchically, but this is not required.

   BEGIN COMMENT

      In practice, EIDs will probably have a second form, which we can
      call the endpoint label (EL). ELs are ASCII strings of unlimited
      length, structured to be used as keys in a distributed database
      (much like DNS names).  Information about an endpoint---for
      example, how to reach it---can be obtained by querying this
      distributed database using the endpoint's label as key.

   END COMMENT

3.2 Nodes and Adjacencies

   A node represents a region of the physical network.  The region of
   the network represented by a node can be as large or as small as
   desired: a node can represent a continent or a process running inside
   a host.  Moreover, as explained in section 4, a region of the network
   can simultaneously be represented by more than one node.

   An adjacency consists of an ordered pair of nodes.  An adjacency
   indicates that traffic can flow from the first node to the second.

3.3 Maps

   The basic data structure used for routing is the map.  A map
   expresses the available connectivity between different points of an
   internetwork.  Different maps can represent the same region of a
   physical network at different levels of detail.



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


   A map is a graph composed of nodes and adjacencies.  Properties of
   nodes are contained in attributes associated with them.  Adjacencies
   have no attributes.  Nimrod defines languages to specify attributes
   and to describe maps.

   Maps are used by routers to generate routes.  In general, it is not
   required that different routers have consistent maps.

   BEGIN COMMENT

      Nimrod has been designed so that there will be no routing loops
      even when the routing databases of different routers are not
      consistent.  A consistency requirement would not permit
      representing the same region of the internetwork at different
      levels of detail.  Also, a routing-database consistency
      requirement would be hard to guarantee in the very large internets
      Nimrod is designed to support.

   END COMMENT

   In this document we speak only of routers.  By "router" we mean a
   physical device that implements functions related to routing: for
   example, forwarding, route calculation, path set-up.  A given device
   need not be capable of doing all of these to be called a router.  The
   protocol specification document, see [2], splits these
   functionalities into specific agents.

3.3.1 Connectivity Specifications

   By connectivity between two points we mean the available services and
   the restrictions on their use.  Connectivity specifications are among
   the attributes associated with nodes.  The following are informal
   examples of connectivity specifications:

  o "Between these two points, there exists best-effort service with no
    restrictions."

  o "Between these two points, guaranteed 10 ms delay can be arranged for
    traffic streams whose data rate is below 1 Mbyte/sec and that have low
    (specified) burstiness."

  o "Between these two points, best-effort service is offered, as long as
    the traffic originates in and is destined for research organizations."

3.4 Locators

   A locator is a string of binary digits that identifies a location in
   an internetwork.  Nodes and endpoint are assigned locators.



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


   Different nodes have necessarily different locators.  A node is
   assigned only one locator.  Locators identify nodes and specify
   *where* a node is in the network.  Locators do *not* specify a path
   to the node.  An endpoint can be assigned more than one locator.  In
   this sense, a locator might appear in more than one location of an
   internetwork.

   In this document locators are written as ASCII strings that include
   colons to underline node structure: for example, a:b:c.  This does
   not mean that the representation of locators in packets or in
   databases will necessarily have something equivalent to the colons.

   A given physical element of the network might help implement more
   than one node---for example, a router might be part of two different
   nodes.  Though this physical element might therefore be associated
   with more than one locator, the nodes that this physical element
   implements have each only one locator.

   The connectivity specifications of a node are identified by a tuple
   consisting of the node's locator and an ID number.

   All map information is expressed in terms of locators, and routing
   selections are based on locators.  EIDs are *not* used in making
   routing decisions---see section 5.

3.5 Node Attributes

   The following are node attributes defined by Nimrod.

3.5.1 Adjacencies

   Adjacencies appear in maps as attributes of both the nodes in the
   adjacency.  A node has two types of adjacencies associated with it:
   those that identify a neighboring node to which the original node can
   send data to; and those that identivy a neighboring node that can
   send data to the original node.

3.5.2 Internal Maps

   As part of its attributes, a node can have internal maps.  A router
   can obtain a node's internal maps---or any other of the node's
   attributes, for that matter---by requesting that information from a
   representative of that node.  (A router associated with that node can
   be such a representative.)  A node's representative can in principle
   reply with different internal maps to different requests---for
   example, because of security concerns.  This implies that different
   routers in the network might have different internal maps for the
   same node.



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


   A node is said to own those locators that have as a prefix the
   locator of the node.  In a node that has an internal map, the
   locators of all nodes in this internal map are prefixed by the
   locator of the original node.

   Given a map, a more detailed map can be obtained by substituting one
   of the map's nodes by one of that node's internal maps.  This process
   can be continued recursively.  Nimrod defines standard internal maps
   that are intended to be used for specific purposes.  A node's
   "detailed map" gives more information about the region of the network
   represented by the original node.  Typically, it is closer to the
   physical realization of the network than the original node.  The
   nodes of this map can themselves have detailed maps.

3.5.3 Transit Connectivity

   For a given node, this attribute specifies the services available
   between nodes adjacent to the given node.  This attribute is
   requested and used when a router intends to route traffic *through* a
   node.  Conceptually, the traffic connectivity attribute is a matrix
   that is indexed by a pair of locators: the locators of adjacent
   nodes.  The entry indexed by such a pair contains the connectivity
   specifications of the services available across the given node for
   traffic entering from the first node and exiting to the second node.

   The actual format of this attribute need not be a matrix.  This
   document does not specify the format for this attribute.

3.5.4 Inbound Connectivity

   For a given node, this attribute represents connectivity from
   adjacent nodes to points within the given node.  This attribute is
   requested and used when a router intends to route traffic to a point
   within the node but does not have, and either cannot or does not want
   to obtain, a detailed map of the node.  The inbound connectivity
   attribute identifies what connectivity specifications are available
   between pairs of locators.  The first element of the pair is the
   locator of an adjacent node; the second is a locator owned by the
   given node.

3.5.5 Outbound Connectivity

   For a given node, this attribute represents connectivity from points
   within the given node to adjacent nodes.  This attribute identifies
   what connectivity specifications are available between pairs of
   locators.  The first element of the pair is a locator owned by the
   given node, the second is the locator of an adjacent node.




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


   The Transit, Inbound and Outbound connectivity attributes together
   wiht a list of adjacencies form the "abstract map."

4. Physical Realization

   A network is modeled as being composed of physical elements: routers,
   hosts, and communication links.  The links can be either point-to-
   point---e.g., T1 links---or multi-point---e.g., ethernets, X.25
   networks, IP-only networks, etc.

   The physical representation of a network can have associated with it
   one or more Nimrod maps.  A Nimrod map is a function not only of the
   physical network, but also of the configured clustering of elements
   (locator assignment) and of the configured connectivity.

   Nimrod has no pre-defined "lowest level": for example, it is possible
   to define and advertise a map that is physically realized inside a
   CPU. In this map, a node could represent, for example, a process or a
   group of processes.  The user of this map need not necessarily know
   or care.  ("It is turtles all the way down!", in [3] page 63.)

4.1 Contiguity

   Locators sharing a prefix must be assigned to a contiguous region of
   a map.  That is, two nodes in a map that have been assigned locators
   sharing a prefix should be connected to each other via nodes that
   themselves have been assigned locators with that prefix.  The main
   consequence of this requirement is that "you cannot take your locator
   with you."

   As an example of this, see figure 1, consider two providers x.net and
   y.net (these designations are *not* locators but DNS names) which
   appear in a Nimrod map as two nodes with locators A and B. Assume
   that corporation z.com (also a DNS name) was originally connected to
   x.net.  Locators corresponding to elements in z.com are, in this
   example, A-prefixed.  Corporation z.com decides to change providers-
   --severing its physical connection to x.net.  The connectivity
   requirement described in this section implies that, after the
   provider change has taken place, elements in z.com will have been, in
   this example, assigned B-prefixed locators and that it is not
   possible for them to receive data destined to A-prefixed locators
   through y.net.









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


                  A                 B
               +------+          +------+
               | x.net|          | y.net|
               +------+         /+------+
                               /
                        +-----+
                        |z.com|
                        +-----+



             Figure 1:  Connectivity after switching providers

   The contiguity requirement simplifies routing information exchange:
   if it were permitted for z.com to receive A-prefixed locators through
   y.net, it would be necessary that a map that contains node B include
   information about the existence of a group of A-prefixed locators
   inside node B. Similarly, a map including node A would have to
   include information that the set of A-prefixed locators asigned to
   z.com is not to be found within A. The more situations like this
   happen, the more the hierarchical nature of Nimrod is subverted to
   "flat routing." The contiguity requirement can also be expressed as
   "EIDs are stable; locators are ephemeral."