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 transmissionJohnson, 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 theJohnson, 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 20043.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 packetJohnson, 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