Top-down Hierarchical Topologies

Top-down is one of the approaches used by BRITE to generate hierarchical topologies. Figure 5 depicts the structure of the top-down approach for generating hierarchical topologies. The main steps are labeled (1)-(3).

Figure 5: Top-down Approach for Generating Hierarchical Topologies

Top-down means that BRITE generates first an AS-level topology (1) according to one of the available flat AS-level models (e.g. Waxman, Imported File, etc.). Next, for each node in the AS-level topology BRITE will generate a router-level topology (2) using a different generation model from the available flat models that can be used at the router-level. BRITE uses an edge connection mechanism to interconnect router-level topologies as dictated by the connectivity of the AS-level topology. Performing this interconnection of router-level topologies in a representative way is an open research question. BRITE provides four edge connection mechanisms, borrowed from the popular GT-ITM [5] topology generator. The idea is to gradually increase the set of edge connection methods with models that reflect what actually happens in Internet topologies.

The basic edge connection methods provided with BRITE operate as follows. If $(i,j)$ is a link in the AS-level topology, then pick a node $u$ from the router-level topology associated with AS node $i$, $RT(i)$, and a node $v$ from the router-level topology associated with the AS node $j$, $RT(j)$, such that:

• Random: $u$ is picked randomly from $RT(i)$ and $v$ randomly from $RT(j)$
• Smallest degree: $u$ and $v$ are nodes with the smallest degrees in $RT(i)$ and $RT(j)$, respectively.
• Smallest degree non-leaf: $u$ and $v$ are nodes of smallest degree in $RT(i)$ and $RT(j)$ respectively but are not leaves.
• Smallest k-degree: $u$ and $v$ are nodes of degree greater that or equal to $k$ in $RT(i)$ and $RT(j)$ respectively.

The final topology is obtained by flattening the hierarchical topology into a router-level topology composed of the individual topologies associated with each node at the AS-level.

Note that we are implicitly assuming that the topology being manipulated is represented by an undirected graph. BRITE internal data structures do not restrict the graph associated with a topology to be undirected. However, some of BRITE functionality, such as importing a topology from a file in BRITE's output format, assumes that the corresponding topology has undirected links. Increasing BRITE's flexibility by explicitly distinguishing between directed and undirected topologies is straightforward and it is part of our ongoing work.

The configuration file used by BRITE to generate a top-down topology contains parameters controlling the bandwidth distribution for inter- and intra-domain links. These parameters override the specific parameters for the AS- and router-level topologies. Bandwidths for the generated AS-level topology will be assigned according to the inter-domain distribution. Furthermore, bandwidths for each generated router-level topology are assigned according to the intra-domain distribution. During the flattening process, the links established between different router-level topologies will have assigned the bandwidth associated with the corresponding AS-AS link. This bandwidth-assignment method represents just one possible mechanism. Different models can be implemented and added to BRITE.