[e2e] new papers on Internet topology

[Hyunseok Chang]

We have several papers out on "Internet topology":

Q. Chen, H. Chang, R. Govindan, S. Jamin, S. Shenker, and W. Willinger
"The Origin of Power Laws in Internet Topologies Revisited"
http://topology.eecs.umich.edu/archive/origin.ps

H. Chang, R. Govindan, S. Jamin, S. Shenker, and W. Willinger
"On Inferring AS-Level Connectivity from BGP Routing Tables"
http://topology.eecs.umich.edu/archive/inferbgp.ps

H. Tangmunarunkit, J. Doyle, R. Govindan, S. Jamin, S. Shenker, and
W. Willinger
"Does Size Determine Degree in AS Topology?"
http://topology.eecs.umich.edu/archive/size.ps

H. Chang, S. Jamin, and W. Willinger
"Inferring AS-level Internet Topology from Router-Level Path Traces"
http://topology.eecs.umich.edu/archive/spie_itcom01.ps

H. Tangmunarunkit, R. Govindan, S. Jamin, S. Shenker, and W. Willinger
"Network Topologies, Power Laws, and Hierarchy"
http://topology.eecs.umich.edu/archive/topo1.ps


The abstracts of these papers are appended below.


Hyunseok

-----

Q. Chen, H. Chang, R. Govindan, S. Jamin, S. Shenker, and W. Willinger
"The Origin of Power Laws in Internet Topologies Revisited"

In a recent paper, Faloutsos et al. [FFF99] found that the inter
Autonomous System (AS) topology exhibits a power-law vertex degree
distribution.  This result was quite unexpected in the networking
community and stirred significant interest in exploring the possible
causes of this phenomenon.  The work of Barabasi and Albert [BA99]
and its application to network topology generation in the work of Medina
et al. [BRITE] have explored a promising class of models that yield
strict power-law vertex degree distributions.  In this paper, we
re-examine the BGP measurements that form the basis for the results
reported in [FFF99].  We find that by their very nature (i.e.,
being strictly BGP-based), the data provides a very incomplete picture of
Internet connectivity at the AS level.  The AS connectivity maps
constructed from this data (the original maps) typically miss
20-50% or even more of the physical links in AS maps constructed using
additional sources (the extended maps). Subsequently, we find that
while the vertex degree distributions resulting from the extended maps
are heavy-tailed, they deviate significantly from a strict power law.
Finally, we show that available historical data does not support the
connectivity-based dynamics assumed in [BA99].  Together, our results
suggest that the Internet topology at the AS level may well have developed
over time following a very different set of growth processes than those
proposed in [BA99].


H. Chang, R. Govindan, S. Jamin, S. Shenker, and W. Willinger
"On Inferring AS-Level Connectivity from BGP Routing Tables"

Recent studies concerning the Internet connectivity at the AS level have
attracted considerable attention.  These studies have exclusively relied
on BGP measurements collected by the National Laboratory for Applied
Network Research (NLANR) in deriving some of the unexpected and intriguing
results.  The NLANR data sets reflect AS peering relationships, as
reported by BGP, seen from a handful of vantage points in the global
Internet.  The possibility that these data sets may provide only a very
sketchy picture of the complete inter-AS connections that exist in the
actual Internet has received surprisingly little scrutiny.  By augmenting
the NLANR data sets with BGP summary information from a large number of
Internet Looking Glass sites and with routing policy information
from Internet Routing Registry (IRR) databases, we find that (i) a
significant number of existing AS connections remain hidden from most BGP
routing tables, (ii) the AS connections to Tier-1 ASs are in general more
easily observed than those to non-Tier-1 ASs, and (iii) there are at least
about 25-50% more AS connections in the Internet than what recently
considered BGP-derived AS maps contain (but only about 2% more ASs).
These findings point out the need for an increased awareness of and a more
critical attitude toward the applicability and completeness of given data
sets at hand when establishing the generality of any particular
observations about the Internet.


H. Chang, S. Jamin, and W. Willinger
"Inferring AS-level Internet Topology from Router-Level Path Traces"

A number of recent studies characterize AS-level topology of the
Internet by exploiting connectivity information contained in BGP
routing tables.  In this paper, we present an alternative method for
discovering AS connectivity by inferring individual AS connections
from the Internet's router-level topology.  This methodology has
several advantages over using BGP routing tables.  First, it allows us
to obtain AS-level connectivity information at a finer granularity
(e.g., multiple connections between a pair of ASs); second, we can
discover ASs aggregated in BGP routing tables; and third, we can
identify AS border routers, which may allow us to further characterize
inter-AS connections.  Border routers have multiple interfaces, each
with an address in a potentially different AS.  A major challenge of
our approach is then to properly map border routers to their
corresponding ASs.  To this end, we present in this paper several
mapping rules and heuristic for inferring the ASs of border routers.
We report on results showing the effectiveness and validity of these
rules and heuristic.


H. Tangmunarunkit, R. Govindan, S. Jamin, S. Shenker, and W. Willinger
"Network Topologies, Power Laws, and Hierarchy"

It has long been thought that the Internet, and its constituent networks,
are hierarchical in nature.  Consequently, the network topology generators
most widely used by the Internet research community, GT-ITM [7] and
Tiers [11], create networks with a deliberately hierarchical structure.
However, recent work by Faloutsos et al. [13] revealed that the Internet's
degree distribution -- the distribution of the number of connections
routers or Autonomous Systems (ASs) have -- is a power-law.
The degree distributions produced by the GT-ITM and Tiers generators
are not power-laws.
To rectify this problem, several new network generators have recently
been proposed that produce more realistic degree distributions; these
new generators do not attempt to create a hierarchical structure but
instead focus solely on the degree distribution.  There are thus two
families of network generators, structural generators that treat hierarchy
as fundamental and degree-based generators that treat the degree
distribution as fundamental.
In this paper, we use several topology metrics to compare the networks
produced by these two families of generators to current measurements of
the Internet graph.  We find that the degree-based generators produce
better models, at least according to our topology metrics, of both
the AS-level and router-level Internet graphs.  We then seek to resolve
the seeming paradox that while the Internet certainly has hierarchy,
it appears that the Internet graphs are better modeled by genrators that
do not explicitly construct hierarchies.  We conclude our paper with
a brief study of other network structures, such as the pointer structure
in the web and the set of airline routes, some of which turn out to
have metric properties similar to that of the Internet.

------