Dynamic Source Routing 

Dynamic Source Routing (DSR) is a routing protocol for wireless mesh networks. It is similar

to AODV in that it forms a route on-demand when a transmitting computer requests one. However, it
uses source routing instead of relying on the routing table at each intermediate device. Many successive
refinements have been made to DSR, including DSRFLOW.

Determining source routes requires accumulating the address of each device between the source and
destination during route discovery. The accumulated path information is cached by nodes processing the
route discoverypackets. The learned paths are used to route packets. To accomplish source routing, the
routed packets contain the address of each device the packet will traverse. This may result in high
overhead for long paths or large addresses, like IPv6. To avoid using source routing, DSR optionally
defines a flow id option that allows packets to be forwarded on a hop-by-hop basis.

This protocol is truly based on source routing whereby all the routing information is maintained
(continually updated) at mobile nodes. It has only two major phases, which are Route Discovery and
Route Maintenance. Route Reply would only be generated if the message has reached the intended
destination node (route record which is initially contained in Route Request would be inserted into the
Route Reply).

To return the Route Reply, the destination node must have a route to the source node. If the route is in
the Destination Node's route cache, the route would be used. Otherwise, the node will reverse the route
based on the route record in the Route Reply message header (this requires that all links are symmetric).
In the event of fatal transmission, the Route Maintenance Phase is initiated whereby the Route Error
packets are generated at a node. The erroneous hop will be removed from the node's route cache; all
routes containing the hop are truncated at that point. Again, the Route Discovery Phase is initiated to
determine the most viable route.

For information on other similar protocols, see the ad hoc routing protocol list.

Dynamic source routing protocol (DSR) is an on-demand protocol designed to restrict

the bandwidth consumed by control packets in ad hoc wireless networks by eliminating the periodic table-
update messages required in the table-driven approach. The major difference between this and the other
on-demand routing protocols is that it is beacon-less and hence does not require periodic hello packet
(beacon) transmissions, which are used by a node to inform its neighbors of its presence. The basic
approach of this protocol (and all other on-demand routing protocols) during the route construction phase
is to establish a route by flooding RouteRequest packets in the network. The destination node, on
receiving a RouteRequest packet, responds by sending a RouteReply packet back to the source, which
carries the route traversed by the RouteRequest packet received.
Consider a source node that does not have a route to the destination. When it has data packets to be
sent to that destination, it initiates a RouteRequest packet. This RouteRequest is flooded throughout the
network. Each node, upon receiving a RouteRequest packet, rebroadcasts the packet to its neighbors if it
has not forwarded it already, provided that the node is not the destination node and that the packet’s time
to live (TTL) counter has not been exceeded. Each RouteRequest carries a sequence number generated
by the source node and the path it has traversed. A node, upon receiving a RouteRequest packet, checks
the sequence number on the packet before forwarding it. The packet is forwarded only if it is not a
duplicate RouteRequest. The sequence number on the packet is used to prevent loop formations and to
avoid multiple transmissions of the same RouteRequest by an intermediate node that receives it through
multiple paths. Thus, all nodes except the destination forward a RouteRequest packet during the route
construction phase. A destination node, after receiving the first RouteRequest packet, replies to the
source node through the reverse path the RouteRequest packet had traversed. Nodes can also learn
about the neighboring routes traversed by data packets if operated in the promiscuous mode (the mode of
operation in which a node can receive the packets that are neither broadcast nor addressed to itself). This
route cache is also used during the route construction phase. If an intermediate node receiving a
RouteRequest has a route to the destination node in its route cache, then it replies to the source node by
sending a RouteReply with the entire route information from the source node to the destination node.

Advantages and disadvantages

This protocol uses a reactive approach which eliminates the need to periodically flood the network with
table update messages which are required in a table-driven approach. In a reactive (on-demand)
approach such as this, a route is established only when it is required and hence the need to find routes to
all other nodes in the network as required by the table-driven approach is eliminated. The intermediate
nodes also utilize the route cache information efficiently to reduce the control overhead. The
disadvantage of this protocol is that the route maintenance mechanism does not locally repair a broken
link. Stale route cache information could also result in inconsistencies during the route reconstruction
phase. The connection setup delay is higher than in table-driven protocols. Even though the protocol
performs well in static and low-mobility environments, the performance degrades rapidly with increasing
mobility. Also, considerable routing overhead is involved due to the source-routing mechanism employed
in DSR. This routing overhead is directly proportional to the path length.
Destination-Sequenced Distance Vector routing
Destination-Sequenced Distance-Vector Routing (DSDV) is a table-driven routing scheme for ad hoc mobile

networks based on the Bellman-Ford algorithm. It was developed by C. Perkins and P.Bhagwat in 1994. The main

contribution of the algorithm was to solve the routing loop problem. Each entry in the routing table contains a

sequence number, the sequence numbers are generally even if a link is present; else, an odd number is used. The

number is generated by the destination, and the emitter needs to send out the next update with this number. Routing

information is distributed between nodes by sending full dumps infrequently and smaller incremental updates more

frequently.

For example the routing table of Node A in this network is

Sequence
Destination Next Hop Number of Hops Install Time
Number

A A 0 A 46 001000

B B 1 B 36 001200

C B 2 C 28 001500

Naturally the table contains description of all possible paths reachable by node A, along with the next hop, number of

hops and sequence number.

Selection of Route

If a router receives new information, then it uses the latest sequence number. If the sequence number is the same as

the one already in the table, the route with the better metric is used. Stale entries are those entries that have not been

