Atom-Based Routing; Policy Atoms

Improving global internet routing by implementing atom-based routers.

3. Policy Atoms

In CAIDA the notion of `policy atoms' was introduced as a means to analyse the complexity of routing tables. By analysing a number of backbone routers the authors found that the use of policy atoms could potentially reduce the size of a complete backbone BGP table by a factor of two, while preservering all globally visible routing policies CAIDA2. In addition, they found that the number of atoms properly scales with the Internet's growth.

3.1. Definition of Policy Atoms

An atom is defined relative to a system of BGP routers. For example, it may be defined relative to the Internet backbone routers or (in the extreme) to all BGP routers in the Internet. Each atom consists of prefixes that are treated equivalently by the chosen system of BGP routers. For example in Figure 2 the prefixes 192.24.0.0/13 and 192.24.0.0/22 are treated equivalently by the backbone routers and are therefore part of the same atom (relative to the backbone).

In CAIDA, an atom is defined as follows. Two prefixes are said to be path equivalent if no BGP router can be found among the considered BGP routers that sees them with different AS paths. An equivalence class of this relation is called a (BGP policy) atom. It follows from this definition that prefixes in the same atom share a set of AS paths.

In this proposal we use a slightly modify definition, as follows³ In determining path equivalence of two prefixes, we ignore the part of a prefix's AS path that falls outside the system of BGP routers. From this definition, it follows that prefixes in the same atom share a set of truncated AS paths, where each AS path is truncated to exclude the part that falls outside the system. Note that under this modified definition a smaller number of atoms will result.

3. This definition corresponds more closely to the definition of crown atoms in CAIDA than to regular (non-crown) atoms.

We call the system of BGP routers relative to which an atom is defined the scope of the atom.

Algorithmically, atoms may be constructed as follows:

1. Select a system of BGP routers to be considered (as mentioned above). This becomes the scope of the atoms.
2. Select the set of prefixes to be considered. For example, the prefixes common to all BGP routers in the chosen system might be selected CAIDA. Another possible selection is the set of prefixes each of which is known by at least one BGP router in the chosen system.
3. With each prefix associate a set of AS paths between the BGP routers. Truncate each AS path in the set by removing the part that falls outside the chosen system.
4. For each set of truncated AS paths, find all prefixes that share this set of paths.

The following example derives atoms from the prefixes shown in Figure 2 using the algorithm. The system of BGP routers considered (and therefore the scope of these atoms) consists of the backbone routers that appear in Figure 2; the prefixes considered are all those shown in Figure 2. The atoms that can then be derived are shown in Figure 3 Note that although the full AS paths of e.g. 192.24.0.0/13 and 192.24.0.0/22 are different (since the former is originated by AS 2 and the latter by AS 1), the parts of the AS paths which fall within the backbone, i.e. the truncated AS paths, are the same. Therefore they are in the same atom.

Figure 3: Atoms derived from Figure 2

Note that the size of the atoms which result from the above definition depends in part on the system of routers considered: the fewer routers are considered the larger the atom size will tend to be. In addition the atom size also depends on the selection of prefixes considered.

Next: 4. Atom-Based Routing