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.

1. 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.
2. Topology
   The topology part can be split into the following two sub-parts: statistical analysis of the Internet topology and AS relationship inference.
   1. 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: 1) dK-distributions (generalizing the average degree (d=0), the node degree distribution (d=1), the degree correlations (d=2), etc.); 2) dK-graphs (sets of graphs with the same dK-distribution); and 3) 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.
   2. 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.
3. 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 growth: 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/