Annotated Bibliography

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 to improve AODV.
REFERENCES:
  • West, David and Dowling, Jim, "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 later successfully implements a Windows CE version. The author makes several points to show the necessity of changing from the current wireless standards, such as 802.11. Wireless connections all use a shared resource of radio band. Therefore, we desire a network that maximizes our limited bandwidth. Also want to minimize power consumed since most mobile device use battery power. Areas without existing authoritative hosts force computer networks to securely handle connections by themselves. Yet, we still want to have networking handled automatically.

    Existing wireless protocols have dealt with these conditions, but come with limitations on networking overhead that clutters networks with routing information and static routes that defeats the purpose of wireless allowing mobility. AODV addresses these issues by providing a protocol that handles a dynamic environment, where computers can change position. Communication responses may use different routes instead of fixed tables, and systems are not required to know the entire network, save overhead cost of sending data AODV is a reactive network, meaning it finds connections when needed, rather then the proactive approach of building routes beforehand.

    AODV is broken into two main parts: Route discovery and route maintance.

    For route discovery, computers send a request to destination IP, along with own IP. Neighboring computers receive the signal and either reply with a match or rebroadcast the request. The protocol limits the number of hops allowed. If the request is not found, the source resends requests with larger limit on hops. Requests are stored by every receiving computer for a brief time. Successful replies move in the reverse direction. Since requests are saved, the node knows where to send the data. 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 maintaining existing routes, each node uses HELLO messages, which are single hop reply messages, to detect a break. On a break, the computer discards bad routing information that was saved. Information is relayed back to sender, who can request again to rediscover its destination. AODV can support repair attempts small scale local routes without going back to the source, but computers needs to buffer incoming packets and report failures.

  • 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 takes ideas from the Destination-Sequenced Distance Vector (DSDV) such as its sequencing number for active network nodes. The main difference is the protocol only stores routing information on-demand for active connections and only stores local information. The protocol builds connections through relaying request commands (RREQ) and building a routing path with its freshest data. Timeouts and local breaks are considered as factors for building efficient routes and detecting broken links. The protocol was simulated using 50, 100, 500, and 1000 nodes, where all nodes are within a set field and can slowly move around in random patterns. The "Goodput" 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 scaling protocol in present 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 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 by 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 overall winner. AODV loses more throughput than others when its connections are broken due to fast moving nodes, but still outperform 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 floods the network.

  • 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 was one of the newer 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 a intelligent routing decision. Using a relatively fixed network topology, three protocols are tested and compared: Ad-hoc On-demand Distance Vector (AODV), Dynamic Source Routing (DSR), and Destination Sequenced Distance Vector (DSDV). Results are graphed using the shadowing and two-ray-ground radio models to show their packet delivery ratio. The article briefly discusses some technical formulas for neighbor probability and coverage, and it talks about interference and how their simulation will be close to the ideal state. Detail table results of shadowing and two ray modeling show a clear distinction when the network is overloading using 95% confidence intervals. AODV seems to perform slightly stronger in the shadowing model than DSR as the number of nodes increase, but both are beaten by DSDV. The two ray ground model reverses the results, giving both AODV and DSR good delivery ratio with high nodes and poor results for 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 of ad-hoc and 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 clients. Due to dynamic state of clients, mesh networks perfer to use reactive protocols such as AODV. The author designs a new protocol named Multi-Radio Ad-hoc On-Demand Distance Vector Routing (AODV-MR). The protocol acts similar to AODV, but now will broadcast 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 author ran a simulation 50 times with 30 connections at 10 packets per second over a mesh network. She measured the experiment by 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]