updated for a while. Such entries as well as the routes using those nodes as next hops are deleted.

Advantages
DSDV was one of the early algorithms available. It is quite suitable for creating ad hoc networks with small number of

nodes. Since no formal specification of this algorithm is present there is no commercial implementation of this

algorithm. DSDV guarantees for loop free path

Disadvantages

DSDV requires a regular update of its routing tables, which uses up battery power and a small amount of bandwidth

even when the network is idle.

Whenever the topology of the network changes, a new sequence number is necessary before the network re-

converges; thus, DSDV is not suitable for highly dynamic networks. (As in all distance-vector protocols, this does not

perturb traffic in regions of the network that are not concerned by the topology change.)

Optimized Link State Routing Protocol

The Optimized Link State Routing Protocol (OLSR)[1] is an IP routing protocol optimized for mobile ad-hoc

networks, which can also be used on other wireless ad-hoc networks. OLSR is a proactive link-state routing protocol,

which uses Hello and Topology Control (TC) messages to discover and then disseminate link state information

throughout the mobile ad-hoc network. Individual nodes use this topology information to compute next hop

destinations for all nodes in the network using shortest hop forwarding paths.

Features specific to OLSR

Link-state routing protocols such as OSPF and IS-IS elect a designated router on every link to perform flooding of

topology information. In wireless ad-hoc networks, there is different notion of a link, packets can and do go out the

same interface; hence, a different approach is needed in order to optimize the flooding process. Using Hello

messages the OLSR protocol at each node discovers 2-hop neighbor information and performs a distributed election

of a set of multipoint relays (MPRs). Nodes select MPRs such that there exists a path to each of its 2-hop neighbors
via a node selected as an MPR. These MPR nodes then source and forward TC messages that contain the MPR

selectors. This functioning of MPRs makes OLSR unique from other link state routing protocols in a few different

ways: The forwarding path for TC messages is not shared among all nodes but varies depending on the source, only

a subset of nodes source link state information, not all links of a node are advertised but only those that represent

MPR selections.

Since link-state routing requires the topology database to be synchronized across the network, OSPF and IS-IS

perform topology flooding using a reliable algorithm. Such an algorithm is very difficult to design for ad-hoc wireless

networks, so OLSR doesn't bother with reliability; it simply floods topology data often enough to make sure that the

database does not remain unsynchronized for extended periods of time.

Benefits
Being a proactive protocol, routes to all destinations within the network are known and maintained before use. Having

the routes available within the standard routing table can be useful for some systems and network applications as

there is no route discovery delay associated with finding a new route.

The routing overhead generated, while generally greater than that of a reactive protocol, does not increase with the

number of routes being used.

Default and network routes can be injected into the system by HNA messages allowing for connection to the internet

or other networks within the OLSR MANET cloud. Network routes are something reactive protocols do not currently

execute well.

Timeout values and validity information is contained within the messages conveying information allowing for differing

timer values to be used at differing nodes.

Criticisms

The original definition of OLSR does not include any provisions for sensing of link quality; it simply assumes that a

link is up if a number of hello packets have been received recently. This assumes that links are bi-modal (either

working or failed), which is not necessarily the case on wireless networks, where links often exhibit intermediate rates

of packet loss. Implementations such as the open source OLSRd (commonly used on Linux-based mesh routers)

have been extended (as of v. 0.4.8) with link quality sensing.

Being a proactive protocol, OLSR uses power and network resources in order to propagate data about possibly

unused routes. While this is not a problem for wired access points, and laptops, it makes OLSR unsuitable for sensor

networks that try to sleep most of the time. For small scale wired access points with low CPU power, the open

source OLSRd project showed that large scale mesh networks can run with OLSRd on thousands of nodes with very

little CPU power on 200 MHz embedded devices.

Being a link-state protocol, OLSR requires a reasonably large amount of bandwidth and CPU power to compute

optimal paths in the network. In the typical networks where OLSR is used (which rarely exceed a few hundreds of

nodes), this does not appear to be a problem.

By only using MPRs to flood topology information, OLSR removes some of the redundancy of the flooding process,

which may be a problem in networks with moderate to large packet loss rates[2] - however the MPR mechanism is

self-pruning (which means that in case of packet losses, some nodes that would not have retransmitted a packet,

may do so).

Messages

OLSR makes use of "Hello" messages to find its one hop neighbors and its two hop neighbors through their

responses. The sender can then select its multipoint relays (MPR) based on the one hop node that offers the best

routes to the two hop nodes. Each node has also an MPR selector set, which enumerates nodes that have selected it
as an MPR node. OLSR uses Topology Control (TC) messages along with MPR forwarding to disseminate neighbor

information throughout the network. Host and Network Association (HNA) messages are used by OLSR to

disseminate network route advertisements in the same way TC messages advertise host routes.

Hello

Hierarchical state routing

Hierarchical state routing (HSR), proposed in Scalable Routing Strategies for Ad Hoc Wireless Networks by Iwata

et al. (1999), is a typical example of a hierarchical routing protocol.

HSR maintains a hierarchical topology, where elected clusterheads at the lowest level become members of the next

higher level. On the higher level, superclusters are formed, and so on. Nodes which want to communicate to a node

outside of their cluster ask their clusterhead to forward their packet to the next level, until a clusterhead of the other

node is in the same cluster. The packet then travels down to the destination node.

Furthermore, HSR proposes to cluster nodes in a logical way instead of in a geological way: members of the same

company or in the same battlegroup are clustered together, assuming they will communicate much within the logical

cluster.HSR does not specify how a cluster is to be formed.