ISSUES IN DESIGNING A ROUTING PROTOCOL

•Major challenges that a routing protocol designed for ad hoc wireless

networks face sare–mobility of nodes–resource constraints–error-prone
channel state–hidden and exposed terminal problems Mobility

• The network topology in an ad hoc wireless network is highly dynamic

due to the movement of nodes, hence an on-going session suffers
frequent path break.
• Disruption occurs either due to the movement of the intermediate nodes
in the path or due to the movement of end nodes.
•Even though the wired network protocols find alternate routes during
path breaks, their convergence is very slow. Therefore, wired network
routing protocols cannot be used in ad hoc wireless networks where the
mobility of nodes results in frequently changing network topologies.
•Routing protocols for ad hoc wireless networks must be able to perform
efficient and effective mobility management.
Bandwidth Constraint
•Abundant bandwidth is available in wired networks due to the advent of
fiber optics and wavelength division multiplexing(WDM) technologies.
•But in a wireless network, the radio band is limited, and hence the data
rates it can offer are much less.
•This requires that the routing protocols use the bandwidth optimally by
keeping the overhead as low as possible.
•Due to the frequent changes in topology , maintaining a consistent
topological information at all the nodes involves more control overhead
which , in turn , results in more bandwidth wastage .
•As efficient routing protocols in wired networks require the complete
topology information, they may not be suitable for routing in the ad hoc
wireless networking environment.
Error-Prone Shared Broadcast Radio Channel
•The broadcast nature of the radio channel poses a unique challenge in ad
hoc wireless networks
Routing

Routing is the process of finding the best path for traffic in a network,
or across multiple networks. The role of routing is similar to the road
map for a hotel. In both cases, we need to deliver messages at proper
location and in an appropriate way.
Routing in a mobile ad-hoc network depends on many factors such as:
o Modeling of the topology,
o Selection of routers,
o Initiation of a route request,
o And specific underlying characteristics that could serve as
heuristics in finding the path effectively.
In a MANET, each node or device is expected to serve as a router, and
each router is indistinguishable from another in the sense that all routers
execute the same routing algorithm to compute paths through the entire
network.
Need for Routing
There are following needs for routing:
o Since centralized routing in a dynamic and even for small networks
is impossible therefore routing computation must be distributed.
o Route computation should not add many more nodes.
o If any host demands for the route, they must have quick access.
o Maintenance of a global state should not involve in the route
computation.
 o Each node should care about their destination node to its route and
should not be involved in frequent topology updates for those
portions of the network that have no traffic.
o Since broadcast can be time consuming for MANETs, it must be
avoided as much as possible.
o In routing there must have a backup route when the primary route
has become stale.
Routing Classification
Routing protocol can be classified as:
1. Proactive Protocol
2. Reactive Protocol
3. Hybrid Protocol
1. Proactive Protocol
Proactive protocols attempt to evaluate continuously the routes within
the network. It means proactive protocol continuously maintain the
routing information, so that when a packet needs to be forwarded, the
path is known already and can be immediately used. The family of
distance vector protocols is an example of proactive scheme.
The advantage of the proactive schemes is that whenever a route is
needed, there is negligible delay in determining the route.
Unfortunately, it is a big overhead to maintain routing tables in the
MANET environment. Therefore, this type of protocol has following
common disadvantages:
o Requires more amounts of data for maintaining routing
information.
o Low reaction on re-structuring network and failures of individual
nodes.
2. Reactive Protocols
Reactive protocols do not maintain routes but invoke a route
determination procedure only on demand or we can say reactive
protocols build the routes only on demand. Thus, when a route is
required, some sort of global search procedure is initiated. The family of
classical flooding algorithms belongs to the reactive protocol group.
Examples of reactive ad-hoc network routing protocols include ad hoc
on demand distance vector (AODV) and temporally ordered routing
algorithm (TORA).
These protocols have the following advantages:
o No large overhead for global routing table maintenance as in
proactive protocols.
o Reaction is quick for network restructure and node failure.
Even though reactive protocols have become the main stream for
MANET routing, they still have the following disadvantages:
o Latency time is high in route finding
o Excessive flooding can lead to network clogging.
3. Hybrid Protocols
Hybrid protocols attempt to take advantage of best of reactive and
proactive schemes. The basic idea behind such protocols is to initiate
route discovery on demand but at a limited search cost. One of the
popular hybrid protocols is zone routing protocol (ZRP).
Routing protocols may also be categorized as follows:
1. Table-driven protocols
2. Source initiated on -demand protocols
1. Table-driven routing protocol
o These protocols are called table-driven because each node is

required to maintain one or more tables containing routing

information on every other node in the network.
 o They are proactive in nature so that the routing information is
