gen_pastry_topo

A program to compute the optimal Pastry network from a set of randomly
generated ids.

Cyrus Hall (hallc@acm.org, hallc@lu.unisi.ch)
http://www.inf.unisi.ch/phd/hall/

Licensed under version 3 of the LGPL, as provided in the source code package as
the file COPYING.

Copyright 2009, Università della Svizzera italiana (University of Lugano)

-------------------------------------------------------------------------------

Need to generate a Pastry topology but don't want to write/run a simulation?
Don't need to care about the effects proximity neighbor selection?  Then
gen_pastry_topo might be useful for you.


BUILDING

First, you need the boost C++ library.  In particular, on a debian-based
system, the packages:
  libboost-dev
	libboost-iostreams-dev
	libboost-program-options-dev

Then just type:
  make

Edit the Makefile if you want to change the compile options.  -O3 is quite a
bit slower than -O2 for this application.


INSTALLING

Copy the resulting binary to your favorite bin directory or run locally.


DETAILS

In the fall of 2009 I needed a way to quickly generate Pastry topologies so
that I could run various static experiments on the resulting graphs.  This is
the little piece of code that resulted.  Here's how it works:

 * N random ids are generated using the boost random variate library.

 * Each random id is added to a radix tree (misnamed bit_trie in the source),
   and recorded at each node it visits during insert.  This will allow for fast
	 prefix searches later.

 * For each id the radix tree is used to fill the Pastry route table.  If more
   than one id can be used to fill a particular location, one is selected at
	 uniform.

 * The leafsets are created (if requested).

 * The graph is printed in graphviz DOT format.

The edges in the graph are annotated if they come from the route table with the
source row and column.  Note that the leafset is not generated by default.  If
you want it, you'll probably want to provide the -s option to suppress
duplicate edges between the route table and the leafset.  Note that edges from
the route table are preferred in output over leaves.

Topologies smaller than n = 25 will result in completely connected graphs when
printed with leaves.

The FreePastry defaults for key-length (128 bits), base (4), and leafset size
(24), are used.  You'll need to recompile the program if you want to change
these, as the C++ bitset<>'s size is parameterized by a template parameter.  To
properly fix this would require a bitset class that took its size as a
constructor argument, and since I didn't need to flexibility I just ignored the
problem.  Feel free to fix it and contribute the code.  To change the defaults,
see the following variables:
  common.hh:
    ID_LEGNTH  // Length of the PastryID util class, and therefore all bitsets
		BIT_BASE   // Parameter 'b' in the Pastry paper; the base used is 2^b
	  LEAF_SET_SIZE  // Size of the leafset, if used

The following options are supported, with defaults given by (=default):
  -h [ --help ]                 print this help
  -n [ --num-nodes ] arg (=100) number of nodes in topology
  -o [ --output ] arg (=-)      output filename; '-' directs output to stdout
  -x [ --seed ] arg (=0)        sets the random seed
  -l [ --leaves ]               print the leafset as well as the route table
  -s [ --suppress-dup-leaves ]  suppress leaves that point to nodes already in 
                                the route table; implies --leaves
  -r [ --rename ]               rename peers from 1 to N instead of using the 
                                full pastry id; reduces size of the resulting 
                                graph by ~4x

To get a feel for it, just run the program with no options.  My typical usage
is something like:
  gen_pastry_topo -n 10000 -rs -x <n> -o topo-000<n>.dot
where <n> is a random seed.