International Journal of Emerging Trends & Technology in Computer Science (IJETTCS)

Web Site: www.ijettcs.org Email: [email protected], [email protected] Volume 2, Issue 2, March April 2013 ISSN 2278-6856

A SURVEY ON MULTIPATH ROUTING PROTOCOLS FOR MANETS

Ranjeet Kaur1, Rajiv Mahajan2, Amanpreet Singh3
1

Ph.D Scholar (CSE), PTU Jalandhar

2

GIMET, Amritsar
3

IET, Bhaddal

ABSTRACT: A Mobile Ad-hoc Network (MANET) is a

temporary wireless network composed of mobile nodes, in which an infrastructure is absent. The mobile nodes can dynamically exchange data among themselves. Because of these characteristics, path connecting source nodes with destination may be very unstable and go down at any time, making communication over ad hoc networks difficult. To solve the problem of stability, multiple routes are created between source and destination nodes. When a primary route fails to deliver the packets, the secondary routes can be used. The multipath routing provides a better fault tolerance in the sense of faster and efficient recovery from route failures. This also provides better Load Balancing. This paper addresses issues and challenges of the various multipath routing protocols in MANETs.

In most cases, the ability of creating multiple routes from a source to a destination is used to provide a backup route. When the primary route fails to deliver the packets in some way, the backup is used. This provides a better fault tolerance in the sense of faster and efficient recovery from route failures. Multiple paths can also provide load balancing and route failure protection by distributing traffic among a set of disjoint paths. The main design criteria for the routing protocols in MANETs are as follows: Scalability and Reliability Simplicity and ease of implementation Fault Tolerance. Dynamic topology maintenance Distributed and lightweight The rest of the paper is organized as follows: We provide the MANETs routing protocols, Multipath routing in MANETs, issues and design challenges in multipath routing and future works.

Keywords: MANET, protocols, QoS.

ad

hoc

networks,

Routing

1. INTRODUCTION
Mobile ad hoc networks (MANETs) [1] consist of a collection of wireless mobile nodes which dynamically exchange data among themselves without the reliance on a fixed base station or a wired backbone network. In such networks, nodes are typically distinguished by their limited power, processing, and memory resources as well as high degree of mobility. Due to the limited transmission range of wireless network nodes, multiple hops are usually needed for a node to exchange information with any other node in the network. Thus routing protocols play an important role in ad hoc network communications. Since all nodes in an ad hoc network can be connected dynamically in an arbitrary manner it is usually possible to establish more than one path between a source and a destination. This property of ad-hoc network routing is called multipath routing.

2. ROUING PROTOCOLS IN MANETS

MANET routing protocols could be broadly classified into three major categories: Proactive, Reactive and hybrid. a) Proactive Routing Protocols: Proactive protocols continuously learn the topology of the network by exchanging topological information among the network nodes. Thus, when there is a need for a route to a destination, such route information is available immediately. If the network topology changes too frequently, the cost of maintaining the network might be very high. If the network activity is low, the information about actual topology might even not be used. b) Reactive Routing Protocols: The reactive routing protocols are based on some sort of query-reply dialog. Reactive protocols proceed for establishing route(s) to the destination only when the need arises. They do not need periodic transmission of topological information of the network. c) Hybrid Routing Protocols: Often reactive or proactive feature of a particular routing protocol might not be enough; instead a mixture might yield better solution. Hence, in the recent days, several hybrid protocols are also proposed. Page 42

Figure 1: A Typical Structure of MANET

Volume 2, Issue 2 March April 2013

International Journal of Emerging Trends & Technology in Computer Science (IJETTCS)

