Nimrod Working Group M. Steenstrup Internet Draft BBN Systems and Technologies June 1994 Expires 30 December 1994 A Perspective on Nimrod Functionality 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 ds.internic.net, venera.isi.edu, munnari.oz.au, or nic.nordu.net 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 We describe the Nimrod routing functionality, expressed in terms of the relationships among a set of distributed databases of routing information together with the procedures for constructing, accessing, and acting upon database contents. Internet Draft Nimrod Functionality June 1994 Contents 1 Introduction 1 2 Overview of the Nimrod Architecture 2 2.1 Clustering and Abstraction . . . . . . . . . . . . . . . . . . . . 2 2.2 Nimrod Entities . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 Nimrod Routing Functions and Databases 4 3.1 Nimrod Database Consistency . . . . . . . . . . . . . . . . . . . . 6 3.2 Nimrod Agents . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4 Nimrod Entity Initialization and Operation 10 4.1 Node Formation . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4.2 Endpoint Definition . . . . . . . . . . . . . . . . . . . . . . . . 12 4.3 Agent Discovery . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.3.1 Neighbor Discovery . . . . . . . . . . . . . . . . . . . . . . 16 4.4 Locator Acquisition . . . . . . . . . . . . . . . . . . . . . . . . 16 4.4.1 Node Locators . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.4.2 Endpoint Locators . . . . . . . . . . . . . . . . . . . . . . . 19 4.5 Map Construction . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.5.1 Arc Formation . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.5.2 Abstraction of Service Information . . . . . . . . . . . . . . 22 4.5.3 Map Updates . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.5.4 Map Queries . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.5.5 Node Partitions . . . . . . . . . . . . . . . . . . . . . . . . 26 4.6 Association Database Maintenance . . . . . . . . . . . . . . . . . 27 4.6.1 Association Updates . . . . . . . . . . . . . . . . . . . . . . 29 i Internet Draft Nimrod Functionality June 1994 4.6.2 Association Queries . . . . . . . . . . . . . . . . . . . . . . 30 5 Routes 30 5.1 Representation . . . . . . . . . . . . . . . . . . . . . . . . . . 32 6 Message Forwarding 32 6.1 Forwarding State . . . . . . . . . . . . . . . . . . . . . . . . . 34 6.1.1 An Example of Path Setup . . . . . . . . . . . . . . . . . . . 36 6.1.2 Path Acceptance . . . . . . . . . . . . . . . . . . . . . . . . 37 6.1.3 Forwarding Information in Messages . . . . . . . . . . . . . . 38 7 Security Considerations 39 8 Author's Address 39 References 40 ii Internet Draft Nimrod Functionality June 1994 1 Introduction In this document, we present an overview of the routing functionality implied by the Nimrod routing architecture. 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 established paths. A complete description of the Nimrod routing architecture appears in [1]. 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 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. The purpose of this document is to present a candidate set of routing mechanisms for Nimrod, illustrating how the Nimrod architecture might be realized. This document represents a stepping stone on the way to a detailed protocol specification for Nimrod. By circulating this document at this time, we hope to solicit design recommendations and to uncover problems before proceeding with the protocol design. The proposed Nimrod routing mechanisms are based on architectural 1 Internet Draft Nimrod Functionality June 1994 requirements and engineering cost/benefit tradeoffs. In the remainder of this document, we describe each of these mechanisms in some detail, and we justify the selection of these particular mechanisms. We begin with a brief review of the Nimrod architecture, followed by a general discussion of Nimrod as a set of databases and functions, and then proceed to describe the individual Nimrod routing mechanisms. 2 Overview of the Nimrod Architecture Before Nimrod routing can be applied within an internetwork, the internetwork must be represented in terms of the three basic Nimrod entities: nodes, arcs, and endpoints. The internetwork's physical assets, such as routers, networks, and point-to-point links must be captured in Nimrod maps comprising nodes and arcs. Traffic sources and destinations must be cast as Nimrod endpoints. Each of these entities possesses a set of attributes, such as location with respect to the maps, interconnectivity with other entities, and service information, all of which are important for routing. 2.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 arcs and abstraction of attributes of the component physical assets resulting in node and arc attributes. The objective of clustering is to reduce the number of entities visible to Nimrod routing. Nodes and arcs are usually formed by clustering physical assets possessing similar attributes. These attribute similarities might, for example, be in terms of qualities of service or restrictions on access to services. 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 such as 2 Internet Draft Nimrod Functionality June 1994 geographical locality of physical assets may be employed. Clustering may be applied repeatedly, such that physical assets are first clustered into nodes and arcs, and then nodes and arcs are themselves clustered into larger nodes and arcs, and so on. Iterative clustering further reduces the number of entities visible to Nimrod routing and results in a hierarchical organization of nodes and arcs 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 and arcs whose component physical assets possess different attributes rely on information abstraction in order to reduce the number of attributes used to characterize those nodes and arcs. Example abstraction procedures include eliminating attributes possessed by only a small percentage of the component physical assets and 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 or arc. 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 authorities that manage the various portions of the internetwork, and hence management authorities 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 before making a final decision. 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, arcs, and endpoints. A node is a set of contiguous internetwork physical assets. It may be formed by clustering physical assets directly or by clustering existing nodes and arcs. If the given node itself comprises component Nimrod nodes, the routing system employed to route traffic within or across the node is Nimrod routing. Otherwise, the routing system may be anything. A node's attributes include its locator, its offered services, its requirements for connectivity with other entities, the locators of the arcs 3 Internet Draft Nimrod Functionality June 1994 attached to it, and a pool of locators that may be assigned to its component nodes and outgoing arcs. These attributes may be preconfigured, acquired during initialization, discovered through measurement, or obtained by abstraction of attributes of component nodes and arcs. A node's locator is a globally unique label describing the node's position in the clustering hierarchy. It consists of the locator of the node's enclosing node in the clustering hierarchy concatenated with a label unique among all component nodes and outgoing arcs of the enclosing node. An arc is a set of physical links connecting two nodes. It may be formed by clustering physical links directly or by clustering existing arcs. Arcs are directed, such that each arc has a source node and a destination node. Hence, a physical link between two nodes is usually represented as two directed arcs. An arc's attributes include its locator, its offered services, and its source and destination nodes. These attributes may be preconfigured, acquired during initialization, discovered through measurement, or obtained by abstraction of attributes of component arcs. An arc's locator is a globally unique label describing the arc's position in the clustering hierarchy. It consists of the locator of the arc's source node concatenated with a label unique among all component nodes and outgoing arcs of the source node. An endpoint is a traffic source, destination, or both that is visible to other Nimrod entities through association with one or more Nimrod nodes. All routers within a node must know how to route traffic toward the endpoints associated with that node. Examples of endpoints include hosts and routers or even processes within hosts and routers. An endpoint's attributes include its globally unique labels such as the endpoint identifier (EID) and mnemonic names, its locators, its service requirements, and its requirements for connectivity with other entities. These attributes may be preconfigured or acquired during initialization. When an endpoint is associated with a node, it is automatically associated with that node's locator. Thus, as an endpoint may be associated with more than one node, it may be associated with more than one locator. 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. Entity attributes. Each of the basic Nimrod entities has a set of attributes, as discussed in section 2.2 above. These attributes are used in controlling neighbor relationships between entities, in 4 Internet Draft Nimrod Functionality June 1994 assigning locators, in constructing maps, and in generating and selecting routes. 2. Endpoint/locator associations. Nimrod endpoint locators are used in generating routes between and forwarding messages toward those endpoints. Endpoint/locator associations are stored and accessed based on well-known unique labels for the endpoints. We refer to the database of endpoint/locator associations as the association database. 3. Maps. Each Nimrod node has a set of maps describing its services and its attached arcs' connectivity and services to neighboring nodes. Node maps are used in generating routes. 4. 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 connectivity and services advertised in maps. Each route is expressed in terms of nodes and arcs and is used to construct forwarding information to be installed in routers. 5. Forwarding information. Nimrod traffic forwarding is path-oriented, where a path is under the control of the source and destination endpoints. Forwarding information, installed in routers according to the routes selected, guides message forwarding in successive routers along established paths. A database relevant to but not maintained by Nimrod is the pool of unique labels, such as EIDs and mnemonic names, that may be assigned to endpoints. 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 should be organized to optimize the performance of these procedures along the dimensions of delay, internetwork resource consumption, fault tolerance, and load balancing. Nimrod databases will be 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 and hosts, 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 have no other choice as the memory required for a single Nimrod database, such as the association 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 5 Internet Draft Nimrod Functionality June 1994 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; however, it may also increase the cost of the average database update. 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 many endpoints. Thus, minimizing the number of such inconsistencies is a primary objective of the Nimrod database maintenance procedures. Inconsistencies between database contents and internetwork state may result from delays incurred in updating database contents following internetwork state changes. Many of the Nimrod databases will be volatile and hence require mechanisms for keeping the contents current, in order to prevent propagation and use of stale routing information. These database maintenance mechanisms include rapid and reliable updating with new information as well as removal of old information. We recommend that each Nimrod database 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 capture and corruption of database updates and responses to queries, through generation of fictitious database updates and responses to queries, 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 should attempt to protect the routing information from introduced errors. In particular, the protocols for communicating information to or from a Nimrod database should permit the intended recipient of that information to: 1. Authenticate the information. 6 Internet Draft Nimrod Functionality June 1994 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 should also permit the sender of the information to retransmit to the intended recipient any information that it preceives 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. For example, 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. For example, two different routers might select routes to the same destination such that each router is included in the other's route, but the underlying path-oriented nature of message forwarding in Nimrod (even for Nimrod's ``datagram'' mode described in section 6) enables loop-free forwarding in the presence of such inconsistencies in selected routes. 3.2 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 process, 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 and thus has an EID and a locator. For each database, certain agents are responsible for maintaining specific portions. Such an agent is designated as an authoritative source for that portion of the given database. Some types of databases are such that not all of their corresponding agents need to be authoritative sources. However, usually an 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. Each Nimrod agent may update its database by querying other agents. The Nimrod 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 propagate queries. The node on whose behalf an agent acts is called the agent's scope, and a single agent may have multiple scopes. Moreover, an agent may be an authoritative source for a database portion that is independent of its scope. Such is the case with association agents, as we 7 Internet Draft Nimrod Functionality June 1994 discuss in section 4.6. The Nimrod agents and their corresponding functions are as follows: 1. Entity representatives. Each Nimrod entity must have one or more representatives, maintaining the database of entity attributes and actin on its behalf. Entity representatives are always authoritative sources for their entities' attributes. Each node representative is responsible for assigning locators to component nodes, forming arcs to other nodes, collecting maps from component nodes, and constructing its node's maps. Nimrod node representatives also act as representatives for arcs to external nodes. Each endpoint representative is responsible for forming associations with nodes, learning the locators of endpoints with which its endpoints communicate, and communicating endpoint locators and service requirements to forwarding agents. 2. Association agents. Each node may have one or more association agents responsible for answering or propagating association queries from endpoints associated with the given node. Some association agents are authoritative sources for specific endpoint/locator associations while others may not be authoritative sources for any endpoint/locator associations. 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 and arc connectivity and services advertised in maps. Route agents 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 Nimrod forwarding information in routers, and forwarding Nimrod messages. Forwarding agents are always authoritative sources for the portion of the paths that traverse them. With the exception of a node's forwarding agents, agents acting on behalf of a node need not reside within the node nor share the node's locator. The node's forwarding agents, however, must reside within the node itself, because they control the traffic flow across the node boundary. Nevertheless, we suggest locating all Nimrod agents close to the entities on whose behalf they act. Such location minimizes delay and internetwork resource consumption in updating the databases corresponding to those entities and in responding to queries from agents in the vicinity of those entities. The Nimrod routing functions involve communication among different Nimrod agents, in order to update or to retrieve information from Nimrod databases. Usually, an agent requires information from a specific database but does not 8 Internet Draft Nimrod Functionality June 1994 care which of that database's agents provides the information. However, Nimrod does provide two different types of database queries, direct and indirect, which enable the querying agent to make its own tradeoffs in query cost versus quality of information obtained. A direct query must be answered by an authoritative source for the given portion of the given database. An indirect query may be answered by any agent for the given database. Indirect queries are likely to consume fewer internetwork resources than direct queries, because they can often be answered by agents that are close to the querying agent. However, indirect queries may yield stale information, because they are likely to be answered using cached information originally obtained from authoritative sources. The type of routing information and hence its expected duration of usefulness, the cost to obtain the routing information, and the success rate of past queries will determine the type of query to place in a particular situation. For example, each agent may execute a database refresh procedure by querying another agent for its latest information concerning a particular database. An agent executes a database refresh following its activation or its detection of a discrepancy between internetwork state and its current database contents. The requesting agent may prefer to query an authoritative source for the information but may be willing to accept information from any agent. It is the responsibility of network managers to choose an algorithm for determining which type of query an agent should place in a given circumstance. Distributing and maintaining agent location (EID and locator) information for inter-agent communication is likely to be expensive when there are many agents in an internetwork. Hence, we provide an inter-agent message forwarding scheme that does not require the sending agent to specify a particular recipient agent but rather a description of where the message should be sent. In particular, the sending agent specifies: 1. The type of message: update or query. If a query, the type: direct or indirect. 2. The type of database to be updated or queried. 3. The type of recipient agent. 4. The key, which in most cases is the scope of the updated or requested routing information. For association updates or queries, the key is the label of the endpoint for which information is updated or requested. This information is sufficient to direct a message toward an appropriate recipient agent, without having to specify the EID and locator of a recipient. Such inter-agent communication may require the participation of many intervening agents, each of which knows how to reach an agent that will know how to direct the message toward the target. Communication between 9 Internet Draft Nimrod Functionality June 1994 agents may also include knowledge of EIDs and locators in order to achieve more efficient message forwarding. In section 4.3, we explain how agents within a given scope discover each others' EIDs. 4 Nimrod Entity Initialization and Operation The Nimrod routing functions must work well in a large dynamic internetwork. Hence, the Nimrod routing functions include mechanisms that enable Nimrod agents to perform much of their own initialization, without requiring human intervention. An agent performs initialization procedures following its activation and may also perform some of these procedures following reconfiguration or movement. The initialization procedures include: 1. Agent discovery. 2. Node, arc, and endpoint locator acquisition. 3. Node map construction. 4. Association database maintenance. Nevertheless, network managers retain ultimate control over Nimrod entities, thus enabling them to organize their networks in order to achieve specific routing behavior. Network managers cluster physical assets into Nimrod nodes and arcs, determine the abstraction algorithms that will yield node and arc attributes, and load Nimrod agent functionality into physical devices. Moreover, network managers may configure each of the attributes of any Nimrod entities under their jurisdiction. In the remainder of this section, we discuss initialization and subsequent operating procedures for each of the Nimrod entities. 4.1 Node Formation Node formation begins when a network manager clusters a contiguous set of physical assets or existing nodes and arcs into a new node. Clustering defines the node boundary, indicating which physical devices belong to the node and which are external to the node. In particular, clustering identifies the node's boundary routers, namely those that have direct physical connectivity to routers external to the node. After defining the node boundary, the network manager installs various agents for the node. The two mandatory types of node agents are forwarding agents and node representatives. The network manager may also install association agents and route agents for the node, but these are not mandatory. 10 Internet Draft Nimrod Functionality June 1994 For each new agent it installs, the network manager assigns a scope, a type, and an EID. The assigned EID may correspond to the physical device in which the agent resides or may be specific to the agent itself. If the node has been formed by clustering existing nodes and arcs, the network manager may not need to install any new agents. Instead, it may add scopes to the existing agents. In either case, the assigned scope may be the permanent one in the context of the clustering hierarchy, or it may be a temporary one which will eventually be replaced when the node to which it refers acquires its locator. Note that a network manager may assign a temporary scope with either a temporary or a permanent prefix. As we have previously noted, forwarding agents must reside in physical devices within the node. Each of the node's boundary routers must contain a forwarding agent, designated as a boundary forwarding agent for that node, which defines the boundary of the node and controls traffic flow across that boundary. Forwarding agents contained within other routers in the node are designated as interior forwarding agents for that node. If the node has no component nodes and arcs, then all of its forwarding agents are boundary forwarding agents. If the node comprises component nodes and arcs, then it may have interior as well as boundary forwarding agents. Its interior forwarding agents consist of those component nodes' boundary forwarding agents that are not boundary forwarding agents for the given node. Each node must have at least one node representative, and that representative need not necessarily reside within the node. The network manager may initially configure the following node attributes to be maintained by the node's representatives: 1. Connectivity requirements defining the type of nodes with which the given node may form an arc. For example, the network manager may specify that a node should only connect to nodes managed by particular authorities. 2. Offered service information, from the perspective of the node as service provider. This service information may include not only services in terms of quality, monetary cost, and access restrictions, but also service-related properties such as the names of the node's management authorities and the types of nodes to which the services should be advertised. Services apply across the node between two arcs, one incoming from an external node and one outgoing toward an external node. Service quality includes but is not limited to offered delay, throughput, reliability, ordering, and security. Access restrictions include but are not limited to who may access the service, for what purposes, and when. All node representatives apply the same abstraction procedures for determining their node's service attributes, as described in section 4.5.2. 3. The pool of locators that may be assigned to component nodes and outgoing arcs. 11 Internet Draft Nimrod Functionality June 1994 The first two types of attributes must be consistent among all of the node's representatives. However, the locator pool is different for each of the node's representatives. Specifically, each of the node's representatives maintains a block of available local locators for component nodes and outgoing arcs, which is disjoint from the blocks maintained by the node's other representatives. Thus, multiple node representatives cannot assign the same locator to multiple entites. Moreover, multiple node representatives cannot assign multiple locators to a component node or outgoing arc, as a single node representative is responsible for assigning a locator to such an entity (as described in sections 4.4.1 and 4.5.1). 4.2 Endpoint Definition Endpoint definition begins when a network manager assigns an EID and an endpoint representative to a new endpoint. If there are no endpoint representatives already in the vicinity of the new endpoint, the network manager installs such an endpoint representative, assigning it a set of endpoints on whose behalf it will act, a type, and an EID. The assigned EID may correspond to the physical device in which the endpoint representative resides or may be specific to the endpoint representative itself. If there is already an endpoint representative in the vicinity of the new endpoint, the network manager need not install a new endpoint representative. Instead, the network manager adds the new endpoint to the existing endpoint representative's set of endpoints on whose behalf it acts. Note that each endpoint representative is a representative of itself as an endpoint. Each endpoint must have at least one endpoint representative, and a single endpoint representative may act on behalf of multiple endpoints. Endpoint representatives do not have scopes. Instead, they form node associations on behalf of their endpoints, as we describe in section 4.4, and they themselves become associated with these same nodes. The network manager may initially configure the following endpoint attributes to be maintained by the endpoint's representatives: 1. A globally unique identifier (EID). 2. A set of mnemonic names. DNS-style names are one such example. 3. A set of locators. Although an endpoint's locators are usually discovered, as described in section 4.4, they may also be preconfigured. 4. Connectivity requirements defining the types of nodes with which the endpoint may be associated. For example, an endpoint owned by a given company may only be permitted to connect to physical assets owned by that company. 5. Traffic service information, from the endpoint's perspectives as source 12 Internet Draft Nimrod Functionality June 1994 and as destination. This service information may include not only service requirements in terms of quality, monetary cost, and access restrictions, but also service-related properties such as the name of the endpoint's management authorities and the classification (e.g., research, commercial) of its traffic. Service quality includes but is not limited to requested delay, throughput, reliability, ordering, and security. Access restrictions include but are not limited to the names of service providers to prefer or to avoid. 6. A set of multicast groups for which the endpoint is automatically a member. (We discuss multicast communication in detail in [3].) The two endpoint label databases, EIDs and mnemonic names, are not maintained as Nimrod databases. Nevertheless, we provide some recommendations for the organization of these databases. In particular, we suggest a hierarchical organization of management authorities, culminating with a central organization such as the Internet Assigned Numbers Authority (IANA). These management authorities would be responsible for maintaining a database of available labels and for assigning labels from this database. At the top, the IANA would assign blocks of labels to network managers. Each network manager would assign blocks of labels to hosts under its jurisdiction, and each host and router would assign labels to endpoints resident within it. There may also be more levels of management authorities between the IANA and the network managers. Whenever its local supply of available labels was exhausted, a management authority could request a new block of labels from its superior authority. Moreover, it might reclaim labels that were no longer in use. 4.3 Agent Discovery Once all of a node's boundary forwarding agents have been installed, the network manager activates all installed agents whose scope is the given node. The network manager also activates endpoint representatives in the node's vicinity. Agent activation also occurs automatically whenever a physical device in which Nimrod agents reside becomes operational. Activated agents begin the agent discovery procedure which enables them to learn each others' EIDs hence allows them to communicate directly. When activating agents in already operational devices, a network manager should follow a strict ordering of agent activation. Boundary forwarding agents should be activated before all others, because they confine the distribution of advertisements to the proper scope. Furthermore, if all of a node's boundary forwarding agents are not activated simultaneously, some of their advertisements may escape that scope. This poses no permanent problems, however, as we discuss later on. Also, forwarding agents should be activated before endpoint representatives, so that endpoint advertisements do not propagate beyond the ``first-hop'' forwarding agents. However, automatic agent activation caused, for example, by rebooting the physical 13 Internet Draft Nimrod Functionality June 1994 devices in which agents reside is not restricted to a particular ordering, provided that the boundary forwarding agents have already been installed. Suppose that a power failure within a building causes several physical devices containing Nimrod agents to go down and subsequently come back up to the running state. In this case, the operational devices will automatically perform their Nimrod functions and the devices that are still down will pass no traffic. Hence, agent discovery information will be contained within the proper scope. During agent discovery, each activated agent advertises the scope on whose behalf it is currently acting (which may be empty, in the case of an endpoint representative), type, and EID, by distributing the advertisement on each physical link connected to its physical device. Advertisement distribution is based on a flooding procedure that terminates depending upon whether the advertisement has been seen before. Note that the flooding procedure should include the reliability measures discussed in section 3.1. An agent receiving an apparently new advertisement must determine whether to cache and distribute that advertisement. The specifics of the agent discovery procedure depend upon whether the advertising agent has a scope, and if so, whether the advertising agent is internal or external to its scope. If the advertising agent has no scope, it must be an endpoint representative. In this case, the recipient agent does not redistribute the advertisement. Forwarding agents are the only agents that cache advertisements from endpoint representatives, and they also respond to these endpoint representatives with advertisements of their own. This ensures that forwarding agents know how to reach the endpoint representatives, and hence the endpoints, in their vicinities and that endpoint representatives know how to reach first-hop forwarding agents. Provided the advertising agent has a scope, the recipient agent compares its scopes with the scope in the advertisement. Lacking scope, endpoint representatives as recipient agents never redistribute advertisements from other agents. They need only cache advertisements from first-hop forwarding agents, and they also respond to these forwarding agents with advertisements of their own. For the remainder of the discussion, we assume the recipient agent has scope. There are four cases to consider: 1. The recipient agent's top-level scope is contained within the advertising agent's scope. In this case, the recipient agent distributes but does not cache the advertisement. 2. One of the recipient agent's scopes matches the advertising agent's scope. In this case, the recipient agent may cache and redistribute the advertisement. Forwarding agents always redistribute advertisements from node representatives, route agents, association agents, and boundary forwarding agents sharing their scope. Other types of agents do not redistribute advertisements. The caching rules depend upon the types of the advertising and recipient agents, as follows: 14 Internet Draft Nimrod Functionality June 1994 (a) Each forwarding agent caches an advertisement from at least one node representative, route agent, and association agent with the same scope as itself (provided the latter two agents exist within its scope). This ensures forwarding agents sharing a scope know how to reach an agent of each type within that scope. (b) Each node representative, route agent, and association agent caches advertisements from all other agents of the same type and with the same scope as itself and responds to such advertisements with an advertisement of its own. This ensures that all agents of a given type and sharing a scope know how to reach each other, thus providing efficient updating of the database maintained by these agents. (c) Each boundary forwarding agent caches advertisements from all other boundary forwarding agents with the same scope as itself and responds to such advertisements with an advertisement of its own. This ensures that all boundary forwarding agents sharing a scope know how to reach each other, and hence how to reach all node exit points defined by that scope. (d) Each interior forwarding agent caches an advertisement from at least one boundary forwarding agent with the same scope as itself, thus ensuring that interior forwarding agents sharing a scope know how to reach the node boundary defined by that scope. 3. The advertising and recipient agents are boundary forwarding agents with different scopes such that one scope is not a subset of the other. In this case, these agents are boundary forwarding agents in neighboring nodes. If the advertisement arrived on a physical link designated to be internal to the node, the recipient agent discards and does not distribute the advertisement. This may happen if those of a node's boundary forwarding agents resident in operational physical devices are not activated simultaneously. In this case, advertisements may escape their scope. Provided the advertisement arrived on a physical link designated to be connected to an external neighbor, the recipient agent caches the advertisement and responds with an advertisement of its own. This ensures that boundary forwarding agents in neighboring nodes know how to reach each other. The recipient agent usually does not redistribute the advertisement, unless the advertising agent has a permanent scope. In this case, the recipient agent distributes the advertisement to a node representative within its scope who in turn distributes the advertisement to all node representatives sharing its scope. This information is subsequently used by node representatives during locator acquisition and arc formation, described respectively in sections 4.4.1 and 4.5.1. 4. In all other cases, the advertisement has escaped its scope, and the recipient agent neither forwards nor caches the information. This is unlikely to happen but may occur if new agents in already operational 15 Internet Draft Nimrod Functionality June 1994 devices are activated out of order. Not all agents responsible for a given scope need reside within that scope. An advertising agent external to its scope forwards its advertisement toward its scope, according to the scheme discussed in section 3.2. Upon receiving the advertisement, a boundary forwarding agent internal to the advertising agent's scope floods the advertisement throughout that scope. The distribution and caching rules listed above apply to advertisements originated externally as well as internally to their scope. However, agents residing internal to their scope never provide advertisements to agents residing external to their scope. The reason is that external agents simply use their scope to reach internal agents and do not require more specific information. 4.3.1 Neighbor Discovery All agents issue agent discovery advertisements during initialization. However, after initialization, endpoint representatives and boundary forwarding agents acting on behalf of their lowest-level scopes also periodically issue these advertisements on the physical links to their external neighbors. The neighbors, acting on behalf of their lowest-level scopes, in turn respond with their own advertisements. We call this procedure neighbor discovery. Neighbor discovery enables endpoint representatives and boundary forwarding agents to detect the current set of neighbors reachable externally. The external neighbors of endpoint representatives are the first-hop forwarding agents, directly connected by physical links. The external neighbors of boundary forwarding agents are the boundary forwarding agents in neighboring nodes, directly connected by physical links. Endpoint representatives and boundary forwarding agents use this information to detect when they have new neighbors and hence when they should acquire new locators. Boundary forwarding agents also use this information to determine when they should alert their node representatives to form new arcs and in turn construct new maps, as described in section 4.5, and when they should stop forwarding traffic over a particular physical link to a neighbor that is no longer reachable. 4.4 Locator Acquisition All Nimrod entities require locators for routing. These locators are expressed with respect to a given clustering hierarchy. Each node and each arc has exactly one locator, whereas an endpoint may be associated with several locators. Entity locators are assigned during entity initialization following activation, reconfiguration, or movement. Although they may be preconfigured as part of the entity attributes, locators are usually 16 Internet Draft Nimrod Functionality June 1994 acquired by exchanging information with other agents. In an internetwork in which physical assets are not stationary, dynamic locator acquisition is especially useful as it enables an entity to obtain a locator without human intervention. The locator acquisition procedure depends upon knowledge of the existence and scope of certain agents, and hence agent discovery must precede locator acquisition. When acquiring a locator for an entity, an entity representative always attempts to obtain a locator at the lowest level possible, in order to minimize the number of new entities visible at higher levels. In this section, we describe node and endpoint locator acquisition; we describe arc locator acquisition in section 4.5.1. 4.4.1 Node Locators A single node representative is responsible for acquiring a locator for its node. That node representative begins by determining the scope within which the node's locator should be acquired. If the node representative's temporary scope contains a permanent prefix, that node representative uses that prefix to define the scope for locator acquisition. Otherwise, the node representative examines the lowest-level scopes of all neighboring boundary forwarding agents, obtained during agent discovery. From all such permanent scopes, the node representative uses the common prefix as the scope within which its node's locator should be acquired. The node representative then sends a locator request message, containing the selected scope, to a boundary forwarding agent, which in turn relays the message to a neighboring boundary forwarding agent. Upon receipt of a node locator request, the neighboring boundary forwarding agent relays the message toward a node representative for the specified scope. The recipient node representative then determines, according to its node's connectivity requirements, whether to honor the request. Hence, the locator request message must contain information, such as the name of the requestor's management authority, that enables the recipient node representative to evaluate the request. The recipient node representative informs the requesting node representative of its decision about the locator request. If it elects to honor the request, the recipient node representative responds with a new node locator, unique among the locators of its node's component nodes and outgoing arcs. Upon receiving the response, the requesting node representative must then determine, according to its connectivity requirements, whether to accept the new node locator. Hence, the locator response message should contain information that enables the requesting node representative to evaluate the response. Once a node representative acquires a new locator for its node, it updates its scope with the new locator and it notifies all agents who share its scope to update their scopes accordingly. A node comprising component nodes 17 Internet Draft Nimrod Functionality June 1994 has interior forwarding agents. Upon receiving a scope update, an interior forwarding agent then acts on behalf of the node for which it is a boundary forwarding agent, to notify a corresponding node representative within that scope, and so on. Thus, when a node representative acquires a new permanent scope and hence a new locator for its node, the notification of the locator change trickles down to all nodes at lower levels. Endpoint representatives and neighboring boundary forwarding agents acting on behalf of their lowest-level scopes learn of the new locator indirectly through the neighbor discovery procedure. Thus, a node locator change reaches all affected endpoints. The endpoint representatives use the new locator information to determine whether they should associate their endpoints with this locator. The neighboring boundary forwarding agents notify their node representatives which in turn use the new locator information as a signal to determine whether to reconstruct their node's map to include a new arc to the new node. Node maps are constructed from information provided in component nodes' maps, as described in section 4.5. In the worst case, construction of a new map at a lowest-level node may result in construction of new maps at all higher-level nodes in a clustering hierarchy. The node representative responsible for acquiring the node's locator is the one with the lowest-numbered EID of all mutually reachable representatives for the given node. Note that node representatives learn which has the lowest-numbered EID through the agent discovery procedure. Node representatives may also act autonomously to obtain a locator for their node, in the case in which node representatives become disconnected from each other following agent discovery. Specifically, each node representative that discovers it does not have the lowest-numbered EID expects to receive a permanent scope within a certain amount of time after initialization begins. If no locator appears within that time, the node representative with the next lowest-numbered EID performs the locator acquisition procedure, and the other node representatives again wait to receive a permanent scope, and so on. Note that this procedure may result in multiple locators being assigned to the same node, as multiple node representatives may attempt locator acquisition concurrently. However, each node representative acquiring a node locator distributes the locator to the other node representatives with the same temporary scope. Thus, all mutually reachable node representatives sharing a common temporary scope will eventually discover that multiple node locators have been acquired. When this happens, all node representatives independently choose the single node locator to be the one with the lowest number (when the locator is viewed as a bit string). Those node representatives who acquired node locators that were not ultimately chosen return those locators to the node representatives from which they acquired them. 18 Internet Draft Nimrod Functionality June 1994 4.4.2 Endpoint Locators An endpoint representative attempts to acquire a set of locators for each of its endpoints lacking a preconfigured set of locators. That endpoint representative begins by determining the scopes within which the endpoint's locators should be acquired. Specifically, the endpoint representative examines the lowest-level scopes of all neighboring forwarding agents, obtained during agent discovery, and uses all differing permanent scopes as those with which to attempt association. For each scope selected and for each endpoint that has not yet been associated with a set of locators, the endpoint representative executes the following procedure. The endpoint representative begins by sending a locator request message, containing a selected scope, to a forwarding agent, which in turn relays the message to a node representative for the specified scope. The recipient node representative then determines, according to its node's connectivity requirements, whether to honor the request. Hence, the locator request message must contain information, such as the name of the endpoint's management authority, that enables the recipient node representative to evaluate the request. The recipient node representative informs the endpoint representative of its decision about the locator request. If it elects to honor the request, the recipient node representative responds with its node's locator. Upon receiving the response, the endpoint representative must then determine, according to its connectivity requirements, whether to accept the new node association. Hence, the locator response message should contain information that enables the endpoint representative to evaluate the response. Once an endpoint representative acquires a new node association, it updates the endpoint/locator associations for the affected endpoints, as described in section 4.6.1. 4.5 Map Construction Maps represent the interconnectivity of and the services provided by the individual physical assets of an internetwork, from the perspective of a given clustering hierarchy. Each node has a raw map and an abstract map derived from the raw map. A node's raw map depicts the component nodes, the arcs interconnecting component nodes, and the arcs connecting component nodes to external nodes. It also describes the services provided by each of these nodes and arcs. Note that the raw map is empty for nodes with no visible component nodes and arcs. A node's abstract map depicts the node and the arcs connecting it to external nodes. It also describes the services provided by the node between any pair of incoming and outgoing arcs and by the outgoing arcs themselves. We provide examples of how to represent this service information concisely in section 4.5.2. The abstract map represents the node's services and 19 Internet Draft Nimrod Functionality June 1994 connectivity to external nodes that the node's management authority elects to advertise externally. It does not necessarily represent the actual services or external connectivity provided by the node's physical assets. In addition to the above information, the abstract map may also provide some indication of intra-node services to component nodes or endpoints associated with the node. It is the responsibility of the node's management authority to decide whether such information should be included in the node's abstract map. Each node representative is an authoritative source for the node's raw and abstract maps and distributes these maps on behalf of its node. A node representative constructs its node's raw map by assembling the abstract maps distributed by the component nodes. A node representative constructs its node's abstract map using information obtained from one or more of the following sources: 1. Abstraction of raw map information. 2. Configuration of node service attributes. 3. Measurement of qualities of service (e.g., delay, throughput, or reliability) across the node and across outgoing arcs. The procedures used to create abstract maps need not be the same for every node. Here is an example of how a node representative might derive the service attributes for its node's abstract map from its node's raw map. Using information provided in the raw map, the node representative first generates a set (not necessarily exhaustive) of routes between each pair of incoming and outgoing arcs. The node representative knows, through the arc formation procedure described in section 4.5.1, which incoming and outgoing arcs for component nodes compose which incoming and outgoing arcs for its node. For each route generated, the node representative determines the service attributes, based on those advertised in the abstract maps of the component nodes. The node representative then decides how to abstract the service attributes of these routes for its node's abstract map. 4.5.1 Arc Formation A single node representative is responsible for forming arcs from its node to neighboring nodes. As in section 4.4.1, that node representative is the one with the lowest-numbered EID. Furthermore, the same backup timeout mechanism ensures that some node representative will form arcs for the node, should the selected node representative become disconnected from the others. At the lowest level, arcs are formed by clustering physical links from the given node to external nodes. Arcs may also be formed, using a node's raw map, by clustering arcs connecting component nodes to external nodes. 20 Internet Draft Nimrod Functionality June 1994 When forming arcs by clustering physical links, a node representative determines which links will compose which arcs. First, the node representative obtains, through agent discovery, candidate component physical links. These are physical links from the given node to external nodes. Then, the node representative groups these physical links according to which of their neighboring boundary forwarding agents are common to the same lowest-level scope. This information defines the scopes of the arc requests. When forming arcs by clustering existing arcs, a node representative determines which component arcs will compose which arcs. First, the node representative obtains, from the node's raw map, candidate component arcs. These are arcs from the node's component nodes to external nodes. Then, the node representative groups these component arcs according to which of their destination nodes are components of the same enclosing node. This information defines the scopes of the arc requests. For each scope and candidate arc determined through the grouping procedures described above, the node representative executes the following arc formation procedure. The node representative begins by sending an arc request message to a node representative for the specified scope. Each arc request message must contain information, such as the name of the requestor's management authority, that enables the recipient node representative to determine, according to its connectivity requirements, whether to honor the request. The recipient node representative informs the requesting node representative of its decision about the arc request. Upon receiving a positive response to an arc request, the requesting node representative must then determine, according to its connectivity requirements, whether to accept the new arc. Hence, the arc response message should contain information that enables the requesting node representative to evaluate the response. Once a node representative definitely decides to form a new arc from its node, it informs all other node representatives sharing its scope, by distributing to them the locator for this arc. The arc's locator has as prefix the locator of the arc's source node and is unique among the source node's component nodes and outgoing arcs. Thus, all node representatives within an arc's source node learn of the existence of the outgoing arc. All representatives for the source node use the same clustering and abstraction algorithms. Hence, each can determine independently which physical links or component arcs are included in the new arc and what that arc's advertised service attributes should be. The source node representative also informs a representative for the arc's destination node, which in turn informs all node representatives sharing its scope, of the arc's existence. Thus, all representatives of an arc's destination node learn of the existence of the incoming arc from the given source node. All representatives of the destination node also have the same raw map for the node. Hence, each can determine independently the set of possible components of the new incoming arc, by grouping incoming arcs to 21 Internet Draft Nimrod Functionality June 1994 component nodes according to which of those arcs' source nodes are components of the given source node. Node representatives use incoming and outgoing arc information to construct their node's abstract map. Each arc must have at least one arc representative, and that representative is also a representative for the arc's source node. In fact, the arc's representatives are all representatives of the arc's source node. The network manager may initially configure attributes to be maintained by the arc's representatives. These attributes include offered service information, from the perspective of the arc as service provider. This service information may include not only services in terms of quality, monetary cost, and access restrictions, but also service-related properties such as the names of the arc's management authorities and the types of nodes to which the services should be advertised. Services apply across the arc from its source node to its destination node. Service quality includes but is not limited to offered delay, throughput, reliability, ordering, and security. Access restrictions include but are not limited to who may access the service, for what purposes, and when. The management authorities for the arc are the same as the management authorities for its source node. All arc representatives apply the same abstraction procedures for determining their arc's service attributes, as described in section 4.5.2. 4.5.2 Abstraction of Service Information The set of all services available between a pair of incoming and outgoing arcs is the set of services available on all routes across the node between the arcs. The set of all services available on an outgoing arc is the set of services available on each of the component outgoing arcs. A node's abstract map may include all of this service information. However, the quantity of service information may be unacceptably large for a node with many routes connecting incoming and outgoing arcs, many arcs composed of many component arcs, or many different service attributes for these routes and arcs. To reduce the size of its node's abstract map, a node representative uses concise representations of service attributes. For example, suppose several pairs of incoming and outgoing arcs share the same services on the routes connecting them. In the abstract map, these service attributes need only be listed once together with the relevant arc pairs, rather than individually for each arc pair. The node representative may also reduce the size of its node's abstract map by applying abstraction procedures to the service attributes related to a particular pair of incoming and outgoing arcs, to all pairs of incoming and outgoing arcs, or to a particular outgoing arc. In any case, the abstracted service attributes should reflect the actual services provided, in order to maximize the chance that the routes generated using abstract maps will actually satisfy the traffic service requirements. As part of the abstraction procedure, a node representative determines the number of 22 Internet Draft Nimrod Functionality June 1994 distinct sets of service attributes to be advertised in its node's abstract map. The node representative assigns each set a label to be used in place of the descriptions of the attributes in the set, when specifying routes as described in section 5.1. The following are example abstraction algorithms for reducing the quantity of service information in a node's abstract map: 1. Eliminate from the abstract map those services that are available only on a small number of routes between a pair of incoming and outgoing arcs, on routes between a small number of incoming and outgoing arc pairs, or on a small number of outgoing arcs. 2. Eliminate from the abstract map those services that have severe restrictions (e.g., available only to a small number of users, for short periods of time, or for an unusual purpose). 3. For the node services provided between each pair of incoming and outgoing arcs or between all such arc pairs, abstract the services provided by the component routes. For the arc services provided on each outgoing arc, abstract the services provided by the component arcs. Example abstraction techniques include: (a) A pessimistic view of the actual services. Such a view might be formed by choosing from the actual services the intersection of the service restrictions (when service restrictions are expressed in terms of what is permitted rather than what is not permitted), the worst (e.g., maximum delay, minimum throughput) value for each quality of service, and the maximum fee for service. (b) An optimistic view of the actual services. Such a view might be formed by choosing from the actual services the union of the service restrictions (when service restrictions are expressed in terms of what is permitted), the best (e.g., minimum delay, maximum throughput) value for each quality of service, and the minimum fee for service. (c) An ``average'' view of the actual services. Such a view might be formed by choosing from the actual services a subset of the service restrictions that appears to apply to the majority of users, the mean value of each quality of service, and the mean value of the fee for service. (d) A range of the actual services. Such a view might be formed by combining the pessimistic and optimistic views. We do not mandate the use of specific service abstraction algorithms for Nimrod. Instead, the abstraction algorithms applied in different portions 23 Internet Draft Nimrod Functionality June 1994 of an internetwork may be completely different. In general, we expect that network managers will choose the services to advertise for their networks so as to maximize their expected revenues. This means trading off the cost incurred in and the income generated by providing a particular service. We expect most networks to offer a set of basic low-cost services to all users as well as special and thus more expensive services to particular groups of users. 4.5.3 Map Updates A node representative updates its node's raw and abstract maps whenever they change. Specifically, a node representative updates its node's raw map whenever it receives a new abstract map from a component node. The node representative updates its node's abstract map in response to a change in the node's connectivity or services, resulting from a new raw map, reconfiguration of the node's service information, or new service measurements. All representatives of a given node have access to the same raw map and use the same abstraction algorithms, and hence can construct the same abstract map for the node. Recall that each set of service attributes for a node or an arc includes information concerning the types of nodes to which the attribute set may be advertised. Thus, a node's raw and abstract maps may have sets of service attributes with restrictions on their distribution. Although each node has a single raw map and a single abstract map, the advertised portion of a map depends upon the intended recipient. Hence, different recipients may obtain different subsets of the same map. The reason is that a node representative adheres to the distribution restrictions associated with its node's and arc's service attributes when distributing its node's maps. Thus, in an internetwork, a given route agent receives from only those parts of a node's maps that are distributable according to the distribution restrictions. In the extreme case, if the distribution restrictions on each set of service attributes associated with a given node or arc preclude a route agent from learning of these attributes, then the node or arc is invisible to the given route agent. A node representative distributes its node's raw and abstract maps in response to map queries, as described in section 4.5.4. It also automatically distributes its node's abstract map, throughout the scope of its node's enclosing node, whenever there is a change in the portion of the map distributable throughout that scope. Only one of a node's representatives initiates automatic distribution of the node's new abstract map, in order to minimize the amount of internetwork resources consumed in map distribution. That node representative is the one with the lowest-numbered EID. A backup timeout mechanism (such as that described in section 4.4.1) ensures that some node representative will distribute a new abstract map following a change in node connectivity or services. The subset of a node's abstract map distributed during automatic map 24 Internet Draft Nimrod Functionality June 1994 distribution contains the sets of service attributes that may be advertised to all nodes within the enclosing node. A node representative begins automatic map distribution by sending the abstract map to one of its boundary forwarding agents, who also acts as a forwarding agent at the next higher-level scope, i.e., the scope of the enclosing node. That forwarding agent distributes the map to one of the route agents and one of the node representatives sharing that scope. The recipient route agent in turn distributes the map to all route agents sharing that scope, who may then use the information to generate routes within the given scope. The recipient node representative distributes the map to all node representatives sharing that scope. These node representatives may then determine whether the information contained in the new abstract map from the component node results in a change in their node's abstract map. In the worst case, a change in a low-level 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 internally multiply connected. Nevertheless, to control the amount of processing and transmission bandwidth required to handle maps from nodes that change often, the procedure for distributing new abstract maps should include a minimum permitted interval between successive map updates for the same node. 4.5.4 Map Queries Route agents query node representatives for maps to be used in route generation. A route agent sends its map request message toward the desired scope. When the map query reaches a boundary forwarding agent within that scope, the forwarding agent relays the query to a node representative for that scope. The node representative then determines, according to the distribution restrictions for the map's sets of service attributes, how it will respond to the map request. Hence, the map request message should contain information, such as the name of the requestor's management authority, that enables the recipient node representative to evaluate the request. The node representative responds to the route agent with the largest subset of the requested map that is consistent with the distribution restrictions. This subset may be the empty if the node representative cannot fill the request. If the node representative issues a negative response to a map query, that implies that it either does not have the requested map or that the distribution restrictions preclude distribution of the requested map to the route agent. Although the information provided by an abstract map is usually sufficient for route generation, a route agent may desire more detailed information than that provided by the node's abstract map. In this case, the route agent requests a raw map of the node, which provides information about the node's internal structure in terms of component nodes and arcs and their services. Raw maps are large, and hence node representatives distribute raw 25 Internet Draft Nimrod Functionality June 1994 maps only in response to queries for them. To enable a route agent to control the amount of internetwork resources it requires to obtain and store raw maps, Nimrod offers a choice of raw map queries along the dimensions of complete or partial raw maps containing full or abbreviated abstract maps. A raw map is complete if it contains abstract maps of all component nodes and partial if it contains abstract maps of a proper subset of component nodes. To obtain a partial map, a route agent must specify which component nodes to include in the map. An abstract map is full if it contains service information and abbreviated if it does not contain service information. Route agents use raw map queries to gain a more detailed view of a node or a portion of a node and thus to generate a route that meets specific service requirements. An example of map querying proceeds as follows. A route agent desiring more information about a node requests a complete abbreviated raw map of that node, i.e., a raw map composed of abbreviated abstract maps for the component nodes. Information contained in this raw map provides the route agent with pointers to the component nodes and arcs. In response to the receipt of this raw map, the route agent then requests a partial full raw map, i.e., a raw map composed of full abstract maps for specific component nodes. The route agent may also place direct queries for some abstract maps of specific component nodes. Queries may be placed for increasingly detailed information, using raw map contents to locate component nodes, and so on. 4.5.5 Node Partitions With Nimrod, a node is a contiguous collection of internetwork physical assets such that if all such assets are functioning properly, traffic can flow between any two endpoints contained within the node by traversing assets that belong only to that node. We call this the connectivity property of a node. However, if enough physical assets fail, a node may no longer possess the connectivity property; in this case, the node is partitioned. A node partition may affect the reachability of only a small number of endpoints associated with a node, but it may also significantly impair the ability of the node to provide transit services. In particular, an incoming arc and an outgoing arc may no longer be connected by intra-node routes. Only when a node's transit service is affected by a partition must this information be advertised in the node's abstract map. Note that a partition may isolate a set of endpoints associated with a node, so that they are not reachable from any incoming arc. This form of partition may not necessarily have an impact on transit service, and hence such a partition may be invisible from outside of the node. Node representatives monitor the connectivity between incoming and outgoing arcs using their node's raw map, and they update their node's abstract map when the connectivity changes. Hence, node representatives can detect the existence of node partitions. A partitioned node has multiple disjoint 26 Internet Draft Nimrod Functionality June 1994 sub-nodes, each of which possesses the connectivity property and has its own has raw and abstract maps. Communication between endpoints within two different sub-nodes of the same partitioned node requires a route that leaves and subsequently re-enters the node. Within a sub-node, mutually reachable node representatives maintain the sub-node's raw map and construct the sub-node's abstract map from this raw map. A single node representative within a sub-node initiates map distribution for the sub-node. This node representative is the one with the lowest-numbered EID among the representatives within the sub-node. As we mentioned in section 4.5.3, a backup timeout mechanism ensures that some node representative will distribute a new abstract map for the sub-node, following detection of a partition. Within a given node, each node representative and route agent should retain at most one abstract map for each sub-node of each of its partitioned component nodes. Recipients of maps for a partitioned node can distinguish the maps, and hence the sub-nodes, by using the EIDs of the node representatives issuing the maps. Thus, Nimrod does not require distinct locators for the separate sub-nodes of a partitioned node, even though each sub-node has a distinct set of maps. When constructing a route to an endpoint in a partitioned node, a route agent should generate a set of routes, one to each sub-node of the partitioned node. The reason is that the node's raw and abstract maps distributed by the sub-nodes do not indicate whether a given endpoint is reachable from a given sub-node. Thus, the route agent should generate multiple routes, testing each one until finding a route that actually reaches the endpoint. 4.6 Association Database Maintenance Endpoint representatives associate nodes and hence locators with the endpoints on whose behalf they act, as we discussed in section 4.4.2. They are also responsible for updating the assocation database with these new endpoint/locator associations. The association database is maintained by association agents, each of which must participate in updating and retrieval of association database contents. Each association agent caches endpoint/locator associations learned from authoritative sources and also maintains the set of endpoint/locator associations for which it is an authoritative source. However, not all association agents are authoritative sources, and not all nodes must have association agents. Most Nimrod databases are organized according to the scope of the information they contain. Thus, to contact an authoritative source for a database portion corresponding to a given scope, an agent merely sends its query toward that scope. However, the authoritative sources for portions of the association database are not organized according to scope, for the following reason. The principal function of the association database is to 27 Internet Draft Nimrod Functionality June 1994 answer queries about the set of nodes currently associated with a given endpoint. In most cases, the querying agent probably has no idea where in an internetwork the endpoint currently resides, particularly if the endpoint is highly mobile. Authoritative sources for specific endpoint associations must be accessible using endpoint labels only. Each endpoint must have a globally unique label that can be used as a key for finding an authoritative source for that endpoint's associations. EIDs or mnemonic names are sufficient for this purpose. However, we recommend a label with structure derived from the organization of the management authorities that assign labels to endpoints, as described in section 4.2. Hence, the labels of endpoints managed by a common authority should share a common prefix. Successive management authorities within a hierarchy would direct a query down toward the correct authoritative sources, by examining successively longer prefixes of an endpoint label structured in this way. Authoritative sources for specific endpoints' associations should be situated in well-known stationary locations under the control of the endpoints' management authorities. Although not mandatory, such organization of authoritative sources significantly simplifies the management of the association database. Moreover, authoritative sources for specific endpoints' associations should ideally reside close to those endpoints so as to minimize the costs of updating the endpoint's associations. However, in the presence of highly mobile endpoints, such organization of authoritative sources may not be possible. Nevertheless, if a management authority has a priori knowledge of the vicinity in which a set of its endpoints may be found, that authority may be able to place authoritative sources within that vicinity. The following example serves to illustrate how one might organize authoritative sources within an association database. Consider an endpoint label as a string of n bits composed of m, where 1 < or = m < or = n, substrings with not necessarily equal numbers of bits. Beginning from the left of the label and successively concatenating substrings, each string thus formed identifies a prefix to a block of endpoint labels. The prefix corresponds to a particular management authority. This correspondence must then be extended to a particular node in the clustering hierarchy and hence a set of association agents. One may simply select the node in which the given management authority resides in order to make the correspondence. To construct linked chains of management authorities leading to authoritative sources for endpoint associations, one begins with the universal node. For each value of the first substring of a label endpoint, one selects the node containing the management authority corresponding to that prefix. One must ensure that all association agents in the universal node point toward the selected node for locating authoritative sources for endpoints whose label prefix equals that substring. One then repeats the procedure at the association agents in the selected nodes, but with the label prefix equal to the concatenation of the corresponding first and second substrings. The procedure concludes when all substrings but the last 28 Internet Draft Nimrod Functionality June 1994 have been included in the label prefix, thus forming a linked chain of nodes following the management authority organization. At this point, each node at the end of a linked chain is the authoritative source for all endpoints whose label prefix equals the concatentation of the first m-1 substrings. 4.6.1 Association Updates When an endpoint representative issues an association update message for a specific endpoint, it distributes that update to association agents within its vicinity. Updating proximate association agents helps to reduce the cost of nearby endpoints' association queries for the given endpoint's locators. The endpoint representative also distributes the association update to the authoritative sources for that endpoint's associations, which may not necessarily reside within the given vicinity. Implications of updating associations when dealing with mobile endpoints are not discussed here but instead are treated in [2]. Association updates propagate up the node clustering hierarchy toward the universal node and then back down along the management hierarchy toward the authoritative sources. Association update distribution begins when an endpoint representative distributes an association update to a neighboring forwarding agent whose scope equals the locator of the association contained in the update. That forwarding agent in turn distributes the association update to an association agent sharing its scope, if such an agent exists, and otherwise distributes the update to a boundary forwarding agent sharing its scope. In the latter case, the boundary forwarding agent acts as a forwarding agent at the next higher-level scope and in turn distributes the association update to an association agent for that scope, if such an agent exists, and so on. Upon receipt of an association update from a forwarding agent, an association agent distributes the update to all other association agents sharing its scope. Association agents receiving association updates from other association agents never redistribute those updates. Each association agent updates its association database according to the contents of the association update. The association agent that received the update from a forwarding agent determines whether it is an authoritative source for the given endpoint's associations. If it is an authoritative source, the association agent concludes update distribution. Otherwise, the association agent uses the endpoint label to determine whether its scope is within the linked chain of nodes pointing toward the authoritative sources for the endpoint's association. If the association agent's scope is not within the linked chain of nodes, the association agent distributes the update to a boundary forwarding agent sharing its scope. In this case, the boundary forwarding agent acts as a forwarding agent at the next higher-level scope and in turn distributes the association update to an association agent sharing its scope, if such an agent exists, and so on. However, if the association agent's scope is 29 Internet Draft Nimrod Functionality June 1994 within the linked chain of nodes, the association agent sends the update toward the next node in the chain, where it will be received by a boundary forwarding agent for that node. In this case, the boundary forwarding agent distributes the update to an association agent sharing its scope, and so on. With this update distribution procedure, the association update is guaranteed to reach a node in the linked chain of nodes leading to an authoritative source, as the universal node is the first node on every such chain. 4.6.2 Association Queries Endpoint representatives query association agents for the set of locators associated with the endpoints with which their endpoints communicate. An endpoint representative issuing an association query distributes it to a forwarding agent. That forwarding agent in turn distributes it to an association agent sharing its scope, if such an agent exists, and otherwise distributes it to a boundary forwarding agent sharing its scope. In the former case, if it cannot answer the query, the association agent forwards the query to a boundary forwarding agent sharing its scope. In either case, the boundary forwarding agent then acts as a forwarding agent at the next higher-level scope and in turn distributes the association update to an association agent for that scope, if such an agent exists, and so on. We note that association queries follow the same distribution patterns as association updates. An indirect association query may be answered by any association agent that has the information requested. However, a direct association query may only be answered by an authoritative source. In the worst case, a direct association query may have to travel all the way up to an association agent in the universal node and back down to an authoritative source. 5 Routes When one endpoint wishes to communicate with another endpoint, the representative of the endpoint initiating communication issues an association query in order to determine the set of locators associated with the other endpoint. We expect that the source endpoint's representative will usually be the one initiating communication, but the destination endpoint's representative may also initiate communication. The initiating endpoint representative also sends a transport request to a first-hop forwarding agent. This request contains the following information: 1. The source and destination endpoint EIDs. 2. The set of source and destination locators. 30 Internet Draft Nimrod Functionality June 1994 3. The traffic service requirements, which may imply a route granularity and a desired forwarding mode (discussed in section 6). 4. Optionally, a data message. Upon receiving a transport request, a forwarding agent first determines if it already has a path to the specified endpoint, which meets the traffic service requirements. Provided such a path exists, the forwarding agent returns to the initiating endpoint representative the path label to use for the session's traffic and may proceed to forward that traffic over the existing path. If no such path exists, the forwarding agent determines the forwarding mode and whether to request a route, based on the traffic service requirements. We note that if the session has no strict traffic service requirements, route generation may not be required. In this case, an adequate route description may consist of the source and destination endpoint locators only. Otherwise, the forwarding agent sends a route request to a route agent sharing its scope. The route request contains the source and destination endpoint locators and the traffic service requirements. In response to a route request, a route agent first searches its route database for a set of feasible routes and, if unsuccessful, attempts to generate a set of feasible routes. Feasible routes are those that meet the service requirements of the source and destination endpoints and are consistent with the services of the intermediate nodes and arcs contained in the routes. Before including an entity within a route, the route agent ensures that at least one set of the entity's service attributes are consistent with the traffic service requirements. The route agent then records the label for this set of service attributes, to be used within the route specification described in section 5.1. Once the route generation procedure concludes, the route agent responds to the forwarding agent either with a set of feasible routes or with an indication that no feasible route could be found. Nimrod permits both localized and distributed route generation. We expect that route generation will normally be localized at a single route agent acting on behalf of a source or destination. Such localization of route generation helps to increase the source's or destination's control over route selection and to confine the costs of route generation to those agents acting on behalf of the traffic using the route. For Nimrod, we do not mandate the use of specific route generation procedures. Instead, each route agent may apply route generation procedures of its own choosing. Such flexibility enables network managers to make their own cost/performance tradeoffs in route generation and to experiment with new route generation algorithms in their networks. However, there are well-defined inputs and outputs common to any such route generation procedure. Inputs include a set of abstract maps and the source and destination endpoint locators and service requirements. Outputs include a 31 Internet Draft Nimrod Functionality June 1994 set of routes or an indication that a feasible route could not be found. 5.1 Representation A route agent generates routes at the minimum node and arc granularity necessary to meet the traffic service requirements, subject to the node and arc granularity of the advertised maps at its disposal. Different portions of the same route may be generated at different granularities. Furthermore, the route agent need only specify those nodes and arcs that must be included in the route in order to satisfy the traffic service requirements. The portion of a route between two successive entities in a route specification is called a route segment. A route specification must include at least the source and destination nodes. Moreover, each entity in the specification must be accompanied by the label of the set of service attributes that resulted in its inclusion in the route. This service information is used to guide message forwarding across these entities. Fine granularity routes concentrate control over and cost of route selection at a route agent acting on behalf of a source or destination and minimize the number of independent forwarding decisions exercised at intermediate forwarding agents. Coarse granularity routes relinquish some control over and distribute the cost of route selection to intermediate forwarding agents along the route, and hence may require some distributed route generation to fill in the segments of the route between the specified nodes and arcs. However, coarse granularity routes are more fault tolerant than fine granularity routes, because the intermediate forwarding agents can quickly repair failed routes by obtaining regenerated segments from intermediate route agents. Moreover, coarse granularity routes provide a means for load balancing, because the intermediate forwarding agents can distribute the load over multiple routes between specified entities. The following is an example of route specification granularity. If the source or destination endpoint requests a particular service provider, then the node containing that service provider should be included in the route. However, if there are several equivalent ways of reaching that service provider, the source or destination may wish to leave that segment of the route unspecified, so that intermediate forwarding agents can choose among multiple alternate routes for that segment. 6 Message Forwarding Nimrod supports two distinct message forwarding modes: flow and datagram. (We note that the four forwarding modes described in [1] each fall into one of the two modes described here.) 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. 32 Internet Draft Nimrod Functionality June 1994 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 globally unique label. 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 links between the path label and the path's previous- and next-hop forwarding agents and service guarantees, if any. In flow mode, data messages carry the path label which guides the message forwarding decisions at forwarding agents along the path. Flow mode provides fast and consistent message forwarding according to path labels, once the session-specific state is established in the forwarding agents. However, this state consumes memory in forwarding agents, and the procedure for its installation imposes some delay before data messages can be forwarded successfully to their destinations. Flow mode should be used when session-specific state is necessary to meet traffic service requirements or when the cost of state installation and maintenance can be amortized over many messages. Hence, we recommend flow mode for traffic sessions requiring guaranteed service or consisting of several messages. 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 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. Datagram mode should be used when the state of the internetwork is unpredictable or when the cost of forwarding state installation and maintenance is unacceptable. Hence, we recommend datagram mode for traffic sessions traversing highly mobile or unreliable portions of an internetwork or consisting of few messages. Both of the Nimrod forwarding modes rely on the existence of underlying paths to fill in route segments. Nimrod can support unicast and multicast paths using the same mechanism. A path may connect one or more source endpoints and one or more destination endpoints. The context of a path is the lowest node in the clustering hierarchy that contains all of the path's sources and destinations. Forwarding agents execute a path maintenance procedure to install path state in and remove path state from their forwarding databases. Each forwarding agent maintains a portion of the forwarding database pertaining to those paths that originate, terminate, or pass through it. As previously discussed, Nimrod permits multiple traffic sessions to use the same path, thus helping to contain the amount of internetwork resources consumed in setting up, tearing down, and managing resources for paths. Path labels 33 Internet Draft Nimrod Functionality June 1994 enable forwarding agents to multiplex and demultiplex multiple traffic sessions over a single path. 6.1 Forwarding State For simplicity of discussion, we focus on unicast paths in the remainder of section 6. Multicast paths are treated in detail in [3]. 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, P1, derived from the selected route between the source and destination endpoints for the traffic session. This path comprises multiple contiguous paths, P2(1), ..., P2(n), one for each of the n segments of the route on which P1 is based. Each P2(j) itself comprises multiple contiguous paths corresponding to each of its segments, and so on. In general, for each Pi(j) composing Pi-1(k), the initiator and terminator of Pi(j) maintain a link to the path Pi-1(k), which helps to guide forwarding along the segments of Pi-1(k). Forwarding agents 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 the paths required for traffic sessions. 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 first-hop forwarding agent for an endpoint receives a 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 and if the forwarding agent is at the source endpoint, this forwarding agent provides the source endpoint representative with the path label to use for all of the session's traffic. However, if no such path exists, the forwarding agent attempts to obtain a feasible route for the session. Note that route generation might not be required and that a feasible route might include only the source and destination locators. Given a feasible route, the forwarding agent proceeds to determine where to install the necessary forwarding state. 34 Internet Draft Nimrod Functionality June 1994 Flow mode: The forwarding agent becomes the initiator of a new path, P1, and generates a setup message. If the route contains more than the source and destination locators, the forwarding agent then checks whether there already exists a satisfactory path for the session from itself to the next entity in the route specification. Provided such a path, P2(1), exists, the forwarding agent proceeds as follows: Flow mode: The initiator of P2 (which is also the initiator of P1) links P1 and P2(1) in its forwarding database and sends P1's setup message to the target of P2(1). Upon reception of the setup message, the target of P2(1) also links P1 and P2(1) in its forwarding database. Datagram mode: The initiator of P2(1) sends the data message to the target of P2(1). If no satisfactory path, P2(1), yet exists between the first two entities in the route specification, the forwarding agent attempts to form such a path by piecing together existing paths. First, the forwarding agent determines the context of the prospective path, P2(1). This context is used to limit the search for component paths, confining it to paths with targets in that context. The forwarding agent begins with the enclosing node of the second entity in the route specification. If that enclosing node is within the context of P2(1), the forwarding agent then checks whether there already exists a satisfactory path whose target is within the enclosing node. If such a path, P3(1), exists, the forwarding agent proceeds as it did with P2(1). Otherwise, the forwarding agent proceeds to the enclosing node's enclosing node and again looks for a satisfactory path, and so. If the forwarding agent's search reaches the context node without finding a satisfactory path to any of the second entity's ancestral nodes contained within but not equal to that context, then there are no ``short-cut'' paths to the second entity. The forwarding agent then seeks a paths up to the first entity's enclosing node, as there are likely to be more existing paths between higher-level entities. To this end, the forwarding agent checks whether there already exists a satisfactory path whose target is an outgoing arc of the first entity's enclosing node. If such a path, P3(1), exists, the forwarding agent proceeds as it did with P2(1). Otherwise, the forwarding agent attempts to obtain a feasible route and set up a path, P3(1). If there are no short-cut paths from the first entity's enclosing node to the second entity, the above procedure may need to be repeated for successively higher-level ancestors of the first entity, up to the context of P2(1). 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. The procedure terminates after attaining the last 35 Internet Draft Nimrod Functionality June 1994 entity in the route, possibly linking together paths at many different levels. Flow mode: If the initiator of P1 is at the source endpoint, this forwarding agent provides the source endpoint representative with the path label to use for all of the session's traffic, once all necessary links between all relevant paths have been formed. 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 links between paths stored in their forwarding databases. Upon receipt of a data message, the target of path Pj(i) finds it is linked to path Pj-1(k) which in turn is linked to path Pj(i+1) and hence is the initiator of Pj(i+1). This forwarding agent strips off the label for Pj(i) and replaces it with the label for Pj(i+1), before forwarding the message along that path. 6.1.1 An Example of Path Setup We illustrate the installation of forwarding state in flow mode, through the following example. Suppose two endpoints wish to establish a traffic session. Let U:V:W:X be the locator for the source endpoint, and let U:V:A:B be the locator for the destination endpoint. Thus, the context for any potential path between these two endpoints is U:V. To improve readability of the figure, we have dropped the context from the locators, and we have left the arcs unlabelled. Suppose that no satisfactory path for the session yet exists between U:V:W:X and U:V:A:B. The first-hop forwarding agent then becomes an initiator for a new path f. Suppose that there are no special service requirements for the session and so the route for f consists of only the source and destination nodes. To assemble f, the initiator of f attempts to find a satisfactory path from U:V:W:X to any node in U:V:A. Suppose no such path yet exists. In this case, the initiator of f has reached the context U:V without finding a satisfactory path and must then look for a satisfactory path to an arc of U:V:W. Suppose such a path g exists. The initiator of g (which is also the initiator of f) links f and g and sends the setup message for f to the target of g, which also links f and g. Suppose there are no short-cut paths from the target of g to U:V:A:B. Then the target of g looks for a satisfactory path to any node in U:V:A. Suppose no such path yet exists. In this case, the target of g requests a route to U:V:A and receives a route terminating at U:V:A:C. The target of g becomes the initiator of the path e to U:V:A:C, which in turn consists of paths 36 Internet Draft Nimrod Functionality June 1994 d(1), ..., d(5), one for each route segment of e. The initiator of e links f and e, and the initiator of each d(i) links e and d(i). Furthermore, the initiator of e sends the setup message for f to the target of e. The target of e then looks for a satisfactory path to U:V:A:B. Suppose such a path h exists. The initiator of h (which is also the target of e) links f and h and then sends the setup message for f to the target of h, which in turn also links f and h. Thus, path installation for f requires only a single route request for the path, e, and new forwarding state installed at only eight forwarding agents. 6.1.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 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 the forwarding agent's scope. When a forwarding agent refuses a datagram message, it informs the source endpoint representative. If a forwarding agent refuses many datagrams from the same endpoint, it might only send refuse messages for some rather than all of these datagrams, in order to help reduce internetwork resource consumption for refusals. Refuse message generation might be triggered by a timer or by a certain number of datagram refusals in a row. 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 contacts the corresponding endpoint representative in order to determine 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 message indicating that it will generate its own route. The target is 37 Internet Draft Nimrod Functionality June 1994 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 may tear down a path by removing the path's state from its forwarding database. Reasons for path teardown might include detection of a connectivity failure along a path, a change in entity service attributes such that the route on which the path is based is no longer feasible, and path expiration if a path exceeds a maximum prescribed lifetime. 6.1.3 Forwarding Information in Messages Datagram messages and setup messages for flow mode must contain information about the route the message should take. Below, we describe this information together with some useful but optional information. 1. Flow mode/datagram mode indicator. 2. Context, in the form of the locator for the node that contains the source and destination endpoints. All locators listed below are relative to this context. Although not required, including a context specification at the beginning may significantly reduce the length of the route specification. 3. Indication of whether the endpoint at the initiator is a source or a destination. This information is required in setup messages only. For datagram messages, the initiator is always the source. 4. EID and locator of the endpoint at the initiator. This information is used by the target endpoint in sending data messages to the initiating endpoint. 5. EID and locator of the endpoint at the target. 6. Locator for each intermediate node and arc (there may be none) included in the route, and label for the set of service attributes for that entity. This information, together with the source and destination locators, constitutes the route specification. 7. Service requirements for the endpoint at the initiator. Intermediate forwarding agents use this service information in obtaining intermediate paths that meet the initiating endpoint's service requirements. For datagram messages, these are always the source service requirements of the endpoint. For setup messages, these depend on whether that endpoint is a source or a destination. If the initiator is at the destination, the target may refuse the path if it 38 Internet Draft Nimrod Functionality June 1994 is inconsistent with the source service requirements. In this case, the target may use the destination service requirements contained in the setup message in conjunction with the source endpoint's service requirements in generating a route which is consistent with both the source and destination service requirements, as described above in section 6.1.2. 8. Path label for the route specified. This information is required in setup messages only. Ideally, path labels should be globally unique. However, in a large internetwork, global uniqueness may require an unacceptably large number of bits per path label. Large paths labels consume space in messages and processing time in forwarding agents, and so path labels are likely to be relatively short strings of bits and thus not necessarily globally unique. However, path labels may be assigned in ways that it is unlikely for two paths with the same label to converge at the same forwarding agent. Moreover, when they occur, path label collisions can be resolved. These issues will be addressed in detail during Nimrod protocol specification. Note that setup messages as well as datagram messages may contain user data in addition to the forwarding information described above. 7 Security Considerations The protocols used to transport Nimrod control information must include mechanisms for source authentication, error detection, and recency determination that will help to prevent the introduction of incorrect control information, as we discussed in section 3.1. In particular, these mechanisms will help to prevent denial of service attacks resulting from masquerading sources of control information, noise introduction, and message replays. This document is not a protocol specification and therefore does not contain a detailed description of the security mechanisms used in Nimrod. 8 Author's Address Martha Steenstrup BBN Systems and Technologies 10 Moulton Street Cambridge, MA 02138 Phone: (617) 873-3192 Email: msteenst@bbn.com 39 Internet Draft Nimrod Functionality June 1994 References [1] I. Castineyra, J. N. Chiappa, and M. Steenstrup. The Nimrod Routing Architecture. June 1994. Working Draft. [2] S. Ramanathan. Mobility Support for Nimrod: Requirements and Approaches. June 1994. Working Draft. [3] S. Ramanathan. Multicast Support for Nimrod: Requirements and Approaches. June 1994. Working Draft. 40