Trajectory Based Forwarding 

Introduction | Design Document | TinyOS | TBF Viewer | Demo | Papers | FAQ | Misc | Home

Introduction

Simple trajectories can be used in implementing important networking portocols such as flooding, discovery, and network management. Trajectory routing os very effectivein implementing many networking functions in a quick and approximate way, as it needs very few support services. Once TBF is deployed on to any network, packets can be routed along any trajectory specified. The applications of such a versatile forwarding algorithm are limitless, especially in disposable networks where nodes are thrown or dropped to form a one-time use network. 

There are many instances when standard bootstrapping and/or configurations services are not available. In such cases, TBF will serve as an competent substitute. Forwarding based on trajectories decouples the path name from the path itself. Since a trajectory can be specified independently of the nodes that makeup the trajectory, routing can be very effective even when the intermediate nodes that makeup the path fail, or are otherwise unavailable. The specification of the trajectory can be independent of the ultimate destinations of the packet, and thus provides efficient methods for implementing network functions sucha s flooding, discovery and multicast. In the end, we want to be able to specify any routing trajectory and have packets forwarded to all nodes along that trajectory.

Design Document

Before work began on the implementation of TBF, we created a requirements document to help guide us in our work:

Requirements Document [doc]

TinyOS 

The current implementation of TBF is represented by 2 main files other than the tbf.desc file.  We hope to eventually separate TBF into its component parts as to conform to the TinyOS paradigm. However, until that occurs, tbf's main algorithms reside in a supporting C file, and tbf's TinyOS specific code resides in the TBF.c file. 

TBF Viewer (trajectory visualization software)

Along with the TBF implementation on the motes, we have developed a application level layer to both debug and visualize the algorithm. The GUI provides an interface to inject packets as well. It was written in Java to promote portability, and makes use of the Serial Forwarder (provided as part of the TinyOS distribution to handle traffic to and from the serial port).

TBF Viewer Screen Shot [small jpg (30K)] [large jpg (116K)]
TBF Viewer with Vertical Trajectory [small jpg (24K)] [large jpg (96K)]
TBF Viewer with Horizontal Trajectory [small jpg (24K] [large jpg (96K)]
TBF Viewer with Diagonal Trajectory [small jpg (24K)] [large jpg (96K)]

Demo

Our initial demonstration showed very promising results. We were able to specify a trajectory in an injected packet, and see the path of the packet, as each mote toggled a yellow LED indicating it had received a packet. For the purposes of the demonstration, each mote was given its location via an input file. The motes were arranged in a 3 x 3 grid and a packet was injected into the network.

Vertical Trajectory [jpg (214K)]
Diagonal Trajectory [jpg (136K)]

Papers

• Dragos Niculescu and Badri Nath, "Trajectory based forwarding" [pdf]

Miscellaneous

TBF Implementation for NS-2
To use, you need a clean installation of ns 2.1b-9a , with the patch in the root NS directory.

cd ns-2.26
cat ../tbf.1.patch | patch -p1
./configure
make
      

TBF Implementation Paper (coming soon)

FAQ