Atom-Based Routing; Practical Deployment

Improving global internet routing by implementing atom-based routers.

5. Practical Deployment of Atom-Based Routing

This section shows two ways of incrementally deploying atom-based routing in the current Internet. The approaches discussed share the following properties:

• They affect only cooperating routers in the backbone. They are transparent to other backbone routers, as well as to routers outside the backbone.
• The protocols used are based on existing routing and forwarding protocols, with only minor modifications.

Neither approach addresses atom computation. Instead they simply assume that the problem of scalable atom computation has been solved. In Section 5.3 we briefly discuss a number of issues pertaining to atom computation.

5.1. Atom-Based Routing Islands

Here we show how to embed an `island' of atom-based routing in the backbone. Routers that are part of such an island reap the benefits of atom-based routing. On the other hand, outside the island the application of atom-based routing is completely transparent (apart from observed performance). By introducing an island of atom-based routing, and gradually growing it, it is possible to effect a gradual transition to an `atomised' Internet backbone. The aproach described here extends BGP, and uses IP addresses (IPv4 or IPv6 addresses) to represent atom ids. The aproach has the following properties (see Section 4.1):

Scope of atoms

The scope of each atom is the entire island of atom-based routing. Note that a more sophisticated version might divide an island into more than one scope for scalability.

Knowledge of prefixes

This aproach does not require each router to be aware of all prefixes. Only a subset of the routers are; others are only aware of atoms without knowing what prefixes they consist of.

The aproach distinguishes the following routers:

• External routers, which are outside the island. These routers are not aware of the atom-based routing protocol.
• Internal routers, which are within the island. Internal routers are further divided into edge routers and transit routers.
• Edge routers which are internal routers that exchange (forward) packets with external and internal routers.
• Transit routers which are internal routers that merely exchange (forward) packets with other internal routers.

The internal routers implement routing and forwarding in three parts:

1. Atom computation:
   As mentioned earlier, the problem of atom computation is assumed to have been solved. We assume the outcome of the computation is a collectively agreed upon atom id for each atom, and a mapping between atom identifiers and the prefixes atoms consist of. Only edge routers need to be aware of this mapping; transit routers do not.
    
2. Updates to the routing of atoms:
   Routing update messages are exchanged between all internal routers (both edge and transit routers). This part of the approach uses BGP. But whereas normally BGP carries reachability information for individual prefixes, here we use BGP to announce reachability information for atom ids. Since an atom id is just an IP address, regular BGP can be used. Alternatively, the MP_REACH_NLRI attribute of BGP RFC2283 can be used to carry this information if we view atom ids as an address family.
    
3. Forwarding of packets:
   A packet is accepted by an edge router from an external router. Based on the destination IP address of the packet, the edge router tags the packet with the correct atom id. Based on the atom id, the packet is then forwarded by the system of internal routers (transit and edge routers) until it reaches the edge router where it leaves the island. This edge router removes the atom id tag and forwards the packet to an external router. One way of implementing this is to `source route' the packet:
   • At the edge router where the packet enters the island, an IPv4 loose source route option RFC791 is added to the packet. If the packet already contains a source route option, the source route option is modified instead. The packet is source-routed first to the atom id destination, and then to the original destination of the packet. For IPv6, a routing header RFC2460 can be inserted to achieve source routing.
   • The packet is forwarded until it leaves the island. Given that the atom id is an IP address, existing forwarding implementations can be used.
   • At the edge router where the packet leaves the island, the changes that were made to the packet when it entered the island (IPv4 source route option or IPv6 routing header) are undone.

Another way of implementing forwarding is to use tunneling, e.g. IP over IP, MPLS or GRE.

In addition, edge routers are responsible for passing on topology changes from external routers (in the form of prefixes) to internal routers (in the form of updates to atom definition and updates to atom routing) and vice-versa.

Referring back to the advantages in Section 4.2:

Table size

Transit routers are able to maintain tables with far fewer entries: one per atom instead of one per prefix. Only the edge routers need to maintain per-prefix tables. In particular during packet forwarding, smaller tables are accessed in the internal routers, i.e. in all but one edge router (where the packet enters the island).

Update costs

Updates that merely change the contents of an atom (i.e. add or remove prefixes) do not affect transit routers at all, since the routing of the atoms remains the same. They are effectively absorbed (see Section 4.2) by the edge routers. Similarly, updates that affect the routing of an entire atom can be summarised in an update message for the atom, rather than an update message per prefix. Routers that process such update messages need to spend fewer CPU cycles on updating their tables.

5.2. Disjunct Atom-Based Routers

Note: the ideas in this section require further elaboration.

The previous section discussed islands of connected atom-based routers. Here we show how to embed disjunct (disconnected) atom-based routers in the backbone.

The atom-based routers in this section are optimised for forwarding packets that carry an atom id tag, but also handle regular packets. The presence of these routers is transparent to regular, `prefix-based' routers. This means that atom-based routers do not need to be placed together in islands, as in Section 5.1. Instead, atom-based routers may be located in different parts of the backbone, separated by prefix-based routers, and still be able to take advantage of atom-based routing. By gradually increasing the number of atom-based routers, it is possible to effect a gradual transition towards a more `atomised' Internet backbone.

