IRTF Routing Research Group's (RRG) Future Domain Routing (FDR)
Scalability Research Subgroup (RR-FS)
Chair:
Dmitri Krioukov <dima@caida.org>
Routing Research Chair:
Avri Doria <avri@psg.com>
Mailing Lists:
This is a closed subgroup.
Send requests to participate to the chair.
Description of the Research Group
From the distributed computation theory, it is known that the scalability issues
associated with routing in dynamic networks are directly related to the triangle of trade-offs between the routing table size, path length inflation (stretch), and convergence/adaptation costs (the amount of messages a routing algorithm generates per topology change, etc.). The term "trade-off" used here means that, for example, routing table size decrease comes with the price of increase of stretch. Such trade-offs are functions of a routing algorithm (aka scheme) and the network topology.
There are well-known scalability concerns associated with BGP stability and routing table sizes. In fact, the BGP adaptation costs were demonstrated to be unbounded (persistent oscillations, etc.). The main goal of this group is to find and specify routing algorithms that would perform better (in terms of trade-offs mentioned above) on realistic Internet topologies. The first step in this direction has been recently made: it was demonstrated that there are routing algorithms guaranteeing extremely small both routing table sizes and stretch on Internet-like topologies. However, the adaptation costs were assumed to be unbounded.
Goals and Milestones
There are three major work areas in this group. The first two areas of research are concurrent and involve progress reports at the RRG meetings (hosted at the IETF meeting or otherwise) on a yearly basis.
1. Routing (to be completed in 2007-2011 (tentative))
This work includes evaluation (analytic and/or via simulations) of the performance of existing routing algorithms (as well as designing and evaluations of new ones) on Internet-like topologies. Existing algorithms include several algorithms recently obtained in the distributed computation theory. The immediate next step (to be completed in 2005 (tentative)) is to analyze recent name-independent low-stretch compact routing schemes. The output from this work area is expected to be in the form of research papers.
2. Internet topology measurement and analysis (to be completed in 2007-2011 (tentative))
As mentioned above, the performance of a routing scheme depends strongly on the actual network topology. More accurate Internet topology measurements, further analysis of its characteristics, and construction of realistic ("explanatory") Internet topology evolution models (topology generators) are the major directions for the work in this area. The output is expected to be in the form of Internet topology data and research papers.
3. Upon completion of the above two steps, the selected routing algorithm(s) are to be specified in the Internet Draft
document(s). These final IDs will also contain information on what other
algorithms were considered and why they were not selected.
More details can be found in:
1. RR-FS Extended Charter,
listing possible work directions for foreseeable future; and
2. NeTS-NR
NSF Proposal, based on the Extended Charter and containing the description
of specific deliverables for 2004-2007.
Compact routing background reading
Overviews:
1. C. Gavoille, "Routing in Distributed Networks: Overview and Open Problems,"
SIGACT News 2001 (ps.gz).
Most important results:
1. L. Cowen, "Compact Routing with Minimum Stretch," SODA 1999
(ps).
2. M. Thorup and U. Zwick, "Compact Routing Schemes," SPAA 2001
(ps.gz).
3. M. Arias, et al., "Compact Routing with Name Independence,"
SPAA 2003 (ps).
4. I. Abraham, et al., "Compact Name-Independent Routing with
Minimum Stretch," SPAA 2004 (pdf).
WG deliverables
Routing
Papers
1. D. Krioukov and kc claffy, "Toward Compact Interdomain Routing," in
progress, 2005 (arxiv).
2. D. Krioukov, et al., "Compact Routing on Internet-Like
Graphs," INFOCOM 2004 (conference version: pdf; technical report
version: arxiv).
Presentations
1. D. Krioukov and kc claffy, "Introduction to Compact Routing," Interdomain
Routing Workshop, Amsterdam, Holland, May 2004 (abstract,
ppt, pdf).
2. D. Krioukov, "Project for a ŽEvolution in Data Network Routing: the
Kleinrock Universe and Beyond," Midnight Sun Routing Workshop,
Lulea, Sweden, June 2002 (ppt,
pdf).
Topology
Papers
1. P. Mahadevan, et al., "Lessons from Three Views of the Internet
Topology," CAIDA-TR-2005-02, 2005 (arxiv).
2. X. Dimitropoulos, et al., "Inferring AS
Relationships: Dead End or Lively Beginning," WEA 2005 (doi).
3. X. Dimitropoulos, et al., "Revisiting Internet AS-Level Topology
Discovery", PAM 2005 (doi).
Presentations
1. D. Krioukov, "Degree Correlations and Topology Generators," 5th
CAIDA-WIDE Workshop, Marina Del Rey, CA, March 2005 (ppt,
pdf).
2. D. Krioukov, "Progress in Inferring Business Relationships Between ASs," 4th
CAIDA-WIDE Workshop, San Diego, CA, August 2004 (ppt,
pdf).
Internet topology data
1. AS-level topology extracted from on-going skitter measurements:
http://www.caida.org/tools/measurement/skitter/as_adjacencies.xml
2. Router-level topology extracted from skitter measurements:
http://www.caida.org/tools/measurement/skitter/router_topology/
3. Statistical characteristics of the AS-level topologies extracted from
skitter, BGP, and WHOIS data:
http://www.caida.org/analysis/topology/as_topo_comparisons/
4. Ranking of ASs based on AS relationships:
http://as-rank.caida.org/
Status reports and reviews
2004:
1. Status report, IETF-60, San Diego, CA,
August 2004 (ppt, pdf).
2005:
1. Status report.
2. Review of external routing research.
3. Review of external topology research.