Study of Multipath Routing Protocols for Ad Hoc Wireless Networks

Anilkumar Krishnan

CS522 Computer Communications

University of Colorado, Colorado Springs

Table of Contents

Introduction

Ad Hoc Networks

Ad hoc On-demand Distance Vector (AODV)

Multipath On-demand Routing Protocols

Ad hoc On-demand Multipath Distance Vector (AOMDV)

Performance Comparison

Other Multipath Routing Protocols

Conclusion

Reference

Introduction

My research project is focused on the study of Multipath Routing Protocol for Ad hoc Wireless Networks. Ad hoc network is a collection of mobile nodes without the intervention of any centralized access point or any infrastructure. Mobile wireless devices are rapidly becoming popular due to the improvements in the portability and the power of these products. These devices need efficient routing protocols to communicate over the wireless links.

This paper mainly discuss about the available protocols and their effectiveness. First it talks about the characteristics of ad hoc networks and then gives an over all picture of the routing protocols, mainly single path routing protocols. Then it briefly describes how the multipath extensions to these single path algorithms improve the performance of these routing protocols. It also reviews the working of single path protocol and a multipath routing protocol. Results of some performance study of the multipath protocol over the single path protocol is also given and finally the paper concludes with the areas to be explored in the field of multipath routing protocols for wireless networks.

Ad Hoc Networks

An ad hoc network consists of a group of wireless nodes without any infrastructure. They are temporary in nature and can be formed spontaneously anywhere and be disbanded after a limited period of time. They are often justified by scenarios, where we don’t want or where we cannot deploy and manage an infrastructure. Examples include a battlefield, a disaster relief or a spontaneous meeting etc.

The most prominent characteristic of this kind of network is its dynamic topology, due to a constantly changing set of nodes. Also they have limited channel bandwidth and they are running with limited battery power. So the challenge is to be able to route with low overheads in dynamic conditions. Overhead here is the routing protocol control message, which consumes both channel bandwidth as well as the battery power of the nodes for processing.

Also in ad hoc wireless networks, there are no default routers available potentially every node becomes a router. So these networks have more route alternatives.

Of the routing protocols available for ad hoc wireless networks, pro-active protocols, which learn the network topology before a forwarding request comes in, are not seems to be efficient in highly dynamic conditions. (DSDV – Destination Sequenced Distance Vector is an example of pro-active routing protocol). On the other hand re-active, also called as On-demand routing protocol reduce the routing overhead by building and maintaining only needed routes. In on-demand protocols, a route discovery process is initiated whenever a route is needed. Examples of On-demand routing protocols are DSR – Dynamic Source Routing, TORA – Temporally-Ordered Routing Algorithm, AODV – Ad hoc On-demand Distance Vector etc.

A brief explanation of the working of AODV protocol is given below.

Ad hoc On-demand Distance Vector (AODV)

When a source needs a route to a destination it initiates a route discovery process. Route discovery is based on broadcasting (network-wide flood) of a route request (RREQ). Each node re-broadcasts the RREQ and adds its own address to a path history. Eventually the destination hears the request and it generate a route reply (RREP). The RREP is routed back to the source via the reverse path established as along the RREQ. As the RREP proceeds towards the source, a forward path to the destination is established. Route maintenance is done using route error (RERR) message. When a source receives a RERR, it indicates a link failure and also it initiates a new route discovery, if a route is still needed.

AODV provides loop free routes. Sequence numbers in AODV ensure loop freedom.

Even though the single path on-demand routing protocols look quite suitable for dynamic self-starting networks, they are not without performance problems. Frequent route discovery attempts in a highly dynamic network where link failures and route breaks are very common together with the route discovery latency can impact the performance negatively.

Multipath On-demand Routing Protocols

Multipath routing protocols can eliminate the frequent route discovery problem by computing multiple paths in a single route discovery attempt. New route discovery is needed only when all paths fail. Multipath protocols provide efficient fault tolerance, so it provides a mechanism for faster and efficient recovery from route failures in dynamic networks. Multiple paths can also be used to balance loads by forwarding data packets through multiple paths at the same time.

Ad hoc On-demand Multipath Distance Vector (AOMDV)

