idnits 2.17.1 draft-ietf-manet-dsr-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-23) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 10 instances of too long lines in the document, the longest one being 5 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 (8 December 1998) is 9268 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 1140, but not defined -- Looks like a reference, but probably isn't: 'NumAddrs' on line 1746 == Outdated reference: A later version (-02) exists of draft-ietf-manet-issues-00 ** Downref: Normative reference to an Informational draft: draft-ietf-manet-issues (ref. '3') -- Possible downref: Non-RFC (?) normative reference: ref. '5' -- Possible downref: Non-RFC (?) normative reference: ref. '6' -- Possible downref: Non-RFC (?) normative reference: ref. '7' -- Possible downref: Non-RFC (?) normative reference: ref. '8' ** Obsolete normative reference: RFC 2002 (ref. '9') (Obsoleted by RFC 3220) -- Possible downref: Non-RFC (?) normative reference: ref. '10' ** Obsolete normative reference: RFC 793 (ref. '13') (Obsoleted by RFC 9293) -- Possible downref: Non-RFC (?) normative reference: ref. '14' ** Obsolete normative reference: RFC 1700 (ref. '15') (Obsoleted by RFC 3232) Summary: 11 errors (**), 0 flaws (~~), 5 warnings (==), 9 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 IETF MANET Working Group Josh Broch 3 INTERNET-DRAFT David B. Johnson 4 David A. Maltz 5 Carnegie Mellon University 6 8 December 1998 8 The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks 10 12 Status of This Memo 14 This document is a submission to the Mobile Ad-hoc Networks (manet) 15 Working Group of the Internet Engineering Task Force (IETF). 16 Comments should be submitted to the Working Group mailing list at 17 "manet@itd.nrl.navy.mil". Distribution of this memo is unlimited. 19 This document is an Internet-Draft. Internet-Drafts are working 20 documents of the Internet Engineering Task Force (IETF), its areas, 21 and its working groups. Note that other groups may also distribute 22 working documents as Internet-Drafts. 24 Internet-Drafts are draft documents valid for a maximum of six months 25 and may be updated, replaced, or obsoleted by other documents at 26 any time. It is inappropriate to use Internet-Drafts as reference 27 material or to cite them other than as "work in progress." 29 To view the entire list of current Internet-Drafts, please check 30 the "1id-abstracts.txt" listing contained in the Internet-Drafts 31 Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net (Europe), 32 munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or 33 ftp.isi.edu (US West Coast). 35 Abstract 37 Dynamic Source Routing (DSR) is a routing protocol designed 38 specifically for use in mobile ad hoc networks. The protocol allows 39 nodes to dynamically discover a source route across multiple network 40 hops to any destination in the ad hoc network. When using source 41 routing, each packet to be routed carries in its header the complete, 42 ordered list of nodes through which the packet must pass. A key 43 advantage of source routing is that intermediate hops do not need 44 to maintain routing information in order to route the packets they 45 receive, since the packets themselves already contain all of the 46 necessary routing information. This, coupled with the dynamic, 47 on-demand nature of DSR's Route Discovery, completely eliminates the 48 need for periodic router advertisements and link status packets, 49 significantly reducing the overhead of DSR, especially during periods 50 when the network topology is stable and these packets serve only as 51 keep-alives. 53 Contents 55 Status of This Memo i 57 Abstract i 59 1. Introduction 1 61 2. Assumptions 1 63 3. Terminology 2 64 3.1. General Terms . . . . . . . . . . . . . . . . . . . . . . 2 65 3.2. Specification Language . . . . . . . . . . . . . . . . . 4 67 4. Protocol Overview 5 68 4.1. Route Discovery and Route Maintenance . . . . . . . . . . 5 69 4.2. Packet Forwarding . . . . . . . . . . . . . . . . . . . . 6 70 4.3. Multicast Routing . . . . . . . . . . . . . . . . . . . . 7 72 5. Conceptual Data Structures 7 73 5.1. Route Cache . . . . . . . . . . . . . . . . . . . . . . . 7 74 5.2. Route Request Table . . . . . . . . . . . . . . . . . . . 9 75 5.3. Send Buffer . . . . . . . . . . . . . . . . . . . . . . . 9 76 5.4. Retransmission Buffer . . . . . . . . . . . . . . . . . . 9 78 6. Packet Formats 11 79 6.1. Destination Options Headers . . . . . . . . . . . . . . . 11 80 6.1.1. DSR Route Request Option . . . . . . . . . . . . 12 81 6.2. Hop-by-Hop Options Headers . . . . . . . . . . . . . . . 14 82 6.2.1. DSR Route Reply Option . . . . . . . . . . . . . 15 83 6.2.2. DSR Route Error Option . . . . . . . . . . . . . 17 84 6.2.3. DSR Acknowledgment Option . . . . . . . . . . . . 18 85 6.3. DSR Routing Header . . . . . . . . . . . . . . . . . . . 20 87 7. Detailed Operation 23 88 7.1. Originating a Data Packet . . . . . . . . . . . . . . . . 23 89 7.2. Originating a Packet with a DSR Routing Header . . . . . 23 90 7.3. Processing a Routing Header . . . . . . . . . . . . . . . 24 91 7.4. Route Discovery . . . . . . . . . . . . . . . . . . . . . 25 92 7.4.1. Originating a Route Request . . . . . . . . . . . 25 93 7.4.2. Processing a Route Request Option . . . . . . . . 26 94 7.4.3. Generating Route Replies using the Route Cache . 27 95 7.4.4. Originating a Route Reply . . . . . . . . . . . . 28 96 7.4.5. Processing a Route Reply Option . . . . . . . . . 29 97 7.5. Route Maintenance . . . . . . . . . . . . . . . . . . . . 30 98 7.5.1. Using Network-Layer Acknowledgments . . . . . . . 30 99 7.5.2. Using Link Layer Acknowledgments . . . . . . . . 32 100 7.5.3. Originating a Route Error . . . . . . . . . . . . 32 101 7.5.4. Processing a Route Error Option . . . . . . . . . 33 102 7.5.5. Salvaging a Packet . . . . . . . . . . . . . . . 33 104 8. Optimizations 35 105 8.1. Leveraging the Route Cache . . . . . . . . . . . . . . . 35 106 8.1.1. Promiscuous Learning of Source Routes . . . . . . 35 107 8.2. Preventing Route Reply Storms . . . . . . . . . . . . . . 36 108 8.3. Piggybacking on Route Discoveries . . . . . . . . . . . . 37 109 8.4. Discovering Shorter Routes . . . . . . . . . . . . . . . 37 110 8.5. Rate Limiting the Route Discovery Process . . . . . . . . 38 111 8.6. Improved Handling of Route Errors . . . . . . . . . . . . 39 113 9. Constants 40 115 10. IANA Considerations 41 117 11. Security Considerations 42 119 Location of DSR Functions in the ISO Model 43 121 Implementation Status 44 123 Acknowledgments 45 125 References 46 127 Chair's Address 48 129 Authors' Addresses 49 130 1. Introduction 132 This document describes Dynamic Source Routing (DSR) [6, 7], a 133 protocol developed by the Monarch Project [8, 14] at Carnegie Mellon 134 University for routing packets in a mobile ad hoc network [3]. 136 Source routing is a routing technique in which the sender of a packet 137 determines the complete sequence of nodes through which to forward 138 the packet; the sender explicitly lists this route in the packet's 139 header, identifying each forwarding "hop" by the address of the next 140 node to which to transmit the packet on its way to the destination 141 node. 143 DSR offers a number of potential advantages over other routing 144 protocols for mobile ad hoc networks. First, DSR uses no periodic 145 routing messages of any kind (e.g., no router advertisements and no 146 link-level neighbor status messages), thereby significantly reducing 147 network bandwidth overhead, conserving battery power, reducing the 148 probability of packet collision, and avoiding the propagation of 149 potentially large routing updates throughout the ad hoc network. Our 150 Dynamic Source Routing protocol is able to adapt quickly to changes 151 such as node movement, yet requires no routing protocol overhead 152 during periods in which no such changes occur. 154 In addition, DSR has been designed to compute correct routes in 155 the presence of asymmetric (uni-directional) links. In wireless 156 networks, links may at times operate asymmetrically due to sources 157 of interference, differing radio or antenna capabilities, or the 158 intentional use of asymmetric communication technology such as 159 satellites. Due to the existence of asymmetric links, traditional 160 link-state or distance vector protocols may compute routes that do 161 not work. DSR, however, will always find a correct route even in the 162 presence of asymmetric links. 164 2. Assumptions 166 We assume that all nodes wishing to communicate with other nodes 167 within the ad hoc network are willing to participate fully in the 168 protocols of the network. In particular, each node participating in 169 the network should also be willing to forward packets for other nodes 170 in the network. 172 We refer to the minimum number of hops necessary for a packet to 173 reach from any node located at one extreme edge of the network to 174 another node located at the opposite extreme, as the diameter of the 175 network. We assume that the diameter of an ad hoc network will be 176 small (e.g., perhaps 5 or 10 hops), but may often be greater than 1. 178 Packets may be lost or corrupted in transmission on the wireless 179 network. A node receiving a corrupted packet can detect the error 180 and discard the packet. 182 We assume that nodes can enable promiscuous receive mode on their 183 wireless network interface hardware, causing the hardware to 184 deliver every received packet to the network driver software without 185 filtering based on link-layer destination address. Although we do 186 not require this facility, it is for example common in current LAN 187 hardware for broadcast media including wireless, and some of our 188 optimizations take advantage of its availability. Use of promiscuous 189 mode does increase the software overhead on the CPU, but we believe 190 that wireless network speeds are more the inherent limiting factor 191 to performance in current and future systems. We also believe 192 that portions of the protocol are also suitable for implementation 193 directly within a programmable network interface unit to avoid this 194 overhead on the CPU. 196 3. Terminology 198 3.1. General Terms 200 link 202 A communication facility or medium over which nodes can 203 communicate at the link layer, such as an Ethernet (simple or 204 bridged). A link is the layer immediately below IP. 206 interface 208 A node's attachment to a link. 210 prefix 212 A bit string that consists of some number of initial bits of an 213 address. 215 interface index 217 An 7-bit quantity which uniquely identifies an interface among 218 a given node's interfaces. Each node can assign interface 219 indices to its interfaces using any scheme it wishes. 221 The index IF_INDEX_MA is reserved for use by Mobile IP [9] 222 mobility agents (home or foreign agents) to indicate that they 223 believe they can reach a destination via a connected internet 224 infrastructure. The index IF_INDEX_ROUTER is reserved for 225 use by routers not acting as Mobile IP mobility agents to 226 indicate that they believe they can reach the destination via a 227 connected internet infrastructure. 229 The distinction between the index for mobility agents and 230 the index for routers, allows mobility agents to advertise 231 their existence ``for free''. A node that processes a routing 232 header listing the interface index IF_INDEX_MA, can then send 233 a unicast Agent Solicitation to the corresponding address in 234 the routing header to obtain complete information about the 235 mobility services being provided. 237 link-layer address 239 A link-layer identifier for an interface, such as IEEE 802 240 addresses on Ethernet links. 242 packet 244 An IP header plus payload. 246 piggybacking 248 Including two or more conceptually different types of data in 249 the same packet so that all data elements move through the 250 network together. 252 home address 254 An IP address that is assigned for an extended period of time 255 to a mobile node. It remains unchanged regardless of where 256 the node is attached to the Internet [9]. If a node has more 257 than one home address, it SHOULD select and use a single home 258 address when participating in the ad hoc network. 260 source route 262 A source route from a node S to some node D is an ordered list 263 of home addresses and interface indexes that contains all the 264 information that would be needed to forward a packet through 265 the ad hoc network. For each node that will transmit the 266 packet, the source route provides the index of the interface 267 over which the packet should be transmitted, and the address of 268 the node which is intended to receive the packet. 270 DSR Routing Headers as described in Section 6.3 use a more 271 compact encoding of the source route and do not explicitly list 272 address S in the Routing Header`, since it is carried as the IP 273 Source Address of the packet. 275 A source route is described as ``broken'' when the specific 276 path it describes through the network is not actually viable. 278 Route Discovery 280 The method in DSR by which a node S dynamically obtains a 281 source route to some node D that will be used by S to route 282 packets through the network to D. Performing a Route Discovery 283 involves sending one or more Route Request packets. 285 Route Maintenance 287 The process in DSR of monitoring the status of a source route 288 while in use, so that any link-failures along the source route 289 can be detected and the broken link removed from use. 291 3.2. Specification Language 293 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 294 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 295 document are to be interpreted as described in RFC 2119 [2]. 297 4. Protocol Overview 299 4.1. Route Discovery and Route Maintenance 301 A source routing protocol must solve two challenges, which DSR terms 302 Route Discovery and Route Maintenance. Route Discovery is the 303 mechanism whereby a node S wishing to send a packet to a destination 304 D obtains a source route to D. 306 Route Maintenance is the mechanism whereby S is able to detect, while 307 using a source route to D, if the network topology has changed such 308 that it can no longer use its route to D because a link along the 309 route no longer works. When Route Maintenance indicates a source 310 route is broken, S can attempt to use any other route it happens to 311 know to D, or can invoke Route Discovery again to find a new route. 313 To perform Route Discovery, the source node S link-layer broadcasts 314 a Route Request packet. Here, node S is termed the initiator of the 315 Route Discovery, and the node to which S is attempting to discover a 316 source route, say D, is termed the target of the Discovery. 318 Each node that hears the Route Request packet forwards a copy of the 319 Request, if appropriate, by adding its own address to a source route 320 being recorded in the Request packet and then rebroadcasting the 321 Route Request. 323 The forwarding of Route Requests is constructed so that copies of the 324 Request propagate hop-by-hop outward from the node initiating the 325 Route Discovery, until either the target of the Request is found or 326 until another node is found that can supply a route to the target. 328 The basic mechanism of forwarding Route Requests forwards the Request 329 if the node (1) is not the target of the Request, (2) is not already 330 listed in the recorded source route in this copy of the Request, and 331 (3) has not recently seen another Route Request packet belonging to 332 this same Route Discovery. A node can determine if it has recently 333 seen such a Route Request, since each Route Request packet contains 334 a unique identifier for this Route Discovery, generated by the 335 initiator of the Discovery. Each node maintains an LRU cache of the 336 unique identifier from each recently received Route Request. By not 337 propagating any copies of a Request after the first, the overhead of 338 forwarding additional copies that reach this node along different 339 paths is avoided. 341 In addition, the Time-to-Live field in the IP header of the packet 342 carrying the Route Request MAY be used to limit the scope over which 343 the Request will propagate, using the normal behavior of Time-to-Live 344 defined by IP [12, 1]. Additional optimizations on the handling and 345 forwarding of Route Requests are also used to further reduce the 346 Route Discovery overhead. 348 When the target of the Request (e.g., node D) receives the Route 349 Request, the recorded source route in the Request identifies the 350 sequence of hops over which this copy of the Request reached D. 351 Node D copies this recorded source route into a Route Reply packet 352 and sends this Route Reply back to the initiator of the Route Request 353 (e.g., node S). 355 All source routes learned by a node are kept in a Route Cache, which 356 is used to further reduce the cost of Route Discovery. When a node 357 wishes to send a packet, it examines its own Route Cache and performs 358 Route Discovery only if no suitable source route is found in its 359 Cache. 361 Further, when some intermediate node B receives a Route Request from 362 S for some target node D, B not equal D, B searches its own Route 363 Cache for a route to D. If B finds such a route, it might not have 364 to propagate the Route Request, but instead return a Route Reply to 365 node S based on the concatenation of the recorded source route from 366 S to B in the Route Request and the cached route from B to D. The 367 details of replying from a Route Cache in this way are discussed in 368 Section 8.1. 370 As a node overhears routes being used by others, either on data 371 packets or on control packets used by Route Discovery or Route 372 Maintenance, the node MAY insert those routes into its Route Cache, 373 leveraging the Route Discovery operations of the other nodes in 374 the network. Such route information MAY be learned either by 375 promiscuously snooping on packets or when forwarding packets. 377 4.2. Packet Forwarding 379 To represent a source route within a packet's header, DSR uses a 380 Routing Header similar to the Routing Header format specified for 381 IPv6, adapted to the needs of DSR and to the use of DSR in IPv4 (or 382 in IPv6 in the future). The DSR Routing Header uses a unique Routing 383 Type field value to distinguish it from the existing Type 0 Routing 384 Header defined within IPv6 [4]. 386 To forward a packet, a receiving node N simply processes the Routing 387 Header as specified in Section 7.3 and transmits the packet to 388 the next hop. If a forwarding error occurs along the link to the 389 next hop in the route, this node N sends a Route Error back to the 390 originator S of this packet informing S that this link is "broken". 391 If node N's Route Cache contains a different route to the destination 392 of the original packet, then the packet is salvaged using the new 393 source route (Section 7.5.5). Otherwise, the packet is dropped. 395 Each node overhearing or forwarding a Route Error packet also 396 removes from its Route Cache the link indicated to be broken, thereby 397 cleaning the stale cache data from the network. 399 4.3. Multicast Routing 401 At this time DSR does not support true multicasting. However, it 402 does support the controlled flooding of a data packet to all nodes in 403 the network that are within some number of hops of the originator. 404 While this mechanism does not support pruning of the broadcast 405 tree to conserve network resources, it can be used to distribute 406 information to nodes in the network. 408 When an application on a DSR node sends a packet to a multicast 409 address, DSR piggybacks the data from the packet inside a Route 410 Request packet targeted at the multicast address. The normal Route 411 Request distribution scheme described in Sections 4.1 and 7.4.2 412 will result in this packet being efficiently distributed to all 413 nodes in the network within the specified TTL of the originator. 414 The receiving nodes can then do destination address filtering on 415 the packet, discarding it if they do not wish to receive multicast 416 packets destined to this multicast address. 418 5. Conceptual Data Structures 420 In order to participate in the Dynamic Source Routing Protocol, a 421 node needs four conceptual data structures: a Route Cache, a Route 422 Request Table, a Send Buffer, and a Retransmission Buffer. These 423 data structures MAY be implemented in any manner consistent with the 424 external behavior described in this document. 426 5.1. Route Cache 428 All routing information needed by a node participating in an ad hoc 429 network using DSR is stored in a Route Cache. Each node in the 430 network maintains its own Route Cache. The node adds information 431 to the Cache as it learns of new links between nodes in the ad hoc 432 network, for example through packets carrying either a Route Reply or 433 a Routing Header. Likewise, the node removes information from the 434 cache as it learns existing links in the ad hoc network have broken, 435 for example through packets carrying a Route Error or through the 436 link-layer retransmission mechanism reporting a failure in forwarding 437 a packet to its next-hop destination. The Route Cache is indexed 438 logically by destination node address, and supports the following 439 operations: 441 void Insert(Route RT) 443 Inserts information extracted from source route RT into the 444 Route Cache. 446 Route Get(Node DEST) 448 Returns a source route from this node to DEST (if one is 449 known). 451 void Delete(Node FROM, Interface INDEX, Node TO) 453 Removes from the route cache any routes which assume that a 454 packet transmitted by node FROM over its interface with the 455 given INDEX will be received by node TO. 457 Each implementation MAY choose the cache replacement and cache search 458 strategies for its Route Cache that are most appropriate for its 459 particular network environment. For example, some environments may 460 choose to return the shortest route to a node (the shortest sequence 461 of hops), while others may select an alternate metric for the Get() 462 operation. 464 The Route Cache SHOULD support storing more than one source route for 465 each destination. 467 If there are multiple cached routes to a destination, the Route Get() 468 operation SHOULD prefer routes that do not traverse a hop with an 469 interface index of IF_INDEX_MA or IF_INDEX_ROUTER. This will prefer 470 routes that lead directly to the target node over routes that attempt 471 to reach the target via any internet infrastructure connected to the 472 ad hoc network. 474 If a node S is using a source route to some destination D that 475 includes intermediate node N, S SHOULD shorten the route to 476 destination D when it learns of a shorter route to node N than the 477 one that is listed as the prefix of its current route to D. 479 A node S using a source route to destination D through intermediate 480 node N, MAY shorten the source route if it learns of a shorter path 481 from node N to node D. 483 The Route Cache replacement policy SHOULD allow routes to be 484 categorized based upon "preference", where routes with a higher 485 preferences are less likely to be removed from the cache. For 486 example, a node could prefer routes for which it initiated a Route 487 Discovery over routes that it learned as the result of promiscuous 488 snooping on other packets. In particular, a node SHOULD prefer 489 routes that it is presently using over those that it is not. 491 5.2. Route Request Table 493 The Route Request Table is a collection of records about Route 494 Request packets that were recently originated or forwarded by this 495 node. The table is indexed by the home address of the target of the 496 route discovery. A record maintained on node S for node D contains 497 the following: 499 - The time that S last originated a Route Discovery for D. 501 - The remaining amount of time that S must wait before the next 502 attempt at a Route Discovery for D. 504 - The Time-to-live (TTL) field in the IP header of last Route 505 Request originated by S for D. 507 - A FIFO cache of the last ID_FIFO_SIZE Identification values from 508 Route Request packets targeted at node D that were forwarded by 509 this node. 511 Nodes SHOULD use an LRU policy to manage the entries of in their 512 Route Request Table. 514 ID_FIFO_SIZE MUST NOT be set to an unlimited value, since, in the 515 worst case, when a node crashes and reboots the first ID_FIFO_SIZE 516 Route Request packets it sends might appear to be duplicates to the 517 other nodes in the network. 519 5.3. Send Buffer 521 The Send Buffer of some node is a queue of packets that cannot be 522 transmitted by that node because it does not yet have a source 523 route to each respective packet's destination. Each packet in the 524 Send Buffer is stamped with the time that it is placed into the 525 Buffer, and SHOULD be removed from the Send Buffer and discarded 526 SEND_BUFFER_TIMEOUT seconds after initially being placed in the 527 Buffer. If necessary, a FIFO strategy SHOULD be used to evict 528 packets before they timeout to prevent the buffer from overflowing. 530 Subject to the rate limiting defined in Section 7.4, a Route 531 Discovery SHOULD be initiated as often as possible for the 532 destination address of any packets residing in the Send Buffer. 534 5.4. Retransmission Buffer 536 The Retransmission Buffer of a node is a queue of packets sent by 537 this node that are awaiting the receipt of an acknowledgment from the 538 next hop in the source route (Section 6.3). 540 For each packet in the Retransmission Buffer, a node maintains (1) a 541 count of the number of retransmissions and (2) the time of the last 542 retransmission. 544 Packets are removed from the buffer when an acknowledgment 545 is received, or when the number of retransmissions exceeds 546 DSR_MAXRXTSHIFT. In the later case, the removal of the packet from 547 the Retransmission Buffer SHOULD result in a Route Error being 548 returned to the initial source of the packet (Section 7.5). 550 6. Packet Formats 552 Dynamic Source Routing makes use of four options carrying control 553 information that can be piggybacked in any existing IP packet. 555 The mechanism used for these options is based on the design of the 556 Hop-by-Hop and Destination Options mechanisms in IPv6 [4]. The 557 ability to generate and process such options must be added to an IPv4 558 protocol stack. Specifically, the Protocol field in the IP header 559 is used to indicate that a Hop-by-Hop Options or Destination Options 560 extension header exists between the IP header and the remaining 561 portion of a packet's payload (such as a transport layer header). 562 The Next Header field in each extension header will then indicate the 563 type of header that follows it in a packet. 565 6.1. Destination Options Headers 567 The Destination Options header is used to carry optional information 568 that need be examined only by a packet's destination node(s). The 569 Destination Options header is identified by a Next Header (or 570 Protocol) value of 60 in the immediately preceding header, and has 571 the following format: 573 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 574 | Next Header | Hdr Ext Len | | 575 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 576 | | 577 . . 578 . Options . 579 . . 580 | | 581 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 583 Next Header 585 8-bit selector. Identifies the type of header immediately 586 following the Destination Options header. Uses the same values 587 as the IPv4 Protocol field [15]. 589 Hdr Ext Len 591 8-bit unsigned integer. Length of the Destination Options 592 header in 4-octet units, not including the first 8 octets. 594 Options 596 Variable-length field, of length such that the complete 597 Destination Options header is an integer multiple of 4 octets 598 long. Contains one or more TLV-encoded options. 600 The following destination option is used by the Dynamic Source 601 Routing protocol: 603 - DSR Route Request option (Section 6.1.1) 605 This destination option MUST NOT appear multiple times within a 606 single Destination Options header. 608 6.1.1. DSR Route Request Option 610 The DSR Route Request destination option is encoded in 611 type-length-value (TLV) format as follows: 613 0 1 2 3 614 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 615 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 616 | Option Type | Option Length | Identification | 617 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 618 | Target Address | 619 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 620 |C| IN Index[1] |C| IN Index[2] |C| IN Index[3] |C| IN Index[4] | 621 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 622 |C|OUT Index[1] |C|OUT Index[2] |C|OUT Index[3] |C|OUT Index[4] | 623 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 624 | Address[1] | 625 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 626 | Address[2] | 627 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 628 | Address[3] | 629 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 630 | Address[4] | 631 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 632 |C| IN Index[5] |C| IN Index[6] |C| IN Index[7] |C| IN Index[8]| 633 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 634 |C|OUT Index[5] |C|OUT Index[6] |C| OUT Index[7] |C|OUT Index[8]| 635 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 636 | Address[5] | 637 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 638 | ... | 639 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 641 IP fields: 643 Source Address 645 MUST be the home address of the node originating this packet. 646 Intermediate nodes that repropagate the request do not change 647 this field. 649 Destination Address 651 MUST be the limited broadcast address (255.255.255.255). 653 Hop Limit (TTL) 655 Can be varied from 1 to 255, for example to implement 656 expanding-ring searches. 658 Route Request fields: 660 Option Type 662 ???. A node that does not understand this option MUST discard 663 the packet and the Option Data may change en-route (the top 664 three bits are 011). 666 Option Length 668 8-bit unsigned integer. Length of the option, in octets, 669 excluding the Option Type and Option Length fields. 671 Identification 673 A unique value generated by the initiator (original sender) 674 of the Route Request. This value allows a recipient to 675 determine whether or not it has recently seen this a copy of 676 this Request; if it has, the packet is simply discarded. When 677 propagating a Route Request, this field MUST be copied from the 678 received copy of the Request being forwarded. 680 Target Address 682 The home address of the node that is the target of the Route 683 Request. 685 Change Interface (C) bit[1..n] 687 A flag associated with each interface index that indicates 688 whether or not the corresponding node repropagated the Request 689 over a different physical interface type than over which it 690 received the Request. 692 IN Index[1..n] 694 IN Index[i] is the index of the interface over which the node 695 indicated by Address[i] received the Route Request option. 696 These are used to record a reverse route from the target of 697 the request to the originator, over which a Route Reply MAY be 698 sent. 700 OUT Index[1..n] 702 OUT Index[i] is the interface index that the node indicated by 703 Address[i-1] used when rebroadcasting the Route Request option. 705 Address[1..n] 707 Address[i] is the home address of the ith hop recorded in the 708 Route Request option. 710 6.2. Hop-by-Hop Options Headers 712 The Hop-by-Hop Options header is used to carry optional information 713 that must be examined by every node along a packet's delivery path. 714 The Hop-by-Hop Options header is identified by a Next Header (or 715 Protocol) value of ??? in the IP header, and has the following 716 format: 718 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 719 | Next Header | Hdr Ext Len | | 720 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 721 | | 722 . . 723 . Options . 724 . . 725 | | 726 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 728 Next Header 730 8-bit selector. Identifies the type of header immediately 731 following the Hop-by-Hop Options header. Uses the same values 732 as the IPv4 Protocol field [15]. 734 Hdr Ext Len 736 8-bit unsigned integer. Length of the Hop-by-Hop Options 737 header in 4-octet units, not including the first 8 octets. 739 Options 741 Variable-length field, of length such that the complete 742 Hop-by-Hop Options header is an integer multiple of 4 octets 743 long. Contains one or more TLV-encoded options. 745 The following hop-by-hop options are used by the Dynamic Source 746 Routing protocol: 748 - DSR Route Reply option (Section 6.2.1) 750 - DSR Route Error option (Section 6.2.2) 752 - DSR Acknowledgment option (Section 6.2.3) 754 All of these destination options MAY appear one or more times within 755 a single Hop-by-Hop Options header. 757 6.2.1. DSR Route Reply Option 759 The DSR Route Reply hop-by-hop option is encoded in type-length-value 760 (TLV) format as follows: 762 0 1 2 3 763 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 764 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 765 | Option Type | Option Length | Reserved | 766 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 767 | Target Address | 768 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 769 |C|OUT Index[1] |C|OUT Index[2] |C|OUT Index[3] |C|OUT Index[4] | 770 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 771 | Address[1] | 772 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 773 | Address[2] | 774 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 775 | Address[3] | 776 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 777 | Address[4] | 778 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 779 |C|OUT Index[5] |C|OUT Index[6] |C|OUT Index[7] |C|OUT Index[8] | 780 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 781 | Address[5] | 782 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 783 | ... | 784 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 785 Option Type 787 ???. A node that does not understand this option should ignore 788 this option and continue processing the packet, and the Option 789 Data does not change en-route (the top three bits are 000). 791 Option Length 793 8-bit unsigned integer. Length of the option, in octets, 794 excluding the Option Type and Option Length fields. 796 Reserved 798 Sent as 0; ignored on reception. 800 Target Address 802 The home address of the node to which the Route Reply must be 803 delivered. 805 Change Interface (C) bit[1..n] 807 If the C bit associated with a node N is set, it implies N will 808 be forwarding the packet out a different interface than the one 809 over which it was received (i.e., the node sending the packet 810 to N should not expect a passive acknowledgment). 812 OUT Index[1..n] 814 OUT Index[i] is the interface index of the ith hop listed in 815 the Route Reply option. It denotes the interface that should 816 be used by Address[i-1] to reach Address[i] when using the 817 specified source route. 819 Address[1..n] 821 Address[i] is the home address of the ith hop listed in the 822 Route Reply option. 824 6.2.2. DSR Route Error Option 826 The DSR Route Error hop-by-hop option is encoded in type-length-value 827 (TLV) format as follows: 829 0 1 2 3 830 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 831 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 832 | Option Type | Option Length | Index | 833 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 834 | Error Source Address | 835 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 836 | Error Destination Address | 837 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 838 | Unreachable Node Address | 839 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 841 Option Type 843 ???. A node that does not understand this option should ignore 844 the option and continue processing the packet, and the Option 845 Data does not change en-route (the top three bits are 000). 847 Option Length 849 8-bit unsigned integer. Length of the option, in octets, 850 excluding the Option Type and Option Length fields. 852 Index 854 The interface index of the network interface over which the 855 node designated by Error Source Address tried to forward a 856 packet to the node designated by Unreachable Node Address. 858 Error Source Address 860 The home address of the node originating the Route Error (e.g., 861 the node that attempted to forward a packet and discovered the 862 link failure). 864 Error Destination Address 866 The home address of the node to which the Route Error must be 867 delivered (e.g, the node that generated the routing information 868 claiming that the hop Error Source Address to Unreachable Node 869 Address was a valid hop). 871 Unreachable Node Address 873 The home address of the node that was found to be unreachable 874 (the next hop neighbor to which the node at ``Error Source 875 Address'' was attempting to transmit the packet). 877 6.2.3. DSR Acknowledgment Option 879 The DSR Acknowledgment hop-by-hop option is encoded in 880 type-length-value (TLV) format as follows: 882 0 1 2 3 883 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 884 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 885 | Option Type | Option Length | 886 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 887 | Identification | 888 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 889 | ACK Source Address | 890 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 891 | ACK Destination Address | 892 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 893 | Data Source Address | 894 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 896 Option Type 898 ???. A node that does not understand this option should ignore 899 the option and continue processing the packet, and the Option 900 Data does not change en-route (the top three bits are 000). 902 Option Length 904 8-bit unsigned integer. Length of the option, in octets, 905 excluding the Option Type and Option Length fields. 907 Identification 909 A 32-bit value that when taken in conjunction with Data Source 910 Address, uniquely identifies the packet being acknowledged. 912 The Identification value is computed as ((ip_id << 16) | ip_off) 913 where ip_id is the value of the 16-bit Identification field in 914 the IP header of the packet being acknowledged, and ip_off is 915 the value of the 13-bit Fragment Offset field in the IP header 916 of the packet being acknowledged. 918 When constructing the Identification, ip_id and ip_off MUST be 919 in host byte-order. The entire Identification value MUST then 920 be converted to network byte-order before being placed in the 921 Acknowledgment option. 923 ACK Source Address 925 The home address of the node originating the Acknowledgment. 927 ACK Destination Address 929 The home address of the node to which the Acknowledgment must 930 be delivered. 932 Data Source Address 934 The IP Source Address of the packet being acknowledged. 936 6.3. DSR Routing Header 938 As specified for IPv6 [4], a Routing header is used by a source to 939 list one or more intermediate nodes to be ``visited'' on the way to 940 a packet's destination. This function is similar to IPv4's Loose 941 Source and Record Route option, but the Routing header does not 942 record the route taken as the packet is forwarded. The specific 943 processing steps required to implement the Routing header must be 944 added to an IPv4 protocol stack. The Routing header is identified by 945 a Next Header value of 43 in the immediately preceding header, and 946 has the following format: 948 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 949 | Next Header | Hdr Ext Len | Routing Type | Segments Left | 950 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 951 | | 952 . . 953 . type-specific data . 954 . . 955 | | 956 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 958 The type specific data for a Routing Header carrying a DSR Source 959 Route is: 961 0 1 2 3 962 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 963 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 964 |R|S| Reserved | 965 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 966 |C|OUT Index[1] |C|OUT Index[2] |C|OUT Index[3] |C|OUT Index[4] | 967 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 968 | Address[1] | 969 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 970 | Address[2] | 971 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 972 | Address[3] | 973 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 974 | Address[4] | 975 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 976 |C|OUT Index[5] |C|OUT Index[6] |C|OUT Index[7] |C|OUT Index[8] | 977 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 978 | Address[5] | 979 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 980 | ... | 981 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 982 Routing Header Fields: 984 Next Header 986 8-bit selector. Identifies the type of header immediately 987 following the Routing header. 989 Hdr Ext Len 991 8-bit unsigned integer. Length of the Routing header in 992 4-octet units, not including the first 8 octets. 994 Routing Type 996 ??? 998 Segments Left 1000 Number of route segments remaining, i.e., number of explicitly 1001 listed intermediate nodes still to be visited before reaching 1002 the final destination. 1004 Type Specific Fields: 1006 Acknowledgment Request (R) 1008 The Acknowledgment Request (R) bit is set to request an 1009 explicit acknowledgment from the next hop. After processing 1010 the Routing Header, The IP Destination Address lists the 1011 address of the next hop. 1013 Salvaged Packet (S) 1015 The Salvaged Packet (S) bit indicates that this packet has been 1016 salvaged by an intermediate node, and thus that this Routing 1017 Header was generated by Address[1] and not the IP Source 1018 Address (Section 7.5.5). 1020 Reserved 1022 Sent as 0; ignored on reception. 1024 Change Interface (C) bit[1..n] 1026 If the C bit associated with a node N is set, it implies N will 1027 be forwarding the packet out a different interface than the one 1028 over which it was received (i.e., the node sending the packet 1029 to N should not expect a passive acknowledgment and MAY wish to 1030 set the R bit). 1032 OUT Index[1..n] 1034 Index[i] is the interface index that the node indicated 1035 by Address[i-1] must use when transmitting the packet to 1036 Address[i]. Index[1] indicates which interface the node 1037 indicated by the IP Source Address uses to transmit the packet. 1039 Address[1..n] 1041 Address[i] is the home address of the ith hop in the Routing 1042 header. 1044 Note that Address[1] is the first intermediate hop along the route. 1045 The address of the originating node is the IP Source Address. The 1046 only exception to this rule is for packets that are salvaged, as 1047 described in Section 7.5.5. A packet that has been salvaged has an 1048 alternate route placed on it by an intermediate node in the network, 1049 and in this case, the address of the originating node (the salvaging 1050 node) is Address[1]. Salvaged packets are indicated by setting the S 1051 bit in the DSR Routing header. 1053 7. Detailed Operation 1055 7.1. Originating a Data Packet 1057 When node A originates a packet, the following steps MUST be taken 1058 before transmitting the packet: 1060 1. If the destination address is a multicast address, piggyback the 1061 data packet on a Route Request targeting the multicast address. 1062 The following fields MUST be initialized as specified: 1064 IP.Source_Address = Home address of node A 1065 IP.Destination_Address = 255.255.255.255 1066 Request.Target_Address = Multicast destination address 1068 DONE. 1070 2. Otherwise, call Route_Cache.Get() to determine if there is a 1071 cached source route to the destination. 1073 3. If the cached route indicates that the destination is directly 1074 reachable over one hop, no Routing Header should be added to the 1075 packet. Initialize the following fields: 1077 IP.Source_Address = Home address of node A 1078 IP.Destination_Address = Home address of the Destination 1080 DONE. 1082 4. Otherwise, if the cached route indicates that multiple hops are 1083 required to reach the destination, insert a Routing Header into 1084 the packet as described in Section 7.2. DONE. 1086 5. Otherwise, if no cached route to the destination is found, insert 1087 the packet into the Send Buffer and initiate Route Discovery as 1088 described in Section 7.4. 1090 7.2. Originating a Packet with a DSR Routing Header 1092 When a node originates a packet with a Routing Header, the address 1093 of the first hop in the source route MUST be listed as the IP 1094 Destination Address as well as Address[1] in the Routing Header. 1095 The final destination of the packet is listed as the last hop 1096 in the Routing Header (Address[n]). At each intermediate hop i, 1097 Address[i] is copied into the IP Destination Address and the packet 1098 is retransmitted. 1100 For example, suppose node A originates a packet destined for node D 1101 that should pass through intermediate hops B and C. The packet MUST 1102 be initialized as follows: 1104 IP.Source_Address = Home address of node A 1105 IP.Destination_Address = Home address of node B 1106 RT.Segments_Left = 2 1107 RT.Out_Index[1] = Interface index used by A to reach B 1108 RT.Out_Index[2] = Interface index used by B to reach C 1109 RT.Out_Index[3] = Interface index used by C to reach D 1110 RT.Address[1] = Home address of node B 1111 RT.Address[2] = Home address of node C 1112 RT.Address[3] = Home address of node D 1114 7.3. Processing a Routing Header 1116 Excluding the exceptions listed here, a DSR Routing Header is 1117 processed using the same rules as outlined for Type 0 Routing Headers 1118 in IPv6 [4]. The Routing Header is only processed by the node whose 1119 address appears as the IP destination of the packet. The following 1120 additional rules apply to processing the type specific data of a DSR 1121 Source Route: 1123 Let 1125 SegLft = the value of Segments Left when the packet was received 1126 NumAddrs = the total number of addresses in the Routing Header 1128 1. The address of the next hop, Address[NumAddrs - SegLft + 1], 1129 is copied into the IP.Destination_Address of the packet. The 1130 existing IP.Destination_Address is NOT copied back into the 1131 Address list of the Routing Header. 1133 2. The interface used to transmit the packet to its next hop from 1134 this node MUST be the interface denoted by Index[NumAddrs - 1135 SegLft + 1]. 1137 3. If the Acknowledgment Request (R) bit is set, the node MUST 1138 transmit a packet containing the DSR Acknowledgment option to 1139 the previous hop, Address[NumAddrs - SegLft - 1], performing 1140 Route Discovery if necessary. (Address[0] is taken as the 1141 IP.Source_Address) 1143 4. Perform Route Maintenance by verifying that the packet was 1144 received by the next hop as described in Section 7.5. 1146 7.4. Route Discovery 1148 Route Discovery is the on-demand process by which nodes actively 1149 obtain source routes to destinations to which they are actively 1150 attempting to send packets. The destination node for which a 1151 Route Discovery is initiated is known as the "target" of the Route 1152 Discovery. A Route Discovery for a destination SHOULD NOT be 1153 initiated unless the initiating node has a packet in the Send Buffer 1154 requiring delivery to that destination. A Route Discovery for a 1155 given target node MUST NOT be initiated unless permitted by the 1156 rate-limiting information contained in the Route Request Table. 1157 After each Route Discovery attempt, the interval between successive 1158 Route Discoveries for this target must be doubled, up to a maximum of 1159 MAX_REQUEST_PERIOD. 1161 Route Discoveries for a multicast address SHOULD NOT be rate limited, 1162 and SHOULD always be permitted. 1164 7.4.1. Originating a Route Request 1166 The basic Route Discovery algorithm for a unicast destination is as 1167 follows: 1169 1. Originate a Route Request packet with the IP header Time-to-Live 1170 field initialized to 1. This type of Route Request is called a 1171 non-propagating Route Request and allows the originator of the 1172 Request to inexpensively query the route caches of each of its 1173 neighbors for a route to the destination. 1175 2. If a Route Reply is received in response to the non-propagating 1176 Request, use the returned source route to transmit all packets 1177 for the destination that are in the Send Buffer. DONE. 1179 3. Otherwise, if no Route Reply is received within 1180 RING0_REQUEST_TIMEOUT seconds, transmit a Route Request 1181 with the IP header Time-to-Live field initialized to 1182 MAX_ROUTE_LEN. This type of Route Request is called a propagating 1183 Route Request. Update the information in the Route Request 1184 Table, to double the amount of time before any subsequent Route 1185 Discovery attempt to this target. 1187 4. If no Route Reply is received within the time interval indicated 1188 by the Route Request Table, GOTO step 1. 1190 The Route Request option SHOULD be initialized as follows: 1192 IP.Source_Address = This node's home address 1193 IP.Destination_Address = 255.255.255.255 1194 Request.Target = Home address of intended destination 1195 Request.OUT_Index[1] = Index of interface used to transmit the Request 1197 The behavior of a node processing a packet containing both a Routing 1198 Header and a Route Request Destination option is unspecified. 1199 Packets SHOULD NOT contain both a Routing Header and a Route Request 1200 Destination option. [This is not exactly true: A Route Request 1201 option appearing in the second Destination Options header that IPv6 1202 allows after the Routing Header would probably do-what-you-mean, 1203 though we have not triple-checked it yet. Namely, it would allow the 1204 originator of a route discovery to unicast the request to some other 1205 node, where it would be released and begin the flood fill. We call 1206 this a Route Request Blossom since the unicast portion of the path 1207 looks like a stem on the blossoming flood-fill of the request.] 1209 Packets containing a Route Request Destination option SHOULD NOT be 1210 retransmitted, SHOULD NOT request an explicit DSR Acknowledgment by 1211 setting the R bit, SHOULD NOT expect a passive acknowledgment, and 1212 SHOULD NOT be placed in the Retransmission Buffer. The repeated 1213 transmission of packets containing a Route Request Destination option 1214 is controlled solely by the logic described in this section. 1216 7.4.2. Processing a Route Request Option 1218 When a node A receives a packet containing a Route Request option, 1219 the Route Request option is processed as follows: 1221 1. If Request.Target_Address matches the home address of this node, 1222 then the Route Request option contains a complete source route 1223 describing the path from the initiator of the Route Request to 1224 this node. 1226 (a) Send a Route Reply as described in Section 7.4.4. 1228 (b) Continue processing the packet in accordance with the Next 1229 Header value contained in the Destination Option extension 1230 header. DONE. 1232 2. Otherwise, if the combination (IP.Source_Address, 1233 Request.Identification) is found in the Route Request 1234 Table, then discard the packet, since this is a copy of a 1235 recently seen Route Request. DONE. 1237 3. Otherwise, if Request.Target_Address is a multicast address then: 1239 (a) If node A is a member of the multicast group indicated by 1240 Request.Target_Address, then create a copy of the packet, 1241 setting IP.Destination_Address = REQUEST.Target_Address, and 1242 continue processing the copy of the packet in accordance with 1243 the Next Header field of the Destination option. 1245 (b) If IP.TTL is non-zero, decrement IP.TTL, and retransmit the 1246 packet. DONE. 1248 (c) Otherwise, discard the packet. DONE. 1250 4. Otherwise, if the home address of node A is already listed in 1251 the Route Request (IP.Source_Address or Request.Address[]), then 1252 discard the packet. DONE. 1254 5. Let 1256 m = number of addresses currently in the Route Request option 1257 n = m + 1 1259 6. Otherwise, append the home address of node A to the Route Request 1260 option (Request.Address[n]). 1262 7. Set Request.IN_Index[n] = index of interface packet was received 1263 on. 1265 8. If a source route to Request.Target_Address is found in our Route 1266 Cache and the rules of Section 7.4.3 permit it, return a Cached 1267 Route Reply as described in Section 7.4.3. DONE. 1269 9. Otherwise, for each interface on which the node is configured to 1270 participate in a DSR ad hoc network: 1272 (a) Make a copy of the packet containing the Route Request. 1274 (b) Set Request.OUT_Index[n+1] = index of the interface. 1276 (c) If the outgoing interface is different from the incoming 1277 interface, then set the C bit on both Request.OUT_Index[n+1] 1278 and Request.IN_Index[n] 1280 (d) Link-layer re-broadcast the packet containing the Route 1281 Request on the interface jittered by T milliseconds, where 1282 T is a uniformly distributed, random number between 0 and 1283 BROADCAST_JITTER. DONE. 1285 7.4.3. Generating Route Replies using the Route Cache 1287 A node SHOULD use its Route Cache to avoid propagating a Route 1288 Request packet received from another node. In particular, suppose a 1289 node receives a Route Request packet for which it is not the target 1290 and which it does not discard based on the logic of Section 7.4.2. 1291 If the node has a Route Cache entry for the target of the Request, 1292 it SHOULD append this cached route to the accumulated route record 1293 in the packet and return this route in a Route Reply packet to 1294 the initiator without propagating (re-broadcasting) the Route 1295 Request. Thus, for example, if node F in the example network shown 1296 in Figure 7.4.3 needs to send a packet to node D, it will initiate 1297 a Route Discovery and broadcast a Route Request packet. If this 1298 broadcast is received by node A, node A can simply return a Route 1299 Reply packet to F containing the complete route to D consisting of 1300 the sequence of hops: A, B, C, and D. 1302 Before transmitting a Route Reply packet that was generated using 1303 information from its Route Cache, a node MUST verify that: 1305 1. The resulting route contains no loops. 1307 2. The node issuing the Route Reply is listed in the route that it 1308 specifies in its Reply. This increases the probability that the 1309 route is valid, since the node in question should have received 1310 a Route Error if this route stopped working. Additionally, this 1311 requirement means that a Route Error traversing the route will 1312 pass through the node that issued the Reply based on stale cache 1313 data, which is critical for ensuring stale data is removed from 1314 caches in a timely manner. Without this requirement, the next 1315 Route Discovery initiated by the original requester might also be 1316 contaminated by a Route Reply from this node containing the same 1317 stale route. 1319 7.4.4. Originating a Route Reply 1321 Let REQPacket denote a packet received by node A that 1322 contains a Route Request option which lists node A as the 1323 REQPacket.Request.Target_Address. Let REPPacket be a packet 1324 transmitted by node A that contains a corresponding Route Reply. The 1325 Route Reply option transmitted in response to a Route Request MUST be 1326 initialized as follows: 1328 B->C->D 1329 +---+ +---+ +---+ +---+ 1330 | A |---->| B |---->| C |---->| D | 1331 +---+ +---+ +---+ +---+ 1333 +---+ 1334 | F | +---+ 1335 +---+ | E | 1336 +---+ 1338 Figure 1: An example network where A knows a 1339 route to D via B and C. 1341 1. If REQPacket.Request.Address[] does not contain any hops, then 1342 node A is only a single hop from the originator of the Route 1343 Request. Build a Route Reply packet as follows: 1345 REPPacket.IP.Source_Address = REQPacket.Request.Target_Address 1346 REPPacket.Reply.Target = REQPacket.IP.Source_Address 1347 REPPacket.Reply.OUT_Index[1] = REQPacket.Request.OUT_index[1] 1348 REPPacket.Reply.OUT_C_bit[1] = REQPacket.Request.OUT_C_bit[1] 1349 REPPacket.Reply.Address[1] = The home address of node A 1351 GOTO step 3. 1353 2. Otherwise, build a Route Reply packet as follows: 1355 REPPacket.IP.Source_Address = The home address of node A 1356 REPPacket.Reply.Target = REQPacket.IP.Source_Address 1357 REPPacket.Reply.OUT_Index[1..n]= REQPacket.Request.OUT_index[1..n] 1358 REPPacket.Reply.OUT_C_bit[1..n]= REQPacket.Request.OUT_C_bit[1..n] 1359 REPPacket.Reply.Address[1..n] = REQPacket.Request.Address[1..n] 1361 3. Send the Route Reply jittered by T milliseconds, where T 1362 is a uniformly distributed random number between 0 and 1363 BROADCAST_JITTER. DONE. 1365 If sending a Route Reply packet to the originator of the Route 1366 Request requires performing a Route Discovery, the Route Reply 1367 hop-by-hop option MUST be piggybacked on the packet that contains the 1368 Route Request. This prevents a loop wherein the target of the new 1369 Route Request (which was itself the originator of the original Route 1370 Request) must do another Route Request in order to return its Route 1371 Reply. 1373 If sending the Route Reply to the originator of the Route Request 1374 does not require performing Route Discovery, a node SHOULD send a 1375 unicast Route Reply in response to every Route Request targeted at 1376 it. 1378 7.4.5. Processing a Route Reply Option 1380 Upon receipt of a Route Reply, a node should extract the source route 1381 (Target_Address, OUT_Index[1]:Address[1], .. OUT_Index[n]:Address[n] 1382 ) and insert this route into its Route Cache. All the packets in the 1383 Send Buffer SHOULD be checked to see whether the information in the 1384 Reply allows them to be sent immediately. 1386 7.5. Route Maintenance 1388 Route Maintenance requires that whenever a node transmits a data 1389 packet, a Route Reply, or a Route Error, it must verify that the next 1390 hop (indicated by the Destination IP Address) correctly receives the 1391 packet. 1393 If the sender cannot verify that the next hop received the packet, it 1394 MUST decide that its link to the next hop is broken and MUST send a 1395 Route Error to the node responsible for generating the Routing Header 1396 that contains the broken link (Section 7.5.3). 1398 The following ways may be used to verify that the next hop correctly 1399 received a packet: 1401 - The receipt of a passive acknowledgment (Section 7.5.1). 1403 - The receipt of an explicitly requested acknowledgment 1404 (Section 7.5.1). 1406 - By the presence of positive feedback from the link layer 1407 indicating that the packet was acknowledged by the next hop 1408 (Section 7.5.2). 1410 - By the absence of explicit failure notification from the link 1411 layer that provides reliable hop-by-hop delivery such as MACAW or 1412 802.11 (Section 7.5.2). 1414 Nodes MUST NOT perform Route Maintenance for packets containing a 1415 Route Request option or packets containing only an Acknowledgment 1416 option. Sending Acknowledgments for packets containing only 1417 an Acknowledgment option would create an infinite loop whereby 1418 acknowledgments would be sent for acknowledgments. Acknowledgments 1419 should be always sent for packets containing a Routing Header with 1420 the R bit set (e.g., packets which contain only an Acknowledgment 1421 and a Routing Header for which the last forwarding hop requires an 1422 explicit acknowledgment of receipt by the final destination). 1424 7.5.1. Using Network-Layer Acknowledgments 1426 For link layers that do not provide explicit failure notification, 1427 the following steps SHOULD be used by a node A to perform Route 1428 Maintenance. 1430 When receiving a packet: 1432 - If the packet contains a Routing Header with the R bit set, send 1433 an explicit acknowledgment as described in Section 7.3. 1435 - If the packet does not contain a Routing Header, the node MUST 1436 transmit a packet containing the DSR Acknowledgment option 1437 to the previous hop as indicated by the IP.Source_Address. 1438 Since the receiving node is the final destination, there 1439 will be no opportunity for the originator to obtain a 1440 passive acknowledgment, and the receiving node must infer the 1441 originator's request for an explicit acknowledgment. 1443 When sending a packet: 1445 1. Before sending a packet, insert a copy of the packet into the 1446 Retransmission Buffer and update the information maintained about 1447 this packet in the Retransmission Buffer. 1449 2. If after processing the Routing Header, RH.Segments_Left is equal 1450 to 0, then node A MUST set the Acknowledgment Request (R) bit in 1451 the Routing Header before transmitting the packet over its final 1452 hop. 1454 3. If after processing the Routing Header and copying 1455 RH.Address[n] to IP.Destination_Address, node A determines that 1456 RH.OUT_C_bit[n+1] is set, then node A MUST set the Acknowledgment 1457 Request (R) bit in the Routing Header before transmitting the 1458 packet (since the C bit was set during Route Discovery by the 1459 node now listed as the IP.Destination_Address to indicate that 1460 it will propagate the packet out a different interface, and that 1461 node A will not receive a passive acknowledgment). 1463 4. Set the retransmission timer for the packet in the Retransmission 1464 Buffer. 1466 5. Transmit the packet. 1468 6. If a passive or explicit acknowledgment is received before the 1469 retransmission timer expires, then remove the packet from the 1470 Retransmission Buffer and disable the retransmission timer. 1471 DONE. 1473 7. Otherwise, when the Retransmission Timer expires, remove the 1474 packet from the Retransmission Buffer. 1476 8. If DSR_MAXRXTSHIFT transmissions have been done, then attempt 1477 to salvage the packet (Section 7.5.5). Also, generate a Route 1478 Error. DONE. 1480 9. GOTO step 1. 1482 7.5.2. Using Link Layer Acknowledgments 1484 If explicit failure notifications are provided by the link layer, 1485 then all packets are assumed to be correctly received by the next hop 1486 and a Route Error is sent only when a explicit failure notification 1487 is made from the link layer. 1489 Nodes receiving a packet without a Routing Header do not need to send 1490 an explicit Acknowledgment to the packet's originator, since the 1491 link layer will notify the originator if the packet was not received 1492 properly. 1494 7.5.3. Originating a Route Error 1496 If the next hop of a packet is found to be unreachable as described 1497 in Section 7.5, a Route Error packet (Section 6.2.2) MUST be returned 1498 to the node whose cache generated the information used to route the 1499 packet. 1501 When a node A generates a Route Error for packet P, it MUST 1502 initialize the fields in the Route Error as follows: 1504 Error.Source_Address = Home address of node A 1505 Error.Unreachable_Address = Home address of the unreachable node 1507 - If the packet contains a DSR Routing Header and the S bit is NOT 1508 set, the packet has been forwarded without the need for salvaging 1509 up to this point. 1511 Error.Destination_Address = P.IP.Source_Address 1513 - Otherwise, if the packet contains a DSR Routing Header and the S 1514 bit IS set, the packet has been salvaged by an intermediate node, 1515 and thus this Routing Header was placed there by the salvaging 1516 node. 1518 Error.Destination_Address = P.RoutingHeader.Address[1] 1520 - Otherwise, if the packet does not contain a DSR Routing Header, 1521 the packet must have been originated by this node A. 1523 Error.Destination_Address = Home address of node A 1525 Send the packet containing the Route Error to Error.Destination_Address, 1526 performing Route Discovery if necessary. 1528 As an optimization, Route Errors that are discovered by the 1529 packet's originator (such that Error.Source_Address is equal to 1530 Error.Destination_Address) SHOULD be processed internally. Such 1531 processing should invoke all the steps that would be taken if a Route 1532 Error option was created, transmitted, received, and processed, 1533 but an actual packet containing a Route Error option SHOULD NOT be 1534 transmitted. 1536 7.5.4. Processing a Route Error Option 1538 Upon receipt of a Route Error via any mechanism, a node 1539 SHOULD remove any route from its Route Cache that uses the hop 1540 (Error.Source_Address, Error.Index to Error.Unreachable_Address). 1541 This includes all Route Errors overheard, and those processed 1542 internally as described in Section 7.5.3. 1544 When the node identified by Error.Destination_Address receives 1545 the Route Error, it SHOULD verify that the source route 1546 responsible for delivering the Route Error includes the same 1547 hops as the working prefix of the original packet's source route 1548 (Error.Destination_Address to Error.Source_Address). If any 1549 hop listed in the working prefix is not included in the Route 1550 Error's source route, then the originator SHOULD forward the Route 1551 Error back along the working prefix (Error.Destination_Address to 1552 Error.Source_Address) so that each node along the working prefix will 1553 remove the invalid route from its Route Cache. 1555 If the node processing a Route Error option discovers its home 1556 address is Error.Destination_Address and the packet contains 1557 additional Route Error option(s) later on the inside of the Hop 1558 by Hop options header, we call the additional Route Errors nested 1559 Route Errors. The node MUST deliver the first nested Route Error 1560 to Nested_Error.Destination_Address, performing Route Discovery if 1561 needed. It does this by removing the Route Error option listing 1562 itself as the Error.Destination_Address, finding the first nested 1563 Route Error option, and originating the remaining packet to 1564 Nested_Error.Destination_Address. This mechanism allows for the 1565 proper handling of Route Errors that are discovered while delivering 1566 a Route Error. 1568 7.5.5. Salvaging a Packet 1570 When node A attempts to salvage a packet originated at node S and 1571 destined for node D, it MUST perform the following steps: 1573 1. Generate and send a Route Error to A as explained in 1574 Section 7.5.3. 1576 2. Call Route_Cache.Get() to determine if it has a cached source 1577 route to the packet's ultimate destination D (which is the last 1578 Address listed in the Routing Header). 1580 3. If node A does not have a cached route for node D, it MUST 1581 discard the packet. DONE. 1583 4. Otherwise, let Salvage_Address[1] through Salvage_Address[m] be 1584 the sequence of hops returned from the Route Cache. Initialize 1585 the following fields in the packet's header: 1587 RT.Segments_Left = m - 2; 1588 RT.S = 1 1589 RT.Address[1] = Home address of Node A 1590 RT.Address[2] = Salvage.Address[1] 1591 ... 1592 RT.Address[n] = Salvage.Address[m] 1594 The IP Source Address of the packet MUST remain unchanged. When the 1595 Routing Header in the outgoing packet is processed, RT.Address[2], 1596 will be copied to the IP Destination Address field. 1598 8. Optimizations 1600 A number of optimizations can be added to the basic operation of 1601 Route Discovery and Route Maintenance as described in Sections 7.4 1602 and 7.5 that can reduce the number of overhead packets and improve 1603 the average efficiency of the routes used on data packets. This 1604 section discusses some of those optimizations. 1606 8.1. Leveraging the Route Cache 1608 The data in a node's Route Cache may be stored in any format, but 1609 the active routes in its cache form a tree of routes, rooted at 1610 this node, to other nodes in the ad hoc network. For example, the 1611 illustration below shows an ad hoc network of six mobile nodes, in 1612 which mobile node A has earlier completed a Route Discovery for 1613 mobile node D and has cached a route to D through B and C: 1615 B->C->D 1616 +---+ +---+ +---+ +---+ 1617 | A |---->| B |---->| C |---->| D | 1618 +---+ +---+ +---+ +---+ 1620 +---+ 1621 | F | +---+ 1622 +---+ | E | 1623 +---+ 1625 Since nodes B and C are on the route to D, node A also learns the 1626 route to both of these nodes from its Route Discovery for D. If A 1627 later performs a Route Discovery and learns the route to E through B 1628 and C, it can represent this in its Route Cache with the addition of 1629 the single new hop from C to E. If A then learns it can reach C in a 1630 single hop (without needing to go through B), A SHOULD use this new 1631 route to C to also shorten the routes to D and E in its Route Cache. 1633 8.1.1. Promiscuous Learning of Source Routes 1635 A node can add entries to its Route Cache any time it learns a new 1636 route. In particular, when a node forwards a data packet as an 1637 intermediate hop on the route in that packet, the forwarding node is 1638 able to observe the entire route in the packet. Thus, for example, 1639 when any intermediate node B forwards packets from A to D, B SHOULD 1640 add the source route information from that packet's Routing Header 1641 to its own Route Cache. If a node forwards a Route Reply packet, it 1642 SHOULD also add the source route information from the route record 1643 being returned in the Route Reply, to its own Route Cache. 1645 In addition, since all wireless network transmissions at the physical 1646 layer are inherently broadcast, it may be possible for a node to 1647 configure its network interface into promiscuous receive mode, such 1648 that the node is able to receive all packets without link layer 1649 address filtering. In this case, the node MAY add to its Route Cache 1650 the route information from any packet it can overhear. 1652 8.2. Preventing Route Reply Storms 1654 The ability for nodes to reply to a Route Request not targeted at 1655 them by using their Route Caches can result in a Route Reply storm. 1656 If a node broadcasts a Route Request for a node that its neighbors 1657 have in their Route Caches, each neighbor may attempt to send a 1658 Route Reply, thereby wasting bandwidth and increasing the rate 1659 of collisions in the area. For example, in the network shown in 1660 Section 8.1, if both node A and node B receive F's Route Request, 1661 they will both attempt to reply from their Route Caches. Both will 1662 send their Replies at about the same time since they receive the 1663 broadcast at about the same time. Particularly when more than the 1664 two mobile nodes in this example are involved, these simultaneous 1665 replies from the mobile nodes receiving the broadcast may create 1666 packet collisions among some or all of these replies and may cause 1667 local congestion in the wireless network. In addition, it will 1668 often be the case that the different replies will indicate routes 1669 of different lengths. For example, A's Route Reply will indicate a 1670 route to D that is one hop longer than that in B's reply. 1672 For interfaces which can promiscuously listen to the channel, mobile 1673 nodes SHOULD use the following algorithm to reduce the number of 1674 simultaneous replies by slightly delaying their Route Reply: 1676 1. Pick a delay period 1678 d = H * (h - 1 + r) 1680 where h is the length in number of network hops for the route 1681 to be returned in this node's Route Reply, r is a random number 1682 between 0 and 1, and H is a small constant delay to be introduced 1683 per hop. 1685 2. Delay transmitting the Route Reply from this node for a period 1686 of d. 1688 3. Within the delay period, promiscuously receive all packets at 1689 this node. If a packet is received by this node during the delay 1690 period that is addressed to the target of this Route Discovery 1691 (the target is the final destination address for the packet, 1692 through any sequence of intermediate hops), and if the length of 1693 the route on this packet is less than h, then cancel the delay 1694 timer and do not transmit the Route Reply from this node; this 1695 node may infer that the initiator of this Route Discovery has 1696 already received a Route Reply, giving an equally good or better 1697 route. 1699 8.3. Piggybacking on Route Discoveries 1701 As described in Section 4.1, when one node needs to send a packet 1702 to another, if the sender does not have a route cached to the 1703 destination node, it must initiate a Route Discovery, buffering the 1704 original packet until the Route Reply is returned. The delay for 1705 Route Discovery and the total number of packets transmitted can be 1706 reduced by allowing data to be piggybacked on Route Request packets. 1707 Since some Route Requests may be propagated widely within the ad hoc 1708 network, though, the amount of data piggybacked must be limited. We 1709 currently use piggybacking when sending a Route Reply or a Route 1710 Error packet, since both are naturally small in size. Small data 1711 packets such as the initial SYN packet opening a TCP connection [13] 1712 could easily be piggybacked. 1714 One problem, however, arises when piggybacking on Route Request 1715 packets. If a Route Request is received by a node that replies 1716 to the request based on its Route Cache without propagating the 1717 Request (Section 8.1), the piggybacked data will be lost if the node 1718 simply discards the Route Request. In this case, before discarding 1719 the packet, the node must construct a new packet containing the 1720 piggybacked data from the Route Request packet. The source route 1721 in this packet MUST be constructed to appear as if the new packet 1722 had been sent by the initiator of the Route Discovery and had been 1723 forwarded normally to this node. Hence, the first portion of the 1724 route is taken from the accumulated route record in the Route Request 1725 packet and the remainder of the route is taken from this node's Route 1726 Cache. The sender address in the packet MUST also be set to the 1727 initiator of the Route Discovery. Since the replying node will be 1728 unable to correctly recompute an Authentication header for the split 1729 off piggybacked data, data covered by an Authentication header SHOULD 1730 NOT be piggybacked on Route Request packets. 1732 8.4. Discovering Shorter Routes 1734 Once a route between a packet source and a destination has been 1735 discovered, the basic DSR protocol MAY continue to use that route 1736 for all traffic from the source to the destination as long as 1737 it continues to work, even if the nodes move such that a shorter 1738 route becomes possible. In many cases, the basic Route Maintenance 1739 procedure will discover the shorter route, since if a node moves 1740 enough to create a shorter route, it will likely also move out of 1741 transmission range of at least one hop on the existing route. 1743 Furthermore, when a data packet is received as the result of 1744 operating in promiscuous receive mode, the node checks if the Routing 1745 Header packet contains its address in the unprocessed portion of the 1746 source route (Address[NumAddrs - SegLft] to Address[NumAddrs]). If 1747 so, the node knows that packet could bypass the unprocessed hops 1748 preceding it in the source route. The node then sends what is called 1749 a gratuitous Route Reply message to the packet's source, giving it 1750 the shorter route without these hops. 1752 The following algorithm describes how a node A should process packets 1753 with an IP.Destination_Address not addressed to A or the IP broadcast 1754 address or a multicast address that are received as a result of A 1755 being in promiscuous receive mode: 1757 1. If the packet is not a data packet containing a Routing Header, 1758 drop the packet. DONE. 1760 2. If the home address of this node does not appear in the portion 1761 of the source route that has not yet been processed (indicated by 1762 Segments Left), then drop the packet. DONE. 1764 3. Otherwise, the node B that just transmitted the packet (indicated 1765 by Address[NumAddrs - SegLft - 1]) can communicate directly with 1766 this node A. Create a Route Reply. The Route Reply MUST list 1767 the entire source route contained in the received packet with the 1768 exception of the intermediate nodes between node B and node A. 1770 4. Send this gratuitous Route Reply to the node listed as the 1771 IP.Source_Address of the received packet. If Route Discovery 1772 is required it MAY be initiated, or the gratuitous Route Reply 1773 packet MAY be dropped. 1775 8.5. Rate Limiting the Route Discovery Process 1777 One common error condition that must be handled in an ad hoc network 1778 is the case in which the network effectively becomes partitioned. 1779 That is, two nodes that wish to communicate are not within 1780 transmission range of each other, and there are not enough other 1781 mobile nodes between them to form a sequence of hops through which 1782 they can forward packets. If a new Route Discovery was initiated 1783 for each packet sent by a node in this situation, a large number of 1784 unproductive Route Request packets would be propagated throughout the 1785 subset of the ad hoc network reachable from this node. In order to 1786 reduce the overhead from such Route Discoveries, we use exponential 1787 back-off to limit the rate at which new Route Discoveries may be 1788 initiated from any node for the same target. If the node attempts to 1789 send additional data packets to this same node more frequently than 1790 this limit, the subsequent packets SHOULD be buffered in the Send 1791 Buffer until a Route Reply is received, but it MUST NOT initiate a 1792 new Route Discovery until the minimum allowable interval between new 1793 Route Discoveries for this target has been reached. This limitation 1794 on the maximum rate of Route Discoveries for the same target is 1795 similar to the mechanism required by Internet nodes to limit the rate 1796 at which ARP requests are sent to any single IP address [1]. 1798 8.6. Improved Handling of Route Errors 1800 All nodes SHOULD process all of the Route Error messages they 1801 receive, regardless of whether the node is the destination of 1802 the Route Error, is forwarding the Route Error, or promiscuously 1803 overhears the Route Error. 1805 Since a Route Error packet names both ends of the hop that is no 1806 longer valid, any of the nodes receiving the error packet may update 1807 their Route Caches to reflect the fact that the two nodes indicated 1808 in the packet can no longer directly communicate. A node receiving 1809 a Route Error packet simply searches its Route Cache for any routes 1810 using this hop. For each such route found, the route is effectively 1811 truncated at this hop. All nodes on the route before this hop are 1812 still reachable on this route, but subsequent nodes are not. 1814 An experimental optimization to improve the handling of errors is 1815 to support the caching of "negative" information in a node's Route 1816 Cache. The goal of negative information is to record that a given 1817 route was tried and found not to work, so that if the same route 1818 is discovered again shortly after the failure, the Route Cache can 1819 ignore or downgrade the metric of the failed route. 1821 We have not currently included this caching of negative information 1822 in our simulations, since it appears to be unnecessary if nodes also 1823 promiscuously receive Route Error packets. 1825 9. Constants 1827 BROADCAST_JITTER 10 milliseconds 1829 MAX_ROUTE_LEN 15 nodes 1831 Interface Indexes 1832 IF_INDEX_INVALID 0x7F 1833 IF_INDEX_MA 0x7E 1834 IF_INDEX_ROUTER 0x7D 1836 Route Cache 1837 ROUTE_CACHE_TIMEOUT 300 seconds 1839 Send Buffer 1840 SEND_BUFFER_TIMEOUT 30 seconds 1842 Request Table 1843 MAX_REQUEST_ENTRIES 32 nodes 1844 MAX_REQUEST_IDS 8 identifiers 1845 MAX_REQUEST_REXMT 16 retransmissions 1846 MAX_REQUEST_PERIOD 10 seconds 1847 REQUEST_PERIOD 500 milliseconds 1848 RING0_REQUEST_TIMEOUT 30 milliseconds 1850 Retransmission Buffer 1851 DSR_RXMT_BUFFER_SIZE 50 packets 1853 Retransmission Timer 1854 DSR_MAXRXTSHIFT 2 1856 10. IANA Considerations 1858 This document proposes the use of the Destination Options header and 1859 the Hop-by-Hop Options header, originally defined for IPv6, in IPv4. 1860 The Next Header values indicating these two extension headers thus 1861 must be reserved within the IPv4 Protocol number space. 1863 Furthermore, this document defines four new types of destination 1864 options, each of which must be assigned an Option Type value: 1866 - The DSR Route Request option, described in Section 6.1.1 1868 - The DSR Route Reply option, described in Section 6.2.1 1870 - The DSR Route Error option, described in Section 6.2.2 1872 - The DSR Acknowledgment option, described in Section 6.2.3 1874 DSR also requires a routing header Routing Type be allocated for the 1875 DSR Source Route defined in Section 6.3. 1877 In IPv4, we require two new protocol numbers be issued to identify 1878 the next header as either an IPv6-style destination option, or an 1879 IPv6-style routing header. Other protocols can make use of these 1880 protocol numbers as nodes that support them will processes any 1881 included destination options or routing headers according to the 1882 normal IPv6 semantics. 1884 11. Security Considerations 1886 This document does not specifically address security concerns. This 1887 document does assume that all nodes participating in the DSR protocol 1888 do so in good faith and with out malicious intent to corrupt the 1889 routing ability of the network. In mission-oriented environments 1890 where all the nodes participating in the DSR protocol share a 1891 common goal that motivates their participation in the protocol, the 1892 communications between the nodes can be encrypted at the physical 1893 channel or link layer to prevent attack by outsiders. 1895 Location of DSR Functions in the ISO Reference Model 1897 When designing DSR, we had to determine at what level within the 1898 protocol hierarchy to implement source routing. We considered two 1899 different options: routing at the link layer (ISO layer 2) and 1900 routing at the network layer (ISO layer 3). Originally, we opted to 1901 route at the link layer for the following reasons: 1903 - Pragmatically, running the DSR protocol at the link layer 1904 maximizes the number of mobile nodes that can participate in 1905 ad hoc networks. For example, the protocol can route equally 1906 well between IPv4 [12], IPv6 [4], and IPX [5] nodes. 1908 - Historically, DSR grew from our contemplation of a multi-hop ARP 1909 protocol [6, 7] and source routing bridges [10]. ARP [11] is a 1910 layer 2 protocol. 1912 - Technically, we designed DSR to be simple enough that that it 1913 could be implemented directly in network interface cards, well 1914 below the layer 3 software within a mobile node. We see great 1915 potential for DSR running between clouds of mobile nodes around 1916 fixed base stations. DSR would act to transparently fill in the 1917 coverage gaps between base stations. Mobile nodes that would 1918 otherwise be unable to communicate with the base station due to 1919 factors such as distance, fading, or local interference sources 1920 could then reach the base station through their peers. 1922 Ultimately, however, we decided to specify DSR as a layer 3 protocol 1923 since this is the only layer at which we could realistically support 1924 nodes with multiple interfaces of different types. 1926 Implementation Status 1928 We have implemented Dynamic Source Routing (DSR) under the 1929 FreeBSD 2.2.7 operating system running on Intel x86 platforms. 1930 FreeBSD is based on a variety of free software, including 4.4 BSD 1931 Lite from the University of California, Berkeley. 1933 Acknowledgments 1935 The protocol described in this draft has been designed within 1936 the CMU Monarch Project, a research project at Carnegie Mellon 1937 University which is developing adaptive networking protocols and 1938 protocol interfaces to allow truly seamless wireless and mobile node 1939 networking [8, 14]. The current members of the CMU Monarch Project 1940 include: 1942 - Josh Broch 1944 - Yih-Chun Hu 1946 - Jorjeta Jetcheva 1948 - David B. Johnson 1950 - Qifa Ke 1952 - David A. Maltz 1954 References 1956 [1] R. Braden, editor. Requirements for Internet Hosts -- 1957 Communication Layers. RFC 1122, October 1989. 1959 [2] Scott Bradner. Key words for use in RFCs to Indicate 1960 Requirement Levels. RFC 2119, March 1997. 1962 [3] Scott Corson and Joseph Macker. Mobile Ad Hoc Networking 1963 (MANET): Routing Protocol Performance Issues and Evaluation 1964 Considerations. Internet-Draft, draft-ietf-manet-issues-00.txt, 1965 September 1997. Work in progress. 1967 [4] Stephen E. Deering and Robert M. Hinden. Internet 1968 Protocol, Version 6 (IPv6) Specification. Internet-Draft, 1969 draft-ietf-ipngwg-ipv6-spec-v2-01.txt, November 1997. Work in 1970 progress. 1972 [5] IPX Router Specification. Novell Part Number 107-000029-001, 1973 Document Version 1.30, March 1996. 1975 [6] David B. Johnson. Routing in ad hoc networks of mobile hosts. 1976 In Proceedings of the IEEE Workshop on Mobile Computing Systems 1977 and Applications, pages 158--163, December 1994. 1979 [7] David B. Johnson and David A. Maltz. Dynamic source routing in 1980 ad hoc wireless networks. In Mobile Computing, edited by Tomasz 1981 Imielinski and Hank Korth, chapter 5, pages 153--181. Kluwer 1982 Academic Publishers, 1996. 1984 [8] David B. Johnson and David A. Maltz. Protocols for adaptive 1985 wireless and mobile networking. IEEE Personal Communications, 1986 3(1):34--42, February 1996. 1988 [9] Charles Perkins, editor. IP Mobility Support. RFC 2002, 1989 October 1996. 1991 [10] Radia Perlman. Interconnections: Bridges and Routers. 1992 Addison-Wesley, Reading, Massachusetts, 1992. 1994 [11] David C. Plummer. An Ethernet Address Resolution Protocol: Or 1995 Converting Network Protocol Address to 48.bit Ethernet Addresses 1996 for Transmission on Ethernet Hardware. RFC 826, November 1982. 1998 [12] J. Postel, editor. Internet Protocol. RFC 791, September 1981. 2000 [13] J. Postel, editor. Transmission Control Protocol. RFC 793, 2001 September 1981. 2003 [14] The CMU Monarch Project. http://www.monarch.cs.cmu.edu/. 2004 Computer Science Department, Carnegie Mellon University. 2006 [15] J. Reynolds and J. Postel. Assigned Numbers. RFC 1700, October 2007 1994. 2009 Chair's Address 2011 The Working Group can be contacted via its current chairs: 2013 M. Scott Corson 2014 Institute for Systems Research 2015 University of Maryland 2016 College Park, MD 20742 2017 USA 2019 Phone: +1 301 405-6630 2020 Email: corson@isr.umd.edu 2022 Joseph Macker 2023 Information Technology Division 2024 Naval Research Laboratory 2025 Washington, DC 20375 2026 USA 2028 Phone: +1 202 767-2001 2029 Email: macker@itd.nrl.navy.mil 2031 Authors' Addresses 2033 Questions about this document can also be directed to the authors: 2035 Josh Broch 2036 Carnegie Mellon University 2037 Electrical and Computer Engineering 2038 5000 Forbes Avenue 2039 Pittsburgh, PA 15213-3890 2040 USA 2042 Phone: +1 412 268-3056 2043 Fax: +1 412 268-7196 2044 Email: broch@cs.cmu.edu 2046 David B. Johnson 2047 Carnegie Mellon University 2048 Computer Science Department 2049 5000 Forbes Avenue 2050 Pittsburgh, PA 15213-3891 2051 USA 2053 Phone: +1 412 268-7399 2054 Fax: +1 412 268-5576 2055 Email: dbj@cs.cmu.edu 2057 David A. Maltz 2058 Carnegie Mellon University 2059 Computer Science Department 2060 5000 Forbes Avenue 2061 Pittsburgh, PA 15213-3891 2062 USA 2064 Phone: +1 412 268-3621 2065 Fax: +1 412 268-5576 2066 Email: dmaltz@cs.cmu.edu