Available Topology Generators

There are several topology generators available to the research community. Some of them mainly aim to generate random topologies [25], others aim to imitate the hierarchical properties of the Internet [5,8], and still others aim to reproduce degree-related properties of the Internet [16,13,1]. Each of these generators implement a different set of generation models. Selecting one for a particular study depends on several factors [26], including the nature of the study to be performed, the size of the required generated topology, the weight certain characteristics of the generated topologies may have (e.g. structural properties such as hierarchical structure, or connectivity properties such as the distribution of outdegrees of the nodes), etc. A brief description of the main topology generators available follows.

Waxman [25] developed one of the first topology generators. This generator produces random graphs based on the Erdös-Renyi [4] random graph model, but it includes network-specific characteristics such as placing the nodes on a plane and using a probability function to interconnect two nodes in the Waxman model which is parameterized by the distance that separates them in the plane.

One of the most popular generators available is GT-ITM [5]. The main characteristic of GT-ITM is that it provides the Transit-Stub (TS) model, which focuses on reproducing the hierarchical structure of the topology of the Internet. In the TS model, a connected random graph is first generated (e.g. using the Waxman method or a variant of it). Each node in that graph represents an entire Transit domain. Each transit domain node is expanded to form another connected random graph, representing the backbone topology of that transit domain. Next, for each node in each transit domain, a number of random graphs are generated representing Stub domains that are attached to that node. Finally, some extra connectivity is added, in the form of ``back-door'' links between pairs of nodes, where a pair of nodes consists of a node from a transit domain and another from a stub domain, or one node from each of two different stub domains. GT-ITM also includes about five flavors of flat random graphs.

Another generator that implements models trying to imitate the structure of the Internet is Tiers [8]. The generation model of Tiers is based on a three-level hierarchy aimed at reproducing the differentiation between Wide-Area, Metropolitan-Area and Local-Area networks comprising the Internet.

BRITE 1.0 [16] is the precursor to the universal generation tool we are presenting in this paper. BRITE 1.0 implements a single generation model that has several degrees of freedom with respect to how the nodes are placed in the plane and the properties of the interconnection method to be used. Under certain configuration of the parameters, BRITE 1.0 generation model is equivalent to Waxman. Under other configuration of parameters, BRITE 1.0 implements the Barabási-Albert model proposed in [2] in which a network grows incrementally and the nodes interconnect with preference towards higher degree nodes.

Inet [13] and PLRG [1] are two generators aimed at reproducing the connectivity properties of Internet topologies as reported in [9]. These generators initially assign node degrees from a power-law distribution and then proceed to interconnect them using different rules. Inet first determines whether the resulting topology will be connected, forms a spanning tree using nodes of degree greater than two, attaches nodes with degree one to the spanning tree and then matches the remaining unfulfilled degrees of all nodes with each other. PLRG works similarly to Inet in that it takes as an argument the number of nodes to be generated and exponent value $\alpha$. This exponent value is the parameter of a power-law distribution which is used to assign a priori degrees to the nodes of the topology. For any given node $n$ with degree $d_{v}$, $n$ is cloned $d_{v}$ times and then the resulting nodes are randomly interconnected.

Another set of topologies for which special generators are not required are regular topologies such as the mesh, star, tree, ring, lattice, etc. These topologies have the advantage that they are very simple, and are generally used for simplicity or to simulate specific scenarios such as LANs or other shared communication media. Finally we note that not all existing topology generation models have been implemented in a generator -- the ``small-world'' model of [24] is one such example.

As we can see, there are a wide variety of generators available. Most of them differ in fundamental ways. For example, Waxman is concerned only with general random networks, GT-ITM and Tiers are concerned with the hierarchical properties of the Internet, BRITE 1.0, Inet and PLRG are concerned with resemblance to Internet topologies in terms of connectivity properties, and regular topologies are concerned only with specific and restricted scenarios. Furthermore, generators such as Inet and PLRG can be characterized as causality-oblivious since they do a fairly good job reproducing for example the outdegree distribution of Internet topologies but their corresponding generation models do not provide insights into why such properties arise in the Internet in the first place. GT-ITM and Tiers are concerned with more specific hierarchical properties which are related to how the Internet is organized. However, the fact that they fail to reproduce properties of the Internet [9] suggests that the generation models they implement are lacking some fundamental characteristics. BRITE 1.0 could be characterized as a causality-aware generator since its main model is aimed to trace back the origin of the power laws in Internet topologies [16]. Note that this situation does not imply that one category of models is ``better'' than the other. However, a unified model that considers both hierarchical properties, degree distributions and connectivity properties, and incorporates causal models has not yet been developed.