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. 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 still preserves the
   fundamental properties of DSR's operation.


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



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


   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
   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 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 [33], 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 as part of the MAC protocol [13], the discovered source
   route MUST be reversed in this way to return the Route Reply since it
   tests the discovered route to ensure it is bidirectional before the



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


   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.

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







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


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, node D is responsible for the link from D to E.

   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 [13]), or by a "passive acknowledgement" [18] (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 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 to not 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



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


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






































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