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

Anukool Lakhina anukool@cs.bu.edu
Thu Feb 20 11:18:01 2003


Hi Vladimir,

I am cross-posting this to the brite-users@ list as others have asked this
question to me also.

To answer your questions:

> - RT_NODE regular host node within AS
> - RT_BORDER router node in AS
> 
> - E_RT - intra AS edge
> - E_AS - router level edge
> 
> Correct?
 

Yes, you're correct.  

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.

> I assume that I can specify how many routers I want per AS? And also that
> I dont want any AS-AS edges that do not go through routers, i.e only
> router edges can connect two different AS's.? I think I've read this in
> documentation.

Yes, you can specify the number of routers per AS. 

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. 

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 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.

Good luck,

Anukool