idnits 2.17.1 draft-ietf-manet-dsr-02.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: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. == No 'Intended status' indicated for this document; assuming Proposed Standard == It seems as if not all pages are separated by form feeds - found 0 form feeds but 52 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 8 instances of too long lines in the document, the longest one being 4 characters in excess of 72. == There are 1 instance of lines with non-RFC2606-compliant FQDNs in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- == The document seems to lack the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. (The document does seem to have the reference to RFC 2119 which the ID-Checklist requires). -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (25 June 1999) is 9064 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: '0' is mentioned on line 1139, but not defined -- Looks like a reference, but probably isn't: 'NumAddrs' on line 1747 -- Possible downref: Non-RFC (?) normative reference: ref. '3' ** Downref: Normative reference to an Informational RFC: RFC 2501 (ref. '4') ** Obsolete normative reference: RFC 2460 (ref. '5') (Obsoleted by RFC 8200) -- Possible downref: Non-RFC (?) normative reference: ref. '6' -- Possible downref: Non-RFC (?) normative reference: ref. '7' -- Possible downref: Non-RFC (?) normative reference: ref. '8' -- Possible downref: Non-RFC (?) normative reference: ref. '9' -- Possible downref: Non-RFC (?) normative reference: ref. '10' ** Obsolete normative reference: RFC 2002 (ref. '11') (Obsoleted by RFC 3220) -- Possible downref: Non-RFC (?) normative reference: ref. '12' ** Obsolete normative reference: RFC 793 (ref. '15') (Obsoleted by RFC 9293) -- Possible downref: Non-RFC (?) normative reference: ref. '16' ** Obsolete normative reference: RFC 1700 (ref. '17') (Obsoleted by RFC 3232) Summary: 9 errors (**), 0 flaws (~~), 5 warnings (==), 11 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 IETF MANET Working Group Josh Broch 2 INTERNET-DRAFT David B. Johnson 3 David A. Maltz 4 Carnegie Mellon University 5 25 June 1999 7 The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks 9 11 Status of This Memo 13 This document is an Internet-Draft and is in full conformance with 14 all provisions of Section 10 of RFC 2026 except that the right to 15 produce derivative works is not granted. 17 Internet-Drafts are working documents of the Internet Engineering 18 Task Force (IETF), its areas, and its working groups. Note 19 that other groups may also distribute working documents as 20 Internet-Drafts. 22 Internet-Drafts are draft documents valid for a maximum of six months 23 and may be updated, replaced, or obsoleted by other documents at 24 any time. It is inappropriate to use Internet-Drafts as reference 25 material or to cite them other than as "work in progress." 27 The list of current Internet-Drafts can be accessed at 28 http://www.ietf.org/ietf/1id-abstracts.txt 30 The list of Internet-Draft Shadow Directories can be accessed at 31 http://www.ietf.org/shadow.html. 33 Abstract 35 Dynamic Source Routing (DSR) is a routing protocol designed 36 specifically for use in mobile ad hoc networks. The protocol allows 37 nodes to dynamically discover a source route across multiple network 38 hops to any destination in the ad hoc network. When using source 39 routing, each packet to be routed carries in its header the complete, 40 ordered list of nodes through which the packet must pass. A key 41 advantage of source routing is that intermediate hops do not need 42 to maintain routing information in order to route the packets they 43 receive, since the packets themselves already contain all of the 44 necessary routing information. This, coupled with the dynamic, 45 on-demand nature of DSR's Route Discovery, completely eliminates the 46 need for periodic router advertisements and link status packets, 47 significantly reducing the overhead of DSR, especially during periods 48 when the network topology is stable and these packets serve only as 49 keep-alives. 51 Contents 53 Status of This Memo i 55 Abstract i 57 1. Introduction 1 59 2. Assumptions 1 61 3. Terminology 2 62 3.1. General Terms . . . . . . . . . . . . . . . . . . . . . . 2 63 3.2. Specification Language . . . . . . . . . . . . . . . . . 4 65 4. Protocol Overview 5 66 4.1. Route Discovery and Route Maintenance . . . . . . . . . . 5 67 4.2. Packet Forwarding . . . . . . . . . . . . . . . . . . . . 6 68 4.3. Multicast Routing . . . . . . . . . . . . . . . . . . . . 7 70 5. Conceptual Data Structures 7 71 5.1. Route Cache . . . . . . . . . . . . . . . . . . . . . . . 7 72 5.2. Route Request Table . . . . . . . . . . . . . . . . . . . 9 73 5.3. Send Buffer . . . . . . . . . . . . . . . . . . . . . . . 9 74 5.4. Retransmission Buffer . . . . . . . . . . . . . . . . . . 9 76 6. Packet Formats 11 77 6.1. Destination Options Headers . . . . . . . . . . . . . . . 11 78 6.1.1. DSR Route Request Option . . . . . . . . . . . . 12 79 6.2. Hop-by-Hop Options Headers . . . . . . . . . . . . . . . 14 80 6.2.1. DSR Route Reply Option . . . . . . . . . . . . . 15 81 6.2.2. DSR Route Error Option . . . . . . . . . . . . . 17 82 6.2.3. DSR Acknowledgment Option . . . . . . . . . . . . 18 83 6.3. DSR Routing Header . . . . . . . . . . . . . . . . . . . 20 85 7. Detailed Operation 23 86 7.1. Originating a Data Packet . . . . . . . . . . . . . . . . 23 87 7.2. Originating a Packet with a DSR Routing Header . . . . . 23 88 7.3. Processing a Routing Header . . . . . . . . . . . . . . . 24 89 7.4. Route Discovery . . . . . . . . . . . . . . . . . . . . . 25 90 7.4.1. Originating a Route Request . . . . . . . . . . . 25 91 7.4.2. Processing a Route Request Option . . . . . . . . 26 92 7.4.3. Generating Route Replies using the Route Cache . 27 93 7.4.4. Originating a Route Reply . . . . . . . . . . . . 28 94 7.4.5. Processing a Route Reply Option . . . . . . . . . 29 95 7.5. Route Maintenance . . . . . . . . . . . . . . . . . . . . 30 96 7.5.1. Using Network-Layer Acknowledgments . . . . . . . 30 97 7.5.2. Using Link Layer Acknowledgments . . . . . . . . 32 98 7.5.3. Originating a Route Error . . . . . . . . . . . . 32 99 7.5.4. Processing a Route Error Option . . . . . . . . . 33 100 7.5.5. Salvaging a Packet . . . . . . . . . . . . . . . 33 102 8. Optimizations 35 103 8.1. Leveraging the Route Cache . . . . . . . . . . . . . . . 35 104 8.1.1. Promiscuous Learning of Source Routes . . . . . . 35 105 8.2. Preventing Route Reply Storms . . . . . . . . . . . . . . 36 106 8.3. Piggybacking on Route Discoveries . . . . . . . . . . . . 37 107 8.4. Discovering Shorter Routes . . . . . . . . . . . . . . . 37 108 8.5. Rate Limiting the Route Discovery Process . . . . . . . . 38 109 8.6. Improved Handling of Route Errors . . . . . . . . . . . . 39 110 8.7. Increasing Scalability . . . . . . . . . . . . . . . . . 39 112 9. Constants 40 114 10. IANA Considerations 41 116 11. Security Considerations 42 118 Location of DSR Functions in the ISO Model 43 120 Implementation Status 44 122 Acknowledgments 45 124 References 46 126 Chair's Address 48 128 Authors' Addresses 49 129 1. Introduction 131 This document describes Dynamic Source Routing (DSR) [7, 8], a 132 protocol developed by the Monarch Project [9, 16] at Carnegie Mellon 133 University for routing packets in a mobile ad hoc network [4]. 135 Source routing is a routing technique in which the sender of a packet 136 determines the complete sequence of nodes through which to forward 137 the packet; the sender explicitly lists this route in the packet's 138 header, identifying each forwarding "hop" by the address of the next 139 node to which to transmit the packet on its way to the destination 140 node. 142 DSR offers a number of potential advantages over other routing 143 protocols for mobile ad hoc networks. First, DSR uses no periodic 144 routing messages of any kind (e.g., no router advertisements and no 145 link-level neighbor status messages), thereby significantly reducing 146 network bandwidth overhead, conserving battery power, reducing the 147 probability of packet collision, and avoiding the propagation of 148 potentially large routing updates throughout the ad hoc network. Our 149 Dynamic Source Routing protocol is able to adapt quickly to changes 150 such as node movement, yet requires no routing protocol overhead 151 during periods in which no such changes occur. 153 In addition, DSR has been designed to compute correct routes in 154 the presence of asymmetric (uni-directional) links. In wireless 155 networks, links may at times operate asymmetrically due to sources 156 of interference, differing radio or antenna capabilities, or the 157 intentional use of asymmetric communication technology such as 158 satellites. Due to the existence of asymmetric links, traditional 159 link-state or distance vector protocols may compute routes that do 160 not work. DSR, however, will always find a correct route even in the 161 presence of asymmetric links. 163 2. Assumptions 165 We assume that all nodes wishing to communicate with other nodes 166 within the ad hoc network are willing to participate fully in the 167 protocols of the network. In particular, each node participating in 168 the network should also be willing to forward packets for other nodes 169 in the network. 171 We refer to the minimum number of hops necessary for a packet to 172 reach from any node located at one extreme edge of the network to 173 another node located at the opposite extreme, as the diameter of the 174 network. We assume that the diameter of an ad hoc network will be 175 small (e.g., perhaps 5 or 10 hops), but may often be greater than 1. 177 Packets may be lost or corrupted in transmission on the wireless 178 network. A node receiving a corrupted packet can detect the error 179 and discard the packet. 181 We assume that nodes can enable promiscuous receive mode on their 182 wireless network interface hardware, causing the hardware to 183 deliver every received packet to the network driver software without 184 filtering based on link-layer destination address. Although we do 185 not require this facility, it is for example common in current LAN 186 hardware for broadcast media including wireless, and some of our 187 optimizations take advantage of its availability. Use of promiscuous 188 mode does increase the software overhead on the CPU, but we believe 189 that wireless network speeds are more the inherent limiting factor 190 to performance in current and future systems. We also believe 191 that portions of the protocol are also suitable for implementation 192 directly within a programmable network interface unit to avoid this 193 overhead on the CPU. 195 3. Terminology 197 3.1. General Terms 199 link 201 A communication facility or medium over which nodes can 202 communicate at the link layer, such as an Ethernet (simple or 203 bridged). A link is the layer immediately below IP. 205 interface 207 A node's attachment to a link. 209 prefix 211 A bit string that consists of some number of initial bits of an 212 address. 214 interface index 216 An 7-bit quantity which uniquely identifies an interface among 217 a given node's interfaces. Each node can assign interface 218 indices to its interfaces using any scheme it wishes. 220 The index IF_INDEX_MA is reserved for use by Mobile IP [11] 221 mobility agents (home or foreign agents) to indicate that they 222 believe they can reach a destination via a connected internet 223 infrastructure. The index IF_INDEX_ROUTER is reserved for 224 use by routers not acting as Mobile IP mobility agents to 225 indicate that they believe they can reach the destination via a 226 connected internet infrastructure. 228 The distinction between the index for mobility agents and 229 the index for routers, allows mobility agents to advertise 230 their existence ``for free''. A node that processes a routing 231 header listing the interface index IF_INDEX_MA, can then send 232 a unicast Agent Solicitation to the corresponding address in 233 the routing header to obtain complete information about the 234 mobility services being provided. 236 link-layer address 238 A link-layer identifier for an interface, such as IEEE 802 239 addresses on Ethernet links. 241 packet 243 An IP header plus payload. 245 piggybacking 247 Including two or more conceptually different types of data in 248 the same packet so that all data elements move through the 249 network together. 251 home address 253 An IP address that is assigned for an extended period of time 254 to a mobile node. It remains unchanged regardless of where 255 the node is attached to the Internet [11]. If a node has more 256 than one home address, it SHOULD select and use a single home 257 address when participating in the ad hoc network. 259 source route 261 A source route from a node S to some node D is an ordered list 262 of home addresses and interface indexes that contains all the 263 information that would be needed to forward a packet through 264 the ad hoc network. For each node that will transmit the 265 packet, the source route provides the index of the interface 266 over which the packet should be transmitted, and the address of 267 the node which is intended to receive the packet. 269 DSR Routing Headers as described in Section 6.3 use a more 270 compact encoding of the source route and do not explicitly list 271 address S in the Routing Header`, since it is carried as the IP 272 Source Address of the packet. 274 A source route is described as ``broken'' when the specific 275 path it describes through the network is not actually viable. 277 Route Discovery 279 The method in DSR by which a node S dynamically obtains a 280 source route to some node D that will be used by S to route 281 packets through the network to D. Performing a Route Discovery 282 involves sending one or more Route Request packets. 284 Route Maintenance 286 The process in DSR of monitoring the status of a source route 287 while in use, so that any link-failures along the source route 288 can be detected and the broken link removed from use. 290 3.2. Specification Language 292 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 293 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 294 document are to be interpreted as described in RFC 2119 [2]. 296 4. Protocol Overview 298 4.1. Route Discovery and Route Maintenance 300 A source routing protocol must solve two challenges, which DSR terms 301 Route Discovery and Route Maintenance. Route Discovery is the 302 mechanism whereby a node S wishing to send a packet to a destination 303 D obtains a source route to D. 305 Route Maintenance is the mechanism whereby S is able to detect, while 306 using a source route to D, if the network topology has changed such 307 that it can no longer use its route to D because a link along the 308 route no longer works. When Route Maintenance indicates a source 309 route is broken, S can attempt to use any other route it happens to 310 know to D, or can invoke Route Discovery again to find a new route. 312 To perform Route Discovery, the source node S link-layer broadcasts 313 a Route Request packet. Here, node S is termed the initiator of the 314 Route Discovery, and the node to which S is attempting to discover a 315 source route, say D, is termed the target of the Discovery. 317 Each node that hears the Route Request packet forwards a copy of the 318 Request, if appropriate, by adding its own address to a source route 319 being recorded in the Request packet and then rebroadcasting the 320 Route Request. 322 The forwarding of Route Requests is constructed so that copies of the 323 Request propagate hop-by-hop outward from the node initiating the 324 Route Discovery, until either the target of the Request is found or 325 until another node is found that can supply a route to the target. 327 The basic mechanism of forwarding Route Requests forwards the Request 328 if the node (1) is not the target of the Request, (2) is not already 329 listed in the recorded source route in this copy of the Request, and 330 (3) has not recently seen another Route Request packet belonging to 331 this same Route Discovery. A node can determine if it has recently 332 seen such a Route Request, since each Route Request packet contains 333 a unique identifier for this Route Discovery, generated by the 334 initiator of the Discovery. Each node maintains an LRU cache of the 335 unique identifier from each recently received Route Request. By not 336 propagating any copies of a Request after the first, the overhead of 337 forwarding additional copies that reach this node along different 338 paths is avoided. 340 In addition, the Time-to-Live field in the IP header of the packet 341 carrying the Route Request MAY be used to limit the scope over which 342 the Request will propagate, using the normal behavior of Time-to-Live 343 defined by IP [14, 1]. Additional optimizations on the handling and 344 forwarding of Route Requests are also used to further reduce the 345 Route Discovery overhead. 347 When the target of the Request (e.g., node D) receives the Route 348 Request, the recorded source route in the Request identifies the 349 sequence of hops over which this copy of the Request reached D. 350 Node D copies this recorded source route into a Route Reply packet 351 and sends this Route Reply back to the initiator of the Route Request 352 (e.g., node S). 354 All source routes learned by a node are kept in a Route Cache, which 355 is used to further reduce the cost of Route Discovery. When a node 356 wishes to send a packet, it examines its own Route Cache and performs 357 Route Discovery only if no suitable source route is found in its 358 Cache. 360 Further, when some intermediate node B receives a Route Request from 361 S for some target node D, B not equal D, B searches its own Route 362 Cache for a route to D. If B finds such a route, it might not have 363 to propagate the Route Request, but instead return a Route Reply to 364 node S based on the concatenation of the recorded source route from 365 S to B in the Route Request and the cached route from B to D. The 366 details of replying from a Route Cache in this way are discussed in 367 Section 8.1. 369 As a node overhears routes being used by others, either on data 370 packets or on control packets used by Route Discovery or Route 371 Maintenance, the node MAY insert those routes into its Route Cache, 372 leveraging the Route Discovery operations of the other nodes in 373 the network. Such route information MAY be learned either by 374 promiscuously snooping on packets or when forwarding packets. 376 4.2. Packet Forwarding 378 To represent a source route within a packet's header, DSR uses a 379 Routing Header similar to the Routing Header format specified for 380 IPv6, adapted to the needs of DSR and to the use of DSR in IPv4 (or 381 in IPv6 in the future). The DSR Routing Header uses a unique Routing 382 Type field value to distinguish it from the existing Type 0 Routing 383 Header defined within IPv6 [5]. 385 To forward a packet, a receiving node N simply processes the Routing 386 Header as specified in Section 7.3 and transmits the packet to 387 the next hop. If a forwarding error occurs along the link to the 388 next hop in the route, this node N sends a Route Error back to the 389 originator S of this packet informing S that this link is "broken". 390 If node N's Route Cache contains a different route to the destination 391 of the original packet, then the packet is salvaged using the new 392 source route (Section 7.5.5). Otherwise, the packet is dropped. 394 Each node overhearing or forwarding a Route Error packet also 395 removes from its Route Cache the link indicated to be broken, thereby 396 cleaning the stale cache data from the network. 398 4.3. Multicast Routing 400 At this time DSR does not support true multicasting. However, it 401 does support the controlled flooding of a data packet to all nodes in 402 the network that are within some number of hops of the originator. 403 While this mechanism does not support pruning of the broadcast 404 tree to conserve network resources, it can be used to distribute 405 information to nodes in the network. 407 When an application on a DSR node sends a packet to a multicast 408 address, DSR piggybacks the data from the packet inside a Route 409 Request packet targeted at the multicast address. The normal Route 410 Request distribution scheme described in Sections 4.1 and 7.4.2 411 will result in this packet being efficiently distributed to all 412 nodes in the network within the specified TTL of the originator. 413 The receiving nodes can then do destination address filtering on 414 the packet, discarding it if they do not wish to receive multicast 415 packets destined to this multicast address. 417 5. Conceptual Data Structures 419 In order to participate in the Dynamic Source Routing Protocol, a 420 node needs four conceptual data structures: a Route Cache, a Route 421 Request Table, a Send Buffer, and a Retransmission Buffer. These 422 data structures MAY be implemented in any manner consistent with the 423 external behavior described in this document. 425 5.1. Route Cache 427 All routing information needed by a node participating in an ad hoc 428 network using DSR is stored in a Route Cache. Each node in the 429 network maintains its own Route Cache. The node adds information 430 to the Cache as it learns of new links between nodes in the ad hoc 431 network, for example through packets carrying either a Route Reply or 432 a Routing Header. Likewise, the node removes information from the 433 cache as it learns existing links in the ad hoc network have broken, 434 for example through packets carrying a Route Error or through the 435 link-layer retransmission mechanism reporting a failure in forwarding 436 a packet to its next-hop destination. The Route Cache is indexed 437 logically by destination node address, and supports the following 438 operations: 440 void Insert(Route RT) 442 Inserts information extracted from source route RT into the 443 Route Cache. 445 Route Get(Node DEST) 447 Returns a source route from this node to DEST (if one is 448 known). 450 void Delete(Node FROM, Interface INDEX, Node TO) 452 Removes from the route cache any routes which assume that a 453 packet transmitted by node FROM over its interface with the 454 given INDEX will be received by node TO. 456 Each implementation MAY choose the cache replacement and cache search 457 strategies for its Route Cache that are most appropriate for its 458 particular network environment. For example, some environments may 459 choose to return the shortest route to a node (the shortest sequence 460 of hops), while others may select an alternate metric for the Get() 461 operation. 463 The Route Cache SHOULD support storing more than one source route for 464 each destination. 466 If there are multiple cached routes to a destination, the Route Get() 467 operation SHOULD prefer routes that do not traverse a hop with an 468 interface index of IF_INDEX_MA or IF_INDEX_ROUTER. This will prefer 469 routes that lead directly to the target node over routes that attempt 470 to reach the target via any internet infrastructure connected to the 471 ad hoc network. 473 If a node S is using a source route to some destination D that 474 includes intermediate node N, S SHOULD shorten the route to 475 destination D when it learns of a shorter route to node N than the 476 one that is listed as the prefix of its current route to D. 478 A node S using a source route to destination D through intermediate 479 node N, MAY shorten the source route if it learns of a shorter path 480 from node N to node D. 482 The Route Cache replacement policy SHOULD allow routes to be 483 categorized based upon "preference", where routes with a higher 484 preferences are less likely to be removed from the cache. For 485 example, a node could prefer routes for which it initiated a Route 486 Discovery over routes that it learned as the result of promiscuous 487 snooping on other packets. In particular, a node SHOULD prefer 488 routes that it is presently using over those that it is not. 490 5.2. Route Request Table 492 The Route Request Table is a collection of records about Route 493 Request packets that were recently originated or forwarded by this 494 node. The table is indexed by the home address of the target of the 495 route discovery. A record maintained on node S for node D contains 496 the following: 498 - The time that S last originated a Route Discovery for D. 500 - The remaining amount of time that S must wait before the next 501 attempt at a Route Discovery for D. 503 - The Time-to-live (TTL) field in the IP header of last Route 504 Request originated by S for D. 506 - A FIFO cache of the last ID_FIFO_SIZE Identification values from 507 Route Request packets targeted at node D that were forwarded by 508 this node. 510 Nodes SHOULD use an LRU policy to manage the entries of in their 511 Route Request Table. 513 ID_FIFO_SIZE MUST NOT be set to an unlimited value, since, in the 514 worst case, when a node crashes and reboots the first ID_FIFO_SIZE 515 Route Request packets it sends might appear to be duplicates to the 516 other nodes in the network. 518 5.3. Send Buffer 520 The Send Buffer of some node is a queue of packets that cannot be 521 transmitted by that node because it does not yet have a source 522 route to each respective packet's destination. Each packet in the 523 Send Buffer is stamped with the time that it is placed into the 524 Buffer, and SHOULD be removed from the Send Buffer and discarded 525 SEND_BUFFER_TIMEOUT seconds after initially being placed in the 526 Buffer. If necessary, a FIFO strategy SHOULD be used to evict 527 packets before they timeout to prevent the buffer from overflowing. 529 Subject to the rate limiting defined in Section 7.4, a Route 530 Discovery SHOULD be initiated as often as possible for the 531 destination address of any packets residing in the Send Buffer. 533 5.4. Retransmission Buffer 535 The Retransmission Buffer of a node is a queue of packets sent by 536 this node that are awaiting the receipt of an acknowledgment from the 537 next hop in the source route (Section 6.3). 539 For each packet in the Retransmission Buffer, a node maintains (1) a 540 count of the number of retransmissions and (2) the time of the last 541 retransmission. 543 Packets are removed from the buffer when an acknowledgment 544 is received, or when the number of retransmissions exceeds 545 DSR_MAXRXTSHIFT. In the later case, the removal of the packet from 546 the Retransmission Buffer SHOULD result in a Route Error being 547 returned to the initial source of the packet (Section 7.5). 549 6. Packet Formats 551 Dynamic Source Routing makes use of four options carrying control 552 information that can be piggybacked in any existing IP packet. 554 The mechanism used for these options is based on the design of the 555 Hop-by-Hop and Destination Options mechanisms in IPv6 [5]. The 556 ability to generate and process such options must be added to an IPv4 557 protocol stack. Specifically, the Protocol field in the IP header 558 is used to indicate that a Hop-by-Hop Options or Destination Options 559 extension header exists between the IP header and the remaining 560 portion of a packet's payload (such as a transport layer header). 561 The Next Header field in each extension header will then indicate the 562 type of header that follows it in a packet. 564 6.1. Destination Options Headers 566 The Destination Options header is used to carry optional information 567 that need be examined only by a packet's destination node(s). The 568 Destination Options header is identified by a Next Header (or 569 Protocol) value of 60 in the immediately preceding header, and has 570 the following format: 572 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 573 | Next Header | Hdr Ext Len | | 574 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 575 | | 576 . . 577 . Options . 578 . . 579 | | 580 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 582 Next Header 584 8-bit selector. Identifies the type of header immediately 585 following the Destination Options header. Uses the same values 586 as the IPv4 Protocol field [17]. 588 Hdr Ext Len 590 8-bit unsigned integer. Length of the Destination Options 591 header in 4-octet units, not including the first 8 octets. 593 Options 595 Variable-length field, of length such that the complete 596 Destination Options header is an integer multiple of 4 octets 597 long. Contains one or more TLV-encoded options. 599 The following destination option is used by the Dynamic Source 600 Routing protocol: 602 - DSR Route Request option (Section 6.1.1) 604 This destination option MUST NOT appear multiple times within a 605 single Destination Options header. 607 6.1.1. DSR Route Request Option 609 The DSR Route Request destination option is encoded in 610 type-length-value (TLV) format as follows: 612 0 1 2 3 613 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 614 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 615 | Option Type | Option Length | Identification | 616 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 617 | Target Address | 618 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 619 |C| IN Index[1] |C| IN Index[2] |C| IN Index[3] |C| IN Index[4] | 620 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 621 |C|OUT Index[1] |C|OUT Index[2] |C|OUT Index[3] |C|OUT Index[4] | 622 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 623 | Address[1] | 624 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 625 | Address[2] | 626 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 627 | Address[3] | 628 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 629 | Address[4] | 630 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 631 |C| IN Index[5] |C| IN Index[6] |C| IN Index[7] |C| IN Index[8]| 632 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 633 |C|OUT Index[5] |C|OUT Index[6] |C| OUT Index[7] |C|OUT Index[8]| 634 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 635 | Address[5] | 636 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 637 | ... | 638 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 640 IP fields: 642 Source Address 644 MUST be the home address of the node originating this packet. 645 Intermediate nodes that repropagate the request do not change 646 this field. 648 Destination Address 650 MUST be the limited broadcast address (255.255.255.255). 652 Hop Limit (TTL) 654 Can be varied from 1 to 255, for example to implement 655 expanding-ring searches. 657 Route Request fields: 659 Option Type 661 ???. A node that does not understand this option MUST discard 662 the packet and the Option Data may change en-route (the top 663 three bits are 011). 665 Option Length 667 8-bit unsigned integer. Length of the option, in octets, 668 excluding the Option Type and Option Length fields. 670 Identification 672 A unique value generated by the initiator (original sender) 673 of the Route Request. This value allows a recipient to 674 determine whether or not it has recently seen this a copy of 675 this Request; if it has, the packet is simply discarded. When 676 propagating a Route Request, this field MUST be copied from the 677 received copy of the Request being forwarded. 679 Target Address 681 The home address of the node that is the target of the Route 682 Request. 684 Change Interface (C) bit[1..n] 686 A flag associated with each interface index that indicates 687 whether or not the corresponding node repropagated the Request 688 over a different physical interface type than over which it 689 received the Request. 691 IN Index[1..n] 693 IN Index[i] is the index of the interface over which the node 694 indicated by Address[i] received the Route Request option. 695 These are used to record a reverse route from the target of 696 the request to the originator, over which a Route Reply MAY be 697 sent. 699 OUT Index[1..n] 701 OUT Index[i] is the interface index that the node indicated by 702 Address[i-1] used when rebroadcasting the Route Request option. 704 Address[1..n] 706 Address[i] is the home address of the ith hop recorded in the 707 Route Request option. 709 6.2. Hop-by-Hop Options Headers 711 The Hop-by-Hop Options header is used to carry optional information 712 that must be examined by every node along a packet's delivery path. 713 The Hop-by-Hop Options header is identified by a Next Header (or 714 Protocol) value of ??? in the IP header, and has the following 715 format: 717 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 718 | Next Header | Hdr Ext Len | | 719 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 720 | | 721 . . 722 . Options . 723 . . 724 | | 725 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 727 Next Header 729 8-bit selector. Identifies the type of header immediately 730 following the Hop-by-Hop Options header. Uses the same values 731 as the IPv4 Protocol field [17]. 733 Hdr Ext Len 735 8-bit unsigned integer. Length of the Hop-by-Hop Options 736 header in 4-octet units, not including the first 8 octets. 738 Options 740 Variable-length field, of length such that the complete 741 Hop-by-Hop Options header is an integer multiple of 4 octets 742 long. Contains one or more TLV-encoded options. 744 The following hop-by-hop options are used by the Dynamic Source 745 Routing protocol: 747 - DSR Route Reply option (Section 6.2.1) 749 - DSR Route Error option (Section 6.2.2) 751 - DSR Acknowledgment option (Section 6.2.3) 753 All of these destination options MAY appear one or more times within 754 a single Hop-by-Hop Options header. 756 6.2.1. DSR Route Reply Option 758 The DSR Route Reply hop-by-hop option is encoded in type-length-value 759 (TLV) format as follows: 761 0 1 2 3 762 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 763 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 764 | Option Type | Option Length | Reserved | 765 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 766 | Target Address | 767 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 768 |C|OUT Index[1] |C|OUT Index[2] |C|OUT Index[3] |C|OUT Index[4] | 769 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 770 | Address[1] | 771 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 772 | Address[2] | 773 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 774 | Address[3] | 775 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 776 | Address[4] | 777 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 778 |C|OUT Index[5] |C|OUT Index[6] |C|OUT Index[7] |C|OUT Index[8] | 779 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 780 | Address[5] | 781 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 782 | ... | 783 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 784 Option Type 786 ???. A node that does not understand this option should ignore 787 this option and continue processing the packet, and the Option 788 Data does not change en-route (the top three bits are 000). 790 Option Length 792 8-bit unsigned integer. Length of the option, in octets, 793 excluding the Option Type and Option Length fields. 795 Reserved 797 Sent as 0; ignored on reception. 799 Target Address 801 The home address of the node to which the Route Reply must be 802 delivered. 804 Change Interface (C) bit[1..n] 806 If the C bit associated with a node N is set, it implies N will 807 be forwarding the packet out a different interface than the one 808 over which it was received (i.e., the node sending the packet 809 to N should not expect a passive acknowledgment). 811 OUT Index[1..n] 813 OUT Index[i] is the interface index of the ith hop listed in 814 the Route Reply option. It denotes the interface that should 815 be used by Address[i-1] to reach Address[i] when using the 816 specified source route. 818 Address[1..n] 820 Address[i] is the home address of the ith hop listed in the 821 Route Reply option. 823 6.2.2. DSR Route Error Option 825 The DSR Route Error hop-by-hop option is encoded in type-length-value 826 (TLV) format as follows: 828 0 1 2 3 829 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 830 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 831 | Option Type | Option Length | Index | 832 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 833 | Error Source Address | 834 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 835 | Error Destination Address | 836 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 837 | Unreachable Node Address | 838 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 840 Option Type 842 ???. A node that does not understand this option should ignore 843 the option and continue processing the packet, and the Option 844 Data does not change en-route (the top three bits are 000). 846 Option Length 848 8-bit unsigned integer. Length of the option, in octets, 849 excluding the Option Type and Option Length fields. 851 Index 853 The interface index of the network interface over which the 854 node designated by Error Source Address tried to forward a 855 packet to the node designated by Unreachable Node Address. 857 Error Source Address 859 The home address of the node originating the Route Error (e.g., 860 the node that attempted to forward a packet and discovered the 861 link failure). 863 Error Destination Address 865 The home address of the node to which the Route Error must be 866 delivered (e.g, the node that generated the routing information 867 claiming that the hop Error Source Address to Unreachable Node 868 Address was a valid hop). 870 Unreachable Node Address 872 The home address of the node that was found to be unreachable 873 (the next hop neighbor to which the node at ``Error Source 874 Address'' was attempting to transmit the packet). 876 6.2.3. DSR Acknowledgment Option 878 The DSR Acknowledgment hop-by-hop option is encoded in 879 type-length-value (TLV) format as follows: 881 0 1 2 3 882 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 883 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 884 | Option Type | Option Length | 885 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 886 | Identification | 887 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 888 | ACK Source Address | 889 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 890 | ACK Destination Address | 891 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 892 | Data Source Address | 893 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 895 Option Type 897 ???. A node that does not understand this option should ignore 898 the option and continue processing the packet, and the Option 899 Data does not change en-route (the top three bits are 000). 901 Option Length 903 8-bit unsigned integer. Length of the option, in octets, 904 excluding the Option Type and Option Length fields. 906 Identification 908 A 32-bit value that when taken in conjunction with Data Source 909 Address, uniquely identifies the packet being acknowledged. 911 The Identification value is computed as ((ip_id << 16) | ip_off) 912 where ip_id is the value of the 16-bit Identification field in 913 the IP header of the packet being acknowledged, and ip_off is 914 the value of the 13-bit Fragment Offset field in the IP header 915 of the packet being acknowledged. 917 When constructing the Identification, ip_id and ip_off MUST be 918 in host byte-order. The entire Identification value MUST then 919 be converted to network byte-order before being placed in the 920 Acknowledgment option. 922 ACK Source Address 924 The home address of the node originating the Acknowledgment. 926 ACK Destination Address 928 The home address of the node to which the Acknowledgment must 929 be delivered. 931 Data Source Address 933 The IP Source Address of the packet being acknowledged. 935 6.3. DSR Routing Header 937 As specified for IPv6 [5], a Routing header is used by a source to 938 list one or more intermediate nodes to be ``visited'' on the way to 939 a packet's destination. This function is similar to IPv4's Loose 940 Source and Record Route option, but the Routing header does not 941 record the route taken as the packet is forwarded. The specific 942 processing steps required to implement the Routing header must be 943 added to an IPv4 protocol stack. The Routing header is identified by 944 a Next Header value of 43 in the immediately preceding header, and 945 has the following format: 947 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 948 | Next Header | Hdr Ext Len | Routing Type | Segments Left | 949 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 950 | | 951 . . 952 . type-specific data . 953 . . 954 | | 955 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 957 The type specific data for a Routing Header carrying a DSR Source 958 Route is: 960 0 1 2 3 961 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 962 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 963 |R|S| Reserved | 964 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 965 |C|OUT Index[1] |C|OUT Index[2] |C|OUT Index[3] |C|OUT Index[4] | 966 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 967 | Address[1] | 968 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 969 | Address[2] | 970 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 971 | Address[3] | 972 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 973 | Address[4] | 974 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 975 |C|OUT Index[5] |C|OUT Index[6] |C|OUT Index[7] |C|OUT Index[8] | 976 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 977 | Address[5] | 978 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 979 | ... | 980 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 981 Routing Header Fields: 983 Next Header 985 8-bit selector. Identifies the type of header immediately 986 following the Routing header. 988 Hdr Ext Len 990 8-bit unsigned integer. Length of the Routing header in 991 4-octet units, not including the first 8 octets. 993 Routing Type 995 ??? 997 Segments Left 999 Number of route segments remaining, i.e., number of explicitly 1000 listed intermediate nodes still to be visited before reaching 1001 the final destination. 1003 Type Specific Fields: 1005 Acknowledgment Request (R) 1007 The Acknowledgment Request (R) bit is set to request an 1008 explicit acknowledgment from the next hop. After processing 1009 the Routing Header, The IP Destination Address lists the 1010 address of the next hop. 1012 Salvaged Packet (S) 1014 The Salvaged Packet (S) bit indicates that this packet has been 1015 salvaged by an intermediate node, and thus that this Routing 1016 Header was generated by Address[1] and not the IP Source 1017 Address (Section 7.5.5). 1019 Reserved 1021 Sent as 0; ignored on reception. 1023 Change Interface (C) bit[1..n] 1025 If the C bit associated with a node N is set, it implies N will 1026 be forwarding the packet out a different interface than the one 1027 over which it was received (i.e., the node sending the packet 1028 to N should not expect a passive acknowledgment and MAY wish to 1029 set the R bit). 1031 OUT Index[1..n] 1033 Index[i] is the interface index that the node indicated 1034 by Address[i-1] must use when transmitting the packet to 1035 Address[i]. Index[1] indicates which interface the node 1036 indicated by the IP Source Address uses to transmit the packet. 1038 Address[1..n] 1040 Address[i] is the home address of the ith hop in the Routing 1041 header. 1043 Note that Address[1] is the first intermediate hop along the route. 1044 The address of the originating node is the IP Source Address. The 1045 only exception to this rule is for packets that are salvaged, as 1046 described in Section 7.5.5. A packet that has been salvaged has an 1047 alternate route placed on it by an intermediate node in the network, 1048 and in this case, the address of the originating node (the salvaging 1049 node) is Address[1]. Salvaged packets are indicated by setting the S 1050 bit in the DSR Routing header. 1052 7. Detailed Operation 1054 7.1. Originating a Data Packet 1056 When node A originates a packet, the following steps MUST be taken 1057 before transmitting the packet: 1059 1. If the destination address is a multicast address, piggyback the 1060 data packet on a Route Request targeting the multicast address. 1061 The following fields MUST be initialized as specified: 1063 IP.Source_Address = Home address of node A 1064 IP.Destination_Address = 255.255.255.255 1065 Request.Target_Address = Multicast destination address 1067 DONE. 1069 2. Otherwise, call Route_Cache.Get() to determine if there is a 1070 cached source route to the destination. 1072 3. If the cached route indicates that the destination is directly 1073 reachable over one hop, no Routing Header should be added to the 1074 packet. Initialize the following fields: 1076 IP.Source_Address = Home address of node A 1077 IP.Destination_Address = Home address of the Destination 1079 DONE. 1081 4. Otherwise, if the cached route indicates that multiple hops are 1082 required to reach the destination, insert a Routing Header into 1083 the packet as described in Section 7.2. DONE. 1085 5. Otherwise, if no cached route to the destination is found, insert 1086 the packet into the Send Buffer and initiate Route Discovery as 1087 described in Section 7.4. 1089 7.2. Originating a Packet with a DSR Routing Header 1091 When a node originates a packet with a Routing Header, the address 1092 of the first hop in the source route MUST be listed as the IP 1093 Destination Address as well as Address[1] in the Routing Header. 1094 The final destination of the packet is listed as the last hop 1095 in the Routing Header (Address[n]). At each intermediate hop i, 1096 Address[i] is copied into the IP Destination Address and the packet 1097 is retransmitted. 1099 For example, suppose node A originates a packet destined for node D 1100 that should pass through intermediate hops B and C. The packet MUST 1101 be initialized as follows: 1103 IP.Source_Address = Home address of node A 1104 IP.Destination_Address = Home address of node B 1105 RT.Segments_Left = 2 1106 RT.Out_Index[1] = Interface index used by A to reach B 1107 RT.Out_Index[2] = Interface index used by B to reach C 1108 RT.Out_Index[3] = Interface index used by C to reach D 1109 RT.Address[1] = Home address of node B 1110 RT.Address[2] = Home address of node C 1111 RT.Address[3] = Home address of node D 1113 7.3. Processing a Routing Header 1115 Excluding the exceptions listed here, a DSR Routing Header is 1116 processed using the same rules as outlined for Type 0 Routing Headers 1117 in IPv6 [5]. The Routing Header is only processed by the node whose 1118 address appears as the IP destination of the packet. The following 1119 additional rules apply to processing the type specific data of a DSR 1120 Source Route: 1122 Let 1124 SegLft = the value of Segments Left when the packet was received 1125 NumAddrs = the total number of addresses in the Routing Header 1127 1. The address of the next hop, Address[NumAddrs - SegLft + 1], 1128 is copied into the IP.Destination_Address of the packet. The 1129 existing IP.Destination_Address is NOT copied back into the 1130 Address list of the Routing Header. 1132 2. The interface used to transmit the packet to its next hop from 1133 this node MUST be the interface denoted by Index[NumAddrs - 1134 SegLft + 1]. 1136 3. If the Acknowledgment Request (R) bit is set, the node MUST 1137 transmit a packet containing the DSR Acknowledgment option to 1138 the previous hop, Address[NumAddrs - SegLft - 1], performing 1139 Route Discovery if necessary. (Address[0] is taken as the 1140 IP.Source_Address) 1142 4. Perform Route Maintenance by verifying that the packet was 1143 received by the next hop as described in Section 7.5. 1145 7.4. Route Discovery 1147 Route Discovery is the on-demand process by which nodes actively 1148 obtain source routes to destinations to which they are actively 1149 attempting to send packets. The destination node for which a 1150 Route Discovery is initiated is known as the "target" of the Route 1151 Discovery. A Route Discovery for a destination SHOULD NOT be 1152 initiated unless the initiating node has a packet in the Send Buffer 1153 requiring delivery to that destination. A Route Discovery for a 1154 given target node MUST NOT be initiated unless permitted by the 1155 rate-limiting information contained in the Route Request Table. 1156 After each Route Discovery attempt, the interval between successive 1157 Route Discoveries for this target must be doubled, up to a maximum of 1158 MAX_REQUEST_PERIOD. 1160 Route Discoveries for a multicast address SHOULD NOT be rate limited, 1161 and SHOULD always be permitted. 1163 7.4.1. Originating a Route Request 1165 The basic Route Discovery algorithm for a unicast destination is as 1166 follows: 1168 1. Originate a Route Request packet with the IP header Time-to-Live 1169 field initialized to 1. This type of Route Request is called a 1170 non-propagating Route Request and allows the originator of the 1171 Request to inexpensively query the route caches of each of its 1172 neighbors for a route to the destination. 1174 2. If a Route Reply is received in response to the non-propagating 1175 Request, use the returned source route to transmit all packets 1176 for the destination that are in the Send Buffer. DONE. 1178 3. Otherwise, if no Route Reply is received within 1179 RING0_REQUEST_TIMEOUT seconds, transmit a Route Request 1180 with the IP header Time-to-Live field initialized to 1181 MAX_ROUTE_LEN. This type of Route Request is called a propagating 1182 Route Request. Update the information in the Route Request 1183 Table, to double the amount of time before any subsequent Route 1184 Discovery attempt to this target. 1186 4. If no Route Reply is received within the time interval indicated 1187 by the Route Request Table, GOTO step 1. 1189 The Route Request option SHOULD be initialized as follows: 1191 IP.Source_Address = This node's home address 1192 IP.Destination_Address = 255.255.255.255 1193 Request.Target = Home address of intended destination 1194 Request.OUT_Index[1] = Index of interface used to transmit the Request 1196 The behavior of a node processing a packet containing both a Routing 1197 Header and a Route Request Destination option is unspecified. 1198 Packets SHOULD NOT contain both a Routing Header and a Route Request 1199 Destination option. [This is not exactly true: A Route Request 1200 option appearing in the second Destination Options header that IPv6 1201 allows after the Routing Header would probably do-what-you-mean, 1202 though we have not triple-checked it yet. Namely, it would allow the 1203 originator of a route discovery to unicast the request to some other 1204 node, where it would be released and begin the flood fill. We call 1205 this a Route Request Blossom since the unicast portion of the path 1206 looks like a stem on the blossoming flood-fill of the request.] 1208 Packets containing a Route Request Destination option SHOULD NOT be 1209 retransmitted, SHOULD NOT request an explicit DSR Acknowledgment by 1210 setting the R bit, SHOULD NOT expect a passive acknowledgment, and 1211 SHOULD NOT be placed in the Retransmission Buffer. The repeated 1212 transmission of packets containing a Route Request Destination option 1213 is controlled solely by the logic described in this section. 1215 7.4.2. Processing a Route Request Option 1217 When a node A receives a packet containing a Route Request option, 1218 the Route Request option is processed as follows: 1220 1. If Request.Target_Address matches the home address of this node, 1221 then the Route Request option contains a complete source route 1222 describing the path from the initiator of the Route Request to 1223 this node. 1225 (a) Send a Route Reply as described in Section 7.4.4. 1227 (b) Continue processing the packet in accordance with the Next 1228 Header value contained in the Destination Option extension 1229 header. DONE. 1231 2. Otherwise, if the combination (IP.Source_Address, 1232 Request.Identification) is found in the Route Request 1233 Table, then discard the packet, since this is a copy of a 1234 recently seen Route Request. DONE. 1236 3. Otherwise, if Request.Target_Address is a multicast address then: 1238 (a) If node A is a member of the multicast group indicated by 1239 Request.Target_Address, then create a copy of the packet, 1240 setting IP.Destination_Address = REQUEST.Target_Address, and 1241 continue processing the copy of the packet in accordance with 1242 the Next Header field of the Destination option. 1244 (b) If IP.TTL is non-zero, decrement IP.TTL, and retransmit the 1245 packet. DONE. 1247 (c) Otherwise, discard the packet. DONE. 1249 4. Otherwise, if the home address of node A is already listed in 1250 the Route Request (IP.Source_Address or Request.Address[]), then 1251 discard the packet. DONE. 1253 5. Let 1255 m = number of addresses currently in the Route Request option 1256 n = m + 1 1258 6. Otherwise, append the home address of node A to the Route Request 1259 option (Request.Address[n]). 1261 7. Set Request.IN_Index[n] = index of interface packet was received 1262 on. 1264 8. If a source route to Request.Target_Address is found in our Route 1265 Cache and the rules of Section 7.4.3 permit it, return a Cached 1266 Route Reply as described in Section 7.4.3. DONE. 1268 9. Otherwise, for each interface on which the node is configured to 1269 participate in a DSR ad hoc network: 1271 (a) Make a copy of the packet containing the Route Request. 1273 (b) Set Request.OUT_Index[n+1] = index of the interface. 1275 (c) If the outgoing interface is different from the incoming 1276 interface, then set the C bit on both Request.OUT_Index[n+1] 1277 and Request.IN_Index[n] 1279 (d) Link-layer re-broadcast the packet containing the Route 1280 Request on the interface jittered by T milliseconds, where 1281 T is a uniformly distributed, random number between 0 and 1282 BROADCAST_JITTER. DONE. 1284 7.4.3. Generating Route Replies using the Route Cache 1286 A node SHOULD use its Route Cache to avoid propagating a Route 1287 Request packet received from another node. In particular, suppose a 1288 node receives a Route Request packet for which it is not the target 1289 and which it does not discard based on the logic of Section 7.4.2. 1290 If the node has a Route Cache entry for the target of the Request, 1291 it SHOULD append this cached route to the accumulated route record 1292 in the packet and return this route in a Route Reply packet to 1293 the initiator without propagating (re-broadcasting) the Route 1294 Request. Thus, for example, if node F in the example network shown 1295 in Figure 7.4.3 needs to send a packet to node D, it will initiate 1296 a Route Discovery and broadcast a Route Request packet. If this 1297 broadcast is received by node A, node A can simply return a Route 1298 Reply packet to F containing the complete route to D consisting of 1299 the sequence of hops: A, B, C, and D. 1301 Before transmitting a Route Reply packet that was generated using 1302 information from its Route Cache, a node MUST verify that: 1304 1. The resulting route contains no loops. 1306 2. The node issuing the Route Reply is listed in the route that it 1307 specifies in its Reply. This increases the probability that the 1308 route is valid, since the node in question should have received 1309 a Route Error if this route stopped working. Additionally, this 1310 requirement means that a Route Error traversing the route will 1311 pass through the node that issued the Reply based on stale cache 1312 data, which is critical for ensuring stale data is removed from 1313 caches in a timely manner. Without this requirement, the next 1314 Route Discovery initiated by the original requester might also be 1315 contaminated by a Route Reply from this node containing the same 1316 stale route. 1318 7.4.4. Originating a Route Reply 1320 Let REQPacket denote a packet received by node A that 1321 contains a Route Request option which lists node A as the 1322 REQPacket.Request.Target_Address. Let REPPacket be a packet 1323 transmitted by node A that contains a corresponding Route Reply. The 1324 Route Reply option transmitted in response to a Route Request MUST be 1325 initialized as follows: 1327 B->C->D 1328 +---+ +---+ +---+ +---+ 1329 | A |---->| B |---->| C |---->| D | 1330 +---+ +---+ +---+ +---+ 1332 +---+ 1333 | F | +---+ 1334 +---+ | E | 1335 +---+ 1337 Figure 1: An example network where A knows a 1338 route to D via B and C. 1340 1. If REQPacket.Request.Address[] does not contain any hops, then 1341 node A is only a single hop from the originator of the Route 1342 Request. Build a Route Reply packet as follows: 1344 REPPacket.IP.Source_Address = REQPacket.Request.Target_Address 1345 REPPacket.Reply.Target = REQPacket.IP.Source_Address 1346 REPPacket.Reply.OUT_Index[1] = REQPacket.Request.OUT_index[1] 1347 REPPacket.Reply.OUT_C_bit[1] = REQPacket.Request.OUT_C_bit[1] 1348 REPPacket.Reply.Address[1] = The home address of node A 1350 GOTO step 3. 1352 2. Otherwise, build a Route Reply packet as follows: 1354 REPPacket.IP.Source_Address = The home address of node A 1355 REPPacket.Reply.Target = REQPacket.IP.Source_Address 1356 REPPacket.Reply.OUT_Index[1..n]= 1357 REQPacket.Request.OUT_index[1..n] 1358 REPPacket.Reply.OUT_C_bit[1..n]= 1359 REQPacket.Request.OUT_C_bit[1..n] 1360 REPPacket.Reply.Address[1..n] = REQPacket.Request.Address[1..n] 1362 3. Send the Route Reply jittered by T milliseconds, where T 1363 is a uniformly distributed random number between 0 and 1364 BROADCAST_JITTER. DONE. 1366 If sending a Route Reply packet to the originator of the Route 1367 Request requires performing a Route Discovery, the Route Reply 1368 hop-by-hop option MUST be piggybacked on the packet that contains the 1369 Route Request. This prevents a loop wherein the target of the new 1370 Route Request (which was itself the originator of the original Route 1371 Request) must do another Route Request in order to return its Route 1372 Reply. 1374 If sending the Route Reply to the originator of the Route Request 1375 does not require performing Route Discovery, a node SHOULD send a 1376 unicast Route Reply in response to every Route Request targeted at 1377 it. 1379 7.4.5. Processing a Route Reply Option 1381 Upon receipt of a Route Reply, a node should extract the source route 1382 (Target_Address, OUT_Index[1]:Address[1], .. OUT_Index[n]:Address[n] 1383 ) and insert this route into its Route Cache. All the packets in the 1384 Send Buffer SHOULD be checked to see whether the information in the 1385 Reply allows them to be sent immediately. 1387 7.5. Route Maintenance 1389 Route Maintenance requires that whenever a node transmits a data 1390 packet, a Route Reply, or a Route Error, it must verify that the next 1391 hop (indicated by the Destination IP Address) correctly receives the 1392 packet. 1394 If the sender cannot verify that the next hop received the packet, it 1395 MUST decide that its link to the next hop is broken and MUST send a 1396 Route Error to the node responsible for generating the Routing Header 1397 that contains the broken link (Section 7.5.3). 1399 The following ways may be used to verify that the next hop correctly 1400 received a packet: 1402 - The receipt of a passive acknowledgment (Section 7.5.1). 1404 - The receipt of an explicitly requested acknowledgment 1405 (Section 7.5.1). 1407 - By the presence of positive feedback from the link layer 1408 indicating that the packet was acknowledged by the next hop 1409 (Section 7.5.2). 1411 - By the absence of explicit failure notification from the link 1412 layer that provides reliable hop-by-hop delivery such as MACAW or 1413 802.11 (Section 7.5.2). 1415 Nodes MUST NOT perform Route Maintenance for packets containing a 1416 Route Request option or packets containing only an Acknowledgment 1417 option. Sending Acknowledgments for packets containing only 1418 an Acknowledgment option would create an infinite loop whereby 1419 acknowledgments would be sent for acknowledgments. Acknowledgments 1420 should be always sent for packets containing a Routing Header with 1421 the R bit set (e.g., packets which contain only an Acknowledgment 1422 and a Routing Header for which the last forwarding hop requires an 1423 explicit acknowledgment of receipt by the final destination). 1425 7.5.1. Using Network-Layer Acknowledgments 1427 For link layers that do not provide explicit failure notification, 1428 the following steps SHOULD be used by a node A to perform Route 1429 Maintenance. 1431 When receiving a packet: 1433 - If the packet contains a Routing Header with the R bit set, send 1434 an explicit acknowledgment as described in Section 7.3. 1436 - If the packet does not contain a Routing Header, the node MUST 1437 transmit a packet containing the DSR Acknowledgment option 1438 to the previous hop as indicated by the IP.Source_Address. 1439 Since the receiving node is the final destination, there 1440 will be no opportunity for the originator to obtain a 1441 passive acknowledgment, and the receiving node must infer the 1442 originator's request for an explicit acknowledgment. 1444 When sending a packet: 1446 1. Before sending a packet, insert a copy of the packet into the 1447 Retransmission Buffer and update the information maintained about 1448 this packet in the Retransmission Buffer. 1450 2. If after processing the Routing Header, RH.Segments_Left is equal 1451 to 0, then node A MUST set the Acknowledgment Request (R) bit in 1452 the Routing Header before transmitting the packet over its final 1453 hop. 1455 3. If after processing the Routing Header and copying 1456 RH.Address[n] to IP.Destination_Address, node A determines that 1457 RH.OUT_C_bit[n+1] is set, then node A MUST set the Acknowledgment 1458 Request (R) bit in the Routing Header before transmitting the 1459 packet (since the C bit was set during Route Discovery by the 1460 node now listed as the IP.Destination_Address to indicate that 1461 it will propagate the packet out a different interface, and that 1462 node A will not receive a passive acknowledgment). 1464 4. Set the retransmission timer for the packet in the Retransmission 1465 Buffer. 1467 5. Transmit the packet. 1469 6. If a passive or explicit acknowledgment is received before the 1470 retransmission timer expires, then remove the packet from the 1471 Retransmission Buffer and disable the retransmission timer. 1472 DONE. 1474 7. Otherwise, when the Retransmission Timer expires, remove the 1475 packet from the Retransmission Buffer. 1477 8. If DSR_MAXRXTSHIFT transmissions have been done, then attempt 1478 to salvage the packet (Section 7.5.5). Also, generate a Route 1479 Error. DONE. 1481 9. GOTO step 1. 1483 7.5.2. Using Link Layer Acknowledgments 1485 If explicit failure notifications are provided by the link layer, 1486 then all packets are assumed to be correctly received by the next hop 1487 and a Route Error is sent only when a explicit failure notification 1488 is made from the link layer. 1490 Nodes receiving a packet without a Routing Header do not need to send 1491 an explicit Acknowledgment to the packet's originator, since the 1492 link layer will notify the originator if the packet was not received 1493 properly. 1495 7.5.3. Originating a Route Error 1497 If the next hop of a packet is found to be unreachable as described 1498 in Section 7.5, a Route Error packet (Section 6.2.2) MUST be returned 1499 to the node whose cache generated the information used to route the 1500 packet. 1502 When a node A generates a Route Error for packet P, it MUST 1503 initialize the fields in the Route Error as follows: 1505 Error.Source_Address = Home address of node A 1506 Error.Unreachable_Address = Home address of the unreachable node 1508 - If the packet contains a DSR Routing Header and the S bit is NOT 1509 set, the packet has been forwarded without the need for salvaging 1510 up to this point. 1512 Error.Destination_Address = P.IP.Source_Address 1514 - Otherwise, if the packet contains a DSR Routing Header and the S 1515 bit IS set, the packet has been salvaged by an intermediate node, 1516 and thus this Routing Header was placed there by the salvaging 1517 node. 1519 Error.Destination_Address = P.RoutingHeader.Address[1] 1521 - Otherwise, if the packet does not contain a DSR Routing Header, 1522 the packet must have been originated by this node A. 1524 Error.Destination_Address = Home address of node A 1526 Send the packet containing the Route Error to Error.Destination_Address, 1527 performing Route Discovery if necessary. 1529 As an optimization, Route Errors that are discovered by the 1530 packet's originator (such that Error.Source_Address is equal to 1531 Error.Destination_Address) SHOULD be processed internally. Such 1532 processing should invoke all the steps that would be taken if a Route 1533 Error option was created, transmitted, received, and processed, 1534 but an actual packet containing a Route Error option SHOULD NOT be 1535 transmitted. 1537 7.5.4. Processing a Route Error Option 1539 Upon receipt of a Route Error via any mechanism, a node 1540 SHOULD remove any route from its Route Cache that uses the hop 1541 (Error.Source_Address, Error.Index to Error.Unreachable_Address). 1542 This includes all Route Errors overheard, and those processed 1543 internally as described in Section 7.5.3. 1545 When the node identified by Error.Destination_Address receives 1546 the Route Error, it SHOULD verify that the source route 1547 responsible for delivering the Route Error includes the same 1548 hops as the working prefix of the original packet's source route 1549 (Error.Destination_Address to Error.Source_Address). If any 1550 hop listed in the working prefix is not included in the Route 1551 Error's source route, then the originator SHOULD forward the Route 1552 Error back along the working prefix (Error.Destination_Address to 1553 Error.Source_Address) so that each node along the working prefix will 1554 remove the invalid route from its Route Cache. 1556 If the node processing a Route Error option discovers its home 1557 address is Error.Destination_Address and the packet contains 1558 additional Route Error option(s) later on the inside of the Hop 1559 by Hop options header, we call the additional Route Errors nested 1560 Route Errors. The node MUST deliver the first nested Route Error 1561 to Nested_Error.Destination_Address, performing Route Discovery if 1562 needed. It does this by removing the Route Error option listing 1563 itself as the Error.Destination_Address, finding the first nested 1564 Route Error option, and originating the remaining packet to 1565 Nested_Error.Destination_Address. This mechanism allows for the 1566 proper handling of Route Errors that are discovered while delivering 1567 a Route Error. 1569 7.5.5. Salvaging a Packet 1571 When node A attempts to salvage a packet originated at node S and 1572 destined for node D, it MUST perform the following steps: 1574 1. Generate and send a Route Error to A as explained in 1575 Section 7.5.3. 1577 2. Call Route_Cache.Get() to determine if it has a cached source 1578 route to the packet's ultimate destination D (which is the last 1579 Address listed in the Routing Header). 1581 3. If node A does not have a cached route for node D, it MUST 1582 discard the packet. DONE. 1584 4. Otherwise, let Salvage_Address[1] through Salvage_Address[m] be 1585 the sequence of hops returned from the Route Cache. Initialize 1586 the following fields in the packet's header: 1588 RT.Segments_Left = m - 2; 1589 RT.S = 1 1590 RT.Address[1] = Home address of Node A 1591 RT.Address[2] = Salvage.Address[1] 1592 ... 1593 RT.Address[n] = Salvage.Address[m] 1595 The IP Source Address of the packet MUST remain unchanged. When the 1596 Routing Header in the outgoing packet is processed, RT.Address[2], 1597 will be copied to the IP Destination Address field. 1599 8. Optimizations 1601 A number of optimizations can be added to the basic operation of 1602 Route Discovery and Route Maintenance as described in Sections 7.4 1603 and 7.5 that can reduce the number of overhead packets and improve 1604 the average efficiency of the routes used on data packets. This 1605 section discusses some of those optimizations. 1607 8.1. Leveraging the Route Cache 1609 The data in a node's Route Cache may be stored in any format, but 1610 the active routes in its cache form a tree of routes, rooted at 1611 this node, to other nodes in the ad hoc network. For example, the 1612 illustration below shows an ad hoc network of six mobile nodes, in 1613 which mobile node A has earlier completed a Route Discovery for 1614 mobile node D and has cached a route to D through B and C: 1616 B->C->D 1617 +---+ +---+ +---+ +---+ 1618 | A |---->| B |---->| C |---->| D | 1619 +---+ +---+ +---+ +---+ 1621 +---+ 1622 | F | +---+ 1623 +---+ | E | 1624 +---+ 1626 Since nodes B and C are on the route to D, node A also learns the 1627 route to both of these nodes from its Route Discovery for D. If A 1628 later performs a Route Discovery and learns the route to E through B 1629 and C, it can represent this in its Route Cache with the addition of 1630 the single new hop from C to E. If A then learns it can reach C in a 1631 single hop (without needing to go through B), A SHOULD use this new 1632 route to C to also shorten the routes to D and E in its Route Cache. 1634 8.1.1. Promiscuous Learning of Source Routes 1636 A node can add entries to its Route Cache any time it learns a new 1637 route. In particular, when a node forwards a data packet as an 1638 intermediate hop on the route in that packet, the forwarding node is 1639 able to observe the entire route in the packet. Thus, for example, 1640 when any intermediate node B forwards packets from A to D, B SHOULD 1641 add the source route information from that packet's Routing Header 1642 to its own Route Cache. If a node forwards a Route Reply packet, it 1643 SHOULD also add the source route information from the route record 1644 being returned in the Route Reply, to its own Route Cache. 1646 In addition, since all wireless network transmissions at the physical 1647 layer are inherently broadcast, it may be possible for a node to 1648 configure its network interface into promiscuous receive mode, such 1649 that the node is able to receive all packets without link layer 1650 address filtering. In this case, the node MAY add to its Route Cache 1651 the route information from any packet it can overhear. 1653 8.2. Preventing Route Reply Storms 1655 The ability for nodes to reply to a Route Request not targeted at 1656 them by using their Route Caches can result in a Route Reply storm. 1657 If a node broadcasts a Route Request for a node that its neighbors 1658 have in their Route Caches, each neighbor may attempt to send a 1659 Route Reply, thereby wasting bandwidth and increasing the rate 1660 of collisions in the area. For example, in the network shown in 1661 Section 8.1, if both node A and node B receive F's Route Request, 1662 they will both attempt to reply from their Route Caches. Both will 1663 send their Replies at about the same time since they receive the 1664 broadcast at about the same time. Particularly when more than the 1665 two mobile nodes in this example are involved, these simultaneous 1666 replies from the mobile nodes receiving the broadcast may create 1667 packet collisions among some or all of these replies and may cause 1668 local congestion in the wireless network. In addition, it will 1669 often be the case that the different replies will indicate routes 1670 of different lengths. For example, A's Route Reply will indicate a 1671 route to D that is one hop longer than that in B's reply. 1673 For interfaces which can promiscuously listen to the channel, mobile 1674 nodes SHOULD use the following algorithm to reduce the number of 1675 simultaneous replies by slightly delaying their Route Reply: 1677 1. Pick a delay period 1679 d = H * (h - 1 + r) 1681 where h is the length in number of network hops for the route 1682 to be returned in this node's Route Reply, r is a random number 1683 between 0 and 1, and H is a small constant delay to be introduced 1684 per hop. 1686 2. Delay transmitting the Route Reply from this node for a period 1687 of d. 1689 3. Within the delay period, promiscuously receive all packets at 1690 this node. If a packet is received by this node during the delay 1691 period that is addressed to the target of this Route Discovery 1692 (the target is the final destination address for the packet, 1693 through any sequence of intermediate hops), and if the length of 1694 the route on this packet is less than h, then cancel the delay 1695 timer and do not transmit the Route Reply from this node; this 1696 node may infer that the initiator of this Route Discovery has 1697 already received a Route Reply, giving an equally good or better 1698 route. 1700 8.3. Piggybacking on Route Discoveries 1702 As described in Section 4.1, when one node needs to send a packet 1703 to another, if the sender does not have a route cached to the 1704 destination node, it must initiate a Route Discovery, buffering the 1705 original packet until the Route Reply is returned. The delay for 1706 Route Discovery and the total number of packets transmitted can be 1707 reduced by allowing data to be piggybacked on Route Request packets. 1708 Since some Route Requests may be propagated widely within the ad hoc 1709 network, though, the amount of data piggybacked must be limited. We 1710 currently use piggybacking when sending a Route Reply or a Route 1711 Error packet, since both are naturally small in size. Small data 1712 packets such as the initial SYN packet opening a TCP connection [15] 1713 could easily be piggybacked. 1715 One problem, however, arises when piggybacking on Route Request 1716 packets. If a Route Request is received by a node that replies 1717 to the request based on its Route Cache without propagating the 1718 Request (Section 8.1), the piggybacked data will be lost if the node 1719 simply discards the Route Request. In this case, before discarding 1720 the packet, the node must construct a new packet containing the 1721 piggybacked data from the Route Request packet. The source route 1722 in this packet MUST be constructed to appear as if the new packet 1723 had been sent by the initiator of the Route Discovery and had been 1724 forwarded normally to this node. Hence, the first portion of the 1725 route is taken from the accumulated route record in the Route Request 1726 packet and the remainder of the route is taken from this node's Route 1727 Cache. The sender address in the packet MUST also be set to the 1728 initiator of the Route Discovery. Since the replying node will be 1729 unable to correctly recompute an Authentication header for the split 1730 off piggybacked data, data covered by an Authentication header SHOULD 1731 NOT be piggybacked on Route Request packets. 1733 8.4. Discovering Shorter Routes 1735 Once a route between a packet source and a destination has been 1736 discovered, the basic DSR protocol MAY continue to use that route 1737 for all traffic from the source to the destination as long as 1738 it continues to work, even if the nodes move such that a shorter 1739 route becomes possible. In many cases, the basic Route Maintenance 1740 procedure will discover the shorter route, since if a node moves 1741 enough to create a shorter route, it will likely also move out of 1742 transmission range of at least one hop on the existing route. 1744 Furthermore, when a data packet is received as the result of 1745 operating in promiscuous receive mode, the node checks if the Routing 1746 Header packet contains its address in the unprocessed portion of the 1747 source route (Address[NumAddrs - SegLft] to Address[NumAddrs]). If 1748 so, the node knows that packet could bypass the unprocessed hops 1749 preceding it in the source route. The node then sends what is called 1750 a gratuitous Route Reply message to the packet's source, giving it 1751 the shorter route without these hops. 1753 The following algorithm describes how a node A should process packets 1754 with an IP.Destination_Address not addressed to A or the IP broadcast 1755 address or a multicast address that are received as a result of A 1756 being in promiscuous receive mode: 1758 1. If the packet is not a data packet containing a Routing Header, 1759 drop the packet. DONE. 1761 2. If the home address of this node does not appear in the portion 1762 of the source route that has not yet been processed (indicated by 1763 Segments Left), then drop the packet. DONE. 1765 3. Otherwise, the node B that just transmitted the packet (indicated 1766 by Address[NumAddrs - SegLft - 1]) can communicate directly with 1767 this node A. Create a Route Reply. The Route Reply MUST list 1768 the entire source route contained in the received packet with the 1769 exception of the intermediate nodes between node B and node A. 1771 4. Send this gratuitous Route Reply to the node listed as the 1772 IP.Source_Address of the received packet. If Route Discovery 1773 is required it MAY be initiated, or the gratuitous Route Reply 1774 packet MAY be dropped. 1776 8.5. Rate Limiting the Route Discovery Process 1778 One common error condition that must be handled in an ad hoc network 1779 is the case in which the network effectively becomes partitioned. 1780 That is, two nodes that wish to communicate are not within 1781 transmission range of each other, and there are not enough other 1782 mobile nodes between them to form a sequence of hops through which 1783 they can forward packets. If a new Route Discovery was initiated 1784 for each packet sent by a node in this situation, a large number of 1785 unproductive Route Request packets would be propagated throughout the 1786 subset of the ad hoc network reachable from this node. In order to 1787 reduce the overhead from such Route Discoveries, we use exponential 1788 back-off to limit the rate at which new Route Discoveries may be 1789 initiated from any node for the same target. If the node attempts to 1790 send additional data packets to this same node more frequently than 1791 this limit, the subsequent packets SHOULD be buffered in the Send 1792 Buffer until a Route Reply is received, but it MUST NOT initiate a 1793 new Route Discovery until the minimum allowable interval between new 1794 Route Discoveries for this target has been reached. This limitation 1795 on the maximum rate of Route Discoveries for the same target is 1796 similar to the mechanism required by Internet nodes to limit the rate 1797 at which ARP requests are sent to any single IP address [1]. 1799 8.6. Improved Handling of Route Errors 1801 All nodes SHOULD process all of the Route Error messages they 1802 receive, regardless of whether the node is the destination of 1803 the Route Error, is forwarding the Route Error, or promiscuously 1804 overhears the Route Error. 1806 Since a Route Error packet names both ends of the hop that is no 1807 longer valid, any of the nodes receiving the error packet may update 1808 their Route Caches to reflect the fact that the two nodes indicated 1809 in the packet can no longer directly communicate. A node receiving 1810 a Route Error packet simply searches its Route Cache for any routes 1811 using this hop. For each such route found, the route is effectively 1812 truncated at this hop. All nodes on the route before this hop are 1813 still reachable on this route, but subsequent nodes are not. 1815 An experimental optimization to improve the handling of errors is 1816 to support the caching of "negative" information in a node's Route 1817 Cache. The goal of negative information is to record that a given 1818 route was tried and found not to work, so that if the same route 1819 is discovered again shortly after the failure, the Route Cache can 1820 ignore or downgrade the metric of the failed route. 1822 We have not currently included this caching of negative information 1823 in our simulations, since it appears to be unnecessary if nodes also 1824 promiscuously receive Route Error packets. 1826 8.7. Increasing Scalability 1828 We recently designed and began experimenting with ways to integrate 1829 ad hoc networks with the Internet and with Mobile IP [11]. In 1830 addition to this, we are also exploring ways to increase the 1831 scalablity of ad hoc networks by taking advantage of their 1832 cooperative nature and the fact that some hierarchy can be imposed 1833 on an ad hoc network, just be assigning addresses to the nodes in a 1834 reasonable way. These ideas are described in a workshop paper [3]. 1836 9. Constants 1838 BROADCAST_JITTER 10 milliseconds 1840 MAX_ROUTE_LEN 15 nodes 1842 Interface Indexes 1843 IF_INDEX_INVALID 0x7F 1844 IF_INDEX_MA 0x7E 1845 IF_INDEX_ROUTER 0x7D 1847 Route Cache 1848 ROUTE_CACHE_TIMEOUT 300 seconds 1850 Send Buffer 1851 SEND_BUFFER_TIMEOUT 30 seconds 1853 Request Table 1854 MAX_REQUEST_ENTRIES 32 nodes 1855 MAX_REQUEST_IDS 8 identifiers 1856 MAX_REQUEST_REXMT 16 retransmissions 1857 MAX_REQUEST_PERIOD 10 seconds 1858 REQUEST_PERIOD 500 milliseconds 1859 RING0_REQUEST_TIMEOUT 30 milliseconds 1861 Retransmission Buffer 1862 DSR_RXMT_BUFFER_SIZE 50 packets 1864 Retransmission Timer 1865 DSR_MAXRXTSHIFT 2 1867 10. IANA Considerations 1869 This document proposes the use of the Destination Options header and 1870 the Hop-by-Hop Options header, originally defined for IPv6, in IPv4. 1871 The Next Header values indicating these two extension headers thus 1872 must be reserved within the IPv4 Protocol number space. 1874 Furthermore, this document defines four new types of destination 1875 options, each of which must be assigned an Option Type value: 1877 - The DSR Route Request option, described in Section 6.1.1 1879 - The DSR Route Reply option, described in Section 6.2.1 1881 - The DSR Route Error option, described in Section 6.2.2 1883 - The DSR Acknowledgment option, described in Section 6.2.3 1885 DSR also requires a routing header Routing Type be allocated for the 1886 DSR Source Route defined in Section 6.3. 1888 In IPv4, we require two new protocol numbers be issued to identify 1889 the next header as either an IPv6-style destination option, or an 1890 IPv6-style routing header. Other protocols can make use of these 1891 protocol numbers as nodes that support them will processes any 1892 included destination options or routing headers according to the 1893 normal IPv6 semantics. 1895 11. Security Considerations 1897 This document does not specifically address security concerns. This 1898 document does assume that all nodes participating in the DSR protocol 1899 do so in good faith and with out malicious intent to corrupt the 1900 routing ability of the network. In mission-oriented environments 1901 where all the nodes participating in the DSR protocol share a 1902 common goal that motivates their participation in the protocol, the 1903 communications between the nodes can be encrypted at the physical 1904 channel or link layer to prevent attack by outsiders. 1906 Location of DSR Functions in the ISO Reference Model 1908 When designing DSR, we had to determine at what level within the 1909 protocol hierarchy to implement source routing. We considered two 1910 different options: routing at the link layer (ISO layer 2) and 1911 routing at the network layer (ISO layer 3). Originally, we opted to 1912 route at the link layer for the following reasons: 1914 - Pragmatically, running the DSR protocol at the link layer 1915 maximizes the number of mobile nodes that can participate in 1916 ad hoc networks. For example, the protocol can route equally 1917 well between IPv4 [14], IPv6 [5], and IPX [6] nodes. 1919 - Historically, DSR grew from our contemplation of a multi-hop ARP 1920 protocol [7, 8] and source routing bridges [12]. ARP [13] is a 1921 layer 2 protocol. 1923 - Technically, we designed DSR to be simple enough that that it 1924 could be implemented directly in network interface cards, well 1925 below the layer 3 software within a mobile node. We see great 1926 potential for DSR running between clouds of mobile nodes around 1927 fixed base stations. DSR would act to transparently fill in the 1928 coverage gaps between base stations. Mobile nodes that would 1929 otherwise be unable to communicate with the base station due to 1930 factors such as distance, fading, or local interference sources 1931 could then reach the base station through their peers. 1933 Ultimately, however, we decided to specify DSR as a layer 3 protocol 1934 since this is the only layer at which we could realistically support 1935 nodes with multiple interfaces of different types. 1937 Implementation Status 1939 We have implemented Dynamic Source Routing (DSR) under the 1940 FreeBSD 2.2.7 operating system running on Intel x86 platforms. 1941 FreeBSD is based on a variety of free software, including 4.4 BSD 1942 Lite from the University of California, Berkeley. 1944 During the 7 months from August 1998 to February 1999, we designed 1945 and implemented a full-scale physical testbed to enable the 1946 evaluation of ad hoc network performance in the field. The last 1947 week of February and the first week of March included demonstrations 1948 of this testbed to a number of our sponsors and partners, including 1949 Lucent Technologies, Bell Atlantic, and DARPA. A complete description 1950 of the testbed is available as a Technical Report [10]. 1952 Acknowledgments 1954 The protocol described in this draft has been designed within 1955 the CMU Monarch Project, a research project at Carnegie Mellon 1956 University which is developing adaptive networking protocols and 1957 protocol interfaces to allow truly seamless wireless and mobile node 1958 networking [9, 16]. The current members of the CMU Monarch Project 1959 include: 1961 - Josh Broch 1963 - Yih-Chun Hu 1965 - Jorjeta Jetcheva 1967 - David B. Johnson 1969 - Qifa Ke 1971 - David A. Maltz 1973 References 1975 [1] Robert Braden, editor. Requirements for Internet Hosts -- 1976 Communication Layers. RFC 1122, October 1989. 1978 [2] Scott Bradner. Key words for use in RFCs to Indicate 1979 Requirement Levels. RFC 2119, March 1997. 1981 [3] Josh Broch, David A. Maltz, and David B. Johnson. Supporting 1982 Hierarchy and Heterogeneous Interfaces in Multi-Hop Wireless Ad 1983 Hoc Networks. In Proceedings of I-SPAN'99, Perth, Australia, 1984 June 1999. To appear. 1986 [4] Scott Corson and Joseph Macker. Mobile Ad Hoc Networking 1987 (MANET): Routing Protocol Performance Issues and Evaluation 1988 Considerations. RFC 2501, January 1999. 1990 [5] S. Deering and R. Hinden. Internet Protocol, version 6 (IPv6) 1991 Specification. RFC 2460, December 1998. 1993 [6] IPX Router Specification. Novell Part Number 107-000029-001, 1994 Document Version 1.30, March 1996. 1996 [7] David B. Johnson. Routing in Ad Hoc Networks of Mobile Hosts. 1997 In Proceedings of the IEEE Workshop on Mobile Computing Systems 1998 and Applications, pages 158--163, December 1994. 2000 [8] David B. Johnson and David A. Maltz. Dynamic Source Routing in 2001 Ad Hoc Wireless Networks. In Mobile Computing, edited by Tomasz 2002 Imielinski and Hank Korth, chapter 5, pages 153--181. Kluwer 2003 Academic Publishers, 1996. 2005 [9] David B. Johnson and David A. Maltz. Protocols for Adaptive 2006 Wireless and Mobile Networking. IEEE Personal Communications, 2007 3(1):34--42, February 1996. 2009 [10] David A. Maltz, Josh Broch, and David B. Johnson. Experiences 2010 Designing and Building a Multi-Hop Wireless Ad Hoc Network 2011 Testbed. Technical Report 99-116, School of Computer Science, 2012 Carnegie Mellon University, March 1999. 2014 [11] Charles Perkins, editor. IP Mobility Support. RFC 2002, 2015 October 1996. 2017 [12] Radia Perlman. Interconnections: Bridges and Routers. 2018 Addison-Wesley, Reading, Massachusetts, 1992. 2020 [13] David C. Plummer. An Ethernet address resolution protocol: 2021 Or converting network protocol addresses to 48.bit Ethernet 2022 addresses for transmission on Ethernet hardware. RFC 826, 2023 November 1982. 2025 [14] J. Postel. Internet Protocol. RFC 791, September 1981. 2027 [15] J. Postel. Transmission Control Protocol. RFC 793, September 2028 1981. 2030 [16] The CMU Monarch Project. http://www.monarch.cs.cmu.edu/. 2031 Computer Science Department, Carnegie Mellon University. 2033 [17] J. Reynolds and J. Postel. Assigned Numbers. RFC 1700, October 2034 1994. 2036 Chair's Address 2038 The Working Group can be contacted via its current chairs: 2040 M. Scott Corson 2041 Institute for Systems Research 2042 University of Maryland 2043 College Park, MD 20742 2044 USA 2046 Phone: +1 301 405-6630 2047 Email: corson@isr.umd.edu 2049 Joseph Macker 2050 Information Technology Division 2051 Naval Research Laboratory 2052 Washington, DC 20375 2053 USA 2055 Phone: +1 202 767-2001 2056 Email: macker@itd.nrl.navy.mil 2058 Authors' Addresses 2060 Questions about this document can also be directed to the authors: 2062 Josh Broch 2063 Carnegie Mellon University 2064 Electrical and Computer Engineering 2065 5000 Forbes Avenue 2066 Pittsburgh, PA 15213-3890 2067 USA 2069 Phone: +1 412 268-3056 2070 Fax: +1 412 268-7196 2071 Email: broch@cs.cmu.edu 2073 David B. Johnson 2074 Carnegie Mellon University 2075 Computer Science Department 2076 5000 Forbes Avenue 2077 Pittsburgh, PA 15213-3891 2078 USA 2080 Phone: +1 412 268-7399 2081 Fax: +1 412 268-5576 2082 Email: dbj@cs.cmu.edu 2084 David A. Maltz 2085 Carnegie Mellon University 2086 Computer Science Department 2087 5000 Forbes Avenue 2088 Pittsburgh, PA 15213-3891 2089 USA 2091 Phone: +1 412 268-3621 2092 Fax: +1 412 268-5576 2093 Email: dmaltz@cs.cmu.edu