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

1. Introduction

   The Dynamic Source Routing protocol (DSR) [15, 16] is a simple and
   efficient routing protocol designed specifically for use in multi-hop
   wireless ad hoc networks of mobile nodes.  Using DSR, the network
   is completely self-organizing and self-configuring, requiring no
   existing network infrastructure or administration.  Network nodes
   cooperate to forward packets for each other to allow communication
   over multiple "hops" between nodes not directly within wireless
   transmission range of one another.  As nodes in the network move
   about or join or leave the network, and as wireless transmission
   conditions such as sources of interference change, all routing is
   automatically determined and maintained by the DSR routing protocol.
   Since the number or sequence of intermediate hops needed to reach any
   destination may change at any time, the resulting network topology
   may be quite rich and rapidly changing.

   In designing DSR, we sought to create a routing protocol that had
   very low overhead yet was able to react very quickly to changes in
   the network.  The DSR protocol provides highly reactive service in
   order to help ensure successful delivery of data packets in spite of
   node movement or other changes in network conditions.

   The DSR protocol is composed of two main mechanisms that work
   together to allow the discovery and maintenance of source routes in
   the ad hoc network:

    -  Route Discovery is the mechanism by which a node S wishing to
       send a packet to a destination node D obtains a source route
       to D.  Route Discovery is used only when S attempts to send a
       packet to D and does not already know a route to D.

    -  Route Maintenance is the mechanism by which node S is able
       to detect, while using a source route to D, if the network
       topology has changed such that it can no longer use its route
       to D because a link along the route no longer works.  When Route
       Maintenance indicates a source route is broken, S can attempt to
       use any other route it happens to know to D, or can invoke Route
       Discovery again to find a new route for subsequent packets to D.
       Route Maintenance for this route is used only when S is actually
       sending packets to D.

   In DSR, Route Discovery and Route Maintenance each operate entirely
   "on demand".  In particular, unlike other protocols, DSR requires no
   periodic packets of any kind at any layer within the network.  For
   example, DSR does not use any periodic routing advertisement, link
   status sensing, or neighbor detection packets, and does not rely on
   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



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


   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.

   All state maintained by DSR is "soft state" [6], in that the loss
   of any state will not interfere with the correct operation of the
   protocol; all state is discovered as needed and can easily and
   quickly be rediscovered if needed after a failure without significant
   impact on the protocol.  This use of only soft state allows the
   routing protocol to be very robust to problems such as dropped or
   delayed routing packets or node failures.  In particular, a node in
   DSR that fails and reboots can easily rejoin the network immediately
   after rebooting; if the failed node was involved in forwarding
   packets for other nodes as an intermediate hop along one or more
   routes, it can also resume this forwarding quickly after rebooting,
   with no or minimal interruption to the routing 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 support for multiple
   routes 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 sender of
   a packet selects and controls the route used for its own packets,
   which together with support for multiple routes also allows features
   such as load balancing to be defined.  In addition, all routes used
   are easily guaranteed to be loop-free, since the sender can avoid
   duplicate hops in the routes selected.

   The operation of both Route Discovery and Route Maintenance in DSR
   are designed to allow unidirectional links and asymmetric routes to
   be 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.

   This document specifies the operation of the DSR protocol for
   routing unicast IPv4 packets in multi-hop wireless ad hoc networks.
   Advanced, optional features, such as Quality of Service (QoS) support
   and efficient multicast routing, and operation of DSR with IPv6 [7],
   are covered in other documents.  The specification of DSR in this
   document provides a compatible base on which such features can be




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


   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 19 January 2005              [Page 3]

INTERNET-DRAFT     The Dynamic Source Routing Protocol      19 July 2004


2. Assumptions

   The DSR protocol as described here is designed mainly for mobile
   ad hoc networks of up to about two hundred nodes, and is designed
   to work well with even very high rates of mobility.  Other protocol
   features and enhancements that may allow DSR to scale to larger
   networks are outside the scope of this document.

   We assume in this document 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 ad hoc 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 [16].  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



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


   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
   around the two nodes [1, 20].  That is, wireless communications
   between each pair of nodes will in many cases be able to operate
   bidirectionally, but at times the wireless link between two nodes
   may be only unidirectional, allowing one node to successfully
   send packets to the other while no communication is possible
   in the reverse direction.  Some MAC protocols, however, such as
   MACA [19], MACAW [2], or IEEE 802.11 [13], limit unicast data
   packet transmission to bidirectional links, due to the required
   bidirectional exchange of RTS and CTS packets in these protocols and
   due to the link-layer 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 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.

   A routing protocol such as DSR chooses a next-hop for each packet
   and provides the IP address of that next-hop.  When the packet
   is transmitted, however, the lower-layer protocol often has a
   separate, MAC-layer address for the next-hop node.  DSR uses the
   Address Resolution Protocol (ARP) [30] to translate from next-hop IP
   addresses to next-hop MAC addresses.  In addition, a node MAY add
   an entry to its ARP cache based on any received packet, when the IP
   address and MAC address of the transmitting node are available in
   the packet; for example, the IP address of the transmitting node
   is present in a Route Request option (in the Address list being
   accumulated) and any packets containing a source route.  Adding
   entries to the ARP cache in this way avoids the overhead of ARP in
   most cases.















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