News

EC publishes study on Next Generation Internet 2025 2018/10/05

Bob Goudriaan successor of Marc Gauw 2017/10/12

NLnet Labs' Jaap Akkerhuis inducted in Internet Hall of Fame 2017/09/19

NLnet and Gartner to write vision for EC's Next Generation Internet initiative 2017/04/12

Dutch Ministry of Economic Affairs donates 0.5 million to "Internet Hardening Fund" 2016/12/16

Vietsch Foundation and NLnet cooperate in internet R&D for research and education 2016/09/28

 

Atomised Routing Interim Report 14 Februari 2003

Project Summary

Project Title Atomised Routing
Organization: CAIDA, NLnet Labs and Ripe NCC
Start Date October 2002
End Date October 2003 (tentative)
Principal Investigator kc claffy and Andre Broido
Project URL http://www.caida.org/projects/routing/atoms/

Overall Objective

In the atomised routing project we are researching and implementing modifications to BGP routing that aggregate prefixes into equivalence classes (policy atoms) based on common AS path from a given topological location. The motivation behind development of BGP atomization mechanisms is to achieve potential savings in computation and communication costs (by absorbing routing dynamics of prefixes into coarser grained atoms), as well as reduction in BGP table size (there will be far fewer atoms than prefixes). The project proposal.

Item: Refining and Releasing Atom Computation Scripts

Objective:

Documenting and releasing Andre Broido's Perl scripts for atoms computation.

Background:

The atoms computation scripts perform two tasks. They derive BGP statistics from the University of Oregon RouteViews `show ip bgp' tables, and they compute BGP policy atoms (groups of prefixes that share the same AS path in each BGP router). Earlier versions of the scripts were used for many of the results in papers authored by Andre Broido et al.:

Results:

The bulk of the original scripts were rewritten for readability and easy usage, code reviewed, and source code and usage documentation were provided. The results have been posted on the Web and can be downloaded from http://www.caida.org/projects/routing/atoms/download/. Announcements were made to a number of mailing lists.

The output generated by the scripts include:

Sample of Results:

A sample of the results of running the scripts on the RouteViews dump of 1 February 2003 (noon) is given below:

Number of prefixes 125857
Maximum number of prefixes per peer in /0-/24 range 119400
Number of prefixes shared by 35 peers 113343
Number of ASes with positive indegree 14754
Number of ASes with positive outdegree 2353
Number of BGP atoms 29059
Number of origin-declared atoms 21771 (derived)

The above results were computed over the 35 RouteViews peers that carry at least 114000 prefixes (with prefix length 24 or less). The full set of files for this run is also available. The number of origin-declared atoms is actually the number of distinct origin links (first link in the AS path) seen. Declared atoms are discussed later.

Current Plan:

In their current version the scripts compute `strict' atoms, that is, in strict accordance with the definition of atoms given above. It is our intention to include alternative definitions of atoms (such as `crown atoms' in Analysis of RouteViews BGP data: policy atoms or Complexity of global routing policies), which better correspond to the atom definition given in the project proposal.

The scripts produce many statistics and are written in Perl. Geoff Huston has written an optimised C program which specialises in the task of computing atoms alone. He intends to include atom statistics on http://bgp.potaroo.net/. In addition, a group at Tel Aviv University is researching BGP atoms and have written an independent implementation of atoms computation. Finally, an associate at CAIDA is writing a Python implementation of atoms computation.

Item: Implementation of atomised routing

Objective:

To design, implement and measure an atomised router, atomised routing and atomised forwarding.

Results: Identifying key issues

As part of the design of atomised routing, we have enumerated and elaborated a list of key issues that need to be resolved in order to come to a BGP protocol based on atoms. Each issue has different trade-offs in terms of performance and complexity. An early version of this list was sent to the atoms mailing list. Some of the more significant issues and trade-offs are listed below.

Issue: to declare or compute atoms

Atoms can be declared by origin ASes (ASes that originate prefixes), or they can be computed from BGP tables, e.g. using the scripts that were described earlier.

We are currently working on a possible solution that combines atoms computation with atoms declaration.

Issue: islands or scattered routers

There are two deployment scenarios: `islands' of atomised routers embedded in the Internet, or a scattering of isolated atomised routers across the Internet.

Issue: absorbing instability

Atoms offer the potential of absorbing some instability of prefixes in much the same way that CIDR aggregation is able to absorb instability. We intend to exploit this property of atoms.

Results: extending the BGP protocol

The BGP protocol needs to be extended to carry both the distribution of atom contents (what prefixes are assigned to an atom), and the routing of atoms as a whole (through what paths can an atom be reached). For incremental deployment it is essential that atomised routing and forwarding be transparent to non-atomised BGP routers. For example, updates for atomised prefixes must be sent to non-atomised BGP routers so that they may continue to route these destinations. Avoiding inconsistency in BGP appears to be one of the main challenges here.

We have drafted two alternative extensions to the BGP protocol, which are summarised below. Both extensions are based on declared (rather than computed) atoms. The extensions can be used in a scenario of atomised routers scattered across the Internet or within an island of atomised routers. The extensions are as follows:

When implemented in the context of an island, these schemes can be supplemented with an atomised forwarding component.

One important issue which has arisen is how an atomised router should resolve conflicting atoms definitions from different neighbours. For example, an atom A1 learned from neighbour N1 may overlap (have prefixes in common with) an atom A2 learned from neighbour N2. This situation may arise after a prefix moves from one atom to another and BGP has not yet converged for these destinations.

Results: implementation

We are currently implementing the first of the above schemes as modifications to the Zebra code base. At this point we are debugging an initial rough implementation.

There are very few open source router implementations, and Zebra appears to be the only reasonable choice for us to base an atoms implementation on. For example, GateD is no longer open source, and MRT is not actively maintained. However, the Zebra code base is rather unstructured and mostly undocumented, and some time has been spent understanding Zebra's BGP implementation. It seems that the community would be well served with an alternative open source router implementation.

Current Plan:

Item: Feedback from community

Objective:

Obtain feedback about atomised protocols and implementation.

Results:

Current Plan:

We will try to further encourage feedback by posting a summary of current status of design and implementation on the atoms web pages as well as a list of issues that we need feedback on.

Considering the usefulness of the feedback we received at IETF-55, we intend to test our latest ideas about atomised routing at IETF-56 (March 2003 in San Francisco), and will be taking further advantage of exposure to the operational experts who have helped us thus far. We will provide a summary of these interactions by 1 April 2003.

Item: BGP Bibliography

Objective:

Provide the community with an online annotated list of BGP related research.

Results:

A BGP bibliography was created at http://www.caida.org/projects/routing/atoms/bib/. So far sixteen entries have been registered.

Current Plan:

We will continue adding papers to the bibliography, and kc will also hold a UCSD summer quarter reading seminar course that will involve reading 10 landmark papers in BGP research relevant to this project. Details forthcoming in a subsequent report.

(text: Wed Feb 19 12:39:07 PST 2003, by Patrick Verkaik and Tuan Le)

Calls

Send in your ideas.
Deadline Feb 1st, 2018.

 

Project Atom-Based Routing

NLnet Projects