Web Site: www.ijettcs.org Email: [email protected], [email protected] Volume 2, Issue 2, March April 2013 ISSN 2278-6856
calculations to prevent loops. At the occurrence of a link breakage, local maintenance is initiated by upstream node. Path freshness is maintained by data flow. As in TORA, the reliable delivery of control packets is required. The authors claim the protocol to work for both wired and wireless networks but, this requirement makes it unviable in wireless networks unless the mobility is very low. f) ZD-AOMDV [5] is an on demand multi-path routing protocol based on AODV. In the proposed algorithm the concept of Active Neighbour is introduced. Active neighbours are the neighbour nodes which have already received and replied to the Route Request packet (RREQ) and its probable that they exist on other paths for the same source and destination, so even though they are located on two disjoint paths they will still affect each other in simultaneous data transfer. As mentioned in the abstract, our proposed algorithm tries to find zonedisjoint paths between source and destination. The nodes in zone disjoint paths have almost no neighbour in the other path, to the feasible extent. g) CMDSR [11] protocol is designed to be adaptive according to network dynamics. It uses hierarchy to perform the route discovery mechanism and distribute traffic among diverse multiple paths. By using this kind of hierarchical routing, routing overhead control messages are greatly reduced. The CMDSR protocol has a 3-level hierarchical scheme, The first level of cluster is 0node, the second level of cluster is 1-cell cluster, each node in the cell is 1-hop away from the cluster head. The third level of the cluster is 2-server, which is the highest level of the hierarchy. Due to node mobility, the clusters change dynamically. The neighbour node information is exchanged among nodes and a cluster head is selected among these nodes. The procedure of choosing a cluster head is based on owning token first(OTF) and minimum ID(MI). Token is an attribute of node that defines whether a node can be a cluster head or not. In this procedure, a node owning the token becomes the cluster head. If there are more than one node owning tokens or there is no token owning node, then the node with the minimum ID is selected as the cluster head. Hello messages are used by a cluster head to update the cluster formation. If a cluster head doesnot receive any reply from a member after sending three Hello messages, it assumes that the link is broken. Then the member nodes can select another cluster head and if it cannot hear from any cluster head, it becomes a cluster head. The cluster heads select a server among themselves. During the route discovery mechanism, many paths are discovered from a source to a destination. The quality of a path is considered important in CMDSR. CMDSR selects only a reliable path. The path reliability is calculated based on the availabilities of all the links along a path. h) SMR (Split Multipath Routing) [4] is an on-demand routing protocol that builds multiple routes using request Page 43

3. MULTIPATH ROUTING PROTOCOLS IN MANETS

The following are the brief summaries of the protocols: a) AODV-BR (Backup Routing in Ad Hoc Networks) [8] protocol is based on [AODV] and maintains multiple paths. After the broadcast of route request, the multiple paths are established during route reply phase. Also a mesh is structured from the overheard packets and the neighbouring nodes are recorded as the next hops to destination in corresponding nodes alternate route table. Alternate paths are use only when the primary link fails and to prevent packets tracing a loop, the mesh nodes forward a data packet only if the packet is not from their next hop to destination. Since one path is used at a given time, [AODV-BR] is not a genuine multipath idea. There is no simultaneous usage of multiple paths. b) AOMDV (Ad Hoc on-demand Multipath Distance Vector Routing) [2] is basically multipath extensions on top of AODV. The route discovery process has been modified to enable multiple paths. They stress on link disjointness of multiple paths such that the paths may share nodes but no edges. Also the loop freedom property of paths is guaranteed by using sequence numbers of nodes. After mentioning link disjoint ness with a high importance, it is interesting that the authors prefer to use one path at a time rather than simultaneous usage of multiple paths. Their reason to choose single path at a time is the requirement of addressing issues, splitting traffic along each path and packet reordering at the destination. And as a different aspect of AOMDV than AODV, the usage of periodic HELLO messages to detect stale paths can be mentioned. c) TORA [3] is a highly adaptive, distributed routing algorithm based on the principle of link-reversal. It provides multiple loop-free paths from source to destination. The key design concept of TORA is to localize control messages to a small set of nodes in the neighbourhood of the topological changes. The protocol consists of three basic functions: route creation, route maintenance and route erasure. d) ROAM [10] routing protocol uses inter-nodal coordination along acyclic sub-graphs, which is derived from the nodes distances to destination. This operation is referred to as a diffusing computation which is originated by source and propagated by each node that has no entry for the destination. The advantage of this protocol is that it eliminates the search-to-infinity problem by stopping multiple flood searches when the required destination is no longer reachable. Among the multiple paths discovered, the shortest one is used primarily and the authors stated that multiple paths can be used for forwarding packets, but not used in path Volume 2, Issue 2 March April 2013

International Journal of Emerging Trends & Technology in Computer Science (IJETTCS)