always consistent and up to date.
o The protocols respond to changes in network topology by
propagating the updates throughput the network so that every node
has a consistent view of the network.
The table driven routing protocols are categorized as follows:
Destination - sequenced distance vector routing
o Destination sequenced distance vector routing (DSDV) is a table

driven routing protocol for MANET based on Bellman-Ford

algorithm.
o DSDV was developed by C. Perkins and P. Bhagwat in 1994.

The main contribution of the algorithm was that the algorithm

works correctly, even in the presence of the loops in the routing
table.
o As we know, each mobile node maintains a routing table with a

route to every possible destination in the network and the number

of hops to the destination.
o Each entry in the table contains a sequence number assigned by the

destination node.
o The sequence numbers allow the node to distinguish stale routes

from new ones, and help avoid formation of routing loops.

o A new route broadcast contains:

o The destination address.

o The number of hops required to reach the destination.

o The sequence number of the information received about the

destination and a new sequence number unique to the

broadcast.
o If there multiple routes are available for the same destination, the

route with the most recent sequence number is used. If two updates
have the same sequence number, the route with smaller metric is
used to optimize the routing.
For example the routing table of Node A from the above network is:

Destination Next No. of Sequence Install

Hop Hops no. time

A A 0 A46 001000

B B 1 B36 001200

C B 2 C28 001500

Basically the table stores description of all possible paths reachable by

node A, along with the hop, number of hops, sequence number and
install time.
Advantages
o Destination sequenced distance vector routing was one of the early
algorithms available. It is suitable for creating ad-hoc networks
with small no. of nodes.
Disadvantage
o Destination sequenced distance vector routing requires a regular
update of its routing tables, which uses more battery power and a
small amount of bandwidth even when the network is idle.
o This algorithm is not suitable for highly dynamic networks.
Cluster Head gateway switch Routing
o The cluster head (CH) gateway switch routing (CGSR) protocol is

different from the destination sequenced distance vector routing in

the type of addressing and the network organization scheme
employed.
o Instead of a flat network, CGSR uses cluster heads, which control a

group of ad hoc nodes and hence achieve a hierarchical framework

for code separation among clusters, routing, channel access, and
bandwidth allocation.
o Identification of appropriate clusters and selection of cluster heads

is quite complex. Once clusters have been defined, it is desirable to

use a distributed algorithm within the cluster to elect a node as the
cluster head.
o The disadvantage of using a cluster head scheme is that frequent

changes adversely affect performance as nodes spend more time

selecting a cluster head rather than relaying packets. Hence, the
least cluster change (LCC) clustering algorithm is used rather than
CH selection every time the cluster membership changes. Using
LCC, CHs change only when two CHs come into contact, or when
a node moves out of contact with all other CHs.

o In this scheme, each node must maintain a cluster member table

(CMT), which stores the destination CH for each node in the
network. The cluster member tables are broadcast periodically by
the nodes using the DSDV algorithm.
 o When a node receives such a table from a neighbor, it can update
its own information. As expected, each node also maintains a
routing table to determine the next hop required to reach any
destination.
Wireless routing protocol (WRP)
The wireless routing protocol is a proactive unicast routing protocol for
MANETs. It uses an enhanced version of the distance vector routing
protocol, which uses the Bellman - Ford algorithm to calculate paths.
For the wireless routing protocol (WRP) each node maintains 4 tables:
o Distance table
o Routing table
o Link cost table
o Message retransmission list (MRL) table
Each entry in the message retransmission list has a sequence number of
the update message, a retransmission counter, an acknowledgment
required flag vector with one entry per neighbor, and a list of updates
sent in the update message. When any node receives a hello message
from a new node, it adds the new node to its routing table and sends the
new node a copy of its routing table. A node must send a message to its
neighbors within a certain time to ensure connectivity.
Advantages
o The advantage of WRP is similar to DSDV. In addition, it has
faster convergence and adds fewer table updates.
Disadvantage
o The complexity of maintenance of multiple tables demands a large
amount of memory and greater processing power from nodes in the
MANET.
o Since it suffers from limited scalability therefore WRP is not
suitable for highly dynamic and for a very large ad hoc wireless
network.
2. Source initiated on -demand protocols
o Source - initiated on demand routing is reactive in nature, unlike

table driven routing. This type of protocols generates routes only

when a source demands it.
o In other words, when a source node requires a route to a

destination, the source initiates a route discovery process in the

network. This process finishes when a route to the destination has
been discovered or all possible routes have been examined without
any success.
o The discovered route is maintained by a route maintenance

procedure, until it is no longer desired or the destination becomes

inaccessible.
The source initiated on demand routing is categorized as follows:
Ad hoc on demand distance vector routing (AODV)
o AODV is a routing protocol for MANETs (mobile ad hoc

networks) and other wireless ad hoc networks.

o It is a reactive routing protocol; it means it establishes a route to a

destination only on demand.

o AODV routing is built over the DSDV algorithm. It is a significant

improvement over DSDV.

o The devices that are not on a particular path do not maintain

routing information, nor do they participate in the routing table

exchanges.
o When a source requires sending a message to a destination and

does not have a valid route to the latter, the source initiates a route
discovery process.
o Source sends a route request (RREQ) packet to all its neighbors,

the latter forward the request to all their neighbors, and so on, until
either the destination or an intermediate mobile (node) with a
"fresh enough" route to the destination is reached.
The above figure illustrates the propagation of the broadcast request
(RREQs) across the network. Since in DSDV, destination sequence
numbers are used to ensure that all routes are loop free and contain the
most recent route information. Each node has a unique sequence
number and a broadcast ID, which is incremented each time the node,
initiates RREQ.
The broadcast ID, together with the IP address of node, uniquely
identifies every RREQ.
Intermediate mobile reply only if they have a route to the destination
with a sequence number greater than or at least equal to that contained
in the RREQ. To optimize the route performance, intermediate nodes
record the address.

From the above figure, since RREP (route reply packet) travels back on
the reverse path, the nodes on this path set up their forward route entries
to point to the node from which RREP had just been received. These
forward route records indicate the active forward route. The RREP
continues traveling back along the reverse path till it reaches the
initiator of the route discovery. Thus, AODV can support only the use
of symmetric links.
Dynamic Source Routing (DSR)
o Dynamic source routing is an on-demand routing protocol which is

based on source routing.

o It is very similar to AODV in that it forms a route on demand when

a transmitting computer requests one. But, it uses source routing

instead of relying on the routing table at each intermediate device.
Many successive refinements have been made to dynamic source
routing.
o This protocol works in two main phases:

o Route discovery

o Route maintenance

o When a node has a message to send, it contacts to the route cache

to determine whether is it has a route to the destination. If an active

route to the destination exists, it is used to send a message.
o Otherwise a node initiates a route discovery by broadcasting a

route request packet. The route request stores the destination

address, the source address, and a unique identification number.
o Each device that receives the route request checks whether it has a

route to the destination. If it does not, it adds its own address to the
route record of the packet and then rebroadcasts the packet on its
outgoing links.
o To minimize the no. of broadcasts, a mobile rebroadcast a packet

only if it has not seen the packet before and its own address was
not already in the route record.

Temporally Ordered Routing Algorithm (TORA)

o TORA (Temporally Ordered Routing Algorithm) is a source
initiated on demand routing protocol.
o It was invented by Vincent Park and M. Scott Corson from
university of Maryland in 1997 for wireless ad hoc network.
o TORA is a highly adaptive, efficient, loop-free and scalable routing
protocol based on link reversal algorithm.
o The main objective of TORA is to limit message propagation in the
highly dynamic mobile computing environment. It means, it is designed
to reduce communication overhead by adapting local topological
changes in ad hoc network. Another main feature of TORA routing
protocol is the localization of control packets to a small region (set of
nodes) near the occurrence of a topological changes due to route break.
Hence, each node of the network required to contain its local routing
and topology information about adjacent nodes.
o TORA supports multiple routes to transmit data packet between
source and destination nodes of mobile ad hoc network. In short, TORA
exhibits multipath routing capability.

o The TORA's operation can be compared to that of water flowing

downhill toward a sink node through a grid of tubes that model the
routes in the real world network. The tube junctions represent the nodes,
the tube themselves represent the route links between the nodes, the
tube's water represents the packets flowing between nodes through the
route links toward the destination, as shown in the figure:
o Considering the data flow to be downhill, each node has a height
with respect to the destination node. The analogy also makes it easy to
correct routes in case of link failure or error.
o One of the biggest advantages of TORA is that it can operate
smoothly in a highly dynamic mobile environment. It provides multiple
paths for any source-destination pair. For this purpose, teach node must
maintain routing information about their one-hop neighbors.
o TORA works in three main phases:
o Route creation: Route creation from source to destination.
o Route maintenance: Maintenance of the route.
o Route erasure: Erasing of the route when the route is no longer
valid.
o TORA attempts to build a separate directed acyclic graph (DAG)
by each node to every destination. When a route to a particular
destination is required, the source node broadcasts a QUERY packet
containing the address of the destination. The route query propagates via
the network till it reaches either the destination or an intermediate node
containing the route to the destination.
o TORA contains a quintuple metric which consists of:
o Logical time of link failure.
o Unique ID of the node that defines the new reference level.
o A reflection indicator bit.
o A propagation ordering parameter.
o Unique ID of the node.
Hybrid Protocol - Zone Routing Protocols
Hybrid protocols attempt to take advantage of best of reactive and
proactive schemes. The basic idea behind such protocols is to initiate
route discovery on demand but at a limited search cost. One of the
popular hybrid protocols is zone routing protocol (ZRP).
Zone routing protocol (ZRP)
o Zone routing protocol is a hybrid of reactive and proactive
protocols. It combines the advantage of both reactive and proactive
schemes.
o ZRP was invented by Zygmunt Haas of Cornell University. Zone
routing protocol finds loop free routes to the destination.
o ZRP divides the network into zones of variable size; size of the
zone is determined radius of length ?, where the ? is the number of hops
or nodes to the perimeter of the zone and not the physical distance.
o In other words we can say that, the neighborhood of the local node
is called a routing zone. Specifically, a routing zone of the node is
defined as the set of nodes whose minimum distance in hops from the
node is no greater than the zone radius.
o A node maintains routes to all the destinations proactively in the
routing zone. It also maintains its zone radius, and the overlap from the
neighboring routing zones.
o To create a routing zone, the node must identify all its neighbors
first which are one hop away and can be reached directly.
o The Process of neighbor discovery is governed by the NDP
(Neighbor Discovery Protocol), a MAC level scheme. ZRP maintains
the routing zones through a proactive component called the intra-zone
routing protocol (IARP) and is implemented as a modified distance
vector scheme. Thus IARP is responsible for maintaining routes within
the routing zone.
o Another protocol called the inter-zone routing protocol (IERP)
which is responsible for maintaining and discovering the routes to nodes
beyond the routing zone.
o This type of process uses a query - response mechanism on-
demand basis. IERP is more efficient than standard flooding schemes.
o When a source node send data to a destination which is not in the
routing zone, the source initiates a route query packet.
o The latter identified by the tuple <source node ID, request
number>. This request is then broadcasted to all the nodes in the source
nodes periphery.
o When a node receives this query, it adds its own identification
number (ID) to the query. Thus the sequence of recorded nodes presents
a route from the current routing zone. Otherwise, if the destination is in
the current routing zone of the node, a route reply is sent back to the
source along the reverse from the accumulated record.
o A big advantage of this scheme is that a single route request can
result in multiple replies of route. The source can determine the quality
of these multiple routes based on such parameter as hop count or traffic
and choose the best route to be used.
_______
_________________________________

Some Open Research Topics in Mobile Communication

The differences between wired, fixed networks and wireless networks
open up various topics:
1. Interference: Radio transmission cannot be protected against
interference using shielding as this is done in coaxial cable or
shielded twisted pair. For example, electrical engines and lightning
because severe interference and result in higher loss rates for
transmitted data or higher bit error rates respectively.
2. Regulations and Spectrum: Frequencies have to be coordinated,
and unfortunately, only a very limited amount of frequencies are
available (due to political and technical reasons). A research topic
involves determining how to use available frequencies more
efficiently, e.g. by new modulation schemes or on demand
multiplexing. Further improvements are new air interfaces, power
aware ad-hoc networks, smart antennas, and SDR (Software
Defined Radios).
3. Low Bandwidth: Although bandwidths are continuously
increasing, transmission rates are still very low for wireless devices
compared to desktop systems. Local wireless system reach some
 Mbit/s while wide area systems only offer some 10 Kbit/s. 1 task
would involve adapting applications used with high-bandwidth
connections to this new environment so that the user can building.
Researchers look for efficient communication protocols with low
overhead.
4. High delays, large delay variation: The big variation in link
characteristics is a serious problem for communication protocols
used in today's internet (TCP/IP). In wireless systems, delays of
several seconds can make links vary asymmetrical (i.e., the links
offer different service quality depending on the direction to and the
wireless device). Applications must be tolerant and use-robust
protocols.
5. Lower security, simple to attack: Not only can portable devices
be robbed more easily, but the radio interface is also prone to the
dangers of eavesdropping. Wireless access must always include
authentication, encryption, and other security mechanisms which
must be efficient and simple to use.
6. Shared medium: Access of radio is always realized via a shared
medium. As it is impossible to have a separate wire between a
sender and each receiver, different competitors have to ?fight' for
the medium. Although different medium access schemes have been
developed, several questions are still unanswered as example how
to provide quality of service efficiently with different combinations
of access, coding, and multiplexing schemes.
7. Ad-hoc networking: Wireless and mobile computing permits for
spontaneous several new questions for research - routing on the
networking and application layer, service discovery, network
scalability, reliability, and stability etc.