Performance Analysis of DHT Based Multi-Path Routing Protocol with Single-Path Routing Protocols in MANETS

Performance Analysis of DHT Based Multi-Path Routing Protocol with Single-Path Routing Protocols in MANETS

[1,2]Jaspreet Singh, Dr. Sandeep Singh Kang

[1,2]Department of CSE Chandigarh Engineering College, Landran, Mohali, Punjab, India

ABSTRACT

A Mobile Ad-hhoc Network(MANET) is a dynamic wireless network that can be formed without the need for any pre- existing infrastructure in which each node can act as a router. One of the main challenges of MANET is the design of robust routing algorithm that adopt to the frequent and randomly changing network topology. A variety of routing protocols have been proposed and several of them have been extensively simulated or implemented as well. In this paper,we compare and evaluate the performance of two types of on demand routing protocols- Ad-hoc on-demand Distance Vector (AODV) routing protocol, which is unipath and Ad-hoc on-demand Multipath Distance Vector(AOMDV) routing protocol and MDART (Multipath Dynamic Address Routing) which is DHT (Distributed Hash Table) based multipath protocol. In this paper we note that on comparing the performance of AODV, AOMDV and MDART, MDART incurs a better efficiency when it comes to throughput, End-to-End Delay, Normalization Overhead.

Keywords:MANET,AOMDV,MDART,AOD V,CBR,NS2

I. INTRODUCTION

To study and analyze various Routing Protocols named AODV and AOMDV and MDART (Multi-Path Dynamic Addressing Routing) in ns-2. To analyze the improved tolerance of these Protocols against mobility as well as power failures.To perform comparative analysis for performance ofRouting protocols based on Energy consumption, PDR, Throughput and Jitter. The most popular on-demand routing protocol, Adhoc On-demand Multipath Distance Vector (AOMDV) routing protocol

[1] is an improvement of Ad-hoc On- demand Routing Protocol (AODV). AOMDV discovers multiple paths between a source and destination to provide efficient fault tolerance by providing quicker and more efficient recovery from route failures in a dynamic network. As AOMDV discovering multiple paths in a single route discovery attempt, new route needs to be discovered only when all paths fail. This reduces not merely the route discovery latency but the routing overheads also. AODV is a reactive and a single path routing protocol. It allows users to find and maintain routes to other users in the network whenever such routes are needed. The adhoc on demand distance vector routing protocol provides unicast, broadcast and multicast communications in adhoc networks. AODV

initiates route discovery whenever a route is needed by the source node or whenever a node wishes to join a multicast group. Routes are maintained as long as they are needed by the source node or as long as themulticast group exists and routes are always loop freethrough the use of sequence numbers [2]. A multipath enhancement to DART [3] was proposed in [4] calledAugmented Tree based Routing (ATR), but in ATR the DHT system is replaced by a global lookup table which is available to all the nodes, which results in a great impact on the address discovery, which is a key process of the whole routing protocol. Among the DHT based Routing Protocols, M-DART is an enhancement of shortest path routing protocol known as Dynamic Address Routing (DART) [3].

M-DART discovers and stores multiple paths to the destination in the routing table. The remainder of this paper is organized as follows. Section II discusses related work of different protocols. SectionIII discusses an overview of dynamic addressing and DHT of routing protocols. Section IV and V discusses proposed scheme and the simulation results of the two routing protocols with different parameters. Finally, we summarize and conclude ourpaper in section VI.

1. Ad-hoc on-Demand Distance Vector Routing(AODV)

   AODV is a reactive protocol that discovers routes on an as needed basis using a route discovery mechanism. It uses traditional routing tables with one entry per destination. Without using source routing, AODV relies on its routing table entries to propagate an RREP (Route Reply) back to the source and

   also to route data packets to the destination. AODV uses sequencenumbers maintained at eachdestination to determine freshness of routing information andto prevent routing loops [1]. All routing packets carry these sequencenumbers. AODV maintains timer- based states in each node, for utilization of individual routing table entries, whereby older unused entries are removed from the table. Predecessor node sets are maintained for each routing table entry, indicating the neighboring nodes sets which use that entry to route packets. These nodes are notified with RERR (Route Error) packets when the next-hop link breaks. This packet gets forwarded by each predecessor node to its predecessors, effectively erasing all routes using the broken link. Route error propagation in AODV can be visualized conceptually as a tree whose root is the node at the point of failure and all sources using the failed link as the leaves [1]. The advantages of AODV are that less memory space is required as information of only active routes are maintained, in turn increasing the performance, while the disadvantage is that this protocol is not scalable and in large networks it does not perform well and does not support asymmetric links.

