dsr_draft1.txt

dsr路协议规范

   these functions from any underlying protocols in the network.  This
   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 that 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.

   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 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 operation of both Route Discovery and Route Maintenance in DSR
   are designed to allow uni-directional links and asymmetric routes
   to be easily supported.  In particular, as noted in Section 2, in
   wireless networks, it is possible that a link between two nodes may
   not work equally well in both directions, due to differing antenna
   or propagation patterns or sources of interference.  DSR allows such
   uni-directional links to be used when necessary, improving overall
   performance and network connectivity in the system.

   This document specifies the operation of the DSR protocol for routing
   unicast IP packets in multi-hop wireless ad hoc networks.  Advanced,
   optional features, such as Quality of Service (QoS) support and
   efficient multicast routing, are covered in other documents.  The
   specification of DSR in this document provides a compatible base
   on which such features can be added, either independently or by
   integration with the DSR operation specified here.

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




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


2. Assumptions

   We assume 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 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 may often be greater than 1.

   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 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 are more the inherent
   limiting factor 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 [13].  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
   differing antenna or propagation patterns or sources of interference



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


   around the two nodes [1, 17].  That is, wireless communications
   between each pair of nodes will in many cases be able to operate
   bi-directionally, but at times the wireless link between two nodes
   may be only uni-directional, allowing one node to successfully send
   packets to the other while no communication is possible in the
   reverse direction.  Although many routing protocols operate correctly
   only over bi-directional links, DSR can successfully discover and
   forward packets over paths that contain uni-directional links.
   Some MAC protocols, however, such as MACA [16], MACAW [2], or IEEE
   802.11 [10], limit unicast data packet transmission to bi-directional
   links, due to the required bi-directional exchange of RTS and CTS
   packets in these protocols and due to the link-level acknowledgement
   feature in IEEE 802.11; when used on top of MAC protocols such as
   these, DSR can take advantage of additional optimizations, such as
   the easy ability to reverse a source route to obtain a route back to
   the origin of the original route.

   The IP address used by a node using the DSR protocol MAY be assigned
   by any mechanism (e.g., static assignment or use of DHCP for dynamic
   assignment [8]), although the method of such assignment is outside
   the scope of this specification.
































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


3. DSR Protocol Overview

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

   Otherwise, if this node receiving the Route Request has recently seen
   another Route Request message from this initiator bearing this same



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


   request identification and target address, or if this node's own
   address is already listed in the route record in the Route Request,
   this node discards the Request.  Otherwise, this node appends its
   own address to the route record in the Route Request and propagates
   it by transmitting it as a local broadcast packet (with the same
   request identification).  In this example, node B broadcast the Route
   Request, which is received by node C; nodes C and D each also, in
   turn, broadcast the Request, resulting in a copy of the Request being
   received by node E.

   In returning the Route Reply to the initiator of the Route Discovery,
   such as in this example, node E replying back to node A, node E will
   typically examine its own Route Cache for a route back to A, and if
   found, will use it for the source route for delivery of the packet
   containing the Route Reply.  Otherwise, E SHOULD perform its own
   Route Discovery for target node A, but to avoid possible infinite
   recursion of Route Discoveries, it MUST piggyback this Route Reply
   on the packet containing its own Route Request for A.  It is also
   possible to piggyback other small data packets, such as a TCP SYN
   packet [25], 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 bi-directional
   frame exchange as part of the MAC protocol [10], this route reversal
   is preferred, as it avoids the overhead of a possible second
   Route Discovery, and it tests the discovered route to ensure it is
   bi-directional before the Route Discovery initiator begins using the
   route.  However, this technique will prevent the discovery of routes
   using uni-directional links.  In wireless environments where the use
   of uni-directional links is permitted, such routes may in some cases
   be more efficient than those with only bi-directional links, or they
   may be the only way to achieve connectivity to the target node.

   When initiating a Route Discovery, the sending node saves a copy of
   the original packet (that triggered the Discovery) in a local buffer
   called the "Send Buffer".  The Send Buffer contains a copy of each
   packet that cannot be transmitted by this node because it does not
   yet have a source route to the packet's destination.  Each packet in
   the Send Buffer is logically associated with the time that it was
   placed into the Send Buffer and is discarded after residing in the
   Send Buffer for some timeout period; if necessary for preventing the
   Send Buffer from overflowing, a FIFO or other replacement strategy
   MAY also be used to evict packets even before they expire.

   While a packet remains in the Send Buffer, the node SHOULD
   occasionally initiate a new Route Discovery for the packet's
   destination address.  However, the node MUST limit the rate at which
   such new Route Discoveries for the same address are initiated, since



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


   it is possible that the destination node is not currently reachable.
   In particular, due to the limited wireless transmission range and the
   movement of the nodes in the network, the network may at times become
   partitioned, meaning that there is currently no sequence of nodes
   through which a packet could be forwarded to reach the destination.
   Depending on the movement pattern and the density of nodes in the
   network, such network partitions may be rare or may be common.

   If a new Route Discovery was initiated for each packet sent by a
   node in such a partitioned network, a large number of unproductive
   Route Request packets would be propagated throughout the subset of
   the ad hoc network reachable from this node.  In order to reduce the
   overhead from such Route Discoveries, a node MUST use an exponential
   back-off algorithm to limit the rate at which it initiates new Route
   Discoveries 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 [3].