GT Internetwork Topology Models (GT-ITM) Ken Calvert and Ellen Zegura College of Computing Georgia Tech Copyright 1996 by Georgia Institute of Technology. $Id: README,v 1.1 1996/10/04 13:27:52 ewz Exp $ This distribution contains code to generate graphs that model the topological structure of internetworks. In addition, some sample graphs are provided. More detail on most of the methods can be found in the paper: "How to Model an Internetwork," Ellen Zegura, Ken Calvert and Samrat Bhattacharjee, Proceedings of IEEE Infocom '96. The files model.ps and metric.ps in the docs directory also contain brief information on the models and evaluation metrics. The distribution has been compiled for SunOS 4.x. If you are running Solaris, you will need to edit the Makefile (see comments in Makefile for directions), then execute the command 'make veryclean' followed by 'make all'. This distribution consists of the following files: 0. README This file 1. Documentation (docs) README-SGB Overview of Stanford GraphBase itm-doc.txt Instructions on use of itm (graph generation driver) edriver-doc.txt Instructions on use of edriver (graph evaluation driver) sgb2alt-doc.txt Instructions on use of sgb2alt (converts graph format) metrics.ps Description of evaluation metrics models.ps Description of graph models 2. Source files (src) Makefile Makefile (** must be edited to compile under Solaris **) A. Graph generation itm.c Driver to create graphs geog.c Routines to construct various flat random graphs and N-level recursive hierarchical graphs ts.c Routines to construct transit-stub graphs dfs.c Depth first search and connectivity test sgb2alt.c Routine to convert from sgb to alternate format B. Graph evaluation edriver.c Driver to evaluate graph properties eval.c Evaluation routines 3. Include files (include) geog.h Header file for graph generation eval.h Header file for graph evaluation gb_graph.h SGB header for graph data structures gb_flip.h SGB header for system-independent random number gen gb_dijk.h SGB header for shortest path routine gb_save.h SGB header for routines to save and restore graphs 4. Libraries (lib) libgb4.a Library of SGB executables for SunOS 4.x libgb5.a Library of SGB executables for Solaris (SunOS 5.x) 5. Executable files (bin) itm Graph creation executable sgb2alt Format conversion executable edriver Evaluation executable 6. Sample graphs (sample-graphs) A. Random (rand) i. 10 node graphs (r10) r10 Parameter file for 10 node graphs r10-[0-2].gb Random graphs of 10 nodes (SGB format) Runconvert Shell script to run conversion routine r10-[0-2].alt Random graphs of 10 nodes (alt format) Runeval Shell script to run evaluation routines r10-[0-2]-ev Evaluation results for 10 node graphs ii. 100 node graphs (r100) r100 Parameter file for 100 node graphs r100-[0-9].gb Random graphs of 100 nodes (SGB format) Runconvert Shell script to run conversion routine r100-[0-9].alt Random graphs of 100 nodes (alt format) Runeval Shell script to run evaluation routines r100-[0-9]-ev Evaluation results for 100 node graphs B. Transit-stub (ts) i. 100 node graphs (ts100) ts100 Parameter file for 100 node graphs ts100-[0-9].gb TS graphs of 100 nodes (SGB format) Runconvert Shell script to run conversion routine ts100-[0-9].alt TS graphs of 100 nodes (alternate format) Runeval Shell script to run evaluation routines ts100-[0-9]-ev Evaluation results for 100 node graphs ii. 600 node graphs (ts600) ts600 Parameter file for 600 node graphs ts600-[0-9].gb TS graphs of 600 nodes (SGB format) Runconvert Shell script to run conversion routine ts600-[0-9].alt TS graphs of 600 nodes (alternate format) Runeval Shell script to run evaluation routines ts600-[0-9]-ev Evaluation results for 600 node graphs