%\documentstyle[11pt,fullpage]{article}
%\setlength{\parindent}{0 in}
%\setlength{\parskip}{.1in}
%\setlength{\topmargin}{-0.5in}
%\setlength{\textheight}{8.5in}
%\begin{document}
\chapter{Directed Diffusion}
\label{chap:diffusion}

The directed diffusion module in ns has been ported from SCADDS group's implementation of directed diffusion at USC/ISI. There is an older version of diffusion in ns that was implemented several years back and has become relatively old and outdated. This older version can be found under directory diffusion. And the newer version of diffusion resides under \nsf{/diffusion3}. This chapter talks about the newer diffusion model in ns. The module and methods described here can be found under \nsf{tcl/lib/ns-diffusion.tcl, ns-lib.tcl} and all relevant C++ code can be found under \nsf{diffusion3}. Visit the SCADDS group webpage at \url{http://www.isi.edu/scadds} for details about their implementation.

\section{What is Directed Diffusion?}
Directed Diffusion is a method of data dissemination especially suitable in distributed sensing scenarios. It differs from IP method of communication. For IP ``nodes are identified by their end-points, and inter-node communication is layered on an end-to-end delivery service provided within the network''. Directed diffusion, on the other hand is data-centric. Data generated by sensor nodes are identified by their attribute-value pair. Sinks or nodes that request data send out ``interest''s into the network. Data generated by ``source'' nodes that match these interests, ``flow'' towards the sinks. Intermediate nodes are capable of caching and transforming data. For details on directed diffusion, see  
``Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks'', authored by Chalermek Intanagonwiwat, Ramesh Govindan and Deborah Estrin that appeared in MobiCOM, August 2000, Boston, Massachusetts. This and other diffusion related papers can be viewed at \url{http://www.isi.edu/scadds/publications.html} under publications section.

\section{The diffusion model in ns}
\label{sec:diff_model}

The directed diffusion model consists of a core diffusion layer, a diffusion library provides an application programming interface for overlying diffusion applications and finally the application layer which includes both diffusion applications and filters. The core diffusion layer is used to receive/send out packets from/into the network. The library provides a interface for the overlying application classes for publishing/subscribing etc. These APIs have been described in details in a document called Network Routing API 8.0 and can be found at 
\url{http://www.isi.edu/scadds/publications.html} under APIs section. In the following paragraphs we are going to describe how the diffusion model looks like in \ns.


First we start with a brief description of the diffusion3 directory structure.
If the reader wishes to examine the C++ code related to NS Diffusion
that underpins the OTcl script commands, it may be found in
ns/diffustion3. Here is a summary by subdirectory:
\begin{description}
\item[apps] contains sample source and sink apps; as well as gradient filter.
\item[lib] DiffusionRouting class definitions. Derived from NR, it is the ISI API to diffusion. 
\item[main] DiffusionCoreAgent class definitions. Core diffusion code and other misc/utility code. 
\item[ns] contains ns wrappers for diffusion code. These wrapper classes allow the core diffusion code and the diffusion API to be seamlessly incorporated into the NS class hierarchy.  The DiffRoutingAgent is a wrapper for the Core Diffusion code, and DiffAppAgent is a wrapper for the DiffusionRouting (API) code.
\item[nr] attribute definition and the class NR which is an abstract factory for the API (so that either ISI or MIT implementations may derive from it. 
\end{description}

\begin{figure}[tb]
	\centerline{\includegraphics{filter}}
	\caption{Message flow in directed diffusion}
	\label{fig:filter}
\end{figure}


The above Figure~\ref{fig:filter} is from SCADDS' network routing API document available from their homepage (URL given earlier). The document describes attribute factories, matching rules for attributes, how applications interface with the core diffusion layer, and filter/timer APIs. All messages coming from/going out in the network is received at/sent out from the core diffusion layer. Messages can also come to core-diffusion layer from local applications and/or filters that might be connected to the node. The applications use the publish/subscribe/send interface to send interest and data messages to the network.

%\begin{figure}[tb]
%	\centerline{\includegraphics{directeddiffusion}
%	\caption{Schematic of a mobilenode supporting directed diffusion}
%	\label{fig:diffusion-node}
%\end{figure}

The above Figure~\ref{fig:diffusion-node} shows the internals of directed diffusion implementation in \ns. The core diffusion agent and diffusion application agent are attached to two well-known ports defined in \nsf{/tcl/lib/ns-default.tcl}. Diffusion applications attached to the node call the underlying diffusion application agent for publishing/subscribing/sending data.

\section{Some mac issues for diffusion in ns}
First of all, all diffusion packets in ns are broadcasted. In the shim layer that sits between diffusion and ns, (see diffusion3/ns dir for code implementing this layer) all diffusion packets are encapsulated within ns packets and are marked to be broadcasted.

This can result in some problems at the mac layer. The mac-802.11 doesnot try to re-transmit a broadcast packet incase there is a collision and the packet is dropped. Coupled to this was the fact that mac-802.11 didn't do random selection of slots in the contention window before it transmitted a packet (a brdcast data or rts for unicast pkts). As a result there were a high number of collisions at the mac layer and a lot of packets were lost. This was fixed by adding random selection of slots before mac tx'ed a brdcast pkt (or a rts pkt).

However if we have a large and dense topology, there is a chance that two or more nodes may select the same slot in the mac contention window (the contention window size varies from 31 to 1023 for DSSS PHY MIB specifications). Thus now we need to add some extra jitters at the higher application layer. Diffusion has a provision to do this by compiling ns with the macro USE\_BROADCAST\_MAC. 
What this does is it in addition to delaying certain messages (to avoid collisions), when run with a BROADCAST MAC layer, diffusion will use a different set of values for delays and jitters. These different delay/jitter values are defined under diffusion3/lib/main/config.hh. Since this might increase the latency 
you might want to fine-tune the delay values by hand. 


\section{Ping: an example diffusion application implementation}
\label{sec:ping_app}

There is a ping application implemented under diffusion3/apps/agents subdir. The application consists of a ping sender and receiver. The receiver requests for data by sending out ``interest''s in the network. The interests get diffused through the network. The ping-sender on receiving matching interests, sends out data. 


\subsection{Ping Application as implemented in C++}
\label{sec:ping_cpp}

The ping-sender and -receiver classes, namely PingSenderApp and PingReceiverApp both derive from DiffApp, the parent class for all diffusion based applications. See diffusion3/lib/diffapp\{.cc,.hh\} for detailed implementation of the DiffApp class.

The ping-sender uses MySenderReceive object that handles all callbacks for it. Also the ping-sender defines two functions setupSubscription() and setupPublication(). 
The first function creates interest attributes that matches with data attributes it (the sender) has to offer. Next it calls the dr-library function subscribe(). The subscription is used by the ping-sender to create an internal state against which attributes for interests received from the network are matched against. Incase of a match, the matching data is sent outinto the network. Function setupPublication() create attributes for the data it has to offer and calls the library function publish() which inturn returns a publish handle. The ping-sender uses this handle to periodically send out data which is forwarded by the gradient to core-diffusion to be sent out into the network only if it finds a matching interest.

The ping-receiver object uses a similar callback object called MyReceiverReceive. And it defines a function setupSubscription() that creates attributes for the interest the receiver will be sending. Next it calls the dr library supported subscribe() which sends the interest out into the network. The recv() function is used to recv matching data and the receiver then calculates the latency for each data packet received from the ping-sender.
The ping sender can be found under ping\_sender{.cc,.h}. And the ping\_receiver is implemented under ping\_receiver{.cc,.h}. Some common defines and attribute factories for data/interest attributes are defined in ping.hh and ping\_common.cc.

\subsection{Tcl APIs for the ping application}
\label{sec:ping_tcl}

An example script for the ping application is under \nsf{tcl/ex/diffusion3/simple-diffusion.tcl}. The example scenario consists of 3 nodes of which one is a ping-sender and another is a ping-receiver. The source and sink nodes are far away from one another and communicate only through a third node. The option adhocRouting is defined as Directed\_Diffusion. This enables a core-diffusion agent to be created during the time of node creation. Also it creates a diffusionApplication agent if one is not present already. And a gradient filter is attached by default to each diffusion-enabled node. 

The ping sender application is created in the following way:
\begin{program}
set src_(0) [new Application/DiffApp/PingSender]
$ns_ attach-diffapp $node_(0) $src_(0)
$ns_ at 0.123 "$src_(0) publish"
\end{program}

The first line creates a ping-sender object. Simulator class method attach-diffapp basically attaches the application to the underlying diffusionApplication agent for that given node.
The command \code{publish} essentially ``starts'' the sender application.

Similarly the ping sink is created as follows:
\begin{program}
#Diffusion sink application
set snk_(0) [new Application/DiffApp/PingReceiver]
$ns_ attach-diffapp $node_(2) $snk_(0)
$ns_ at 1.456 "$snk_(0) subscribe"
\end{program}

The command \code{subscribe} once again starts the ping-receiver application.

Thus in order to create your own application, you need to :
\begin{description}
\item[1.] define attribute-factories and attributes for application interest/data.
\item[2.] create the application class (using dr-library APIs)
\item[3.] add tcl commands to start the application
\end{description}

See \nsf{tcl/lib/ns-lib.tcl, ns-diffusion.tcl} for implementations of OTcl hooks for directed diffusion. Alo see chapter on Mobility in this manual for details on mobility model and wireless simulations in \ns.


\section{Test-suites for diffusion}
\label{sec:test_diff}

Currently we have a simple testcase under \nsf{tcl/test/test-suite-diffusion3.tcl}. In future we plan to extend the test-suite for testing different components/functionalities of directed diffusion.

\section{Commands at a glance}
\label{sec:directeddiffusion}

Following is a list of commands used for diffusion ping application. Similar APIs can be used for extending to other diffusion applications.

\begin{program}
$ns_ node-config -adhocRouting $opt(adhocRouting) 
	         -llType $opt(ll)
	         ...
where,
value of opt(adhocRouting) is set to Directed_Diffusion
\end{program}
This command is used to enable directed diffusion in wireless nodes.

\begin{flushleft}
\code{ set src [new Application/DiffApp/PingSender]}\\
This command is used to create ping-sender application.

\code{set snk [new Application/DiffApp/PingReceiver]}\\
This command is used to create ping-receiver application.

\code{$ns_ attach-diffapp $node_ $src_}\\
where the diffusion application \code{$src_} gets attached to the given \code{$node_}.

\code{$src_(0) publish}\\
Command to start a ping source (sender).

\code{$snk_(0) subscribe}\\
Command to start a ping sink (receiver).

\end{flushleft}
%\end{document}
\endinput
