tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Glossaries     Architecture     IMS     UICC    |    search

RFC 4728

 Errata 
Experimental
Pages: 107
Top     in Index     Prev     Next
in Group Index     Prev in Group     Next in Group     Group: MANET

The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks for IPv4

Part 1 of 4, p. 1 to 20
None       Next RFC Part

 


Top       ToC       Page 1 
Network Working Group                                         D. Johnson
Request for Comments: 4728                               Rice University
Category: Experimental                                             Y. Hu
                                                                    UIUC
                                                                D. Maltz
                                                      Microsoft Research
                                                           February 2007


               The Dynamic Source Routing Protocol (DSR)
                  for Mobile Ad Hoc Networks for IPv4

Status of This Memo

   This memo defines an Experimental Protocol for the Internet
   community.  It does not specify an Internet standard of any kind.
   Discussion and suggestions for improvement are requested.
   Distribution of this memo is unlimited.

Copyright Notice

   Copyright (C) The IETF Trust (2007).

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 what is
   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 even with very high rates of mobility.  This
   document specifies the operation of the DSR protocol for routing
   unicast IPv4 packets.

Top       Page 2 
Table of Contents

   1. Introduction ....................................................5
   2. Assumptions .....................................................7
   3. DSR Protocol Overview ...........................................9
      3.1. Basic DSR Route Discovery .................................10
      3.2. Basic DSR Route Maintenance ...............................12
      3.3. Additional Route Discovery Features .......................14
           3.3.1. Caching Overheard Routing Information ..............14
           3.3.2. Replying to Route Requests Using Cached Routes .....15
           3.3.3. Route Request Hop Limits ...........................16
      3.4. Additional Route Maintenance Features .....................17
           3.4.1. Packet Salvaging ...................................17
           3.4.2. Queued Packets Destined over a Broken Link .........18
           3.4.3. Automatic Route Shortening .........................19
           3.4.4. Increased Spreading of Route Error Messages ........20
      3.5. Optional DSR Flow State Extension .........................20
           3.5.1. Flow Establishment .................................21
           3.5.2. Receiving and Forwarding Establishment Packets .....22
           3.5.3. Sending Packets along Established Flows ............22
           3.5.4. Receiving and Forwarding Packets Sent along
                  Established Flows ..................................23
           3.5.5. Processing Route Errors ............................24
           3.5.6. Interaction with Automatic Route Shortening ........24
           3.5.7. Loop Detection .....................................25
           3.5.8. Acknowledgement Destination ........................25
           3.5.9. Crash Recovery .....................................25
           3.5.10. Rate Limiting .....................................25
           3.5.11. Interaction with Packet Salvaging .................26
   4. Conceptual Data Structures .....................................26
      4.1. Route Cache ...............................................26
      4.2. Send Buffer ...............................................30
      4.3. Route Request Table .......................................30
      4.4. Gratuitous Route Reply Table ..............................31
      4.5. Network Interface Queue and Maintenance Buffer ............32
      4.6. Blacklist .................................................33
   5. Additional Conceptual Data Structures for Flow State
      Extension ......................................................34
      5.1. Flow Table ................................................34
      5.2. Automatic Route Shortening Table ..........................35
      5.3. Default Flow ID Table .....................................36
   6. DSR Options Header Format ......................................36
      6.1. Fixed Portion of DSR Options Header .......................37
      6.2. Route Request Option ......................................40
      6.3. Route Reply Option ........................................42

