idnits 2.17.1 draft-ietf-manet-dsr-05.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). == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'SHOULD not' in this paragraph: As node C forwards a data packet along the route from A to E, it MAY add to its cache the presence of the "forward" direction links that it learns from the headers of these packets, from itself to D and from D to E. However, the "reverse" direction of the links identified in the packet headers, from itself back to B and from B to A, may not work for it since these links might be uni-directional. If C knows that the links are in fact bi-directional, for example due to the MAC protocol in use, it could cache them but otherwise SHOULD not. -- 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' -- Possible downref: Non-RFC (?) normative reference: ref. '6' ** Obsolete normative reference: RFC 2460 (ref. '7') (Obsoleted by RFC 8200) -- Possible downref: Non-RFC (?) normative reference: ref. '9' -- Possible downref: Non-RFC (?) normative reference: ref. '10' -- Possible downref: Non-RFC (?) normative reference: ref. '11' -- Possible downref: Non-RFC (?) normative reference: ref. '12' -- Possible downref: Non-RFC (?) normative reference: ref. '13' -- 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' ** Obsolete normative reference: RFC 793 (ref. '25') (Obsoleted by RFC 9293) ** Obsolete normative reference: RFC 1700 (ref. '26') (Obsoleted by RFC 3232) -- Possible downref: Non-RFC (?) normative reference: ref. '27' Summary: 5 errors (**), 0 flaws (~~), 3 warnings (==), 20 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 2 March 2001 Yih-Chun Hu, Rice University 4 Jorjeta G. Jetcheva, Carnegie Mellon University 6 The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks 8 10 Status of This Memo 12 This document is an Internet-Draft and is in full conformance with 13 all provisions of Section 10 of RFC 2026 except that the right to 14 produce derivative works is not granted. 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 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 IP 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 69 3.1. Basic DSR Route Discovery . . . . . . . . . . . . . . . . 5 70 3.2. Basic DSR Route Maintenance . . . . . . . . . . . . . . . 7 71 3.3. Additional Route Discovery Features . . . . . . . . . . . 8 72 3.3.1. Caching Overheard Routing Information . . . . . . 8 73 3.3.2. Replying to Route Requests using Cached Routes . 9 74 3.3.3. Preventing Route Reply Storms . . . . . . . . . . 10 75 3.3.4. Route Request Hop Limits . . . . . . . . . . . . 12 76 3.4. Additional Route Maintenance Features . . . . . . . . . . 13 77 3.4.1. Packet Salvaging . . . . . . . . . . . . . . . . 13 78 3.4.2. Automatic Route Shortening . . . . . . . . . . . 13 79 3.4.3. Increased Spreading of Route Error Messages . . . 14 81 4. Conceptual Data Structures 15 82 4.1. Route Cache . . . . . . . . . . . . . . . . . . . . . . . 15 83 4.2. Route Request Table . . . . . . . . . . . . . . . . . . . 17 84 4.3. Send Buffer . . . . . . . . . . . . . . . . . . . . . . . 18 85 4.4. Retransmission Buffer . . . . . . . . . . . . . . . . . . 19 87 5. DSR Header Format 20 88 5.1. Fixed Portion of DSR Header . . . . . . . . . . . . . . . 21 89 5.2. Route Request Option . . . . . . . . . . . . . . . . . . 23 90 5.3. Route Reply Option . . . . . . . . . . . . . . . . . . . 25 91 5.4. Route Error Option . . . . . . . . . . . . . . . . . . . 27 92 5.5. Acknowledgment Request Option . . . . . . . . . . . . . . 29 93 5.6. Acknowledgment Option . . . . . . . . . . . . . . . . . . 30 94 5.7. Source Route Option . . . . . . . . . . . . . . . . . . . 31 95 5.8. Pad1 Option . . . . . . . . . . . . . . . . . . . . . . . 33 96 5.9. PadN Option . . . . . . . . . . . . . . . . . . . . . . . 34 98 6. Detailed Operation 35 99 6.1. General Packet Processing . . . . . . . . . . . . . . . . 35 100 6.1.1. Originating a Packet . . . . . . . . . . . . . . 35 101 6.1.2. Adding a DSR Header to a Packet . . . . . . . . . 35 102 6.1.3. Adding a Source Route Option to a Packet . . . . 36 103 6.1.4. Receiving a Packet . . . . . . . . . . . . . . . 36 104 6.1.5. Processing a Received Source Route Option . . . . 38 105 6.2. Route Discovery Processing . . . . . . . . . . . . . . . 40 106 6.2.1. Originating a Route Request . . . . . . . . . . . 40 107 6.2.2. Processing a Received Route Request Option . . . 42 108 6.2.3. Generating Route Replies using the Route Cache . 43 109 6.2.4. Originating a Route Reply . . . . . . . . . . . . 44 110 6.2.5. Processing a Route Reply Option . . . . . . . . . 46 111 6.3. Route Maintenance Processing . . . . . . . . . . . . . . 47 112 6.3.1. Using Network-Layer Acknowledgments . . . . . . . 47 113 6.3.2. Using Link Layer Acknowledgments . . . . . . . . 48 114 6.3.3. Originating a Route Error . . . . . . . . . . . . 48 115 6.3.4. Processing a Route Error Option . . . . . . . . . 49 116 6.3.5. Salvaging a Packet . . . . . . . . . . . . . . . 49 118 7. Constants 50 120 8. IANA Considerations 51 122 9. Security Considerations 52 124 Appendix A. Location of DSR in the ISO Network Reference Model 53 126 Appendix B. Implementation and Evaluation Status 54 128 Acknowledgements 55 130 References 56 132 Chair's Address 59 134 Authors' Addresses 60 135 1. Introduction 137 The Dynamic Source Routing protocol (DSR) [12, 13] is a simple and 138 efficient routing protocol designed specifically for use in multi-hop 139 wireless ad hoc networks of mobile nodes. Using DSR, the network 140 is completely self-organizing and self-configuring, requiring no 141 existing network infrastructure or administration. Network nodes 142 cooperate to forward packets for each other to allow communication 143 over multiple "hops" between nodes not directly within wireless 144 transmission range of one another. As nodes in the network move 145 about or join or leave the network, and as wireless transmission 146 conditions such as sources of interference change, all routing is 147 automatically determined and maintained by the DSR routing protocol. 148 Since the number or sequence of intermediate hops needed to reach any 149 destination may change at any time, the resulting network topology 150 may be quite rich and rapidly changing. 152 The DSR protocol allows nodes to dynamically discover a source 153 route across multiple network hops to any destination in the ad hoc 154 network. Each data packet sent then carries in its header the 155 complete, ordered list of nodes through which the packet will pass, 156 allowing packet routing to be trivially loop-free and avoiding the 157 need for up-to-date routing information in the intermediate nodes 158 through which the packet is forwarded. By including this source 159 route in the header of each data packet, other nodes forwarding or 160 overhearing any of these packets may also easily cache this routing 161 information for future use. 163 In designing DSR, we sought to create a routing protocol that had 164 very low overhead yet was able to react quickly to changes in the 165 network. The DSR protocol provides highly reactive service to help 166 ensure successful delivery of data packets in spite of node movement 167 or other changes in network conditions. 169 The DSR protocol is composed of two mechanisms that work together to 170 allow the discovery and maintenance of source routes in the ad hoc 171 network: 173 - Route Discovery is the mechanism by which a node S wishing to 174 send a packet to a destination node D obtains a source route 175 to D. Route Discovery is used only when S attempts to send a 176 packet to D and does not already know a route to D. 178 - Route Maintenance is the mechanism by which node S is able 179 to detect, while using a source route to D, if the network 180 topology has changed such that it can no longer use its route 181 to D because a link along the route no longer works. When Route 182 Maintenance indicates a source route is broken, S can attempt to 183 use any other route it happens to know to D, or can invoke Route 184 Discovery again to find a new route for subsequent packets to D. 186 Route Maintenance for this route is used only when S is actually 187 sending packets to D. 189 In DSR, Route Discovery and Route Maintenance each operate entirely 190 "on demand". In particular, unlike other protocols, DSR requires no 191 periodic packets of any kind at any level within the network. For 192 example, DSR does not use any periodic routing advertisement, link 193 status sensing, or neighbor detection packets, and does not rely on 194 these functions from any underlying protocols in the network. This 195 entirely on-demand behavior and lack of periodic activity allows 196 the number of overhead packets caused by DSR to scale all the way 197 down to zero, when all nodes are approximately stationary with 198 respect to each other and all routes needed for current communication 199 have already been discovered. As nodes begin to move more or 200 as communication patterns change, the routing packet overhead of 201 DSR automatically scales to only that needed to track the routes 202 currently in use. Network topology changes not affecting routes 203 currently in use are ignored and do not cause reaction from the 204 protocol. 206 In response to a single Route Discovery (as well as through routing 207 information from other packets overheard), a node may learn and cache 208 multiple routes to any destination. This allows the reaction to 209 routing changes to be much more rapid, since a node with multiple 210 routes to a destination can try another cached route if the one it 211 has been using should fail. This caching of multiple routes also 212 avoids the overhead of needing to perform a new Route Discovery each 213 time a route in use breaks. 215 The operation of both Route Discovery and Route Maintenance in DSR 216 are designed to allow uni-directional links and asymmetric routes 217 to be easily supported. In particular, as noted in Section 2, in 218 wireless networks, it is possible that a link between two nodes may 219 not work equally well in both directions, due to differing antenna 220 or propagation patterns or sources of interference. DSR allows such 221 uni-directional links to be used when necessary, improving overall 222 performance and network connectivity in the system. 224 This document specifies the operation of the DSR protocol for routing 225 unicast IP packets in multi-hop wireless ad hoc networks. Advanced, 226 optional features, such as Quality of Service (QoS) support and 227 efficient multicast routing, are covered in other documents. The 228 specification of DSR in this document provides a compatible base 229 on which such features can be added, either independently or by 230 integration with the DSR operation specified here. 232 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 233 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 234 document are to be interpreted as described in RFC 2119 [4]. 236 2. Assumptions 238 We assume that all nodes wishing to communicate with other nodes 239 within the ad hoc network are willing to participate fully in the 240 protocols of the network. In particular, each node participating in 241 the network SHOULD also be willing to forward packets for other nodes 242 in the network. 244 The diameter of an ad hoc network is the minimum number of hops 245 necessary for a packet to reach from any node located at one extreme 246 edge of the ad hoc network to another node located at the opposite 247 extreme. We assume that this diameter will often be small (e.g., 248 perhaps 5 or 10 hops), but may often be greater than 1. 250 Packets may be lost or corrupted in transmission on the wireless 251 network. We assume that a node receiving a corrupted packet can 252 detect the error and discard the packet. 254 Nodes within the ad hoc network MAY move at any time without notice, 255 and MAY even move continuously, but we assume that the speed with 256 which nodes move is moderate with respect to the packet transmission 257 latency and wireless transmission range of the particular underlying 258 network hardware in use. In particular, DSR can support very 259 rapid rates of arbitrary node mobility, but we assume that nodes do 260 not continuously move so rapidly as to make the flooding of every 261 individual data packet the only possible routing protocol. 263 A common feature of many network interfaces, including most current 264 LAN hardware for broadcast media such as wireless, is the ability 265 to operate the network interface in "promiscuous" receive mode. 266 This mode causes the hardware to deliver every received packet to 267 the network driver software without filtering based on link-layer 268 destination address. Although we do not require this facility, some 269 of our optimizations can take advantage of its availability. Use 270 of promiscuous mode does increase the software overhead on the CPU, 271 but we believe that wireless network speeds are more the inherent 272 limiting factor to performance in current and future systems; we also 273 believe that portions of the protocol are suitable for implementation 274 directly within a programmable network interface unit to avoid this 275 overhead on the CPU [13]. Use of promiscuous mode may also increase 276 the power consumption of the network interface hardware, depending 277 on the design of the receiver hardware, and in such cases, DSR can 278 easily be used without the optimizations that depend on promiscuous 279 receive mode, or can be programmed to only periodically switch the 280 interface into promiscuous mode. Use of promiscuous receive mode is 281 entirely optional. 283 Wireless communication ability between any pair of nodes may at 284 times not work equally well in both directions, due for example to 285 differing antenna or propagation patterns or sources of interference 286 around the two nodes [1, 17]. That is, wireless communications 287 between each pair of nodes will in many cases be able to operate 288 bi-directionally, but at times the wireless link between two nodes 289 may be only uni-directional, allowing one node to successfully send 290 packets to the other while no communication is possible in the 291 reverse direction. Although many routing protocols operate correctly 292 only over bi-directional links, DSR can successfully discover and 293 forward packets over paths that contain uni-directional links. 294 Some MAC protocols, however, such as MACA [16], MACAW [2], or IEEE 295 802.11 [10], limit unicast data packet transmission to bi-directional 296 links, due to the required bi-directional exchange of RTS and CTS 297 packets in these protocols and due to the link-level acknowledgement 298 feature in IEEE 802.11; when used on top of MAC protocols such as 299 these, DSR can take advantage of additional optimizations, such as 300 the easy ability to reverse a source route to obtain a route back to 301 the origin of the original route. 303 The IP address used by a node using the DSR protocol MAY be assigned 304 by any mechanism (e.g., static assignment or use of DHCP for dynamic 305 assignment [8]), although the method of such assignment is outside 306 the scope of this specification. 308 3. DSR Protocol Overview 310 3.1. Basic DSR Route Discovery 312 When some source node originates a new packet addressed to some 313 destination node, the source node places in the header of the packet 314 a source route giving the sequence of hops that the packet is to 315 follow on its way to the destination. Normally, the sender will 316 obtain a suitable source route by searching its "Route Cache" of 317 routes previously learned, but if no route is found in its cache, it 318 will initiate the Route Discovery protocol to dynamically find a new 319 route to this destination node. In this case, we call the source 320 node the "initiator" and the destination node the "target" of the 321 Route Discovery. 323 For example, suppose a node A is attempting to discover a route to 324 node E. The Route Discovery initiated by node A in this example 325 would proceed as follows: 327 ^ "A" ^ "A,B" ^ "A,B,C" ^ "A,B,C,D" 328 | id=2 | id=2 | id=2 | id=2 329 +-----+ +-----+ +-----+ +-----+ +-----+ 330 | A |---->| B |---->| C |---->| D |---->| E | 331 +-----+ +-----+ +-----+ +-----+ +-----+ 332 | | | | 333 v v v v 335 To initiate the Route Discovery, node A transmits a "Route 336 Request" as a single local broadcast packet, which is received by 337 (approximately) all nodes currently within wireless transmission 338 range of A, including node B in this example. Each Route Request 339 identifies the initiator and target of the Route Discovery, and 340 also contains a unique request identification (2, in this example), 341 determined by the initiator of the Request. Each Route Request also 342 contains a record listing the address of each intermediate node 343 through which this particular copy of the Route Request has been 344 forwarded. This route record is initialized to an empty list by the 345 initiator of the Route Discovery. In this example, the route record 346 initially lists only node A. 348 When another node receives this Route Request (such as node B in this 349 example), if it is the target of the Route Discovery, it returns 350 a "Route Reply" to the initiator of the Route Discovery, giving 351 a copy of the accumulated route record from the Route Request; 352 when the initiator receives this Route Reply, it caches this route 353 in its Route Cache for use in sending subsequent packets to this 354 destination. 356 Otherwise, if this node receiving the Route Request has recently seen 357 another Route Request message from this initiator bearing this same 358 request identification and target address, or if this node's own 359 address is already listed in the route record in the Route Request, 360 this node discards the Request. Otherwise, this node appends its 361 own address to the route record in the Route Request and propagates 362 it by transmitting it as a local broadcast packet (with the same 363 request identification). In this example, node B broadcast the Route 364 Request, which is received by node C; nodes C and D each also, in 365 turn, broadcast the Request, resulting in a copy of the Request being 366 received by node E. 368 In returning the Route Reply to the initiator of the Route Discovery, 369 such as in this example, node E replying back to node A, node E will 370 typically examine its own Route Cache for a route back to A, and if 371 found, will use it for the source route for delivery of the packet 372 containing the Route Reply. Otherwise, E SHOULD perform its own 373 Route Discovery for target node A, but to avoid possible infinite 374 recursion of Route Discoveries, it MUST piggyback this Route Reply 375 on the packet containing its own Route Request for A. It is also 376 possible to piggyback other small data packets, such as a TCP SYN 377 packet [25], on a Route Request using this same mechanism. 379 Node E could instead simply reverse the sequence of hops in the route 380 record that it is trying to send in the Route Reply, and use this 381 as the source route on the packet carrying the Route Reply itself. 382 For MAC protocols such as IEEE 802.11 that require a bi-directional 383 frame exchange as part of the MAC protocol [10], this route reversal 384 is preferred, as it avoids the overhead of a possible second 385 Route Discovery, and it tests the discovered route to ensure it is 386 bi-directional before the Route Discovery initiator begins using the 387 route. However, this technique will prevent the discovery of routes 388 using uni-directional links. In wireless environments where the use 389 of uni-directional links is permitted, such routes may in some cases 390 be more efficient than those with only bi-directional links, or they 391 may be the only way to achieve connectivity to the target node. 393 When initiating a Route Discovery, the sending node saves a copy of 394 the original packet (that triggered the Discovery) in a local buffer 395 called the "Send Buffer". The Send Buffer contains a copy of each 396 packet that cannot be transmitted by this node because it does not 397 yet have a source route to the packet's destination. Each packet in 398 the Send Buffer is logically associated with the time that it was 399 placed into the Send Buffer and is discarded after residing in the 400 Send Buffer for some timeout period; if necessary for preventing the 401 Send Buffer from overflowing, a FIFO or other replacement strategy 402 MAY also be used to evict packets even before they expire. 404 While a packet remains in the Send Buffer, the node SHOULD 405 occasionally initiate a new Route Discovery for the packet's 406 destination address. However, the node MUST limit the rate at which 407 such new Route Discoveries for the same address are initiated, since 408 it is possible that the destination node is not currently reachable. 409 In particular, due to the limited wireless transmission range and the 410 movement of the nodes in the network, the network may at times become 411 partitioned, meaning that there is currently no sequence of nodes 412 through which a packet could be forwarded to reach the destination. 413 Depending on the movement pattern and the density of nodes in the 414 network, such network partitions may be rare or may be common. 416 If a new Route Discovery was initiated for each packet sent by a 417 node in such a partitioned network, a large number of unproductive 418 Route Request packets would be propagated throughout the subset of 419 the ad hoc network reachable from this node. In order to reduce the 420 overhead from such Route Discoveries, a node MUST use an exponential 421 back-off algorithm to limit the rate at which it initiates new Route 422 Discoveries for the same target. If the node attempts to send 423 additional data packets to this same destination node more frequently 424 than this limit, the subsequent packets SHOULD be buffered in the 425 Send Buffer until a Route Reply is received giving a route to this 426 destination, but the node MUST NOT initiate a new Route Discovery 427 until the minimum allowable interval between new Route Discoveries 428 for this target has been reached. This limitation on the maximum 429 rate of Route Discoveries for the same target is similar to the 430 mechanism required by Internet nodes to limit the rate at which ARP 431 Requests are sent for any single target IP address [3]. 433 3.2. Basic DSR Route Maintenance 435 When originating or forwarding a packet using a source route, each 436 node transmitting the packet is responsible for confirming that the 437 packet has been received by the next hop along the source route; the 438 packet SHOULD be retransmitted (up to a maximum number of attempts) 439 until this confirmation of receipt is received. For example, in the 440 situation shown below, node A has originated a packet for node E 441 using a source route through intermediate nodes B, C, and D: 443 +-----+ +-----+ +-----+ +-----+ +-----+ 444 | A |---->| B |---->| C |--x | D | | E | 445 +-----+ +-----+ +-----+ +-----+ +-----+ 447 In this case, node A is responsible for receipt of the packet at B, 448 node B is responsible for receipt at C, node C is responsible for 449 receipt at D, and node D is responsible for receipt finally at the 450 destination E. 452 This confirmation of receipt in many cases may be provided at no cost 453 to DSR, either as an existing standard part of the MAC protocol in 454 use (such as the link-level acknowledgement frame defined by IEEE 455 802.11 [10]), or by a "passive acknowledgement" [15] (in which, 456 for example, B confirms receipt at C by overhearing C transmit the 457 packet when forwarding it on to D). If neither of these confirmation 458 mechanisms are available, the node transmitting the packet can 459 explicitly request a DSR-specific software acknowledgement be 460 returned by the next hop; this software acknowledgement will normally 461 be transmitted directly to the sending node, but if the link between 462 these two nodes is uni-directional, this software acknowledgement may 463 travel over a different, multi-hop path. 465 If no receipt confirmation is received after the packet has been 466 retransmitted the maximum number of attempts by some hop, this node 467 SHOULD return a "Route Error" to the original sender of the packet, 468 identifying the link over which the packet could not be forwarded. 469 For example, in the example shown above, if C is unable to deliver 470 the packet to the next hop D, then C returns a Route Error to A, 471 stating that the link from C to D is currently "broken". Node A 472 then removes this broken link from its cache; any retransmission of 473 the original packet can be performed by upper layer protocols such 474 as TCP, if necessary. For sending such a retransmission or other 475 packets to this same destination E, if A has in its Route Cache 476 another route to E (for example, from additional Route Replies from 477 its earlier Route Discovery, or from having overheard sufficient 478 routing information from other packets), it can send the packet 479 using the new route immediately. Otherwise, it SHOULD perform a new 480 Route Discovery for this target (subject to the exponential back-off 481 described in Section 3.1). 483 3.3. Additional Route Discovery Features 485 3.3.1. Caching Overheard Routing Information 487 A node forwarding or otherwise overhearing any packet MAY add the 488 routing information from that packet to its own Route Cache. In 489 particular, the source route used in a data packet, the accumulated 490 route record in a Route Request, or the route being returned in a 491 Route Reply MAY all be cached by any node. Routing information from 492 any of these packets received can be cached, whether the packet 493 was addressed to this node, sent to a broadcast (or multicast) 494 MAC address, or received while the node's network interface is in 495 promiscuous mode. 497 One limitation, however, on caching of such overheard routing 498 information is the possible presence of uni-directional links in the 499 ad hoc network (Section 2). For example, in the situation shown 500 below, node A is using a source route to communicate with node E: 502 +-----+ +-----+ +-----+ +-----+ +-----+ 503 | A |---->| B |---->| C |---->| D |---->| E | 504 +-----+ +-----+ +-----+ +-----+ +-----+ 505 ^ 506 | 507 +-----+ +-----+ +-----+ +-----+ +-----+ 508 | V |---->| W |---->| X |---->| Y |---->| Z | 509 +-----+ +-----+ +-----+ +-----+ +-----+ 511 As node C forwards a data packet along the route from A to E, it 512 MAY add to its cache the presence of the "forward" direction links 513 that it learns from the headers of these packets, from itself to D 514 and from D to E. However, the "reverse" direction of the links 515 identified in the packet headers, from itself back to B and from B 516 to A, may not work for it since these links might be uni-directional. 517 If C knows that the links are in fact bi-directional, for example due 518 to the MAC protocol in use, it could cache them but otherwise SHOULD 519 not. 521 Likewise, node V in the example above is using a different source 522 route to communicate with node Z. If node C overhears node X 523 transmitting a data packet to forward it to Y (from V), node C SHOULD 524 consider whether the links involved can be known to be bi-directional 525 or not before caching them. If the link from X to C (over which this 526 data packet was received) can be known to be bi-directional, then C 527 MAY cache the link from itself to X, the link from X to Y, and the 528 link from Y to Z. If all links can be assumed to be bi-directional, 529 C MAY also cache the links from X to W and from W to V. Similar 530 considerations apply to the routing information that might be learned 531 from forwarded or otherwise overheard Route Request or Route Reply 532 packets. 534 3.3.2. Replying to Route Requests using Cached Routes 536 A node receiving a Route Request for which it is not the target, 537 searches its own Route Cache for a route to the target of the 538 Request. If found, the node generally returns a Route Reply to the 539 initiator itself rather than forwarding the Route Request. In the 540 Route Reply, this node sets the route record to list the sequence of 541 hops over which this copy of the Route Request was forwarded to it, 542 concatenated with the source route to this target obtained from its 543 own Route Cache. 545 However, before transmitting a Route Reply packet that was generated 546 using information from its Route Cache in this way, a node MUST 547 verify that the resulting route being returned in the Route Reply, 548 after this concatenation, contains no duplicate nodes listed in the 549 route record. For example, the figure below illustrates a case in 550 which a Route Request for target E has been received by node F, and 551 node F already has in its Route Cache a route from itself to E: 553 +-----+ +-----+ +-----+ +-----+ 554 | A |---->| B |- >| D |---->| E | 555 +-----+ +-----+ \ / +-----+ +-----+ 556 \ / 557 \ +-----+ / 558 >| C |- 559 +-----+ 560 | ^ 561 v | 562 Route Request +-----+ 563 Route: A - B - C - F | F | Cache: C - D - E 564 +-----+ 566 The concatenation of the accumulated route record from the Route 567 Request and the cached route from F's Route Cache would include a 568 duplicate node in passing from C to F and back to C. 570 Node F in this case could attempt to edit the route to eliminate the 571 duplication, resulting in a route from A to B to C to D and on to E, 572 but in this case, node F would not be on the route that it returned 573 in its own Route Reply. DSR Route Discovery prohibits node F from 574 returning such a Route Reply from its cache for two reasons. First, 575 this limitation increases the probability that the resulting route 576 is valid, since node F in this case should have received a Route 577 Error if the route had previously stopped working. Second, this 578 limitation means that a Route Error traversing the route is very 579 likely to pass through any node that sent the Route Reply for the 580 route (including node F), which helps to ensure that stale data is 581 removed from caches (such as at F) in a timely manner. Otherwise, 582 the next Route Discovery initiated by A might also be contaminated by 583 a Route Reply from F containing the same stale route. If the Route 584 Request does not meet these restrictions, the node (node F in this 585 example) discards the Route Request rather than replying to it or 586 propagating it. 588 3.3.3. Preventing Route Reply Storms 590 The ability for nodes to reply to a Route Request based on 591 information in their Route Caches, as described in Section 3.3.2, 592 could result in a possible Route Reply "storm" in some cases. In 593 particular, if a node broadcasts a Route Request for a target node 594 for which the node's neighbors have a route in their Route Caches, 595 each neighbor may attempt to send a Route Reply, thereby wasting 596 bandwidth and possibly increasing the number of network collisions in 597 the area. 599 For example, the figure below shows a situation in which nodes B, C, 600 D, E, and F all receive A's Route Request for target G, and each has 601 the indicated route cached for this target: 603 +-----+ +-----+ 604 | D |< >| C | 605 +-----+ \ / +-----+ 606 Cache: C - B - G \ / Cache: B - G 607 \ +-----+ / 608 -| A |- 609 +-----+\ +-----+ +-----+ 610 | | \--->| B | | G | 611 / \ +-----+ +-----+ 612 / \ Cache: G 613 v v 614 +-----+ +-----+ 615 | E | | F | 616 +-----+ +-----+ 617 Cache: F - B - G Cache: B - G 619 Normally, these nodes would all attempt to reply from their own 620 Route Caches, and would all send their Route Replies at about the 621 same time, since they all received the broadcast Route Request at 622 about the same time. Such simultaneous replies from different nodes 623 all receiving the Route Request may create packet collisions among 624 some or all of these Replies and may cause local congestion in the 625 wireless network. In addition, it will often be the case that the 626 different replies will indicate routes of different lengths, as shown 627 in this example. 629 If a node can put its network interface into promiscuous receive 630 mode, it SHOULD delay sending its own Route Reply for a short period, 631 while listening to see if the initiating node begins using a shorter 632 route first. That is, this node SHOULD delay sending its own Route 633 Reply for a random period 635 d = H * (h - 1 + r) 637 where h is the length in number of network hops for the route to be 638 returned in this node's Route Reply, r is a random floating point 639 number between 0 and 1, and H is a small constant delay (at least 640 twice the maximum wireless link propagation delay) to be introduced 641 per hop. This delay effectively randomizes the time at which each 642 node sends its Route Reply, with all nodes sending Route Replies 643 giving routes of length less than h sending their Replies before this 644 node, and all nodes sending Route Replies giving routes of length 645 greater than h sending their Replies after this node. 647 Within the delay period, this node promiscuously receives all 648 packets, looking for data packets from the initiator of this Route 649 Discovery destined for the target of the Discovery. If such a data 650 packet received by this node during the delay period uses a source 651 route of length less than or equal to h, this node may infer that the 652 initiator of the Route Discovery has already received a Route Reply 653 giving an equally good or better route. In this case, this node 654 SHOULD cancel its delay timer and SHOULD NOT send its Route Reply for 655 this Route Discovery. 657 3.3.4. Route Request Hop Limits 659 Each Route Request message contains a "hop limit" that may be used 660 to limit the number of intermediate nodes allowed to forward that 661 copy of the Route Request. This hop limit is implemented using the 662 Time-to-Live (TTL) field in the IP header of the packet carrying 663 the Route Request. As the Request is forwarded, this limit is 664 decremented, and the Request packet is discarded if the limit reaches 665 zero before finding the target. 667 This Route Request hop limit can be used to implement a variety of 668 algorithms for controlling the spread of a Route Request during a 669 Route Discovery attempt. For example, a node MAY send its first 670 Route Request attempt for some target node using a hop limit of 1, 671 such that any node receiving the initial transmission of the Route 672 Request will not forward the Request to other nodes by rebroadcasting 673 it. This form of Route Request is called a "non-propagating" 674 Route Request. It provides an inexpensive method for determining 675 if the target is currently a neighbor of the initiator or if a 676 neighbor node has a route to the target cached (effectively using the 677 neighbors' Route Caches as an extension of the initiator's own Route 678 Cache). If no Route Reply is received after a short timeout, then a 679 "propagating" Route Request (i.e., with no hop limit) MAY be sent. 681 Another possible use of the hop limit in a Route Request is to 682 implement an "expanding ring" search for the target [13]. For 683 example, a node could send an initial non-propagating Route Request 684 as described above; if no Route Reply is received for it, the node 685 could initiate another Route Request with a hop limit of 2. For 686 each Route Request initiated, if no Route Reply is received for it, 687 the node could double the hop limit used on the previous attempt, 688 to progressively explore for the target node without allowing the 689 Route Request to propagate over the entire network. However, this 690 expanding ring search approach could have the effect of increasing 691 the average latency of Route Discovery, since multiple Discovery 692 attempts and timeouts may be needed before discovering a route to the 693 target node. 695 3.4. Additional Route Maintenance Features 697 3.4.1. Packet Salvaging 699 After sending a Route Error message as part of Route Maintenance 700 as described in Section 3.2, a node MAY attempt to "salvage" the 701 data packet that caused the Route Error rather than discarding the 702 packet. To attempt to salvage a packet, the node sending a Route 703 Error searches its own Route Cache for a route from itself to the 704 destination of the packet causing the Error. If such a route is 705 found, the node MAY salvage the packet after returning the Route 706 Error by replacing the original source route on the packet with the 707 route from its Route Cache. The node then forwards the packet to the 708 next node indicated along this source route. For example, in the 709 situation shown in the example of Section 3.2, if node C has another 710 route cached to node E, it can salvage the packet by replacing the 711 original route in the packet with this new route from its own Route 712 Cache, rather than discarding the packet. 714 When salvaging a packet in this way, a count is maintained in the 715 packet of the number of times that it has been salvaged, to prevent a 716 single packet from being salvaged endlessly. Otherwise, it could be 717 possible for the packet to enter a routing loop, as different nodes 718 repeatedly salvage the packet and replace the source route on the 719 packet with routes to each other. 721 3.4.2. Automatic Route Shortening 723 Source routes in use MAY be automatically shortened if one or more 724 intermediate hops in the route become no longer necessary. This 725 mechanism of automatically shortening routes in use is somewhat 726 similar to the use of passive acknowledgements [15]. In particular, 727 if a node is able to overhear a packet carrying a source route (e.g., 728 by operating its network interface in promiscuous receive mode), then 729 this node examines the unused portion of that source route. If this 730 node is not the intended next hop for the packet but is named in 731 the later unused portion of the packet's source route, then it can 732 infer that the intermediate nodes before itself in the source route 733 are no longer needed in the route. For example, the figure below 734 illustrates an example in which node D has overheard a data packet 735 being transmitted from B to C, for later forwarding to D and to E: 737 +-----+ +-----+ +-----+ +-----+ +-----+ 738 | A |---->| B |---->| C | | D | | E | 739 +-----+ +-----+ +-----+ +-----+ +-----+ 740 \ ^ 741 \ / 742 --------------------- 744 In this case, this node (node D) returns a "gratuitous" Route Reply 745 to the original sender of the packet (node A). The Route Reply 746 gives the shorter route as the concatenation of the portion of the 747 original source route up through the node that transmitted the 748 overheard packet (node B), plus the suffix of the original source 749 route beginning with the node returning the gratuitous Route Reply 750 (node D). In this example, the route returned in the gratuitous Route 751 Reply message sent from D to A gives the new route as the sequence of 752 hops from A to B to D to E. 754 3.4.3. Increased Spreading of Route Error Messages 756 When a source node receives a Route Error for a data packet that 757 it originated, this source node propagates this Route Error to its 758 neighbors by piggybacking it on its next Route Request. In this way, 759 stale information in the caches of nodes around this source node will 760 not generate Route Replies that contain the same invalid link for 761 which this source node received the Route Error. 763 For example, in the situation shown in the example of Section 3.2, 764 node A learns from the Route Error message from C, that the link 765 from C to D is currently broken. It thus removes this link from 766 its own Route Cache and initiates a new Route Discovery (if it has 767 no other route to E in its Route Cache). On the Route Request 768 packet initiating this Route Discovery, node A piggybacks a copy 769 of this Route Error, ensuring that the Route Error spreads well to 770 other nodes, and guaranteeing that any Route Reply that it receives 771 (including those from other node's Route Caches) in response to this 772 Route Request does not contain a route that assumes the existence of 773 this broken link. 775 4. Conceptual Data Structures 777 This document describes the operation of the DSR protocol in terms 778 of a number of conceptual data structures. This section describes 779 each of these data structures and provides an overview of its use 780 in the protocol. In an implementation of the protocol, these data 781 structures MAY be implemented in any manner consistent with the 782 external behavior described in this document. 784 4.1. Route Cache 786 All routing information needed by a node participating in an ad hoc 787 network using DSR is stored in that node's Route Cache. Each node in 788 the network maintains its own Route Cache. A node adds information 789 to its Route Cache as it learns of new links between nodes in the 790 ad hoc network; for example, a node may learn of new links when it 791 receives a packet carrying either a Route Reply or a DSR Routing 792 header. Likewise, a node removes information from its Route Cache as 793 it learns that existing links in the ad hoc network have broken; for 794 example, a node may learn of a broken link when it receives a packet 795 carrying a Route Error or through the link-layer retransmission 796 mechanism reporting a failure in forwarding a packet to its next-hop 797 destination. 799 It is possible to interface a DSR network with other networks, 800 external to this DSR network. Such external networks may, for 801 example, be the Internet, or may be other ad hoc networks routed 802 with a routing protocol other than DSR. Such external networks may 803 also be other DSR networks that are treated as external networks 804 in order to improve scalability. The complete handling of such 805 external networks is beyond the scope of this document. However, 806 this document specifies a minimal set of requirements and features 807 necessary to allow nodes only implementing this specification to 808 interoperate correctly with nodes implementing interfaces to such 809 external networks. This minimal set of requirements and features 810 involve the First Hop External (F) and Last Hop External (L) 811 bits in a Source Route option (Section 5.7) and a Route Reply 812 option (Section 5.3) in a packet's DSR header (Section 5). These 813 requirements also include the addition of an External flag bit 814 tagging each node in the Route Cache, copied from the First Hop 815 External (F) and Last Hop External (L) bits in the Source Route 816 option or Route Reply option from which the link to this node was 817 learned. 819 The Route Cache SHOULD support storing more than one route to each 820 destination. In searching the Route Cache for a route to some 821 destination node, the Route Cache is indexed by destination node 822 address. The following properties describe this searching function 823 on a Route Cache: 825 - Each implementation of DSR at any node MAY choose any appropriate 826 strategy and algorithm for searching its Route Cache and 827 selecting a "best" route to the destination from among those 828 found. For example, a node MAY choose to select the shortest 829 route to the destination (the shortest sequence of hops), or it 830 MAY use an alternate metric to select the route from the Cache. 832 - However, if there are multiple cached routes to a destination, 833 the selection of routes when searching the Route Cache SHOULD 834 prefer routes that do not have the External flag set on any node. 835 This preference will select routes that lead directly to the 836 target node over routes that attempt to reach the target via any 837 external networks connected to the DSR ad hoc network. 839 - In addition, any route selected when searching the Route Cache 840 MUST NOT have the External bit set for any nodes other than 841 possibly the first node, the last node, or both; the External bit 842 MUST NOT be set for any intermediate hops in the route selected. 844 An implementation of a Route Cache MAY provide a fixed capacity 845 for the cache, or the cache size MAY be variable. The following 846 properties describe the management of available space within a node's 847 Route Cache: 849 - Each implementation of DSR at each node MAY choose any 850 appropriate policy for managing the entries in its Route Cache, 851 such as when limited cache capacity requires a choice of which 852 entries to retain in the Cache. For example, a node MAY chose a 853 "least recently used" (LRU) cache replacement policy, in which 854 the entry last used longest ago is discarded from the cache if a 855 decision needs to be made to allow space in the cache for some 856 new entry being added. 858 - However, the Route Cache replacement policy SHOULD allow routes 859 to be categorized based upon "preference", where routes with a 860 higher preferences are less likely to be removed from the cache. 861 For example, a node could prefer routes for which it initiated 862 a Route Discovery over routes that it learned as the result of 863 promiscuous snooping on other packets. In particular, a node 864 SHOULD prefer routes that it is presently using over those that 865 it is not. 867 Any suitable data structure organization, consistent with this 868 specification, MAY be used to implement the Route Cache in any node. 869 For example, the following two types of organization are possible: 871 - In DSR, the route returned in each Route Reply that is received 872 by the initiator of a Route Discovery (or that is learned from 873 the header of overhead packets, as described in Section 6.1.4) 874 represents a complete path (a sequence of links) leading to the 875 destination node. By caching each of these paths separately, 876 a "path cache" organization for the Route Cache can be formed. 877 A path cache is very simple to implement and easily guarantees 878 that all routes are loop-free, since each individual route from 879 a Route Reply or Route Request or used in a packet is loop-free. 880 To search for a route in a path cache data structure, the sending 881 node can simply search its Route Cache for any path (or prefix of 882 a path) that leads to the intended destination node. 884 This type of organization for the Route Cache in DSR has 885 been extensively studied through simulation [5, 11, 18] and 886 through implementation of DSR in a mobile outdoor testbed under 887 significant workload [19, 20, 20]. 889 - Alternatively, a "link cache" organization could be used for the 890 Route Cache, in which each individual link (hop) in the routes 891 returned in Route Reply packets (or otherwise learned from the 892 header of overhead packets) is added to a unified graph data 893 structure of this node's current view of the network topology. 894 To search for a route in link cache, the sending node must use 895 a more complex graph search algorithm, such as the well-known 896 Dijkstra's shortest-path algorithm, to find the current best path 897 through the graph to the destination node. Such an algorithm is 898 more difficult to implement and may require significantly more 899 CPU time to execute. 901 However, a link cache organization is more powerful than a 902 path cache organization, in its ability to effectively utilize 903 all of the potential information that a node might learn about 904 the state of the network: links learned from different Route 905 Discoveries or from the header of any overheard packets can be 906 merged together to form new routes in the network, but this 907 is not possible in a path cache due to the separation of each 908 individual path in the cache. 910 This type of organization for the Route Cache in DSR, including 911 the effect of a range of implementation choices, has been studied 912 through detailed simulation [9]. 914 The choice of data structure organization to use for the Route Cache 915 in any DSR implementation is a local matter for each node and affects 916 only performance; any reasonable choice of organization for the Route 917 Cache does not affect either correctness or interoperability. 919 4.2. Route Request Table 921 The Route Request Table records information about Route Requests that 922 have been recently originated or forwarded by this node. The table 923 is indexed by IP address. 925 The Route Request Table on a node records the following information 926 about nodes to which this node has initiated a Route Request: 928 - The time that this node last originated a Route Request for that 929 target node. 931 - The number of consecutive Route Requests initiated for this 932 target since receiving a valid Route Reply giving a route to that 933 target node. 935 - The remaining amount of time before which this node MAY next 936 attempt at a Route Discovery for that target node. 938 - The Time-to-Live (TTL) field used in the IP header of last Route 939 Request initiated by this node for that target node. 941 In addition, the Route Request Table on a node also records the 942 following information about initiator nodes from which this node has 943 received a Route Request: 945 - A FIFO cache of size REQUEST_TABLE_IDS entries containing the 946 Identification value and target address from the most recent 947 Route Requests received by this node from that initiator node. 949 Nodes SHOULD use an LRU policy to manage the entries in their Route 950 Request Table. 952 The number of Identification values to retain in each Route Request 953 Table entry, REQUEST_TABLE_IDS, MUST NOT be unlimited, since, 954 in the worst case, when a node crashes and reboots, the first 955 REQUEST_TABLE_IDS Route Discoveries it initiates after rebooting 956 could appear to be duplicates to the other nodes in the network. 957 In addition, a node SHOULD base its initial Identification value, 958 used for Route Discoveries after rebooting, on a battery backed-up 959 clock or other persistent memory device, in order to help avoid any 960 possible such delay in successfully discovering new routes after 961 rebooting; if no such source of initial Identification value is 962 available, a node SHOULD base its initial Identification value after 963 rebooting on a random number. 965 4.3. Send Buffer 967 The Send Buffer of a node implementing DSR is a queue of packets that 968 cannot be sent by that node because it does not yet have a source 969 route to each such packet's destination. Each packet in the Send 970 Buffer is logically associated with the time that it was placed into 971 the Buffer, and SHOULD be removed from the Send Buffer and silently 972 discarded SEND_BUFFER_TIMEOUT seconds after initially being placed in 973 the Buffer. If necessary, a FIFO strategy SHOULD be used to evict 974 packets before they timeout to prevent the buffer from overflowing. 976 Subject to the rate limiting defined in Section 6.2, a Route 977 Discovery SHOULD be initiated as often as possible for the 978 destination address of any packets residing in the Send Buffer. 980 4.4. Retransmission Buffer 982 The Retransmission Buffer of a node implementing DSR is a queue 983 of packets sent by this node that are awaiting the receipt of an 984 acknowledgment from the next hop in the source route (Section 5.7). 985 For each packet in the Retransmission Buffer, a node maintains (1) a 986 count of the number of retransmissions and (2) the time of the last 987 retransmission. 989 Packets are removed from the Retransmission Buffer when an 990 acknowledgment is received or when the number of retransmissions 991 exceeds DSR_MAXRXTSHIFT. In the later case, the removal of the 992 packet from the Retransmission Buffer SHOULD result in a Route Error 993 being returned to the original source of the packet (Section 6.3). 995 5. DSR Header Format 997 The Dynamic Source Routing protocol makes use of a special header 998 carrying control information that can be included in any existing IP 999 packet. This DSR header in a packet contains a small fixed-sized, 1000 4-octet portion, followed by a sequence of zero or more DSR options 1001 carrying optional information. The end of the sequence of DSR 1002 options in the DSR header is implied by total length of the DSR 1003 header. 1005 The DSR header is inserted in the packet following the packet's IP 1006 header, before any following header such as a traditional (e.g., TCP 1007 or UDP) transport layer header. Specifically, the Protocol field 1008 in the IP header is used to indicate that a DSR header follows the 1009 IP header, and the Next Header field in the DSR header is used to 1010 indicate the type of protocol header (such as a transport layer 1011 header) following the DSR header. 1013 The total length of the DSR header (and thus the total, combined 1014 length of all DSR options present) MUST be a multiple of 4 octets. 1015 This requirement preserves the alignment of any following headers in 1016 the packet. 1018 5.1. Fixed Portion of DSR Header 1020 The fixed portion of the DSR header is used to carry information that 1021 must be present in any DSR header. This fixed portion of the DSR 1022 header has the following format: 1024 0 1 2 3 1025 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 1026 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1027 | Next Header | Reserved | Payload Length | 1028 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1029 . . 1030 . Options . 1031 . . 1032 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1034 Next Header 1036 8-bit selector. Identifies the type of header immediately 1037 following the DSR header. Uses the same values as the IPv4 1038 Protocol field [26]. 1040 Reserved 1042 Sent as 0; ignored on reception. 1044 Payload Length 1046 The length of the DSR header, excluding the 4-octet fixed 1047 portion. The value of the Payload Length field defines the 1048 total length of all options carried in the DSR header. 1050 Options 1052 Variable-length field; the length of the Options field is 1053 specified by the Payload Length field in this DSR header. 1054 Contains one or more pieces of optional information (DSR 1055 options), encoded in type-length-value (TLV) format (with the 1056 exception of the Pad1 option, described in Section 5.8). 1058 The placement of DSR options following the fixed portion of the DSR 1059 header MAY be padded for alignment. However, due to the typically 1060 limited available wireless bandwidth in ad hoc networks, this padding 1061 is not required, and receiving nodes MUST NOT expect options within 1062 a DSR header to be aligned. A node inserting a DSR header into 1063 a packet MUST set the Don't Fragment (DF) bit in the packet's IP 1064 header. 1066 The following types of DSR options are defined in this document for 1067 use within a DSR header: 1069 - Route Request option (Section 5.2) 1071 - Route Reply option (Section 5.3) 1073 - Route Error option (Section 5.4) 1075 - Acknowledgement Request option (Section 5.5) 1077 - Acknowledgement option (Section 5.6) 1079 - Source Route option (Section 5.7) 1081 - Pad1 option (Section 5.8) 1083 - PadN option (Section 5.9) 1085 5.2. Route Request Option 1087 The Route Request DSR option is encoded as follows: 1089 0 1 2 3 1090 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 1091 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1092 | Option Type | Opt Data Len | Identification | 1093 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1094 | Target Address | 1095 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1096 | Address[1] | 1097 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1098 | Address[2] | 1099 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1100 | ... | 1101 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1102 | Address[n] | 1103 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1105 IP fields: 1107 Source Address 1109 MUST be set to the address of the node originating this packet. 1110 Intermediate nodes that retransmit the packet to propagate the 1111 Route Request MUST NOT change this field. 1113 Destination Address 1115 MUST be set to the IP limited broadcast address 1116 (255.255.255.255). 1118 Hop Limit (TTL) 1120 MAY be varied from 1 to 255, for example to implement 1121 non-propagating Route Requests and Route Request expanding-ring 1122 searches (Section 3.3.4). 1124 Route Request fields: 1126 Option Type 1128 2 1130 Opt Data Len 1132 8-bit unsigned integer. Length of the option, in octets, 1133 excluding the Option Type and Opt Data Len fields. 1135 Identification 1137 A unique value generated by the initiator (original sender) of 1138 the Route Request. Nodes initiating a Route Request generate 1139 a new Identification value for each Route Request, for example 1140 based on a sequence number counter of all Route Requests 1141 initiated by the node. 1143 This value allows a receiving node to determine whether it 1144 has recently seen a copy of this Route Request: if this 1145 Identification value is found by this receiving node in its 1146 Route Request Table (in the cache of Identification values 1147 in the entry there for this initiating node), this receiving 1148 node MUST discard the Route Request. When propagating a Route 1149 Request, this field MUST be copied from the received copy of 1150 the Route Request being propagated. 1152 Target Address 1154 The address of the node that is the target of the Route 1155 Request. 1157 Address[1..n] 1159 Address[i] is the address of the i-th hop recorded in the Route 1160 Request option. The address given in the Source Address field 1161 in the IP header is the address of the initiator of the Route 1162 Discovery and MUST NOT be listed in the Address[i] fields; the 1163 address given in Address[1] is thus the address of the first 1164 node on the path after the initiator. The number of addresses 1165 present in this field is indicated by the Opt Data Len field in 1166 the option (n = (Opt Data Len - 2) / 4). Each node propagating 1167 the Route Request adds its own address to this list, increasing 1168 the Opt Data Len value by 4 octets. 1170 The Route Request option MUST NOT appear more than once within a DSR 1171 header. 1173 5.3. Route Reply Option 1175 The Route Reply DSR option is encoded as follows: 1177 0 1 2 3 1178 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 1179 +-+-+-+-+-+-+-+-+ 1180 | Option Type | 1181 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1182 | Opt Data Len |L| Reserved | Identification | 1183 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1184 | Address[1] | 1185 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1186 | Address[2] | 1187 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1188 | ... | 1189 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1190 | Address[n] | 1191 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1193 IP fields: 1195 Source Address 1197 Set to the address of the node sending the Route Reply. 1198 In the case of a node sending a reply from its Route 1199 Cache (Section 3.3.2) or sending a gratuitous Route Reply 1200 (Section 3.4.2), this address can differ from the address that 1201 was the target of the Route Discovery. 1203 Destination Address 1205 MUST be set to the address of the source node of the route 1206 being returned. Copied from the Source Address field of the 1207 Route Request generating the Route Reply, or in the case of a 1208 gratuitous Route Reply, copied from the Source Address field of 1209 the data packet triggering the gratuitous Reply. 1211 Route Reply fields: 1213 Option Type 1215 3 1217 Opt Data Len 1219 8-bit unsigned integer. Length of the option, in octets, 1220 excluding the Option Type and Opt Data Len fields. 1222 Last Hop External (L) 1224 Set to indicate that the last node indicated by the Route 1225 Reply (Address[n]) is actually in a network external to the 1226 DSR network; the exact sequence of hops leading to it outside 1227 the DSR network is not represented in the Route Reply. Nodes 1228 caching this hop in their Route Cache MUST flag the cached hop 1229 with the External flag. Such hops MUST NOT be returned in a 1230 cached Route Reply generated from this Route Cache entry, and 1231 selection of routes from the Route Cache to route a packet 1232 being sent SHOULD prefer routes that contain no hops flagged as 1233 External. 1235 Reserved 1237 Sent as 0; ignored on reception. 1239 Identification 1241 Copied from the Identification field of the Route Request for 1242 which this Reply is sent in response. Sent as 0 if the Route 1243 Reply is not sent in response to a Route Request (a gratuitous 1244 Route Reply). 1246 Address[1..n] 1248 The source route being returned by the Route Reply. The route 1249 indicates a sequence of hops, originating at the source node 1250 specified in the Destination Address field of the IP header 1251 of the packet carrying the Route Reply, through each of the 1252 Address[i] nodes in the order listed in the Route Reply, 1253 ending with the destination node indicated by Address[n]. 1254 The number of addresses present in the Address[1..n] 1255 field is indicated by the Opt Data Len field in the option 1256 (n = (Opt Data Len - 3) / 4). 1258 A Route Reply option MAY appear one or more times within a DSR 1259 header. 1261 5.4. Route Error Option 1263 The Route Error DSR option is encoded as follows: 1265 0 1 2 3 1266 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 1267 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1268 | Option Type | Opt Data Len | Error Type |Reservd|Salvage| 1269 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1270 | Error Source Address | 1271 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1272 | Error Destination Address | 1273 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1274 . . 1275 . Type-Specific Information . 1276 . . 1277 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1279 Option Type 1281 4 1283 Opt Data Len 1285 8-bit unsigned integer. Length of the option, in octets, 1286 excluding the Option Type and Opt Data Len fields. 1288 For the current definition of the Route Error option, 1289 this field MUST be set to 10, plus the size of any 1290 Type-Specific Information present in the Route Error. Further 1291 extensions to the Route Error option format may also be 1292 included after the Type-Specific Information portion of the 1293 Route Error option specified above. The presence of such 1294 extensions will be indicated by the Opt Data Len field. 1295 When the Opt Data Len is greater than that required for 1296 the fixed portion of the Route Error plus the necessary 1297 Type-Specific Information as indicated by the Option Type 1298 value in the option, the remaining octets are interpreted as 1299 extensions. Currently, no such further extensions have been 1300 defined. 1302 Error Type 1304 The type of error encountered. Currently, the following type 1305 value is defined: 1307 1 = NODE_UNREACHABLE 1309 Other values of the Error Type field are reserved for future 1310 use. 1312 Reservd 1314 Reserved. Sent as 0; ignored on reception. 1316 Salvage 1318 A 4-bit unsigned integer. Copied from the Salvage field in the 1319 Source Route option of the packet triggering the Route Error, 1320 incremented by the node returning the Route Error. 1322 Error Source Address 1324 The address of the node originating the Route Error (e.g., the 1325 node that attempted to forward a packet and discovered the link 1326 failure). 1328 Error Destination Address 1330 The address of the node to which the Route Error must be 1331 delivered For example, when the Error Type field is set to 1332 NODE_UNREACHABLE, this field will be set to the address of the 1333 node that generated the routing information claiming that the 1334 hop from the Error Source Address to Unreachable Node Address 1335 (specified in the Type-Specific Information) was a valid hop. 1337 Type-Specific Information 1339 Information specific to the Error Type of this Route Error 1340 message. 1342 Currently, the Type-Specific Information field is defined only for 1343 Route Error messages of type NODE_UNREACHABLE. In this case, the 1344 Type-Specific Information field is defined as follows: 1346 0 1 2 3 1347 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 1348 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1349 | Unreachable Node Address | 1350 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1352 Unreachable Node Address 1354 The address of the node that was found to be unreachable 1355 (the next hop neighbor to which the node with address 1356 Error Source Address was attempting to transmit the packet). 1358 A Route Error option MAY appear one or more times within a DSR 1359 header. 1361 5.5. Acknowledgment Request Option 1363 The Acknowledgment Request DSR option is encoded as follows: 1365 0 1 2 3 1366 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 1367 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1368 | Option Type | Opt Data Len | Identification | 1369 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1370 | ACK Request Source Address | 1371 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1373 Option Type 1375 5 1377 Opt Data Len 1379 8-bit unsigned integer. Length of the option, in octets, 1380 excluding the Option Type and Opt Data Len fields. 1382 Identification 1384 The Identification field is set to a unique nonzero value and 1385 is copied into the Identification field of the Acknowledgement 1386 option when returned by the node receiving the packet over this 1387 hop. 1389 ACK Request Source Address 1391 The address of the node requesting the acknowledgment. 1393 An Acknowledgement Request option MUST NOT appear more than once 1394 within a DSR header. 1396 5.6. Acknowledgment Option 1398 The Acknowledgment DSR option is encoded as follows: 1400 0 1 2 3 1401 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 1402 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1403 | Option Type | Opt Data Len | Identification | 1404 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1405 | ACK Source Address | 1406 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1407 | ACK Destination Address | 1408 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1410 Option Type 1412 6 1414 Opt Data Len 1416 8-bit unsigned integer. Length of the option, in octets, 1417 excluding the Option Type and Opt Data Len fields. 1419 Identification 1421 Copied from the Identification field of the Acknowledgement 1422 Request option of the packet being acknowledged. 1424 ACK Source Address 1426 The address of the node originating the acknowledgment. 1428 ACK Destination Address 1430 The address of the node to which the acknowledgment is to be 1431 delivered. 1433 An Acknowledgement option MAY appear one or more times within a DSR 1434 header. 1436 5.7. Source Route Option 1438 The Source Route DSR option is encoded as follows: 1440 0 1 2 3 1441 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 1442 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1443 | Option Type | Opt Data Len |F|L|Reservd|Salvage| Segs Left | 1444 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1445 | Address[1] | 1446 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1447 | Address[2] | 1448 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1449 | ... | 1450 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1451 | Address[n] | 1452 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1454 Option Type 1456 7 1458 Opt Data Len 1460 8-bit unsigned integer. Length of the option, in octets, 1461 excluding the Option Type and Opt Data Len fields. For the 1462 format of the Source Route option defined here, this field 1463 MUST be set to the value (n * 4) + 2, where n is the number of 1464 addresses present in the Address[i] fields. 1466 First Hop External (F) 1468 Set to indicate that the first node indicated by the Source 1469 Route option is actually in a network external to the DSR 1470 network; the exact sequence of hops leading from it outside the 1471 DSR network are not represented in the Source Route option. 1472 Nodes caching this hop in their Route Cache MUST flag the 1473 cached hop with the External flag. Such hops MUST NOT be 1474 returned in a Route Reply generated from this Route Cache 1475 entry, and selection of routes from the Route Cache to route 1476 a packet being sent SHOULD prefer routes that contain no hops 1477 flagged as External. 1479 Last Hop External (L) 1481 Set to indicate that the last hop indicated by the Source Route 1482 option is actually in a network external to the DSR network; 1483 the exact sequence of hops leading to it outside the DSR 1484 network are not represented in the Source Route option. Nodes 1485 caching this hop in their Route Cache MUST flag the cached 1486 hop with the External flag. Such hops MUST NOT be returned 1487 in a Route Reply generated from this Route Cache entry, and 1488 selection of routes from the Route Cache to route a packet 1489 being sent SHOULD prefer routes that contain no hops flagged as 1490 External. 1492 Reserved 1494 Sent as 0; ignored on reception. 1496 Salvage 1498 A 4-bit unsigned integer. Count of number of times that 1499 this packet has been salvaged as a part of DSR routing 1500 (Section 3.4.1). 1502 Segments Left (Segs Left) 1504 Number of route segments remaining, i.e., number of explicitly 1505 listed intermediate nodes still to be visited before reaching 1506 the final destination. 1508 Address[1..n] 1510 The sequence of addresses of the source route. In routing 1511 and forwarding the packet, the source route is processed as 1512 described in Sections 6.1.3 and 6.1.5. 1514 When forwarding a packet along a DSR source route using a Source 1515 Route option in the packet's DSR header, the Source Address field in 1516 the packet's IP header is always set to the address of the packet's 1517 ultimate destination. A node receiving a packet containing a DSR 1518 header with a Source Route option MUST examine the indicated source 1519 route to determine if it is the intended next hop for the packet and 1520 determine how to forward the packet, as defined in Sections 6.1.4 1521 and 6.1.5. 1523 5.8. Pad1 Option 1525 The Pad1 DSR option is encoded as follows: 1527 +-+-+-+-+-+-+-+-+ 1528 | Option Type | 1529 +-+-+-+-+-+-+-+-+ 1531 Option Type 1533 0 1535 A Pad1 option MAY be included in the Options field of a DSR header 1536 in order to align subsequent DSR options, but such alignment is 1537 not required and MUST NOT be expected by nodes receiving packets 1538 containing a DSR header. 1540 The total length of a DSR header, indicated by the Payload Length 1541 field in the DSR header MUST be a multiple of 4 octets. When 1542 building a DSR header in a packet, sufficient Pad1 or PadN options 1543 MUST be included in the Options field of the DSR header to make the 1544 total length a multiple of 4 octets. 1546 If more than one consecutive octet of padding is being inserted in 1547 the Options field of a DSR header, the PadN option, described next, 1548 SHOULD be used, rather than multiple Pad1 options. 1550 Note that the format of the Pad1 option is a special case; it does 1551 not have an Opt Data Len or Option Data field. 1553 5.9. PadN Option 1555 The PadN DSR option is encoded as follows: 1557 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - 1558 | Option Type | Opt Data Len | Option Data 1559 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - 1561 Option Type 1563 1 1565 Opt Data Len 1567 8-bit unsigned integer. Length of the option, in octets, 1568 excluding the Option Type and Opt Data Len fields. 1570 Option Data 1572 A number of zero valued octets equal to the Opt Data Len. 1574 A PadN option MAY be included in the Options field of a DSR header 1575 in order to align subsequent DSR options, but such alignment is 1576 not required and MUST NOT be expected by nodes receiving packets 1577 containing a DSR header. 1579 The total length of a DSR header, indicated by the Payload Length 1580 field in the DSR header MUST be a multiple of 4 octets. When 1581 building a DSR header in a packet, sufficient Pad1 or PadN options 1582 MUST be included in the Options field of the DSR header to make the 1583 total length a multiple of 4 octets. 1585 6. Detailed Operation 1587 6.1. General Packet Processing 1589 6.1.1. Originating a Packet 1591 When originating any packet, a node using DSR routing MUST perform 1592 the following sequence of steps: 1594 - Search the node's Route Cache for a route to the address given in 1595 the IP Destination Address field in the packet's header. 1597 - If no such route is found in the Route Cache, then perform 1598 Route Discovery for the Destination Address, as described in 1599 Section 6.2. 1601 - If the packet contains a Route Request option, then replace the 1602 IP Destination Address field with the IP "limited broadcast" 1603 address (255.255.255.255) [3]. 1605 - Else, this node must have a route to the Destination Address 1606 of the packet (since otherwise a Route Request would have 1607 been added to the packet). If the length of this route is 1608 greater than 1 hop, or if the node determines to request a DSR 1609 network-layer acknowledgement from the first hop of the route, 1610 then insert a DSR header as described in Section 6.1.2, and 1611 insert a Source Route option, as described in Section 6.1.3. The 1612 source route in the packet is initialized from the route to the 1613 Destination Address found in the Route Cache. 1615 - Transmit the packet to the address given in the next hop, using 1616 Route Maintenance to retransmit the packet if necessary, as 1617 described in Section 6.3. 1619 6.1.2. Adding a DSR Header to a Packet 1621 A node originating a packet adds a DSR header to the packet, if 1622 necessary, to carry information needed by the routing protocol. A 1623 packet MUST NOT contain more than one DSR header. A DSR header is 1624 added to a packet by performing the following sequence of steps 1625 (these steps assume that the packet contains no other headers that 1626 MUST be located in the packet before the DSR header): 1628 - Insert a DSR header after the IP header but before any other 1629 header that may be present. 1631 - Set the Next Header field of the DSR header to the Protocol 1632 number field of the packet's IP header. 1634 - Set the Protocol field of the packet's IP header to the Protocol 1635 number assigned for a DSR header (???). 1637 6.1.3. Adding a Source Route Option to a Packet 1639 A node originating a packet adds a Source Route option to the packet, 1640 if necessary, in order to carry the source route of hops from this 1641 originating node to the final destination address of the packet. 1642 Specifically, the node adding the Source Route option constructs 1643 the Source Route option and modifies the IP packet according to the 1644 following sequence of steps: 1646 - A Source Route option, as described in Section 5.7, is created 1647 and appended to the DSR header in the packet (a DSR header is 1648 added, as described in Section 6.1.2, if not already present). 1650 - The number of Address[i] fields to include in the DSR Source 1651 Route option (n) is the number of intermediate nodes in the 1652 source route for the packet (i.e., excluding address of the 1653 originating node and the final destination address of the 1654 packet). The Segments Left field in the DSR Source Route option 1655 is initialized equal to n. 1657 - The Destination Address from the IP header is copied into 1658 Address[n] in the DSR Source Route option. 1660 - The first hop of the source route for the packet is copied into 1661 the Destination Address field in the IP header. 1663 - The remaining hops of the source route for the packet are copied 1664 into sequential Address[i] fields in the Source Route option, 1665 for i = 1, 2, ..., n-1. 1667 - The First Hop External (F) bit in the Source Route option is 1668 copied from the External bit flagging the first hop node in the 1669 source route for the packet, as indicated in the Route Cache. 1671 - The Last Hop External (L) bit in the Source Route option is 1672 copied from the External bit flagging the last hop node in the 1673 source route for the packet, as indicated in the Route Cache. 1675 6.1.4. Receiving a Packet 1677 When a node receives any packet containing a DSR header, it MUST 1678 process the packet according to the following sequence of steps: 1680 - If the Destination Address in the packet's IP header matches 1681 one of this receiving node's own IP address(es), remove the DSR 1682 header and all the included DSR options in the header, and pass 1683 the rest of the packet to the network layer. 1685 - Examine and process each of the options (if any) in the DSR 1686 header in the order in which they occur in the packet, skipping 1687 over any Pad1 or PadN options. 1689 Any DSR routing information carried in a packet SHOULD be examined 1690 and reflected in the node's Route Cache, even if the options in 1691 the packet are not otherwise processed as described above. In 1692 particular, the following routing information SHOULD be handled in 1693 this way: 1695 - In a Route Request option, the accumulated route record, 1696 represented by the IP Source Address of the packet and by the 1697 sequence of Address[i] entries in the Route Request option SHOULD 1698 be added to the node's Route Cache. 1700 - In a Route Reply option, the route record being returned, 1701 represented by the sequence of Address[i] entries in the Route 1702 Request option and by the Destination Address in the packet's IP 1703 header SHOULD be added to the node's Route Cache. 1705 - In an Acknowledgement option, the single link from the 1706 ACK Source Address to the ACK Destination Address SHOULD be added 1707 to the node's Route Cache. 1709 - In a Route Error option, the single link from the 1710 Error Source Address to the Unreachable Node Address MUST 1711 be removed from the node's Route Cache. 1713 - In a Source Route option, the indicated source route SHOULD 1714 be added to the node's Route Cache, subject to the conditions 1715 identified in Section 3.3.1. The full sequence of hops in the 1716 DSR Source Route option is as follows: 1718 * The Source Address in the packet's IP header is the first hop 1719 (the sender of the packet). 1721 * The sequence of hops 1723 Address[1], Address[2], ..., Address[n] 1725 follow immediately after the IP Source Address in the source 1726 route, where n is the number of addresses in the packet, or 1727 (Opt Data Len - 2) / 4. 1729 * The Destination Address in the packet's IP header is the 1730 final destination of the packet and is the last hop of the 1731 source route. 1733 In addition to the processing of received packets described above, a 1734 node SHOULD examine the packet to determine if the receipt of this 1735 packet indicates an opportunity for automatic route shortening, as 1736 described in Section 3.4.2. If the received packet satisfies the 1737 tests described there, then this node SHOULD perform the following 1738 sequence of steps: 1740 - Return a gratuitous Route Reply to the IP Source Address of the 1741 packet, as described in Section 3.4.2. 1743 - Discard the received packet, since the packet has been received 1744 before its normal traversal of the packet's source route would 1745 have caused it to reach this receiving node. Another copy of 1746 the packet will normally arrive at this node as indicated in 1747 the packet's source route; discarding this initial copy of the 1748 packet, which triggered the gratuitous Route Reply, will prevent 1749 the duplication of this packet that would otherwise occur. 1751 6.1.5. Processing a Received Source Route Option 1753 If a received packet contains a DSR header with a DSR Source Route 1754 option, the Source Route option MUST be examined and processed (even 1755 though this node is not indicated in the Destination Address field of 1756 the packet's IP header). 1758 If, after processing a Source Route option in a received packet, an 1759 intermediate node determines that the packet is to be forwarded onto 1760 a link whose link MTU is less than the size of the packet, the node 1761 MUST discard the packet and send an ICMP Packet Too Big message to 1762 the packet's Source Address [23]. 1764 A Source Route option in a DSR header for IPv4 is processed according 1765 to the following sequence of steps: 1767 - If the value of the Segments Left field in the Source Route 1768 option equals 0, then remove the Source Route option from the DSR 1769 header. 1771 - Else, let n equal (Opt Data Len - 2) / 4. This is the number of 1772 addresses in the Source Route option. 1774 - If the value of the Segments Left field is greater than n, then 1775 send an ICMP Parameter Problem, Code 0, message [23] to the IP 1776 Source Address, pointing to the Segments Left field, and discard 1777 the packet. Do not process the Source Route option further. 1779 - Else, decrement the value of the Segments Left field by 1. Let i 1780 equal n minus Segments Left. This is the index of the next 1781 address to be visited in the Address vector. 1783 - If Address[i] or the IP Destination Address is a multicast 1784 address, then discard the packet. Do not process the Source 1785 Route option further. 1787 - Forward the packet to the IP address specified in the Address[i] 1788 field of the IP header, following normal IP forwarding 1789 procedures, including checking and decrementing the Time-to-Live 1790 (TTL) field in the packet's IP header [24, 3]. In this 1791 forwarding of the packet, the next hop node (identified by 1792 Address[i]) MUST be treated as a direct neighbor node; the 1793 transmission to that next node MUST be done in a single IP 1794 forwarding hop, without Route Discovery and without searching the 1795 Route Cache. 1797 - In forwarding the packet, perform Route Maintenance for the next 1798 hop of the packet, by verifying that the packet was received by 1799 that next hop, as described in Section 6.3. 1801 Multicast addresses MUST NOT appear in a Source Route option or in 1802 the IP Destination Address field of a packet carrying a Source Route 1803 option in a DSR header. 1805 6.2. Route Discovery Processing 1807 Route Discovery is the mechanism by which a node S wishing to send a 1808 packet to a destination node D obtains a source route to D. Route 1809 Discovery is used only when S attempts to send a packet to D and 1810 does not already know a route to D. The node initiating a Route 1811 Discovery is known as the "initiator" of the Route Discovery, and the 1812 destination node for which the Route Discovery is initiated is known 1813 as the "target" of the Route Discovery. 1815 Route Discovery operates entirely on demand, with a node initiating 1816 Route Discovery based on its own origination of new packets for 1817 some destination address to which it does not currently know a 1818 route. Route Discovery does not depend on any periodic or background 1819 exchange of routing information or neighbor node detection at any 1820 layer in the network protocol stack at any node. 1822 The Route Discovery procedure utilizes two types of messages, a Route 1823 Request (Section 5.2) and a Route Reply (Section 5.3), to actively 1824 search the ad hoc network for a route to the desired destination. 1825 These DSR messages MAY be carried in any type of IP packet, through 1826 use of the DSR header as described in Section 5. 1828 A Route Discovery for a destination address SHOULD NOT be initiated 1829 unless the initiating node has a packet in its Send Buffer requiring 1830 delivery to that destination. A Route Discovery for a given target 1831 node MUST NOT be initiated unless permitted by the rate-limiting 1832 information contained in the Route Request Table. After each 1833 Route Discovery attempt, the interval between successive Route 1834 Discoveries for this target MUST be doubled, up to a maximum of 1835 MAX_REQUEST_PERIOD, until a valid Route Reply is received for this 1836 target. 1838 6.2.1. Originating a Route Request 1840 A node initiating a Route Discovery for some target creates and 1841 initializes a Route Request option in a DSR header in some IP packet. 1842 This MAY be a separate IP packet, used only to carry this Route 1843 Request option, or the node MAY include the Route Request option 1844 in some existing packet it needs to send to the target node (e.g., 1845 the IP packet originated by this node, that caused the node to 1846 attempt Route Discovery for the destination address of the packet). 1847 The Route Request option MUST be included in a DSR header in the 1848 packet. To initialize the Route Request option, the node performs 1849 the following sequence of steps: 1851 - The Option Type in the option MUST be set to the value 2. 1853 - The Opt Data Len field in the option MUST be set to the value 6. 1854 The total size of the Route Request option when initiated 1855 is 8 octets; the Opt Data Len field excludes the size of the 1856 Option Type and Opt Data Len fields themselves. 1858 - The Identification field in the option MUST be set to a new 1859 value, different from that used for other Route Requests recently 1860 initiated by this node. For example, each node MAY maintain a 1861 single counter value for generating a new Identification value 1862 for each Route Request it initiates. 1864 - The Target Address field in the option MUST be set to the IP 1865 address that is the target of this Route Discovery. 1867 The Source Address in the IP header of this packet MUST be the node's 1868 own IP address. The Destination Address in the IP header of this 1869 packet MUST be the IP "limited broadcast" address (255.255.255.255). 1871 A node MUST maintain in its Route Request Table, information about 1872 Route Requests that it initiates. When initiating a new Route 1873 Request, the node MUST use the information recorded in the Route 1874 Request Table entry for the target of that Route Request, and it MUST 1875 update that information in the table entry for use in the next Route 1876 Request initiated for this target. In particular: 1878 - The Route Request Table entry for a target node records the 1879 Time-to-Live (TTL) field used in the IP header of the last Route 1880 Request initiated by this node for that target node. This 1881 value allows the node to implement a variety of algorithms 1882 for controlling the spread of its Route Request on each Route 1883 Discovery initiated for a target. As examples, two possible 1884 algorithms for this use of the TTL field are described in 1885 Section 3.3.4. 1887 - The Route Request Table entry for a target node records the 1888 number of consecutive Route Requests initiated for this target 1889 since receiving a valid Route Reply giving a route to that target 1890 node, and the remaining amount of time before which this node MAY 1891 next attempt at a Route Discovery for that target node. 1893 These values MUST be used to implement an exponential back-off 1894 algorithm to limit the rate at which this node initiates new 1895 Route Discoveries for the same target address. Until a valid 1896 Route Reply is received for this target node address, the timeout 1897 between consecutive Route Discovery initiations for this target 1898 node SHOULD increase by doubling the timeout value on each new 1899 initiation. 1901 The behavior of a node processing a packet containing DSR header with 1902 both a Source Route option and a Route Request option is unspecified. 1904 Packets SHOULD NOT contain both a Source Route option and a Route 1905 Request option. 1907 Packets containing a Route Request option SHOULD NOT be 1908 retransmitted, SHOULD NOT request a DSR acknowledgment by including 1909 an Acknowledgement Request option, SHOULD NOT expect a passive 1910 acknowledgment, and SHOULD NOT be placed in the Retransmission 1911 Buffer. The repeated transmission of packets containing a Route 1912 Request option is controlled solely by the logic described in this 1913 section. 1915 6.2.2. Processing a Received Route Request Option 1917 When a node receives a packet containing a Route Request option, the 1918 node MUST process the option according to the following sequence of 1919 steps: 1921 - If the Target Address field in the Route Request matches this 1922 node's own IP address, then the node SHOULD return a Route Reply 1923 to the initiator of this Route Request (the Source Address in the 1924 IP header of the packet), as described in Section 6.2.4. The 1925 source route for this reply is the sequence of hops 1927 initiator, Address[1], Address[2], ..., Address[n], target 1929 where initiator is the address of the initiator of this Route 1930 Request, each Address[i] is an address from the Route Request, 1931 and target is the target of the Route Request (the Target Address 1932 field in the Route Request). 1934 The node MUST then continue processing the rest of the packet 1935 normally. The node in this case MUST NOT retransmit the Route 1936 Request to propagate it to other nodes. Do not process the Route 1937 Request option further. 1939 - Else, the node MUST examine the route recorded in the Route 1940 Request option (the IP Source Address field and the sequence of 1941 Address[i] fields) to determine if this node's own IP address 1942 already appears in this list of addresses. If so, the node MUST 1943 discard the entire packet carrying the Route Request option. 1945 - Else, the node MUST search its Route Request Table for an entry 1946 for the initiator of this Route Request (the IP Source Address 1947 field). If such an entry is found in the table, the node MUST 1948 search the cache of Identification values of recently received 1949 Route Requests in that table entry, to determine if an entry 1950 is present in the cache matching the Identification value 1951 and target node address in this Route Request. If such an 1952 (Identification, target address) entry is found in this cache in 1953 this entry in the Route Request Table, then the node MUST discard 1954 the entire packet carrying the Route Request option. 1956 - Else, this node SHOULD further process the Route Request 1957 according to the following sequence of steps: 1959 * Add an entry for this Route Request in its cache of 1960 (Identification, target address) values of recently received 1961 Route Requests. 1963 * Create a copy of this entire packet and perform the following 1964 steps on the copy of the packet. 1966 * Append this node's own IP address to the list of Address[i] 1967 values in the Route Request, and increase the value of the 1968 Opt Data Len field in the Route Request by 4 (the size of an 1969 IP address). 1971 * This node SHOULD search its own Route Cache for a route 1972 (from itself, as if it were the source of a packet) to the 1973 target of this Route Request. If such a route is found in 1974 its Route Cache, then this node SHOULD follow the procedure 1975 outlined in Section 6.2.3 to return a "cached Route Reply" 1976 to the initiator of this Route Request, if permitted by the 1977 restrictions specified there. 1979 * If the node does not return a cached Route Reply, then this 1980 node SHOULD link-layer re-broadcast this copy of the packet, 1981 with a short jitter delay before the broadcast is sent. The 1982 jitter period SHOULD be chosen as a random period, uniformly 1983 distributed between 0 and BROADCAST_JITTER. 1985 6.2.3. Generating Route Replies using the Route Cache 1987 As described in Section 3.3.2, it is possible for a node processing a 1988 received Route Request to avoid propagating the Route Request further 1989 toward the target of the Request, if this node has in its Route Cache 1990 a route from itself to this target. Such a Route Reply generated by 1991 a node from its own cached route to the target of a Route Request is 1992 called a "cached Route Reply", and this mechanism can greatly reduce 1993 the overall overhead of Route Discovery on the network by reducing 1994 the flood of Route Requests. The general processing of a received 1995 Route Request is described in Section 6.2.2; this section specifies 1996 the additional requirements that MUST be met before a cached Route 1997 Reply may be generated and returned and specifies the procedure for 1998 returning such a cached Route Reply. 2000 While processing a received Route Request, for a node to possibly 2001 return a cached Route Reply, it MUST have in its Route Cache a route 2002 from itself to the target of this Route Request. However, before 2003 generating a cached Route Reply for this Route Request, the node MUST 2004 verify that there are no duplicate addresses listed in the route 2005 accumulated in the Route Request together with the route from this 2006 node's Route Cache. Specifically, there MUST be no duplicates among 2007 the following addresses: 2009 - The IP Source Address of the packet containing the Route Request, 2011 - The Address[i] fields in the Route Request, and 2013 - The nodes listed in the route obtained from this node's Route 2014 Cache, excluding the address of this node itself (this node 2015 itself is the common point between the route accumulated in the 2016 Route Request and the route obtained from the Route Cache). 2018 If any duplicates exist among these addresses, then the node MUST NOT 2019 send a cached Route Reply. The node SHOULD continue to process the 2020 Route Request as described in Section 6.2.2. 2022 If the Route Request and the route from the Route Cache meet the 2023 restriction above, then the node SHOULD construct and return a cached 2024 Route Reply as follows: 2026 - The source route for this reply is the sequence of hops 2028 initiator, Address[1], Address[2], ..., Address[n], c-route 2030 where initiator is the address of the initiator of this Route 2031 Request, each Address[i] is an address from the Route Request, 2032 and c-route is the sequence of hops in the source route to this 2033 target node, obtained from the node's Route Cache. In appending 2034 this cached route to the source route for the reply, the address 2035 of this node itself MUST be excluded, since it is already listed 2036 as Address[n]. 2038 - Send a Route Reply to the initiator of the Route Request, using 2039 the procedure defined in Section 6.2.4. The initiator of the 2040 Route Request is indicated in the Source Address field in the 2041 packet's IP header. 2043 6.2.4. Originating a Route Reply 2045 A node originates a Route Reply in order to reply to a received and 2046 processed Route Request, according to the procedures described in 2047 Sections 6.2.2 and 6.2.3. The Route Reply is returned in a Route 2048 Reply option (Section 5.3). The Route Reply option MAY be returned 2049 to the initiator of the Route Request in a separate IP packet, used 2050 only to carry this Route Reply option, or it MAY be included in any 2051 other IP packet being sent to this address. 2053 The Route Reply option MUST be included in a DSR header in the packet 2054 returned to the initiator. To initialize the Route Reply option, the 2055 node performs the following sequence of steps: 2057 - The Option Type in the option MUST be set to the value 3. 2059 - The Opt Data Len field in the option MUST be set to the value 2060 (n * 4) + 3, where n is the number of addresses in the source 2061 route being returned (excluding the Route Discovery initiator 2062 node's address). 2064 - The Last Hop External (L) bit in the option MUST be initialized 2065 to 0. 2067 - The Reserved field in the option MUST be initialized to 0. 2069 - The Route Request Identifier MUST be initialized to the 2070 Identifier field of the Route Request that this reply is sent in 2071 response to. 2073 - The sequence of addresses of the source route are copied into 2074 the Address[i] fields of the option. Address[1] MUST be set 2075 to the first hop of the route after the initiator of the Route 2076 Discovery, Address[n] MUST be set to the last hop of the source 2077 route (the address of the target node), and each other Address[i] 2078 MUST be set to the next address in sequence in the source route 2079 being returned. 2081 The Destination Address field in the IP header of the packet carrying 2082 the Route Reply option MUST be set to the address of the initiator 2083 of the Route Discovery (i.e., for a Route Reply being returned in 2084 response to some Route Request, the IP Source Address of the Route 2085 Request). 2087 After creating and initializing the Route Reply option and the IP 2088 packet containing it, send the Route Reply. In sending the Route 2089 Reply from this node (but not from nodes forwarding the Route Reply), 2090 this node SHOULD delay the rely by a small jitter period chosen 2091 randomly between 0 and BROADCAST_JITTER milliseconds. 2093 If the MAC layer above which DSR is operating requires 2094 bidirectionality for unidirectional transmissions, the Route 2095 Reply MUST be sent by reversing the sequence of hops that are stored 2096 in it. 2098 If sending a Route Reply to the originator of the Route Request 2099 requires performing a Route Discovery, the Route Reply Option MUST 2100 be piggybacked on the packet that contains the Route Request. This 2101 piggybacking prevents a loop wherein the target of the new Route 2102 Request (which was itself the originator of the original Route 2103 Request) must do another Route Request in order to return its Route 2104 Reply. 2106 If sending the Route Reply to the originator of the Route Request 2107 does not require performing Route Discovery, a node SHOULD send a 2108 unicast Route Reply in response to every received Route Request 2109 targeted at it. 2111 6.2.5. Processing a Route Reply Option 2113 Upon receiving a Route Reply, a node SHOULD extract the source route 2114 from the Route Reply and add this routing information to its Route 2115 Cache. The source route from the Route Reply is the sequence of hops 2117 initiator, Address[1], Address[2], ..., Address[n] 2119 where initiator is the value of the Destination Address field in 2120 the IP header of the packet carrying the Route Reply (the address 2121 of the initiator of the Route Discovery), and each Address[i] is a 2122 node through which the source route passes, in turn, on the route to 2123 the target of the Route Discovery. Address[n] is the address of the 2124 target. 2126 If the Last Hop External (L) bit is set in the Route Reply, the node 2127 MUST flag the hop Address[n] in its Route Cache as External. 2129 Each packet in the Send Buffer SHOULD then be checked to see whether 2130 the information in the Route Reply and now in the Route Cache allows 2131 it to be sent immediately. 2133 6.3. Route Maintenance Processing 2135 Route Maintenance is the mechanism by which node S is able to detect, 2136 while using a source route to D, if the network topology has changed 2137 such that it can no longer use its route to D because a link along 2138 the route no longer works. When Route Maintenance indicates a source 2139 route is broken, S can attempt to use any other route it happens to 2140 know to D, or can invoke Route Discovery again to find a new route 2141 for subsequent packets to D. Route Maintenance for this route is 2142 used only when S is actually sending packets to D. 2144 When forwarding a packet, a node MUST attempt to receive an 2145 acknowledgement for the packet from the next hop. If no 2146 acknowledgement is received, the node SHOULD return a Route Error to 2147 the IP Source Address of the packet, as described in Section 6.3.3. 2148 A node's algorithm for deciding whether or not to return a Route 2149 Error MUST NOT allow any node to attempt to send an unbounded number 2150 of packets along a broken link without receiving a Route Error. 2152 6.3.1. Using Network-Layer Acknowledgments 2154 When a node retransmits a packet or has no other way to ensure 2155 successful delivery of a packet to the next hop, it MUST request a 2156 network-layer acknowledgement by placing inserting an Acknowledgement 2157 Request the DSR header. The Identification value contained in that 2158 header MUST be unique over all packets delivered to the same next hop 2159 which are either unacknowledged or recently acknowledged. 2161 A node receiving an Acknowledgement Request MUST send an 2162 acknowledgement to the previous hop by performing the following 2163 sequence of steps: 2165 - Create a packet and set the IP Source Address to the address 2166 of this node, the IP Destination Address to the address of the 2167 previous hop, and the IP Protocol field to the protocol number 2168 reserved for DSR headers. 2170 - Set the DSR header's Next Header field to be the "No Next Header" 2171 value. 2173 - Set the Acknowledgement option's Option Type field to 6, and the 2174 Opt Data Len field to 10. 2176 - Copy the Identification field from the Acknowledgement Request 2177 option into the Identification field in the Acknowledgement 2178 option. Set the ACK Source Address field in the option to be the 2179 IP Source Address and the ACK Destination Address field to the IP 2180 Destination Address. 2182 - Send the packet as described in Section 6.1.1. 2184 6.3.2. Using Link Layer Acknowledgments 2186 If explicit failure notifications are provided by the link layer, 2187 then all packets are assumed to be correctly received by the 2188 next hop, and a Route Error is sent only when an explicit failure 2189 notification is made from the link layer. 2191 Nodes receiving a packet without an Acknowledgement Request Option 2192 do not need to send an explicit Acknowledgment to the packet's 2193 originator, since the link layer will notify the originator if the 2194 packet was not received properly. 2196 6.3.3. Originating a Route Error 2198 When a node is unable to verify successful delivery of a packet to 2199 the next hop after a maximum number of retransmission attempts, 2200 a node SHOULD send a Route Error to the IP Source Address of the 2201 packet. In addition, a node's algorithm for deciding whether or not 2202 to return a Route Error MUST NOT allow any node to attempt to send 2203 an unbounded number of packets along a broken link without receiving 2204 a Route Error. When sending a Route Error for a packet containing 2205 either a Route Error option or an Acknowledgement option, a node 2206 SHOULD add these options to its Route Error, subject to some limit on 2207 lifetime. Specifically, we define the "salvage count" of an option 2208 to be the sum of one plus the salvage count recorded in the Source 2209 Route option plus the sum of the salvage counts of any Route Errors 2210 preceding that option. 2212 A node transmitting a Route Error MUST follow the following steps: 2214 - Create a packet and set the IP Source Address to the address of 2215 this node, the IP Destination Address to the address IP Source 2216 Address of the packet experiencing the error. 2218 - Insert a DSR header into the packet. 2220 - Add a Route Error Option, setting the Error Type to 2221 NODE_UNREACHABLE, the Reserved bits to 0, the Salvage value to 2222 one plus the Salvage value from the DSR Source Route option, and 2223 the Unreachable Node Address to the address of the next hop. Set 2224 the Error Source Address to the IP Source Address and the Error 2225 Destination to the IP Destination Address. 2227 - The node MAY append each Route Error and Acknowledgement 2228 option, in order, from the packet experiencing the error, 2229 though it MUST exclude options with salvage counts greater 2230 than MAX_SALVAGE_TIMES. 2232 - Send the packet as described in Section 6.1.1. 2234 6.3.4. Processing a Route Error Option 2236 A node receiving a Route Error MUST process it as follows: 2238 - Delete all routes from the Route Cache that have a link from the 2239 Route Error Source Address to the Unreachable Node Address. 2241 - If the option following the Route Error is an Acknowledgement 2242 or Route Error option sent by this node (that is, with 2243 Acknowledgement or Error Source Address equal to this node's 2244 address), copy the DSR options following the current Route 2245 Error into a new packet with IP Source Address equal to this 2246 node's own IP address and IP Destination Address equal to the 2247 Acknowledgement or Error Destination Address. Transmit this 2248 packet as described in Section 6.1.1, with the salvage count in 2249 the Source Route option set to the Salvage value of the Route 2250 Error. 2252 6.3.5. Salvaging a Packet 2254 When a node is unable to verify successful delivery of a packet 2255 to the next hop after a maximum number of retransmission attempts 2256 and has transmitted a Route Error to the sender, it MAY attempt to 2257 salvage the packet by examining its route cache. If the node can 2258 find a route to the packet's IP Destination Address in its own Route 2259 Cache, then this node replaces the packet's Source Route option 2260 with a new Source Route option in the same way as described in 2261 Section 6.1.3, except that Address[1] MUST be set to the address of 2262 this node and the Salvage field MUST be set to 1 plus the value of 2263 the Salvage field in the Source Route option that caused the error. 2265 7. Constants 2267 BROADCAST_JITTER 10 milliseconds 2269 MAX_ROUTE_LEN 15 nodes 2271 MAX_SALVAGE_TIMES 15 salvages 2273 Route Cache 2274 ROUTE_CACHE_TIMEOUT 300 seconds 2276 Send Buffer 2277 SEND_BUFFER_TIMEOUT 30 seconds 2279 Route Request Table 2280 REQUEST_TABLE_SIZE 64 nodes 2281 REQUEST_TABLE_IDS 16 identifiers 2282 MAX_REQUEST_REXMT 16 retransmissions 2283 MAX_REQUEST_PERIOD 10 seconds 2284 REQUEST_PERIOD 500 milliseconds 2285 NONPROP_REQUEST_TIMEOUT 30 milliseconds 2287 Retransmission Buffer 2288 DSR_RXMT_BUFFER_SIZE 50 packets 2290 Retransmission Timer 2291 DSR_MAXRXTSHIFT 2 2293 8. IANA Considerations 2295 This document proposes the use of a DSR header, which requires an IP 2296 Protocol number. 2298 In addition, this document proposes use of the value "No Next Header" 2299 (originally defined for use in IPv6) within an IPv4 packet, to 2300 indicate that no further header follows a DSR header. 2302 9. Security Considerations 2304 This document does not specifically address security concerns. This 2305 document does assume that all nodes participating in the DSR protocol 2306 do so in good faith and without malicious intent to corrupt the 2307 routing ability of the network. In mission-oriented environments 2308 where all the nodes participating in the DSR protocol share a 2309 common goal that motivates their participation in the protocol, the 2310 communications between the nodes can be encrypted at the physical 2311 channel or link layer to prevent attack by outsiders. 2313 Appendix A. Location of DSR in the ISO Network Reference Model 2315 When designing DSR, we had to determine at what layer within 2316 the protocol hierarchy to implement ad hoc network routing. We 2317 considered two different options: routing at the link layer (ISO 2318 layer 2) and routing at the network layer (ISO layer 3). Originally, 2319 we opted to route at the link layer for several reasons: 2321 - Pragmatically, running the DSR protocol at the link layer 2322 maximizes the number of mobile nodes that can participate in 2323 ad hoc networks. For example, the protocol can route equally 2324 well between IPv4 [24], IPv6 [7], and IPX [27] nodes. 2326 - Historically [12, 13], DSR grew from our contemplation of 2327 a multi-hop propagating version of the Internet's Address 2328 Resolution Protocol (ARP) [22], as well as from the routing 2329 mechanism used in IEEE 802 source routing bridges [21]. These 2330 are layer 2 protocols. 2332 - Technically, we designed DSR to be simple enough that it could 2333 be implemented directly in the firmware inside wireless network 2334 interface cards [12, 13], well below the layer 3 software within 2335 a mobile node. We see great potential in this for DSR running 2336 inside a cloud of mobile nodes around a fixed base station, 2337 where DSR would act to transparently extend the coverage range 2338 to these nodes. Mobile nodes that would otherwise be unable 2339 to communicate with the base station due to factors such as 2340 distance, fading, or local interference sources could then reach 2341 the base station through their peers. 2343 Ultimately, however, we decided to specify and to implement [19] 2344 DSR as a layer 3 protocol, since this is the only layer at which we 2345 could realistically support nodes with multiple network interfaces of 2346 different types forming an ad hoc network. 2348 Appendix B. Implementation and Evaluation Status 2350 The DSR protocol has been implemented under the FreeBSD 2.2.7 2351 operating system running on Intel x86 platforms. FreeBSD is based 2352 on a variety of free software, including 4.4 BSD Lite from the 2353 University of California, Berkeley. For the environments in which 2354 we used it, this implementation is functionally equivalent to the 2355 protocol specified in this draft. 2357 During the 7 months from August 1998 to February 1999, we designed 2358 and implemented a full-scale physical testbed to enable the 2359 evaluation of ad hoc network performance in the field, in a actively 2360 mobile ad hoc network under realistic communication workloads. 2361 The last week of February and the first week of March included 2362 demonstrations of this testbed to a number of our sponsors and 2363 partners, including Lucent Technologies, Bell Atlantic, and DARPA. 2364 A complete description of the testbed is available as a Technical 2365 Report [19]. 2367 The software was ported to FreeBSD 3.3, and a preliminary version 2368 of Quality of Service (QoS) support was added. A demonstration of 2369 this modified version of DSR was presented in July 2000. Those QoS 2370 features are not included in this draft, and will be added later in a 2371 separate draft on top of the base protocol specified here. 2373 The DSR protocol has been extensively studied using simulation; we 2374 have implemented DSR in the ns-2 simulator [5, 18] and conducted 2375 evaluations of different caching strategies documented in this 2376 draft [9]. 2378 Several independent groups have also used DSR as a platform for their 2379 own research, or and as a basis of comparison between ad hoc network 2380 routing protocols. 2382 Acknowledgements 2384 The protocol described in this draft has been designed and developed 2385 within the Monarch Project, a research project at Rice University and 2386 Carnegie Mellon University which is developing adaptive networking 2387 protocols and protocol interfaces to allow truly seamless wireless 2388 and mobile node networking [14, 6]. 2390 The authors would like to acknowledge the substantial contributions 2391 of Josh Broch in helping to design, simulate, and implement the DSR 2392 protocol. Josh is currently on leave of absence from Carnegie Mellon 2393 University at AON Networks. We thank him for his contributions to 2394 earlier versions of this draft. 2396 We would also like to acknowledge the assistance of Robert V. Barron 2397 at Carnegie Mellon University. Bob ported our DSR implementation 2398 from FreeBSD 2.2.7 into FreeBSD 3.3. 2400 References 2402 [1] David F. Bantz and Frederic J. Bauchot. Wireless LAN design 2403 alternatives. IEEE Network, 8(2):43--53, March/April 1994. 2405 [2] Vaduvur Bharghavan, Alan Demers, Scott Shenker, and Lixia 2406 Zhang. MACAW: A media access protocol for wireless LAN's. In 2407 Proceedings of the ACM SIGCOMM '94 Conference, pages 212--225, 2408 August 1994. 2410 [3] Robert T. Braden, editor. Requirements for Internet 2411 hosts---communication layers. RFC 1122, October 1989. 2413 [4] Scott Bradner. Key words for use in RFCs to indicate 2414 requirement levels. RFC 2119, March 1997. 2416 [5] Josh Broch, David A. Maltz, David B. Johnson, Yih-Chun Hu, 2417 and Jorjeta Jetcheva. A performance comparison of multi-hop 2418 wireless ad hoc network routing protocols. In Proceedings of 2419 the Fourth Annual ACM/IEEE International Conference on Mobile 2420 Computing and Networking, pages 85--97, October 1998. 2422 [6] Carnegie Mellon University Monarch Project. CMU Monarch Project 2423 Home Page. Available at http://www.monarch.cs.cmu.edu/. 2425 [7] Stephen E. Deering and Robert M. Hinden. Internet Protocol 2426 version 6 (IPv6) specification. RFC 2460, December 1998. 2428 [8] Ralph Droms. Dynamic Host Configuration Protocol. RFC 2131, 2429 March 1997. 2431 [9] Yih-Chun Hu and David B. Johnson. Caching strategies in 2432 on-demand routing protocols for wireless ad hoc networks. In 2433 Proceedings of the Sixth Annual ACM International Conference on 2434 Mobile Computing and Networking, August 2000. 2436 [10] IEEE Computer Society LAN MAN Standards Committee. Wireless 2437 LAN Medium Access Control (MAC) and Physical Layer (PHY) 2438 Specifications, IEEE Std 802.11-1997. The Institute of 2439 Electrical and Electronics Engineers, New York, New York, 1997. 2441 [11] Per Johansson, Tony Larsson, Nicklas Hedman, Bartosz Mielczarek, 2442 and Mikael Degermark. Scenario-based performance analysis of 2443 routing protocols for mobile ad-hoc networks. In Proceedings 2444 of the Fifth Annual ACM/IEEE International Conference on Mobile 2445 Computing and Networking, pages 195--206, August 1999. 2447 [12] David B. Johnson. Routing in ad hoc networks of mobile hosts. 2448 In Proceedings of the IEEE Workshop on Mobile Computing Systems 2449 and Applications, pages 158--163, December 1994. 2451 [13] David B. Johnson and David A. Maltz. Dynamic Source Routing in 2452 ad hoc wireless networks. In Mobile Computing, edited by Tomasz 2453 Imielinski and Hank Korth, chapter 5, pages 153--181. Kluwer 2454 Academic Publishers, 1996. 2456 [14] David B. Johnson and David A. Maltz. Protocols for adaptive 2457 wireless and mobile networking. IEEE Personal Communications, 2458 3(1):34--42, February 1996. 2460 [15] John Jubin and Janet D. Tornow. The DARPA Packet Radio Network 2461 Protocols. Proceedings of the IEEE, 75(1):21--32, January 1987. 2463 [16] Phil Karn. MACA---A new channel access method for packet radio. 2464 In ARRL/CRRL Amateur Radio 9th Computer Networking Conference, 2465 pages 134--140, September 1990. 2467 [17] Gregory S. Lauer. Packet-radio routing. In Routing in 2468 Communications Networks, edited by Martha E. Steenstrup, 2469 chapter 11, pages 351--396. Prentice-Hall, Englewood Cliffs, 2470 New Jersey, 1995. 2472 [18] David A. Maltz, Josh Broch, Jorjeta Jetcheva, and David B. 2473 Johnson. The effects of on-demand behavior in routing protocols 2474 for multi-hop wireless ad hoc networks. IEEE Journal on 2475 Selected Areas of Communications, 17(8):1439--1453, August 1999. 2477 [19] David A. Maltz, Josh Broch, and David B. Johnson. Experiences 2478 designing and building a multi-hop wireless ad hoc network 2479 testbed. Technical Report CMU-CS-99-116, School of Computer 2480 Science, Carnegie Mellon University, Pittsburgh, Pennsylvania, 2481 March 1999. 2483 [20] David A. Maltz, Josh Broch, and David B. Johnson. Lessons from 2484 a full-scale multihop wireless ad hoc network testbed. IEEE 2485 Personal Communications, 8(1):8--15, February 2001. 2487 [21] Radia Perlman. Interconnections: Bridges and Routers. 2488 Addison-Wesley, Reading, Massachusetts, 1992. 2490 [22] David C. Plummer. An Ethernet address resolution protocol: 2491 Or converting network protocol addresses to 48.bit Ethernet 2492 addresses for transmission on Ethernet hardware. RFC 826, 2493 November 1982. 2495 [23] J. B. Postel, editor. Internet Control Message Protocol. 2496 RFC 792, September 1981. 2498 [24] J. B. Postel, editor. Internet Protocol. RFC 791, September 2499 1981. 2501 [25] J. B. Postel, editor. Transmission Control Protocol. RFC 793, 2502 September 1981. 2504 [26] Joyce K. Reynolds and Jon Postel. Assigned numbers. RFC 1700, 2505 October 1994. See also http://www.iana.org/numbers.html. 2507 [27] Paul Turner. NetWare communications processes. NetWare 2508 Application Notes, Novell Research, pages 25--91, September 2509 1990. 2511 Chair's Address 2513 The MANET Working Group can be contacted via its current chairs: 2515 M. Scott Corson Phone: +1 301 405-6630 2516 Institute for Systems Research Email: corson@isr.umd.edu 2517 University of Maryland 2518 College Park, MD 20742 2519 USA 2521 Joseph Macker Phone: +1 202 767-2001 2522 Information Technology Division Email: macker@itd.nrl.navy.mil 2523 Naval Research Laboratory 2524 Washington, DC 20375 2525 USA 2527 Authors' Addresses 2529 Questions about this document can also be directed to the authors: 2531 David B. Johnson Phone: +1 713 348-3063 2532 Rice University Fax: +1 713 348-5930 2533 Computer Science Department, MS 132 Email: dbj@cs.rice.edu 2534 6100 Main Street 2535 Houston, TX 77005-1892 2536 USA 2538 David A. Maltz Phone: +1 650 688-3128 2539 AON Networks Fax: +1 650 688-3119 2540 3045 Park Blvd. Email: dmaltz@cs.cmu.edu 2541 Palo Alto, CA 94306 2542 USA 2544 Yih-Chun Hu Phone: +1 412 268-3075 2545 Rice University Fax: +1 412 268-5576 2546 Computer Science Department, MS 132 Email: yihchun@cs.cmu.edu 2547 6100 Main Street 2548 Houston, TX 77005-1892 2549 USA 2551 Jorjeta G. Jetcheva Phone: +1 412 268-3053 2552 Carnegie Mellon University Fax: +1 412 268-5576 2553 Computer Science Department Email: jorjeta@cs.cmu.edu 2554 5000 Forbes Avenue 2555 Pittsburgh, PA 15213-3891 2556 USA