Dynamic Source Routing (DSR)

DSR was first introduced and described by David B. Johnson, David A. Maltz and Josh Broch in 1994. The protocol is specifically designed for use in multi-hop wireless ad hoc networks. The protocol does not require any existing network infrastructure or administration and is completely self-organizing and self-configuring.
The protocol basically consists of the two mechanisms: Route Discovery and Route Maintenance, where the Route Discovery mechanism handles establishment of routes and the Route Maintenance mechanism keeps route information updated.
Assumptions
Some assumptions concerning the behavior of the nodes that participate in the ad hoc network are made. The most important assumptions are the following:
A1. All nodes that participate in the network are willing to participate fully in the protocols of the network.
A2. 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 it may often be greater than 1.
A3. Nodes can detect the error through a standard link-layer checksum or Cyclic Redundancy Check (CRC), and discard corrupted packages .
A4. The speed at which nodes move is moderate with respect to packet transmission latency and wireless transmission range of the particular underlying network hardware in use.
A5. Each node can be identified by a unique id by which it is recognized in the network.
Mode of Operation
DSR operate on demand, which means that no data, such as route advertisement messages, is send periodically and therefore routing traffic caused by DSR can scale down and overhead packages can be avoided.
DSR is a source routing protocol, which means the entire route is known before a packet transmission is begun. DSR stores discovered routes in a Route Cache.
DSR Modules 1. Route Discovery 2. Route Maintenance
The modules are described as follows:
Route Discovery * When a node S sends a packet to the destination D, it first searches its Route Cache or a suitable route to D.

* If no route from S to D exists in S’s route cache, S initiates Route Discovery and sends out a ROUTE REQUEST message to find a route.

* The sending node is referred to as the initiator and the destination node as the target. The fields of the ROUTE REQUEST message are explained in Following Table. Fields | Explanation | Initiator ID | The address of the initiator. | Target ID | The address of the target. | Unique Request ID | A unique ID that can identify the message. | Address list | A list of all addresses of intermediate nodes that the message passes before its destination. This is empty when the message is first send. | Hop Limit | The hop limit can be used to limit thenumber of nodes that the message isallowed to pass. | Network Interface List | If nodes have several network interfaces this information can be stored in this list. | Acknowledgement bit | There is an option of setting a bit so that the receiver returns an acknowledgement when a packet is received. |

* The initiator initialize the Address List to an empty list and set the Initiator ID, the Target Id and the Unique Request Id in the ROUTE REQUEST message and then broadcasts the message.

* When a node receives a ROUTE REQUEST message it examine the Target ID to determine if it is the target of the message. If the node is not the target it searches its own route cache for a route to the target. If a route is found it is returned.

* If the route the is not found in its Cache, the node’s own id is appended to the Address List and the ROUTE REQUEST is broadcasted.

* If a node subsequently receives two ROUTE REQUESTs with the same Request id, it is possible to specify that only the first should be handled and the subsequent discarded.

* If the node is the target it returns a ROUTE REPLY message to the initiator. This ROUTE REPLY message includes the accumulated route from the ROUTE REQUEST message.

* The target node checks if the link is bidirectional, is it is not, it searches its own Route Cache for a route to the initiator. If a route is not found in the targets Route Cache, it performs a route discovery of its own and sends out a ROUTE REQUEST where it piggybacks the ROUTE REPLY for the initiator.

* If the link is bidirectional, the target node reverses the found route in ROUTE REQUEST message and sends ROUTE REPLY back to the sender on the route discovered.

* The initiator keeps a copy of the packet in a buffer, referred to as the send buffer. It timestamps the message so it can be examined later to determine if it should be send again. If no route is discovered within a specified time frame, the packet is dropped from the send buffer. Packets are also dropped from the send buffer if the buffer overruns.

The figure below shows that as the ROUTE REQUEST originates by the sender and pass through the intermediate nodes it appends the node ID in the ROUTE REQUEST.

