GENWiki

Premier IT Outsourcing and Support Services within the UK

User Tools

Site Tools


rfc:rfc1992

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
 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."

4.2 An Example

 Figure 2 shows a physical network.  Hosts are drawn as squares,
 routers as diamonds, and communication links as lines.  The network
 shown has the following components: five ethernets ---EA through EE;
 five routers---RA through RE; and four hosts---HA through HD. Routers
 RA, RB, and RC interconnect the backbone ethernets---EB, EC and ED.
 Router RD connects backbone EC to a network consisting of ethernet EA
 and hosts HA and HB.  Router RE interconnects backbone ED to a
 network consisting of ethernet EE and hosts HC and HD. The assigned
 locators appear in lower case beside the corresponding physical
 entity.
 Figure 3 shows a Nimrod map for that network.  The nodes of the map
 are represented as squares.  Lines connecting nodes represent two
 adjacencies in opposite directions.  Different regions of the network
 are represented at different detail.  Backbone b1 is represented as a
 single node.  The region of the network with locators prefixed by "a"
 is represented as a single node.  The region of the network with
 locators prefixed by "c" is represented in full detail.

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

4.3 Multiple Locator Assignment

 Physical elements can form part of, or implement, more than one node.
 In this sense it can be said that they can be assigned more than one
 locator.  Consider figure 4, which shows a physical network.  This
 network is composed of routers (RA, RB, RC, and RD), hosts (HA, HB,
 and HC), and communication links.  Routers RA, RB, and RC are
 connected with point-to-point links.  The two horizontal lines in the
 bottom of the figure represent ethernets.  The figure also shows the
 locators assigned to hosts and routers.
 In figure 4, RA and RB have each been assigned one locator (a:t:r1
 and b:t:r1, respectively).  RC has been assigned locators a:y:r1 and
 b:d:r1; one of these two locators shares a prefix with RA's locator,
 the other shares a prefix with RB's locator.  Hosts HA and HB have
 each been assigned three locators.  Host HC has been assigned one
 locator.  Depending on what communication paths have been set up
 between points, different Nimrod maps result.  A possible Nimrod map
 for this network is given in figure 5.

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

                                           a:h1 +--+      a:h2 +--+
                                                |HA|           |HB|
                                                |  |           |  |
                                                +--+           +--+
                                         a:e1    |              |
                                             --------------------- EA
                                                     |
                               /\                    /\
                              /RB\ b1:r1            /RD\ b2:r1
                             /\  /\                 \  /
                            /  \/  \                 \/
  EB         b1:t:e1       /        \                 |   EC
  ------------------------          -------------------------- b2:e1
             /                             \
            /                               \
           /\                                \
          /RA\ b1:r2                          \/\
          \  /                                /RC\  b2:t:r2
           \/                                 \  /
             \                                 \/
              \                               /   ED
                ----------------------------------- b3:t:e1
                                  |
                                  |
                                  |
                                 /\
                                /RE\ b3:t:r1
                                \  /
                    EE           \/
                    -----------------------------   c:e1
                       |                   |
                      +--+                +--+
                      |HC|   c:h1         |HD|    c:h2
                      |  |                |  |
                      +--+                +--+
                  Figure 2:  Example Physical Network

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

                           +-----+               +-----+
 +----------+              |     |               |     |
 |          |--------------| b2  | --------------| a   |
 |          |              |     |               |     |
 |    b1    |              +-----+               +-----+
 |          |                 |
 |          |                 |
 |          |                 |
 +----------+                 |
             \                |
              \               |
               \              |
                \             |
                 \         +--------+
                  \        |        |
                   ------- | b3:t:e1|
                           |        |
                           +--------+
                              |
                              |
                              |
                              |
                           +-------+
                           |       |
                           |b3:t:r1|
                           |       |
                           +-------+
                                |
               +-----+       +-----+     +-----+
               |     |       |     |     |     |
               | c:h1|-------| c:e1|-----| c:h2|
               |     |       |     |     |     |
               +-----+       +-----+     +-----+
                         Figure 3:  Nimrod Map

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

                    a:t:r1              b:t:r1
                       +--+            +--+
                       |RA|------------|RB|
                       +--+            +--+
                         \             /
                          \           /
                           \         /
                            \       /
                             \     /
                              \   /
                               \ /
                                \
                               +--+
                               |RC|  a:y:r1
                               +--+  b:d:r1
                                |
                   ---------------------------
                    |        |             |
           a:y:h1  +--+     +--+          +--+    a:y:h2
           b:d:h2  |HA|     |RD| c:r1     |HB|    b:d:h1
           c:h1    +--+     +--+          +--+    c:h2
                              |
                              |
                       --------------------
                                |
                               +--+
                               |HC| c:h3
                               +--+
                      Figure 4:  Multiple Locators

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

         a                       b                   c
   +-------------+       +-------------+         +---------------+
   |             |       |             |         |               |
   |        a:t  |       |      b:t    |         |               |
   |   +--+      |       |  +--+       |         |               |
   |   |  |--------------|--|  |       |         |               |
   |   +--+      |       |  +--+       |         |               |
   |     |       |       |    |        |         |               |
   |   +--+      |       |  +--+       |         |               |
   |   +  +      |       |  +  +       |         |               |
   |   +--+ a:y  |       |  +--+ b:d   |         |               |
   |             |       |             |         |               |
   +-------------+       +-------------+         +---------------+
                         Figure 5:  Nimrod Map
 Nodes and adjacencies represent the *configured* clustering and
 connectivity of the network.  Notice that even though a:y and b:d are
 defined on the same hardware, the map shows no connection between
 them: this connection has not been configured.  A packet given to
 node `a' addressed to a locator prefixed with "b:d" would have to
 travel from node a to node b via the arc joining them before being
 directed towards its destination.  Similarly, the map shows no
 connection between the c node and the other two top level nodes.  If
 desired, these connections could be established, which would
 necessitate setting up the exchange of routing information.  Figure 6
 shows the map when these connections have been established.
 In the strict sense, Nimrod nodes do not overlap: they are distinct
 entities.  But, as we have seen in the previous example, a physical
 element can be given more than one locator, and, in that sense,
 participate in implementing more than one node.  That is, two
 different nodes might be defined on the same hardware.  In this
 sense, Nimrod nodes can be said to overlap.  But to notice this
 overlap one would have to know the physical-to-map correspondence.
 It is not possible to know when two nodes share physical assets by
 looking only at a Nimrod map.

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

5. Forwarding

 Nimrod supports four forwarding modes:

1. Connectivity Specification Chain (CSC) mode: In this mode, packets

  carry a list of connectivity specifications.  The packet is
  required to go through the nodes that own the connectivity
  specifications using the services specified.  The nodes associated
  with the listed connectivity specifications should define a
  continuous path in the map.  A more detailed description of the
  requirements of this mode is given in section 5.3.

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

 +--------+                                               +--------+
 |        |                                               |        |
 | a:t:r1 |-----------------------------------------------| b:t:r1 |
 |        |                                               |        |
 +--------+                                               +--------+
   |                                                             |
   |                                                             |
   |         /-----------------------------------------\         |
   |         |                                         |         |
   |         |                                         |         |
   |  +--------+       +--------+                    +--------+  |
   |  |        |       |        |                    |        |  |
   |  | a:y:h1 --------|  c:h1  |--------------------| b:d:h1 |  |
   |  |        |       |        |                    |        |  |
   |  +--------+       +--------+                    +--------+  |
   |    |    |           |    |                        |    |    |
 +--------+  |           |  +------+  +------+         |  +--------+
 |        |  |           |  |      |  |      |         |  |        |
 | a:y:r1 |  |           |  | c:r1 |--| c:h3 |         |  | b:d:r1 |
 |        |  |           |  |      |  |      |         |  |        |
 +--------+  |           |  +------+  +------+         |  +--------+
   |    |    |           |    |                        |    |    |
   |  +--------+       +--------+                    +--------+  |
   |  |        |       |        |                    |        |  |
   |  | a:y:h2 |--------  c:h2  |--------------------| b:d:h2 |  |
   |  |        |       |        |                    |        |  |
   |  +--------+       +--------+                    +--------+  |
   |         |                                         |         |
   |         |                                         |         |
   |         |                                         |         |
   |         \-----------------------------------------/         |
   \-------------------------------------------------------------/
                        Figure 6:  Nimrod Map II

2. Connectivity Specifications Sequence (CSS) mode: In this mode,

  packets carry a list of connectivity specifications.  The packet
  is supposed to go sequentially through the nodes that own each one
  of the listed connectivity specifications in the order they were
  specified.  The nodes need not be adjacent.  This mode can be seen
  as a generalization of the CSC mode.  Notice that CSCs are said to
  be a *chains* of locators, CSSs are *sequences* of locators.  This
  difference emphasizes the contiguity requirement in CSCs.  A
  detailed description of this mode is in section 5.6.

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

3. Flow mode: In this mode, the packet includes a path-id that

  indexes state that has been previously set up in routers along the
  path.  Packet forwarding when flow state has been established is
  relatively simple: follow the instructions in the routers' state.
  Nimrod includes a mechanism for setting up this state.  A more
  detailed description of this mode can be found in section 5.4.

4. Datagram mode: in this mode, every packet carries source and

  destination locators.  This mode can be seen as a special case of
  the CSS mode.  Forwarding is done following procedures as
  indicated in section 5.5.
  BEGIN COMMENT
  The obvious parallels are between CSC mode and IPV4's strict
  source route and between CSS mode and IPV4's loose source route.
  END COMMENT
 In all of these modes, the packet may also carry locators and EIDs
 for the source and destinations.  In normal operation, forwarding
 does not take the EIDs into account, only the receiver does.  EIDs
 may be carried for demultiplexing at the receiver, and to detect
 certain error conditions.  For example, if the EID is unknown at the
 receiver, the locator and EID of the source included in the packet
 could be used to generate an error message to return to the source
 (as usual, this error message itself should probably not be allowed
 to be the cause of other error messages).  Forwarding can also use
 the source locator and EID to respond to error conditions, for
 example, to indicate to the source that the state for a path-id
 cannot be found.
 Packets can be visualized as moving between nodes in a map.  A packet
 indicates, implicitly or explicitly, a destination locator.  In a
 packet that uses the datagram, CSC, or CSS forwarding mode, the
 destination locator is explicitly indicated .  In a packet that uses
 the flow forwarding mode, the destination locator is implied by the
 path-id and the distributed state in the network (it might also be
 included explicitly).  Given a map, a packet moves to the node in
 this map to which the associated destination locator belongs.  If the
 destination node has a "detailed" internal map, the destination
 locator must belong to one of the nodes in this internal map
 (otherwise it is an error).  The packet goes to this node (and so on,
 recursively).

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

5.1 Policy

 CSC and CSS mode implement policy by specifying the connectivity
 specifications associated with those nodes that the packet should
 traverse.  Strictly speaking, there is no policy information included
 in the packet.  That is, in principle, it is not possible to
 determine what criteria were used to select the route by looking at
 the packet.  The packet only contains the results of the route
 generation process.  Similarly, in a flow mode packet, policy is
 implicit in the chosen route.
 A datagram-mode packet can indicate a limited form of policy routing
 by the choice of destination and source locators.  For this choice to
 exist, the source or destination endpoints must have several locators
 associated with them.  This type of policy routing is capable of, for
 example, choosing providers.

5.2 Trust

 A node that chooses not to divulge its internal map can work
 internally any way its administrators decide, as long as the node
 satisfies its external characterization as given in its Nimrod map
 advertisements.  Therefore, the advertised Nimrod map should be
 consistent with a node's actual capabilities.  For example, consider
 the network shown in figure 7 which shows a physical network and the
 advertised Nimrod map.  The physical network consists of hosts and a
 router connected together by an ethernet.  This node can be sub-
 divided into component nodes by assigning locators as shown in the
 figure and advertising the map shown.  The map seems to imply that it
 is possible to send packets to node a:x without these being
 observable by node a:y; however, this is actually not enforceable.
 In general, it is reasonable to ask how much trust should be put in
 the maps obtained by a router.  Even when a node is "trustworthy,"
 and the information received from the node has been authenticated,
 there is always the possibility of an honest mistake.

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

                               +--+
                               |RA| a:r1
                               +--+
                                |
                                |
                                |
                                |
                   -------------------------------
                       |                       |
                      +--+                    +--+
                      |Ha| a:x:h1             |Ha| a:y:h2
                      +--+                    +--+
                             Physical Network
                    a             |
                 +----------------|--------------------
                 |                |                   |
                 |              +----+                |
                 |              |a:r1|                |
                 |   a:x        +----+  a:y           |
                 |   +------+  /      \ +-------+     |
                 |   |      | /        \|       |     |
                 |   |      |           |       |     |
                 |   |      |           |       |     |
                 |   +------+           +-------+     |
                 |                                    |
                 + -----------------------------------+
                             Advertised Nimrod Map
                  Figure 7:  Example of Misleading Map

5.3 Connectivity Specification (CSC) Mode

 Routing for a CSC packet is specified by a list of connectivity
 specifications carried in the packet.  These are the connectivity
 specifications that make the specified path, in the order that they
 appear along the path.  These connectivity specifications are
 attributes of nodes.  The route indicated by a CSC packet is specifed
 in terms of connectivity specifications rather than physical
 entities:  a connectivity specification in a CSC-mode packet would

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

 correspond to a type of service between two points of the network
 without specifying the physical path.
 Given two connectivity specifications that appear consecutively in
 the a CSC-mode packet, there should exist an adjacency going from the
 node corresponding to the first connectivity specification to the
 node corresponding to the second connectivity specification.  The
 first connectivity specification referenced in a CSC-mode packet
 should be an outbound connectivity specification; similarly, the last
 connectivity specification referenced in a CSC-mode packet should be
 an inbound connectivity specification; the rest should be transit
 connectivity specifications.

5.4 Flow Mode

 A flow mode packet includes a path-id field.  This field identifies
 state that has been established in intermediate routers.  The packet
 might also contain locators and EIDs for the source and destination.
 The setup packet also includes resource requirements.  Nimrod
 includes protocols to set up and modify flow-related state in
 intermediate routers.  These protocols not only identify the
 requested route, but also describe the resources requested by the
 flow---e.g., bandwidth, delay, etc.  The result of a set-up attempt
 might be either confirmation of the set-up or notification of its
 failure.  The source-specified routes in flow mode setup are
 specified in terms of CSSs.

5.5 Datagram Mode

 A realistic routing architecture must include an optimization for
 datagram traffic, by which we mean user transactions which consist of
 single packets, such as a lookup in a remote translation database.
 Either of the two previous modes contains unacceptable overhead if
 much of the network traffic consists of such datagram transactions.
 A mechanism is needed which is approximately as efficient as the
 existing IPv4 "hop-by-hop" mechanism.  Nimrod has such a mechanism.
 The scheme can be characterized by the way it divides the state in a
 datagram network between routers and the actual packets.  In IPv4,
 most packets currently contain only a small amount of state
 associated with the forwarding process ("forwarding state")---the hop
 count.  Nimrod proposes that enlarging the amount of forwarding state
 in packets can produce a system with useful properties.  It was
 partially inspired by the efficient source routing mechanism in SIP
 [5], and the locator pointer mechanism in PIP [6]).
 Nimrod datagram mode uses pre-set flow-mode state to support a
 strictly non-looping path, but without a source-route.

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

5.6 Connectivity Specification Sequence Mode

 The connectivity specification sequence mode specifies a route by a
 list of connectivity specifications.  There are no contiguity
 restrictions on consecutive connectivity specifications.
  BEGIN COMMENT
  The CSS and CSC modes can be seen as combination of the datagram
  and flow modes.  Therefore, in a sense, the basic forwarding modes
  of Nimrod are just these last two.
  END COMMENT

6. Security Considerations

 Security issues are not addressed in this document.

7. References

 [1] Steenstrup, M., "Inter-Domain Policy Routing Protocol
     Specification: Version 1," RFC 1479, June 1993.
 [2] Steenstrup M., and R. Ramanathan, "Nimrod Functionality and
     Protocols Specification," Work in Progress, February 1996.
 [3] Wright, R., "Three Scientists and their Gods Looking for Meaning
     in an Age of Information", New York: Times Book, first ed., 1988.
 [4] Deering, S., "SIP: Simple Internet Protocol," IEEE Network, vol.
     7, May 1993.
 [5] Francis, P., "A Near-Term Architecture for Deploying Pip," IEEE
     Network, vol. 7, May 1993.

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

8. Authors' Addresses

 Isidro Castineyra
 BBN Systems and Technologies
 10 Moulton Street
 Cambridge, MA 02138
 Phone:  (617) 873-6233
 EMail:  isidro@bbn.com
 Noel Chiappa
 EMail:  gnc@ginger.lcs.mit.edu
 Martha Steenstrup
 BBN Systems and Technologies
 10 Moulton Street
 Cambridge, MA 02138
 Phone:  (617) 873-3192
 EMail:  msteenst@bbn.com

Castineyra, et. al. Informational [Page 27]

/data/webs/external/dokuwiki/data/pages/rfc/rfc1992.txt · Last modified: 1996/08/28 18:51 by 127.0.0.1

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki