[brite-users] Re: Huge node sets and Dijkstra's SP algorithm

Anukool Lakhina anukool@cs.bu.edu
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.

Good luck!