The Need for Programmability in Routing Protocols

In order to know which features are supported by vendors' devices, protocols such as TCP or BGP have mechanisms to negotiate features during the session establishment. This allows routers to enable the feature if both support them.

In addition, networks are generally made up of devices from different network vendors, each with its own implementation and specific hardware architecture, influenced by various factors such as economics. To ensure compatibility between these different network devices, the Internet relies on standards developed by the IETF.

Although these protocols are designed to be scalable, the introduction of new extensions requires a standardisation process before they can be included into the vendor implementations. However, this process can take time. Figure 1 shows the delay in publishing BGP extensions from their initial design as drafts to RFCs. As shown, it can take several years to document and standardise new features. The median time is 3.5 years, and some features have taken up to 10 years to be standardised.

Furthermore, network vendors must also implement the new standard in their equipment, but they have the "final'' decision on whether or not to implement it. Some are never implemented, or are implemented long after standardisation. Network operators also request for features that are never standardised, thus slowing down innovation in networks.

To address these limitations, we introduce xBGP, a paradigm shift that allows all BGP implementations to be programmable. This allows network operators to develop and experiment with new features before standardisation, but also to implement features that vendors may never add to their routing equipment.

xBGP aims to enable faster deployment of new services and better compatibility between routers. Network operators now have the ability to directly implement and test their own features.

There are several elements of xBGP that contribute to this goal:

First, xBGP uses an eBPF VM to dynamically inject platform-independent bytecode. In a nutshell, these are small software modules, which we call plugins, that are written in C and compiled into eBPF bytecode. The eBPF bytecode will be executed within the eBPF VM, which allows the plugin to interface with any BGP implementation, regardless of the router's CPU architecture.

Second, all xBGP-enabled routers include a vendor-independent API. This API provides access to the internal functions and data structures of a BGP implementation. In general, BGP implementations have their own representation of the BGP data structure. xBGP performs a conversion of this specific representation into a vendor-independent format that can be manipulated by any plugin.

Third, now that xBGP has a runtime environment and an API to communicate with BGP, the plugins need to be executed somewhere in the BGP code. For this purpose, xBGP relies on the fact that all BGP implementations must follow the protocol specification defined in RFC4271. This specification describes the structure of BGP messages, a conceptual BGP finite-state machine responsible for processing individual BGP sessions, an abstract BGP workflow, and data structures that detail the procedure for processing BGP update and BGP withdraw messages.

xBGP uses the BGP workflow definition to place insertion points (green circles in Figure 2). Insertion points are the locations in the BGP implementation where plugins can be executed.

The BGP workflow consists of the following steps:

1. The router receives BGP messages from its peers.
2. If it is a BGP UPDATE, the router checks the message against the import filters. If the route satisfies the import policies, it is added to the theoretical Adj-RIB-in.
3. Accepted routes are added to the Loc-RIB, which stores routes from all acceptable neighbouring BGP speakers. The BGP decision process is run to select one best BGP route per prefix.
4. Routes are also subjected to export filters before being sent as BGP updates to neighbouring routers. If a route passes the export filters, it is included in the theoretical Adj-RIB-Out.
5. Finally, the routes are sent to the BGP neighbours.

Let us take an example to illustrate how a network operator can implement Route-Reflection (RFC4456) with xBGP.

To implement this use case, the operator needs to write five plugins that will be attached to the five insertion points described previously:

1. Each time a BGP update is received from the peer, the first plugin will parse the BGP UPDATE message to decode the new BGP attributes (CLUSTER_LIST & ORIGINATOR_ID).
2. The second plugin will be responsible for checking the validity of the route. It will check in the import filter if its router-id contains the CLUSTER_LIST or ORIGINATOR_ID.
3. The Route Reflection RFC4456 specifies that the BGP decision process must be modified to change the tie breaking rules by giving preference to routes with shorter cluster list lengths and lower ORIGINATOR_ID.
4. The fourth plugin will only export the route in accordance with section 6 of RFC4456.
5. Serialising the BGP message as it will be transmitted over the wire. The fifth plugin is responsible for adding the cluster list and originator to the BGP message.

Simple xBGP plugin

As explained earlier, plugins are small pieces of software written in the C language. Due to the nature of the eBPF VM, plugins are written in a specific way so that the eBPF VM can successfully execute them.