Web Site: www.ijettcs.org Email: [email protected], [email protected] Volume 2, Issue 2, March April 2013 ISSN 2278-6856
reply cycles. When the source needs a route to the destination but no route information is known, it floods the ROUTER REQUEST (RREQ) message to the entire network. Because this packet is flooded, several duplicates that traversed through different routes reach the destination. The destination node selects multiple disjoint routes and sends ROUTE REPLY (RREP) packets back to the source via the chosen routes. i) NDMRP (Node-Disjoint Multipath routing protocol) [6] protocol modifies and extends AODV to enable the path accumulation feature of DSR in route request/reply and discover multiple node-disjoint routing paths with a low broadcast redundancy, which ensures reliability and timeliness by computing a pair of node-disjoint paths. Multi-constrained Node-disjoint paths find significance in delivering real time information to geographically distributed critical infrastructure applications. j) In SMP-DSR (Split Multipath Dynamic Source Routing) [7] each mobile host maintains route caches, in which it caches routes that it has learned. When one host wants to send a packet to another host, the sender first checks for a source route to a destination. If a route is found, the sender uses this route to transmit the packet. Otherwise the sender attempts to discover one using the route discovery process (route request/reply cycles). While waiting for route discovery to complete, the host continues normal processing. The host buffers the original packet in order to transmit it once the route is discovered. Each entry in the route cache is deleted after an expiration period. k) RSR[12] protocol is based on a dispersity routing scheme. In a dispersity routing scheme, a message is partitioned and sent over different paths. The key idea is that if a path fails, there is still a chance for other paths to send a packet successfully to a destination. Dispersity routing can be broadly classified into two major types: non-redundant and redundant. In non-redundant dispersity routing, a message is divided into sub-messages and these sub-messages are routed through different paths. In redundant dispersity routing, a message is also divided into sub- messages. But the number of submessages is less than the number of discovered paths that the routing protocol uses. Additional sub-messages are constructed as a linear combination of the bits in the original sub-messages in such a way so that the original message can be constructed without receiving all the submessages. In RSR, two paths are selected: one is the primary path and the other is the secondary path. Two identical packets are sent using these two paths. The original packet is sent along the primary path and the other copy of the packet is sent along the redundant path. The primary path called Path1 is formed from the route cache based on the least number of hops. The other paths Path2, Path3; . . . are chosen from paths that are disjointed with Path1. The traffic dispersion on different Volume 2, Issue 2 March April 2013 paths is done in a round-robin fashion where each path has a constant weight of one packet. If no other alternate path is available, RSR performs similarly as DSR. In the source node RSR adds an agent named packet duplication agent (PDA)at the network layer to duplicate packets before sending them out. The PDA agent only duplicates TCP or UDP packets. Routing layer protocol packets, like route discovery and route maintenance packets, are sent without any duplication. In the destination node, RSR has an agent named duplicate packet filter (DPF) at the network layer. The function of DPF is to filter out the duplicate packets. Moreover, when there is no intermediate node between a source and a destination, PDA doesnot duplicate a message. PDA also doesnot duplicate a packet if there is only one route available between a source and a destination. l) In ZRP {Zone Routing Protocol) [9], the nodes have a routing zone, which defines a range (in hops) that each node is required to maintain network connectivity proactively. This means that for nodes within the routing zone, routes are kept in a table and therefore are immediately available. For the outside nodes, routes are discovered on-demand (reactively) and any on-demand routing protocol can be used to find a route to the destination. It can be seen that, the control overhead is much less than pure proactive routing protocols. The delay for discovering routes is also improved with respect to pure reactive protocols such as DSR by allowing routes to be discovered faster. This is due to the fact that the boundary node of a routing zone will have the information of required destination proactively. So, the route request will only have to travel to a boundary node of the destinations zone. The route maintenance procedure for out-of-zone destinations will be same as the used reactive protocols maintenance, where, inside the zone periodic updates will handle this issue proactively.

4. ISSUES AND DESIGN CHALLENGES OF MULTIPATH ROUTING PROTOCOLS

While designing a multipath routing protocol the following three major fundamental issues have been addressed in the literature: -How to discover multiple paths: To discover multiple paths from a source to a destination, the basic route discovery mechanisms used in DSR and AODV protocols need to be modified. In fact, one of the major reasons for using multipath routing is to discover multiple paths that should be node-disjointed or linkdisjointed. In the node-disjointed paths, nodes on the paths should not be common. In the link-disjointed paths, links on the paths should not be common. Hence, the route discovery mechanisms of the existing routing protocols need to be modified to discover a maximum number of node- disjointed or link-disjointed paths .Once Page 44

International Journal of Emerging Trends & Technology in Computer Science (IJETTCS)