Top      ToC       Page 3 
      6.4. Route Error Option ........................................44
           6.4.1. Node Unreachable Type-Specific Information .........46
           6.4.2. Flow State Not Supported Type-Specific
                  Information ........................................46
           6.4.3. Option Not Supported Type-Specific Information .....46
      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 ...............................................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 ..........52
           7.2.1. Timeout Option .....................................52
           7.2.2. Destination and Flow ID Option .....................53
      7.3. New Error Types for Route Error Option ....................54
           7.3.1. Unknown Flow Type-Specific Information .............54
           7.3.2. Default Flow Unknown Type-Specific Information .....55
      7.4. New Acknowledgement Request Option Extension ..............55
           7.4.1. Previous Hop Address Extension .....................55
   8. Detailed Operation .............................................56
      8.1. General Packet Processing .................................56
           8.1.1. Originating a Packet ...............................56
           8.1.2. Adding a DSR Options Header to a Packet ............57
           8.1.3. Adding a DSR Source Route Option to a Packet .......57
           8.1.4. Processing a Received Packet .......................58
           8.1.5. Processing a Received DSR Source Route Option ......60
           8.1.6. Handling an Unknown DSR Option .....................63
      8.2. Route Discovery Processing ................................64
           8.2.1. Originating a Route Request ........................65
           8.2.2. Processing a Received Route Request Option .........66
           8.2.3. Generating a Route Reply Using the Route Cache .....68
           8.2.4. Originating a Route Reply ..........................71
           8.2.5. Preventing Route Reply Storms ......................72
           8.2.6. Processing a Received Route Reply Option ...........74
      8.3. Route Maintenance Processing ..............................74
           8.3.1. Using Link-Layer Acknowledgements ..................75
           8.3.2. Using Passive Acknowledgements .....................76
           8.3.3. Using Network-Layer Acknowledgements ...............77
           8.3.4. Originating a Route Error ..........................80
           8.3.5. Processing a Received Route Error Option ...........81
           8.3.6. Salvaging a Packet .................................82
      8.4. Multiple Network Interface Support ........................84
      8.5. IP Fragmentation and Reassembly ...........................84
      8.6. Flow State Processing .....................................85
           8.6.1. Originating a Packet ...............................85
           8.6.2. Inserting a DSR Flow State Header ..................88

Top      ToC       Page 4 
           8.6.3. Receiving a Packet .................................88
           8.6.4. Forwarding a Packet Using Flow IDs .................93
           8.6.5. Promiscuously Receiving a Packet ...................93
           8.6.6. Operation Where the Layer below DSR
                  Decreases the IP TTL ...............................94
           8.6.7. Salvage Interactions with DSR ......................94
   9. Protocol Constants and Configuration Variables .................95
   10. IANA Considerations ...........................................96
   11. Security Considerations .......................................96
   Appendix A. Link-MaxLife Cache Description ........................97
   Appendix B. Location of DSR in the ISO Network Reference Model ....99
   Appendix C. Implementation and Evaluation Status .................100
   Acknowledgements .................................................101
   Normative References .............................................102
   Informative References ...........................................102

Top      ToC       Page 5 
1.  Introduction

   The Dynamic Source Routing protocol (DSR) [JOHNSON94, JOHNSON96a] 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 transmission range of one another.  As nodes in the network
   move about or join or leave the network, and as wireless transmission
   conditions such as sources of interference change, all routing is
   automatically determined and maintained by the DSR routing protocol.
   Since the number or sequence of intermediate hops needed to reach any
   destination may change at any time, the resulting network topology
   may be quite rich and rapidly changing.

   In designing DSR, we sought to create a routing protocol that had
   very low overhead yet was able to react very quickly to changes in
   the network.  The DSR protocol provides highly reactive service in
   order to help ensure successful delivery of data packets in spite of
   node movement or other changes in network conditions.

   The DSR protocol is composed of two main mechanisms that work
   together to allow the discovery and maintenance of source routes in
   the ad hoc network:

   -  Route Discovery is the mechanism by which a node S wishing to send
      a packet to a destination node D obtains a source route to D.
      Route Discovery is used only when S attempts to send a packet to D
      and does not already know a route to D.

   -  Route Maintenance is the mechanism by which node S is able to
      detect, while using a source route to 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 a source route is broken, S can attempt to use any other
      route it happens to know to D, or it can invoke Route Discovery
      again to find a new route for subsequent packets to D.  Route
      Maintenance for this route is used only when S is actually sending
      packets to D.

   In DSR, Route Discovery and Route Maintenance each operate entirely
   "on demand".  In particular, unlike other protocols, DSR requires no
   periodic packets of any kind at any layer within the network.  For
   example, DSR does not use any periodic routing advertisement, link
   status sensing, or neighbor detection packets and does not rely on
   these functions from any underlying protocols in the network.  This

