[brite-users] Re: Huge node sets and Dijkstra's SP algorithm
Sat Mar 1 13:34:01 2003
Sorry for the late reply. My responses below:
> > More precisely, RT_BORDER stands for a border router in an AS. That is,
> > it is a router in AS A which has neighbors that fall in other ASes.
> > Also, E_AS stands for an inter-AS edge, i.e. an edge that connects two
> > ASes, or equivalently, two border routers belonging to two different ASes.
> For topdown approach , it seems that I can not generate router level that
> is singly connected graph on AS level - simple path between each two ASes
> using only inter-AS edges.
I'm not sure I understand what you mean by "simple path between each
two ASes using only inter-AS edges".
The topdown approach works as follows: 1) generate an AS
graph. 2) for each AS node, generate a router topology. 3) for each AS-AS
edge (u,v), construct a router-router edge corresponding to the router
topologies of the AS nodes u and v. These border routers can be selected
in several ways. In BRITE, we adopted the options of GT-ITM, the
georgia-tech generator: random, k-degree, smallest degree, smallest
non-leaf node. Therefore, the top-down approach yields a connected router
level topology, where each node is annotated with the parent AS it belongs
> > If you decide to do this, you may want to use the
> > BottomUpHierModel. This model does the following: first, it
> > generates a single-level router topology. Second, it groups routers
> > into AS boundaries until a specified threshold (size) is reached.
> Yes but as things stand right now , it seems to me that bottomup doesn't
> differentiate between RT_NODEs and RT_BORDER nodes. Does this imply that
> each node is directly connected to router level graph?
The bottom-up approach should label routers which connect to other routers
in a different AS as RT_BORDER. In anycase, one can easily determine this
by looking at the parent AS for each router. Suppose we are given a
router-router edge (u,v) and suppose u's parent AS is A and v's parent AS
is B. Then u and v are RT_BORDERS. I will point you to the BRITE
manual for more information on this. You can also take a peek at the
Java source code, as a lot of these things are commented carefully.
> > You could also easily extend the TopDownHierModel so that it generates a
> > router level topology for each AS of the size you desire. I think that
> > right now TopDownHierModel generates fixed size router topologies for each
> > AS (clearly not realistic, but it was intended to be a dummy model that
> > others would extend).
> I think I have to look into this option :(
Its not that difficult! And you can contribute your changes to BRITE
too :) I'd suggest starting with TopDownHierMpdel.java and using it as a
template, extending where you see fit.
> > I would also suggest you take a peek at Tangmunarunkit et al's CCR
> > paper: Does Size Determine AS Degree. In this paper they found that they
> > number of routers corresponding to an AS (its size) follows a heavy tailed
> > distribution. Another suggestion would be to use rocketfuel
> > traces for your router level topologies.
> What is the difference between rocketfuel and skitter?
Rocketfuel specifically maps ISP topologies by using a lot of clever
heuristics to guide the probing. As a result, ISP maps obtained by
rocketfuel are more complete when compared to their skitter
counterparts according to the rocketfuel sigcomm'02 paper.