2.1. Proactive Routing Protocols

These protocols attempt to maintain consistent up-to-date routing information from each node to every other node in the network. The routing information is usually kept in tables, which are updated as the network topology changes. The two popular proactive routing protocols are (a) Destination Sequenced Distance Vector (DSDV) Routing [3] and (b) Optimized Link State Routing (OLSR) [4].

(a) Destination Sequenced Distance Vector (DSDV)

The DSDV algorithm [3] is modification of Distributed Bellman-Ford algorithm, which guarantees loop-free routes. It provides a single path to destination that is selected using the distance vector shortest path routing algorithm. Each node maintains a routing table that stores all available destinations, and the number of hops to each destination. Each routing table entry is also tagged with a destination sequence number that is created by the destination itself. The use of sequence numbers ensures utilization of most recent routing information and avoids routing loop formation. Each node periodically forwards the routing table to its neighbours. Two types of update packets are transmitted in DSDV protocol. These are referred to as a “full dump” and “incremental” packets. The full dump packets carry all the available routing information and the incremental packets carry only the information changed since the last full dump. The incremental update packets are sent more frequently than the full dump packets.

DSDV introduces large amount of overhead to the network due to the requirement of the periodic update messages. Therefore the protocol does not scale in large network since large portion of network bandwidth is used in updating procedures.

(b) Optimized Link State Routing (OLSR)

OLSR [4] is a point-to-point routing protocol based on the traditional link state routing algorithm [5]. In this protocol, each node maintains topology information about the network by periodically exchanging link state messages. OLSR minimizes the size of control message and the number of rebroadcast nodes during each route update by employing multipoint relaying (MPR) strategy. To do this, during each topology update, each node in the network selects a set of neighbouring nodes to retransmit its packets. This set of nodes is called the multipoint relay set (MPRS) of that node. Any node that is not in this set can read and process each packet but cannot retransmit.

To select the MPRS, each node periodically broadcasts a list of its one-hop neighbours using “Hello” messages. From the list of nodes in the “Hello” messages, each node selects a subset of one-hop neighbours, which covers all of its two hop neighbours. Each node determines an optimal route (in terms of hops) to every known destination using the topology information (from the topology table and neighbouring table).

2.2. Reactive Protocols

In these protocols, the routing information is maintained only for active routes. That is, the routes are determined and maintained only for nodes that require to send data to a particular destination. Route discovery usually occurs by flooding a route request packet throughout the network. Route reply is sent back if the destination itself or node with route to the destination is reached. The reactive protocols are classified as source routing where each data packet carries the source to destination addresses and hopby- hop routing where each data packet only carries the destination address and next hop address. The two main reactive protocols are (a) Dynamic Source Routing (DSR) [6] and (b) Ad hoc On-Demand Distance Vector Routing (AODV) [7].

(a) Dynamic Source Routing (DSR)

DSR protocol [6] requires each packet to carry the full address from source to destination. This protocol has two phases namely Route Discovery and Route Maintenance.

Route Discovery phase

When a source node desires a route to a destination for which it does not already have a route in its cache, it broadcasts a route request packet (RREQ) across the network using flooding. Each intermediate node appends its own identifier when forwarding RREQ, along with the address of the original initiator of the request and the destination of the request. Each RREQ packet accumulates a record of the sequence of hops taken by the route request packet as it propagates through the network. The destination on receiving the first RREQ sends a Route Reply (RREP) packet. The RREP packet is sent on a route obtained by reversing the route present in the received RREQ packet.

Route Maintenance phase

A node A detects transmission of corrupted or lost packets by means of passive acknowledgements i.e.