Implementation of Ad Hoc Routing Protocol : AODV for purposes of simulation.

By Srdjan Petrovic and Soumendra Nanda

7^th December 2001

Table of Contents:

Introduction

What is AODV

Working in breifL

Overview of Task

Progress and Results.

Introduction:

We have been studying various aspects of simulation of computer networks and

had implemented some basic queueing models. Amongst the several papers we studied

was a comparission of various ad hoc routing protocols such as AODV, DSR and DSDV.

We decided to attempt to implement AODV : Ad Hoc On Demand Vector Routing as it

showed potential for scaling better in our planned simulation experiments.

In any simulation experiment(serial or parallel) when one increases the number

of entities being simulated the performance degrades drastically and the experiment

is not scalable. Compared to the other algoritms available we felt that

AODV would be one that is likely to scale very well. The only one perhaps that

would perform better would be a hierarchically organised protocol(based on

clusters and cluster heads), however we found building such a protocol from the ground

up to be extremely challenging and virtually impossible given the time constraints.

We plan to integrate our AODV code into an existing network simulator SWAN

which is coded in C++ and is open sourced and designed to utilize DaSSF(

Dartmouth Scalable Simulation Framework) at its core. SWAN is used to model and

simulate mobile wireless networks. It has a layered architecture and at

present the mobility components have not yet been implemented. At present SWAN

uses a commerical and proprietory routing algoritm called WIROKIT. Our goal is

to replace WIROKIT with our own routing code AODV to act at the network layer.

What is AODV:

The Ad hoc On Demand Distance Vector (AODV) routing algorithm is a routing

protocol designed for ad hoc mobile networks. AODV is capable of both unicast

and multicast routing. It is an on demand algorithm, meaning that it builds

routes between nodes only as desired by source nodes. It maintains these routes

as long as they are needed by the sources. Additionally, AODV forms trees which

connect multicast group members. The trees are composed of the group members

and the nodes needed to connect the members. AODV uses sequence numbers to

ensure the freshness of routes. It is loop-free, self-starting, and scales to

large numbers of mobile nodes.

It is still a work in progress and most of it is based on the IETF(Mobile Ad

Hoc Networking Working Group of the Internet Engineering Task Force) draft

available at http://www.cs.ucsb.edu/~eroyer/txt/aodvid.txt by Charles Perkins,

E Royer and Samir Das.

The design is based on DSDV (Distance Sequenced Distance Vector) routing

algorithm (also by Perkins) with the aim of reducing the need for system wide

broadcasts as much as possible.

With AODV small changed in network topology due to mobility does not require

systemwide broadcasts. This localizes the effects of local movements whereas in

DSDV local movemensts have global effects.

Broadcasts in DSDV have been replaced by careful bookkeeping that identifies if

one or more links are broken. Whenever routes are not used they are expired and

consequently discarded, which reduces the effects of stale routes as well as

the need for route maintenance for unused routes.

Multiple routes can be used when they are collected during the discovery phase.

However there are several potential difficulties with this approach: complexity

in managing the ageing process for several routes; complexity involved when an

alterbate route goes stale and complexity in book keeping when two alternate

routes share a common link which eventaully breaks!

Hence current implementations of AODV use a single route for unicast destinations.

Working in brief:

AODV stands for Ad-hoc On-demand Distance Vector routing and is, as it states,

an on demand protocol. It provides loop-free routes through the use of sequence

numbers associated to each route. In short, if A needs a route to B it

broadcasts a ROUTE REQUEST message. Each node that receives this message, and

does not have a route to B, rebroadcasts it. The node also keeps track of the

number of hops the message has made, as well as remembering who sent it the

broadcast.

If a node has the route to B it replies by unicasting a ROUTE REPLY back to the

node it received the request from. The reply is then forwarded back to A by

unicasting it to the next hop towards A. This establishes a uni-directional

route(asymmetrical link). For a bi-directional route(symmetrical link) this

procedure will need to be repeated in the reverse direction.

To achieve faster convergence in the net, and thus higher mobility, a ROUTE

ERROR message can be broadcasted on to the net in the case of a link breakage.

Hosts that receive the error message remove the route and re-broadcasts the

error messages to all nodes with information added about new unreachable

destinations.

A More Detailed View:

AODV builds routes using a route request / route reply query cycle. When a

source node desires a route to a destination for which it does not already have

a route, it broadcasts a route request (RREQ) packet across the network. Nodes

receiving this packet update their information for the source node and set up

backwards pointers to the source node in the route tables. In addition to the

source node's IP address, current sequence number, and broadcast ID, the RREQ

also contains the most recent sequence number for the destination of which the

source node is aware. A node receiving the RREQ may send a

