Dynamic Source Routing

DSR

DSR is a reactive routing protocol which is able to manage a MANET without using periodic table-update messages like table-driven routing protocols do. DSR was specifically designed for use in multi-hop wireless ad hoc networks. Ad-hoc protocol allows the network to be completely self-organizing and self-configuring which means that there is no need for an existing network infrastructure or administration.

For restricting the bandwidth, the process to find a path is only executed when a path is required by a node (On-Demand Routing). In DSR the sender (source, initiator) determines the whole path from the source to the destination node (Source-Routing) and deposits the addresses of the intermediate nodes of the route in the packets. Compared to other reactive routing protocols like ABR or SSA, DSR is beacon-less which means that there are no hello-messages used between the nodes to notify their neighbors about her presence. DSR was developed for MANETs with a small diameter between 5 and 10 hops and the nodes should only move around at a moderate speed.

DSR is based on the Link-State-Algorithms which mean that each node is capable to save the best way to a destination. Also if a change appears in the network topology, then the whole network will get this informations by flooding.

Importent terms

Route Source & Route Cache

DSR contains 2 phases

Route Discovery (find a path)
Route Maintenance (maintain a path)

Route Discovery and Route Maintenance only response on a request.

Route Discovery

Example 1

If node A has in his Route Cache a route to the destination E, this route is immediately used. If not, the Route Discovery protocol is started:

Node A (initiator) sends a RouteRequest packet by flooding the network
If node B has recently seen another RouteRequest from the same target or if the address of node B is already listed in the Route Record, Then node B discards the request!
If node B is the target of the Route Discovery, it returns a RouteReply to the initiator. The RouteReply contains a list of the “best” path from the initiator to the target. When the initiator receives this RouteReply, it caches this route in its Route Cache for use in sending subsequent packets to this destination.
Otherwise node B isn’t the target and it forwards the RouteRequest to his neighbors (except to the initiator).

Path-finding-process: RouteRequest & RouteReply

Example 2

Route Maintenance

In DSR every node is responsible for confirming that the next hop in the Source Route receives the packet. Also each packet is only forwarded once by a node (hop-by-hop routing). If a packet can’t be received by a node, it is retransmitted up to some maximum number of times until a confirmation is received from the next hop.
Only if retransmission results then in a failure, a RouteError message is sent to the initiator, that can remove that Source Route from its Route Cache. So the initiator can check his Route Cache for another route to the target. If there is no route in the cache, a RouteRequest packet is broadcasted.

Example 3

If node C does not receive an acknowledgement from node D after some number of requests, it returns a RouteError to the initiator A.
As soon as node receives the RouteError message, it deletes the broken-link-route from its cache. If A has another route to E, it sends the packet immediately using this new route.
Otherwise the initiator A is starting the Route Discovery process again.

Advantages

Reactive routing protocols have no need to periodically flood the network for updating the routing tables like table-driven routing protocols do. Intermediate nodes are able to utilize the Route Cache information efficiently to reduce the control overhead. The initiator only tries to find a route (path) if actually no route is known (in cache). Current and bandwidth saving because there are no hello messages needed (beacon-less).

Disadvantages

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 then 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. Flooding the network can cause collusions between the packets. Also there is always a small time delay at the begin of a new connection because the initiator must first find the route to the target.

Reference

[Johnson1996] Original Paper
[Johnson2004] Picture of Example 1
[Bahr2002] Picture of Example 2
[Johnson2001] Picture of Example 3
[Wetjen2004]
[Broch1998]

"Dynamic Source Routing" is mentioned on: Ad-Hoc Protocols (Classification) | Ad-Hoc Protocols (History) | Ad-Hoc Workshop Winter 04/05 (Termine) | Location-Aided Routing Protocol | Signal Stability-based Adaptive Routing Protocol