RFC 1992
The Nimrod Routing Architecture
RFC 1992: The Nimrod Routing Architecture ✨ (Part 1 of 6)
Okay bestie, let's start with the basics 🎀. RFC 1992 is called The Nimrod Routing Architecture, and it came out in August 1996. The authors are I. Castineyra (BBN), N. Chiappa, and M. Steenstrup (BBN). It's classed as Informational, which means it's just sharing info and isn't a standard. The title block doesn't list anything it obsoletes or updates, so it's not replacing or changing any other doc 💅.
Status of This Memo 🌸
So, this memo gives info to the Internet community 🫶. It does not specify an Internet standard of any kind, so nobody's getting graded on it lol. Distribution is totally unlimited, so you can share it with everyone 💖.
Abstract 🦋
Here's the big idea: they present a scalable internetwork routing architecture called Nimrod 👑. It's built for a dynamic internetwork of any size, with all kinds of service requirements and restrictions, and it lets you deploy it bit by bit throughout an internetwork. The secret to Nimrod's scalability is that it can represent and manipulate routing-related information at multiple levels of abstraction. It's giving zoom-in, zoom-out energy 🔍✨.
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
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 . . . . . . . . . . . . . . . . . . . . . . 271. Introduction 🎀
Nimrod is a scalable routing architecture built for an internetwork that keeps expanding and diversifying 🌈. Noel Chiappa first suggested it, and then the Nimrod working group of the IETF revised and refined it. This doc is where they give the full detailed description 📖.
The goals of Nimrod are:
- 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.
- To provide service-specific routing in the presence of multiple constraints imposed by service providers and users.
- To admit incremental deployment throughout an internetwork.
They designed the Nimrod architecture to meet these goals, and the key features include:
- Representation of internetwork connectivity and services in the form of maps at multiple levels of abstraction.
- User-controlled route generation and selection based on maps and traffic service requirements.
- User-directed packet forwarding along established paths.
Nimrod is a general routing architecture, so it works for routing within a single routing domain and also among multiple routing domains 🦋. Since it's built to handle a bigger, more diverse internetwork, it's equally applicable to both the TCP/IP and OSI environments. Literally one architecture, two worlds 💅.
2. Overview of Nimrod ✨
Before we get into the nitty-gritty, here's the overview 👀. We start with the internetworking requirements, move on to the routing functions, and wrap up with Nimrod's scaling characteristics.
2.1 Constraints of the Internetworking Environment 🌍
Internetworks are growing and evolving systems. The number, diversity, and interconnectivity of service providers and users keep changing, so they need a routing architecture that can handle growth and evolution 📈. A messy mix of factors like tech advances, political alliances, and the economics of service supply and demand will decide how an internetwork changes over time. Predicting all of those factors and all of their effects might not be possible, though. So the flexibility of an internetwork routing architecture is basically its superpower for handling unanticipated requirements 🦸♀️.
First, they put together a list of internetwork environmental constraints that have implications for routing. The list includes observations about the present Internet, and it also includes predictions about internetworks five to ten years in the future 🔮.
- The Internet will grow to include
O(10^9)networks. - The number of internetwork users may be unbounded.
- The capacity of internetwork resources is steadily increasing, but so is the demand for these resources.
- Routers and hosts have finite processing capacity and finite memory, and networks have finite transmission capacity.
- 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 📡.
- Internetwork elements -- networks, routers, hosts, and processes -- may be mobile 🚶♀️.
- Service providers will specify offered services and restrictions on access to those services. Restrictions may be about 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 💸.
- Users will specify traffic service requirements, which may vary widely among sessions. These specifications may cover 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 🛍️.
- A user traffic session may include
m, n > or = 1sources and destinations, wherem, n > or = 1. - Service providers and users have a synergistic relationship. As users develop more applications with special service requirements, service providers respond with services to meet those demands. And as service providers deliver more services, users develop more applications that take advantage of them 🔁.
- Support for varied and special services will require more processing, memory, and transmission bandwidth from both the service providers offering these services and the users requesting them. So many routing-related activities will likely be performed not by routers and hosts, but by independent devices acting on their behalf to process, store, and distribute routing information 🤖.
- 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 ⏳.
- Service providers are reluctant to introduce complicated protocols into their networks, because those protocols are more difficult to manage 😩.
- Vendors are reluctant to implement complicated protocols in their products, because those take longer to develop 🛠️.
Collectively, these constraints mean that a successful internetwork routing architecture must support special features, like service-specific routing and component mobility in a large and changing internetwork. It has to do this using simple procedures that consume a minimal amount of internetwork resources. The authors believe the Nimrod architecture meets these goals, and they justify that claim in the rest of the document 💜.
That's the first part, bestie. There's a lot more Nimrod coming up 🦋
2.2 The Basic Routing Functions 🦋
okay bestie, every routing system has to do the same four jobs, no cap:
- Collecting, assembling, and distributing the information necessary for route generation and selection. 📦
- Generating and selecting routes based on this information. 🗺️
- Establishing in routers information necessary for forwarding packets along the selected routes. 🛠️
- Forwarding packets along the selected routes. 🚀
Nimrod's take on this is so organized 💅 It uses map distribution with the "link-state" paradigm, localizes route generation and selection at traffic sources and destinations, and specifies packet forwarding through path establishment by those same sources and destinations.
Link-state map distribution lets each service provider control the services it offers, by both distributing restrictions in and restricting distribution of its routing information. Restricting distribution shrinks the amount of routing information kept across the internetwork and keeps certain routing information private. BUT, the catch is that it also leads to inconsistent routing information databases throughout an internetwork, since not every database will be complete or identical 😬 We expect these inconsistencies to show up often in a large internetwork, whether or not privacy is involved. The reason is that some devices won't be able to keep the complete set of routing information for the internetwork. Those devices will only store some of the distributed routing information 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. It doesn't require global coordination among routers, so these devices can generate routes tailored to the users' needs, and only those users pay the cost of generating those routes ✨ Locally-controlled route generation also allows incremental deployment of and experimentation with new route generation algorithms, since these algorithms don't need to be the same at each location in an internetwork.
Packet forwarding according to paths may be completely controlled by the users or by the devices acting on their behalf. These paths can be specified in as much detail as the maps permit. This kind of forwarding gives you 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, based on routing information maintained at a single device.
We note that the Nimrod architecture and Inter-Domain Policy Routing (IDPR) [1] share link-state routing information distribution, localized route generation, and path-oriented message forwarding. Nimrod was built with experience gained from developing and experimenting with IDPR, so it's giving family tree energy 🌳
2.3 Scalability Features 📈
Nimrod must provide service-specific routing in arbitrarily large internetworks, so it must employ mechanisms that help contain the amount of internetwork resources consumed by the routing functions. Here's a quick synopsis of those mechanisms. Heads up though: using these mechanisms arbitrarily does not guarantee a scalable routing architecture 🙈 They must be used wisely, in order to enable a routing architecture to scale with internetwork growth.
2.3.1 Clustering and Abstraction 🧩
The Nimrod architecture can represent 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, like 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 can be formed by clustering together existing clusters. Repeated clustering of entities produces a hierarchy of clusters with a unique universal cluster that contains all the others. The same clustering algorithm need not be applied at each level of the hierarchy.
All elements within a cluster must satisfy at least one relation, namely connectivity. That means 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 rules out certain types of separated clusters 🚫 For example, say a company has two branches at opposite ends of a country, and those branches have to communicate over a public network the company doesn't own. 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 eliminating services provided by a small fraction of the elements in the cluster, or expressing 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 that is 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 the resource consumption tied to that distribution and to permit information hiding. Each cluster decides which portions of its routing information to distribute and which set of entities to distribute it to. Recipients are picky too, since they're selective about which information they retain. Some examples: 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.
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 to take on the computational load of generating and selecting those routes. Plus, the Nimrod architecture lets individual entities choose their own route generation and selection algorithms, and therefore how many resources to devote to those functions.
2.3.4 Caching 💾
The Nimrod architecture encourages caching of acquired routing information, so less resource is consumed and less delay is incurred when getting that 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's great for caching, since future requests for any of these routes can be satisfied directly from the route cache. However, as with any caching scheme, the cached information may go stale, and using it may result in poor quality routes. So the routing information's expected duration of usefulness must be considered when deciding 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 multiple traffic flows with similar service requirements over a single path (or tree, for multicast). The second approach is to install and retain forwarding information only for active traffic flows.
With Nimrod, 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 is different from 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 manage, in a scalable fashion, how much information about the internetwork is required to choose a route for that stream. In other words, it manages the trade-off between the 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💬 Okay, side note bestie: 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, like how to reach it, can be obtained by querying this distributed database using the endpoint's label as the key.END COMMENT
3.2 Nodes and Adjacencies 🌸
okay so a node is a region of the physical network 🗺️ and bestie, that region can be as big or as small as you want!! a node can be a whole continent 🌍 or a process running inside a host 💻. the flexibility is literally iconic. section 4 gets into this more, but a region of the network can be represented by more than one node at the same time 🫶
an adjacency is an ordered pair of nodes ✨. it means traffic can flow from the first node to the second. the order matters, so pay attention 💅
3.3 Maps 🗺️
the map is the basic data structure for routing 💖. a map shows the connectivity available between different points of an internetwork. different maps can show the same region of a physical network at different levels of detail, which is so main character of them 👑
a map is a graph made of nodes and adjacencies. the properties of nodes live in attributes attached to them 🎀. adjacencies don't have attributes 🙈. Nimrod defines languages for specifying attributes and for describing maps 🧚
routers use maps to generate routes 🦋. in general, it is not required that different routers have consistent maps.
💬BEGIN COMMENTNimrod 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 only talk about routers 🤖. by "router" we mean a physical device that implements functions related to routing, like forwarding, route calculation, and path set-up. a device doesn't have to be able to do all of these to count as a router. the protocol specification document, see [2], splits these functionalities into specific agents 🌈
3.3.1 Connectivity Specifications 📶
connectivity between two points means the available services and the restrictions on using them. connectivity specifications are among the attributes associated with nodes. here are some informal examples, bestie 💕
"Between these two points, there exists best-effort service with no restrictions.""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.""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 🧭. both nodes and endpoints get locators.
different nodes have necessarily different locators 💜. a node gets only one locator. locators identify nodes and tell you where a node is. locators do not tell you a path to the node 🙅. an endpoint can be assigned more than one locator, so a locator might show up in more than one location of an internetwork. it's giving multi-location energy ✨
in this document, locators are written as ASCII strings with colons to show the node structure, like a:b:c. that doesn't mean locators in packets or databases will necessarily have colons 👀
a single physical element of the network might help implement more than one node. for example, a router might be part of two different nodes 🎀. that element might therefore have more than one locator, but each node it implements still has only one locator.
the connectivity specifications of a node are identified by a tuple made 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 too. EIDs are not used in making routing decisions, so see section 5 🫶
3.5 Node Attributes 🎀
the following are node attributes defined by Nimrod 💅
3.5.1 Adjacencies 🔗
adjacencies show up in maps as attributes of both nodes in the adjacency. a node has two types of adjacencies: ones that identify a neighboring node it can send data to, and ones that identify a neighboring node that can send data to it 📨
3.5.2 Internal Maps 🧩
a node can have internal maps as part of its attributes ✨. a router can get a node's internal maps (or any other attribute of that node) by asking 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, that could happen because of security concerns 🔐. so different routers in the network might have different internal maps for the same node, which is a lot but also kind of genius 🤯
a node owns the locators that have its own locator as a prefix. in a node with an internal map, all the locators of nodes in that internal map are prefixed by the locator of the original node 🌸
given a map, you can get a more detailed map by swapping one of the map's nodes for one of that node's internal maps. you can keep doing this recursively 🔁. Nimrod defines standard internal maps meant for specific purposes. a node's "detailed map" gives more info about the region of the network that the original node represents. it's usually closer to the physical reality of the network than the original node is. the nodes of that map can have detailed maps too, bestie 🪆
3.5.3 Transit Connectivity 🚇
for a given node, this attribute specifies the services available between nodes adjacent to that node. it gets requested and used when a router wants to route traffic through a node 🚦. conceptually, the traffic connectivity attribute is a matrix indexed by a pair of locators: the locators of adjacent nodes. the entry for a pair holds 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 doesn't have to 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 🏠. it gets requested and used when a router wants to route traffic to a point within the node, but it doesn't have a detailed map of the node and either can't or doesn't want to get one 🙃. the inbound connectivity attribute says which connectivity specifications are available between pairs of locators. the first element of the pair is the locator of an adjacent node, and 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 🌷. it identifies which connectivity specifications are available between pairs of locators. the first element of the pair is a locator owned by the given node, and the second is the locator of an adjacent node 🫶
the Transit, Inbound and Outbound connectivity attributes, together with a list of adjacencies, form the "abstract map" 🎀
4. Physical Realization 🌈
a network is modeled as being made of physical elements: routers, hosts, and communication links 🛠️. links can be 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 one or more Nimrod maps associated with it 🗺️. 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, you can define and advertise a map that's physically realized inside a CPU. in that map, a node could represent a process or a group of processes. the user of this map doesn't necessarily need to 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 means 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 is that "you cannot take your locator with you." 📦🚫
look at figure 1 for an example 👀. two providers, x.net and y.net (these designations are not locators, they're DNS names), show up in a Nimrod map as two nodes with locators A and B. say corporation z.com (also a DNS name) was originally connected to x.net, and its locators are A-prefixed. then z.com decides to change providers, severing its physical connection to x.net 💔. the connectivity requirement in this section means that after the switch, elements in z.com will have been assigned B-prefixed locators, and it's not possible for them to receive data destined for A-prefixed locators through y.net 🙅♀️
A B
+------+ +------+
| x.net| | y.net|
+------+ /+------+
/
+-----+
|z.com|
+-----+
Figure 1: Connectivity after switching providersthe contiguity requirement makes routing information exchange simpler 🧘♀️. if z.com were allowed to receive A-prefixed locators through y.net, a map that contains node B would have to include info about the existence of a group of A-prefixed locators inside node B. similarly, a map including node A would have to include info that the set of A-prefixed locators assigned to z.com is not to be found within A 😵. the more situations like this happen, the more Nimrod's hierarchical nature gets subverted into "flat routing" 📉. contiguity can also be put 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. this network has 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 made of ethernet EA and hosts HA and HB. router RE interconnects backbone ED to a network made of ethernet EE and hosts HC and HD. the assigned locators appear in lower case next to the matching physical entity 🏷️
figure 3 shows a Nimrod map for that network 🗺️. the nodes of the map are drawn as squares. lines connecting nodes represent two adjacencies in opposite directions ↔️. different regions of the network are represented at different levels of detail 🔍. backbone b1 is one single node. the region with locators prefixed by "a" is also a single node. the region with locators prefixed by "c" is shown in full detail 🫶
4.3 Multiple Locator Assignment ✨
okay so bestie, physical stuff can be part of more than one node, or help implement more than one node 🫶. That means it can be assigned more than one locator, which is lowkey iconic 💅. Look at figure 4, the physical network. It has routers (RA, RB, RC, and RD), hosts (HA, HB, and HC), and communication links 🌸. RA, RB, and RC are linked with point-to-point links, and the two horizontal lines at the bottom are ethernets 🦋. The figure also shows which locators each host and router got.
So RA and RB each got one locator: a:t:r1 and b:t:r1, respectively 💜. RC got a:y:r1 and b:d:r1, and one of those shares a prefix with RA's locator while the other shares a prefix with RB's 🎀. HA and HB each got three locators, and HC got one 😭. Depending on which communication paths get set up between points, you end up with different Nimrod maps 🧚. A possible one for this network is figure 5, so here are the diagrams.
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 +-----+ +-----+
+----------+ | | | |
| |--------------| b2 | --------------| a |
| | | | | |
| b1 | +-----+ +-----+
| | |
| | |
| | |
+----------+ |
\ |
\ |
\ |
\ |
\ +--------+
\ | |
------- | b3:t:e1|
| |
+--------+
|
|
|
|
+-------+
| |
|b3:t:r1|
| |
+-------+
|
+-----+ +-----+ +-----+
| | | | | |
| c:h1|-------| c:e1|-----| c:h2|
| | | | | |
+-----+ +-----+ +-----+
Figure 3: Nimrod Map 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 a b c
+-------------+ +-------------+ +---------------+
| | | | | |
| a:t | | b:t | | |
| +--+ | | +--+ | | |
| | |--------------|--| | | | |
| +--+ | | +--+ | | |
| | | | | | | |
| +--+ | | +--+ | | |
| + + | | + + | | |
| +--+ a:y | | +--+ b:d | | |
| | | | | |
+-------------+ +-------------+ +---------------+
Figure 5: Nimrod MapNodes 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, because 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 ✨.
Okay, here's the tea 🍵. In the strict sense, Nimrod nodes do not overlap, because they are distinct entities 💅. But, as we just saw, a physical element can be given more than one locator, and in that sense it can participate in implementing more than one node. That means two different nodes might be defined on the same hardware 🫠. In this sense, Nimrod nodes can be said to overlap, bestie 🦋. But noticing that overlap would mean knowing the physical-to-map correspondence 🔍.
It is not possible to know when two nodes share physical assets by looking only at a Nimrod map. 🙈💀
5. Forwarding 🚚✨
okay so forwarding is literally where packets actually go places 🦋 and Nimrod has FOUR forwarding modes. let's gooo 💅
Nimrod supports four forwarding modes:
- Connectivity Specification Chain (CSC) mode 🔗: packets carry a list of connectivity specifications. the packet is required to go through the nodes that own those connectivity specifications, using the services that are specified. the nodes tied to the listed connectivity specifications should define a continuous path in the map. (there's a more detailed breakdown of this mode's requirements in section 5.3, obviously 🙄💖)
+--------+ +--------+
| | | |
| 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- Connectivity Specifications Sequence (CSS) mode 🌊: packets carry a list of connectivity specifications too, but this time 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 don't need to be adjacent 🙌. this mode can be seen as a generalization of CSC mode. ngl the key difference is in the wording: CSCs are said to be chains of locators, while CSSs are sequences of locators. that difference is all about the contiguity requirement in CSCs 🫶. a detailed description of this mode is in section 5.6.
- Flow mode 🌸: the packet includes a path-id that indexes state that has already been set up in routers along the path. once flow state is established, forwarding is relatively simple: just 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.
- Datagram 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 the procedures 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 sources and destinations 🧚. in normal operation, forwarding doesn't 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 send back to the source (as usual, that error message itself should probably not be allowed to cause other error messages 💀). forwarding can also use the source locator and EID to respond to error conditions, like telling the source that the state for a path-id can't 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's an error 🚨). the packet goes to this node, and so on, recursively 🔁.
5.1 Policy 🧠
CSC and CSS mode implement policy by specifying the connectivity specifications associated with the nodes the packet should traverse. strictly speaking, there's no policy information included in the packet 🙈. that means, in principle, you can't figure out what criteria were used to pick the route just 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 show a limited form of policy routing through its choice of destination and source locators 💅. for that choice to exist, the source or destination endpoints must have several locators associated with them. this type of policy routing can, for example, be used to choose providers 🎀.
5.2 Trust 🕵️♀️
a node that chooses not to divulge its internal map can run things internally any way its administrators decide, as long as it satisfies its external characterization in its Nimrod map advertisements 🤫. so the advertised Nimrod map should be consistent with a node's actual capabilities. for example, look at the network 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's possible to send packets to node a:x without them being observable by node a:y. however, this is actually not enforceable 😭.
in general, it's fair to ask how much trust should be put in the maps a router gets 🤔. even when a node is "trustworthy," and the information received from it has been authenticated, there's always the possibility of an honest mistake 🥺.
+--+
|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 Map5.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 up the specified path, in the order they appear along the path. these connectivity specifications are attributes of nodes. the route a CSC packet indicates is specified in terms of connectivity specifications rather than physical entities. basically, a connectivity specification in a CSC-mode packet would 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 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 one 🛤️. 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 don't just identify the requested route, they also describe the resources the flow requests, like bandwidth, delay, etc. 📶. the result of a setup attempt might be either confirmation of the setup or notification of its failure 🎉😬. the source-specified routes in flow mode setup are specified in terms of CSSs 🌈.
5.5 Datagram Mode
okay bestie, a realistic routing architecture has to include an optimization for datagram traffic 💌 That's user transactions made of single packets, like a lookup in a remote translation database 🔍. Either of the two modes we just covered has unacceptable overhead if most of the network traffic is stuff like that 💀 So we need something about as efficient as the existing IPv4 "hop-by-hop" mechanism ✨ Nimrod has one 🫶
The scheme is basically defined by how it splits the state in a datagram network between the routers and the actual packets 🦋 In IPv4, most packets carry only a tiny bit of forwarding state, the hop count ("forwarding state") 🙈 Nimrod's whole thing is that making the forwarding state in packets bigger can get you a system with useful properties 💅 It was partly inspired by the efficient source routing mechanism in SIP [5], and the locator pointer mechanism in PIP [6]). Iconic borrowing, honestly 👑
Nimrod datagram mode uses pre-set flow-mode state to support a strictly non-looping path, but without a source-route 🌸 No source-route, but still no loops. Main character energy 🧚
5.6 Connectivity Specification Sequence Mode
okay so the connectivity specification sequence mode specifies a route as a list of connectivity specifications 🎀 And there are no contiguity restrictions between consecutive connectivity specifications, so they can just chain together however they want ✨
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 COMMENTNgl this comment is the lowkey tea 🫖 CSS and CSC are basically datagram and flow mixed together, which means the basic forwarding modes of Nimrod are really just those last two 🌈
6. Security Considerations 🔒
Bestie, I have to be real with you 😭 Security issues are not addressed in this document at all. Zero. None. Please keep that in mind 🚨
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.
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📦 where this page comes from
- ietf: rfc1992 1996-08
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms