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:

· Modeling of the topology,

· Selection of routers,

· Initiation of a route request,

· 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:

· Since centralized routing in a dynamic and even for small networks is impossible therefore routing computation must be distributed.

· Route computation should not add many more nodes.

· If any host demands for the route, they must have quick access.

· Maintenance of a global state should not involve in the route computation.

· 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.

· Since broadcast can be time consuming for MANETs, it must be avoided as much as possible.

· 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:

· Requires more amounts of data for maintaining routing information.

· 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:

· No large overhead for global routing table maintenance as in proactive protocols.

· 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:

· Latency time is high in route finding

· 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

• 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.
• They are proactive in nature so that the routing information is always consistent and up to date.
• 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

• Destination sequenced distance vector routing (DSDV) is a table driven routing protocol for MANET based on Bellman-Ford algorithm.
• 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.
• 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.
• Each entry in the table contains a sequence number assigned by the destination node.
• The sequence numbers allow the node to distinguish stale routes from new ones, and help avoid formation of routing loops.
• A new route broadcast contains:
• The destination address.
• The number of hops required to reach the destination.
• The sequence number of the information received about the destination and a new sequence number unique to the broadcast.
• 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 Hop	No. of Hops	Sequence no.	Install 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

• 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

• 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.
• This algorithm is not suitable for highly dynamic networks.

Cluster Head gateway switch Routing

• 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.
• 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.
• 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.
• 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.

• 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.
• 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:

• Distance table
• Routing table
• Link cost table
• 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

• The advantage of WRP is similar to DSDV. In addition, it has faster convergence and adds fewer table updates.

Disadvantage

• The complexity of maintenance of multiple tables demands a large amount of memory and greater processing power from nodes in the MANET.
• 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

• 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.
• 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.
• 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)

• AODV is a routing protocol for MANETs (mobile ad hoc networks) and other wireless ad hoc networks.
• It is a reactive routing protocol; it means it establishes a route to a destination only on demand.
• AODV routing is built over the DSDV algorithm. It is a significant improvement over DSDV.
• The devices that are not on a particular path do not maintain routing information, nor do they participate in the routing table exchanges.
• 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.
• 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)

• Dynamic source routing is an on-demand routing protocol which is based on source routing.
• 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.
• This protocol works in two main phases:
• Route discovery
• Route maintenance
• 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.
• 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.
• 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.
• To minimize the no. of broadcasts, a mobile rebroadcasts a packet only if it has not seen the packet before and its own address was not already in the route record.