[Back to main Grid page]

The Grid Project: Software

Overview | Download and Run | More Info

This page describes the Grid project DSDV and DSR implementations, and describes how to get started with the Grid software. If you are looking for information about the GLS or capacity simulation code, see our simulation page.


The Grid software implements the DSDV (Highly Dynamic Destination-Sequenced Distance-Vector Routing) and DSR (Dynamic Source Routing) protocols for routing in ad hoc mobile wireless networks. DSDV was designed by Charles Perkins and Pravin Bhagwat; it is described in [1]. The Grid DSDV implementation aims to conform as closely as possible to the protocol as described by Perkins and Bhagwat, and as implemented by the CMU/Rice Monarch group in their wireless extensions to the ns simulator. DSR was designed by David Johnson, David Maltz, and Josh Broch; it is described in [2]. The Grid DSR implementation follows revision 9 of the IETF Internet-Draft specification, following the requirements for networks which require bidirectional links to send unicast data. The DSR implementation is based on one developed at the University of Colorado at Boulder. Both the DSDV and DSR implementations include modifications which allow the protocols to work properly with routing metrics other than minimum hopcount; these changes are described in the MobiCom 2003 paper. The Grid software also implements geographic forwarding and a simple flooding location service, but those protocols aren't described on this page.

The Grid software is implemented as part of the Click modular router. The Grid code is a set of Click elements that can be put together in various ways to run DSDV, DSR, or geographic forwarding. All the routing protocol state (e.g. routing tables, link tables, ARP caches, etc.) is maintained in Click elements, independently of the OS. Protocol state is accessed using through Click.

Because Click can run at userlevel on many different operating systems and machine architectures, Grid also runs on many operating systems and machines. In addtion, Grid can run at kernel level in Linux, using the Click Linux module. The same protocol code is used at userlevel and in the kernel, but the way Grid interfaces to the network devices and operating system is different. More details can be found on the implementation page.

Download and Run Grid

This section describes how to get started with the Grid DSDV implementation at userlevel in Linux and BSD-compatible operating systems. We recommend that you first try to follow these instructions before moving on to trying DSR or using the protocols in the Linux kernel.

The four basic steps are to get the code, compile Click, start the DSDV protocol, and check that it is running correctly. These instructions assume that there are two machines that you want to communicate with each other using DSDV. Downloading and compiling the code is the same for both machines, but running the protocols will be slightly different on each machine.

Download Software

