idnits 2.17.1 draft-ietf-nimrod-fun-pro-spec-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-25) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity. ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 1 longer page, the longest (page 2) being 59 lines Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 1702 instances of too long lines in the document, the longest one being 9 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (30 August 1996) is 10100 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Missing reference section? '1' on line 267 looks like a reference -- Missing reference section? '2' on line 712 looks like a reference -- Missing reference section? '3' on line 269 looks like a reference -- Missing reference section? '4' on line 2041 looks like a reference -- Missing reference section? '6' on line 1176 looks like a reference -- Missing reference section? '10' on line 1237 looks like a reference -- Missing reference section? '9' on line 1238 looks like a reference -- Missing reference section? 'Node' on line 1523 looks like a reference -- Missing reference section? 'AgentType' on line 1523 looks like a reference -- Missing reference section? '7' on line 3447 looks like a reference -- Missing reference section? '13' on line 4538 looks like a reference -- Missing reference section? '11' on line 3504 looks like a reference -- Missing reference section? '12' on line 3505 looks like a reference -- Missing reference section? '16' on line 4534 looks like a reference Summary: 9 errors (**), 0 flaws (~~), 2 warnings (==), 17 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Nimrod Working Group Ram Ramanathan 2 Internet Draft Martha Steenstrup 3 March 1996 BBN Systems and Technologies 4 draft-ietf-nimrod-fun-pro-spec-00.txt Expires 30 August 1996 6 Nimrod Functionality and Protocol Specifications, Version 1 8 Status of this Memo 10 This document is an Internet Draft. Internet Drafts are working documents 11 of the Internet Engineering Task Force (IETF), its Areas, and its Working 12 Groups. Note that other groups may also distribute working documents as 13 Internet Drafts. 15 Internet Drafts are draft documents valid for a maximum of six months. 16 Internet Drafts may be updated, replaced, or obsoleted by other documents at 17 any time. It is not appropriate to use Internet Drafts as reference 18 material or to cite them other than as a ``working draft'' or ``work in 19 progress''. 21 Please check the 1id-abstracts.txt listing contained in the 22 ``internet-drafts'' directories on ftp.isi.edu (U.S. West Coast), 23 ds.internic.net (U.S. East Coast), munnari.oz.au (Pacific Rim), 24 nic.nordu.net (Europe), or ftp.is.co.za (Africa) to learn the current status 25 of any Internet Draft. 27 Distribution of this Internet Draft is unlimited. Please send all comments 28 to nimrod-wg@bbn.com. 30 Abstract 32 Nimrod is a scalable routing architecture designed to support a dynamic 33 internetwork of arbitrary size, to provide service-specific routing in the 34 presence of multiple constraints, and to admit incremental deployment 35 throughout an internetwork. The key features of Nimrod include 36 representation of internetwork connectivity and services in the form of maps 37 at multiple levels of abstraction; source- and destination-controlled route 38 generation and selection based on maps and traffic service requirements; and 39 source- and destination-controlled message forwarding according to the 40 routes selected. This document contains a description of Nimrod 41 functionality and a specification of the protocols constituting Nimrod. In 42 particular, the operations pertinent to the map, locator, adjacency, route, 43 and forwarding databases are described, and the Reliable Transaction, 44 Update, Query-Response, Path Management, and Discovery protocols are 45 specified. 47 Acknowledgments 49 We thank Tom Calderwood, Winston Edmond, Charlie Lynn, Trevor Mendez, Betty 50 O'Neil, Mike Patton, Ram Ramanathan, and Tim Shepard for producing an 51 experimental Nimrod software system that has enabled us to test the 52 practicality of Nimrod. We are especially grateful to Charlie Lynn, chief 53 architect of the Nimrod software, for his flexible system design, his 54 careful and critical analysis of the Nimrod protcols, and his detailed 55 packet formats (depicted in this document). 57 1 58 Contents 60 1 Scope and Overview 1 62 2 Introduction 1 64 2.1 Overview of the Nimrod Architecture : :: :: :: :: :: :: :: :: :: 2 66 2.1.1 Clustering and Abstraction : :: :: :: :: :: :: :: :: :: :: 2 68 2.2 Nimrod Entities :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 3 70 2.3 Nimrod Routing Functions and Databases : :: :: :: :: :: :: :: :: 5 72 2.3.1 Nimrod Database Consistency :: :: :: :: :: :: :: :: :: :: 6 74 2.4 Nimrod Agents :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 8 76 3 Nimrod Operation : An Overview 10 78 3.1 Maps :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 10 80 3.1.1 Map Update :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 10 82 3.1.2 Map Request and Release : :: :: :: :: :: :: :: :: :: :: :: 11 84 3.2 Routes :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 11 86 3.2.1 Route Generation :: :: :: :: :: :: :: :: :: :: :: :: :: :: 12 88 3.2.2 Route Request and Release :: :: :: :: :: :: :: :: :: :: :: 12 90 3.3 Locators : :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 13 92 3.3.1 Acquiring and Releasing Node Locators :: :: :: :: :: :: :: 13 94 3.3.2 Acquiring and Releasing Endpoint Locators : :: :: :: :: :: 14 96 3.4 Adjacencies : :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 14 98 3.4.1 Acquiring, Activating, and Releasing Adjacencies :: :: :: 14 100 3.5 Paths : :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 15 102 3.5.1 Path Setup :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 16 104 3.5.2 Path Acceptance :: :: :: :: :: :: :: :: :: :: :: :: :: :: 18 106 i 107 3.6 Control Message Integrity and Authentication : :: :: :: :: :: :: 19 109 3.6.1 Timestamps :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 19 111 3.6.2 Authentication : :: :: :: :: :: :: :: :: :: :: :: :: :: :: 20 113 4 Reliable Transaction Protocol 21 115 4.1 Services Interface :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 21 117 5 The Update Protocol 23 119 5.1 Service Interface : :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 23 121 5.2 Protocol Operation :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 24 123 5.2.1 Update Header :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 24 125 5.2.2 Originating Agent Operations :: :: :: :: :: :: :: :: :: :: 25 127 5.2.3 Transit Agent Operations :: :: :: :: :: :: :: :: :: :: :: 26 129 5.2.4 The Update Message Action Table (UMAT) : :: :: :: :: :: :: 26 131 5.3 Database Specific Updates :: :: :: :: :: :: :: :: :: :: :: :: :: 27 133 5.3.1 Adjacency Updates : :: :: :: :: :: :: :: :: :: :: :: :: :: 28 135 5.3.2 Locator Updates :: :: :: :: :: :: :: :: :: :: :: :: :: :: 28 137 5.3.3 Map Updates : :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 29 139 6 The Query-Response Protocol 30 141 6.1 Service Interface : :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 30 143 6.2 Protocol Operation :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 30 145 6.3 Query/Response Header :: :: :: :: :: :: :: :: :: :: :: :: :: :: 31 147 6.4 Database Specific Request/Release :: :: :: :: :: :: :: :: :: :: 32 149 6.4.1 Adjacency Formation :: :: :: :: :: :: :: :: :: :: :: :: :: 32 151 6.4.2 Adjacency Release : :: :: :: :: :: :: :: :: :: :: :: :: :: 32 153 6.4.3 Adjacency Activation : :: :: :: :: :: :: :: :: :: :: :: :: 33 155 ii 156 6.4.4 Locator Acquisition :: :: :: :: :: :: :: :: :: :: :: :: :: 34 158 6.4.5 Locator Release :: :: :: :: :: :: :: :: :: :: :: :: :: :: 35 160 6.4.6 Map Acquisition :: :: :: :: :: :: :: :: :: :: :: :: :: :: 35 162 6.4.7 Map Termination Request : :: :: :: :: :: :: :: :: :: :: :: 36 164 6.4.8 Path Information Request :: :: :: :: :: :: :: :: :: :: :: 37 166 6.4.9 Route Generation Request/Reply :: :: :: :: :: :: :: :: :: 37 168 7 Path Management Protocol 39 170 7.1 Protocol Messages : :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 40 172 7.1.1 Setup : :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 40 174 7.1.2 Accept :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 42 176 7.1.3 Teardown : :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 43 178 7.1.4 Status :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 45 180 7.1.5 Ack :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 47 182 7.2 Protocol Finite-State Machines :: :: :: :: :: :: :: :: :: :: :: 48 184 7.2.1 Initiator :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 50 186 7.2.2 Intermediate Forwarding Agents and Target : :: :: :: :: :: 51 188 7.2.3 Check State Actions :: :: :: :: :: :: :: :: :: :: :: :: :: 53 190 8 Discovery Protocols 57 192 8.1 Neighbor Discovery :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 57 194 8.1.1 Neighbor Reachability :: :: :: :: :: :: :: :: :: :: :: :: 58 196 8.2 Agent Discovery :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 60 198 8.2.1 Flooding Agent Advertisements : :: :: :: :: :: :: :: :: :: 61 200 8.2.2 Distribution of Advertisements to Distant Agents :: :: :: 62 202 8.2.3 Unreachable Agents :: :: :: :: :: :: :: :: :: :: :: :: :: 63 204 8.2.4 Node Partitions :: :: :: :: :: :: :: :: :: :: :: :: :: :: 64 206 iii 207 8.3 Route Tracing :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 65 209 9 Packet Formats 67 211 9.1 Overview : :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 67 213 9.2 IP and Security Headers : :: :: :: :: :: :: :: :: :: :: :: :: :: 68 215 9.3 Nimrod Forwarding Information : :: :: :: :: :: :: :: :: :: :: :: 70 217 9.4 Transaction Headers :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 76 219 9.5 Update, Query, and Response Protocol Headers : :: :: :: :: :: :: 77 221 9.6 Update Operation Messages :: :: :: :: :: :: :: :: :: :: :: :: :: 79 223 9.7 Query/Response Operation Messages :: :: :: :: :: :: :: :: :: :: 80 225 9.8 Discovery Message Header :: :: :: :: :: :: :: :: :: :: :: :: :: 82 227 10 Appendix 1: Figures for Update and Q-R protocols 85 229 11 Appendix 2: Basic Data Formats 90 231 11.1Element (NimElem) : :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 90 233 11.2Locator (NimLoc) :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 91 235 11.3Endpoint Identifier (NimEID) :: :: :: :: :: :: :: :: :: :: :: :: 92 237 11.4Endpoint Name (NimFQDN) : :: :: :: :: :: :: :: :: :: :: :: :: :: 93 239 11.5Node Identifier (NimNID) :: :: :: :: :: :: :: :: :: :: :: :: :: 93 241 11.6Services (NimServ) :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 93 243 11.7Maps (NimMap) :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 94 245 11.8Routes (NimRute) :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: 95 247 11.9Credentials (NimCred) :: :: :: :: :: :: :: :: :: :: :: :: :: :: 96 249 11.10Path Labels (NimPLbl) :: :: :: :: :: :: :: :: :: :: :: :: :: :: 96 251 11.11Time (NimSecs, NimNTP) :: :: :: :: :: :: :: :: :: :: :: :: :: :: 96 253 11.12Authenticator (NimAuth) : :: :: :: :: :: :: :: :: :: :: :: :: :: 97 255 iv 256 12 Security Considerations 98 258 13 Contact Information 98 260 v 261 1 Scope and Overview 263 This document contains a description of Nimrod functionality,and a 264 specification of the protocols constituting Nimrod. While it has been our 265 intention that the document be self-contained, it would help the reader to 266 be familiar with the Nimrod architecture and functionality as described in 267 [1] and [2]. Nimrod does not specify support for mobility or multicast, but 268 does specify requirements for solutions to mobility and multicast within the 269 Nimrod context. A discussion of these issues can be found in [3] and [4]. 271 The document has been organized so that readers may inform themselves at 272 various levels of detail. Specifically, readers wishing to know only what 273 Nimrod's functionality is may confine themselves to sections 2 and 3. For 274 readers wishing to understand and evaluate the protocols comprising Nimrod, 275 we additionally recommend sections 4, 5, 6, 7, and 8. Finally, for Nimrod 276 implementors, sections 9 and 11 give additional details. 278 2 Introduction 280 Nimrod is a scalable routing architecture designed to support a dynamic 281 internetwork of arbitrary size, to provide service-specific routing in the 282 presence of multiple constraints, and to admit incremental deployment 283 throughout an internetwork. The key features of Nimrod include 284 representation of internetwork connectivity and services in the form of maps 285 at multiple levels of abstraction; source- and destination-controlled route 286 generation and selection based on maps and traffic service requirements; and 287 source- and destination-controlled message forwarding according to the 288 routes selected. 290 At the most general level, one may view any routing system as a set of basic 291 functions which are producers and consumers of certain databases of routing 292 information. These routing functions and their associated routing 293 information include: 295 1. Assembling, distributing, and collecting information necessary for 296 route generation and selection. This information includes internetwork 297 connectivity and services, traffic service requirements, and locations 298 of traffic sources and destinations. 300 2. Generating and selecting routes, based on the collected information. 302 3. Establishing in routers information necessary for forwarding messages, 303 based on the selected routes. 305 4. Forwarding messages along these routes. 307 Routing systems may, however, differ in the details of the mechanisms that 308 provide a particular routing function. As Nimrod has been designed for 309 routing in large, heterogeneous, and dynamic internetworks, its basic 310 routing functions include additional mechanisms for reducing the quantity of 312 1 313 routing information that must be distributed, processed, and stored 314 throughout an internetwork; for discovering and accommodating changes in 315 routing information caused by physical changes in an internetwork; and for 316 protecting the integrity of routing information. 318 2.1 Overview of the Nimrod Architecture 320 Before Nimrod routing can be applied within an internetwork, the 321 internetwork must be represented in terms of the two basic Nimrod entities: 322 nodes and endpoints. The internetwork's physical assets, such as routers, 323 point-to-point links, and multiaccess networks, must be captured in Nimrod 324 maps comprising interconnected nodes. Traffic sources and destinations must 325 be cast as Nimrod endpoints. Nimrod entities possess attributes (e.g., 326 location with respect to the maps, interconnectivity with other entities, 327 and service information) which are important for routing. 329 2.1.1 Clustering and Abstraction 331 Ideally, Nimrod maps should be constructed so as to satisfy the following 332 two primary, and potentially conflicting, goals: 334 1. Minimize the amount of routing information maintained throughout an 335 internetwork. 337 2. Maintain routing information sufficient to generate routes that meet 338 traffic service requirements. 340 To satisfy these goals, Nimrod employs two complementary map construction 341 procedures, namely clustering of internetwork physical assets into nodes and 342 abstraction of attributes of the component physical assets resulting in node 343 attributes. 345 The objective of clustering is to reduce the number of entities visible to 346 Nimrod routing at any given level of the hierarchy. Nodes are usually 347 formed by clustering physical assets possessing similar attributes. These 348 attribute similarities might be in terms of, for example, qualities of 349 service, restrictions on access to services, or ownership of these assets. 350 Such clustering results in a reduction in the amount of information 351 necessary to characterize these physical assets, without a reduction in 352 information detail. However, an internetwork's physical assets may be 353 diverse enough so that clustering according to attribute similarity produces 354 no significant reduction in the number of entities visible to Nimrod 355 routing. In this case, alternative clustering criteria (e.g., geographical 356 locality of physical assets) may be employed. 358 Clustering may be applied repeatedly, such that physical assets are first 359 clustered into nodes, and then nodes are themselves clustered into larger 360 nodes, and so on. Iterative clustering further reduces the number of 362 2 363 entities visible to Nimrod routing at a given level of the hierarchy, and 364 results in a hierarchical organization of nodes with a single top-level 365 universal node containing all other entities. In the clustering hierarchy, 366 the clustering criteria applied at different levels may not necessarily be 367 the same. 369 The objective of abstraction is to reduce the amount of information required 370 to characterize an entity visible to Nimrod routing. Nodes whose component 371 physical assets possess different attributes rely on information abstraction 372 in order to reduce the number of attributes used to characterize them. 373 Abstraction procedures include, for example, eliminating attributes 374 possessed by only a small percentage of the component physical assets or 375 expressing attributes in terms of ranges of values exhibited by these 376 physical assets. Multiple abstraction procedures may be applied to produce 377 the attributes of a given node (e.g., first eliminating attributes possessed 378 by only a few physical assets and then taking the average values of the 379 remaining attributes for the physical assets in the node). 381 Nimrod does not mandate the choice of clustering and abstraction procedures 382 to invoke in an internetwork. Rather, this choice is a local one under the 383 control of the managers of the portions of the internetwork to be 384 represented as Nimrod nodes, and hence network managers may develop 385 procedures that best suit their needs. We note that the specific clustering 386 and abstraction procedures employed in an internetwork may have a 387 significant effect on the quality of routes generated and on the cost of 388 routing information maintenance. Hence, network managers should exercise 389 care in selecting and using these procedures and may wish to experiment with 390 several different ones during the evolution of their nodes. Although 391 clustering and abstraction procedures may be fully automated, we recommend 392 allowing manual intervention in order to enable network managers to make 393 cost-benefit tradeoffs appropriate for their particular networks. 395 2.2 Nimrod Entities 397 All of the Nimrod routing functions are performed with respect to an 398 internetwork's representation in terms of the basic Nimrod routing entities, 399 namely nodes and endpoints. Each Nimrod entity has a set of attributes, 400 each of which may be established through one or more of the following 401 methods: 403 1. Manual configuration. 405 2. Automatic acquisition during initialization. 407 3. Active measurement. 409 4. Abstraction of attributes of component nodes. 411 A node is a set of contiguous internetwork physical assets. It may be 412 formed by clustering physical assets directly or by clustering existing 414 3 415 nodes. If the given node itself comprises component nodes, the routing 416 system employed to route traffic within or across the node is Nimrod 417 routing. Otherwise, this routing system may use any other routing 418 protocol(s). A node's attributes include its: 420 1. Node identifier (NID). An NID is a location-independent referent for a 421 node. It is a globally unique, relatively short, fixed-length bit 422 string used by Nimrod-capable devices to communicate node identity 423 (primarily used before a node acquires its locator). 425 2. Locator. A node's locator is a globally unique label describing the 426 node's position in the clustering hierarchy. It consists of the global 427 locator of the node's enclosing node in the clustering hierarchy, 428 concatenated with a local bit-string, called an element, unique among 429 all component nodes and endpoints of the enclosing node. 431 3. A pool of locator elements that may be assigned to its component nodes 432 and endpoints. 434 4. Constraints on forming associations with endpoints. An association is 435 a relationship formed between a node and an endpoint, such that the 436 endpoint acquires a locator from the node. A node may be associated 437 with multiple endpoints, and an endpoint may be associated with 438 multiple nodes. 440 5. Constraints on forming adjacencies with other nodes. An adjacency is a 441 neighbor relationship formed between two nodes that have a direct 442 communication capability. The neighbor relationship need not be 443 symmetric. For example, nodes X and Y may agree to a relationship in 444 which Y is adjacent to X, but X is not adjacent to Y. 446 6. Maps consisting of the node's current adjacencies and service 447 offerings. 449 7. Credentials of the node's manager, used in forming node adjacencies and 450 endpoint associations. 452 An endpoint is a traffic source, destination, or both that is visible to 453 other Nimrod entities through association with one or more Nimrod nodes. 454 Examples of endpoints include hosts and routers or even processes within 455 hosts and routers. An endpoint's attributes include its: 457 1. Endpoint identifier (EID). An EID is a location-independent referent 458 for an endpoint. It is a globally unique, relatively short, 459 fixed-length bit string used by Nimrod-capable devices to communicate 460 endpoint identity. 462 2. Names. A endpoint name is a globally unique, variable-length, 463 structured, ASCII string used primarily by humans to refer to the 464 endpoints. Nimrod uses Domain Name System (DNS) names for this 465 purpose. 467 4 468 3. Constraints on forming associations with nodes. 470 4. Locators. An endpoint's locators are obtained from the nodes with 471 which the endpoint is associated. Therefore, as an endpoint may be 472 associated with more than one node, it may obtain more than one 473 locator. 475 5. Traffic service requirements from the perspectives of the endpoint as 476 source and as destination. 478 6. Credentials of the endpoint and its manager, used respectively in 479 authentication of routing information and in forming node associations. 481 2.3 Nimrod Routing Functions and Databases 483 At the core of Nimrod lies a set of distributed databases containing routing 484 information that is constructed, accessed, and acted upon by the routing 485 functions. These databases and their relationships to the routing functions 486 are as follows: 488 1. Node attributes. Each node has a set of attributes used in forming 489 node adjacencies and endpoint associations, in constructing maps, and 490 in assigning locators to component nodes and endpoints. 492 2. Endpoint attributes. Each endpoint has a set of attributes used in 493 forming node associations and in selecting routes. 495 3. Endpoint/locator associations. Nimrod endpoint locators are used in 496 generating routes between and in forwarding messages toward those 497 endpoints. Endpoint/locator associations are stored and accessed 498 through the DNS. 500 4. Maps. Each Nimrod node has a set of maps describing its traffic 501 service offerings and adjacencies to other nodes, collectively called 502 connectivity specifications and used in generating routes. 504 5. Routes. Routes are generated in response to requests on behalf of 505 traffic sessions between endpoints. Route generation works within the 506 constraints of the service requirements specified by the endpoints and 507 the services and adjacencies advertised in maps. Each route is 508 expressed in terms of nodes and their corresponding connectivity 509 specifications and is used to construct forwarding information to be 510 installed in routers. 512 6. Forwarding information. Nimrod traffic forwarding is path-oriented, 513 where a path is defined by the forwarding state stored in routers 514 according to the route selected and is under the control of the source 515 and destination endpoints. 517 5 518 Databases relevant to but not maintained by Nimrod are the pool of NIDs that 519 may be assigned to nodes and the pools of EIDs and names that may be 520 assigned to endpoints. EIDs and NIDs may be drawn from the same number 521 space. 523 Each of the Nimrod routing functions uses portions of the contents of one or 524 more of the Nimrod databases. In a dynamic internetwork, the procedures for 525 updating and retrieving the contents of Nimrod databases will be performed 526 frequently. Therefore, each Nimrod database is organized to optimize the 527 performance of these procedures along the dimensions of delay, internetwork 528 resource consumption, fault tolerance, and load balancing. 530 Nimrod databases are maintained by a combination of routers, hosts, and 531 special-purpose physical devices. The use of special-purpose devices means 532 that routers and hosts do not have to assume all of the processing and 533 memory load related to routing. For example, as route generation is a 534 computationally intensive procedure, some network managers may elect to use 535 dedicated devices, distinct from routers, whose sole purpose is to generate 536 Nimrod routes. 538 For most Nimrod databases, we suggest distributing database contents over 539 several physical devices throughout an internetwork. In a large 540 internetwork, one may in fact have no other choice; the memory required for 541 a single Nimrod database may exceed the storage capacity of any one device. 542 Also, we suggest distributing database contents with partial redundancy, 543 such that each database entry is stored in more than one device. 544 Distributed organization of Nimrod database contents helps to reduce the 545 database maintenance and query-response costs borne by any one physical 546 device. Partial redundancy helps to increase the availability of database 547 contents and to reduce the costs of the average database query-response; it 548 may also increase the cost of the average database update, however. 550 2.3.1 Nimrod Database Consistency 552 Each Nimrod database contains routing information crucial for successful 553 communication between endpoints. Inconsistencies between the actual state 554 of the internetwork and the state as reflected by Nimrod database contents 555 may result in impaired communication between a pair of endpoints and, in the 556 worst case, may completely disrupt communication among all endpoints. Thus, 557 minimizing the number as well as the consequences of such inconsistencies is 558 a primary objective of the Nimrod database maintenance procedures. 560 Inconsistencies between database contents and actual internetwork state may 561 result from delays incurred in updating database contents following 562 internetwork state changes. Many of the Nimrod databases are volatile and 563 hence require mechanisms for keeping the contents current, in order to 564 prevent propagation and use of stale routing information. Database 565 maintenance includes rapid and reliable updating with new information as 566 well as removal of old information. We recommend that each Nimrod database 568 6 569 be maintained as a cache, such that each entry has a finite lifetime and may 570 be removed from the database when it expires. Cache entry lifetimes will 571 depend upon the expected duration of the usefulness of the cached 572 information. 574 Inconsistencies between database contents and internetwork state may also 575 result from errors introduced directly into database contents. Errors in 576 Nimrod database contents may be injected inadvertently, through faults in 577 the transmission media or in physical device memory, through 578 misconfiguration, or through incorrect implementation of the database 579 maintenance procedures. Errors may also be injected intentionally by 580 malicious parties, through distribution of fictitious database updates and 581 responses to queries (by capturing and corrupting existing database messages 582 or by generating new messages) or through modification of database 583 maintenance procedures. 585 Updating and retrieval of Nimrod database contents involve frequent 586 communication of routing information over an internetwork and hence expose 587 this routing information to numerous potential opportunities for error 588 introduction. Therefore, the protocols that carry out these procedures 589 attempt to protect the routing information from introduced errors and 590 malicious parties. In particular, the protocols for communicating 591 information to or from a Nimrod database permit the intended recipient of 592 that information to: 594 1. Authenticate the information. 596 2. Detect corruption of the information. 598 3. Determine whether the information received is newer than any related 599 information the recipient already possesses. 601 4. Indicate to the sender the receipt of acceptable or unacceptable 602 information. 604 These protocols also permit the sender to retransmit to the intended 605 recipient any information that it perceives the recipient has failed to 606 receive successfully. 608 We note that while Nimrod requires consistency between database contents and 609 internetwork state, it does not require different physical devices to 610 maintain identical views of internetwork state (e.g., two different routers 611 might maintain different maps for the same node, both of which are 612 consistent with the physical assets of that node). Furthermore, Nimrod does 613 not require consistency in route selection across different physical devices 614 (e.g., two different routers might select routes to the same destination 615 such that each router is included in the other's route). The underlying 616 path-oriented nature of message forwarding in Nimrod enables loop-free 617 forwarding in the presence of such inconsistencies in route selection among 618 routers. 620 7 621 2.4 Nimrod Agents 623 Within an internetwork, each Nimrod database is stored in a set of physical 624 devices. Each physical device containing a portion of a Nimrod database 625 executes a set of functionality, called a Nimrod agent, for manipulating the 626 database contents. A single device may contain portions of more than one 627 Nimrod database and hence may contain more than one Nimrod agent. Each 628 Nimrod agent is a Nimrod endpoint. 630 For each Nimrod database, certain agents are responsible for maintaining 631 specific portions. Such an agent is designated as an authoritative source 632 for that portion of the database. A specific portion of a database may have 633 multiple authoritative sources. Each agent is an authoritative source for 634 some portion of a database but may also obtain and cache information learned 635 from authoritative sources for other portions of that same database. In 636 addition to receiving unsolicited database updates, a Nimrod agent may also 637 refresh its database by querying other agents of the same type for their 638 database contents. 640 Nimrod agents and databases are organized according to the clustering 641 hierarchy, such that each node has a set of agents that act on its behalf to 642 answer or forward database queries. The Nimrod agents and their 643 corresponding functions are as follows: 645 1. Node representatives. Each Nimrod node must have one or more 646 representatives which maintain the database of the node's attributes 647 and act on its behalf. A node representative is responsible for 648 forming adjacencies with other nodes; forming associations with 649 endpoints; assigning locator elements to component nodes and endpoints; 650 receiving maps from component nodes; and constructing its node's maps. 651 All node representatives for a given node must construct the same map 652 for a node, i.e., must use the same algorithms for map construction. 653 Node representatives are authoritative sources for the maps of the 654 nodes they represent. 656 2. Endpoint representives. Each Nimrod endpoint must have one or more 657 representatives which maintain the database of the endpoint's 658 attributes and act on its behalf. An endpoint representative is 659 responsible for forming associations with nodes; discovering, through 660 the DNS, locators of the endpoints with which its endpoints wish to 661 communicate; requesting routes to those endpoints by querying route 662 agents, and ensuring that the routes satisfy its endpoints' service 663 requirements; initiating path setup along the selected routes; and 664 forwarding data along the established paths. Endpoint representatives 665 are authoritative sources for the locators and service requirements of 666 the endpoints they represent. 668 3. Route agents. Each node may have one or more route agents responsible 669 for collecting maps from nodes throughout the internetwork and for 670 generating and dispensing routes based on endpoint service requirements 671 and node connectivity specificiations advertised in maps. Route agents 673 8 674 are authoritative sources for the routes they generate. 676 4. Forwarding agents. Each node must have one or more forwarding agents 677 responsible for initiating neighbor relationships with forwarding 678 agents in other nodes; requesting routes; installing forwarding 679 information in routers; forwarding messages along established paths; 680 and controlling traffic flow into and out of the node according to the 681 node's access restrictions. While each of these functions could be 682 performed by a different type of agent, we have elected to concentrate 683 them in the forwarding agents, in order to minimize the number of 684 different agent types performing the Nimrod routing functions. 685 Forwarding agents are authoritative sources for the portion of the 686 paths that traverse them. 688 Agents acting on behalf of a node need not reside within that node. 689 Nevertheless, we recommend locating all Nimrod agents (and their databases) 690 close to the entities on whose behalf they act. Such location minimizes 691 delay and internetwork resource consumption when updating the databases 692 corresponding to those entities and in responding to queries from other 693 agents in the vicinity of those entities. A Nimrod agent residing external 694 to the node on whose behalf it acts must be configured with location 695 information for that node, and in some cases for ancestral and descendant 696 nodes as well, in order communicate with other agents that act on behalf of 697 the same node. Also, the forwarding agents within a node must be configured 698 with the location of agents external to but acting on behalf of that node. 699 We recommend placing all agents within the node on whose behalf they act, 700 and henceforth we describe agent behavior from this perspective. 702 9 703 3 Nimrod Operation : An Overview 705 This section describes key operating procedures in Nimrod from the viewpoint 706 of how the various databases are managed. The description is organized 707 based on the pertinent database. Specifically, maps (construction, 708 dissemination), routes (generation, acquisition), locators (acquisition, 709 notification, release), adjacencies (formation, release), paths (setup, 710 teardown, forwarding), and discovery (of neighbors, agents) are addressed. 711 This section only provides a brief summary of the operations. For a 712 detailed exposition, the reader is referred to [2]. In the postscript 713 version of this document, the reader may refer to Figures 1-4 (given in 714 Appendix 1), for a quick overview of some of these operations. Throughout 715 this section, the text contains references in parentheses to labels in these 716 figures. 718 3.1 Maps 720 Each Nimrod node has a set of maps describing its traffic service offerings 721 and its adjacencies. Maps are maintained and updated by node 722 representatives. A node representative maintains two kinds of maps for its 723 node: a basic map that depicts the child nodes, the adjacencies between 724 child nodes and the adjacencies between child and external nodes, plus the 725 services provided by each of these nodes; an abstract map that depicts the 726 node, its adjacencies to other nodes and the services provided by the node 727 between any pair of such node adjacencies. A node representative may 728 construct its abstract map using information obtained from abstraction of 729 basic map, configuration, or measurement of service qualities across the 730 node. Abstraction mechanisms are not a part of the Nimrod specifications. 731 Rather, each node may choose to implement its own abstraction algorithm 732 (uniform throughout a given node). Maps are updated using map updates, and 733 obtained using map queries as described below. 735 3.1.1 Map Update 737 Map updates are distributed using the Update protocol described in 738 section 5. Maps are automatically updated in response to topological 739 changes using constrained hierarchical flooding, according to the following 740 procedure. The update originates from a representative (Nr in Figure 1) of 741 the node whose abstract map has changed. This node representative sends 742 (arrow 1 in Figure 1) the new abstract map to each boundary forwarding agent 743 (F) which is a neighbor of a boundary forwarding agent of its parent. Note 744 that sending to each forwarding agent is necessary in order to handle the 745 case of a partitioned node. F in turn forwards (arrow 2) the update to each 746 Fpto which it is adjacent. That Fp sends (3.x) the map to all of the node 747 representatives (Nrp) and all of the route agents (Rp) in the node. 749 The change in the abstract map of a node causes a change in the basic map of 750 the parent node. This in turn may or may not cause a change in the abstract 752 10 753 map of the parent node. If it does, then a designated node representative 754 originates another update to the next higher level by sending (4) the new 755 abstract map to a boundary forwarding agent. The procedure described above 756 now applies again at this higher level. In the worst case, a change in a 757 node's abstract map may force changes in all of its ancestral nodes' 758 abstract maps. We expect such changes to be rare, especially in nodes whose 759 descendants are multiply connected. 761 3.1.2 Map Request and Release 763 Map requestsm, responses, and releases are transmitted using the 764 Query-Response protocol described in section 6. A map request is sent by a 765 route agent, acting on behalf of an endpoint wishing to obtain or subscribe 766 to the map of a node for route computation. A map release unsubscribes to 767 the map of the node for which a subscribe request was sent. Our description 768 below is in terms of map request; map release is very similar. The kinds of 769 maps that can be requested are as follows: 771 1. Abstract Maps. Two kinds of abstract maps can be requested - 772 abbreviated or full. An abstract map is full if it contains service 773 information (i.e., connectivity specifications) and abbreviated if it 774 does not. 776 2. Basic Maps. Two kinds of basic maps can be requested - complete or 777 partial. A basic map is complete if it contains abstract maps of all 778 component nodes and is partial if it only contains maps of a proper 779 subset of the component nodes. The abstract map of the component nodes 780 contained in a basic map may all be either full or abbreviated. 782 A route agent sends the map request towards the targeted node. A flag in 783 the request indicates whether or not a subscription is requested, i.e., 784 updates are to be automatically sent. When the map query reaches a boundary 785 forwarding agent for the targeted node, this forwarding agent relays the 786 query to a node representative for that node. The node representative 787 responds to the route agent with the largest subset of the requested map 788 that is consistent with the map distribution restrictions. If it does not 789 have the maps to fulfill the query, or if its restrictions do not permit it 790 to respond, it still sends a reply to the requestor containing a reason for 791 failure. A node representative is not required to support the map 792 subscription service. 794 3.2 Routes 796 Route agents use the maps obtained, either through automatic updates or in 797 response to explicit map requests, in order to do route generation. 798 Endpoint representatives and forwarding agents obtain these routes from the 799 route agent using route requests. A route specification is expressed in 800 terms of nodes and the connectivity specifications through those nodes, and 802 11 803 is used to specify forwarding information to be installed in routers. It 804 also lists the services provided by the route. 806 3.2.1 Route Generation 808 The input to route generation includes maps of the topology, a set of 809 session service requirements, and the source and the destination node 810 locators. Its output includes a (set of) route(s), or an indication that no 811 route can be found. Each route contains a sequence of node locators and 812 connectivity specification labels for nodes that have to be traversed in 813 order to meet the service requirements. 815 We note that the topology used for route generation typically represents the 816 network in varying levels of detail for different regions. Thus, the route 817 constructed by the route generation algorithm will typically not contain the 818 complete list of all routers through which a datagram should pass. The 819 details are filled in at the node where they are required in a recursive 820 fashion when setting up a path or forwarding datagrams (see section 7 for 821 details). Route generation algorithms are not specified by Nimrod. Rather, 822 each route agent may choose to implement its own route generation algorithm, 823 even within a single node. 825 3.2.2 Route Request and Release 827 Route requests, response, and releases are transmitted using the 828 Query-Response protocol described in section 6. An endpoint representative 829 or a forwarding agent that wishes to obtain a route to a destination may 830 request a route from a route agent. The route request contains the source 831 endpoint's EID and locators, the destination endpoint's EID and locators, 832 and the source and/or destination traffic service requirements. Note that 833 if there are no strict traffic service requirements, in terms of quality, 834 monetary cost, or access restrictions, a route may not need to be acquired 835 (the source and destination endpoint locators may suffice for the route). 836 Note also that the route agent to which a route request is sent need not be 837 in the same node as the requestor. 839 A route request may also be a subscription to a route, i.e., updated routes 840 are automatically sent to the subscriber. A route release is used to 841 unsubscribe to a specific route. Route agents are not required to support 842 the route subscription service in this version of Nimrod. 844 In response to a route request, a route agent first searches its route 845 database for a set of feasible routes and if unsuccessful, invokes the route 846 generation algorithm. The route agent may, in the process of attempting to 847 generate feasible routes, obtain more maps of nodes using the map query 848 procedure described in section 3.1.2. A route agent responds to the 850 12 851 requestor with either a set of feasible routes or an indication that no 852 feasible route could be found. 854 3.3 Locators 856 Nimrod nodes and endpoints require locators for routing. Each node has 857 exactly one locator and each endpoint is associated with at least one 858 locator. Locators are assigned during initialization following activation, 859 reconfiguration, or movement. The representatives of a node are responsible 860 for acquiring the node locator, and the endpoint representative is 861 responsible for acquiring the locators for each of its endpoints. 863 3.3.1 Acquiring and Releasing Node Locators 865 Node locator requests, responses, and releases are transmitted using the 866 Query-Response protocol described in section 6. Node locator acquisition 867 involves two phases. First, the designated representative of a node 868 acquires a locator from a representative of its parent node. Next, it 869 notifies all of the representatives within its node and all descendant nodes 870 of the existence of the new locator. The first phase is illustrated in 871 Appendix 1, Figure 2 and the second phase in Figure 3. 873 The designated node representative (Nr in Figure 3) wishing to acquire a 874 locator for a node Z first determines the node P from which its locator 875 should be acquired. This node representative (Nr) then sends (1) a locator 876 request message to a boundary forwarding agent (F) which forwards (2) the 877 locator request message to the neighboring boundary forwarding agent in the 878 parent node, which in turn relays (3) the message to a node representative 879 for P (Nrp). The request contains information that enables the recipient 880 node representative (Nrp) to evaluate the request and decide whether it can 881 or wants to honor the request. 883 The node representative responds (4) either with a new node locator (if it 884 decides to honor the request), unique among the locators of P's component 885 nodes, or a denial response otherwise. Upon receiving a positive response, 886 the originating node representative (Nr) decides whether to accept the 887 locator. 889 If it (Nr) decides to accept the locator, the node representative starts the 890 notification phase (refer Fig 3). Locator notifications are distributed 891 using the Update protocol described in section 5. The node representative 892 notifies all agents in its node (arrows 5.x), and all agents in Z's 893 descendant nodes, of the new locator. The latter is done by forwarding the 894 message to each forwarding agent in Z which is a neighbor of a forwarding 895 agent for one of Z's component nodes. These forwarding agents (Fc) in the 896 component nodes distribute the message to all agents in the component nodes 897 including boundary forwarding agents (Fcc) to their children and so on until 898 the locator trickles down to all of the nodes that have Z as an ancestor. 900 13 901 A locator release may be sent by a node representative of a node wishing to 902 unsubscribe to a locator. This could happen, for instance, if an 903 organization changes its service provider, or due to mobility of a network. 904 The node representative includes the old locator to be released, and the 905 locator and EID of the node representative that issued the locator, in its 906 locator release message to its parent. 908 3.3.2 Acquiring and Releasing Endpoint Locators 910 Endpoint locator requests, responses, and releases are transmitted using the 911 Query-Response protocol described in section 6. An endoint representative 912 attempts to acquire a set of locators for each of its endpoints. The 913 endpoint representative, say Er, selects a set of target nodes and for each 914 selected node Z, sends a locator request message identifying Z (label 5 in 915 Figure 2) to a node representative for Z. As in the case of node locators, 916 if this node representative decides to honor the request, it sends a 917 response (6) containing the locator. 919 3.4 Adjacencies 921 An adjacency is a neighbor relationship formed between two nodes that are 922 physically joined. The neighbor relationship need not be symmetric, i.e., 923 node A may be adjacent to node B but not vice versa. Adjacencies of a node 924 Z to an external node Y may be formed by clustering together adjacencies of 925 component nodes of Z to Y. At the lowest level, adjacencies are the physical 926 connections themselves. 928 3.4.1 Acquiring, Activating, and Releasing Adjacencies 930 Adjacency requests, responses, releases, and activations are transmitted 931 using the Query-Response protocol described in section 6. The distribution 932 of A single designated node representative is responsible for forming 933 adjacencies between its node and neighboring nodes. When forming 934 adjacencies by clustering existing adjacencies (or physical connections), 935 the node representative obtains candidate external adjacencies from the 936 node's basic map and groups these adjacencies according to which of their 937 destination nodes are components of the same enclosing node. This 938 information defines the target node for the adjacency formation requests. 940 For each candidate adjacency, the node representative initiates an adjacency 941 formation procedure (depicted in Appendix 1 - Figure 4). The node 942 representative (Nr) begins by sending an adjacency request (1) to a node 943 representative for the specified node (Nrs). Using information present in 944 this request, the recipient node representative (Nrs) determines whether or 945 not to honor the request, and replies (2) to the requesting node 946 representative (Nr) about its decision. If the response is positive, then 948 14 949 the node representative decides whether or not to accept the adjacency. If 950 it decides to accept, then it updates (3.x) all of the node representatives 951 of the newly formed adjacency. The node representative at the other end of 952 the adjacency (Nrs) also updates (4.x) all node representatives within its 953 node. The adjacency updates to node representatives in the nodes forming 954 the adjacency are distributed using the Update protocol described in 955 section 5. In addition, the adjacency is ``activated'' by having the two 956 node representatives inform the respective boundary forwarding agents 957 constituting the adjacency that Nimrod data traffic may now be passed. 959 If a node representative receives a negative reply to an adjacency request 960 message, the message may contain information that indicates that the 961 adjacency is not appropriate. An adjacency is terminated by sending an 962 adjacency release request to the node representative which granted the 963 adjacency. Management decisions and lack of data for a specified period of 964 time may be other reasons for terminating an adjacency. 966 3.5 Paths 968 Nimrod supports two distinct data message forwarding modes: flow and 969 datagram. For each mode, a forwarding agent's ``next-hop'' forwarding 970 decision is dictated by the information stored in its forwarding database 971 and by information contained within the message to be forwarded. 973 Flow mode requires the establishment of session-specific forwarding state in 974 certain forwarding agents along the routes selected for a traffic session. 975 With flow mode, each session is assigned one or more paths, derived from the 976 selected routes. A path corresponds to forwarding state stored in 977 forwarding agents along a route, and each path has a label which is unique 978 within all of these forwarding agents (but not necessarily globally unique). 979 Distinct traffic sessions may use the same path, and distinct paths may use 980 the same route. The minimum forwarding state required for flow-mode 981 forwarding includes linkages between the path label and the path's previous- 982 and next-hop forwarding agents (and service guarantees for traffic control, 983 if any). In flow mode, data messages carry the path label(s) that guides 984 the message forwarding decisions at forwarding agents along the path. 986 Datagram mode does not require the establishment of any session-specific 987 forwarding state. In datagram mode, data messages carry a description of 988 the selected route, which guides the message forwarding decisions at 989 forwarding agents along the route. Each forwarding agent at the beginning 990 of a route segment (the portion of a route between two successive nodes 991 listed in a route specification) makes an independent forwarding decision 992 for that segment, and hence the session source and destination relinquish 993 some control over message forwarding. However, datagram mode provides 994 robust forwarding, in the sense that the intermediate forwarding agents can 995 base their message forwarding decisions on the current state of their 996 portion of the internetwork. 998 Both of the Nimrod forwarding modes rely on the existence of underlying 1000 15 1001 paths to fill in route segments. A path may connect a source endpoint to 1002 one or more destination endpoints. Forwarding agents execute path 1003 management procedures to install path state in and remove path state from 1004 their forwarding databases. With these procedures, Nimrod provides support 1005 for management and use of unicast and multicast paths. We note, however, 1006 that multicast group management and multicast route construction are not 1007 part of this initial version of Nimrod. These and other multicast issues 1008 are treated in detail in [4]. For simplicity of discussion, we focus on 1009 unicast paths in the remainder of this section. 1011 3.5.1 Path Setup 1013 Paths may be set up from source to destination or from destination to 1014 source. Each path has an initiator and a target. We expect that most paths 1015 will be set up from the source endpoint to the destination endpoint. Hence, 1016 the initiator usually begins the path setup procedure on behalf of the 1017 source endpoint, and the target usually accepts or rejects a path on behalf 1018 of the destination endpoint. 1020 Nimrod paths are inherently multilevel as follows. We begin with a single 1021 path, p0, derived from the selected route between the source and destination 1022 endpoints for the traffic session. (The superscript indexes the level of 1023 the path, where the top level is 0.) This path comprises multiple 1024 contiguous paths, p11;: ::;p1n, one for each of the n segments of the route on 1025 which p0is based. (The subscript indexes the path for the corresponding 1026 route segment of the higher level path.) Each p1jitself comprises multiple 1027 contiguous paths corresponding to each of its segments, and so on. In 1028 general, for each pijcomposing pi-1k= pi, the initiator and target of pij 1029 maintain linkages to the path pi-1k(pi), which helps to guide forwarding 1030 along the successive segments of pi-1k(pi). 1032 Forwarding agents and endpoint representatives try to form paths by piecing 1033 together existing paths rather than by setting up new paths. This method 1034 provides the lowest-cost message forwarding in terms of the amount of route 1035 generation and forwarding state installation required. In a busy 1036 internetwork, there are likely to be many existing paths, and hence we 1037 expect this mechanism to be much less expensive than individually setting up 1038 and maintaining paths for each traffic session. 1040 We now describe how a new traffic session uses paths at multiple levels, 1041 distinguishing the actions in flow mode and datagram mode where appropriate. 1042 Whenever the endpoint representative receives a data transport request, it 1043 always checks whether there already exists a satisfactory path for the 1044 session. This is true whether the new session desires flow or datagram mode 1045 forwarding. If a satisfactory path exists, the endpoint representative 1046 links the session to the path and forwards session traffic along that path. 1047 If no such path exists, however, the endpoint representative attempts to 1048 obtain a feasible route for the session. Note that route generation might 1050 16 1051 not be required and that a feasible route might include only the source and 1052 destination locators. 1054 After obtaining a feasible route, the endpoint representative proceeds to 1055 determine where to install the necessary forwarding state. 1057 Flow mode:The endpoint representative becomes the initiator of a new path, 1058 p0, and generates a path setup message. 1060 If the route contains more than the source and destination locators, the 1061 endpoint representative then checks whether there already exists a 1062 satisfactory path for the session from itself to the next node in the route 1063 specification. Provided such a path, p11, exists, the endpoint 1064 representative proceeds as follows: 1066 Flow mode:The initiator of p11 (which is also the initiator of p0) links p0 1067 and p11in its forwarding database and sends p0's setup message to the 1068 target of p11. Upon reception of the setup message, the target of p11 1069 also links p0 and p11in its forwarding database. 1071 Datagram mode:The initiator of p11 sends the data message to the target of 1072 p11. 1074 If no satisfactory path, p11, yet exists between the first two nodes in the 1075 route specification, the endpoint representative attempts to form such a 1076 path by piecing together existing paths. The endpoint representative 1077 attempts to find an existing path whose destination locator is the longest 1078 match on the next node's locator and is within the context of the two nodes 1079 (i.e., the lowest node in the hierarchy that contains both nodes). If such 1080 a path, p21, exists, the endpoint representative proceeds as it did with p11. 1082 If the endpoint representative fails to find a satisfactory path to any of 1083 the second node's ancestral nodes contained within the context, then there 1084 are no ``direct'' paths to the second node. The endpoint representative 1085 then seeks a path up to the its node's enclosing node, as there are likely 1086 to be more existing paths between higher-level entities. To this end, the 1087 endpoint representative checks whether there already exists a satisfactory 1088 path whose target is an exit point of the its node's enclosing node. If 1089 such a path, p21, exists, the endpoint representative proceeds as it did 1091 with p11. Otherwise, the endpoint representative attempts to obtain a 1092 feasible route and set up a path, p21. If there are no short-cut paths from 1093 the its node's enclosing node to any of the second node's ancestral nodes in 1094 the context, the above procedure may need to be repeated for successively 1095 higher-level ancestors of the endpoint representative's node, up to but not 1096 including the context. If no short-cut paths exist at any of these levels, 1097 a route must be generated and a path set up, from the node below the context 1098 and containing the first node to the second node. 1100 17 1101 This iterative path formation procedure is performed by the target of each 1102 path thus selected, which then becomes the initiator for the path for the 1103 next segment, and so. Note that in the above description, the words 1104 ``endpoint representative'' should be replaced by ``forwarding agent'' when 1105 referring to the actions taken by intermediate agents along a path. The 1106 procedure terminates after attaining the last node in the route and the 1107 target endpoint representative in that node, possibly linking together paths 1108 at many different levels. 1110 In the presence of multilevel paths, each data message carries a nested 1111 sequence of path labels, in order to enable all forwarding agents involved 1112 in the paths to forward the message correctly. Intermediate forwarding 1113 agents update the path labels in the message, according to the linkages 1114 between paths stored in their forwarding databases. Upon receipt of a data 1115 message, the target of path pjifinds it is linked to path pj-1k=pj which in 1116 turn is linked to path pji+1and hence is the initiator of pji+1. This 1117 forwarding agent strips off the label for pjiand replaces it with the label 1118 for pji+1, before forwarding the message along that path. 1120 3.5.2 Path Acceptance 1122 Each setup message in flow mode and each data message in datagram mode 1123 contains the route specification and additional service requirements, such 1124 as resource reservation requests. A boundary forwarding agent or endpoint 1125 representative receiving a setup or datagram message determines message 1126 acceptability. Acceptability is in part based on the perceived consistency 1127 between the route specification and service requirements contained in the 1128 message and the service attributes of each node traversed. 1130 When a forwarding agent refuses a setup message, it informs the other 1131 forwarding agents on the path between and including itself and the 1132 initiator. At the target, once a setup message passes the service attribute 1133 consistency check, it must also pass an endpoint-specific consistency check. 1134 In particular, the target determines the perceived consistency between the 1135 route specification and service requirements contained in the message and 1136 the service requirements of the target endpoint. Each target that accepts a 1137 setup message informs the initiator. If there is an inconsistency with the 1138 target endpoint's service requirements, the target takes one of two actions, 1139 depending upon whether the target is the path's destination or source: 1141 1. If the target is at the destination endpoint, it returns to the 1142 initiator a message containing its endpoints' destination service 1143 requirements. The initiator is then responsible for obtaining a route 1144 and setting up a path that is consistent with both the source and 1145 destination service requirements. 1147 2. If the target is at the source endpoint, it returns to the initiator a 1149 18 1150 message indicating that it will generate its own route. The target is 1151 then responsible for obtaining a route and setting up a path that is 1152 consistent with the source service requirements and the destination 1153 service requirements contained in the setup message. 1155 Any forwarding agent or endpoint representative may tear down a path by 1156 removing the corresponding forwarding state from its forwarding database. 1157 Reasons for path teardown include: 1159 o Detection of a connectivity failure along a path. 1161 o A change in node service attributes or traffic service requirements 1162 such that the route on which the path is based is no longer feasible. 1164 o Path expiration if a path exceeds a maximum prescribed lifetime. 1166 o Path preemption in favor of another path. 1168 3.6 Control Message Integrity and Authentication 1170 Nimrod control messages (all messages except data messages are considered to 1171 be control messages) include several pieces of information which permit 1172 recipient agents to determine whether the message has been corrupted in some 1173 way. In addition to information on type and length of various sections of 1174 the message, each Nimrod control message contains its generation timestamp, 1175 expressed in seconds elapsed since 0 hours on 1 January 1900 (same format as 1176 the NTP timestamp [6]), as well as ``authentication'' information that 1177 simultaneously acts as a checksum and as source authentication. 1179 3.6.1 Timestamps 1181 Timestamps establish message recency and hence help recipients detect 1182 message replays. In order to detect whether a Nimrod control message is 1183 timely, the recipient agent compares its local time with the timestamp 1184 contained in the control message. If the timestamp is less recent than the 1185 local time by no more than ffi seconds or more recent than the local time by 1186 no more than ffl seconds, the message is considered to be timely. Otherwise, 1187 the message is considered to be out-of-date. Nimrod agents do not require 1188 fine-grained time synchronization in order to make their message recency 1189 determinations. Time synchonization on the order of minutes is all that is 1190 required. In fact, periodic manual adjusting of local clocks should be 1191 sufficient to maintain the necessary synchronization among agents. 1193 19 1194 3.6.2 Authentication 1196 This initial version of Nimrod does not contain any specification of 1197 security measures for Nimrod but rather place holders for such security 1198 measures to be introduced in a future version. Nevertheless, we do make 1199 recommendations for what these security measures might be. 1201 Most Nimrod control messages are generated by a single agent but distributed 1202 to many different agents, and most parts of these messages remain constant 1203 as the messages are passed among agents. To prevent communication problems 1204 caused by errors introduced into these messages which carrying 1205 routing-related information, each recipient agent should be able to 1206 determine with high confidence whether the message has indeed been generated 1207 by the stated source and whether the constant portions of the message have 1208 been modified since being generated by that source. 1210 We recommend that each Nimrod control message carry a public-key-based 1211 digital signature covering a reduced form of the constant portions of the 1212 message (e.g., apply the MD5 hashing function followed by the RSA signing 1213 function to the constant portions of the message). The authentication 1214 information may also include the public key to be used to verify the 1215 signature together with its certificate. While the RSA signing procedure is 1216 computationally intensive, signature verification is not. As long as 1217 control message generation at a particular agent is infrequent, that agent 1218 should be able to handle the load imposed by signing. Discovery messages 1219 are the only control messages generated frequently (i.e., inter-message 1220 period on the order of tens of seconds); an alternative mechanism may be 1221 required to protect these messages. 1223 The authentication information field in Nimrod control messages is 1224 represented as type, length, and value and hence is able to accommodate any 1225 integrity and security information that may be desired or required in the 1226 future. 1228 20 1229 4 Reliable Transaction Protocol 1231 Many Nimrod control messages reliable delivery. Rather than have each agent 1232 duplicate this reliability functionality, Nimrod includes a reliable 1233 transaction service, which provides its clients the ability to reliably 1234 communicate arbitrary size blocks of information between a client and a peer 1235 and to receive an arbitrary size reply in approximately one round-trip time. 1237 The reliable transaction service is built on Transaction-TCP (T/TCP) [10], 1238 [9]. T/TCP is a backwards-compatible extension of TCP, which is opti,mized 1239 for request/response interactions. In particular, T/TCP may bypass the 1240 normal three-way handshake required at TCP connection setup time. This 1241 bypass is accomplished by adding a ``connection count'' option in the TCP 1242 header, and by maintaining per-host connection history at both client and 1243 server. This information allows the server to correctly distinguish a new 1244 connection open (SYN, no ACK) from a duplicate or out-of-order open, without 1245 shaking hands with the client. Using T/TCP, the client can obtain a 1246 response to a request message in one round-trip-time to the server and back 1247 (plus the server's processing time). T/TCP uses the normal three-way close 1248 handshake; it does not impact transaction latency. 1250 4.1 Services Interface 1252 The reliable transaction service permits one or more transactions to be 1253 invoked at a peer. The service interface is: 1255 o Flags, misellaneous flags. 1257 o Source locator and EID of the transaction. 1259 o Destination locator and EID of the transaction. 1261 o Keying info, for authentication purposes. 1263 o Service requirements for the transactions. 1265 o Transaction, beginning with a protocol header (e.g., Query-Response or 1266 Update). 1268 Each transaction uses a separate TCP connection. We note that this may 1269 cause excessive overhead if the client(s) invoke many transactions within a 1270 short period of time, and is an issue to be examined more carefully in 1271 future versions of Nimrod. The beginning of each transaction is the 1272 transaction header, containing the following fields. The packet formats are 1273 illustrated and specified values given in section 9.4. 1275 o Length(32 bits) of the transaction, including this field. 1277 o Version(2 bits) of Nimrod update and query-response protocols. 1279 21 1280 o Protocol(2 bits) identifier. Whether Update, Query, Response, or 1281 Discovery message. 1283 o Operation(4 bits). Particular operation within the protocol. 1285 o Phase(8 bits). The Update protocol uses several phases for certain 1286 operations. This denotes the current phase. 1288 o Transaction ID(16 bits). To identify the transaction. 1290 o Timestamp(32 bits). Seconds since 1/1/1900, 00:00. 1292 The user may abort an initiated transaction at any time. Note that race 1293 conditions are possible as the aborted opertion may have actually been 1294 performed by the peer. There is no rollback facility provided by the 1295 reliable transaction service. 1297 22 1298 5 The Update Protocol 1300 The Update Protocol is used to update database contents (e.g., the map 1301 database). The peers in the Update Protocol are the Nimrod agents, 1302 currently including the forwarding agents, node representatives, route 1303 agents, and endpoint representatives. These agents participate in the 1304 distribution of the updated information in the required portion of the 1305 network. The implicit flooding constituting the protocol is carefully 1306 constrained by involving only a few agents per update. 1308 5.1 Service Interface 1310 The Update Protocol offers a distributed database update service in a manner 1311 that renders the exact locations of the database transparent to the user. 1312 The portion of the distributed database updated is dependent on the 1313 particular database and the operation as indicated by the user. The service 1314 interface includes the following: 1316 o Source. EID and optionally locator of the agent initating the update. 1318 o Destination. EID and optionally locator of a specific agent (e.g., 1319 endpoint representative whose locator has changed). May be left 1320 unspecified. 1322 o Operation. Indicates what kind of update (i.e., for what database) it 1323 is. Current values are shown in section 9. 1325 o Keying info for authentication purposes. 1327 o Service requirements if any. Will be ``best effort'' if unspecified. 1329 o Patience. A time interval within which the user wishes to hear about 1330 the success of the update. 1332 The Update Protocol provides hop-by-hop reliablity, but no effort is made to 1333 ensure end-to-end reliablity. An agent that has initiated an update cannot 1334 be certain that the message has been delivered to all intended agents, or 1335 that all intended database portions have been updated. We believe that the 1336 resource and complexity overhead demanded by an end-to-end reliablity 1337 mechanism is not justified by the importance for database updates (note that 1338 Nimrod does not require absolute database consistency (see section 2.3.1)). 1339 The user may abort a previously initiated update, for instance, because an 1340 update is superseded by more recent information. The protocol will discard 1341 the update if it has not already been sent out. However, no rollback 1342 facility is provided. 1344 23 1345 5.2 Protocol Operation 1347 The Update Protocol consists of an Update Message that is generated by the 1348 agent wishing to make an update to a particular database. (The Update 1349 Message consists of a variable length database specific portion, described 1350 in section 5.3, prepended by a common update protocol header, described in 1351 section 5.2.1 below, prepended by the transaction header, described in 1352 section 4.) The database may be held redundantly or cooperatively by 1353 multiple agents in a node, and an update may involve several nodes in the 1354 hierarchy. Thus, the update protocol involves several cooperating 1355 communicating agents. 1357 We classify the participating (peer) agents into two for ease of 1358 description: the originating agent and the transit agents. The originating 1359 agent forwards the message to one or more agents which further forward it to 1360 other agents and so on, until all the necessary database locations have been 1361 updated. Once an originating or transit agent has successfully forwarded a 1362 message, it does not retain any state corresponding to the message. The 1363 originating and transit agent operations are described in more detail later 1364 in this section. 1366 The Update Message uses the reliable transaction service (see section 4). 1367 Since no effort is made to provide end-to-end reliability, no 1368 acknowledgements (positive or negative) are part of the Update Protocol. 1369 Exceptions are handled by making a log entry into a file. 1371 The actions performed by an agent upon receipt of an Update Message is a 1372 function of the receiving agent type and of the user supplied Phase of the 1373 message, which are contained in the transaction header. Examples of 1374 operation types are map update, locator update, etc. The actions include 1375 the decision of whether to cache the message or not, and whether to forward 1376 the message further, and if so to whom. We specify such actions 1377 corresponding to each agent type (columns) and operation type (rows) pair 1378 using an Update Message Action Table (UMAT) shown in section 5.2.4. 1380 We note that the update protocol is an application level protocol between a 1381 set of peer agents indicated in the destination field of the Nimrod header 1382 (or the IP header). In transit between these peer agents, the Update 1383 Message map may be forwarded through other intermediate agents, which are 1384 not peers in the protocol. For instance, an update message from agent A1to 1385 agent A2may go through (forwarding) agents a1, a2, ..., ak before reaching 1386 A2. However, such an agent ai is not a peer, and does not act upon the 1387 message using the UMAT. 1389 5.2.1 Update Header 1391 Each item in the common update header is explained below. The packet format 1392 of the header is illustrated in section 9.5. 1394 24 1395 o Originating agent type(8 bits). The type of agent originating the 1396 update. Current agent types include Forwarding Agent, Endpoint 1397 Representative, Node Representative, and Route Agent. 1399 o Destination agents type(8 bits). The type(s) of agent(s) for whom the 1400 update is intended. For multiple agents, the field contains a 1401 bitwise-OR of respective agent types. 1403 o Flags(16 bits). Miscellaneous operation dependent flags. 1405 o Database Type(8 bits). The type of the database that is being updated. 1406 At most one kind of database can be updated with an update message. 1408 o Database timestamp(24 bits). Denotes the origination time of the 1409 message with respect to the originating agent EID. That is, the 1410 timestamp and the EID together identify the packet uniquely, modulo 1411 wraparounds. The timestamp is the lower 24 bits of the the current 1412 time in seconds, beginning 0:00 1 January 1900. 1414 o Destination NID (8 bytes). The update is restricted to this node. 1415 Refer to section 11.5 for NID format. 1417 o Originating EID (8 bytes). EID of the agent that issued the update. 1418 Refer to section 11.3 for EID format. 1420 o Originating Locator. Locator of the agent that issued the update. 1421 Refer to section 11.2 for locator format. 1423 o Authenticator. Authentication field. Contains authentication 1424 information for the agent originating the update. 1426 5.2.2 Originating Agent Operations 1428 An originating agent issuing the update constructs Update Message 1429 database-specific information (update) and fills in the transaction and 1430 common update protocol headers, including the timestamp that is incremented 1431 for every update originating from the agent. Note that the user-specified 1432 Operation is placed in the ``operation'' field of the transaction header. 1433 The UMAT is then consulted to obtain the actions, which typically involve 1434 sending the Update Message to one or more next-hop agents. This could be in 1435 terms of specific agents, all agents of a given type, or any agent of a 1436 given type. 1438 Using the destination agent's EID, locator, etc., the Update Message is 1439 enclosed within the appropriate headers (see section 9) and sent. Note that 1440 the protocol calls for one-to-one individual transmissions (no multicast) to 1441 the next-hop peer agents. If it is required that the message be sent to any 1442 one agent of a given type, each agent of that type is tried until 1443 successful. An update failure occurs if a specified agent is unreachable or 1445 25 1446 if (in case of ``any agent of given type'') no agent of a given type is 1447 reachable. Update failures should be logged for possible network management 1448 action. 1450 5.2.3 Transit Agent Operations 1452 A transit agent receives an Update Message as ``TCP data''. It then 1453 performs checks on the message to determine whether the message is a valid 1454 one. This may include checking the timestamp in the update header to ensure 1455 that the Update Message is not a duplicate, and verifying the authenticator 1456 in the update header. If any of the checks fail, the error should be logged 1457 for possible network management action. 1459 If the checks pass, then the UMAT is consulted for actions using the Phase 1460 field in the transaction header. This may involve caching the information 1461 (i.e., updating the relevant database using the message contents) and/or 1462 sending the message with a changed Phase, to one or more next-hop agents. 1463 This could be in terms of specific agents, all agents of a given type, or 1464 any agent of a given type. 1466 Using the destination agent's EID, locator, etc., the Update Message is sent 1467 as TCP data. Note that the protocol calls for one-to-one individual 1468 transmissions (no multicast) to the next-hop peer agents. If it is required 1469 that the message be sent to any one agent of a given type, each agent of 1470 that type is tried until successful. An update failure occurs if a 1471 specified agent is unreachable or if (in case of ``any agent of given 1472 type'') no agent of a given type is reachable. Update failures should be 1473 logged for possible network management action. 1475 5.2.4 The Update Message Action Table (UMAT) 1477 The UMAT represents Update Message forwarding instructions based on agent 1478 and phase, and depends on what functionality is mapped into the protocol and 1479 how the mapping is done. The Update Protocol is used for map updates 1480 (section 3.1), locator updates(section 3.3), and adjacency updates 1481 (section 3.4). Our use of the UMAT is mainly to provide a succinct and 1482 flexible protocol specification. While it is clearly not necessary that an 1483 implementation use an UMAT-equivalent, it is strongly recommended from 1484 experience since it provides flexibility by making it easy to change the 1485 functionality and the mapping - one simply needs to add additional message 1486 types and/or alter the entries in the table. The Update Protocol is 1487 typically used by Nimrod agents or other ``users'' in order to initiate 1488 updates. We use the term client to denote such users. 1490 For each of the four agent types (Forwarding Agent, Endpoint Representative, 1491 Node Representative, and Route Agent), we give below the actions upon 1492 receipt of an Update Message of each phase. The phases form the rows, and 1494 26 1495 _____________________________________________________________________________ 1496 ||________________________||_____F_________|_______N_________|__R___|__E___||__ 1497 ||_CLIENT-MAP-UPD_________||_______________|send(1,_,F-P)(1)_|______|______||_ 1498 ||_phase-map-forw-par_(1)_||send(2,P,F-C)___|________________|______|______||_ 1500 ||_phase-map-distrib_(2)_s||end(3,_,{R*,N*})_|_______________|______|______||_ 1501 ||_phase-map-notify_(3)___||_______________|_____cache_______|cache_|______||__ 1502 ||_CLIENT-LOC-UPD_________||_______________|_send(4,_,*)(2)__|______|______||_ 1504 || phase-loc-notify (4) || cache | cache |cache |cache || 1505 ||________________________||send(5,C,F-P)___|________________|______|______||_ 1506 ||_phase-loc-child_(5)____||_send(4,*)_____|_________________|______|______||_ 1507 ||_CLIENT-ADJ-UPD_________||_______________|__send(6,_,N*)___|______|______||_ 1508 ||_phase-adj-notify_(6)___||_______________|_____cache_______|______|______||__ 1510 Table 1: Update Message Action Table for each agent type (columns) upon 1511 receipt of message with each Operation Type (rows). 1512 . 1514 the value of each phase is indicated within paranthesis. Some operations 1515 are client requests, and these are denoted in upper case. Note that to a 1516 given agent, only the column corresponding to its agent type is of interest, 1517 and thus every agent may be thought of as implementing a column of the UMAT. 1519 The actions primarily involve the functions described, along with their 1520 parameter legends, below. We assume the existence of forwarding 1521 functionality required to realize these functions. 1523 1. send(Phase, [Node] , [AgentType][*]). This sends an Update Message 1524 with phase field denoted by Phase to an agent of AgentType in Node. 1525 The AgentType is one of N, F, R, E, F-P (boundary to/from parent), or 1526 F-C (boundary to/from child). A suffix `*' denotes all agents of the 1527 type. If AgentType is omitted, it means all agents in the specified 1528 node. For the Node field, P, C and S denote a parent, child, and 1529 sibling nodes respectively. If it is absent, it means the current 1530 node. 1532 2. cache. Update the relevant data structures containing the database. 1534 In the postscript version, the reader may refer to Figures 1 through 4 in 1535 Appendix 1 for assistance in understanding the protocol. 1537 5.3 Database Specific Updates 1539 As mentioned earlier, the Update messages contain a database specific 1540 information, depending on the operation being performed. In this section, 1541 we describe the database specific contents and their semantics for each 1542 operation. This information is referred to as ``additional information'' in 1543 the following. The packet formats for the additional fields are illustrated 1544 in section 9.6. 1546 27 1547 5.3.1 Adjacency Updates 1549 After an adjacency has been formed, the node representatives of the nodes 1550 constituting the adjacency have to be informed, so that they may modify 1551 their maps accordingly. Note that there are two adjacency updates sent for 1552 each uni-directional adjacency: one from the node representative that sent 1553 the Adjacency Request query and one from the node representative that sent 1554 the Adjacency Request response. The additional information in the adjacency 1555 updates is: 1557 o Flags, indicating whether the adjacency is to a parent, child, or 1558 sibling. 1560 o Neighbor node NID and locator. 1562 o Locator of boundary forwarding agent that implements the adjacency. 1564 5.3.2 Locator Updates 1566 A node representative that changes a locator acquired by an endpoint 1567 representative must notify that endpoint representative if the locator 1568 changes or becomes unusable, e.g., the association between the node and 1569 endpoint is being terminated. The additional information contained in such 1570 an update is: 1572 o Flags, indicating nature of change (e.g., depreciate use of old 1573 locator, terminate use of old locator). 1575 o Credentials of the representative originating update. 1577 o Old locator that is being changed/terminated. 1579 o EID and locator (optional) of the supplier of the old locator, if 1580 different from the originator. Either both EID and locator are present 1581 or both are absent. 1583 o New locator (optional) or reassigned locator. 1585 o Expiration (optional, present only if new locator is present) time for 1586 the new locator. 1588 The representative of a node that acquires a new locator must update all of 1589 its children so that they can change their locator. Also, a node 1590 representative that changes a locator acquired by a component node must 1591 notify that component node if the locator changes or becomes unusable, e.g., 1592 the parent-child relationship is being terminated. The additional 1593 information contained in such an update is: 1595 28 1596 o Flags, indicating nature of change (e.g., depreciate use of old 1597 locator, terminate use of old locator). 1599 o Credentials of the representative originating update. 1601 o Old locator that is being changed/terminated. 1603 o EID and locator (optional) of the supplier of the old locator, if 1604 different from the originator. Either both EID and locator are present 1605 or both are absent. 1607 o New locator (optional) or reassigned locator. 1609 o Expiration (optional, present only if new locator is present) time for 1610 the new locator. 1612 5.3.3 Map Updates 1614 Whenever a node's topology or offered services change, it must generate a 1615 new set of maps. The new maps must be propagated to the node 1616 representatives and route agents in the node's parent. The maps are also 1617 sent to any agents that have explicitly requested to be notified of updates, 1618 if an implementation supports the subscription functionality. 1620 o Flags. Qualifies the map (e.g., one or more component nodes not in 1621 map, map is of a partitioned node). 1623 o Sequence number (24 bits) of the transaction that requested explicit 1624 (automatic) updates. 1626 o Map. Abstract map of node. 1628 o Maps (optional) to specific agents as requested. 1630 29 1631 6 The Query-Response Protocol 1633 The Query-Response (Q-R) Protocol is used to obtain database 1634 information(e.g., portions of the map database) in an efficient manner. The 1635 Q-R Protocol consists of two messages: the Query Message and the Response 1636 Message. (The Query and Response Messages consist of a variable length 1637 database specific portion, described in section 6.4, prepended by a common 1638 Query/Response Protocol header, described in section 6.3 below, prepended by 1639 the transaction header, described in section 4.) The Query Message is 1640 generated by the agent wishing to make a query, contains the nature of the 1641 information required, and is sent directly to a destination agent that the 1642 originating agent believes is in possession of the information. The 1643 destination agent obtains the requisite information and sends the Response 1644 Message back to the originating agent. Note that the destination agent may 1645 obtain the information from its own database, or may in turn send a Query to 1646 another agent in order to obtain this information. 1648 6.1 Service Interface 1650 The Q-R protocol offers a reliable query-response service in one round trip 1651 time. It uses the reliable transaction service. In fact, excepting headers 1652 and minor interface differences, the Q-R protocol adds very little to the 1653 service provided by the transaction service. 1655 o Originator. EID (and optionally locator) of the agent initiating the 1656 query. 1658 o Destination. EID (and optionally locator) of the destination agent 1659 being queried. 1661 o Operation. Indicates what kind of query (i.e., for what database) it 1662 is. Current values are shown in section 9. 1664 o Keying info for authentication purposes. 1666 o Service requirements if any. Will be ``best effort'' if unspecified. 1668 o Patience. A time interval that the user wishes to wait for the 1669 response to the query. If there is no response within this time, the 1670 user expects to be informed. 1672 6.2 Protocol Operation 1674 Unlike the update protocol, the Q-R Protocol involves only two agents - the 1675 originator and destination. The Query Message header (given below) contains 1676 the EID and locator of the querying agent. These fields are used by the 1677 destination agent for the destination of the response. The destination 1678 agent verifies the authentication information to ensure that the query can 1679 indeed be honored. Should the authentication check fail or if the 1681 30 1682 destination agent is unable to supply the required information, it still 1683 sends a response back with the appropriate error code. 1685 If the originator does not get a response within a certain time t, it is 1686 informed of a query failure. The value of t is given to the protocol by the 1687 application (e.g., map request). The application also has the option of 1688 requesting an abort of the query - in this case, the state is reset and the 1689 response is ignored. As in the case of the Update Protocol, exceptions are 1690 handled by making a log entry into a file for possible network management 1691 action. 1693 6.3 Query/Response Header 1695 Each item in the common Query/Response header is given below. The packet 1696 format of the header is illustrated in section 9.5. 1698 o Originating agent type (8 bits). The type of agent originating the 1699 query. Agent types include Forwarding Agent, Endpoint Representative, 1700 Node Representative, and Route Agent. 1702 o Destination agent type (8 bits). The type of agent for whom the query 1703 is intended. 1705 o Flags (16 bits). Miscellaneous operation dependent flags. 1707 o Database Type (8 bits). The type of the database to which the 1708 information being queried pertains. At most one kind of database can 1709 be queried with a query message. Database types are defined in 1710 section 9.5. 1712 o Count (8 bits). Operation dependent. 1714 o Opcode (16 bits) In a query, operation specific or database specific 1715 information. In a response, zero if query is being responded to 1716 successfully, otherwise an error code indicating the reason for 1717 failure. 1719 o Originating EID. In a query, the EID of the agent that issued the 1720 query. Used to obtain the destination for the response. In a 1721 response, the EID of the agent issuing the response. 1723 o Originating Locator. In a query, the locator of the agent that issued 1724 the query. Used to obtain the destination for the response. In a 1725 response, the locator of the agent issuing the response. 1727 o Authenticator. Authentication field contains the information used to 1728 authenticate the query (in Query) or the response (in Reply). 1730 31 1731 6.4 Database Specific Request/Release 1733 As mentioned earlier, the Query and Response messages contain a database 1734 specific information, depending on the operation being performed. In this 1735 section, we describe the database specific contents and their semantics for 1736 each operation. This information is referred to as ``additional 1737 information'' in the following. The packet formats for all of the packets 1738 in this section are illustrated in section 9.7. 1740 6.4.1 Adjacency Formation 1742 The designated representative of a node forms adjacencies with a neighboring 1743 node by sending an adjacency request message to one of the neighboring 1744 node's representatives. Any resulting adjacency is one-way, from the node 1745 requesting the adjacency to that which granted it. The additional 1746 information in an adjacency request Query Message is: 1748 o Locator of the node initiating the adjacency. 1750 o NID of the node initiating the adjacency. 1752 o Circuit ID. Physical circuit identifier of the link to form the 1753 adjacency, as known in the originating node. 1755 o Neighbor NID of the intended neighbor node in the adjacency. 1757 The additional information in an adjacency request Response Message is: 1759 o Credentials of the granting node. 1761 o Locator of the granting node. 1763 o NID of the granting node. 1765 o Circuit ID. Physical circuit identifier of the link to form the 1766 adjacency, as known in the granting node. 1768 6.4.2 Adjacency Release 1770 If a node representative receives a positive reply to an adjacency request 1771 message, the message may contain information that indicates that the 1772 adjacency is not appropriate. An adjacency is terminated by sending an 1773 adjacency release request to the node representative which granted the 1774 adjacency. Node mobility and management policy changes may also induce a 1775 node to release adjacencies. The additional information in an adjacency 1776 release Query Message is: 1778 32 1779 o Opcode giving a reason for terminating the adjacency (e.g., policy, 1780 lack of traffic, movement, etc.). 1782 o Locator of the requesting node. 1784 o NID of the requesting node. 1786 o Circuit ID of the link forming the adjacency, as known in the 1787 requesting node. 1789 o Neighbor NID of the granting neighbor node. 1791 o Circuit ID of the link forming the adjacency, as known in the granting 1792 neighbor. 1794 The adjacency release response contains indication of success or failure 1795 (reason code if latter). It does not contain any other message-specific 1796 information. 1798 6.4.3 Adjacency Activation 1800 When a node representative has formed an adjacency with a neighbor node, the 1801 boundary forwarding agent connected to the neighbor must be informed that 1802 Nimrod data traffic may be passed to the neighbor. Note that there are two 1803 instances of the Adjacency Activation associated with each uni-directional 1804 adjacency, one from the node representative that sent the Adjacency Request 1805 query to its boundary forwarding agent indicating outgoing connectivity, and 1806 one from the node representative that sent the Adjacency Request reply to 1807 its boundary forwarding agent indicating incoming connectivity. The 1808 additional information in an Adjacency activation request is: 1810 o Flags, indicating whether the adjacency to be activated is to a parent, 1811 child, or sibling. 1813 o Locator of requesting node. 1815 o NID of requesting node. 1817 o Circuit ID of the link forming the adjacency as known in the requesting 1818 node. 1820 o Neighbor NID of granting node. 1822 o Circuit ID of the link forming the adjacency as known in the granting 1823 node. 1825 33 1826 6.4.4 Locator Acquisition 1828 There are two forms of locator acquisition: one for a component node 1829 requesting its locator from a node representative of the parent node, and 1830 one for endpoint representatives requesting a locator for an endpoint from a 1831 node representative of the node. The two forms are distinguished by the 1832 originating agent type field in the common Query/Response header. The 1833 additional information in a locator acquisition Query Message, from a 1834 component node is: 1836 o Old locator (optional), previously assigned locator, requestor wants it 1837 to be reassigned. 1839 o EID and locator (optional) of the node representative that previously 1840 assigned the locator. Either both EID and locator are present or both 1841 are absent. 1843 o Parent NID of the node to provide the locator. 1845 o Child NID of the node requesting the locator. 1847 The additional information in a locator acquisition Query Message, from an 1848 endpoint representative is: 1850 o Old locator (optional). Previously assigned locator; requestor wants 1851 it to be reassigned. 1853 o EID and locator (optional), of the node representative that previously 1854 assigned the locator. Either both EID and locator are present or both 1855 are absent. 1857 o Provider NID of the node to provide the locator. 1859 o Name of the endpoint requesting a locator. 1861 o EID of the endpoint requesting a locator. 1863 The locator acquisition Response Message, for a request from a component 1864 node or an endpoint contains the following additional information: 1866 o Flags indicating nature of error if any, 0 if okay (e.g., might 1867 indicate that another agent may be able to provide it (see below)). 1869 o New/Reassigned Locator (optional, present when successful) that the 1870 requestor and its descendants should use as prefix. 1872 o Expiration time of the locator supplied. 1874 o EID (optional) of node representative that might be able to (re)assign 1875 the locator. 1877 34 1878 o Locator (optional) of node representative that might (re)assign the 1879 locator. 1881 o NID (optional) of node containing representative that might (re)assign 1882 locator. 1884 6.4.5 Locator Release 1886 The locator release operation is used by a component node or endpoint 1887 representative that wishes to release a locator, typically due to 1888 mobility/relocation of a network or endpoint. The additional information in 1889 a locator release Query Message is: 1891 o Opcode indicating reason for release. 1893 o Flags indicates if a different agent should be contacted (see below). 1895 o Old locator to be released. 1897 o Issuing NR EID, that issued the locator that is being released. 1899 o Issuing NR locator, that issued the locator that is being released. 1901 o Different NR EID (optional, only if flag is set) that might release the 1902 locator. 1904 o Different NR locator (optional, only if flag is set) that might release 1905 the locator. 1907 6.4.6 Map Acquisition 1909 Route agents request maps from node representatives. Since the requesting 1910 route agent is both acting on behalf of an endpoint, either through the 1911 endpoint representative or a forwarding agent, and possibly on behalf of 1912 other route agents that delegated the original route request, there are 1913 usually two or more sets of credentials associated with a map request. 1914 These credentials are used by the node representative's filter module, which 1915 is tasked with enforcing any distribution restrictions on the maps it 1916 dispenses. The additional information in a map Query Message is: 1918 o Flags qualifying the maps requested. Values allow to indicate: 1919 authoritative response required, abbreviated map required, complete map 1920 required, basic map required, need automatic map updates. 1922 o Locator of the node whose map is desired. 1924 35 1925 o Child elements (optional, if flag does not indicate complete). The 1926 locators of children whose map is desired. 1928 o Credentials of requesting node. 1930 The map request Response Message contains the following additional 1931 information: 1933 o Flags qualifiying map supplied. Values allow to indicate: partitioned 1934 node, map is of partitioned node, access denied/not available, 1935 automatic updates not supported 1937 o Requested Map. 1939 o Child Maps (optional). Maps of children nodes as requested (partial or 1940 complete). 1942 o Agents (e.g., in other partitions) that may be able to answer query. 1944 Note that the reply for a basic map may contain several maps, one for the 1945 requested node (map) and an abstract map for each of the child component 1946 nodes (child maps). The signature of the basic map covers the basic map and 1947 each of the maps of the child component nodes. 1949 6.4.7 Map Termination Request 1951 An agent that has explicitly requested to be notified of map updates may 1952 choose to terminate that subscription request. The map termination Query 1953 Message contains the following additional information: 1955 o Transaction number (16 bits) of the map request that requested 1956 automatic updates. 1958 The map termination Response Message contains the following additional 1959 information: 1961 o Flags. Allow to indicate: Automatic updates not supported, try 1962 alternate agent. 1964 o Opcode. Zero if ok, error code (e.g., no record of automatic update 1965 request) otherwise. 1967 o Agent (optional) that might have the automatic update request. 1969 36 1970 6.4.8 Path Information Request 1972 Route agents that are generating multicast routes may require access to 1973 existing path information for a multicast group so that more optimal routes 1974 may be generated. The path information is distributed among the forwarding 1975 agents supporting the multicast group. Route agents use path database 1976 queries to obtain the necessary information. The additional information in 1977 a path database Query Message is: 1979 o Flags. Which info to return. 1981 o Path Labels about which info is desired. 1983 The additional information in path database Response Message is: 1985 o Opcode indicating error code or zero. 1987 o Path entries. List of path entries requested. 1989 6.4.9 Route Generation Request/Reply 1991 Route agents generate routes on behalf of an endpoint in response to 1992 requests received from endpoint representatives and forwarding agents. 1993 Requests from forwarding agents will contain the credentials of the 1994 forwarding agent in addition to those provided by the endpoint 1995 representative. These credentials, along with those of the route agent (and 1996 any other route agents that delegated the request) are passed to any node 1997 representatives when requesting the node's map(s). The additional 1998 information in a Route Generation Query Message is: 2000 o Misc. Flags qualifying the nature of route required. 2002 o Count, number of feasible routes required. 2004 o Sources. Source locators for the route. 2006 o Destinations. Destination locators for the route. 2008 o Services required by the initiating endpoint. 2010 o Services required by the target endpoint. 2012 The route generation Response Message contains the following additional 2013 information: 2015 o Count. Number of feasible routes returned. 2017 37 2018 o Routes (optional, only if Count is non-zero). A list of routes from 2019 source(s) to destination(s) meeting the requirements. 2021 38 2022 7 Path Management Protocol 2024 Nimrod endpoint representatives and forwarding agents are responsible for 2025 establishing, in hosts and routers, state information necessary for 2026 forwarding Nimrod data messages. These agents are also responsible for 2027 forwarding Nimrod data messages according to this state information and the 2028 forwarding directives carried along in the messages. For a particular 2029 traffic session, the forwarding state information installed and maintained 2030 by endpoint representatives and forwarding agents is derived from the routes 2031 selected for the session. The forwarding state corresponding to a 2032 particular session and route is called a path. Multiple traffic sessions 2033 may use the same path, and multiple paths may be established based on the 2034 same route. A path may connect one or more source endpoints and one or more 2035 destination endpoints. In this initial version of Nimrod, each multicast 2036 path is either a source tree or a sink tree. (We note that this version of 2037 Nimrod includes procedures for installing and removing forwarding state for 2038 multicast trees and for forwarding session traffic along such trees. It, 2039 however, does not include procedures for multicast route construction and 2040 group management. For more information on these and other multicast issues 2041 as they relate to Nimrod, see [4].) 2043 Endpoint representatives and forwarding agents use the path management 2044 protocol to install and remove state information from their forwarding 2045 databases. Each endpoint representative and forwarding agent maintains 2046 state information for those paths that originate, terminate, or pass through 2047 it. Paths may be set up from source to destination or from destination to 2048 source. Each path has an initiator and a target. We expect that, in most 2049 cases, paths will be set up from the representative of the source endpoint 2050 to the representative of the destination endpoint. Hence, the initiator 2051 usually begins the path setup procedure on behalf of the source endpoint, 2052 and the target usually accepts or rejects a path on behalf of the 2053 destination endpoint. Forwarding state is established such that path 2054 management messages may be forwarded in both directions along the path; data 2055 messages always flow from source to destination. 2057 Paths are identified by path labels, which are unique along the path but not 2058 necessarily globally unique throughout the internetwork. Multiple 2059 non-intersecting paths may carry the same path label. By eliminating the 2060 requirement for global uniqueness of path labels, we can allow paths labels 2061 to be relatively short (24 bits), thus reducing the cost of carrying them in 2062 data messages and the cost of accessing information in forwarding databases 2063 indexed by them. The labels for each direction of a path are distinguished 2064 by a bit that indicates whether the message is flowing from from source to 2065 destination or from destination to source. 2067 Endpoint representatives and forwarding agents try to form a path for a new 2068 session by piecing together existing paths, rather than by setting up 2069 entirely new paths, provided the existing paths meet the new session's 2070 service requirements and permit its traffic to flow over them. This method 2071 of path construction incurs the least cost, in terms of the amount of route 2072 generation and forwarding state installation required per session. In a 2074 39 2075 busy internetwork, there are likely to be many existing paths. Moreover, we 2076 expect that most traffic sessions will not require specific service 2077 guarantees and most networks will not refuse to carry this ``best effort'' 2078 traffic. Therefore, we expect this method of path constructruction to be 2079 much less expensive than individually setting up and maintaining distinct 2080 paths for every traffic session. 2082 Most Nimrod paths are likely to be composed of paths which in turn are 2083 composed of lower-level paths, and so on. A Nimrod flow-mode data message 2084 (refer to section 3.5 for a description of flow mode and datagram mode 2085 message transmission) travelling over one of these multilevel, multi-segment 2086 paths must carry the path labels of all component paths it is currently 2087 traversing. These path labels are stacked in the data message and 2088 manipulated, i.e., pushed and popped, by the agents handling the message. 2089 Note, however, that an endpoint representative or forwarding agent uses only 2090 one of these path labels at a time in making a forwarding decision for the 2091 message. 2093 7.1 Protocol Messages 2095 The path management protocol uses five types of messages: setup, accept, 2096 teardown, status, and ack. Message contents are described below, but 2097 explicit formats are depicted in section 9. Each path management message is 2098 covered by the same basic types of integrity and authentication checks as 2099 other Nimrod control messages, including checks on message length, timestamp 2100 validity, content corruption, and source authentication. (Refer to 2101 section 3 for more information on Nimrod control message integrity and 2102 authentication.) 2104 All path management messages travel along the path to which they refer. 2105 Endpoint representatives and forwarding agents respond to the receipt of a 2106 path management message in different ways, depending upon the type of agent 2107 and the type of message. Path management protocol messages may be used not 2108 only to set up and teardown a path, but also to collect and report 2109 performance monitoring information for a path (e.g., path delay and 2110 throughput). Path monitoring operates in two modes: collection and report. 2111 Hence, monitored information for a path may appear in a message as 2112 information being collected or reported. 2114 7.1.1 Setup 2116 A setup message is generated by the initiator and travels along the path 2117 toward the target. It is used to establish forwarding state in endpoint 2118 representatives and forwarding agents. In this initial version of Nimrod, 2119 all endpoint representatives and forwarding agents retain the setup message 2120 for each active path that traverses them. This copy is used for detection 2121 of duplicate setup messages and for selecting alternate lower-level paths if 2122 the one initially chosen fails. Each setup message contains: 2124 40 2125 1. The label of the path to be established. 2127 2. The time at which the setup message was originally generated. 2129 3. Path indications: 2131 (a) Source-initiated or destination-initiated. 2133 (b) Unicast or multicast. 2135 (c) Available for shared use by multiple sessions or dedicated to a 2136 single session. 2138 4. Requested services for the session, indicated as either requirements or 2139 preferences and expressed as type, length, and value, from the 2140 perspective of the initiator. These may include but are not limited 2141 to: 2143 o delay; 2145 o variation in delay; 2147 o throughput; 2149 o variation in throughput; 2151 o bit error rate; 2153 o packet error/loss rate; 2155 o monetary cost (per byte, per packet, or per unit time); 2157 o whether packet order must be preserved. 2159 They may also include information about the session itself, such as its 2160 expected lifetime, the type of organization to which the originator 2161 belongs (e.g., academic, government, commercial), and the 2162 characterization of session traffic (e.g., in terms of average and peak 2163 rates and burst durations). As the work of the Integrated Services 2164 working group progresses, we plan to integrate these service 2165 specifications into future versions of Nimrod. 2167 5. The route, in terms of the locators of the nodes through which it must 2168 pass and, for each of these nodes, the label of the relevant 2169 connectivity specification to invoke across the node. 2171 6. The EIDs of the source and destination endpoints and their 2172 representatives. 2174 (a) Unicast path setup. The EID information for the initiator is 2175 included to enable the target to establish a path in the reverse 2177 41 2178 direction, if desired. It is also useful for network management. 2179 The type of the target agent determines what EID information is 2180 included for the target in the setup message. 2182 i. The target is the representative of one of the session's 2183 endpoints. Hence, EID information about this specific target 2184 must be included in the setup message, in order for the path to 2185 connect to the intended endpoint. 2187 ii. The target is any boundary forwarding agent for the last node on 2188 the route. Hence, there is no specific target and thus EID 2189 information related to the target may be left unspecified in the 2190 setup message. Such a situation is likely to arise when 2191 constructing a higher-level path intended to carry traffic for 2192 multiple sessions. 2194 (b) Multicast path setup. Although source and destination EID 2195 information is not strictly necessary in this case, it is included 2196 for network management reasons. Note that the multicast path is 2197 either a source tree or a sink tree. Hence, EID information is 2198 included for either the source or the destination but not for both. 2200 7. Collection-mode monitored information expressed as type, length, and 2201 value. This information can be used to determine the actual services 2202 available over the path. The initiator determines whether to collect 2203 this information during path setup. 2205 8. Integrity and authentication information covering all but 2206 collection-mode monitored information. 2208 7.1.2 Accept 2210 An accept message is generated by the target and travels along the path 2211 toward the initiator. It is used to indicate to the initiator that the path 2212 has been successfully established. Each accept message contains: 2214 1. The label of the accepted path. 2216 2. The EID of the agent that generated the accept message. 2218 3. The time at which the accept message was generated. 2220 4. Report-mode monitored information, expressed as type, length, and 2221 value. If the setup message collected monitored information, the 2222 accept message reports this information as the services available over 2223 the path. 2225 5. Integrity and authentication information covering all of the above. 2227 42 2228 Provided the initiator is the source, it may send data over the path before 2229 it receives an accept message from the target. Circumstances under which an 2230 initiator may wish to wait for an accept message before sending data on a 2231 path include the following example. If the source pays for all data 2232 messages sent, whether or not they are successfully received at the 2233 destination, it may want to wait to make sure that the path is successfully 2234 established before sending data to the destination. In this case, the 2235 source should be prepared to buffer data received from the host until the 2236 accept message is received. An initiating source determines whether to wait 2237 for an accept message before transmitting data, based upon the session's 2238 requested services. 2240 7.1.3 Teardown 2242 A teardown message is generated by any endpoint representative or forwarding 2243 agent on the path. It usually travels outwards, in both directions, towards 2244 the initiator and the target. In some cases (e.g., incomplete path setup or 2245 teardown generation by initiator or target), the teardown message may travel 2246 in only one direction. Teardown messages are used to remove forwarding 2247 state in endpoint representatives and forwarding agents. Each teardown 2248 message contains: 2250 1. The label of the path to be torn down. 2252 2. The EID of the agent that generated the teardown message. 2254 3. The time at which the teardown message was generated. 2256 4. The reason for the teardown, expressed as type, length, and value. A 2257 teardown message may be generated in response to any of the following 2258 events: 2260 Type 1: A path timeout. Each path has a specified maximum lifetime, in 2261 order to ensure that forwarding state is eventually removed, no 2262 matter how a path might fail. The agent detecting the path timeout 2263 generates two teardown messages, sending one toward the initiator 2264 and one toward the target. 2265 Type 2: Setup message is out-of-date. A setup message is out-of-date 2266 if the absolute value of the difference between its timestamp and 2267 the local time kept by the recipient agent varies by more than a 2268 specified maximum value. The agent receiving the out-of-date setup 2269 message generates a teardown message and sends it toward the 2270 initiator. 2272 Type 3: Route specification carried in the setup message is 2273 inconsistent with the node. 2274 Subtype 1: Recipient agent's node does not appear in the route 2275 specification. 2277 43 2278 Subtype 2: Connectivity specification carried in the setup message 2279 is not a valid connectivity specification for the recipient's 2280 node. 2281 These situations might indicate that the setup message has been 2282 corrupted in an undetected way, that a route agent used an 2283 out-of-date or corrupted map for the node when constructing the 2284 route, or that a setup message was misdelivered. In any case, the 2285 agent unable to recognize the node or connectivity specification 2286 generates a teardown message and sends it toward the initiator. 2287 Type 4: Conflict between the path and either the services provided by 2288 the recipient's node or the session service requirements from the 2289 target's perspective. 2290 Subtype 1: During path setup, an agent detects a conflict between 2291 the path and the services provided by its node (as reflected in 2292 the node's connectivity specifications) such that the node 2293 refuses to carry the session traffic or cannot meet the session 2294 service requirements. The agent generates a teardown message 2295 and sends it toward the initiator. 2296 Subtype 2: During path setup, the target detects a conflict between 2297 the path and the session service requirements from its 2298 perspective such that the path fails to meet these requirements. 2299 The target generates a teardown message containing its service 2300 requirements and sends the message toward the initiator. In 2301 this case, the initiator will attempt to find a path that is 2302 consistent with the target's service requirements as well as its 2303 own. 2304 Subtype 3: After path establishment, a forwarding agent detects a 2305 change in its node's services (as reflected in the node's 2306 connectivity specifications), which conflicts with the path such 2307 that either the node refuses to carry the session traffic or 2308 cannot meet the session service requirements. The agent 2309 generates a teardown message and sends copies toward the 2310 initiator and target. 2311 Subtype 4: After path establishment, the initiator or target 2312 detects a change in session service requirements which conflicts 2313 with the path such that the path fails to meet the new 2314 requirements. The initiator (or target) generates a teardown 2315 message and sends it toward the target (or initiator). 2317 Type 5: Preemption in favor of another path. The preempting agent 2318 generates a teardown message and sends copies toward the initiator 2319 and target. Endpoint representatives and forwarding agents are 2320 free to implement their own preemption criteria, but these are not 2321 part of this initial version of Nimrod. In this version, all paths 2322 are established on a first-come, first-served basis, with no 2323 preemption. 2324 Type 6: Unresolvable path label collision during path setup. (Refer to 2325 the discussion of status and ack messages below and to 2326 section 7.2.3 below for information on collision resolution.) The 2327 agent unable to resolve the path label collision generates a 2328 teardown message and sends it toward the initiator. 2330 44 2331 Type 7: Insufficient resources to any next-hop agent during path setup. 2332 The agent detecting a lack of resources to reach a specific 2333 next-hop agent attempts to find a suitable alternate next-hop 2334 agent. If it fails to find an alternate agent, the agent generates 2335 a teardown message and sends it to the previous-hop agent on the 2336 path. 2337 Subtype 1: Insufficient space in the forwarding database. The 2338 agent has no room for another entry in its forwarding database. 2339 Subtype 2: Insufficient resources for the path (e.g., unable to 2340 reserve required capacity for the session). 2341 Type 8: Loss of connectivity in the path. An agent may detect a loss 2342 in path connectivity through neighbor discovery (see section 8.1), 2343 agent discovery (see section 8.2), or through the loss of a 2344 lower-level path forming part of the given path. 2346 Subtype 1: An agent detecting a downstream loss to a specific 2347 next-hop agent attempts to repair the path by sending the 2348 original setup message to an alternate next-hop agent. If it 2349 fails to find an alternate agent, the agent generates a teardown 2350 message and sends it to the previous-hop agent on the path. 2351 Subtype 2: An agent detecting an upstream loss sets a repair timer. 2352 If the timer fires before the agent detects the path is 2353 repaired, the agent generates a teardown message and sends it to 2354 the next-hop agent on the path. An agent detects a repaired 2355 path through receipt of a copy of the original setup message 2356 (described in more detail in section 7.2). 2357 Type 9: Initiator exceeds specified maximum number of setup attempts. 2358 The initiator generates a teardown message and sends it toward the 2359 target, in order to clear any partially established forwarding 2360 state for the path. 2362 5. Report-mode monitored information, expressed as type, length, and 2363 value. If the setup message collected monitored information, and the 2364 teardown is generated in response to the setup message, then the 2365 teardown message reports this information as the services available 2366 over the path thus far. 2368 6. Integrity and authentication information covering all of the above. 2370 7.1.4 Status 2372 Status messages may be generated by any agent along a path, in order to 2373 report path information or modify path characteristics. Each status message 2374 contains: 2376 1. The label of the path to which the status pertains. 2378 2. The EID of the agent that generated the status message. 2380 45 2381 3. The time at which the status message was generated. 2383 4. The reason for the status message, expressed as type, length, and 2384 value. A status message may be generated for any of the following 2385 reasons: 2387 Type 1: Path monitoring. The initiator (or target) generates a status 2388 message containing collection-mode monitored information and sends 2389 it toward the target (or initiator). The ultimate recipient (which 2390 is usually the target or initiator but which may be an intermediate 2391 forwarding agent along the path if the path has failed in some way) 2392 responds by generating a status message containing report-mode 2393 monitored information and sends it toward the initiator (or 2394 target). 2395 Type 2: Path lifetime extension. The initiator generates a status 2396 message containing the amount of time by which to extend the path's 2397 life, hence preventing a path teardown prior to session cessation. 2399 Type 3: Replacement path label. When a path label contained in a setup 2400 message collides with a path label already in use at a forwarding 2401 agent or endpoint representative, that agent usually generates an 2402 ack message containing a replacement label for the new path that 2403 the previous-hop agent should use when sending messages along the 2404 new path toward this agent. In some cases, the agent may instead 2405 generate status messages containing replacement labels to use for 2406 an existing path, one for the previous-hop agent and one for the 2407 next-hop agent on the path. For example, if the existing path has 2408 not been used in a long time, the agent may choose to alter the 2409 forwarding information for that path rather than for the new path, 2410 in order to speed processing of data flowing along the new path. 2411 Type 4: Unrecognized requested session service contained in a setup 2412 message. This might indicate that the setup message has been 2413 corrupted in an undetected way or that the initiator is requesting 2414 new service requirements not yet known throughout the internetwork. 2415 In any case, the agent unable to recognize the session service 2416 request generates a status message, sends it toward the initiator, 2417 and ignores the unknown service when making next-hop decisions. 2418 Type 5: Failure to transmit a setup message successfully over a path 2419 hop. An agent detects this failure through an indication of 2420 unsuccessful transmission provided by the mechanism for hop-by-hop 2421 reliability (refer to the ack message discussion below for more 2422 information). It then generates a status message and sends it 2423 toward the initiator. In response to this type of status message, 2424 the initiator may either resend the original setup message or 2425 teardown the established portion of the path. 2427 Type 6: Unrecognized path label carried in a data message. This might 2428 indicate that the data message has been corrupted in an undetected 2429 way or that the agent receiving the message has failed recently and 2430 has lost state concerning the paths previously established through 2431 it. In any case, the agent unable to recognize the path label 2433 46 2434 generates a status message and sends it to the agent from which it 2435 received the data message containing that path label. 2437 5. Integrity and authentication information covering all but 2438 collection-mode monitored information. 2440 7.1.5 Ack 2442 The path management protocol provides reliable transmission of setup, 2443 accept, teardown, and status messages between successive sending and 2444 receiving agents along a path. After transmitting one of these messages 2445 along a path, the sending agent expects to receive, within a specified 2446 period of time, an ack message acknowledging successful receipt of the 2447 message at the next agent. If no ack message is forthcoming, the sending 2448 agent retransmits the setup, accept, teardown, or status message up to a 2449 specified maximum number of times. Furthermore, if the sending agent fails 2450 to receive an ack message after the specified number of retransmissions, it 2451 logs the event for possible network management action. Ack messages are 2452 generated by each agent along a path in response to the receipt of a setup, 2453 accept, teardown, or status message. Each ack message contains: 2455 1. The label of the path to which the ack pertains. 2457 2. The EID of the agent that generated the ack message. 2459 3. The time at which the ack message was generated. 2461 4. In the case of a path label collision, the replacement path label to 2462 use when sending messages along that path toward this agent. 2464 5. Integrity and authentication information covering all of the above. 2466 Given that the setup portion of the path management protocol is already 2467 reliable end to end (i.e., the initiator expects to receive either an accept 2468 or teardown message in response to its setup message and retransmits the 2469 setup message if no response if forthcoming within a specifed time period), 2470 one might consider hop-by-hop reliability overkill. Note that in lossy 2471 networks, the additional hop-by-hop reliability increases the reliability 2472 and responsiveness of the path management protocol and reduces the number of 2473 end-to-end path setup message retransmissions required for successful path 2474 establishment. 2476 In this version of Nimrod, the path management protocol, unlike the other 2477 Nimrod protocols, uses its own reliability mechanism rather than T/TCP. A 2478 simpler and more appealing design is one that employs a single reliable 2479 transaction protocol for all Nimrod control messages, either T/TCP or 2480 perhaps a Nimrod-specific transaction protocol. The reason for treating 2481 path management messages differently from other Nimrod control messages is 2483 47 2484 performance. In the prototype implementation of Nimrod, much of the path 2485 management functionality has been placed in the packet handling ``fast 2486 path'' while T/TCP is not. We expect that other implementations would 2487 likely be structured similarly. To improve message handling efficiency, the 2488 path management protocol uses its own separate mechanism for reliability of 2489 message transmissions. Thus, for this initial version of Nimrod, practical 2490 considerations have prevailed in the area of packet handling. 2492 7.2 Protocol Finite-State Machines 2494 The path setup procedure for this initial version of Nimrod operates as 2495 follows. An endpoint representative initiates path setup either under 2496 control of network management or when it receives, from an endpoint it 2497 represents, a data message that requires Nimrod routing and for which no 2498 existing path is suitable. After determining the location of the message's 2499 destination (by consulting its local locator cache or by querying the DNS) 2500 and obtaining a feasible route to that destination (by consulting its local 2501 route cache or by querying a route agent), the endpoint representative 2502 generates a setup message and sends it toward the target. The endpoint 2503 representative expects to receive an accept message from the target, 2504 indicating successful path establishment, within a specified time interval. 2505 If the endpoint representative fails to receive an accept message for the 2506 path within the allotted time interval, it retransmits the setup message, 2507 provided it has not yet exhausted its permitted number of setup attempts. 2508 The endpoint representative may make a specified maximum number of path 2509 setup attempts, in an effort to establish the path successfully. 2511 Unsuccessful path establishment manifests itself as either failure to 2512 receive an accept message after the maximum number of setup attempts or 2513 receipt of a teardown message instead of an accept message for the path. In 2514 either case, the initiator removes the path's state from its forwarding 2515 database and the corresponding route from its route cache, so that it does 2516 not use that route again immediately. It also logs the event for possible 2517 network management action. Moreover, when the initiator exhausts its 2518 maximum number of setup attempts and does not receive a teardown message, it 2519 generates a teardown message of type 9 (exceeded maximum number of setup 2520 attempts) and sends it toward the target, in order to remove any partially 2521 established forwarding state for the path. 2523 The agents in which a path's state is stored include boundary forwarding 2524 agents for nodes listed in the path's route specification, as well as 2525 endpoint representatives. When a boundary forwarding agent at the entrance 2526 to a node X receives a setup message for a path p, it performs a set of 2527 consistency and resource availability checks, in order to determine whether 2528 to install state for p in its forwarding database. Provided it does not 2529 reject p, the boundary forwarding agent installs state relating to the 2530 previous hop on p. For example, if the setup message for p arrives on a 2531 lower-level path q from agent G, the boundary forwarding agent installs 2532 state information in its forwarding database, indicating that the previous 2533 hop for p is via q and ends at agent G. It then looks up the next node Y 2535 48 2536 in the route specification carried in the setup message. 2538 If Y is adjacent to X, the boundary forwarding agent attempts to reach any 2539 boundary forwarding agent in X participating in the adjacency to Y. 2541 Case 1:X supports Nimrod routing internally. The boundary forwarding 2542 agent attempts to obtain a path to the boundary of X adjacent to Y , 2543 which may also involve obtaining a route. If there is an existing path 2544 r to the boundary of X adjacent to Y that is consistent with the 2545 session's requested services, the boundary forwarding agent sends the 2546 setup message for p over r. If there is no such path r, but a route 2547 consistent with the session's requested services does exist, the 2548 boundary forwarding agent initiates establishment of a path r for that 2549 route. It then installs information in its forwarding database, 2550 indicating that the next hop for p is via r, and then sends the setup 2551 message for p over r. Upon receipt of the accept message for r, the 2552 initiating boundary forwarding agent learns the identity of the 2553 next-hop agent H for p and then installs this information in its 2554 forwarding database entry for p. 2556 Case 2:X does not support Nimrod routing internally. The boundary 2557 forwarding agent picks a boundary forwarding agent H participating in 2558 the adjacency with Y (the existence of such boundary forwarding agents 2559 is learned through agent discovery, described in section 8.2). It then 2560 installs information in its forwarding database, indicating that the 2561 next-hop agent for p is H and sends the setup message to H. 2563 In either case, H then proceeds to install state for p in its forwarding 2564 database and to send the setup message on toward a boundary forwarding agent 2565 for Y. 2567 If Y is not adjacent to X, then the boundary forwarding agent attempts to 2568 obtain a path to Y, which may also involve obtaining a route to Y. If 2569 there is an existing path r to Y that is consistent with the session's 2570 requested services, the boundary forwarding agent sends the setup message 2571 for p over r. If there is no such path r, but a route consistent with the 2572 session's requested services does exist to Y, the boundary forwarding agent 2573 initiates establishment of a path r to Y. It then installs information in 2574 its forwarding database, indicating that the next hop for p is via r, and 2575 then sends the setup message for p over r. Upon receipt of the accept 2576 message for r, the initiating boundary forwarding agent learns the identity 2577 of the next-hop agent H for p and then installs this information in its 2578 forwarding database entry for p. 2580 There are two finite-state machines for the path management protocol, one 2581 applicable to the initiator and one applicable to the target or any 2582 intermediate forwarding agent in the path. The difference in state machines 2583 arises because the accept message contents only affect the behavior of the 2584 initiator. All state transitions caused by receipt of messages are 2585 described below. Except in one case, receipt of unexpected messages, such 2587 49 2588 as an accept following a teardown, does not cause state changes, further 2589 propagation of these messages, or issuing of new messages. The exceptional 2590 case is the receipt of a Nimrod data message with an unrecognized path 2591 label. This event causes no state transitions nor propagation of this 2592 message, but it does cause the recipient agent to generate a status message 2593 of type 6 and send it to the agent from which it received the unexpected 2594 data message. All anomalous and error events in the path management 2595 protocol are logged for possible network management action. 2597 7.2.1 Initiator 2599 The state machine for the initiator has four states: idle, check, ready, 2600 and done. State transitions are described below: 2602 o idle ! check: This transition occurs when the initiator begins to set 2603 up a path. The initiator then performs the consistency and resource 2604 availability checks for the path (described below). 2606 o check ! idle: This transition occurs if the initiator cannot 2607 successfully complete the consistency and resource availability checks 2608 for the path because a check failed. 2610 o check ! ready: This transition occurs after the initiator has 2611 successfully completed all of the consistency and resource availability 2612 checks for the path. The initiator then installs state for the path, 2613 including next-hop information, in its forwarding database, sends the 2614 setup message to the next hop, starts the accept timer, and initializes 2615 the setup transmission count. At this point, the initiator may begin 2616 to send data traffic over the path or may withhold data traffic until 2617 receipt of an accept message, depending upon the session service 2618 requirements. 2620 o ready ! done: This transition occurs when the initiator receives an 2621 accept message from the target. The initiator then stops the accept 2622 timer for the path. If the initiator had been withholding data traffic 2623 until this point, it may now send this traffic over the path. 2625 o ready ! check: This transition occurs when: 2627 - The initiator receives from the next-hop agent a teardown message 2628 of type 7.1 (insufficient space in forwarding database), 7.2 2629 (insufficient path resources), or 8 (loss of path connectivity). 2630 It then attempts to repair the path by sending a copy of the 2631 original setup message to an alternate next-hop agent. 2633 - The initiator receives from the next-hop agent a status message of 2634 type 6 (unrecognized path label in data message) containing a path 2635 label matching one of its own. It then seeks to re-establish the 2636 path by resending the original setup message to the next-hop agent. 2638 50 2639 o ready ! idle, done ! idle: This transition occurs when: 2641 - The initiator generates a teardown message for the path because the 2642 path lifetime expires, the node's offered services or the session 2643 service requirements have changed in a way that is inconsistent 2644 with the path, the path is preempted, or the accept timer fires 2645 before the path is successfully established. It then generates a 2646 teardown message and sends the message toward the target. 2648 - The initiator is unsuccessful at finding an alternate next-hop 2649 agent, following receipt of a teardown message of type 7.1 2650 (insufficient space in forwarding database), 7.2 (insufficient path 2651 resources), or 8 (loss of path connectivity). 2653 - The initiator receives a teardown message of type 1, 2, 3, 4, 5, or 2654 6. 2656 The initiator then removes the state information for the path from its 2657 forwarding database. 2659 7.2.2 Intermediate Forwarding Agents and Target 2661 The state machine for the intermediate forwarding agents and the target has 2662 three states: idle, check, and ready. There is no done state for these 2663 agents, because the accept message is only meaningful to the initiator. 2664 State transitions are described below: 2666 o idle ! check: This transition occurs when the agent receives a setup 2667 message for a new path. The agent then performs the consistency and 2668 resource availability checks for the path (described later on). 2670 o check ! idle: This transition occurs when: 2672 - The agent cannot complete the consistency and resource availability 2673 checks for the path, because a check failed. 2675 - The repair timer fires before completing the checks. 2677 - The agent receives from the previous-hop agent, a teardown message 2678 of type 4.3 (change in node offered services), 4.4 (change in 2679 session service requirements), 8 (loss of path connectivity), or 9 2680 (exceeded maximum number of setup attempts), before completing the 2681 checks. 2683 The agent then removes any partial state it has installed for the path. 2685 o check ! ready: This transition occurs after the agent has 2686 successfully completed all of the consistency and resource availability 2687 checks for the path. If the repair timer is ticking, the agent stops 2689 51 2690 the timer. The agent then installs state for the path, including 2691 previous hop and next hop and sends the setup message to the next hop. 2692 From the agent's perspective, the path may be used to carry data 2693 traffic. 2695 o ready ! check: This transition occurs when: 2697 - The agent receives, from the next-hop agent, a teardown message of 2698 type 7.1 (insufficient space in forwarding database), 7.2 2699 (insufficient path resources), or 8 (loss of path connectivity). 2700 It then attempts to repair the path by sending a copy of the 2701 original setup message to an alternate next hop. 2703 - The agent receives, from the next-hop agent, a status message of 2704 type 6 (unrecognized path label in data message) containing a path 2705 label matching one of its own. It then attempts to re-establish 2706 path state by resending a copy of the original setup message to the 2707 next hop. 2709 - The agent receives, from the previous-hop agent, a setup message 2710 for the path. This may occur when an upstream agent attempts path 2711 repair. 2713 o ready ! idle: This transition occurs when: 2715 - The agent generates a teardown message for the path, because the 2716 path lifetime expires, the node's services or the session service 2717 requirements have change in a way that is inconsistent with the 2718 path, the path is preempted, or the repair timer fires before the 2719 path is repaired. 2721 - The agent receives from the previous-hop or next-hop agent a 2722 teardown message of type 1, 2, 3, 4, 5, 6, or 9 or receives from 2723 the previous-hop agent a teardown message of type 8 (loss of path 2724 connectivity). 2726 The agent then removes the state information for the path from its 2727 forwarding database and sends the teardown message in the path 2728 direction indicated in the message. 2730 When in the check or ready states, if the agent detects a loss in 2731 connectivity with the previous-hop agent on the path, it sets the repair 2732 timer and waits for attempted path repair. The agent generates a teardown 2733 message of type 8 (loss of path connectivity), if the repair timer fires 2734 before the previous-hop state information is repaired, and sends the message 2735 toward the target. 2737 52 2738 7.2.3 Check State Actions 2740 When in the check state, an endpoint representative or forwarding agent must 2741 perform a series of tests to determine whether to install forwarding 2742 information for the path. These tests are partitioned into two sets, those 2743 related to consistency between the path and the services provided over the 2744 next hop and those related to resource availability over the next hop. Note 2745 that Nimrod datagram-mode data messages carrying requested session services 2746 and route specifications are subject to the same consistency checks as setup 2747 messages, even though no session-specific forwarding state is installed for 2748 these messages. Consistency checks performed by the intermediate forwarding 2749 agents and the target include the following: 2751 o The setup message is timely. Detection of out-of-date setup messages 2752 can help prevent denial of service attacks caused by replays. If the 2753 setup message is out of date, the agent sends a teardown message of 2754 reason type 2 (out-of-date setup message), toward the initiator. 2756 o The path label carried in the setup message is not already in use. If 2757 the path label is already in use, one of the following holds: 2759 Case 1: The timestamp and route specification carried in the setup 2760 message are identical to the timestamp and route specification for 2761 an already-established path. 2762 - If the previous-hop agent for the setup message (previous-hop 2763 information appears in messages as the source EID carried in the 2764 EID option, described in section 9), is the same as the 2765 previous-hop agent for the existing path, the agent assumes that 2766 the setup message is a duplicate submitted by the initiator 2767 subsequent to the firing of the accept timer for the path. The 2768 agent then forwards the setup message along the path toward the 2769 target to enable any downstream agents to establish state for 2770 the path, in case they failed to receive the original copy of 2771 the setup message. 2773 - If the previous-hop agent for the setup message is different 2774 from the previous-hop agent for the existing path, the agent 2775 assumes that the setup message is a duplicate submitted by an 2776 upstream agent attempting path repair. The agent updates its 2777 previous-hop information for the path in its forwarding database 2778 and does not forward the setup message. 2779 Case 2: The timestamp or route specification carried in the setup 2780 message are different from those of any already-established path. 2782 - If the setup message is for a unicast path, the agent assumes 2783 that the setup message is for a new path. The agent then 2784 attempts to obtain an alternate label either for the new path or 2785 for the existing path with which the new path label collides. 2787 53 2788 Subcase 1: The agent attempts to select a non-colliding path 2789 label for the new path if the most recent use of the existing 2790 path occurred within a specified interval relative to the 2791 current time. If the agent's supply of usused path labels is 2792 exhausted, the agent generates a teardown message of type 6 2793 (unresolvable path label collision) and sends it toward the 2794 initiator of the new path. Otherwise, the agent installs the 2795 appropriate forwarding state and selects a next-hop agent for 2796 the new path. It then includes in its ack message for the 2797 previous-hop agent and in its setup message for the next-hop 2798 agent, the replacement path labels to use when sending 2799 messages over the path and through this agent. Finally, it 2800 sends the ack message to the previous-hop agent and the setup 2801 message on toward the target. 2803 Case 2: The agent attempts to select a non-colliding path label 2804 for the existing path if the most recent use of the existing 2805 path occurred outside a specified interval relative to the 2806 current time. In this case, the agent installs the 2807 appropriate forwarding state, selects a next-hop agent, and 2808 sends the setup message on toward the target. The agent also 2809 changes the forwarding state for the existing path. If the 2810 agent's supply of usused path labels is exhausted, the agent 2811 generates a teardown message of type 6 (unresolvable path 2812 label collision) and sends it toward the initiator of the 2813 existing path. Otherwise, the agent substitutes the 2814 replacement path label in the forwarding state for the new 2815 path. It then generates two status messages of type 3, 2816 sending one to the previous-hop agent and one to the next-hop 2817 agent, on the existing path. These status messages contain 2818 the replacement path labels to use when sending messages over 2819 the existing path and through this agent. 2821 - If the setup message is for a multicast path, the agent assumes 2822 that the setup message is for a new branch of a multicast tree, 2823 other branches of which may already exist. The agent then 2824 installs new forwarding state for the indicated branch of the 2825 tree and sends the setup message toward the target. 2827 Consistency checks performed only by the intermediate forwarding agents 2828 include the following: 2830 o The route specification carried in the setup message is consistent with 2831 the node. Specifically, the recipient agent's node appears in the 2832 route specification and the connectivity specification contained in the 2833 route specification is valid for this node. If either of these 2834 conditions is not satisfied, the agent generates a teardown message of 2835 type 3.1 (node not present in route specification) or 3.2 (invalid 2836 connectivity specification) and sends the message toward the initiator. 2838 54 2839 o The path is consistent with the node's offered services. Specifically, 2840 the node permits the session traffic to use its resources and provides 2841 the required services. If these conditions are not satisfied, the 2842 agent generates a teardown message of type 4.1 (service conflict during 2843 setup) and sends the message toward the initiator. 2845 Consistency checks performed only by the target include the following: 2847 o The path is consistent with the session service requirements for the 2848 target. If this condition is satisfied, the target generates an accept 2849 message and sends it toward the initiator. Otherwise, the target 2850 generates a teardown message of type 4.2 (target service conflict) and 2851 sends the message toward the initiator. The teardown message contains 2852 the service requirements from the target's perspective. Upon receipt 2853 of such a teardown message, the initiator is responsible for attempting 2854 to obtain a feasible route that accounts for the session service 2855 requirements from the target's perspective. 2857 Resource availability checks performed by all agents include the following: 2859 o The forwarding database can accommodate state for the new path. If 2860 there is insufficient room in the forwarding database, the agent sends 2861 a teardown message of type 7.1 (insufficient space in forwarding 2862 database) to the previous-hop agent. 2864 Following successful completion of this check, the agent installs the 2865 previous-hop information in its forwarding database so that path management 2866 messages can flow in both directions along the path. Resource availability 2867 checks performed by the initiator and intermediate forwarding agents include 2868 the following: 2870 o There exists a way to reach the next node in the route specification, 2871 which provides the required services for the session and permits access 2872 to session traffic. This check is extensive and may require additional 2873 route generation and path setup for lower-level paths. To illustrate, 2874 let the current path be p. 2876 - The selected next-hop agent is directly connected to the agent, and 2877 thus there is no need to establish a lower-level path. In this 2878 case, the agent simply installs the next-hop information in its 2879 forwarding database and sends the setup message for p to the 2880 next-hop agent. 2882 - There is an already-established feasible lower-level path q with 2883 the required resources to a forwarding agent in the next-hop node. 2884 In this case, the agent links p with q in its next-hop entry for p 2885 in its forwarding database and sends the setup message for p to the 2886 next-hop agent, using q. 2888 55 2889 - There is no established feasible lower-level path to the next-hop 2890 node. In this case, the agent attempts to obtain a route for, set 2891 up, and obtain the necessary resources for a path q. The agent may 2892 either piggyback the setup information for q on the setup message 2893 for p or send a separate setup message for q, depending upon the 2894 session service requirements. Piggybacking reduces the time to set 2895 up a path at the expense of flexibility in collecting monitored 2896 information (monitored information can only be collected for one 2897 path at a time). If session traffic is allowed to flow before 2898 confirmation of successful path setup, the agent piggybacks the 2899 setup information for the two paths and links p and q in its 2900 next-hop entry for p in its forwarding database. Otherwise, the 2901 agent sends a separate setup message for q, waits for receipt of an 2902 accept message for q before linking p and q in its next-hop entry 2903 for p in its forwarding database, and then sends the setup message 2904 for p to the next-hop agent, using q. 2906 - A feasible lower-level path with the necessary resources cannot be 2907 established, either because no route exists or the path setup 2908 fails. In this case, the agent generates a teardown message of 2909 type 7.2 (insufficient path resources) and sends the message to the 2910 previous-hop agent on p. 2912 A teardown message of type 7.1 (insufficient space in forwarding database) 2913 or 7.2 (insuffcient path resources) received from an upstream neighbor 2914 during path setup may result in the recipient agent resending the setup 2915 message to another next-hop agent, if one is available. Only if there are 2916 no suitable next-hop agents does the agent propagate the teardown message 2917 toward the initiator. 2919 56 2920 8 Discovery Protocols 2922 Each Nimrod agent acting on behalf of a node requires knowledge about its 2923 immediately neighboring agents and about the other agents acting on behalf 2924 of the same node, in order to perform its routing functions properly. 2925 Agents continually execute a neigbor discovery protocol and an agent 2926 discovery protocol in order to obtain current information about each other. 2927 Neighbor discovery and agent discovery can be performed prior to 2928 hierarchical locator assignment, because forwarding of these messages 2929 requires knowledge of NIDs and EIDs only. Hence, the discovery protocols 2930 may be used to bootstrap the Nimrod routing system. 2932 8.1 Neighbor Discovery 2934 Neighbor discovery is performed by activated Nimrod agents within a node and 2935 provides the initial information for the formation of adjacencies between 2936 nodes and the formation of associations between endpoints and nodes. It 2937 enables an agent to determine whether there are other Nimrod agents 2938 reachable within one ``hop'' and if so which agents. A hop may constitute a 2939 direct link (point-to-point or multiaccess) between two agents or a virtual 2940 link (composed of many intervening links and routers that are not 2941 Nimrod-capable). 2943 When the hop is a virtual link, each agent at the end of the link must be 2944 configured with location information (e.g., IP address) for the agent at the 2945 other end, so that the neighbor discovery messages are distributed to the 2946 appropriate agent. Note that even when the hop is a direct link, the agent 2947 may require some location information configuration or discovery (e.g., IP 2948 router discovery) prior to Nimrod neighbor discovery; these requirements 2949 depend upon the specific network in which these Nimrod agents reside. 2950 Specifically, an agent must know the type of link attached to each of the 2951 interfaces of the device in which it resides, so that it can invoke the 2952 appropriate low-level protocols. For example, if an agent resides in a 2953 device attached to an Ethernet that also uses IP, that agent may use a 2954 combination of ARP, dynamic host configuration, and router discovery to 2955 determine its IP address and the IP address of a neighboring router. These 2956 functions must be executed prior to Nimrod neighbor discovery. 2958 A Nimrod agent periodically issues a neighbor discovery message over each of 2959 its interfaces through which a Nimrod-capable neighbor is expected to exist. 2960 Neighbor discovery messages are transported using T/TCP (with IP destination 2961 address set equal to the ``all devices'' multicast address) but are never 2962 retransmitted. Each neighbor discovery message contains the following 2963 information concerning the issuing agent: 2965 1. Type. 2967 2. The time at which the message was generated. 2969 3. Node on whose behalf it acts, expressed as an NID. 2971 57 2972 4. EID. 2974 5. Locator(s), when available. 2976 6. Set of nodes in which it resides, expressed as a hierarchical sequence 2977 of NIDs. 2979 7. Additional location information (e.g., IP address contained in the IP 2980 header section). 2982 8. Integrity and authentication information covering all but the 2983 additional location information. 2985 When a Nimrod agent X receives a neighbor discovery message, it knows that 2986 it has a neighboring agent Y. From then on, X expects to continue to 2987 receive periodic neighbor discovery messages from Y. Failure to receive 2988 neighbor discovery messages from a known neighbor indicates a reachability 2989 problem, caused by a physical component's malfunction or movement. An agent 2990 detecting a failure to reach a neighboring agent must alert the agent 2991 discovery protocol (see section 8.2) and path management protocol (see 2992 section 7) operating within it. Agent discovery uses this information to 2993 determine which agents are reachable, and path management uses this 2994 information to determine which paths require repair. 2996 8.1.1 Neighbor Reachability 2998 The periodic exchange of neighbor discovery messages works as an ``up/down'' 2999 protocol, such that from an agent's perspective the link to the neighbor is 3000 in one of two states, ``up'' or ``down''. Each agent maintains a sliding 3001 window for each neighboring agent. Each window slot corresponds to one 3002 period and contains either a ``hit'' for receipt of a message or a ``miss'' 3003 for failure to receive a message. In addition to the sliding window, the 3004 agent also records the number of hits during the current period and number 3005 of misses over the current window. 3007 The neighbor link is always considered ``down'' initially until the agent 3008 receives a sufficient number of messages from it to consider it to be 3009 ``up''. Whenever the neighbor link is down, the values of the protocol 3010 parameters are set as follows: 3012 o The sliding window size is equal to m. 3014 o Each window slot contains a miss. 3016 o The number of hits during the current period is equal to 0. 3018 o The number of misses within the window is equal to m. 3020 When the neighbor link moves from down to up, the values of the protocol 3022 58 3023 parameters are set as follows: 3025 o The sliding window size is equal to n. 3027 o Each window slot contains a hit. 3029 o The number of hits during the current period is equal to 0. 3031 o The number of misses within the window is equal to 0. 3033 At the conclusion of each period, an agent counts the misses and determines 3034 whether there has been a state transition in the neighbor link. When the 3035 neighbor link is down, a miss count of no more than m-j signals a 3036 transition to the up state. In the up state, a miss count of no less than 3037 n-k signals a transition to the down state. 3039 Counting the misses involves several steps. First, the agent prepares to 3040 slide the window by one slot so that the oldest slot disappears, making room 3041 for the newest slot. However, before sliding the window, the agent checks 3042 the contents of the oldest window slot. If this slot contains a miss, the 3043 agent decrements the number of misses by 1, as this slot is no longer part 3044 of the current window. After sliding the window, the agent initially 3045 records a miss in the newest window slot and then determines what the proper 3046 slot contents should be. If the number of hits for the current period 3047 equals 0, a miss is the correct value for the newest slot, and so the agent 3048 increases the number of misses by 1. Otherwise, if the number of hits for 3049 the current period is greater than 0, the agent applies the hits to any slot 3050 containing a miss, beginning with the newest and progressing to the oldest 3051 such slot. For each such slot, the agent records a hit in that slot and 3052 reduces the number of hits by 1. If the selected slot is not the newest 3053 slot, the hit cancels out an actual miss, and so the agent reduces the 3054 number of misses by 1 as well. The agent continues to apply each remaining 3055 hit to any slot containing a miss, until either all such hits are exhausted 3056 or all such slots are accounted for. Before beginning the next up/down 3057 period, the agent resets the number of hits to 0. 3059 Although we expect the number of hits, within any given period, to be no 3060 greater than 1, we do anticipate the occasional period in which an agent 3061 receives more than one message from a neighbor. The most common reasons for 3062 this occurrence are message delay and clock drift. When a message is 3063 delayed, the recipient agent observes a miss in one period followed by two 3064 hits in the next period, one of which cancels the previous miss. Excess 3065 hits remaining in the tally after miss cancellation indicate a problem, such 3066 as clock drift. Thus, whenever an agent accumulates excess hits, it logs 3067 the event for potential network management action. 3069 When clock drift occurs between two agents, it causes the period of one 3070 agent to grow with respect to the period of the other. Let pX be the 3071 period for agent X, let pY be the period for agent Y, and let g and h be 3072 the smallest positive integers such that gpX= hpY. Suppose that pX , 3394 and its packet format with field values is illustrated in the sections as 3395 indicated at the end of that line. The formats below assume IP (V.4 or V.6) 3396 as the network layer protocol. 3398 ::=
3400
::= AUTH-HDR ESP-HDR (section 9.2) 3402 ::= IP-V.4-HDR | IP-V.6-HDR (section 9.2) 3404 ::= ( | | 3405 | ) 3407 ::= PATH-STK SETUP | PATH-STK (section 9.3) 3409 ::= TRACE | MONITOR | TRACE MONITOR (section 9.3) 3411 ::= DATA (section 9.3) 3413 ::= ACK | ACCEPT | TEARDOWN | STATUS (section 9.3) 3415 ::= ( | ) 3417 ::= ( | ) 3419 ::= TTCP-HDR NIM-XACT-HDR (section 9.4) 3421 ::= UPDATE-HDR (section 9.5) 3423 ::= Q-R-HDR (section 9.5) 3425 ::= MAP-UPDATE | LOC-UPDATE | ADJ-UPDATE (section 9.6) 3427 ::= MAP-REQ | LOC-REQ | ADJ-REQ | ROUT-REQ | PATH-REQ (sec 9.7) 3429 ::= DISC-HDR (section 9.8) 3431 ::= DISC-HDR AGT-ADV (section 9.8) 3433 In the packet formats given in subsequent sections, fixed length fields are 3434 bordered by ``|'', and variable length fields are bordered by ``:''. In 3436 67 3437 case of the latter, a structure name is attached in parentheses along with 3438 the field, and the exact packet format of the structure name is given in 3439 Appendix 2. 3441 9.2 IP and Security Headers 3443 Nimrod does not require all routers and hosts to be Nimrod capable. Only 3444 Nimrod agents need to be able to recognize Nimrod-specific information in 3445 messages. Nimrod information exchaned between Nimrod agents is encapsulated 3446 within packets prefaced by the native forwarding header of the network. For 3447 this version of Nimrod, we have specified encapsulation within IPv4 [7] and 3448 IPv6 [13]. In the future, one might consider migration of some 3449 Nimrod-specific information into the IPv6 header as options (e.g. route 3450 specifications might appear as a route option). For now, we have elected to 3451 keep the Nimrod-specific information largely separate from the IPv6 header 3452 until we have gained more experience with Nimrod. 3454 IP-V.4-HDR ::= 3456 +=======+=======+===============+===============================+ 3457 | 4 |HdrLen |Type of Service| Packet Length | 3458 +-------+-------+---------------+-------------------------------+ 3459 | IP ID | Fragment | 3460 +---------------+---------------+-------------------------------+ 3461 | Time to Live | Protocol | Checksum | 3462 +---------------+---------------+-------------------------------+ 3463 | Source IPv4 Address | 3464 +---------------------------------------------------------------+ 3465 | Destination IPv4 Address | 3466 +===============================================================+ 3468 IP-V.6-HDR ::= 3470 +=======+=======+===============================================+ 3471 | 6 | Prio | Flow Label | 3472 +-------+-------+---------------+---------------+---------------+ 3473 | Payload Length | Next Header | Hop Limit | 3474 +-------------------------------+---------------+---------------+ 3475 | | 3476 | Source IPv6 Address | 3477 | | 3478 | | 3479 +---------------------------------------------------------------+ 3480 | | 3481 | Destination IPv6 Address | 3483 68 3484 | | 3485 | | 3486 +===============================================================+ 3488 There exists a new IP option (protocol number 60) to carry the EIDs for the 3489 source and destination of the message. This option is described in 3490 draft-ietf-nimrod-eid-00.txt and is pictured below. 3492 +---------------+---------------+---------------+---------------+ 3493 | Next Header | Ext Len = 2 | PadN = 1 | PadN Len = 0 | 3494 +---------------+---------------+---------------+---------------+ 3495 | Opt EID = A3 | EID Len = 18 | Src Len = 8 | Dst Len = 8 | 3496 +---------------+---------------+---------------+---------------+ 3497 | Source EID | 3498 | | 3499 +---------------------------------------------------------------+ 3500 | Destination EID | 3501 | | 3502 +---------------------------------------------------------------+ 3504 The IP security headers, including IP authentication [11] (protocol number 3505 51) and encryption [12] (protocol number 50), follow immediately after the 3506 IP forwarding headers, thus enabling the recipient to authenticate the 3507 message before parsing the rest of it. These headers are not required but 3508 instead are inserted at the discretion of the agent sending the message. 3510 AUTH-HDR ::= 3512 +---------------+---------------+-------------------------------+ 3513 | Next Header | Length | RESERVED | 3514 +---------------+---------------+-------------------------------+ 3515 | SPI | 3516 +---------------------------------------------------------------+ 3517 | | 3518 | Authentication Data | 3519 | | 3520 | | 3521 +---------------------------------------------------------------+ 3523 ESP-HDR ::= 3525 69 3526 Clear +---------------------------------------------------------------+ 3527 Text | SPI | 3528 ====== +---------------------------------------------------------------+ 3529 Cypher | InitVec | 3530 Text +---------------------------------------------------------------+ 3531 | Data : 3532 + +---------------+---------------+ 3533 : Padding | Pad Length | Next Header | 3534 +-------------------------------+---------------+---------------+ 3536 9.3 Nimrod Forwarding Information 3538 Nimrod forwarding information (protocol number 43) is contained in every 3539 Nimrod message, following the IP-related headers. This forwarding 3540 information consists of four possible sections: a set of paths to be setup 3541 or used; a set of routes that the message should follow; the route traversed 3542 thus far; and monitored information collected or reported along the path. 3543 Not all Nimrod messages contain all portions, as we describe in more detail 3544 below, but all Nimrod messages carry a path-stack section. Moreover, a 3545 message might carry no path labels in its path stack section (e.g., a 3546 response to a query that requires source-directed forwarding). There are 3547 several special bits in the path-stack section that indicate which other 3548 sections are present and how to parse them. 3550 The S bit indicates whether the path indicated by the label already exists 3551 and is to be used (S = 0) or does not yet exist and should be installed (S = 3552 1). Only data messages and path management messages carry path labels. 3554 The R bit indicates whether the path direction is from source to destination 3555 (R = 1) or from destination to source (R = 0). At each forwarding agent 3556 along a path, there is a forwarding entry for each direction of the path 3557 (previous hop and next hop). Data messages flow in the 3558 source-to-destination direction. Path management messages may flow in 3559 either direction, but the direction must be indicated in the path label. 3561 The C bit indicates whether there has been a path label collision (C = 1) 3562 during path setup. If there has been a collision, the first path label with 3563 the C bit set is the original path label and the second path label with the 3564 C bit set is the replacement path label. The next agent to receive this 3565 message will use the replacement path label when forwarding messages toward 3566 the previous agent along the path. 3568 The T bit indicates whether or not there is route tracing in progress. 3569 Routing tracing is used to collect routing information during queries that 3570 occur prior to locator assignment, so that the response can return to the 3571 agent that placed the query, even if the queried agent does not know the 3572 locator of the requesting agent. Route tracing is normally only used in 3573 query messages, and then only prior to locator assignment. 3575 70 3576 The M bit indicates whether there is monitored information being collected 3577 in the message (M = 1). Monitored information is normally only collected in 3578 path management messages. 3580 PATH-STK ::= 3582 +------ (Header Length + 1) * 8 3583 | +---- (Section Length + 1) * 8 3584 | | +-- Path Offset 3585 | | | 3586 v v v 3587 ===== +===============+===============+===============+===============+ 3588 ^ ^ ^ | Next Header | Header Length | Version = 1 | Hops to Go | 3589 | | | +---------------+---------------+---------------+-+-+-+-+-+-----+ 3590 | | | | Type=Forward | Section Length| Path Offset |S|C|M|R|T| 0 | 3591 | | | +---------------+---------------+---------------+-+-+-+-+-+-----+ 3592 | | v : Available for additional Path Labels : 3593 | | - +---------------+-----------------------------------------------+ 3594 | | |S:0 1 1:C:0 0 0:R: Path Label n | 3595 | | +---------------+-----------------------------------------------+ 3596 | | |S:0 1 1:C:0 0 0:R: ... : 3597 | | +---------------+-----------------------------------------------+ 3598 | | |S:0 1 1:0:0 0 0:R: Path Label 1 | 3599 | | +---------------+-----------------------------------------------+ 3600 | v |S:0 1 1:0:0 1 0:R: Path Label 0 | 3601 |====== +===============================================================+ 3602 | 3604 All messages that require source-directed forwarding contain the following 3605 section, which carries routes. These messages include setup messages 3606 themselves, datagram-mode messages, and responses to queries prior to 3607 locator assignment (in this case, the route contains a sequence of NIDs and 3608 ``best effort'' connectivity specifications). The authentication field 3609 carried in each route covers all of the common information except the route 3610 offset, destination EID, destination endpoint representative EID, and all of 3611 the information pertaining to that route. 3613 In a setup messages, the flags indicate whether the path is source-initiated 3614 or destination-initiated, unicast or multicast, sharable among sessions or 3615 dedicated to a particular session, and whether the requested services are 3616 preferences or requirements. The destination endpoint and endpoint 3617 representative may be designated as ``unknown'' in some cases. Setup 3618 message may simultaneously set up more than one path. In this case, 3619 multiple routes are carried in a single setup message. 3621 71 3622 SETUP ::= 3624 | 3625 | +------- (Section Length + 1) * 8 3626 | | +----- (Common Length + 1) * 8 3627 | | | +--- route offset 3628 | v v v 3629 |====== +===============+===============+===============+===============+ 3630 | ^ ^ | Type=Paths |Section Length | Subtype=Setup | Flags | 3631 | | | | +---------------+---------------+---------------+---------------+ 3632 | | | | | | Common Length | 0 | 3633 | | | | +---------------+---------------+-------------------------------+ 3634 | | | | | Message Generation Timestamp | 3635 | | | | +---------------------------------------------------------------+ 3636 | | | | : Requested Services : 3637 | | | | +---------------------------------------------------------------+ 3638 | | | | | Source EID | 3639 | | | | | | 3640 | | | | +---------------------------------------------------------------+ 3641 | | | | | Source Endpoint Representative EID | 3642 | | | | | | 3643 | | | | +---------------------------------------------------------------+ 3644 | | | | | Destination EID | 3645 | | | | | | 3646 | | | | +---------------------------------------------------------------+ 3647 | | | | | Destination Endpoint Representative EID | 3648 | | | | | | 3649 | | | | +---------------------------------------------------------------+ 3650 | | v | ? 64-bit Pad ? 3651 | |---| +===============================================================+ 3652 | | v : Free/64-bit pad : 3653 | | -- +---------------+---------------+---------------+---------------+ 3654 | | | Type=Route | Route Length | 0 | | 3655 | | +---------------+---------------+---------------+---------------+ 3656 | | : Authentication : 3657 | | +---------------------------------------------------------------+ 3658 | | : Route n : 3659 | | : a sequence of hops each represented as : 3660 | | : length, connectivity specification, and node locator or nid : 3661 | | +---------------------------------------------------------------+ 3662 | | : ... : 3663 | | +---------------+---------------+---------------+---------------+ 3664 | | | Type=Route | Stack Length | 0 | | 3665 | | +---------------+---------------+---------------+---------------+ 3666 | | : Authentication : 3667 | | +---------------------------------------------------------------+ 3668 | v : Route 0 : 3669 |===== +---------------+---------------+---------------+---------------+ 3670 | 3672 72 3673 All path management messages are transmitted reliably, hop by hop along the 3674 path. The ack message indicates the type of message acknowledged. If the 3675 type of message acknowledged is a setup message and the C bit is set in the 3676 path label acknowledged, then the message contains a replacement path label 3677 to use in the opposite direction along the path. In the ack, accept, 3678 status, and teardown messages, the authentication field covers the entire 3679 section of the message. 3681 ACK ::= 3683 | 3684 | +------- (Section Length + 1) * 8 3685 | v 3686 |=== +===============+===============+===============+===============+ 3687 | ^ | Type=Paths | Section Length| Subtype=Ack | Flags | 3688 | | +---------------+---------------+---------------+---------------+ 3689 | | |Type Msg Acked | 0 | 3690 | | +---------------+-----------------------------------------------+ 3691 | | | Message Generation Timestamp | 3692 | | +---------------------------------------------------------------+ 3693 | | | Path Label of Acknowledged Message | 3694 | | +---------------------------------------------------------------+ 3695 | | | Replacement Path Label | 3696 | | +---------------------------------------------------------------+ 3697 | | : Authentication : 3698 | | +---------------------------------------------------------------+ 3699 | v ? 64-bit Pad ? 3700 |=== +---------------------------------------------------------------+ 3701 | 3703 ACCEPT ::= 3705 | 3706 | +------- (Section Length + 1) * 8 3707 | v 3708 |=== +===============+===============+===============+===============+ 3709 | ^ | Type=Paths | Section Length| Subtype=Accept| Flags | 3710 | | +---------------+---------------+---------------+---------------+ 3711 | | | 0 | 3712 | | +---------------------------------------------------------------+ 3713 | | | Message Generation Timestamp | 3714 | | +---------------------------------------------------------------+ 3715 | | | Accepted Path Label | 3716 | | +---------------------------------------------------------------+ 3717 | | : Authentication : 3718 | | +---------------------------------------------------------------+ 3720 73 3721 | v ? 64-bit Pad ? 3722 |=== +---------------------------------------------------------------+ 3723 | 3725 Status and teardown message contain information pertaining to the reason for 3726 the status or teardown message. 3728 STATUS ::= 3730 | 3731 | +------- (Section Length + 1) * 8 3732 | v 3733 |=== +===============+===============+===============+===============+ 3734 | ^ | Type=Paths | Section Length| Subtype=Status| Flags | 3735 | | +---------------+---------------+---------------+---------------+ 3736 | | | Status Code | Code Length | Code Data : 3737 | | +---------------+-----------------------------------------------+ 3738 | | | Message Generation Timestamp | 3739 | | +---------------------------------------------------------------+ 3740 | | | Path Label | 3741 | | +---------------------------------------------------------------+ 3742 | | : Authentication : 3743 | | +---------------------------------------------------------------+ 3744 | v ? 64-bit Pad ? 3745 |=== +---------------------------------------------------------------+ 3746 | 3748 TEARDOWN ::= 3750 | 3751 | +------- (Section Length + 1) * 8 3752 | v 3753 |=== +===============+===============+===============+===============+ 3754 | ^ | Type=Paths | Section Length|Subtype=Teardwn| Flags | 3755 | | +---------------+---------------+---------------+---------------+ 3756 | | | Teardown Code | Code Length | Code Data : 3757 | | +---------------+-----------------------------------------------+ 3758 | | | Message Generation Timestamp | 3759 | | +---------------------------------------------------------------+ 3760 | | | Path Label | 3761 | | +---------------------------------------------------------------+ 3762 | | : Authentication : 3763 | | +---------------------------------------------------------------+ 3764 | v ? 64-bit Pad ? 3766 74 3767 |=== +---------------------------------------------------------------+ 3768 | 3770 The route tracing section is optional and usually only contained in query 3771 messages transmitted prior to locator assignment. The route collected in 3772 the message can be reversed to send the response back to the requesting 3773 agent. In this case, the traced route is expressed in terms of NIDs instead 3774 of locators. 3776 TRACE ::= 3778 | 3779 | +------- (Section Length + 1) * 8 3780 | | +----- free offset 3781 | v v 3782 |====== +===============+===============+===============+===============+ 3783 | ^ ^ | Type=Trace | Section Length| 0 | | 3784 | | | +---------------+---------------+---------------+---------------+ 3785 | | v : Free/64-bit pad : 3786 | |--- +---------------------------------------------------------------+ 3787 | | : : 3788 | | +---------------------------------------------------------------+ 3789 | | : ... : 3790 | | +---------------------------------------------------------------+ 3791 | v : : 3792 |=== +---------------------------------------------------------------+ 3793 | 3795 Monitored information is normally carried only in path management messages. 3796 There are two types of monitored information, collection-mode and 3797 report-mode. Setup messages carry only collection-mode information and 3798 accept and teardown carry only report-mode information; status messages may 3799 carry either type. Each of the monitored items is expressed in terms of a 3800 service specification (e.g., delay, MTU, throughput). 3802 MONITOR ::= 3804 | 3805 | +------- (Section Length + 1) * 8 3806 | v 3807 |=== +===============+===============+===============================+ 3808 | ^ | Type=Monitor | Section Length|Subtype=Cl/Rp | Flags | 3809 | | +---------------+---------------+-------------------------------+ 3811 75 3812 | | | | 3813 | | +---------------------------------------------------------------+ 3814 | | : ... : 3815 | | +---------------------------------------------------------------+ 3816 | | | | 3817 | | +---------------------------------------------------------------+ 3818 v v ? 64-bit Pad ? 3819 ==== +---------------------------------------------------------------+ 3821 9.4 Transaction Headers 3823 TTCP-HDR ::= 3825 (Transaction) TCP Header (IPPROTO_TCP = 6) 3827 +-------------------------------+-------------------------------+ 3828 | Src Port | Dest Port = 1617 | 3829 +-------------------------------+-------------------------------+ 3830 | Sequence Number | 3831 +---------------------------------------------------------------+ 3832 | Acknowledgement Number | 3833 +-------+-----------+-+-+-+-+-+-+-------------------------------+ 3834 |TCP Len| |U|A|P|R|S|F| Window | 3835 +-------+-----------+-+-+-+-+-+-+-------------------------------+ 3836 | Checksum | Urgent Pointer | 3837 +---------------+---------------+-------------------------------+ 3838 | MSS = 2 | Len = 4 | Maximum Segment Size | 3839 +---------------+---------------+-------------------------------+ 3840 | CC=11/.NEW=12 | Len = 6 | Seg.cc 3841 +---------------+---------------+---------------+---------------+ 3842 | CC.Echo = 13 ? Len = 6 ? 3843 +-------------------------------+---------------+---------------+ 3844 ? Seg.cc ? 3845 ---- +---------------------------------------------------------------+ 3847 NIM-XACT-HDR ::= (Nimrod) Transaction Header (TCP Dest Port = 1617) 3849 +---------------------------------------------------------------+ 3850 | Transaction Length | 3851 +---+---+-------+---------------+-------------------------------+ 3852 |Ver|Prt| Oper | Phase | Transaction Identifier | 3853 +---+---+-------+---------------+-------------------------------+ 3854 | NTP Seconds | 3855 ---- +---------------------------------------------------------------+ 3857 76 3858 Ver value : 0 3860 Prt values : 3862 0 = Discovery Protocol 3863 1 = Update Protocol 3864 2 = Query Protocol 3865 3 = Response Protocol 3867 Oper values : 3869 When Prt = 1 : 3871 1 = Adjacency update 3872 3 = Endpoint locator update 3873 4 = Node locator update 3874 5 = Map update 3876 When Prt = 2 or 3 : 3878 1 = Adjacency Activation 3879 2 = Adjacency Release 3880 3 = Adjacency Request 3881 4 = Endpoint locator acquisition 3882 5 = Node locator acquisition 3883 6 = Locator release 3884 7 = Map request 3885 8 = Map update termination 3886 9 = Path request 3887 10 = Route request 3889 Phase values : 10 = forward map update to parent node FA 3890 12 = distribute map update to NR and RA 3891 13 = forward locator update to child node FA 3892 14 = notify all agents in node of new locator 3893 16 = notify adjacency to NR 3895 9.5 Update, Query, and Response Protocol Headers 3897 UPD-HDR ::= 3899 +---------------+---------------+-------------------------------+ 3900 | org agt typ | dst agt typ | flags | 3901 +---------------+---------------+-------------------------------+ 3902 | db_type | db sequence | 3903 +---------------+-----------------------------------------------+ 3904 : authenticator (NimAuth) : 3906 77 3907 +---------------------------------------------------------------+ 3908 : dst NID (NimNID) : 3909 +---------------------------------------------------------------+ 3910 : originator's EID (NimEID) : 3911 +---------------------------------------------------------------+ 3912 : originator's Locator (NimLoc) : 3913 +---------------- ----------------------------------------------+ 3915 agt typ values : 3917 0 = Any endpoint, not a Nimrod agent. 3918 0x01 = Association Agent (for future use). 3919 0x02 = Endpoint Representative. 3920 0x04 = All Forwarding Agents. 3921 0x08 = Boundary to child Forwarding Agent. 3922 0x10 = Boundary to parent FA. 3923 0x20 = Node Representative. 3924 0x40 = Designated Node Representative. 3925 0x80 = Route Agent. 3926 0xA0 = Node representative and Route Agents. 3927 0xA6 = All agents in the node. 3928 0x1000 = Neighboring FA. 3929 0x2000 = Neighboring FA in parent. 3930 0x4000 = Neighboring FA in child. 3932 db type values : 3934 1 = Abstraction DB 2 = Agent DB 3935 3 = Adjacency DB 4 = ARP DB 3936 5 = Association DB 6 = DNS DB 3937 7 = Endpoint DB 8 = End-to-End Session DB 3938 9 = Forwarding Agt DB 10 = Forwarding path branch DB 3939 11 = Forw. Conn. Spec DB 12 = Forwarding flood DB 3940 13 = Filtering DB 14 = Forwarding neighbor DB 3941 15 = Forwarding path DB 16 = Forwarding route DB 3942 17 = Intercept endpoint DB 18 = Intercept session DB 3943 19 = Key DB 20 = Locator DB 3944 21 = IP Multicast forwarding DB 22 = Map DB 3945 23 = Map registration DB 24 = Node DB 3946 25 = Route DB 26 = IP unicast forwarding DB 3948 Q-R-HDR ::= 3950 +---------------+---------------+-------------------------------+ 3951 | org agt typ | dst agt typ | flags | 3952 +---------------+---------------+-------------------------------+ 3953 | db_type | count | opcd | 3955 78 3956 +---------------------------------------------------------------+ 3957 : authenticator (NimAuth) : 3958 +---------------------------------------------------------------+ 3959 : Q: Originator's or R: Responder's EID (NimEID) : 3960 +---------------------------------------------------------------+ 3961 : Q: Originator's or R: Responder's Locator (NimLoc) : 3962 +---------------------------------------------------------------+ 3963 : credentials (NimCred) : 3964 +---------------------------------------------------------------+ 3966 9.6 Update Operation Messages 3968 ADJ-UPDATE ::= 3970 +---------------+---------------+---------------+---------------+ 3971 : Neighbor node id (NimNID) : 3972 +---------------+---------------+---------------+---------------+ 3973 : Neighbor node loc (NimLoc) : 3974 +---------------+---------------+---------------+---------------+ 3975 : Boundary forwarding agent locator (NimLoc) : 3976 +---------------+---------------+---------------+---------------+ 3978 LOC-UPDATE ::= 3980 +---------------+---------------+---------------+---------------+ 3981 : Originator Credentials (NimCred) : 3982 +---------------+---------------+---------------+---------------+ 3983 : Old NR EID (NimEID) : 3984 +---------------+---------------+---------------+---------------+ 3985 : Old NR locator (NimLoc) : 3986 +---------------+---------------+---------------+---------------+ 3987 : Old locator (NimLoc) : 3988 +---------------+---------------+---------------+---------------+ 3989 : New locator (NimLoc) : 3990 +---------------+---------------+---------------+---------------+ 3991 : Valid until (NimSecs) : 3992 +---------------+---------------+---------------+---------------+ 3994 Defined Flag (in UPD-HDR) values : 3996 1 = Depreciate use of old locator 3997 2 = Terminate use of old locator. 3999 79 4000 MAP-UPDATE ::= 4002 +---------------+---------------+---------------+---------------+ 4003 : Abstract Map (NimMap) : 4004 +---------------+---------------+---------------+---------------+ 4005 : Agent specific map 1 (NimMap) : 4006 +---------------+---------------+---------------+---------------+ 4007 : Agent specific map 2 (NimMap) : 4008 +---------------+---------------+---------------+---------------+ 4009 : ....... : 4010 +---------------+---------------+---------------+---------------+ 4011 : Agent specific map n (NimMap) : 4012 +---------------+---------------+---------------+---------------+ 4014 Defined Flag (in UPD-HDR) values : 4016 1 = One or more component nodes not in map 4017 2 = Map is of a partitioned node. 4019 9.7 Query/Response Operation Messages 4021 For most databases, we have the request, release, and response messages (for 4022 adjacencies, we additionally have the activation message). We only give the 4023 formats for the request messages for each database. The other message 4024 formats are similar and can be easily reconstructed from the contents 4025 description given earlier in section 6.4. 4027 ADJ-REQ ::= 4029 +---------------+---------------+---------------+---------------+ 4030 : Requesting Node Locator (NimLoc) : 4031 +---------------+---------------+---------------+---------------+ 4032 : Requesting Node Identifier (NimNID) : 4033 +---------------+---------------+---------------+---------------+ 4034 : Requesting Node Circuit ID (NimLkID) : 4035 +---------------+---------------+---------------+---------------+ 4036 : Neighbor Node ID (NimNID) : 4037 +---------------+---------------+---------------+---------------+ 4039 Defined Flag (in Q-R-HDR) values : 4041 1 = Adjacency from parent to child 4042 2 = Other adjacencies 4043 4 = Adjacency from child to parent 4044 8 = Adjacency to siblings 4046 80 4047 NODE-LOC-REQ ::= 4049 +---------------+---------------+---------------+---------------+ 4050 | Old NR EID (NimEID) : 4051 +---------------+---------------+---------------+---------------+ 4052 : Old NR locator (NimLoc) : 4053 +---------------+---------------+---------------+---------------+ 4054 : Previously assigned loc (NimLoc) : 4055 +---------------+---------------+---------------+---------------+ 4056 : Parent NID (NimNID) : 4057 +---------------+---------------+---------------+---------------+ 4058 : Child NID (NimNID) : 4059 +---------------+---------------+---------------+---------------+ 4061 EP-LOC-REQ ::= 4063 +---------------+---------------+---------------+---------------+ 4064 | Old NR EID (NimEID) : 4065 +---------------+---------------+---------------+---------------+ 4066 : Old NR locator (NimLoc) : 4067 +---------------+---------------+---------------+---------------+ 4068 : Previously assigned loc (NimLoc) : 4069 +---------------+---------------+---------------+---------------+ 4070 : NID to provided loc (NimNID) : 4071 +---------------+---------------+---------------+---------------+ 4072 : Endpoint name (NimFQDN) : 4073 +---------------+---------------+---------------+---------------+ 4074 : Endpoint ID (NimEID) : 4075 +---------------+---------------+---------------+---------------+ 4077 MAP-REQ ::= 4079 +---------------+---------------+---------------+---------------+ 4080 | Node loc of desired map (NimLoc) : 4081 +---------------+---------------+---------------+---------------+ 4082 : Child elements if partial (NimLElem) : 4083 +---------------+---------------+---------------+---------------+ 4084 : Credentials of requesting node (NimCred) : 4085 +---------------+---------------+---------------+---------------+ 4087 81 4088 Defined Flag (in Q-R-HDR) values : 4090 0x8000 = Response must be authoritative 4091 0x4000 = Abbreviated map desired 4092 0x2000 = Complete maps desired 4093 0x1000 = Automatic updates desired 4095 ROUT-REQ ::= 4097 +---------------+---------------+---------------+---------------+ 4098 | Sources (NimLEpt) : 4099 +---------------+---------------+---------------+---------------+ 4100 : Destinations (NimLEpt) : 4101 +---------------+---------------+---------------+---------------+ 4102 : Initiating EPs service reqs (NimServ) : 4103 +---------------+---------------+---------------+---------------+ 4104 : Target EPs service reqs (NimServ) : 4105 +---------------+---------------+---------------+---------------+ 4106 : Child NID (NimNID) : 4107 +---------------+---------------+---------------+--------------- 4109 Defined Flag (in Q-R-Hdr) values : 4111 0x10 = Want maximally disjoint routes 4113 9.8 Discovery Message Header 4115 Neighbor discovery messages and agent discovery messages contain much of the 4116 same information. This information is represented in a single header 4117 pictured below. The authentication field covers the header and any enclosed 4118 information. 4120 DISC-HDR ::= 4122 +---------------+---------------+-------------------------------+ 4123 | Type=Nbr/Agt | Agent Type | 0 | Flags | 4124 +---------------+---------------+-------------------------------+ 4125 | Message Generation Timestamp | 4126 +---------------------------------------------------------------+ 4127 : Authentication : 4128 +---------------------------------------------------------------+ 4129 | Agent's EID | 4130 | | 4131 +---------------------------------------------------------------+ 4133 82 4134 | NID of Agent's Node | 4135 | | 4136 +---------------------------------------------------------------+ 4137 : Agent's Locator : 4138 +---------------------------------------------------------------+ 4139 : Sequence of NIDs : 4140 : of nodes containing agent : 4141 : formatted as a locator : 4142 +---------------------------------------------------------------+ 4144 The neighbor discovery message includes only the discovery header, while the 4145 agent discovery message contains the EID and services to each neighbor. 4146 Furthermore, if the advertising agent is a boundary forwarding agent, the 4147 advertisement also contains the neighbor's NID, locator, sequence of NIDs in 4148 which the neighbor is contained, and an indication of whether the agent 4149 participates in an adjacency (A = 1) with the neighbor and if so which 4150 types: outbound (T = 1), inbound (T = 2), or both (T = 3). 4152 AGT-ADV ::= 4154 +---------------------------------------------------------------+ 4155 | EID of Neighbor n | 4156 | | 4157 +---------------------------------------------------------------+ 4158 : Services to Neighbor n : 4159 +---------------------------------------------------------------+ 4160 | NID of Neighbor n's Node | 4161 | | 4162 +---------------------------------------------------------------+ 4163 : Locator of Neighbor n's Node : 4164 +---------------------------------------------------------------+ 4165 : Sequence of NIDs : 4166 : of nodes containing neighbor n : 4167 : formatted as a locator : 4168 +---------------------------------------------------------------+ 4169 |A|T | type of adjacency with neighbor n's node | 4170 +---------------------------------------------------------------+ 4171 : ... : 4172 +---------------------------------------------------------------+ 4173 | EID of Neighbor 0 | 4174 | | 4175 +---------------------------------------------------------------+ 4176 : Services to Neighbor 0 : 4177 +---------------------------------------------------------------+ 4178 | NID of Neighbor 0's Node | 4179 | | 4180 +---------------------------------------------------------------+ 4182 83 4183 : Locator of Neighbor 0's Node : 4184 +---------------------------------------------------------------+ 4185 : Sequence of NIDs : 4186 : of nodes containing neighbor 0 : 4187 : formatted as a locator : 4188 +---------------------------------------------------------------+ 4189 |A|T | type of adjacency with neighbor 0's node | 4190 +---------------------------------------------------------------+ 4192 84 4193 10 Appendix 1: Figures for Update and Q-R protocols 4195 85 4196 86 4197 87 4198 88 4199 89 4200 11 Appendix 2: Basic Data Formats 4202 In section 9, a number of packet formats were pictured in terms of other, 4203 more basic, variable length data objects such as locator (NimLoc), and EID 4204 (NimEID). Here we give the formats for such basic data elements. Only the 4205 more basic and important data objects are described in detail and 4206 illustrated pictorially - namely Element (NimElem), Locator (NimLoc), EID 4207 (NimEID), Endpoint Name (NimFQDN), Node ID (NimNID). The other data objects 4208 are given in the form of C structure declarations. 4210 11.1 Element (NimElem) 4212 An Element consists of a variable number of octets, with the most frequently 4213 used length expected to be two octets. The most significant bit (M) is one 4214 (1) for a multicast element and zero (0) otherwise. The next few bits 4215 encodes the element length. The remaining bits may be asigned by node 4216 representatives. Different instances of a node representative might choose 4217 to use different assignment algorithms. The only constraint is that the set 4218 of node representatives for a node should cooperate to make sure that an 4219 element is not given out by more than one of the representatives. 4221 Several formats have been predefined. One-octet elements are expected to be 4222 used to identify routers or router interfaces of small sized nodes that 4223 choose to include router identification in their locators, e.g., use Nimrod 4224 routing as their intra-node routing protocol. The format of a one-octet 4225 element is: 4227 +-+-+-+-+-+-+-+-+ 4228 |M|0| | 1 octet, 6 free bits 4229 +-+-+-+-+-+-+-+-+ 4231 Two-octet elements are expected to be used in most cases. An organization 4232 might choose to set aside some bits in an element that could be used, e.g., 4233 to identify successive numbering plans, so that internal management and 4234 monitoring might be simplified. The format of a two-octet element is: 4236 +-+-+-+-+-+-+-+-+-+...+-+ 4237 |M|1 0 0| | 2 octets, 12 free bits 4238 +-+-+-+-+-+-+-+-+-+...+-+ 4240 Four-octet elements are provided for nodes that, e.g., want to include local 4241 information in an element. The format of a four-octet element is: 4243 +-+-+-+-+-+-+-+-+-+...+-+ 4244 |M|1 1 1 0 0 0 0| | 4 octets, 24 free bits 4246 90 4247 +-+-+-+-+-+-+-+-+-+...+-+ 4249 Nimrod uses a two-octet element to specify which agents within a node should 4250 receive a control message. The format of this element is: 4252 +-+-+-+-+-+-+-+-+-+-+...+-+-+ 4253 |M|1 1 1 0 0 0 1| Agent Set | 2 octets, Nimrod Agent Set 4254 +-+-+-+-+-+-+-+-+-+-+...+-+-+ 4256 Seven-octet elements are used within the Nimrod system to encode EIDs and 4257 NIDs in a locator element. These elements are used during bootstrapping to 4258 enable intra-node (including to a parent or component node) communication 4259 before globally routable locator (element)s have been acquired. The format 4260 of this element is: 4262 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4263 |M|1 1 0|Rel| EID / NID bits | 4264 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4265 | | 4266 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4268 The relationship field (Rel) is used for node-relative addressing. Its 4269 values are: 4271 00 This node 4272 01 Parent node 4273 10 Child node 4274 11 Reserved 4276 11.2 Locator (NimLoc) 4278 A locator is a variable length object that represents a location in an 4279 internet. It consists of a header containing a flag bit, bits that identify 4280 the object as a locator and bits encoding the total length, one or more self 4281 delimiting locator elements, and optional octets of zero padding to make the 4282 overall length of the locator in octets zero mod 4. An element occupies an 4283 integral number of octets. 4285 The bits identifying a locator are 0000 011. This is derived from the 4286 experimental IPv6 address space. 4288 Each locator begins on a 32-bit boundary, and is padded with zero octets to 4289 maintain 32-bit overall alignment. 4291 91 4292 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+---------------+ 4293 |0 0 0 0 0 1 1|Z|F|1 1 0 0|CdLen| | | 4294 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+---------------+ 4295 | | 4296 +---------------+---------------+---------------+---------------+ 4298 The Z field must be zero and is reserved for future expansion. 4300 The F field is a context-dependent flag bit. 4302 The length, in octets, of a locator is indicated by the CdLen field as 4303 follows: 4305 CdLen 0 1 2 3 4 5 6 7 4306 Octets 4 8 12 16 20 24 32 Reserved 4308 11.3 Endpoint Identifier (NimEID) 4310 Nimrod uses Endpoint Identifiers (EIDs), globally unique, hierarchy 4311 independent, relatively fixed and short length, administratively assigned 4312 binary representations of endpoint names. Initially, EIDs will be 4313 eight-octet quantities, with fiftey bits available for assignment. The 4314 format of the EID is (HELP???) : 4316 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4317 |F|0 1 0 0|0 0 1| octet-1 | octet-2 | octet-3 | 4318 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+---------------+ 4319 | octet-4 | octet-5 | octet-6 | octet-7 | 4320 +---------------+---------------+---------------+---------------+ 4322 A first cut at an EID allocation policy is as follows, where "r" is the 4323 two-bit relationship code (00 = this node, 01 = parent node, 10 = child 4324 node, 11 = reserved). 4326 6r0 00 00 00 00 00 00 "Wild" Node/Endpoint 4327 6r0 00 00 00 00 00 01 "This" Node/Endpoint 4328 6r0 00 00 00 00 00 02 thru 6r0 FF FF FF FF FF FF 48-bit administered 4329 6r1 00 00 00 00 00 00 thru 6r1 FF FF FF FF FF FF 48-bit reserved 4330 6r2 00 00 00 00 00 00 thru 6r2 FF FE|FF FF FF FF Reserved 4331 6r2 FF FF|00 00 00 00 thru 6r2 FF FF|FF FF FF FF Embedded IPv4 4332 6r3 00 00 00 00 00 00 thru 6r3 FF FF FF FF FF FF Embedded IEEE 802 4334 Note that NIDs and EIDs are taken from the same number space. EIDs have the 4335 "0x21" prefix and NIDs the "0x29" prefix. 4337 92 4338 11.4 Endpoint Name (NimFQDN) 4340 Endpoint names have the form of a fully qualified domain name (FQDN) and are 4341 represented by the NimFQDN object. Nimrod uses the user-friendly host name, 4342 e.g., www.nimrod.BBN.Com form. 4344 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4345 |F|0 0 1 1 1 1 0 0 0 0 0 1 1 0| obj len in octets | 4346 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+---------------+ 4347 : DNS Name : 4348 +---------------+---------------+---------------+---------------+ 4349 : DNS Name : pad (if nec.) : 4350 +---------------+---------------+---------------+---------------+ 4352 11.5 Node Identifier (NimNID) 4354 Nimrod uses a Node Identifier to identify a node in a topologically 4355 independent manner. Node identifiers are administratively assigned and are 4356 used to identify a node before the Nimrod bootstrapping process and the 4357 associated locator acquisition and update messages have determined the 4358 node's global locator. An NID may be thought of as an EID of a node (they 4359 come from the same number space). A node's policies are tagged by the 4360 node's NID. Each interface of a forwarding agent that provides connectivity 4361 across a node boundary has an associated sequence of NIDs that identify the 4362 nodes whose policies, both incoming and outgoing, must be enforced on that 4363 interface. Such an interface is termed a boundary forwarding agent. 4365 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4366 |F|0 1 0 1|0 0 1| octet-1 | octet-2 | octet-3 | 4367 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+---------------+ 4368 | octet-4 | octet-5 | octet-6 | octet-7 | 4369 +---------------+---------------+---------------+---------------+ 4371 11.6 Services (NimServ) 4373 Nimrod advertises, requests, and offers communication services through lists 4374 of communication parameters. Each parameter has its own object type code, 4375 length, and value. 4377 struct NimServ { 4378 NimOL2 idlen; /* Object type code and length */ 4379 NimMgmt mgmt; /* Management authority */ 4380 NimAuth auth; /* Authentication of authority */ 4381 NimLSrv orig_req; /* Opt: Service requested by orig*/ 4382 NimLSrv dest_req; /* Opt: Service requested by dest*/ 4384 93 4385 NimLSrv offered; /* Opt: Service offered*/ 4386 } 4388 struct NimLSrv { /* Object type code and length */ 4389 NimOL2 idlen; /* List of Service Parameter */ 4390 u_int32_t skd_id; /* Schedule id */ 4391 NimSrvP values[]; /* Set of parameters and values */ 4392 } 4394 struct NimSrvP { /* Service Parameter */ 4395 NimOL2 idlen; /* Object type code and length */ 4396 NIM_SRV_* 0x /* Service parameter */ 4397 u_int32_t value[]; /* Opt: Value of parameter */ 4398 } 4400 Service parameters include but are not limited to delay, throughput, 4401 probability of packet error, MTU, monetary cost of service, time at which 4402 the service is offered, organizations which may use the service, and 4403 characterization of traffic necessary to obtain the service. The 4404 availability of services is frequently restricted to certain time intervals, 4405 called schedules, especially when fees are being charged for the services. 4407 struct NimSked { 4408 NimOL2 idlen; /* Object type code and length */ 4409 u_int32_t skd_id; /* Schedule id, within context ... */ 4410 NimMgmt mgmt; /* ... of a management authority */ 4411 NimAuth auth; /* Authentication of authorizing entity*/ 4412 NimSkd1 sets[]; /* Opt: time intervals */ 4413 } /* Omitted means anytime */ 4415 struct NimSkd1 { 4416 NimOL2 idlen; /* Object type code and length */ 4417 u_int16_t flags; /* Periodic events */ 4418 int16_t tzone; /* Minutes from UTC */ 4419 NimSecs earliest, /* Bounding time, or 0 ... */ 4420 latest; /* ... or all 1's */ 4421 u_int16_t intervals[2*i]; /* Opt: Start and stop pairs, minutes 4422 from midnight */ 4423 } 4425 11.7 Maps (NimMap) 4427 struct NimMap { 4429 94 4430 NimOL2 idlen; /* Object type code and length */ 4432 u_int8_t kind; /* Kind of map */ 4433 u_int24_t seq; /* 24 LSB of generation NTP seconds */ 4434 /* Rollsover in 6 mo, longer than */ 4435 /* signature key lifetime */ 4436 NimLoc locs[]; /* Locator(s) of node represntd */ 4437 /* Makes component and connspec unique */ 4438 NimNID nid; /* NID of node */ 4439 NimAgnt agent; /* NR that produced the map */ 4440 NimSecs expires; /* When map expires, advisory */ 4441 NimLLoc adj_in, /* Adjacent incoming nodes */ 4442 adj_out; /* Adjacent outgoing nodes */ 4444 NimAuth abv_auth; /* Authenticator over abbreviated map */ 4446 /* Next 4 are only in Full map, either all present, or all omitted */ 4447 NimLCsp csp_in, /* Opt1: Set of incoming conn specs */ 4448 csp_out, /* Opt1: Set of outgoing conn specs */ 4449 csp_trnst; /* Opt1: Set of transit conn specs */ 4450 NimAuth full_auth; /*Opt1: Authenticator over full map */ 4451 /* (incl abv_auth) */ 4452 /* Next 5 are only in Basic map: */ 4453 /* appended child maps, NimMap len excludes child maps */ 4454 NimAuth basic_auth; /* Opt2:Authenticator over this map */ 4455 /* and appended child maps */ 4456 u_int32_t num_maps; /* Opt2: Number of appended maps */ 4457 /* of child nodes */ 4458 NimLElm chilren; /* Opt2: Elements of component nodes */ 4459 | 4460 /* Context is "locs", above */ 4461 NimLLoc adj_child; /* Opt2: Adjacent children nodes */ 4462 /* Service may be omitted if it appears (for same cspec_id) above */ 4463 NimLCsp topology; /* Opt2: Interconnectivity of node */ 4464 } 4466 11.8 Routes (NimRute) 4468 A route is used to identify, at the level of Nimrod nodes or forwarding 4469 agents, the communication components through which traffic from one endpoint 4470 to another endpoint should pass, where each endpoint is identified by its 4471 locator. It includes the type of route, such as unicast, multicast, 4472 sharable, and so on. Each hop in a route identifies the next node or 4473 forwarding agent through which traffic should be routed and the connectivity 4474 specification that should be used for that portion of the route. 4476 struct NimRute { 4477 NimOL2 idlen; /* Object type code and length */ 4479 95 4480 u_int32_t flags; /* multicast, unicast, etc. */ 4481 NimAuth auth; /* Authentication for generating 4482 route agent */ 4483 NimServ serv_req; /* Services required */ 4484 NimDRst drst; /* Opt: Restrictions on reuse of route */ 4485 NimServ offered; /* Services associated with route */ 4486 NimRutH hops[]; /* List of hops in route */ 4487 } 4489 struct NimRutH { 4490 NimOL2 idlen; /* Object type code and length */ 4491 u_int32_t cspec_id; /* Connectivity Specification Id */ 4492 NimLoc node; /* Next Node to pass through */ 4493 } 4495 11.9 Credentials (NimCred) 4497 struct NimCred { 4498 NimOL2 idlen; /* Object type code and length */ 4499 NimFQDN name; /* Who's credentials */ 4500 u_int32_t cred[]; /* Body of credentials */ 4501 } 4503 11.10 Path Labels (NimPLbl) 4505 struct NimPLbl { 4506 u_int32_t flag:1, /* Setup flag */ 4507 obj_id:7, /* Object type code */ 4508 label:24; /* Path label */ 4509 NimEID source; /* Opt: source EID, top level only */ 4510 } 4512 11.11 Time (NimSecs, NimNTP) 4514 struct NimSecs { 4515 NimOL2 idlen; /* Object type code and length */ 4516 u_int32_t seconds; /* Seconds */ 4517 } 4519 struct NimNTP { 4520 NimOL2 idlen; /* Object type code and length */ 4521 u_int32_t seconds; /* NTP Seconds */ 4522 u_int32_t fraction; /* NTP Fractional Seconds */ 4524 96 4525 } 4527 11.12 Authenticator (NimAuth) 4529 struct NimAuth { 4530 NimOL2 idlen; /* Object type code and length */ 4531 u_int16_t alg_id, /* Authentication algorithm id */ 4532 key_ftpt; /* Footprint of key, for key rollover */ 4533 NimFQDN signer; /* Opt: Identify of signer */ 4534 u_int8_t auth[16]; /* Authenticator, 16 for MD5 */ 4535 } 4537 The key footprint field specifies the least significant two bytes of the key 4538 used to form the authenticator; see [13]. It is used to identify which of 4539 the possible keys was used to form the authenticator. Multiple keys may be 4540 valid when keys are being changed. Having the footprint is an optimization 4541 that makes it possible to pick the right key without having to try each one 4542 until one works, or all possible keys fail. 4544 97 4545 12 Security Considerations 4547 Security issues for Nimrod are discussed in general in sections 2 and 3 and 4548 more specifically in the sections for the specific protocols and packet 4549 formats (section 9). 4551 13 Contact Information 4553 Ram Ramanathan Martha Steenstrup 4554 BBN Systems and Technologies BBN Systems and Technologies 4555 10 Moulton St. 10 Moulton St. 4556 Cambridge, MA 02138 Cambridge, MA 02138 4557 Ph: (617) 873-2736 Ph: (617) 873-3192 4558 email: ramanath@bbn.com email: msteenst@bbn.com 4560 98 4561 References 4563 [1]I. Castineyra, J.N. Chiappa and M. Steenstrup, ``The Nimrod 4564 Architecture'', Working Draft, March 1996. 4566 [2]M. Steenstrup, ``A Perspective on Nimrod Functionality'', Working 4567 Draft, March 1996. 4569 [3]S. Ramanathan, ``Mobility Support for Nimrod: Requirements and 4570 Solution Approaches'', Working Draft, March 1996. 4572 [4]S. Ramanathan, ``Multicast Support for Nimrod: Requirements and 4573 Solution Approaches'', Working Draft, March 1996. 4575 [5]C. Lynn, ``Nimrod Deployment'', Working Draft, March 1995. 4577 [6]D.L. Mills, ``Network Time Protocol (Version 3) Specification, 4578 Implementation and Analysis'', Internet RFC, Number 1305, March 1992. 4580 [7]J. Postel, ``Internet Protocol'', Internet RFC, Number 791, September 4581 1981. 4583 [8]J. Postel, ``Transmission Control Protocol'', Internet RFC, Number 793, 4584 September 1981. 4586 [9]R. Braden, ``Extending TCP for Transactions -- Concepts'', Internet 4587 RFC, Number 1379, November 1992. 4588 [10]R. Braden, ``T/TCP -- TCP Extensions for Transactions Functional 4589 Specification'', Internet RFC, Number 1664, July 1994. 4591 [11]R. Atkinson, ``IP Authentication Header'', Internet RFC, Number 1826, 4592 August 1995. 4594 [12]R. Atkinson, ``IP Encapsulating Security Payload (ESP)'', Internet RFC, 4595 Number 1827, August 1995. 4597 [13]S. Deering and R. Hinden, ``Internet Protocol, Version 6 (IPv6) 4598 Specification'', Internet RFC, Number 1883, January 1996. 4600 99