| configuration | - Software configuration
To allow as accurate a comparison as possible, we needed the implementations
of the four algorithms to be as similar as possible. If one algorithm operated
in kernel space and another operated in user space, for example,
it would not be possible to attribute any difference in packet latencies solely
to the way in which an algorithm finds and uses its routes. For this reason,
although we used existing source code as a guide in all four cases, we implemented
each algorithm from scratch so that we could minimize any implementation
differences. There are four key features that the implementations have in common.
Key Feature 1.
All four algorithms are implemented as user-level applications through the use of
a tunnel device. The tunnel device, which we ported from FreeBSD, provides a network
interface on one end and a file interface, specifically a /dev entry, on the other
end. Each node is assigned two IP addresses, one associated with the physical network
device, and one associated with the tunnel or virtual network device.
Applications use the virtual IP address, routing algorithms use the physical IP address,
and the standard Linux routing tables route all virtual IP addresses to the virtual
network interface. Any application-level packets, therefore, are directed through
the tunnel, and the routing algorithms read those packets from the file end of the tunnel.
The tunnel allowed us to avoid any implementation work at the kernel or
driver level, and also to switch from one routing algorithm to another
(during experiments) simply by stopping one user-level process and
starting another. The drawback of our approach is the additional overhead
associated with moving packets between kernel and user space.
Our laptops, however, had more than enough capacity for our experiments,
and thus we chose implementation simplicity over maximum performance.
Key Feature 2.
All four algorithms use UDP for traffic destined
for a specific neighbor and multicast IP for traffic that should reach
every neighbor. Multicast IP, as opposed to broadcast IP, allows us
to run multiple routing algorithms at the same time without adding
filtering code to every algorithm, a useful feature in some of our
earlier experiments. Each algorithm simply subscribes to its own
multicast address.
Key Feature 3.
All four algorithms use an event loop that invokes
algorithm-specific handlers in response to (1) incoming UDP
or multicast IP network traffic or (2) the expiration of route or other
timeouts. As with user-level routing, the event-loop approach leads
to additional overhead, but allows more straightforward implementations.
Key Feature 4.
All four algorithms are implemented in C++ and
share a core set of classes. These classes include the event loop, as
well as unicast and multicast, routing, and logging support.
With these four key features, algorithm-specific code is confined
to the packet handler classes that process incoming control and data
packets, the timer handler classes that process timed actions (such
as route expiration), the logging classes that log algorithm events,
and utility classes that serialize and unserialize control packets.
Minimizing the algorithm-specific code simplified implementation
and debugging, and should make the routing results as independent
of a particular implementation choice as possible.
- Traffic generation
The routing algorithms themselves are not enough for an experiment,
of course. A traffic generator runs on each laptop, and
sends a sequence of packet streams to randomly selected destination
laptops. Each stream contains a random number of packets of
a random size. Two Gaussian distributions determine the packet
numbers and sizes, two exponential distributions determine the delay
between streams and packets, and a uniform distribution determines
the destination laptops. A GPS service also runs on each
laptop, reading and recording the current laptop position from the
attached GPS unit, and broadcasting beacons that contain the laptop's
position (as well as sequence-numbered positions that it has
received from other laptops). We thus are flooding the GPS beacons
through the network, an appropriate choice in our application
domain where soldiers and first responders need to see a continuous
view of each other's positions. In addition, broadcasting the
beacons allows us to build a connectivity graph, independent of any
particular routing algorithm, as to which laptops actually can hear
which other laptops. Finally, we use a set of Tcl scripts to setup
and run the experiments.
- Parameter configuration
The best parameters for the four routing algorithms could not be
determined precisely beforehand, since there are no experiments of
this size for which data is available. Instead, we used values that
gave effective results in published simulation studies or that were
set as default values in the sample source code obtained from the
developers. We did adjust some values to achieve some degree of
consistency between the algorithms, however.
Summarizing the major parameters, APRL recorded up to seven
routes per destination, one primary and six alternates, broadcast
its beacons every 6 seconds, and expired any route that had not
been refreshed by a beacon within the last 12 seconds. STARA
broadcast a neighborhood probe every 2 seconds, sent a DDP if a
path had gone unexplored for 6 seconds, removed a neighbor from
a node's neighborhood set if two successive neighborhood probes
passed without an acknowledgment, and weighed delay estimates
by 0.9 on each update to exponentially forget old delay information
as new information became available. AODV broadcast each
RREQ twice, expired a route if it had not been used in 12 seconds,
sent a HELLO every 6 seconds, and removed a neighbor
from a node's neighborhood set if it did not receive two successive
HELLOs. ODMRP refreshed an in-use route every 6 seconds,
and expired a route (forwarding group) if it had not been used for
12 seconds.
As can be seen, these parameters reduce to 6 seconds between
beacons, HELLO messages or route refreshes for APRL, AODV
and ODMRP, and 12 seconds for a route to time out for APRL,
AODV and ODMRP, either by direct timeout or by failure to receive
two successive HELLOs. Using equivalent values for STARA,
however, led to unacceptably slow convergence of the delay es
timates, particularly given the fifteen-minute window available to
us for each algorithm. Reducing the parameters improved convergence,
but at the expense of even more control overhead, an effect
that we consider below.
- User mobility
The laptops moved continuously during the experiment. At the
start of the experiment, the participants were divided into equalsized
groups of ten, each participant given a laptop, and each group
instructed to randomly disburse in one of the four sections of the
field (three upper and one lower). The participants then walked
continuously, always picking a section different than the one in
which they were currently located, picking a random position within
that section, walking to that position in a straight line, and then repeating.
This approach was chosen since it was simple, but still provided
continuous movement to which the routing algorithms could
react, as well as a similar spatial distribution across each algorithm. |
| format | The tarball contains both trace (under "Trace" directory) and the software
that was used to collect the trace (under "Software" directory.)
1. Trace
The trace consists of 41 directories corresponding to 41 nodes
(node 1-40, and a master control node).
Each node directory (e.g., 1) has four sub-directories:
- AODV: traces of AODV experiment
- APRL: traces of APRL experiment
- ODMRP: traces of ODMRP experiment
- STARA : traces of STARA experiment
- gps_tcpdump: traces of GPS readings and tcpdump
---------------
In gps_tcpdump directory (e.g., under a directory of node 1),
you can find the following files:
full/beacon.log: beacon logs in binary format
full/position.log: position logs in binary format
full/position.log.parsed: each line in a format of [time] [x-coord] [y-coord] [z-coord]
full/position.log.stripped: with bogus positions removed from position.log.parsed,
each line in the same format as position.log.parsed
full/signal.log: signal logs in binary format
monitor.stderr: stderr file used by monitor app
monitor.stdout: stdout file used by monitor app
tcmpdump.stderr : stderr file used by tcpdump app
tcpdump.stdout: stdout file used by tcpdump app
tcpdump.dat.gz : tcpdump file
---------------
In each of PROTO (= AODV, APRL, ODMRP, and STARA) directories (e.g., under a directory of node 1),
you can find the following files:
- 10.0.0.1.PROTO.data.out: transmission logs in binary format
- 10.0.0.1.PROTO.data.parsed : user-level (through the use of tunnel device) transmission logs in text format
- 10.0.0.1.PROTO.out: routing-level transmission logs (including control packets) in text format
- 10.0.0.1.trafgen.out: generated traffic logs in binary format
- 10.0.0.1.trafgen.parsed: generated traffic logs in text format
- trafgen.stderr: stderr file used by trafgen app
- trafgen.stdout: stdout file used by trafgen app
- PROTO.stderr: stderr file used by PROTO app
- PROTO.stdout: stdout file used by PROTO app
Among these, 10.0.0.1.PROTO.data.parsed and 10.0.0.1.trafgen.parsed have the following format:
There are four types of line entries:
TIN [size] [seconds portion of timestamp] [usecs portion of time stamp] [src] [dest] [seq #]
SIN [size] [seconds portion of timestamp] [usecs portion of time stamp] [src] [dest] [previous_hop_ip] [seq #]
TOUT [size] [seconds portion of timestamp] [usecs portion of time stamp] [src] [dest] [seq #]
SOUT [size> [seconds portion of timestamp] [usecs portion of time stamp] [src] [dest] [previous_hop_ip] [seq #]
The TIN (In from Tunnel) entries describe a packet that was generated by this node's
traffic generation process and that is being passed down to the
routing layer to be sent out on its way.
The TOUT (Out over Tunnel) entries describe a packed generated by a traffic generation
process arriving safely at its destination
The SIN (In from Socket) and SOUT (Out over Socket) entires describe
the transmission and receipt of a traffic generation packet, respectively,
at a hop-by-hop level. That is, if a packet is generated by the traffic
gen program at node 1 bound for node 3, and to get there it bounces
from 1 to 2 then 2 to 3, then you will see a TIN for this packet at 1,
a TOUT at 3, and a SOUT at 1, SIN at 2, SOUT at 2, and SIN at 3.
2. Software
---------------
FILES and DIRECTORIES
The software consists of the following four directories:
- AODV: AODV protocol implementation
- APRL: APRL protocol implementation
- ODMRP: ODMRP protocol implementation
- STARA : STARA protocol implementation
- analysis: scripts used for trace analysis
---------------
OVERVIEW of routing protocols
A short overview of the four routing algorithms (AODV, APRL, ODMRP, and STARA)
is available in Section 2 of [gray-outdoor]:
http://www.cs.dartmouth.edu/~dfk/papers/gray:compare.pdf
---------------
BUILD - how to `make` each protocol
To build each protocol (say AODV), first `cd AODV` and edit the makefile's definition
for the "depend" target. Change the path to the standard header include directory used
by your compiler (e.g., "/usr/include/g++-2/" for g++ on actcomm) to whatever it is
on the machine you're compiling on. Then just run "make depend" and "make" inside
the AODV/ directory. If everything goes well, an executable named AODV and will
appear in the directory.
---------------
USAGE - how to run each protocol
To run a protocol (say AODV) simply run the command "./AODV <conf_file> (assuming that
AODV and <conf_file> are in the current working directory). You can rename the <conf_file>
to anything you wish, as long as you pass the correct name of the file as the argument to AODV.
If a protocol was compiled with debugging, detailed messages will be printed to the
standard output; you can send them to a file instead by using the "> redirect
operator. All error messages are output to standard error.
The following parameters and values are specified in <conf_file>
- AODV
(The required parameters are:)
LOCAL_IP = Local IP address.
MAX_DATA_PACKET_QUEUE_SIZE = Maximum size for the data packet queue.
MAX_AODV_PACKET_SIZE = Maximum size for AODV
MAX_DATA_PACKET_SIZE = Maximum size for data packets.
NET_DIAMATER = maximum expected diameter of the MANET. Used in discovery.
NODE_TRAVERSAL_TIME = expected time for a packet to transit a -node-
TTL_THRESHOLD = Number of TTL values for RREQ packets.
RREQ_RETRIES_WITH_TTL_AT_NET_DIAMETER = Number of RE-broadcasts for RREQ packets.
ACTIVE_ROUTE_TIMEOUT = Lifetimes for routes and cache entries.
HELLO_INTERVAL = Broadcast interval for Hello messages.
ALLOWED_HELLO_LOSS = lifetime for Hello messages.
(The optional parameters are:)
NET_TRAVERSAL_TIME = expected time for a packet to transit from one side of
the network to another (i.e., across the maximum expected hops). Typically not
specific in the config value. Calculated from NET_DIAMETER and NODE_TRAVERSAL_TIME
TTL_START, TTL_INCREMENT = start and delta ttl values.
LISTEN_TO_INPUT_FILE = ListenToTable input file
POSITION_INPUT_FILE = PositionTable input file
- APRL
(The required parameters are:)
localIP = the local IP
(The optional parameters are:)
logfile = name of a file for logging info
err_logfile = name of a file for logging errors
block_size = the maximum segment size of the network
route_cap = the maximum number of routes to any destination that are stored in the routing table
report_interval = the interval, in msec, at which we beacon the routing table
caching = (0 or 1) whether we're caching reverse hop data for PSVNs
buffering = (0 or 1) whether we are buffering packets
delay = the interval, in msec, after which reverse hop data times out
data_logfile = the log file in which to log info about data traffic
data_log_bufsize = the size of the buffer used in our buffered binary logging scheme
ListenTo_config_file = name of a file to set up the ListenToTable with
Position_config_file = name of file to set up the PositionTable with
- ODMRP
LOCAL_IP = IP address of the local node
MAX_DATA_PACKET_SIZE = maximum size of a data packet in bytes (including IP hhead)
MAX_DATA_PACKET_QUEUE_SIZE = maximum number of data packets that we will queue.
We drop data packets if the queue is full
NET_DIAMATER = maximum expected diameter of the MANET. Used in discovery.
NODE_TRAVERSAL_TIME = expected time for a packet to transit a -node-
(in device to out device). Used in discovery.
NET_TRAVERSAL_TIME = expected time for a packet to transit from one side of
the network to another (i.e., across the maximum expected hops). Typically not
specific in the config value. Calculated from NET_DIAMETER and NODE_TRAVERSAL_TIME
TTL_START, TTL_INCREMENT, TTL_THRESHOLD = start, delta, and max ttl values. Used in discovery.
JOIN_QUERY_RETRIES = number of times to retry a JOIN query. Typically not
specified in the config file. Instead calculated from the three TTL
parameters (i.e., increasing TTL values from TTL_START to TTL_TRHESHOLD by
TTL_INCREMENT step size; always at least 1 retry no matter the values)
JOIN_QUERY_RETRIES_WITH_TTL_AT_NET_DIAMETER = after reaching TTL_THRESHOLD,
ODMRP will try the JOIN query this many more times with the ttl set to the
net diametera
FWD_GROUP_LIFE = timeout on a forwarding group, i.e., node will stop being
a forwarder if the group information is not refreshed within this timeout.
Timeout in milliseconds.
REFRESH_INTERVAL = interval at which we refresh forwarding info. Involves
network traffic. Should not be too small. Must be smaller than FWD_GROUP_LIFE
(typically 2x to 3x smaller) for protocol to be stable. Timeout in milliseconds.
REV_ROUTE_LIFE = timeout on a forearding group. Timeout in milliseconds.
- STARA
NUMBER_OF_HOSTS = The number of hosts in the ad hoc network
LOCAL_IP = The IP address of the host computer
MAX_ACK_HOPS = The number of hops that a flooded acknowledgement
can travel before it dies. If set to 1, this will require bidirectional links
to form routes
PROBE_REPEAT_DELAY = The amount of time, in msec, between the sending of
NeighborhoodProbes to other nodes.
DELAY_TOO_OLD = The amount pf time, in msec, before a route's delay
estimate is considered to be too old. After this time,
a DummyDataPacket will be sent to explore the route
PACKETS_BEFORE_LINK_FAILS = The number of packets that can be sent to a node, without
acknowledgement, before the link is determined to have failed
IP_LIST_FILENAME = The name of the file (must be in same directory as this file)
That contains a list of the IP addresses of all the hosts in the ad hoc network
MULTICAST_GROUP = The multicast group
MULTICAST_PORT = The port that is used for sending via multicast (for NeighborhoodProbes and ACKs)
CONTROL_PORT = The port that is used for sending via unicast for all other control packets)
DATA_PORT = The port that is used for sending via unicast (for all data packets)
MTU = the maximum transfer unit for this network
FORGETTING_FACTOR = the exponential forgetting factor for delay updates.
This is a floating-point number between 0 and 1. The
smaller it is, the more weight is given to older
delay estimates when incorporating new measurements
into the expected delay for a route
TTL = Time-To-Live for DataPackets and DummyDataPackets in the
network. This is to prevent looping -- any packet that
has not reached its destination after this many hops
will be dropped.
MIN_DELAY = This value is used for normalizing the delays for probability
calculation purposes. It should be small enough that the
delays maintain differentiation, but large enough that they
are not overly differentiated.
ListenTo_config_file listen = The location of the listen-to-table configuration file,
if one is being used for simulation purposes.
---------------
USAGE - analysis scripts
The stats.tcl program produces summary statistics from a wireless run's
raw event data. The stats.tcl uses the parsed (text) files, not the unparsed
binary log files.
Before running stats.tcl, please make sure that the variable c_gnuplotExecutable
in conf file (e.g., stats-20031017.conf) is set to a correct path of your
gnuplot executable on your system.
stats.tcl takes five arguments, e.g.,
./stats.tcl ./stats-20031017.conf AODV 30 ../../Trace ./analysis-20031017
The first argument is the configuration file.
The second argument is the routing protocol for which you want statistics.
The third argument is the size - in seconds - of the data aggregation buckets,
e.g., generated graphs will summarize the data at this granularity.
The fourth argument is the directory that contains the parsed data files
from the run. This directory refers to one of the outdoor datasets that you
downloaded from crawdad.
The fifth argument is the directory in which you want to put the output
files, text and gnuplot graphs. stats.tcl creates this directory if it
does not exist.
The stats-20041013.conf file is an example configuration file. The
modifiable fields in this configuration file are:
c_gnuplotExecutable = the path of your GNUPLOT executable
c_templateDirectory = the directory that contains the .template files (same directory that contains stats.tcl)
c_dummySequence = a starting sequence number for DROP events (for which we did
not record a sequence number in the raw data)
c_algorithms = the valid routing protocols. Used only for additional error
checking.
c_excludedLaptops = laptops (i.e., node ids, which correspond to the
subdirectory names in the dataset) to exclude from the summary statistics |