Web Site: www.ijettcs.org Email: [email protected], [email protected] Volume 2, Issue 2, March April 2013 ISSN 2278-6856
all node-disjointed or link-disjointed paths have been discovered, there arise other issues like how to select a suitable path or a set of paths from all the discovered paths and what node should make this selection, namely the source or the destination. -How to select a path: Once multiple paths are discovered, a multipath routing protocol should decide how to select a path for sending data packets. If a number of paths are discovered, there is a question to ask how many of these paths should be used? If only a few paths are used, the performance of a multipath routing protocol should be similar to that of the shortest path routing protocol. On the other hand, if all paths are used, there is a chance of selecting an excessively long path, which may adversely affect the performance of a multipath routing protocol. -How to distribute a load: Once a path or a set of paths are selected, a good multipath routing protocol should decide how to use these multiple paths while sending data packets. While using the paths, the following issues need to be addressed: (1) All paths can be used in a round-robin fashion (Wangetal., 2005), (2) Paths can be selected at random, (3) A path can be selected to send a preset number of packets(Cha and Lee, 2005) and then a different path can be selected to send the same number of packets (4) Paths can be selected to satisfy the reliability or the delay constraint of a network. Once a path or a set of paths is selected, there arises another issue, specifically, how a source node should send a packet. It may divide a packet into multiple segments and send these segments by using different paths or it may send duplicate copies of a packet by using different paths.

[2] Marina, M.K. and Das, S.R., On-demand Multipath Distance Vector Routing for Ad Hoc Networks, Proc. of 9th IEEE Int. Conf. On Network Protocols, pp. 14-23, 2001. [3]A. B. McDonald and T. F. Znabi, "A path availability model for wireless ad hoc networks," in Proc. IEEE WCNC, New Orlean, LA, Sep. 1999, pp. 35--40. [4] Sung-Ju Lee, Mario Gerla, Split Multipath Routing with Maximally Disjoint Paths in Ad hoc Networks, IEEE,2001 [5] Nastooh Taheri Javan, Reza Kiaeifar, Bahram Hakhamaneshi, Mehdi Dehghan, ZD-AOMDV: A New Routing Algorithm for Mobile Ad-Hoc Networks, Eigth IEEE/ACIS International Conference on Computer and Information Science,2009. [6] Xu Yi, Cui Mei, Yang Wei, Xan Yin, A Nodedisjoin Multipath Routing in Mobile Ad hoc Networks, IEEE,2011. [7] Shabnam Vahedi,Maryam Mohseni and Amir Darehshoorzadeh, Design a multipath routing algorithm in ad hoc networks in order to improve fault tolerance, The 18th Annual IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, 2007 [8] S.-J. Lee and M. Gerla, .AODV-BR: Backup Routing in Ad hoc Networks, In Proceedings of IEEE WCNC 2000, Chicago, IL, Sep. 2000. [9] Zygmunt J. Haas and Marc R. Pearlman. ThePerformance of Query Control Schemes for the Zone Routing Protocol. IEEE/ACM Transactions on Networking, Aug 2001.

5. CONCLUSIONS AND FUTURE WORK

The mobile ad hoc networks have been a subject of quite a number of investigations in recent years. Most of these investigations have been motivated by the need to design an efficient routing protocol for an ad hoc network. A good routing protocol needs to provide reliability and energy efficiency with low control overhead. To ensure reliability, load balancing and QoS, multipath routing protocols have been proposed for MANET. This paper presented a survey of most recent multipath routing protocols for MANETs. Our future work will focus on the design of a multipath routing protocol that will consider the advantages and weaknesses of the protocols mentioned in this paper. We will pay special attention to simultaneous usage of paths, data forwarding mechanism considering the delay of the available paths, scalability and energy efficiency. REFERENCES [1] S. Corson and 1. Macker, "Mobile Ad Hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Consideration ", IETF WG Charter, Volume 2, Issue 2 March April 2013

[10] J. Raju and J. J. Garcia-Luna-Aceves. A new approach to on-demand loop-free multipath routing. Proceedings IC3N, pages 522527, 1999. [11 ]Hui-Yao An, Ling Zhong, Xi-Cheng Lu, and Wei Peng, A Cluster-Based Multipath Dynamic Source Routing in MANET, IEEE International conference WiMOB2005, Volume-3, pp. 369-376, Aug.2005. [12] Wang L, Jang S, Lee T-Y. Redundant source routing for real-time services in ad hoc networks. In: Proceedings of IEEE international conference on mobile ad hoc and sensor systems conference, Washington, DC, November, 2005.

Page 45