written_report.tex

AODV version of Uppsala University

A queue is added to the simulation to enable a location where packets can be held or dropped. The packet scheduling facility decides which packets that should be serviced or dropped. NS-2 supports different types of queuing mechanisms including drop-tail (FIFO) queuing, RED buffer management and variants of Fair Queuing (e.g. Stochastic Fair Queuing). The priority queue (\texttt{PriQueue}) is based on the drop-tail implementation and allows for instance routing traffic to be prioritized.

A queue has two different states, blocked or unblocked. A queue is blocked when dequeued packets are in transit between the queue and its downstream neighbor. The queue will remain blocked as long as it has at least one packet to send and the downstream link is busy. The queue becomes unblocked only when a downstream neighbor invokes the \texttt{resume} function.


\section{NS-MIRACLE}
This section will give a brief introduction to NS-Miracle (Multi InteRfAce Cross Layer Extension for NS)\cite{miracle} and explain some of the key concepts of NS-Miracle in more detail.

\subsection{INTRODUCTION}
\begin{figure}
\begin{center}
\includegraphics[scale=0.3,keepaspectratio=true]{nsmiracle.eps}                                                               \end{center}
\caption{The NS-Miracle structure}
\label{figureNsMiracle}
\end{figure}
NS-Miracle is a set of libraries that enhance functionality provided by NS-2. It is currently developed by the SIGNET Lab at the University of Padova\cite{miracledoc}.

It provides a modular structure of the network stack in NS-2 and allows users to place multiple modules on each layer in the stack (figure \ref{figureNsMiracle}). This enables for instance several network interfaces in a node. NS-Miracle also supports backend functionality for cross-layer messages, where modules in the same, or in different layers, can communicate with each other.

NS-Miracle uses dynamic linkage and can therefore be used without recompiling NS-2 when code in NS-Miracle changes. Up to version 2.32 of NS-2 you need to patch NS-2 to support dynamic linkage, this is however included in version 2.33 and above. Dynamic linkage also enables users to develop their own modules without modifying the NS-Miracle framework. The module compiles to a shared object which can be loaded at runtime.

\subsection{MODULE}
\label{miraclemodule}
One of the basic building blocks in NS-Miracle is the \texttt{Module} class. A \texttt{Module} represents an entity that can be placed in the stack. This entity can be anything between a Ping-application and a wireless interface at the physical layer. A \texttt{Module} is placed on a specific layer in the stack which is defined in the OTcl simulation setup.

A special type of module is the \texttt{ChannelModule} which connects two \texttt{Module}s in two different nodes.

\subsection{SAP}
\label{miraclesap}
To connect \texttt{Module}s to each other the SAP interface concept (figure \ref{figureNsMiracle}) from the OSI model\cite{osiiso} is used. This is implemented through the class \texttt{SAP}. Besides being able to forward data the \texttt{SAP} is also a tracing point where dataflows can be logged. It is of course the perfect point for tracing since all communication in a simulation flow through \texttt{SAP}s.

\texttt{SAP}s are used in three different ways. The first place where \texttt{SAP}s are used is to connect modules in neighboring layers with each other. This is where regular data packets travels up and down the stack. This connectivity is manually defined in the OTcl script to be able to define multiple branches in the stack (e.g. multiple IP interfaces connects to one linklayer each).

The second way a \texttt{SAP} is used is to connect a node to a channel. For this purpose a specific \texttt{SAP} class called \texttt{ChSAP} exits, which connects a \texttt{Module} to a \texttt{ChannelModule}.

The last use of \texttt{SAP}s are to connect every \texttt{Module} to the \texttt{NodeCore}. This connection is handled by the \texttt{ClSAP} subclass and is used to send cross layer messages (see \ref{clmessages}).

\subsection{CROSS LAYER MESSAGES}
\label{clmessages}
NS-Miracle supports the ability to communicate between \texttt{Module}s with the help of cross layer messages. Every \texttt{Module} is connected to the \texttt{NodeCore} which can be considered as a cross layer message bus. The \texttt{NodeCore} includes all logic to receive and forward cross layer messages.

A cross layer message is derived from the base class \texttt{ClMessage}. By extending \texttt{ClMessage}, \texttt{Module}s are able to pass any kind of data between them. It is however important to note that \texttt{Module}s need explicit knowledge about a specific \texttt{ClMessage}-type to be able to handle it.

Cross layer messages can be sent in synchronous or asynchronous mode. In synchronous mode the sending \texttt{Module} blocks until a reply has been received. This is achieved by letting the receiving node set the reply in the original \texttt{ClMessage} object. A synchronous \texttt{ClMessage} also allows \texttt{Module}s to share variables as the same \texttt{ClMessage} is known to both \texttt{Module}s.

In asynchronous mode the send method returns immediately at the sending module, and the replying modules need to send a new asynchronous message in return. As the sender do not wait for a reply, asynchronous messages can be sent with a specific delay.

The \texttt{NodeCore} can handle two types of destinations for cross layer messages. \texttt{UNICAST} messages are directed to a specific \texttt{Module}, whereas \texttt{BROADCAST} messages are directed to all \texttt{Module}s, or \texttt{Module}s at a specific layer in the stack.

As a complement to the \texttt{NodeCore} bus, cross layer messages can also be sent through the regular \texttt{SAP}s that connect \texttt{Module}s in a stack. This can be useful for communication related to the stack structure, e.g. a mac-layer controlling operation mode of phy-layer.

\subsection{PLUG-IN}
\label{miracleplugin}
The \texttt{PlugIn} is a kind of \texttt{Module} that lives outside the stack connecting directly to the \texttt{NodeCore}. In fact it is the base class of \texttt{Module} and only defines the \texttt{ClSAP} connection to the \texttt{NodeCore}. A \texttt{PlugIn} should include functionality that does not fit in a stack, but rather communicate or coordinate \texttt{Module}s on different sites in the stack. It can also contain functionality specific for the whole node. Example of \texttt{PlugIn} applications are battery drain models and network utilization monitors.

