idnits 2.17.1 draft-ietf-manet-dsr-00.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-25) 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 is 1 instance of too long lines in the document, the longest one being 1 character in excess of 72. == There are 13 instances 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). == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: A single attempt at Route Discovery for destination node D may therefore involve sending two Route Request packets. Nodes MUST not backoff between the sending a Route Request with a hop limit of one and the subsequent sending of Route Request with a hop limit of MAX_ROUTE_LEN. This procedure uses the hop limit on the Route Request packet to inexpensively check if the target is currently within wireless transmitter range of the initiator, or if another node within range has a Route Cache entry for this target (effectively using the caches of this node's neighbors as an extension of its own cache). Since the initial request is limited to one network hop, the timeout period before sending the propagating request can be quite small. -- 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 (13 March 1998) is 9540 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) == 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' Summary: 10 errors (**), 0 flaws (~~), 5 warnings (==), 8 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 13 March 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 Route Discovery, completely eliminates the need 48 for periodic router advertisements and link status packets, reducing 49 the overhead of DSR, especially during periods when the network 50 topology is stable and these packets serve only as keep-alives. 52 Contents 54 Status of This Memo i 56 Abstract i 58 1. Introduction 1 60 2. Assumptions 1 62 3. Terminology 2 63 3.1. General Terms . . . . . . . . . . . . . . . . . . . . . . 2 64 3.2. Specification Language . . . . . . . . . . . . . . . . . 4 66 4. Protocol Overview 5 67 4.1. Route Discovery and Route Maintenance . . . . . . . . . . 5 68 4.2. Packet Forwarding . . . . . . . . . . . . . . . . . . . . 6 69 4.3. Conceptual Data Structures . . . . . . . . . . . . . . . 6 70 4.3.1. Route Cache . . . . . . . . . . . . . . . . . . . 6 71 4.3.2. Node Information Cache . . . . . . . . . . . . . 8 72 4.3.3. Send Buffer . . . . . . . . . . . . . . . . . . . 8 73 4.3.4. Retransmission Buffer . . . . . . . . . . . . . . 8 75 5. Packet Formats 10 76 5.1. Destination Options Headers . . . . . . . . . . . . . . . 10 77 5.1.1. DSR Route Request Option . . . . . . . . . . . . 11 78 5.1.2. DSR Route Reply Option . . . . . . . . . . . . . 13 79 5.1.3. DSR Route Error Option . . . . . . . . . . . . . 14 80 5.1.4. DSR Acknowledgment Option . . . . . . . . . . . . 15 81 5.2. DSR Routing Header . . . . . . . . . . . . . . . . . . . 17 83 6. Detailed Operation 19 84 6.1. Route Discovery . . . . . . . . . . . . . . . . . . . . . 19 85 6.1.1. Originating a Route Request . . . . . . . . . . . 19 86 6.1.2. Processing a Route Request Option . . . . . . . . 19 87 6.1.3. Originating a Route Reply . . . . . . . . . . . . 20 88 6.1.4. Processing a Route Reply Option . . . . . . . . . 21 89 6.2. Route Maintenance . . . . . . . . . . . . . . . . . . . . 21 90 6.2.1. Originating a Route Error . . . . . . . . . . . . 21 91 6.2.2. Processing a Route Error Option . . . . . . . . . 21 92 6.2.3. Processing a DSR Acknowledgment Option . . . . . 22 93 6.3. Processing a Routing Header . . . . . . . . . . . . . . . 22 95 7. Optimizations 24 96 7.1. Leveraging the Route Cache . . . . . . . . . . . . . . . 24 97 7.1.1. Promiscuous Learning of Source Routes . . . . . . 24 98 7.1.2. Answering Route Requests using the Route Cache . 25 99 7.2. Route Discovery Using Expanding Ring Search . . . . . . . 25 100 7.3. Preventing Route Reply Storms . . . . . . . . . . . . . . 26 101 7.4. Piggybacking on Route Discoveries . . . . . . . . . . . . 27 102 7.5. Discovering Shorter Routes . . . . . . . . . . . . . . . 27 103 7.6. Rate Limiting the Route Discovery Process . . . . . . . . 28 104 7.7. Improved Handling of Route Errors . . . . . . . . . . . . 29 106 8. Constants 30 108 9. IANA Considerations 31 110 10. Security Considerations 32 112 Location of DSR Functions in the ISO Model 33 114 Implementation Status 34 116 Acknowledgments 35 118 Areas for Refinement 36 120 References 37 122 Chair's Address 39 124 Authors' Addresses 40 125 1. Introduction 127 This document describes Dynamic Source Routing (DSR) [6, 7], a 128 protocol developed by the Monarch Project [8, 14] at Carnegie Mellon 129 University for routing packets in a mobile ad hoc network [3]. 131 Source routing is a routing technique in which the sender of a packet 132 determines the complete sequence of nodes through which to forward 133 the packet; the sender explicitly lists this route in the packet's 134 header, identifying each forwarding "hop" by the address of the next 135 node to which to transmit the packet on its way to the destination 136 host. 138 DSR offers a number of potential advantages over other routing 139 protocols for mobile ad hoc networks. First, DSR uses no periodic 140 routing messages (e.g., no router advertisements and no link-level 141 neighbor status messages), thereby reducing network bandwidth 142 overhead, conserving battery power, and avoiding the propagation of 143 potentially large routing updates throughout the ad hoc network. Our 144 Dynamic Source Routing protocol is able to adapt quickly to changes 145 such as host movement, yet requires no routing protocol overhead 146 during periods in which no such changes occur. 148 In addition, DSR has been designed to compute correct routes in 149 the presence of asymmetric (uni-directional) links. In wireless 150 networks, links may at times operate asymmetrically due to sources 151 of interference, differing radio or antenna capabilities, or the 152 intentional use of asymmetric communication technology such as 153 satellites. Due to the existence of asymmetric links, traditional 154 link-state or distance vector protocols may compute routes that 155 do not work. DSR, however, will find a correct route even in the 156 presence of asymmetric links. 158 2. Assumptions 160 We assume that all hosts wishing to communicate with other hosts 161 within the ad hoc network are willing to participate fully in the 162 protocols of the network. In particular, each host participating in 163 the network should also be willing to forward packets for other hosts 164 in the network. 166 We refer to the minimum number of hops necessary for a packet to 167 reach from any host located at one extreme edge of the network to 168 another host located at the opposite extreme, as the diameter of the 169 network. We assume that the diameter of an ad hoc network will be 170 small (e.g., perhaps 5 or 10 hops), but may often be greater than 1. 172 Packets may be lost or corrupted in transmission on the wireless 173 network. A host receiving a corrupted packet can detect the error 174 and discard the packet. 176 We assume that hosts can enable a promiscuous receive mode on 177 their wireless network interface hardware, causing the hardware to 178 deliver every received packet to the network driver software without 179 filtering based on link-layer destination address. Although we do 180 not require this facility, it is for example common in current LAN 181 hardware for broadcast media including wireless, and some of our 182 optimizations take advantage of it if available. Use of promiscuous 183 mode does increase the software overhead on the CPU, but we believe 184 that wireless network speeds are more the inherent limiting factor to 185 performance in current and future systems. We believe that portions 186 of the protocol are also suitable for implementation directly within 187 a programmable network interface unit to avoid this overhead on the 188 CPU. 190 3. Terminology 192 3.1. General Terms 194 node 196 A device that implements IP. 198 router 200 A node that forwards IP packets not explicitly addressed to 201 itself. 203 host 205 Any node that is not a router. 207 link 209 A communication facility or medium over which nodes can 210 communicate at the link layer, such as an Ethernet (simple or 211 bridged). A link is the layer immediately below IP. 213 interface 215 A node's attachment to a link. 217 prefix 219 A bit string that consists of some number of initial bits of an 220 address. 222 interface index 224 An 8-bit quantity which uniquely identifies an interface among 225 a given node's interfaces. 227 link-layer address 229 A link-layer identifier for an interface, such as IEEE 802 230 addresses on Ethernet links. 232 packet 234 An IP header plus payload. 236 home address 238 An IP address that is assigned for an extended period of time 239 to a mobile node. It remains unchanged regardless of where 240 the node is attached to the Internet [9]. If a node has more 241 than one home address, it SHOULD select and use a single home 242 address when participating in the ad hoc network. 244 source route 246 A source route from node A to node B is an ordered list of home 247 addresses, starting with the home address of node A and ending 248 with the home address of the node B. Between A and B, the 249 source route includes an ordered list of all the intermediate 250 hops between A and B, as well as the interface index of the 251 interface through which the packet should be transmitted to 252 reach the next hop. Note that the packet formats defined in 253 Section 5.1 encode the Target Address (node B) separately, 254 instead of encoding it as the last hop on the source route. 256 Route Discovery 258 The method in DSR by which a node A dynamically obtains a 259 source route to node B that will carry packets through the 260 network from A to B. Performing a route discovery involves 261 sending one or more Route Request packets. 263 Route Maintenance 265 The process in DSR of monitoring the status of a source route 266 while in use, so that any link-failures along the source route 267 can be detected and the broken source route removed from use. 269 3.2. Specification Language 271 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 272 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 273 document are to be interpreted as described in RFC 2119 [2]. 275 4. Protocol Overview 277 4.1. Route Discovery and Route Maintenance 279 A source routing protocol must solve two challenges, which DSR terms 280 Route Discovery and Route Maintenance. Route Discovery is the 281 mechanism whereby a node S wishing to send a packet to a destination 282 D obtains a source route to D. 284 Route Maintenance is the mechanism whereby S is able to detect, while 285 using a source route to D, if the network topology has changed such 286 that it can no longer use its route to D because a hop along the 287 route no longer works. When Route Maintenance indicates a source 288 route is broken, S can attempt to use any other route it happens to 289 know to D, or can invoke Route Discovery again to find a new route. 291 To perform Route Discovery, the source node S broadcasts a Route 292 Request packet with a recorded source route listing only itself. 293 Each node that hears the Route Request forwards the Request if 294 appropriate, adding its own address to the recorded source route in 295 this copy of the Request and rebroadcasts the packet. The forwarding 296 of Requests is constructed so that copies of the Request propagate 297 hop-by-hop outward from the node initiating the Route Discovery, 298 until either the target of the Request is found or until another node 299 is found that can supply a route to the target. 301 The basic mechanism of forwarding Route Requests forwards the Request 302 if the node (1) is not the target of the Request and (2) is not 303 already listed in the recorded source route in this copy of the 304 Request. In addition, however, each node maintains an LRU cache of 305 recently received Route Requests and does not propagate any copies 306 of a Request after the first, avoiding the overhead of forwarding 307 additional copies that reach this node along different paths. Also, 308 the Time-to-Live field in the IP header of the packet carrying the 309 Route Request MAY be used to limit the scope over which the Request 310 will propagate, using the normal behavior of Time-to-Live defined by 311 IP [12, 1]. Additional optimizations on the handling and forwarding 312 of Route Requests are also used to further reduce the Route Discovery 313 overhead. When the target of the Request (e.g., node D) receives the 314 Route Request, it copies the recorded source route into a Route Reply 315 packet which it then sends this Reply back to the initiator of the 316 Route Request (e.g., node S). 318 All source routes learned by a node are kept in a Route Cache, which 319 is used to further reduce the cost of Route Discovery. When a node 320 wishes to send a packet, it examines its own Route Cache and performs 321 Route Discovery only if no suitable source route is found in its 322 Cache. 324 Further, when a node B receives a Route Request from S for another 325 node D, B searches its own Route Cache for a route to D. If B finds 326 such a route, it does not propagate the Route Request, but instead 327 returns a Route Reply to node S based on the concatenation of the 328 recorded source route from S to B in the Route Request and the cached 329 route from B to D. The details of replying from a Route Cache in this 330 way are discussed in Section 7.1. 332 As a node overhears routes being used by others, either by 333 promiscuously snooping on them or when forwarding packets, the node 334 MAY insert those routes into its Route Cache, leveraging the Route 335 Discovery operations of the other nodes. 337 4.2. Packet Forwarding 339 To represent a source route within a packet's header, DSR uses a 340 Routing Header that conforms to the Routing Header format specified 341 for IPv6, adapted to the needs of DSR and to the use of the DSR in 342 IPv4 (or in IPv6 in the future). The DSR Routing Header uses a 343 unique Routing Type field value to distinguish it from the existing 344 Type 0 Routing Header defined within IPv6 [4]. 346 To forward a packet, a receiving node N simply processes the Routing 347 Header as specified in the IPv6 [4] and transmits the packet to 348 the next hop. If a forwarding error occurs along the link to 349 the next hop in the route, this node N sends a Route Error back 350 to the originator S of the packet informing S that this link is 351 "broken". If node N's Route Cache contains a different route to the 352 destination, then the packet is retransmitted using the new source 353 route. Each node overhearing or forwarding a Route Error packet also 354 removes from its Route Cache the link indicated to be broken, thereby 355 cleaning the stale cache data from the network. 357 4.3. Conceptual Data Structures 359 All information a node needs for participation in an ad hoc 360 network using the Dynamic Source Routing Protocol can be organized 361 conceptually into four data structures: a Route Cache, a Node 362 Information Cache, a Send Buffer, and a Retransmission Buffer. These 363 data structures MAY be implemented in any manner consistent with the 364 external behavior described in this document. 366 4.3.1. Route Cache 368 All routing information needed by a node participating in an ad hoc 369 network is stored in a Route Cache. Each node in the network 370 maintains its own Route Cache. The node adds information to the 371 cache as it learns of new links between nodes in the ad hoc network, 372 for example through packets carrying either a Route Reply or a 373 Routing Header. Likewise, the node removes information from the 374 cache as it learns existing links in the ad hoc network have broken, 375 for example through packets carrying a Route Error or through the 376 link-layer retransmission mechanism reporting a failure in forwarding 377 a packet to its next-hop destination. The Route Cache is indexed 378 logically by destination node, and supports the following operations: 380 void Insert(Route RT) 382 Information extracted from source route RT is inserted into the 383 Route Cache. 385 Route Get(Node DEST) 387 A source route from this node to DEST (if it exists) is 388 returned. 390 void Delete(Node FROM, Node TO) 392 Any routes in the cache that assume the existence of a 393 unidirectional link from node FROM to node TO are removed from 394 the cache. 396 Each implementation MAY choose the cache replacement and cache search 397 strategies most appropriate for its particular network environment. 398 For example, some environments may choose to return the shortest 399 route to a node (the shortest sequence of hops), while others may 400 select an alternate metric for the Get() operation. 402 The Route Cache SHOULD support storing more than one source route for 403 each destination. 405 If node S is using a source route to destination D that includes 406 intermediate node I, S SHOULD shorten the route to destination D when 407 it learns of a shorter route to node I. A node S using a source route 408 to destination D through node I, MAY shorten the source route if it 409 learns of a shorter path from node I to node D. 411 The Route Cache replacement policy SHOULD allow routes to be 412 categorized based upon "preference", where routes with a higher 413 preferences are less likely to be removed from the cache. For 414 example, a node could prefer routes for which it initiated a Route 415 Discovery over routes that it learned as the result of promiscuous 416 snooping. In particular, a node SHOULD prefer routes that it is 417 presently using over those that it is not. 419 The Route Cache SHOULD time-stamp each route as it is inserted into 420 the cache. If the route is not used within ROUTE_CACHE_TIMEOUT 421 seconds, it SHOULD be removed from the cache. 423 4.3.2. Node Information Cache 425 The Node Information Cache is a collection of records indexed by home 426 address. A record maintained on node N1 for node N2 contains the 427 following: 429 - The time that N1 last began a Route Discovery for N2. 431 - The interval of time that N1 must wait before the next attempt at 432 a Route Discovery for N2. 434 - The Time-to-live (TTL) field in the IP header of last Route 435 Request transmitted by N1 for N2. 437 - A FIFO cache of the last ID_FIFO_SIZE Identification values 438 observed in Route Request packets initiated by N2. 440 Nodes SHOULD use an LRU policy to manage the entries of the Node 441 Information Cache. 443 4.3.3. Send Buffer 445 The Send Buffer is a queue of packets that cannot be transmitted 446 because the transmitting node does not yet have a source route 447 to the packets' destinations. Each packet in the Send Buffer is 448 stamped with the time that it is placed into the Buffer, and SHOULD 449 be removed from the Send Buffer and discarded SEND_BUFFER_TIMEOUT 450 seconds after initially being placed in the Buffer. If necessary, a 451 FIFO strategy SHOULD be used to evict packets before they timeout to 452 prevent the buffer from overflowing. 454 Subject to the rate limiting defined in Section 6.1, a Route 455 Discovery SHOULD be initiated as often as possible for any packets 456 residing in the Send Buffer. 458 4.3.4. Retransmission Buffer 460 The Retransmission Buffer is a queue of packets that are awaiting the 461 receipt of an explicit acknowledgment from the next hop in the source 462 route (Section 5.2). 464 For each packet in the Retransmission Buffer, a node maintains (1) a 465 count of the number of retransmissions and (2) the time of the last 466 retransmission. 468 Packets are removed from the buffer when an acknowledgment 469 is received, or when the number of retransmissions exceeds 470 MAX_EXPLICIT_REXMIT. In the later case, the removal of the packet 471 from the Retransmission Buffer should result in a Route Error being 472 returned to the initial source of the packet (Section 6.2). 474 5. Packet Formats 476 5.1. Destination Options Headers 478 Dynamic Source Routing makes use of four options carrying control 479 information that can be piggybacked in any existing IP packet. 480 The mechanism used for these options is based on the design of 481 the Destination Option mechanism in IPv6 [4]. This notion of 482 a Destination Option must be build in to a IPv4 protocol stack. 483 Specifically, the Protocol field in the IP header should be used to 484 indicate that a Destination Options header exists between the IP 485 header and the remaining portion of a packet's payload (such as a 486 transport layer header). The Next Header field in the Destination 487 Options header will then indicate the type of header that follows it 488 in a packet. 490 The Destination Options header is used to carry optional information 491 that need be examined only by a packet's destination node(s). The 492 Destination Options header is identified by a Next Header value of 60 493 in the immediately preceding header, and has the following format: 495 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 496 | Next Header | Hdr Ext Len | | 497 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 498 | | 499 . . 500 . Options . 501 . . 502 | | 503 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 505 The following destination options are used by the Dynamic Source 506 Routing protocol: 508 - DSR Route Request option (Section 5.1.1) 510 - DSR Route Reply option (Section 5.1.2) 512 - DSR Route Error option (Section 5.1.3) 514 - DSR Acknowledgement option (Section 5.1.4) 516 All of these destination options MAY appear multiple times within a 517 single Destination Options header. 519 5.1.1. DSR Route Request Option 521 The DSR Route Request destination option is encoded in 522 type-length-value (TLV) format as follows: 524 0 1 2 3 525 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 526 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 527 | Option Type | Option Length | Identification | 528 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 529 | Target Address | 530 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 531 | Index[1] | Index[2] | Index[3] | Index[4] | 532 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 533 | Address[1] | 534 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 535 | Address[2] | 536 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 537 | Address[3] | 538 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 539 | Address[4] | 540 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 541 | Index[5] | Index[6] | Index[7] | Index[8] | 542 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 543 | ... | 544 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 546 IP fields: 548 Source Address 550 MUST be the home address of the node transmitting this packet. 552 Destination Address 554 MUST be the limited broadcast address (255.255.255.255). 556 Hop Limit (TTL) 558 Can be varied from 1 to 255, for example to implement 559 expanding-ring searches. 561 Route Request fields: 563 Option Type 565 ???. A node that does not understand this option MUST discard 566 the packet (the top two bits must be 01). 568 Option Length 570 8-bit unsigned integer. Length of the option, in octets, 571 excluding the Option Type and Option Length fields. 573 Identification 575 A unique value generated by the initiator (original sender) 576 of the Route Request. This value allows a recipient to 577 determine whether or not it has recently seen this a copy of 578 this Request; if it has, the packet is simply discarded. When 579 propagating a Route Request, this field MUST be copied from the 580 received copy of the Request being forwarded. 582 Target Address 584 The home address of the node that is the target of the Route 585 Request. 587 Index[1..n] 589 Index[i] is the interface index of the ith hop recorded in in 590 the Route Request option (in Address[i]). 592 Address[1..n] 594 Address[i] is the home address of the ith hop recorded in the 595 Route Request option. 597 5.1.2. DSR Route Reply Option 599 The DSR Route Reply destination option is encoded in 600 type-length-value (TLV) format as follows: 602 0 1 2 3 603 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 604 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 605 | Option Type | Option Length |R|F| Reserved | 606 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 607 | Target Address | 608 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 609 | Index[1] | Index[2] | Index[3] | Index[4] | 610 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 611 | Address[1] | 612 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 613 | Address[2] | 614 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 615 | Address[3] | 616 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 617 | Address[4] | 618 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 619 | Index[5] | Index[6] | Index[7] | Index[8] | 620 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 621 | ... | 622 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 624 Option Type 626 ???. A node that does not understand this option should ignore 627 this option and continue processing the packet (the top two 628 bits should be 00). 630 Option Length 632 8-bit unsigned integer. Length of the option, in octets, 633 excluding the Option Type and Option Length fields. 635 Router (R) 637 If the Router (R) bit is set, the last address recorded in this 638 header is the home address of a router that believes it can 639 reach the Target Address specified in the Route Request packet. 641 Foreign Agent (F) 643 If the Foreign Agent (F) bit is set, the last address recorded 644 in this header is the home address of an IETF Mobile IP [9] 645 Foreign Agent. The Router (R) bit and the Foreign Agent (F) 646 bit are mutually exclusive as (F) implies (R). 648 Reserved 650 Sent as 0; ignored on reception. 652 Target Address 654 The home address of the node that is the ultimate destination 655 of the source route contained in the Route Reply. 657 Index[1..n] 659 Index[i] is the interface index of the ith hop listed in the 660 Route Reply option (in Address[i]). 662 Address[1..n] 664 Address[i] is the home address of the ith hop listed in the 665 Route Reply option. 667 5.1.3. DSR Route Error Option 669 The DSR Route Error destination option is encoded in 670 type-length-value (TLV) format as follows: 672 0 1 2 3 673 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 674 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 675 | Option Type | Option Length | Index | 676 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 677 | Originator Address | 678 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 679 | From Hop Address | 680 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 681 | Next Hop Address | 682 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 684 Option Type 686 ???. A node that does not understand this option should ignore 687 the option and continue processing the packet (the top two bits 688 must be 00). 690 Option Length 692 8-bit unsigned integer. Length of the option, in octets, 693 excluding the Option Type and Option Length fields. 695 Index 697 The interface index of the network interface over which the 698 link from the From Hop Address node to the Next Hop Node is 699 being reported as broken by this Route Error option. This 700 Index refers to an interface on the From Hop Address node. 702 Originating Address 704 The home address of the node which originated the packet that 705 could not be forwarded. 707 From Hop Address 709 The home address of the node that attempted to forward a packet 710 and discovered the link failure. 712 Next Hop Address 714 The home address of the node that was found to be unreachable 715 (the next hop neighbor to which the node at Originating Address 716 was attempting to transmit the packet). 718 5.1.4. DSR Acknowledgment Option 720 The DSR Acknowledgment destination option is encoded in 721 type-length-value (TLV) format as follows: 723 0 1 2 3 724 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 725 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 726 | Option Type | Option Length | Identification | 727 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 728 | Address[1] | 729 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 731 Option Type 733 ???. A node that does not understand this option should ignore 734 the option and continue processing the packet (the top two bits 735 must be 00). 737 Option Length 739 8-bit unsigned integer. Length of the option, in octets, 740 excluding the Option Type and Option Length fields. 742 Identification 744 A unique value assigned by the originator of the packet. 745 This value is used to match explicit acknowledgments to the 746 corresponding packet. 748 Address[1] 750 The home address of the original source of the IP packet. 752 5.2. DSR Routing Header 754 As specified for IPv6 [4], a Routing header is used by a source to 755 list one or more intermediate nodes to be "visited" on the way to 756 a packet's destination. This function is similar to IPv4's Loose 757 Source and Record Route option, but the Routing header does not 758 record the route taken as the packet is forwarded. The specific 759 processing steps required to implement the Routing header must be 760 added to an IPv4 protocol stack. The Routing header is identified by 761 a Next Header value of 43 in the immediately preceding header, and 762 has the following format: 764 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 765 | Next Header | Hdr Ext Len | Routing Type | Segments Left | 766 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 767 | | 768 . . 769 . type-specific data . 770 . . 771 | | 772 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 774 The type specific data for a Routing Header carrying a DSR Source 775 Route is: 777 0 1 2 3 778 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 779 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 780 |R| Reserved | Identification | 781 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 782 | Index[1] | Index[2] | Index[3] | Index[4] | 783 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 784 | Address[1] | 785 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 786 | Address[2] | 787 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 788 | Address[3] | 789 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 790 | Address[4] | 791 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 792 | Index[5] | Index[6] | Index[7] | Index[8] | 793 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 794 | ... | 795 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 796 Routing Header Fields: 798 Next Header 800 8-bit selector. Identifies the type of header immediately 801 following the Routing Request header. 803 Hdr Ext Len 805 8-bit unsigned integer. Length of the Routing header in 806 8-octet units, not including the first 8 octets. 808 Routing Type 810 ??? 812 Segments Left 814 Number of route segments remaining, i.e., number of explicitly 815 listed intermediate nodes still to be visited before reaching 816 the final destination. 818 Type Specific Fields: 820 Acknowledgment Request (R) 822 The Acknowledgment Request (R) bit is set to request an 823 explicit acknowledgment from the next hop. 825 Reserved 827 Sent as 0; ignored on reception. 829 Identification 831 A unique value assigned by the originator of the packet. This 832 value is used to match acknowledgments (passive or explicit) to 833 the appropriate packet. 835 Index[1..n] 837 Index[i] is the interface index of the ith hop in the Routing 838 header. 840 Address[1..n] 842 Address[i] is the home address of the ith hop in the Routing 843 header. 845 6. Detailed Operation 847 6.1. Route Discovery 849 Route Discovery is the demand-driven process by which nodes actively 850 obtain source routes to destinations to which they are actively 851 attempting to send packets. The destination node for which a Route 852 Discovery is initiated to discover a route is known as the "target" 853 of the Route Discovery. A Route Discovery for a destination SHOULD 854 NOT be initiated unless the initiating node has an unexpired packet 855 to be delivered to that destination. 857 A Route Discovery for a given target node MUST NOT be initiated 858 unless the difference between the current time and the time that a 859 Route Discovery was last initiated for destination D is greater than 860 the backoff interval currently listed in the Node Information Cache 861 for node D. After each Route Discovery attempt, the interval between 862 successive Route Discoverys must be doubled, up to a maximum of 863 MAX_RTDISCOV_INTERVAL. 865 The basic Route Discovery algorithm is to originate a single 866 Route Request packet as described below that targets the desired 867 destination and has a maximum hop limit set to MAX_ROUTE_LEN. 869 6.1.1. Originating a Route Request 871 A node originates a Route Request for a particular host when it has 872 no route to that host. The Option Length field in the Route Request 873 option MUST be set to 6, the Identification field MUST be set to a 874 unique number, and the Target Address field MUST contain the Home 875 Address of the node for which a route is being requested. 877 6.1.2. Processing a Route Request Option 879 Let P1 be the received packet containing a Route Request option. 880 Let P2 be a packet containing a corresponding Route Reply. A Route 881 Request option is processed as follows: 883 1. Determine the originator of the Route Request. 885 If no addresses are presently listed in P1.REQUEST.Address[], 886 then P1.Source_Address identifies the originator of the Route 887 Request. Otherwise, P1.REQUEST.Address[1] identifies the 888 originator of the Route Request. 890 2. If the combination (Originator Address, P1.REQUEST.Identification) 891 is in the node's cache of recently seen (Address, Identification) 892 pairs, then discard the packet. DONE. 894 3. If the home address of this node is already listed in 895 P1.REQUEST.Address[], then discard the packet. DONE. 897 4. If P1.REQUEST.Target_Address matches the home address of 898 this node, then this packet contains a complete source route 899 describing the path from the initiator of the Route Request to 900 this node. 902 (a) Send a Route Reply as described in Section 6.1.3. 904 (b) If P1.REQUEST.Next_Header indicates No Next Header, DONE. 906 (c) Otherwise, swap P1.REQUEST.Target_Address and 907 P1.Source_Address and pass the packet up the protocol 908 stack. DONE. 910 5. Set P1.REQUEST.Address[n+1] = home address of this node. 911 Re-broadcast the Route Request packet jittered by T milliseconds, 912 where T is a uniformly distributed, random number between 0 and 913 BROADCAST_JITTER. DONE. 915 6.1.3. Originating a Route Reply 917 Let P1 be the received packet containing a Route Request option. Let 918 P2 be a packet containing a corresponding Route Reply. A Route Reply 919 is transmitted in response to a Route Request as follows: 921 1. If P1.REQUEST.Address[] does not contain any hops, then this node 922 is only a single hop from the originator of the Route Request. 923 Build a Route Replay packet as follows: 925 P2.Destination_Address = P1.Source_Address 926 P2.Source_Address = P1.REQUEST.Target_Address 928 GOTO 3. 930 2. Otherwise, build a Route Reply packet as follows: 932 P2.Destination_Address = P1.REQUEST.Address[1] 933 P2.Source_Address = P1.REQUEST.Target_Address 934 P2.REPLY.Address[1..n] = P1.REQUEST.Address[1..n] 936 3. Transmit the Route Reply jittered by T milliseconds, where 937 T is a uniformly distributed, random number between 0 and 938 BROADCAST_JITTER. DONE. 940 If sending a Route Reply packet to the originator of the Route 941 Request requires performing a Route Discovery, the Route Reply 942 destination option MUST be piggybacked on the packet that contains 943 the Route Request. This prevents a loop wherein the target of the 944 Route Request (which was itself the originator of the original Route 945 Request) must do another Route Request in order to return its Route 946 Reply. 948 If sending the Route Reply to the originator of the Route Request 949 does not require performing Route Discovery, nodes SHOULD send a 950 unicast Route Reply in response to every Route Request targeted at 951 them. 953 6.1.4. Processing a Route Reply Option 955 Upon receipt of a Route Reply, a node should extract the source route 956 (Address[1..n] + Target Address) and insert this route into its Route 957 Cache. Any packets in the Send Buffer that are addressed to Target 958 Address SHOULD be processed. 960 6.2. Route Maintenance 962 6.2.1. Originating a Route Error 964 If while forwarding a packet with a Routing Header, the next hop 965 specified in the source route is found to be unreachable, a Route 966 Error packet (Section 5.1.3) MUST be returned to the originator 967 (Address[1]) of the packet. 969 The forwarding node SHOULD consider the next hop to be unreachable if 970 any of the following conditions occurs: 972 - The failure to receive a passive acknowledgment when such passive 973 acknowledgments had been received previously. 975 - The failure to receive an explicitly requested acknowledgment 976 after MAX_EXPLICIT_REXMIT retransmissions. 978 - In link layers providing retransmissions and acknowledgments 979 (e.g., 802.11), a signal from the link layer that it is unable to 980 deliver the packet. 982 6.2.2. Processing a Route Error Option 984 Upon receipt of a Route Error via any mechanism, a node SHOULD remove 985 any route from its Route Cache that uses the hop (From Hop Address, 986 Next Hop Address). 988 When the Route Error is returned to the Originator Address, the 989 originator must verify that the source route in the Route Error 990 packet (From Hop Address...Originator Address) includes the same 991 hops as the working prefix of the original packet's source route 992 (Originator Address...From Hop Address). If any hop listed in the 993 working prefix is not included in the Route Error's source route, 994 then the originator must transmit the Route Error back along the 995 working prefix (Originator Address...From Hop Address) so that each 996 node along the working prefix will remove the invalid route from its 997 Route Cache. 999 If the node processing a Route Error option discovers its home 1000 address equals the Router Error's Originator Address and the packet 1001 contains an additional nested Route Error, the node MUST perform the 1002 following steps: 1004 1. Remove the Route Error being processed from the packet. 1006 2. Copy the Originator Address from the next nested Route Error to 1007 the IP destination field of the packet. 1009 3. Attach a source route and send the packet to the IP destination, 1010 performing Route Discovery if needed. 1012 6.2.3. Processing a DSR Acknowledgment Option 1014 Upon receipt of a DSR Acknowledgment, a node should remove any packet 1015 in its Retransmission Buffer matching the (Address, Identification) 1016 pair found in the Acknowledgment option. If no match is found, the 1017 Acknowledgment should be silently discarded. 1019 [I'm supposed to say something intelligent here, but I can't remember 1020 what... -josh] 1022 6.3. Processing a Routing Header 1024 A DSR Routing Header should be processed in accordance with the steps 1025 outlined for Routing Headers in [4]. The Routing Header is only 1026 processed by the node whose address appears as the IP destination 1027 of the packet. A few additional rules apply to processing the type 1028 specific data of a DSR Source Route: 1030 1. The interface used to transmit the packet MUST be the interface 1031 denoted by Index[n] where Address[n] is the home address of this 1032 node. 1034 2. If the Acknowledgment Request (R) bit is set, the node MUST 1035 create and transmit a packet containing the DSR Acknowledgment 1036 option to the IP Source of the packet, performing Route Discovery 1037 if necessary. 1039 3. If the node chooses to set the Acknowledgment Request (R) bit in 1040 the packet when it forwards it, it must first make a copy of the 1041 packet and insert this copy into its Retransmission Buffer. 1043 4. If a node finds the next hop in the Routing Header to be 1044 unreachable, it MUST send a Route Error packet to the originator 1045 of the packet, denoted by ROUTING.Address[1]. 1047 7. Optimizations 1049 A number of optimizations can be added to the basic operation of 1050 Route Discovery and route maintenance as described in Section 4.1 1051 that can reduce the number of overhead packets and improve the 1052 average efficiency of the routes used on data packets. This section 1053 discusses some of those optimizations. 1055 7.1. Leveraging the Route Cache 1057 The data in a node's Route Cache may be stored in any format, but 1058 the active routes in its cache form a tree of routes, rooted at 1059 this node, to other nodes in the ad hoc network. For example, the 1060 illustration below shows an ad hoc network of six mobile nodes, in 1061 which mobile node A has earlier completed a Route Discovery for 1062 mobile node D and has cached a route to D through B and C: 1064 B->C->D 1065 +---+ +---+ +---+ +---+ 1066 | A |---->| B |---->| C |---->| D | 1067 +---+ +---+ +---+ +---+ 1069 +---+ 1070 | F | +---+ 1071 +---+ | E | 1072 +---+ 1074 Since nodes B and C are on the route to D, node A also learns the 1075 route to both of these nodes from its Route Discovery for D. If A 1076 later performs a Route Discovery and learns the route to E through B 1077 and C, it can represent this in its Route Cache with the addition of 1078 the single new hop from C to E. If A then learns it can reach C in a 1079 single hop (without needing to go through B), A SHOULD use this new 1080 route to C to also shorten the routes to D and E in its Route Cache. 1082 7.1.1. Promiscuous Learning of Source Routes 1084 A node can add entries to its Route Cache any time it learns a 1085 new route. In particular, when a node forwards a data packet as 1086 an intermediate hop on the route in that packet, the forwarding 1087 node is able to observe the entire route in the packet. Thus, for 1088 example, when node B forwards packets from A to D, B SHOULD add the 1089 route information from that packet to its own Route Cache. If a 1090 node forwards a Route Reply packet, it SHOULD also add the route 1091 information from the route record being returned in the Route Reply, 1092 to its own Route Cache. 1094 Finally, since all wireless network transmissions are inherently 1095 broadcast, a node MAY configure its network interface into 1096 promiscuous receive mode, and add to its Route Cache the route 1097 information from any packet it can overhear. 1099 7.1.2. Answering Route Requests using the Route Cache 1101 A node SHOULD use its Route Cache to avoid propagating a Route 1102 Request packet received from another node. In particular, suppose a 1103 node receives a Route Request packet for which it is not the target 1104 and which it does not discard on based on the logic of section 6.1.1. 1105 If the node has a Route Cache entry for the target of the request, 1106 it may append this cached route to the accumulated route record 1107 in the packet, and may return this route in a Route Reply packet 1108 to the initiator without propagating (re-broadcasting) the Route 1109 Request. Thus, for example, if node F in the example network shown 1110 in Section 7.1 needs to send a packet to node D, it will initiate 1111 a Route Discovery and broadcast a Route Request packet. If this 1112 broadcast is received by A, A can simply return a Route Reply packet 1113 to F containing the complete route to D consisting of the sequence of 1114 hops A, B, C, and D. 1116 Before transmitting a Route Reply packet that was generated using 1117 information from its Route Cache, a node MUST verify that: 1119 1. The resulting route does not contain any loops. 1121 2. The node issuing the Route Reply is listed in the route that it 1122 is replying with. This increases the probability that the route 1123 is valid, since the node in question should have received a Route 1124 Error if this route stopped working. 1126 7.2. Route Discovery Using Expanding Ring Search 1128 The propagating nature of a basic Route Request packet means that 1129 potentially every node in the ad hoc network will be disturbed 1130 whenever one is originated. To reduce this network-wide cost, all 1131 nodes SHOULD limit the maximum propagation of their Route Requests in 1132 some way, and MAY use the following algorithm. 1134 1. Whenever the backoff algorithm permits the initiation of a Route 1135 Discovery, initially send a Route Request with a hop limit of one 1136 (we refer to this as a non-propagating Route Request). 1138 2. If no Route Reply is received from the non-propagating Route 1139 Request after RING0_TIMEOUT seconds, send a new Route Request 1140 with the hop limit set to MAX_ROUTE_LEN. 1142 A single attempt at Route Discovery for destination node D may 1143 therefore involve sending two Route Request packets. Nodes MUST 1144 not backoff between the sending a Route Request with a hop limit of 1145 one and the subsequent sending of Route Request with a hop limit of 1146 MAX_ROUTE_LEN. This procedure uses the hop limit on the Route Request 1147 packet to inexpensively check if the target is currently within 1148 wireless transmitter range of the initiator, or if another node 1149 within range has a Route Cache entry for this target (effectively 1150 using the caches of this node's neighbors as an extension of its own 1151 cache). Since the initial request is limited to one network hop, the 1152 timeout period before sending the propagating request can be quite 1153 small. 1155 7.3. Preventing Route Reply Storms 1157 The ability for nodes to reply to a Route Request not targeted at 1158 them using their Route Caches can result in a Route Reply storm. If 1159 a node broadcasts a Route Request for a node that its neighbors have 1160 in their Route Caches, each neighbor may attempt to send a Route 1161 Reply thereby wasting bandwidth and increasing the rate of collisions 1162 in the area. For example, in the network shown in Section 7.1, if 1163 both A and B receive F's Route Request, they will both attempt to 1164 reply from their Route Caches. Both will send their replies at 1165 about the same time since they receive the broadcast at about the 1166 same time. Particularly when more than the two mobile nodes in this 1167 example are involved, these simultaneous replies from the mobile 1168 nodes receiving the broadcast may create packet collisions among 1169 some or all of these replies and may cause local congestion in the 1170 wireless network. In addition, it will often be the case that the 1171 different replies will indicate routes of different lengths. For 1172 example, A's reply will indicate a route to D that is one hop longer 1173 than that in B's reply. 1175 For interfaces which can promiscuously listen to the channel, mobile 1176 nodes SHOULD use the following algorithm to reduce the number of 1177 simultaneous replies by slightly delaying their Route Reply: 1179 1. Pick a delay period 1181 d = H * (h - 1 + r) 1183 where h is the length in number of network hops for the route to 1184 be returned in this node's reply, r is a random number between 0 1185 and 1, and H is a small constant delay to be introduced per hop. 1187 2. Delay transmitting the Route Reply from this node for a period 1188 of d. 1190 3. Within the delay period, promiscuously receive all packets at 1191 this node. If a packet is received by this node during the delay 1192 period that is addressed to the target of this Route Discovery 1193 (the target is the final destination address for the packet, 1194 through any sequence of intermediate hops), and if the length of 1195 the route on this packet is less than h, then cancel the delay 1196 and do not transmit the Route Reply from this node; this node 1197 may infer that the initiator of this Route Discovery has already 1198 received a Route Reply, giving an equal or better route. 1200 7.4. Piggybacking on Route Discoveries 1202 As described in Section 4.1, when one node needs to send a packet 1203 to another, if the sender does not have a Route Cached to the 1204 destination node, it must initiate a Route Discovery, either 1205 buffering the original packet until the Route Reply is returned, or 1206 discarding it and relying on a higher-layer protocol to retransmit 1207 it if needed. The delay for Route Discovery and the total number 1208 of packets transmitted can be reduced by allowing data to be 1209 piggybacked on Route Request packets. Since some Route Requests may 1210 be propagated widely within the ad hoc network, though, the amount 1211 of data piggybacked must be limited. We currently use piggybacking 1212 when sending a Route Reply or a Route Error packet, since both are 1213 naturally small in size, and small data packets such as the initial 1214 SYN packet opening a TCP connection [13] could easily be piggybacked. 1216 One problem, however, arises when piggybacking on Route Request 1217 packets. If a Route Request is received by a node that replies 1218 to the request based on its Route Cache without propagating the 1219 request (Section 7.1), the piggybacked data will be lost if the node 1220 simply discards the Route Request. In this case, before discarding 1221 the packet, the node must construct a new packet containing the 1222 piggybacked data from the Route Request packet. The source route 1223 in this packet MUST be constructed to appear as if the new packet 1224 had been sent by the initiator of the Route Discovery and had been 1225 forwarded normally to this node. Hence, the first portion of the 1226 route is taken from the accumulated route record in the Route Request 1227 packet and the remainder of the route is taken from this node's Route 1228 Cache. The sender address in the packet should also be set to the 1229 initiator of the Route Discovery. Since the replying node will be 1230 unable to correctly recompute an Authentication header for the split 1231 off piggybacked data, data covered by an Authentication header SHOULD 1232 NOT be piggybacked on Route Request packets. 1234 7.5. Discovering Shorter Routes 1236 Once a route between a packet source and a destination has been 1237 discovered, the basic DSR protocol MAY continue to use that route for 1238 all traffic from the source to the destination, even if the nodes 1239 move such that a shorter route becomes possible. In many cases, the 1240 basic route maintenance procedure will discover the shorter route, 1241 since if a node moves enough to create a shorter route, it will 1242 likely also move out of transmission range of at least one hop on the 1243 existing route. 1245 When operating in promiscuous receive mode, a node SHOULD use the 1246 following algorithm to process a received packet. Whenever possible, 1247 this algorithm shortens routes that already exist in the Route Cache. 1249 1. If the packet is not a data packet containing a Routing Header, 1250 drop the packet. DONE. 1252 2. If the IP destination is the home address of this node, then 1253 follow the normal steps to process the packet. DONE. 1255 3. If the home address of this node does not appear in the portion 1256 of the source route that has not yet been processed (indicated by 1257 Segments Left), then drop the packet. DONE. 1259 4. The node S indicated by the Source Address field in the IP header 1260 can communicated directly with this node N. Create a Route Reply. 1261 The Route Reply MUST list the entire source routing contained in 1262 the received packet with the exception of the intermediate nodes 1263 between node S and node N. 1265 7.6. Rate Limiting the Route Discovery Process 1267 One common error condition that must be handled in an ad hoc network 1268 is the case in which the network effectively becomes partitioned. 1269 That is, two nodes that wish to communicate are not within 1270 transmission range of each other, and there are not enough other 1271 mobile nodes between them to form a sequence of hops through which 1272 they can forward packets. If a new Route Discovery was initiated 1273 for each packet sent by a node in this situation, a large number of 1274 unproductive Route Request packets would be propagated throughout the 1275 subset of the ad hoc network reachable from this node. In order to 1276 reduce the overhead from such route discoveries, we use exponential 1277 backoff to limit the rate at which new route discoveries may be 1278 initiated from any node for the same target. If the node attempts to 1279 send additional data packets to this same node more frequently than 1280 this limit, the subsequent packets SHOULD be buffered in the Send 1281 Buffer until a Route Reply is received, but it MUST NOT initiate a 1282 new Route Discovery until the minimum allowable interval between new 1283 route discoveries for this target has been reached. This limitation 1284 on the maximum rate of route discoveries for the same target is 1285 similar to the mechanism required by Internet nodes to limit the rate 1286 at which ARP requests are sent to any single IP address [1]. 1288 7.7. Improved Handling of Route Errors 1290 All nodes SHOULD process all of the Route Error messages they 1291 receive, regardless of whether the node is the destination of 1292 the Route Error, is forwarding the Route Error, or promiscuously 1293 overhears the Route Error. 1295 Since a Route Error packet names both ends of the hop that is no 1296 longer valid, any of the nodes receiving the error packet may update 1297 their Route Caches to reflect the fact that the two nodes indicated 1298 in the packet can no longer directly communicate. A node receiving 1299 a Route Error packet simply searches its Route Cache for any routes 1300 using this hop. For each such route found, the route is truncated at 1301 this hop. All nodes on the route before this hop are still reachable 1302 on this route, but subsequent nodes are not. 1304 An experimental optimization to improve the handling of errors is 1305 to support the caching of "negative" information in a node's Route 1306 Cache. The goal of negative information is to record that a given 1307 route was tried and found not to work, so that if the same route 1308 is discovered again shortly after the failure, the Route Cache can 1309 ignore or downgrade the metric of the failed route. 1311 We have not currently included this caching of negative information 1312 in our simulations, since it appears to be unnecessary if nodes also 1313 promiscuously receive Route Error packets. 1315 8. Constants 1317 BROADCAST_JITTER 10 milliseconds 1319 ID_FIFO_SIZE 8 identifiers 1321 INVALID_INTERFACE_INDEX 0xFF 1323 MAX_EXPLICIT_REXMIT 3 attempts 1325 MAX_RTDISCOV_INTERVAL 120 seconds 1327 MAX_ROUTE_LEN 15 nodes 1329 RING0_TIMEOUT 30 milliseconds 1331 ROUTE_CACHE_TIMEOUT 300 seconds 1333 SEND_BUFFER_TIMEOUT 30 seconds 1335 9. IANA Considerations 1337 This document defines four new types of IPv6 destination option, each 1338 of which must be assigned an Option Type value: 1340 - The DSR Route Request option, described in Section 5.1.1 1342 - The DSR Route Reply option, described in Section 5.1.2 1344 - The DSR Route Error option, described in Section 5.1.3 1346 - The DSR Acknowledgment option, described in Section 5.1.4 1348 DSR also requires a routing header Routing Type be allocated for the 1349 DSR Source Route defined in section 5.2. 1351 In IPv4, we require two new protocol numbers be issued to identify 1352 the next header as either an IPv6-style destination option, or an 1353 IPv6-style routing header. Other protocols can make use of these 1354 protocol numbers as nodes that support them will processes any 1355 included destination options or routing headers according to the 1356 normal IPv6 semantics. 1358 10. Security Considerations 1360 This document does not specifically address security concerns. This 1361 document does assume that all nodes participating in the DSR protocol 1362 do so in good faith and with out malicious intent to corrupt the 1363 routing ability of the network. In mission-oriented environments 1364 where all the nodes participating in the DSR protocol share a 1365 common goal that motivates their participation in the protocol, the 1366 communications between the nodes can be encrypted at the physical 1367 channel or link layer to prevent attack by outsiders. 1369 Location of DSR Functions in the ISO Model 1371 When designing DSR, we had to determine at what level within the 1372 protocol hierarchy to implement source routing. We considered two 1373 different options: routing at the link layer (ISO layer 2) and 1374 routing at the network layer (ISO layer 3). Originally, we opted to 1375 route at the link layer for the following reasons: 1377 - Pragmatically, running the DSR protocol at the link layer 1378 maximizes the number of mobile nodes that can participate in 1379 ad hoc networks. For example, the protocol can route equally 1380 well between IP [12], IPv6 [4], and IPX [5] nodes. 1382 - Historically, DSR grew from our contemplation of a multihop ARP 1383 protocol [6, 7] and source routing bridges [10]. ARP [11] is a 1384 layer 2protocol. 1386 - Technically, we designed DSR to be simple enough that that it 1387 could be implemented directly in network interface cards, well 1388 below the layer 3 software within a mobile node. We see great 1389 potential for DSR running between clouds of mobile nodes around 1390 fixed base stations. DSR would act to transparently fill in the 1391 coverage gaps between base stations. Mobile nodes that would 1392 otherwise be unable to communicate with the base station due to 1393 factors such as distance, fading, or local interference sources 1394 could then reach the base station through their peers. 1396 Ultimately, however, we decided to design DSR as a layer 3 protocol 1397 since this is the only layer at which we could realistically support 1398 nodes with multiple interfaces of different types. 1400 Implementation Status 1402 We have implemented Dynamic Source Routing (DSR) under the 1403 FreeBSD 2.2.2 operating system running on Intel x86 platforms. 1404 FreeBSD is based on a variety of free software, including 4.4 BSD 1405 Lite from the University of California, Berkeley. 1407 Acknowledgments 1409 The protocol described in this draft has been designed within 1410 the CMU Monarch Project, a research project at Carnegie Mellon 1411 University which is developing adaptive networking protocols and 1412 protocol interfaces to allow truly seamless wireless and mobile host 1413 networking [8, 14]. The current members of the CMU Monarch Project 1414 include: 1416 - Josh Broch 1418 - Yih-Chun Hu 1420 - Jorjeta Jetcheva 1422 - David B. Johnson 1424 - David A. Maltz 1426 Areas for Refinement 1428 We are currently working to refine the DSR protocol in the following 1429 ways: 1431 - Improve the algorithms and data structures used by the Route 1432 Cache. We currently represent the Route Cache as a directed 1433 acyclic tree of paths branching out from a root that represents 1434 the node owning the Route Cache. However, each source 1435 route learned by the Route Cache effectively describes the 1436 interconnectedness of all the hops listed on the route, and 1437 can be treated as a type of partial information Link State 1438 Packet as one would find in a Link State routing algorithm. 1439 By generalizing the Route Cache to a graph of all known links 1440 between all known nodes, it may be possible to better leverage 1441 the information a node overhears. 1443 - Support for better route selection. In order to select the 1444 best source route to send a packet with, nodes need be able to 1445 evaluate the costs/benefits of each of their cached routes to the 1446 destination. If those routes involve forwarding through nodes 1447 with more than one interface, some routes may be better suited to 1448 the traffic type because the bandwidth/range/latency/error-rate 1449 characteristics of of the interfaces used on those routes best 1450 match the needs of the traffic type. The Route Request and Route 1451 Reply option format must be extended to enable node to report 1452 the properties of the interfaces on the route, as well as the 1453 interface index used in basic DSR forwarding. 1455 - Improved Route Discovery algorithms. We are investigating ways 1456 to cancel a propagating Route Request if the target of the 1457 request has already been found in another part of the network. 1458 Similarly, we are studying various ring-search algorithms in case 1459 a more sophisticated algorithm might perform better than the 1460 2-step algorithm we currently use. 1462 References 1464 [1] R. Braden, editor. Requirements for Internet Hosts -- 1465 Communication Layers. RFC 1122, October 1989. 1467 [2] Scott Bradner. Key words for use in RFCs to Indicate 1468 Requirement Levels. RFC 2119, March 1997. 1470 [3] Scott Corson and Joseph Macker. Mobile Ad Hoc Networking 1471 (MANET): Routing Protocol Performance Issues and Evaluation 1472 Considerations. Internet-Draft, draft-ietf-manet-issues-00.txt, 1473 September 1997. Work in progress. 1475 [4] Stephen E. Deering and Robert M. Hinden. Internet 1476 Protocol, Version 6 (IPv6) Specification. Internet-Draft, 1477 draft-ietf-ipngwg-ipv6-spec-v2-01.txt, November 1997. Work in 1478 progress. 1480 [5] IPX Router Specification. Novell Part Number 107-000029-001, 1481 Document Version 1.30, March 1996. 1483 [6] David B. Johnson. Routing in ad hoc networks of mobile hosts. 1484 In Proceedings of the IEEE Workshop on Mobile Computing Systems 1485 and Applications, pages 158--163, December 1994. 1487 [7] David B. Johnson and David A. Maltz. Dynamic source routing in 1488 ad hoc wireless networks. In Mobile Computing, edited by Tomasz 1489 Imielinski and Hank Korth, chapter 5, pages 153--181. Kluwer 1490 Academic Publishers, 1996. 1492 [8] David B. Johnson and David A. Maltz. Protocols for adaptive 1493 wireless and mobile networking. IEEE Personal Communications, 1494 3(1):34--42, February 1996. 1496 [9] Charles Perkins, editor. IP Mobility Support. RFC 2002, 1497 October 1996. 1499 [10] Radia Perlman. Interconnections: Bridges and Routers. 1500 Addison-Wesley, Reading, Massachusetts, 1992. 1502 [11] David C. Plummer. An Ethernet Address Resolution Protocol: Or 1503 Converting Network Protocol Address to 48.bit Ethernet Addresses 1504 for Transmission on Ethernet Hardware. RFC 826, November 1982. 1506 [12] J. Postel, editor. Internet Protocol. RFC 791, September 1981. 1508 [13] J. Postel, editor. Transmission Control Protocol. RFC 793, 1509 September 1981. 1511 [14] The CMU Monarch Project. http://www.monarch.cs.cmu.edu/. 1512 Computer Science Department, Carnegie Mellon University. 1514 Chair's Address 1516 The Working Group can be contacted via its current chairs: 1518 M. Scott Corson 1519 Institute for Systems Research 1520 University of Maryland 1521 College Park, MD 20742 1522 USA 1524 Phone: +1 301 405-6630 1525 Email: corson@isr.umd.edu 1527 Joseph Macker 1528 Information Technology Division 1529 Naval Research Laboratory 1530 Washington, DC 20375 1531 USA 1533 Phone: +1 202 767-2001 1534 Email: macker@itd.nrl.navy.mil 1536 Authors' Addresses 1538 Questions about this document can also be directed to the authors: 1540 Josh Broch 1541 Carnegie Mellon University 1542 Electrical and Computer Engineering Department 1543 5000 Forbes Avenue 1544 Pittsburgh, PA 15213-3891 1545 USA 1547 Phone: +1 412 268-3056 1548 Email: broch@andrew.cmu.edu 1550 David B. Johnson 1551 Carnegie Mellon University 1552 Computer Science Department 1553 5000 Forbes Avenue 1554 Pittsburgh, PA 15213-3891 1555 USA 1557 Phone: +1 412 268-7399 1558 Fax: +1 412 268-5576 1559 Email: dbj@cs.cmu.edu 1561 David A. Maltz 1562 Carnegie Mellon University 1563 Computer Science Department 1564 5000 Forbes Avenue 1565 Pittsburgh, PA 15213-3891 1566 USA 1568 Phone: +1 412 268-3621 1569 Fax: +1 412 268-5576 1570 Email: dmaltz@cs.cmu.edu