dsr_draft1.txt

dsr路协议规范

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 the
   packet has been received by the next hop along the source route; the
   packet SHOULD be retransmitted (up to a maximum number of attempts)
   until this confirmation of receipt is received.  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  |--x  |  D  |     |  E  |
         +-----+     +-----+     +-----+     +-----+     +-----+

   In this case, node A is responsible for receipt of the packet at B,
   node B is responsible for receipt at C, node C is responsible for
   receipt at D, and node D is responsible for receipt finally at the
   destination E.

   This confirmation of receipt in many cases may be provided at no cost
   to DSR, either as an existing standard part of the MAC protocol in
   use (such as the link-level acknowledgement frame defined by IEEE
   802.11 [10]), or by a "passive acknowledgement" [15] (in which,
   for example, B confirms receipt at C by overhearing C transmit the



Johnson, et al             Expires 2 September 2001             [Page 7]
 
INTERNET-DRAFT     The Dynamic Source Routing Protocol      2 March 2001


   packet when forwarding it on to D).  If neither of these confirmation
   mechanisms are available, the node transmitting the packet can
   explicitly request a DSR-specific software acknowledgement be
   returned by the next hop; this software acknowledgement will normally
   be transmitted directly to the sending node, but if the link between
   these two nodes is uni-directional, this software acknowledgement may
   travel over a different, multi-hop path.

   If no receipt confirmation is received after the packet has been
   retransmitted the maximum number of attempts by some hop, this node
   SHOULD return a "Route Error" to the original sender of the packet,
   identifying the link over which the packet could not be forwarded.
   For example, in the example shown above, if C is unable to deliver
   the packet to the next hop D, then C returns a Route Error to A,
   stating that the link from C to D is currently "broken".  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 send the packet
   using the new route immediately.  Otherwise, it SHOULD perform a new
   Route Discovery for this target (subject to the exponential 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 MAY add the
   routing information from that packet to its own Route Cache.  In
   particular, 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 MAY all be cached by any node.  Routing information from
   any of these packets received can be cached, whether the packet
   was addressed to this node, sent to a broadcast (or multicast)
   MAC address, or received while the node's network interface is in
   promiscuous mode.

   One limitation, however, on caching of such overheard routing
   information is the possible presence of uni-directional links in the










Johnson, et al             Expires 2 September 2001             [Page 8]
 
INTERNET-DRAFT     The Dynamic Source Routing Protocol      2 March 2001


   ad hoc network (Section 2).  For example, in the situation shown
   below, node A is using a source route to communicate with node E:

         +-----+     +-----+     +-----+     +-----+     +-----+
         |  A  |---->|  B  |---->|  C  |---->|  D  |---->|  E  |
         +-----+     +-----+     +-----+     +-----+     +-----+
                                    ^
                                    |
         +-----+     +-----+     +-----+     +-----+     +-----+
         |  V  |---->|  W  |---->|  X  |---->|  Y  |---->|  Z  |
         +-----+     +-----+     +-----+     +-----+     +-----+

   As node C forwards a data packet along the route from A to E, it
   MAY 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.  However, the "reverse" direction of the links
   identified in the packet headers, from itself back to B and from B
   to A, may not work for it since these links might be uni-directional.
   If C knows that the links are in fact bi-directional, for example due
   to the MAC protocol in use, it could cache them but otherwise SHOULD
   not.

   Likewise, node V in the example above is using a different source
   route to communicate with node Z.  If node C overhears node X
   transmitting a data packet to forward it to Y (from V), node C SHOULD
   consider whether the links involved can be known to be bi-directional
   or not before caching them.  If the link from X to C (over which this
   data packet was received) can be known to be bi-directional, then C
   MAY cache the link from itself to X, the link from X to Y, and the
   link from Y to Z.  If all links can be assumed to be bi-directional,
   C MAY also cache the links from X to W and from W to V.  Similar
   considerations apply to the routing information that might be learned
   from forwarded or otherwise overheard Route Request or Route Reply
   packets.


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,



Johnson, et al             Expires 2 September 2001             [Page 9]
 
INTERNET-DRAFT     The Dynamic Source Routing Protocol      2 March 2001


   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:

         +-----+     +-----+                 +-----+     +-----+
         |  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 for two reasons.  First,
   this limitation 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.  Second, this
   limitation means that a 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 the Route
   Request does not meet these restrictions, the node (node F in this
   example) discards the Route Request rather than replying to it or
   propagating it.


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




Johnson, et al            Expires 2 September 2001             [Page 10]
 
INTERNET-DRAFT     The Dynamic Source Routing Protocol      2 March 2001


   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, these nodes would all attempt to reply from their own
   Route Caches, and would 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 replies from different nodes
   all receiving the Route Request may create packet collisions among
   some or all of these Replies and may cause local congestion in the
   wireless network.  In addition, it will often be the case that the
   different replies will indicate routes of different lengths, as shown
   in this example.

   If a node can put its network interface into promiscuous receive
   mode, it SHOULD delay sending its own Route Reply for a short period,
   while listening to see if the initiating node begins using a shorter
   route first.  That is, this node SHOULD 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.



Johnson, et al            Expires 2 September 2001             [Page 11]
 
INTERNET-DRAFT     The Dynamic Source Routing Protocol      2 March 2001


   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

   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.  For example, a node MAY send 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 rebroadcasting
   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 a
   "propagating" Route Request (i.e., with no hop limit) MAY be sent.

   Another possible use of the hop limit in a Route Request is to
   implement an "expanding ring" search for the target [13].  For
   example, a node could send an initial non-propagating Route Request
   as described above; if no Route Reply is received for it, the node
   could initiate another Route Request with a hop limit of 2.  For