All the necessary Grid software is included in the latest version of Click, available through anonymous CVS. Follow this example to check out the latest version of the code to a directory named `click' in your home directory:

% cd ~
% cvs -d :pserver:anoncvs@cvs.pdos.lcs.mit.edu:/cvs login
CVS password: [just hit enter here]
% cvs -z5 -d :pserver:anoncvs@cvs.pdos.lcs.mit.edu:/cvs co -d click click/release/one

The above example supercedes the instructions on the Click anonymous CVS webpage.

Build Click

The basic steps to build Click are to make sure that you have the neccessary software, correctly configure the Click distribution, and compile the code.

  1. Obtain and Build Required Software

    You need to have a tun driver and the libcap software. The tun driver is enabled by default on most BSD systems. In Linux you will need to make sure your kernel is configured with the `Universal TUN/TAP device' (under `Network device support') or, for older kernels, the `Ethertap device'. The default RedHat Linux kernel includes the Universal TUN/TAP driver. For more detailed instructions, see the files tuntap.txt and ethertap.txt in your Linux kernel's source tree, under Documentation/networking/. You might need to create the /dev/tap0 or /dev/tun device files; check the driver documentation files for more instructions.

    Some systems have libpcap installed, but if yours doesn't, or you aren't sure, download libpcap from tcpdump.org. Configure and compile libpcap according to the libpcap INSTALL file. The rest of the instructions will assume you have compiled the libpcap distribution in ~/libpcap-0.7.1. Example:

    # [assumes libpcap archive downloaded to ~/libpcap-0.7.1.tar.gz]
    % cd ~
    % tar zxvf libpcap-0.7.1
    % cd libpcap-0.7.1
    % ./configure
    % gmake

  2. Configure and Build Click

    Configure and build the Click userlevel driver according to the Click README and INSTALL instructions. Be sure to run autoconf first (to create the configure script), and tell configure where to find the libpcap libaries and headers. If you don't have autoconf installed, you can download it from ftp.gnu.org. Alternatively, there might be precompiled packages available for your system, such as RedHat Linux RPMS or BSD Ports or Packages. Specify the --enable-grid, --enable-analysis, and --enable-wifi options to configure, this will make sure all the required Click elements are built. This example assumes that libpcap is at /home/joeuser/libpcap-0.7.1, and that you are using bash or sh as your shell:

    % cd ~/click
    % autoconf
    % PCAP_INCLUDES=-I/home/joeuser/pcap-0.7.1 PCAP_LIBS=-L/home/joeuser/pcap-0.7.1 \
        ./configure --enable-userlevel --enable-wifi --disable-linuxmodule --enable-grid --enable-analysis
    # [check that configure found your libpcap]
    % gmake

    You can tell that the Click configure program found libpcap by looking for the following lines in the configure output:

    checking for pcap.h... found
    checking whether pcap.h works... yes
    checking for bpf_timeval in pcap.h... no
    checking for -lpcap... found

    Whether running at userlevel or in the kernel, it is useful to install the Click man pages, which have lots of useful information (the man pages are also available as part of the Click online documentation). On most systems you must be root to install the man pages:

    % cd ~/click
    % su
    % gmake install-man 
    % exit


There are three main steps to running the Grid DSDV or DSR protocols: set up the network interfaces; generate a Click configuration, and start Click. This instructions for this step assume that you want to run Grid on two machines, using the IP addresses and, respectively.

  1. Set Up Interfaces

    You can run the Grid protocols on a regular wired ethernet, to get a flavor of how everything works. However, that's not very interesting since every machine can already talk directly to every other machine, so we'll assume you are using some sort of 802.11 wireless interface, and that it is called eth1 on both machines. You'll have to perform the following steps on both machines.

    Bring up your wireless interface (i.e. with a command like `ifconfig eth1 up', and appropriately configure its radio parameters. You'll need to be root to do both of these things. Set the 802.11 interfaces into `ad-hoc' mode so that they can send packets directly to each other without an access point. Also set them all to use the same network name (also known as the `SSID' or `ESSID'), and set the channel or frequency to be the same. On Linux you do all of this using the iwconfig command (part of the Linux Wireless Tools distribution; on FreeBSD/OpenBSD you use either ancontrol/wicontrol or ifconfig. Here is an example on Linux:

    % su
    % ifconfig eth1 up
    % iwconfig eth1 mode ad-hoc essid my-grid-net channel 2
    % exit

    Remember to setup the interfaces on both machines.

  2. Generate Click DSDV Configuration

    Generate DSDV configurations with the ~/click/conf/make-dsdv-config.pl command. By default, this command produces a configuration for the Click Linux module, so specify the -u option to make a userlevel configuration. Also be sure to specify the interface name and IP address:

    # on the first machine
    % ~/click/conf/make-dsdv-config.pl -i eth1 -a -u > /tmp/dsdv1.click
    # on the second machine
    % ~/click/conf/make-dsdv-config.pl -i eth1 -a -u > /tmp/dsdv2.click

    You can use the --help option to see other options for make-dsdv-config.pl.

  3. Start DSDV

    Start DSDV on each node by running the Click userlevel driver with the configuration files produced in the previous step. You'll have to be root. Example:

    # on the first machine
    % ~/click/userlevel/click /tmp/dsdv1.click
    # on the second machine
    % ~/click/userlevel/click /tmp/dsdv2.click

    That should be it! If everything is working right, you should eventually (15--30 seconds) see a message like this on each machine:

    DSDVRouteTable nb: new 1-hop nbr 10.0.0.X -- 00:d0:59:33:db:XX

    This message indicates that the machine has heard the first DSDV route message from the other machine, and you should be able to ping back and forth between the machines, or even login via ssh.

    If DSDV doesn't seem to be working, check the troubleshooting page.

More Information


  1. Charles E. Perking and Pravin Bhagwat. ``Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers''. In SIGCOMM 1994.
  2. David B. Johnson, David A. Maltz, and Josh Broch. ``DSR: The Dynamic Source Routing Protocol for Multi-Hop Wireless Ad Hoc Networks''. In Ad Hoc Networking, edited by Charles E. Perkins, Chapter 5, pp. 139-172, Addison-Wesley, 2001

Last modified: $Date: 2003/08/18 15:29:44 $