2. Ad-hoc On-demand Multipath Distance Vector Routing (AOMDV)

   To eliminate the occurrence of frequent link failures and route breaks in highly dynamic ad-hoc networks, AOMDV has been developed from aunipath path on Demand routing protocol AODV. The AOMDV [2,3] protocol finds multiple paths and this involves two stages which are as follows: i)

   A route update rule establishesand maintains multiple loop-free paths at each node, andii) A distributed protocol finds link-disjoint paths. The AOMDV protocol finds node- disjoint or link-disjoint routes between source and destination. Link failures may occur because of node mobility, node failures, congestion in traffic, packet collisions, and so on. For finding node- disjoint routes, each node does not immediately reject duplicate RREQs. A node-disjoint path is obtained by each RREQ, arriving from different neighbor of the source because nodes cannot broadcast duplicate RREQs. Any two RREQs arriving at an intermediate node through a different neighbour of the source could not have traversed the same node. To get multiple link-disjoint routes, the destination sends RREP to duplicate RREQs regardless of their first hop. For ensuring link-disjointness in the first hop of the RREP, the destination only replies to RREQs arriving through unique neighbours. The RREPs follow the reverse paths, which are node-disjoint and thus link-disjoint after the first hop. Each RREP intersects at an intermediate node and also takes a different reverse path to the source to ensure link-disjointness.

3. Multipath Dynamic Address Routing (MDART)

   The protocol, namely the multi-path dynamic address routing (M-DART), is based on a prominent DHT-based shortest- path routing protocol known as DART [4,5]. M-DART extends the DART protocol to discover multiple routes between the source and the destination. In such a way, M- DART is able to improve the tolerance of a

   tree-based address space against mobility as well as channel impairments. Moreover, the multi-path feature also improves the performances in case of static topologies thanks to the route diversity. M-DART has two novel aspects compared to other multi- path routing protocols [6–7]. First, the redundant routes discovered by M- DART are guaranteed to be communication-free and coordination-free, i.e., their discovering and announcing though the network does not require any additional communication or coordination overhead. Second, M-DART discovers all the available redundant paths between source and destination, not just a limited number.

4. An Overview of Dynamic Addessing and DHT in the terms of routing protocols Dynamic Addressing [11] is used to separates the address of routing protocols and the identity of a node.The address of node is dynamic which changes the movement of node and location of nodes.

5.1 MDART: The multi-path dynamic Address routing (MDART) is proposed by J. Eriksson,

