draft-ietf-manet-dsr-10.txt

DSR-UU is a DSR implementation that runs in Linux and in the ns-2 network simulator. DSR-UU imple

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 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 [13]
       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.










Johnson, et al             Expires 19 January 2005             [Page 11]

INTERNET-DRAFT     The Dynamic Source Routing Protocol      19 July 2004


   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, but 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 found, the node generally returns a Route Reply to the
   initiator itself rather than forwarding 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






Johnson, et al             Expires 19 January 2005             [Page 12]

INTERNET-DRAFT     The Dynamic Source Routing Protocol      19 July 2004


   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:

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



Johnson, et al             Expires 19 January 2005             [Page 13]

INTERNET-DRAFT     The Dynamic Source Routing Protocol      19 July 2004


   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 [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
   approach could have the effect of increasing 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
   discarding it.  To salvage a packet, the node replaces the original
   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, since TTL is decremented



Johnson, et al             Expires 19 January 2005             [Page 14]

INTERNET-DRAFT     The Dynamic Source Routing Protocol      19 July 2004


   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

   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 a
       single new broken link detected, 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.








Johnson, et al             Expires 19 January 2005             [Page 15]

INTERNET-DRAFT     The Dynamic Source Routing Protocol      19 July 2004


3.4.3. Automatic Route Shortening