[RRG] rr-fs yearly status report

["Dmitri Krioukov" <dima@caida.org>]

The RR-FS page has been recently updated http://rr-fs.caida.org/ 

The RR-FS research agenda consists of three parts: routing,
Internet topology analysis, and modeling of Internet topology
evolution. For more details, see this NSF project description:
http://www.caida.org/projects/nets-nr/

Over the past year, the work focused mostly on the second part,
topology. The main reason is that scalability characteristics of
routing algorithms depend strongly on topological properties of
underlying networks, therefore it is logical to concentrate
on topology analysis first.

Below are the summaries of the current work and the work in
the past year for all the three parts.

I. Routing

The routing work has been essentially dormant because of the
reason discussed above. It started only recently (this summer).

1. The position paper http://arxiv.org/abs/cs.NI/0508021
(in submission) discusses the roots of the scalability
problems with current Internet interdomain routing,
and indeed with all known proposals for future Internet
interdomain routing. The paper demonstrates that according
to the best available knowledge about Internet topology,
a class of algorithms known as compact routing algorithms
offer the best candidates for a potential solution. This
paper also describes the history of compact routing, and
formulates the four most important problems concerning the
potential applicability of compact routing to interdomain
routing: the stretch scaling problem, the scale-free routing
problem, the name-independent routing problem, and the
dynamic routing problem.

2. Work on the stretch scaling problem is currently in
progress and led by L.Zan from UCI.

3. Work on the scale-free routing problem is currently
in progress and led by L.Cowen and A.Brady from Tufts.

II. Topology

The topology part can be split into the following two
sub-parts: statistical analysis of the Internet topology
and AS relationship inference.

A. Statistical analysis

This part of the agenda has the following three goals:
provide the Internet topology data to the community,
analyze the statistical properties of Internet topologies
extracted from these data sources, and then construct
equilibrium network models (equilibrium models produce
static, non-growing networks) reproducing the found statistical
properties of Internet topologies. The ultimate goal is to
use these models for theoretical and empirical performance
analysis of new routing algorithms and protocols. 

1. The AS-level topology graphs extracted from continuous
traceroute (skitter) measurements are available from
http://www.caida.org/tools/measurement/skitter/as_adjacencies.xml
The data is aggregated and updated on a daily basis.
The data is available for almost every day starting
01/02/2000.

2. An anonymized router-level topology graph extracted
from skitter measurements in April and May of 2003 is available from
http://www.caida.org/tools/measurement/skitter/router_topology/

3. The AS-level topologies extracted from skitter, BGP,
and WHOIS data in March and April of 2004, the statistical
comparison of these topologies, plots of a number of topology
characteristics and associated datasets are all available from
http://www.caida.org/analysis/topology/as_topo_comparisons/

4. Associated with the previous point, paper
http://arxiv.org/abs/cs.NI/0508033 finds that the joint node
degree distributions (degree correlations) define many other
statistical characteristics of a network topology.

5. The observation in the previous point leads to the
introduction of the concept of dK-series: dK-distributions
(generalizing the average degree (d=0), the node degree
distribution (d=1), the degree correlations (d=2), etc.),
dK-graphs, and dK-random graphs (generalizing the classical
(Erdos-Renyi) random graphs (d=0), the random graphs with
prescribed degree sequences, e.g., PLRG (d=1), etc.). For
a high-level picture, see
http://www.caida.org/projects/wide/0503/slides/krioukov.pdf
or the poster at the SIGCOMM next week (by P.Mahadevan from
UCSD). The paper formalizing the details of the theoretical
constructions and providing their empirical validation using
data from II.A.3 above is currently in submission.

6. Work on publicly downloadable 2K-random graph generator,
which according to the previous point, is superior to all
the currently existing topology generators, is currently
in progress and led by P.Mahadevan from UCSD.

7. Work on analytic derivation of clustering (the only
commonly used topology characteristic not reproduced by
2K-random graphs) is currently in progress.

8. Work on generalizing the dK-series for directed graphs
and graphs with edges labeled by arbitrary sets of relationship
classes (e.g., AS relationships) is currently in progress and
led by X.Dimitropoulos from GaTech.

9. Paper http://arxiv.org/abs/cs.NI/0507046 analyzes BGP updates
and AS-level topologies one can extract from them. The paper
finds that BGP updates have more topological information than
BGP tables.

B. AS relationship inference

AS relationships are required to augment the Internet topology
graphs with policy routing information introducing a set of
constraints for and affecting performance of routing algorithms.

1. Paper http://arxiv.org/abs/cs.NI/0507047 fixes a number
of serious problems in the AS relationship inference techniques
that had been previously considered state-of-the-art. Still,
the paper does not try to infer peering links, as they cannot
be inferred within the framework borrowed in the paper from
the previous results in this area.

2. The first paper capable of inferring peering links with
unprecedented accuracy validated by an extensive survey
with numerous ISPs is currently in submission.

3. AS-ranking induced by the AS relationship inferences above
is available from http://as-rank.caida.org/ (The page is currently
being improved and a new version with the date selection options
will be available soon.)

III. Evolution

The main goal of this part of the agenda is to construct 
non-equilibrium network models (non-equilibrium models produce
growing networks) reflecting the laws driving Internet evolution.

1. The work, led by R.Liu from UCLA, on translating ISP business
realities into an AS-level topology growth model failed. The model
could hardly reproduce the observed node degree distribution. (It is
instructive to compare these difficulties with easiness with which the
equilibrium dK-series approach reproduces *all* the characteristics
of a network topology.) The reason for the model's failure to reproduce
observed reality appears to be related to the fundamental
methodological problem with modeling complex systems: the set of 
abstractions used by the model was probably not adequate.

2. The PFP network growth model http://arxiv.org/abs/cs.NI/0402011
remains the model that most closely matches the best available 
observations of Internet AS-level topology. This model does not
try to embed any economic realities of Internet interconnection:
it is simply a variation of the preferential attachment approach,
but the model is the best *non-equilibrium* network growth model,
with respect to its proximity to observed Internet topology. Work
on an analytical solution of this model, led by P.Krapivsky from BU,
has produced preliminary results showing that the asymptotic
behavior of this model is degenerate and the power laws it produces 
are pre-asymptotic finite-size effects which can be explained by
the specifics of data-fitting techniques that the model utilizes.
These findings might have interesting implications if we consider
a possibility that power laws observed in many real-world complex
networks are exclusively due to finite-size effects, while the
asymptotic behavior of those networks is different.
--
dima.
http://www.caida.org/~dima/




--
to unsubscribe send a message to rrg-request@psg.com with the
word 'unsubscribe' in a single line as the message text body.
archive: <http://psg.com/lists/rrg/> & ftp://psg.com/pub/lists/rrg