We've implemented several ad hoc routing algorithms using the infrastructure provided by the Click Modular Router; this project was Audun Tornquist's masters project. The primary algorithm we've concentrated on is AODV, although there are implementations of DSR and the AODV elements were also extended to support the DSDV protocol. See the masters thesis for more details.
Mike Neufeld
Audun Tornquist
Dirk Grunwald
This software was designed to work with the "ns2click" simulator as well as production systems.
The "madhoc" implementation of AODV may be useful
Our goals were to build a portable, configurable implementation of different ad hoc routing algorithms. Since our implementation was entirely encoded as Click elements, we are able to execute our implementation both within the Linux kernel and as a user space process.
We build implementations of the AODV, DSR, DSDV and a variant of the ZRP protocol. It's difficult to assess when one implementation of an ad hoc routing algorithm actually implements a defined standard. All of our implementations route traffic and are thus "correct" - but do they follow the actual protocol specification? To verify that at least one of our protocols (AODV) was correct, we conducted a performance comparison against an existing implementation of that protocol, using the implementation in the ns-2 simulator.
The following figure compares one aspect of the performance of our implementation of AODV to the standard implementation distributed with the NS-2 simulator. This figure shows the percentage of delivered packets for three different ``pause times'' using a the random-waypoint workload model. We ran three simulation variants. The first, labeled ``NS/Click'' used our Click implementation of AODV in the NS-2 simulator. The second, labeled ``NS/AODV/LL'', uses the AODV implementation distributed with NS-2. This version of AODV uses link-layer ``hello'' packets to detect link breakage. The last variant, ``NS/AODV'' uses that same implementation, but uses explicit network layer ``hello'' messages; this version is comparable to our version since we use explicit ``hello'' messages as well.
The figure shows the mean packet delivery rate and the 95% confidence interval for a set of five randomly selected initial workload configurations. The variance for the ``NS/AODV'' implementation is high because we had difficulty running that configuration to completion -- it often de-referenced empty routing table entries, resulting in runtime errors.
For two samples, comparing the mean and confidence interval is equivalent to a paired-observation test of equality for the mean. This means that for this set of paired experiments, our implementation and the ``NS/AODV'' implementations have the same performance at the 95% confidence level. The dropped packets arise from contention within the wireless media. Both the Click and NS-2 implementations used the same wireless media model provided by NS-2.