Performance evaluation of AODV, DSDV, OLSR routing protocols using NS-3 simulator

Published Online July 2018 in MECS

Wireless ad hoc network is a self-organised, selfconfigured collection of nodes that communicate over wireless links without help of any base station or an access point nodes work as both host and specialized router. The infrastructure less interconnection of the nodes through routers can be arranged dynamically in Ad-Hoc network. There are lot of work has been completed in improvement of routing protocols in Ad-Hoc network mainly in WSNs, MANETs, VANETs and WMNs[14].In Ad-Hoc network routing protocol should consider various function like packet routing ,channel assessment, transmission scheduling ,maintaining network connectivity and determination of network topology. Primary goal behind the development of routing are minimum processing overhead ,multi-hop routing capability ,dynamic topology maintenance ,loop prevention and minimal control overhead [13].In Ad-Hoc routing protocol performance depends upon the various factor like node mobility which leads to link failure several time ,quality of service(QOS) support, network size and traffic intensity. The performance sometimes also depends upon the behaviour of network as well as type of work in that environment [12].Ad-hoc network can be deployed quickly with minimal overhead. This nature makes suitable for emergency use such as in earthquake, in disaster areas or where building infrastructure is expansible in conference room where people need to share the information. Ad-hoc network is also as option for connectivity to internet by co-operation of people. Choosing a suitable protocol is very important to deploy an ad-hoc network. The main objective of this paper is simulation analysis of routing protocols to observe and evaluate various factors without using resources and with minimum effort that may influence the performance of network.

We emphasized on analysis of the performance matrices including jitter, end to end delay, packet loss and packet delivery fraction of multi-hop network by Destination Sequenced Distance Vector (DSDV), Ad-hoc On Demand Distance Vector (AODV) and Optimized Link State Routing (OLSR) routing protocol by using NS-3 simulator. Simulation analyses are also useful for understanding behaviour of protocols and to know the weakness for further improvements.

Remaining part of this paper is organised as follows: Section-2 gives related work, section-3 gives overview of Ad-Hoc routing protocols, section-4 gives simulation environment and section-5 gives performance analysis of protocols. Lastly conclusion and future work follows in section-6.

• II.    Related Work

Many researchers have worked on performance modelling and analysis of routing protocols. In [5] Broch and Maltz have analysed a performance analysis of ad hoc routing protocols using ns-2 with more emphasis on physical layer and MAC layer issues. In [6] Mehran Abolhasan Tadeusz Wysocki, Eryk Dutkiewicz have analysed various parameter and protocol like convergence time , memory overhead, control overhead of proactive protocols, time complexity; communication complexity; route discovery; route maintenance of reactive routing protocols and hybrid protocols . In [7] packet delivery fraction, average end to end delay, packet loss, routing overhead of AODV and DSR protocol are evaluated using by ns-2 simulator. In [8] comparing AODV and OLSR routing protocols .In [12] evaluation parameter’s for deferent network size are control overhead, packet delivery ratio, end to end delay are throughput at different pause time are discussed. In [13] different routing protocols are classified which are based on their reactive, proactive and hybrid nature.In [17] comparing the AODV MIMC & AODV with simulation results.

• III.    Overview of Ad-Hoc Routing Protocol

In ad hoc network each node has to perform routing function by using multiple hopes to deliver data. Routing in ad hoc network can be classified in two ways.

Proactive routing protocols: - Proactive routing protocols (table driven) maintains up to date information about all nodes which are in the network and frequently updates its routing tables.

Example - DSDV, OLSR.

Reactive routing protocols: - Reactive routing protocols (on demand) does not maintain information about all nodes in advance. It creates route from source node to destination when required.

Example-AODV, DSR.

• A.    Destination Sequenced Distance Vector (DSDV)

DSDV [1 ] is a proactive routing protocol which requires to have a routing table. At each mobile node routing table keeps the information about all nodes which are in the network. Its column entries are list of destinations, next hop route, sequence number generated by destination which guarantees a loop free path.

Consistency of routing table is maintained in two ways to share the information to its neighbour. Information sharing to routing node is handled by help of two table like full dump table and incremental table. In full dump table, node share entire table to its neighbour periodically. Between two full dump a node exchange incremental dump takes place, when a small changes is occurred in network such as sequence number or route change.

