As per Relevance of the word specific, we have this rfc below:
Network Working Group I.
Request for Comments: 1992
Category: Informational N.
M.
August 1996
The Nimrod Routing
Status of this
This memo provides information for the Internet community. This
does not specify an Internet standard of any kind. Distribution
this memo is unlimited
We present a scalable internetwork routing architecture,
Nimrod. The Nimrod architecture is designed to accommodate a
internetwork of arbitrary size with heterogeneous
requirements and restrictions and to admit incremental
throughout an internetwork. The key to Nimrod's scalability is
ability to represent and manipulate routing-related information
multiple levels of abstraction
Table of
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.
Nimrod is a scalable routing architecture designed to accommodate
continually expanding and diversifying internetwork. First
by Noel Chiappa, the Nimrod architecture has undergone revision
refinement through the efforts of the Nimrod working group of
IETF. In this document, we present a detailed description of
architecture
The goals of Nimrod are as follows
1. To support a dynamic internetwork of arbitrary size
providing mechanisms to control the amount of routing
that must be known throughout an internetwork
2. To provide service-specific routing in the presence of
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.
key features of this architecture include
1. Representation of internetwork connectivity and services in
form of maps at multiple levels of abstraction
2. User-controlled route generation and selection based on maps
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
routing both within a single routing domain and among
routing domains. As a general internetwork routing
designed to deal with increased internetwork size and diversity
Nimrod is equally applicable to both the TCP/IP and OSI environments
2. Overview of
Before describing the Nimrod architecture in detail, we provide
overview. We begin with the internetworking requirements,
by the routing functions, and concluding with Nimrod's
characteristics
2.1 Constraints of the Internetworking
Internetworks are growing and evolving systems, in terms of number
diversity, and interconnectivity of service providers and users,
therefore require a routing architecture that can
internetwork growth and evolution. A complicated mix of factors
as technological advances, political alliances, and service
and demand economics will determine how an internetwork will
over time. However, correctly predicting all of these factors
all of their effects on an internetwork may not be possible. Thus
the flexibility of an internetwork routing architecture is its key
handling unanticipated requirements
In developing the Nimrod architecture, we first assembled a list
internetwork environmental constraints that have implications
routing. This list, enumerated below, includes observations
the present Internet; it also includes predictions
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
so is the demand for these resources
4. Routers and hosts have finite processing capacity and
memory, and networks have finite transmission capacity
5. Internetworks comprise different types of communications media --
including wireline, optical and wireless, terrestrial
satellite, shared multiaccess and point-to-point -- with
service characteristics in terms of throughput, delay, error
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
access to those services. Restrictions may be in terms of when
service is available, how much the service costs, which users
subscribe to the service and for what purposes, and how the
must shape its traffic in order to receive a service guarantee
8. Users will specify traffic service requirements which may
widely among sessions. These specifications may be in terms
requested qualities of service, the amounts they are willing to
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.
is, as users develop more applications with special
requirements, service providers will respond with the services
meet these demands. Moreover, as service providers deliver
services, users will develop more applications that take
of these services
11. Support for varied and special services will require
processing, memory, and transmission bandwidth on the part of
the service providers offering these services and the
requesting these services. Hence, many routing-related
will likely be performed not by routers and hosts but rather
independent devices acting on their behalf to process, store,
distribute routing information
12. Users requiring specialized services (e.g., high
throughput) will usually be willing to pay more for these
and to incur some delay in obtaining them
13. Service providers are reluctant to introduce complicated
into their networks, because they are more difficult to manage
14. Vendors are reluctant to implement complicated protocols in
products, because they take longer to develop
Collectively, these constraints imply that a successful
routing architecture must support special features, such as service
specific routing and component mobility in a large and
internetwork, using simple procedures that consume a minimal
of internetwork resources. We believe that the Nimrod
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
document
2.2 The Basic Routing
The basic routing functions provided by Nimrod are those provided
any routing system, namely
1. Collecting, assembling, and distributing the information
for route generation and selection
2. Generating and selecting routes based on this information
3. Establishing in routers information necessary for
packets along the selected routes
4. Forwarding packets along the selected routes
The Nimrod approach to providing this routing functionality
map distribution according to the "link-state" paradigm,
of route generation and selection at traffic sources
destinations, and specification of packet forwarding through
establishment by the sources and destinations
Link-state map distribution permits each service provider to
control over the services it offers, through both
restrictions in and restricting distribution of its
information. Restricting distribution of routing information
to reduce the amount of routing information maintained throughout
internetwork and to keep certain routing information private
However, it also leads to inconsistent routing information
throughout an internetwork, as not all such databases will
complete or identical. We expect routing information
inconsistencies to occur often in a large internetwork, regardless
whether privacy is an issue. The reason is that we expect
devices to be incapable of maintaining the complete set of
information for the internetwork. These devices will select
some of the distributed routing information for storage in
databases
Route generation and selection, based on maps and traffic
requirements, may be completely controlled by the users or,
likely, by devices acting on their behalf and does not require
coordination among routers. Thus these devices may generate
specific to the users' needs, and only those users pay the cost
generating those routes. Locally-controlled route generation
incremental deployment of and experimentation with new
generation algorithms, as these algorithms need not be the same
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
the users or the devices acting on their behalf. These paths may
specified in as much detail as the maps permit. Such
forwarding provides freedom from forwarding loops, even when
in a path have inconsistent routing information. The reason is
the forwarding path is a route computed by a single device and
on routing information maintained at a single device
We note that the Nimrod architecture and Inter-Domain Policy
(IDPR) [1] share in common link-state routing
distribution, localized route generation and path-oriented
forwarding. In developing the Nimrod architecture, we have
upon experience gained in developing and experimenting with IDPR
2.3 Scalability
Nimrod must provide service-specific routing in arbitrarily
internetworks and hence must employ mechanisms that help to
the amount of internetwork resources consumed by the
functions. We provide a brief synopsis of such mechanisms below
noting that arbitrary use of these mechanisms does not guarantee
scalable routing architecture. Instead, these mechanisms must
used wisely, in order enable a routing architecture to scale
internetwork growth
2.3.1 Clustering and
The Nimrod architecture is capable of representing an internetwork
clusters of entities at multiple levels of abstraction.
reduces the number of entities visible to routing.
reduces the amount of information required to characterize an
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
them, such as "managed by the same authority", or so as to
some objective function, such as "minimize the expected amount
forwarding information stored at each router". Nimrod does
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
a unique universal cluster that contains all others. The
clustering algorithm need not be applied at each level in
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
operational, then any two of them must be connected by at least
route that lies entirely within that cluster. This
prohibits the formation of certain types of separated clusters,
as the following. Suppose that a company has two branches located
opposite ends of a country and that these two branches
communicate over a public network not owned by the company. Then
two branches cannot be members of the same cluster, unless
cluster also includes the public network connecting them
Once the clusters are formed, their connectivity and
information is abstracted to reduce the representation of
characteristics. Example abstraction procedures include
of services provided by a small fraction of the elements in
cluster or expression of services in terms of average values.
does not mandate a particular abstraction algorithm. The
abstraction algorithm need not be applied to each cluster,
multiple abstraction algorithms may be applied to a single cluster
A particular combination of clustering and abstraction
applied to an internetwork results in an organization related to
distinct from the physical organization of the component hosts
routers, and networks. When a clustering is superimposed over
physical internetwork elements, the cluster boundaries may
necessarily coincide with host, router, or network boundaries
Nimrod performs its routing functions with respect to the
of entities resulting from clustering and abstraction, not
respect to the physical realization of the internetwork. In fact
Nimrod need not even be aware of the physical elements of
internetwork
2.3.2 Restricting Information
The Nimrod architecture supports restricted distribution of
information, both to reduce resource consumption associated with
distribution and to permit information hiding. Each
determines the portions of its routing information to distribute
the set of entities to which to distribute this information
Moreover, recipients of routing information are selective in
information they retain. Some examples are as follows. Each
might automatically advertise its routing information to its
(i.e., those clusters with a common parent cluster). In response
requests, a cluster might advertise information about
portions of the cluster or information that applies only to
users. A cluster might only retain routing information from
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
Generating routes that satisfy multiple constraints is usually
NP-complete problem and hence a computationally intensive procedure
With Nimrod, only those entities that require routes with
constraints need assume the computational load associated
generation and selection of such routes. Moreover, the
architecture allows individual entities to choose their own
generation and selection algorithms and hence the amount of
to devote to these functions
2.3.4
The Nimrod architecture encourages caching of acquired
information in order to reduce the amount of resources consumed
delay incurred in obtaining the information in the future. The
of routes generated as a by-product of generating a particular
is an example of routing information that is amenable to caching
future requests for any of these routes may be satisfied
from the route cache. However, as with any caching scheme,
cached information may become stale and its use may result in
quality routes. Hence, the routing information's expected
of usefulness must be considered when determining whether to
the information and for how long
2.3.5 Limiting Forwarding
The Nimrod architecture supports two separate approaches
containing the amount of forwarding information that must
maintained per router. The first approach is to multiplex, over
single path (or tree, for multicast), multiple traffic flows
similar service requirements. The second approach is to install
retain forwarding information only for active traffic flows
With Nimrod, the service providers and users share responsibility
the amount of forwarding information in an internetwork. Users
control over the establishment of paths, and service providers
control over the maintenance of paths. This approach is
from that of the current Internet, where forwarding information
established in routers independent of demand for this information
3.
Nimrod is a hierarchical, map-based routing architecture that
been designed to support a wide range of user requirements and
scale to very large dynamic internets. Given a traffic stream'
description and requirements (both quality of service
and usage-restriction requirements), Nimrod's main function is
Castineyra, et. al. Informational [Page 8]
RFC 1992 Nimrod Routing Architecture August 1996
manage in a scalable fashion how much information about
internetwork is required to choose a route for that stream, in
words, to manage the trade-off between amount of information
the internetwork and the quality of the computed route. Nimrod
implemented as a set of protocols and distributed databases.
following sections describe the basic architectural concepts used
Nimrod. The protocols and databases are specified in
documents
3.1
The basic entity in Nimrod is the endpoint. An endpoint represents
user of the internetwork layer: for example, a transport connection
Each endpoint has at least one endpoint identifier (EID). Any
EID corresponds to a single endpoint. EIDs are globally unique
relatively short "computer-friendly" bit strings---for example,
multiples of 64 bits. EIDs have no topological
whatsoever. For ease of management, EIDs might be
hierarchically, but this is not required
BEGIN
In practice, EIDs will probably have a second form, which we
call the endpoint label (EL). ELs are ASCII strings of
length, structured to be used as keys in a distributed
(much like DNS names). Information about an endpoint---
example, how to reach it---can be obtained by querying
distributed database using the endpoint's label as key
END
3.2 Nodes and
A node represents a region of the physical network. The region
the network represented by a node can be as large or as small
desired: a node can represent a continent or a process running
a host. Moreover, as explained in section 4, a region of the
can simultaneously be represented by more than one node
An adjacency consists of an ordered pair of nodes. An
indicates that traffic can flow from the first node to the second
3.3
The basic data structure used for routing is the map. A
expresses the available connectivity between different points of
internetwork. Different maps can represent the same region of
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
nodes are contained in attributes associated with them.
have no attributes. Nimrod defines languages to specify
and to describe maps
Maps are used by routers to generate routes. In general, it is
required that different routers have consistent maps
BEGIN
Nimrod has been designed so that there will be no routing
even when the routing databases of different routers are
consistent. A consistency requirement would not
representing the same region of the internetwork at
levels of detail. Also, a routing-database
requirement would be hard to guarantee in the very large
Nimrod is designed to support
END
In this document we speak only of routers. By "router" we mean
physical device that implements functions related to routing:
example, forwarding, route calculation, path set-up. A given
need not be capable of doing all of these to be called a router.
protocol specification document, see [2], splits
functionalities into specific agents
3.3.1 Connectivity
By connectivity between two points we mean the available services
the restrictions on their use. Connectivity specifications are
the attributes associated with nodes. The following are
examples of connectivity specifications
o "Between these two points, there exists best-effort service with
restrictions."
o "Between these two points, guaranteed 10 ms delay can be arranged
traffic streams whose data rate is below 1 Mbyte/sec and that have
(specified) burstiness."
o "Between these two points, best-effort service is offered, as long
the traffic originates in and is destined for research organizations."
3.4
A locator is a string of binary digits that identifies a location
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
assigned only one locator. Locators identify nodes and
*where* a node is in the network. Locators do *not* specify a
to the node. An endpoint can be assigned more than one locator.
this sense, a locator might appear in more than one location of
internetwork
In this document locators are written as ASCII strings that
colons to underline node structure: for example, a:b:c. This
not mean that the representation of locators in packets or
databases will necessarily have something equivalent to the colons
A given physical element of the network might help implement
than one node---for example, a router might be part of two
nodes. Though this physical element might therefore be
with more than one locator, the nodes that this physical
implements have each only one locator
The connectivity specifications of a node are identified by a
consisting of the node's locator and an ID number
All map information is expressed in terms of locators, and
selections are based on locators. EIDs are *not* used in
routing decisions---see section 5.
3.5 Node
The following are node attributes defined by Nimrod
3.5.1
Adjacencies appear in maps as attributes of both the nodes in
adjacency. A node has two types of adjacencies associated with it
those that identify a neighboring node to which the original node
send data to; and those that identivy a neighboring node that
send data to the original node
3.5.2 Internal
As part of its attributes, a node can have internal maps. A
can obtain a node's internal maps---or any other of the node'
attributes, for that matter---by requesting that information from
representative of that node. (A router associated with that node
be such a representative.) A node's representative can in
reply with different internal maps to different requests---
example, because of security concerns. This implies that
routers in the network might have different internal maps for
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
locator of the node. In a node that has an internal map,
locators of all nodes in this internal map are prefixed by
locator of the original node
Given a map, a more detailed map can be obtained by substituting
of the map's nodes by one of that node's internal maps. This
can be continued recursively. Nimrod defines standard internal
that are intended to be used for specific purposes. A node'
"detailed map" gives more information about the region of the
represented by the original node. Typically, it is closer to
physical realization of the network than the original node.
nodes of this map can themselves have detailed maps
3.5.3 Transit
For a given node, this attribute specifies the services
between nodes adjacent to the given node. This attribute
requested and used when a router intends to route traffic *through*
node. Conceptually, the traffic connectivity attribute is a
that is indexed by a pair of locators: the locators of
nodes. The entry indexed by such a pair contains the
specifications of the services available across the given node
traffic entering from the first node and exiting to the second node
The actual format of this attribute need not be a matrix.
document does not specify the format for this attribute
3.5.4 Inbound
For a given node, this attribute represents connectivity
adjacent nodes to points within the given node. This attribute
requested and used when a router intends to route traffic to a
within the node but does not have, and either cannot or does not
to obtain, a detailed map of the node. The inbound
attribute identifies what connectivity specifications are
between pairs of locators. The first element of the pair is
locator of an adjacent node; the second is a locator owned by
given node
3.5.5 Outbound
For a given node, this attribute represents connectivity from
within the given node to adjacent nodes. This attribute
what connectivity specifications are available between pairs
locators. The first element of the pair is a locator owned by
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
wiht a list of adjacencies form the "abstract map."
4. Physical
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
one or more Nimrod maps. A Nimrod map is a function not only of
physical network, but also of the configured clustering of
(locator assignment) and of the configured connectivity
Nimrod has no pre-defined "lowest level": for example, it is
to define and advertise a map that is physically realized inside
CPU. In this map, a node could represent, for example, a process or
group of processes. The user of this map need not necessarily
or care. ("It is turtles all the way down!", in [3] page 63.)
4.1
Locators sharing a prefix must be assigned to a contiguous region
a map. That is, two nodes in a map that have been assigned
sharing a prefix should be connected to each other via nodes
themselves have been assigned locators with that prefix. The
consequence of this requirement is that "you cannot take your
with you."
As an example of this, see figure 1, consider two providers x.net
y.net (these designations are *not* locators but DNS names)
appear in a Nimrod map as two nodes with locators A and B.
that corporation z.com (also a DNS name) was originally connected
x.net. Locators corresponding to elements in z.com are, in
example, A-prefixed. Corporation z.com decides to change providers
--severing its physical connection to x.net. The
requirement described in this section implies that, after
provider change has taken place, elements in z.com will have been,
this example, assigned B-prefixed locators and that it is
possible for them to receive data destined to A-prefixed
through y.net
Castineyra, et. al. Informational [Page 13]
RFC 1992 Nimrod Routing Architecture August 1996
A
+------+ +------+
| x.net| | y.net
+------+ /+------+
/
+-----+
|z.com
+-----+
Figure 1: Connectivity after switching
The contiguity requirement simplifies routing information exchange
if it were permitted for z.com to receive A-prefixed locators
y.net, it would be necessary that a map that contains node B
information about the existence of a group of A-prefixed
inside node B. Similarly, a map including node A would have
include information that the set of A-prefixed locators asigned
z.com is not to be found within A. The more situations like
happen, the more the hierarchical nature of Nimrod is subverted
"flat routing." The contiguity requirement can also be expressed
"EIDs are stable; locators are ephemeral."
4.2 An
Figure 2 shows a physical network. Hosts are drawn as squares
routers as diamonds, and communication links as lines. The
shown has the following components: five ethernets ---EA through EE
five routers---RA through RE; and four hosts---HA through HD.
RA, RB, and RC interconnect the backbone ethernets---EB, EC and ED
Router RD connects backbone EC to a network consisting of ethernet
and hosts HA and HB. Router RE interconnects backbone ED to
network consisting of ethernet EE and hosts HC and HD. The
locators appear in lower case beside the corresponding
entity
Figure 3 shows a Nimrod map for that network. The nodes of the
are represented as squares. Lines connecting nodes represent
adjacencies in opposite directions. Different regions of the
are represented at different detail. Backbone b1 is represented as
single node. The region of the network with locators prefixed by "a
is represented as a single node. The region of the network
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
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
locator. Consider figure 4, which shows a physical network.
network is composed of routers (RA, RB, RC, and RD), hosts (HA, HB
and HC), and communication links. Routers RA, RB, and RC
connected with point-to-point links. The two horizontal lines in
bottom of the figure represent ethernets. The figure also shows
locators assigned to hosts and routers
In figure 4, RA and RB have each been assigned one locator (a:t:r
and b:t:r1, respectively). RC has been assigned locators a:y:r1
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
each been assigned three locators. Host HC has been assigned
locator. Depending on what communication paths have been set
between points, different Nimrod maps result. A possible Nimrod
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 | |
---------------------
|
/\ /\
/RB\ b1:r1 /RD\ b2:r
/\ /\ \ /
/ \/ \ \/
EB b1:t:e1 / \ |
------------------------ -------------------------- b2:e
/ \
/ \
/\ \
/RA\ b1:r2 \/\
\ / /RC\ b2:t:r
\/ \ /
\ \/
\ /
----------------------------------- b3:t:e
|
|
|
/\
/RE\ b3:t:r
\ /
EE \/
----------------------------- c:e
| |
+--+ +--+
|HC| c:h1 |HD| c:h
| | | |
+--+ +--+
Figure 2: Example Physical
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
Castineyra, et. al. Informational [Page 17]
RFC 1992 Nimrod Routing Architecture August 1996
a:t:r1 b:t:r
+--+ +--+
|RA|------------|RB
+--+ +--+
\ /
\ /
\ /
\ /
\ /
\ /
\ /
\
+--+
|RC| a:y:r
+--+ b:d:r
|
---------------------------
| | |
a:y:h1 +--+ +--+ +--+ a:y:h
b:d:h2 |HA| |RD| c:r1 |HB| b:d:h
c:h1 +--+ +--+ +--+ c:h
|
|
--------------------
|
+--+
|HC| c:h
+--+
Figure 4: Multiple
Castineyra, et. al. Informational [Page 18]
RFC 1992 Nimrod Routing Architecture August 1996
a b
+-------------+ +-------------+ +---------------+
| | | | | |
| a:t | | b:t | | |
| +--+ | | +--+ | | |
| | |--------------|--| | | | |
| +--+ | | +--+ | | |
| | | | | | | |
| +--+ | | +--+ | | |
| + + | | + + | | |
| +--+ a:y | | +--+ b:d | | |
| | | | | |
+-------------+ +-------------+ +---------------+
Figure 5: Nimrod
Nodes and adjacencies represent the *configured* clustering
connectivity of the network. Notice that even though a:y and b:d
defined on the same hardware, the map shows no connection
them: this connection has not been configured. A packet given
node `a' addressed to a locator prefixed with "b:d" would have
travel from node a to node b via the arc joining them before
directed towards its destination. Similarly, the map shows
connection between the c node and the other two top level nodes.
desired, these connections could be established, which
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
entities. But, as we have seen in the previous example, a
element can be given more than one locator, and, in that sense
participate in implementing more than one node. That is,
different nodes might be defined on the same hardware. In
sense, Nimrod nodes can be said to overlap. But to notice
overlap one would have to know the physical-to-map correspondence
It is not possible to know when two nodes share physical assets
looking only at a Nimrod map
Castineyra, et. al. Informational [Page 19]
RFC 1992 Nimrod Routing Architecture August 1996
5.
Nimrod supports four forwarding modes
1. Connectivity Specification Chain (CSC) mode: In this mode,
carry a list of connectivity specifications. The packet
required to go through the nodes that own the
specifications using the services specified. The nodes
with the listed connectivity specifications should define
continuous path in the map. A more detailed description of
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
2. Connectivity Specifications Sequence (CSS) mode: In this mode
packets carry a list of connectivity specifications. The
is supposed to go sequentially through the nodes that own each
of the listed connectivity specifications in the order they
specified. The nodes need not be adjacent. This mode can be
as a generalization of the CSC mode. Notice that CSCs are said
be a *chains* of locators, CSSs are *sequences* of locators.
difference emphasizes the contiguity requirement in CSCs.
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
indexes state that has been previously set up in routers along
path. Packet forwarding when flow state has been established
relatively simple: follow the instructions in the routers' state
Nimrod includes a mechanism for setting up this state. A
detailed description of this mode can be found in section 5.4.
4. Datagram mode: in this mode, every packet carries source
destination locators. This mode can be seen as a special case
the CSS mode. Forwarding is done following procedures
indicated in section 5.5.
BEGIN
The obvious parallels are between CSC mode and IPV4's
source route and between CSS mode and IPV4's loose source route
END
In all of these modes, the packet may also carry locators and
for the source and destinations. In normal operation,
does not take the EIDs into account, only the receiver does.
may be carried for demultiplexing at the receiver, and to
certain error conditions. For example, if the EID is unknown at
receiver, the locator and EID of the source included in the
could be used to generate an error message to return to the
(as usual, this error message itself should probably not be
to be the cause of other error messages). Forwarding can also
the source locator and EID to respond to error conditions,
example, to indicate to the source that the state for a path-
cannot be found
Packets can be visualized as moving between nodes in a map. A
indicates, implicitly or explicitly, a destination locator. In
packet that uses the datagram, CSC, or CSS forwarding mode,
destination locator is explicitly indicated . In a packet that
the flow forwarding mode, the destination locator is implied by
path-id and the distributed state in the network (it might also
included explicitly). Given a map, a packet moves to the node
this map to which the associated destination locator belongs. If
destination node has a "detailed" internal map, the
locator must belong to one of the nodes in this internal
(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
CSC and CSS mode implement policy by specifying the
specifications associated with those nodes that the packet
traverse. Strictly speaking, there is no policy information
in the packet. That is, in principle, it is not possible
determine what criteria were used to select the route by looking
the packet. The packet only contains the results of the
generation process. Similarly, in a flow mode packet, policy
implicit in the chosen route
A datagram-mode packet can indicate a limited form of policy
by the choice of destination and source locators. For this choice
exist, the source or destination endpoints must have several
associated with them. This type of policy routing is capable of,
example, choosing providers
5.2
A node that chooses not to divulge its internal map can
internally any way its administrators decide, as long as the
satisfies its external characterization as given in its Nimrod
advertisements. Therefore, the advertised Nimrod map should
consistent with a node's actual capabilities. For example,
the network shown in figure 7 which shows a physical network and
advertised Nimrod map. The physical network consists of hosts and
router connected together by an ethernet. This node can be sub
divided into component nodes by assigning locators as shown in
figure and advertising the map shown. The map seems to imply that
is possible to send packets to node a:x without these
observable by node a:y; however, this is actually not enforceable
In general, it is reasonable to ask how much trust should be put
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:r
+--+
|
|
|
|
-------------------------------
| |
+--+ +--+
|Ha| a:x:h1 |Ha| a:y:h
+--+ +--+
Physical
a |
+----------------|--------------------
| | |
| +----+ |
| |a:r1| |
| a:x +----+ a:y |
| +------+ / \ +-------+ |
| | | / \| | |
| | | | | |
| | | | | |
| +------+ +-------+ |
| |
+ -----------------------------------+
Advertised Nimrod
Figure 7: Example of Misleading
5.3 Connectivity Specification (CSC)
Routing for a CSC packet is specified by a list of
specifications carried in the packet. These are the
specifications that make the specified path, in the order that
appear along the path. These connectivity specifications
attributes of nodes. The route indicated by a CSC packet is
in terms of connectivity specifications rather than
entities: a connectivity specification in a CSC-mode packet
Castineyra, et. al. Informational [Page 24]
RFC 1992 Nimrod Routing Architecture August 1996
correspond to a type of service between two points of the
without specifying the physical path
Given two connectivity specifications that appear consecutively
the a CSC-mode packet, there should exist an adjacency going from
node corresponding to the first connectivity specification to
node corresponding to the second connectivity specification.
first connectivity specification referenced in a CSC-mode
should be an outbound connectivity specification; similarly, the
connectivity specification referenced in a CSC-mode packet should
an inbound connectivity specification; the rest should be
connectivity specifications
5.4 Flow
A flow mode packet includes a path-id field. This field
state that has been established in intermediate routers. The
might also contain locators and EIDs for the source and destination
The setup packet also includes resource requirements.
includes protocols to set up and modify flow-related state
intermediate routers. These protocols not only identify
requested route, but also describe the resources requested by
flow---e.g., bandwidth, delay, etc. The result of a set-up
might be either confirmation of the set-up or notification of
failure. The source-specified routes in flow mode setup
specified in terms of CSSs
5.5 Datagram
A realistic routing architecture must include an optimization
datagram traffic, by which we mean user transactions which consist
single packets, such as a lookup in a remote translation database
Either of the two previous modes contains unacceptable overhead
much of the network traffic consists of such datagram transactions
A mechanism is needed which is approximately as efficient as
existing IPv4 "hop-by-hop" mechanism. Nimrod has such a mechanism
The scheme can be characterized by the way it divides the state in
datagram network between routers and the actual packets. In IPv4,
most packets currently contain only a small amount of
associated with the forwarding process ("forwarding state")---the
count. Nimrod proposes that enlarging the amount of forwarding
in packets can produce a system with useful properties. It
partially inspired by the efficient source routing mechanism in
[5], and the locator pointer mechanism in PIP [6]).
Nimrod datagram mode uses pre-set flow-mode state to support
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
The connectivity specification sequence mode specifies a route by
list of connectivity specifications. There are no
restrictions on consecutive connectivity specifications
BEGIN
The CSS and CSC modes can be seen as combination of the
and flow modes. Therefore, in a sense, the basic forwarding
of Nimrod are just these last two
END
6. Security
Security issues are not addressed in this document
7.
[1] Steenstrup, M., "Inter-Domain Policy Routing
Specification: Version 1," RFC 1479, June 1993.
[2] Steenstrup M., and R. Ramanathan, "Nimrod Functionality
Protocols Specification," Work in Progress, February 1996.
[3] Wright, R., "Three Scientists and their Gods Looking for
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,"
Network, vol. 7, May 1993.
Castineyra, et. al. Informational [Page 26]
RFC 1992 Nimrod Routing Architecture August 1996
8. Authors'
Isidro
BBN Systems and
10 Moulton
Cambridge, MA 02138
Phone: (617) 873-6233
EMail: isidro@bbn.
Noel
EMail: gnc@ginger.lcs.mit.
Martha
BBN Systems and
10 Moulton
Cambridge, MA 02138
Phone: (617) 873-3192
EMail: msteenst@bbn.
Castineyra, et. al. Informational [Page 27]
if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.
RFC documents can be found at I.E.T.F.
Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX
