Nimrod Working Group Ram Ramanathan Internet Draft Martha Steenstrup March 1996 BBN Systems and Technologies draft-ietf-nimrod-fun-pro-spec-00.txt Expires 30 August 1996 Nimrod Functionality and Protocol Specifications, Version 1 Status of this Memo This document is an Internet Draft. Internet Drafts are working documents of the Internet Engineering Task Force (IETF), its Areas, and its Working Groups. Note that other groups may also distribute working documents as Internet Drafts. Internet Drafts are draft documents valid for a maximum of six months. Internet Drafts may be updated, replaced, or obsoleted by other documents at any time. It is not appropriate to use Internet Drafts as reference material or to cite them other than as a ``working draft'' or ``work in progress''. Please check the 1id-abstracts.txt listing contained in the ``internet-drafts'' directories on ftp.isi.edu (U.S. West Coast), ds.internic.net (U.S. East Coast), munnari.oz.au (Pacific Rim), nic.nordu.net (Europe), or ftp.is.co.za (Africa) to learn the current status of any Internet Draft. Distribution of this Internet Draft is unlimited. Please send all comments to nimrod-wg@bbn.com. Abstract Nimrod is a scalable routing architecture designed to support a dynamic internetwork of arbitrary size, to provide service-specific routing in the presence of multiple constraints, and to admit incremental deployment throughout an internetwork. The key features of Nimrod include representation of internetwork connectivity and services in the form of maps at multiple levels of abstraction; source- and destination-controlled route generation and selection based on maps and traffic service requirements; and source- and destination-controlled message forwarding according to the routes selected. This document contains a description of Nimrod functionality and a specification of the protocols constituting Nimrod. In particular, the operations pertinent to the map, locator, adjacency, route, and forwarding databases are described, and the Reliable Transaction, Internet DraftNimrod Functionality and Protocol Specifications March 1996 Update, Query-Response, Path Management, and Discovery protocols are specified. Acknowledgments We thank Tom Calderwood, Winston Edmond, Charlie Lynn, Trevor Mendez, Betty O'Neil, Mike Patton, Ram Ramanathan, and Tim Shepard for producing an experimental Nimrod software system that has enabled us to test the practicality of Nimrod. We are especially grateful to Charlie Lynn, chief architect of the Nimrod software, for his flexible system design, his careful and critical analysis of the Nimrod protcols, and his detailed packet formats (depicted in this document). 1 Internet DraftNimrod Functionality and Protocol Specifications March 1996 Contents 1 Scope and Overview 1 2 Introduction 1 2.1 Overview of the Nimrod Architecture : :: :: :: :: :: :: :: :: :: 2 2.1.1 Clustering and Abstraction : :: :: :: :: :: :: :: :: :: :: 2 2.2 Nimrod Entities :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 3 2.3 Nimrod Routing Functions and Databases : :: :: :: :: :: :: :: :: 5 2.3.1 Nimrod Database Consistency :: :: :: :: :: :: :: :: :: :: 6 2.4 Nimrod Agents :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 8 3 Nimrod Operation : An Overview 10 3.1 Maps :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 10 3.1.1 Map Update :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 10 3.1.2 Map Request and Release : :: :: :: :: :: :: :: :: :: :: :: 11 3.2 Routes :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 11 3.2.1 Route Generation :: :: :: :: :: :: :: :: :: :: :: :: :: :: 12 3.2.2 Route Request and Release :: :: :: :: :: :: :: :: :: :: :: 12 3.3 Locators : :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 13 3.3.1 Acquiring and Releasing Node Locators :: :: :: :: :: :: :: 13 3.3.2 Acquiring and Releasing Endpoint Locators : :: :: :: :: :: 14 3.4 Adjacencies : :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 14 3.4.1 Acquiring, Activating, and Releasing Adjacencies :: :: :: 14 3.5 Paths : :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 15 3.5.1 Path Setup :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 16 3.5.2 Path Acceptance :: :: :: :: :: :: :: :: :: :: :: :: :: :: 18 i Internet DraftNimrod Functionality and Protocol Specifications March 1996 3.6 Control Message Integrity and Authentication : :: :: :: :: :: :: 19 3.6.1 Timestamps :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 19 3.6.2 Authentication : :: :: :: :: :: :: :: :: :: :: :: :: :: :: 20 4 Reliable Transaction Protocol 21 4.1 Services Interface :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 21 5 The Update Protocol 23 5.1 Service Interface : :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 23 5.2 Protocol Operation :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 24 5.2.1 Update Header :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 24 5.2.2 Originating Agent Operations :: :: :: :: :: :: :: :: :: :: 25 5.2.3 Transit Agent Operations :: :: :: :: :: :: :: :: :: :: :: 26 5.2.4 The Update Message Action Table (UMAT) : :: :: :: :: :: :: 26 5.3 Database Specific Updates :: :: :: :: :: :: :: :: :: :: :: :: :: 27 5.3.1 Adjacency Updates : :: :: :: :: :: :: :: :: :: :: :: :: :: 28 5.3.2 Locator Updates :: :: :: :: :: :: :: :: :: :: :: :: :: :: 28 5.3.3 Map Updates : :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 29 6 The Query-Response Protocol 30 6.1 Service Interface : :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 30 6.2 Protocol Operation :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 30 6.3 Query/Response Header :: :: :: :: :: :: :: :: :: :: :: :: :: :: 31 6.4 Database Specific Request/Release :: :: :: :: :: :: :: :: :: :: 32 6.4.1 Adjacency Formation :: :: :: :: :: :: :: :: :: :: :: :: :: 32 6.4.2 Adjacency Release : :: :: :: :: :: :: :: :: :: :: :: :: :: 32 6.4.3 Adjacency Activation : :: :: :: :: :: :: :: :: :: :: :: :: 33 ii Internet DraftNimrod Functionality and Protocol Specifications March 1996 6.4.4 Locator Acquisition :: :: :: :: :: :: :: :: :: :: :: :: :: 34 6.4.5 Locator Release :: :: :: :: :: :: :: :: :: :: :: :: :: :: 35 6.4.6 Map Acquisition :: :: :: :: :: :: :: :: :: :: :: :: :: :: 35 6.4.7 Map Termination Request : :: :: :: :: :: :: :: :: :: :: :: 36 6.4.8 Path Information Request :: :: :: :: :: :: :: :: :: :: :: 37 6.4.9 Route Generation Request/Reply :: :: :: :: :: :: :: :: :: 37 7 Path Management Protocol 39 7.1 Protocol Messages : :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 40 7.1.1 Setup : :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 40 7.1.2 Accept :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 42 7.1.3 Teardown : :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 43 7.1.4 Status :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 45 7.1.5 Ack :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 47 7.2 Protocol Finite-State Machines :: :: :: :: :: :: :: :: :: :: :: 48 7.2.1 Initiator :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 50 7.2.2 Intermediate Forwarding Agents and Target : :: :: :: :: :: 51 7.2.3 Check State Actions :: :: :: :: :: :: :: :: :: :: :: :: :: 53 8 Discovery Protocols 57 8.1 Neighbor Discovery :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 57 8.1.1 Neighbor Reachability :: :: :: :: :: :: :: :: :: :: :: :: 58 8.2 Agent Discovery :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 60 8.2.1 Flooding Agent Advertisements : :: :: :: :: :: :: :: :: :: 61 8.2.2 Distribution of Advertisements to Distant Agents :: :: :: 62 8.2.3 Unreachable Agents :: :: :: :: :: :: :: :: :: :: :: :: :: 63 8.2.4 Node Partitions :: :: :: :: :: :: :: :: :: :: :: :: :: :: 64 iii Internet DraftNimrod Functionality and Protocol Specifications March 1996 8.3 Route Tracing :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 65 9 Packet Formats 67 9.1 Overview : :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 67 9.2 IP and Security Headers : :: :: :: :: :: :: :: :: :: :: :: :: :: 68 9.3 Nimrod Forwarding Information : :: :: :: :: :: :: :: :: :: :: :: 70 9.4 Transaction Headers :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 76 9.5 Update, Query, and Response Protocol Headers : :: :: :: :: :: :: 77 9.6 Update Operation Messages :: :: :: :: :: :: :: :: :: :: :: :: :: 79 9.7 Query/Response Operation Messages :: :: :: :: :: :: :: :: :: :: 80 9.8 Discovery Message Header :: :: :: :: :: :: :: :: :: :: :: :: :: 82 10 Appendix 1: Figures for Update and Q-R protocols 85 11 Appendix 2: Basic Data Formats 90 11.1Element (NimElem) : :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 90 11.2Locator (NimLoc) :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 91 11.3Endpoint Identifier (NimEID) :: :: :: :: :: :: :: :: :: :: :: :: 92 11.4Endpoint Name (NimFQDN) : :: :: :: :: :: :: :: :: :: :: :: :: :: 93 11.5Node Identifier (NimNID) :: :: :: :: :: :: :: :: :: :: :: :: :: 93 11.6Services (NimServ) :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 93 11.7Maps (NimMap) :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 94 11.8Routes (NimRute) :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 95 11.9Credentials (NimCred) :: :: :: :: :: :: :: :: :: :: :: :: :: :: 96 11.10Path Labels (NimPLbl) :: :: :: :: :: :: :: :: :: :: :: :: :: :: 96 11.11Time (NimSecs, NimNTP) :: :: :: :: :: :: :: :: :: :: :: :: :: :: 96 11.12Authenticator (NimAuth) : :: :: :: :: :: :: :: :: :: :: :: :: :: 97 iv Internet DraftNimrod Functionality and Protocol Specifications March 1996 12 Security Considerations 98 13 Contact Information 98 v Internet DraftNimrod Functionality and Protocol Specifications March 1996 1 Scope and Overview This document contains a description of Nimrod functionality,and a specification of the protocols constituting Nimrod. While it has been our intention that the document be self-contained, it would help the reader to be familiar with the Nimrod architecture and functionality as described in [1] and [2]. Nimrod does not specify support for mobility or multicast, but does specify requirements for solutions to mobility and multicast within the Nimrod context. A discussion of these issues can be found in [3] and [4]. The document has been organized so that readers may inform themselves at various levels of detail. Specifically, readers wishing to know only what Nimrod's functionality is may confine themselves to sections 2 and 3. For readers wishing to understand and evaluate the protocols comprising Nimrod, we additionally recommend sections 4, 5, 6, 7, and 8. Finally, for Nimrod implementors, sections 9 and 11 give additional details. 2 Introduction Nimrod is a scalable routing architecture designed to support a dynamic internetwork of arbitrary size, to provide service-specific routing in the presence of multiple constraints, and to admit incremental deployment throughout an internetwork. The key features of Nimrod include representation of internetwork connectivity and services in the form of maps at multiple levels of abstraction; source- and destination-controlled route generation and selection based on maps and traffic service requirements; and source- and destination-controlled message forwarding according to the routes selected. At the most general level, one may view any routing system as a set of basic functions which are producers and consumers of certain databases of routing information. These routing functions and their associated routing information include: 1. Assembling, distributing, and collecting information necessary for route generation and selection. This information includes internetwork connectivity and services, traffic service requirements, and locations of traffic sources and destinations. 2. Generating and selecting routes, based on the collected information. 3. Establishing in routers information necessary for forwarding messages, based on the selected routes. 4. Forwarding messages along these routes. Routing systems may, however, differ in the details of the mechanisms that provide a particular routing function. As Nimrod has been designed for routing in large, heterogeneous, and dynamic internetworks, its basic routing functions include additional mechanisms for reducing the quantity of 1 Internet DraftNimrod Functionality and Protocol Specifications March 1996 routing information that must be distributed, processed, and stored throughout an internetwork; for discovering and accommodating changes in routing information caused by physical changes in an internetwork; and for protecting the integrity of routing information. 2.1 Overview of the Nimrod Architecture Before Nimrod routing can be applied within an internetwork, the internetwork must be represented in terms of the two basic Nimrod entities: nodes and endpoints. The internetwork's physical assets, such as routers, point-to-point links, and multiaccess networks, must be captured in Nimrod maps comprising interconnected nodes. Traffic sources and destinations must be cast as Nimrod endpoints. Nimrod entities possess attributes (e.g., location with respect to the maps, interconnectivity with other entities, and service information) which are important for routing. 2.1.1 Clustering and Abstraction Ideally, Nimrod maps should be constructed so as to satisfy the following two primary, and potentially conflicting, goals: 1. Minimize the amount of routing information maintained throughout an internetwork. 2. Maintain routing information sufficient to generate routes that meet traffic service requirements. To satisfy these goals, Nimrod employs two complementary map construction procedures, namely clustering of internetwork physical assets into nodes and abstraction of attributes of the component physical assets resulting in node attributes. The objective of clustering is to reduce the number of entities visible to Nimrod routing at any given level of the hierarchy. Nodes are usually formed by clustering physical assets possessing similar attributes. These attribute similarities might be in terms of, for example, qualities of service, restrictions on access to services, or ownership of these assets. Such clustering results in a reduction in the amount of information necessary to characterize these physical assets, without a reduction in information detail. However, an internetwork's physical assets may be diverse enough so that clustering according to attribute similarity produces no significant reduction in the number of entities visible to Nimrod routing. In this case, alternative clustering criteria (e.g., geographical locality of physical assets) may be employed. Clustering may be applied repeatedly, such that physical assets are first clustered into nodes, and then nodes are themselves clustered into larger nodes, and so on. Iterative clustering further reduces the number of 2 Internet DraftNimrod Functionality and Protocol Specifications March 1996 entities visible to Nimrod routing at a given level of the hierarchy, and results in a hierarchical organization of nodes with a single top-level universal node containing all other entities. In the clustering hierarchy, the clustering criteria applied at different levels may not necessarily be the same. The objective of abstraction is to reduce the amount of information required to characterize an entity visible to Nimrod routing. Nodes whose component physical assets possess different attributes rely on information abstraction in order to reduce the number of attributes used to characterize them. Abstraction procedures include, for example, eliminating attributes possessed by only a small percentage of the component physical assets or expressing attributes in terms of ranges of values exhibited by these physical assets. Multiple abstraction procedures may be applied to produce the attributes of a given node (e.g., first eliminating attributes possessed by only a few physical assets and then taking the average values of the remaining attributes for the physical assets in the node). Nimrod does not mandate the choice of clustering and abstraction procedures to invoke in an internetwork. Rather, this choice is a local one under the control of the managers of the portions of the internetwork to be represented as Nimrod nodes, and hence network managers may develop procedures that best suit their needs. We note that the specific clustering and abstraction procedures employed in an internetwork may have a significant effect on the quality of routes generated and on the cost of routing information maintenance. Hence, network managers should exercise care in selecting and using these procedures and may wish to experiment with several different ones during the evolution of their nodes. Although clustering and abstraction procedures may be fully automated, we recommend allowing manual intervention in order to enable network managers to make cost-benefit tradeoffs appropriate for their particular networks. 2.2 Nimrod Entities All of the Nimrod routing functions are performed with respect to an internetwork's representation in terms of the basic Nimrod routing entities, namely nodes and endpoints. Each Nimrod entity has a set of attributes, each of which may be established through one or more of the following methods: 1. Manual configuration. 2. Automatic acquisition during initialization. 3. Active measurement. 4. Abstraction of attributes of component nodes. A node is a set of contiguous internetwork physical assets. It may be formed by clustering physical assets directly or by clustering existing 3 Internet DraftNimrod Functionality and Protocol Specifications March 1996 nodes. If the given node itself comprises component nodes, the routing system employed to route traffic within or across the node is Nimrod routing. Otherwise, this routing system may use any other routing protocol(s). A node's attributes include its: 1. Node identifier (NID). An NID is a location-independent referent for a node. It is a globally unique, relatively short, fixed-length bit string used by Nimrod-capable devices to communicate node identity (primarily used before a node acquires its locator). 2. Locator. A node's locator is a globally unique label describing the node's position in the clustering hierarchy. It consists of the global locator of the node's enclosing node in the clustering hierarchy, concatenated with a local bit-string, called an element, unique among all component nodes and endpoints of the enclosing node. 3. A pool of locator elements that may be assigned to its component nodes and endpoints. 4. Constraints on forming associations with endpoints. An association is a relationship formed between a node and an endpoint, such that the endpoint acquires a locator from the node. A node may be associated with multiple endpoints, and an endpoint may be associated with multiple nodes. 5. Constraints on forming adjacencies with other nodes. An adjacency is a neighbor relationship formed between two nodes that have a direct communication capability. The neighbor relationship need not be symmetric. For example, nodes X and Y may agree to a relationship in which Y is adjacent to X, but X is not adjacent to Y. 6. Maps consisting of the node's current adjacencies and service offerings. 7. Credentials of the node's manager, used in forming node adjacencies and endpoint associations. An endpoint is a traffic source, destination, or both that is visible to other Nimrod entities through association with one or more Nimrod nodes. Examples of endpoints include hosts and routers or even processes within hosts and routers. An endpoint's attributes include its: 1. Endpoint identifier (EID). An EID is a location-independent referent for an endpoint. It is a globally unique, relatively short, fixed-length bit string used by Nimrod-capable devices to communicate endpoint identity. 2. Names. A endpoint name is a globally unique, variable-length, structured, ASCII string used primarily by humans to refer to the endpoints. Nimrod uses Domain Name System (DNS) names for this purpose. 4 Internet DraftNimrod Functionality and Protocol Specifications March 1996 3. Constraints on forming associations with nodes. 4. Locators. An endpoint's locators are obtained from the nodes with which the endpoint is associated. Therefore, as an endpoint may be associated with more than one node, it may obtain more than one locator. 5. Traffic service requirements from the perspectives of the endpoint as source and as destination. 6. Credentials of the endpoint and its manager, used respectively in authentication of routing information and in forming node associations. 2.3 Nimrod Routing Functions and Databases At the core of Nimrod lies a set of distributed databases containing routing information that is constructed, accessed, and acted upon by the routing functions. These databases and their relationships to the routing functions are as follows: 1. Node attributes. Each node has a set of attributes used in forming node adjacencies and endpoint associations, in constructing maps, and in assigning locators to component nodes and endpoints. 2. Endpoint attributes. Each endpoint has a set of attributes used in forming node associations and in selecting routes. 3. Endpoint/locator associations. Nimrod endpoint locators are used in generating routes between and in forwarding messages toward those endpoints. Endpoint/locator associations are stored and accessed through the DNS. 4. Maps. Each Nimrod node has a set of maps describing its traffic service offerings and adjacencies to other nodes, collectively called connectivity specifications and used in generating routes. 5. Routes. Routes are generated in response to requests on behalf of traffic sessions between endpoints. Route generation works within the constraints of the service requirements specified by the endpoints and the services and adjacencies advertised in maps. Each route is expressed in terms of nodes and their corresponding connectivity specifications and is used to construct forwarding information to be installed in routers. 6. Forwarding information. Nimrod traffic forwarding is path-oriented, where a path is defined by the forwarding state stored in routers according to the route selected and is under the control of the source and destination endpoints. 5 Internet DraftNimrod Functionality and Protocol Specifications March 1996 Databases relevant to but not maintained by Nimrod are the pool of NIDs that may be assigned to nodes and the pools of EIDs and names that may be assigned to endpoints. EIDs and NIDs may be drawn from the same number space. Each of the Nimrod routing functions uses portions of the contents of one or more of the Nimrod databases. In a dynamic internetwork, the procedures for updating and retrieving the contents of Nimrod databases will be performed frequently. Therefore, each Nimrod database is organized to optimize the performance of these procedures along the dimensions of delay, internetwork resource consumption, fault tolerance, and load balancing. Nimrod databases are maintained by a combination of routers, hosts, and special-purpose physical devices. The use of special-purpose devices means that routers and hosts do not have to assume all of the processing and memory load related to routing. For example, as route generation is a computationally intensive procedure, some network managers may elect to use dedicated devices, distinct from routers, whose sole purpose is to generate Nimrod routes. For most Nimrod databases, we suggest distributing database contents over several physical devices throughout an internetwork. In a large internetwork, one may in fact have no other choice; the memory required for a single Nimrod database may exceed the storage capacity of any one device. Also, we suggest distributing database contents with partial redundancy, such that each database entry is stored in more than one device. Distributed organization of Nimrod database contents helps to reduce the database maintenance and query-response costs borne by any one physical device. Partial redundancy helps to increase the availability of database contents and to reduce the costs of the average database query-response; it may also increase the cost of the average database update, however. 2.3.1 Nimrod Database Consistency Each Nimrod database contains routing information crucial for successful communication between endpoints. Inconsistencies between the actual state of the internetwork and the state as reflected by Nimrod database contents may result in impaired communication between a pair of endpoints and, in the worst case, may completely disrupt communication among all endpoints. Thus, minimizing the number as well as the consequences of such inconsistencies is a primary objective of the Nimrod database maintenance procedures. Inconsistencies between database contents and actual internetwork state may result from delays incurred in updating database contents following internetwork state changes. Many of the Nimrod databases are volatile and hence require mechanisms for keeping the contents current, in order to prevent propagation and use of stale routing information. Database maintenance includes rapid and reliable updating with new information as well as removal of old information. We recommend that each Nimrod database 6 Internet DraftNimrod Functionality and Protocol Specifications March 1996 be maintained as a cache, such that each entry has a finite lifetime and may be removed from the database when it expires. Cache entry lifetimes will depend upon the expected duration of the usefulness of the cached information. Inconsistencies between database contents and internetwork state may also result from errors introduced directly into database contents. Errors in Nimrod database contents may be injected inadvertently, through faults in the transmission media or in physical device memory, through misconfiguration, or through incorrect implementation of the database maintenance procedures. Errors may also be injected intentionally by malicious parties, through distribution of fictitious database updates and responses to queries (by capturing and corrupting existing database messages or by generating new messages) or through modification of database maintenance procedures. Updating and retrieval of Nimrod database contents involve frequent communication of routing information over an internetwork and hence expose this routing information to numerous potential opportunities for error introduction. Therefore, the protocols that carry out these procedures attempt to protect the routing information from introduced errors and malicious parties. In particular, the protocols for communicating information to or from a Nimrod database permit the intended recipient of that information to: 1. Authenticate the information. 2. Detect corruption of the information. 3. Determine whether the information received is newer than any related information the recipient already possesses. 4. Indicate to the sender the receipt of acceptable or unacceptable information. These protocols also permit the sender to retransmit to the intended recipient any information that it perceives the recipient has failed to receive successfully. We note that while Nimrod requires consistency between database contents and internetwork state, it does not require different physical devices to maintain identical views of internetwork state (e.g., two different routers might maintain different maps for the same node, both of which are consistent with the physical assets of that node). Furthermore, Nimrod does not require consistency in route selection across different physical devices (e.g., two different routers might select routes to the same destination such that each router is included in the other's route). The underlying path-oriented nature of message forwarding in Nimrod enables loop-free forwarding in the presence of such inconsistencies in route selection among routers. 7 Internet DraftNimrod Functionality and Protocol Specifications March 1996 2.4 Nimrod Agents Within an internetwork, each Nimrod database is stored in a set of physical devices. Each physical device containing a portion of a Nimrod database executes a set of functionality, called a Nimrod agent, for manipulating the database contents. A single device may contain portions of more than one Nimrod database and hence may contain more than one Nimrod agent. Each Nimrod agent is a Nimrod endpoint. For each Nimrod database, certain agents are responsible for maintaining specific portions. Such an agent is designated as an authoritative source for that portion of the database. A specific portion of a database may have multiple authoritative sources. Each agent is an authoritative source for some portion of a database but may also obtain and cache information learned from authoritative sources for other portions of that same database. In addition to receiving unsolicited database updates, a Nimrod agent may also refresh its database by querying other agents of the same type for their database contents. Nimrod agents and databases are organized according to the clustering hierarchy, such that each node has a set of agents that act on its behalf to answer or forward database queries. The Nimrod agents and their corresponding functions are as follows: 1. Node representatives. Each Nimrod node must have one or more representatives which maintain the database of the node's attributes and act on its behalf. A node representative is responsible for forming adjacencies with other nodes; forming associations with endpoints; assigning locator elements to component nodes and endpoints; receiving maps from component nodes; and constructing its node's maps. All node representatives for a given node must construct the same map for a node, i.e., must use the same algorithms for map construction. Node representatives are authoritative sources for the maps of the nodes they represent. 2. Endpoint representives. Each Nimrod endpoint must have one or more representatives which maintain the database of the endpoint's attributes and act on its behalf. An endpoint representative is responsible for forming associations with nodes; discovering, through the DNS, locators of the endpoints with which its endpoints wish to communicate; requesting routes to those endpoints by querying route agents, and ensuring that the routes satisfy its endpoints' service requirements; initiating path setup along the selected routes; and forwarding data along the established paths. Endpoint representatives are authoritative sources for the locators and service requirements of the endpoints they represent. 3. Route agents. Each node may have one or more route agents responsible for collecting maps from nodes throughout the internetwork and for generating and dispensing routes based on endpoint service requirements and node connectivity specificiations advertised in maps. Route agents 8 Internet DraftNimrod Functionality and Protocol Specifications March 1996 are authoritative sources for the routes they generate. 4. Forwarding agents. Each node must have one or more forwarding agents responsible for initiating neighbor relationships with forwarding agents in other nodes; requesting routes; installing forwarding information in routers; forwarding messages along established paths; and controlling traffic flow into and out of the node according to the node's access restrictions. While each of these functions could be performed by a different type of agent, we have elected to concentrate them in the forwarding agents, in order to minimize the number of different agent types performing the Nimrod routing functions. Forwarding agents are authoritative sources for the portion of the paths that traverse them. Agents acting on behalf of a node need not reside within that node. Nevertheless, we recommend locating all Nimrod agents (and their databases) close to the entities on whose behalf they act. Such location minimizes delay and internetwork resource consumption when updating the databases corresponding to those entities and in responding to queries from other agents in the vicinity of those entities. A Nimrod agent residing external to the node on whose behalf it acts must be configured with location information for that node, and in some cases for ancestral and descendant nodes as well, in order communicate with other agents that act on behalf of the same node. Also, the forwarding agents within a node must be configured with the location of agents external to but acting on behalf of that node. We recommend placing all agents within the node on whose behalf they act, and henceforth we describe agent behavior from this perspective. 9 Internet DraftNimrod Functionality and Protocol Specifications March 1996 3 Nimrod Operation : An Overview This section describes key operating procedures in Nimrod from the viewpoint of how the various databases are managed. The description is organized based on the pertinent database. Specifically, maps (construction, dissemination), routes (generation, acquisition), locators (acquisition, notification, release), adjacencies (formation, release), paths (setup, teardown, forwarding), and discovery (of neighbors, agents) are addressed. This section only provides a brief summary of the operations. For a detailed exposition, the reader is referred to [2]. In the postscript version of this document, the reader may refer to Figures 1-4 (given in Appendix 1), for a quick overview of some of these operations. Throughout this section, the text contains references in parentheses to labels in these figures. 3.1 Maps Each Nimrod node has a set of maps describing its traffic service offerings and its adjacencies. Maps are maintained and updated by node representatives. A node representative maintains two kinds of maps for its node: a basic map that depicts the child nodes, the adjacencies between child nodes and the adjacencies between child and external nodes, plus the services provided by each of these nodes; an abstract map that depicts the node, its adjacencies to other nodes and the services provided by the node between any pair of such node adjacencies. A node representative may construct its abstract map using information obtained from abstraction of basic map, configuration, or measurement of service qualities across the node. Abstraction mechanisms are not a part of the Nimrod specifications. Rather, each node may choose to implement its own abstraction algorithm (uniform throughout a given node). Maps are updated using map updates, and obtained using map queries as described below. 3.1.1 Map Update Map updates are distributed using the Update protocol described in section 5. Maps are automatically updated in response to topological changes using constrained hierarchical flooding, according to the following procedure. The update originates from a representative (Nr in Figure 1) of the node whose abstract map has changed. This node representative sends (arrow 1 in Figure 1) the new abstract map to each boundary forwarding agent (F) which is a neighbor of a boundary forwarding agent of its parent. Note that sending to each forwarding agent is necessary in order to handle the case of a partitioned node. F in turn forwards (arrow 2) the update to each Fpto which it is adjacent. That Fp sends (3.x) the map to all of the node representatives (Nrp) and all of the route agents (Rp) in the node. The change in the abstract map of a node causes a change in the basic map of the parent node. This in turn may or may not cause a change in the abstract 10 Internet DraftNimrod Functionality and Protocol Specifications March 1996 map of the parent node. If it does, then a designated node representative originates another update to the next higher level by sending (4) the new abstract map to a boundary forwarding agent. The procedure described above now applies again at this higher level. In the worst case, a change in a node's abstract map may force changes in all of its ancestral nodes' abstract maps. We expect such changes to be rare, especially in nodes whose descendants are multiply connected. 3.1.2 Map Request and Release Map requestsm, responses, and releases are transmitted using the Query-Response protocol described in section 6. A map request is sent by a route agent, acting on behalf of an endpoint wishing to obtain or subscribe to the map of a node for route computation. A map release unsubscribes to the map of the node for which a subscribe request was sent. Our description below is in terms of map request; map release is very similar. The kinds of maps that can be requested are as follows: 1. Abstract Maps. Two kinds of abstract maps can be requested - abbreviated or full. An abstract map is full if it contains service information (i.e., connectivity specifications) and abbreviated if it does not. 2. Basic Maps. Two kinds of basic maps can be requested - complete or partial. A basic map is complete if it contains abstract maps of all component nodes and is partial if it only contains maps of a proper subset of the component nodes. The abstract map of the component nodes contained in a basic map may all be either full or abbreviated. A route agent sends the map request towards the targeted node. A flag in the request indicates whether or not a subscription is requested, i.e., updates are to be automatically sent. When the map query reaches a boundary forwarding agent for the targeted node, this forwarding agent relays the query to a node representative for that node. The node representative responds to the route agent with the largest subset of the requested map that is consistent with the map distribution restrictions. If it does not have the maps to fulfill the query, or if its restrictions do not permit it to respond, it still sends a reply to the requestor containing a reason for failure. A node representative is not required to support the map subscription service. 3.2 Routes Route agents use the maps obtained, either through automatic updates or in response to explicit map requests, in order to do route generation. Endpoint representatives and forwarding agents obtain these routes from the route agent using route requests. A route specification is expressed in terms of nodes and the connectivity specifications through those nodes, and 11 Internet DraftNimrod Functionality and Protocol Specifications March 1996 is used to specify forwarding information to be installed in routers. It also lists the services provided by the route. 3.2.1 Route Generation The input to route generation includes maps of the topology, a set of session service requirements, and the source and the destination node locators. Its output includes a (set of) route(s), or an indication that no route can be found. Each route contains a sequence of node locators and connectivity specification labels for nodes that have to be traversed in order to meet the service requirements. We note that the topology used for route generation typically represents the network in varying levels of detail for different regions. Thus, the route constructed by the route generation algorithm will typically not contain the complete list of all routers through which a datagram should pass. The details are filled in at the node where they are required in a recursive fashion when setting up a path or forwarding datagrams (see section 7 for details). Route generation algorithms are not specified by Nimrod. Rather, each route agent may choose to implement its own route generation algorithm, even within a single node. 3.2.2 Route Request and Release Route requests, response, and releases are transmitted using the Query-Response protocol described in section 6. An endpoint representative or a forwarding agent that wishes to obtain a route to a destination may request a route from a route agent. The route request contains the source endpoint's EID and locators, the destination endpoint's EID and locators, and the source and/or destination traffic service requirements. Note that if there are no strict traffic service requirements, in terms of quality, monetary cost, or access restrictions, a route may not need to be acquired (the source and destination endpoint locators may suffice for the route). Note also that the route agent to which a route request is sent need not be in the same node as the requestor. A route request may also be a subscription to a route, i.e., updated routes are automatically sent to the subscriber. A route release is used to unsubscribe to a specific route. Route agents are not required to support the route subscription service in this version of Nimrod. In response to a route request, a route agent first searches its route database for a set of feasible routes and if unsuccessful, invokes the route generation algorithm. The route agent may, in the process of attempting to generate feasible routes, obtain more maps of nodes using the map query procedure described in section 3.1.2. A route agent responds to the 12 Internet DraftNimrod Functionality and Protocol Specifications March 1996 requestor with either a set of feasible routes or an indication that no feasible route could be found. 3.3 Locators Nimrod nodes and endpoints require locators for routing. Each node has exactly one locator and each endpoint is associated with at least one locator. Locators are assigned during initialization following activation, reconfiguration, or movement. The representatives of a node are responsible for acquiring the node locator, and the endpoint representative is responsible for acquiring the locators for each of its endpoints. 3.3.1 Acquiring and Releasing Node Locators Node locator requests, responses, and releases are transmitted using the Query-Response protocol described in section 6. Node locator acquisition involves two phases. First, the designated representative of a node acquires a locator from a representative of its parent node. Next, it notifies all of the representatives within its node and all descendant nodes of the existence of the new locator. The first phase is illustrated in Appendix 1, Figure 2 and the second phase in Figure 3. The designated node representative (Nr in Figure 3) wishing to acquire a locator for a node Z first determines the node P from which its locator should be acquired. This node representative (Nr) then sends (1) a locator request message to a boundary forwarding agent (F) which forwards (2) the locator request message to the neighboring boundary forwarding agent in the parent node, which in turn relays (3) the message to a node representative for P (Nrp). The request contains information that enables the recipient node representative (Nrp) to evaluate the request and decide whether it can or wants to honor the request. The node representative responds (4) either with a new node locator (if it decides to honor the request), unique among the locators of P's component nodes, or a denial response otherwise. Upon receiving a positive response, the originating node representative (Nr) decides whether to accept the locator. If it (Nr) decides to accept the locator, the node representative starts the notification phase (refer Fig 3). Locator notifications are distributed using the Update protocol described in section 5. The node representative notifies all agents in its node (arrows 5.x), and all agents in Z's descendant nodes, of the new locator. The latter is done by forwarding the message to each forwarding agent in Z which is a neighbor of a forwarding agent for one of Z's component nodes. These forwarding agents (Fc) in the component nodes distribute the message to all agents in the component nodes including boundary forwarding agents (Fcc) to their children and so on until the locator trickles down to all of the nodes that have Z as an ancestor. 13 Internet DraftNimrod Functionality and Protocol Specifications March 1996 A locator release may be sent by a node representative of a node wishing to unsubscribe to a locator. This could happen, for instance, if an organization changes its service provider, or due to mobility of a network. The node representative includes the old locator to be released, and the locator and EID of the node representative that issued the locator, in its locator release message to its parent. 3.3.2 Acquiring and Releasing Endpoint Locators Endpoint locator requests, responses, and releases are transmitted using the Query-Response protocol described in section 6. An endoint representative attempts to acquire a set of locators for each of its endpoints. The endpoint representative, say Er, selects a set of target nodes and for each selected node Z, sends a locator request message identifying Z (label 5 in Figure 2) to a node representative for Z. As in the case of node locators, if this node representative decides to honor the request, it sends a response (6) containing the locator. 3.4 Adjacencies An adjacency is a neighbor relationship formed between two nodes that are physically joined. The neighbor relationship need not be symmetric, i.e., node A may be adjacent to node B but not vice versa. Adjacencies of a node Z to an external node Y may be formed by clustering together adjacencies of component nodes of Z to Y. At the lowest level, adjacencies are the physical connections themselves. 3.4.1 Acquiring, Activating, and Releasing Adjacencies Adjacency requests, responses, releases, and activations are transmitted using the Query-Response protocol described in section 6. The distribution of A single designated node representative is responsible for forming adjacencies between its node and neighboring nodes. When forming adjacencies by clustering existing adjacencies (or physical connections), the node representative obtains candidate external adjacencies from the node's basic map and groups these adjacencies according to which of their destination nodes are components of the same enclosing node. This information defines the target node for the adjacency formation requests. For each candidate adjacency, the node representative initiates an adjacency formation procedure (depicted in Appendix 1 - Figure 4). The node representative (Nr) begins by sending an adjacency request (1) to a node representative for the specified node (Nrs). Using information present in this request, the recipient node representative (Nrs) determines whether or not to honor the request, and replies (2) to the requesting node representative (Nr) about its decision. If the response is positive, then 14 Internet DraftNimrod Functionality and Protocol Specifications March 1996 the node representative decides whether or not to accept the adjacency. If it decides to accept, then it updates (3.x) all of the node representatives of the newly formed adjacency. The node representative at the other end of the adjacency (Nrs) also updates (4.x) all node representatives within its node. The adjacency updates to node representatives in the nodes forming the adjacency are distributed using the Update protocol described in section 5. In addition, the adjacency is ``activated'' by having the two node representatives inform the respective boundary forwarding agents constituting the adjacency that Nimrod data traffic may now be passed. If a node representative receives a negative reply to an adjacency request message, the message may contain information that indicates that the adjacency is not appropriate. An adjacency is terminated by sending an adjacency release request to the node representative which granted the adjacency. Management decisions and lack of data for a specified period of time may be other reasons for terminating an adjacency. 3.5 Paths Nimrod supports two distinct data message forwarding modes: flow and datagram. For each mode, a forwarding agent's ``next-hop'' forwarding decision is dictated by the information stored in its forwarding database and by information contained within the message to be forwarded. Flow mode requires the establishment of session-specific forwarding state in certain forwarding agents along the routes selected for a traffic session. With flow mode, each session is assigned one or more paths, derived from the selected routes. A path corresponds to forwarding state stored in forwarding agents along a route, and each path has a label which is unique within all of these forwarding agents (but not necessarily globally unique). Distinct traffic sessions may use the same path, and distinct paths may use the same route. The minimum forwarding state required for flow-mode forwarding includes linkages between the path label and the path's previous- and next-hop forwarding agents (and service guarantees for traffic control, if any). In flow mode, data messages carry the path label(s) that guides the message forwarding decisions at forwarding agents along the path. Datagram mode does not require the establishment of any session-specific forwarding state. In datagram mode, data messages carry a description of the selected route, which guides the message forwarding decisions at forwarding agents along the route. Each forwarding agent at the beginning of a route segment (the portion of a route between two successive nodes listed in a route specification) makes an independent forwarding decision for that segment, and hence the session source and destination relinquish some control over message forwarding. However, datagram mode provides robust forwarding, in the sense that the intermediate forwarding agents can base their message forwarding decisions on the current state of their portion of the internetwork. Both of the Nimrod forwarding modes rely on the existence of underlying 15 Internet DraftNimrod Functionality and Protocol Specifications March 1996 paths to fill in route segments. A path may connect a source endpoint to one or more destination endpoints. Forwarding agents execute path management procedures to install path state in and remove path state from their forwarding databases. With these procedures, Nimrod provides support for management and use of unicast and multicast paths. We note, however, that multicast group management and multicast route construction are not part of this initial version of Nimrod. These and other multicast issues are treated in detail in [4]. For simplicity of discussion, we focus on unicast paths in the remainder of this section. 3.5.1 Path Setup Paths may be set up from source to destination or from destination to source. Each path has an initiator and a target. We expect that most paths will be set up from the source endpoint to the destination endpoint. Hence, the initiator usually begins the path setup procedure on behalf of the source endpoint, and the target usually accepts or rejects a path on behalf of the destination endpoint. Nimrod paths are inherently multilevel as follows. We begin with a single path, p0, derived from the selected route between the source and destination endpoints for the traffic session. (The superscript indexes the level of the path, where the top level is 0.) This path comprises multiple contiguous paths, p11;: ::;p1n, one for each of the n segments of the route on which p0is based. (The subscript indexes the path for the corresponding route segment of the higher level path.) Each p1jitself comprises multiple contiguous paths corresponding to each of its segments, and so on. In general, for each pijcomposing pi-1k= pi, the initiator and target of pij maintain linkages to the path pi-1k(pi), which helps to guide forwarding along the successive segments of pi-1k(pi). Forwarding agents and endpoint representatives try to form paths by piecing together existing paths rather than by setting up new paths. This method provides the lowest-cost message forwarding in terms of the amount of route generation and forwarding state installation required. In a busy internetwork, there are likely to be many existing paths, and hence we expect this mechanism to be much less expensive than individually setting up and maintaining paths for each traffic session. We now describe how a new traffic session uses paths at multiple levels, distinguishing the actions in flow mode and datagram mode where appropriate. Whenever the endpoint representative receives a data transport request, it always checks whether there already exists a satisfactory path for the session. This is true whether the new session desires flow or datagram mode forwarding. If a satisfactory path exists, the endpoint representative links the session to the path and forwards session traffic along that path. If no such path exists, however, the endpoint representative attempts to obtain a feasible route for the session. Note that route generation might 16 Internet DraftNimrod Functionality and Protocol Specifications March 1996 not be required and that a feasible route might include only the source and destination locators. After obtaining a feasible route, the endpoint representative proceeds to determine where to install the necessary forwarding state. Flow mode:The endpoint representative becomes the initiator of a new path, p0, and generates a path setup message. If the route contains more than the source and destination locators, the endpoint representative then checks whether there already exists a satisfactory path for the session from itself to the next node in the route specification. Provided such a path, p11, exists, the endpoint representative proceeds as follows: Flow mode:The initiator of p11 (which is also the initiator of p0) links p0 and p11in its forwarding database and sends p0's setup message to the target of p11. Upon reception of the setup message, the target of p11 also links p0 and p11in its forwarding database. Datagram mode:The initiator of p11 sends the data message to the target of p11. If no satisfactory path, p11, yet exists between the first two nodes in the route specification, the endpoint representative attempts to form such a path by piecing together existing paths. The endpoint representative attempts to find an existing path whose destination locator is the longest match on the next node's locator and is within the context of the two nodes (i.e., the lowest node in the hierarchy that contains both nodes). If such a path, p21, exists, the endpoint representative proceeds as it did with p11. If the endpoint representative fails to find a satisfactory path to any of the second node's ancestral nodes contained within the context, then there are no ``direct'' paths to the second node. The endpoint representative then seeks a path up to the its node's enclosing node, as there are likely to be more existing paths between higher-level entities. To this end, the endpoint representative checks whether there already exists a satisfactory path whose target is an exit point of the its node's enclosing node. If such a path, p21, exists, the endpoint representative proceeds as it did with p11. Otherwise, the endpoint representative attempts to obtain a feasible route and set up a path, p21. If there are no short-cut paths from the its node's enclosing node to any of the second node's ancestral nodes in the context, the above procedure may need to be repeated for successively higher-level ancestors of the endpoint representative's node, up to but not including the context. If no short-cut paths exist at any of these levels, a route must be generated and a path set up, from the node below the context and containing the first node to the second node. 17 Internet DraftNimrod Functionality and Protocol Specifications March 1996 This iterative path formation procedure is performed by the target of each path thus selected, which then becomes the initiator for the path for the next segment, and so. Note that in the above description, the words ``endpoint representative'' should be replaced by ``forwarding agent'' when referring to the actions taken by intermediate agents along a path. The procedure terminates after attaining the last node in the route and the target endpoint representative in that node, possibly linking together paths at many different levels. In the presence of multilevel paths, each data message carries a nested sequence of path labels, in order to enable all forwarding agents involved in the paths to forward the message correctly. Intermediate forwarding agents update the path labels in the message, according to the linkages between paths stored in their forwarding databases. Upon receipt of a data message, the target of path pjifinds it is linked to path pj-1k=pj which in turn is linked to path pji+1and hence is the initiator of pji+1. This forwarding agent strips off the label for pjiand replaces it with the label for pji+1, before forwarding the message along that path. 3.5.2 Path Acceptance Each setup message in flow mode and each data message in datagram mode contains the route specification and additional service requirements, such as resource reservation requests. A boundary forwarding agent or endpoint representative receiving a setup or datagram message determines message acceptability. Acceptability is in part based on the perceived consistency between the route specification and service requirements contained in the message and the service attributes of each node traversed. When a forwarding agent refuses a setup message, it informs the other forwarding agents on the path between and including itself and the initiator. At the target, once a setup message passes the service attribute consistency check, it must also pass an endpoint-specific consistency check. In particular, the target determines the perceived consistency between the route specification and service requirements contained in the message and the service requirements of the target endpoint. Each target that accepts a setup message informs the initiator. If there is an inconsistency with the target endpoint's service requirements, the target takes one of two actions, depending upon whether the target is the path's destination or source: 1. If the target is at the destination endpoint, it returns to the initiator a message containing its endpoints' destination service requirements. The initiator is then responsible for obtaining a route and setting up a path that is consistent with both the source and destination service requirements. 2. If the target is at the source endpoint, it returns to the initiator a 18 Internet DraftNimrod Functionality and Protocol Specifications March 1996 message indicating that it will generate its own route. The target is then responsible for obtaining a route and setting up a path that is consistent with the source service requirements and the destination service requirements contained in the setup message. Any forwarding agent or endpoint representative may tear down a path by removing the corresponding forwarding state from its forwarding database. Reasons for path teardown include: o Detection of a connectivity failure along a path. o A change in node service attributes or traffic service requirements such that the route on which the path is based is no longer feasible. o Path expiration if a path exceeds a maximum prescribed lifetime. o Path preemption in favor of another path. 3.6 Control Message Integrity and Authentication Nimrod control messages (all messages except data messages are considered to be control messages) include several pieces of information which permit recipient agents to determine whether the message has been corrupted in some way. In addition to information on type and length of various sections of the message, each Nimrod control message contains its generation timestamp, expressed in seconds elapsed since 0 hours on 1 January 1900 (same format as the NTP timestamp [6]), as well as ``authentication'' information that simultaneously acts as a checksum and as source authentication. 3.6.1 Timestamps Timestamps establish message recency and hence help recipients detect message replays. In order to detect whether a Nimrod control message is timely, the recipient agent compares its local time with the timestamp contained in the control message. If the timestamp is less recent than the local time by no more than ffi seconds or more recent than the local time by no more than ffl seconds, the message is considered to be timely. Otherwise, the message is considered to be out-of-date. Nimrod agents do not require fine-grained time synchronization in order to make their message recency determinations. Time synchonization on the order of minutes is all that is required. In fact, periodic manual adjusting of local clocks should be sufficient to maintain the necessary synchronization among agents. 19 Internet DraftNimrod Functionality and Protocol Specifications March 1996 3.6.2 Authentication This initial version of Nimrod does not contain any specification of security measures for Nimrod but rather place holders for such security measures to be introduced in a future version. Nevertheless, we do make recommendations for what these security measures might be. Most Nimrod control messages are generated by a single agent but distributed to many different agents, and most parts of these messages remain constant as the messages are passed among agents. To prevent communication problems caused by errors introduced into these messages which carrying routing-related information, each recipient agent should be able to determine with high confidence whether the message has indeed been generated by the stated source and whether the constant portions of the message have been modified since being generated by that source. We recommend that each Nimrod control message carry a public-key-based digital signature covering a reduced form of the constant portions of the message (e.g., apply the MD5 hashing function followed by the RSA signing function to the constant portions of the message). The authentication information may also include the public key to be used to verify the signature together with its certificate. While the RSA signing procedure is computationally intensive, signature verification is not. As long as control message generation at a particular agent is infrequent, that agent should be able to handle the load imposed by signing. Discovery messages are the only control messages generated frequently (i.e., inter-message period on the order of tens of seconds); an alternative mechanism may be required to protect these messages. The authentication information field in Nimrod control messages is represented as type, length, and value and hence is able to accommodate any integrity and security information that may be desired or required in the future. 20 Internet DraftNimrod Functionality and Protocol Specifications March 1996 4 Reliable Transaction Protocol Many Nimrod control messages reliable delivery. Rather than have each agent duplicate this reliability functionality, Nimrod includes a reliable transaction service, which provides its clients the ability to reliably communicate arbitrary size blocks of information between a client and a peer and to receive an arbitrary size reply in approximately one round-trip time. The reliable transaction service is built on Transaction-TCP (T/TCP) [10], [9]. T/TCP is a backwards-compatible extension of TCP, which is opti,mized for request/response interactions. In particular, T/TCP may bypass the normal three-way handshake required at TCP connection setup time. This bypass is accomplished by adding a ``connection count'' option in the TCP header, and by maintaining per-host connection history at both client and server. This information allows the server to correctly distinguish a new connection open (SYN, no ACK) from a duplicate or out-of-order open, without shaking hands with the client. Using T/TCP, the client can obtain a response to a request message in one round-trip-time to the server and back (plus the server's processing time). T/TCP uses the normal three-way close handshake; it does not impact transaction latency. 4.1 Services Interface The reliable transaction service permits one or more transactions to be invoked at a peer. The service interface is: o Flags, misellaneous flags. o Source locator and EID of the transaction. o Destination locator and EID of the transaction. o Keying info, for authentication purposes. o Service requirements for the transactions. o Transaction, beginning with a protocol header (e.g., Query-Response or Update). Each transaction uses a separate TCP connection. We note that this may cause excessive overhead if the client(s) invoke many transactions within a short period of time, and is an issue to be examined more carefully in future versions of Nimrod. The beginning of each transaction is the transaction header, containing the following fields. The packet formats are illustrated and specified values given in section 9.4. o Length(32 bits) of the transaction, including this field. o Version(2 bits) of Nimrod update and query-response protocols. 21 Internet DraftNimrod Functionality and Protocol Specifications March 1996 o Protocol(2 bits) identifier. Whether Update, Query, Response, or Discovery message. o Operation(4 bits). Particular operation within the protocol. o Phase(8 bits). The Update protocol uses several phases for certain operations. This denotes the current phase. o Transaction ID(16 bits). To identify the transaction. o Timestamp(32 bits). Seconds since 1/1/1900, 00:00. The user may abort an initiated transaction at any time. Note that race conditions are possible as the aborted opertion may have actually been performed by the peer. There is no rollback facility provided by the reliable transaction service. 22 Internet DraftNimrod Functionality and Protocol Specifications March 1996 5 The Update Protocol The Update Protocol is used to update database contents (e.g., the map database). The peers in the Update Protocol are the Nimrod agents, currently including the forwarding agents, node representatives, route agents, and endpoint representatives. These agents participate in the distribution of the updated information in the required portion of the network. The implicit flooding constituting the protocol is carefully constrained by involving only a few agents per update. 5.1 Service Interface The Update Protocol offers a distributed database update service in a manner that renders the exact locations of the database transparent to the user. The portion of the distributed database updated is dependent on the particular database and the operation as indicated by the user. The service interface includes the following: o Source. EID and optionally locator of the agent initating the update. o Destination. EID and optionally locator of a specific agent (e.g., endpoint representative whose locator has changed). May be left unspecified. o Operation. Indicates what kind of update (i.e., for what database) it is. Current values are shown in section 9. o Keying info for authentication purposes. o Service requirements if any. Will be ``best effort'' if unspecified. o Patience. A time interval within which the user wishes to hear about the success of the update. The Update Protocol provides hop-by-hop reliablity, but no effort is made to ensure end-to-end reliablity. An agent that has initiated an update cannot be certain that the message has been delivered to all intended agents, or that all intended database portions have been updated. We believe that the resource and complexity overhead demanded by an end-to-end reliablity mechanism is not justified by the importance for database updates (note that Nimrod does not require absolute database consistency (see section 2.3.1)). The user may abort a previously initiated update, for instance, because an update is superseded by more recent information. The protocol will discard the update if it has not already been sent out. However, no rollback facility is provided. 23 Internet DraftNimrod Functionality and Protocol Specifications March 1996 5.2 Protocol Operation The Update Protocol consists of an Update Message that is generated by the agent wishing to make an update to a particular database. (The Update Message consists of a variable length database specific portion, described in section 5.3, prepended by a common update protocol header, described in section 5.2.1 below, prepended by the transaction header, described in section 4.) The database may be held redundantly or cooperatively by multiple agents in a node, and an update may involve several nodes in the hierarchy. Thus, the update protocol involves several cooperating communicating agents. We classify the participating (peer) agents into two for ease of description: the originating agent and the transit agents. The originating agent forwards the message to one or more agents which further forward it to other agents and so on, until all the necessary database locations have been updated. Once an originating or transit agent has successfully forwarded a message, it does not retain any state corresponding to the message. The originating and transit agent operations are described in more detail later in this section. The Update Message uses the reliable transaction service (see section 4). Since no effort is made to provide end-to-end reliability, no acknowledgements (positive or negative) are part of the Update Protocol. Exceptions are handled by making a log entry into a file. The actions performed by an agent upon receipt of an Update Message is a function of the receiving agent type and of the user supplied Phase of the message, which are contained in the transaction header. Examples of operation types are map update, locator update, etc. The actions include the decision of whether to cache the message or not, and whether to forward the message further, and if so to whom. We specify such actions corresponding to each agent type (columns) and operation type (rows) pair using an Update Message Action Table (UMAT) shown in section 5.2.4. We note that the update protocol is an application level protocol between a set of peer agents indicated in the destination field of the Nimrod header (or the IP header). In transit between these peer agents, the Update Message map may be forwarded through other intermediate agents, which are not peers in the protocol. For instance, an update message from agent A1to agent A2may go through (forwarding) agents a1, a2, ..., ak before reaching A2. However, such an agent ai is not a peer, and does not act upon the message using the UMAT. 5.2.1 Update Header Each item in the common update header is explained below. The packet format of the header is illustrated in section 9.5. 24 Internet DraftNimrod Functionality and Protocol Specifications March 1996 o Originating agent type(8 bits). The type of agent originating the update. Current agent types include Forwarding Agent, Endpoint Representative, Node Representative, and Route Agent. o Destination agents type(8 bits). The type(s) of agent(s) for whom the update is intended. For multiple agents, the field contains a bitwise-OR of respective agent types. o Flags(16 bits). Miscellaneous operation dependent flags. o Database Type(8 bits). The type of the database that is being updated. At most one kind of database can be updated with an update message. o Database timestamp(24 bits). Denotes the origination time of the message with respect to the originating agent EID. That is, the timestamp and the EID together identify the packet uniquely, modulo wraparounds. The timestamp is the lower 24 bits of the the current time in seconds, beginning 0:00 1 January 1900. o Destination NID (8 bytes). The update is restricted to this node. Refer to section 11.5 for NID format. o Originating EID (8 bytes). EID of the agent that issued the update. Refer to section 11.3 for EID format. o Originating Locator. Locator of the agent that issued the update. Refer to section 11.2 for locator format. o Authenticator. Authentication field. Contains authentication information for the agent originating the update. 5.2.2 Originating Agent Operations An originating agent issuing the update constructs Update Message database-specific information (update) and fills in the transaction and common update protocol headers, including the timestamp that is incremented for every update originating from the agent. Note that the user-specified Operation is placed in the ``operation'' field of the transaction header. The UMAT is then consulted to obtain the actions, which typically involve sending the Update Message to one or more next-hop agents. This could be in terms of specific agents, all agents of a given type, or any agent of a given type. Using the destination agent's EID, locator, etc., the Update Message is enclosed within the appropriate headers (see section 9) and sent. Note that the protocol calls for one-to-one individual transmissions (no multicast) to the next-hop peer agents. If it is required that the message be sent to any one agent of a given type, each agent of that type is tried until successful. An update failure occurs if a specified agent is unreachable or 25 Internet DraftNimrod Functionality and Protocol Specifications March 1996 if (in case of ``any agent of given type'') no agent of a given type is reachable. Update failures should be logged for possible network management action. 5.2.3 Transit Agent Operations A transit agent receives an Update Message as ``TCP data''. It then performs checks on the message to determine whether the message is a valid one. This may include checking the timestamp in the update header to ensure that the Update Message is not a duplicate, and verifying the authenticator in the update header. If any of the checks fail, the error should be logged for possible network management action. If the checks pass, then the UMAT is consulted for actions using the Phase field in the transaction header. This may involve caching the information (i.e., updating the relevant database using the message contents) and/or sending the message with a changed Phase, to one or more next-hop agents. This could be in terms of specific agents, all agents of a given type, or any agent of a given type. Using the destination agent's EID, locator, etc., the Update Message is sent as TCP data. Note that the protocol calls for one-to-one individual transmissions (no multicast) to the next-hop peer agents. If it is required that the message be sent to any one agent of a given type, each agent of that type is tried until successful. An update failure occurs if a specified agent is unreachable or if (in case of ``any agent of given type'') no agent of a given type is reachable. Update failures should be logged for possible network management action. 5.2.4 The Update Message Action Table (UMAT) The UMAT represents Update Message forwarding instructions based on agent and phase, and depends on what functionality is mapped into the protocol and how the mapping is done. The Update Protocol is used for map updates (section 3.1), locator updates(section 3.3), and adjacency updates (section 3.4). Our use of the UMAT is mainly to provide a succinct and flexible protocol specification. While it is clearly not necessary that an implementation use an UMAT-equivalent, it is strongly recommended from experience since it provides flexibility by making it easy to change the functionality and the mapping - one simply needs to add additional message types and/or alter the entries in the table. The Update Protocol is typically used by Nimrod agents or other ``users'' in order to initiate updates. We use the term client to denote such users. For each of the four agent types (Forwarding Agent, Endpoint Representative, Node Representative, and Route Agent), we give below the actions upon receipt of an Update Message of each phase. The phases form the rows, and 26 Internet DraftNimrod Functionality and Protocol Specifications March 1996 _____________________________________________________________________________ ||________________________||_____F_________|_______N_________|__R___|__E___||__ ||_CLIENT-MAP-UPD_________||_______________|send(1,_,F-P)(1)_|______|______||_ ||_phase-map-forw-par_(1)_||send(2,P,F-C)___|________________|______|______||_ ||_phase-map-distrib_(2)_s||end(3,_,{R*,N*})_|_______________|______|______||_ ||_phase-map-notify_(3)___||_______________|_____cache_______|cache_|______||__ ||_CLIENT-LOC-UPD_________||_______________|_send(4,_,*)(2)__|______|______||_ || phase-loc-notify (4) || cache | cache |cache |cache || ||________________________||send(5,C,F-P)___|________________|______|______||_ ||_phase-loc-child_(5)____||_send(4,*)_____|_________________|______|______||_ ||_CLIENT-ADJ-UPD_________||_______________|__send(6,_,N*)___|______|______||_ ||_phase-adj-notify_(6)___||_______________|_____cache_______|______|______||__ Table 1: Update Message Action Table for each agent type (columns) upon receipt of message with each Operation Type (rows). . the value of each phase is indicated within paranthesis. Some operations are client requests, and these are denoted in upper case. Note that to a given agent, only the column corresponding to its agent type is of interest, and thus every agent may be thought of as implementing a column of the UMAT. The actions primarily involve the functions described, along with their parameter legends, below. We assume the existence of forwarding functionality required to realize these functions. 1. send(Phase, [Node] , [AgentType][*]). This sends an Update Message with phase field denoted by Phase to an agent of AgentType in Node. The AgentType is one of N, F, R, E, F-P (boundary to/from parent), or F-C (boundary to/from child). A suffix `*' denotes all agents of the type. If AgentType is omitted, it means all agents in the specified node. For the Node field, P, C and S denote a parent, child, and sibling nodes respectively. If it is absent, it means the current node. 2. cache. Update the relevant data structures containing the database. In the postscript version, the reader may refer to Figures 1 through 4 in Appendix 1 for assistance in understanding the protocol. 5.3 Database Specific Updates As mentioned earlier, the Update messages contain a database specific information, depending on the operation being performed. In this section, we describe the database specific contents and their semantics for each operation. This information is referred to as ``additional information'' in the following. The packet formats for the additional fields are illustrated in section 9.6. 27 Internet DraftNimrod Functionality and Protocol Specifications March 1996 5.3.1 Adjacency Updates After an adjacency has been formed, the node representatives of the nodes constituting the adjacency have to be informed, so that they may modify their maps accordingly. Note that there are two adjacency updates sent for each uni-directional adjacency: one from the node representative that sent the Adjacency Request query and one from the node representative that sent the Adjacency Request response. The additional information in the adjacency updates is: o Flags, indicating whether the adjacency is to a parent, child, or sibling. o Neighbor node NID and locator. o Locator of boundary forwarding agent that implements the adjacency. 5.3.2 Locator Updates A node representative that changes a locator acquired by an endpoint representative must notify that endpoint representative if the locator changes or becomes unusable, e.g., the association between the node and endpoint is being terminated. The additional information contained in such an update is: o Flags, indicating nature of change (e.g., depreciate use of old locator, terminate use of old locator). o Credentials of the representative originating update. o Old locator that is being changed/terminated. o EID and locator (optional) of the supplier of the old locator, if different from the originator. Either both EID and locator are present or both are absent. o New locator (optional) or reassigned locator. o Expiration (optional, present only if new locator is present) time for the new locator. The representative of a node that acquires a new locator must update all of its children so that they can change their locator. Also, a node representative that changes a locator acquired by a component node must notify that component node if the locator changes or becomes unusable, e.g., the parent-child relationship is being terminated. The additional information contained in such an update is: 28 Internet DraftNimrod Functionality and Protocol Specifications March 1996 o Flags, indicating nature of change (e.g., depreciate use of old locator, terminate use of old locator). o Credentials of the representative originating update. o Old locator that is being changed/terminated. o EID and locator (optional) of the supplier of the old locator, if different from the originator. Either both EID and locator are present or both are absent. o New locator (optional) or reassigned locator. o Expiration (optional, present only if new locator is present) time for the new locator. 5.3.3 Map Updates Whenever a node's topology or offered services change, it must generate a new set of maps. The new maps must be propagated to the node representatives and route agents in the node's parent. The maps are also sent to any agents that have explicitly requested to be notified of updates, if an implementation supports the subscription functionality. o Flags. Qualifies the map (e.g., one or more component nodes not in map, map is of a partitioned node). o Sequence number (24 bits) of the transaction that requested explicit (automatic) updates. o Map. Abstract map of node. o Maps (optional) to specific agents as requested. 29 Internet DraftNimrod Functionality and Protocol Specifications March 1996 6 The Query-Response Protocol The Query-Response (Q-R) Protocol is used to obtain database information(e.g., portions of the map database) in an efficient manner. The Q-R Protocol consists of two messages: the Query Message and the Response Message. (The Query and Response Messages consist of a variable length database specific portion, described in section 6.4, prepended by a common Query/Response Protocol header, described in section 6.3 below, prepended by the transaction header, described in section 4.) The Query Message is generated by the agent wishing to make a query, contains the nature of the information required, and is sent directly to a destination agent that the originating agent believes is in possession of the information. The destination agent obtains the requisite information and sends the Response Message back to the originating agent. Note that the destination agent may obtain the information from its own database, or may in turn send a Query to another agent in order to obtain this information. 6.1 Service Interface The Q-R protocol offers a reliable query-response service in one round trip time. It uses the reliable transaction service. In fact, excepting headers and minor interface differences, the Q-R protocol adds very little to the service provided by the transaction service. o Originator. EID (and optionally locator) of the agent initiating the query. o Destination. EID (and optionally locator) of the destination agent being queried. o Operation. Indicates what kind of query (i.e., for what database) it is. Current values are shown in section 9. o Keying info for authentication purposes. o Service requirements if any. Will be ``best effort'' if unspecified. o Patience. A time interval that the user wishes to wait for the response to the query. If there is no response within this time, the user expects to be informed. 6.2 Protocol Operation Unlike the update protocol, the Q-R Protocol involves only two agents - the originator and destination. The Query Message header (given below) contains the EID and locator of the querying agent. These fields are used by the destination agent for the destination of the response. The destination agent verifies the authentication information to ensure that the query can indeed be honored. Should the authentication check fail or if the 30 Internet DraftNimrod Functionality and Protocol Specifications March 1996 destination agent is unable to supply the required information, it still sends a response back with the appropriate error code. If the originator does not get a response within a certain time t, it is informed of a query failure. The value of t is given to the protocol by the application (e.g., map request). The application also has the option of requesting an abort of the query - in this case, the state is reset and the response is ignored. As in the case of the Update Protocol, exceptions are handled by making a log entry into a file for possible network management action. 6.3 Query/Response Header Each item in the common Query/Response header is given below. The packet format of the header is illustrated in section 9.5. o Originating agent type (8 bits). The type of agent originating the query. Agent types include Forwarding Agent, Endpoint Representative, Node Representative, and Route Agent. o Destination agent type (8 bits). The type of agent for whom the query is intended. o Flags (16 bits). Miscellaneous operation dependent flags. o Database Type (8 bits). The type of the database to which the information being queried pertains. At most one kind of database can be queried with a query message. Database types are defined in section 9.5. o Count (8 bits). Operation dependent. o Opcode (16 bits) In a query, operation specific or database specific information. In a response, zero if query is being responded to successfully, otherwise an error code indicating the reason for failure. o Originating EID. In a query, the EID of the agent that issued the query. Used to obtain the destination for the response. In a response, the EID of the agent issuing the response. o Originating Locator. In a query, the locator of the agent that issued the query. Used to obtain the destination for the response. In a response, the locator of the agent issuing the response. o Authenticator. Authentication field contains the information used to authenticate the query (in Query) or the response (in Reply). 31 Internet DraftNimrod Functionality and Protocol Specifications March 1996 6.4 Database Specific Request/Release As mentioned earlier, the Query and Response messages contain a database specific information, depending on the operation being performed. In this section, we describe the database specific contents and their semantics for each operation. This information is referred to as ``additional information'' in the following. The packet formats for all of the packets in this section are illustrated in section 9.7. 6.4.1 Adjacency Formation The designated representative of a node forms adjacencies with a neighboring node by sending an adjacency request message to one of the neighboring node's representatives. Any resulting adjacency is one-way, from the node requesting the adjacency to that which granted it. The additional information in an adjacency request Query Message is: o Locator of the node initiating the adjacency. o NID of the node initiating the adjacency. o Circuit ID. Physical circuit identifier of the link to form the adjacency, as known in the originating node. o Neighbor NID of the intended neighbor node in the adjacency. The additional information in an adjacency request Response Message is: o Credentials of the granting node. o Locator of the granting node. o NID of the granting node. o Circuit ID. Physical circuit identifier of the link to form the adjacency, as known in the granting node. 6.4.2 Adjacency Release If a node representative receives a positive reply to an adjacency request message, the message may contain information that indicates that the adjacency is not appropriate. An adjacency is terminated by sending an adjacency release request to the node representative which granted the adjacency. Node mobility and management policy changes may also induce a node to release adjacencies. The additional information in an adjacency release Query Message is: 32 Internet DraftNimrod Functionality and Protocol Specifications March 1996 o Opcode giving a reason for terminating the adjacency (e.g., policy, lack of traffic, movement, etc.). o Locator of the requesting node. o NID of the requesting node. o Circuit ID of the link forming the adjacency, as known in the requesting node. o Neighbor NID of the granting neighbor node. o Circuit ID of the link forming the adjacency, as known in the granting neighbor. The adjacency release response contains indication of success or failure (reason code if latter). It does not contain any other message-specific information. 6.4.3 Adjacency Activation When a node representative has formed an adjacency with a neighbor node, the boundary forwarding agent connected to the neighbor must be informed that Nimrod data traffic may be passed to the neighbor. Note that there are two instances of the Adjacency Activation associated with each uni-directional adjacency, one from the node representative that sent the Adjacency Request query to its boundary forwarding agent indicating outgoing connectivity, and one from the node representative that sent the Adjacency Request reply to its boundary forwarding agent indicating incoming connectivity. The additional information in an Adjacency activation request is: o Flags, indicating whether the adjacency to be activated is to a parent, child, or sibling. o Locator of requesting node. o NID of requesting node. o Circuit ID of the link forming the adjacency as known in the requesting node. o Neighbor NID of granting node. o Circuit ID of the link forming the adjacency as known in the granting node. 33 Internet DraftNimrod Functionality and Protocol Specifications March 1996 6.4.4 Locator Acquisition There are two forms of locator acquisition: one for a component node requesting its locator from a node representative of the parent node, and one for endpoint representatives requesting a locator for an endpoint from a node representative of the node. The two forms are distinguished by the originating agent type field in the common Query/Response header. The additional information in a locator acquisition Query Message, from a component node is: o Old locator (optional), previously assigned locator, requestor wants it to be reassigned. o EID and locator (optional) of the node representative that previously assigned the locator. Either both EID and locator are present or both are absent. o Parent NID of the node to provide the locator. o Child NID of the node requesting the locator. The additional information in a locator acquisition Query Message, from an endpoint representative is: o Old locator (optional). Previously assigned locator; requestor wants it to be reassigned. o EID and locator (optional), of the node representative that previously assigned the locator. Either both EID and locator are present or both are absent. o Provider NID of the node to provide the locator. o Name of the endpoint requesting a locator. o EID of the endpoint requesting a locator. The locator acquisition Response Message, for a request from a component node or an endpoint contains the following additional information: o Flags indicating nature of error if any, 0 if okay (e.g., might indicate that another agent may be able to provide it (see below)). o New/Reassigned Locator (optional, present when successful) that the requestor and its descendants should use as prefix. o Expiration time of the locator supplied. o EID (optional) of node representative that might be able to (re)assign the locator. 34 Internet DraftNimrod Functionality and Protocol Specifications March 1996 o Locator (optional) of node representative that might (re)assign the locator. o NID (optional) of node containing representative that might (re)assign locator. 6.4.5 Locator Release The locator release operation is used by a component node or endpoint representative that wishes to release a locator, typically due to mobility/relocation of a network or endpoint. The additional information in a locator release Query Message is: o Opcode indicating reason for release. o Flags indicates if a different agent should be contacted (see below). o Old locator to be released. o Issuing NR EID, that issued the locator that is being released. o Issuing NR locator, that issued the locator that is being released. o Different NR EID (optional, only if flag is set) that might release the locator. o Different NR locator (optional, only if flag is set) that might release the locator. 6.4.6 Map Acquisition Route agents request maps from node representatives. Since the requesting route agent is both acting on behalf of an endpoint, either through the endpoint representative or a forwarding agent, and possibly on behalf of other route agents that delegated the original route request, there are usually two or more sets of credentials associated with a map request. These credentials are used by the node representative's filter module, which is tasked with enforcing any distribution restrictions on the maps it dispenses. The additional information in a map Query Message is: o Flags qualifying the maps requested. Values allow to indicate: authoritative response required, abbreviated map required, complete map required, basic map required, need automatic map updates. o Locator of the node whose map is desired. 35 Internet DraftNimrod Functionality and Protocol Specifications March 1996 o Child elements (optional, if flag does not indicate complete). The locators of children whose map is desired. o Credentials of requesting node. The map request Response Message contains the following additional information: o Flags qualifiying map supplied. Values allow to indicate: partitioned node, map is of partitioned node, access denied/not available, automatic updates not supported o Requested Map. o Child Maps (optional). Maps of children nodes as requested (partial or complete). o Agents (e.g., in other partitions) that may be able to answer query. Note that the reply for a basic map may contain several maps, one for the requested node (map) and an abstract map for each of the child component nodes (child maps). The signature of the basic map covers the basic map and each of the maps of the child component nodes. 6.4.7 Map Termination Request An agent that has explicitly requested to be notified of map updates may choose to terminate that subscription request. The map termination Query Message contains the following additional information: o Transaction number (16 bits) of the map request that requested automatic updates. The map termination Response Message contains the following additional information: o Flags. Allow to indicate: Automatic updates not supported, try alternate agent. o Opcode. Zero if ok, error code (e.g., no record of automatic update request) otherwise. o Agent (optional) that might have the automatic update request. 36 Internet DraftNimrod Functionality and Protocol Specifications March 1996 6.4.8 Path Information Request Route agents that are generating multicast routes may require access to existing path information for a multicast group so that more optimal routes may be generated. The path information is distributed among the forwarding agents supporting the multicast group. Route agents use path database queries to obtain the necessary information. The additional information in a path database Query Message is: o Flags. Which info to return. o Path Labels about which info is desired. The additional information in path database Response Message is: o Opcode indicating error code or zero. o Path entries. List of path entries requested. 6.4.9 Route Generation Request/Reply Route agents generate routes on behalf of an endpoint in response to requests received from endpoint representatives and forwarding agents. Requests from forwarding agents will contain the credentials of the forwarding agent in addition to those provided by the endpoint representative. These credentials, along with those of the route agent (and any other route agents that delegated the request) are passed to any node representatives when requesting the node's map(s). The additional information in a Route Generation Query Message is: o Misc. Flags qualifying the nature of route required. o Count, number of feasible routes required. o Sources. Source locators for the route. o Destinations. Destination locators for the route. o Services required by the initiating endpoint. o Services required by the target endpoint. The route generation Response Message contains the following additional information: o Count. Number of feasible routes returned. 37 Internet DraftNimrod Functionality and Protocol Specifications March 1996 o Routes (optional, only if Count is non-zero). A list of routes from source(s) to destination(s) meeting the requirements. 38 Internet DraftNimrod Functionality and Protocol Specifications March 1996 7 Path Management Protocol Nimrod endpoint representatives and forwarding agents are responsible for establishing, in hosts and routers, state information necessary for forwarding Nimrod data messages. These agents are also responsible for forwarding Nimrod data messages according to this state information and the forwarding directives carried along in the messages. For a particular traffic session, the forwarding state information installed and maintained by endpoint representatives and forwarding agents is derived from the routes selected for the session. The forwarding state corresponding to a particular session and route is called a path. Multiple traffic sessions may use the same path, and multiple paths may be established based on the same route. A path may connect one or more source endpoints and one or more destination endpoints. In this initial version of Nimrod, each multicast path is either a source tree or a sink tree. (We note that this version of Nimrod includes procedures for installing and removing forwarding state for multicast trees and for forwarding session traffic along such trees. It, however, does not include procedures for multicast route construction and group management. For more information on these and other multicast issues as they relate to Nimrod, see [4].) Endpoint representatives and forwarding agents use the path management protocol to install and remove state information from their forwarding databases. Each endpoint representative and forwarding agent maintains state information for those paths that originate, terminate, or pass through it. Paths may be set up from source to destination or from destination to source. Each path has an initiator and a target. We expect that, in most cases, paths will be set up from the representative of the source endpoint to the representative of the destination endpoint. Hence, the initiator usually begins the path setup procedure on behalf of the source endpoint, and the target usually accepts or rejects a path on behalf of the destination endpoint. Forwarding state is established such that path management messages may be forwarded in both directions along the path; data messages always flow from source to destination. Paths are identified by path labels, which are unique along the path but not necessarily globally unique throughout the internetwork. Multiple non-intersecting paths may carry the same path label. By eliminating the requirement for global uniqueness of path labels, we can allow paths labels to be relatively short (24 bits), thus reducing the cost of carrying them in data messages and the cost of accessing information in forwarding databases indexed by them. The labels for each direction of a path are distinguished by a bit that indicates whether the message is flowing from from source to destination or from destination to source. Endpoint representatives and forwarding agents try to form a path for a new session by piecing together existing paths, rather than by setting up entirely new paths, provided the existing paths meet the new session's service requirements and permit its traffic to flow over them. This method of path construction incurs the least cost, in terms of the amount of route generation and forwarding state installation required per session. In a 39 Internet DraftNimrod Functionality and Protocol Specifications March 1996 busy internetwork, there are likely to be many existing paths. Moreover, we expect that most traffic sessions will not require specific service guarantees and most networks will not refuse to carry this ``best effort'' traffic. Therefore, we expect this method of path constructruction to be much less expensive than individually setting up and maintaining distinct paths for every traffic session. Most Nimrod paths are likely to be composed of paths which in turn are composed of lower-level paths, and so on. A Nimrod flow-mode data message (refer to section 3.5 for a description of flow mode and datagram mode message transmission) travelling over one of these multilevel, multi-segment paths must carry the path labels of all component paths it is currently traversing. These path labels are stacked in the data message and manipulated, i.e., pushed and popped, by the agents handling the message. Note, however, that an endpoint representative or forwarding agent uses only one of these path labels at a time in making a forwarding decision for the message. 7.1 Protocol Messages The path management protocol uses five types of messages: setup, accept, teardown, status, and ack. Message contents are described below, but explicit formats are depicted in section 9. Each path management message is covered by the same basic types of integrity and authentication checks as other Nimrod control messages, including checks on message length, timestamp validity, content corruption, and source authentication. (Refer to section 3 for more information on Nimrod control message integrity and authentication.) All path management messages travel along the path to which they refer. Endpoint representatives and forwarding agents respond to the receipt of a path management message in different ways, depending upon the type of agent and the type of message. Path management protocol messages may be used not only to set up and teardown a path, but also to collect and report performance monitoring information for a path (e.g., path delay and throughput). Path monitoring operates in two modes: collection and report. Hence, monitored information for a path may appear in a message as information being collected or reported. 7.1.1 Setup A setup message is generated by the initiator and travels along the path toward the target. It is used to establish forwarding state in endpoint representatives and forwarding agents. In this initial version of Nimrod, all endpoint representatives and forwarding agents retain the setup message for each active path that traverses them. This copy is used for detection of duplicate setup messages and for selecting alternate lower-level paths if the one initially chosen fails. Each setup message contains: 40 Internet DraftNimrod Functionality and Protocol Specifications March 1996 1. The label of the path to be established. 2. The time at which the setup message was originally generated. 3. Path indications: (a) Source-initiated or destination-initiated. (b) Unicast or multicast. (c) Available for shared use by multiple sessions or dedicated to a single session. 4. Requested services for the session, indicated as either requirements or preferences and expressed as type, length, and value, from the perspective of the initiator. These may include but are not limited to: o delay; o variation in delay; o throughput; o variation in throughput; o bit error rate; o packet error/loss rate; o monetary cost (per byte, per packet, or per unit time); o whether packet order must be preserved. They may also include information about the session itself, such as its expected lifetime, the type of organization to which the originator belongs (e.g., academic, government, commercial), and the characterization of session traffic (e.g., in terms of average and peak rates and burst durations). As the work of the Integrated Services working group progresses, we plan to integrate these service specifications into future versions of Nimrod. 5. The route, in terms of the locators of the nodes through which it must pass and, for each of these nodes, the label of the relevant connectivity specification to invoke across the node. 6. The EIDs of the source and destination endpoints and their representatives. (a) Unicast path setup. The EID information for the initiator is included to enable the target to establish a path in the reverse 41 Internet DraftNimrod Functionality and Protocol Specifications March 1996 direction, if desired. It is also useful for network management. The type of the target agent determines what EID information is included for the target in the setup message. i. The target is the representative of one of the session's endpoints. Hence, EID information about this specific target must be included in the setup message, in order for the path to connect to the intended endpoint. ii. The target is any boundary forwarding agent for the last node on the route. Hence, there is no specific target and thus EID information related to the target may be left unspecified in the setup message. Such a situation is likely to arise when constructing a higher-level path intended to carry traffic for multiple sessions. (b) Multicast path setup. Although source and destination EID information is not strictly necessary in this case, it is included for network management reasons. Note that the multicast path is either a source tree or a sink tree. Hence, EID information is included for either the source or the destination but not for both. 7. Collection-mode monitored information expressed as type, length, and value. This information can be used to determine the actual services available over the path. The initiator determines whether to collect this information during path setup. 8. Integrity and authentication information covering all but collection-mode monitored information. 7.1.2 Accept An accept message is generated by the target and travels along the path toward the initiator. It is used to indicate to the initiator that the path has been successfully established. Each accept message contains: 1. The label of the accepted path. 2. The EID of the agent that generated the accept message. 3. The time at which the accept message was generated. 4. Report-mode monitored information, expressed as type, length, and value. If the setup message collected monitored information, the accept message reports this information as the services available over the path. 5. Integrity and authentication information covering all of the above. 42 Internet DraftNimrod Functionality and Protocol Specifications March 1996 Provided the initiator is the source, it may send data over the path before it receives an accept message from the target. Circumstances under which an initiator may wish to wait for an accept message before sending data on a path include the following example. If the source pays for all data messages sent, whether or not they are successfully received at the destination, it may want to wait to make sure that the path is successfully established before sending data to the destination. In this case, the source should be prepared to buffer data received from the host until the accept message is received. An initiating source determines whether to wait for an accept message before transmitting data, based upon the session's requested services. 7.1.3 Teardown A teardown message is generated by any endpoint representative or forwarding agent on the path. It usually travels outwards, in both directions, towards the initiator and the target. In some cases (e.g., incomplete path setup or teardown generation by initiator or target), the teardown message may travel in only one direction. Teardown messages are used to remove forwarding state in endpoint representatives and forwarding agents. Each teardown message contains: 1. The label of the path to be torn down. 2. The EID of the agent that generated the teardown message. 3. The time at which the teardown message was generated. 4. The reason for the teardown, expressed as type, length, and value. A teardown message may be generated in response to any of the following events: Type 1: A path timeout. Each path has a specified maximum lifetime, in order to ensure that forwarding state is eventually removed, no matter how a path might fail. The agent detecting the path timeout generates two teardown messages, sending one toward the initiator and one toward the target. Type 2: Setup message is out-of-date. A setup message is out-of-date if the absolute value of the difference between its timestamp and the local time kept by the recipient agent varies by more than a specified maximum value. The agent receiving the out-of-date setup message generates a teardown message and sends it toward the initiator. Type 3: Route specification carried in the setup message is inconsistent with the node. Subtype 1: Recipient agent's node does not appear in the route specification. 43 Internet DraftNimrod Functionality and Protocol Specifications March 1996 Subtype 2: Connectivity specification carried in the setup message is not a valid connectivity specification for the recipient's node. These situations might indicate that the setup message has been corrupted in an undetected way, that a route agent used an out-of-date or corrupted map for the node when constructing the route, or that a setup message was misdelivered. In any case, the agent unable to recognize the node or connectivity specification generates a teardown message and sends it toward the initiator. Type 4: Conflict between the path and either the services provided by the recipient's node or the session service requirements from the target's perspective. Subtype 1: During path setup, an agent detects a conflict between the path and the services provided by its node (as reflected in the node's connectivity specifications) such that the node refuses to carry the session traffic or cannot meet the session service requirements. The agent generates a teardown message and sends it toward the initiator. Subtype 2: During path setup, the target detects a conflict between the path and the session service requirements from its perspective such that the path fails to meet these requirements. The target generates a teardown message containing its service requirements and sends the message toward the initiator. In this case, the initiator will attempt to find a path that is consistent with the target's service requirements as well as its own. Subtype 3: After path establishment, a forwarding agent detects a change in its node's services (as reflected in the node's connectivity specifications), which conflicts with the path such that either the node refuses to carry the session traffic or cannot meet the session service requirements. The agent generates a teardown message and sends copies toward the initiator and target. Subtype 4: After path establishment, the initiator or target detects a change in session service requirements which conflicts with the path such that the path fails to meet the new requirements. The initiator (or target) generates a teardown message and sends it toward the target (or initiator). Type 5: Preemption in favor of another path. The preempting agent generates a teardown message and sends copies toward the initiator and target. Endpoint representatives and forwarding agents are free to implement their own preemption criteria, but these are not part of this initial version of Nimrod. In this version, all paths are established on a first-come, first-served basis, with no preemption. Type 6: Unresolvable path label collision during path setup. (Refer to the discussion of status and ack messages below and to section 7.2.3 below for information on collision resolution.) The agent unable to resolve the path label collision generates a teardown message and sends it toward the initiator. 44 Internet DraftNimrod Functionality and Protocol Specifications March 1996 Type 7: Insufficient resources to any next-hop agent during path setup. The agent detecting a lack of resources to reach a specific next-hop agent attempts to find a suitable alternate next-hop agent. If it fails to find an alternate agent, the agent generates a teardown message and sends it to the previous-hop agent on the path. Subtype 1: Insufficient space in the forwarding database. The agent has no room for another entry in its forwarding database. Subtype 2: Insufficient resources for the path (e.g., unable to reserve required capacity for the session). Type 8: Loss of connectivity in the path. An agent may detect a loss in path connectivity through neighbor discovery (see section 8.1), agent discovery (see section 8.2), or through the loss of a lower-level path forming part of the given path. Subtype 1: An agent detecting a downstream loss to a specific next-hop agent attempts to repair the path by sending the original setup message to an alternate next-hop agent. If it fails to find an alternate agent, the agent generates a teardown message and sends it to the previous-hop agent on the path. Subtype 2: An agent detecting an upstream loss sets a repair timer. If the timer fires before the agent detects the path is repaired, the agent generates a teardown message and sends it to the next-hop agent on the path. An agent detects a repaired path through receipt of a copy of the original setup message (described in more detail in section 7.2). Type 9: Initiator exceeds specified maximum number of setup attempts. The initiator generates a teardown message and sends it toward the target, in order to clear any partially established forwarding state for the path. 5. Report-mode monitored information, expressed as type, length, and value. If the setup message collected monitored information, and the teardown is generated in response to the setup message, then the teardown message reports this information as the services available over the path thus far. 6. Integrity and authentication information covering all of the above. 7.1.4 Status Status messages may be generated by any agent along a path, in order to report path information or modify path characteristics. Each status message contains: 1. The label of the path to which the status pertains. 2. The EID of the agent that generated the status message. 45 Internet DraftNimrod Functionality and Protocol Specifications March 1996 3. The time at which the status message was generated. 4. The reason for the status message, expressed as type, length, and value. A status message may be generated for any of the following reasons: Type 1: Path monitoring. The initiator (or target) generates a status message containing collection-mode monitored information and sends it toward the target (or initiator). The ultimate recipient (which is usually the target or initiator but which may be an intermediate forwarding agent along the path if the path has failed in some way) responds by generating a status message containing report-mode monitored information and sends it toward the initiator (or target). Type 2: Path lifetime extension. The initiator generates a status message containing the amount of time by which to extend the path's life, hence preventing a path teardown prior to session cessation. Type 3: Replacement path label. When a path label contained in a setup message collides with a path label already in use at a forwarding agent or endpoint representative, that agent usually generates an ack message containing a replacement label for the new path that the previous-hop agent should use when sending messages along the new path toward this agent. In some cases, the agent may instead generate status messages containing replacement labels to use for an existing path, one for the previous-hop agent and one for the next-hop agent on the path. For example, if the existing path has not been used in a long time, the agent may choose to alter the forwarding information for that path rather than for the new path, in order to speed processing of data flowing along the new path. Type 4: Unrecognized requested session service contained in a setup message. This might indicate that the setup message has been corrupted in an undetected way or that the initiator is requesting new service requirements not yet known throughout the internetwork. In any case, the agent unable to recognize the session service request generates a status message, sends it toward the initiator, and ignores the unknown service when making next-hop decisions. Type 5: Failure to transmit a setup message successfully over a path hop. An agent detects this failure through an indication of unsuccessful transmission provided by the mechanism for hop-by-hop reliability (refer to the ack message discussion below for more information). It then generates a status message and sends it toward the initiator. In response to this type of status message, the initiator may either resend the original setup message or teardown the established portion of the path. Type 6: Unrecognized path label carried in a data message. This might indicate that the data message has been corrupted in an undetected way or that the agent receiving the message has failed recently and has lost state concerning the paths previously established through it. In any case, the agent unable to recognize the path label 46 Internet DraftNimrod Functionality and Protocol Specifications March 1996 generates a status message and sends it to the agent from which it received the data message containing that path label. 5. Integrity and authentication information covering all but collection-mode monitored information. 7.1.5 Ack The path management protocol provides reliable transmission of setup, accept, teardown, and status messages between successive sending and receiving agents along a path. After transmitting one of these messages along a path, the sending agent expects to receive, within a specified period of time, an ack message acknowledging successful receipt of the message at the next agent. If no ack message is forthcoming, the sending agent retransmits the setup, accept, teardown, or status message up to a specified maximum number of times. Furthermore, if the sending agent fails to receive an ack message after the specified number of retransmissions, it logs the event for possible network management action. Ack messages are generated by each agent along a path in response to the receipt of a setup, accept, teardown, or status message. Each ack message contains: 1. The label of the path to which the ack pertains. 2. The EID of the agent that generated the ack message. 3. The time at which the ack message was generated. 4. In the case of a path label collision, the replacement path label to use when sending messages along that path toward this agent. 5. Integrity and authentication information covering all of the above. Given that the setup portion of the path management protocol is already reliable end to end (i.e., the initiator expects to receive either an accept or teardown message in response to its setup message and retransmits the setup message if no response if forthcoming within a specifed time period), one might consider hop-by-hop reliability overkill. Note that in lossy networks, the additional hop-by-hop reliability increases the reliability and responsiveness of the path management protocol and reduces the number of end-to-end path setup message retransmissions required for successful path establishment. In this version of Nimrod, the path management protocol, unlike the other Nimrod protocols, uses its own reliability mechanism rather than T/TCP. A simpler and more appealing design is one that employs a single reliable transaction protocol for all Nimrod control messages, either T/TCP or perhaps a Nimrod-specific transaction protocol. The reason for treating path management messages differently from other Nimrod control messages is 47 Internet DraftNimrod Functionality and Protocol Specifications March 1996 performance. In the prototype implementation of Nimrod, much of the path management functionality has been placed in the packet handling ``fast path'' while T/TCP is not. We expect that other implementations would likely be structured similarly. To improve message handling efficiency, the path management protocol uses its own separate mechanism for reliability of message transmissions. Thus, for this initial version of Nimrod, practical considerations have prevailed in the area of packet handling. 7.2 Protocol Finite-State Machines The path setup procedure for this initial version of Nimrod operates as follows. An endpoint representative initiates path setup either under control of network management or when it receives, from an endpoint it represents, a data message that requires Nimrod routing and for which no existing path is suitable. After determining the location of the message's destination (by consulting its local locator cache or by querying the DNS) and obtaining a feasible route to that destination (by consulting its local route cache or by querying a route agent), the endpoint representative generates a setup message and sends it toward the target. The endpoint representative expects to receive an accept message from the target, indicating successful path establishment, within a specified time interval. If the endpoint representative fails to receive an accept message for the path within the allotted time interval, it retransmits the setup message, provided it has not yet exhausted its permitted number of setup attempts. The endpoint representative may make a specified maximum number of path setup attempts, in an effort to establish the path successfully. Unsuccessful path establishment manifests itself as either failure to receive an accept message after the maximum number of setup attempts or receipt of a teardown message instead of an accept message for the path. In either case, the initiator removes the path's state from its forwarding database and the corresponding route from its route cache, so that it does not use that route again immediately. It also logs the event for possible network management action. Moreover, when the initiator exhausts its maximum number of setup attempts and does not receive a teardown message, it generates a teardown message of type 9 (exceeded maximum number of setup attempts) and sends it toward the target, in order to remove any partially established forwarding state for the path. The agents in which a path's state is stored include boundary forwarding agents for nodes listed in the path's route specification, as well as endpoint representatives. When a boundary forwarding agent at the entrance to a node X receives a setup message for a path p, it performs a set of consistency and resource availability checks, in order to determine whether to install state for p in its forwarding database. Provided it does not reject p, the boundary forwarding agent installs state relating to the previous hop on p. For example, if the setup message for p arrives on a lower-level path q from agent G, the boundary forwarding agent installs state information in its forwarding database, indicating that the previous hop for p is via q and ends at agent G. It then looks up the next node Y 48 Internet DraftNimrod Functionality and Protocol Specifications March 1996 in the route specification carried in the setup message. If Y is adjacent to X, the boundary forwarding agent attempts to reach any boundary forwarding agent in X participating in the adjacency to Y. Case 1:X supports Nimrod routing internally. The boundary forwarding agent attempts to obtain a path to the boundary of X adjacent to Y , which may also involve obtaining a route. If there is an existing path r to the boundary of X adjacent to Y that is consistent with the session's requested services, the boundary forwarding agent sends the setup message for p over r. If there is no such path r, but a route consistent with the session's requested services does exist, the boundary forwarding agent initiates establishment of a path r for that route. It then installs information in its forwarding database, indicating that the next hop for p is via r, and then sends the setup message for p over r. Upon receipt of the accept message for r, the initiating boundary forwarding agent learns the identity of the next-hop agent H for p and then installs this information in its forwarding database entry for p. Case 2:X does not support Nimrod routing internally. The boundary forwarding agent picks a boundary forwarding agent H participating in the adjacency with Y (the existence of such boundary forwarding agents is learned through agent discovery, described in section 8.2). It then installs information in its forwarding database, indicating that the next-hop agent for p is H and sends the setup message to H. In either case, H then proceeds to install state for p in its forwarding database and to send the setup message on toward a boundary forwarding agent for Y. If Y is not adjacent to X, then the boundary forwarding agent attempts to obtain a path to Y, which may also involve obtaining a route to Y. If there is an existing path r to Y that is consistent with the session's requested services, the boundary forwarding agent sends the setup message for p over r. If there is no such path r, but a route consistent with the session's requested services does exist to Y, the boundary forwarding agent initiates establishment of a path r to Y. It then installs information in its forwarding database, indicating that the next hop for p is via r, and then sends the setup message for p over r. Upon receipt of the accept message for r, the initiating boundary forwarding agent learns the identity of the next-hop agent H for p and then installs this information in its forwarding database entry for p. There are two finite-state machines for the path management protocol, one applicable to the initiator and one applicable to the target or any intermediate forwarding agent in the path. The difference in state machines arises because the accept message contents only affect the behavior of the initiator. All state transitions caused by receipt of messages are described below. Except in one case, receipt of unexpected messages, such 49 Internet DraftNimrod Functionality and Protocol Specifications March 1996 as an accept following a teardown, does not cause state changes, further propagation of these messages, or issuing of new messages. The exceptional case is the receipt of a Nimrod data message with an unrecognized path label. This event causes no state transitions nor propagation of this message, but it does cause the recipient agent to generate a status message of type 6 and send it to the agent from which it received the unexpected data message. All anomalous and error events in the path management protocol are logged for possible network management action. 7.2.1 Initiator The state machine for the initiator has four states: idle, check, ready, and done. State transitions are described below: o idle ! check: This transition occurs when the initiator begins to set up a path. The initiator then performs the consistency and resource availability checks for the path (described below). o check ! idle: This transition occurs if the initiator cannot successfully complete the consistency and resource availability checks for the path because a check failed. o check ! ready: This transition occurs after the initiator has successfully completed all of the consistency and resource availability checks for the path. The initiator then installs state for the path, including next-hop information, in its forwarding database, sends the setup message to the next hop, starts the accept timer, and initializes the setup transmission count. At this point, the initiator may begin to send data traffic over the path or may withhold data traffic until receipt of an accept message, depending upon the session service requirements. o ready ! done: This transition occurs when the initiator receives an accept message from the target. The initiator then stops the accept timer for the path. If the initiator had been withholding data traffic until this point, it may now send this traffic over the path. o ready ! check: This transition occurs when: - The initiator receives from the next-hop agent a teardown message of type 7.1 (insufficient space in forwarding database), 7.2 (insufficient path resources), or 8 (loss of path connectivity). It then attempts to repair the path by sending a copy of the original setup message to an alternate next-hop agent. - The initiator receives from the next-hop agent a status message of type 6 (unrecognized path label in data message) containing a path label matching one of its own. It then seeks to re-establish the path by resending the original setup message to the next-hop agent. 50 Internet DraftNimrod Functionality and Protocol Specifications March 1996 o ready ! idle, done ! idle: This transition occurs when: - The initiator generates a teardown message for the path because the path lifetime expires, the node's offered services or the session service requirements have changed in a way that is inconsistent with the path, the path is preempted, or the accept timer fires before the path is successfully established. It then generates a teardown message and sends the message toward the target. - The initiator is unsuccessful at finding an alternate next-hop agent, following receipt of a teardown message of type 7.1 (insufficient space in forwarding database), 7.2 (insufficient path resources), or 8 (loss of path connectivity). - The initiator receives a teardown message of type 1, 2, 3, 4, 5, or 6. The initiator then removes the state information for the path from its forwarding database. 7.2.2 Intermediate Forwarding Agents and Target The state machine for the intermediate forwarding agents and the target has three states: idle, check, and ready. There is no done state for these agents, because the accept message is only meaningful to the initiator. State transitions are described below: o idle ! check: This transition occurs when the agent receives a setup message for a new path. The agent then performs the consistency and resource availability checks for the path (described later on). o check ! idle: This transition occurs when: - The agent cannot complete the consistency and resource availability checks for the path, because a check failed. - The repair timer fires before completing the checks. - The agent receives from the previous-hop agent, a teardown message of type 4.3 (change in node offered services), 4.4 (change in session service requirements), 8 (loss of path connectivity), or 9 (exceeded maximum number of setup attempts), before completing the checks. The agent then removes any partial state it has installed for the path. o check ! ready: This transition occurs after the agent has successfully completed all of the consistency and resource availability checks for the path. If the repair timer is ticking, the agent stops 51 Internet DraftNimrod Functionality and Protocol Specifications March 1996 the timer. The agent then installs state for the path, including previous hop and next hop and sends the setup message to the next hop. From the agent's perspective, the path may be used to carry data traffic. o ready ! check: This transition occurs when: - The agent receives, from the next-hop agent, a teardown message of type 7.1 (insufficient space in forwarding database), 7.2 (insufficient path resources), or 8 (loss of path connectivity). It then attempts to repair the path by sending a copy of the original setup message to an alternate next hop. - The agent receives, from the next-hop agent, a status message of type 6 (unrecognized path label in data message) containing a path label matching one of its own. It then attempts to re-establish path state by resending a copy of the original setup message to the next hop. - The agent receives, from the previous-hop agent, a setup message for the path. This may occur when an upstream agent attempts path repair. o ready ! idle: This transition occurs when: - The agent generates a teardown message for the path, because the path lifetime expires, the node's services or the session service requirements have change in a way that is inconsistent with the path, the path is preempted, or the repair timer fires before the path is repaired. - The agent receives from the previous-hop or next-hop agent a teardown message of type 1, 2, 3, 4, 5, 6, or 9 or receives from the previous-hop agent a teardown message of type 8 (loss of path connectivity). The agent then removes the state information for the path from its forwarding database and sends the teardown message in the path direction indicated in the message. When in the check or ready states, if the agent detects a loss in connectivity with the previous-hop agent on the path, it sets the repair timer and waits for attempted path repair. The agent generates a teardown message of type 8 (loss of path connectivity), if the repair timer fires before the previous-hop state information is repaired, and sends the message toward the target. 52 Internet DraftNimrod Functionality and Protocol Specifications March 1996 7.2.3 Check State Actions When in the check state, an endpoint representative or forwarding agent must perform a series of tests to determine whether to install forwarding information for the path. These tests are partitioned into two sets, those related to consistency between the path and the services provided over the next hop and those related to resource availability over the next hop. Note that Nimrod datagram-mode data messages carrying requested session services and route specifications are subject to the same consistency checks as setup messages, even though no session-specific forwarding state is installed for these messages. Consistency checks performed by the intermediate forwarding agents and the target include the following: o The setup message is timely. Detection of out-of-date setup messages can help prevent denial of service attacks caused by replays. If the setup message is out of date, the agent sends a teardown message of reason type 2 (out-of-date setup message), toward the initiator. o The path label carried in the setup message is not already in use. If the path label is already in use, one of the following holds: Case 1: The timestamp and route specification carried in the setup message are identical to the timestamp and route specification for an already-established path. - If the previous-hop agent for the setup message (previous-hop information appears in messages as the source EID carried in the EID option, described in section 9), is the same as the previous-hop agent for the existing path, the agent assumes that the setup message is a duplicate submitted by the initiator subsequent to the firing of the accept timer for the path. The agent then forwards the setup message along the path toward the target to enable any downstream agents to establish state for the path, in case they failed to receive the original copy of the setup message. - If the previous-hop agent for the setup message is different from the previous-hop agent for the existing path, the agent assumes that the setup message is a duplicate submitted by an upstream agent attempting path repair. The agent updates its previous-hop information for the path in its forwarding database and does not forward the setup message. Case 2: The timestamp or route specification carried in the setup message are different from those of any already-established path. - If the setup message is for a unicast path, the agent assumes that the setup message is for a new path. The agent then attempts to obtain an alternate label either for the new path or for the existing path with which the new path label collides. 53 Internet DraftNimrod Functionality and Protocol Specifications March 1996 Subcase 1: The agent attempts to select a non-colliding path label for the new path if the most recent use of the existing path occurred within a specified interval relative to the current time. If the agent's supply of usused path labels is exhausted, the agent generates a teardown message of type 6 (unresolvable path label collision) and sends it toward the initiator of the new path. Otherwise, the agent installs the appropriate forwarding state and selects a next-hop agent for the new path. It then includes in its ack message for the previous-hop agent and in its setup message for the next-hop agent, the replacement path labels to use when sending messages over the path and through this agent. Finally, it sends the ack message to the previous-hop agent and the setup message on toward the target. Case 2: The agent attempts to select a non-colliding path label for the existing path if the most recent use of the existing path occurred outside a specified interval relative to the current time. In this case, the agent installs the appropriate forwarding state, selects a next-hop agent, and sends the setup message on toward the target. The agent also changes the forwarding state for the existing path. If the agent's supply of usused path labels is exhausted, the agent generates a teardown message of type 6 (unresolvable path label collision) and sends it toward the initiator of the existing path. Otherwise, the agent substitutes the replacement path label in the forwarding state for the new path. It then generates two status messages of type 3, sending one to the previous-hop agent and one to the next-hop agent, on the existing path. These status messages contain the replacement path labels to use when sending messages over the existing path and through this agent. - If the setup message is for a multicast path, the agent assumes that the setup message is for a new branch of a multicast tree, other branches of which may already exist. The agent then installs new forwarding state for the indicated branch of the tree and sends the setup message toward the target. Consistency checks performed only by the intermediate forwarding agents include the following: o The route specification carried in the setup message is consistent with the node. Specifically, the recipient agent's node appears in the route specification and the connectivity specification contained in the route specification is valid for this node. If either of these conditions is not satisfied, the agent generates a teardown message of type 3.1 (node not present in route specification) or 3.2 (invalid connectivity specification) and sends the message toward the initiator. 54 Internet DraftNimrod Functionality and Protocol Specifications March 1996 o The path is consistent with the node's offered services. Specifically, the node permits the session traffic to use its resources and provides the required services. If these conditions are not satisfied, the agent generates a teardown message of type 4.1 (service conflict during setup) and sends the message toward the initiator. Consistency checks performed only by the target include the following: o The path is consistent with the session service requirements for the target. If this condition is satisfied, the target generates an accept message and sends it toward the initiator. Otherwise, the target generates a teardown message of type 4.2 (target service conflict) and sends the message toward the initiator. The teardown message contains the service requirements from the target's perspective. Upon receipt of such a teardown message, the initiator is responsible for attempting to obtain a feasible route that accounts for the session service requirements from the target's perspective. Resource availability checks performed by all agents include the following: o The forwarding database can accommodate state for the new path. If there is insufficient room in the forwarding database, the agent sends a teardown message of type 7.1 (insufficient space in forwarding database) to the previous-hop agent. Following successful completion of this check, the agent installs the previous-hop information in its forwarding database so that path management messages can flow in both directions along the path. Resource availability checks performed by the initiator and intermediate forwarding agents include the following: o There exists a way to reach the next node in the route specification, which provides the required services for the session and permits access to session traffic. This check is extensive and may require additional route generation and path setup for lower-level paths. To illustrate, let the current path be p. - The selected next-hop agent is directly connected to the agent, and thus there is no need to establish a lower-level path. In this case, the agent simply installs the next-hop information in its forwarding database and sends the setup message for p to the next-hop agent. - There is an already-established feasible lower-level path q with the required resources to a forwarding agent in the next-hop node. In this case, the agent links p with q in its next-hop entry for p in its forwarding database and sends the setup message for p to the next-hop agent, using q. 55 Internet DraftNimrod Functionality and Protocol Specifications March 1996 - There is no established feasible lower-level path to the next-hop node. In this case, the agent attempts to obtain a route for, set up, and obtain the necessary resources for a path q. The agent may either piggyback the setup information for q on the setup message for p or send a separate setup message for q, depending upon the session service requirements. Piggybacking reduces the time to set up a path at the expense of flexibility in collecting monitored information (monitored information can only be collected for one path at a time). If session traffic is allowed to flow before confirmation of successful path setup, the agent piggybacks the setup information for the two paths and links p and q in its next-hop entry for p in its forwarding database. Otherwise, the agent sends a separate setup message for q, waits for receipt of an accept message for q before linking p and q in its next-hop entry for p in its forwarding database, and then sends the setup message for p to the next-hop agent, using q. - A feasible lower-level path with the necessary resources cannot be established, either because no route exists or the path setup fails. In this case, the agent generates a teardown message of type 7.2 (insufficient path resources) and sends the message to the previous-hop agent on p. A teardown message of type 7.1 (insufficient space in forwarding database) or 7.2 (insuffcient path resources) received from an upstream neighbor during path setup may result in the recipient agent resending the setup message to another next-hop agent, if one is available. Only if there are no suitable next-hop agents does the agent propagate the teardown message toward the initiator. 56 Internet DraftNimrod Functionality and Protocol Specifications March 1996 8 Discovery Protocols Each Nimrod agent acting on behalf of a node requires knowledge about its immediately neighboring agents and about the other agents acting on behalf of the same node, in order to perform its routing functions properly. Agents continually execute a neigbor discovery protocol and an agent discovery protocol in order to obtain current information about each other. Neighbor discovery and agent discovery can be performed prior to hierarchical locator assignment, because forwarding of these messages requires knowledge of NIDs and EIDs only. Hence, the discovery protocols may be used to bootstrap the Nimrod routing system. 8.1 Neighbor Discovery Neighbor discovery is performed by activated Nimrod agents within a node and provides the initial information for the formation of adjacencies between nodes and the formation of associations between endpoints and nodes. It enables an agent to determine whether there are other Nimrod agents reachable within one ``hop'' and if so which agents. A hop may constitute a direct link (point-to-point or multiaccess) between two agents or a virtual link (composed of many intervening links and routers that are not Nimrod-capable). When the hop is a virtual link, each agent at the end of the link must be configured with location information (e.g., IP address) for the agent at the other end, so that the neighbor discovery messages are distributed to the appropriate agent. Note that even when the hop is a direct link, the agent may require some location information configuration or discovery (e.g., IP router discovery) prior to Nimrod neighbor discovery; these requirements depend upon the specific network in which these Nimrod agents reside. Specifically, an agent must know the type of link attached to each of the interfaces of the device in which it resides, so that it can invoke the appropriate low-level protocols. For example, if an agent resides in a device attached to an Ethernet that also uses IP, that agent may use a combination of ARP, dynamic host configuration, and router discovery to determine its IP address and the IP address of a neighboring router. These functions must be executed prior to Nimrod neighbor discovery. A Nimrod agent periodically issues a neighbor discovery message over each of its interfaces through which a Nimrod-capable neighbor is expected to exist. Neighbor discovery messages are transported using T/TCP (with IP destination address set equal to the ``all devices'' multicast address) but are never retransmitted. Each neighbor discovery message contains the following information concerning the issuing agent: 1. Type. 2. The time at which the message was generated. 3. Node on whose behalf it acts, expressed as an NID. 57 Internet DraftNimrod Functionality and Protocol Specifications March 1996 4. EID. 5. Locator(s), when available. 6. Set of nodes in which it resides, expressed as a hierarchical sequence of NIDs. 7. Additional location information (e.g., IP address contained in the IP header section). 8. Integrity and authentication information covering all but the additional location information. When a Nimrod agent X receives a neighbor discovery message, it knows that it has a neighboring agent Y. From then on, X expects to continue to receive periodic neighbor discovery messages from Y. Failure to receive neighbor discovery messages from a known neighbor indicates a reachability problem, caused by a physical component's malfunction or movement. An agent detecting a failure to reach a neighboring agent must alert the agent discovery protocol (see section 8.2) and path management protocol (see section 7) operating within it. Agent discovery uses this information to determine which agents are reachable, and path management uses this information to determine which paths require repair. 8.1.1 Neighbor Reachability The periodic exchange of neighbor discovery messages works as an ``up/down'' protocol, such that from an agent's perspective the link to the neighbor is in one of two states, ``up'' or ``down''. Each agent maintains a sliding window for each neighboring agent. Each window slot corresponds to one period and contains either a ``hit'' for receipt of a message or a ``miss'' for failure to receive a message. In addition to the sliding window, the agent also records the number of hits during the current period and number of misses over the current window. The neighbor link is always considered ``down'' initially until the agent receives a sufficient number of messages from it to consider it to be ``up''. Whenever the neighbor link is down, the values of the protocol parameters are set as follows: o The sliding window size is equal to m. o Each window slot contains a miss. o The number of hits during the current period is equal to 0. o The number of misses within the window is equal to m. When the neighbor link moves from down to up, the values of the protocol 58 Internet DraftNimrod Functionality and Protocol Specifications March 1996 parameters are set as follows: o The sliding window size is equal to n. o Each window slot contains a hit. o The number of hits during the current period is equal to 0. o The number of misses within the window is equal to 0. At the conclusion of each period, an agent counts the misses and determines whether there has been a state transition in the neighbor link. When the neighbor link is down, a miss count of no more than m-j signals a transition to the up state. In the up state, a miss count of no less than n-k signals a transition to the down state. Counting the misses involves several steps. First, the agent prepares to slide the window by one slot so that the oldest slot disappears, making room for the newest slot. However, before sliding the window, the agent checks the contents of the oldest window slot. If this slot contains a miss, the agent decrements the number of misses by 1, as this slot is no longer part of the current window. After sliding the window, the agent initially records a miss in the newest window slot and then determines what the proper slot contents should be. If the number of hits for the current period equals 0, a miss is the correct value for the newest slot, and so the agent increases the number of misses by 1. Otherwise, if the number of hits for the current period is greater than 0, the agent applies the hits to any slot containing a miss, beginning with the newest and progressing to the oldest such slot. For each such slot, the agent records a hit in that slot and reduces the number of hits by 1. If the selected slot is not the newest slot, the hit cancels out an actual miss, and so the agent reduces the number of misses by 1 as well. The agent continues to apply each remaining hit to any slot containing a miss, until either all such hits are exhausted or all such slots are accounted for. Before beginning the next up/down period, the agent resets the number of hits to 0. Although we expect the number of hits, within any given period, to be no greater than 1, we do anticipate the occasional period in which an agent receives more than one message from a neighbor. The most common reasons for this occurrence are message delay and clock drift. When a message is delayed, the recipient agent observes a miss in one period followed by two hits in the next period, one of which cancels the previous miss. Excess hits remaining in the tally after miss cancellation indicate a problem, such as clock drift. Thus, whenever an agent accumulates excess hits, it logs the event for potential network management action. When clock drift occurs between two agents, it causes the period of one agent to grow with respect to the period of the other. Let pX be the period for agent X, let pY be the period for agent Y, and let g and h be the smallest positive integers such that gpX= hpY. Suppose that pX <pY because of clock drift. In this case, X observes g- h misses in g 59 Internet DraftNimrod Functionality and Protocol Specifications March 1996 consecutive periods, while Y observes g- h surplus hits in h consecutive periods. As long as g-h_g< n-k_nand g-h_g m-j_m, the clock drift itself will not cause the neighbor link to enter or remain in the down state. 8.2 Agent Discovery Agent discovery is performed by all Nimrod agents within a node. It enables agents acting on behalf of the same node to learn how to reach each other and hence to communicate before Nimrod inter-node routing is fully operational. Note that agents resident within a node may be configured in advance with location information pertaining to other agents in that node instead of participating in agent discovery. During agent discovery, each agent acting on behalf of a node periodically generates and distributes an advertisement about itself. Agent discovery messages are transported using T/TCP (with IP destination address set equal to the next-hop IP address learned through neighbor discovery). Each advertisement message contains the following ``link-state'' information for the issuing agent: 1. Type. 2. The time at which the message was generated. 3. Node on whose behalf it acts, expressed as an NID. 4. EID. 5. Locator(s), when available. 6. Set of nodes in which it resides, expressed as a hierarchical sequence of NIDs. 7. Additional location information (e.g., IP address). 8. The following information for each neighboring agent: (a) EID. (b) Services offered on the link to that neighbor. 9. Integrity and authentication information covering all of the above except the additional location information and also covering the following information. Each boundary forwarding agent also includes in its advertisements the following information for each neighboring boundary forwarding agent external to the node: 60 Internet DraftNimrod Functionality and Protocol Specifications March 1996 1. Node on whose behalf it acts, expressed as an NID. 2. Locator(s), when available. 3. Set of nodes in which it resides, expressed as a hierarchical sequence of NIDs. 4. Whether the advertising agent currently participates in an adjacency (either inbound or outbound) with that neighboring node. In a Nimrod node that does not execute Nimrod routing internally, the agent discovery procedure should be tailored to the information distribution mechanisms native to that node. Consider the following examples. Broadcasting agent advertisements is the method of choice, if the node is a multiaccess network with broadcast capability (e.g., an Ethernet). Flooding agent advertisements may be appropriate, provided the node supports a native flooding mode. Multicasting agent advertisements may be the most efficient strategy, if the node supports multicast distribution (e.g., an IP network that supports IP multicast). In this case, all agents in the node should be configured with a multicast address specific to those agents, which they use when distributing agent advertisements. Moreover, specific types of agents may also have their own multicast addresses (e.g., all boundary forwarding agents for a node may share a multicast address). 8.2.1 Flooding Agent Advertisements In a Nimrod node that supports Nimrod routing internally, the agent discovery procedure is a hop-by-hop reliable flooding procedure among agents within a node. Each agent periodically generates an advertisement and distributes it to each of its neighboring agents that acts on behalf of the same node as itself or on behalf of a child node. Periodic distribution ensures that all agents acting on behalf of the same node keep current with respect to their mutual reachability. Upon receipt of an advertisement, an agent decides either to accept and forward the advertisement or to reject the advertisement. An advertisement is acceptable if it is more recent than any thus far received from the advertising agent and if the recipient agent's node is the same as or is a child of the advertising agent's node. If the advertisement is acceptable, the agent stores the advertised agent information locally and determines where to redistribute the advertisement. Otherwise, the agent discards the advertisement. Forwarding agents are the only type of agents that redistribute advertisements received from neighboring agents. When a forwarding agent receives an acceptable advertisement, it includes its EID (referred to as the ``next-hop'' EID) in the message. As we explain below, this information will be used by the next recipient to determine how to reach the agent that generated the advertisement. The agent then distributes the advertisement to all agents, for which it has forwarding 61 Internet DraftNimrod Functionality and Protocol Specifications March 1996 entries, that act on behalf of the same node as the advertising agent or that are boundary forwarding agents acting on behalf of child nodes of the advertising agent. These prospective receipients may be neighboring agents, or they may be other more distant agents learned about through agent discovery. To reach more distant agents, the agent uses special forwarding hints discussed below. Note that the agent never transmits the message back to the ``next-hop'' agent from which the advertisement was received. For each acceptable advertisement received, an agent records the next-hop EID contained in the advertisement, thus establishing forwarding information indicating how to reach the agent in the advertisement. Note that this procedure is similar to distance-vector routing, with the exception that the routes thus learned are the first and not necessarily the shortest. With this procedure, no persistent routing loops may form. The reasons are as follows: each agent knows of at most one way to reach a particular agent, and no agent distributes an advertisement to the next-hop agent from which it was received. Temporary reachability problems may occur, however, if an agent or a link between agents fails. Node representative and route agents acting on behalf of a node receive advertisements from all agents acting on behalf of the same node. The node representatives use the link-state information contained in these advertisements to construct the node's maps. The route agents use the information to generate intra-node routes at the request of other agents in the same node and may tailor these routes to the specific service requirements of the requesting agents. 8.2.2 Distribution of Advertisements to Distant Agents Suppose a boundary forwarding agent A acts on behalf of node X contained in node Y. The agent discovery procedure operates at two different levels, one for each nodes. Through agent discovery within X, all agents acting on behalf of X learn about each other. Moreover, through neighbor discovery, A learns of any neighbors that act on behalf of child nodes of X. Furthermore, boundary forwarding agents for X, such as A, learn about agents that act on behalf of Y. Hence, A can build up hierarchical forwarding information for reaching agents that act on behalf of X, Y, or children of X. Suppose that A receives from outside X an advertisement for an agent acting on behalf of Y. A must then distribute a copy of this advertisement to boundary forwarding agent in X. For each such agent B, A includes the EID of the destination agent in the route portion of the forwarding header (see section 9, SETUP). It then determines, using forwarding information obtained through agent discovery within X, which neighboring agent C, acting on behalf of X, is the next hop on the way to B and sends the message to C. When C receives the message, it ignores the payload and simply acts on the forwarding information, determining its next hop toward B; it does not act on the agent advertisement information itself. Thus, 62 Internet DraftNimrod Functionality and Protocol Specifications March 1996 advertisements for agents in higher-level nodes can tunnel through lower-level nodes. 8.2.3 Unreachable Agents The following procedure ensures that agents acting on behalf of the same node quickly learn when an agent becomes unreachable. If an agent Q loses connectivity with a next-hop agent R, all agents learned through R become unreachable from the perspective of Q. In this case, Q floods a message indicating the set of agents that are now unreachable from its perspective. Note that all of these unreachable agents will be acting on behalf of the same node N. Each agent X receiving this unreachability message compares the list of unreachable agents contained in the message and with the list of agents supposedly reachable through the next-hop agent from which the message was received. If no agent is present on both lists, then X reaches the listed agents through other next-hop agents and so X may safely discard the unreachability message. If at least one agent is present on both lists, then X can no longer reach those agents. In this case, X constructs an unreachability message containing all such agents. It distributes the message to all agents, for which it has forwarding entries, that either act on behalf of N or are boundary forwarding agents acting on behalf of children of N, but it does not redistribute the message to the agent from which it was received. X also removes its forwarding entries pertaining to the unreachable agents. With the above procedure, all agents affected by a connectivity problem between agents learn which agents they can no longer reach. The periodic distribution of agent discovery messages ensures that agents will learn of alternate routes to currently unreachable agents, if such routes exist. Moreover, by installing multiple agents of each type throughout a node, a network manager may minimize the probability that a particular agent is unable to reach any agents of a particular type acting on behalf of the same node. Furthermore, all route agents acting on behalf of a particular node have a complete picture of all other agents acting on behalf of the same node, and they can attempt to generate alternate routes when reachability problems occur. As long as an agent can reach at least one route agent acting on behalf of the same node, it can request a route to agents that appear to be currently unreachable. A boundary forwarding agent detecting a failure to reach another boundary forwarding agent for the same node must alert the management protocol (see section 7) operating within it. Path management uses this information to determine which paths require repair. Node representatives that learn of unreachable boundary forwarding agents through agent discovery may need to construct a new abstract map if the loss of agent reachability affects the existing abstract map. We discuss this case in more detail in the next section. 63 Internet DraftNimrod Functionality and Protocol Specifications March 1996 8.2.4 Node Partitions Failure of physical assets in a Nimrod internetwork may lead to the partitioning of a Nimrod node, such that assets in one part of the node cannot communicate with assets in the other part of the node by traversing assets within the node. There are two cases: 1. A group of assets in a node are completely isolated from the rest of the internetwork. 2. No assets are isolated from the internetwork, but assets in one part of a node must use assets external to the node in order to communicate with assets in another part of the node. This is the more interesting case and the one discussed below. A node's representatives detect node partitions of the second type, using information received through agent discovery. Specifically, each node representative tracks the reachability of all boundary forwarding agents and all node representatives. When a node representative detects that some boundary forwarding agents are no longer reachable, it concludes that the node has partitioned into multiple pieces. These multiple pieces of the same node are not new nodes. Each piece has the same locator and NID of the original node. However, each piece may have a different map. All node representatives within a given piece have the same knowledge of that piece of the node. A single mutually agreed upon node representative resident in that piece of the node may generate a new map for that piece, if the loss of reachability of a boundary forwarding agent has resulted in a change in the node's abstract map. Note that if the node representative cannot reach any boundary forwarding agents, there is no point in generating a new map for the node, because no one outside that piece of the node will be able to obtain the map. Representatives resident in each such piece of the node generate a different map for the node. These maps are distinguished by the EID of the node representative generating the map and are distributed throughout the parent node. Route agents receiving these maps maintain multiple maps for the node. In fact, when generating routes that include the partitioned node, a route agent uses the node's maps as though they were constructed by different nodes. During a partition, when an endpoint in one piece of the node wishes to communicate with another endpoint in the same node, it may have to use a route that goes outside of the node. First, the representative acting on behalf of the source endpoint determines the locator and EID of the destination endpoint (and its representative), by querying the DNS using the name of the destination endpoint. If the source and destination locators are different, the source's representative then attempts to obtain a route (usually from a route agent 64 Internet DraftNimrod Functionality and Protocol Specifications March 1996 in the parent node) to the destination. This route agent may need to ask each piece of the node for a more detailed map, containing its component nodes, in order to determine which piece contains the source and which piece contains the destination. Once it determines which pieces contain which session endpoints, the route agent can generate a route connecting them and passing through external nodes to do so. If the source and destination locators are the same, the source endpoint's representative determines whether it can reach the destination's endpoint representative, using information obtained through agent discovery. Only if it cannot reach the destination endpoint's representative, does the source endpoint's representative ask a route agent for a route. This route agent does not know which piece each resides in, and generates multiple routes, one from each of the two pieces of the node to the other. The endpoint representative can determine which route is feasible by attempting to set up paths; one path setup is likely to fail because a node along the way will be unreachable. This trial-end-error setup, while not the most efficient, is reasonable, because we expect that nodes will seldom partition into more than two pieces. When the failed resources work again and the node partition disappears, a node representative generates a new abstract map for the node. Maps generated during the partition might still exist in the route agent's map database after the partition disappears. These maps will eventually be removed from that database, because all maps have finite lifetimes. Moreover, the new map for the whole node is available for use immediately, and even when the old maps are usable. The only drawbacks to keeping the old maps around for awhile are the storage space they consume, and the slight amount of extra work they cause during route generation. 8.3 Route Tracing By participating in the agent discovery protocol, each agent acting on behalf of a node constructs forwarding entries for all other agents acting on behalf of the same node. This forwarding information is sufficient to enable a node representative to perform such tasks as locator acquisition for its node (see section 6.4. Recall that locator acquisition involves a query to the parent node representative. Agents within a node can forward such a query to a representative of the parent node, using only the forwarding information obtained during neighbor and agent discovery. This forwarding information, however, is not always sufficient to enable the parent node's representative to return a response to the requesting node representative; additional information may be required. Nimrod includes a route tracing feature that enables agents handling a message, such as a locator request, to include their NID as a part of a message trailer. Thus, as the message progresses to its destination agent, the route (expressed in terms of NIDs of nodes traversed) is accumulated in the message. The destination agent can then use this route to return its response to the source agent. (Refer to section 9 for the specific format 65 Internet DraftNimrod Functionality and Protocol Specifications March 1996 of traced routes and their use as forwarding directives). Although this feature is available to all Nimrod messages, we expect that its use will be confined to node locator request and response messages. 66 Internet DraftNimrod Functionality and Protocol Specifications March 1996 9 Packet Formats 9.1 Overview The ``syntax'' of a Nimrod packet is given below in Backus-Naur notation. Each ``terminal'' is shown in uppercase and without the delimiters <, >, and its packet format with field values is illustrated in the sections as indicated at the end of that line. The formats below assume IP (V.4 or V.6) as the network layer protocol. <Nimrod Pkt> ::= <header><payload> <header> ::= <IP hdr> AUTH-HDR ESP-HDR (section 9.2) <IP hdr> ::= IP-V.4-HDR | IP-V.6-HDR (section 9.2) <payload> ::= <forw hdr> ( <data pkt> | <path pkt> | <uqr pkt> | <disc pkt> ) <forw-tlr> <forw hdr> ::= PATH-STK SETUP | PATH-STK (section 9.3) <forw tlr> ::= TRACE | MONITOR | TRACE MONITOR (section 9.3) <data pkt> ::= DATA (section 9.3) <path pkt> ::= ACK | ACCEPT | TEARDOWN | STATUS (section 9.3) <uqr pkt> ::= <ttcp hdr> ( <upd pkt> | <q-r pkt> ) <disc pkt> ::= <ttcp hdr> ( <n-d pkt> | <a-d pkt> ) <ttcp hdr> ::= TTCP-HDR NIM-XACT-HDR (section 9.4) <upd pkt> ::= UPDATE-HDR <upd oper> (section 9.5) <q-r pkt> ::= Q-R-HDR <q-r oper> (section 9.5) <upd oper> ::= MAP-UPDATE | LOC-UPDATE | ADJ-UPDATE (section 9.6) <q-r oper> ::= MAP-REQ | LOC-REQ | ADJ-REQ | ROUT-REQ | PATH-REQ (sec 9.7) <n-d pkt> ::= DISC-HDR (section 9.8) <a-d pkt> ::= DISC-HDR AGT-ADV (section 9.8) In the packet formats given in subsequent sections, fixed length fields are bordered by ``|'', and variable length fields are bordered by ``:''. In 67 Internet DraftNimrod Functionality and Protocol Specifications March 1996 case of the latter, a structure name is attached in parentheses along with the field, and the exact packet format of the structure name is given in Appendix 2. 9.2 IP and Security Headers Nimrod does not require all routers and hosts to be Nimrod capable. Only Nimrod agents need to be able to recognize Nimrod-specific information in messages. Nimrod information exchaned between Nimrod agents is encapsulated within packets prefaced by the native forwarding header of the network. For this version of Nimrod, we have specified encapsulation within IPv4 [7] and IPv6 [13]. In the future, one might consider migration of some Nimrod-specific information into the IPv6 header as options (e.g. route specifications might appear as a route option). For now, we have elected to keep the Nimrod-specific information largely separate from the IPv6 header until we have gained more experience with Nimrod. IP-V.4-HDR ::= +=======+=======+===============+===============================+ | 4 |HdrLen |Type of Service| Packet Length | +-------+-------+---------------+-------------------------------+ | IP ID | Fragment | +---------------+---------------+-------------------------------+ | Time to Live | Protocol | Checksum | +---------------+---------------+-------------------------------+ | Source IPv4 Address | +---------------------------------------------------------------+ | Destination IPv4 Address | +===============================================================+ IP-V.6-HDR ::= +=======+=======+===============================================+ | 6 | Prio | Flow Label | +-------+-------+---------------+---------------+---------------+ | Payload Length | Next Header | Hop Limit | +-------------------------------+---------------+---------------+ | | | Source IPv6 Address | | | | | +---------------------------------------------------------------+ | | | Destination IPv6 Address | 68 Internet DraftNimrod Functionality and Protocol Specifications March 1996 | | | | +===============================================================+ There exists a new IP option (protocol number 60) to carry the EIDs for the source and destination of the message. This option is described in draft-ietf-nimrod-eid-00.txt and is pictured below. +---------------+---------------+---------------+---------------+ | Next Header | Ext Len = 2 | PadN = 1 | PadN Len = 0 | +---------------+---------------+---------------+---------------+ | Opt EID = A3 | EID Len = 18 | Src Len = 8 | Dst Len = 8 | +---------------+---------------+---------------+---------------+ | Source EID | | | +---------------------------------------------------------------+ | Destination EID | | | +---------------------------------------------------------------+ The IP security headers, including IP authentication [11] (protocol number 51) and encryption [12] (protocol number 50), follow immediately after the IP forwarding headers, thus enabling the recipient to authenticate the message before parsing the rest of it. These headers are not required but instead are inserted at the discretion of the agent sending the message. AUTH-HDR ::= +---------------+---------------+-------------------------------+ | Next Header | Length | RESERVED | +---------------+---------------+-------------------------------+ | SPI | +---------------------------------------------------------------+ | | | Authentication Data | | | | | +---------------------------------------------------------------+ ESP-HDR ::= 69 Internet DraftNimrod Functionality and Protocol Specifications March 1996 Clear +---------------------------------------------------------------+ Text | SPI | ====== +---------------------------------------------------------------+ Cypher | InitVec | Text +---------------------------------------------------------------+ | Data : + +---------------+---------------+ : Padding | Pad Length | Next Header | +-------------------------------+---------------+---------------+ 9.3 Nimrod Forwarding Information Nimrod forwarding information (protocol number 43) is contained in every Nimrod message, following the IP-related headers. This forwarding information consists of four possible sections: a set of paths to be setup or used; a set of routes that the message should follow; the route traversed thus far; and monitored information collected or reported along the path. Not all Nimrod messages contain all portions, as we describe in more detail below, but all Nimrod messages carry a path-stack section. Moreover, a message might carry no path labels in its path stack section (e.g., a response to a query that requires source-directed forwarding). There are several special bits in the path-stack section that indicate which other sections are present and how to parse them. The S bit indicates whether the path indicated by the label already exists and is to be used (S = 0) or does not yet exist and should be installed (S = 1). Only data messages and path management messages carry path labels. The R bit indicates whether the path direction is from source to destination (R = 1) or from destination to source (R = 0). At each forwarding agent along a path, there is a forwarding entry for each direction of the path (previous hop and next hop). Data messages flow in the source-to-destination direction. Path management messages may flow in either direction, but the direction must be indicated in the path label. The C bit indicates whether there has been a path label collision (C = 1) during path setup. If there has been a collision, the first path label with the C bit set is the original path label and the second path label with the C bit set is the replacement path label. The next agent to receive this message will use the replacement path label when forwarding messages toward the previous agent along the path. The T bit indicates whether or not there is route tracing in progress. Routing tracing is used to collect routing information during queries that occur prior to locator assignment, so that the response can return to the agent that placed the query, even if the queried agent does not know the locator of the requesting agent. Route tracing is normally only used in query messages, and then only prior to locator assignment. 70 Internet DraftNimrod Functionality and Protocol Specifications March 1996 The M bit indicates whether there is monitored information being collected in the message (M = 1). Monitored information is normally only collected in path management messages. PATH-STK ::= +------ (Header Length + 1) * 8 | +---- (Section Length + 1) * 8 | | +-- Path Offset | | | v v v ===== +===============+===============+===============+===============+ ^ ^ ^ | Next Header | Header Length | Version = 1 | Hops to Go | | | | +---------------+---------------+---------------+-+-+-+-+-+-----+ | | | | Type=Forward | Section Length| Path Offset |S|C|M|R|T| 0 | | | | +---------------+---------------+---------------+-+-+-+-+-+-----+ | | v : Available for additional Path Labels : | | - +---------------+-----------------------------------------------+ | | |S:0 1 1:C:0 0 0:R: Path Label n | | | +---------------+-----------------------------------------------+ | | |S:0 1 1:C:0 0 0:R: ... : | | +---------------+-----------------------------------------------+ | | |S:0 1 1:0:0 0 0:R: Path Label 1 | | | +---------------+-----------------------------------------------+ | v |S:0 1 1:0:0 1 0:R: Path Label 0 | |====== +===============================================================+ | All messages that require source-directed forwarding contain the following section, which carries routes. These messages include setup messages themselves, datagram-mode messages, and responses to queries prior to locator assignment (in this case, the route contains a sequence of NIDs and ``best effort'' connectivity specifications). The authentication field carried in each route covers all of the common information except the route offset, destination EID, destination endpoint representative EID, and all of the information pertaining to that route. In a setup messages, the flags indicate whether the path is source-initiated or destination-initiated, unicast or multicast, sharable among sessions or dedicated to a particular session, and whether the requested services are preferences or requirements. The destination endpoint and endpoint representative may be designated as ``unknown'' in some cases. Setup message may simultaneously set up more than one path. In this case, multiple routes are carried in a single setup message. 71 Internet DraftNimrod Functionality and Protocol Specifications March 1996 SETUP ::= | | +------- (Section Length + 1) * 8 | | +----- (Common Length + 1) * 8 | | | +--- route offset | v v v |====== +===============+===============+===============+===============+ | ^ ^ | Type=Paths |Section Length | Subtype=Setup | Flags | | | | | +---------------+---------------+---------------+---------------+ | | | | |<route offset> | Common Length | 0 | | | | | +---------------+---------------+-------------------------------+ | | | | | Message Generation Timestamp | | | | | +---------------------------------------------------------------+ | | | | : Requested Services : | | | | +---------------------------------------------------------------+ | | | | | Source EID | | | | | | | | | | | +---------------------------------------------------------------+ | | | | | Source Endpoint Representative EID | | | | | | | | | | | +---------------------------------------------------------------+ | | | | | Destination EID | | | | | | | | | | | +---------------------------------------------------------------+ | | | | | Destination Endpoint Representative EID | | | | | | | | | | | +---------------------------------------------------------------+ | | v | ? 64-bit Pad ? | |---| +===============================================================+ | | v : Free/64-bit pad : | | -- +---------------+---------------+---------------+---------------+ | | | Type=Route | Route Length | 0 | <hop offset> | | | +---------------+---------------+---------------+---------------+ | | : Authentication : | | +---------------------------------------------------------------+ | | : Route n : | | : a sequence of hops each represented as : | | : length, connectivity specification, and node locator or nid : | | +---------------------------------------------------------------+ | | : ... : | | +---------------+---------------+---------------+---------------+ | | | Type=Route | Stack Length | 0 | <hop offset> | | | +---------------+---------------+---------------+---------------+ | | : Authentication : | | +---------------------------------------------------------------+ | v : Route 0 : |===== +---------------+---------------+---------------+---------------+ | 72 Internet DraftNimrod Functionality and Protocol Specifications March 1996 All path management messages are transmitted reliably, hop by hop along the path. The ack message indicates the type of message acknowledged. If the type of message acknowledged is a setup message and the C bit is set in the path label acknowledged, then the message contains a replacement path label to use in the opposite direction along the path. In the ack, accept, status, and teardown messages, the authentication field covers the entire section of the message. ACK ::= | | +------- (Section Length + 1) * 8 | v |=== +===============+===============+===============+===============+ | ^ | Type=Paths | Section Length| Subtype=Ack | Flags | | | +---------------+---------------+---------------+---------------+ | | |Type Msg Acked | 0 | | | +---------------+-----------------------------------------------+ | | | Message Generation Timestamp | | | +---------------------------------------------------------------+ | | | Path Label of Acknowledged Message | | | +---------------------------------------------------------------+ | | | Replacement Path Label | | | +---------------------------------------------------------------+ | | : Authentication : | | +---------------------------------------------------------------+ | v ? 64-bit Pad ? |=== +---------------------------------------------------------------+ | ACCEPT ::= | | +------- (Section Length + 1) * 8 | v |=== +===============+===============+===============+===============+ | ^ | Type=Paths | Section Length| Subtype=Accept| Flags | | | +---------------+---------------+---------------+---------------+ | | | 0 | | | +---------------------------------------------------------------+ | | | Message Generation Timestamp | | | +---------------------------------------------------------------+ | | | Accepted Path Label | | | +---------------------------------------------------------------+ | | : Authentication : | | +---------------------------------------------------------------+ 73 Internet DraftNimrod Functionality and Protocol Specifications March 1996 | v ? 64-bit Pad ? |=== +---------------------------------------------------------------+ | Status and teardown message contain information pertaining to the reason for the status or teardown message. STATUS ::= | | +------- (Section Length + 1) * 8 | v |=== +===============+===============+===============+===============+ | ^ | Type=Paths | Section Length| Subtype=Status| Flags | | | +---------------+---------------+---------------+---------------+ | | | Status Code | Code Length | Code Data : | | +---------------+-----------------------------------------------+ | | | Message Generation Timestamp | | | +---------------------------------------------------------------+ | | | Path Label | | | +---------------------------------------------------------------+ | | : Authentication : | | +---------------------------------------------------------------+ | v ? 64-bit Pad ? |=== +---------------------------------------------------------------+ | TEARDOWN ::= | | +------- (Section Length + 1) * 8 | v |=== +===============+===============+===============+===============+ | ^ | Type=Paths | Section Length|Subtype=Teardwn| Flags | | | +---------------+---------------+---------------+---------------+ | | | Teardown Code | Code Length | Code Data : | | +---------------+-----------------------------------------------+ | | | Message Generation Timestamp | | | +---------------------------------------------------------------+ | | | Path Label | | | +---------------------------------------------------------------+ | | : Authentication : | | +---------------------------------------------------------------+ | v ? 64-bit Pad ? 74 Internet DraftNimrod Functionality and Protocol Specifications March 1996 |=== +---------------------------------------------------------------+ | The route tracing section is optional and usually only contained in query messages transmitted prior to locator assignment. The route collected in the message can be reversed to send the response back to the requesting agent. In this case, the traced route is expressed in terms of NIDs instead of locators. TRACE ::= | | +------- (Section Length + 1) * 8 | | +----- free offset | v v |====== +===============+===============+===============+===============+ | ^ ^ | Type=Trace | Section Length| 0 | <free offset> | | | | +---------------+---------------+---------------+---------------+ | | v : Free/64-bit pad : | |--- +---------------------------------------------------------------+ | | :<locator id/len> <locator/nid n> : | | +---------------------------------------------------------------+ | | : ... : | | +---------------------------------------------------------------+ | v :<locator id/len> <locator/nid 0 (source)> : |=== +---------------------------------------------------------------+ | Monitored information is normally carried only in path management messages. There are two types of monitored information, collection-mode and report-mode. Setup messages carry only collection-mode information and accept and teardown carry only report-mode information; status messages may carry either type. Each of the monitored items is expressed in terms of a service specification (e.g., delay, MTU, throughput). MONITOR ::= | | +------- (Section Length + 1) * 8 | v |=== +===============+===============+===============================+ | ^ | Type=Monitor | Section Length|Subtype=Cl/Rp | Flags | | | +---------------+---------------+-------------------------------+ 75 Internet DraftNimrod Functionality and Protocol Specifications March 1996 | | | <monitored item 1> | | | +---------------------------------------------------------------+ | | : ... : | | +---------------------------------------------------------------+ | | | <monitored item n> | | | +---------------------------------------------------------------+ v v ? 64-bit Pad ? ==== +---------------------------------------------------------------+ 9.4 Transaction Headers TTCP-HDR ::= (Transaction) TCP Header (IPPROTO_TCP = 6) +-------------------------------+-------------------------------+ | Src Port | Dest Port = 1617 | +-------------------------------+-------------------------------+ | Sequence Number | +---------------------------------------------------------------+ | Acknowledgement Number | +-------+-----------+-+-+-+-+-+-+-------------------------------+ |TCP Len| |U|A|P|R|S|F| Window | +-------+-----------+-+-+-+-+-+-+-------------------------------+ | Checksum | Urgent Pointer | +---------------+---------------+-------------------------------+ | MSS = 2 | Len = 4 | Maximum Segment Size | +---------------+---------------+-------------------------------+ | CC=11/.NEW=12 | Len = 6 | Seg.cc +---------------+---------------+---------------+---------------+ | CC.Echo = 13 ? Len = 6 ? +-------------------------------+---------------+---------------+ ? Seg.cc ? ---- +---------------------------------------------------------------+ NIM-XACT-HDR ::= (Nimrod) Transaction Header (TCP Dest Port = 1617) +---------------------------------------------------------------+ | Transaction Length | +---+---+-------+---------------+-------------------------------+ |Ver|Prt| Oper | Phase | Transaction Identifier | +---+---+-------+---------------+-------------------------------+ | NTP Seconds | ---- +---------------------------------------------------------------+ 76 Internet DraftNimrod Functionality and Protocol Specifications March 1996 Ver value : 0 Prt values : 0 = Discovery Protocol 1 = Update Protocol 2 = Query Protocol 3 = Response Protocol Oper values : When Prt = 1 : 1 = Adjacency update 3 = Endpoint locator update 4 = Node locator update 5 = Map update When Prt = 2 or 3 : 1 = Adjacency Activation 2 = Adjacency Release 3 = Adjacency Request 4 = Endpoint locator acquisition 5 = Node locator acquisition 6 = Locator release 7 = Map request 8 = Map update termination 9 = Path request 10 = Route request Phase values : 10 = forward map update to parent node FA 12 = distribute map update to NR and RA 13 = forward locator update to child node FA 14 = notify all agents in node of new locator 16 = notify adjacency to NR 9.5 Update, Query, and Response Protocol Headers UPD-HDR ::= +---------------+---------------+-------------------------------+ | org agt typ | dst agt typ | flags | +---------------+---------------+-------------------------------+ | db_type | db sequence | +---------------+-----------------------------------------------+ : authenticator (NimAuth) : 77 Internet DraftNimrod Functionality and Protocol Specifications March 1996 +---------------------------------------------------------------+ : dst NID (NimNID) : +---------------------------------------------------------------+ : originator's EID (NimEID) : +---------------------------------------------------------------+ : originator's Locator (NimLoc) : +---------------- ----------------------------------------------+ agt typ values : 0 = Any endpoint, not a Nimrod agent. 0x01 = Association Agent (for future use). 0x02 = Endpoint Representative. 0x04 = All Forwarding Agents. 0x08 = Boundary to child Forwarding Agent. 0x10 = Boundary to parent FA. 0x20 = Node Representative. 0x40 = Designated Node Representative. 0x80 = Route Agent. 0xA0 = Node representative and Route Agents. 0xA6 = All agents in the node. 0x1000 = Neighboring FA. 0x2000 = Neighboring FA in parent. 0x4000 = Neighboring FA in child. db type values : 1 = Abstraction DB 2 = Agent DB 3 = Adjacency DB 4 = ARP DB 5 = Association DB 6 = DNS DB 7 = Endpoint DB 8 = End-to-End Session DB 9 = Forwarding Agt DB 10 = Forwarding path branch DB 11 = Forw. Conn. Spec DB 12 = Forwarding flood DB 13 = Filtering DB 14 = Forwarding neighbor DB 15 = Forwarding path DB 16 = Forwarding route DB 17 = Intercept endpoint DB 18 = Intercept session DB 19 = Key DB 20 = Locator DB 21 = IP Multicast forwarding DB 22 = Map DB 23 = Map registration DB 24 = Node DB 25 = Route DB 26 = IP unicast forwarding DB Q-R-HDR ::= +---------------+---------------+-------------------------------+ | org agt typ | dst agt typ | flags | +---------------+---------------+-------------------------------+ | db_type | count | opcd | 78 Internet DraftNimrod Functionality and Protocol Specifications March 1996 +---------------------------------------------------------------+ : authenticator (NimAuth) : +---------------------------------------------------------------+ : Q: Originator's or R: Responder's EID (NimEID) : +---------------------------------------------------------------+ : Q: Originator's or R: Responder's Locator (NimLoc) : +---------------------------------------------------------------+ : credentials (NimCred) : +---------------------------------------------------------------+ 9.6 Update Operation Messages ADJ-UPDATE ::= +---------------+---------------+---------------+---------------+ : Neighbor node id (NimNID) : +---------------+---------------+---------------+---------------+ : Neighbor node loc (NimLoc) : +---------------+---------------+---------------+---------------+ : Boundary forwarding agent locator (NimLoc) : +---------------+---------------+---------------+---------------+ LOC-UPDATE ::= +---------------+---------------+---------------+---------------+ : Originator Credentials (NimCred) : +---------------+---------------+---------------+---------------+ : Old NR EID (NimEID) : +---------------+---------------+---------------+---------------+ : Old NR locator (NimLoc) : +---------------+---------------+---------------+---------------+ : Old locator (NimLoc) : +---------------+---------------+---------------+---------------+ : New locator (NimLoc) : +---------------+---------------+---------------+---------------+ : Valid until (NimSecs) : +---------------+---------------+---------------+---------------+ Defined Flag (in UPD-HDR) values : 1 = Depreciate use of old locator 2 = Terminate use of old locator. 79 Internet DraftNimrod Functionality and Protocol Specifications March 1996 MAP-UPDATE ::= +---------------+---------------+---------------+---------------+ : Abstract Map (NimMap) : +---------------+---------------+---------------+---------------+ : Agent specific map 1 (NimMap) : +---------------+---------------+---------------+---------------+ : Agent specific map 2 (NimMap) : +---------------+---------------+---------------+---------------+ : ....... : +---------------+---------------+---------------+---------------+ : Agent specific map n (NimMap) : +---------------+---------------+---------------+---------------+ Defined Flag (in UPD-HDR) values : 1 = One or more component nodes not in map 2 = Map is of a partitioned node. 9.7 Query/Response Operation Messages For most databases, we have the request, release, and response messages (for adjacencies, we additionally have the activation message). We only give the formats for the request messages for each database. The other message formats are similar and can be easily reconstructed from the contents description given earlier in section 6.4. ADJ-REQ ::= +---------------+---------------+---------------+---------------+ : Requesting Node Locator (NimLoc) : +---------------+---------------+---------------+---------------+ : Requesting Node Identifier (NimNID) : +---------------+---------------+---------------+---------------+ : Requesting Node Circuit ID (NimLkID) : +---------------+---------------+---------------+---------------+ : Neighbor Node ID (NimNID) : +---------------+---------------+---------------+---------------+ Defined Flag (in Q-R-HDR) values : 1 = Adjacency from parent to child 2 = Other adjacencies 4 = Adjacency from child to parent 8 = Adjacency to siblings 80 Internet DraftNimrod Functionality and Protocol Specifications March 1996 NODE-LOC-REQ ::= +---------------+---------------+---------------+---------------+ | Old NR EID (NimEID) : +---------------+---------------+---------------+---------------+ : Old NR locator (NimLoc) : +---------------+---------------+---------------+---------------+ : Previously assigned loc (NimLoc) : +---------------+---------------+---------------+---------------+ : Parent NID (NimNID) : +---------------+---------------+---------------+---------------+ : Child NID (NimNID) : +---------------+---------------+---------------+---------------+ EP-LOC-REQ ::= +---------------+---------------+---------------+---------------+ | Old NR EID (NimEID) : +---------------+---------------+---------------+---------------+ : Old NR locator (NimLoc) : +---------------+---------------+---------------+---------------+ : Previously assigned loc (NimLoc) : +---------------+---------------+---------------+---------------+ : NID to provided loc (NimNID) : +---------------+---------------+---------------+---------------+ : Endpoint name (NimFQDN) : +---------------+---------------+---------------+---------------+ : Endpoint ID (NimEID) : +---------------+---------------+---------------+---------------+ MAP-REQ ::= +---------------+---------------+---------------+---------------+ | Node loc of desired map (NimLoc) : +---------------+---------------+---------------+---------------+ : Child elements if partial (NimLElem) : +---------------+---------------+---------------+---------------+ : Credentials of requesting node (NimCred) : +---------------+---------------+---------------+---------------+ 81 Internet DraftNimrod Functionality and Protocol Specifications March 1996 Defined Flag (in Q-R-HDR) values : 0x8000 = Response must be authoritative 0x4000 = Abbreviated map desired 0x2000 = Complete maps desired 0x1000 = Automatic updates desired ROUT-REQ ::= +---------------+---------------+---------------+---------------+ | Sources (NimLEpt) : +---------------+---------------+---------------+---------------+ : Destinations (NimLEpt) : +---------------+---------------+---------------+---------------+ : Initiating EPs service reqs (NimServ) : +---------------+---------------+---------------+---------------+ : Target EPs service reqs (NimServ) : +---------------+---------------+---------------+---------------+ : Child NID (NimNID) : +---------------+---------------+---------------+--------------- Defined Flag (in Q-R-Hdr) values : 0x10 = Want maximally disjoint routes 9.8 Discovery Message Header Neighbor discovery messages and agent discovery messages contain much of the same information. This information is represented in a single header pictured below. The authentication field covers the header and any enclosed information. DISC-HDR ::= +---------------+---------------+-------------------------------+ | Type=Nbr/Agt | Agent Type | 0 | Flags | +---------------+---------------+-------------------------------+ | Message Generation Timestamp | +---------------------------------------------------------------+ : Authentication : +---------------------------------------------------------------+ | Agent's EID | | | +---------------------------------------------------------------+ 82 Internet DraftNimrod Functionality and Protocol Specifications March 1996 | NID of Agent's Node | | | +---------------------------------------------------------------+ : Agent's Locator : +---------------------------------------------------------------+ : Sequence of NIDs : : of nodes containing agent : : formatted as a locator : +---------------------------------------------------------------+ The neighbor discovery message includes only the discovery header, while the agent discovery message contains the EID and services to each neighbor. Furthermore, if the advertising agent is a boundary forwarding agent, the advertisement also contains the neighbor's NID, locator, sequence of NIDs in which the neighbor is contained, and an indication of whether the agent participates in an adjacency (A = 1) with the neighbor and if so which types: outbound (T = 1), inbound (T = 2), or both (T = 3). AGT-ADV ::= +---------------------------------------------------------------+ | EID of Neighbor n | | | +---------------------------------------------------------------+ : Services to Neighbor n : +---------------------------------------------------------------+ | NID of Neighbor n's Node | | | +---------------------------------------------------------------+ : Locator of Neighbor n's Node : +---------------------------------------------------------------+ : Sequence of NIDs : : of nodes containing neighbor n : : formatted as a locator : +---------------------------------------------------------------+ |A|T | type of adjacency with neighbor n's node | +---------------------------------------------------------------+ : ... : +---------------------------------------------------------------+ | EID of Neighbor 0 | | | +---------------------------------------------------------------+ : Services to Neighbor 0 : +---------------------------------------------------------------+ | NID of Neighbor 0's Node | | | +---------------------------------------------------------------+ 83 Internet DraftNimrod Functionality and Protocol Specifications March 1996 : Locator of Neighbor 0's Node : +---------------------------------------------------------------+ : Sequence of NIDs : : of nodes containing neighbor 0 : : formatted as a locator : +---------------------------------------------------------------+ |A|T | type of adjacency with neighbor 0's node | +---------------------------------------------------------------+ 84 Internet DraftNimrod Functionality and Protocol Specifications March 1996 10 Appendix 1: Figures for Update and Q-R protocols 85 Internet DraftNimrod Functionality and Protocol Specifications March 1996 86 Internet DraftNimrod Functionality and Protocol Specifications March 1996 87 Internet DraftNimrod Functionality and Protocol Specifications March 1996 88 Internet DraftNimrod Functionality and Protocol Specifications March 1996 89 Internet DraftNimrod Functionality and Protocol Specifications March 1996 11 Appendix 2: Basic Data Formats In section 9, a number of packet formats were pictured in terms of other, more basic, variable length data objects such as locator (NimLoc), and EID (NimEID). Here we give the formats for such basic data elements. Only the more basic and important data objects are described in detail and illustrated pictorially - namely Element (NimElem), Locator (NimLoc), EID (NimEID), Endpoint Name (NimFQDN), Node ID (NimNID). The other data objects are given in the form of C structure declarations. 11.1 Element (NimElem) An Element consists of a variable number of octets, with the most frequently used length expected to be two octets. The most significant bit (M) is one (1) for a multicast element and zero (0) otherwise. The next few bits encodes the element length. The remaining bits may be asigned by node representatives. Different instances of a node representative might choose to use different assignment algorithms. The only constraint is that the set of node representatives for a node should cooperate to make sure that an element is not given out by more than one of the representatives. Several formats have been predefined. One-octet elements are expected to be used to identify routers or router interfaces of small sized nodes that choose to include router identification in their locators, e.g., use Nimrod routing as their intra-node routing protocol. The format of a one-octet element is: +-+-+-+-+-+-+-+-+ |M|0| | 1 octet, 6 free bits +-+-+-+-+-+-+-+-+ Two-octet elements are expected to be used in most cases. An organization might choose to set aside some bits in an element that could be used, e.g., to identify successive numbering plans, so that internal management and monitoring might be simplified. The format of a two-octet element is: +-+-+-+-+-+-+-+-+-+...+-+ |M|1 0 0| | 2 octets, 12 free bits +-+-+-+-+-+-+-+-+-+...+-+ Four-octet elements are provided for nodes that, e.g., want to include local information in an element. The format of a four-octet element is: +-+-+-+-+-+-+-+-+-+...+-+ |M|1 1 1 0 0 0 0| | 4 octets, 24 free bits 90 Internet DraftNimrod Functionality and Protocol Specifications March 1996 +-+-+-+-+-+-+-+-+-+...+-+ Nimrod uses a two-octet element to specify which agents within a node should receive a control message. The format of this element is: +-+-+-+-+-+-+-+-+-+-+...+-+-+ |M|1 1 1 0 0 0 1| Agent Set | 2 octets, Nimrod Agent Set +-+-+-+-+-+-+-+-+-+-+...+-+-+ Seven-octet elements are used within the Nimrod system to encode EIDs and NIDs in a locator element. These elements are used during bootstrapping to enable intra-node (including to a parent or component node) communication before globally routable locator (element)s have been acquired. The format of this element is: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |M|1 1 0|Rel| EID / NID bits | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The relationship field (Rel) is used for node-relative addressing. Its values are: 00 This node 01 Parent node 10 Child node 11 Reserved 11.2 Locator (NimLoc) A locator is a variable length object that represents a location in an internet. It consists of a header containing a flag bit, bits that identify the object as a locator and bits encoding the total length, one or more self delimiting locator elements, and optional octets of zero padding to make the overall length of the locator in octets zero mod 4. An element occupies an integral number of octets. The bits identifying a locator are 0000 011. This is derived from the experimental IPv6 address space. Each locator begins on a 32-bit boundary, and is padded with zero octets to maintain 32-bit overall alignment. 91 Internet DraftNimrod Functionality and Protocol Specifications March 1996 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+---------------+ |0 0 0 0 0 1 1|Z|F|1 1 0 0|CdLen| <element> | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+---------------+ | <element> <padding> | +---------------+---------------+---------------+---------------+ The Z field must be zero and is reserved for future expansion. The F field is a context-dependent flag bit. The length, in octets, of a locator is indicated by the CdLen field as follows: CdLen 0 1 2 3 4 5 6 7 Octets 4 8 12 16 20 24 32 Reserved 11.3 Endpoint Identifier (NimEID) Nimrod uses Endpoint Identifiers (EIDs), globally unique, hierarchy independent, relatively fixed and short length, administratively assigned binary representations of endpoint names. Initially, EIDs will be eight-octet quantities, with fiftey bits available for assignment. The format of the EID is (HELP???) : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |F|0 1 0 0|0 0 1| octet-1 | octet-2 | octet-3 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+---------------+ | octet-4 | octet-5 | octet-6 | octet-7 | +---------------+---------------+---------------+---------------+ A first cut at an EID allocation policy is as follows, where "r" is the two-bit relationship code (00 = this node, 01 = parent node, 10 = child node, 11 = reserved). 6r0 00 00 00 00 00 00 "Wild" Node/Endpoint 6r0 00 00 00 00 00 01 "This" Node/Endpoint 6r0 00 00 00 00 00 02 thru 6r0 FF FF FF FF FF FF 48-bit administered 6r1 00 00 00 00 00 00 thru 6r1 FF FF FF FF FF FF 48-bit reserved 6r2 00 00 00 00 00 00 thru 6r2 FF FE|FF FF FF FF Reserved 6r2 FF FF|00 00 00 00 thru 6r2 FF FF|FF FF FF FF Embedded IPv4 6r3 00 00 00 00 00 00 thru 6r3 FF FF FF FF FF FF Embedded IEEE 802 Note that NIDs and EIDs are taken from the same number space. EIDs have the "0x21" prefix and NIDs the "0x29" prefix. 92 Internet DraftNimrod Functionality and Protocol Specifications March 1996 11.4 Endpoint Name (NimFQDN) Endpoint names have the form of a fully qualified domain name (FQDN) and are represented by the NimFQDN object. Nimrod uses the user-friendly host name, e.g., www.nimrod.BBN.Com form. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |F|0 0 1 1 1 1 0 0 0 0 0 1 1 0| obj len in octets | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+---------------+ : DNS Name : +---------------+---------------+---------------+---------------+ : DNS Name : pad (if nec.) : +---------------+---------------+---------------+---------------+ 11.5 Node Identifier (NimNID) Nimrod uses a Node Identifier to identify a node in a topologically independent manner. Node identifiers are administratively assigned and are used to identify a node before the Nimrod bootstrapping process and the associated locator acquisition and update messages have determined the node's global locator. An NID may be thought of as an EID of a node (they come from the same number space). A node's policies are tagged by the node's NID. Each interface of a forwarding agent that provides connectivity across a node boundary has an associated sequence of NIDs that identify the nodes whose policies, both incoming and outgoing, must be enforced on that interface. Such an interface is termed a boundary forwarding agent. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |F|0 1 0 1|0 0 1| octet-1 | octet-2 | octet-3 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+---------------+ | octet-4 | octet-5 | octet-6 | octet-7 | +---------------+---------------+---------------+---------------+ 11.6 Services (NimServ) Nimrod advertises, requests, and offers communication services through lists of communication parameters. Each parameter has its own object type code, length, and value. struct NimServ { NimOL2 idlen; /* Object type code and length */ NimMgmt mgmt; /* Management authority */ NimAuth auth; /* Authentication of authority */ NimLSrv orig_req; /* Opt: Service requested by orig*/ NimLSrv dest_req; /* Opt: Service requested by dest*/ 93 Internet DraftNimrod Functionality and Protocol Specifications March 1996 NimLSrv offered; /* Opt: Service offered*/ } struct NimLSrv { /* Object type code and length */ NimOL2 idlen; /* List of Service Parameter */ u_int32_t skd_id; /* Schedule id */ NimSrvP values[]; /* Set of parameters and values */ } struct NimSrvP { /* Service Parameter */ NimOL2 idlen; /* Object type code and length */ NIM_SRV_* 0x /* Service parameter */ u_int32_t value[]; /* Opt: Value of parameter */ } Service parameters include but are not limited to delay, throughput, probability of packet error, MTU, monetary cost of service, time at which the service is offered, organizations which may use the service, and characterization of traffic necessary to obtain the service. The availability of services is frequently restricted to certain time intervals, called schedules, especially when fees are being charged for the services. struct NimSked { NimOL2 idlen; /* Object type code and length */ u_int32_t skd_id; /* Schedule id, within context ... */ NimMgmt mgmt; /* ... of a management authority */ NimAuth auth; /* Authentication of authorizing entity*/ NimSkd1 sets[]; /* Opt: time intervals */ } /* Omitted means anytime */ struct NimSkd1 { NimOL2 idlen; /* Object type code and length */ u_int16_t flags; /* Periodic events */ int16_t tzone; /* Minutes from UTC */ NimSecs earliest, /* Bounding time, or 0 ... */ latest; /* ... or all 1's */ u_int16_t intervals[2*i]; /* Opt: Start and stop pairs, minutes from midnight */ } 11.7 Maps (NimMap) struct NimMap { 94 Internet DraftNimrod Functionality and Protocol Specifications March 1996 NimOL2 idlen; /* Object type code and length */ u_int8_t kind; /* Kind of map */ u_int24_t seq; /* 24 LSB of generation NTP seconds */ /* Rollsover in 6 mo, longer than */ /* signature key lifetime */ NimLoc locs[]; /* Locator(s) of node represntd */ /* Makes component and connspec unique */ NimNID nid; /* NID of node */ NimAgnt agent; /* NR that produced the map */ NimSecs expires; /* When map expires, advisory */ NimLLoc adj_in, /* Adjacent incoming nodes */ adj_out; /* Adjacent outgoing nodes */ NimAuth abv_auth; /* Authenticator over abbreviated map */ /* Next 4 are only in Full map, either all present, or all omitted */ NimLCsp csp_in, /* Opt1: Set of incoming conn specs */ csp_out, /* Opt1: Set of outgoing conn specs */ csp_trnst; /* Opt1: Set of transit conn specs */ NimAuth full_auth; /*Opt1: Authenticator over full map */ /* (incl abv_auth) */ /* Next 5 are only in Basic map: */ /* appended child maps, NimMap len excludes child maps */ NimAuth basic_auth; /* Opt2:Authenticator over this map */ /* and appended child maps */ u_int32_t num_maps; /* Opt2: Number of appended maps */ /* of child nodes */ NimLElm chilren; /* Opt2: Elements of component nodes */ | /* Context is "locs", above */ NimLLoc adj_child; /* Opt2: Adjacent children nodes */ /* Service may be omitted if it appears (for same cspec_id) above */ NimLCsp topology; /* Opt2: Interconnectivity of node */ } 11.8 Routes (NimRute) A route is used to identify, at the level of Nimrod nodes or forwarding agents, the communication components through which traffic from one endpoint to another endpoint should pass, where each endpoint is identified by its locator. It includes the type of route, such as unicast, multicast, sharable, and so on. Each hop in a route identifies the next node or forwarding agent through which traffic should be routed and the connectivity specification that should be used for that portion of the route. struct NimRute { NimOL2 idlen; /* Object type code and length */ 95 Internet DraftNimrod Functionality and Protocol Specifications March 1996 u_int32_t flags; /* multicast, unicast, etc. */ NimAuth auth; /* Authentication for generating route agent */ NimServ serv_req; /* Services required */ NimDRst drst; /* Opt: Restrictions on reuse of route */ NimServ offered; /* Services associated with route */ NimRutH hops[]; /* List of hops in route */ } struct NimRutH { NimOL2 idlen; /* Object type code and length */ u_int32_t cspec_id; /* Connectivity Specification Id */ NimLoc node; /* Next Node to pass through */ } 11.9 Credentials (NimCred) struct NimCred { NimOL2 idlen; /* Object type code and length */ NimFQDN name; /* Who's credentials */ u_int32_t cred[]; /* Body of credentials */ } 11.10 Path Labels (NimPLbl) struct NimPLbl { u_int32_t flag:1, /* Setup flag */ obj_id:7, /* Object type code */ label:24; /* Path label */ NimEID source; /* Opt: source EID, top level only */ } 11.11 Time (NimSecs, NimNTP) struct NimSecs { NimOL2 idlen; /* Object type code and length */ u_int32_t seconds; /* Seconds */ } struct NimNTP { NimOL2 idlen; /* Object type code and length */ u_int32_t seconds; /* NTP Seconds */ u_int32_t fraction; /* NTP Fractional Seconds */ 96 Internet DraftNimrod Functionality and Protocol Specifications March 1996 } 11.12 Authenticator (NimAuth) struct NimAuth { NimOL2 idlen; /* Object type code and length */ u_int16_t alg_id, /* Authentication algorithm id */ key_ftpt; /* Footprint of key, for key rollover */ NimFQDN signer; /* Opt: Identify of signer */ u_int8_t auth[16]; /* Authenticator, 16 for MD5 */ } The key footprint field specifies the least significant two bytes of the key used to form the authenticator; see [13]. It is used to identify which of the possible keys was used to form the authenticator. Multiple keys may be valid when keys are being changed. Having the footprint is an optimization that makes it possible to pick the right key without having to try each one until one works, or all possible keys fail. 97 Internet DraftNimrod Functionality and Protocol Specifications March 1996 12 Security Considerations Security issues for Nimrod are discussed in general in sections 2 and 3 and more specifically in the sections for the specific protocols and packet formats (section 9). 13 Contact Information Ram Ramanathan Martha Steenstrup BBN Systems and Technologies BBN Systems and Technologies 10 Moulton St. 10 Moulton St. Cambridge, MA 02138 Cambridge, MA 02138 Ph: (617) 873-2736 Ph: (617) 873-3192 email: ramanath@bbn.com email: msteenst@bbn.com 98 Internet DraftNimrod Functionality and Protocol Specifications March 1996 References [1]I. Castineyra, J.N. Chiappa and M. Steenstrup, ``The Nimrod Architecture'', Working Draft, March 1996. [2]M. Steenstrup, ``A Perspective on Nimrod Functionality'', Working Draft, March 1996. [3]S. Ramanathan, ``Mobility Support for Nimrod: Requirements and Solution Approaches'', Working Draft, March 1996. [4]S. Ramanathan, ``Multicast Support for Nimrod: Requirements and Solution Approaches'', Working Draft, March 1996. [5]C. Lynn, ``Nimrod Deployment'', Working Draft, March 1995. [6]D.L. Mills, ``Network Time Protocol (Version 3) Specification, Implementation and Analysis'', Internet RFC, Number 1305, March 1992. [7]J. Postel, ``Internet Protocol'', Internet RFC, Number 791, September 1981. [8]J. Postel, ``Transmission Control Protocol'', Internet RFC, Number 793, September 1981. [9]R. Braden, ``Extending TCP for Transactions -- Concepts'', Internet RFC, Number 1379, November 1992. [10]R. Braden, ``T/TCP -- TCP Extensions for Transactions Functional Specification'', Internet RFC, Number 1664, July 1994. [11]R. Atkinson, ``IP Authentication Header'', Internet RFC, Number 1826, August 1995. [12]R. Atkinson, ``IP Encapsulating Security Payload (ESP)'', Internet RFC, Number 1827, August 1995. [13]S. Deering and R. Hinden, ``Internet Protocol, Version 6 (IPv6) Specification'', Internet RFC, Number 1883, January 1996. 99
Datatracker
Report a datatracker bug
draft-ietf-nimrod-fun-pro-spec-00
None
| Document | Document type |
Expired Internet-Draft
(nimrod WG)
Expired & archived
|
|
|---|---|---|---|
| Select version | |||
| Authors |
Martha E. Steenstrup
,
Dr. Ram Ramanathan
Email authors |
||
| RFC stream |
|
||
| Intended RFC status | (None) | ||
| Other formats | |||
| Additional resources | Mailing list discussion |