Graham Phillips' contributed utilities:

1. An Active-Network Execution Environment

This project is part of a DARPA initiative to study active-networking. The term active-networking refers to packets that are active in the sense that they contain code, rather than passive data. The code is then executed at each hop in the network.

We are using Java byte-code as the language for active packets. In this regard, we have re-implemented our RSVP code in Java and we have also designed an execution environment (written in Java wherever possible and C otherwise). The main function of the execution environment is to accept packets, to load any code that is not available locally and to execute the code contained therein. The execution environment also provides a programming interface to active code, much like the JDK provides an interface to Java applications. The difference is that our interface contains additional functions that are useful for networking applications. The source code for the execution environment is located at http://www.isi.edu/active-signal/ARP/.

2. SimScripts

SimScripts is a set of scripts for invoking multiple programs (typically simulations) on multiple machines. The SimScripts computational model is that a central machine schedules (or pushes) jobs on multiple machines. This model is in contrast to worker machines that fetch jobs from a central job queue. Our model will not scale to hundreds of machines, nor is it suitable for invoking short-lived jobs. However, our push model implementation is very simple (currently under 800 lines of 'sh') and robust.

The scripts are written in 'sh' and 'awk' and have been tested on Solaris and FreeBSD. Basically, you need to create a number of command scripts (in 'sh') containing the commands for your particular simulation, and then SimScripts will start scheduling these command scripts on remote machines. Tasks will be scheduled until all command scripts have completed. Apart from scheduling, SimScripts takes care of some other things such as stdin and stderr for each command script and recording any errors.

The scheduling model is quite simple, and in particular there is no CPU load-balancing. For more information see the SimScripts home page at http://netweb.usc.edu/simscripts/. SimScripts was co-authored with Pavlin Radoslavov.

3. Topology utility programs

These topology utilities where used in the following paper:
Graham Phillips, Scott Shenker and Hongsuda  Tangmunarunkit. Scaling of Multicast Trees: Comments on the Chuang-Sirbu scaling law (.ps). | Abstract (.html) In SIGCOMM '99, Boston , USA, August 31-September 3, 1999.

The Stanford Graph Base (SGB) topology format was used for all our topology simulations. The Stanford Graph Base package defines a file-based topology format as well as C structures. The SGB package includes various library routines for manipulating the C structures as well as SGB topology files representing data from various sources (eg. coordinates of cities in the USA).

The text "The Stanford GraphBase: A Platform for Combinatorial Computing" is available from the Addison-Wesley Publishing Company (ISBN 0-201-54275-7) and may be available in your local library. The source code as well as more information on the Stanford Graph Base can be found at ftp://labrea.stanford.edu/pub/sgb/. I suggest reading the book first because it is far more comprehensive than any documentation on the ftp site.

The advantage with using SGB is that it provides functions to convert topologies from file format to C structures and visa-versa. Another advantage is that the SGB library includes routines to find shortest distances and compute spanning trees etc., so one can reuse code. Although I recommend using the SGB topology format, the SGB C structures do have limitations. For example, one of the problems is that if you want to store per node state in the SGB C structures there are only a limited number of utility variables (see the SGB documentation). I didn't need extra state variables in my simulations, but if you do need such state then it might be better to design your own C structures (and then have code to convert from the SGB C structures to your C structures).

My recommendation is to use SGB to represent the topologies as files, but whether you use the SGB C structures or your own structures depends on the problem, and how general you want to be. You could use ns too, but ns is a more general purpose simulator and includes an event-scheduler. We have found that event-scheduling becomes burdensome for topologies greater than 50000 nodes and so our methodology has been to abstract the problem to avoid using an event-scheduler. Obviously, some accuracy is lost in this abstraction step, but much larger topologies can be studied.

The itm topology generator outputs SGB files, but some other generators, such as tiers (written by Mathew Doar) do not. In those cases where the generator does not produce SGB files, I have written converter programs to convert topology files to an intermediate form, which I call an adjacency-list form. I then use 'adj2sgb' (below) to construct the SGB topology file.

All the topology utilities listed below are bundled in sgb_utils.tar.gz. All the real and generated topologies for the above paper (as well as other topologies) are bundled in sgb_topologies.tar.gz.

3.1 Topology converters

The following programs convert topologies from one format to another. I use an adjacency-list format as the "common language" with which to convert any topology to any other topology. The adjacency-list format has the following structure. The first line contains two numbers, the number of nodes and the number of links in topology. Each remaining line represents a link and contains at least two entries, the first two entries are the names of the node (usually strings, but may be just numbers) that the link connects and an optional third number is the length of the link.

adj2nam converts from an adjacency-list format to a nam format. Nam is a Tcl/TK based animation tool for viewing simulation traces and topologies.
adj2sgb.c converts from an adjacency-list format to SGB format.
sgb2adj.c converts from SGB format to an adjacency-list format.
edges2adj converts a file containing a list of edges (represented by two columns) to an adjacency-list format.
mbone2adj converts from ISI's mbone format to an adjacency-list format.
tiers2adj converts from the Tiers topology generator output to an adjacency-list format.
sgb2ns converts from the SGB to ns format. This utility is not bundled in the above mentioned tar file, but is available from the ns web site of contributed modules.

3.2 Topology construction

star.c creates a star topology in SGB format.
string.c creates a string topology in SGB format.
nary_tree.cc creates an nary-tree in SGB format.
remove_dup_edges creates a new topology (in .adj format) by removing all duplicate edges from an existing topology (in .adj format).
sgb_uni2bi.cc creates a new SGB topology such that any unidirectional edges are converted into bi-directional edges.

3.3 Topology checking

connected.c determines whether an SGB topology is fully connected.
sgb_any_uni_edges.c determines whether there are any edges in an SGB topology that are unidirectional only.
sgbpeek.c pretty-prints an SGB topology.

4. Unix shell scripts

A 'sh' script, called findfile, to find executable files on a Unix system by collating search paths from various sources including the user's PATH environment variable and the 'whereis' command.

A 'sh' script, called strrep, to replace strings, given as a 'sed' regular expression, in a list of files.

5. Traceroute utility

A perl script, called traceAS, to determine the path of ASs (autonomous systems) for a given traceroute output. It works by using the 'whois' program on the machine 'radb.ra.net'. There is an example output documented in the script itself. For example, try 'traceroute www.uct.ac.za | traceAS'. There are some more AS utilities at http://www.isi.edu/ra/.

6. Dynamic array bounds-checking

Some C++ code to implement arrays that perform bound checking at runtime. There are classes for single dimensional and two dimensional arrays. (See the README file.)

7. Web page construction

Here is a web page containing a list created from simple Perl scripts and a simple text-based database called JDB (written by John Heidemann). The Perl scripts basically do a mail-merge-like function found in most word-processors. The template file defines the format of the resultant file, but includes special tags that are used to invoke arbitrary programs (that you then write) to process entries in the database. Its is extremely simple, but saves a great deal of time. In the example, the template is template.html (view it as ascii not html because there are some html comments that contain the special tags), the database is members.db (in JDB format) and the perl program that does the merge is pmerge.
Home page