Nimrod

A New Routing and Addressing Architecture for the Internet



J. Noel Chiappa




"In anything at all, perfection is finally attained not when there is no longer anything to add, but when there is no longer anything to take away..." 
	-- Antoine de Saint Exupery, "Wind, Sand and Stars"
		(quoted in "Multics: The First Seven Years",
		 F. J. Corbato, J. H. Saltzer)
"One ring to rule them all, one ring to find them, one ring to bring them all, and in the darkness bind them." 
	-- J. R. R. Tolkien, "Lord of the Rings"



Introduction

What is Nimrod about?

Nimrod is a routing architecture, not a routing protocol; done by a system architect, not an algorithmic expert.

In other words, don't expect to see:

Expect rather to see:

Internet Evolutionary Needs

The Internet was not designed to grow to its current size or importance. The Internet desperately needs several things:


Routing and Addressing Architectures

What are "routing and addressing architectures"?

An addressing architecture includes: A routing architecture is not simply a protocol (i.e. a set of packet formats, and instructions on how to process them). Rather, it considers the entire subject of how the network organizes the handling of user traffic.

A routing architecture includes:

Examples and Non-Examples of Routing Architectures

Routing protocols: Routing architectures:


Architectural Discussion Fundamentals

Confusion in Terminology and Concepts

I am far from thinking that nomenclature is a remedy for every defect in art or science: still I cannot but feel that confusion of terms generally springs from, and always leads to, confusion of ideas. 
	-- John Louis Petit, Architectural Studies in France, 1854
Much of the confusion in discussion of routing results from varying meanings for terms, particularly address. This happened, in part, because the set of fundamental objects recognized was not rich enough.

Thus, difficulties have arisen when solutions to various problems demanded that objects which were previously hidden "inside" or "behind" other objects be recognized as separate entities.

Names and Objects

We must also separate out the name for a thing from the object, the thing itself, to which those names refer. We must also separate out the form of the name for a thing from the generic concept of a name for the thing.

One of more possible names or types of names can exist for each object, and different names may or may not have structure. The structure is there to help something else do its job.

Objects

Names

New Terminology and Concepts

A new routing architecture should add a new object, and a new naming space for them, to the packet layer: the endpoint.

An endpoint is:




Routing Fundamentals

Classes of Routing Architectures

In one of the two fundamental divisions of routing architectures, paths can be calculated either: (Note: these latter terms, explicit and unitary, are to be preferred to source routing, as this is often taken to have the limited meaning that the host sending the packet must compute the entire route, which is then included in every packet.)

There is also a complex spectrum of possibilities between these endpoints.

Along another axis, there are two broad classes of routing algorithms:

Advantages and Disadvantages of Various Routing Architectures

Hop-by-hop architectures have the following disdvantages: Explicit architectures have the following advantages:

DV architectures have the following advantages:

MD architectures have the following advantages:

The Current Internet Routing Architecture

The current Internet routing architecture has the following key characteristics: Do not be misled by the deployment of IGP's which use MD architectures, such as OSPF and IS-IS, in limited areas of the network. The overall operation of the current Internet routing architecture is DV:

Tradeoffs in Large Scale Routing

In a large network, "good routes" are not a simple, fixed goal. Rather, there is a complex tradeoff at work:

Addresses, Topology and Routing

There are subtle connections between the topology of a network (i.e. how it is connected together), the abstraction hierarchy (i.e. hierarchical addressing structure) used to create addresses for it, and the routes that are generated:


Nimrod Design Goals and Principles

Technical Goals for Nimrod

Nimrod has an extensive list of goals, but this one tops the list: This is by far and away the most important goal. To understand why, let's look at why large-scale communication networks - and the design philosophy that must be used in designing them - are inherently fundamentally different from all other large-scale software systems.

Design Philosophy for Large-Scale Communication Networks

Devolution

As fate-sharing was perhaps the key concept behind the last generation of networking architecture, the key concept of the next generation of networking architecture will probably be devolution.

Devolution, simply put, means that we will never do in the core of the network anything we can move to the edge. In other words, the network won't try and make decisions for the users, but rather will hand the responsibility over to the users.

This is related to the concept of separating policy from mechanism.

The relocation of mechanism, from the network, into the hosts, is a key part of maximizing the lifetime of the architecture. The less the network does, the easier it will be to change and upgrade functionality.

Architectural Lifetimes and Engineering Viability

There is an inherent tension between producing an architecture with a useful lifetime (and how often have we seen crippling costs when an architecture runs into its limits), and producing an architecture which is viable, in engineering terms, at the time it is first deployed.

Overhead costs, etc, which seem trivial toward the end of the lifetime of an architecture (typically twenty years, or more) seem infeasible at the time the architecture is deployed.

However, without the boldness to pay high costs up front, to allow adoption of an architecture with more room for growth over the long run, down the line the architecture will be crippled by limitations imposed in order to produce engineering savings with only short utility.

There is no easy solution to this problem.

Additional Technical Goals for Nimrod

Nimrod has many other goals, which are ancillary to simply maximizing the lifetime:

Design Principles for Nimrod




Nimrod Architecture Overview

Nimrod Fundamental Architecture

The Nimrod routing architecture has the following key characteristics: This combination has a number of advantages: It also includes the following key concepts: Note: The path-selection algorithm is not part of the protocol (although a sample algorithm can be given in an appendix).

Additional Nimrod Architectural Points

The Nimrod routing architecture is also characterized by the following concepts:

Reflections on the Architecture




Overview of Nimrod Mechanisms

Addresses

Nimrod uses, and allow use of, new addresses (something else the Internet needs), called locators, using a syntax and semantics which will hopefully never need to be reworked. Their characteristics are: Note that it is not intended that all packets will carry these addresses; packets which are using the flow service mode need only carry flow identifiers.

