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 . 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 with degree , is cloned 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.