From April 17 to 19, the NSDI23’ conference was held in Boston, during which we presented our paper titled “xBGP: Faster Innovation in Routing Protocols.”

In this post we will explore the outlines of xBGP.

The Need of programability in routing protocols

Whether at the level of the end user or the network operator, there is a constant need to extend the services provided by the network. This often leads to the addition of new features in the protocols used by the network equipment. In order to meet these requirements, widely used session-oriented Internet protocols, such as TCP or BGP, incorporate feature negotiation mechanisms during their handshake. Networks are made up of devices from different vendors, each with its own implementation and specific hardware architecture, influenced by various factors such as economics. To ensure compatibility between these different network nodes, the Internet relies on standards developed by the IETF. Although these protocols are designed to be scalable, the introduction of new extensions requires a standardization process before they can be incorporated into network node implementations. However, this process can take time. Figure 1 shows the delay in publishing BGP extensions in RFCs. The median time is 3.5 years, and some features have taken up to 10 years to be standardized.

Figure 1 — Delay between the publication of the first IETF draft and the published version of the last 40 BGP RFCs.
Figure 1 — Delay between the publication of the first IETF draft and the published version of the last 40 BGP RFCs.

To address this limitation, 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 standardization. By using a programmable protocol, networks gain flexibility and agility. This results in faster deployment of new services and better compatibility between routers. In addition, the introduction of xBGP allows for more sophisticated services to be implemented between Autonomous Systems (AS), thus improving the overall quality of routing.

How xBGP works

xBGP allows network operators to adapt to changing needs and offer better services to their customers by implementing their own xBGP program. They can introduce new features or enhance existing ones by leveraging the capabilities of xBGP. There are several elements of xBGP that help achieve this goal:

First, xBGP integrates an eBPF virtual machine to dynamically inject platform-independent bytecode. This allows to interface with any BGP implementation without having to adapt to the router architecture. The new features implemented by the operator will be compatible regardless of the router.

Second, all xBGP-enabled routers include a vendor-independent API. This API provides access to the internal components and data structures of BGP. If necessary, xBGP performs a conversion of the internal representation into its own format before providing data to xBGP programs, and vice versa.

Third, to talk BGP with another router, all BGP implementations must follow the protocol specification defined in RFC4271. This specification describes the structure of BGP messages, a finite-state BGP conceptual machine responsible for processing individual BGP sessions, an abstract BGP workflow and data structures that detail the procedure for processing BGP update and delete 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 the xBGP program can be run. The BGP workflow includes the following steps:

Figure 2 — BGP Workflow with xBGP Insertion Points (green circles).
Figure 2 — BGP Workflow with xBGP Insertion Points (green circles).
  1. The Router receives BGP messages from its peers.
  2. If it’s a BGP UPDATE, the router checks the message on the importation filters. If the route meets the import policies, it’s added to the theoritical Adj-RIB-in.
  3. Accepted routes are inserted to the Loc-RIB, which stores routes from all neighboring BGP speakers. The BGP decision process is run to select one best BGP route per prefix.
  4. Routes are subjected to export filters before being sent as BGP updates to neighboring routers. If a route passes the export filters, it is included in the theoretical Adj-RIB-Out
  5. Finally the routes are sent to BGP neighbors.

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 fail. 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.

xBGP uses verification techniques to ensure the safe injection of programs. To do this, we (i) define a set of properties that a program must meet to be considered safe, and (ii) use a toolchain consisting of three well-established and widely tested software verification tools - SeaHorn, CBMC, and T2. Table 1 illustrates the different properties verified by our tool chain and the corresponding verifiers used for verification.

Table 1 — Properties that xBGP programs must satisfy.
Table 1 — Properties that xBGP programs must satisfy.

Use Cases

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

  • a mechanism that detects zombie routes. These are routes that are installed in the routing table but are no longer reachable.

  • a way to control path diversity. Each time a route is chosen, an xBGP program increases an internal counter, repeating this process for each BGP decision step. When a route is advertised to a peer, that statistic is joined as a BGP community. The BGP router receiving the route can use these statistics to better understand the current routing table of its peer. If all routes were determined only by the last step of the BGP decision process, this indicates a lack of path diversity.

With xBGP design, operators have the ability to quickly design and introduce the features they want into the network, even before they are implemented by the vendor.

Read More

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

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.