Top      ToC       Page 6 
   entirely on-demand behavior and lack of periodic activity allows the
   number of overhead packets caused by DSR to scale all the way down to
   zero, when all nodes are approximately stationary with respect to
   each other and all routes needed for current communication have
   already been discovered.  As nodes begin to move more or as
   communication patterns change, the routing packet overhead of DSR
   automatically scales to only what is needed to track the routes
   currently in use.  Network topology changes not affecting routes
   currently in use are ignored and do not cause reaction from the
   protocol.

   All state maintained by DSR is "soft state" [CLARK88], in that the
   loss of any state will not interfere with the correct operation of
   the protocol; all state is discovered as needed and can easily and
   quickly be rediscovered if needed after a failure without significant
   impact on the protocol.  This use of only soft state allows the
   routing protocol to be very robust to problems such as dropped or
   delayed routing packets or node failures.  In particular, a node in
   DSR that fails and reboots can easily rejoin the network immediately
   after rebooting; if the failed node was involved in forwarding
   packets for other nodes as an intermediate hop along one or more
   routes, it can also resume this forwarding quickly after rebooting,
   with no or minimal interruption to the routing protocol.

   In response to a single Route Discovery (as well as through routing
   information from other packets overheard), a node may learn and cache
   multiple routes to any destination.  This support for multiple routes
   allows the reaction to routing changes to be much more rapid, since a
   node with multiple routes to a destination can try another 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 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 transmit power
   levels or sources of interference.

   It is possible to interface a DSR network with other networks,
   external to this DSR network.  Such external networks may, for
   example, be the Internet or may be other ad hoc networks routed with

Top      ToC       Page 7 
   a routing protocol other than DSR.  Such external networks may also
   be other DSR networks that are treated as external networks in order
   to improve scalability.  The complete handling of such external
   networks is beyond the scope of this document.  However, this
   document specifies a minimal set of requirements and features
   necessary to allow nodes only implementing this specification to
   interoperate correctly with nodes implementing interfaces to such
   external networks.

   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
   [RFC2460], will be 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.  As described in Appendix C, the
   design of DSR has been extensively studied through detailed
   simulations and testbed implementation and demonstration; this
   document encourages additional implementation and experimentation
   with the protocol.

   The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC 2119 [RFC2119].

2.  Assumptions

   As described here, the DSR protocol is designed mainly for mobile ad
   hoc networks of up to about two hundred nodes and is designed to work
   well even with very high rates of mobility.  Other protocol features
   and enhancements that may allow DSR to scale to larger networks are
   outside the scope of this document.

   We assume in this document that all nodes wishing to communicate with
   other nodes within the ad hoc network are willing to participate
   fully in the protocols of the network.  In particular, each node
   participating in the ad hoc network SHOULD also be willing to forward
   packets for other nodes in the network.

   The diameter of an ad hoc network is the minimum number of hops
   necessary for a packet to reach from any node located at one extreme
   edge of the ad hoc network to another node located at the opposite
   extreme.  We assume that this diameter will often be small (e.g.,
   perhaps 5 or 10 hops), but it may often be greater than 1.