1. Faloutsos and S. Krishnamurthywhich is extends version of DART which is a shortest- path routing protocol to discover multiple routes between the source and the destination. M- DART is improves the tolerance of a tree-based address space and channel impairments. M- DART containing two novel aspects, first, the Redundant Routes are guaranteed the communication-free and coordination-free which are be used to discover thatany network does not require any additional communication or coordination overhead. Second, all the available redundant paths between source and destination do not contained limited number.The Multi-Path Dynamic Addressing Routing (M- DART) is a routing protocol for ad hoc networks

   are used for improves the performances of static topologies as well as route diversity.

   1. Address space: The address space of MDART can be represented as a binary tree of three levels. A binary tree contained in that way every vertex has zero or two children and all leaves are at the samelevel (fig 1).In the binary tree structure each leaf is containing with a network address, and the set of network addresses having inner vertex of level k which is called a level-k sub tree. For example, according to Figure 1, the vertex with the label 01z is a level-1 subtree and represents the leaves 010 and 011. Let us define level-k sibling of a leaf as the level-k subtree which shares the same parent with the level-k subtree the leaf belongs to. Therefore, each address has l siblings at all and each other address belongs to one and only one of these siblings. Referring to the previous example, the vertex with the label1zz is the level-2 sibling of the address 000, and the address 100 belongs only to this sibling.

      Figure 1: Address Space

   2. Route discovery and packet forwarding

   Each node maintains a routing table in figure 3 having one for each sibling and the kth section stores the path toward a node belonging to the level-k sibling. Every section stores five fields: the sibling ID, the next hop, the Route Cost, the network IDand the Route log. The table has three sections:the first stores the best route containing the node 001, the second toward

   anode containing to the sibling 01Zand the lasttoward nodes containing to the sibling.

   Figure 2 :packet forwarding

   1. AOMDV

      AOMDV [12], [11] is a multi-path routing protocol. It isan extension to AODV and also provides two mainservices i.e. route discovery and maintenance. UnlikeAODV, every RREP is being considered by thesource node and thus multiple paths can bediscovered in one route discovery. Being the hop-by-hoprouting protocol, the intermediate node canmaintain multiple path entries in their respectiverouting table. hop. To discover distinct paths, AOMDV suppressesduplicate route requests at intermediatenodes. Such suppression comes in two differentvariations, resulting in either node or link disjoint.AOMDV can be configured to either discover the link(no common link between any given pair of nodes) ornode (in addition to link disjoint, commonintermediate nodes are also excluded between anygiven pair of nodes) disjoints paths.Disjoint alternate paths are a good choice thanOverlapping alternate paths, as the probability of theirinterrelated and concurrent failure is smaller. Finding a disjoint path is quitestraightforward in source routing but hop-by-hop routing i.e. AOMDV is consideredmore efficient in

      terms of creating less overheadNumber of paths in any given source and destinationis directly proportional to the number of nodes inentire network. AOMDV works more efficiently indense and heavy networks.

      1. Node Disjoint (b)Link Disjoint Figure 3 AOMDV Multi-path

   4. Proposed Work

   We proposed a new protocol to enhance the performance of MANETs which is based on new paradigm .We will implement a new DHT based multipath routing protocol in ns-

   2. Our main objective is to check its performance against scalability and power failures. In addition to this we will implement AODV and AOMDV and M- DART routing protocol in ns-2.AODV has single path reactive protocol of MANETs where as M-DART and AOMDV is multipath reactive protocol of MANETs. We give a contribution toward such an approach by focousing our attention on the problem of implementing a DHT-based routing protocol whose performance are competitive with those of other widely adopted protocols.The proposed protocol,namely the multipath dynamic address routing(M-DART),is based on prominent DHT-based shortest path routing protocol known as DART. M-DART extends the DART protocol to discover multiple routes between the source and destination. In this way,M-DART is able to

   improve the tolerance of tree based address space against mobility. Moreover, the multipath features also improve the overall performance. Here we compare two multipath routing protocols M-DART and AOMDVand one single path routing protocol AODV to analyze the tolerance against mobility as well as power failures and parameters such as PDR(packet delivery ratio),Average Throughput, Average Jitter,and Energy Consumption.There are many research papers on routing protocols in wireless sensor network and all are used for evaluating performance of different parameters in different scenario. Researchers specify the performance for different parameters and which one is best for the case of Wireless Sensor Network. In comparison of AODV, DSR and Hybrid the Average end-to-end delay of WBAODV is very high. While in comparison of DSR and WBAODV routing protocols, WBAODV performed better than DSR in terms of throughput. As compare to WBAODV and DSR,Hybrid protocol perform better which has high Throughput and less End To End delay and high pdf.

   1. The Simulation Results

      We will implement three protocols named MDART and DART (Multi-Path Dynamic Addressing Routing) in ns-2 and evaluate their performance w.r.t. PDR, throughput, jitter and Energy Consumption. We will perform comparative analysis of these protocols in different mobility scenarios.

      Performance Metrics to be used:

      Average Throughput, End-to-End Delay, Normalization Overhead,

      1. Average Throughput:

         200

         150

         100

         50

         0

         th- MDART

         th- AOMDV

         th- AODV

   2. CONCLUSION

   This paper proposes the M-DART protocol, AOMDV protocol and AODV protocol. M- DART is used for shortest-path routing protocol and it exploit all paths without introducingany communication or coordination overhead with respectto the original protocol.Simulation results and performance comparisons withexisting protocols substantiate the effectiveness of

   0 100 200 300 400

   Figure 3 Throughput Vs Number Of Nodes

   1. End to End Delay

      Fig.5EndToEndDelayVsNumberOfNodes

      Figure 5

   2. Normalized Routing Overhead

