GridG: Synthesizing Realistic Computational Grids

GridG is a generator of synthetic computational grids. We model a grid as a network topology graph whose nodes and links are annotated with the available hardware and software. GridG is currently described in the following two papers, with the latest one covering new advances and more details:

GridG is a part of the URGIS Project at Northwestern University, which is researching grid information service systems based on the relational data model. The following papers give an example of how GridG can be used to evaluate such systems:

GridG can also be used to evaluate overlay networks and P2P systems:

GridG has two components: a topology generator and an annotation generator.

Recent research shows that many natural and artificial networks follow the so-called outdegree power law. In particular, it has been shown that the Internet follows this power law, as does the peer-to-peer sharing overlay network Gnutella. Like the Gnutella network, future grids will be embedded in the Internet topology and thus will likely follow its rules. It is also well-known that the Internet has a structured topology. GridG generates topologies that are both structured and follow the outdegree power law (and, consequently, other power laws). We used the well known Tiers tool (M. Doar, A Better Model for Generating Test Networks, GLOBECOM 1996) to generate a basic structured graph and then add additional links to force it follow the outdegree power law. While developing GridG, we found some interesting relations among the four power laws of the Internet topology, the details of which are presented in the above paper.

The annotation generator annotates the routers, hosts, and links in the graph with attributes such as memory size, number of CPUs, disk size, bandwidth, etc. There are correlations among the attributes of a host, and also among the hosts which are near to each other on the network. For example, a host with a large number of CPUs is likely to have a large memory, and hosts on the same LAN are likely to have the same operating systems. To capture such intra-host and inter-host attribute correlations, GridG's annotator supports user-supplied conditional probability rules. We provide a set of such rules in the distribution.

GridG is implemented in Perl as a sequence of transformations on a text-based representation of an annotated graph. A binary version of Tiers for the Linux platform is included.

Source Code

Download version 1.0.


Effort sponsored by the National Science Foundation under Grants ANI-0093221, ACI-0112891, ANI-0301108, EIA-0130869, and EIA-0224449. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation (NSF).

Questions? Comments? Bug reports? Contact: Dong Lu or Peter A. Dinda