route reply (RREP) if it is either the destination or if it has a route to the

destination with corresponding sequence number greater than or equal to that

contained in the RREQ. If this is the case, it unicasts a RREP back to the

source. Otherwise, it rebroadcasts the RREQ. Nodes keep track of the RREQ's

source IP address and broadcast ID. If they receive a RREQ which they have

already processed, they discard the RREQ and do not forward it.

As the RREP propagates back to the source, nodes set up forward pointers to the

destination. Once the source node receives the RREP, it may begin to forward

data packets to the destination. If the source later receives a RREP containing

a greater sequence number or contains the same sequence number with a smaller

hopcount, it may update its routing information for that destination and begin

using the better route.

As long as the route remains active, it will continue to be maintained. A route

is considered active as long as there are data packets periodically travelling

from the source to the destination along that path. Once the source stops

sending data packets, the links will time out and eventually be deleted from

the intermediate node routing tables. If a link break occurs while the route is

active, the node upstream of the break propagates a route error (RERR) message

to the source node to inform it of the now unreachable destination(s). After

receiving the RERR, if the source node still desires the route, it can

reinitiate route discovery.

Overview of task:

We would have liked to implement AODV from scratch but due to limited time

constraints decided to use GloMoSim code for AODV as our base. Certain

components of SWAN such as the code for its MAC layer are based on GloMoSim

code and the code is an open source and freely available for academic use.

Certain major differences do exist which we hope to overcome:

First of all, the GloMosSim code is written entirely in C. Although the switch

to the C++ implementation theoretically shouldn't be hard, we had a lot of problems

switching from the non-object oriented design of C, to the OO design of C++. During

this switch, we noticed the clear advantages of the OO design when implementing simulation

environment.:

-The C implementation of the Aodv protocol suffered from the fact that a large number of

arguments had to be passed around in the simulation. This made a lot of code redundant

and less clear.

-But even greater dissadvantage of the GlomoSim code is the lack of

inheritance. This has the effect not only to the code design, but on the performance of the

simulator. It also limits the extensibility of the current GlomoSim implementation.

The timer systems in both were very different, and had to be modified.

SWAN has a layered protocol stack architecture and it works by pushing and popping data

between layers after adding/removing header information. This corresponds to the

real-life behaviour of the protocol stack. GlomoSim, due to the structure of the C language

couldn't implement this type of behaviour very well. Instead the messages beeing passed

between layers, they are passed to the kernel,and then distributed to the corresponding

protocol session. This has clear effect on the performance of the simulator.

Packet structures used in our implementation had to be implemented in SWAN format.

A portion of the MAC layer implementation had to be modified also. MAC layer used to expect

the WIROKit session to be above it in the protocol stack.

The GloMoSim implements AODV based on an older IETF draft.

(draft-ietf-manet-aodv-03.txt)

The authors of GloMoSim state that:

" This version implements only unicast functionality of AODV.

Assumes the MAC protocol sends a signal to the routing protocol

when it detects link breaks. MAC protocols such as IEEE 802.11

and MACAW has this functionality. In IEEE 802.11, when no CTS

is received after RTS, and no ACK is received after retransmissions

of unicasted packet, it sends the signal to the routing protocol

If users want to use MAC protocols other than IEEE 802.11, they

must implement schemes to detect link breaks. A way to do this is,

for example, using HELLO packets, as specified in AODV documents.

- No Precursors (Implemented other mechanism so that the protocol can

still function the same as when precursors are used)

- Unsolicited RREPs are broadcasted and forwarded only if the node

is part of the broken route and not the source of that route

- If more than one route uses the broken link, send RREP multiple times

(this should be fixed based on new specification by C. Perkins,

E. Royer, and S. Das)

- Rev route of RREQ overwrites the one in the route table"

Our implementation currently also suffers from the problems stated above.

Progress and Results:

We are hopeful that we have successfully implemented the AODV protocol to run

as an integral part of SWAN.

Very simple validation tests have been run. The test model that we used consists of a

string of nodes, each "connected" only to the nodes to the left and right of

it (if any). The traffic to the model is introduced though an application

protocol session running directly on top of the aodv session. For this purpose

we have implemented the session called "test session". Test session simply

generates traffic according to an exponential distribution, and sends it to

some destination.

In the firt set of validation tests only the first node (node 1) provides the

traffic, and sends it to the last node. This test was run successfully.

In the second set of validation tests, both the first and the last node provide

the traffic, that is directed to one another. This test showed one bug in our code,

which has been corrected (it involved buffering packets before transmission). Further

testing and validation is required to detect and iron out any bugs if present and test

performance of the implemented protocol and verify its integration with SWAN.