\section{AODV-UU}
In this section we give a brief introduction to AODV-UU (Ad hoc On-demand Distance Vector implementation from Uppsala University)\cite{aodvuu}. We also give a somewhat more complete introduction to the port of AODV-UU for the network simulator NS-2\cite{ns2}.

\subsection{DESCRIPTION}
\label{aodvuudesc}
AODV-UU\cite{aodvuu} is an implementation of the AODV routing protocol for the Linux operating system. It is developed at Uppsala University, with some funding from Ericsson AB. It runs as a user-space daemon, maintaining the kernel routing table. The latest release of AODV-UU is based on RFC3561\cite{rfc3561} and is released under the GNU General Public License (GPL). AODV-UU also supports \textit{Internet gateway mode}, where a gateway node can forward encapsulated packets towards the Internet.

It supports both version 2.4.x and 2.6.x of the linux kernel, and cross-compiling for at least the ARM platform is possible. As AODV-UU includes a Linux kernel-module the programming language of choice is C.

\subsection{NS-2 PORT}
\label{aodvuuns}
\subsubsection{DESCRIPTION}
Since late 2002 the AODV-UU package also includes a port\cite{aodvuuns2} for NS-2\cite{ns2}. The codebase for each of the two versions of AODV-UU are merged and you can decide which one to build when compiling. In NS-2, AODV-UU appears as an \textit{Agent} for a mobile node and can be used just like any other \textit{routing agent}. The port uses as much as possible of the original code to ease further maintainability and to affect the functionality of the Linux-version as little as possible.

\subsubsection{LIMITATIONS}
Some of the features implemented in AODV-UU is not applicable for the NS-2 version. In NS-2 you define addressing information (e.g. IP-address and netmask) per node, which make multi-interface nodes non-trivial. Therefore, support for multiple interfaces is left out in the NS-2 port.

\subsubsection{IMPLEMENTATION}
The implementation of the port has to consider a number of issues to not affect the original code. A first difference is that NS-2 agents are written in the programming language C++ while the original AODV-UU code is written in C. However, C-code can be used in C++ as C is a subset of C++, but C++-code cannot be used in C. Therefore, modifications in the original codebase still needs to conform to C syntax and semantics.

The biggest change in code for the port is in the way packets are handled. The original AODV-UU uses the built in kernel methods like netfilter/iptables\cite{netfilter} to decide what to do with packets, while the NS-2 port needs to use NS-2 methods for passing packets between agents and protocols. The structure of a packet is also quite different between the two versions. A packet in NS-2 is a collection of structs representing headers of a ``real packet''.

Another key issue in the implementation is the way an AODV routing agent / daemon is instantiated. In the original Linux implementation of AODV-UU every node in an ad-hoc network runs a single AODV-UU daemon. The same is valid for the NS-2 version. Every node in the simulation runs an AODV-UU agent, but in this case the whole ad-hoc network is part of the same process on a single computer. This changes the way global variables can be used. As AODV-UU agents on different nodes in the simulation should be completely isolated, no global variables can be used.

The original AODV-UU implementation uses a specific interface as the \textit{Internet interface} when operating in \textit{Internet gateway mode}. Since NS-2 does not support multiple interfaces, but can attach to both wireless and wired channels, the NS-2 implementation uses the address classifier (section \ref{nsnodes}) to support \textit{Internet gateway mode}.

The author of the NS-2 port of AODV-UU, Bj枚rn Wiberg\cite{aodvuuns2}, has chosen a \textit{monolithic class approach}. This means that all source code is placed in a single class, which can be used as a stand-alone class without dependencies to other classes. This method was used because of its simplicity, all existing code just needs to be wrapped into a class definition, which is easily done with \textit{defines} in C/C++. However, this approach may result in a non object-oriented structure with class definition and implementation spread out over many files in the codebase.

\subsubsection{INTEGRATION}
The port introduce a new NS-2 packet type (\texttt{PT\_AODVUU}) and a new NS-2 packet header (\texttt{PacketHeader/AODVUU}). This packet type and packet header are used instead of the AODV control packets over UDP that the AODV draft defines\cite{rfc3561}. This method has become the \textit{de facto standard} in NS-2, mainly because of easier handling in the node classifiers.

To make NS-2 aware of this new packet type and packet header, a patch needs to be applied to the source. This includes modification of several files in the NS-2 code. Except for the definitions and tracers some queues also need patches to recognize the new packet type and header. The complete patch also includes the OTcl code needed for instantiation and default values.

\section{THE PORTING PROCESS}
\subsection{INTRODUCTION}
This introduction will give a brief summary of our procedure to port the AODV-UU code into a NS-Miracle compatible module.
\subsubsection{INITIAL CODE REVIEW}
We started the porting work by doing source code analysis. This gave us basic understanding and the ``big picture'' of the AODV-UU code. It also helped us to determine the scope of the project.

\subsubsection{API INCOMPATIBILITY}
In order to get the source code compatible with NS-Miracle, we had to adapt the code to use the NS-Miracle API. We identified and changed the most obvious incompatibilities.

\subsubsection{STEP BY STEP}
To find the more subtle changes that were needed, we followed different execution paths and changed code elements step by step.

\subsubsection{ADD FEATURES}
The original AODV-UU code has support for multiple network interfaces. The NS-2 port of AODV-UU does not support multiple interfaces due to the experimental support for multihoming in NS-2. We have re-enabled support for multiple interfaces.

\subsubsection{INTEGRATE}