--- 1/draft-ietf-manet-dsr-09.txt 2006-02-05 00:16:53.000000000 +0100 +++ 2/draft-ietf-manet-dsr-10.txt 2006-02-05 00:16:53.000000000 +0100 @@ -1,19 +1,18 @@ - IETF MANET Working Group David B. Johnson, Rice University INTERNET-DRAFT David A. Maltz, Carnegie Mellon University -15 April 2003 Yih-Chun Hu, Rice University +19 July 2004 Yih-Chun Hu, Rice University The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR) - + Status of This Memo This document is an Internet-Draft and is subject to all provisions of Section 10 of RFC 2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. @@ -32,174 +31,174 @@ This Internet-Draft is a submission to the IETF Mobile Ad Hoc Networks (MANET) Working Group. Comments on this draft may be sent to the Working Group at manet@itd.nrl.navy.mil, or may be sent directly to the authors. Abstract The Dynamic Source Routing protocol (DSR) is a simple and efficient routing protocol designed specifically for use in multi-hop wireless ad hoc networks of mobile nodes. DSR allows the network to be - completely self-organizing and self-configuring, without the need - for any existing network infrastructure or administration. The - protocol is composed of the two main mechanisms of "Route Discovery" - and "Route Maintenance", which work together to allow nodes to - discover and maintain routes to arbitrary destinations in the ad hoc - network. All aspects of the protocol operate entirely on-demand, - allowing the routing packet overhead of DSR to scale automatically - to only that needed to react to changes in the routes currently in - use. The protocol allows multiple routes to any destination and - allows each sender to select and control the routes used in routing - its packets, for example for use in load balancing or for increased - robustness. Other advantages of the DSR protocol include easily - guaranteed loop-free routing, support for use in networks containing - unidirectional links, use of only "soft state" in routing, and very - rapid recovery when routes in the network change. The DSR protocol - is designed mainly for mobile ad hoc networks of up to about two - hundred nodes, and is designed to work well with even very high - rates of mobility. This document specifies the operation of the DSR - protocol for routing unicast IPv4 packets. + completely self-organizing and self-configuring, without the need for + any existing network infrastructure or administration. The protocol + is composed of the two main mechanisms of "Route Discovery" and + "Route Maintenance", which work together to allow nodes to discover + and maintain routes to arbitrary destinations in the ad hoc network. + All aspects of the protocol operate entirely on-demand, allowing + the routing packet overhead of DSR to scale automatically to only + that needed to react to changes in the routes currently in use. The + protocol allows multiple routes to any destination and allows each + sender to select and control the routes used in routing its packets, + for example for use in load balancing or for increased robustness. + Other advantages of the DSR protocol include easily guaranteed + loop-free routing, operation in networks containing unidirectional + links, use of only "soft state" in routing, and very rapid recovery + when routes in the network change. The DSR protocol is designed + mainly for mobile ad hoc networks of up to about two hundred nodes, + and is designed to work well with even very high rates of mobility. + This document specifies the operation of the DSR protocol for routing + unicast IPv4 packets. Contents Status of This Memo i Abstract ii 1. Introduction 1 - 2. Assumptions 3 + 2. Assumptions 4 - 3. DSR Protocol Overview 5 + 3. DSR Protocol Overview 6 - 3.1. Basic DSR Route Discovery . . . . . . . . . . . . . . . . 5 - 3.2. Basic DSR Route Maintenance . . . . . . . . . . . . . . . 8 - 3.3. Additional Route Discovery Features . . . . . . . . . . . 10 - 3.3.1. Caching Overheard Routing Information . . . . . . 10 - 3.3.2. Replying to Route Requests using Cached Routes . 11 - 3.3.3. Preventing Route Reply Storms . . . . . . . . . . 12 - 3.3.4. Route Request Hop Limits . . . . . . . . . . . . 14 - 3.4. Additional Route Maintenance Features . . . . . . . . . . 15 - 3.4.1. Packet Salvaging . . . . . . . . . . . . . . . . 15 + 3.1. Basic DSR Route Discovery . . . . . . . . . . . . . . . . 6 + 3.2. Basic DSR Route Maintenance . . . . . . . . . . . . . . . 9 + 3.3. Additional Route Discovery Features . . . . . . . . . . . 11 + 3.3.1. Caching Overheard Routing Information . . . . . . 11 + 3.3.2. Replying to Route Requests using Cached Routes . 12 + 3.3.3. Route Request Hop Limits . . . . . . . . . . . . 13 + 3.4. Additional Route Maintenance Features . . . . . . . . . . 14 + 3.4.1. Packet Salvaging . . . . . . . . . . . . . . . . 14 3.4.2. Queued Packets Destined over a Broken Link . . . 15 3.4.3. Automatic Route Shortening . . . . . . . . . . . 16 - 3.4.4. Increased Spreading of Route Error Messages . . . 17 + 3.4.4. Increased Spreading of Route Error Messages . . . 16 3.5. Optional DSR Flow State Extension . . . . . . . . . . . . 17 - 3.5.1. Flow Establishment . . . . . . . . . . . . . . . 18 + 3.5.1. Flow Establishment . . . . . . . . . . . . . . . 17 3.5.2. Receiving and Forwarding Establishment Packets . 19 3.5.3. Sending Packets Along Established Flows . . . . . 19 3.5.4. Receiving and Forwarding Packets Sent Along Established Flows . . . . . . . . . . . . 20 3.5.5. Processing Route Errors . . . . . . . . . . . . . 21 3.5.6. Interaction with Automatic Route Shortening . . . 21 - 3.5.7. Loop Detection . . . . . . . . . . . . . . . . . 22 + 3.5.7. Loop Detection . . . . . . . . . . . . . . . . . 21 3.5.8. Acknowledgement Destination . . . . . . . . . . . 22 3.5.9. Crash Recovery . . . . . . . . . . . . . . . . . 22 3.5.10. Rate Limiting . . . . . . . . . . . . . . . . . . 22 - 3.5.11. Interaction with Packet Salvaging . . . . . . . . 23 - - 4. Conceptual Data Structures 24 + 3.5.11. Interaction with Packet Salvaging . . . . . . . . 22 - 4.1. Route Cache . . . . . . . . . . . . . . . . . . . . . . . 24 - 4.2. Send Buffer . . . . . . . . . . . . . . . . . . . . . . . 27 - 4.3. Route Request Table . . . . . . . . . . . . . . . . . . . 28 - 4.4. Gratuitous Route Reply Table . . . . . . . . . . . . . . 29 - 4.5. Network Interface Queue and Maintenance Buffer . . . . . 30 - 4.6. Blacklist . . . . . . . . . . . . . . . . . . . . . . . . 31 + 4. Conceptual Data Structures 23 - 5. Additional Conceptual Data Structures for Flow State Extension 32 + 4.1. Route Cache . . . . . . . . . . . . . . . . . . . . . . . 23 + 4.2. Send Buffer . . . . . . . . . . . . . . . . . . . . . . . 26 + 4.3. Route Request Table . . . . . . . . . . . . . . . . . . . 27 + 4.4. Gratuitous Route Reply Table . . . . . . . . . . . . . . 28 + 4.5. Network Interface Queue and Maintenance Buffer . . . . . 29 + 4.6. Blacklist . . . . . . . . . . . . . . . . . . . . . . . . 30 + 5. Additional Conceptual Data Structures for Flow State Extension 31 - 5.1. Flow Table . . . . . . . . . . . . . . . . . . . . . . . 32 - 5.2. Automatic Route Shortening Table . . . . . . . . . . . . 33 - 5.3. Default Flow ID Table . . . . . . . . . . . . . . . . . . 33 + 5.1. Flow Table . . . . . . . . . . . . . . . . . . . . . . . 31 + 5.2. Automatic Route Shortening Table . . . . . . . . . . . . 32 + 5.3. Default Flow ID Table . . . . . . . . . . . . . . . . . . 32 - 6. DSR Options Header Format 35 + 6. DSR Options Header Format 34 - 6.1. Fixed Portion of DSR Options Header . . . . . . . . . . . 36 - 6.2. Route Request Option . . . . . . . . . . . . . . . . . . 39 - 6.3. Route Reply Option . . . . . . . . . . . . . . . . . . . 41 - 6.4. Route Error Option . . . . . . . . . . . . . . . . . . . 43 - 6.4.1. Node Unreachable Type-Specific Information . . . 45 - 6.4.2. Flow State Not Supported Type-Specific Information 45 - 6.4.3. Option Not Supported Type-Specific Information . 45 - 6.5. Acknowledgement Request Option . . . . . . . . . . . . . 46 - 6.6. Acknowledgement Option . . . . . . . . . . . . . . . . . 47 - 6.7. DSR Source Route Option . . . . . . . . . . . . . . . . . 48 - 6.8. Pad1 Option . . . . . . . . . . . . . . . . . . . . . . . 50 - 6.9. PadN Option . . . . . . . . . . . . . . . . . . . . . . . 51 + 6.1. Fixed Portion of DSR Options Header . . . . . . . . . . . 35 + 6.2. Route Request Option . . . . . . . . . . . . . . . . . . 38 + 6.3. Route Reply Option . . . . . . . . . . . . . . . . . . . 40 + 6.4. Route Error Option . . . . . . . . . . . . . . . . . . . 42 + 6.4.1. Node Unreachable Type-Specific Information . . . 44 + 6.4.2. Flow State Not Supported Type-Specific Information 44 + 6.4.3. Option Not Supported Type-Specific Information . 44 + 6.5. Acknowledgement Request Option . . . . . . . . . . . . . 45 + 6.6. Acknowledgement Option . . . . . . . . . . . . . . . . . 46 + 6.7. DSR Source Route Option . . . . . . . . . . . . . . . . . 47 + 6.8. Pad1 Option . . . . . . . . . . . . . . . . . . . . . . . 49 + 6.9. PadN Option . . . . . . . . . . . . . . . . . . . . . . . 50 - 7. Additional Header Formats and Options for Flow State Extension 52 + 7. Additional Header Formats and Options for Flow State Extension 51 - 7.1. DSR Flow State Header . . . . . . . . . . . . . . . . . . 53 - 7.2. Options and Extensions in DSR Options Header . . . . . . 54 - 7.2.1. Timeout Option . . . . . . . . . . . . . . . . . 54 - 7.2.2. Destination and Flow ID Option . . . . . . . . . 55 - 7.2.3. New Error Type Value for Unknown Flow . . . . . . 56 - 7.2.4. New Error Type Value for Default Flow Unknown . . 57 - 7.2.5. Acknowledgement Request Option - Previous Hop Address Extension . . . . . . 58 + 7.1. DSR Flow State Header . . . . . . . . . . . . . . . . . . 52 + 7.2. New Options and Extensions in DSR Options Header . . . . 53 + 7.2.1. Timeout Option . . . . . . . . . . . . . . . . . 53 + 7.2.2. Destination and Flow ID Option . . . . . . . . . 54 + 7.3. New Error Types for Route Error Option . . . . . . . . . 55 + 7.3.1. Unknown Flow Type-Specific Information . . . . . 55 + 7.3.2. Default Flow Unknown Type-Specific Information . 56 + 7.4. New Acknowledgement Request Option Extension . . . . . . 57 + 7.4.1. Previous Hop Address Extension . . . . . . . . . 57 - 8. Detailed Operation 59 + 8. Detailed Operation 58 - 8.1. General Packet Processing . . . . . . . . . . . . . . . . 59 - 8.1.1. Originating a Packet . . . . . . . . . . . . . . 59 - 8.1.2. Adding a DSR Options Header to a Packet . . . . . 59 - 8.1.3. Adding a DSR Source Route Option to a Packet . . 60 - 8.1.4. Processing a Received Packet . . . . . . . . . . 61 - 8.1.5. Processing a Received DSR Source Route Option . . 63 - 8.1.6. Handling an Unknown DSR Option . . . . . . . . . 65 - 8.2. Route Discovery Processing . . . . . . . . . . . . . . . 67 - 8.2.1. Originating a Route Request . . . . . . . . . . . 67 - 8.2.2. Processing a Received Route Request Option . . . 69 - 8.2.3. Generating a Route Reply using the Route Cache . 71 - 8.2.4. Originating a Route Reply . . . . . . . . . . . . 73 - 8.2.5. Processing a Received Route Reply Option . . . . 75 - 8.3. Route Maintenance Processing . . . . . . . . . . . . . . 76 - 8.3.1. Using Link-Layer Acknowledgements . . . . . . . . 76 - 8.3.2. Using Passive Acknowledgements . . . . . . . . . 77 - 8.3.3. Using Network-Layer Acknowledgements . . . . . . 78 - 8.3.4. Originating a Route Error . . . . . . . . . . . . 81 - 8.3.5. Processing a Received Route Error Option . . . . 82 - 8.3.6. Salvaging a Packet . . . . . . . . . . . . . . . 83 - 8.4. Multiple Interface Support . . . . . . . . . . . . . . . 85 - 8.5. Fragmentation and Reassembly . . . . . . . . . . . . . . 86 - 8.6. Flow State Processing . . . . . . . . . . . . . . . . . . 87 - 8.6.1. Originating a Packet . . . . . . . . . . . . . . 87 - 8.6.2. Inserting a DSR Flow State Header . . . . . . . . 89 - 8.6.3. Receiving a Packet . . . . . . . . . . . . . . . 89 - 8.6.4. Forwarding a Packet Using Flow IDs . . . . . . . 94 - 8.6.5. Promiscuously Receiving a Packet . . . . . . . . 94 + 8.1. General Packet Processing . . . . . . . . . . . . . . . . 58 + 8.1.1. Originating a Packet . . . . . . . . . . . . . . 58 + 8.1.2. Adding a DSR Options Header to a Packet . . . . . 58 + 8.1.3. Adding a DSR Source Route Option to a Packet . . 59 + 8.1.4. Processing a Received Packet . . . . . . . . . . 60 + 8.1.5. Processing a Received DSR Source Route Option . . 62 + 8.1.6. Handling an Unknown DSR Option . . . . . . . . . 64 + 8.2. Route Discovery Processing . . . . . . . . . . . . . . . 66 + 8.2.1. Originating a Route Request . . . . . . . . . . . 66 + 8.2.2. Processing a Received Route Request Option . . . 68 + 8.2.3. Generating a Route Reply using the Route Cache . 70 + 8.2.4. Originating a Route Reply . . . . . . . . . . . . 72 + 8.2.5. Preventing Route Reply Storms . . . . . . . . . . 74 + 8.2.6. Processing a Received Route Reply Option . . . . 75 + 8.3. Route Maintenance Processing . . . . . . . . . . . . . . 77 + 8.3.1. Using Link-Layer Acknowledgements . . . . . . . . 77 + 8.3.2. Using Passive Acknowledgements . . . . . . . . . 78 + 8.3.3. Using Network-Layer Acknowledgements . . . . . . 79 + 8.3.4. Originating a Route Error . . . . . . . . . . . . 82 + 8.3.5. Processing a Received Route Error Option . . . . 83 + 8.3.6. Salvaging a Packet . . . . . . . . . . . . . . . 84 + 8.4. Multiple Network Interface Support . . . . . . . . . . . 86 + 8.5. IP Fragmentation and Reassembly . . . . . . . . . . . . . 87 + 8.6. Flow State Processing . . . . . . . . . . . . . . . . . . 88 + 8.6.1. Originating a Packet . . . . . . . . . . . . . . 88 + 8.6.2. Inserting a DSR Flow State Header . . . . . . . . 90 + 8.6.3. Receiving a Packet . . . . . . . . . . . . . . . 90 + 8.6.4. Forwarding a Packet Using Flow IDs . . . . . . . 95 + 8.6.5. Promiscuously Receiving a Packet . . . . . . . . 95 8.6.6. Operation where the Layer below DSR Decreases - the IP TTL Non-Uniformly . . . . . . . . . 95 - 8.6.7. Salvage Interactions with DSR . . . . . . . . . . 95 + the IP TTL Non-Uniformly . . . . . . . . . 96 + 8.6.7. Salvage Interactions with DSR . . . . . . . . . . 96 - 9. Protocol Constants and Configuration Variables 96 + 9. Protocol Constants and Configuration Variables 97 -10. IANA Considerations 97 +10. IANA Considerations 98 -11. Security Considerations 98 +11. Security Considerations 99 -Appendix A. Link-MaxLife Cache Description 99 +Appendix A. Link-MaxLife Cache Description 100 -Appendix B. Location of DSR in the ISO Network Reference Model 101 +Appendix B. Location of DSR in the ISO Network Reference Model 102 -Appendix C. Implementation and Evaluation Status 102 +Appendix C. Implementation and Evaluation Status 103 -Changes from Previous Version of the Draft 104 +Changes from Previous Version of the Draft 105 -Acknowledgements 105 +Acknowledgements 106 -References 106 +References 107 -Chair's Address 110 +Chair's Address 111 -Authors' Addresses 111 +Authors' Addresses 112 1. Introduction The Dynamic Source Routing protocol (DSR) [15, 16] is a simple and efficient routing protocol designed specifically for use in multi-hop wireless ad hoc networks of mobile nodes. Using DSR, the network is completely self-organizing and self-configuring, requiring no existing network infrastructure or administration. Network nodes cooperate to forward packets for each other to allow communication over multiple "hops" between nodes not directly within wireless @@ -274,27 +273,25 @@ cached route if the one it has been using should fail. This caching of multiple routes also avoids the overhead of needing to perform a new Route Discovery each time a route in use breaks. The sender of a packet selects and controls the route used for its own packets, which together with support for multiple routes also allows features such as load balancing to be defined. In addition, all routes used are easily guaranteed to be loop-free, since the sender can avoid duplicate hops in the routes selected. The operation of both Route Discovery and Route Maintenance in DSR - are designed to allow unidirectional links and asymmetric routes - to be easily supported. In particular, as noted in Section 2, in - wireless networks, it is possible that a link between two nodes may - not work equally well in both directions, due to differing antenna - or propagation patterns or sources of interference. DSR allows such - unidirectional links to be used when necessary, improving overall - performance and network connectivity in the system. + are designed to allow unidirectional links and asymmetric routes to + be supported. In particular, as noted in Section 2, in wireless + networks, it is possible that a link between two nodes may not + work equally well in both directions, due to differing antenna or + propagation patterns or sources of interference. This document specifies the operation of the DSR protocol for routing unicast IPv4 packets in multi-hop wireless ad hoc networks. Advanced, optional features, such as Quality of Service (QoS) support and efficient multicast routing, and operation of DSR with IPv6 [7], are covered in other documents. The specification of DSR in this document provides a compatible base on which such features can be added, either independently or by integration with the DSR operation specified here. @@ -354,39 +351,50 @@ receive mode, or can be programmed to only periodically switch the interface into promiscuous mode. Use of promiscuous receive mode is entirely optional. Wireless communication ability between any pair of nodes may at times not work equally well in both directions, due for example to differing antenna or propagation patterns or sources of interference around the two nodes [1, 20]. That is, wireless communications between each pair of nodes will in many cases be able to operate bidirectionally, but at times the wireless link between two nodes - may be only unidirectional, allowing one node to successfully send - packets to the other while no communication is possible in the - reverse direction. Although many routing protocols operate correctly - only over bidirectional links, DSR can successfully discover and - forward packets over paths that contain unidirectional links. Some - MAC protocols, however, such as MACA [19], MACAW [2], or IEEE - 802.11 [13], limit unicast data packet transmission to bidirectional - links, due to the required bidirectional exchange of RTS and CTS - packets in these protocols and due to the link-layer acknowledgement - feature in IEEE 802.11; when used on top of MAC protocols such as - these, DSR can take advantage of additional optimizations, such as - the ability to reverse a source route to obtain a route back to the - origin of the original route. + may be only unidirectional, allowing one node to successfully + send packets to the other while no communication is possible + in the reverse direction. Some MAC protocols, however, such as + MACA [19], MACAW [2], or IEEE 802.11 [13], limit unicast data + packet transmission to bidirectional links, due to the required + bidirectional exchange of RTS and CTS packets in these protocols and + due to the link-layer acknowledgement feature in IEEE 802.11; when + used on top of MAC protocols such as these, DSR can take advantage + of additional optimizations, such as the ability to reverse a source + route to obtain a route back to the origin of the original route. The IP address used by a node using the DSR protocol MAY be assigned by any mechanism (e.g., static assignment or use of DHCP for dynamic assignment [8]), although the method of such assignment is outside the scope of this specification. + A routing protocol such as DSR chooses a next-hop for each packet + and provides the IP address of that next-hop. When the packet + is transmitted, however, the lower-layer protocol often has a + separate, MAC-layer address for the next-hop node. DSR uses the + Address Resolution Protocol (ARP) [30] to translate from next-hop IP + addresses to next-hop MAC addresses. In addition, a node MAY add + an entry to its ARP cache based on any received packet, when the IP + address and MAC address of the transmitting node are available in + the packet; for example, the IP address of the transmitting node + is present in a Route Request option (in the Address list being + accumulated) and any packets containing a source route. Adding + entries to the ARP cache in this way avoids the overhead of ARP in + most cases. + 3. DSR Protocol Overview This section provides an overview of the operation of the DSR protocol. The basic version of DSR uses explicit "source routing", in which each data packet sent carries in its header the complete, ordered list of nodes through which the packet will pass. This use of explicit source routing allows the sender to select and control the routes used for its own packets, supports the use of multiple routes to any destination (for example, for load balancing), and allows a simple guarantee that the routes used are loop-free; by @@ -444,77 +452,75 @@ a "Route Reply" to the initiator of the Route Discovery, giving a copy of the accumulated route record from the Route Request; when the initiator receives this Route Reply, it caches this route in its Route Cache for use in sending subsequent packets to this destination. Otherwise, if this node receiving the Route Request has recently seen another Route Request message from this initiator bearing this same request identification and target address, or if this node's own address is already listed in the route record in the Route Request, - this node discards the Request. Otherwise, this node appends its - own address to the route record in the Route Request and propagates - it by transmitting it as a local broadcast packet (with the same - request identification). In this example, node B broadcast the Route - Request, which is received by node C; nodes C and D each also, in - turn, broadcast the Request, resulting in a copy of the Request being - received by node E. + this node discards the Request. (A node considers a Request recently + seen if it still has information about that Request in its Route + Request Table, which is described in Section 4.3.) Otherwise, this + node appends its own address to the route record in the Route Request + and propagates it by transmitting it as a local broadcast packet + (with the same request identification). In this example, node B + broadcast the Route Request, which is received by node C; nodes C + and D each also, in turn, broadcast the Request, resulting in a copy + of the Request being received by node E. In returning the Route Reply to the initiator of the Route Discovery, such as in this example, node E replying back to node A, node E will typically examine its own Route Cache for a route back to A, and if found, will use it for the source route for delivery of the packet containing the Route Reply. Otherwise, E SHOULD perform its own Route Discovery for target node A, but to avoid possible infinite recursion of Route Discoveries, it MUST piggyback this Route Reply on the packet containing its own Route Request for A. It is also possible to piggyback other small data packets, such as a TCP SYN - packet [31], on a Route Request using this same mechanism. + packet [33], on a Route Request using this same mechanism. Node E could instead simply reverse the sequence of hops in the route record that it is trying to send in the Route Reply, and use this as the source route on the packet carrying the Route Reply itself. For MAC protocols such as IEEE 802.11 that require a bidirectional frame exchange as part of the MAC protocol [13], the discovered source route MUST be reversed in this way to return the Route Reply since it tests the discovered route to ensure it is bidirectional before the Route Discovery initiator begins using the route; this route reversal also avoids the overhead of a possible second Route Discovery. - However, this route reversal technique will prevent the discovery of - routes using unidirectional links, and in wireless environments where - the use of unidirectional links is permitted, such routes may in some - cases be more efficient than those with only bidirectional links, or - they may be the only way to achieve connectivity to the target node. - When initiating a Route Discovery, the sending node saves a copy of the original packet (that triggered the Discovery) in a local buffer called the "Send Buffer". The Send Buffer contains a copy of each packet that cannot be transmitted by this node because it does not yet have a source route to the packet's destination. Each packet in the Send Buffer is logically associated with the time that it was placed into the Send Buffer and is discarded after residing in the - Send Buffer for some timeout period; if necessary for preventing the - Send Buffer from overflowing, a FIFO or other replacement strategy - MAY also be used to evict packets even before they expire. + Send Buffer for some timeout period SendBufferTimeout; if necessary + for preventing the Send Buffer from overflowing, a FIFO or other + replacement strategy MAY also be used to evict packets even before + they expire. While a packet remains in the Send Buffer, the node SHOULD occasionally initiate a new Route Discovery for the packet's destination address. However, the node MUST limit the rate at which - such new Route Discoveries for the same address are initiated, since - it is possible that the destination node is not currently reachable. - In particular, due to the limited wireless transmission range and the - movement of the nodes in the network, the network may at times become - partitioned, meaning that there is currently no sequence of nodes - through which a packet could be forwarded to reach the destination. - Depending on the movement pattern and the density of nodes in the - network, such network partitions may be rare or may be common. + such new Route Discoveries for the same address are initiated (as + described in Section 4.3), since it is possible that the destination + node is not currently reachable. In particular, due to the limited + wireless transmission range and the movement of the nodes in the + network, the network may at times become partitioned, meaning that + there is currently no sequence of nodes through which a packet could + be forwarded to reach the destination. Depending on the movement + pattern and the density of nodes in the network, such network + partitions may be rare or may be common. If a new Route Discovery was initiated for each packet sent by a node in such a partitioned network, a large number of unproductive Route Request packets would be propagated throughout the subset of the ad hoc network reachable from this node. In order to reduce the overhead from such Route Discoveries, a node SHOULD use an exponential back-off algorithm to limit the rate at which it initiates new Route Discoveries for the same target, doubling the timeout between each successive Discovery initiated for the same target. If the node attempts to send additional data packets to this @@ -550,22 +556,22 @@ protocol in use (such as the link-layer acknowledgement frame defined by IEEE 802.11 [13]), or by a "passive acknowledgement" [18] (in which, for example, B confirms receipt at C by overhearing C transmit the packet when forwarding it on to D). If a built-in acknowledgement mechanism is not available, the node transmitting the packet can explicitly request a DSR-specific software acknowledgement be returned by the next node along the route; this software acknowledgement will normally be transmitted directly to the sending node, but if the link between these two nodes - is unidirectional, this software acknowledgement could travel over a - different, multi-hop path. + is unidirectional (Section 4.6), this software acknowledgement could + travel over a different, multi-hop path. After an acknowledgement has been received from some neighbor, a node MAY choose to not require acknowledgements from that neighbor for a brief period of time, unless the network interface connecting a node to that neighbor always receives an acknowledgement in response to unicast traffic. When a software acknowledgement is used, the acknowledgement request SHOULD be retransmitted up to a maximum number of times. A retransmission of the acknowledgement request can be sent as a @@ -715,91 +721,21 @@ means that a future Route Error traversing the route is very likely to pass through any node that sent the Route Reply for the route (including node F), which helps to ensure that stale data is removed from caches (such as at F) in a timely manner; otherwise, the next Route Discovery initiated by A might also be contaminated by a Route Reply from F containing the same stale route. If node F, due to this restriction on returning a Route Reply based on information from its Route Cache, does not return such a Route Reply, node F propagates the Route Request normally. -3.3.3. Preventing Route Reply Storms - - The ability for nodes to reply to a Route Request based on - information in their Route Caches, as described in Section 3.3.2, - could result in a possible Route Reply "storm" in some cases. In - particular, if a node broadcasts a Route Request for a target node - for which the node's neighbors have a route in their Route Caches, - each neighbor may attempt to send a Route Reply, thereby wasting - bandwidth and possibly increasing the number of network collisions in - the area. - - For example, the figure below shows a situation in which nodes B, C, - D, E, and F all receive A's Route Request for target G, and each has - the indicated route cached for this target: - - +-----+ +-----+ - | D |< >| C | - +-----+ \ / +-----+ - Cache: C - B - G \ / Cache: B - G - \ +-----+ / - -| A |- - +-----+\ +-----+ +-----+ - | | \--->| B | | G | - / \ +-----+ +-----+ - / \ Cache: G - v v - +-----+ +-----+ - | E | | F | - +-----+ +-----+ - Cache: F - B - G Cache: B - G - - Normally, each of these nodes would attempt to reply from its own - Route Cache, and they would thus all send their Route Replies at - about the same time, since they all received the broadcast Route - Request at about the same time. Such simultaneous Route Replies - from different nodes all receiving the Route Request may cause local - congestion in the wireless network and may create packet collisions - among some or all of these Replies if the MAC protocol in use does - not provide sufficient collision avoidance for these packets. In - addition, it will often be the case that the different replies will - indicate routes of different lengths, as shown in this example. - - In order to reduce these effects, if a node can put its network - interface into promiscuous receive mode, it MAY delay sending its - own Route Reply for a short period, while listening to see if the - initiating node begins using a shorter route first. Specifically, - this node MAY delay sending its own Route Reply for a random period - - d = H * (h - 1 + r) - - where h is the length in number of network hops for the route to be - returned in this node's Route Reply, r is a random floating point - number between 0 and 1, and H is a small constant delay (at least - twice the maximum wireless link propagation delay) to be introduced - per hop. This delay effectively randomizes the time at which each - node sends its Route Reply, with all nodes sending Route Replies - giving routes of length less than h sending their Replies before this - node, and all nodes sending Route Replies giving routes of length - greater than h sending their Replies after this node. - - Within the delay period, this node promiscuously receives all - packets, looking for data packets from the initiator of this Route - Discovery destined for the target of the Discovery. If such a data - packet received by this node during the delay period uses a source - route of length less than or equal to h, this node may infer that the - initiator of the Route Discovery has already received a Route Reply - giving an equally good or better route. In this case, this node - SHOULD cancel its delay timer and SHOULD NOT send its Route Reply for - this Route Discovery. - -3.3.4. Route Request Hop Limits +3.3.3. Route Request Hop Limits Each Route Request message contains a "hop limit" that may be used to limit the number of intermediate nodes allowed to forward that copy of the Route Request. This hop limit is implemented using the Time-to-Live (TTL) field in the IP header of the packet carrying the Route Request. As the Request is forwarded, this limit is decremented, and the Request packet is discarded if the limit reaches zero before finding the target. This Route Request hop limit can be used to implement a variety of algorithms for controlling the spread of a Route Request during a Route Discovery attempt. @@ -808,23 +744,24 @@ "non-propagating" Route Request as an initial phase of a Route Discovery. A node using this technique sends its first Route Request attempt for some target node using a hop limit of 1, such that any node receiving the initial transmission of the Route Request will not forward the Request to other nodes by re-broadcasting it. This form of Route Request is called a "non-propagating" Route Request; it provides an inexpensive method for determining if the target is currently a neighbor of the initiator or if a neighbor node has a route to the target cached (effectively using the neighbors' Route Caches as an extension of the initiator's own Route Cache). If no - Route Reply is received after a short timeout, then the node sends a - "propagating" Route Request (i.e., with no hop limit) for the target - node. + Route Reply is received after a short timeout, then the node sends + a "propagating" Route Request for the target node (i.e., with hop + limit as defined by the value of the DiscoveryHopLimit configuration + variable). As another example, a node MAY use this hop limit to implement an "expanding ring" search for the target [16]. A node using this technique sends an initial non-propagating Route Request as described above; if no Route Reply is received for it, the node originates another Route Request with a hop limit of 2. For each Route Request originated, if no Route Reply is received for it, the node doubles the hop limit used on the previous attempt, to progressively explore for the target node without allowing the Route Request to propagate over the entire network. However, this expanding ring search @@ -844,24 +781,27 @@ source route on the packet with the route from its Route Cache. The node then forwards the packet to the next node indicated along this source route. For example, in the situation shown in the example of Section 3.2, if node C has another route cached to node E, it can salvage the packet by replacing the original route in the packet with this new route from its own Route Cache, rather than discarding the packet. When salvaging a packet, a count is maintained in the packet of the number of times that it has been salvaged, to prevent a single packet - from being salvaged endlessly. Otherwise, it could be possible for - the packet to enter a routing loop, as different nodes repeatedly - salvage the packet and replace the source route on the packet with - routes to each other. + from being salvaged endlessly. Otherwise, since TTL is decremented + only once by each node, a single node could salvage a packet an + unbounded number of times. Even if we chose to require TTL to be + decremented on each salvage attempt, packet salvaging is an expensive + operation, so it is desirable to bound the maximum number of times a + packet can be salvaged independently of the maximum number of hops a + packet can traverse. As described in Section 3.2, an intermediate node, such as in this case, that detects through Route Maintenance that the next hop along the route for a packet that it is forwarding is broken, the node also SHOULD return a Route Error to the original sender of the packet, identifying the link over which the packet could not be forwarded. If the node sends this Route Error, it SHOULD originate the Route Error before salvaging the packet. 3.4.2. Queued Packets Destined over a Broken Link @@ -925,21 +865,21 @@ overheard packet (node B), plus the suffix of the original source route beginning with the node returning the gratuitous Route Reply (node D). In this example, the route returned in the gratuitous Route Reply message sent from D to A gives the new route as the sequence of hops from A to B to D to E. When deciding whether to return a gratuitous Route Reply in this way, a node MAY factor in additional information beyond the fact that it was able to overhear the packet. For example, the node MAY decide to return the gratuitous Route Reply only when the overheard packet is - received with a signal strenth or signal-to-noise ratio above some + received with a signal strength or signal-to-noise ratio above some specific threshold. In addition, each node maintains a Gratuitous Route Reply Table, as described in Section 4.4, to limit the rate at which it originates gratuitous Route Replies for the same returned route. 3.4.4. Increased Spreading of Route Error Messages When a source node receives a Route Error for a data packet that it originated, this source node propagates this Route Error to its neighbors by piggybacking it on its next Route Request. In this way, @@ -1027,21 +967,22 @@ DSR Options header, giving the lifetime after which state information about this flow is to expire. This packet will generally be a normal data packet being sent from this sender to the receiver (for example, the first packet sent after discovering the new route) but is also treated as a "flow establishment" packet. The source node records this flow in its Flow Table for future use, setting the TTL in this Flow Table entry to be the value used in the TTL field in the packet's IP header and setting the Lifetime in this entry to be the lifetime specified in the Timeout option in the DSR - Options header. + Options header. The TTL field is used for Default Flow Forwarding, + as described in Sections 3.5.3 and 3.5.4. Any further packets sent with this flow ID before the timeout that also contain a DSR Options header with a Source Route option MUST use this same source route in the Source Route option. 3.5.2. Receiving and Forwarding Establishment Packets Packets intended to establish a flow, as described in Section 3.5.1, contain a DSR Options header with a Source Route option, and are forwarded along the indicated route. A node implementing the DSR @@ -1155,40 +1096,41 @@ the flow to indicate that it has not been established end-to-end. When a node receives a Route Error of type Default Flow Unknown, it marks the default flow to indicate that it has not been established end-to-end. 3.5.6. Interaction with Automatic Route Shortening Because a full source route is not carried in every packet, an alternative method for performing automatic route shortening is necessary for packets using the flow state extension. Instead, nodes - promiscuously listen to packets, and if a node receives a packet - with (IP Source, IP Destination, Flow ID) found in the Flow Table - but the MAC-layer (next hop) destination address of the packet is - not this node, the node determines whether the packet was sent by - an upstream or downstream node by examining the Hop Count field in - the DSR Flow State header. If the Hop Count field is less than the - expected Hop Count at this node, the node assumes that the packet - was sent by an upstream node, and adds an entry for the packet to - its Automatic Route Shortening Table, possibly evicting an earlier + promiscuously listen to packets, and if a node receives a packet with + (IP Source, IP Destination, Flow ID) found in the Flow Table but the + MAC-layer (next hop) destination address of the packet is not this + node, the node determines whether the packet was sent by an upstream + or downstream node by examining the Hop Count field in the DSR Flow + State header. If the Hop Count field is less than the expected + Hop Count at this node (that is, the expected Hop Count field in + the Flow Table described in Section 5.1), the node assumes that the + packet was sent by an upstream node, and adds an entry for the packet + to its Automatic Route Shortening Table, possibly evicting an earlier entry added to this table. When the packet is then sent to that node for forwarding, the node finds that it has previously received the packet by checking its Automatic Route Shortening Table, and returns a gratuitous Route Reply to the source of the packet. 3.5.7. Loop Detection - If a node receives a packet for forwarding with adjusted TTL lower - than expected and default flow forwarding is being used, it sends - a Route Error of type Default Flow Unknown back to the IP source. - It can attempt delivery of the packet by normal salvaging (subject + If a node receives a packet for forwarding with TTL lower than + expected and default flow forwarding is being used, it sends a + Route Error of type Default Flow Unknown back to the IP source. It + can attempt delivery of the packet by normal salvaging (subject to constraints described in Section 8.6.7) or by inserting a Flow ID option with Special TTL extension based on what that node's understanding of the default Flow ID and TTL. 3.5.8. Acknowledgement Destination In packets sent using Flow State, the previous hop is not necessarily known. In order to allow nodes that have lost flow state to determine the previous hop, the address of the previous hop can optionally be stored in the Acknowledgement Request. This extension @@ -1229,28 +1171,29 @@ in a DSR Options header, packets without a Source Route option are considered to have the value zero in the Salvage field. 4. Conceptual Data Structures This document describes the operation of the DSR protocol in terms of a number of conceptual data structures. This section describes each of these data structures and provides an overview of its use in the protocol. In an implementation of the protocol, these data structures MAY be implemented in any manner consistent with the - external behavior described in this document. + external behavior described in this document. Additional conceptual + data structures are required for the optional flow state extensions + to DSR; these data structures are described in Section 5. 4.1. Route Cache - All ad hoc network routing information needed by a node implementing - DSR is stored in that node's Route Cache. Each node in the network - maintains its own Route Cache. A node adds information to its - Route Cache as it learns of new links between nodes in the ad hoc + Each node implementing DSR MUST maintain a Route Cache, containing + routing information needed by the node. A node adds information to + its Route Cache as it learns of new links between nodes in the ad hoc network; for example, a node may learn of new links when it receives a packet carrying a Route Request, Route Reply, or DSR source route. Likewise, a node removes information from its Route Cache as it learns that existing links in the ad hoc network have broken; for example, a node may learn of a broken link when it receives a packet carrying a Route Error or through the link-layer retransmission mechanism reporting a failure in forwarding a packet to its next-hop destination. Anytime a node adds new information to its Route Cache, the node @@ -1410,40 +1353,40 @@ The Send Buffer of a node implementing DSR is a queue of packets that cannot be sent by that node because it does not yet have a source route to each such packet's destination. Each packet in the Send Buffer is logically associated with the time that it was placed into the Buffer, and SHOULD be removed from the Send Buffer and silently discarded after a period of SendBufferTimeout after initially being placed in the Buffer. If necessary, a FIFO strategy SHOULD be used to evict packets before they timeout to prevent the buffer from overflowing. - Subject to the rate limiting defined in Section 8.2, a Route + Subject to the rate limiting defined in Section 4.3, a Route Discovery SHOULD be initiated as often as possible for the destination address of any packets residing in the Send Buffer. 4.3. Route Request Table The Route Request Table of a node implementing DSR records information about Route Requests that have been recently originated or forwarded by this node. The table is indexed by IP address. The Route Request Table on a node records the following information about nodes to which this node has initiated a Route Request: - The Time-to-Live (TTL) field used in the IP header of the Route Request for the last Route Discovery initiated by this node for that target node. This value allows the node to implement a variety of algorithms for controlling the spread of its Route Request on each Route Discovery initiated for a target. As examples, two possible algorithms for this use of the TTL field - are described in Section 3.3.4. + are described in Section 3.3.3. - The time that this node last originated a Route Request for that target node. - The number of consecutive Route Discoveries initiated for this target since receiving a valid Route Reply giving a route to that target node. - The remaining amount of time before which this node MAY next attempt at a Route Discovery for that target node. When the @@ -1537,21 +1480,21 @@ requires limited buffering of packets already transmitted for which the reachability of the next-hop destination has not yet been determined. The operation of DSR is defined here in terms of two conceptual data structures that together incorporate this queuing behavior. The Network Interface Queue of a node implementing DSR is an output queue of packets from the network protocol stack waiting to be transmitted by the network interface; for example, in the 4.4BSD Unix network protocol stack implementation, this queue for a network - interface is represented as a "struct ifqueue" [36]. This queue is + interface is represented as a "struct ifqueue" [38]. This queue is used to hold packets while the network interface is in the process of transmitting another packet. The Maintenance Buffer of a node implementing DSR is a queue of packets sent by this node that are awaiting next-hop reachability confirmation as part of Route Maintenance. For each packet in the Maintenance Buffer, a node maintains a count of the number of retransmissions and the time of the last retransmission. The Maintenance Buffer MAY be of limited size; when adding a new packet to the Maintenance Buffer, if the buffer size is insufficient to hold @@ -1568,43 +1511,46 @@ that might be attempted for a packet at the link layer or within the network interface hardware. The timeout value to use for each transmission attempt for an acknowledgement request depends on the type of acknowledgement mechanism used by Route Maintenance for that attempt, as described in Section 8.3. 4.6. Blacklist When a node using the DSR protocol is connected through an interface that requires physically bidirectional links for unicast - transmission, it MUST maintain a blacklist. A Blacklist is a table, - indexed by neighbor address, that indicates that the link between - this node and the specified neighbor may not be bidirectional. A - node places another node's address in this list when it believes that - broadcast packets from that other node reach this node, but that - unicast transmission between the two nodes is not possible. For - example, if a node forwarding a Route Reply discovers that the next - hop is unreachable, it places that next hop in the node's blacklist. + transmission, it MUST maintain a Blacklist. The Blacklist is a + table, indexed by neighbor node address, that indicates that the + link between this node and the specified neighbor node may not be + bidirectional. A node places another node's address in this list + when it believes that broadcast packets from that other node reach + this node, but that unicast transmission between the two nodes is not + possible. For example, if a node forwarding a Route Reply discovers + that the next hop is unreachable, it places that next hop in the + node's Blacklist. Once a node discovers that it can communicate bidirectionally with - one of the nodes listed in the blacklist, it SHOULD remove that - node from the blacklist. For example, if node A has node B in its - blacklist, but A hears B forward a Route Request with a hop list - indicating that the broadcast from A to B was successful, then A - SHOULD remove B from its blacklist. + one of the nodes listed in the Blacklist, it SHOULD remove that + node from the Blacklist. For example, if node A has node B listed + in its Blacklist, but after transmitting a Route Request, node A + hears B forward the Route Request with a hop list indicating that the + broadcast from A to B was successful, then A SHOULD remove the entry + for node B from its Blacklist. - A node MUST associate a state with each node in the blacklist, - specifying whether the unidirectionality is "questionable" - or "probable". Each time the unreachability is positively - determined, the node SHOULD set the state to "probable". After the - unreachability has not been positively determined for some amount of - time, the state should revert to "questionable". A node MAY expire - nodes from its blacklist after a reasonable amount of time. + A node MUST associate a state with each node listed in its Blacklist, + specifying whether the unidirectionality of the link to that node + is "questionable" or "probable". Each time the unreachability is + positively determined, the node SHOULD set the state to "probable". + After the unreachability has not been positively determined for some + amount of time, the state SHOULD revert to "questionable". A node + MAY expire entries for nodes from its Blacklist after a reasonable + amount of time. 5. Additional Conceptual Data Structures for Flow State Extension This section defines additional conceptual data structures used by the optional "flow state" extension to DSR. In an implementation of the protocol, these data structures MAY be implemented in any manner consistent with the external behavior described in this document. 5.1. Flow Table @@ -1763,21 +1709,21 @@ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ . . . Options . . . +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Next Header 8-bit selector. Identifies the type of header immediately following the DSR Options header. Uses the same values as the - IPv4 Protocol field [32]. + IPv4 Protocol field [34]. Flow State Header (F) Flag bit. MUST be set to 0. This bit is set in a DSR Flow State header (Section 7.1) and clear in a DSR Options header. Reserved MUST be sent as 0 and ignored on reception. @@ -1852,20 +1798,23 @@ - Acknowledgement Request option (Section 6.5) - Acknowledgement option (Section 6.6) - DSR Source Route option (Section 6.7) - Pad1 option (Section 6.8) - PadN option (Section 6.9) + In addition, Section 7 specifies further DSR options for use with the + optional DSR flow state extension. + 6.2. Route Request Option The Route Request option in a DSR Options header is encoded as follows: 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Option Type | Opt Data Len | Identification | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ @@ -1890,27 +1839,28 @@ Destination Address MUST be set to the IP limited broadcast address (255.255.255.255). Hop Limit (TTL) MAY be varied from 1 to 255, for example to implement non-propagating Route Requests and Route Request expanding-ring - searches (Section 3.3.4). + searches (Section 3.3.3). Route Request fields: Option Type - 2 + 1. Nodes not understanding this option will ignore this + option. Opt Data Len 8-bit unsigned integer. Length of the option, in octets, excluding the Option Type and Opt Data Len fields. Identification A unique value generated by the initiator (original sender) of the Route Request. Nodes initiating a Route Request generate @@ -1981,21 +1931,21 @@ MUST be set to the address of the source node of the route being returned. Copied from the Source Address field of the Route Request generating the Route Reply, or in the case of a gratuitous Route Reply, copied from the Source Address field of the data packet triggering the gratuitous Reply. Route Reply fields: Option Type - 1. Nodes not understanding this option will ignore this + 2. Nodes not understanding this option will ignore this option. Opt Data Len 8-bit unsigned integer. Length of the option, in octets, excluding the Option Type and Opt Data Len fields. Last Hop External (L) Set to indicate that the last hop given by the Route Reply @@ -2387,23 +2337,23 @@ Options header to make the total length a multiple of 4 octets. 7. Additional Header Formats and Options for Flow State Extension The optional DSR flow state extension requires a new header type, the DSR Flow State header. In addition, the DSR flow state extension adds the following options for the DSR Options header defined in Section 6: - - Timeout option + - Timeout option (Section 7.2.1 - - Destination and Flow ID option + - Destination and Flow ID option (Section 7.2.2 Two new Error Type values are also defined for use in the Route Error option in a DSR Options header: - Unknown Flow - Default Flow Unknown Finally, an extension to the Acknowledgement Request option in a DSR Options header is also defined: @@ -2423,37 +2373,37 @@ 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Next Header |F| Hop Count | Flow Identifier | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Next Header 8-bit selector. Identifies the type of header immediately following the DSR Flow State header. Uses the same values as - the IPv4 Protocol field [32]. + the IPv4 Protocol field [34]. Flow State Header (F) Flag bit. MUST be set to 1. This bit is set in a DSR Flow State header and clear in a DSR Options header (Section 6.1). Hop Count 7-bit unsigned integer. The number of hops through which this packet has been forwarded. Flow Identification The flow ID for this flow, as described in Section 3.5.1. -7.2. Options and Extensions in DSR Options Header +7.2. New Options and Extensions in DSR Options Header 7.2.1. Timeout Option The Timeout option is defined for use in a DSR Options header to indicate the amount of time before the expiration of the flow ID along which the packet is being sent. 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ @@ -2522,21 +2472,23 @@ the DSR Options header. New IP Destination Address Indicates the next address to store in the Destination Address field of the IP header. The Destination and Flow ID option MAY appear one or more times within a DSR Options header. -7.2.3. New Error Type Value for Unknown Flow +7.3. New Error Types for Route Error Option + +7.3.1. Unknown Flow Type-Specific Information A new Error Type value of 129 (Unknown Flow) is defined for use in a Route Error option in a DSR Options header. The Type-Specific Information for errors of this type is encoded as follows: 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Original IP Destination Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ @@ -2545,38 +2497,40 @@ Original IP Destination Address The IP Destination Address of the packet that caused the error. Flow ID The Flow ID contained in the DSR Flow ID option that caused the error. -7.2.4. New Error Type Value for Default Flow Unknown +7.3.2. Default Flow Unknown Type-Specific Information A new Error Type value of 130 (Default Flow Unknown) is defined for use in a Route Error option in a DSR Options header. The Type-Specific Information for errors of this type is encoded as follows: 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Original IP Destination Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Original IP Destination Address The IP Destination Address of the packet that caused the error. -7.2.5. Acknowledgement Request Option Previous Hop Address Extension +7.4. New Acknowledgement Request Option Extension + +7.4.1. Previous Hop Address Extension When the Option Length field of an Acknowledgement Request option in a DSR Options header is greater than or equal to 6, a Previous Hop Address Extension is present. The option is then formatted as follows: 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Option Type | Option Length | Packet Identifier | @@ -2667,21 +2621,21 @@ other headers that MUST be located in the packet before the DSR Options header): - Insert a DSR Options header after the IP header but before any other header that may be present. - Set the Next Header field of the DSR Options header to the Protocol number field of the packet's IP header. - Set the Protocol field of the packet's IP header to the Protocol - number assigned for a DSR Options header (TBA???). + number assigned for DSR (TBA???). 8.1.3. Adding a DSR Source Route Option to a Packet A node originating a packet adds a DSR Source Route option to the packet, if necessary, in order to carry the source route from this originating node to the final destination address of the packet. Specifically, the node adding the DSR Source Route option constructs the DSR Source Route option and modifies the IP packet according to the following sequence of steps: @@ -2758,21 +2712,21 @@ set in the Route Reply, the node MUST flag the last hop from the Route Reply (the link from Address[n-1] to Address[n]) in its Route Cache as External. The value n here is the number of addresses in the source route being returned in the Route Reply option, or (Opt Data Len - 1) / 4. After possibly updating the node's Route Cache in response to the routing information in the Route Reply option, then if the packet's IP Destination Address matches one of this node's IP addresses, the node MUST then process the Route Reply option as - described in Section 8.2.5. + described in Section 8.2.6. - If the DSR Options header contains a Route Error option, the node MUST process the Route Error option as described in Section 8.3.5. - If the DSR Options header contains an Acknowledgement Request option, the node MUST process the Acknowledgement Request option as described in Section 8.3.3. - If the DSR Options header contains an Acknowledgement option, @@ -2875,53 +2829,65 @@ - Discard the overheard packet, since the packet has been received before its normal traversal of the packet's source route would have caused it to reach this receiving node. Another copy of the packet will normally arrive at this node as indicated in the packet's source route; discarding this initial copy of the packet, which triggered the gratuitous Route Reply, will prevent the duplication of this packet that would otherwise occur. If the packet is not discarded as part of automatic route shortening - above, then the node MUST process the option according to the - following sequence of steps: + above, then the node MUST process the Source Route option according + to the following sequence of steps: - If the value of the Segments Left field in the DSR Source Route option equals 0, then remove the DSR Source Route option from the DSR Options header. - Else, let n equal (Opt Data Len - 2) / 4. This is the number of addresses in the DSR Source Route option. - If the value of the Segments Left field is greater than n, then - send an ICMP Parameter Problem, Code 0, message [29] to the IP + send an ICMP Parameter Problem, Code 0, message [31] to the IP Source Address, pointing to the Segments Left field, and discard the packet. Do not process the DSR Source Route option further. - Else, decrement the value of the Segments Left field by 1. Let i equal n minus Segments Left. This is the index of the next address to be visited in the Address vector. - If Address[i] or the IP Destination Address is a multicast address, then discard the packet. Do not process the DSR Source Route option further. + - If this node has more than one network interface and if + Address[i] is the address of one this node's network interfaces, + then this indicates a change in the network interface to use in + forwarding the packet, as described in Section 8.4. In this + case, decrement the value of the Segments Left field by 1 to + skip over this address (that indicated the change of network + interface) and go to the first step above (checking the value of + the Segments Left field) to continue processing this Source Route + option; in further processing of this Source Route option, the + indicated new network interface MUST be used in forwarding the + packet. + - If the MTU of the link over which this node would transmit the packet to forward it to the node Address[i] is less than the size of the packet, the node MUST either discard the packet and send an ICMP Packet Too Big message to the packet's - Source Address [29] or fragment it as specified in Section 8.5. + Source Address [31] or fragment it as specified in Section 8.5. - Forward the packet to the IP address specified in the Address[i] field of the IP header, following normal IP forwarding procedures, including checking and decrementing the Time-to-Live - (TTL) field in the packet's IP header [30, 3]. In this + (TTL) field in the packet's IP header [32, 3]. In this forwarding of the packet, the next-hop node (identified by Address[i]) MUST be treated as a direct neighbor node: the transmission to that next node MUST be done in a single IP forwarding hop, without Route Discovery and without searching the Route Cache. - In forwarding the packet, perform Route Maintenance for the next hop of the packet, by verifying that the next-hop node is reachable, as described in Section 8.3. @@ -3048,21 +3014,21 @@ update that information in the table entry for use in the next Route Request initiated for this target. In particular: - The Route Request Table entry for a target node records the Time-to-Live (TTL) field used in the IP header of the Route Request for the last Route Discovery initiated by this node for that target node. This value allows the node to implement a variety of algorithms for controlling the spread of its Route Request on each Route Discovery initiated for a target. As examples, two possible algorithms for this use of the TTL field - are described in Section 3.3.4. + are described in Section 3.3.3. - The Route Request Table entry for a target node records the number of consecutive Route Requests initiated for this target since receiving a valid Route Reply giving a route to that target node, and the remaining amount of time before which this node MAY next attempt at a Route Discovery for that target node. A node MUST use these values to implement a back-off algorithm to limit the rate at which this node initiates new Route Discoveries for the same target address. In particular, until a valid Route @@ -3113,37 +3079,39 @@ as part of the Route Discovery. - Else, the node MUST examine the route recorded in the Route Request option (the IP Source Address field and the sequence of Address[i] fields) to determine if this node's own IP address already appears in this list of addresses. If so, the node MUST discard the entire packet carrying the Route Request option. - Else, if the Route Request was received through a network interface that requires physically bidirectional links for - unicast transmission, the node MUST check if the Request was last - forwarded by a node on its blacklist. If such an entry is found, - and the state of the unidirectional link is "probable", then the - Request MUST be silently discarded. + unicast transmission, the node MUST check if the Route Request + was last forwarded by a node on its Blacklist (Section 4.6). + If such an entry is found in the Blacklist, and the state of + the unidirectional link is "probable", then the Request MUST be + silently discarded. - Else, if the Route Request was received through a network interface that requires physically bidirectional links for - unicast transmission, the node MUST check if the Request was last - forwarded by a node on its blacklist. If such an entry is found, - and the state of the unidirectional link is "questionable", - then the node MUST create and unicast a Route Request packet to - that previous node, setting the IP Time-To-Live (TTL) to 1 to - prevent the Request from being propagated. If the node receives - a Route Reply in response to the new Request, it MUST remove the - blacklist entry for that node, and SHOULD continue processing. - If the node does not receive a Route Reply within some reasonable - amount of time, MUST silently discard the Route Request packet. + unicast transmission, the node MUST check if the Route Request + was last forwarded by a node on its Blacklist. If such an entry + is found in the Blacklist, and the state of the unidirectional + link is "questionable", then the node MUST create and unicast + a Route Request packet to that previous node, setting the + IP Time-To-Live (TTL) to 1 to prevent the Request from being + propagated. If the node receives a Route Reply in response to + the new Request, it MUST remove the Blacklist entry for that + node, and SHOULD continue processing. If the node does not + receive a Route Reply within some reasonable amount of time, the + node MUST silently discard the Route Request packet. - Else, the node MUST search its Route Request Table for an entry for the initiator of this Route Request (the IP Source Address field). If such an entry is found in the table, the node MUST search the cache of Identification values of recently received Route Requests in that table entry, to determine if an entry is present in the cache matching the Identification value and target node address in this Route Request. If such an (Identification, target address) entry is found in this cache in this entry in the Route Request Table, then the node MUST discard @@ -3154,36 +3122,38 @@ o Add an entry for this Route Request in its cache of (Identification, target address) values of recently received Route Requests. o Conceptually create a copy of this entire packet and perform the following steps on the copy of the packet. o Append this node's own IP address to the list of Address[i] values in the Route Request, and increase the value of the - Opt Data Len field in the Route Request by 4 (the size of an - IP address). + Opt Data Len field in the Route Request by 4 (the size of + an IP address). However, if the node has multiple network + interfaces, this step MUST be modified by the special + processing specified in Section sec:multiple. o This node SHOULD search its own Route Cache for a route (from itself, as if it were the source of a packet) to the target of this Route Request. If such a route is found in its Route Cache, then this node SHOULD follow the procedure outlined in Section 8.2.3 to return a "cached Route Reply" to the initiator of this Route Request, if permitted by the restrictions specified there. o If the node does not return a cached Route Reply, then this - node SHOULD link-layer re-broadcast this copy of the packet, - with a short jitter delay before the broadcast is sent. The - jitter period SHOULD be chosen as a random period, uniformly - distributed between 0 and BroadcastJitter. + node SHOULD transmit this copy of the packet as a link-layer + broadcast, with a short jitter delay before the broadcast is + sent. The jitter period SHOULD be chosen as a random period, + uniformly distributed between 0 and BroadcastJitter. 8.2.3. Generating a Route Reply using the Route Cache As described in Section 3.3.2, it is possible for a node processing a received Route Request to avoid propagating the Route Request further toward the target of the Request, if this node has in its Route Cache a route from itself to this target. Such a Route Reply generated by a node from its own cached route to the target of a Route Request is called a "cached Route Reply", and this mechanism can greatly reduce the overall overhead of Route Discovery on the network by reducing @@ -3229,20 +3199,24 @@ to this target node, obtained from the node's Route Cache. In appending this cached route to the source route for the reply, the address of this node itself MUST be excluded, since it is already listed as Address[n]. - Send a Route Reply to the initiator of the Route Request, using the procedure defined in Section 8.2.4. The initiator of the Route Request is indicated in the Source Address field in the packet's IP header. + Before sending the cached Route Reply, however, the node MAY delay + the Reply in order to help prevent a possible Route Reply "storm", as + described in Section 8.2.5. + If the node returns a cached Route Reply as described above, then the node MUST NOT propagate the Route Request further (i.e., the node MUST NOT rebroadcast the Route Request). In this case, instead, if the packet contains no other DSR options and contains no payload after the DSR Options header (e.g., the Route Request is not piggybacked on a TCP or UDP packet), then the node SHOULD simply discard the packet. Otherwise (if the packet contains other DSR options or contains any payload after the DSR Options header), the node SHOULD forward the packet along the cached route to the target of the Route Request. Specifically, if the node does so, it MUST use @@ -3364,44 +3338,114 @@ piggybacking prevents a loop wherein the target of the new Route Request (which was itself the initiator of the original Route Request) must do another Route Request in order to return its Route Reply. If sending the Route Reply to the initiator of the Route Request does not require performing a Route Discovery, a node SHOULD send a unicast Route Reply in response to every Route Request it receives for which it is the target node. -8.2.5. Processing a Received Route Reply Option +8.2.5. Preventing Route Reply Storms + + The ability for nodes to reply to a Route Request based on + information in their Route Caches, as described in Sections 3.3.2 + and 8.2.3, could result in a possible Route Reply "storm" in some + cases. In particular, if a node broadcasts a Route Request for a + target node for which the node's neighbors have a route in their + Route Caches, each neighbor may attempt to send a Route Reply, + thereby wasting bandwidth and possibly increasing the number of + network collisions in the area. + + For example, the figure below shows a situation in which nodes B, C, + D, E, and F all receive A's Route Request for target G, and each has + the indicated route cached for this target: + + +-----+ +-----+ + | D |< >| C | + +-----+ \ / +-----+ + Cache: C - B - G \ / Cache: B - G + \ +-----+ / + -| A |- + +-----+\ +-----+ +-----+ + | | \--->| B | | G | + / \ +-----+ +-----+ + / \ Cache: G + v v + +-----+ +-----+ + | E | | F | + +-----+ +-----+ + Cache: F - B - G Cache: B - G + + Normally, each of these nodes would attempt to reply from its own + Route Cache, and they would thus all send their Route Replies at + about the same time, since they all received the broadcast Route + Request at about the same time. Such simultaneous Route Replies + from different nodes all receiving the Route Request may cause local + congestion in the wireless network and may create packet collisions + among some or all of these Replies if the MAC protocol in use does + not provide sufficient collision avoidance for these packets. In + addition, it will often be the case that the different replies will + indicate routes of different lengths, as shown in this example. + + In order to reduce these effects, if a node can put its network + interface into promiscuous receive mode, it MAY delay sending its + own Route Reply for a short period, while listening to see if the + initiating node begins using a shorter route first. Specifically, + this node MAY delay sending its own Route Reply for a random period + + d = H * (h - 1 + r) + + where h is the length in number of network hops for the route to be + returned in this node's Route Reply, r is a random floating point + number between 0 and 1, and H is a small constant delay (at least + twice the maximum wireless link propagation delay) to be introduced + per hop. This delay effectively randomizes the time at which each + node sends its Route Reply, with all nodes sending Route Replies + giving routes of length less than h sending their Replies before this + node, and all nodes sending Route Replies giving routes of length + greater than h sending their Replies after this node. + + Within the delay period, this node promiscuously receives all + packets, looking for data packets from the initiator of this Route + Discovery destined for the target of the Discovery. If such a data + packet received by this node during the delay period uses a source + route of length less than or equal to h, this node may infer that the + initiator of the Route Discovery has already received a Route Reply + giving an equally good or better route. In this case, this node + SHOULD cancel its delay timer and SHOULD NOT send its Route Reply for + this Route Discovery. + +8.2.6. Processing a Received Route Reply Option Section 8.1.4 describes the general processing for a received packet, including the addition of routing information from options in the packet's DSR Options header to the receiving node's Route Cache. If the received packet contains a Route Reply, no additional special processing of the Route Reply option is required beyond what is described there. As described in Section 4.1 anytime a node adds new information to its Route Cache (including the information added from this Route Reply option), the node SHOULD check each packet in its own Send Buffer (Section 4.2) to determine whether a route to that packet's IP Destination Address now exists in the node's Route Cache (including the information just added to the Cache). If so, the packet SHOULD then be sent using that route and removed from the Send Buffer. This general procedure handles all processing required for a received Route Reply option. - When a MAC protocol requires bidirectional links for unicast - transmission, a unidirectional link may be discovered by the + When using a MAC protocol that requires bidirectional links for + unicast transmission, a unidirectional link may be discovered by the propagation of the Route Request. When the Route Reply is sent over the reverse path, a forwarding node may discover that the next-hop is unreachable. In this case, it MUST add the next-hop address to its - blacklist. + Blacklist (Section 4.6). 8.3. Route Maintenance Processing Route Maintenance is the mechanism by which a source node S is able to detect, while using a source route to some destination node D, if the network topology has changed such that it can no longer use its route to D because a link along the route no longer works. When Route Maintenance indicates that a source route is broken, S can attempt to use any other route it happens to know to D, or can invoke Route Discovery again to find a new route for subsequent packets @@ -3517,21 +3561,21 @@ acknowledgements. In using passive acknowledgements for a packet that it originates or forwards, a node considers the later receipt of a new packet (e.g., with promiscuous receive mode enabled on its network interface) to be an acknowledgement of this first packet if both of the following two tests succeed: - The Source Address, Destination Address, Protocol, Identification, and Fragment Offset fields in the IP header - of the two packets MUST match [30], and + of the two packets MUST match [32], and - If either packet contains a DSR Source Route header, both packets MUST contain one, and the value in the Segments Left field in the DSR Source Route header of the new packet MUST be less than that in the first packet. When a node hears such a passive acknowledgement for any packet in its Maintenance Buffer, that node SHOULD remove that packet, as well as any other packets in its Maintenance Buffer with the same next-hop destination, from its Maintenance Buffer. @@ -3562,21 +3606,21 @@ - If the packet contains an Acknowledgement option, then this node MUST NOT process the Acknowledgement Request option. If neither of the tests above fails, then this node MUST process the Acknowledgement Request option by sending an Acknowledgement option to the previous-hop node; to do so, the node performs the following sequence of steps: - Create a packet and set the IP Protocol field to the protocol - number assigned for a DSR Options header (TBA???). + number assigned for DSR (TBA???). - Set the IP Source Address field in this packet to the IP address of this node, copied from the source route in the DSR Source Route option in that packet (or from the IP Destination Address field of the packet, if the packet does not contain a DSR Source Route option). - Set the IP Destination Address field in this packet to the IP address of the previous-hop node, copied from the source route in the DSR Source Route option in that packet (or from the IP @@ -3610,21 +3654,21 @@ When a node receives a packet with both an Acknowledgement option and an Acknowledgement Request option, if that node is not the destination of the Acknowledgement option (the IP Destination Address of the packet), then the Acknowledgement Request option MUST be ignored. Otherwise (that node is the destination of the Acknowledgement option), that node MUST process the Acknowledgement Request option by returning an Acknowledgement option according to the following sequence of steps: - Create a packet and set the IP Protocol field to the protocol - number assigned for a DSR Options header (TBA???). + number assigned for DSR (TBA???). - Set the IP Source Address field in this packet to the IP address of this node, copied from the source route in the DSR Source Route option in that packet (or from the IP Destination Address field of the packet, if the packet does not contain a DSR Source Route option). - Set the IP Destination Address field in this packet to the IP address of the node originating the Acknowledgement option. @@ -3825,85 +3869,81 @@ - Transmit the packet to the next-hop node on the new source route in the packet, using the forwarding procedure described in Section 8.1.5. As described in Section 8.3.4, the node in this case also SHOULD return a Route Error to the original sender of the packet. If the node chooses to salvage the packet, it SHOULD do so after originating the Route Error. -8.4. Multiple Interface Support +8.4. Multiple Network Interface Support - A node in DSR MAY have multiple network interfaces that support + A node using DSR MAY have multiple network interfaces that support ad hoc network routing. This section describes special packet processing at such nodes. A node with multiple network interfaces MUST have some policy for - determining which Request packets are forwarded out which network - interfaces. For example, a node MAY choose to forward all Requests - out all network interfaces. + determining which Route Request packets are forwarded out which + network interfaces. For example, a node MAY choose to forward all + Route Requests out all network interfaces. When a node with multiple network interfaces propagates a Route - Request on an network interface other than the one it received the - Request on, it MUST modify the address list between receipt and - re-propagation as follows: - - - Append the address of the incoming interface - - - If the incoming interface and outgoing interface differ in - whether or not they require bidirectionality for unicast - transmission, append the address 127.0.0.1 + Request on an network interface other than the one one which it + received the Route Request, it MUST modify the address list between + receipt and propagation as follows: - - If the incoming interface and outgoing interface differ in - whether or not unidirectional links are common, append the - address 127.0.0.2 + - Append the address of the incoming network interface. - - Append the address of the outgoing interface + - Append the address of the outgoing network interface. When a node forwards a packet containing a source route, it MUST - assume that the next hop is reachable on the incoming interface, - unless the next hop is the address of one of this node's interfaces, - in which case this node MUST process the packet in the same way as if - the node had just received it from that interface. + assume that the next-hop node is reachable on the incoming network + interface, unless the next hop is the address of one of this node's + network interfaces, in which case this node MUST skip over this + address in the source route and process the packet in the same way as + if it had just received it from that network interface, as described + in section 8.1.5. - If a node which previously had multiple network interfaces receives a - packet sent with a source route specifying an interface change to an + If a node that previously had multiple network interfaces receives + a packet sent with a source route specifying a change to a network interface that is no longer available, it MAY send a Route Error to - the source of the packet without attempting to forward the packet on - the incoming interface, unless the network uses an autoconfiguration - mechanism that may have allowed another node to acquire the now - unused address of the unavailable interface. - - Source routes MUST never contain the special addresses 127.0.0.1 and - 127.0.0.2. + the source of the packet without attempting to forward the packet + on the incoming network interface, unless the network uses an + autoconfiguration mechanism that may have allowed another node to + acquire the now unused address of the unavailable network interface. -8.5. Fragmentation and Reassembly +8.5. IP Fragmentation and Reassembly When a node using DSR wishes to fragment a packet that contains a DSR header not containing a Route Request option, it MUST perform the following sequence of steps: - Remove the DSR Options header from the packet. - - Fragment the packet. + - Fragment the packet. When determining the size of each fragment + to create from the original packet, the fragment size MUST be + reduced by the size of the DSR Options header from the original + packet. - - IP-in-IP encapsulate each fragment. + - IP-in-IP encapsulate each fragment [28]. The IP Destination + address of the outer (encapsulating) packet MUST be set equal to + the IP Destination address of the original packet. - - Add the DSR Options header to each fragment. If a Source Route - header is present in the DSR Options header, increment the - Salvage field. + - Add the DSR Options header from the original packet to each + resulting encapsulating packet. If a Source Route header is + present in the DSR Options header, increment the Salvage field. When a node using the DSR protocol receives an IP-in-IP encapsulated - packet destined to itself, it SHOULD decapsulate the packet and - reassemble any fragments contained inside, in accordance with - RFC 791 [30]. + packet destined to itself, it SHOULD decapsulate the packet [28] and + then process the inner packet according to standard IP reassembly + processing [32]. 8.6. Flow State Processing A node implementing the optional DSR flow state extension MUST follow these additional processing steps. 8.6.1. Originating a Packet When originating any packet to be routed using flow state, a node using DSR flow state MUST: @@ -4033,21 +4073,21 @@ - Insert a DSR Flow State header after the IP header and any Hop-by-Hop Options header that may already be in the packet, but before any other header that may be present. - Set the Next Header field of the DSR Flow State header to the Next Header field of the previous header (either an IP header or a Hop-by-Hop Options header). - Set the Next Header field of the previous header to the Protocol - number assigned to DSR Options headers. + number assigned for DSR (TBA???). 8.6.3. Receiving a Packet This section describes processing only for packets that are sent to the processing node as the next-hop node; that is, when the MAC-layer destination address is the MAC address of this node. Otherwise, the process described in Sections 8.6.5 should be followed. The flow along which a packet is being sent is considered to be in the Flow Table if the triple (IP Source Address, IP Destination @@ -4101,24 +4141,24 @@ o On receiving a Route Request that this node has not previously seen for which this node is not the destination, discard the packet and stop processing. o On receiving any Route Request, add appropriate links to the cache, as specified in Section 8.2.2. o On receiving a Route Reply that this node is the Requester for, remove the Route Reply from the packet and process it as - specified in Section 8.2.5. + specified in Section 8.2.6. o On receiving any Route Reply, add appropriate links to the - cache, as specified in Section 8.2.5. + cache, as specified in Section 8.2.6. o On receiving any Route Error of type NODE_UNREACHABLE, remove appropriate links to the cache, as specified in Section 8.3.5. o On receiving a Route Error of type NODE_UNREACHABLE that this node is the Error Destination Address of, remove the Route Error from the packet and process it as specified in Section 8.3.5. It also MUST stop originating packets along any flows using the link from Error Source Address to @@ -4333,20 +4373,22 @@ is not required to use these names for the configuration variables, so long as the external behavior of the implementation is consistent with that described in this document. For each configuration variable below, the default value is specified to simplify configuration. In particular, the default values given below are chosen for a DSR network running over 2 Mbps IEEE 802.11 network interfaces using the Distributed Coordination Function (DCF) MAC with RTS and CTS [13, 5]. + DiscoveryHopLimit 255 hops + BroadcastJitter 10 milliseconds RouteCacheTimeout 300 seconds SendBufferTimeout 30 seconds RequestTableSize 64 nodes RequestTableIds 16 identifiers MaxRequestRexmt 16 retransmissions MaxRequestPeriod 10 seconds @@ -4364,53 +4406,54 @@ GratReplyHoldoff 1 second In addition, the following protocol constant MUST be supported by any implementation of the DSR protocol: MAX_SALVAGE_COUNT 15 salvages 10. IANA Considerations - This document specifies the DSR Options header, which requires an IP - Protocol number. - - This document also specifies the DSR Flow State header, which - requires an IP Protocol number. + This document specifies the DSR Options header and DSR Flow State + header, which require an IP Protocol number. A single IP protocol + number can be used for both header types, since they can be + distinguished by the Flow State Header (F) bit in each header. In addition, this document proposes use of the value "No Next Header" (originally defined for use in IPv6) within an IPv4 packet, to indicate that no further header follows a DSR Options header. Finally, this document introduces a number of DSR options for use in the DSR Options header, and additional new DSR options may be defined in the future. Each of these options requires a unique Option Type value, with the most significant 3 bits (that is, Option Type & 0xE0) encoded as defined in Section 6.1. It is necessary only that each Option Type value be unique, not that they be unique in the remaining - 5 bits of the value after these 3 most significant bits. + 5 bits of the value after these 3 most significant bits. Assignment + of new values for DSR options will be by Expert Review [25], with the + authors of this document serving as the Designated Experts. 11. Security Considerations This document does not specifically address security concerns. This document does assume that all nodes participating in the DSR protocol do so in good faith and without malicious intent to corrupt the routing ability of the network. Depending on the threat model, a number of different mechanisms can be used to secure DSR. For example, in an environment where node compromise is unrealistic and where where all the nodes participating in the DSR protocol share a common goal that motivates their participation in the protocol, the communications between the nodes can be encrypted at the physical channel or link layer to prevent attack by outsiders. Cryptographic approaches, such as that provided - by Ariadne [12] or SRP [26], can resist stronger attacks. + by Ariadne [12] or SRP [27], can resist stronger attacks. Appendix A. Link-MaxLife Cache Description As guidance to implementors of DSR, the description below outlines the operation of a possible implementation of a Route Cache for DSR that has been shown to outperform other other caches studied in detailed simulations. Use of this design for the Route Cache is recommended in implementations of DSR. This cache, called "Link-MaxLife" [10], is a link cache, in that each @@ -4483,26 +4526,26 @@ When designing DSR, we had to determine at what layer within the protocol hierarchy to implement ad hoc network routing. We considered two different options: routing at the link layer (ISO layer 2) and routing at the network layer (ISO layer 3). Originally, we opted to route at the link layer for several reasons: - Pragmatically, running the DSR protocol at the link layer maximizes the number of mobile nodes that can participate in ad hoc networks. For example, the protocol can route equally - well between IPv4 [30], IPv6 [7], and IPX [35] nodes. + well between IPv4 [32], IPv6 [7], and IPX [37] nodes. - Historically [15, 16], DSR grew from our contemplation of a multi-hop propagating version of the Internet's Address - Resolution Protocol (ARP) [28], as well as from the routing - mechanism used in IEEE 802 source routing bridges [27]. These + Resolution Protocol (ARP) [30], as well as from the routing + mechanism used in IEEE 802 source routing bridges [29]. These are layer 2 protocols. - Technically, we designed DSR to be simple enough that it could be implemented directly in the firmware inside wireless network interface cards [15, 16], well below the layer 3 software within a mobile node. We see great potential in this for DSR running inside a cloud of mobile nodes around a fixed base station, where DSR would act to transparently extend the coverage range to these nodes. Mobile nodes that would otherwise be unable to communicate with the base station due to factors such as @@ -4516,21 +4559,21 @@ Appendix C. Implementation and Evaluation Status The initial design of the DSR protocol, including DSR's basic Route Discovery and Route Maintenance mechanisms, was first published in December 1994 [15], with significant additional design details and initial simulation results published in early 1996 [16]. The DSR protocol has been extensively studied since then through additional detailed simulations. In particular, we have implemented - DSR in the ns-2 network simulator [25, 5] and performed extensive + DSR in the ns-2 network simulator [26, 5] and performed extensive simulations of DSR using ns-2 (e.g., [5, 21]). We have also conducted evaluations of the different caching strategies in this document [10]. We have also implemented the DSR protocol under the FreeBSD 2.2.7 operating system running on Intel x86 platforms. FreeBSD [9] is based on a variety of free software, including 4.4 BSD Lite from the University of California, Berkeley. For the environments in which we used it, this implementation is functionally equivalent to the version of the DSR protocol specified in this document. @@ -4546,21 +4589,21 @@ Report [22]. We have since ported this implementation of DSR to FreeBSD 3.3, and we have also added a preliminary version of Quality of Service (QoS) support for DSR. A demonstration of this modified version of DSR was presented in July 2000. These QoS features are not included in this document, and will be added later in a separate document on top of the base protocol specified here. DSR has also been implemented under Linux by Alex Song at the - University of Queensland, Australia [34]. This implementation + University of Queensland, Australia [36]. This implementation supports the Intel x86 PC platform and the Compaq iPAQ. The Network and Telecommunications Research Group at Trinity College Dublin have implemented a version of DSR on Windows CE. Microsoft Research has implemented a version of DSR on Windows XP, and has used it in testbeds of over 15 nodes. Several machines use this implementation as their primary means of accessing the Internet. Several other independent groups have also used DSR as a platform for @@ -4569,45 +4612,55 @@ A preliminary version of the optional DSR flow state extension was implemented in FreeBSD 3.3. A demonstration of this modified version of DSR was presented in July 2000. The DSR flow state extension has also been extensively evaluated using simulation [11]. Changes from Previous Version of the Draft This appendix briefly lists some of the major changes in this draft relative to the previous version of this same draft, - draft-ietf-manet-dsr-07.txt: + draft-ietf-manet-dsr-09.txt: - - Integrated the specification of the DSR flow state extension into - the main DSR draft. Previously, these had been specified in a - separate draft. + - Changed the values used for the Route Request and Route Reply + options so that they are assigned in a more logical order (Route + Request is now 1 and Route Reply is 2, rather than the other way + around). - - Included processing directions for unknown Option Types. + - Specification of interaction of DSR with ARP. - - Changed the name of the DSR header to DSR Options header, to - clarify it as a separate header type from the DSR Flow State - header. + - Better integration of multiple network interfaces into the main + packet processing specification in Section 8. - - Slightly changed the format of the DSR Options header and the DSR - Flow State header to allow the same IP protocol number to be used - for both. The new Flow State Header (F) bit in the two headers - indicates which type of header is being used (the bit is clear in - a DSR Options header and set in a DSR Flow State header). + - Removal of optimizations for unidirectional links, based on + special 127.0.0.1 and 127.0.0.2 flags in a Route Request and + Route Reply. These optimizations were not fully specified in + the draft and will be included in future versions of the DSR + specification. + + - Clarification of rules for IP fragmentation in Section 8.5. + + - Revisions to the IANA Considerations section to state that the + DSR Options header and DSR Flow State header can share a single + IP protocol number assignment, and to add of a policy for DSR + options assignments. + + - Other general clarification of the specification, based on + feedback received in Area Director review comments. Acknowledgements The protocol described in this document has been designed and developed within the Monarch Project, a research project at Rice University (previously at Carnegie Mellon University) that is developing adaptive networking protocols and protocol interfaces to - allow truly seamless wireless and mobile node networking [17, 33]. + allow truly seamless wireless and mobile node networking [17, 35]. The authors would like to acknowledge the substantial contributions of Josh Broch in helping to design, simulate, and implement the DSR protocol. We thank him for his contributions to earlier versions of this document. We would also like to acknowledge the assistance of Robert V. Barron at Carnegie Mellon University. Bob ported our DSR implementation from FreeBSD 2.2.7 into FreeBSD 3.3. @@ -4717,63 +4770,70 @@ [23] David A. Maltz, Josh Broch, and David B. Johnson. Quantitative Lessons From a Full-Scale Multi-Hop Wireless Ad Hoc Network Testbed. In Proceedings of the IEEE Wireless Communications and Networking Conference, September 2000. [24] David A. Maltz, Josh Broch, and David B. Johnson. Lessons From a Full-Scale MultiHop Wireless Ad Hoc Network Testbed. IEEE Personal Communications, 8(1):8--15, February 2001. - [25] The Network Simulator -- ns-2. Project web page available at + [25] Thomas Narten and Harald Tveit Alvestrand. Guidelines for + Writing an IANA Considerations Section in RFCs. RFC 2434, + October 1998. + + [26] The Network Simulator -- ns-2. Project web page available at http://www.isi.edu/nsnam/ns/. - [26] Panagiotis Papadimitratos and Zygmunt J. Haas. Secure Routing + [27] Panagiotis Papadimitratos and Zygmunt J. Haas. Secure Routing for Mobile Ad Hoc Networks. In SCS Communication Networks and Distributed Systems Modeling and Simulation Conference (CNDS 2002), January 2002. - [27] Radia Perlman. Interconnections: Bridges and Routers. + [28] Charles Perkins. IP Encapsulation within IP. RFC 2003, October + 1996. + + [29] Radia Perlman. Interconnections: Bridges and Routers. Addison-Wesley, Reading, Massachusetts, 1992. - [28] David C. Plummer. An Ethernet Address Resolution Protocol: + [30] David C. Plummer. An Ethernet Address Resolution Protocol: Or Converting Network Protocol Addresses to 48.bit Ethernet Addresses for Transmission on Ethernet Hardware. RFC 826, November 1982. - [29] J. B. Postel, editor. Internet Control Message Protocol. + [31] J. B. Postel, editor. Internet Control Message Protocol. RFC 792, September 1981. - [30] J. B. Postel, editor. Internet Protocol. RFC 791, September + [32] J. B. Postel, editor. Internet Protocol. RFC 791, September 1981. - [31] J. B. Postel, editor. Transmission Control Protocol. RFC 793, + [33] J. B. Postel, editor. Transmission Control Protocol. RFC 793, September 1981. - [32] Joyce K. Reynolds and Jon Postel. Assigned Numbers. RFC 1700, + [34] Joyce K. Reynolds and Jon Postel. Assigned Numbers. RFC 1700, October 1994. See also http://www.iana.org/numbers.html. - [33] Rice University Monarch Project. Monarch Project Home Page. + [35] Rice University Monarch Project. Monarch Project Home Page. Available at http://www.monarch.cs.rice.edu/. - [34] Alex Song. picoNet II: A Wireless Ad Hoc Network for Mobile + [36] Alex Song. picoNet II: A Wireless Ad Hoc Network for Mobile Handheld Devices. Submitted for the degree of Bachelor of Engineering (Honours) in the division of Electrical Engineering, Department of Information Technology and Electrical Engineering, University of Queensland, Australia, October 2001. Available at http://student.uq.edu.au/~s369677/main.html. - [35] Paul Turner. NetWare Communications Processes. NetWare + [37] Paul Turner. NetWare Communications Processes. NetWare Application Notes, Novell Research, pages 25--91, September 1990. - [36] Gary R. Wright and W. Richard Stevens. TCP/IP Illustrated, + [38] Gary R. Wright and W. Richard Stevens. TCP/IP Illustrated, Volume 2: The Implementation. Addison-Wesley, Reading, Massachusetts, 1995. Chair's Address The MANET Working Group can be contacted via its current chairs: M. Scott Corson Phone: +1 908 947-7033 Flarion Technologies, Inc. Email: corson@flarion.com Bedminster One