Figure 6

MDARTfor scalable networks with different workloads andenvironmental conditions in presence of moderate mobility.In particular, M-DART is able to perform best or comparablewith the best protocol for each considered scenario.Several additional issues related to the design and evaluationof the M-DART protocol requires further investigation.First, the protocol can be improved by resorting to moreeffective multi-path schemes. Second, we need to validatethe obtained results with experimental results, at least forthe scenarios that do not involve large networks, and tocarefully study the interaction between timeout settingsand M-DART performances. Third, evaluating the performancesof M- DART for P2P applications is another issuefor future work. Finally, it will be useful to see if the opportunisticapproach applied to the dynamic addressing can assure satisfactory performances in scenarios characterizedby high mobility.

REFERENCES

[1]. M. Z. Oo , M. Othman , Performance Comparisons ofAOMDV and OLSR Routing Protocols for Mobile Ad HocNetwork, Second International Conference on ComputerEngineering and Applications, 2010.

[2]. Elizabeth M.Royer, Charles E. Perkins An Implementationstudy of AODV routing protocol IEEE, 0-7803-6596-8/00,2000.

[3]. 11. J. Eriksson, M. Faloutsos and S. Krishnamurthy.DART: Dynamic Address RouTing for Scalable Ad Hocand Mesh Networks in IEEE- ACM Transactions on Networking, vol. 15, no. 1, April 2007, pp.

119-132.

[4]. Caleffi, M., Ferraiuolo, G., and Paura,

L. Augmented Treebased Routing Protocol for Scalable Ad Hoc Networks, inMHWMN '07: Proceedings of the Third IEEE InternationalWorkshop on Heterogeneous Multi-Hop Wireless and Mobile Networks, 2007.

1. Xu Yi, Cui Mei, Yang Wei, Xan Yin, A Node-disjoin Multipath Routing in Mobile Ad hoc Networks, IEEE,2011.

2. Fubao Yang, Baolin Sun, Ad hoc On- demand Distance Vector Multipath Routing Protocol with Path Selection Entropy,IEEE, 2011.

3. Phu Hung Le, Guy Pujolle, Thi-Mai- Trang Nguyen, An Interference-aware multi-path routing protocol for Mobile Ad hoc Network,International Conference on Networking, Sensing and Control Delft, 11- 13 April 2011.

4. May ZinOo,Mazliza Othman , Performance Comparisons of AOMDV and OLSR Routing Protocols for Mobile Ad Hoc Network,Second International Conference on Computer Engineering and Applications, 2010.

5. Yanbin Yang, Hongbin Chen, An Improved AODV Routing Protocol for MANETs, IEEE, 2009.

EhsanKhosrowshahiAsly,MortezaDamanafs

hany, MaghsoudAbbaspour, MajidNoorhosseiniz, Kamran Shekoufandehy, EMP-DSR: An Enhanced Multi-Path Dynamic Source Routing Algorithm for MANETs Based on Ant Colony Optimization, Third Asia International Conference on Modelling& Simulation, 2009.

[11]. 11. J. Eriksson, M. Faloutsos and S. Krishnamurthy.DART: Dynamic Address RouTing for Scalable Ad Hocand Mesh Networks. in IEEE- ACM Transactions onNetworking, vol. 15, no. 1, April 2007,

pp. 119-132.

[12]. Elizabeth M.Royer, Charles E. Perkins An Implementation study of AODV routing protocol IEEE, 0-7803-6596- 8/00,2000.

Dr. Sandeep Singh Kang Working at CGC- College of Engg.Landran as HOD (CSE) Since Nov,2007. 2013. He did his B.Tech from Punjab Technical University and M.Tech from Punjabi University Patiala. Recently he has completed his Ph.D in Computer Science & Engineering in the area of Wireless Networks. He has total of 10 years of Experience. He has Published 52 Research Papers in International/National Journals and Conferences and attended 12 workshops and FDPs for enhancement of his skills. He has published a BOOK Title: Integrated Approach to Network Security. Besides this, he has guided

around 20 Students for PG Research Work and guiding 02 students for doctorate. His area of specialization is Security of Wireless Networks. He is the Life Member of

Computer Society of India and Member Board of Studies (Computer Science), Punjab Technical University, Jalandhar.