written_report.tex

AODV version of Uppsala University

\documentclass[a4paper]{llncs}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usepackage{url}
\usepackage{llncsdoc}

%% Define a new 'leo' style for the package that will use a smaller font.
\makeatletter
\def\url@leostyle{%
  \@ifundefined{selectfont}{\def\UrlFont{\sf}}{\def\UrlFont{\small\ttfamily}}}
\makeatother
%% Now actually use the newly defined style.
\urlstyle{leostyle}

% Title Page
\title{Porting AODV-UU into NS-Miracle}
\author{Erik Andersson, Emil Ljungdahl}
\institute{Karlstad University}

\bibliographystyle{unsrt}

\begin{document}
\pagestyle{plain}
\maketitle

\begin{abstract}
The NS-Miracle\cite{miracle} (Multi InteRfAce Cross Layer Extension for NS) framework lacks support for AODV (Ad-hoc On-demand Distance Vector) routing. Research projects at Karlstad University need this feature for simulation of wireless Ad-hoc networks. The Network Simulator (NS-2)\cite{ns2} has support for AODV routing, but NS-2 does not meet the requirements in simulation with multihomed nodes. AODV-UU\cite{aodvuu} is a draft compliant Linux implementation of the AODV protocol from Uppsala University. This implementation also includes a port for NS-2. This project has resulted in a port of AODV-UU for NS-2 into NS-Miracle compatible modules. We have also extended the original code to support multiple interfaces. Different simulation scenarios have been created and analyzed to verify functionality of the port. However, simulation tests that cover more technologies and topologies are still needed. Features such as automatic interface discovery and AP-gateway mode are proposals for future work.
\end{abstract}

\section{INTRODUCTION}
In order to establish and maintain connectivity between nodes in an Ad-hoc network, a routing protocol needs to be in place. The routing protocol controls how nodes should route packets in the network. Routing protocols in multihop environments can be divided in three major categories, proactive, reactive and hybrid. One example of a proactive protocol is DSDV (Destination-Sequenced Distance Vector)\cite{dsdv} which determines routes prior any data traffic requests. AODV (Ad-hoc On-demand Distance Vector)\cite{rfc3561} is a reactive routing protocol that only maintain routes when needed. A hybrid protocol uses both proactive and reactive techniques.

Our main objective for this project is to port AODV-UU\cite{aodvuu} for the Network Simulator (NS-2)\cite{ns2} into NS-Miracle (Multi InteRfAce Cross Layer Extension for NS)\cite{miracle} compatible modules. We will also try to extend the original code to better support multihoming. In this report we will give a brief presentation of the AODV protocol and the AODV-UU implementation. We will also cover some basic information about NS-2 and the NS-Miracle framework. Given this background information we will describe the porting process and test results. At the end we will discuss open issues and future work.

\section{MOTIVATION}
The NS-Miracle framework lacks support for AODV routing. Research projects at Karlstad University need this feature for simulation of wireless Ad-hoc networks. NS-2 has support for AODV routing, but does not meet the requirements in simulation with multihomed nodes.

\section{AODV}
\subsection{DESCRIPTION}
AODV (Ad hoc On-demand Distance Vector)\cite{rfc3561} is a routing protocol used in ad-hoc networks by mobile nodes. It is a reactive protocol, which means that no routes are discovered until they are needed. This ensures quick adaption to dynamic link conditions and moving nodes. As only active routes are maintained the AODV protocol uses a small amount of resources. To avoid routing loops at all time it uses destination sequence numbers.

\subsection{ROUTE DISCOVERY}
When data is to be sent to a new node in the mesh, AODV first needs to find a route to this node. AODV broadcasts a RREQ-packet which includes information about the requesting host, the requested host and sequence numbers. To avoid routing loops, a receiving node first checks that it has not received the RREQ before. A reverse route to the requesting node is then set up. If the node does not know about the requested node, it will increment a ``hop count field'' and re-broadcast the request. If the node already know a route to the requested node (or it is the requested node), it will send a route reply message (RREP-message) as unicast back to the previous node in the request chain.

After a while when intermediate nodes know a route to the destination, there is a great chance that the destination node never receives any RREQ-packets, and thus cannot set up a reverse route, which will cause the destination node to send a RREQ-packet before it is able to send a reply message. To avoid this, there is a \textit{gratuitous RREP} flag defined in a RREQ-packet. If this flag is set, an intermediate node which replies to a RREQ-message also needs to send a RREP-message with route information about the requesting node to the requested node.