Route Maintenance
Since nodes move in and out of transmission range of other nodes and thereby creates and breaks routes, it is necessary to maintain the routes that are stored in the Route Cache. When a node receives a packet it is responsible for confirming that the packet reaches the next node on the route. Following

Figure shows that the mechanism works like a chain where each link has to make sure that the link in front of it is not broken. The figure also illustrates that node C might use another route to communicate to node A. * If a node transmits a packet and does not receive an acknowledgment it tries to retransmit a fixed number of times.

* If no acknowledgement is received after the retransmissions, it returns a ROUTE ERROR message to the initiator of the packet. (As in the above figure node C returns ROUTE ERROR message to node A.)

* In this message the link that was broken is included.

* The initiator removes the route from its Route Cache. * The initiator now tries to transmit using another route from its Route Cache.

* If no route is available in the Route Cache a ROUTE REQUEST is transmitted in order to establish a new route.
Additional Features in DSR
As explained in the above sections DSR has a quite simple mode of operation. However several additional features exist. This section gives an overview of these additional features. * Caching of Overheard Route Information
Nodes can cache information about routes from packets that they forward. This mechanism is called snooping and is mostly used for snooping of routes. For example a node can cache the route that is returned in a ROUTE REPLY message when it forwards it. The use of route snooping can limit the amount of ROUTE REQUEST that are sends, since nodes can discover new routes this way. * Replying to Route Request Using Cached Routes
When a node receives a ROUTE REQUEST message for which it was not the destination it can attempt to find a route from its Route Cache instead of broadcasting the ROUTE REQUEST. If a route is found it is returned to the initiator. The node must however verify that the route that is being returned does not contain any duplicating nodes since this can lead to loops. * Avoiding Storms of Route Reply
When nodes are allowed to reply to ROUTE REQUEST messages with routes from their Route Cache the risk of ROUTE REPLY “storms” is present. “Storms” can occur when a node broadcast a ROUTE REQUEST and its neighbour nodes all has routes for the target in their cache. This will result in simultaneous ROUTE REPLYs from all neighbours that can cause congestion or packet collision. This can be avoided by letting the nodes delay ROUTE REPLYs for a random period. This delay effectively randomizes the time at which a node returns a ROUTE REPLY message. * 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 Rout 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. * Salvaging Packets
When a node forwards a packet, it might successively discover, through the use of Route Maintenance, that the route for the packet is broken. If the node has another route to the destination it can use it and thereby salvage the packet. If the packet is salvaged a ROUTE ERROR should be send to the original sender to report the link on the route that was broken. * Decreased spreading of ROUTE ERROR Messages
When a source node receives a Route Error for a data packet that it originated, this source node propagates this Route Error to its neighbors by piggybacking it on its next Route Request. In this way, stale information in the caches of nodes around this source node will not generate Route Replies that contain the same invalid link for which this source node received the Route Error.
Advantages
* Routes are maintained only between nodes who need to communicate, this reduces overhead of route maintenance. * Route caching can further reduce route discovery overhead. * A single route discovery may yield many routes to the destination, due to intermediate nodes replying from local caches.

Disadvantages * Packet header size grows with route length due to source routing. * The Route Maintenance protocol does not locally repair a broken link. The broken link is only communicated to the initiator. * The DSR protocol is only efficient in MANETs with less than 200 nodes. * Problems appear by fast moving of more hosts, so that the nodes can only move around in this case with a moderate speed * Flood of route requests may potentially reach all nodes in the network * Care must be taken to avoid collisions between route requests propagated by neighboring nodes, by insertion of random delays before forwarding RREQ. * Increased contention if too many route replies come back due to nodes replying using their local cache. Route Reply Storm problem Reply storm may be eased by preventing a node from sending RREP if it hears another RREP with a shorter route.

References 1. M.Sc. Thesis Secure Routing in Mobile Ad Hoc Networks by Lennart Conrad 2003 2. Research Paper: DSR: The Dynamic Source Routing Protocol for Multi-HopWirelessAdHocNetworks by David B. Johnson David A. Maltz Josh Broch Computer Science Department Carnegie Mellon University 3. RFC 4728