Atom-based routers forward packets as follows. If an atom-based router encounters a packet that has not yet been tagged, it tags the packet with the correct atom id and forwards it. If an atom-based router encounters a packet that has already been tagged, it simply forwards it based on the atom id, using a small forwarding table.

Atom tagging occurs in such a way that (a) other atom-based routers can detect whether or not a packet has been tagged, and (b) unmodified prefix-based routers are able to forward tagged packets. There are two ways of achieving this:

1. Atom tagging is performed in a similar way to Section 5.1 e.g. using a loose source option. However, instead of using regular IP addresses to represent atom ids, an atom id is represented by an IP address taken from a special range. This allows atom-based routers to readily detect that a packet has been tagged. In the case of IPv4, atom ids might initially be taken from the class E (`experimental') range. If the approach is successful a separate range might be allocated at some point (by IANA).

   To allow prefix-based routers to forward tagged packets, all we need to do is to ensure that additional entries for IP addresses representing atom ids are made (e.g. by announcing them using regular BGP messages). This of course has the disadvantage of increasing the size of the prefix-based router tables.

2. Atom tagging is performed in some other (unspecified) way that does not alter the destination of the packet. Since the destination of the packet is unaltered, prefix-based routers do not need to have separate entries corresponding to atom ids.

We are also able to handle prefixes that are not (yet) part of any atom. If an atom-based router encounters a packet that has not been tagged, but does not know of an atom that contains the prefix either, it passes it on to the nearest prefix-based router that it knows (possibly located at the same site), which forwards it using a regular, large forwarding table. Therefore, even if some ratio of Internet traffic never becomes atomised, we will still be able to handle atomised traffic in an expedited way, and fall back to a less efficient forwarding behaviour for the remaining traffic.

5.3. Atom Computation

Neither of the above approaches addresses atom computation. Atom computation consists of identifying atoms and determining what prefixes belong to each atom. The outcome of atom computation is a collectively agreed upon atom id for each atom, and a mapping between atom ids and the prefixes atoms consist of.

We know how to compute atoms in a centralised way. However, to perfom atom computation in a scalable, distributed way is an unsolved problem, which will be addressed in the course of the project. Several scalability issues were discussed in Section 4.1. Special attention will be paid to convergence time. An example of a convergence issue is how to update (a) atom contents (i.e. the prefixes atoms consist of) and (b) atom routing (i.e. the routing of atoms as a whole) independently. We must avoid updates to one causing unnecessary updates to the other while the system converges to a new routing state. Note that convergence time is highly recognised as problematic at this point, and is an example of why this kind of research is so important.

Next: 6. Ansers to Questions