idnits 2.17.1 draft-ietf-manet-dsr-06.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 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. 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 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.) -- Couldn't find a document date in the document -- date freshness check skipped. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Possible downref: Non-RFC (?) normative reference: ref. '1' -- Possible downref: Non-RFC (?) normative reference: ref. '2' -- Possible downref: Non-RFC (?) normative reference: ref. '5' ** Obsolete normative reference: RFC 2460 (ref. '6') (Obsoleted by RFC 8200) -- Possible downref: Non-RFC (?) normative reference: ref. '8' -- Possible downref: Non-RFC (?) normative reference: ref. '9' -- Possible downref: Normative reference to a draft: 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' -- Possible downref: Non-RFC (?) normative reference: ref. '14' -- Possible downref: Non-RFC (?) normative reference: ref. '15' -- Possible downref: Non-RFC (?) normative reference: ref. '16' -- Possible downref: Non-RFC (?) normative reference: ref. '17' -- Possible downref: Non-RFC (?) normative reference: ref. '18' -- Possible downref: Non-RFC (?) normative reference: ref. '19' -- Possible downref: Non-RFC (?) normative reference: ref. '20' -- 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' ** Obsolete normative reference: RFC 793 (ref. '28') (Obsoleted by RFC 9293) ** Obsolete normative reference: RFC 1700 (ref. '29') (Obsoleted by RFC 3232) -- Possible downref: Non-RFC (?) normative reference: ref. '30' -- Possible downref: Non-RFC (?) normative reference: ref. '31' -- Possible downref: Non-RFC (?) normative reference: ref. '32' -- Possible downref: Non-RFC (?) normative reference: ref. '33' Summary: 5 errors (**), 0 flaws (~~), 2 warnings (==), 26 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 IETF MANET Working Group David B. Johnson, Rice University 2 INTERNET-DRAFT David A. Maltz, AON Networks 3 21 November 2001 Yih-Chun Hu, Rice University 4 Jorjeta G. Jetcheva, Carnegie Mellon University 6 The Dynamic Source Routing Protocol 7 for Mobile Ad Hoc Networks (DSR) 9 11 Status of This Memo 13 This document is an Internet-Draft and is subject to all provisions 14 of Section 10 of RFC 2026. 16 Internet-Drafts are working documents of the Internet Engineering 17 Task Force (IETF), its areas, and its working groups. Note 18 that other groups may also distribute working documents as 19 Internet-Drafts. 21 Internet-Drafts are draft documents valid for a maximum of six months 22 and may be updated, replaced, or obsoleted by other documents at 23 any time. It is inappropriate to use Internet-Drafts as reference 24 material or to cite them other than as "work in progress". 26 The list of current Internet-Drafts can be accessed at 27 http://www.ietf.org/ietf/1id-abstracts.txt 29 The list of Internet-Draft Shadow Directories can be accessed at 30 http://www.ietf.org/shadow.html. 32 This Internet-Draft is a submission to the IETF Mobile Ad Hoc 33 Networks (MANET) Working Group. Comments on this draft may be sent 34 to the Working Group at manet@itd.nrl.navy.mil, or may be sent 35 directly to the authors. 37 Abstract 39 The Dynamic Source Routing protocol (DSR) is a simple and efficient 40 routing protocol designed specifically for use in multi-hop wireless 41 ad hoc networks of mobile nodes. DSR allows the network to be 42 completely self-organizing and self-configuring, without the need 43 for any existing network infrastructure or administration. The 44 protocol is composed of the two main mechanisms of "Route Discovery" 45 and "Route Maintenance", which work together to allow nodes to 46 discover and maintain source routes to arbitrary destinations in the 47 ad hoc network. The use of source routing allows packet routing 48 to be trivially loop-free, avoids the need for up-to-date routing 49 information in the intermediate nodes through which packets are 50 forwarded, and allows nodes forwarding or overhearing packets to 51 cache the routing information in them for their own future use. All 52 aspects of the protocol operate entirely on-demand, allowing the 53 routing packet overhead of DSR to scale automatically to only that 54 needed to react to changes in the routes currently in use. This 55 document specifies the operation of the DSR protocol for routing 56 unicast IPv4 packets in multi-hop wireless ad hoc networks. 58 Contents 60 Status of This Memo i 62 Abstract ii 64 1. Introduction 1 66 2. Assumptions 3 68 3. DSR Protocol Overview 5 70 3.1. Basic DSR Route Discovery . . . . . . . . . . . . . . . . 5 71 3.2. Basic DSR Route Maintenance . . . . . . . . . . . . . . . 7 72 3.3. Additional Route Discovery Features . . . . . . . . . . . 9 73 3.3.1. Caching Overheard Routing Information . . . . . . 9 74 3.3.2. Replying to Route Requests using Cached Routes . 10 75 3.3.3. Preventing Route Reply Storms . . . . . . . . . . 11 76 3.3.4. Route Request Hop Limits . . . . . . . . . . . . 13 77 3.4. Additional Route Maintenance Features . . . . . . . . . . 14 78 3.4.1. Packet Salvaging . . . . . . . . . . . . . . . . 14 79 3.4.2. Queued Packets Destined over a Broken Link . . . 14 80 3.4.3. Automatic Route Shortening . . . . . . . . . . . 15 81 3.4.4. Increased Spreading of Route Error Messages . . . 16 83 4. Conceptual Data Structures 17 85 4.1. Route Cache . . . . . . . . . . . . . . . . . . . . . . . 17 86 4.2. Send Buffer . . . . . . . . . . . . . . . . . . . . . . . 20 87 4.3. Route Request Table . . . . . . . . . . . . . . . . . . . 21 88 4.4. Gratuitous Route Reply Table . . . . . . . . . . . . . . 22 89 4.5. Network Interface Queue and Retransmission Buffer . . . . 23 91 5. DSR Header Format 25 93 5.1. Fixed Portion of DSR Header . . . . . . . . . . . . . . . 26 94 5.2. Route Request Option . . . . . . . . . . . . . . . . . . 28 95 5.3. Route Reply Option . . . . . . . . . . . . . . . . . . . 30 96 5.4. Route Error Option . . . . . . . . . . . . . . . . . . . 32 97 5.5. Acknowledgment Request Option . . . . . . . . . . . . . . 35 98 5.6. Acknowledgment Option . . . . . . . . . . . . . . . . . . 36 99 5.7. DSR Source Route Option . . . . . . . . . . . . . . . . . 37 100 5.8. Pad1 Option . . . . . . . . . . . . . . . . . . . . . . . 39 101 5.9. PadN Option . . . . . . . . . . . . . . . . . . . . . . . 40 103 6. Detailed Operation 41 105 6.1. General Packet Processing . . . . . . . . . . . . . . . . 41 106 6.1.1. Originating a Packet . . . . . . . . . . . . . . 41 107 6.1.2. Adding a DSR Header to a Packet . . . . . . . . . 41 108 6.1.3. Adding a DSR Source Route Option to a Packet . . 42 109 6.1.4. Processing a Received Packet . . . . . . . . . . 43 110 6.1.5. Processing a Received DSR Source Route Option . . 45 111 6.2. Route Discovery Processing . . . . . . . . . . . . . . . 48 112 6.2.1. Originating a Route Request . . . . . . . . . . . 48 113 6.2.2. Processing a Received Route Request Option . . . 50 114 6.2.3. Generating a Route Reply using the Route Cache . 51 115 6.2.4. Originating a Route Reply . . . . . . . . . . . . 54 116 6.2.5. Processing a Received Route Reply Option . . . . 55 117 6.3. Route Maintenance Processing . . . . . . . . . . . . . . 57 118 6.3.1. Using Link-Layer Acknowledgments . . . . . . . . 57 119 6.3.2. Using Passive Acknowledgments . . . . . . . . . . 58 120 6.3.3. Using Network-Layer Acknowledgments . . . . . . . 59 121 6.3.4. Originating a Route Error . . . . . . . . . . . . 62 122 6.3.5. Processing a Received Route Error Option . . . . 63 123 6.3.6. Salvaging a Packet . . . . . . . . . . . . . . . 64 125 7. Protocol Constants and Configuration Variables 66 127 8. IANA Considerations 67 129 9. Security Considerations 68 131 Appendix A. Link-MaxLife Cache Description 69 133 Appendix B. Location of DSR in the ISO Network Reference Model 71 135 Appendix C. Implementation and Evaluation Status 72 137 Changes from Previous Version of the Draft 73 139 Acknowledgements 76 141 References 77 143 Chair's Address 80 145 Authors' Addresses 81 146 1. Introduction 148 The Dynamic Source Routing protocol (DSR) [13, 14] is a simple and 149 efficient routing protocol designed specifically for use in multi-hop 150 wireless ad hoc networks of mobile nodes. Using DSR, the network 151 is completely self-organizing and self-configuring, requiring no 152 existing network infrastructure or administration. Network nodes 153 cooperate to forward packets for each other to allow communication 154 over multiple "hops" between nodes not directly within wireless 155 transmission range of one another. As nodes in the network move 156 about or join or leave the network, and as wireless transmission 157 conditions such as sources of interference change, all routing is 158 automatically determined and maintained by the DSR routing protocol. 159 Since the number or sequence of intermediate hops needed to reach any 160 destination may change at any time, the resulting network topology 161 may be quite rich and rapidly changing. 163 The DSR protocol allows nodes to dynamically discover a source 164 route across multiple network hops to any destination in the ad hoc 165 network. Each data packet sent then carries in its header the 166 complete, ordered list of nodes through which the packet will pass, 167 allowing packet routing to be trivially loop-free and avoiding the 168 need for up-to-date routing information in the intermediate nodes 169 through which the packet is forwarded. By including this source 170 route in the header of each data packet, other nodes forwarding or 171 overhearing any of these packets can also easily cache this routing 172 information for future use. 174 In designing DSR, we sought to create a routing protocol that had 175 very low overhead yet was able to react very quickly to changes in 176 the network. The DSR protocol provides highly reactive service in 177 order to help ensure successful delivery of data packets in spite of 178 node movement or other changes in network conditions. 180 The DSR protocol is composed of two main mechanisms that work 181 together to allow the discovery and maintenance of source routes in 182 the ad hoc network: 184 - Route Discovery is the mechanism by which a node S wishing to 185 send a packet to a destination node D obtains a source route 186 to D. Route Discovery is used only when S attempts to send a 187 packet to D and does not already know a route to D. 189 - Route Maintenance is the mechanism by which node S is able 190 to detect, while using a source route to D, if the network 191 topology has changed such that it can no longer use its route 192 to D because a link along the route no longer works. When Route 193 Maintenance indicates a source route is broken, S can attempt to 194 use any other route it happens to know to D, or can invoke Route 195 Discovery again to find a new route for subsequent packets to D. 197 Route Maintenance for this route is used only when S is actually 198 sending packets to D. 200 In DSR, Route Discovery and Route Maintenance each operate entirely 201 "on demand". In particular, unlike other protocols, DSR requires no 202 periodic packets of any kind at any layer within the network. For 203 example, DSR does not use any periodic routing advertisement, link 204 status sensing, or neighbor detection packets, and does not rely on 205 these functions from any underlying protocols in the network. This 206 entirely on-demand behavior and lack of periodic activity allows 207 the number of overhead packets caused by DSR to scale all the way 208 down to zero, when all nodes are approximately stationary with 209 respect to each other and all routes needed for current communication 210 have already been discovered. As nodes begin to move more or 211 as communication patterns change, the routing packet overhead of 212 DSR automatically scales to only that needed to track the routes 213 currently in use. Network topology changes not affecting routes 214 currently in use are ignored and do not cause reaction from the 215 protocol. 217 In response to a single Route Discovery (as well as through routing 218 information from other packets overheard), a node may learn and cache 219 multiple routes to any destination. This allows the reaction to 220 routing changes to be much more rapid, since a node with multiple 221 routes to a destination can try another cached route if the one it 222 has been using should fail. This caching of multiple routes also 223 avoids the overhead of needing to perform a new Route Discovery each 224 time a route in use breaks. 226 The operation of both Route Discovery and Route Maintenance in DSR 227 are designed to allow uni-directional links and asymmetric routes 228 to be easily supported. In particular, as noted in Section 2, in 229 wireless networks, it is possible that a link between two nodes may 230 not work equally well in both directions, due to differing antenna 231 or propagation patterns or sources of interference. DSR allows such 232 uni-directional links to be used when necessary, improving overall 233 performance and network connectivity in the system. 235 This document specifies the operation of the DSR protocol for 236 routing unicast IPv4 packets in multi-hop wireless ad hoc networks. 237 Advanced, optional features, such as Quality of Service (QoS) support 238 and efficient multicast routing, and operation of DSR with IPv6 [6], 239 are covered in other documents. The specification of DSR in this 240 document provides a compatible base on which such features can be 241 added, either independently or by integration with the DSR operation 242 specified here. 244 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 245 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 246 document are to be interpreted as described in RFC 2119 [4]. 248 2. Assumptions 250 We assume in this document that all nodes wishing to communicate with 251 other nodes within the ad hoc network are willing to participate 252 fully in the protocols of the network. In particular, each node 253 participating in the ad hoc network SHOULD also be willing to forward 254 packets for other nodes in the network. 256 The diameter of an ad hoc network is the minimum number of hops 257 necessary for a packet to reach from any node located at one extreme 258 edge of the ad hoc network to another node located at the opposite 259 extreme. We assume that this diameter will often be small (e.g., 260 perhaps 5 or 10 hops), but may often be greater than 1. 262 Packets may be lost or corrupted in transmission on the wireless 263 network. We assume that a node receiving a corrupted packet can 264 detect the error and discard the packet. 266 Nodes within the ad hoc network MAY move at any time without notice, 267 and MAY even move continuously, but we assume that the speed with 268 which nodes move is moderate with respect to the packet transmission 269 latency and wireless transmission range of the particular underlying 270 network hardware in use. In particular, DSR can support very 271 rapid rates of arbitrary node mobility, but we assume that nodes do 272 not continuously move so rapidly as to make the flooding of every 273 individual data packet the only possible routing protocol. 275 A common feature of many network interfaces, including most current 276 LAN hardware for broadcast media such as wireless, is the ability 277 to operate the network interface in "promiscuous" receive mode. 278 This mode causes the hardware to deliver every received packet to 279 the network driver software without filtering based on link-layer 280 destination address. Although we do not require this facility, some 281 of our optimizations can take advantage of its availability. Use 282 of promiscuous mode does increase the software overhead on the CPU, 283 but we believe that wireless network speeds are more the inherent 284 limiting factor to performance in current and future systems; we also 285 believe that portions of the protocol are suitable for implementation 286 directly within a programmable network interface unit to avoid this 287 overhead on the CPU [14]. Use of promiscuous mode may also increase 288 the power consumption of the network interface hardware, depending 289 on the design of the receiver hardware, and in such cases, DSR can 290 easily be used without the optimizations that depend on promiscuous 291 receive mode, or can be programmed to only periodically switch the 292 interface into promiscuous mode. Use of promiscuous receive mode is 293 entirely optional. 295 Wireless communication ability between any pair of nodes may at 296 times not work equally well in both directions, due for example to 297 differing antenna or propagation patterns or sources of interference 298 around the two nodes [1, 18]. That is, wireless communications 299 between each pair of nodes will in many cases be able to operate 300 bi-directionally, but at times the wireless link between two nodes 301 may be only uni-directional, allowing one node to successfully send 302 packets to the other while no communication is possible in the 303 reverse direction. Although many routing protocols operate correctly 304 only over bi-directional links, DSR can successfully discover and 305 forward packets over paths that contain uni-directional links. 306 Some MAC protocols, however, such as MACA [17], MACAW [2], or IEEE 307 802.11 [11], limit unicast data packet transmission to bi-directional 308 links, due to the required bi-directional exchange of RTS and CTS 309 packets in these protocols and due to the link-layer acknowledgement 310 feature in IEEE 802.11; when used on top of MAC protocols such as 311 these, DSR can take advantage of additional optimizations, such as 312 the ability to reverse a source route to obtain a route back to the 313 origin of the original route. 315 The IP address used by a node using the DSR protocol MAY be assigned 316 by any mechanism (e.g., static assignment or use of DHCP for dynamic 317 assignment [7]), although the method of such assignment is outside 318 the scope of this specification. 320 3. DSR Protocol Overview 322 3.1. Basic DSR Route Discovery 324 When some source node originates a new packet addressed to some 325 destination node, the source node places in the header of the packet 326 a source route giving the sequence of hops that the packet is to 327 follow on its way to the destination. Normally, the sender will 328 obtain a suitable source route by searching its "Route Cache" of 329 routes previously learned; if no route is found in its cache, it will 330 initiate the Route Discovery protocol to dynamically find a new route 331 to this destination node. In this case, we call the source node 332 the "initiator" and the destination node the "target" of the Route 333 Discovery. 335 For example, suppose a node A is attempting to discover a route to 336 node E. The Route Discovery initiated by node A in this example 337 would proceed as follows: 339 ^ "A" ^ "A,B" ^ "A,B,C" ^ "A,B,C,D" 340 | id=2 | id=2 | id=2 | id=2 341 +-----+ +-----+ +-----+ +-----+ +-----+ 342 | A |---->| B |---->| C |---->| D |---->| E | 343 +-----+ +-----+ +-----+ +-----+ +-----+ 344 | | | | 345 v v v v 347 To initiate the Route Discovery, node A transmits a "Route 348 Request" as a single local broadcast packet, which is received by 349 (approximately) all nodes currently within wireless transmission 350 range of A, including node B in this example. Each Route Request 351 identifies the initiator and target of the Route Discovery, and 352 also contains a unique request identification (2, in this example), 353 determined by the initiator of the Request. Each Route Request also 354 contains a record listing the address of each intermediate node 355 through which this particular copy of the Route Request has been 356 forwarded. This route record is initialized to an empty list by the 357 initiator of the Route Discovery. In this example, the route record 358 initially lists only node A. 360 When another node receives this Route Request (such as node B in this 361 example), if it is the target of the Route Discovery, it returns 362 a "Route Reply" to the initiator of the Route Discovery, giving 363 a copy of the accumulated route record from the Route Request; 364 when the initiator receives this Route Reply, it caches this route 365 in its Route Cache for use in sending subsequent packets to this 366 destination. 368 Otherwise, if this node receiving the Route Request has recently seen 369 another Route Request message from this initiator bearing this same 370 request identification and target address, or if this node's own 371 address is already listed in the route record in the Route Request, 372 this node discards the Request. Otherwise, this node appends its 373 own address to the route record in the Route Request and propagates 374 it by transmitting it as a local broadcast packet (with the same 375 request identification). In this example, node B broadcast the Route 376 Request, which is received by node C; nodes C and D each also, in 377 turn, broadcast the Request, resulting in a copy of the Request being 378 received by node E. 380 In returning the Route Reply to the initiator of the Route Discovery, 381 such as in this example, node E replying back to node A, node E will 382 typically examine its own Route Cache for a route back to A, and if 383 found, will use it for the source route for delivery of the packet 384 containing the Route Reply. Otherwise, E SHOULD perform its own 385 Route Discovery for target node A, but to avoid possible infinite 386 recursion of Route Discoveries, it MUST piggyback this Route Reply 387 on the packet containing its own Route Request for A. It is also 388 possible to piggyback other small data packets, such as a TCP SYN 389 packet [28], on a Route Request using this same mechanism. 391 Node E could instead simply reverse the sequence of hops in the route 392 record that it is trying to send in the Route Reply, and use this as 393 the source route on the packet carrying the Route Reply itself. For 394 MAC protocols such as IEEE 802.11 that require a bi-directional frame 395 exchange as part of the MAC protocol [11], the discovered source 396 route MUST be reversed in this way to return the Route Reply since it 397 tests the discovered route to ensure it is bi-directional before the 398 Route Discovery initiator begins using the route; this route reversal 399 also avoids the overhead of a possible second Route Discovery. 400 However, this route reversal technique will prevent the discovery 401 of routes using uni-directional links, and in wireless environments 402 where the use of uni-directional links is permitted, such routes may 403 in some cases be more efficient than those with only bi-directional 404 links, or they may be the only way to achieve connectivity to the 405 target node. 407 When initiating a Route Discovery, the sending node saves a copy of 408 the original packet (that triggered the Discovery) in a local buffer 409 called the "Send Buffer". The Send Buffer contains a copy of each 410 packet that cannot be transmitted by this node because it does not 411 yet have a source route to the packet's destination. Each packet in 412 the Send Buffer is logically associated with the time that it was 413 placed into the Send Buffer and is discarded after residing in the 414 Send Buffer for some timeout period; if necessary for preventing the 415 Send Buffer from overflowing, a FIFO or other replacement strategy 416 MAY also be used to evict packets even before they expire. 418 While a packet remains in the Send Buffer, the node SHOULD 419 occasionally initiate a new Route Discovery for the packet's 420 destination address. However, the node MUST limit the rate at which 421 such new Route Discoveries for the same address are initiated, since 422 it is possible that the destination node is not currently reachable. 423 In particular, due to the limited wireless transmission range and the 424 movement of the nodes in the network, the network may at times become 425 partitioned, meaning that there is currently no sequence of nodes 426 through which a packet could be forwarded to reach the destination. 427 Depending on the movement pattern and the density of nodes in the 428 network, such network partitions may be rare or may be common. 430 If a new Route Discovery was initiated for each packet sent by a 431 node in such a partitioned network, a large number of unproductive 432 Route Request packets would be propagated throughout the subset 433 of the ad hoc network reachable from this node. In order to 434 reduce the overhead from such Route Discoveries, a node SHOULD use 435 an exponential back-off algorithm to limit the rate at which it 436 initiates new Route Discoveries for the same target, doubling the 437 timeout between each successive Discovery initiated for the same 438 target. If the node attempts to send additional data packets to this 439 same destination node more frequently than this limit, the subsequent 440 packets SHOULD be buffered in the Send Buffer until a Route Reply is 441 received giving a route to this destination, but the node MUST NOT 442 initiate a new Route Discovery until the minimum allowable interval 443 between new Route Discoveries for this target has been reached. This 444 limitation on the maximum rate of Route Discoveries for the same 445 target is similar to the mechanism required by Internet nodes to 446 limit the rate at which ARP Requests are sent for any single target 447 IP address [3]. 449 3.2. Basic DSR Route Maintenance 451 When originating or forwarding a packet using a source route, each 452 node transmitting the packet is responsible for confirming that the 453 packet has been received by the next node along the source route; the 454 packet SHOULD be retransmitted (up to a maximum number of attempts) 455 until this confirmation of receipt is received. For example, in the 456 situation shown below, node A has originated a packet for node E 457 using a source route through intermediate nodes B, C, and D: 459 +-----+ +-----+ +-----+ +-----+ +-----+ 460 | A |---->| B |---->| C |-->? | D | | E | 461 +-----+ +-----+ +-----+ +-----+ +-----+ 463 In this case, node A is responsible for receipt of the packet at B, 464 node B is responsible for receipt at C, node C is responsible for 465 receipt at D, and node D is responsible for receipt finally at the 466 destination E. 468 This confirmation of receipt in many cases may be provided at no cost 469 to DSR, either as an existing standard part of the MAC protocol in 470 use (such as the link-layer acknowledgement frame defined by IEEE 471 802.11 [11]), or by a "passive acknowledgement" [16] (in which, 472 for example, B confirms receipt at C by overhearing C transmit 473 the packet when forwarding it on to D). If neither of these 474 confirmation mechanisms are available, the node transmitting the 475 packet can explicitly request a DSR-specific software acknowledgement 476 be returned by the next node along the route; this software 477 acknowledgement will normally be transmitted directly to the sending 478 node, but if the link between these two nodes is uni-directional, 479 this software acknowledgement could travel over a different, 480 multi-hop path. 482 At the original sender of a packet if no receipt confirmation is 483 received after the sender has retransmitted the packet the maximum 484 number of attempts to the first intermediate node on the source 485 route, then the sender determines that this first hop of the route 486 is currently "broken". For example, in the situation shown above, 487 if the sender, node A, is unable to deliver the packet to the next 488 node B, then A determines that the hop from A to B is broken. In 489 this case, node A removes this link from its Route Cache and removes 490 the DSR routing information that it had previously added to the 491 packet. Node A then again searches its Route Cache for a route to 492 the destination node, and if no route is found in the cache, uses the 493 Route Discovery protocol again to dynamically discover a new route 494 for the packet. 496 At an intermediate node forwarding a packet, if no receipt 497 confirmation is received after the node has retransmitted the packet 498 the maximum number of attempts, this node SHOULD return a "Route 499 Error" to the original sender of the packet, identifying the link 500 over which the packet could not be forwarded. For example, in the 501 situation shown above, if C is unable to deliver the packet to the 502 next node D, then C returns a Route Error to A, stating that the link 503 from C to D is currently "broken". Node A then removes this broken 504 link from its cache; any retransmission of the original packet can 505 be performed by upper layer protocols such as TCP, if necessary. 506 For sending such a retransmission or other packets to this same 507 destination E, if A has in its Route Cache another route to E 508 (for example, from additional Route Replies from its earlier Route 509 Discovery, or from having overheard sufficient routing information 510 from other packets), it can send the packet using the new route 511 immediately. Otherwise, it SHOULD perform a new Route Discovery for 512 this target (subject to the back-off described in Section 3.1). 514 3.3. Additional Route Discovery Features 516 3.3.1. Caching Overheard Routing Information 518 A node forwarding or otherwise overhearing any packet SHOULD add all 519 usable routing information from that packet to its own Route Cache. 520 The usefulness of routing information in a packet depends on the 521 directionality characteristics of the physical medium (Section 2), as 522 well as the MAC protocol being used. Specifically, three distinct 523 cases are possible: 525 - Links in the network frequently are capable of operating only 526 uni-directionally (not bi-directionally), and the MAC protocol 527 in use in the network is capable of transmitting unicast packets 528 over uni-directional links. 530 - Links in the network occasionally are capable of operating 531 only uni-directionally (not bi-directionally), but this 532 uni-directional restriction on any link is not persistent, almost 533 all links are physically bi-directional, and the MAC protocol in 534 use in the network is capable of transmitting unicast packets 535 over uni-directional links. 537 - The MAC protocol in use in the network is not capable of 538 transmitting unicast packets over uni-directional links; 539 only bi-directional links can be used by the MAC protocol for 540 transmitting unicast packets. For example, the IEEE 802.11 541 Distributed Coordination Function (DCF) MAC protocol [11] 542 is capable of transmitting a unicast packet only over a 543 bi-directional link, since the MAC protocol requires the return 544 of a link-level acknowledgement packet from the receiver and also 545 optionally requires the bi-directional exchange of an RTS and CTS 546 packet between the transmitter and receiver nodes. 548 In the first case above, for example, the source route used in a data 549 packet, the accumulated route record in a Route Request, or the route 550 being returned in a Route Reply SHOULD all be cached by any node in 551 the "forward" direction; any node SHOULD cache this information from 552 any such packet received, whether the packet was addressed to this 553 node, sent to a broadcast (or multicast) MAC address, or overheard 554 while the node's network interface is in promiscuous mode. However, 555 the "reverse" direction of the links identified in such packet 556 headers SHOULD NOT be cached. 558 For example, in the situation shown below, node A is using a source 559 route to communicate with node E: 561 +-----+ +-----+ +-----+ +-----+ +-----+ 562 | A |---->| B |---->| C |---->| D |---->| E | 563 +-----+ +-----+ +-----+ +-----+ +-----+ 565 As node C forwards a data packet along the route from A to E, it 566 SHOULD add to its cache the presence of the "forward" direction 567 links that it learns from the headers of these packets, from itself 568 to D and from D to E. Node C SHOULD NOT, in this case, cache the 569 "reverse" direction of the links identified in these packet headers, 570 from itself back to B and from B to A, since these links might be 571 uni-directional. 573 In the second case above, in which links may occasionally operate 574 uni-directionally, the links described above SHOULD be cached in both 575 directions. Furthermore, in this case, if node X overhears (e.g., 576 through promiscuous mode) a packet transmitted by node C that is 577 using a source route from node A to E, node X SHOULD cache all of 578 these links as well, also including the link from C to X over which 579 it overheard the packet. 581 In the final case, in which the MAC protocol requires physical 582 bi-directionality for unicast operation, links from a source 583 route SHOULD be cached in both directions, except when the packet 584 also contains a Route Reply, in which case only the links already 585 traversed in this source route SHOULD be cached, but the links not 586 yet traversed in this route SHOULD NOT be cached. 588 3.3.2. Replying to Route Requests using Cached Routes 590 A node receiving a Route Request for which it is not the target, 591 searches its own Route Cache for a route to the target of the 592 Request. If found, the node generally returns a Route Reply to the 593 initiator itself rather than forwarding the Route Request. In the 594 Route Reply, this node sets the route record to list the sequence of 595 hops over which this copy of the Route Request was forwarded to it, 596 concatenated with the source route to this target obtained from its 597 own Route Cache. 599 However, before transmitting a Route Reply packet that was generated 600 using information from its Route Cache in this way, a node MUST 601 verify that the resulting route being returned in the Route Reply, 602 after this concatenation, contains no duplicate nodes listed in the 603 route record. For example, the figure below illustrates a case in 604 which a Route Request for target E has been received by node F, and 605 node F already has in its Route Cache a route from itself to E: 607 +-----+ +-----+ +-----+ +-----+ 608 | A |---->| B |- >| D |---->| E | 609 +-----+ +-----+ \ / +-----+ +-----+ 610 \ / 611 \ +-----+ / 612 >| C |- 613 +-----+ 614 | ^ 615 v | 616 Route Request +-----+ 617 Route: A - B - C - F | F | Cache: C - D - E 618 +-----+ 620 The concatenation of the accumulated route record from the Route 621 Request and the cached route from F's Route Cache would include a 622 duplicate node in passing from C to F and back to C. 624 Node F in this case could attempt to edit the route to eliminate the 625 duplication, resulting in a route from A to B to C to D and on to E, 626 but in this case, node F would not be on the route that it returned 627 in its own Route Reply. DSR Route Discovery prohibits node F 628 from returning such a Route Reply from its cache; this prohibition 629 increases the probability that the resulting route is valid, since 630 node F in this case should have received a Route Error if the route 631 had previously stopped working. Furthermore, this prohibition 632 means that a future Route Error traversing the route is very likely 633 to pass through any node that sent the Route Reply for the route 634 (including node F), which helps to ensure that stale data is removed 635 from caches (such as at F) in a timely manner; otherwise, the next 636 Route Discovery initiated by A might also be contaminated by a Route 637 Reply from F containing the same stale route. If node F, due to this 638 restriction on returning a Route Reply based on information from its 639 Route Cache, does not return such a Route Reply, node F propagates 640 the Route Request normally. 642 3.3.3. Preventing Route Reply Storms 644 The ability for nodes to reply to a Route Request based on 645 information in their Route Caches, as described in Section 3.3.2, 646 could result in a possible Route Reply "storm" in some cases. In 647 particular, if a node broadcasts a Route Request for a target node 648 for which the node's neighbors have a route in their Route Caches, 649 each neighbor may attempt to send a Route Reply, thereby wasting 650 bandwidth and possibly increasing the number of network collisions in 651 the area. 653 For example, the figure below shows a situation in which nodes B, C, 654 D, E, and F all receive A's Route Request for target G, and each has 655 the indicated route cached for this target: 657 +-----+ +-----+ 658 | D |< >| C | 659 +-----+ \ / +-----+ 660 Cache: C - B - G \ / Cache: B - G 661 \ +-----+ / 662 -| A |- 663 +-----+\ +-----+ +-----+ 664 | | \--->| B | | G | 665 / \ +-----+ +-----+ 666 / \ Cache: G 667 v v 668 +-----+ +-----+ 669 | E | | F | 670 +-----+ +-----+ 671 Cache: F - B - G Cache: B - G 673 Normally, each of these nodes would attempt to reply from its own 674 Route Cache, and they would thus all send their Route Replies at 675 about the same time, since they all received the broadcast Route 676 Request at about the same time. Such simultaneous Route Replies 677 from different nodes all receiving the Route Request may cause local 678 congestion in the wireless network and may create packet collisions 679 among some or all of these Replies if the MAC protocol in use does 680 not provide sufficient collision avoidance for these packets. In 681 addition, it will often be the case that the different replies will 682 indicate routes of different lengths, as shown in this example. 684 In order to reduce these effects, if a node can put its network 685 interface into promiscuous receive mode, it MAY delay sending its 686 own Route Reply for a short period, while listening to see if the 687 initiating node begins using a shorter route first. Specifically, 688 this node MAY delay sending its own Route Reply for a random period 690 d = H * (h - 1 + r) 692 where h is the length in number of network hops for the route to be 693 returned in this node's Route Reply, r is a random floating point 694 number between 0 and 1, and H is a small constant delay (at least 695 twice the maximum wireless link propagation delay) to be introduced 696 per hop. This delay effectively randomizes the time at which each 697 node sends its Route Reply, with all nodes sending Route Replies 698 giving routes of length less than h sending their Replies before this 699 node, and all nodes sending Route Replies giving routes of length 700 greater than h sending their Replies after this node. 702 Within the delay period, this node promiscuously receives all 703 packets, looking for data packets from the initiator of this Route 704 Discovery destined for the target of the Discovery. If such a data 705 packet received by this node during the delay period uses a source 706 route of length less than or equal to h, this node may infer that the 707 initiator of the Route Discovery has already received a Route Reply 708 giving an equally good or better route. In this case, this node 709 SHOULD cancel its delay timer and SHOULD NOT send its Route Reply for 710 this Route Discovery. 712 3.3.4. Route Request Hop Limits 714 Each Route Request message contains a "hop limit" that may be used 715 to limit the number of intermediate nodes allowed to forward that 716 copy of the Route Request. This hop limit is implemented using the 717 Time-to-Live (TTL) field in the IP header of the packet carrying 718 the Route Request. As the Request is forwarded, this limit is 719 decremented, and the Request packet is discarded if the limit reaches 720 zero before finding the target. This Route Request hop limit can be 721 used to implement a variety of algorithms for controlling the spread 722 of a Route Request during a Route Discovery attempt. 724 For example, a node MAY use this hop limit to implement a 725 "non-propagating" Route Request as an initial phase of a Route 726 Discovery. A node using this technique sends its first Route Request 727 attempt for some target node using a hop limit of 1, such that any 728 node receiving the initial transmission of the Route Request will 729 not forward the Request to other nodes by re-broadcasting it. This 730 form of Route Request is called a "non-propagating" Route Request; 731 it provides an inexpensive method for determining if the target is 732 currently a neighbor of the initiator or if a neighbor node has a 733 route to the target cached (effectively using the neighbors' Route 734 Caches as an extension of the initiator's own Route Cache). If no 735 Route Reply is received after a short timeout, then the node sends a 736 "propagating" Route Request (i.e., with no hop limit) for the target 737 node. 739 As another example, a node MAY use this hop limit to implement an 740 "expanding ring" search for the target [14]. A node using this 741 technique sends an initial non-propagating Route Request as described 742 above; if no Route Reply is received for it, the node originates 743 another Route Request with a hop limit of 2. For each Route Request 744 originated, if no Route Reply is received for it, the node doubles 745 the hop limit used on the previous attempt, to progressively explore 746 for the target node without allowing the Route Request to propagate 747 over the entire network. However, this expanding ring search 748 approach could have the effect of increasing the average latency of 749 Route Discovery, since multiple Discovery attempts and timeouts may 750 be needed before discovering a route to the target node. 752 3.4. Additional Route Maintenance Features 754 3.4.1. Packet Salvaging 756 When an intermediate node forwarding a packet detects through Route 757 Maintenance that the next hop along the route for that packet is 758 broken, if the node has another route to the packet's destination in 759 its Route Cache, the node SHOULD "salvage" the packet rather than 760 discarding it. To salvage a packet, the node replaces the original 761 source route on the packet with the route from its Route Cache. The 762 node then forwards the packet to the next node indicated along this 763 source route. For example, in the situation shown in the example of 764 Section 3.2, if node C has another route cached to node E, it can 765 salvage the packet by replacing the original route in the packet with 766 this new route from its own Route Cache, rather than discarding the 767 packet. 769 When salvaging a packet, a count is maintained in the packet of the 770 number of times that it has been salvaged, to prevent a single packet 771 from being salvaged endlessly. Otherwise, it could be possible for 772 the packet to enter a routing loop, as different nodes repeatedly 773 salvage the packet and replace the source route on the packet with 774 routes to each other. 776 As described in Section 3.2, an intermediate node, such as in this 777 case, that detects through Route Maintenance that the next hop along 778 the route for a packet that it is forwarding is broken, the node also 779 SHOULD return a Route Error to the original sender of the packet, 780 identifying the link over which the packet could not be forwarded. 781 If the node sends this Route Error, it SHOULD originate the Route 782 Error before salvaging the packet. 784 3.4.2. Queued Packets Destined over a Broken Link 786 When an intermediate node forwarding a packet detects through Route 787 Maintenance that the next-hop link along the route for that packet 788 is broken, in addition to handling that packet as defined for Route 789 Maintenance, the node SHOULD also handle in a similar way any pending 790 packets that it has queued that are destined over this new broken 791 link. Specifically, the node SHOULD search its Network Interface 792 Queue and Retransmission Buffer (Section 4.5) for packets for which 793 the next-hop link is this new broken link. For each such packet 794 currently queued at this node, the node SHOULD process that packet as 795 follows: 797 - Remove the packet from the node's Network Interface Queue and 798 Retransmission Buffer and stop any retransmission activity for 799 the packet. 801 - Originate a Route Error for this packet to the original sender of 802 the packet, using the procedure described in Section 6.3.4, as if 803 the node had already reached the maximum number of retransmission 804 attempts for that packet for Route Maintenance. However, in 805 sending such Route Errors for queued packets in response to a 806 single new broken link detected, the node SHOULD send no more 807 than one Route Error to each original sender of any of these 808 packets. 810 - If the node has another route to the packet's IP 811 Destination Address in its Route Cache, the node SHOULD 812 salvage the packet as described in Section 6.3.6. Otherwise, the 813 node SHOULD discard the packet. 815 3.4.3. Automatic Route Shortening 817 Source routes in use MAY be automatically shortened if one or more 818 intermediate nodes in the route become no longer necessary. This 819 mechanism of automatically shortening routes in use is somewhat 820 similar to the use of passive acknowledgements [16]. In particular, 821 if a node is able to overhear a packet carrying a source route (e.g., 822 by operating its network interface in promiscuous receive mode), then 823 this node examines the unexpended portion of that source route. If 824 this node is not the intended next-hop destination for the packet 825 but is named in the later unexpended portion of the packet's source 826 route, then it can infer that the intermediate nodes before itself in 827 the source route are no longer needed in the route. For example, the 828 figure below illustrates an example in which node D has overheard a 829 data packet being transmitted from B to C, for later forwarding to D 830 and to E: 832 +-----+ +-----+ +-----+ +-----+ +-----+ 833 | A |---->| B |---->| C | | D | | E | 834 +-----+ +-----+ +-----+ +-----+ +-----+ 835 \ ^ 836 \ / 837 --------------------- 839 In this case, this node (node D) SHOULD return a "gratuitous" Route 840 Reply to the original sender of the packet (node A). The Route 841 Reply gives the shorter route as the concatenation of the portion of 842 the original source route up through the node that transmitted the 843 overheard packet (node B), plus the suffix of the original source 844 route beginning with the node returning the gratuitous Route Reply 845 (node D). In this example, the route returned in the gratuitous Route 846 Reply message sent from D to A gives the new route as the sequence of 847 hops from A to B to D to E. 849 When deciding whether to return a gratuitous Route Reply in this way, 850 a node MAY factor in additional information beyond the fact that it 851 was able to overhear the packet. For example, the node MAY decide to 852 return the gratuitous Route Reply only when the overheard packet is 853 received with a signal strenth or signal-to-noise ratio above some 854 specific threshold. In addition, each node maintains a Gratuitous 855 Route Reply Table, as described in Section 4.4, to limit the rate at 856 which it originates gratuitous Route Replies for the same returned 857 route. 859 3.4.4. Increased Spreading of Route Error Messages 861 When a source node receives a Route Error for a data packet that 862 it originated, this source node propagates this Route Error to its 863 neighbors by piggybacking it on its next Route Request. In this way, 864 stale information in the caches of nodes around this source node will 865 not generate Route Replies that contain the same invalid link for 866 which this source node received the Route Error. 868 For example, in the situation shown in the example of Section 3.2, 869 node A learns from the Route Error message from C, that the link 870 from C to D is currently broken. It thus removes this link from 871 its own Route Cache and initiates a new Route Discovery (if it has 872 no other route to E in its Route Cache). On the Route Request 873 packet initiating this Route Discovery, node A piggybacks a copy 874 of this Route Error, ensuring that the Route Error spreads well to 875 other nodes, and guaranteeing that any Route Reply that it receives 876 (including those from other node's Route Caches) in response to this 877 Route Request does not contain a route that assumes the existence of 878 this broken link. 880 4. Conceptual Data Structures 882 This document describes the operation of the DSR protocol in terms 883 of a number of conceptual data structures. This section describes 884 each of these data structures and provides an overview of its use 885 in the protocol. In an implementation of the protocol, these data 886 structures MAY be implemented in any manner consistent with the 887 external behavior described in this document. 889 4.1. Route Cache 891 All ad hoc network routing information needed by a node implementing 892 DSR is stored in that node's Route Cache. Each node in the network 893 maintains its own Route Cache. A node adds information to its 894 Route Cache as it learns of new links between nodes in the ad hoc 895 network; for example, a node may learn of new links when it receives 896 a packet carrying a Route Request, Route Reply, or DSR source route. 897 Likewise, a node removes information from its Route Cache as it 898 learns that existing links in the ad hoc network have broken; for 899 example, a node may learn of a broken link when it receives a packet 900 carrying a Route Error or through the link-layer retransmission 901 mechanism reporting a failure in forwarding a packet to its next-hop 902 destination. 904 Anytime a node adds new information to its Route Cache, the node 905 SHOULD check each packet in its own Send Buffer (Section 4.2) to 906 determine whether a route to that packet's IP Destination Address 907 now exists in the node's Route Cache (including the information just 908 added to the Cache). If so, the packet SHOULD then be sent using 909 that route and removed from the Send Buffer. 911 It is possible to interface a DSR network with other networks, 912 external to this DSR network. Such external networks may, for 913 example, be the Internet, or may be other ad hoc networks routed 914 with a routing protocol other than DSR. Such external networks may 915 also be other DSR networks that are treated as external networks 916 in order to improve scalability. The complete handling of such 917 external networks is beyond the scope of this document. However, 918 this document specifies a minimal set of requirements and features 919 necessary to allow nodes only implementing this specification to 920 interoperate correctly with nodes implementing interfaces to such 921 external networks. This minimal set of requirements and features 922 involve the First Hop External (F) and Last Hop External (L) 923 bits in a DSR Source Route option (Section 5.7) and a Route Reply 924 option (Section 5.3) in a packet's DSR header (Section 5). These 925 requirements also include the addition of an External flag bit 926 tagging each link in the Route Cache, copied from the First Hop 927 External (F) and Last Hop External (L) bits in the DSR Source Route 928 option or Route Reply option from which this link was learned. 930 The Route Cache SHOULD support storing more than one route to each 931 destination. In searching the Route Cache for a route to some 932 destination node, the Route Cache is indexed by destination node 933 address. The following properties describe this searching function 934 on a Route Cache: 936 - Each implementation of DSR at any node MAY choose any appropriate 937 strategy and algorithm for searching its Route Cache and 938 selecting a "best" route to the destination from among those 939 found. For example, a node MAY choose to select the shortest 940 route to the destination (the shortest sequence of hops), or it 941 MAY use an alternate metric to select the route from the Cache. 943 - However, if there are multiple cached routes to a destination, 944 the selection of routes when searching the Route Cache MUST 945 prefer routes that do not have the External flag set on any link. 946 This preference will select routes that lead directly to the 947 target node over routes that attempt to reach the target via any 948 external networks connected to the DSR ad hoc network. 950 - In addition, any route selected when searching the Route Cache 951 MUST NOT have the External bit set for any links other than 952 possibly the first link, the last link, or both; the External bit 953 MUST NOT be set for any intermediate hops in the route selected. 955 An implementation of a Route Cache MAY provide a fixed capacity 956 for the cache, or the cache size MAY be variable. The following 957 properties describe the management of available space within a node's 958 Route Cache: 960 - Each implementation of DSR at each node MAY choose any 961 appropriate policy for managing the entries in its Route Cache, 962 such as when limited cache capacity requires a choice of which 963 entries to retain in the Cache. For example, a node MAY chose a 964 "least recently used" (LRU) cache replacement policy, in which 965 the entry last used longest ago is discarded from the cache if a 966 decision needs to be made to allow space in the cache for some 967 new entry being added. 969 - However, the Route Cache replacement policy SHOULD allow routes 970 to be categorized based upon "preference", where routes with a 971 higher preferences are less likely to be removed from the cache. 972 For example, a node could prefer routes for which it initiated 973 a Route Discovery over routes that it learned as the result of 974 promiscuous snooping on other packets. In particular, a node 975 SHOULD prefer routes that it is presently using over those that 976 it is not. 978 Any suitable data structure organization, consistent with this 979 specification, MAY be used to implement the Route Cache in any node. 980 For example, the following two types of organization are possible: 982 - In DSR, the route returned in each Route Reply that is received 983 by the initiator of a Route Discovery (or that is learned from 984 the header of overhead packets, as described in Section 6.1.4) 985 represents a complete path (a sequence of links) leading to the 986 destination node. By caching each of these paths separately, 987 a "path cache" organization for the Route Cache can be formed. 988 A path cache is very simple to implement and easily guarantees 989 that all routes are loop-free, since each individual route from 990 a Route Reply or Route Request or used in a packet is loop-free. 991 To search for a route in a path cache data structure, the sending 992 node can simply search its Route Cache for any path (or prefix of 993 a path) that leads to the intended destination node. 995 This type of organization for the Route Cache in DSR has been 996 extensively studied through simulation [5, 9, 12, 19] and 997 through implementation of DSR in a mobile outdoor testbed under 998 significant workload [20, 21, 22]. 1000 - Alternatively, a "link cache" organization could be used for the 1001 Route Cache, in which each individual link (hop) in the routes 1002 returned in Route Reply packets (or otherwise learned from the 1003 header of overhead packets) is added to a unified graph data 1004 structure of this node's current view of the network topology. 1005 To search for a route in link cache, the sending node must use 1006 a more complex graph search algorithm, such as the well-known 1007 Dijkstra's shortest-path algorithm, to find the current best path 1008 through the graph to the destination node. Such an algorithm is 1009 more difficult to implement and may require significantly more 1010 CPU time to execute. 1012 However, a link cache organization is more powerful than a path 1013 cache organization, in its ability to effectively utilize all of 1014 the potential information that a node might learn about the state 1015 of the network. In particular, links learned from different 1016 Route Discoveries or from the header of any overheard packets can 1017 be merged together to form new routes in the network, but this 1018 is not possible in a path cache due to the separation of each 1019 individual path in the cache. 1021 This type of organization for the Route Cache in DSR, including 1022 the effect of a range of implementation choices, has been studied 1023 through detailed simulation [9]. 1025 The choice of data structure organization to use for the Route Cache 1026 in any DSR implementation is a local matter for each node and affects 1027 only performance; any reasonable choice of organization for the Route 1028 Cache does not affect either correctness or interoperability. 1030 Each entry in the Route Cache SHOULD have a timeout associated 1031 with it, to allow that entry to be deleted if not used within some 1032 time. The particular choice of algorithm and data structure used 1033 to implement the Route Cache SHOULD be considered in choosing the 1034 timeout for entries in the Route Cache. The configuration variable 1035 RouteCacheTimeout defined in Section 7 specifies the timeout to be 1036 applied to entries in the Route Cache, although it is also possible 1037 to instead use an adaptive policy in choosing timeout values rather 1038 than using a single timeout setting for all entries; for example, the 1039 Link-MaxLife cache design (below) uses an adaptive timeout algorithm 1040 and does not use the RouteCacheTimeout configuration variable. 1042 As guidance to implementors, Appendix A describes a type of link 1043 cache known as "Link-MaxLife" that has been shown to outperform 1044 other types of link caches and path caches studied in detailed 1045 simulation [9]. Link-MaxLife is an adaptive link cache in which each 1046 link in the cache has a timeout that is determined dynamically by the 1047 caching node according to its observed past behavior of the two nodes 1048 at the ends of the link; in addition, when selecting a route for a 1049 packet being sent to some destination, among cached routes of equal 1050 length (number of hops) to that destination, Link-MaxLife selects the 1051 route with the longest expected lifetime (highest minimum timeout of 1052 any link in the route). Use of the Link-MaxLife design for the Route 1053 Cache is recommended in implementations of DSR. 1055 4.2. Send Buffer 1057 The Send Buffer of a node implementing DSR is a queue of packets that 1058 cannot be sent by that node because it does not yet have a source 1059 route to each such packet's destination. Each packet in the Send 1060 Buffer is logically associated with the time that it was placed into 1061 the Buffer, and SHOULD be removed from the Send Buffer and silently 1062 discarded after a period of SendBufferTimeout after initially being 1063 placed in the Buffer. If necessary, a FIFO strategy SHOULD be used 1064 to evict packets before they timeout to prevent the buffer from 1065 overflowing. 1067 Subject to the rate limiting defined in Section 6.2, a Route 1068 Discovery SHOULD be initiated as often as possible for the 1069 destination address of any packets residing in the Send Buffer. 1071 4.3. Route Request Table 1073 The Route Request Table of a node implementing DSR records 1074 information about Route Requests that have been recently originated 1075 or forwarded by this node. The table is indexed by IP address. 1077 The Route Request Table on a node records the following information 1078 about nodes to which this node has initiated a Route Request: 1080 - The Time-to-Live (TTL) field used in the IP header of the Route 1081 Request for the last Route Discovery initiated by this node for 1082 that target node. This value allows the node to implement a 1083 variety of algorithms for controlling the spread of its Route 1084 Request on each Route Discovery initiated for a target. As 1085 examples, two possible algorithms for this use of the TTL field 1086 are described in Section 3.3.4. 1088 - The time that this node last originated a Route Request for that 1089 target node. 1091 - The number of consecutive Route Discoveries initiated for this 1092 target since receiving a valid Route Reply giving a route to that 1093 target node. 1095 - The remaining amount of time before which this node MAY next 1096 attempt at a Route Discovery for that target node. When the 1097 node initiates a new Route Discovery for this target node, this 1098 field in the Route Request Table entry for that target node is 1099 initialized to the timeout for that Route Discovery, after which 1100 the node MAY initiate a new Discovery for that target. Until 1101 a valid Route Reply is received for this target node address, 1102 a node MUST implement a back-off algorithm in determining this 1103 timeout value for each successive Route Discovery initiated 1104 for this target using the same Time-to-Live (TTL) value in the 1105 IP header of the Route Request packet. The timeout between 1106 such consecutive Route Discovery initiations SHOULD increase by 1107 doubling the timeout value on each new initiation. 1109 In addition, the Route Request Table on a node also records the 1110 following information about initiator nodes from which this node has 1111 received a Route Request: 1113 - A FIFO cache of size RequestTableIds entries containing the 1114 Identification value and target address from the most recent 1115 Route Requests received by this node from that initiator node. 1117 Nodes SHOULD use an LRU policy to manage the entries in their Route 1118 Request Table. 1120 The number of Identification values to retain in each Route 1121 Request Table entry, RequestTableIds, MUST NOT be unlimited, since, 1122 in the worst case, when a node crashes and reboots, the first 1123 RequestTableIds Route Discoveries it initiates after rebooting 1124 could appear to be duplicates to the other nodes in the network. 1125 In addition, a node SHOULD base its initial Identification value, 1126 used for Route Discoveries after rebooting, on a battery backed-up 1127 clock or other persistent memory device, in order to help avoid 1128 any possible such delay in successfully discovering new routes 1129 after rebooting; if no such source of initial Identification 1130 value is available, a node after rebooting SHOULD base its initial 1131 Identification value on a random number. 1133 4.4. Gratuitous Route Reply Table 1135 The Gratuitous Route Reply Table of a node implementing DSR records 1136 information about "gratuitous" Route Replies sent by this node as 1137 part of automatic route shortening. As described in Section 3.4.3, 1138 a node returns a gratuitous Route Reply when it overhears a packet 1139 transmitted by some node, for which the node overhearing the 1140 packet was not the intended next-hop node but was named later in 1141 the unexpended hops of the source route in that packet; the node 1142 overhearing the packet returns a gratuitous Route Reply to the 1143 original sender of the packet, listing the shorter route (not 1144 including the hops of the source route "skipped over" by this 1145 packet). A node uses its Gratuitous Route Reply Table to limit the 1146 rate at which it originates gratuitous Route Replies to the same 1147 original sender for the same node from which it overheard a packet to 1148 trigger the gratuitous Route Reply. 1150 Each entry in the Gratuitous Route Reply Table of a node contains the 1151 following fields: 1153 - The address of the node to which this node originated a 1154 gratuitous Route Reply. 1156 - The address of the node from which this node overheard the packet 1157 triggering that gratuitous Route Reply. 1159 - The remaining time before which this entry in the Gratuitous 1160 Route Reply Table expires and SHOULD be deleted by the node. 1161 When a node creates a new entry in its Gratuitous Route Reply 1162 Table, the timeout value for that entry should be initialized to 1163 the value GratReplyHoldoff. 1165 When a node overhears a packet that would trigger a gratuitous 1166 Route Reply, if a corresponding entry already exists in the node's 1167 Gratuitous Route Reply Table, then the node SHOULD NOT send a 1168 gratuitous Route Reply for that packet. Otherwise (no corresponding 1169 entry already exists), the node SHOULD create a new entry in its 1170 Gratuitous Route Reply Table to record that gratuitous Route Reply, 1171 with a timeout value of GratReplyHoldoff. 1173 4.5. Network Interface Queue and Retransmission Buffer 1175 Depending on factors such as the structure and organization of 1176 the operating system, protocol stack implementation, network 1177 interface device driver, and network interface hardware, a 1178 packet being transmitted could be queued in a variety of ways. 1179 For example, outgoing packets from the network protocol stack 1180 might be queued at the operating system or link layer, before 1181 transmission by the network interface. The network interface 1182 might also provide a retransmission mechanism for packets, such 1183 as occurs in IEEE 802.11 [11]; the DSR protocol also requires 1184 limited retransmission of packets as part of Route Maintenance. The 1185 operation of DSR is defined here in terms of two conceptual data 1186 structures that together incorporate this queueing and retransmission 1187 behavior. 1189 The Network Interface Queue of a node implementing DSR is an output 1190 queue of packets from the network protocol stack waiting to be 1191 transmitted by the network interface; for example, in the 4.4BSD 1192 Unix network protocol stack implementation, this queue for a network 1193 interface is represented as a "struct ifqueue" [33]. This queue is 1194 used to hold packets while the network interface is in the process of 1195 transmitting another packet. 1197 The Retransmission Buffer of a node implementing DSR is a queue of 1198 packets sent by this node that are awaiting retransmission as part 1199 of Route Maintenance. For each packet in the Retransmission Buffer, 1200 a node maintains a count of the number of retransmissions and the 1201 time of the last retransmission. The Retransmission Buffer MAY be 1202 of limited size; when adding a new packet to the Retransmission 1203 Buffer, if the buffer size is insufficient to hold the new packet, 1204 the new packet SHOULD be silently discarded. The maximum number of 1205 retransmission attempts for a packet for Route Maintenance (after the 1206 initial transmission of the packet) is MaxMaintRexmt. After this 1207 time, if Route Maintenance for a packet has not been satisfied, the 1208 packet SHOULD be removed from the Retransmission Buffer, stopping 1209 retransmissions for that packet; in this case, the node also SHOULD 1210 originate a Route Error for this packet to the original source of the 1211 packet (Section 6.3) and SHOULD salvage the packet (Section 6.3.6) if 1212 it has another route to the packet's IP Destination Address in its 1213 Route Cache. The definition of MaxMaintRexmt conceptually includes 1214 any retransmissions that might be attempted for a packet at the link 1215 layer or within the network interface hardware. The retransmission 1216 timeout value to use for each transmission attempt for a packet 1217 depends on the type of acknowledgement mechanism used for Route 1218 Maintenance for that attempt, as described in Section 6.3. 1220 5. DSR Header Format 1222 The Dynamic Source Routing protocol makes use of a special header 1223 carrying control information that can be included in any existing IP 1224 packet. This DSR header in a packet contains a small fixed-sized, 1225 4-octet portion, followed by a sequence of zero or more DSR options 1226 carrying optional information. The end of the sequence of DSR 1227 options in the DSR header is implied by total length of the DSR 1228 header. 1230 For IPv4, the DSR header MUST immediately follow the IP header in the 1231 packet. (If a Hop-by-Hop Options extension header, as defined in 1232 IPv6 [6], becomes defined for IPv4, the DSR header MUST immediately 1233 follow the Hop-by-Hop Options extension header, if one is present in 1234 the packet, and MUST otherwise immediately follow the IP header.) 1236 To add a DSR header to a packet, the DSR header is inserted following 1237 the packet's IP header, before any following header such as a 1238 traditional (e.g., TCP or UDP) transport layer header. Specifically, 1239 the Protocol field in the IP header is used to indicate that a DSR 1240 header follows the IP header, and the Next Header field in the DSR 1241 header is used to indicate the type of protocol header (such as a 1242 transport layer header) following the DSR header. 1244 If any headers follow the DSR header in a packet, the total length 1245 of the DSR header (and thus the total, combined length of all DSR 1246 options present) MUST be a multiple of 4 octets. This requirement 1247 preserves the alignment of these following headers in the packet. 1249 5.1. Fixed Portion of DSR Header 1251 The fixed portion of the DSR header is used to carry information that 1252 must be present in any DSR header. This fixed portion of the DSR 1253 header has the following format: 1255 0 1 2 3 1256 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 1257 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1258 | Next Header | Reserved | Payload Length | 1259 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1260 . . 1261 . Options . 1262 . . 1263 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1265 Next Header 1267 8-bit selector. Identifies the type of header immediately 1268 following the DSR header. Uses the same values as the IPv4 1269 Protocol field [29]. 1271 Reserved 1273 MUST be sent as 0 and ignored on reception. 1275 Payload Length 1277 The length of the DSR header, excluding the 4-octet fixed 1278 portion. The value of the Payload Length field defines the 1279 total length of all options carried in the DSR header. 1281 Options 1283 Variable-length field; the length of the Options field is 1284 specified by the Payload Length field in this DSR header. 1285 Contains one or more pieces of optional information (DSR 1286 options), encoded in type-length-value (TLV) format (with the 1287 exception of the Pad1 option, described in Section 5.8). 1289 The placement of DSR options following the fixed portion of the DSR 1290 header MAY be padded for alignment. However, due to the typically 1291 limited available wireless bandwidth in ad hoc networks, this padding 1292 is not required, and receiving nodes MUST NOT expect options within a 1293 DSR header to be aligned. 1295 A node inserting a DSR header into a packet MUST set the Don't 1296 Fragment (DF) bit in the packet's IP header. 1298 The following types of DSR options are defined in this document for 1299 use within a DSR header: 1301 - Route Request option (Section 5.2) 1303 - Route Reply option (Section 5.3) 1305 - Route Error option (Section 5.4) 1307 - Acknowledgement Request option (Section 5.5) 1309 - Acknowledgement option (Section 5.6) 1311 - DSR Source Route option (Section 5.7) 1313 - Pad1 option (Section 5.8) 1315 - PadN option (Section 5.9) 1317 5.2. Route Request Option 1319 The Route Request option in a DSR header is encoded as follows: 1321 0 1 2 3 1322 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 1323 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1324 | Option Type | Opt Data Len | Identification | 1325 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1326 | Target Address | 1327 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1328 | Address[1] | 1329 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1330 | Address[2] | 1331 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1332 | ... | 1333 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1334 | Address[n] | 1335 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1337 IP fields: 1339 Source Address 1341 MUST be set to the address of the node originating this packet. 1342 Intermediate nodes that retransmit the packet to propagate the 1343 Route Request MUST NOT change this field. 1345 Destination Address 1347 MUST be set to the IP limited broadcast address 1348 (255.255.255.255). 1350 Hop Limit (TTL) 1352 MAY be varied from 1 to 255, for example to implement 1353 non-propagating Route Requests and Route Request expanding-ring 1354 searches (Section 3.3.4). 1356 Route Request fields: 1358 Option Type 1360 2 1362 Opt Data Len 1364 8-bit unsigned integer. Length of the option, in octets, 1365 excluding the Option Type and Opt Data Len fields. 1367 Identification 1369 A unique value generated by the initiator (original sender) of 1370 the Route Request. Nodes initiating a Route Request generate 1371 a new Identification value for each Route Request, for example 1372 based on a sequence number counter of all Route Requests 1373 initiated by the node. 1375 This value allows a receiving node to determine whether it 1376 has recently seen a copy of this Route Request: if this 1377 Identification value is found by this receiving node in its 1378 Route Request Table (in the cache of Identification values 1379 in the entry there for this initiating node), this receiving 1380 node MUST discard the Route Request. When propagating a Route 1381 Request, this field MUST be copied from the received copy of 1382 the Route Request being propagated. 1384 Target Address 1386 The address of the node that is the target of the Route 1387 Request. 1389 Address[1..n] 1391 Address[i] is the address of the i-th node recorded in the 1392 Route Request option. The address given in the Source Address 1393 field in the IP header is the address of the initiator of 1394 the Route Discovery and MUST NOT be listed in the Address[i] 1395 fields; the address given in Address[1] is thus the address 1396 of the first node on the path after the initiator. The 1397 number of addresses present in this field is indicated by the 1398 Opt Data Len field in the option (n = (Opt Data Len - 6) / 4). 1399 Each node propagating the Route Request adds its own address to 1400 this list, increasing the Opt Data Len value by 4 octets. 1402 The Route Request option MUST NOT appear more than once within a DSR 1403 header. 1405 5.3. Route Reply Option 1407 The Route Reply option in a DSR header is encoded as follows: 1409 0 1 2 3 1410 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 1411 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1412 | Option Type | Opt Data Len |L| Reserved | 1413 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1414 | Address[1] | 1415 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1416 | Address[2] | 1417 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1418 | ... | 1419 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1420 | Address[n] | 1421 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1423 IP fields: 1425 Source Address 1427 Set to the address of the node sending the Route Reply. 1428 In the case of a node sending a reply from its Route 1429 Cache (Section 3.3.2) or sending a gratuitous Route Reply 1430 (Section 3.4.3), this address can differ from the address that 1431 was the target of the Route Discovery. 1433 Destination Address 1435 MUST be set to the address of the source node of the route 1436 being returned. Copied from the Source Address field of the 1437 Route Request generating the Route Reply, or in the case of a 1438 gratuitous Route Reply, copied from the Source Address field of 1439 the data packet triggering the gratuitous Reply. 1441 Route Reply fields: 1443 Option Type 1445 3 1447 Opt Data Len 1449 8-bit unsigned integer. Length of the option, in octets, 1450 excluding the Option Type and Opt Data Len fields. 1452 Last Hop External (L) 1454 Set to indicate that the last hop given by the Route Reply 1455 (the link from Address[n-1] to Address[n]) is actually an 1456 arbitrary path in a network external to the DSR network; the 1457 exact route outside the DSR network is not represented in the 1458 Route Reply. Nodes caching this hop in their Route Cache MUST 1459 flag the cached hop with the External flag. Such hops MUST NOT 1460 be returned in a cached Route Reply generated from this Route 1461 Cache entry, and selection of routes from the Route Cache to 1462 route a packet being sent MUST prefer routes that contain no 1463 hops flagged as External. 1465 Reserved 1467 MUST be sent as 0 and ignored on reception. 1469 Address[1..n] 1471 The source route being returned by the Route Reply. The route 1472 indicates a sequence of hops, originating at the source node 1473 specified in the Destination Address field of the IP header 1474 of the packet carrying the Route Reply, through each of the 1475 Address[i] nodes in the order listed in the Route Reply, 1476 ending with the destination node indicated by Address[n]. 1477 The number of addresses present in the Address[1..n] 1478 field is indicated by the Opt Data Len field in the option 1479 (n = (Opt Data Len - 1) / 4). 1481 A Route Reply option MAY appear one or more times within a DSR 1482 header. 1484 5.4. Route Error Option 1486 The Route Error option in a DSR header is encoded as follows: 1488 0 1 2 3 1489 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 1490 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1491 | Option Type | Opt Data Len | Error Type |Reservd|Salvage| 1492 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1493 | Error Source Address | 1494 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1495 | Error Destination Address | 1496 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1497 . . 1498 . Type-Specific Information . 1499 . . 1500 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1502 Option Type 1504 4 1506 Opt Data Len 1508 8-bit unsigned integer. Length of the option, in octets, 1509 excluding the Option Type and Opt Data Len fields. 1511 For the current definition of the Route Error option, 1512 this field MUST be set to 10, plus the size of any 1513 Type-Specific Information present in the Route Error. Further 1514 extensions to the Route Error option format may also be 1515 included after the Type-Specific Information portion of the 1516 Route Error option specified above. The presence of such 1517 extensions will be indicated by the Opt Data Len field. 1518 When the Opt Data Len is greater than that required for 1519 the fixed portion of the Route Error plus the necessary 1520 Type-Specific Information as indicated by the Option Type 1521 value in the option, the remaining octets are interpreted as 1522 extensions. Currently, no such further extensions have been 1523 defined. 1525 Error Type 1527 The type of error encountered. Currently, the following type 1528 value is defined: 1530 1 = NODE_UNREACHABLE 1532 Other values of the Error Type field are reserved for future 1533 use. 1535 Reservd 1537 Reserved. MUST be sent as 0 and ignored on reception. 1539 Salvage 1541 A 4-bit unsigned integer. Copied from the Salvage field in 1542 the DSR Source Route option of the packet triggering the Route 1543 Error. 1545 The "total salvage count" of the Route Error option is derived 1546 from the value in the Salvage field of this Route Error option 1547 and all preceding Route Error options in the packet as follows: 1548 the total salvage count is the sum of, for each such Route 1549 Error option, one plus the value in the Salvage field of that 1550 Route Error option. 1552 Error Source Address 1554 The address of the node originating the Route Error (e.g., the 1555 node that attempted to forward a packet and discovered the link 1556 failure). 1558 Error Destination Address 1560 The address of the node to which the Route Error must be 1561 delivered For example, when the Error Type field is set to 1562 NODE_UNREACHABLE, this field will be set to the address of the 1563 node that generated the routing information claiming that the 1564 hop from the Error Source Address to Unreachable Node Address 1565 (specified in the Type-Specific Information) was a valid hop. 1567 Type-Specific Information 1569 Information specific to the Error Type of this Route Error 1570 message. 1572 Currently, the Type-Specific Information field is defined only for 1573 Route Error messages of type NODE_UNREACHABLE. In this case, the 1574 Type-Specific Information field is defined as follows: 1576 0 1 2 3 1577 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 1578 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1579 | Unreachable Node Address | 1580 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1581 Unreachable Node Address 1583 The address of the node that was found to be unreachable 1584 (the next-hop neighbor to which the node with address 1585 Error Source Address was attempting to transmit the packet). 1587 A Route Error option MAY appear one or more times within a DSR 1588 header. 1590 5.5. Acknowledgment Request Option 1592 The Acknowledgment Request option in a DSR header is encoded as 1593 follows: 1595 0 1 2 3 1596 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 1597 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1598 | Option Type | Opt Data Len | Identification | 1599 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1601 Option Type 1603 5 1605 Opt Data Len 1607 8-bit unsigned integer. Length of the option, in octets, 1608 excluding the Option Type and Opt Data Len fields. 1610 Identification 1612 The Identification field is set to a unique value and is copied 1613 into the Identification field of the Acknowledgement option 1614 when returned by the node receiving the packet over this hop. 1616 An Acknowledgement Request option MUST NOT appear more than once 1617 within a DSR header. 1619 5.6. Acknowledgment Option 1621 The Acknowledgment option in a DSR header is encoded as follows: 1623 0 1 2 3 1624 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 1625 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1626 | Option Type | Opt Data Len | Identification | 1627 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1628 | ACK Source Address | 1629 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1630 | ACK Destination Address | 1631 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1633 Option Type 1635 6 1637 Opt Data Len 1639 8-bit unsigned integer. Length of the option, in octets, 1640 excluding the Option Type and Opt Data Len fields. 1642 Identification 1644 Copied from the Identification field of the Acknowledgement 1645 Request option of the packet being acknowledged. 1647 ACK Source Address 1649 The address of the node originating the acknowledgment. 1651 ACK Destination Address 1653 The address of the node to which the acknowledgment is to be 1654 delivered. 1656 An Acknowledgement option MAY appear one or more times within a DSR 1657 header. 1659 5.7. DSR Source Route Option 1661 The DSR Source Route option in a DSR header is encoded as follows: 1663 0 1 2 3 1664 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 1665 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1666 | Option Type | Opt Data Len |F|L|Reservd|Salvage| Segs Left | 1667 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1668 | Address[1] | 1669 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1670 | Address[2] | 1671 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1672 | ... | 1673 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1674 | Address[n] | 1675 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1677 Option Type 1679 7 1681 Opt Data Len 1683 8-bit unsigned integer. Length of the option, in octets, 1684 excluding the Option Type and Opt Data Len fields. For the 1685 format of the DSR Source Route option defined here, this field 1686 MUST be set to the value (n * 4) + 2, where n is the number of 1687 addresses present in the Address[i] fields. 1689 First Hop External (F) 1691 Set to indicate that the first hop indicated by the DSR 1692 Source Route option is actually an arbitrary path in a network 1693 external to the DSR network; the exact route outside the DSR 1694 network is not represented in the DSR Source Route option. 1695 Nodes caching this hop in their Route Cache MUST flag the 1696 cached hop with the External flag. Such hops MUST NOT be 1697 returned in a Route Reply generated from this Route Cache 1698 entry, and selection of routes from the Route Cache to route 1699 a packet being sent MUST prefer routes that contain no hops 1700 flagged as External. 1702 Last Hop External (L) 1704 Set to indicate that the last hop indicated by the DSR Source 1705 Route option is actually an arbitrary path in a network 1706 external to the DSR network; the exact route outside the DSR 1707 network is not represented in the DSR Source Route option. 1708 Nodes caching this hop in their Route Cache MUST flag the 1709 cached hop with the External flag. Such hops MUST NOT be 1710 returned in a Route Reply generated from this Route Cache 1711 entry, and selection of routes from the Route Cache to route 1712 a packet being sent MUST prefer routes that contain no hops 1713 flagged as External. 1715 Reserved 1717 MUST be sent as 0 and ignored on reception. 1719 Salvage 1721 A 4-bit unsigned integer. Count of number of times that 1722 this packet has been salvaged as a part of DSR routing 1723 (Section 3.4.1). 1725 Segments Left (Segs Left) 1727 Number of route segments remaining, i.e., number of explicitly 1728 listed intermediate nodes still to be visited before reaching 1729 the final destination. 1731 Address[1..n] 1733 The sequence of addresses of the source route. In routing 1734 and forwarding the packet, the source route is processed as 1735 described in Sections 6.1.3 and 6.1.5. The number of addresses 1736 present in the Address[1..n] field is indicated by the 1737 Opt Data Len field in the option (n = (Opt Data Len - 2) / 4). 1739 When forwarding a packet along a DSR source route using a DSR Source 1740 Route option in the packet's DSR header, the Destination Address 1741 field in the packet's IP header is always set to the address of the 1742 packet's ultimate destination. A node receiving a packet containing 1743 a DSR header with a DSR Source Route option MUST examine the 1744 indicated source route to determine if it is the intended next-hop 1745 node for the packet and determine how to forward the packet, as 1746 defined in Sections 6.1.4 and 6.1.5. 1748 5.8. Pad1 Option 1750 The Pad1 option in a DSR header is encoded as follows: 1752 +-+-+-+-+-+-+-+-+ 1753 | Option Type | 1754 +-+-+-+-+-+-+-+-+ 1756 Option Type 1758 0 1760 A Pad1 option MAY be included in the Options field of a DSR header 1761 in order to align subsequent DSR options, but such alignment is 1762 not required and MUST NOT be expected by a node receiving a packet 1763 containing a DSR header. 1765 If any headers follow the DSR header in a packet, the total length of 1766 a DSR header, indicated by the Payload Length field in the DSR header 1767 MUST be a multiple of 4 octets. In this case, when building a DSR 1768 header in a packet, sufficient Pad1 or PadN options MUST be included 1769 in the Options field of the DSR header to make the total length a 1770 multiple of 4 octets. 1772 If more than one consecutive octet of padding is being inserted in 1773 the Options field of a DSR header, the PadN option, described next, 1774 SHOULD be used, rather than multiple Pad1 options. 1776 Note that the format of the Pad1 option is a special case; it does 1777 not have an Opt Data Len or Option Data field. 1779 5.9. PadN Option 1781 The PadN option in a DSR header is encoded as follows: 1783 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - 1784 | Option Type | Opt Data Len | Option Data 1785 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - 1787 Option Type 1789 1 1791 Opt Data Len 1793 8-bit unsigned integer. Length of the option, in octets, 1794 excluding the Option Type and Opt Data Len fields. 1796 Option Data 1798 A number of zero-valued octets equal to the Opt Data Len. 1800 A PadN option MAY be included in the Options field of a DSR header 1801 in order to align subsequent DSR options, but such alignment is 1802 not required and MUST NOT be expected by a node receiving a packet 1803 containing a DSR header. 1805 If any headers follow the DSR header in a packet, the total length of 1806 a DSR header, indicated by the Payload Length field in the DSR header 1807 MUST be a multiple of 4 octets. In this case, when building a DSR 1808 header in a packet, sufficient Pad1 or PadN options MUST be included 1809 in the Options field of the DSR header to make the total length a 1810 multiple of 4 octets. 1812 6. Detailed Operation 1814 6.1. General Packet Processing 1816 6.1.1. Originating a Packet 1818 When originating any packet, a node using DSR routing MUST perform 1819 the following sequence of steps: 1821 - Search the node's Route Cache for a route to the address given in 1822 the IP Destination Address field in the packet's header. 1824 - If no such route is found in the Route Cache, then perform 1825 Route Discovery for the Destination Address, as described in 1826 Section 6.2. Initiating a Route Discovery for this target node 1827 address results in the node adding a Route Request option in 1828 a DSR header in this existing packet, or saving this existing 1829 packet to its Send Buffer and initiating the Route Discovery 1830 by sending a separate packet containing such a Route Request 1831 option. If the node chooses to initiate the Route Discovery 1832 by adding the Route Request option to this existing packet, 1833 it will replace the IP Destination Address field with the IP 1834 "limited broadcast" address (255.255.255.255) [3], copying the 1835 original IP Destination Address to the Target Address field of 1836 the new Route Request option added to the packet, as described in 1837 Section 6.2.1. 1839 - If the packet now does not contain a Route Request option, 1840 then this node must have a route to the Destination Address 1841 of the packet; if the node has more than one route to this 1842 Destination Address, the node selects one to use for this packet. 1843 If the length of this route is greater than 1 hop, or if the 1844 node determines to request a DSR network-layer acknowledgement 1845 from the first-hop node in that route, then insert a DSR header 1846 into the packet, as described in Section 6.1.2, and insert a DSR 1847 Source Route option, as described in Section 6.1.3. The source 1848 route in the packet is initialized from the selected route to the 1849 Destination Address of the packet. 1851 - Transmit the packet to the first-hop node address given in 1852 selected source route, using Route Maintenance to retransmit the 1853 packet if necessary, as described in Section 6.3. 1855 6.1.2. Adding a DSR Header to a Packet 1857 A node originating a packet adds a DSR header to the packet, if 1858 necessary, to carry information needed by the routing protocol. A 1859 packet MUST NOT contain more than one DSR header. A DSR header is 1860 added to a packet by performing the following sequence of steps 1861 (these steps assume that the packet contains no other headers that 1862 MUST be located in the packet before the DSR header): 1864 - Insert a DSR header after the IP header but before any other 1865 header that may be present. 1867 - Set the Next Header field of the DSR header to the Protocol 1868 number field of the packet's IP header. 1870 - Set the Protocol field of the packet's IP header to the Protocol 1871 number assigned for a DSR header (TBA???). 1873 6.1.3. Adding a DSR Source Route Option to a Packet 1875 A node originating a packet adds a DSR Source Route option to the 1876 packet, if necessary, in order to carry the source route from this 1877 originating node to the final destination address of the packet. 1878 Specifically, the node adding the DSR Source Route option constructs 1879 the DSR Source Route option and modifies the IP packet according to 1880 the following sequence of steps: 1882 - The node creates a DSR Source Route option, as described in 1883 Section 5.7, and appends it to the DSR header in the packet. 1884 (A DSR header is added, as described in Section 6.1.2, if not 1885 already present.) 1887 - The number of Address[i] fields to include in the DSR Source 1888 Route option (n) is the number of intermediate nodes in the 1889 source route for the packet (i.e., excluding address of the 1890 originating node and the final destination address of the 1891 packet). The Segments Left field in the DSR Source Route option 1892 is initialized equal to n. 1894 - The addresses within the source route for the packet are copied 1895 into sequential Address[i] fields in the DSR Source Route option, 1896 for i = 1, 2, ..., n. 1898 - The First Hop External (F) bit in the DSR Source Route option is 1899 copied from the External bit flagging the first hop in the source 1900 route for the packet, as indicated in the Route Cache. 1902 - The Last Hop External (L) bit in the DSR Source Route option is 1903 copied from the External bit flagging the last hop in the source 1904 route for the packet, as indicated in the Route Cache. 1906 - The Salvage field in the DSR Source Route option is 1907 initialized to 0. 1909 6.1.4. Processing a Received Packet 1911 When a node receives any packet (whether for forwarding, overheard, 1912 or as the final destination of the packet), if that packet contains a 1913 DSR header, then that node MUST process any options contained in that 1914 DSR header, in the order contained there. Specifically: 1916 - If the DSR header contains a Route Request option, the node 1917 SHOULD extract the source route from the Route Request and add 1918 this routing information to its Route Cache, subject to the 1919 conditions identified in Section 3.3.1. The routing information 1920 from the Route Request is the sequence of hop addresses 1922 initiator, Address[1], Address[2], ..., Address[n] 1924 where initiator is the value of the Source Address field in 1925 the IP header of the packet carrying the Route Request (the 1926 address of the initiator of the Route Discovery), and each 1927 Address[i] is a node through which this Route Request has passed, 1928 in turn, during this Route Discovery. The value n here is the 1929 number of addresses recorded in the Route Request option, or 1930 (Opt Data Len - 6) / 4. 1932 After possibly updating the node's Route Cache in response to 1933 the routing information in the Route Request option, the node 1934 MUST then process the Route Request option as described in 1935 Section 6.2.2. 1937 - If the DSR header contains a Route Reply option, the node SHOULD 1938 extract the source route from the Route Reply and add this 1939 routing information to its Route Cache, subject to the conditions 1940 identified in Section 3.3.1. The source route from the Route 1941 Reply is the sequence of hop addresses 1943 initiator, Address[1], Address[2], ..., Address[n] 1945 where initiator is the value of the Destination Address field in 1946 the IP header of the packet carrying the Route Reply (the address 1947 of the initiator of the Route Discovery), and each Address[i] 1948 is a node through which the source route passes, in turn, on 1949 the route to the target of the Route Discovery. Address[n] is 1950 the address of the target. If the Last Hop External (L) bit is 1951 set in the Route Reply, the node MUST flag the last hop from 1952 the Route Reply (the link from Address[n-1] to Address[n]) in 1953 its Route Cache as External. The value n here is the number of 1954 addresses in the source route being returned in the Route Reply 1955 option, or (Opt Data Len - 1) / 4. 1957 After possibly updating the node's Route Cache in response to 1958 the routing information in the Route Reply option, then if the 1959 packet's IP Destination Address matches one of this node's IP 1960 addresses, the node MUST then process the Route Reply option as 1961 described in Section 6.2.5. 1963 - If the DSR header contains a Route Error option, the node MUST 1964 process the Route Error option as described in Section 6.3.5. 1966 - If the DSR header contains an Acknowledgement Request option, the 1967 node MUST process the Acknowledgement Request option as described 1968 in Section 6.3.3. 1970 - If the DSR header contains an Acknowledgement option, then 1971 subject to the conditions identified in Section 3.3.1, the node 1972 SHOULD add to its Route Cache the single link from the node 1973 identified by the ACK Source Address field to the node identified 1974 by the ACK Destination Address field. 1976 After possibly updating the node's Route Cache in response to 1977 the routing information in the Acknowledgement option, the node 1978 MUST then process the Acknowledgement option as described in 1979 Section 6.3.3. 1981 - If the DSR header contains a DSR Source Route option, the node 1982 SHOULD extract the source route from the DSR Source Route and 1983 add this routing information to its Route Cache, subject to the 1984 conditions identified in Section 3.3.1. If the value of the 1985 Salvage field in the DSR Source Route option is zero, then the 1986 routing information from the DSR Source Route is the sequence of 1987 hop addresses 1989 source, Address[1], Address[2], ..., Address[n], destination 1991 and otherwise (Salvage is nonzero), the routing information from 1992 the DSR Source Route is the sequence of hop addresses 1994 Address[1], Address[2], ..., Address[n], destination 1996 where source is the value of the Source Address field in the IP 1997 header of the packet carrying the DSR Source Route option (the 1998 original sender of the packet), each Address[i] is the value in 1999 the Address[i] field in the DSR Source Route, and destination is 2000 the value of the Destination Address field in the packet's IP 2001 header (the last-hop address of the source route). The value n 2002 here is the number of addresses in source route in the DSR Source 2003 Route option, or (Opt Data Len - 2) / 4. 2005 After possibly updating the node's Route Cache in response to 2006 the routing information in the DSR Source Route option, the node 2007 MUST then process the DSR Source Route option as described in 2008 Section 6.1.5. 2010 - Any Pad1 or PadN options in the DSR header are ignored. 2012 Finally, if the Destination Address in the packet's IP header matches 2013 one of this receiving node's own IP address(es), remove the DSR 2014 header and all the included DSR options in the header, and pass the 2015 rest of the packet to the network layer. 2017 6.1.5. Processing a Received DSR Source Route Option 2019 When a node receives a packet containing a DSR Source Route option 2020 (whether for forwarding, overheard, or as the final destination of 2021 the packet), that node SHOULD examine the packet to determine if 2022 the receipt of that packet indicates an opportunity for automatic 2023 route shortening, as described in Section 3.4.3. Specifically, if 2024 this node is not the intended next-hop destination for the packet 2025 but is named in the later unexpended portion of the source route in 2026 the packet's DSR Source Route option, then this packet indicates an 2027 opportunity for automatic route shortening: the intermediate nodes 2028 after the node from which this node overheard the packet and before 2029 this node itself, are no longer necessary in the source route. In 2030 this case, this node SHOULD perform the following sequence of steps 2031 as part of automatic route shortening: 2033 - The node searches its Gratuitous Route Reply Table for an entry 2034 describing a gratuitous Route Reply earlier sent by this node, 2035 for which the original sender of the packet triggering the 2036 gratuitous Route Reply and the transmitting node from which this 2037 node overheard that packet in order to trigger the gratuitous 2038 Route Reply, both match the respective node addresses for this 2039 new received packet. If such an entry is found in the node's 2040 Gratuitous Route Reply Table, the node SHOULD NOT perform 2041 automatic route shortening in response to this receipt of this 2042 packet. 2044 - Otherwise, the node creates an entry for this overheard packet in 2045 its Gratuitous Route Reply Table. The timeout value for this new 2046 entry SHOULD be initialized to the value GratReplyHoldoff. After 2047 this timeout has expired, the node SHOULD delete this entry from 2048 its Gratuitous Route Reply Table. 2050 - After creating the new Gratuitous Route Reply Table entry 2051 above, the node originates a gratuitous Route Reply to the 2052 IP Source Address of this overheard packet, as described in 2053 Section 3.4.3. 2055 If the MAC protocol in use in the network is not capable of 2056 transmitting unicast packets over uni-directional links, as 2057 discussed in Section 3.3.1, then in originating this Route Reply, 2058 the node MUST use a source route for routing the Route Reply 2059 packet that is obtained by reversing the sequence of hops over 2060 which the packet triggering the gratuitous Route Reply was routed 2061 in reaching and being overheard by this node; this reversing of 2062 the route uses the gratuitous Route Reply to test this sequence 2063 of hops for bi-directionality, preventing the gratuitous Route 2064 Reply from being received by the initiator of the Route Discovery 2065 unless each of the hops over which the gratuitous Route Reply is 2066 returned is bi-directional. 2068 - Discard the overheard packet, since the packet has been received 2069 before its normal traversal of the packet's source route would 2070 have caused it to reach this receiving node. Another copy of 2071 the packet will normally arrive at this node as indicated in 2072 the packet's source route; discarding this initial copy of the 2073 packet, which triggered the gratuitous Route Reply, will prevent 2074 the duplication of this packet that would otherwise occur. 2076 If the packet is not discarded as part of automatic route shortening 2077 above, then the node MUST process the option according to the 2078 following sequence of steps: 2080 - If the value of the Segments Left field in the DSR Source Route 2081 option equals 0, then remove the DSR Source Route option from the 2082 DSR header. 2084 - Else, let n equal (Opt Data Len - 2) / 4. This is the number of 2085 addresses in the DSR Source Route option. 2087 - If the value of the Segments Left field is greater than n, then 2088 send an ICMP Parameter Problem, Code 0, message [26] to the IP 2089 Source Address, pointing to the Segments Left field, and discard 2090 the packet. Do not process the DSR Source Route option further. 2092 - Else, decrement the value of the Segments Left field by 1. Let i 2093 equal n minus Segments Left. This is the index of the next 2094 address to be visited in the Address vector. 2096 - If Address[i] or the IP Destination Address is a multicast 2097 address, then discard the packet. Do not process the DSR Source 2098 Route option further. 2100 - If the MTU of the link over which this node would transmit the 2101 packet to forward it to the node Address[i] is less than the size 2102 of the packet, the node MUST discard the packet and send an ICMP 2103 Packet Too Big message to the packet's Source Address [26]. 2105 - Forward the packet to the IP address specified in the Address[i] 2106 field of the IP header, following normal IP forwarding 2107 procedures, including checking and decrementing the Time-to-Live 2108 (TTL) field in the packet's IP header [27, 3]. In this 2109 forwarding of the packet, the next-hop node (identified by 2110 Address[i]) MUST be treated as a direct neighbor node: the 2111 transmission to that next node MUST be done in a single IP 2112 forwarding hop, without Route Discovery and without searching the 2113 Route Cache. 2115 - In forwarding the packet, perform Route Maintenance for the next 2116 hop of the packet, by verifying that the packet was received by 2117 that next-hop node, as described in Section 6.3. 2119 Multicast addresses MUST NOT appear in a DSR Source Route option or 2120 in the IP Destination Address field of a packet carrying a DSR Source 2121 Route option in a DSR header. 2123 6.2. Route Discovery Processing 2125 Route Discovery is the mechanism by which a node S wishing to send a 2126 packet to a destination node D obtains a source route to D. Route 2127 Discovery is used only when S attempts to send a packet to D and 2128 does not already know a route to D. The node initiating a Route 2129 Discovery is known as the "initiator" of the Route Discovery, and the 2130 destination node for which the Route Discovery is initiated is known 2131 as the "target" of the Route Discovery. 2133 Route Discovery operates entirely on demand, with a node initiating 2134 Route Discovery based on its own origination of new packets for 2135 some destination address to which it does not currently know a 2136 route. Route Discovery does not depend on any periodic or background 2137 exchange of routing information or neighbor node detection at any 2138 layer in the network protocol stack at any node. 2140 The Route Discovery procedure utilizes two types of messages, a Route 2141 Request (Section 5.2) and a Route Reply (Section 5.3), to actively 2142 search the ad hoc network for a route to the desired destination. 2143 These DSR messages MAY be carried in any type of IP packet, through 2144 use of the DSR header as described in Section 5. 2146 Except as discussed in Section 6.3.5, a Route Discovery for a 2147 destination address SHOULD NOT be initiated unless the initiating 2148 node has a packet in its Send Buffer requiring delivery to that 2149 destination. A Route Discovery for a given target node MUST NOT be 2150 initiated unless permitted by the rate-limiting information contained 2151 in the Route Request Table. After each Route Discovery attempt, the 2152 interval between successive Route Discoveries for this target SHOULD 2153 be doubled, up to a maximum of MaxRequestPeriod, until a valid Route 2154 Reply is received for this target. 2156 6.2.1. Originating a Route Request 2158 A node initiating a Route Discovery for some target creates and 2159 initializes a Route Request option in a DSR header in some IP packet. 2160 This MAY be a separate IP packet, used only to carry this Route 2161 Request option, or the node MAY include the Route Request option 2162 in some existing packet that it needs to send to the target node 2163 (e.g., the IP packet originated by this node, that caused the node to 2164 attempt Route Discovery for the destination address of the packet). 2165 The Route Request option MUST be included in a DSR header in the 2166 packet. To initialize the Route Request option, the node performs 2167 the following sequence of steps: 2169 - The Option Type in the option MUST be set to the value 2. 2171 - The Opt Data Len field in the option MUST be set to the value 6. 2172 The total size of the Route Request option when initiated 2173 is 8 octets; the Opt Data Len field excludes the size of the 2174 Option Type and Opt Data Len fields themselves. 2176 - The Identification field in the option MUST be set to a new 2177 value, different from that used for other Route Requests recently 2178 initiated by this node for this same target address. For 2179 example, each node MAY maintain a single counter value for 2180 generating a new Identification value for each Route Request it 2181 initiates. 2183 - The Target Address field in the option MUST be set to the IP 2184 address that is the target of this Route Discovery. 2186 The Source Address in the IP header of this packet MUST be the node's 2187 own IP address. The Destination Address in the IP header of this 2188 packet MUST be the IP "limited broadcast" address (255.255.255.255). 2190 A node MUST maintain in its Route Request Table, information about 2191 Route Requests that it initiates. When initiating a new Route 2192 Request, the node MUST use the information recorded in the Route 2193 Request Table entry for the target of that Route Request, and it MUST 2194 update that information in the table entry for use in the next Route 2195 Request initiated for this target. In particular: 2197 - The Route Request Table entry for a target node records the 2198 Time-to-Live (TTL) field used in the IP header of the Route 2199 Request for the last Route Discovery initiated by this node for 2200 that target node. This value allows the node to implement a 2201 variety of algorithms for controlling the spread of its Route 2202 Request on each Route Discovery initiated for a target. As 2203 examples, two possible algorithms for this use of the TTL field 2204 are described in Section 3.3.4. 2206 - The Route Request Table entry for a target node records the 2207 number of consecutive Route Requests initiated for this target 2208 since receiving a valid Route Reply giving a route to that target 2209 node, and the remaining amount of time before which this node MAY 2210 next attempt at a Route Discovery for that target node. 2212 A node MUST use these values to implement a back-off algorithm to 2213 limit the rate at which this node initiates new Route Discoveries 2214 for the same target address. In particular, until a valid Route 2215 Reply is received for this target node address, the timeout 2216 between consecutive Route Discovery initiations for this target 2217 node with the same hop limit SHOULD increase by doubling the 2218 timeout value on each new initiation. 2220 The behavior of a node processing a packet containing DSR header 2221 with both a DSR Source Route option and a Route Request option is 2222 unspecified. Packets SHOULD NOT contain both a DSR Source Route 2223 option and a Route Request option. 2225 Packets containing a Route Request option SHOULD NOT include 2226 an Acknowledgement Request option, SHOULD NOT expect link-layer 2227 acknowledgement or passive acknowledgment, and SHOULD NOT be 2228 retransmitted. The retransmission of packets containing a Route 2229 Request option is controlled solely by the logic described in this 2230 section. 2232 6.2.2. Processing a Received Route Request Option 2234 When a node receives a packet containing a Route Request option, that 2235 node MUST process the option according to the following sequence of 2236 steps: 2238 - If the Target Address field in the Route Request matches this 2239 node's own IP address, then the node SHOULD return a Route Reply 2240 to the initiator of this Route Request (the Source Address in the 2241 IP header of the packet), as described in Section 6.2.4. The 2242 source route for this Reply is the sequence of hop addresses 2244 initiator, Address[1], Address[2], ..., Address[n], target 2246 where initiator is the address of the initiator of this 2247 Route Request, each Address[i] is an address from the Route 2248 Request, and target is the target of the Route Request (the 2249 Target Address field in the Route Request). The value n here 2250 is the number of addresses recorded in the Route Request, or 2251 (Opt Data Len - 6) / 4. 2253 The node then MUST replace the Destination Address field in 2254 the Route Request packet's IP header with the value in the 2255 Target Address field in the Route Request option, and continue 2256 processing the rest of the Route Request packet normally. The 2257 node MUST NOT process the Route Request option further and MUST 2258 NOT retransmit the Route Request to propagate it to other nodes 2259 as part of the Route Discovery. 2261 - Else, the node MUST examine the route recorded in the Route 2262 Request option (the IP Source Address field and the sequence of 2263 Address[i] fields) to determine if this node's own IP address 2264 already appears in this list of addresses. If so, the node MUST 2265 discard the entire packet carrying the Route Request option. 2267 - Else, the node MUST search its Route Request Table for an entry 2268 for the initiator of this Route Request (the IP Source Address 2269 field). If such an entry is found in the table, the node MUST 2270 search the cache of Identification values of recently received 2271 Route Requests in that table entry, to determine if an entry 2272 is present in the cache matching the Identification value 2273 and target node address in this Route Request. If such an 2274 (Identification, target address) entry is found in this cache in 2275 this entry in the Route Request Table, then the node MUST discard 2276 the entire packet carrying the Route Request option. 2278 - Else, this node SHOULD further process the Route Request 2279 according to the following sequence of steps: 2281 o Add an entry for this Route Request in its cache of 2282 (Identification, target address) values of recently received 2283 Route Requests. 2285 o Conceptually create a copy of this entire packet and perform 2286 the following steps on the copy of the packet. 2288 o Append this node's own IP address to the list of Address[i] 2289 values in the Route Request, and increase the value of the 2290 Opt Data Len field in the Route Request by 4 (the size of an 2291 IP address). 2293 o This node SHOULD search its own Route Cache for a route 2294 (from itself, as if it were the source of a packet) to the 2295 target of this Route Request. If such a route is found in 2296 its Route Cache, then this node SHOULD follow the procedure 2297 outlined in Section 6.2.3 to return a "cached Route Reply" 2298 to the initiator of this Route Request, if permitted by the 2299 restrictions specified there. 2301 o If the node does not return a cached Route Reply, then this 2302 node SHOULD link-layer re-broadcast this copy of the packet, 2303 with a short jitter delay before the broadcast is sent. The 2304 jitter period SHOULD be chosen as a random period, uniformly 2305 distributed between 0 and BroadcastJitter. 2307 6.2.3. Generating a Route Reply using the Route Cache 2309 As described in Section 3.3.2, it is possible for a node processing a 2310 received Route Request to avoid propagating the Route Request further 2311 toward the target of the Request, if this node has in its Route Cache 2312 a route from itself to this target. Such a Route Reply generated by 2313 a node from its own cached route to the target of a Route Request is 2314 called a "cached Route Reply", and this mechanism can greatly reduce 2315 the overall overhead of Route Discovery on the network by reducing 2316 the flood of Route Requests. The general processing of a received 2317 Route Request is described in Section 6.2.2; this section specifies 2318 the additional requirements that MUST be met before a cached Route 2319 Reply may be generated and returned and specifies the procedure for 2320 returning such a cached Route Reply. 2322 While processing a received Route Request, for a node to possibly 2323 return a cached Route Reply, it MUST have in its Route Cache a route 2324 from itself to the target of this Route Request. However, before 2325 generating a cached Route Reply for this Route Request, the node MUST 2326 verify that there are no duplicate addresses listed in the route 2327 accumulated in the Route Request together with the route from this 2328 node's Route Cache. Specifically, there MUST be no duplicates among 2329 the following addresses: 2331 - The IP Source Address of the packet containing the Route Request, 2333 - The Address[i] fields in the Route Request, and 2335 - The nodes listed in the route obtained from this node's Route 2336 Cache, excluding the address of this node itself (this node 2337 itself is the common point between the route accumulated in the 2338 Route Request and the route obtained from the Route Cache). 2340 If any duplicates exist among these addresses, then the node MUST NOT 2341 send a cached Route Reply. The node SHOULD continue to process the 2342 Route Request as described in Section 6.2.2. 2344 If the Route Request and the route from the Route Cache meet the 2345 restriction above, then the node SHOULD construct and return a cached 2346 Route Reply as follows: 2348 - The source route for this reply is the sequence of hop addresses 2350 initiator, Address[1], Address[2], ..., Address[n], c-route 2352 where initiator is the address of the initiator of this Route 2353 Request, each Address[i] is an address from the Route Request, 2354 and c-route is the sequence of hop addresses in the source route 2355 to this target node, obtained from the node's Route Cache. In 2356 appending this cached route to the source route for the reply, 2357 the address of this node itself MUST be excluded, since it is 2358 already listed as Address[n]. 2360 - Send a Route Reply to the initiator of the Route Request, using 2361 the procedure defined in Section 6.2.4. The initiator of the 2362 Route Request is indicated in the Source Address field in the 2363 packet's IP header. 2365 If the node returns a cached Route Reply as described above, then 2366 the node MUST NOT propagate the Route Request further (i.e., the 2367 node MUST NOT rebroadcast the Route Request). In this case, instead, 2368 if the packet contains no other DSR options and contains no payload 2369 after the DSR header (e.g., the Route Request is not piggybacked 2370 on a TCP or UDP packet), then the node SHOULD simply discard the 2371 packet. Otherwise (if the packet contains other DSR options or 2372 contains any payload after the DSR header), the node SHOULD forward 2373 the packet along the cached route to the target of the Route Request. 2374 Specifically, if the node does so, it MUST use the following 2375 steps: 2377 - Copy the Target Address from the Route Request option in the 2378 DSR header to the Destination Address field in the packet's IP 2379 header. 2381 - Remove the Route Request option from the DSR header in the 2382 packet, and add a DSR Source Route option to the packet's DSR 2383 header. 2385 - In the DSR Source Route option, set the Address[i] fields 2386 to represent the source route found in this node's Route 2387 Cache to the original target of the Route Discovery (the 2388 new IP Destination Address of the packet). Specifically, 2389 the node copies the hop addresses of the source route into 2390 sequential Address[i] fields in the DSR Source Route option, 2391 for i = 1, 2, ..., n. Address[1] here is the address of this 2392 node itself (the first address in the source route found from 2393 this node to the original target of the Route Discovery). The 2394 value n here is the number of hop addresses in this source route, 2395 excluding the destination of the packet (which is instead already 2396 represented in the Destination Address field in the packet's IP 2397 header). 2399 - Initialize the Segments Left field in the DSR Source Route option 2400 to n as defined above. 2402 - The First Hop External (F) bit in the DSR Source Route option is 2403 copied from the External bit flagging the first hop in the source 2404 route for the packet, as indicated in the Route Cache. 2406 - The Last Hop External (L) bit in the DSR Source Route option is 2407 copied from the External bit flagging the last hop in the source 2408 route for the packet, as indicated in the Route Cache. 2410 - The Salvage field in the DSR Source Route option MUST be 2411 initialized to some nonzero value; the particular nonzero value 2412 used SHOULD be MAX_SALVAGE_COUNT. By initializing this field to 2413 a nonzero value, nodes forwarding or overhearing this packet will 2414 not consider a link to exist between the IP Source Address of the 2415 packet and the Address[1] address in the DSR Source Route option 2416 (e.g., they will not attempt to add this to their Route Cache as 2417 a link). By choosing MAX_SALVAGE_COUNT as the nonzero value to 2418 which the node initializes this field, nodes furthermore will not 2419 attempt to salvage this packet. 2421 - Transmit the packet to the next-hop node on the new source route 2422 in the packet, using the forwarding procedure described in 2423 Section 6.1.5. 2425 6.2.4. Originating a Route Reply 2427 A node originates a Route Reply in order to reply to a received and 2428 processed Route Request, according to the procedures described in 2429 Sections 6.2.2 and 6.2.3. The Route Reply is returned in a Route 2430 Reply option (Section 5.3). The Route Reply option MAY be returned 2431 to the initiator of the Route Request in a separate IP packet, used 2432 only to carry this Route Reply option, or it MAY be included in any 2433 other IP packet being sent to this address. 2435 The Route Reply option MUST be included in a DSR header in the packet 2436 returned to the initiator. To initialize the Route Reply option, the 2437 node performs the following sequence of steps: 2439 - The Option Type in the option MUST be set to the value 3. 2441 - The Opt Data Len field in the option MUST be set to the value 2442 (n * 4) + 3, where n is the number of addresses in the source 2443 route being returned (excluding the Route Discovery initiator 2444 node's address). 2446 - The Last Hop External (L) bit in the option MUST be 2447 initialized to 0. 2449 - The Reserved field in the option MUST be initialized to 0. 2451 - The Route Request Identifier MUST be initialized to the 2452 Identifier field of the Route Request that this reply is sent in 2453 response to. 2455 - The sequence of hop addresses in the source route are copied into 2456 the Address[i] fields of the option. Address[1] MUST be set to 2457 the first-hop address of the route after the initiator of the 2458 Route Discovery, Address[n] MUST be set to the last-hop address 2459 of the source route (the address of the target node), and each 2460 other Address[i] MUST be set to the next address in sequence in 2461 the source route being returned. 2463 The Destination Address field in the IP header of the packet carrying 2464 the Route Reply option MUST be set to the address of the initiator 2465 of the Route Discovery (i.e., for a Route Reply being returned in 2466 response to some Route Request, the IP Source Address of the Route 2467 Request). 2469 After creating and initializing the Route Reply option and the IP 2470 packet containing it, send the Route Reply. In sending the Route 2471 Reply from this node (but not from nodes forwarding the Route Reply), 2472 this node SHOULD delay the Reply by a small jitter period chosen 2473 randomly between 0 and BroadcastJitter. 2475 When returning any Route Reply in the case in which the MAC protocol 2476 in use in the network is not capable of transmitting unicast packets 2477 over uni-directional links, the source route used for routing 2478 the Route Reply packet MUST be obtained by reversing the sequence 2479 of hops in the Route Request packet (the source route that is 2480 then returned in the Route Reply). This restriction on returning 2481 a Route Reply enables the Route Reply to test this sequence of 2482 hops for bi-directionality, preventing the Route Reply from being 2483 received by the initiator of the Route Discovery unless each of 2484 the hops over which the Route Reply is returned (and thus each 2485 of the hops in the source route being returned in the Reply) is 2486 bi-directional. 2488 If sending a Route Reply to the initiator of the Route Request 2489 requires performing a Route Discovery, the Route Reply Option MUST 2490 be piggybacked on the packet that contains the Route Request. This 2491 piggybacking prevents a loop wherein the target of the new Route 2492 Request (which was itself the initiator of the original Route 2493 Request) must do another Route Request in order to return its 2494 Route Reply. 2496 If sending the Route Reply to the initiator of the Route Request 2497 does not require performing a Route Discovery, a node SHOULD send a 2498 unicast Route Reply in response to every Route Request it receives 2499 for which it is the target node. 2501 6.2.5. Processing a Received Route Reply Option 2503 Section 6.1.4 describes the general processing for a received packet, 2504 including the addition of routing information from options in the 2505 packet's DSR header to the receiving node's Route Cache. 2507 If the received packet contains a Route Reply, no additional special 2508 processing of the Route Reply option is required beyond what is 2509 described there. As described in Section 4.1 anytime a node adds 2510 new information to its Route Cache (including the information added 2511 from this Route Reply option), the node SHOULD check each packet in 2512 its own Send Buffer (Section 4.2) to determine whether a route to 2513 that packet's IP Destination Address now exists in the node's Route 2514 Cache (including the information just added to the Cache). If so, 2515 the packet SHOULD then be sent using that route and removed from the 2516 Send Buffer. This general procedure handles all processing required 2517 for a received Route Reply option. 2519 6.3. Route Maintenance Processing 2521 Route Maintenance is the mechanism by which a source node S is able 2522 to detect, while using a source route to some destination node D, 2523 if the network topology has changed such that it can no longer use 2524 its route to D because a link along the route no longer works. When 2525 Route Maintenance indicates that a source route is broken, S can 2526 attempt to use any other route it happens to know to D, or can invoke 2527 Route Discovery again to find a new route for subsequent packets 2528 to D. Route Maintenance for this route is used only when S is 2529 actually sending packets to D. 2531 Specifically, when forwarding a packet, a node MUST attempt to 2532 receive an acknowledgement for the packet from the next-hop node. If 2533 no acknowledgement is received after MaxMaintRexmt retransmissions of 2534 the packet (after the initial transmission of the packet), the node 2535 determines that the link for this next-hop node of the source route 2536 is "broken". This acknowledgement from the next-hop node for Route 2537 Maintenance can be implemented using a link-layer acknowledgement 2538 (Section 6.3.1), using a "passive acknowledgement" (Section 6.3.2), 2539 or using a network-layer acknowledgement (Section 6.3.3); the 2540 particular strategy for retransmission timing depends on the type of 2541 acknowledgement mechanism used. If no acknowledgment is received 2542 after MaxMaintRexmt retransmissions (if necessary), the node SHOULD 2543 originate a Route Error to the original sender of the packet, as 2544 described in Section 6.3.4. 2546 In deciding whether or not to send a Route Error in response to 2547 attempting to forward a packet from some sender over a broken link, 2548 a node MUST limit the number of consecutive packets from a single 2549 sender that the node attempts to forward over this same broken 2550 link for which the node chooses not to return a Route Error; this 2551 requirement MAY be satisfied by returning a Route Error for each 2552 packet that the node attempts to forward over a broken link. 2554 6.3.1. Using Link-Layer Acknowledgments 2556 If the MAC protocol in use provides feedback as to the successful 2557 delivery of a data packet (such as is provided by the link-layer 2558 acknowledgement frame defined by IEEE 802.11 [11]), then the use 2559 of the DSR Acknowledgement Request and Acknowledgement options 2560 is not necessary. If such link-layer feedback is available, it 2561 SHOULD be used instead of any other acknowledgement mechanism 2562 for Route Maintenance, and the node SHOULD NOT use either passive 2563 acknowledgements or network-layer acknowledgements for Route 2564 Maintenance. 2566 When using link-layer acknowledgements for Route Maintenance, the 2567 retransmission timing and the timing at which retransmission attempts 2568 are scheduled are generally controlled by the particular link layer 2569 implementation in use in the network. For example, in IEEE 802.11, 2570 the link-layer acknowledgement is returned after the data packet as 2571 a part of the basic access method of of the IEEE 802.11 Distributed 2572 Coordination Function (DCF) MAC protocol; the time at which the 2573 acknowledgement is expected to arrive and the time at which the next 2574 retransmission attempt (if necessary) will occur are controlled by 2575 the MAC protocol implementation. 2577 When a node receives a link-layer acknowledgement for any packet in 2578 its Retransmission Buffer, that node SHOULD remove that packet from 2579 its Retransmission Buffer, stopping Route Maintenance retransmissions 2580 for that packet. 2582 6.3.2. Using Passive Acknowledgments 2584 When link-layer acknowledgements are not available, but passive 2585 acknowledgements [16] are available, passive acknowledgements SHOULD 2586 be used for Route Maintenance when originating or forwarding a packet 2587 along any hop other than the last hop (the hop leading to the IP 2588 Destination Address node of the packet). In particular, passive 2589 acknowledgements SHOULD be used for Route Maintenance in such cases 2590 if the node can place its network interface into "promiscuous" 2591 receive mode, and network links used for data packets generally 2592 operate bi-directionally (such as when the MAC protocol requires 2593 this, as with IEEE 802.11). 2595 A node MUST NOT attempt to use passive acknowledgements for Route 2596 Maintenance for a packet originated or forwarded over its last hop 2597 (the hop leading to the IP Destination Address node of the packet), 2598 since the receiving node will not be forwarding the packet and thus 2599 no passive acknowledgement will be available to be heard by this 2600 node. Beyond this restriction, a node MAY utilize a variety of 2601 strategies in using passive acknowledgements for Route Maintenance of 2602 a packet that it originates or forwards. For example, the following 2603 two strategies are possible: 2605 - Each time a node receives a packet to be forwarded to a node 2606 other than the final destination (the IP Destination Address 2607 of the packet), that node sends the original transmission of 2608 that packet without requesting a network-layer acknowledgement 2609 for it. If no passive acknowledgement is received within 2610 PassiveAckTimeout after this transmission, the node retransmits 2611 the packet, again without requesting a network-layer 2612 acknowledgement for it; the same PassiveAckTimeout timeout value 2613 is used for each such attempt. If no acknowledgement has been 2614 received after a total of TryPassiveAcks retransmissions of 2615 the packet, network-layer acknowledgements (as described in 2616 Section 6.3.3) are used for all remaining attempts for that 2617 packet. 2619 - Each node keeps a table of possible next-hop destination nodes, 2620 noting whether or not passive acknowledgements can typically 2621 be expected from transmission to that node, and the expected 2622 latency and jitter of a passive acknowledgement from that node. 2623 Each time a node receives a packet to be forwarded to a node 2624 other than the IP Destination Address, the node checks its table 2625 of next-hop destination nodes to determine whether to use a 2626 passive acknowledgement or a network-layer acknowledgement for 2627 that transmission to that node. The timeout for this packet 2628 can also be derived from this table. A node using this method 2629 SHOULD prefer using passive acknowledgements to network-layer 2630 acknowledgements. 2632 In using passive acknowledgements for a packet that it originates or 2633 forwards, a node considers the later receipt of a new packet (e.g., 2634 with promiscuous receive mode enabled on its network interface) to be 2635 an acknowledgement of this first packet if both of the following two 2636 tests succeed: 2638 - The Source Address, Destination Address, Protocol, 2639 Identification, and Fragment Offset fields in the IP header 2640 of the two packets MUST match [27], and 2642 - If either packet contains a DSR Source Route header, both packets 2643 MUST contain one, and the value in the Segments Left field in the 2644 DSR Source Route header of the new packet MUST be less than that 2645 in the first packet. 2647 When a node hears such a passive acknowledgement for any packet in 2648 its Retransmission Buffer, that node SHOULD remove that packet from 2649 its Retransmission Buffer, stopping Route Maintenance retransmissions 2650 for that packet. 2652 6.3.3. Using Network-Layer Acknowledgments 2654 When a node originates or forwards a packet and has no other 2655 mechanism of acknowledgement available to determine successful 2656 delivery of the packet to the next-hop node in the source route 2657 for Route Maintenance, that node SHOULD request a network-layer 2658 acknowledgement from that next-hop node. To do so, the node inserts 2659 an Acknowledgement Request option in the DSR header in the packet. 2660 The Identification field in that Acknowledgement Request option MUST 2661 be set to a value unique over all packets transmitted by this node 2662 to the same next-hop node that are either unacknowledged or recently 2663 acknowledged. 2665 When a node receives a packet containing an Acknowledgement Request 2666 option, then that node performs the following tests on the packet: 2668 - If the indicated next-hop node address for this packet does not 2669 match any of this node's own IP addresses, then this node MUST 2670 NOT process the Acknowledgement Request option. The indicated 2671 next-hop node address is the next Address[i] field in the DSR 2672 Source Route option in the DSR header in the packet, or is the IP 2673 Destination Address in the packet if the packet does not contain 2674 a DSR Source Route option or the Segments Left there is zero. 2676 - If the packet contains an Acknowledgement option, then this node 2677 MUST NOT process the Acknowledgement Request option. 2679 If neither of the tests above fails, then this node MUST process the 2680 Acknowledgement Request option by sending an Acknowledgement option 2681 to the previous-hop node; to do so, the node performs the following 2682 sequence of steps: 2684 - Create a packet and set the IP Protocol field to the protocol 2685 number assigned for a DSR header (TBA???). 2687 - Set the IP Source Address field in this packet to the IP address 2688 of this node, copied from the source route in the DSR Source 2689 Route option in that packet (or from the IP Destination Address 2690 field of the packet, if the packet does not contain a DSR Source 2691 Route option). 2693 - Set the IP Destination Address field in this packet to the IP 2694 address of the previous-hop node, copied from the source route 2695 in the DSR Source Route option in that packet (or from the IP 2696 Source Address field of the packet, if the packet does not 2697 contain a DSR Source Route option). 2699 - Add a DSR header to the packet, and set the DSR header's 2700 Next Header field to the "No Next Header" value. 2702 - Add an Acknowledgement option to the DSR header in the packet; 2703 set the Acknowledgement option's Option Type field to 6 and the 2704 Opt Data Len field to 10. 2706 - Copy the Identification field from the received Acknowledgement 2707 Request option into the Identification field in the 2708 Acknowledgement option. 2710 - Set the ACK Source Address field in the Acknowledgement option to 2711 be the IP Source Address of this new packet (set above to be the 2712 IP address of this node). 2714 - Set the ACK Destination Address field in the Acknowledgement 2715 option to be the IP Destination Address of this new packet (set 2716 above to be the IP address of the previous-hop node). 2718 - Send the packet as described in Section 6.1.1. 2720 Packets containing an Acknowledgement option SHOULD NOT be 2721 retransmitted by intermediate nodes for Route Maintenance, and SHOULD 2722 NOT expect a link-layer acknowledgement or passive acknowledgment. 2724 When a node receives a packet with both an Acknowledgement option 2725 and an Acknowledgement Request option, if that node is not the 2726 destination of the Acknowledgement option (the IP Destination Address 2727 of the packet), then the Acknowledgement Request option MUST 2728 be ignored. Otherwise (that node is the destination of the 2729 Acknowledgement option), that node MUST process the Acknowledgement 2730 Request option by returning an Acknowledgement option according to 2731 the following sequence of steps: 2733 - Create a packet and set the IP Protocol field to the protocol 2734 number assigned for a DSR header (TBA???). 2736 - Set the IP Source Address field in this packet to the IP address 2737 of this node, copied from the source route in the DSR Source 2738 Route option in that packet (or from the IP Destination Address 2739 field of the packet, if the packet does not contain a DSR Source 2740 Route option). 2742 - Set the IP Destination Address field in this packet to the IP 2743 address of the node originating the Acknowledgement option. 2745 - Add a DSR header to the packet, and set the DSR header's 2746 Next Header field to the "No Next Header" value. 2748 - Add an Acknowledgement option to the DSR header in this packet; 2749 set the Acknowledgement option's Option Type field to 6 and the 2750 Opt Data Len field to 10. 2752 - Copy the Identification field from the received Acknowledgement 2753 Request option into the Identification field in the 2754 Acknowledgement option. 2756 - Set the ACK Source Address field in the option to be the IP 2757 Source Address of this new packet (set above to be the IP address 2758 of this node). 2760 - Set the ACK Destination Address field in the option to be the IP 2761 Destination Address of this new packet (set above to be the IP 2762 address of the node originating the Acknowledgement option.) 2764 - Send the packet directly to the destination. The IP 2765 Destination Address MUST be treated as a direct neighbor node: 2766 the transmission to that node MUST be done in a single IP 2767 forwarding hop, without Route Discovery and without searching 2768 the Route Cache. In addition, this packet MUST NOT contain a 2769 DSR Acknowledgement Request, MUST NOT be retransmitted for Route 2770 Maintenance, and MUST NOT expect a link-layer acknowledgement or 2771 passive acknowledgment. 2773 When using network-layer acknowledgements for Route Maintenance, 2774 a node SHOULD use an adaptive algorithm in determining the 2775 retransmission timeout for each transmission attempt of a packet. 2776 For example, a node SHOULD maintain a separate round-trip time (RTT) 2777 estimate for each to which it has recently attempted to transmit 2778 packets, and it SHOULD use this RTT estimate in setting the timeout 2779 for each retransmission attempt for Route Maintenance. The TCP RTT 2780 estimation algorithm has been shown to work well for this purpose in 2781 implementation and testbed experiments with DSR [20, 22]. 2783 6.3.4. Originating a Route Error 2785 When a node is unable to verify successful delivery of a packet to 2786 the next-hop node after reaching a maximum number of retransmission 2787 attempts, a node SHOULD send a Route Error to the IP Source Address 2788 of the packet. When sending a Route Error for a packet containing 2789 either a Route Error option or an Acknowledgement option, a node 2790 SHOULD add these existing options to its Route Error, subject to the 2791 limit described below. 2793 A node transmitting a Route Error MUST perform the following steps: 2795 - Create an IP packet and set the Source Address field in this 2796 packet's IP header to the address of this node. 2798 - If the Salvage field in the DSR Source Route option in the 2799 packet triggering the Route Error is zero, then copy the 2800 Source Address field of the packet triggering the Route Error 2801 into the Destination Address field in the new packet's IP 2802 header; otherwise, copy the Address[1] field from the DSR Source 2803 Route option of the packet triggering the Route Error into the 2804 Destination Address field in the new packet's IP header 2806 - Insert a DSR header into the new packet. 2808 - Add a Route Error Option to the new packet, setting the Error 2809 Type to NODE_UNREACHABLE, the Salvage value to the Salvage 2810 value from the DSR Source Route option of the packet triggering 2811 the Route Error, and the Unreachable Node Address field to 2812 the address of the next-hop node from the original source 2813 route. Set the Error Source Address field to this node's IP 2814 address, and the Error Destination field to the new packet's IP 2815 Destination Address. 2817 - If the packet triggering the Route Error contains any Route Error 2818 or Acknowledgement options, the node MAY append to its Route 2819 Error each of these options, with the following constraints: 2821 o The node MUST NOT include any Route Error option from the 2822 packet triggering the new Route Error, for which the total 2823 salvage count (Section 5.4) of that included Route Error 2824 would be greater than MAX_SALVAGE_COUNT in the new packet. 2826 o If any Route Error option from the packet triggering the new 2827 Route Error is not included in the packet, the node MUST NOT 2828 include any following Route Error or Acknowledgement options 2829 from the packet triggering the new Route Error. 2831 o Any appended options from the packet triggering the Route 2832 Error MUST follow the new Route Error in the packet. 2834 o In appending these options to the new Route Error, the order 2835 of these options from the packet triggering the Route Error 2836 MUST be preserved. 2838 - Send the packet as described in Section 6.1.1. 2840 6.3.5. Processing a Received Route Error Option 2842 When a node receives a packet containing a Route Error option, that 2843 node MUST process the Route Error option according to the following 2844 sequence of steps: 2846 - The node MUST remove from its Route Cache the link from the 2847 node identified by the Error Source Address field to the node 2848 identified by the Unreachable Node Address field (if this link is 2849 present in its Route Cache). If the node implements its Route 2850 Cache as a link cache, as described in Section 4.1, only this 2851 single link is removed; if the node implements its Route Cache as 2852 a path cache, however, all routes (paths) that use this link are 2853 removed. 2855 - If the option following the Route Error is an Acknowledgement 2856 or Route Error option sent by this node (that is, with 2857 Acknowledgement or Error Source Address equal to this node's 2858 address), copy the DSR options following the current Route 2859 Error into a new packet with IP Source Address equal to this 2860 node's own IP address and IP Destination Address equal to the 2861 Acknowledgement or Error Destination Address. Transmit this 2862 packet as described in Section 6.1.1, with the salvage count 2863 in the DSR Source Route option set to the Salvage value of the 2864 Route Error. 2866 In addition, after processing the Route Error as described above, 2867 the node MAY initiate a new Route Discovery for any destination node 2868 for which it then has no route in its Route Cache as a result of 2869 processing this Route Error, if the node has indication that a route 2870 to that destination is needed. For example, if the node has an open 2871 TCP connection to some destination node, then if the processing of 2872 this Route Error removed the only route to that destination from this 2873 node's Route Cache, then this node MAY initiate a new Route Discovery 2874 for that destination node. Any node, however, MUST limit the rate at 2875 which it initiates new Route Discoveries for any single destination 2876 address, and any new Route Discovery initiated in this way as part of 2877 processing this Route Error MUST conform to this limit. 2879 6.3.6. Salvaging a Packet 2881 When an intermediate node forwarding a packet detects through Route 2882 Maintenance that the next-hop link along the route for that packet is 2883 broken (Section 6.3), if the node has another route to the packet's 2884 IP Destination Address in its Route Cache, the node SHOULD "salvage" 2885 the packet rather than discarding it. To do so using the route found 2886 in its Route Cache, this node processes the packet as follows: 2888 - If the MAC protocol in use in the network is not capable of 2889 transmitting unicast packets over uni-directional links, as 2890 discussed in Section 3.3.1, then if this packet contains a Route 2891 Reply option, remove and discard the Route Reply option in the 2892 packet; if the DSR header in the packet then contains no DSR 2893 options, remove the DSR header from the packet. If the resulting 2894 packet then contains only an IP header, the node SHOULD NOT 2895 salvage the packet and instead SHOULD discard the entire packet. 2897 When returning any Route Reply in the case in which the MAC 2898 protocol in use in the network is not capable of transmitting 2899 unicast packets over uni-directional links, the source route 2900 used for routing the Route Reply packet MUST be obtained by 2901 reversing the sequence of hops in the Route Request packet (the 2902 source route that is then returned in the Route Reply). This 2903 restriction on returning a Route Reply and on salvaging a packet 2904 that contains a Route Reply option enables the Route Reply to 2905 test this sequence of hops for bi-directionality, preventing the 2906 Route Reply from being received by the initiator of the Route 2907 Discovery unless each of the hops over which the Route Reply is 2908 returned (and thus each of the hops in the source route being 2909 returned in the Reply) is bi-directional. 2911 - Modify the existing DSR Source Route option in the packet so 2912 that the Address[i] fields represent the source route found in 2913 this node's Route Cache to this packet's IP Destination Address. 2914 Specifically, the node copies the hop addresses of the source 2915 route into sequential Address[i] fields in the DSR Source Route 2916 option, for i = 1, 2, ..., n. Address[1] here is the address 2917 of the salvaging node itself (the first address in the source 2918 route found from this node to the IP Destination Address of the 2919 packet). The value n here is the number of hop addresses in this 2920 source route, excluding the destination of the packet (which is 2921 instead already represented in the Destination Address field in 2922 the packet's IP header). 2924 - Initialize the Segments Left field in the DSR Source Route option 2925 to n as defined above. 2927 - The First Hop External (F) bit in the DSR Source Route option is 2928 copied from the External bit flagging the first hop in the source 2929 route for the packet, as indicated in the Route Cache. 2931 - The Last Hop External (L) bit in the DSR Source Route option is 2932 copied from the External bit flagging the last hop in the source 2933 route for the packet, as indicated in the Route Cache. 2935 - The Salvage field in the DSR Source Route option is set to 1 plus 2936 the value of the Salvage field in the DSR Source Route option of 2937 the packet that caused the error. 2939 - Transmit the packet to the next-hop node on the new source route 2940 in the packet, using the forwarding procedure described in 2941 Section 6.1.5. 2943 As described in Section 6.3.4, the node in this case also SHOULD 2944 return a Route Error to the original sender of the packet. If the 2945 node chooses to salvage the packet, it SHOULD do so after originating 2946 the Route Error. 2948 7. Protocol Constants and Configuration Variables 2950 Any DSR implementation MUST support the following configuration 2951 variables and MUST support a mechanism enabling the value of these 2952 variables to be modified by system management. The specific variable 2953 names are used for demonstration purposes only, and an implementation 2954 is not required to use these names for the configuration variables, 2955 so long as the external behavior of the implementation is consistent 2956 with that described in this document. 2958 For each configuration variable below, the default value is specified 2959 to simplify configuration. In particular, the default values given 2960 below are chosen for a DSR network running over 2 Mbps IEEE 802.11 2961 network network interfaces using the Distributed Coordination 2962 Function (DCF) MAC with RTS and CTS [11, 5]. 2964 BroadcastJitter 10 milliseconds 2966 RouteCacheTimeout 300 seconds 2968 SendBufferTimeout 30 seconds 2970 RequestTableSize 64 nodes 2971 RequestTableIds 16 identifiers 2972 MaxRequestRexmt 16 retransmissions 2973 MaxRequestPeriod 10 seconds 2974 RequestPeriod 500 milliseconds 2975 NonpropRequestTimeout 30 milliseconds 2977 RexmtBufferSize 50 packets 2979 MaxMaintRexmt 2 retransmissions 2981 TryPassiveAcks 1 attempt 2982 PassiveAckTimeout 100 milliseconds 2984 GratReplyHoldoff 1 second 2986 In addition, the following protocol constant MUST be supported by any 2987 implementation of the DSR protocol: 2989 MAX_SALVAGE_COUNT 15 salvages 2991 8. IANA Considerations 2993 This document proposes the use of a DSR header, which requires an IP 2994 Protocol number. 2996 In addition, this document proposes use of the value "No Next Header" 2997 (originally defined for use in IPv6) within an IPv4 packet, to 2998 indicate that no further header follows a DSR header. 3000 9. Security Considerations 3002 This document does not specifically address security concerns. This 3003 document does assume that all nodes participating in the DSR protocol 3004 do so in good faith and without malicious intent to corrupt the 3005 routing ability of the network. In mission-oriented environments 3006 where all the nodes participating in the DSR protocol share a 3007 common goal that motivates their participation in the protocol, the 3008 communications between the nodes can be encrypted at the physical 3009 channel or link layer to prevent attack by outsiders. 3011 Appendix A. Link-MaxLife Cache Description 3013 As guidance to implementors of DSR, the description below outlines 3014 the operation of a possible implementation of a Route Cache for DSR 3015 that has been shown to outperform other other caches studied in 3016 detailed simulations. Use of this design for the Route Cache is 3017 recommended in implementations of DSR. 3019 This cache, called "Link-MaxLife" [9], is a link cache, in that each 3020 individual link (hop) in the routes returned in Route Reply packets 3021 (or otherwise learned from the header of overhead packets) is added 3022 to a unified graph data structure of this node's current view of the 3023 network topology, as described in Section 4.1. To search for a route 3024 in this cache to some destination node, the sending node uses a graph 3025 search algorithm, such as the well-known Dijkstra's shortest-path 3026 algorithm, to find the current best path through the graph to the 3027 destination node. 3029 The Link-MaxLife form of link cache is adaptive in that each link in 3030 the cache has a timeout that is determined dynamically by the caching 3031 node according to its observed past behavior of the two nodes at the 3032 ends of the link; in addition, when selecting a route for a packet 3033 being sent to some destination, among cached routes of equal length 3034 (number of hops) to that destination, Link-MaxLife selects the route 3035 with the longest expected lifetime (highest minimum timeout of any 3036 link in the route). 3038 Specifically, in Link-MaxLife, a link's timeout in the Route Cache 3039 is chosen according to a "Stability Table" maintained by the caching 3040 node. Each entry in a node's Stability Table records the address of 3041 another node and a factor representing the perceived "stability" of 3042 this node. The stability of each other node in a node's Stability 3043 Table is initialized to InitStability. When a link from the Route 3044 Cache is used in routing a packet originated or salvaged by that 3045 node, the stability metric for each of the two endpoint nodes of that 3046 link is incremented by the amount of time since that link was last 3047 used, multiplied by StabilityIncrFactor (StabilityIncrFactor >= 1); 3048 when a link is observed to break and the link is thus removed 3049 from the Route Cache (either due the receipt of a Route Error for 3050 this link or due to exceeding the maximum number of retransmission 3051 attempts for Route Maintenance for a packet being originated or 3052 forwarded by this node), the stability metric for each of the two 3053 endpoint nodes of that link is multiplied by StabilityDecrFactor 3054 (StabilityDecrFactor < 1). 3056 When a node adds a new link to its Route Cache, the node assigns a 3057 lifetime for that link in the Cache equal to the stability of the 3058 less "stable" of the two endpoint nodes for the link, except that a 3059 link is not allowed to be given a lifetime less than MinLifetime. 3060 When a link is used in a route chosen for a packet originated or 3061 salvaged by this node, the link's lifetime is set to be at least 3062 UseExtends into the future; if the lifetime of that link in the 3063 Route Cache is already further into the future, the lifetime remains 3064 unchanged. 3066 When a node using Link-MaxLife selects a route from its Route Cache 3067 for a packet being originated or salvaged by this node, it selects 3068 the shortest-length route that has the longest expected lifetime 3069 (highest minimum timeout of any link in the route), as opposed to 3070 simply selecting an arbitrary route of shortest length. 3072 The following configuration variables are used in the description 3073 of Link-MaxLife above. The specific variable names are used for 3074 demonstration purposes only, and an implementation is not required 3075 to use these names for these configuration variables. For each 3076 configuration variable below, the default value is specified to 3077 simplify configuration. In particular, the default values given 3078 below are chosen for a DSR network where nodes move at relative 3079 velocities between 12 and 25 seconds per transmission radius. 3081 InitStability 25 seconds 3082 StabilityIncrFactor 4 3083 StabilityDecrFactor 2 3085 MinLifetime 1 second 3086 UseExtends 120 seconds 3088 Appendix B. Location of DSR in the ISO Network Reference Model 3090 When designing DSR, we had to determine at what layer within 3091 the protocol hierarchy to implement ad hoc network routing. We 3092 considered two different options: routing at the link layer (ISO 3093 layer 2) and routing at the network layer (ISO layer 3). Originally, 3094 we opted to route at the link layer for several reasons: 3096 - Pragmatically, running the DSR protocol at the link layer 3097 maximizes the number of mobile nodes that can participate in 3098 ad hoc networks. For example, the protocol can route equally 3099 well between IPv4 [27], IPv6 [6], and IPX [32] nodes. 3101 - Historically [13, 14], DSR grew from our contemplation of 3102 a multi-hop propagating version of the Internet's Address 3103 Resolution Protocol (ARP) [25], as well as from the routing 3104 mechanism used in IEEE 802 source routing bridges [24]. These 3105 are layer 2 protocols. 3107 - Technically, we designed DSR to be simple enough that it could 3108 be implemented directly in the firmware inside wireless network 3109 interface cards [13, 14], well below the layer 3 software within 3110 a mobile node. We see great potential in this for DSR running 3111 inside a cloud of mobile nodes around a fixed base station, 3112 where DSR would act to transparently extend the coverage range 3113 to these nodes. Mobile nodes that would otherwise be unable 3114 to communicate with the base station due to factors such as 3115 distance, fading, or local interference sources could then reach 3116 the base station through their peers. 3118 Ultimately, however, we decided to specify and to implement [20] 3119 DSR as a layer 3 protocol, since this is the only layer at which we 3120 could realistically support nodes with multiple network interfaces of 3121 different types forming an ad hoc network. 3123 Appendix C. Implementation and Evaluation Status 3125 The initial design of the DSR protocol, including DSR's basic Route 3126 Discovery and Route Maintenance mechanisms, was first published in 3127 December 1994 [13], with significant additional design details and 3128 initial simulation results published in early 1996 [14]. 3130 The DSR protocol has been extensively studied since then through 3131 additional detailed simulations. In particular, we have implemented 3132 DSR in the ns-2 network simulator [23, 5] and performed extensive 3133 simulations of DSR using ns-2 (e.g., [5, 19]). We have also 3134 conducted evaluations of different caching strategies documented in 3135 this draft [9]. 3137 We have also implemented the DSR protocol under the FreeBSD 2.2.7 3138 operating system running on Intel x86 platforms. FreeBSD [8] is 3139 based on a variety of free software, including 4.4 BSD Lite from the 3140 University of California, Berkeley. For the environments in which 3141 we used it, this implementation is functionally equivalent to the 3142 version of the DSR protocol specified in this draft. 3144 During the 7 months from August 1998 to February 1999, we designed 3145 and implemented a full-scale physical testbed to enable the 3146 evaluation of ad hoc network performance in the field, in an actively 3147 mobile ad hoc network under realistic communication workloads. The 3148 last week of February and the first week of March of 1999 included 3149 demonstrations of this testbed to a number of our sponsors and 3150 partners, including Lucent Technologies, Bell Atlantic, and DARPA. 3151 A complete description of the testbed is available as a Technical 3152 Report [20]. 3154 We have since ported this implementation of DSR to FreeBSD 3.3, and 3155 we have also added a preliminary version of Quality of Service (QoS) 3156 support for DSR. A demonstration of this modified version of DSR was 3157 presented in July 2000. These QoS features are not included in this 3158 draft, and will be added later in a separate draft on top of the base 3159 protocol specified here. 3161 DSR has also been implemented under Linux by Alex Song at the 3162 University of Queensland, Australia [31]. This implementation 3163 supports the Intel x86 PC platform and the Compaq iPAQ. 3165 Several other independent groups have also used DSR as a platform for 3166 their own research, or and as a basis of comparison between ad hoc 3167 network routing protocols. 3169 Changes from Previous Version of the Draft 3171 This appendix briefly lists some of the major changes in this 3172 draft relative to the previous version of this same draft, 3173 draft-ietf-manet-dsr-05.txt: 3175 - Clarified how to handle Route Maintenance at the original sender 3176 of a packet, which is slightly different than at an intermediate 3177 node forwarding the packet. 3179 - In the definition of the Route Cache in Section 4.1, if there 3180 are multiple cached routes to a destination, a node MUST prefer 3181 routes that do not have the External flag set on any link; this 3182 restriction was previously specified as a "SHOULD". This change 3183 does not affect the operation of DSR with respect to this draft, 3184 since the use of external links is outside the scope of this 3185 draft. 3187 - Clarified that the Retransmission Buffer MAY be of limited size, 3188 and that when adding a new packet to the Retransmission Buffer, 3189 if the buffer size is insufficient to hold the new packet, the 3190 new packet SHOULD be silently discarded. 3192 - Changed the calculation of the Salvage field in a Route 3193 Error option and the total salvage count of an option to not 3194 explicitely increment the count when the count is copied from a 3195 DSR Source Route option into a new Route Error option. Instead, 3196 the increment is implicit in the value of the Salvage field 3197 and is added in when the total salvage count of an option is 3198 calculated. 3200 - In Section 5.2, corrected the specification of the number of 3201 Address[i] fields present in a Route Request option. The number 3202 of addresses present is indicated by the Opt Data Len field in 3203 the option as n = (Opt Data Len - 6) / 4. 3205 - In Section 6.1.3, corrected the specification of the steps for 3206 adding a DSR Source Route option to a packet. As described 3207 elsewhere in the draft, the entire source route (excluding the 3208 address of the originating node and the final destination address 3209 of the packet) is copied into the DSR Source Route option, and 3210 the IP Destination Address of the packet is not changed when 3211 inserting the source route. 3213 - Added a specific statement in the abstract and introduction 3214 that this document specifies the operation of DSR only for 3215 IPv4. Operation of DSR with IPv6 [6] will be covered in other 3216 documents. 3218 - Removed the ACK Request Source Address field from the 3219 Acknowledgement Request option, as this field was not used in 3220 standard DSR; instead, the address of the node requesting a DSR 3221 Acknowledgement is obtained as the previous-hop address of the 3222 source route in the packet. This field is, however, used in the 3223 "flow state" enhancement to DSR [10] and will be specified in 3224 that draft. 3226 - The DSR header was previously specified to always be a multiple 3227 of 4 octet in size; this is now only required if any other 3228 headers follow the DSR header in the packet. 3230 - Clarified the definition of salvaging to be a "SHOULD" rather 3231 than a "MAY". 3233 - Added the definition of the Gratuitous Route Reply Table as a new 3234 conceptual data structure in Section 4.4, and added corresponding 3235 uses of it in the detailed operation. This data structure and 3236 its use have always been a part of the DSR simulation but had not 3237 previously been documented in the draft. 3239 - Removed the Identification field from the definition of a Route 3240 Reply option since it was not used in the protocol. 3242 - Removed the restriction that the value of the Identification 3243 field in an Acknowledgement Request option needed to be nonzero; 3244 the value zero at one time had a special meaning in the protocol 3245 but no longer is used for this purpose. 3247 - Added a description of a specific possible implementation of the 3248 Route Cache data structure, called "Link-MaxLife", in Appendix A. 3249 The actual choice of data structure implementation to use for 3250 the Route Cache in any DSR implementation is a local matter 3251 for each node and affects only performance, not correctness or 3252 interoperability; the Link-MaxLife cache, however, has been 3253 studied extensively and been shown to outperform other types of 3254 cache implementations studied in detailed simulation [9], and its 3255 use in DSR implementations is recommended. 3257 - Changed most of the protocol constants to now be configuration 3258 variables, which MUST support a mechanism enabling the value of 3259 these variables to be modified by system management. Also, to 3260 be clear in the specification which values are variables now and 3261 which are constants, changed the names of all variables to be in 3262 MixedCase instead of ALL_CAPS. 3264 - Changed name of the constant MAX_SALVAGE_TIMES to 3265 MAX_SALVAGE_COUNT. 3267 - Changed the name of the variable DsrMaxRxtShift to now 3268 be MaxMaintRexmt. Also changed the name of the variable 3269 DsrRxmtBufferSize to now be RexmtBufferSize. 3271 - Clarified the description of what to add to a node's Route Cache 3272 in response to different options in the DSR header of a received 3273 packet, and coalesced this description into Section 6.1.4. 3275 - In Section 6.3.5, added a suggestion that a node, after 3276 processing a Route Error, MAY initiate a new Route Discovery for 3277 any destination node for which it then has no route in its Route 3278 Cache as a result of processing this Route Error, if the node has 3279 indication that a route to that destination is needed (e.g., an 3280 open TCP connection). Such Route Discoveries MUST conform to the 3281 standard rate limiting for Route Discoveries. 3283 - Clarified the retransmission timing for Route Maintenance 3284 retransmissions, in Section 6.3. 3286 - Updated the implementation and evaluation description in 3287 Appendix C to include mention of the implementation of DSR under 3288 Linux by Alex Song at the University of Queensland, Australia. 3289 This implementation supports the Intel x86 PC platform and the 3290 Compaq iPAQ. 3292 - Changed the status of the document to indicate full conformance 3293 with all provisions of Section 10 of RFC 2026. 3295 Acknowledgements 3297 The protocol described in this draft has been designed and developed 3298 within the Monarch Project, a research project at Rice University 3299 (previously at Carnegie Mellon University) that is developing 3300 adaptive networking protocols and protocol interfaces to allow truly 3301 seamless wireless and mobile node networking [15, 30]. 3303 The authors would like to acknowledge the substantial contributions 3304 of Josh Broch in helping to design, simulate, and implement the DSR 3305 protocol. Josh is currently on leave of absence from Carnegie Mellon 3306 University at AON Networks. We thank him for his contributions to 3307 earlier versions of this draft. 3309 We would also like to acknowledge the assistance of Robert V. Barron 3310 at Carnegie Mellon University. Bob ported our DSR implementation 3311 from FreeBSD 2.2.7 into FreeBSD 3.3. 3313 References 3315 [1] David F. Bantz and Frederic J. Bauchot. Wireless LAN Design 3316 Alternatives. IEEE Network, 8(2):43--53, March/April 1994. 3318 [2] Vaduvur Bharghavan, Alan Demers, Scott Shenker, and Lixia 3319 Zhang. MACAW: A Media Access Protocol for Wireless LAN's. In 3320 Proceedings of the ACM SIGCOMM '94 Conference, pages 212--225, 3321 August 1994. 3323 [3] Robert T. Braden, editor. Requirements for Internet 3324 Hosts---Communication Layers. RFC 1122, October 1989. 3326 [4] Scott Bradner. Key words for use in RFCs to Indicate 3327 Requirement Levels. RFC 2119, March 1997. 3329 [5] Josh Broch, David A. Maltz, David B. Johnson, Yih-Chun Hu, 3330 and Jorjeta Jetcheva. A Performance Comparison of Multi-Hop 3331 Wireless Ad Hoc Network Routing Protocols. In Proceedings of 3332 the Fourth Annual ACM/IEEE International Conference on Mobile 3333 Computing and Networking, pages 85--97, October 1998. 3335 [6] Stephen E. Deering and Robert M. Hinden. Internet Protocol 3336 Version 6 (IPv6) Specification. RFC 2460, December 1998. 3338 [7] Ralph Droms. Dynamic Host Configuration Protocol. RFC 2131, 3339 March 1997. 3341 [8] The FreeBSD Project. Project web page available at 3342 http://www.freebsd.org/. 3344 [9] Yih-Chun Hu and David B. Johnson. Caching Strategies in 3345 On-Demand Routing Protocols for Wireless Ad Hoc Networks. In 3346 Proceedings of the Sixth Annual ACM International Conference on 3347 Mobile Computing and Networking, August 2000. 3349 [10] Yih-Chun Hu, David B. Johnson, and David A. Maltz. Flow 3350 State in the Dynamic Source Routing Protocol for Mobile Ad Hoc 3351 Networks. Internet-Draft, draft-ietf-manet-dsrflow-00.txt, 3352 February 2001. Work in progress. 3354 [11] IEEE Computer Society LAN MAN Standards Committee. Wireless 3355 LAN Medium Access Control (MAC) and Physical Layer (PHY) 3356 Specifications, IEEE Std 802.11-1997. The Institute of 3357 Electrical and Electronics Engineers, New York, New York, 1997. 3359 [12] Per Johansson, Tony Larsson, Nicklas Hedman, Bartosz Mielczarek, 3360 and Mikael Degermark. Scenario-based Performance Analysis of 3361 Routing Protocols for Mobile Ad-hoc Networks. In Proceedings 3362 of the Fifth Annual ACM/IEEE International Conference on Mobile 3363 Computing and Networking, pages 195--206, August 1999. 3365 [13] David B. Johnson. Routing in Ad Hoc Networks of Mobile Hosts. 3366 In Proceedings of the IEEE Workshop on Mobile Computing Systems 3367 and Applications, pages 158--163, December 1994. 3369 [14] David B. Johnson and David A. Maltz. Dynamic Source Routing in 3370 Ad Hoc Wireless Networks. In Mobile Computing, edited by Tomasz 3371 Imielinski and Hank Korth, chapter 5, pages 153--181. Kluwer 3372 Academic Publishers, 1996. 3374 [15] David B. Johnson and David A. Maltz. Protocols for Adaptive 3375 Wireless and Mobile Networking. IEEE Personal Communications, 3376 3(1):34--42, February 1996. 3378 [16] John Jubin and Janet D. Tornow. The DARPA Packet Radio Network 3379 Protocols. Proceedings of the IEEE, 75(1):21--32, January 1987. 3381 [17] Phil Karn. MACA---A New Channel Access Method for Packet Radio. 3382 In ARRL/CRRL Amateur Radio 9th Computer Networking Conference, 3383 pages 134--140, September 1990. 3385 [18] Gregory S. Lauer. Packet-Radio Routing. In Routing in 3386 Communications Networks, edited by Martha E. Steenstrup, 3387 chapter 11, pages 351--396. Prentice-Hall, Englewood Cliffs, 3388 New Jersey, 1995. 3390 [19] David A. Maltz, Josh Broch, Jorjeta Jetcheva, and David B. 3391 Johnson. The Effects of On-Demand Behavior in Routing Protocols 3392 for Multi-Hop Wireless Ad Hoc Networks. IEEE Journal on 3393 Selected Areas of Communications, 17(8):1439--1453, August 1999. 3395 [20] David A. Maltz, Josh Broch, and David B. Johnson. Experiences 3396 Designing and Building a Multi-Hop Wireless Ad Hoc Network 3397 Testbed. Technical Report CMU-CS-99-116, School of Computer 3398 Science, Carnegie Mellon University, Pittsburgh, Pennsylvania, 3399 March 1999. 3401 [21] David A. Maltz, Josh Broch, and David B. Johnson. Quantitative 3402 Lessons From a Full-Scale Multi-Hop Wireless Ad Hoc Network 3403 Testbed. In Proceedings of the IEEE Wireless Communications and 3404 Networking Conference, September 2000. 3406 [22] David A. Maltz, Josh Broch, and David B. Johnson. Lessons From 3407 a Full-Scale MultiHop Wireless Ad Hoc Network Testbed. IEEE 3408 Personal Communications, 8(1):8--15, February 2001. 3410 [23] The Network Simulator -- ns-2. Project web page available at 3411 http://www.isi.edu/nsnam/ns/. 3413 [24] Radia Perlman. Interconnections: Bridges and Routers. 3414 Addison-Wesley, Reading, Massachusetts, 1992. 3416 [25] David C. Plummer. An Ethernet Address Resolution Protocol: 3417 Or Converting Network Protocol Addresses to 48.bit Ethernet 3418 Addresses for Transmission on Ethernet Hardware. RFC 826, 3419 November 1982. 3421 [26] J. B. Postel, editor. Internet Control Message Protocol. 3422 RFC 792, September 1981. 3424 [27] J. B. Postel, editor. Internet Protocol. RFC 791, September 3425 1981. 3427 [28] J. B. Postel, editor. Transmission Control Protocol. RFC 793, 3428 September 1981. 3430 [29] Joyce K. Reynolds and Jon Postel. Assigned Numbers. RFC 1700, 3431 October 1994. See also http://www.iana.org/numbers.html. 3433 [30] Rice University Monarch Project. Monarch Project Home Page. 3434 Available at http://www.monarch.cs.rice.edu/. 3436 [31] Alex Song. picoNet II: A Wireless Ad Hoc Network for Mobile 3437 Handheld Devices. Submitted for the degree of Bachelor of 3438 Engineering (Honours) in the division of Electrical Engineering, 3439 Department of Information Technology and Electrical Engineering, 3440 University of Queensland, Australia, October 2001. Available at 3441 http://student.uq.edu.au/~s369677/main.html. 3443 [32] Paul Turner. NetWare Communications Processes. NetWare 3444 Application Notes, Novell Research, pages 25--91, September 3445 1990. 3447 [33] Gary R. Wright and W. Richard Stevens. TCP/IP Illustrated, 3448 Volume 2: The Implementation. Addison-Wesley, Reading, 3449 Massachusetts, 1995. 3451 Chair's Address 3453 The MANET Working Group can be contacted via its current chairs: 3455 M. Scott Corson Phone: +1 908 947-7033 3456 Flarion Technologies, Inc. Email: corson@flarion.com 3457 Bedminster One 3458 135 Route 202/206 South 3459 Bedminster, NJ 07921 3460 USA 3462 Joseph Macker Phone: +1 202 767-2001 3463 Information Technology Division Email: macker@itd.nrl.navy.mil 3464 Naval Research Laboratory 3465 Washington, DC 20375 3466 USA 3468 Authors' Addresses 3470 Questions about this document can also be directed to the authors: 3472 David B. Johnson Phone: +1 713 348-3063 3473 Rice University Fax: +1 713 348-5930 3474 Computer Science Department, MS 132 Email: dbj@cs.rice.edu 3475 6100 Main Street 3476 Houston, TX 77005-1892 3477 USA 3479 David A. Maltz Phone: +1 650 688-3128 3480 AON Networks Fax: +1 650 688-3119 3481 3045 Park Blvd. Email: dmaltz@cs.cmu.edu 3482 Palo Alto, CA 94306 3483 USA 3485 Yih-Chun Hu Phone: +1 412 268-3075 3486 Rice University Fax: +1 412 268-5576 3487 Computer Science Department, MS 132 Email: yihchun@cs.cmu.edu 3488 6100 Main Street 3489 Houston, TX 77005-1892 3490 USA 3492 Jorjeta G. Jetcheva Phone: +1 412 268-3053 3493 Carnegie Mellon University Fax: +1 412 268-5576 3494 Computer Science Department Email: jorjeta@cs.cmu.edu 3495 5000 Forbes Avenue 3496 Pittsburgh, PA 15213-3891 3497 USA