POPULAR ROUTING PROTOCOLS

i.Destination Sequenced Distance Vector Routing (DSDV)

Destination sequenced distance vector routing (DSDV) is adapted from the conventional
Routing Information Protocol (RIP) to ad hoc networks routing. It adds a new attribute, sequence
number, to each route table entry of the conventional RIP. Using the newly added sequence
number, the mobile nodes can distinguish stale route information from the new and thus prevent
the formation of routing loops.
Packet Routing and Routing Table Management
In DSDV, each mobile node of an ad hoc network maintains a routing table, which lists all
available destinations, the metric and next hop to each destination and a sequence number
generated by the destination node. Using such routing table stored in each mobile node, the
packets are transmitted between the nodes of an ad hoc network. Each node of the ad hoc
network updates the routing table with advertisement periodically or when significant new
information is available to maintain the consistency of the routing table with the dynamically
changing topology of the ad hoc network.
Periodically or immediately when network topology changes are detected, each mobile node
advertises routing information using broadcasting or multicasting a routing table update packet.
The update packet starts out with a metric of one to direct connected nodes. This indicates that
each receiving neighbor is one metric (hop) away from the node. It is different from that of the
conventional routing algorithms.
After receiving the update packet, the neighbors update their routing table with incrementing the
metric by one and retransmit the update packet to the corresponding neighbors of each of them.
The process will be repeated until all the nodes in the ad hoc network have received a copy of the
update packet with a corresponding metric. The update data is also kept for a while to wait for
the arrival of the best route for each particular destination node in each node before updating its
routing table and retransmitting the update packet.
If a node receives multiple update packets for a same destination during the waiting time period,
the routes with more recent sequence numbers are always preferred as the basis for packet
forwarding decisions, but the routing information is not necessarily advertised immediately, if
only the sequence numbers have been changed. If the update packets have the same sequence
number with the same node, the update packet with the smallest metric will be used and the
existing route will be discarded or stored as a less preferable route. In this case, the update packet
will be propagated with the sequence number to all mobile nodes in the ad hoc network.
The advertisement of routes that are about to change may be delayed until the best routes have
been found. Delaying the advertisement of possibly unstable route can damp the fluctuations of
the routing table and reduce the number of rebroadcasts of possible route entries that arrive with
the same sequence number. The elements in the routing table of each mobile node change
dynamically to keep consistency with dynamically changing topology of an ad hoc network.
To reach this consistency, the routing information advertisement must be frequent or quick
enough to ensure that each mobile node can almost always locate all the other mobile nodes in
the dynamic ad hoc network. Upon the updated routing information, each node has to relay data
packet to other nodes upon request in the dynamically created ad hoc network.
ii.Dynamic Source Routing Protocol (DSR)
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 node requests one. However, it
uses source routing instead of relying on the routing table at each intermediate device.
Determining source routes requires accumulating the address of each device between the source
and destination during route discovery. The accumulated path information iscached by nodes
processing the route discovery packets. 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 Request 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.
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 neighbouring 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.
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.
iii.Adhoc On-Demand Distance Vector Routing (AODV)
Reactive protocols seek to set up routes on-demand. If a node wants to initiate communication
with a node to which it has no route, the routing protocol will try to establish such a route. The
Ad-Hoc On-Demand Distance Vector routing protocol is described in RFC 3561. The
philosophy in AODV, like all reactive protocols, is that topology information is only transmitted
by nodes on-demand. When a node wishes to transmit traffic to a host to which it has no route, it
will generate a route request(RREQ) message that will be flooded in a limited way to other
nodes.
This causes control traffic overhead to be dynamic and it will result in an initial delay when
initiating such communication. A route is considered found when the RREQ message reaches
either the destination itself, or an intermediate node with a valid route entry for the destination.
For as long as a route exists between two endpoints, AODV remains passive. When the route
becomes invalid or lost, AODV will again issue a request.
AODV avoids the ``counting to infinity'' problem from the classical distance vector algorithm
by using sequence numbers for every route. The counting to infinity problem is the situation
where nodes update each other in a loop. Consider nodes A, B, C and D making up a
MANET. A is not updated on the fact that its route to D via C is broken. This means that A has a
registered route, with a metric of 2, to D. C has registered that the link to D is down, so once
node B is updated on the link breakage between C and D, it will calculate the shortest path
to D to be via A using a metric of 3. C receives information that B can reach D in 3 hops and
updates its metric to 4 hops. A then registers an update in hop-count for its route to D via C and
updates the metric to 5. And so they continue to increment the metric in a loop.
 The way this is avoided in AODV, for the example described, is by B noticing that As
route to D is old based on a sequence number. B will then discard the route and C will be the
node with the most recent routing information by which B will update its routing table.
AODV defines three types of control messages for route maintenance:
RREQ - A route request message is transmitted by a node requiring a route to a node. As
an optimization AODV uses an expanding ring technique when flooding these messages. Every
RREQ carries a time to live (TTL) value that states for how many hops this message should be
forwarded. This value is set to a predefined value at the first transmission and increased at
retransmissions. Retransmissions occur if no replies are received. Data packets waiting to be
transmitted(i.e. the packets that initiated the RREQ) should be buffered locally and transmitted
by a FIFO principal when a route is set.
RREP - A route reply message is unicasted back to the originator of a RREQ if the receiver is
either the node using the requested address, or it has a valid route to the requested address. The
reason one can unicast the message back, is that every route forwarding a RREQ caches a route
back to the originator.
RERR - Nodes monitor the link status of next hops in active routes. When a link breakage in an
active route is detected, a RERR message is used to notify other nodes of the loss of the link. In
order to enable this reporting mechanism, each node keeps a ``precursor list'', containing the IP
address for each its neighbors that are likely to use it as a next hop towards each destination.

Node A wishes to initiate traffic to node J for which it has no route. A broadcasts a
RREQ which is flooded to all nodes in the network. When this request is forwarded to J from H,
J generates a RREP. This RREP is then unicasted back to A using the cached entries in nodes H,
G and D.