Atom-Based Routing; Introduction

Improving global internet routing by implementing atom-based routers.

1. Introduction

Global routing in today's Internet is negotiated among individually operated sets of networks known as Autonomous Systems (AS). An AS is an entity that connects one or more networks to the Internet, and applies its own policies to the exchange of traffic.

AS policy is used to control routing of traffic from and to certain networks via specific connections. These policies are articulated in router configuration languages and implemented by the Border Gateway Protocol (BGP) RFC1771.

A basic BGP exchange consists of a message announcing (advertising) reachability of a single network via a certain router. The reachability information includes an AS path, which is a sequence of ASes. BGP assumes that:

• This path is taken by the reachability message.
• The advertised network can be reached via this path.

A BGP table associates a network prefix identifier (prefix) with the AS path through which the network is considered reachable. This table is an important ingredient of the packet forwarding process by a BGP router.

Reduction of the number of entries in BGP tables is typically seen as beneficial to infrastructural integrity. The number of entries in a table has bearing on both router memory and CPU cycles. The number and size of routing update messages (announcements and withdrawals of networks) tends to increase with the number of prefixes in the table. Not only are communication costs affected by this, but also the CPU resources needed to process the updates Huston.

The project proposed in this document aims to significantly reduce growth of BGP table size and updates, in particular in the Internet backbone¹, through the use of BGP policy atoms CAIDA. The intent is to devise a routing protocol ² (or adapt a routing protocol such as BGP) which makes use of atoms to achieve a protocol of lower compexity.

1. The problem of BGP table size is not as severe outside the backbone. Routers that are not part of the backbone can rely on `default routes' which direct traffic for unrecognised destinations towards the backbone. Therefore they do not need to have a complete picture of the Internet. Routers in the backbone on the other hand cannot make use of such default routes, and need to have a picture of the Internet which covers every globally reachable IP address.
2. We consider the routing protocol to be both the messages exchanged by the protocol and the basic algorithms of the routers that exchange these messages.

Atoms could reduce current backbone BGP table sizes and growth by a factor of two, using the methodology of CAIDA2. However as mentioned later, there is a potential of a far greater return than a factor of two: around 22%.

Next: 2. Background --- CIDR