IETF MANET Working Group               David B. Johnson, Rice UniversityINTERNET-DRAFT                David A. Maltz, Carnegie Mellon University19 July 2004                                Yih-Chun Hu, Rice University                  The Dynamic Source Routing Protocol                    for Mobile Ad Hoc Networks (DSR)                     <draft-ietf-manet-dsr-10.txt>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.   Internet-Drafts are draft documents valid for a maximum of six months   and may be updated, replaced, or obsoleted by other documents at   any time.  It is inappropriate to use Internet-Drafts as reference   material or to cite them other than as "work in progress".   The list of current Internet-Drafts can be accessed at   http://www.ietf.org/ietf/1id-abstracts.txt   The list of Internet-Draft Shadow Directories can be accessed at   http://www.ietf.org/shadow.html.   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.Johnson, et al             Expires 19 January 2005              [Page i]INTERNET-DRAFT     The Dynamic Source Routing Protocol      19 July 2004Abstract   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, 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.Johnson, et al             Expires 19 January 2005             [Page ii]INTERNET-DRAFT     The Dynamic Source Routing Protocol      19 July 2004                                ContentsStatus of This Memo                                                    iAbstract                                                              ii 1. Introduction                                                       1 2. Assumptions                                                        4 3. DSR Protocol Overview                                              6     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 . . .   16     3.5. Optional DSR Flow State Extension . . . . . . . . . . . .   17           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  . . . . . . . . . . . . . . . . .   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 . . . . . . . .   22 4. Conceptual Data Structures                                        23     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 . . . . . . . . . . . . . . . . . . . . . . . .   30Johnson, et al            Expires 19 January 2005             [Page iii]INTERNET-DRAFT     The Dynamic Source Routing Protocol      19 July 2004 5. Additional Conceptual Data Structures for Flow State Extension    31     5.1. Flow Table  . . . . . . . . . . . . . . . . . . . . . . .   31     5.2. Automatic Route Shortening Table  . . . . . . . . . . . .   32     5.3. Default Flow ID Table . . . . . . . . . . . . . . . . . .   32 6. DSR Options Header Format                                         34     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    51     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                                                58     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  . . . . . . . . . . . . . .   77Johnson, et al             Expires 19 January 2005             [Page iv]INTERNET-DRAFT     The Dynamic Source Routing Protocol      19 July 2004           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 . . . . . . . . .  96           8.6.7. Salvage Interactions with DSR . . . . . . . . . .   96 9. Protocol Constants and Configuration Variables                    9710. IANA Considerations                                               9811. Security Considerations                                           99Appendix A. Link-MaxLife Cache Description                           100Appendix B. Location of DSR in the ISO Network Reference Model       102Appendix C. Implementation and Evaluation Status                     103Changes from Previous Version of the Draft                           105Acknowledgements                                                     106References                                                           107Chair's Address                                                      111Authors' Addresses                                                   112Johnson, et al             Expires 19 January 2005              [Page v]INTERNET-DRAFT     The Dynamic Source Routing Protocol      19 July 2004