Safely work from home with open source 2020/03/30

NGI0 grant for Software Heritage 2020/03/26

Hackers donate 90% of profit to charity 2019/06/13

NGI Zero awarded two EC research and innovation actions 2018/12/01

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


Atom-Based Routing; Introduction

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:

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 backbone1, through the use of BGP policy atoms CAIDA. The intent is to devise a routing protocol 2 (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


Send in your ideas.
Deadline June 1st, 2020.

NLnet projects
Atom-Based Routing
Project plan:
1. Introduction
2. Background
3. Policy Atoms
4. Atom-Based Routing
5. Practical Deployment
6. Answers to Questions
7. Related Ideas
8. Planning
9. Project Members
R. References
Plan as PDF (201kB)
Plan as PostScript.gz (71kB)