Grouping Mechanisms.

Once the number of nodes for an AS has been assigned, BRITE assigns this number of router nodes to a single AS. BRITE does this step in one of two ways:

• Random pick: Pick randomly one node at a time and assign it to AS $i$ until it reaches its size. Repeat for all ASs.

• Random walk: Perform a random walk through the graph, where each step in the walk corresponds to choosing a random neighbor from a given vertex. Each visited node is assigned AS $i$ until it reaches its size. Repeat for all ASs.

The random walk mechanism is slightly more complicated than random pick for two reasons. First, we need to keep track of which nodes has been visited (assigned). After finishing with a given AS, BRITE picks a not-yet-visited router node and starts the random walk for the next AS. Second, it can happen that a random walk can not be completed for an intermediate AS (not the first one) because the random-walk algorithm cannot continue walking the graph any further through not-yet-visited router nodes. In this approach the parameter $NumAS$ provided by the user is used as a guideline for BRITE. As many nodes as possible, up to the value assigned to the corresponding AS, will be picked from the set of nodes during a random walk. Certain number of ASs may get less nodes than initially assigned to them. BRITE reports the actual number of ASs assigned, which may exceed the parameter $NumAS$.

We emphasize that the Bottom-Up approach is an experimental model for generating hierarchical topologies. Providing several ways to group nodes into ASs is aimed at facilitating the process of experimentation. However, there is no analysis supporting the use of random pick over random-walk or vice-versa. One could implement an assignment mechanism of routers to ASs that mimics the assignment procedure proposed in [12] to compute an AS overlay on top of a measured router-level topology. This and other assignment/grouping mechanisms is the subject of ongoing research.