Ad hoc on-demand multipath distance vector (AOMDV) protocol is an example of multipath routing protocol for wireless ad hoc networks. This is an extension of AODV protocol discussed earlier. The main idea in AOMDV is to compute multiple redundant paths during route discovery. The AOMDV protocol uses the routing information already available in the underlying AODV protocol as much as possible. So little additional overhead is required for the computation of multiple paths.

Two main components of the AOMDV protocols are

A route update rule to establish and maintain multiple loop-free paths at each node
A distributed protocol to find link disjoint paths

In AODV protocol, each copy of the RREQ packet arriving at a node defines an alternate path back to the source. But accepting all such copies to construct routes will lead to routing loops. To eliminate any possibility of loop, AOMDV uses an invariant based on a notion of “advertised hope count”.

The distributed protocol to find link-disjoint path make the multiple loop- free paths disjoint. Path disjointness has the nice property that paths fail independently. The two types of disjoint paths are node-disjoint and link-disjoint. Node-disjoint paths do not have any nodes in common other than source and destination. Similarly link-disjoint paths do not have any common link, but they may have common nodes. Even though node-disjointness guarantees that links fail independently, lesser number of such disjoint routes make them less effective compared to link disjoint routes, when the interest is mainly fault tolerance. However with simple modification, AOMDV can allow the discovery of either node or link-disjoint paths.

Performance Comparison

Some studies evaluated the performance of AOMDV with respect to AODV using ns-2 simulation under variety of mobility and traffic scenarios. They suggest that AOMDV is able to achieve a remarkable improvement in the end-to-end delay and is also able to reduce routing overhead by 20%.

Other Multipath Routing Protocols

On-demand protocols like Dynamic Source Routing (DSR) and Temporally-Ordered Routing Algorithms (TORA) have built in capability to compute multiple paths. But they are having different set of performance/overhead problems. Routing On-demand Acyclic Multipath (ROAM) is an on-demand multipath distance vector algorithm based on diffusing computations. For ROAM, the state information must be maintained at each node during route discovery, thus increasing overheads. So ROAM is better suited for static ad hoc networks or networks with low node mobility. Split Multipath Routing (SMR) is another disjoint multipath protocol using source routing. SMR is similar to DSR except that it uses a modified flooding algorithm and the data traffic is split among the multiple paths.

Conclusion

From this study it is clear that multipath routing can be used in on-demand protocols to improve efficiency and faster recovery from route failures in highly dynamic ad hoc networks. However multipath techniques are not without pitfalls. In many of these protocols alternate routes in practice will always tend to be longer than the primary routes. This will present a trade-off between end-to-end delay and routing overhead. Also maintenance cost of multiple routes in terms of additional routing packets should be evaluated. Issues related to on-demand multipath routing protocols such as availability of multiple paths in relationship with node density and load balancing with multiple paths are needed to be explored more.

Performance comparisons of different multipath routing protocols for wireless ad hoc networks under a wide range of mobility and traffic- scenarios can be studied. That was one of the goals of this semester project, but due to time limitation I couldn’t finish it.

Reference

Asis Nasipuri and Samir R. Das. On-demand Multipath Routing for Mobile Ad Hoc Networks. Proceedings of the 8th international conference on Computer communication and Networks, Boston, Oct 1999.

Charles E. Perkins and Elizabeth M Royer. Ad hoc On-demand Distance Vector Routing. Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, LA, Feb 1999.

Elizabeth M Royer and Charles E Perkins. An Implementation Study of the AODV Routing Protocol. Proceedings of the IEEE Wireless Communications and Networking Conference, Chicago, IL, Sept 2000.

Mahesh K Marina and Samir R as. On-demand Multipath Distance Vector Routing in Ad Hoc Networks. To appear in the proceedings of the international Conference for Network Protocols. Riverside, Nov 2001.

Samir R Das, Charles E Perkins and Elizabeth M Royer. Performance Comparison of Two On-demand Routing Protocols for Ad Hoc Networks. Proceedings of the IEEE Conference on Computer Communications (INFOCOM). Tel Aviv, Israel, March2000.

http://www.ececs.uc.edu/~sdas/pub.html

http://www.cs.ucsb.edu/~eroyer/aodv.html

http://www.monarch.cs.cmu.edu/cmu-ns.html