• a) . Routing Table in DSDV

Network of 7 nodes are given in figure 1. The routing table of node A is a list of information about all nodes is illustrated in table 1.

Table 1. Routing Table of DSDV

Destination	Next Hop	Hop Count	Sequence Number
B	B	1	S102_B
C	C	1	S202_C
D	D	1	S302_D
E	B	2	S402_E
F	D	3	S502_F
G	D	2	S602_G

Fig.1. Network of 7 Nodes

• b) . Looping Problem in Routing Information Protocol (RIP)

The problem that is addressed by DSDV is a looping problem [15]. We describe here how a loop is formed in RIP, and how DSDV prevents loop formation. To demonstrate this we take three nodes which are shown in figure 2.

Loops creation in RIP:

• •    If node E is not reachable from B, it would be better if B sends route update before A with hop count to metric ∞.

• •    But before node B, A sends its routing table to B, B think that there is route to node E from node A and updates its routing with hop count 2.

• •    After updating routing table by node B it sends update to A and it also updates its routing table.

  

Fig.2. Looping Problem in Three Nodes

Table 2. Routing Table of RIP

A’s Routing table before link failure			B’s Routing table before link failure
Destination	Next Hop	Metric	Destination	Next Hop	Metric
E	B	2	E	B	1
A’s routing table after link failure			B’s Routing after before link failure
Destination	Next Hop	Metric	Destination	Next Hop	Metric
E	B	2	E	B	∞

A’s Routing table with hop count 2- first update			B’s Routing table with hop count 3- first update
Destination	Next Hop	Metric	Destination	Next Hop	Metric
E	B	2	E	B	3
A’s Routing table with hop count 4- Second update			B’s Routing table with hop count 5- second update
Destination	Next Hop	Metric	Destination	Next Hop	Metric
E	B	4	E	B	5

..A’s Routing table with hop count in loop			B’s Routing table with hop count in loop
Destination	Next Hop	Metric	Destination	Next Hop	Metric
E	B	∞	E	B	∞

• c)    Loop prevention in DSDV

Routing table of node A and B in DSDV routing protocol is given in table 3. DSDV adds a sequence number to prevent loop. A sequence number is an even number generated by destination, whenever a change is occurred. Sequence number is incremented by one from source node which is illustrated below.

Table 3. Routing Table

A’s routing table before link failure				B’s routing table before link failure
Destin ation	Next Hop	Me tric	Sequen ce No.	Des tina tion	Nex t Hop	Met ric	Sequence No.
E	B	2	S402_ E	E	B	1	S402_E
A’s routing table after link failure				B’s routing after before link failure
Destin ation	Next Hop	Me tric	Sequen ce No.	Des tina tion	Next Hop	Met ric	Sequence No.
E	B	2	S402_ E	E	B	∞	S403_E

In table after link failure of node A and B, node B updates its routing table by setting hop count to ∞ and it increments sequence number by one i.e. S403_E, and when an update is sent by node A before updating routing table B checks sequence number if sequence number is greater than its updates otherwise discard it. In above case B checks sequence number of A (S402_E) > sequence number of B (S403_E), which is not true so node B does not update its routing table on the basis of information provided by node and loop is prevented.

• B.    Ad-hoc On Demand Distance Vector (AODV) –

AODV [2] is a reactive routing protocol, which is combination of DSDV [1] and DSR [3] (Dynamic Source Routing) routing protocols. AODV hires the concept of destination sequence number from DSDV as well as route discovery and route maintenance concept from DSR. AODV protocol does not keep information about all nodes in its routing table in advance like its counterpart’s proactive routing protocols. In AODV, node creates a route to destination whenever necessary.

AODV Protocol Functioning –

• a) . Route Discovery

In figure 3 node A needs to communicate with G, A initiates a route discovery process by flooding Route Request (RREQ) packets in the entire network which contains source address, source sequence number, broadcast id, destination address, destination sequence number, and hop count etc. A RREQ message is uniquely identified by the pair like sequence number, Broadcast id. If an intermediate node receives RREQ message and has a route to destination it replies with a unicast packet RREP (Route Reply) which contains the fields, destination IP, destination sequence number, originator IP address, lifetime of packet and hop count otherwise it forwards to other nodes connected to it and sets a reverse route entry for future use. If RREQ packet is reached at destination node G from A, then node G answer with RREP which is illustrated in figure 4.

