[IRTF-Announce] RRG Report

[Aaron Falk <[e-mail]>]

Routing Research Group Report
August 2005

While several of the efforts have been dormant or closed, one effort
has continued working toward its goals: the Future Domain Routing
Scalability sub-project (RR-FS), the report for this group is appended
below.

Two projects went dormant for a while but are now working to get on
track: documenting the History of Routing Requirements and getting the
report out on the Routing Requirements definition efforts.

One project never got off the ground: BGP Stability
(http://psg.com/~avri/irtf/BGP-stability-charter.html) and one
project has closed down: Ad hoc Network Systems Research Sub-group
(ANS).

At this point, in addition to looking for a co-chair who can help me
get this group energized, especially within the academic research
community, I am looking for a few good projects that the members of
this research group can get interested in; interested enough to
actually participate.

In terms of meetings, I am planning to request a slot at IETF64.  I
will be inviting people to present on research work and ideas that can
be brought into this research group.  At the moment I don't think
there is enough call for anything longer then a few hours worth of
discussions, but after some work gets done, I would like to organize a
full day meeting in conjunction with an appropriate conference or
technical meeting.


Report of RR-FS project:
From:       [e-mail]

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.


_______________________________________________
IRTF-Announce mailing list
[e-mail]
https://www1.ietf.org/mailman/listinfo/irtf-announce