Maps

Connectivity information in the form of maps is the key data item in Nimrod.

Maps:

Nimrod maps consist of: In general, it is not required that different routers have consistent maps.

More About Maps

A node in a map represents some part of the physical network. It may be as large or as small as desired: a node can represent an entire ISP, or a single interface.

A contiguous portion of the graph which represents the entire physical network may be represented by a node, or set of nodes, which are an abstraction for that part of the network.

Abstractions can be recursive.

The entities responsible for advertising the abstraction for an area of the physical network get to chose what abstraction for that area they wish to hand out.

Each node which is using maps to select paths can, within limits, decide for iself how much detail it wants to see in its map. If the information it gets by default is not detailed enough, it can go out and ask for more.

Attributes

The nodes in the map may be characterized by an open-ended (and locally extensible) list of attributes, which can include many different kinds of information. Attributes might include: Each node also has some inherent attributes, i.e. ones which each node must have:

Path Selection

Conceptually, path selection is done by the users of the network, i.e. the hosts. However, many hosts will not want to deal with keeping maps, running path-selection algorithms, etc. It is thus expected that most hosts will get paths from route servers.

Route servers have the advantage that they form a central point at which an organization can express organizational policies with regard to path preferences through the network outside the organization.

Path selection across a large graph, in the presence of multiple constraints, is a difficult problem, and will probably be the subject of research for decades to come.

User Data Forwarding

The plan is for Nimrod to support four basic modes for handling user data traffic: The first and last modes are intended to be the ones principally used; the others are for special situations, fault isolation, critical network operations, etc.

Datagram Mode

Flows are the fundamental entity in Nimrod, and no packet travels anywhere except in a flow. To provide Datagram mode service, Nimrod routers will assign a packet to a sequence of Datagram Mode Flows (DMF's), which are relatively short-distance flows which are set up specifically to handle Datagram mode packets.

The network is completely spanned by a mesh of DMF's. The packet traverses the network by being assigned to a sequence of DMF's, a sequence which is specifically selected to move the packet towards its eventual destination.

Datagram mode packet headers contain:

Datagram Mode Operation

While in a DMF, the forwarding routers do not examine the locators, only the flow-id.

Only active routers (i.e., one that actually makes a decision about where to send the packet, after it has exited a DMF - as opposed to handling it as part of a flow) look at the locators.

At each active router, the router examines the locators in the header to see where to send the packet next, assigns the packet to the appropriate flow, and sends the packet off.

The pointer is initialized to point at the lowest level of the source locator. From there, it moves up that locator, then to the destination locator, and then down.

While going up the source locator, each active router selects a DMF which will take the packet to the next higher level object in the source locator, and then advances the pointer.

The process repeats, until the packet reaches a router which represents an abstraction which is at the least common intersection of the two locators. (E.g., for A.P.Q.R and A.X.Y.Z, this would be when the packet reaches A).

The process then inverts, with each active router selecting a DMF which takes the packet to the next lower object in the destination locator. So, A would select a flow to A.X, and once it got to A.X, A.X would select a flow to A.X.Y, etc.

Datagram Mode Flows

All routers have to contain a minimal set of pre-setup Datagram Mode flows (or be prepared to set these flows on demand) to certain routers, which are at critical places in the abstraction hierarchy.

These flows are used to carry Datagram mode packets through the network. It is purely a local decision which, if any, of those flows to set up before there is an actual traffic requirement for them.

There is a minimum set of flows which do have to be able to be set up for the system to operate, however.

Datagram Mode Flow Optimization

If the system keeps more than the minimal set of DMF's, and the router allows longest-match lookups (e.g., in much the same way as the current routing table for hop-by-hop datagrams), routing can be more efficient. I.e. packets will no longer travel along strictly hierarchical paths, but will "short-cut" closer to ultimate destinations. (When this happens, the pointer will advance more than one level at a time in the locators.)

Traffic monitoring and analysis (again, using purely local algorithms) can result in a database being created over time, which shows which DMF's above and beyond the minimal set are worth keeping around.

This traffic monitoring could also show which flows from the required minimal set of DMF's it would be useful to set up in advance of actual traffic which needed them.

Note that all these sets can be changed in a local, incremental way, without disturbing the operation of the system as a whole.

Datagram Mode Efficiency and Robustness

The forwarding of Datagram mode packets can be quite efficient (possibly more so than even standard hop-by-hop): It can easily be seen that the process guarantees that the resulting path is loop-free:

Multicast Support

Nimrod approaches multicast with the same ideas used elsewhere: try and break the problem up into pieces, and put as much of the functionality as possible outside the architecture, to allow flexibility in algorithms, etc.

This last is especially important for multicast, where group sizes can vary by many orders of magnitude.

Nimrod separates several distinct phases of creating a multicast group:

Nimrod provides some very fundamental multicast building block(s), such as multicast flow setup. All the rest (like the mechanisms to maintain the state about group membership, calculate the spanning tree, etc) are outside the core architecture. Users can select locally whichever algorithm makes sense in their particular application.

This has all the advantages of the Nimrod approach to unicast:

Nimrod will also distinguish between a multicast group (i.e. a name for the set of members) and a particular multicast flow (i.e. a particular data distribution channel to that group). There can be multiple flows which go to the same group, but controlled independently.

Flow Aggregation

Flow aggregation: So, why add it? Note that you don't have to have a lot of aggregation, just enough to keep the unit cost of per-flow state memory declining at an appropriate rate.


Other Topics

There are many other topics which are not covered here. They include:




Back to the Nimrod Documentation page