Fig.3. Route Request in AODV Protocol

Fig.4. Route Reply in AODV Protocol

• b) . Route Maintenance

In route maintenance phase, figure shows that, there is route from node A to node G for data transfer. If any change occurred like link failure during the data transfer then link failure notify by its intermediate node to its upstream neighbours by sending a RRER (Route Error) message. RRER message contains destination count, unreachable destination IP address and unreachable destination sequence number. RRER is a unicast message to maintain the connectivity to neighbour node which uses hello massage (RREP packet with TTL (time to live) =1 and is transmitted by nodes periodically to the neighbours).Route error is illustrated in figure 5.

Fig.5. Route Error in AODV

• C.    Optimized Link State Routing (OLSR)

Optimized Link State Routing (OLSR) [4] is designed for ad hoc network which is optimized version of traditional link state routing protocol. OLSR is a proactive routing protocol i.e. it maintains information about all nodes in a table, in which routes are immediately available when they are needed. Protocol uses TC (Topology Control) messages which contain the following fields like advertised neighbour sequence number and advertised neighbour main address. Topology control are flooded by neighbours of a node in entire network to exchange topology information. Flooding process in network imposes heavy computational burden on network to overcome this problem, OLSR uses MPR (Multipoint Relays) nodes which are one hop neighbours that covers all two hop neighbours. Only MPR nodes are allowed to broadcast TC messages throughout the network. The connectivity to neighbours is maintained by emitting HELLO messages at regular interval which contains the following field like hello time interval, willingness of node, link code, size of link message and neighbour interface address.

OLSR makes use of three types of tables like neighbour table 4, topology table 5 and routing table 6, which is illustrated below. Neighbour table contains the entries of list of neighbours and state of the link. Topology table contains the entries of the field like address of destination node, address of last hop to destination, MPR selector set sequence number and holding time. Topology table if holding time expires then all the entries in the row will be marked as invalid.

• a). Protocol Functioning

In figure 6 network of 14 nodes are given. A selects C as MPR node that covers all two hop neighbours E, F and G. Similarly N selects L as MPR node, which covers two hop neighbours H,I,J nodes.

Working of OLSR protocol is very complicated and we describe it briefly.

If nodes A and N needs to communicate each other, both require four steps to calculate routing table.

Step 1: Node A and N checks its one hop and two hop neighbours whether they contain bidirectional or unidirectional links by using regularly emitting HELLO Messages and builds one hop and two hop neighbour tables.

Step 2: After checking link property of nodes A and N make C, L as MPR which are one hop neighbours and have bidirectional links.

Step 3: If node A and N declare C, L as MPR node both flood TC (Topology Control) message in entire network upon receiving TC message A and N update topology table.

Step 4: On the basis of topology and neighbour table node A calculates routing table after calculating routing table, both nodes are able to communicate each other.

Table 4. Neighbour Table

One Hop Neighbour Table of A		One Hop Neighbour Table of N
Neighbour	State Of Link	Neighbour	State Of Link
B	Bidirectional	K	Bidirectional
C	MPR Node	L	MPR Node
B	Bidirectional	M	Bidirectional
Two Hop Neighbour table of A		Two Hop Neighbour Table of N
Neighbour	Access Through	Neighbour	Access Through
E	C	H	L
F	C	I	L
G	C	J	L

Table 5. Topology Table

An Instance of Topology Table of node A is given in Table				An Instance of Topology Table of Node N is given in Table
Destination	Last hop to that destination	MPR selector sequence number	Holding time	Destination	Last hop to that destination	MPR selector sequence number	Holding time
N	L	N_102	2 second	A	C	A_602	2 second

Table 6. Routing Table

An Instance of Routing Table of Node A			An Instance of Routing Table of Node N
Destination	Next Hop	Distance	Destination	Next Hop	Distance
N	C	5	A	L	5

• IV.    Simulation Enviorment

To compare the performance matrices of ad-hoc routing protocols in 50% of source and destination node respectively, we have consider the NS-3[16] simulation environment using with their respective parameter.

Table 7. Simulation Environment Table

