Annotated Bibliography Revised

NAME: Stephen Walter
TOPIC: Wireless Communication via Ad-hoc On-demand Distance Vectoring (AODV)
DESCRIPTION: AODV is a reactive wireless network routing protocol. It is designed with work in areas without access to static wireless servers, where computers must connect to neighboring nodes find routes (paths) to distant computers, while minimizing exchanged data to keep airwaves free.
MOTIVATION: Society is constantly increasing demands for wireless communication and capacity within our internet era. We are facing problems of designing large networks that handle dynamic environments, such as building public internet access in cities. AODV is one of the promising protocols that can organize an such an ad-hoc network. This protocol is often mentioned as one of the wireless standards, but it has not received common acceptance. The goal is to determine how AODV works, its advantages and disadvantages, and what modifications could be made to improve AODV.
REFERENCES:
  • West, David, "An Implementation and Evaluation of the Ad-hoc On-demand Distance Vector Routing Protocol for Windows CE," Master Thesis, University of Dublin, Sept 2003.

    This is a master thesis that describes the foundation of the AODV protocol and successfully implements a Windows CE version. The author makes several points to show the necessity of switching from the current wireless standards, such as 802.11, to a new wireless technology. Wireless connections all use a shared radio band resource. Therefore, we desire a network that maximizes our limited bandwidth. We also want to minimize the power consumed since most mobile devices operate on battery power. Areas without authoritative hosts force computer networks to securely handle connections by themselves. Yet, we perfer to remove the user's burden of setting up networks by automating all of the AODV processes.

    Existing wireless protocols address some of these constraints, but tend to induce significant networking overhead that clutters networks with routing information. On the other hand, use use of static routes defeats the purpose of wireless technology allowing mobility. AODV addresses these issues by providing a protocol that handles a dynamic environment, in which computers can change position. Communication responses may use routes that change over time (as opposed to fixed tables), and systems are not required to know the topology of the entire network. AODV is a reactive network, meaning that it finds routes dynamically when needed, as opposed to the proactive approaches that building routes beforehand.

    AODV is composed of two main parts: Route discovery and route maintenance.

    In the route discovery phase, a computer sends a request to the destination IP, along with its own IP. Neighboring computers receive the request and either reply with a match or rebroadcast the request. The protocol limits the number of hops that a request is allowed to pass through. If the destination IP is not found, the source resends requests with a larger limit on the hop count. Requests are stored by every receiving computer for a brief time. Successful replies move in the reverse direction. Since requests have been saved, eache node knows where to send the data on the way back to the original sender. Network nodes can also reply with a known route to destination to remove redundant requests. All messages get timestamped to track which signals and hops are more recent.

    To maintain valid existing routes at all times, each node uses HELLO messages, which are single hop reply messages, to detect a connection break. On detecting a connection break, a computer discards erroneous routing information previously saved. Such information is relayed back to sender, which can request again to rediscover its destination. The protocol can support repairing local connection breaks without forcing the source to rebuild the connection from scratch, since it is likely only a few adjustments are necessary. This method requires that computers store a buffer of incoming packets and also report failure if a connection could not be reestablished.

  • Parkins, Charles E. and Royer, Elizabeth M., "Ad-hoc On-Demand Distance Vector Routing," Second IEEE Workshop on Mobile Computer Systems and Applications, pp. 90, February 1999.

    This paper is the original protocol proposal for AODV routing. The protocol employs some ideas from the Destination-Sequenced Distance Vector (DSDV) such as its sequencing number for active network nodes. The main difference is that the AODV protocol stores local routing information and routing information on-demand for active connections. The protocol builds connections through relaying request commands (RREQ) and building a routing path with its most recent data. Timeouts and local connection breaks are regarded as factors for building efficient routes and detecting broken links. The AODV protocol was simulated using 50, 100, 500, and 1000 nodes, slowly moving around in random patterns within a set field. The "Goodput" (a comparsion of the good, substantial data versus total data transmitted) results were above 90% for the two smaller networks, and remained acceptable for the larger two. The author concluded that the AODV protocol was the best existing scaling protocol at the time.

  • Boukerche, Azzedine, "Performance Evaluation of Routing Protocols for Ad Hoc Wireless Networks," Mobile Networks and Applications, vol. 9, pp. 333-342, 2004.

    This article features a performance test of one proactive and four reactive protocols in a simulated ad-hoc network. The proactive protocol, Destination-Sequenced Distance Vector (DSDV), was selected due to its relation to our highlighted protocol, Ad hoc On Demand Distance Vector (AODV). In addition to AODV, the test includes Preemptive On-demand Distance Vector routing (PAODV), Dynamic Source Routing (DSR), and Cluster based routing protocol (CBRP). RAODV is an extension of AODV with intermediate repairing. DSR requires the sender to know the full connection route. CBRP develops central branches to reduce discovery requests. Each protocol differs in the amount of discoveries, locality detection, source tracing, or broadcast request range. The simulation use 50 to 100 moving nodes ranging from 10 to 30 connections. The author measured results of each protocol's throughput (ratio of received packets), average delay between source and destination, and overhead (extra routing data per real data sent). The conclusion was there was no definite winner. AODV loses more throughput than others when its connections are broken due to fast moving nodes, but still outperforms the proactive protocols. AODV has the shortest delay between connections, due to the speed of route discovery. At the cost of fast route discovery, AODV has one of the highest overhead ratios since it can flood the entire network with route request messages.

  • Tao, Yang, Makoto Ikeda, Giuseppe De Marco, and Leonard Barolli. "Performance Behavior of AODV, DSR and DSDV Protocols for Different Radio Models in Ad-Hoc Sensor Networks," ICPPW. International Conference Workshops on Parallel Processing, pp. 6, Sept 2007.

    This is one of the more recent articles about AODV, which discusses how Wireless Sensor and Actor Networks (WSANs) play a role in protocols. The authors suggest that we no longer have to make the assumption that wireless networks have stable connections. Computers can analyze sensor data and make an intelligent routing decision. Using a relatively fixed network topology, three protocols have been tested and compared: Ad-hoc On-demand Distance Vector (AODV), Dynamic Source Routing (DSR), and Destination Sequenced Distance Vector (DSDV). Results are presented using the shadowing and two-ray-ground radio models to show their packet delivery ratio. Detailed table results of shadowing and two ray modeling show a clear distinction for the case when the network is overloading using 95% confidence intervals for delivery ratios while incrementing data transfer loads. AODV achieves higher delivery ratio in the shadowing model compared to DSR as the number of nodes increase, but both AODV and DSR are outperformed by DSDV. The two ray ground model reverses the results, giving both AODV and DSR better delivery ratios compared to DSDV.

  • Pirzada, A. Amir, Portmann, M. Portmann and Indulska, Jadwiga, "Evaluation of Multi-Radio Extensions to AODV for Wireless Mesh Networks," Proceedings of the 4th ACM International Workshop on Mobility Management and Wireless Access pp. 45-51, 2006.

    This paper examines how applying a multi-radio feature to AODV greatly improves its performance on mesh networks. A mesh network is a hybrid network that comprises both an ad-hoc and a standard infrastructure. It uses a combination of fixed wireless routers and mobile wireless clients. The routers serve as a backbone and are more dependable than the clients. Due to dynamic state of clients, mesh networks perfer to use reactive protocols such as AODV. The authors design a new protocol named Multi-Radio Ad-hoc On-Demand Distance Vector Routing (AODV-MR). The protocol acts similarly to AODV, with the difference that it broadcasts on one common interface channel when sending out route requests. To simplify the model, all devices have the same channels available. The protocol can vary in number of interfaces. Optimal multi-channel assignment is found to be a NP-hard problem, so the author uses the 2-phase Hyacinth assignment heuristic. The algorithm considers imbalanced loads, which aids routers that take more of the network load. To test the protocol, the authors ran a simulation 50 times with 30 connections at 10 packets per second over a mesh network. Performance factors that have been measured include packet loss, delivery ratio, overhead, latency, and optimal route. Results showed a significant decrease in packet loss, latency, and overhead with each additional interface to ADOV. AODV-MR-3 was able to maintain high loads (3 Mbps) of traffic with strong delivery rate (80%) where AODV failed. Comparison graphs indict a clear improvement to system speed and capacity.

