SNetGen 0.1.2

A set of programs to compute static topologies of various types interesting in
the study of networks.  SNetGen currently supports just two types, I expect to
add more as I have less time for the old python networkx generators to chug
away on large graphs.  Current supported:

* Erdos-Renyi (i.e., p-random)
* Pastry DHT

Both generators create *directed* graphs.  It would be easy to support
undirected graphs, and a future release most likely will.

The Erdos-Renyi generator should be self-explanatory, and the code is very
simple.  The Pastry generator is a bit more complex as it uses a radix tree
to quickly create the core route table.  Both can easily handle N = 100000,
although the memory usage of the Pastry generator could be greatly reduced.
With a couple of gigs RAM, you should be able to hit N > 500000, and future
improvements could easily get it to N = 10^6.

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)

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

gen_er_topo

Need some truly massive Erdos-Renyi graphs and are tired of the existing
generators that are written in slow scripting languages?  The gen_er_topo might
trip your need for speed.


BUILDING


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

Then just type:
  make

You may need to edit the makefile if you have a non-threadsafe version of boost
installed and comment out the appropriate LFLAGS.

Edit the Makefile if you want to change the compile options.  -O3 is quite a
bit slower than -O2 for this application with g++ < 4.4, while -O3 is fast for
4.4+.


INSTALLING

Copy the resulting binary to your favorite bin directory or run locally.  There
is an aborted make install for my own use which will probably not do what you
want.


DETAILS

One day I was super tired of waiting for networkx to spit out some N=100000
Erdos-Renyi graphs, and figured it would be simple to whip up using boost.
Indeed it was, and two hours later (about the time networkx takes to generate 2
graphs), gen_er_topo was ready for business.

The algorithm is what you would expect.  Each edge is considered with
probability p, and added if a random uniform number x < p (as the generation
range is (0, 1]).  Each edge which exists is added to a boost-graph adjacency
list, and then, once all edges are considered, output using the graphviz
writer.

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
                                       standard out
  -x [ --seed ] arg (=0)               sets the random seed
  -p [ --edge-probability ] arg (=0.5) the probability a particular edge exists
  -c [ --force-connected ] arg (=1)    force the resulting topology to be
                                       strongly connected

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

Note that graphs are forced to be connected by default.  Since these generators
are created for network studies, users are expected to be largely interested in
networks where all peers are reachable from all locations.  If this is not the
case, you can set -c false (or -c 0).

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

gen_pastry_topo

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       (to be removed as a dep in a future release)
	libboost-program-options-dev

Then just type:
  make

You may need to edit the makefile if you have a non-threadsafe version of boost
installed and comment out the appropriate LFLAGS.

Edit the Makefile if you want to change the compile options.  -O3 is quite a
bit slower than -O2 for this application with g++ < 4.4, while -O3 is fast for
4.4+.


INSTALLING

Copy the resulting binary to your favorite bin directory or run locally.  There
is an aborted make install for my own use which will probably not do what you
want.


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.