The Internetwork Layer and the Nimrod Routing Architecture

Overview of Nimrod

Nimrod is a project which aims, in part, to produce a next-generation routing architecture for the Internet; but also, more generally, to try and produce a basic design for routing in a single global-scale communication substrate, a design which will prove sufficiently flexible and powerful to serve into a future as yet unforseeable.

Nimrod does this through the conjunction of two powerful basic mechanisms:

(This latter approach is sometimes called source routing, but this term can be a bit misleading, since in Nimrod the route does not have to be chosen by the actual source, but can be the responsibility of an agent working on the source's behalf. The terms unitary routing or explicit routing have therefore been used to describe this approach. The important thing to realize is that the path is not selected in a fully distributed, hop-by-hop manner, in which each switch has an equal role to play in selecting the path.)

The actual operation is fairly simple, in principle. Maps of the network's actual connectivity (maps which will usually include high-level abstractions for large parts of that connectivity, in the same way road maps of an area may not show all the roads, just the 'important' ones) are made available to all the entities which need to select paths. Those entities use these maps to compute paths, and those paths are passed to the actual switches, along with the data, as directions on how to forward the data.

The rest of this section discusses how the Nimrod routing and addressing architecture interacts with the rest of the internetwork layer, and what requirements it has upon the internetwork layer protocol's packet format.

The Nimrod Subsystems of the Internetwork Layer

As mentioned elsewhere, Nimrod springs, in part, from a design vision which sees the entire internetwork layer, even though it is distributed across all the hosts and routers of the internetwork as a single system; in such a vision, one starts to think about what subsystems are needed, and what the interactions among them should look like. (See this for more information.)

The Nimrod routing architecture is simply a number of the subsystems of this larger system, the internetwork layer. It is not intended to be a purely standalone set of subsystems, but rather, to work together in close concert with the other subsystems of the internetwork layer (resource allocation, security, charging, etc.) to provide the internetwork layer service model.

One reason that Nimrod is not simply a monolithic subsystem is that some of the interaction with the other subsystems of the internetwork layer, for instance the resource allocation subsystem, is much clearer and easier to manage if the routing is broken up into several subsystems, with the interaction between them open.

It is important to realize that Nimrod was initially broken up into separate subsystems for purely internal reasons. It so happens that, considered as a separate problem, the fundamental boundary lines for dividing routing up into subsystems are the same boundaries that make interaction with other subsystems cleaner; this provides added evidence that these boundaries are in fact the right ones.

The subsystems which comprise the functionality covered by Nimrod are

  1. Routing information distribution (in the case of Nimrod, topology map distribution, along with the attributes [policy, QOS, etc.] of the topology elements),
  2. Route selection (strictly speaking, not part of the Nimrod system per se, but a local matter, although they are necessary), and
  3. User traffic handling.

The first can be defined fairly well without reference to other subsystems, but the second and third (route selection and user traffic handling) are necessarily more involved. For instance, route selection might involve finding out which links have the resources available to handle some required level of service. For user traffic handling, if a particular application needs a resource reservation, getting that resource reservation to the routers is as much a part of getting the routers ready as making sure they have the correct routing information, so here too, routing is tied in with other subsystems.

It is possible to talk about the relationship between the Nimrod subsystems, and the other functional subsystems of the internetwork layer, but until the service model of the internetwork layer is more clearly visible, along with the functional boundaries within that layer, such a discussion is necessarily rather nebulous.

Specific Interaction Issues

Here is an incomplete list of the things that Nimrod would like to see from the internetwork layer as a whole:

General Principles for Packet Formats

As a general rule, the design philosophy of Nimrod is 'maximize the lifetime (and flexibility) of the architecture'. Design tradeoffs (i.e. optimizations) that will adversely affect the flexibility, adaptability and lifetime of the design are not not necessarily wise choices; they may cost more than they save. Such optimizations might be the correct choices in a stand-alone system, where the replacement costs are relatively small; in the global communication network, the replacement costs are very much higher.

Providing the Nimrod functionality requires the carrying of certain information in the packets. The design principle noted above has a number of corollaries in specifying the fields to contain that information.

First, the design should be 'simple and straightforward', which means that various functions should be handled by completely separate mechanisms, and fields in the packets. It may seem that an opportunity exists to save space by overloading two functions onto one mechanism or field, but general experience is that, over time, this attempt at optimization costs more, by restricting flexibility and adaptability.

Second, fixed field lengths should be specified to be somewhat larger than can conceivably be used; the history of system architecture is replete with examples (processor address size being the most notorious) where fields became too short over the lifetime of the system. Below, for each item, an indication is given as what the smallest reasonable 'adequate' lengths are, but this is more of a 'critical floor' than a recommendation. A 'recommended' length is also given, which is the length which corresponds to the application of this principle, but note that these are not upper bounds; modulo efficiency concerns, fields cannot be 'too long', only 'too short'!

It is important to note that this does not mean that implementations must support the maximum value possible in a field of that size. In practise, system-wide administrative limits would be placed on the maximum values which must be supported. Then, as the need arises, the administrative limit can be increased. This allows an easy, and completely interoperable (with no special mechanisms) path to upgrade the capability of the network. If the maximum supported value of a field needs to be increased from M to N, an announcement is made that this is coming; during the interim period, the system continues to operate with M, but new implementations are deployed; while this is happening, interoperation is automatic, with no transition mechanisms of any kind needed. When things are 'ready' (i.e. the proportion of old equipment is small enough), use of the larger value commences.

Packet Format Fields

In considering the packet format, one can distinguish between the host-router part of the packet's path, and the router-router part. It is not absolutely necessary that they be the same (although it is simpler), and if they are different, a format that is good for one may not be best suited to the another. In addition, Nimrod has three forwarding modes (flows, datagram, and source-routed packets), and some modes use fields that are not used by other modes.

Bearing these points in mind, what Nimrod would like to see in the internetworking packet is:

Field Requirements and Addition Methods

It is possible to use Nimrod in a mode where needed information/fields are added by the first-hop router. It is thus useful to ask 'which of the fields must be present in the host-router header, and which could be added by the router?' The only ones which are absolutely necessary in all packets are the TLEI's (provided that some means is available to the routers to map them into locators).

As to the others, if the user wishes to use flows, and wants to guarantee that their packets are assigned to the correct flow, the flow-id field is needed. If the user wishes efficient use of the datagram mode, it's probably necessary to include the locators in the packet sent to the router. If the user wishes to specify the route for the packets, and does not wish to set up a flow, they need to include the source route.

How would additional information/fields be added to the packet, if the packet is emitted from the host in incomplete form? (By this is meant the simple question of how, mechanically, not the more complex issue of where any needed information comes from. It is assumed here that the packet does not contain empty fields for this information, but rather a format which does not include those fields at all.)

This question is complex, since all the IPng candidates (and in fact, any reasonable inter-networking protocol) are extensible protocols; those extension mechanisms could be used. Also, it would possible to carry some of the required information as user data in the internetworking packet, with the original user's data encapsulated further inside. Finally, a private inter-router packet format could be defined.

It's not clear which choice is best, but it is possible to discuss which fields the Nimrod routers need access to, and how often; less used ones could be placed in harder-to-get-to locations (such as in an encapsulated header). The fields to which the routers need access on every hop are the flow-id and the looping packet detector. The locator/pointer fields are only needed at intervals (in what Nimrod's datagram forwarding mode calls active routers), as is the source route (the latter on entry to every object which is named in the source route).

Depending on how access control is done, and which forwarding mode is used, the TLEI's and/or locators might be examined for access control purposes, wherever that function is performed.

This is not a complete exploration of the topic, but should give a rough idea of the issues.

The Future of Routing

It is worth noting that although this section is specifically about the requirements of the Nimrod routing architecture, there are reasons to believe that any routing architecture for a large, ubiquitous global network will have many of the same basic fundamental principles as the Nimrod architecture, and the requirements that these generate.

While contemporary routing technologies do not yet have the characteristics and capabilities that generate these requirements, they also do not seem to be completely suited to routing in the next-generation Internet. As routing technology moves towards what is needed for the next generation Internet, the underlying fundamental laws and principles of routing will almost inevitably drive the design, and hence the requirements, toward things which look like the material presented here.

Therefore, even if Nimrod is not the routing architecture of the next-generation Internet, the basic routing architecture of that Internet will have requirements that, while differing in detail, will almost inevitably be similar to these. This makes the requirements of Nimrod worth looking at, even if the specific Nimrod design is destined to be nothing more than a historical curiousity.


[Nimrod]    Isidro Castineyra, Noel Chiappa, Martha Steenstrup, "The Nimrod
                Routing Architecture", RFC 1992, August 1996.

Back to JNC's home page