idnits 2.17.1 draft-ietf-manet-dsr-03.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 70 longer pages, the longest (page 0) being 59 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 71 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 10 instances of too long lines in the document, the longest one being 4 characters in excess of 72. == There are 1 instance of lines with non-RFC2606-compliant FQDNs in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- == The document seems to lack the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. (The document does seem to have the reference to RFC 2119 which the ID-Checklist requires). -- The exact meaning of the all-uppercase expression 'MAY NOT' is not defined in RFC 2119. If it is intended as a requirements expression, it should be rewritten using one of the combinations defined in RFC 2119; otherwise it should not be all-uppercase. == The expression 'MAY NOT', while looking like RFC 2119 requirements text, is not defined in RFC 2119, and should not be used. Consider using 'MUST NOT' instead (if that is what you mean). Found 'MAY NOT' in this paragraph: Path and flow identifiers are carried as an option inside the Hop-by-Hop options header. This option MAY NOT appear more than once in a single Hop-by-Hop Options header. -- 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 (22 October 1999) is 8946 days in the past. Is this intentional? 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: '0' is mentioned on line 1180, but not defined -- Looks like a reference, but probably isn't: 'NumAddrs' on line 1786 == Unused Reference: '23' is defined on line 2933, but no explicit reference was found in the text ** Obsolete normative reference: RFC 2581 (ref. '1') (Obsoleted by RFC 5681) -- Possible downref: Non-RFC (?) normative reference: ref. '4' ** Downref: Normative reference to an Informational RFC: RFC 2501 (ref. '5') ** Obsolete normative reference: RFC 2460 (ref. '6') (Obsoleted by RFC 8200) -- Possible downref: Non-RFC (?) normative reference: ref. '7' -- Possible downref: Non-RFC (?) normative reference: ref. '8' -- Possible downref: Non-RFC (?) normative reference: ref. '9' -- Possible downref: Non-RFC (?) normative reference: ref. '10' -- Possible downref: Non-RFC (?) normative reference: ref. '11' -- Possible downref: Non-RFC (?) normative reference: ref. '12' -- Possible downref: Non-RFC (?) normative reference: ref. '13' ** Obsolete normative reference: RFC 2002 (ref. '14') (Obsoleted by RFC 3220) -- Possible downref: Non-RFC (?) normative reference: ref. '15' ** Obsolete normative reference: RFC 793 (ref. '18') (Obsoleted by RFC 9293) -- Possible downref: Non-RFC (?) normative reference: ref. '19' ** Obsolete normative reference: RFC 1700 (ref. '20') (Obsoleted by RFC 3232) -- Possible downref: Non-RFC (?) normative reference: ref. '21' -- Possible downref: Non-RFC (?) normative reference: ref. '22' -- Possible downref: Non-RFC (?) normative reference: ref. '23' -- Possible downref: Non-RFC (?) normative reference: ref. '24' Summary: 9 errors (**), 0 flaws (~~), 8 warnings (==), 18 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 IETF MANET Working Group Josh Broch 2 INTERNET-DRAFT David B. Johnson 3 David A. Maltz 4 Carnegie Mellon University 5 22 October 1999 7 The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks 9 11 Status of This Memo 13 This document is an Internet-Draft and is in full conformance with 14 all provisions of Section 10 of RFC 2026 except that the right to 15 produce derivative works is not granted. 17 Internet-Drafts are working documents of the Internet Engineering 18 Task Force (IETF), its areas, and its working groups. Note 19 that other groups may also distribute working documents as 20 Internet-Drafts. 22 Internet-Drafts are draft documents valid for a maximum of six months 23 and may be updated, replaced, or obsoleted by other documents at 24 any time. It is inappropriate to use Internet-Drafts as reference 25 material or to cite them other than as "work in progress." 27 The list of current Internet-Drafts can be accessed at 28 http://www.ietf.org/ietf/1id-abstracts.txt 30 The list of Internet-Draft Shadow Directories can be accessed at 31 http://www.ietf.org/shadow.html. 33 Abstract 35 Dynamic Source Routing (DSR) is a routing protocol designed 36 specifically for use in mobile ad hoc networks. The protocol allows 37 nodes to dynamically discover a source route across multiple network 38 hops to any destination in the ad hoc network. When using source 39 routing, each packet to be routed carries in its header the complete, 40 ordered list of nodes through which the packet must pass. A key 41 advantage of source routing is that intermediate hops do not need 42 to maintain routing information in order to route the packets they 43 receive, since the packets themselves already contain all of the 44 necessary routing information. This, coupled with the dynamic, 45 on-demand nature of DSR's Route Discovery, completely eliminates the 46 need for periodic router advertisements and link status packets, 47 significantly reducing the overhead of DSR, especially during periods 48 when the network topology is stable and these packets serve only as 49 keep-alives. 51 Contents 53 Status of This Memo i 55 Abstract i 57 1. Introduction 1 59 2. Changes 1 61 3. Assumptions 1 63 4. Terminology 2 64 4.1. General Terms . . . . . . . . . . . . . . . . . . . . . . 2 65 4.2. Specification Language . . . . . . . . . . . . . . . . . 4 67 5. Protocol Overview 5 68 5.1. Route Discovery and Route Maintenance . . . . . . . . . . 5 69 5.2. Packet Forwarding . . . . . . . . . . . . . . . . . . . . 6 70 5.3. Multicast Routing . . . . . . . . . . . . . . . . . . . . 7 72 6. Conceptual Data Structures 7 73 6.1. Route Cache . . . . . . . . . . . . . . . . . . . . . . . 7 74 6.2. Route Request Table . . . . . . . . . . . . . . . . . . . 9 75 6.3. Send Buffer . . . . . . . . . . . . . . . . . . . . . . . 9 76 6.4. Retransmission Buffer . . . . . . . . . . . . . . . . . . 9 78 7. Packet Formats 11 79 7.1. Destination Options Headers . . . . . . . . . . . . . . . 11 80 7.1.1. DSR Route Request Option . . . . . . . . . . . . 12 81 7.2. Hop-by-Hop Options Headers . . . . . . . . . . . . . . . 14 82 7.2.1. DSR Route Reply Option . . . . . . . . . . . . . 15 83 7.2.2. DSR Route Error Option . . . . . . . . . . . . . 17 84 7.2.3. DSR Acknowledgment Option . . . . . . . . . . . . 18 85 7.3. DSR Routing Header . . . . . . . . . . . . . . . . . . . 20 87 8. Detailed Operation 23 88 8.1. Originating a Data Packet . . . . . . . . . . . . . . . . 23 89 8.2. Originating a Packet with a DSR Routing Header . . . . . 23 90 8.3. Processing a Routing Header . . . . . . . . . . . . . . . 24 91 8.4. Route Discovery . . . . . . . . . . . . . . . . . . . . . 25 92 8.4.1. Originating a Route Request . . . . . . . . . . . 25 93 8.4.2. Processing a Route Request Option . . . . . . . . 26 94 8.4.3. Generating Route Replies using the Route Cache . 27 95 8.4.4. Originating a Route Reply . . . . . . . . . . . . 28 96 8.4.5. Processing a Route Reply Option . . . . . . . . . 29 98 8.5. Route Maintenance . . . . . . . . . . . . . . . . . . . . 30 99 8.5.1. Using Network-Layer Acknowledgments . . . . . . . 30 100 8.5.2. Using Link Layer Acknowledgments . . . . . . . . 32 101 8.5.3. Originating a Route Error . . . . . . . . . . . . 32 102 8.5.4. Processing a Route Error Option . . . . . . . . . 33 103 8.5.5. Salvaging a Packet . . . . . . . . . . . . . . . 33 105 9. Optimizations 35 106 9.1. Leveraging the Route Cache . . . . . . . . . . . . . . . 35 107 9.1.1. Promiscuous Learning of Source Routes . . . . . . 35 108 9.2. Preventing Route Reply Storms . . . . . . . . . . . . . . 36 109 9.3. Piggybacking on Route Discoveries . . . . . . . . . . . . 37 110 9.4. Discovering Shorter Routes . . . . . . . . . . . . . . . 37 111 9.5. Rate Limiting the Route Discovery Process . . . . . . . . 38 112 9.6. Improved Handling of Route Errors . . . . . . . . . . . . 39 113 9.7. Increasing Scalability . . . . . . . . . . . . . . . . . 39 115 10. Path-State and Flow-State Mechanisms 40 116 10.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . 40 117 10.2. Path-State and Flow-State Identifiers . . . . . . . . . . 41 118 10.3. Path-State Creation, Use, and Maintenance . . . . . . . . 42 119 10.3.1. Creating Path-State for Routing . . . . . . . . . 42 120 10.3.2. Monitoring Characteristics of the Path . . . . . 43 121 10.3.3. Candidate Metrics . . . . . . . . . . . . . . . . 45 122 10.4. Flow-State Creation, Use, and Maintenance . . . . . . . . 46 123 10.4.1. Requesting Promises along Existing Paths . . . . 46 124 10.4.2. Requesting Promises as Part of Route Discovery . 48 125 10.4.3. Providing Notifications of Changing Path Metrics 49 126 10.5. Expiration of State from Intermediate Nodes . . . . . . . 50 127 10.6. Packet Formats . . . . . . . . . . . . . . . . . . . . . 51 128 10.6.1. Identifier Option . . . . . . . . . . . . . . . . 51 129 10.6.2. Path-Metrics Option . . . . . . . . . . . . . . . 52 130 10.6.3. Flow Request Option . . . . . . . . . . . . . . . 54 131 10.6.4. Encoding Path-Metrics . . . . . . . . . . . . . . 55 133 11. Constants 58 135 12. IANA Considerations 59 137 13. Security Considerations 60 139 Location of DSR Functions in the ISO Model 61 141 Implementation Status 62 143 Acknowledgments 63 145 References 64 147 Chair's Address 66 148 Authors' Addresses 67 149 1. Introduction 151 This document describes Dynamic Source Routing (DSR) [8, 9], a 152 protocol developed by the Monarch Project [10, 19] at Carnegie Mellon 153 University for routing packets in a mobile ad hoc network [5]. 155 Source routing is a routing technique in which the sender of a packet 156 determines the complete sequence of nodes through which to forward 157 the packet; the sender explicitly lists this route in the packet's 158 header, identifying each forwarding "hop" by the address of the next 159 node to which to transmit the packet on its way to the destination 160 node. 162 DSR offers a number of potential advantages over other routing 163 protocols for mobile ad hoc networks. First, DSR uses no periodic 164 routing messages of any kind (e.g., no router advertisements and no 165 link-level neighbor status messages), thereby significantly reducing 166 network bandwidth overhead, conserving battery power, reducing the 167 probability of packet collision, and avoiding the propagation of 168 potentially large routing updates throughout the ad hoc network. Our 169 Dynamic Source Routing protocol is able to adapt quickly to changes 170 such as node movement, yet requires no routing protocol overhead 171 during periods in which no such changes occur. 173 In addition, DSR has been designed to compute correct routes in 174 the presence of asymmetric (uni-directional) links. In wireless 175 networks, links may at times operate asymmetrically due to sources 176 of interference, differing radio or antenna capabilities, or the 177 intentional use of asymmetric communication technology such as 178 satellites. Due to the existence of asymmetric links, traditional 179 link-state or distance vector protocols may compute routes that do 180 not work. DSR, however, will always find a correct route even in the 181 presence of asymmetric links. 183 2. Changes 185 Changes from version 02 to version 03 (10/1999) 187 - Added description of path-state and flow-state maintenance 188 (Section 10). These extensions remove the need for every 189 data packet to carry a source route, thereby decreasing 190 the byte-overhead of DSR. They also provide a framework for 191 supporting QoS inside DSR networks. 193 3. Assumptions 195 We assume that all nodes wishing to communicate with other nodes 196 within the ad hoc network are willing to participate fully in the 197 protocols of the network. In particular, each node participating in 198 the network should also be willing to forward packets for other nodes 199 in the network. 201 We refer to the minimum number of hops necessary for a packet to 202 reach from any node located at one extreme edge of the network to 203 another node located at the opposite extreme, as the diameter of the 204 network. We assume that the diameter of an ad hoc network will be 205 small (e.g., perhaps 5 or 10 hops), but may often be greater than 1. 207 Packets may be lost or corrupted in transmission on the wireless 208 network. A node receiving a corrupted packet can detect the error 209 and discard the packet. 211 We assume that nodes can enable promiscuous receive mode on their 212 wireless network interface hardware, causing the hardware to 213 deliver every received packet to the network driver software without 214 filtering based on link-layer destination address. Although we do 215 not require this facility, it is for example common in current LAN 216 hardware for broadcast media including wireless, and some of our 217 optimizations take advantage of its availability. Use of promiscuous 218 mode does increase the software overhead on the CPU, but we believe 219 that wireless network speeds are more the inherent limiting factor 220 to performance in current and future systems. We also believe 221 that portions of the protocol are also suitable for implementation 222 directly within a programmable network interface unit to avoid this 223 overhead on the CPU. 225 4. Terminology 227 4.1. General Terms 229 link 231 A communication facility or medium over which nodes can 232 communicate at the link layer, such as an Ethernet (simple or 233 bridged). A link is the layer immediately below IP. 235 interface 237 A node's attachment to a link. 239 prefix 241 A bit string that consists of some number of initial bits of an 242 address. 244 interface index 246 An 7-bit quantity which uniquely identifies an interface among 247 a given node's interfaces. Each node can assign interface 248 indices to its interfaces using any scheme it wishes. 250 The index IF_INDEX_MA is reserved for use by Mobile IP [14] 251 mobility agents (home or foreign agents) to indicate that they 252 believe they can reach a destination via a connected internet 253 infrastructure. The index IF_INDEX_ROUTER is reserved for 254 use by routers not acting as Mobile IP mobility agents to 255 indicate that they believe they can reach the destination via a 256 connected internet infrastructure. 258 The distinction between the index for mobility agents and 259 the index for routers, allows mobility agents to advertise 260 their existence ``for free''. A node that processes a routing 261 header listing the interface index IF_INDEX_MA, can then send 262 a unicast Agent Solicitation to the corresponding address in 263 the routing header to obtain complete information about the 264 mobility services being provided. 266 link-layer address 268 A link-layer identifier for an interface, such as IEEE 802 269 addresses on Ethernet links. 271 packet 273 An IP header plus payload. 275 piggybacking 277 Including two or more conceptually different types of data in 278 the same packet so that all data elements move through the 279 network together. 281 home address 283 An IP address that is assigned for an extended period of time 284 to a mobile node. It remains unchanged regardless of where 285 the node is attached to the Internet [14]. If a node has more 286 than one home address, it SHOULD select and use a single home 287 address when participating in the ad hoc network. 289 source route 291 A source route from a node S to some node D is an ordered list 292 of home addresses and interface indexes that contains all the 293 information that would be needed to forward a packet through 294 the ad hoc network. For each node that will transmit the 295 packet, the source route provides the index of the interface 296 over which the packet should be transmitted, and the address of 297 the node which is intended to receive the packet. 299 DSR Routing Headers as described in Section 7.3 use a more 300 compact encoding of the source route and do not explicitly list 301 address S in the Routing Header`, since it is carried as the IP 302 Source Address of the packet. 304 A source route is described as ``broken'' when the specific 305 path it describes through the network is not actually viable. 307 Route Discovery 309 The method in DSR by which a node S dynamically obtains a 310 source route to some node D that will be used by S to route 311 packets through the network to D. Performing a Route Discovery 312 involves sending one or more Route Request packets. 314 Route Maintenance 316 The process in DSR of monitoring the status of a source route 317 while in use, so that any link-failures along the source route 318 can be detected and the broken link removed from use. 320 4.2. Specification Language 322 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 323 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 324 document are to be interpreted as described in RFC 2119 [3]. 326 5. Protocol Overview 328 5.1. Route Discovery and Route Maintenance 330 A source routing protocol must solve two challenges, which DSR terms 331 Route Discovery and Route Maintenance. Route Discovery is the 332 mechanism whereby a node S wishing to send a packet to a destination 333 D obtains a source route to D. 335 Route Maintenance is the mechanism whereby S is able to detect, while 336 using a source route to D, if the network topology has changed such 337 that it can no longer use its route to D because a link along the 338 route no longer works. When Route Maintenance indicates a source 339 route is broken, S can attempt to use any other route it happens to 340 know to D, or can invoke Route Discovery again to find a new route. 342 To perform Route Discovery, the source node S link-layer broadcasts 343 a Route Request packet. Here, node S is termed the initiator of the 344 Route Discovery, and the node to which S is attempting to discover a 345 source route, say D, is termed the target of the Discovery. 347 Each node that hears the Route Request packet forwards a copy of the 348 Request, if appropriate, by adding its own address to a source route 349 being recorded in the Request packet and then rebroadcasting the 350 Route Request. 352 The forwarding of Route Requests is constructed so that copies of the 353 Request propagate hop-by-hop outward from the node initiating the 354 Route Discovery, until either the target of the Request is found or 355 until another node is found that can supply a route to the target. 357 The basic mechanism of forwarding Route Requests forwards the Request 358 if the node (1) is not the target of the Request, (2) is not already 359 listed in the recorded source route in this copy of the Request, and 360 (3) has not recently seen another Route Request packet belonging to 361 this same Route Discovery. A node can determine if it has recently 362 seen such a Route Request, since each Route Request packet contains 363 a unique identifier for this Route Discovery, generated by the 364 initiator of the Discovery. Each node maintains an LRU cache of the 365 unique identifier from each recently received Route Request. By not 366 propagating any copies of a Request after the first, the overhead of 367 forwarding additional copies that reach this node along different 368 paths is avoided. 370 In addition, the Time-to-Live field in the IP header of the packet 371 carrying the Route Request MAY be used to limit the scope over which 372 the Request will propagate, using the normal behavior of Time-to-Live 373 defined by IP [17, 2]. Additional optimizations on the handling and 374 forwarding of Route Requests are also used to further reduce the 375 Route Discovery overhead. 377 When the target of the Request (e.g., node D) receives the Route 378 Request, the recorded source route in the Request identifies the 379 sequence of hops over which this copy of the Request reached D. 380 Node D copies this recorded source route into a Route Reply packet 381 and sends this Route Reply back to the initiator of the Route Request 382 (e.g., node S). 384 All source routes learned by a node are kept in a Route Cache, which 385 is used to further reduce the cost of Route Discovery. When a node 386 wishes to send a packet, it examines its own Route Cache and performs 387 Route Discovery only if no suitable source route is found in its 388 Cache. 390 Further, when some intermediate node B receives a Route Request from 391 S for some target node D, B not equal D, B searches its own Route 392 Cache for a route to D. If B finds such a route, it might not have 393 to propagate the Route Request, but instead return a Route Reply to 394 node S based on the concatenation of the recorded source route from 395 S to B in the Route Request and the cached route from B to D. The 396 details of replying from a Route Cache in this way are discussed in 397 Section 9.1. 399 As a node overhears routes being used by others, either on data 400 packets or on control packets used by Route Discovery or Route 401 Maintenance, the node MAY insert those routes into its Route Cache, 402 leveraging the Route Discovery operations of the other nodes in 403 the network. Such route information MAY be learned either by 404 promiscuously snooping on packets or when forwarding packets. 406 5.2. Packet Forwarding 408 To represent a source route within a packet's header, DSR uses a 409 Routing Header similar to the Routing Header format specified for 410 IPv6, adapted to the needs of DSR and to the use of DSR in IPv4 (or 411 in IPv6 in the future). The DSR Routing Header uses a unique Routing 412 Type field value to distinguish it from the existing Type 0 Routing 413 Header defined within IPv6 [6]. 415 To forward a packet, a receiving node N simply processes the Routing 416 Header as specified in Section 8.3 and transmits the packet to 417 the next hop. If a forwarding error occurs along the link to the 418 next hop in the route, this node N sends a Route Error back to the 419 originator S of this packet informing S that this link is "broken". 420 If node N's Route Cache contains a different route to the destination 421 of the original packet, then the packet is salvaged using the new 422 source route (Section 8.5.5). Otherwise, the packet is dropped. 424 Each node overhearing or forwarding a Route Error packet also 425 removes from its Route Cache the link indicated to be broken, thereby 426 cleaning the stale cache data from the network. 428 5.3. Multicast Routing 430 At this time DSR does not support true multicasting. However, it 431 does support the controlled flooding of a data packet to all nodes in 432 the network that are within some number of hops of the originator. 433 While this mechanism does not support pruning of the broadcast 434 tree to conserve network resources, it can be used to distribute 435 information to nodes in the network. 437 When an application on a DSR node sends a packet to a multicast 438 address, DSR piggybacks the data from the packet inside a Route 439 Request packet targeted at the multicast address. The normal Route 440 Request distribution scheme described in Sections 5.1 and 8.4.2 441 will result in this packet being efficiently distributed to all 442 nodes in the network within the specified TTL of the originator. 443 The receiving nodes can then do destination address filtering on 444 the packet, discarding it if they do not wish to receive multicast 445 packets destined to this multicast address. 447 6. Conceptual Data Structures 449 In order to participate in the Dynamic Source Routing Protocol, a 450 node needs four conceptual data structures: a Route Cache, a Route 451 Request Table, a Send Buffer, and a Retransmission Buffer. These 452 data structures MAY be implemented in any manner consistent with the 453 external behavior described in this document. 455 6.1. Route Cache 457 All routing information needed by a node participating in an ad hoc 458 network using DSR is stored in a Route Cache. Each node in the 459 network maintains its own Route Cache. The node adds information 460 to the Cache as it learns of new links between nodes in the ad hoc 461 network, for example through packets carrying either a Route Reply or 462 a Routing Header. Likewise, the node removes information from the 463 cache as it learns existing links in the ad hoc network have broken, 464 for example through packets carrying a Route Error or through the 465 link-layer retransmission mechanism reporting a failure in forwarding 466 a packet to its next-hop destination. The Route Cache is indexed 467 logically by destination node address, and supports the following 468 operations: 470 void Insert(Route RT) 472 Inserts information extracted from source route RT into the 473 Route Cache. 475 Route Get(Node DEST) 477 Returns a source route from this node to DEST (if one is 478 known). 480 void Delete(Node FROM, Interface INDEX, Node TO) 482 Removes from the route cache any routes which assume that a 483 packet transmitted by node FROM over its interface with the 484 given INDEX will be received by node TO. 486 Each implementation MAY choose the cache replacement and cache search 487 strategies for its Route Cache that are most appropriate for its 488 particular network environment. For example, some environments may 489 choose to return the shortest route to a node (the shortest sequence 490 of hops), while others may select an alternate metric for the Get() 491 operation. 493 The Route Cache SHOULD support storing more than one source route for 494 each destination. 496 If there are multiple cached routes to a destination, the Route Get() 497 operation SHOULD prefer routes that do not traverse a hop with an 498 interface index of IF_INDEX_MA or IF_INDEX_ROUTER. This will prefer 499 routes that lead directly to the target node over routes that attempt 500 to reach the target via any internet infrastructure connected to the 501 ad hoc network. 503 If a node S is using a source route to some destination D that 504 includes intermediate node N, S SHOULD shorten the route to 505 destination D when it learns of a shorter route to node N than the 506 one that is listed as the prefix of its current route to D. 508 A node S using a source route to destination D through intermediate 509 node N, MAY shorten the source route if it learns of a shorter path 510 from node N to node D. 512 The Route Cache replacement policy SHOULD allow routes to be 513 categorized based upon "preference", where routes with a higher 514 preferences are less likely to be removed from the cache. For 515 example, a node could prefer routes for which it initiated a Route 516 Discovery over routes that it learned as the result of promiscuous 517 snooping on other packets. In particular, a node SHOULD prefer 518 routes that it is presently using over those that it is not. 520 6.2. Route Request Table 522 The Route Request Table is a collection of records about Route 523 Request packets that were recently originated or forwarded by this 524 node. The table is indexed by the home address of the target of the 525 route discovery. A record maintained on node S for node D contains 526 the following: 528 - The time that S last originated a Route Discovery for D. 530 - The remaining amount of time that S must wait before the next 531 attempt at a Route Discovery for D. 533 - The Time-to-live (TTL) field in the IP header of last Route 534 Request originated by S for D. 536 - A FIFO cache of the last ID_FIFO_SIZE Identification values from 537 Route Request packets targeted at node D that were forwarded by 538 this node. 540 Nodes SHOULD use an LRU policy to manage the entries of in their 541 Route Request Table. 543 ID_FIFO_SIZE MUST NOT be set to an unlimited value, since, in the 544 worst case, when a node crashes and reboots the first ID_FIFO_SIZE 545 Route Request packets it sends may appear to be duplicates to the 546 other nodes in the network. 548 6.3. Send Buffer 550 The Send Buffer of some node is a queue of packets that cannot be 551 transmitted by that node because it does not yet have a source 552 route to each respective packet's destination. Each packet in the 553 Send Buffer is stamped with the time that it is placed into the 554 Buffer, and SHOULD be removed from the Send Buffer and discarded 555 SEND_BUFFER_TIMEOUT seconds after initially being placed in the 556 Buffer. If necessary, a FIFO strategy SHOULD be used to evict 557 packets before they timeout to prevent the buffer from overflowing. 559 Subject to the rate limiting defined in Section 8.4, a Route 560 Discovery SHOULD be initiated as often as possible for the 561 destination address of any packets residing in the Send Buffer. 563 6.4. Retransmission Buffer 565 The Retransmission Buffer of a node is a queue of packets sent by 566 this node that are awaiting the receipt of an acknowledgment from the 567 next hop in the source route (Section 7.3). 569 For each packet in the Retransmission Buffer, a node maintains (1) a 570 count of the number of retransmissions and (2) the time of the last 571 retransmission. 573 Packets are removed from the buffer when an acknowledgment 574 is received, or when the number of retransmissions exceeds 575 DSR_MAXRXTSHIFT. In the later case, the removal of the packet from 576 the Retransmission Buffer SHOULD result in a Route Error being 577 returned to the initial source of the packet (Section 8.5). 579 7. Packet Formats 581 Dynamic Source Routing makes use of four options carrying control 582 information that can be piggybacked in any existing IP packet. 584 The mechanism used for these options is based on the design of the 585 Hop-by-Hop and Destination Options mechanisms in IPv6 [6]. The 586 ability to generate and process such options must be added to an IPv4 587 protocol stack. Specifically, the Protocol field in the IP header 588 is used to indicate that a Hop-by-Hop Options or Destination Options 589 extension header exists between the IP header and the remaining 590 portion of a packet's payload (such as a transport layer header). 591 The Next Header field in each extension header will then indicate the 592 type of header that follows it in a packet. 594 7.1. Destination Options Headers 596 The Destination Options header is used to carry optional information 597 that need be examined only by a packet's destination node(s). The 598 Destination Options header is identified by a Next Header (or 599 Protocol) value of 60 in the immediately preceding header, and has 600 the following format: 602 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 603 | Next Header | Hdr Ext Len | | 604 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 605 | | 606 . . 607 . Options . 608 . . 609 | | 610 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 612 Next Header 614 8-bit selector. Identifies the type of header immediately 615 following the Destination Options header. Uses the same values 616 as the IPv4 Protocol field [20]. 618 Hdr Ext Len 620 8-bit unsigned integer. Length of the Destination Options 621 header in 4-octet units, not including the first 8 octets. 623 Options 625 Variable-length field, of length such that the complete 626 Destination Options header is an integer multiple of 4 octets 627 long. Contains one or more TLV-encoded options. 629 The following destination option is used by the Dynamic Source 630 Routing protocol: 632 - DSR Route Request option (Section 7.1.1) 634 This destination option MUST NOT appear multiple times within a 635 single Destination Options header. 637 7.1.1. DSR Route Request Option 639 The DSR Route Request destination option is encoded in 640 type-length-value (TLV) format as follows: 642 0 1 2 3 643 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 644 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 645 | Option Type | Option Length | Identification | 646 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 647 | Target Address | 648 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 649 |C| IN Index[1] |C| IN Index[2] |C| IN Index[3] |C| IN Index[4] | 650 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 651 |C|OUT Index[1] |C|OUT Index[2] |C|OUT Index[3] |C|OUT Index[4] | 652 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 653 | Address[1] | 654 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 655 | Address[2] | 656 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 657 | Address[3] | 658 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 659 | Address[4] | 660 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 661 |C| IN Index[5] |C| IN Index[6] |C| IN Index[7] |C| IN Index[8]| 662 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 663 |C|OUT Index[5] |C|OUT Index[6] |C| OUT Index[7] |C|OUT Index[8]| 664 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 665 | Address[5] | 666 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 667 | ... | 668 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 670 IP fields: 672 Source Address 674 MUST be the home address of the node originating this packet. 675 Intermediate nodes that repropagate the request do not change 676 this field. 678 Destination Address 680 MUST be the limited broadcast address (255.255.255.255). 682 Hop Limit (TTL) 684 Can be varied from 1 to 255, for example to implement 685 expanding-ring searches. 687 Route Request fields: 689 Option Type 691 ???. A node that does not understand this option MUST discard 692 the packet and the Option Data may change en-route (the top 693 three bits are 011). 695 Option Length 697 8-bit unsigned integer. Length of the option, in octets, 698 excluding the Option Type and Option Length fields. 700 Identification 702 A unique value generated by the initiator (original sender) 703 of the Route Request. This value allows a recipient to 704 determine whether or not it has recently seen this a copy of 705 this Request; if it has, the packet is simply discarded. When 706 propagating a Route Request, this field MUST be copied from the 707 received copy of the Request being forwarded. 709 Target Address 711 The home address of the node that is the target of the Route 712 Request. 714 Change Interface (C) bit[1..n] 716 A flag associated with each interface index that indicates 717 whether or not the corresponding node repropagated the Request 718 over a different physical interface type than over which it 719 received the Request. 721 IN Index[1..n] 723 IN Index[i] is the index of the interface over which the node 724 indicated by Address[i] received the Route Request option. 725 These are used to record a reverse route from the target of 726 the request to the originator, over which a Route Reply MAY be 727 sent. 729 OUT Index[1..n] 731 OUT Index[i] is the interface index that the node indicated by 732 Address[i-1] used when rebroadcasting the Route Request option. 734 Address[1..n] 736 Address[i] is the home address of the ith hop recorded in the 737 Route Request option. 739 7.2. Hop-by-Hop Options Headers 741 The Hop-by-Hop Options header is used to carry optional information 742 that must be examined by every node along a packet's delivery path. 743 The Hop-by-Hop Options header is identified by a Next Header (or 744 Protocol) value of ??? in the IP header, and has the following 745 format: 747 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 748 | Next Header | Hdr Ext Len | | 749 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 750 | | 751 . . 752 . Options . 753 . . 754 | | 755 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 757 Next Header 759 8-bit selector. Identifies the type of header immediately 760 following the Hop-by-Hop Options header. Uses the same values 761 as the IPv4 Protocol field [20]. 763 Hdr Ext Len 765 8-bit unsigned integer. Length of the Hop-by-Hop Options 766 header in 4-octet units, not including the first 8 octets. 768 Options 770 Variable-length field, of length such that the complete 771 Hop-by-Hop Options header is an integer multiple of 4 octets 772 long. Contains one or more TLV-encoded options. 774 The following hop-by-hop options are used by the Dynamic Source 775 Routing protocol: 777 - DSR Route Reply option (Section 7.2.1) 779 - DSR Route Error option (Section 7.2.2) 781 - DSR Acknowledgment option (Section 7.2.3) 783 All of these destination options MAY appear one or more times within 784 a single Hop-by-Hop Options header. 786 7.2.1. DSR Route Reply Option 788 The DSR Route Reply hop-by-hop option is encoded in type-length-value 789 (TLV) format as follows: 791 0 1 2 3 792 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 793 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 794 | Option Type | Option Length | Reserved | 795 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 796 | Target Address | 797 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 798 |C|OUT Index[1] |C|OUT Index[2] |C|OUT Index[3] |C|OUT Index[4] | 799 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 800 | Address[1] | 801 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 802 | Address[2] | 803 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 804 | Address[3] | 805 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 806 | Address[4] | 807 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 808 |C|OUT Index[5] |C|OUT Index[6] |C|OUT Index[7] |C|OUT Index[8] | 809 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 810 | Address[5] | 811 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 812 | ... | 813 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 814 Option Type 816 ???. A node that does not understand this option should ignore 817 this option and continue processing the packet, and the Option 818 Data does not change en-route (the top three bits are 000). 820 Option Length 822 8-bit unsigned integer. Length of the option, in octets, 823 excluding the Option Type and Option Length fields. 825 Reserved 827 Sent as 0; ignored on reception. 829 Target Address 831 The home address of the node to which the Route Reply must be 832 delivered. 834 Change Interface (C) bit[1..n] 836 If the C bit associated with a node N is set, it implies N will 837 be forwarding the packet out a different interface than the one 838 over which it was received (i.e., the node sending the packet 839 to N should not expect a passive acknowledgment). 841 OUT Index[1..n] 843 OUT Index[i] is the interface index of the ith hop listed in 844 the Route Reply option. It denotes the interface that should 845 be used by Address[i-1] to reach Address[i] when using the 846 specified source route. 848 Address[1..n] 850 Address[i] is the home address of the ith hop listed in the 851 Route Reply option. 853 7.2.2. DSR Route Error Option 855 The DSR Route Error hop-by-hop option is encoded in type-length-value 856 (TLV) format as follows: 858 0 1 2 3 859 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 860 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 861 | Option Type | Option Length | Index | Error Type | 862 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 863 | Error Source Address | 864 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 865 | Error Destination Address | 866 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 867 | Unreachable Node Address | 868 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 870 Option Type 872 ???. A node that does not understand this option should ignore 873 the option and continue processing the packet, and the Option 874 Data does not change en-route (the top three bits are 000). 876 Option Length 878 8-bit unsigned integer. Length of the option, in octets, 879 excluding the Option Type and Option Length fields. 881 Index 883 The interface index of the network interface over which the 884 node designated by Error Source Address tried to forward a 885 packet to the node designated by Unreachable Node Address. 887 Error Type 889 The type of error encountered. Values between 0 and 127 890 inclusive indicate a hard failure of connectivity between the 891 Error Source Address and the Unreachable Node Address. Values 892 between 128 and 255 inclusive indicate a soft failure. 894 NODE_UNREACHABLE 1 896 PATH_STATE_NOT_FOUND 129 898 Error Source Address 900 The home address of the node originating the Route Error (e.g., 901 the node that attempted to forward a packet and discovered the 902 link failure). 904 Error Destination Address 906 The home address of the node to which the Route Error must be 907 delivered (e.g, the node that generated the routing information 908 claiming that the hop Error Source Address to Unreachable Node 909 Address was a valid hop). 911 Unreachable Node Address 913 The home address of the node that was found to be unreachable 914 (the next hop neighbor to which the node at ``Error Source 915 Address'' was attempting to transmit the packet). 917 7.2.3. DSR Acknowledgment Option 919 The DSR Acknowledgment hop-by-hop option is encoded in 920 type-length-value (TLV) format as follows: 922 0 1 2 3 923 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 924 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 925 | Option Type | Option Length | 926 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 927 | Identification | 928 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 929 | ACK Source Address | 930 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 931 | ACK Destination Address | 932 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 933 | Data Source Address | 934 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 936 Option Type 938 ???. A node that does not understand this option should ignore 939 the option and continue processing the packet, and the Option 940 Data does not change en-route (the top three bits are 000). 942 Option Length 944 8-bit unsigned integer. Length of the option, in octets, 945 excluding the Option Type and Option Length fields. 947 Identification 949 A 32-bit value that when taken in conjunction with Data Source 950 Address, uniquely identifies the packet being acknowledged. 952 The Identification value is computed as ((ip_id << 16) | ip_off) 953 where ip_id is the value of the 16-bit Identification field in 954 the IP header of the packet being acknowledged, and ip_off is 955 the value of the 13-bit Fragment Offset field in the IP header 956 of the packet being acknowledged. 958 When constructing the Identification, ip_id and ip_off MUST be 959 in host byte-order. The entire Identification value MUST then 960 be converted to network byte-order before being placed in the 961 Acknowledgment option. 963 ACK Source Address 965 The home address of the node originating the Acknowledgment. 967 ACK Destination Address 969 The home address of the node to which the Acknowledgment must 970 be delivered. 972 Data Source Address 974 The IP Source Address of the packet being acknowledged. 976 7.3. DSR Routing Header 978 As specified for IPv6 [6], a Routing header is used by a source to 979 list one or more intermediate nodes to be ``visited'' on the way to 980 a packet's destination. This function is similar to IPv4's Loose 981 Source and Record Route option, but the Routing header does not 982 record the route taken as the packet is forwarded. The specific 983 processing steps required to implement the Routing header must be 984 added to an IPv4 protocol stack. The Routing header is identified by 985 a Next Header value of 43 in the immediately preceding header, and 986 has the following format: 988 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 989 | Next Header | Hdr Ext Len | Routing Type | Segments Left | 990 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 991 | | 992 . . 993 . type-specific data . 994 . . 995 | | 996 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 998 The type specific data for a Routing Header carrying a DSR Source 999 Route is: 1001 0 1 2 3 1002 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1003 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1004 |R|S| Reserved | 1005 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1006 |C|OUT Index[1] |C|OUT Index[2] |C|OUT Index[3] |C|OUT Index[4] | 1007 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1008 | Address[1] | 1009 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1010 | Address[2] | 1011 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1012 | Address[3] | 1013 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1014 | Address[4] | 1015 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1016 |C|OUT Index[5] |C|OUT Index[6] |C|OUT Index[7] |C|OUT Index[8] | 1017 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1018 | Address[5] | 1019 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1020 | ... | 1021 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1022 Routing Header Fields: 1024 Next Header 1026 8-bit selector. Identifies the type of header immediately 1027 following the Routing header. 1029 Hdr Ext Len 1031 8-bit unsigned integer. Length of the Routing header in 1032 4-octet units, not including the first 8 octets. 1034 Routing Type 1036 ??? 1038 Segments Left 1040 Number of route segments remaining, i.e., number of explicitly 1041 listed intermediate nodes still to be visited before reaching 1042 the final destination. 1044 Type Specific Fields: 1046 Acknowledgment Request (R) 1048 The Acknowledgment Request (R) bit is set to request an 1049 explicit acknowledgment from the next hop. After processing 1050 the Routing Header, The IP Destination Address lists the 1051 address of the next hop. 1053 Salvaged Packet (S) 1055 The Salvaged Packet (S) bit indicates that this packet has been 1056 salvaged by an intermediate node, and thus that this Routing 1057 Header was generated by Address[1] and not the IP Source 1058 Address (Section 8.5.5). 1060 Reserved 1062 Sent as 0; ignored on reception. 1064 Change Interface (C) bit[1..n] 1066 If the C bit associated with a node N is set, it implies N will 1067 be forwarding the packet out a different interface than the one 1068 over which it was received (i.e., the node sending the packet 1069 to N should not expect a passive acknowledgment and MAY wish to 1070 set the R bit). 1072 OUT Index[1..n] 1074 Index[i] is the interface index that the node indicated 1075 by Address[i-1] must use when transmitting the packet to 1076 Address[i]. Index[1] indicates which interface the node 1077 indicated by the IP Source Address uses to transmit the packet. 1079 Address[1..n] 1081 Address[i] is the home address of the ith hop in the Routing 1082 header. 1084 Note that Address[1] is the first intermediate hop along the route. 1085 The address of the originating node is the IP Source Address. The 1086 only exception to this rule is for packets that are salvaged, as 1087 described in Section 8.5.5. A packet that has been salvaged has an 1088 alternate route placed on it by an intermediate node in the network, 1089 and in this case, the address of the originating node (the salvaging 1090 node) is Address[1]. Salvaged packets are indicated by setting the S 1091 bit in the DSR Routing header. 1093 8. Detailed Operation 1095 8.1. Originating a Data Packet 1097 When node A originates a packet, the following steps MUST be taken 1098 before transmitting the packet: 1100 1. If the destination address is a multicast address, piggyback the 1101 data packet on a Route Request targeting the multicast address. 1102 The following fields MUST be initialized as specified: 1104 IP.Source_Address = Home address of node A 1105 IP.Destination_Address = 255.255.255.255 1106 Request.Target_Address = Multicast destination address 1108 DONE. 1110 2. Otherwise, call Route_Cache.Get() to determine if there is a 1111 cached source route to the destination. 1113 3. If the cached route indicates that the destination is directly 1114 reachable over one hop, no Routing Header should be added to the 1115 packet. Initialize the following fields: 1117 IP.Source_Address = Home address of node A 1118 IP.Destination_Address = Home address of the Destination 1120 DONE. 1122 4. Otherwise, if the cached route indicates that multiple hops are 1123 required to reach the destination, insert a Routing Header into 1124 the packet as described in Section 8.2. DONE. 1126 5. Otherwise, if no cached route to the destination is found, insert 1127 the packet into the Send Buffer and initiate Route Discovery as 1128 described in Section 8.4. 1130 8.2. Originating a Packet with a DSR Routing Header 1132 When a node originates a packet with a Routing Header, the address 1133 of the first hop in the source route MUST be listed as the IP 1134 Destination Address as well as Address[1] in the Routing Header. 1135 The final destination of the packet is listed as the last hop 1136 in the Routing Header (Address[n]). At each intermediate hop i, 1137 Address[i] is copied into the IP Destination Address and the packet 1138 is retransmitted. 1140 For example, suppose node A originates a packet destined for node D 1141 that should pass through intermediate hops B and C. The packet MUST 1142 be initialized as follows: 1144 IP.Source_Address = Home address of node A 1145 IP.Destination_Address = Home address of node B 1146 RT.Segments_Left = 2 1147 RT.Out_Index[1] = Interface index used by A to reach B 1148 RT.Out_Index[2] = Interface index used by B to reach C 1149 RT.Out_Index[3] = Interface index used by C to reach D 1150 RT.Address[1] = Home address of node B 1151 RT.Address[2] = Home address of node C 1152 RT.Address[3] = Home address of node D 1154 8.3. Processing a Routing Header 1156 Excluding the exceptions listed here, a DSR Routing Header is 1157 processed using the same rules as outlined for Type 0 Routing Headers 1158 in IPv6 [6]. The Routing Header is only processed by the node whose 1159 address appears as the IP destination of the packet. The following 1160 additional rules apply to processing the type specific data of a DSR 1161 Source Route: 1163 Let 1165 SegLft = the value of Segments Left when the packet was received 1166 NumAddrs = the total number of addresses in the Routing Header 1168 1. The address of the next hop, Address[NumAddrs - SegLft + 1], 1169 is copied into the IP.Destination_Address of the packet. The 1170 existing IP.Destination_Address is NOT copied back into the 1171 Address list of the Routing Header. 1173 2. The interface used to transmit the packet to its next hop from 1174 this node MUST be the interface denoted by Index[NumAddrs - 1175 SegLft + 1]. 1177 3. If the Acknowledgment Request (R) bit is set, the node MUST 1178 transmit a packet containing the DSR Acknowledgment option to 1179 the previous hop, Address[NumAddrs - SegLft - 1], performing 1180 Route Discovery if necessary. (Address[0] is taken as the 1181 IP.Source_Address) 1183 4. Perform Route Maintenance by verifying that the packet was 1184 received by the next hop as described in Section 8.5. 1186 8.4. Route Discovery 1188 Route Discovery is the on-demand process by which nodes actively 1189 obtain source routes to destinations to which they are actively 1190 attempting to send packets. The destination node for which a 1191 Route Discovery is initiated is known as the "target" of the Route 1192 Discovery. A Route Discovery for a destination SHOULD NOT be 1193 initiated unless the initiating node has a packet in the Send Buffer 1194 requiring delivery to that destination. A Route Discovery for a 1195 given target node MUST NOT be initiated unless permitted by the 1196 rate-limiting information contained in the Route Request Table. 1197 After each Route Discovery attempt, the interval between successive 1198 Route Discoveries for this target must be doubled, up to a maximum of 1199 MAX_REQUEST_PERIOD. 1201 Route Discoveries for a multicast address SHOULD NOT be rate limited, 1202 and SHOULD always be permitted. 1204 8.4.1. Originating a Route Request 1206 The basic Route Discovery algorithm for a unicast destination is as 1207 follows: 1209 1. Originate a Route Request packet with the IP header Time-to-Live 1210 field initialized to 1. This type of Route Request is called a 1211 non-propagating Route Request and allows the originator of the 1212 Request to inexpensively query the route caches of each of its 1213 neighbors for a route to the destination. 1215 2. If a Route Reply is received in response to the non-propagating 1216 Request, use the returned source route to transmit all packets 1217 for the destination that are in the Send Buffer. DONE. 1219 3. Otherwise, if no Route Reply is received within 1220 RING0_REQUEST_TIMEOUT seconds, transmit a Route Request 1221 with the IP header Time-to-Live field initialized to 1222 MAX_ROUTE_LEN. This type of Route Request is called a propagating 1223 Route Request. Update the information in the Route Request 1224 Table, to double the amount of time before any subsequent Route 1225 Discovery attempt to this target. 1227 4. If no Route Reply is received within the time interval indicated 1228 by the Route Request Table, GOTO step 1. 1230 The Route Request option SHOULD be initialized as follows: 1232 IP.Source_Address = This node's home address 1233 IP.Destination_Address = 255.255.255.255 1234 Request.Target = Home address of intended destination 1235 Request.OUT_Index[1] = Index of interface used to transmit the Request 1237 The behavior of a node processing a packet containing both a Routing 1238 Header and a Route Request Destination option is unspecified. 1239 Packets SHOULD NOT contain both a Routing Header and a Route Request 1240 Destination option. [This is not exactly true: A Route Request 1241 option appearing in the second Destination Options header that IPv6 1242 allows after the Routing Header would probably do-what-you-mean, 1243 though we have not triple-checked it yet. Namely, it would allow the 1244 originator of a route discovery to unicast the request to some other 1245 node, where it would be released and begin the flood fill. We call 1246 this a Route Request Blossom since the unicast portion of the path 1247 looks like a stem on the blossoming flood-fill of the request.] 1249 Packets containing a Route Request Destination option SHOULD NOT be 1250 retransmitted, SHOULD NOT request an explicit DSR Acknowledgment by 1251 setting the R bit, SHOULD NOT expect a passive acknowledgment, and 1252 SHOULD NOT be placed in the Retransmission Buffer. The repeated 1253 transmission of packets containing a Route Request Destination option 1254 is controlled solely by the logic described in this section. 1256 8.4.2. Processing a Route Request Option 1258 When a node A receives a packet containing a Route Request option, 1259 the Route Request option is processed as follows: 1261 1. If Request.Target_Address matches the home address of this node, 1262 then the Route Request option contains a complete source route 1263 describing the path from the initiator of the Route Request to 1264 this node. 1266 (a) Send a Route Reply as described in Section 8.4.4. 1268 (b) Continue processing the packet in accordance with the Next 1269 Header value contained in the Destination Option extension 1270 header. DONE. 1272 2. Otherwise, if the combination (IP.Source_Address, 1273 Request.Identification) is found in the Route Request 1274 Table, then discard the packet, since this is a copy of a 1275 recently seen Route Request. DONE. 1277 3. Otherwise, if Request.Target_Address is a multicast address then: 1279 (a) If node A is a member of the multicast group indicated by 1280 Request.Target_Address, then create a copy of the packet, 1281 setting IP.Destination_Address = REQUEST.Target_Address, and 1282 continue processing the copy of the packet in accordance with 1283 the Next Header field of the Destination option. 1285 (b) If IP.TTL is non-zero, decrement IP.TTL, and retransmit the 1286 packet. DONE. 1288 (c) Otherwise, discard the packet. DONE. 1290 4. Otherwise, if the home address of node A is already listed in 1291 the Route Request (IP.Source_Address or Request.Address[]), then 1292 discard the packet. DONE. 1294 5. Let 1296 m = number of addresses currently in the Route Request option 1297 n = m + 1 1299 6. Otherwise, append the home address of node A to the Route Request 1300 option (Request.Address[n]). 1302 7. Set Request.IN_Index[n] = index of interface packet was received 1303 on. 1305 8. If a source route to Request.Target_Address is found in our Route 1306 Cache and the rules of Section 8.4.3 permit it, return a Cached 1307 Route Reply as described in Section 8.4.3. DONE. 1309 9. Otherwise, for each interface on which the node is configured to 1310 participate in a DSR ad hoc network: 1312 (a) Make a copy of the packet containing the Route Request. 1314 (b) Set Request.OUT_Index[n+1] = index of the interface. 1316 (c) If the outgoing interface is different from the incoming 1317 interface, then set the C bit on both Request.OUT_Index[n+1] 1318 and Request.IN_Index[n] 1320 (d) Link-layer re-broadcast the packet containing the Route 1321 Request on the interface jittered by T milliseconds, where 1322 T is a uniformly distributed, random number between 0 and 1323 BROADCAST_JITTER. DONE. 1325 8.4.3. Generating Route Replies using the Route Cache 1327 A node SHOULD use its Route Cache to avoid propagating a Route 1328 Request packet received from another node. In particular, suppose a 1329 node receives a Route Request packet for which it is not the target 1330 and which it does not discard based on the logic of Section 8.4.2. 1331 If the node has a Route Cache entry for the target of the Request, 1332 it SHOULD append this cached route to the accumulated route record 1333 in the packet and return this route in a Route Reply packet to 1334 the initiator without propagating (re-broadcasting) the Route 1335 Request. Thus, for example, if node F in the example network shown 1336 in Figure 8.4.3 needs to send a packet to node D, it will initiate 1337 a Route Discovery and broadcast a Route Request packet. If this 1338 broadcast is received by node A, node A can simply return a Route 1339 Reply packet to F containing the complete route to D consisting of 1340 the sequence of hops: A, B, C, and D. 1342 Before transmitting a Route Reply packet that was generated using 1343 information from its Route Cache, a node MUST verify that: 1345 1. The resulting route contains no loops. 1347 2. The node issuing the Route Reply is listed in the route that it 1348 specifies in its Reply. This increases the probability that the 1349 route is valid, since the node in question should have received 1350 a Route Error if this route stopped working. Additionally, this 1351 requirement means that a Route Error traversing the route will 1352 pass through the node that issued the Reply based on stale cache 1353 data, which is critical for ensuring stale data is removed from 1354 caches in a timely manner. Without this requirement, the next 1355 Route Discovery initiated by the original requester might also be 1356 contaminated by a Route Reply from this node containing the same 1357 stale route. 1359 8.4.4. Originating a Route Reply 1361 Let REQPacket denote a packet received by node A that 1362 contains a Route Request option which lists node A as the 1363 REQPacket.Request.Target_Address. Let REPPacket be a packet 1364 transmitted by node A that contains a corresponding Route Reply. The 1365 Route Reply option transmitted in response to a Route Request MUST be 1366 initialized as follows: 1368 B->C->D 1369 +---+ +---+ +---+ +---+ 1370 | A |---->| B |---->| C |---->| D | 1371 +---+ +---+ +---+ +---+ 1373 +---+ 1374 | F | +---+ 1375 +---+ | E | 1376 +---+ 1378 Figure 1: An example network where A knows a 1379 route to D via B and C. 1381 1. If REQPacket.Request.Address[] does not contain any hops, then 1382 node A is only a single hop from the originator of the Route 1383 Request. Build a Route Reply packet as follows: 1385 REPPacket.IP.Source_Address = REQPacket.Request.Target_Address 1386 REPPacket.Reply.Target = REQPacket.IP.Source_Address 1387 REPPacket.Reply.OUT_Index[1] = REQPacket.Request.OUT_index[1] 1388 REPPacket.Reply.OUT_C_bit[1] = REQPacket.Request.OUT_C_bit[1] 1389 REPPacket.Reply.Address[1] = The home address of node A 1391 GOTO step 3. 1393 2. Otherwise, build a Route Reply packet as follows: 1395 REPPacket.IP.Source_Address = The home address of node A 1396 REPPacket.Reply.Target = REQPacket.IP.Source_Address 1397 REPPacket.Reply.OUT_Index[1..n]= REQPacket.Request.OUT_index[1..n] 1398 REPPacket.Reply.OUT_C_bit[1..n]= REQPacket.Request.OUT_C_bit[1..n] 1399 REPPacket.Reply.Address[1..n] = REQPacket.Request.Address[1..n] 1401 3. Send the Route Reply jittered by T milliseconds, where T 1402 is a uniformly distributed random number between 0 and 1403 BROADCAST_JITTER. DONE. 1405 If sending a Route Reply packet to the originator of the Route 1406 Request requires performing a Route Discovery, the Route Reply 1407 hop-by-hop option MUST be piggybacked on the packet that contains the 1408 Route Request. This prevents a loop wherein the target of the new 1409 Route Request (which was itself the originator of the original Route 1410 Request) must do another Route Request in order to return its Route 1411 Reply. 1413 If sending the Route Reply to the originator of the Route Request 1414 does not require performing Route Discovery, a node SHOULD send a 1415 unicast Route Reply in response to every Route Request targeted at 1416 it. 1418 8.4.5. Processing a Route Reply Option 1420 Upon receipt of a Route Reply, a node should extract the source route 1421 (Target_Address, OUT_Index[1]:Address[1], .. OUT_Index[n]:Address[n] 1422 ) and insert this route into its Route Cache. All the packets in the 1423 Send Buffer SHOULD be checked to see whether the information in the 1424 Reply allows them to be sent immediately. 1426 8.5. Route Maintenance 1428 Route Maintenance requires that whenever a node transmits a data 1429 packet, a Route Reply, or a Route Error, it must verify that the next 1430 hop (indicated by the Destination IP Address) correctly receives the 1431 packet. 1433 If the sender cannot verify that the next hop received the packet, it 1434 MUST decide that its link to the next hop is broken and MUST send a 1435 Route Error to the node responsible for generating the Routing Header 1436 that contains the broken link (Section 8.5.3). 1438 The following ways may be used to verify that the next hop correctly 1439 received a packet: 1441 - The receipt of a passive acknowledgment (Section 8.5.1). 1443 - The receipt of an explicitly requested acknowledgment 1444 (Section 8.5.1). 1446 - By the presence of positive feedback from the link layer 1447 indicating that the packet was acknowledged by the next hop 1448 (Section 8.5.2). 1450 - By the absence of explicit failure notification from the link 1451 layer that provides reliable hop-by-hop delivery such as MACAW or 1452 802.11 (Section 8.5.2). 1454 Nodes MUST NOT perform Route Maintenance for packets containing a 1455 Route Request option or packets containing only an Acknowledgment 1456 option. Sending Acknowledgments for packets containing only 1457 an Acknowledgment option would create an infinite loop whereby 1458 acknowledgments would be sent for acknowledgments. Acknowledgments 1459 should be always sent for packets containing a Routing Header with 1460 the R bit set (e.g., packets which contain only an Acknowledgment 1461 and a Routing Header for which the last forwarding hop requires an 1462 explicit acknowledgment of receipt by the final destination). 1464 8.5.1. Using Network-Layer Acknowledgments 1466 For link layers that do not provide explicit failure notification, 1467 the following steps SHOULD be used by a node A to perform Route 1468 Maintenance. 1470 When receiving a packet: 1472 - If the packet contains a Routing Header with the R bit set, send 1473 an explicit acknowledgment as described in Section 8.3. 1475 - If the packet does not contain a Routing Header, the node MUST 1476 transmit a packet containing the DSR Acknowledgment option 1477 to the previous hop as indicated by the IP.Source_Address. 1478 Since the receiving node is the final destination, there 1479 will be no opportunity for the originator to obtain a 1480 passive acknowledgment, and the receiving node must infer the 1481 originator's request for an explicit acknowledgment. 1483 When sending a packet: 1485 1. Before sending a packet, insert a copy of the packet into the 1486 Retransmission Buffer and update the information maintained about 1487 this packet in the Retransmission Buffer. 1489 2. If after processing the Routing Header, RH.Segments_Left is equal 1490 to 0, then node A MUST set the Acknowledgment Request (R) bit in 1491 the Routing Header before transmitting the packet over its final 1492 hop. 1494 3. If after processing the Routing Header and copying 1495 RH.Address[n] to IP.Destination_Address, node A determines that 1496 RH.OUT_C_bit[n+1] is set, then node A MUST set the Acknowledgment 1497 Request (R) bit in the Routing Header before transmitting the 1498 packet (since the C bit was set during Route Discovery by the 1499 node now listed as the IP.Destination_Address to indicate that 1500 it will propagate the packet out a different interface, and that 1501 node A will not receive a passive acknowledgment). 1503 4. Set the retransmission timer for the packet in the Retransmission 1504 Buffer. 1506 5. Transmit the packet. 1508 6. If a passive or explicit acknowledgment is received before the 1509 retransmission timer expires, then remove the packet from the 1510 Retransmission Buffer and disable the retransmission timer. 1511 DONE. 1513 7. Otherwise, when the Retransmission Timer expires, remove the 1514 packet from the Retransmission Buffer. 1516 8. If DSR_MAXRXTSHIFT transmissions have been done, then attempt 1517 to salvage the packet (Section 8.5.5). Also, generate a Route 1518 Error. DONE. 1520 9. GOTO step 1. 1522 8.5.2. Using Link Layer Acknowledgments 1524 If explicit failure notifications are provided by the link layer, 1525 then all packets are assumed to be correctly received by the next hop 1526 and a Route Error is sent only when a explicit failure notification 1527 is made from the link layer. 1529 Nodes receiving a packet without a Routing Header do not need to send 1530 an explicit Acknowledgment to the packet's originator, since the 1531 link layer will notify the originator if the packet was not received 1532 properly. 1534 8.5.3. Originating a Route Error 1536 If the next hop of a packet is found to be unreachable as described 1537 in Section 8.5, a Route Error packet (Section 7.2.2) MUST be returned 1538 to the node whose cache generated the information used to route the 1539 packet. 1541 When a node A generates a Route Error for packet P, it MUST 1542 initialize the fields in the Route Error as follows: 1544 Error.Source_Address = Home address of node A 1545 Error.Unreachable_Address = Home address of the unreachable node 1547 - If the packet contains a DSR Routing Header and the S bit is NOT 1548 set, the packet has been forwarded without the need for salvaging 1549 up to this point. 1551 Error.Destination_Address = P.IP.Source_Address 1553 - Otherwise, if the packet contains a DSR Routing Header and the S 1554 bit IS set, the packet has been salvaged by an intermediate node, 1555 and thus this Routing Header was placed there by the salvaging 1556 node. 1558 Error.Destination_Address = P.RoutingHeader.Address[1] 1560 - Otherwise, if the packet does not contain a DSR Routing Header, 1561 the packet must have been originated by this node A. 1563 Error.Destination_Address = Home address of node A 1565 Send the packet containing the Route Error to Error.Destination_Address, 1566 performing Route Discovery if necessary. 1568 As an optimization, Route Errors that are discovered by the 1569 packet's originator (such that Error.Source_Address is equal to 1570 Error.Destination_Address) SHOULD be processed internally. Such 1571 processing should invoke all the steps that would be taken if a Route 1572 Error option was created, transmitted, received, and processed, 1573 but an actual packet containing a Route Error option SHOULD NOT be 1574 transmitted. 1576 8.5.4. Processing a Route Error Option 1578 Upon receipt of a Route Error via any mechanism, a node 1579 SHOULD remove any route from its Route Cache that uses the hop 1580 (Error.Source_Address, Error.Index to Error.Unreachable_Address). 1581 This includes all Route Errors overheard, and those processed 1582 internally as described in Section 8.5.3. 1584 When the node identified by Error.Destination_Address receives 1585 the Route Error, it SHOULD verify that the source route 1586 responsible for delivering the Route Error includes the same 1587 hops as the working prefix of the original packet's source route 1588 (Error.Destination_Address to Error.Source_Address). If any 1589 hop listed in the working prefix is not included in the Route 1590 Error's source route, then the originator SHOULD forward the Route 1591 Error back along the working prefix (Error.Destination_Address to 1592 Error.Source_Address) so that each node along the working prefix will 1593 remove the invalid route from its Route Cache. 1595 If the node processing a Route Error option discovers its home 1596 address is Error.Destination_Address and the packet contains 1597 additional Route Error option(s) later on the inside of the Hop 1598 by Hop options header, we call the additional Route Errors nested 1599 Route Errors. The node MUST deliver the first nested Route Error 1600 to Nested_Error.Destination_Address, performing Route Discovery if 1601 needed. It does this by removing the Route Error option listing 1602 itself as the Error.Destination_Address, finding the first nested 1603 Route Error option, and originating the remaining packet to 1604 Nested_Error.Destination_Address. This mechanism allows for the 1605 proper handling of Route Errors that are discovered while delivering 1606 a Route Error. 1608 8.5.5. Salvaging a Packet 1610 When node A attempts to salvage a packet originated at node S and 1611 destined for node D, it MUST perform the following steps: 1613 1. Generate and send a Route Error to S as explained in 1614 Section 8.5.3. 1616 2. Call Route_Cache.Get() to determine if it has a cached source 1617 route to the packet's ultimate destination D (which is the last 1618 Address listed in the Routing Header). 1620 3. If node A does not have a cached route for node D, it MUST 1621 discard the packet. DONE. 1623 4. Otherwise, let Salvage_Address[1] through Salvage_Address[m] be 1624 the sequence of hops returned from the Route Cache. Initialize 1625 the following fields in the packet's header: 1627 RT.Segments_Left = m - 2; 1628 RT.S = 1 1629 RT.Address[1] = Home address of Node A 1630 RT.Address[2] = Salvage.Address[1] 1631 ... 1632 RT.Address[n] = Salvage.Address[m] 1634 The IP Source Address of the packet MUST remain unchanged. When the 1635 Routing Header in the outgoing packet is processed, RT.Address[2], 1636 will be copied to the IP Destination Address field. 1638 9. Optimizations 1640 A number of optimizations can be added to the basic operation of 1641 Route Discovery and Route Maintenance as described in Sections 8.4 1642 and 8.5 that can reduce the number of overhead packets and improve 1643 the average efficiency of the routes used on data packets. This 1644 section discusses some of those optimizations. 1646 9.1. Leveraging the Route Cache 1648 The data in a node's Route Cache may be stored in any format, but 1649 the active routes in its cache form a tree of routes, rooted at 1650 this node, to other nodes in the ad hoc network. For example, the 1651 illustration below shows an ad hoc network of six mobile nodes, in 1652 which mobile node A has earlier completed a Route Discovery for 1653 mobile node D and has cached a route to D through B and C: 1655 B->C->D 1656 +---+ +---+ +---+ +---+ 1657 | A |---->| B |---->| C |---->| D | 1658 +---+ +---+ +---+ +---+ 1660 +---+ 1661 | F | +---+ 1662 +---+ | E | 1663 +---+ 1665 Since nodes B and C are on the route to D, node A also learns the 1666 route to both of these nodes from its Route Discovery for D. If A 1667 later performs a Route Discovery and learns the route to E through B 1668 and C, it can represent this in its Route Cache with the addition of 1669 the single new hop from C to E. If A then learns it can reach C in a 1670 single hop (without needing to go through B), A SHOULD use this new 1671 route to C to also shorten the routes to D and E in its Route Cache. 1673 9.1.1. Promiscuous Learning of Source Routes 1675 A node can add entries to its Route Cache any time it learns a new 1676 route. In particular, when a node forwards a data packet as an 1677 intermediate hop on the route in that packet, the forwarding node is 1678 able to observe the entire route in the packet. Thus, for example, 1679 when any intermediate node B forwards packets from A to D, B SHOULD 1680 add the source route information from that packet's Routing Header 1681 to its own Route Cache. If a node forwards a Route Reply packet, it 1682 SHOULD also add the source route information from the route record 1683 being returned in the Route Reply, to its own Route Cache. 1685 In addition, since all wireless network transmissions at the physical 1686 layer are inherently broadcast, it may be possible for a node to 1687 configure its network interface into promiscuous receive mode, such 1688 that the node is able to receive all packets without link layer 1689 address filtering. In this case, the node MAY add to its Route Cache 1690 the route information from any packet it can overhear. 1692 9.2. Preventing Route Reply Storms 1694 The ability for nodes to reply to a Route Request not targeted at 1695 them by using their Route Caches can result in a Route Reply storm. 1696 If a node broadcasts a Route Request for a node that its neighbors 1697 have in their Route Caches, each neighbor may attempt to send a 1698 Route Reply, thereby wasting bandwidth and increasing the rate 1699 of collisions in the area. For example, in the network shown in 1700 Section 9.1, if both node A and node B receive F's Route Request, 1701 they will both attempt to reply from their Route Caches. Both will 1702 send their Replies at about the same time since they receive the 1703 broadcast at about the same time. Particularly when more than the 1704 two mobile nodes in this example are involved, these simultaneous 1705 replies from the mobile nodes receiving the broadcast may create 1706 packet collisions among some or all of these replies and may cause 1707 local congestion in the wireless network. In addition, it will 1708 often be the case that the different replies will indicate routes 1709 of different lengths. For example, A's Route Reply will indicate a 1710 route to D that is one hop longer than that in B's reply. 1712 For interfaces which can promiscuously listen to the channel, mobile 1713 nodes SHOULD use the following algorithm to reduce the number of 1714 simultaneous replies by slightly delaying their Route Reply: 1716 1. Pick a delay period 1718 d = H * (h - 1 + r) 1720 where h is the length in number of network hops for the route 1721 to be returned in this node's Route Reply, r is a random number 1722 between 0 and 1, and H is a small constant delay to be introduced 1723 per hop. 1725 2. Delay transmitting the Route Reply from this node for a period 1726 of d. 1728 3. Within the delay period, promiscuously receive all packets at 1729 this node. If a packet is received by this node during the delay 1730 period that is addressed to the target of this Route Discovery 1731 (the target is the final destination address for the packet, 1732 through any sequence of intermediate hops), and if the length of 1733 the route on this packet is less than h, then cancel the delay 1734 timer and do not transmit the Route Reply from this node; this 1735 node may infer that the initiator of this Route Discovery has 1736 already received a Route Reply, giving an equally good or better 1737 route. 1739 9.3. Piggybacking on Route Discoveries 1741 As described in Section 5.1, when one node needs to send a packet 1742 to another, if the sender does not have a route cached to the 1743 destination node, it must initiate a Route Discovery, buffering the 1744 original packet until the Route Reply is returned. The delay for 1745 Route Discovery and the total number of packets transmitted can be 1746 reduced by allowing data to be piggybacked on Route Request packets. 1747 Since some Route Requests may be propagated widely within the ad hoc 1748 network, though, the amount of data piggybacked must be limited. We 1749 currently use piggybacking when sending a Route Reply or a Route 1750 Error packet, since both are naturally small in size. Small data 1751 packets such as the initial SYN packet opening a TCP connection [18] 1752 could easily be piggybacked. 1754 One problem, however, arises when piggybacking on Route Request 1755 packets. If a Route Request is received by a node that replies 1756 to the request based on its Route Cache without propagating the 1757 Request (Section 9.1), the piggybacked data will be lost if the node 1758 simply discards the Route Request. In this case, before discarding 1759 the packet, the node must construct a new packet containing the 1760 piggybacked data from the Route Request packet. The source route 1761 in this packet MUST be constructed to appear as if the new packet 1762 had been sent by the initiator of the Route Discovery and had been 1763 forwarded normally to this node. Hence, the first portion of the 1764 route is taken from the accumulated route record in the Route Request 1765 packet and the remainder of the route is taken from this node's Route 1766 Cache. The sender address in the packet MUST also be set to the 1767 initiator of the Route Discovery. Since the replying node will be 1768 unable to correctly recompute an Authentication header for the split 1769 off piggybacked data, data covered by an Authentication header SHOULD 1770 NOT be piggybacked on Route Request packets. 1772 9.4. Discovering Shorter Routes 1774 Once a route between a packet source and a destination has been 1775 discovered, the basic DSR protocol MAY continue to use that route 1776 for all traffic from the source to the destination as long as 1777 it continues to work, even if the nodes move such that a shorter 1778 route becomes possible. In many cases, the basic Route Maintenance 1779 procedure will discover the shorter route, since if a node moves 1780 enough to create a shorter route, it will likely also move out of 1781 transmission range of at least one hop on the existing route. 1783 Furthermore, when a data packet is received as the result of 1784 operating in promiscuous receive mode, the node checks if the Routing 1785 Header packet contains its address in the unprocessed portion of the 1786 source route (Address[NumAddrs - SegLft] to Address[NumAddrs]). If 1787 so, the node knows that packet could bypass the unprocessed hops 1788 preceding it in the source route. The node then sends what is called 1789 a gratuitous Route Reply message to the packet's source, giving it 1790 the shorter route without these hops. 1792 The following algorithm describes how a node A should process packets 1793 with an IP.Destination_Address not addressed to A or the IP broadcast 1794 address or a multicast address that are received as a result of A 1795 being in promiscuous receive mode: 1797 1. If the packet is not a data packet containing a Routing Header, 1798 drop the packet. DONE. 1800 2. If the home address of this node does not appear in the portion 1801 of the source route that has not yet been processed (indicated by 1802 Segments Left), then drop the packet. DONE. 1804 3. Otherwise, the node B that just transmitted the packet (indicated 1805 by Address[NumAddrs - SegLft - 1]) can communicate directly with 1806 this node A. Create a Route Reply. The Route Reply MUST list 1807 the entire source route contained in the received packet with the 1808 exception of the intermediate nodes between node B and node A. 1810 4. Send this gratuitous Route Reply to the node listed as the 1811 IP.Source_Address of the received packet. If Route Discovery 1812 is required it MAY be initiated, or the gratuitous Route Reply 1813 packet MAY be dropped. 1815 9.5. Rate Limiting the Route Discovery Process 1817 One common error condition that must be handled in an ad hoc network 1818 is the case in which the network effectively becomes partitioned. 1819 That is, two nodes that wish to communicate are not within 1820 transmission range of each other, and there are not enough other 1821 mobile nodes between them to form a sequence of hops through which 1822 they can forward packets. If a new Route Discovery was initiated 1823 for each packet sent by a node in this situation, a large number of 1824 unproductive Route Request packets would be propagated throughout the 1825 subset of the ad hoc network reachable from this node. In order to 1826 reduce the overhead from such Route Discoveries, we use exponential 1827 back-off to limit the rate at which new Route Discoveries may be 1828 initiated from any node for the same target. If the node attempts to 1829 send additional data packets to this same node more frequently than 1830 this limit, the subsequent packets SHOULD be buffered in the Send 1831 Buffer until a Route Reply is received, but it MUST NOT initiate a 1832 new Route Discovery until the minimum allowable interval between new 1833 Route Discoveries for this target has been reached. This limitation 1834 on the maximum rate of Route Discoveries for the same target is 1835 similar to the mechanism required by Internet nodes to limit the rate 1836 at which ARP requests are sent to any single IP address [2]. 1838 9.6. Improved Handling of Route Errors 1840 All nodes SHOULD process all of the Route Error messages they 1841 receive, regardless of whether the node is the destination of 1842 the Route Error, is forwarding the Route Error, or promiscuously 1843 overhears the Route Error. 1845 Since a Route Error packet names both ends of the hop that is no 1846 longer valid, any of the nodes receiving the error packet may update 1847 their Route Caches to reflect the fact that the two nodes indicated 1848 in the packet can no longer directly communicate. A node receiving 1849 a Route Error packet simply searches its Route Cache for any routes 1850 using this hop. For each such route found, the route is effectively 1851 truncated at this hop. All nodes on the route before this hop are 1852 still reachable on this route, but subsequent nodes are not. 1854 An experimental optimization to improve the handling of errors is 1855 to support the caching of "negative" information in a node's Route 1856 Cache. The goal of negative information is to record that a given 1857 route was tried and found not to work, so that if the same route 1858 is discovered again shortly after the failure, the Route Cache can 1859 ignore or downgrade the metric of the failed route. 1861 We have not currently included this caching of negative information 1862 in our simulations, since it appears to be unnecessary if nodes also 1863 promiscuously receive Route Error packets. 1865 9.7. Increasing Scalability 1867 We recently designed and began experimenting with ways to integrate 1868 ad hoc networks with the Internet and with Mobile IP [14]. In 1869 addition to this, we are also exploring ways to increase the 1870 scalability of ad hoc networks by taking advantage of their 1871 cooperative nature and the fact that some hierarchy can be imposed 1872 on an ad hoc network, just be assigning addresses to the nodes in a 1873 reasonable way. These ideas are described in a workshop paper [4]. 1875 10. Path-State and Flow-State Mechanisms 1877 This section describes the current design of our framework for 1878 supporting better-than-best-effort Quality of Service in DSR 1879 networks. The framework dovetails into DSR's existing mechanisms, 1880 and, like DSR itself, is completely on-demand in nature --- no 1881 packets are sent unless there is user data to transfer. The 1882 framework is based on the introduction of two kinds of soft-state, 1883 called path-state and flow-state, at the intermediate nodes along the 1884 path between senders and destinations. 1886 Taken together, the path-state and flow-state extensions extend the 1887 Quality of Service provided by DSR networks in the following ways: 1889 - They eliminate the need for all data packets to carry a source 1890 route, increasing the efficiency of the protocol in general. 1892 - They provide accurate measurements of the state of the network to 1893 higher layers protocols for use in adaptation. 1895 - They enable senders to explicitly manage the consumption of 1896 resources across the network. 1898 - They enable the network to provide better-than-best-effort 1899 service via admission control and per-flow resource management. 1901 10.1. Overview 1903 Path-state allows intermediate nodes to forward packets according to 1904 a predetermined source route, even when most packets do not include 1905 the full source route. Conceptually, the originator of each data 1906 packet initially includes both a source route and a unique path 1907 identifier in each packet it sends. As intermediate nodes forward 1908 the packet, they cache the source route from the packet, indexed by 1909 the path identifier. The source can then send subsequent packets 1910 carrying only the path identifier, since intermediate nodes will be 1911 able to forward the packet based on the source route for the path 1912 that they have cached. 1914 While path-state allows the elimination of the source route from each 1915 packet, thereby reducing the overhead of the DSR protocol, it also 1916 provides a way for sources to monitor the state of each path through 1917 the network. When a source wishes to know the characteristics of 1918 a path through the network, it piggybacks a path-metrics header 1919 onto any data or control packet traversing the path. As the 1920 packet propagates through the network, each intermediate node 1921 updates the set of path-metrics carried by the packet to reflect 1922 the local network conditions seen at the node. These metrics are 1923 reflected back to the sender by the destination, along with the path 1924 identifier, and enable the sender to track the value of these metrics 1925 for each of the source routes it is currently using. 1927 We are currently experimenting with metrics that are easy for nodes 1928 to measure, that require constant size to represent regardless of 1929 source route length, and that would enable the sender's network 1930 layer to provide useful feedback to higher layers on the state of 1931 the network. For example, by including ``available bandwidth'' 1932 or ``battery level'' as a metric, senders can load balance 1933 the consumption of resources across the network. We have also 1934 considered the possibility of replacing the TCP congestion control 1935 algorithm with a ``leaky-bucket'' system controlled by the reflected 1936 path-metrics --- our measured performance results show this could 1937 dramatically improve TCP throughput in environments where many 1938 packets are lost due to packet corruption. The feedback could also 1939 be used as inputs to other researcher's systems for improving the 1940 transport layer, such as Liu and Singh's ATCP [11], or for adaptation 1941 at higher layers, as in Odyssey [13]. 1943 Flow-state allows a source to differentiate its traffic into 1944 flows, and then request better-than-best-effort handling for these 1945 flows. With the additional information provided by the flow-state, 1946 the network can provide admission control and promise a specific 1947 Quality of Service (QoS) to each flow. Since the ad hoc network may 1948 frequently change topology, the flow-state mechanisms are directly 1949 integrated into the routing protocol to minimize their reaction time 1950 and provide notifications to a flow when the network must break its 1951 promise for a specific level of QoS. 1953 10.2. Path-State and Flow-State Identifiers 1955 The metadata that intermediate nodes in the network must process 1956 is divided into path-state and flow-state, where path-state is 1957 the fundamental unit of routing information and flow-state is the 1958 fundamental unit of Quality of Service information. 1960 Path-state is associated with a particular set of hops through the 1961 network from some source S to a destination D (i.e., a particular 1962 source route in the network). It consists of the information needed 1963 to route packets along the path, and information about the carrying 1964 capacity of the path, such as the unused bandwidth along the path or 1965 the minimum latency of the path. 1967 Flow-state is specific to a particular class of packets flowing 1968 between S and D that is routed over a given path. Flow-state is 1969 used to record Quality of Service promises that have been made for a 1970 particular flow, and allows packets from S to D that take the same 1971 path through the network to be treated differently by intermediate 1972 nodes. For example, all the TCP connections between S and D that 1973 take the same path will share the same path-state, but may have 1974 independent flow-state. At any point in time, S may use multiple 1975 paths for its traffic to D and each of these paths may be comprised 1976 of many flows. However, a single network layer flow may not be 1977 multiplexed over different paths. 1979 To represent paths and flows inside the network, we use a scheme 1980 inspired by the Virtual Path Index and Virtual Circuit Index of 1981 ATM networks [23, p. 451]. Paths are identified by the logical 1982 concatenation of the source node address and a 16-bit path identifier 1983 where the low 5 bits are 0. Flows are identified by a path 1984 identifier where the low 5 bits are used to distinguish between the 1985 different flows that use the same path. 1987 This scheme has two main advantages. First, each source node can 1988 independently generate globally unique path- and flow-identifiers. 1989 Second, the hierarchical relation of flow-identifiers to 1990 path-identifiers means that many flows from the same source node can 1991 share the same path-state, which reduces the overhead of maintaining 1992 the routing information. The drawback is that if a flow must be 1993 rerouted, its flow identifier will change. However, when a flow is 1994 rerouted the QoS metadata must be renegotiated anyway, so changing 1995 flow identifiers will not create needless additional work in the 1996 network. 1998 10.3. Path-State Creation, Use, and Maintenance 2000 The path-state portion of the protocol has two major goals. The 2001 first goal is to ensure sufficient state exists at the nodes along a 2002 path from a source S to a destination D so that packets from S to D 2003 do not need to carry the complete source route. The second goal is 2004 to allow S to discover the characteristics of a particular path to D 2005 so that it can adapt its sending pattern to the capabilities of the 2006 path, or even choose a different path entirely. 2008 The next sections describe how the path-state is created, how the 2009 characteristics of the path are discovered, and what metrics can be 2010 used to characterize the path. 2012 10.3.1. Creating Path-State for Routing 2014 To create the path-state, we assume that Route Discovery proceeds as 2015 normal in DSR. Once the source node S has obtained a source route to 2016 the destination D, it begins sending data packets to D as normally 2017 done in DSR, with each packet carrying a full source route header. 2018 Internally, S assigns a path-identifier to that particular source 2019 route and stores the path-identifier in its route cache along with 2020 the source route. S then includes the path-identifier as part of the 2022 A -----------------> B -----------------> C -----------------> D 2024 +-------------+ +-------------+ +-------------+ 2025 |src: A | |src: A | |src: A | 2026 |dst: D | |dst: D | |dst: D | 2027 |path-id: 15 | |path-id: 15 | |path-id: 15 | 2028 |rt: A,(B),C,D| |rt: A,B,(C),D| |rt: A,B,C,(D)| 2029 +-------------+ +-------------+ +-------------+ 2030 | payload | | payload | | payload | 2032 (a) Packet with path identifier and source route. 2034 A -----------------> B -----------------> C -----------------> D 2036 +-------------+ +-------------+ +-------------+ 2037 |src: A | |src: A | |src: A | 2038 |dst: D | |dst: D | |dst: D | 2039 |path-id: 15 | |path-id: 15 | |path-id: 15 | 2040 +-------------+ +-------------+ +-------------+ 2041 | payload | | payload | | payload | 2043 (b) Packet with path identifier only. 2045 Figure 2: Path identifiers assigned to a source route by the 2046 originating node A enable later packets to omit the source route. 2048 source route header as shown in Figure 2(a). As each intermediate 2049 node processes the source route to forward the packet, it also stores 2050 the source route in its route cache, indexed by the source and 2051 path-identifier. 2053 After sending a packet containing both the source route and the 2054 path-identifier into the network, S can begin sending subsequent 2055 packets to D without a full source route --- carrying only the 2056 path-identifier as shown in Figure 2(b). Each intermediate node 2057 receiving such a packet queries its route cache to find the route 2058 the packet is supposed to take, and determines its next hop. As 2059 explained in Section 10.5, if the cached source route is not 2060 available at some intermediate node, S will receive a Route Error and 2061 can then correct the situation. 2063 10.3.2. Monitoring Characteristics of the Path 2065 In order to support network layer services such as balancing the 2066 traffic load across the network, end-systems must have a method for 2067 determining the characteristics of the paths through the network that 2068 they could use. While many schemes have been proposed by which the 2069 end-systems themselves can measure the characteristics of a path 2070 (e.g., TCP congestion window and RTT calculations [1, 22, 24] and 2071 SPAND [21]), we hypothesize that, particularly in the in the dynamic 2072 environment of an ad hoc network, more useful, more accurate, and 2073 more timely information can be developed by enlisting the aid of the 2074 nodes along the path to measure the path characteristics. 2076 We propose that each node can measure the activity around itself, 2077 and thereby determine information such as: the mean latency it adds 2078 to the packets it forwards and the latency variation (jitter); the 2079 number of additional packets per second it believes it can process; 2080 or the unused amount of wireless media capacity in the air around 2081 the node. Experimentation will be required to discover exactly 2082 which metrics will prove to be accurately measurable and useful, 2083 though Section 10.3.3 provides several proposals. If the metrics 2084 kept by each node on a path are combined, the result should be a 2085 characterization of the path that the packet sender can use to 2086 organize or adapt its offered load. 2088 To implement this scheme, we first define a new type of extension 2089 header for DSR than can be piggybacked onto a packet in the same way 2090 as the existing DSR headers. This new header is called the path 2091 metrics header (written as Measure) and conceptually consists of the 2092 path-identifier of the path along which the metrics are measured, 2093 the type of the Measure, and the metrics themselves encoded in a TLV 2094 format (Section 10.6.2). 2096 Whenever a sender S wishes to measure the characteristics of a path 2097 it is using, it includes the Measure header in any packet it sends 2098 along that path, setting the type of the header to record. As each 2099 node along the path forwards the packet, it updates the variables 2100 inside the Measure header with the metrics it has measured locally. 2101 When the header reaches the final destination D, D sets the type 2102 of the Measure header to return and piggybacks the header into any 2103 packet headed back to S. Since the path metrics header includes 2104 the path-identifier of the path along which it was measured, S can 2105 include the data into its route cache for future use, and can treat 2106 the receipt of the path metrics header as a positive acknowledgment 2107 that the path-state between S and D for the given path-identifier 2108 is correctly set up. This could lead S to cease including source 2109 routes in the packets it sends along the path, as described in 2110 Section 10.3.1. 2112 If we find that it is valuable to immediately provide S with the path 2113 metrics of every discovered route, we could alter Route Discovery 2114 slightly to generate this information. Currently, if an intermediate 2115 node has a cached route that it can use to answer a Route Request, 2116 it generates a Route Reply itself. Instead, we could require it to 2117 place its proposed route on the Route Request (turning it from a 2118 flood-fill broadcast into a unicast packet) and send the packet to 2119 the destination so it will measure the metrics of the complete path. 2120 The destination will then return the metrics to the source along with 2121 the Route Reply as described above. 2123 We have been intending to experiment with this alteration to 2124 Route Discovery for some time, since it offers two benefits, 2125 even without path-state metrics. It should decrease the 2126 number of broken routes returned by Route Discovery since 2127 each cached route is tested before being returned, and 2128 it should save us from jeopardizing one data packet for 2129 every bad route in someone's cache. The cost is some extra 2130 latency on Route Discovery. 2132 10.3.3. Candidate Metrics 2134 In order to limit the additional overhead that collecting and 2135 distributing path-state metrics will place on the network, all the 2136 metrics must have the property that the amount of space required to 2137 express the metric does not increase as the number of hops on the 2138 path increases. Experimentation will be required to determine which 2139 metrics are most accurately measured and most useful, but our initial 2140 set of candidates includes the following: 2142 - Interface queue length --- Our previous work [12] has shown that 2143 this is a good estimator of local congestion. 2145 - Rate of interface queue draining --- When an interface is 2146 backlogged, the rate at which packets leave the queue directly 2147 measures the usable capacity of that interface. 2149 - Quiet time fraction --- When an interface is not backlogged, 2150 the usable capacity of the interface can be estimated by 2151 promiscuously listening to the media and measuring the fraction 2152 of time during which it is not in use (though this will 2153 overestimate the capacity). 2155 - Fraction Free Air Time --- The fraction of time our interface 2156 would be able to send a packet. That is, the fraction of time 2157 the interface does not sense carrier, is not deferring, and is 2158 not backed off. Current experiments show this is an excellent 2159 predictor of congestion and available capacity. 2161 - Forwarding latency and variation --- This can be measured 2162 as the time between when a packet is received and when it is 2163 acknowledged by the next hop. 2165 - Unidirectional links --- Paths containing unidirectional links 2166 are usable, but undesirable as they increase the overhead of 2167 Route Maintenance. 2169 - Packet loss rate --- Signal quality information from the 2170 interface itself, or the frequency of hop-by-hop retransmission, 2171 can be used to estimate the loss rate of each link. 2173 - Likelihood of path breakage --- Intermediate nodes may know ahead 2174 of time that they intend to shutdown or move such that paths 2175 through them will no longer work. 2177 These metrics all have the property that they can be expressed in 2178 a single value that each node can measure locally. As a packet 2179 with a path metrics header passes through a node, the metrics in 2180 the header can be updated to reflect the node's metrics using a 2181 combination function like minimum, maximum, sum, or weighted average 2182 that produces another single value to replace the one already in 2183 the header. This updating will be done at the last possible moment 2184 before the packet is forwarded, in order to assure the packet has the 2185 most current metrics on it when it leaves. 2187 10.4. Flow-State Creation, Use, and Maintenance 2189 The flow-state portion of the protocol enables a sender to obtain 2190 promises from all nodes along a path to a destination that a 2191 certain set of resources are available along the path, and that 2192 the intermediate nodes are committed to making these resources 2193 available for the particular flow. This allows a sender to obtain 2194 better-than-best-effort Quality of Service for a flow by obtaining 2195 promises from the intermediate nodes to reserve the resources needed 2196 to provide that QoS. 2198 Unlike prior QoS work in wired networks, at this point we cannot 2199 formally characterize or bound exactly what type of services the 2200 flow-state protocol will be able to offer. The goal is to provide 2201 CBR and TCP streams with the ability to specify and obtain a 2202 minimum bandwidth and delay/jitter bound. If the environment is 2203 particularly harsh, it is possible that only best-effort service will 2204 be offerable. It is this intuition that leads us to the system of 2205 promises and notifications. Experimentally, we hope to determine 2206 how stable and effective this system will be in a multi-hop ad hoc 2207 network environment. 2209 10.4.1. Requesting Promises along Existing Paths 2211 Similar to the use of the path metrics header, at any time a promise 2212 can be requested or changed along any path an originator is currently 2213 using. Once an originating node has created a path-identifier 2214 for a route through the network, it can request a promise of 2215 network resources along that route by first generating a new 2216 flow-identifier to identify the promise. The originator then fills 2217 out a flow-request header (written as Flow Request) and inserts it 2218 into any packet sent along that path. 2220 Figure 3 shows the conceptual layout of a Flow Request, which 2221 contains the new path-identifier assigned by the originator, the 2222 flow-identifier of the promise that this request supersedes (if any), 2223 the requested lifetime of the promise, and the QoS parameters that 2224 describe the requested promise itself. Section 10.6.3 provides the 2225 detailed packet format. The use of the minimum and requested fields 2226 for the QoS parameters differs depending on whether the Flow Request 2227 is piggybacked on a Route Request or not, as described below. 2229 When a Flow Request piggybacked on a unicast packet is received by a 2230 node, the node performs the following steps: 2232 - If the node is the destination of the packet, it converts the 2233 Flow Request into a Measure with type return and uses the current 2234 values in the desired fields of the Flow Request to populate the 2235 fields of the Measure. It then piggybacks the Measure onto any 2236 packet being returned to the originator. 2238 - Else if the intermediate node has available enough resources to 2239 meet the minimum requested promise in the Flow Request, it: 2241 * Sets aside the maximum of its available resources and the 2242 desired resources. The set aside resources are held in a 2243 tentative promise pool until the promise is confirmed, or a 2244 relatively short timeout expires. 2246 * Nodes can recycle resources from listed old flow-id 2248 +--------------------------------------+ 2249 | flow-id | old flow-id | 2250 +--------------------------------------+ 2251 | lifetime | 2252 +--------------------------------------+ 2253 | capacity | min | desired | 2254 | latency | min | desired | 2255 |variation | min | desired | 2256 | loss | min | desired | 2257 +--------------------------------------+ 2259 Figure 3: Conceptual layout of the Flow Request header. 2261 * Updates the desired fields of the Flow Request to reflect 2262 the resources set aside (there is questionable value in a 2263 down stream node allocating more resources to a flow than an 2264 upstream node can currently handle). 2266 * Forward the packet and piggybacked Flow Request to the next 2267 node on the path. 2269 - Else, the node does not have enough resources to meet the 2270 minimum requested promise, so it sends the originator a Route 2271 Error piggybacked with a Measure reflecting the minimum of the 2272 current values of the desired fields in the Flow Request and the 2273 available resources. The type field is set to refused. Such a 2274 Measure enables the originator to learn three things: that its 2275 requested cannot be satisfied along the given path; the identity 2276 of the bottleneck node; and the available resources up to and 2277 through the bottleneck node. 2279 When the originating node receives a Measure header of type return 2280 for a flow on which it has an outstanding Flow Request, it accepts 2281 the promised level of service by changing the type of the Measure 2282 header to confirm and piggybacking the header on any packet going 2283 along the flow. This informs the intermediate nodes to move the set 2284 aside resources from the tentative promise pool to the allocated 2285 pool, and enables upstream nodes to free any set aside resources in 2286 excess of the capacity of a bottleneck downstream node. 2288 The use of the old flow-id to recycle resources is important for two 2289 reasons. First, it enables an originator to attempt to increase or 2290 decrease the amount of a current promise without losing the resources 2291 it already has promised. Second, both packet loss and the expanding 2292 ring search of Route Discovery may result in several Flow Requests 2293 being sent for the same flow. If subsequent Flow Requests for a 2294 flow were not able to notify intermediate nodes that they can reuse 2295 resources set aside while processing earlier Flow Requests, the 2296 network could quickly reach a state where admissible flows are being 2297 needlessly rejected. 2299 10.4.2. Requesting Promises as Part of Route Discovery 2301 The scheme for requesting promises described in the previous section 2302 has the advantage that it enables an originator to request or update 2303 a promise for a flow along any route currently in its route cache, 2304 regardless of how it obtained the route. For the common case in 2305 which a node wishes to obtain a resource promise for a new flow to 2306 a previously unknown destination, we can integrate the flow request 2307 with the Route Discovery for the destination. 2309 Integrating the flow request with Route Discovery enables us to avoid 2310 the inefficiency of discovering routes that will not be usable by the 2311 flow due to insufficient resources. The integration of flow requests 2312 with Route Discovery also allows us to avoid a common pitfall of 2313 QoS schemes that layer a reservation signaling protocol on top of 2314 a unicast routing algorithm --- schemes without tight integration 2315 will refuse admissible flows whenever the unicast routing algorithm 2316 directs the request packets into a congested area of the network, 2317 unless the signaling protocol also provides a method to backtrack 2318 the request and route around the congested area. Utilizing the same 2319 mechanisms currently used in Route Discovery, we can avoid the need 2320 for backtracking. 2322 We call the combination of flow requests with Route Discovery 2323 QoS-guided Route Discovery, which originating nodes can invoke simply 2324 by piggybacking a Flow Request on the Route Request. Each node 2325 receiving the Flow Request uses the same algorithm described in 2326 Section 10.4.1, with two exceptions: 2328 - Nodes silently discard the Route Request if they can not meet 2329 minimum requirements 2331 - Unless the Route Request indicates that replying from cache is 2332 forbidden, nodes with a cached route to destination unicast the 2333 Route Request along the cached route. 2335 A node requiring a route with a QoS promise uses the following 2336 algorithm. First, it sends a Route Request that permits intermediate 2337 nodes to reply from cache. If the network is uncongested, this 2338 should frequently and quickly succeed in returning both a Route Reply 2339 and a Measure describing the available QoS along the discovered 2340 path. If after a timeout, the originating node has not received a 2341 Route Reply, it begins another Route Discovery, this time forbidding 2342 replies from cache, which will force an exploration of all feasible 2343 paths to the destination. 2345 This scheme does risk an implosion of unicast Requests at the target 2346 of the Route Discovery (e.g., if target is a popular server to which 2347 many nodes have cached routes). At the cost of additional complexity 2348 and soft-state, it would be possible to add hold-downs at the nodes 2349 surrounding the target so that only the first few Requests are 2350 forwarded towards the target. 2352 10.4.3. Providing Notifications of Changing Path Metrics 2354 When a node detects that it must break a promise, it must notify the 2355 node to which it made that promise. It is an open question how the 2356 now reduced resources should be distributed among the flows. We 2357 currently pick the minimum set of promises to break that leave the 2358 other promises unchanged. 2360 The difficulty in providing notification of a changed path metric is 2361 getting this information back to the source. When promise must be 2362 broken at a node B, it sends a Measure to the originator indicating 2363 what resources are now available. The use of Measure headers to 2364 determine the currently available resources along a path is more 2365 problematic, however, as for every Measure sent by the originator, 2366 the destination must send a response containing the measured metrics. 2368 If the traffic is TCP, the overhead of the responses are low, as 2369 they can be piggybacked on the ACK stream. For one-way CBR traffic 2370 though, introducing the overhead of a reverse stream to carry the 2371 changing metrics could be severe. 2373 If the overhead of the responses becomes a problem, it may be 2374 possible to implement a enhanced piggyback mechanism. The approach 2375 is based on the fact that although no work has been exerted to create 2376 hop-by-hop routing information at each node, chances are good that 2377 each node can determine a next-hop for packets headed to any known 2378 destination by simply examining its route cache. By piggybacking 2379 the Measure header for one hop onto any packet that is headed to 2380 that next-hop, we can cheaply create a reverse flow of information 2381 that will eventually reach the originator of the Measure. Each 2382 node who receives a Measure with a type of return simply piggybacks 2383 the Measure for one-hop on packets that seem to be flowing the 2384 right direction back to the source. To insure the timeliness of 2385 the information, each Measure being returned to an originator could 2386 include a deadline by which the information is supposed to reach the 2387 originator. If it appears that hop-by-hop propagation will result 2388 in missing the deadline, the Measure can be unicast as a first-class 2389 packet to the originator. 2391 10.5. Expiration of State from Intermediate Nodes 2393 Since there is no guarantee that either the source or destination of 2394 a packet flow will be able to communicate with all of the nodes that 2395 carried the flow when they wish to terminate the flow, there must 2396 be time-based expiration mechanism by which intermediate nodes can 2397 purge the path-state and flow-state from their caches and reclaim the 2398 resources set aside to maintain it. However, if intermediate nodes 2399 were to purge the state of an active flow, the intermediate nodes 2400 would find themselves with packets to forward that do not contain 2401 a source route, but only contain a flow-identifier that references 2402 state they no longer hold. Since intermediate nodes do not 2403 necessarily know the timing with which the sender originates packets, 2404 an inactivity timer alone would have to be set very conservatively to 2405 prevent purging the path-state of low bit-rate connections. 2407 To solve the expiration problem, we take advantage of the relatively 2408 ``soft'' nature of the path-state and flow-state. When the state 2409 is created, the source node specifies a time after which it should 2410 be discarded (This time will typically be on the order of a hundred 2411 seconds). The source node can thereby estimate how often it must 2412 refresh the state, for example, by sending packets that contain a 2413 full source route on them. Should the state have somehow expired 2414 at an intermediate node when a packet labeled with a flow or path 2415 identifier arrives, the intermediate node can return a Route Error to 2416 the source node specifying ``missing state information'' as the cause 2417 of the Error and elicit the sender to refresh the missing state. 2419 Since all path-state information is guaranteed to have expired from 2420 the network after a bounded amount of time, nodes can safely and 2421 unambiguously reuse path- and flow-identifiers after that period. 2423 10.6. Packet Formats 2425 10.6.1. Identifier Option 2427 Path and flow identifiers are carried as an option inside the 2428 Hop-by-Hop options header. This option MAY NOT appear more than once 2429 in a single Hop-by-Hop Options header. 2431 0 1 2 3 2432 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2433 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2434 | Option Type | Option Length | Path-ID | Flow-ID | 2435 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2437 Option Type 2439 ???. A node that does not understand this option should ignore 2440 this option and continue processing the packet, and the Option 2441 Data does not change en-route (the top three bits are 000). 2443 Option Length 2445 8-bit unsigned integer. Length of the option, in octets, 2446 excluding the Option Type and Option Length fields. 2448 Path-ID 2450 The identifier assigned to this path by the node listed as the 2451 IP Source Address (Section 10.2). 2453 Flow-ID 2455 The identifier assigned by the node listed as the IP Source 2456 Address to a particular flow along the path identified by the 2457 Path-ID. If this portion is 0, the option names a path, but not 2458 a particular flow. 2460 Discussion: This encoding of the path and flow identifiers will cost 2461 8 bytes of additional header overhead in a data packet with no other 2462 extensions or options (4 bytes for the Hop-by-Hop options header, and 2463 4 bytes for the identifier option). A more compact encoding would be 2464 to define that, in a DSR network, an IP destination address with a 2465 first octet of 127 actually encodes the path and flow identifiers as 2466 follows: 2468 0 1 2 3 2469 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2470 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2471 |0 1 1 1 1 1 1 1| reserved | Path-ID | Flow-ID | 2472 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2474 The DSR module of the final destination would replace the IP 2475 destination address with its actual value before passing the packet 2476 up the stack for further processing. 2478 This encoding has the advantage that it requires no additional 2479 overhead in a data packet. The disadvantage is that if the packet 2480 was somehow received by a DSR-unaware node without first being 2481 processed by a DSR gateway node [4], the DSR-unaware node will either 2482 drop the packet or will attempt to receive it locally (since the IP 2483 destination address belongs to the loopback subnet). 2485 10.6.2. Path-Metrics Option 2487 Path-metrics are carried as an option inside the Hop-by-Hop options 2488 header. 2490 0 1 2 3 2491 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2492 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2493 | Option Type | Option Length | Path-ID | Flow-ID | 2494 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2495 | Type | Metrics... 2496 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2497 Option Type 2499 ???. A node that does not understand this option should ignore 2500 this option and continue processing the packet, and the Option 2501 Data does change en-route (the top three bits are 001). 2503 Option Length 2505 8-bit unsigned integer. Length of the option, in octets, 2506 excluding the Option Type and Option Length fields. 2508 Path-ID and Flow-ID 2510 The path identifier of the path that the metrics correspond 2511 to. If the Path-Metrics Option Type equals Measure, then the 2512 Path-ID and Flow-ID fields MUST equal those in any Identifier 2513 Option carried in the Hop-by-Hop Options Header. 2515 Type 2517 One of 2519 Measure 2521 Each node processing the option should update the metrics 2522 to reflect the conditions at that node. 2524 Reply 2526 The metrics in this option SHOULD NOT be modified by any 2527 intermediate node. They represent the metrics measured 2528 along the identified path. 2530 Confirm 2532 The metrics in this option MUST NOT be modified by any 2533 intermediate node. They represent a confirmation by 2534 the sender that will transmit traffic conforming to the 2535 listed Quality of Service metrics along the identified 2536 flow. 2538 Metrics 2540 The individual path-metrics, encoded as described in 2541 Section 10.6.4. Unknown metrics SHOULD be ignored. If a 2542 single value is provide for the metric, it MUST be interpreted 2543 as the metrics value. If two values are provided for the 2544 metric, they MUST be interpreted as the range of values taken 2545 by the metric (low value first). It is undefined for there to 2546 be more than two values for the metric. 2548 10.6.3. Flow Request Option 2550 Flow-requests are carried as an option inside the Hop-by-Hop options 2551 header. They allow a sender to request that intermediate nodes 2552 reserve sufficient resources for a flow to provide that flow with the 2553 QoS characteristics described by the metrics. 2555 0 1 2 3 2556 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2557 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2558 | Option Type | Option Length | Lifetime | 2559 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2560 | old | old | new | new | 2561 | Path-ID | Flow-ID | Path-ID | Flow-ID | 2562 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2563 | Metrics ... 2564 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2566 Option Type 2568 ???. A node that does not understand this option should ignore 2569 this option and continue processing the packet, and the Option 2570 Data does change en-route (the top three bits are 001). 2572 Option Length 2574 8-bit unsigned integer. Length of the option, in octets, 2575 excluding the Option Type and Option Length fields. 2577 old Path-ID and old Flow-ID 2579 The flow identifier provide in a previous request which this 2580 request supersedes. 2582 new Path-ID and new Flow-ID 2584 The flow identifier that will be used with to identify the 2585 packets that should receive the QoS described by the included 2586 metrics. 2588 Metrics 2590 The metrics that characterize the desired QoS, encoded as 2591 described in Section 10.6.4. Unknown metrics SHOULD be 2592 ignored. If a range of values are provided for a metric, they 2593 MUST be interpreted as the minimum acceptable value and the 2594 desired value. 2596 10.6.4. Encoding Path-Metrics 2598 Each path-metric is encoded in a modified Type-Length-Value form as 2600 0 1 2 3 2601 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2602 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2603 | Type |R| Length | Data... 2604 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2606 Type 2608 The type of metric 2610 R bit 2612 If 0, the data is a list of discrete values the metric can 2613 or did take. If 1, the data represent a range of values 2614 the metric can or did take. If a single metric value is 2615 supplied, the range is assumed to be 0 <= metric <= value. If 2616 two metric values are supplied, the range is assumed to be 2617 value1 <= metric <= value2. 2619 Option Length 2621 8-bit unsigned integer. Length of the metric, in octets, 2622 excluding the Type and Length fields. 2624 The currently defined metric types follow: 2626 Padding 2628 Type: 0 2630 The padding metric is special in that it contains no length field and 2631 no data. 2633 Available Capacity 2635 Type: 1 2636 Data encoded as 2638 0 1 2639 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 2640 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2641 | Mantissa | Shift | 2642 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2644 where the value is (Mantissa << Shift) bits per second. 2646 Delay and Delay Variation 2648 Data encoded as 2650 0 1 2651 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 2652 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2653 | Delay | 2654 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2656 Type: 2 - Delay 2658 The value is Delay milliseconds. 2660 Type: 3 - Delay Variation 2662 The value is the standard deviation of Delay, in milliseconds. 2664 Link Bidirectionality 2666 Type: 16 - Link Bidirectionality 2668 Data encoded as 2670 0 1 2671 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 2672 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2673 | # Uni-links | #Explicit ACK | 2674 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2676 where # Uni-links is the number of uni-directional links on the path, 2677 and # Explicit ACK is the number of hops which require explicit 2678 acknowledgments. 2680 Packet Loss Rate 2682 Data encoded as 2684 0 1 2685 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 2686 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2687 | # Packets Lost | 2688 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2690 where the loss rate is (# Packets Lost / 2 ** 16). 2692 Type: 17 - Path Packet Loss Rate 2694 The value is the expected packet loss rate of the entire path 2696 Type: 18 - Worst Loss Rate 2698 The value is the expected packet loss rate of the single worst link 2699 in the path. 2701 11. Constants 2703 BROADCAST_JITTER 10 milliseconds 2705 MAX_ROUTE_LEN 15 nodes 2707 Interface Indexes 2708 IF_INDEX_INVALID 0x7F 2709 IF_INDEX_MA 0x7E 2710 IF_INDEX_ROUTER 0x7D 2712 Route Cache 2713 ROUTE_CACHE_TIMEOUT 300 seconds 2715 Send Buffer 2716 SEND_BUFFER_TIMEOUT 30 seconds 2718 Request Table 2719 MAX_REQUEST_ENTRIES 32 nodes 2720 MAX_REQUEST_IDS 8 identifiers 2721 MAX_REQUEST_REXMT 16 retransmissions 2722 MAX_REQUEST_PERIOD 10 seconds 2723 REQUEST_PERIOD 500 milliseconds 2724 RING0_REQUEST_TIMEOUT 30 milliseconds 2726 Retransmission Buffer 2727 DSR_RXMT_BUFFER_SIZE 50 packets 2729 Retransmission Timer 2730 DSR_MAXRXTSHIFT 2 2732 12. IANA Considerations 2734 This document proposes the use of the Destination Options header and 2735 the Hop-by-Hop Options header, originally defined for IPv6, in IPv4. 2736 The Next Header values indicating these two extension headers thus 2737 must be reserved within the IPv4 Protocol number space. 2739 Furthermore, this document defines four new types of destination 2740 options, each of which must be assigned an Option Type value: 2742 - The DSR Route Request option, described in Section 7.1.1 2744 - The DSR Route Reply option, described in Section 7.2.1 2746 - The DSR Route Error option, described in Section 7.2.2 2748 - The DSR Acknowledgment option, described in Section 7.2.3 2750 DSR also requires a routing header Routing Type be allocated for the 2751 DSR Source Route defined in Section 7.3. 2753 In IPv4, we require two new protocol numbers be issued to identify 2754 the next header as either an IPv6-style destination option, or an 2755 IPv6-style routing header. Other protocols can make use of these 2756 protocol numbers as nodes that support them will processes any 2757 included destination options or routing headers according to the 2758 normal IPv6 semantics. 2760 13. Security Considerations 2762 This document does not specifically address security concerns. This 2763 document does assume that all nodes participating in the DSR protocol 2764 do so in good faith and with out malicious intent to corrupt the 2765 routing ability of the network. In mission-oriented environments 2766 where all the nodes participating in the DSR protocol share a 2767 common goal that motivates their participation in the protocol, the 2768 communications between the nodes can be encrypted at the physical 2769 channel or link layer to prevent attack by outsiders. 2771 Location of DSR Functions in the ISO Reference Model 2773 When designing DSR, we had to determine at what level within the 2774 protocol hierarchy to implement source routing. We considered two 2775 different options: routing at the link layer (ISO layer 2) and 2776 routing at the network layer (ISO layer 3). Originally, we opted to 2777 route at the link layer for the following reasons: 2779 - Pragmatically, running the DSR protocol at the link layer 2780 maximizes the number of mobile nodes that can participate in 2781 ad hoc networks. For example, the protocol can route equally 2782 well between IPv4 [17], IPv6 [6], and IPX [7] nodes. 2784 - Historically, DSR grew from our contemplation of a multi-hop ARP 2785 protocol [8, 9] and source routing bridges [15]. ARP [16] is a 2786 layer 2 protocol. 2788 - Technically, we designed DSR to be simple enough that that it 2789 could be implemented directly in network interface cards, well 2790 below the layer 3 software within a mobile node. We see great 2791 potential for DSR running between clouds of mobile nodes around 2792 fixed base stations. DSR would act to transparently fill in the 2793 coverage gaps between base stations. Mobile nodes that would 2794 otherwise be unable to communicate with the base station due to 2795 factors such as distance, fading, or local interference sources 2796 could then reach the base station through their peers. 2798 Ultimately, however, we decided to specify DSR as a layer 3 protocol 2799 since this is the only layer at which we could realistically support 2800 nodes with multiple interfaces of different types. 2802 Implementation Status 2804 We have implemented Dynamic Source Routing (DSR) under the 2805 FreeBSD 2.2.7 operating system running on Intel x86 platforms. 2806 FreeBSD is based on a variety of free software, including 4.4 BSD 2807 Lite from the University of California, Berkeley. 2809 During the 7 months from August 1998 to February 1999, we designed 2810 and implemented a full-scale physical testbed to enable the 2811 evaluation of ad hoc network performance in the field. The last 2812 week of February and the first week of March included demonstrations 2813 of this testbed to a number of our sponsors and partners, including 2814 Lucent Technologies, Bell Atlantic, and DARPA. A complete description 2815 of the testbed is available as a Technical Report [12]. 2817 The software is currently being ported to FreeBSD 3.3. 2819 Implementors notes: 2821 - Added field to Route Error 2823 Acknowledgments 2825 The protocol described in this draft has been designed within 2826 the CMU Monarch Project, a research project at Carnegie Mellon 2827 University which is developing adaptive networking protocols and 2828 protocol interfaces to allow truly seamless wireless and mobile node 2829 networking [10, 19]. The current members of the CMU Monarch Project 2830 include: 2832 - Robert V. Barron 2834 - Josh Broch 2836 - Yih-Chun Hu 2838 - Jorjeta Jetcheva 2840 - David B. Johnson 2842 - Qifa Ke 2844 - David A. Maltz 2846 References 2848 [1] M. Allman, V. Paxson, and W. Stevens. Tcp congestion control. 2849 Internet Request For Comments RFC 2581, April 1999. 2851 [2] R. Braden, editor. Requirements for Internet Hosts -- 2852 Communication Layers. RFC 1122, October 1989. 2854 [3] Scott Bradner. Key words for use in RFCs to Indicate 2855 Requirement Levels. RFC 2119, March 1997. 2857 [4] Josh Broch, David A. Maltz, and David B. Johnson. Supporting 2858 Hierarchy and Heterogeneous Interfaces in Multi-Hop Wireless 2859 Ad Hoc Networks. In Proceedings of the Workshop on Mobile 2860 Computing held in conjunction with the International Symposium 2861 on Parallel Architectures, Algorithms, and Networks, pages 2862 370--375, Perth, Australia, June 1999. 2864 [5] M. Scott Corson and Joe Macker. Mobile Ad hoc Networking 2865 (MANET): Routing Protocol Performance Issues and Evaluation 2866 Considerations howpublished = RFC 2501, month = jan, year = 2867 1999. 2869 [6] Stephen E. Deering and Robert M. Hinden. Internet Protocol, 2870 version 6 (IPv6) Specification. RFC 2460, December 1998. 2872 [7] IPX Router Specification. Novell Part Number 107-000029-001, 2873 Document Version 1.30, March 1996. 2875 [8] David B. Johnson. Routing in Ad Hoc Networks of Mobile Hosts. 2876 In Proceedings of the IEEE Workshop on Mobile Computing Systems 2877 and Applications, pages 158--163, December 1994. 2879 [9] David B. Johnson and David A. Maltz. Dynamic Source Routing in 2880 Ad Hoc Wireless Networks. In Mobile Computing, edited by Tomasz 2881 Imielinski and Hank Korth, chapter 5, pages 153--181. Kluwer 2882 Academic Publishers, 1996. 2884 [10] David B. Johnson and David A. Maltz. Protocols for Adaptive 2885 Wireless and Mobile Networking. IEEE Personal Communications, 2886 3(1):34--42, February 1996. 2888 [11] Jian Liu and Suresh Singh. Atcp: Tcp for mobile ad hoc 2889 networks. Available from web page??? Personal Communication, 2890 June 1999. 2892 [12] David A. Maltz, Josh Broch, and David B. Johnson. Experiences 2893 Designing and Building a Multi-Hop Wireless Ad Hoc Network 2894 Testbed. Technical Report 99-116, School of Computer Science, 2895 Carnegie Mellon University, March 1999. 2897 [13] Brian D. Noble, M. Satyanarayanan, Dushyanth Narayanan, 2898 Eric J. Tilton, Jason Flinn, and Kevin R. Walker. Agile 2899 Application-Aware Adaptation for Mobility. In Proceedings of 2900 the 16th ACM Symposium on Operating System Principles, pages 2901 276--287, St. Malo, France, October 1997. 2903 [14] Charles Perkins, editor. IP Mobility Support. RFC 2002, 2904 October 1996. 2906 [15] Radia Perlman. Interconnections: Bridges and Routers. 2907 Addison-Wesley, Reading, Massachusetts, 1992. 2909 [16] David C. Plummer. An Ethernet address resolution protocol: 2910 Or converting network protocol addresses to 48.bit Ethernet 2911 addresses for transmission on Ethernet hardware. RFC 826, 2912 November 1982. 2914 [17] J. Postel. Internet Protocol. RFC 791, September 1981. 2916 [18] J. Postel. Transmission Control Protocol. RFC 793, September 2917 1981. 2919 [19] The CMU Monarch Project. http://www.monarch.cs.cmu.edu/. 2920 Computer Science Department, Carnegie Mellon University. 2922 [20] J. Reynolds and J. Postel. Assigned Numbers. RFC 1700, October 2923 1994. 2925 [21] Srinivasan Seshan, Mark Stemm, and Randy H. Katz. Spand: 2926 Shared passive network performance discovery. In Proceedings of 2927 the USENIX Symposium on Internet Technologies and Systems, pages 2928 135--146, dec 1997. 2930 [22] W. Richard Stevens. TCP/IP IIlustrated, The Protocols, 2931 volume 1. Addison-Welsley, 1994. 2933 [23] Andrew S. Tannenbaum. Computer Networks. Prentice Hall, third 2934 edition, 1996. 2936 [24] Gary R. Wright and W. Richard Stevens. TCP/IP IIlustrated, The 2937 Implementation, volume 2. Addison-Welsley, 1995. 2939 Chair's Address 2941 The Working Group can be contacted via its current chairs: 2943 M. Scott Corson 2944 Institute for Systems Research 2945 University of Maryland 2946 College Park, MD 20742 2947 USA 2949 Phone: +1 301 405-6630 2950 Email: corson@isr.umd.edu 2952 Joseph Macker 2953 Information Technology Division 2954 Naval Research Laboratory 2955 Washington, DC 20375 2956 USA 2958 Phone: +1 202 767-2001 2959 Email: macker@itd.nrl.navy.mil 2961 Authors' Addresses 2963 Questions about this document can also be directed to the authors: 2965 Josh Broch 2966 Carnegie Mellon University 2967 Electrical and Computer Engineering 2968 5000 Forbes Avenue 2969 Pittsburgh, PA 15213-3890 2970 USA 2972 Phone: +1 412 268-3056 2973 Fax: +1 412 268-7196 2974 Email: broch@cs.cmu.edu 2976 David B. Johnson 2977 Carnegie Mellon University 2978 Computer Science Department 2979 5000 Forbes Avenue 2980 Pittsburgh, PA 15213-3891 2981 USA 2983 Phone: +1 412 268-7399 2984 Fax: +1 412 268-5576 2985 Email: dbj@cs.cmu.edu 2987 David A. Maltz 2988 Carnegie Mellon University 2989 Computer Science Department 2990 5000 Forbes Avenue 2991 Pittsburgh, PA 15213-3891 2992 USA 2994 Phone: +1 412 268-3621 2995 Fax: +1 412 268-5576 2996 Email: dmaltz@cs.cmu.edu