Imagine that you want to quickly fix the problem that occurred in June 2023, where JunOS routers were resetting BGP sessions due to an incorrectly processed attribute defined in RFC 6790. One solution to prevent the routers from resetting the BGP session is to reimplement the way this attribute is handled. The idea is to remove the attribute from the route, as it will no longer be detected.

An example of a such plugin can be written as depicted in Listing 1:

^{Listing 1 - Simple plugin that remove the BGP_ENTROPY_LABEL_CAPABILITY attribute from the BGP route}

This simple example shows some of the API calls to use in order to retrieve the data from the BGP implementation. The get_arg function is taking which argument the plugin would like to get. In addition, it tells the VM to copy this data inside a memory zone accessible to the plugin

The plugin is attached to the insertion point that decodes BGP attributes (insertion point 1). As the insertion point is responsible for decoding every route attribute, there is a possibility that a plugin may not decode the attribute being processed by the BGP workflow. If this occurs, the plugin will call the next() function to request that another plugin or the implementation itself decode the attribute (i.e. if no plugin can do so).

The return value will serve as an indication for the VM that the plugin has successfully completed or not its work.

Safely injecting xBGP program into the host implementation

From the operator’s perspective, injecting an xBGP program is risky because the program can cause a router to crash. This risk is considered unacceptable because BGP implementations are generally expected to run continuously without interruption, typically 24 hours a day, 7 days a week.

To ensure the safe execution of plugins inside a BGP implementation, xBGP uses software verification techniques. This involves defining a set of properties that a plugin must meet to be considered safe, and utilising a toolchain consisting of SeaHorn, CBMC, and T2 - three software verification tools. Table 1 shows the various properties that are checked by the tool chain and the corresponding verifiers used to check the property.

These properties can be divided into three main sets. The first set of properties is related to the termination of the plugin. We do not want the plugin to get stuck in a loop indefinitely, because BGP will not process the other part of the workflow and will be considered down for its other neighbours. Therefore, all plugins must terminate.

The second set of properties relates to the unsafe memory aspect of the C language. C can access an unauthorised memory location, dereference an illegal pointer, causing the plugin to stop executing or causing buffer overflows, etc. CBMC is used to check all properties related to memory.

Finally, the last set of properties that the toolchain checks are those related to BGP. When BGP sends a message through its neighbours, it must conform to a "wire format" so that the other BGP neighbour can also understand what the router is sending. To successfully verify these properties, we use the Seahorn software verification tool. Searhorn is also used to check that the plugin is using the xBGP API correctly, so that the plugin is not using it in a way that is not intended.

Use cases

To demonstrate the benefits of xBGP, we have implemented several categories of problems that operators want to solve. Some of them can be solved without xBGP, but others are really complex to solve without xBGP. For example, we have implemented:

A mechanism to detect zombie routes. These are routes that are installed in the routing table but are no longer reachable in the data-plane.

A way to control path diversity. Each time a route is selected, an xBGP program increments an internal counter and repeats this process for each BGP step of the decision process. When a route is advertised to a peer, this statistic is joined as a BGP community. The BGP router receiving the route can use these statistics to better understand its peer's current routing table and adapt its routing strategies to select better routes.

An alternative to ORF (RFC5291). Instead of sending the filtering rules as with ORF, the operator can send an xBGP plugin to the remote router that decides which routes to send to our router. This new type of use case allows them to get the route they want directly from the source and in a more fine-grained way.

The xBGP design gives operators the ability to quickly design and introduce the features they want into the network before the vendor implements them. xBGP is the starting point for bringing innovation back to networks.

To go further

If you are interested in learning more about the internals of xBGP, the possible use cases, and the verification toolchain, please refer to our latest article published in the NSDI23 conference:

xBGP: Faster Innovation in Routing Protocols

Thomas Wirtgen, Tom Rousseaux, Quentin De Coninck, and Nicolas Rybowski, ICTEAM, UCLouvain; Randy Bush, Internet Initiative Japan & Arrcus, Inc; Laurent Vanbever, NSG, ETH Zürich; Axel Legay and Olivier Bonaventure, ICTEAM, UCLouvain

This work was partially supported by the French Community of Belgium through the funding of a FRIA (Fund for Research training in Industry and Agriculture) grant.