Top      ToC       Page 8 
   Packets may be lost or corrupted in transmission on the wireless
   network.  We assume that a node receiving a corrupted packet can
   detect the error, such as through a standard link-layer checksum or
   Cyclic Redundancy Check (CRC), and discard the packet.

   Nodes within the ad hoc network MAY move at any time without notice
   and MAY even move continuously, but we assume that the speed with
   which nodes move is moderate with respect to the packet transmission
   latency and wireless transmission range of the particular underlying
   network hardware in use.  In particular, DSR can support very rapid
   rates of arbitrary node mobility, but we assume that nodes do not
   continuously move so rapidly as to make the flooding of every
   individual data packet the only possible routing protocol.

   A common feature of many network interfaces, including most current
   LAN hardware for broadcast media such as wireless, is the ability to
   operate the network interface in "promiscuous" receive mode.  This
   mode causes the hardware to deliver every received packet to the
   network driver software without filtering based on link-layer
   destination address.  Although we do not require this facility, some
   of our optimizations can take advantage of its availability.  Use of
   promiscuous mode does increase the software overhead on the CPU, but
   we believe that wireless network speeds and capacity are more the
   inherent limiting factors to performance in current and future
   systems; we also believe that portions of the protocol are suitable
   for implementation directly within a programmable network interface
   unit to avoid this overhead on the CPU [JOHNSON96a].  Use of
   promiscuous mode may also increase the power consumption of the
   network interface hardware, depending on the design of the receiver
   hardware, and in such cases, DSR can easily be used without the
   optimizations that depend on promiscuous 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
   transmit power levels or sources of interference around the two nodes
   [BANTZ94, LAUER95].  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.
   Some Medium Access Control (MAC) protocols, however, such as MACA
   [KARN90], MACAW [BHARGHAVAN94], or IEEE 802.11 [IEEE80211], limit
   unicast data packet transmission to bidirectional links, due to the
   required bidirectional exchange of request to send (RTS) and clear to
   send (CTS) packets in these protocols and to the link-layer
   acknowledgement feature in IEEE 802.11.  When used on top of MAC

Top      ToC       Page 9 
   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 Dynamic Host
   Configuration Protocol (DHCP) for dynamic assignment [RFC2131]),
   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) [RFC826] 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
   including this source route in the header of each data packet, other
   nodes forwarding or overhearing any of these packets can also easily
   cache this routing information for future use.  Section 3.1 describes
   this basic operation of Route Discovery, Section 3.2 describes basic
   Route Maintenance, and Sections 3.3 and 3.4 describe additional
   features of these two parts of DSR's operation.  Section 3.5 then
   describes an optional, compatible extension to DSR, known as "flow
   state", that allows the routing of most packets without an explicit
   source route header in the packet, while the fundamental properties
   of DSR's operation are preserved.

Top      ToC       Page 10 
3.1.  Basic DSR Route Discovery

   When some source node originates a new packet addressed to some
   destination node, the source node places in the header of the packet
   a "source route" giving the sequence of hops that the packet is to
   follow on its way to the destination.  Normally, the sender will
   obtain a suitable source route by searching its "Route Cache" of
   routes previously learned; if no route is found in its cache, it will
   initiate the Route Discovery protocol to dynamically find a new route
   to this destination node.  In this case, we call the source node the
   "initiator" and the destination node the "target" of the Route
   Discovery.

   For example, suppose a node A is attempting to discover a route to
   node E.  The Route Discovery initiated by node A in this example
   would proceed as follows:

            ^    "A"    ^   "A,B"   ^  "A,B,C"  ^ "A,B,C,D"
            |   id=2    |   id=2    |   id=2    |   id=2
         +-----+     +-----+     +-----+     +-----+     +-----+
         |  A  |---->|  B  |---->|  C  |---->|  D  |---->|  E  |
         +-----+     +-----+     +-----+     +-----+     +-----+
            |           |           |           |
            v           v           v           v

   To initiate the Route Discovery, node A transmits a "Route Request"
   as a single local broadcast packet, which is received by
   (approximately) all nodes currently within wireless transmission
   range of A, including node B in this example.  Each Route Request
   identifies the initiator and target of the Route Discovery, and also
   contains a unique request identification (2, in this example),
   determined by the initiator of the Request.  Each Route Request also
   contains a record listing the address of each intermediate node
   through which this particular copy of the Route Request has been
   forwarded.  This route record is initialized to an empty list by the
   initiator of the Route Discovery.  In this example, the route record
   initially lists only node A.

   When another node receives this Route Request (such as node B in this
   example), if it is the target of the Route Discovery, it returns 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.

