[IRTF-Announce] RRG Report

[Aaron Falk <falk at ISI.EDU>]

ï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:       dima at 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.


_______________________________________________
IRTF-Announce mailing list
IRTF-Announce at irtf.org
https://www1.ietf.org/mailman/listinfo/irtf-announce