[e2e] thoughts on router-level topology modeling

[Ellen Witte Zegura]

I was recently inspired to write down some thoughts on
router-level topology modeling.  They are below.

Comments welcome.

Ellen
-----

On occasion, people ask me whether they should use GT-ITM[1] to
generate topologies for Internet simulations.  Usually they mention
the Faloutsos work observing power laws in measurements of Internet
topology[2], and perhaps they point to some of the more recent
topology generators such as Inet[3] and BRITE[4].  Here is an answer.

Let me start by explaining that the GT-ITM software package implements
a collection of topology generation methods, including standard random
graphs, Waxman's variant on random graphs, and the transit-stub
method.  The transit-stub method uses the other methods to build up a
topology whose high-level structure arguably reflects the high-level
structure of the Internet, and it is probably the most widely used
method in GT-ITM.

In principle, any of the graphs generated by GT-ITM could be
interpreted as modeling either the router-level Internet topology
(where vertices are routers and edges are one-hop connectivity) or the
autonomous-system level Internet topology (where vertices are
autonomous systems and edges represent peering agreements).  In
practice, however, transit-stub graphs should be interpreted as
router-level models, since they explicitly group vertices into
domains, and reflect that grouping in the connectivity between
vertices.

The graphs generated by the transit-stub method (and indeed by all the
methods currently implemented in GT-ITM) will NOT generally have
structure described by power laws.  I say "generally" because the
transit-stub method in particular has many parameters; the structure
of the graphs that are generated can vary widely (even for the same
size and number of edges) depending on the parameters.  It is
therefore difficult to make statements that apply to all
instantiations of the method.

Does that mean you shouldn't use the transit-stub method?  If you need
an AS-level representation, I would not recommend it.  However, if you
need a router-level representation, I think it remains a reasonable
choice.  Let me explain why.  First, the power law observations have
primarily focused on the autonomous-system level representation of the
Internet, because that data is available via BGP route tables.  Data
on the router-level topology of the Internet can only be obtained
indirectly (e.g., by inference from traceroute measurements), since
network administrators don't like to reveal details of internal
topology.  I believe it remains an open question whether the
router-level Internet topology has power-law behavior.  It wouldn't
surprise me if it does, but it also wouldn't surprise me if
router-level topology has more complex structural behavior, due to
differences in intradomain and interdomain connectivity.

Second, many simulations will involve topologies with a few 100s of
nodes, due to limitations on simulation speed.  My intuition says that
these topologies are too small for discussions of power laws (i.e.,
linear on a log-log plot) to make much sense.  And if you are
simulating an even smaller topology (few 10s of nodes) a multi-domain
topology probably doesn't make much sense.

Third, the other options for router-level models are fairly limited.
The newer topology generation methods that I know about (BRITE, Inet)
target AS-level representation, not router-level representation.  They
do a fairly good job generating large graphs (1000s of vertices) with
power-law behavior similar to that observed in the snapshots of the
Internet AS-level topology.  But they aren't intended as router-level
models.


I don't claim the transit-stub method is the last word in router-level
topology modeling.  Indeed, I'm sure it's not, and I know of some
specific things that would improve it.  For example, transit domains
should have explicitly designated border router vertices, to which all
external edges are connected, rather than using all vertices
as endpoints of external edges.  However, I do think it is
currently a reasonable choice for moderate size router-level topologies.

Ellen Zegura
January 2001

[1] http://www.cc.gatech.edu/projects/gtitm/

[2] Faloutsos, Faloutsos and Faloutsos, On power-law relationships
of the Internet topology, Proceedings of Sigcomm 1999.
http://www.acm.org/sigcomm/sigcomm99/papers/session7-2.html

[3] Jin, Chen and Jamin, Inet: Internet topology generator,
Technical report CSE-TR-433-00, Dept of EECS, U. of Michigan.
http://topology.eecs.umich.edu/inet/

[4] Medina, Matta and Byers, On the origin of power-laws in
Internet topologies, ACM Computer Communication Review, April 2000.
http://www.cs.bu.edu/faculty/matta/Research/BRITE/