Simulation Parameters	Value
Network Simulator	Network Simulator Version 3(ns3)
Area Size	600*600 meter square
Protocols	DSDV, AODV, OLSR
Total Simulation Time	120 seconds
Propagation Delay Model	Constant Speed Delay Model
Propagation Loss Model	Friss Propagation Loss Model
Physical Layer	DSSS 11Mbps
MAC layer	802.11b
Node Pause Time	10 second
Node Speed	10 meter/second
Packet Size	64 Byte
Application Data Rate	2048 bps
Mobility Model	Random Waypoint Mobility Model
Traffic Model	CBR (Constant Bit Rate)

• V.    Performance Analysis

  We have taken the performance metric from RFC 2501[9] [10] in which a number of quantitative and qualitative metrics are defined. In RFC- 5148[11] jitter metrics issues are explained.

• A.    End to End Delay

End to End Delay is defined as time (T) taken by a packet to travel from application layer of source node to application layer of destination node.

End to End Delay = (Time at reception of packet) - (Time at generation of packet). (1)

End to end delay has four components, transmission delay, propagation delay, processing delay and queuing delay. In figure[7] end to end delay of all three protocols are same for 20 nodes, but when number of nodes are increases then there is increase in end to end delay in all three protocols. AODV exhibits less delay compare to DSDV because it does not have flood control packets like DSDV so there are less processing delay and queuing delay for AODV.

LSR uses MPR nodes for selected flooding of control packets in network, so less number of control traffic is produced by OLSR in data delivery. In OLSR packets experienced less queuing delay and processing delay at nodes from the above simulation. Therefore OLSR is best routing protocol compare to AODV and DSDV in terms of end to end delay.

Fig.7. No of nodes vs. End to End Delay

• B.    Jitter -

• Jitter is defined as the difference in delay between two successive packets related to the same flow.

Jitter = (Delay (P n )-Delay (P n-1 ) .          (2)

Variation in delay (Jitter) is occurred when different delays are experienced by packets related to the flow, it may experience that when a packet arrives at input queue it wait for some time and after that node forwards the packet through outgoing queue at different delays. While ingoing/outgoing packets from in/out queue belong to same flow. In figure [8] AODV exhibits lower jitter than DSDV. So OLSR has lowest compare to both AODV and DSDV, jitter can also be interpreted as mean deviation of delay in packet arrival at receiver compared to the sender, so if there is more end to end delay in the network the possibility of jitter is increased.

Fig.8. No of Nodes vs. Jitter

• C.    Packet Loss-

• Packet loss is the number of packets fail to arrive at destination across network.

Packet Loss = (Numbers of Packets Sent)-(Number of

Packet Received).                                   (3)

Figure shows that packet loss is equivalent in AODV

and DSDV distance vector protocol. This type of protocols does not have global knowledge of whole topology. In mobile node communication if link failure occur then, due to the limitation in distance vector routing (It does not contain any global information about network topology) it leads to packet loss.

OLSR exhibits minimum packet loss because it has global knowledge of topology. If a change is occurred in network it updates it routing table and then attempts to send packets so it has less number of packet loss compare to AODV and DSDV.

Fig.9. No of nodes vs. Packet Loss

• D.    Packet Delivery Fraction (PDF):-

• Packet delivery fraction is the ratio of packets received by destinations and sent by sources across the network.

PDF = (Total Number of Packets Received)/ (Total Number of Packets Sent).                            (4)

Fig.10. No of nodes vs. Packet Delivery Fraction

• VI. Conclusion and Future Work

In this paper, for the performance analysis we used 600* 600 sq.m. size network .We evaluated four performance matrices i.e. End to end delay, jitter, packet loss and packet delivery fraction ratio with different no of nodes or different network size. From simulation results we conclude that OLSR is best routing protocol in terms of all parameters which have been chosen for simulation. OLSR protocol gives the better result for high mobility environment. During the simulation we observed that OLSR protocol is very complicated. Similarly for small network size DSDV is very effective and simple but when network become larger, then the performance of DSDV protocol degrades. AODV is good for medium size network.

In my upcoming paper our main focus on Quality of Service (QoS) of routing protocols, where several researchers are working on this issue. In future we have planned to work on QoS metrics for jitter control, guarantees end to end delay and ensuring less number of packet loss, and imposing security model on ad hoc routing protocols.