Atom-Based Routing

Improving global internet routing by implementing atom-based routers.

4. Atom-Based Routing

Routing protocols such as BGP operate on individual prefixes. Each update, table entry, and computation is based on a single prefix as the basic element. Although several prefixes may be stored or transmitted at a time by BGP, the prefix remains the basic element of the protocol. For example, an update message may carry a route containing several prefixes, but the receiving BGP router will still need to consider each prefix in the message separately in its computations.

A routing protocol based on atoms will treat a number of prefixes as equivalent and amortise overhead of the protocol over the equivalent prefixes. Such a routing protocol is the goal of this project.

The effects of atom-based routing are similar to CIDR in that both are able to summarise prefixes (as aggregates and atoms respectively) and treat the summary as a unit. An important difference is that CIDR aggregation can be performed independently by each router; however by definition the computation of an atom requires cooperation between many routers.

Figure 4 illustrates the general idea behind atom-based routing as applied to the example in Figure 2 The atoms shown are those derived in Figure 3. In Figure 4, advertisements of atoms replace advertisements of individual prefixes. As a result, the number of update messages in the backbone has decreased from six to four, and the number of entities advertised into the backbone has decreased from five to three. This is one example of how an atom-based routing protocol might take advantage of the equivalence of the prefixes in an atom. Note that this example assumes that the routers involved know what prefixes make up each atom, i.e. have some of means of knowing the mapping in Figure 3.

Figure 4: Example of atoms.

4.1. Dimensions of Atom-Based Routing Protocols

A number of atom-based routing protocols are possible, varying in a number of dimensions, some of which are:

Scope of atoms

Computing atoms in a large system of BGP routers may run into scalability problems. Possible scalability problems are:

• Determining the precise set of equivalent prefixes that make up an atom may require taking a global snapshot of all BGP routers in the system. For systems consisting of many routers, this may be too expensive.
• If the messages of the atom-based protocol contain references to atoms, the routers involved in a message exchange need to agree on what atom is being referred to in the message. In other words, the routers need to have a common naming (identification) system of atoms. Establishing a common naming system among all the routers in a large system may be too expensive.

These problems may be diminished by limiting the scope of an atom. For example, an atom-based protocol might divide a large system of BGP routers into smaller `areas', and compute atoms independently in each area. The scope of an atom then consists of the area it is computed in.

The more areas the system is divided into, the smaller each area will be, and the cheaper it will be to manage the atoms of that area. However, there is a trade-off, in that the more areas the system is divided into, the less useful each atom may be to the system as a whole.

Knowledge of prefixes

An atom-based routing protocol may be able to do away with the knowledge of the individual prefixes that compose an atom (i.e. a mapping such as the one shown in Figure 2 in a subset of the routers. An example appears in Section 5.1.

Alternatively, even if knowledge of individual prefixes continues to be maintained by each router, an atom-based routing protocol allows large tables to be taken out of the critical path during packet forwarding. This capability is examined in Section 5.2.

4.2. Benefits of Atom-Based Routing

Benefits in one or more of the following areas are to be expected:

Table size

If each entry in a router's table governs an atom rather than a single prefix, fewer entries need to be stored. Note that a straightforward compression algorithm in a BGP router may be able to reduce table size as well, but at the expense of CPU cycles. A more real advantage is obtained if (a subset of) routers do not need to be aware of each prefix in the system, or at least if individual prefixes can be eliminated from their packet forwarding tables and algorithms.

A factor of two reduction of backbone BGP table sizes was already established in CAIDA2. However, there is a potential of a far greater return than a factor of two in a subset of routers. In replacing prefix entries by atom entries, a router's table size could be shrunk to 22.2% CAIDA2⁴.

4. This figure is based on the definition of atoms given in CAIDA2. Using the modified definition of Section 3.1, the number of entries should drop to the number of crown atoms. Recent figures (June 1 2002) indicate a factor of four for the original definition of atoms in CAIDA2, or five for our modified definition.

Note that even a factor of two can be substantial, considering that we should expect this factor to hold not only for today but for the ongoing growth of the Internet. In other words, this result halves the growth rate of backbone routing tables for all time.

While in terms of theoretical complexity this is a trivial result, from an engineering perspective, this can easily be the difference between a thriving Internet and considerable indigestion in the routing plane. Growth in the backbone tables is somewhere around (at least) half the rate dictated by Moore's law.

Update communication costs

If each update message in the routing protocol governs an atom rather than one prefix, fewer update messages are needed. Note that BGP already allows an update message to govern more than one prefix simply by including a list of prefixes to which the message applies. Update messages in an atom-based routing protocol on the other hand may govern multiple prefixes without listing those prefixes explicitly (thereby reducing their size).

Another potential source of savings in communication costs is the effect of absorption of routing instability, which is similar to the absorption of routing instability resulting from CIDR aggregation (Section 2.2). An example of this appears in Section 5.1.

Note that there is a trade-off with the communication costs needed to compute and maintain an agreed set of atoms between routers.

Update computation costs

The algorithms of the protocol allow the routing information of the prefixes of an atom to be updated at one time. Whereas BGP may carry several prefixes in one update message, prefixes still need to be considered individually by the BGP algorithms.

Furthermore, the effect of absorption of routing instability mentioned above would also reduce update computation costs.

Note that again there is a trade-off with the processing needed to compute and maintain an agreed set of atoms between routers.

Next: 5. Practical Deployment of Atom-Based Routing