OTHER REFERENCES:
  • Joseph, Camp, Vincenzo Mancuso, Omer Gurewitz, and Edward W. Knightly, "A Measurement Study of Multiplicative Overhead Effects in Wireless Networks," IEEE Infocom, 2008.
    [Tests a multi-tier mesh network's performance produced by overhead. Talks about protocols, particular AODV, at the end of the paper]
  • Panagiotis, Papadimitratos and Haas, Zygmunt J., "Secure On-Demand Distance Vector Routing in Ad Hoc Networks," IEEE/Sarnoff Symposium on Advances in Wired and Wireless Communication, pp. 168-171, April 2005.
    [Variant of AODV designed to stabilize the network with multiple routes]
  • Marina1, Mahesh K. and Das, Samir R., "Ad hoc on-demand multipath distance vector routing," Wireless Communications and Mobile Computing, vol. 6, pp. 969-988, 2006.
    [Alternative implementation of AODV, potentially addresses shortcomings of the original protocol. Talks about packet loss and network failures]
  • Kumar, V.S. Anil, Madhav V. Marathe, Srinivasan Parthasarathy, and Aravind Srinivasan, "Algorithmic Aspects of Capacity in Wireless Networks," ACM Sigmetrics International Conference on Measurement and Modeling of Computer Systems, pp. 133-144, 2005.
    []
  • Chakeres, Ian D. and Belding-Royer, Elizabeth M., "AODV Routing Protocol Implementation Design," Proceedings of the 24th International Conference on Distributed Computing Systems Workshops, pp. 698-703, March 2004
    [Different perspective on AODV design. More modern paper that references Perkins's paper]