\subsection{ROUTE MAINTENANCE}
Routes are only kept as long as they are needed. If a route is not used for a certain period of time it is marked as invalid and subsequently removed. To monitor the link availability of routes two techniques are available. The first method is to observing periodically broadcasted \textit{beacons}, called HELLO-messages. The second method AODV supports is \textit{link layer feedback}, such as the one defined for IEEE 802.11 \cite{ieee1997wirelessLAN}.

\section{THE NETWORK SIMULATOR (NS-2)}
This section will give a brief overview of NS-2. Parts that are interesting for the porting work will be described in more detail in section \ref{eoi}.
\subsection{BACKGROUND}
NS-2 is a discrete event simulator that supports simulations of many different network protocols and techniques. Simulations can be conducted over wired LANs and WANs, and in wireless ad-hoc networks. NS development began in 1989 as a variant of the REAL network simulator\cite{real}. In 1995 the project was supported by DARPA, Xerox PARC, UCB, and USC/ISI. Due to its open source nature the project has grown through contributions from network researchers around the world.

\subsection{DESIGN}
The NS-2 core is written in the object-oriented language C++. It is important that the core is capable of manipulate bytes, packet headers and deal with computation logic in an effective way. A compiling language like C++ meets these requirements. In contrast to fast computation logic, the creation and modifications of simulation scenarios need to be flexible. Given these premises the interpreting object-oriented language OTcl\cite{otcl} was chosen as a frontend to the core. The class hierarchies created in the two programming languages are closely related to each other. Objects created in the C++ environment can be made available in the OTcl environment and vice versa. This is done by OTcl linkage. The OTcl linkage also enable the OTcl interpreter to be invoked from C++ code.

\subsection{SIMULATION}
To run a simulation in NS-2 you first need to create a test scenario written in OTcl. The test scenario usually consists of nodes, links and agents. Nodes (fixed or mobile) are connected through links (wired or wireless) and agents (protocols) are attached to the nodes. Scheduling of events instructs the simulator to trigger events at certain points in time during the simulation. One example is that nodeA sends a HTTP GET request to nodeB. The output of the simulation is written to a tracefile. The tracefile could then be analyzed to determine simulation results.

\subsection{ENTITIES OF INTEREST}
\label{eoi}
\subsubsection{NODES}
\label{nsnodes}
A node is composed of several objects. The default unicast node (see figure \ref{ns2nodefig}) contains the following:
\begin{itemize}
 \item an address
 \item a list of neighbors
 \item a node entry
 \item an address classifier
 \item a port classifier
 \item a list of agents
 \item a node type identifier
 \item a routing module
\end{itemize}
\begin{figure}
\includegraphics[scale=0.3,keepaspectratio=true]{ns2node.eps}
\caption{A NS-2 unicast node\label{ns2node}}
\label{ns2nodefig}
\end{figure}
The address is monotonically increasing by 1 (starting with zero) for every node that is added to the simulation scenario. NS-2 addresses consist of a node id and and a port id. Nodes can be addressed in two different ways, flat (one level node ids) or hierarchical (multilevel node ids).

The node entry points to the first element that will handle arriving packets (the address classifier). The address classifier is responsible to route packets. Routing facilities in the routing module helps the address classifier to determine the correct route. If the incoming packet is destined for the current node, the packet will be forwarded to the port classifier. Otherwise the address classifier tries to route the packet to the correct link. The port classifier determines which agent that should receive the packet.

Prior any node creation the simulator needs to be instructed how to create nodes. This is done through the node configuration interface. If no configuration is given the default one will be used.

\subsubsection{AGENTS}
\label{nsagent}
Agents act as endpoints in the simulation environment. This is where packets are constructed or consumed. Agents are used when implementing various network protocols in NS-2. Examples of agents are \textit{Routing agents} and \textit{traffic sinks}. The agent functionality (class \texttt{Agent}) is written in both OTcl and C++. To be able to assign various fields to a constructed packet, each agent holds internal state information. The C++ class \texttt{Agent} holds the following information:
\begin{itemize}
 \item \textbf{addr\_} (node address)
 \item \textbf{dst\_} (where packet should be sent)
 \item \textbf{size\_} (packet size in bytes)
 \item \textbf{type\_} (type of packet)
 \item \textbf{fid\_} (IP flow identifier)
 \item \textbf{prio\_} (IP priority field)
 \item \textbf{flags\_} (packet flags)
 \item \textbf{defttl\_} (default IP ttl value)
\end{itemize}
In order to make two agents (different endpoints) communicate, they need to be connected to each other. This means that the originating agent sets the destination address and destination port to the corresponding agent.

It is possible to attach \textit{applications} to agents, but due to limitations in the API this is not a common used feature. The API between agents and applications might be enough for simple services such as FTP and traffic generators. Application functionality is usually implemented as an agent. 

\subsubsection{QUEUES}