Top      ToC       Page 11 
   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.  (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 receipt of
   a copy of the Request 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
   one is 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 in this case 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 [RFC793], 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 for unicast packets as part of the MAC protocol
   [IEEE80211], the discovered source route MUST be reversed in this way
   to return the Route Reply, since this route reversal tests the
   discovered route to ensure that 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.

   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 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.

Top      ToC       Page 12 
   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 (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 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
   same destination node more frequently than this limit, the subsequent
   packets SHOULD be buffered in the Send Buffer until a Route Reply is
   received giving a route to this destination, but the node MUST NOT
   initiate a new Route Discovery until the minimum allowable interval
   between new Route Discoveries for this target has been reached.  This
   limitation on the maximum rate of Route Discoveries for the same
   target is similar to the mechanism required by Internet nodes to
   limit the rate at which ARP Requests are sent for any single target
   IP address [RFC1122].

3.2.  Basic DSR Route Maintenance

   When originating or forwarding a packet using a source route, each
   node transmitting the packet is responsible for confirming that data
   can flow over the link from that node to the next hop.  For example,
   in the situation shown below, node A has originated a packet for node
   E using a source route through intermediate nodes B, C, and D:

         +-----+     +-----+     +-----+     +-----+     +-----+
         |  A  |---->|  B  |---->|  C  |-->? |  D  |     |  E  |
         +-----+     +-----+     +-----+     +-----+     +-----+

   In this case, node A is responsible for the link from A to B, node B
   is responsible for the link from B to C, node C is responsible for
   the link from C to D, and node D is responsible for the link from D
   to E.

Top      ToC       Page 13 
   An acknowledgement can provide confirmation that a link is capable of
   carrying data, and in wireless networks, acknowledgements are often
   provided at no cost, either as an existing standard part of the MAC
   protocol in use (such as the link-layer acknowledgement frame defined
   by IEEE 802.11 [IEEE80211]), or by a "passive acknowledgement"
   [JUBIN87] (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 that 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 (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 not to 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
   separate packet, piggybacked on a retransmission of the original data
   packet, or piggybacked on any packet with the same next-hop
   destination that does not also contain a software acknowledgement.

   After the acknowledgement request has been retransmitted the maximum
   number of times, if no acknowledgement has been received, then the
   sender treats the link to this next-hop destination as currently
   "broken".  It SHOULD remove this link from its Route Cache and SHOULD
   return a "Route Error" to each node that has sent a packet routed
   over that link since an acknowledgement was last received.  For
   example, in the situation shown above, if C does not receive an
   acknowledgement from D after some number of requests, it would return
   a Route Error to A, as well as any other node that may have used the
   link from C to D since C last received an acknowledgement from D.
   Node A then removes this broken link from its cache; any
   retransmission of the original packet can be performed by upper layer
   protocols such as TCP, if necessary.  For sending such a
   retransmission or other packets to this same destination E, if A has
   in its Route Cache another route to E (for example, from additional
   Route Replies from its earlier Route Discovery, or from having
   overheard sufficient routing information from other packets), it can

Top      ToC       Page 14 
   send the packet using the new route immediately.  Otherwise, it
   SHOULD perform a new Route Discovery for this target (subject to the
   back-off described in Section 3.1).

3.3.  Additional Route Discovery Features

3.3.1.  Caching Overheard Routing Information

   A node forwarding or otherwise overhearing any packet SHOULD add all
   usable routing information from that packet to its own Route Cache.
   The usefulness of routing information in a packet depends on the
   directionality characteristics of the physical medium (Section 2), as
   well as on the MAC protocol being used.  Specifically, three distinct
   cases are possible:

   -  Links in the network frequently are capable of operating only
      unidirectionally (not bidirectionally), and the MAC protocol in
      use in the network is capable of transmitting unicast packets over
      unidirectional links.

   -  Links in the network occasionally are capable of operating only
      unidirectionally (not bidirectionally), but this unidirectional
      restriction on any link is not persistent; almost all links are
      physically bidirectional, and the MAC protocol in use in the
      network is capable of transmitting unicast packets over
      unidirectional links.

   -  The MAC protocol in use in the network is not capable of
      transmitting unicast packets over unidirectional links; only
      bidirectional links can be used by the MAC protocol for
      transmitting unicast packets.  For example, the IEEE 802.11
      Distributed Coordination Function (DCF) MAC protocol [IEEE80211]
      is capable of transmitting a unicast packet only over a
      bidirectional link, since the MAC protocol requires the return of
      a link-level acknowledgement packet from the receiver and also
      optionally requires the bidirectional exchange of an RTS and CTS
      packet between the transmitter and receiver nodes.

   In the first case above, for example, the source route used in a data
   packet, the accumulated route record in a Route Request, or the route
   being returned in a Route Reply SHOULD all be cached by any node in
   the "forward" direction.  Any node SHOULD cache this information from
   any such packet received, whether the packet was addressed to this
   node, sent to a broadcast (or multicast) MAC address, or overheard
   while the node's network interface is in promiscuous mode.  However,
   the "reverse" direction of the links identified in such packet
   headers SHOULD NOT be cached.

Top      ToC       Page 15 
   For example, in the situation shown below, node A is using a source
   route to communicate with node E:

      +-----+     +-----+     +-----+     +-----+     +-----+
      |  A  |---->|  B  |---->|  C  |---->|  D  |---->|  E  |
      +-----+     +-----+     +-----+     +-----+     +-----+

   As node C forwards a data packet along the route from A to E, it
   SHOULD add to its cache the presence of the "forward" direction links
   that it learns from the headers of these packets, from itself to D
   and from D to E.  Node C SHOULD NOT, in this case, cache the
   "reverse" direction of the links identified in these packet headers,
   from itself back to B and from B to A, since these links might be
   unidirectional.

   In the second case above, in which links may occasionally operate
   unidirectionally, the links described above SHOULD be cached in both
   directions.  Furthermore, in this case, if node X overhears (e.g.,
   through promiscuous mode) a packet transmitted by node C that is
   using a source route from node A to E, node X SHOULD cache all of
   these links as well, also including the link from C to X over which
   it overheard the packet.

   In the final case, in which the MAC protocol requires physical
   bidirectionality for unicast operation, links from a source route
   SHOULD be cached in both directions, except when the packet also
   contains a Route Reply, in which case only the links already
   traversed in this source route SHOULD be cached.  However, the links
   not yet traversed in this route SHOULD NOT be cached.

3.3.2.  Replying to Route Requests Using Cached Routes

   A node receiving a Route Request for which it is not the target
   searches its own Route Cache for a route to the target of the
   Request.  If it is found, the node generally returns a Route Reply to
   the initiator itself rather than forward the Route Request.  In the
   Route Reply, this node sets the route record to list the sequence of
   hops over which this copy of the Route Request was forwarded to it,
   concatenated with the source route to this target obtained from its
   own Route Cache.

   However, before transmitting a Route Reply packet that was generated
   using information from its Route Cache in this way, a node MUST
   verify that the resulting route being returned in the Route Reply,
   after this concatenation, contains no duplicate nodes listed in the
   route record.  For example, the figure below illustrates a case in
   which a Route Request for target E has been received by node F, and
   node F already has in its Route Cache a route from itself to E:

Top      ToC       Page 16 
         +-----+     +-----+                 +-----+     +-----+
         |  A  |---->|  B  |-               >|  D  |---->|  E  |
         +-----+     +-----+ \             / +-----+     +-----+
                              \           /
                               \ +-----+ /
                                >|  C  |-
                                 +-----+
                                   | ^
                                   v |
           Route Request         +-----+
           Route: A - B - C - F  |  F  |  Cache: C - D - E
                                 +-----+

   The concatenation of the accumulated route record from the Route
   Request and the cached route from F's Route Cache would include a
   duplicate node in passing from C to F and back to C.

   Node F in this case could attempt to edit the route to eliminate the
   duplication, resulting in a route from A to B to C to D and on to E,
   but in this case, node F would not be on the route that it returned
   in its own Route Reply.  DSR Route Discovery prohibits node F from
   returning such a Route Reply from its cache; this prohibition
   increases the probability that the resulting route is valid, since
   node F in this case should have received a Route Error if the route
   had previously stopped working.  Furthermore, this prohibition 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, due to this restriction
   on returning a Route Reply based on information from its Route Cache,
   node F does not return such a Route Reply, it propagates the Route
   Request normally.

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.

Top      ToC       Page 17 
   For example, a node MAY use this hop limit to implement a "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 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 [JOHNSON96a].  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 approach could increase the average latency of
   Route Discovery, since multiple Discovery attempts and timeouts may
   be needed before discovering a route to the target node.

3.4.  Additional Route Maintenance Features

3.4.1.  Packet Salvaging

   When an intermediate node forwarding a packet detects through Route
   Maintenance that the next hop along the route for that packet is
   broken, if the node has another route to the packet's destination in
   its Route Cache, the node SHOULD "salvage" the packet rather than
   discard it.  To salvage a packet, the node replaces the original
   source route on the packet with a 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, since the TTL is

Top      ToC       Page 18 
   decremented only once by each node, a single node could salvage a
   packet an unbounded number of times.  Even if we chose to require the
   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

   When an intermediate node forwarding a packet detects through Route
   Maintenance that the next-hop link along the route for that packet is
   broken, in addition to handling that packet as defined for Route
   Maintenance, the node SHOULD also handle in a similar way any pending
   packets that it has queued that are destined over this new broken
   link.  Specifically, the node SHOULD search its Network Interface
   Queue and Maintenance Buffer (Section 4.5) for packets for which the
   next-hop link is this new broken link.  For each such packet
   currently queued at this node, the node SHOULD process that packet as
   follows:

   -  Remove the packet from the node's Network Interface Queue and
      Maintenance Buffer.

   -  Originate a Route Error for this packet to the original sender of
      the packet, using the procedure described in Section 8.3.4, as if
      the node had already reached the maximum number of retransmission
      attempts for that packet for Route Maintenance.  However, in
      sending such Route Errors for queued packets in response to
      detection of a single, new broken link, the node SHOULD send no
      more than one Route Error to each original sender of any of these
      packets.

   -  If the node has another route to the packet's IP Destination
      Address in its Route Cache, the node SHOULD salvage the packet as
      described in Section 8.3.6.  Otherwise, the node SHOULD discard
      the packet.

Top      ToC       Page 19 
3.4.3.  Automatic Route Shortening

   Source routes in use MAY be automatically shortened if one or more
   intermediate nodes in the route become no longer necessary.  This
   mechanism of automatically shortening routes in use is somewhat
   similar to the use of passive acknowledgements [JUBIN87].  In
   particular, if a node is able to overhear a packet carrying a source
   route (e.g., by operating its network interface in promiscuous
   receive mode), then this node examines the unexpended portion of that
   source route.  If this node is not the intended next-hop destination
   for the packet but is named in the later unexpended portion of the
   packet's source route, then it can infer that the intermediate nodes
   before itself in the source route are no longer needed in the route.
   For example, the figure below illustrates an example in which node D
   has overheard a data packet being transmitted from B to C, for later
   forwarding to D and to E:

         +-----+     +-----+     +-----+     +-----+     +-----+
         |  A  |---->|  B  |---->|  C  |     |  D  |     |  E  |
         +-----+     +-----+     +-----+     +-----+     +-----+
                        \                       ^
                         \                     /
                          ---------------------

   In this case, this node (node D) SHOULD return a "gratuitous" Route
   Reply to the original sender of the packet (node A).  The Route Reply
   gives the shorter route as the concatenation of the portion of the
   original source route up through the node that transmitted the
   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 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.

Top      ToC       Page 20 
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,
   stale information in the caches of nodes around this source node will
   not generate Route Replies that contain the same invalid link for
   which this source node received the Route Error.

   For example, in the situation shown in the example of Section 3.2,
   node A learns from the Route Error message from C that the link from
   C to D is currently broken.  It thus removes this link from its own
   Route Cache and initiates a new Route Discovery (if it has no other
   route to E in its Route Cache).  On the Route Request packet
   initiating this Route Discovery, node A piggybacks a copy of this
   Route Error, ensuring that the Route Error spreads well to other
   nodes, and guaranteeing that any Route Reply that it receives
   (including those from other node's Route Caches) in response to this
   Route Request does not contain a route that assumes the existence of
   this broken link.



(page 20 continued on part 2)

Next RFC Part