RFC 7911 – What happens when routers do not speak the same language

To regularly analyze the behavior of global routing and the updates your BGP speaker is receiving, the Multi-Threaded Routing Toolkit (MRT) format reads, reviews, and stores this information in a standardized data representation. The two most prominent and large-scale BGP routing information collection systems based on MRT – University of Oregon Route Views Project and the RIPE NCC Routing Information Service (RIS) – have been archiving MRT data for many years. These publicly available archives have helped many researchers and network engineers understand routing behavior by reviewing BGP updates and RIB (Routing Information Base) dumps.

With the right tools and systems in place, any network can understand how its BGP announcements are propagating across the global routing table and discover route leaks and hijacks. This provides exceptional clarity into the data and helps operators make decisions most relevant to their business goals and strategies. But the key to good decision-making is uncorrupted data and tools to visualize and understand that data.

On 20 January 2022, we received a series of notifications suggesting that AS57695 was leaking some very strange routes. Here’s an example of what we could see:

TIME: 01/19/22 17:00:07.114554
TYPE: BGP4MP_ET/MESSAGE/Update
FROM: 206.126.236.214 AS57695
TO: 206.126.236.142 AS6447
ORIGIN: IGP
ASPATH: 57695 60068 174 37282 37714
NEXT_HOP: 206.126.236.214
COMMUNITY: 174:21101 174:22011 57695:13000 60068:201 60068:2000 60068:2010 60068:7330
ANNOUNCE
  0.0.0.0/0
  0.0.0.0/0
  104.0.0.0/2
  154.117.72.0/22
  0.0.0.0/0
  0.0.0.0/0
  104.0.0.0/2
  154.117.64.0/22

Interestingly, nothing was visible in the global routing table at the same time, but examining the notifications further, we found out that they originated from one of the Route Views collectors at Equinix Ashburn. This triggered a long investigation that resulted in something very informative that we would like to share here.

It all started with RFC7911 – “Advertisement of Multiple Paths in BGP.” BGP routers normally only advertise the best path to their neighbors, so when a better path is advertised to the same prefix, the earlier path will be automatically withdrawn.

With the BGP Additional Paths capability, BGP can advertise multiple paths for the same prefix to provide path diversity. RFC7911 provides an extension to BGP that adds a unique “Path Identifier” (PATH_ID) to each path.

ADD-PATH is a BGP capability [RFC5492] with capability code 69. When you enable it, your BGP routers will negotiate the ADD-PATH capability described in RFC7911 Section 4 to indicate that they are capable of sending/receiving (or both) multiple paths for the same prefix.

This sounds simple, but it fundamentally changes the structure of NLRI (Network Layer Reachability Information).

Without the extension, we get Prefix Length and then the Prefix itself as shown below via a packet capture (e.g., Prefix Length: 24 Prefix: 190.121.239.0). NLRI is [Prefix Length, Prefix].

To carry the capability of additional path, a “Path Identifier” is added in the UPDATE message, and the NLRI encoding is extended by prepending the Path Identifier field. As a result, NLRI becomes [Path_ID, Prefix Length, Prefix]. Path_ID has a fixed length of 4 Octets.

This extension capability is negotiated between the peers so the BGP speakers both know that there will be Path_ID before the Prefix Length. There is no confusion for BGP speakers, but a simple script won’t know about capabilities since it is only reading the BGP UPDATE messages and not the “OPEN” message which has all the capabilities in it.

MRT, which creates the BGP dumps, was updated to reflect these issues. When the ADD_Path capability is enabled, BGP UPDATE messages are marked as “MESSAGE_ADDPATH/Update”, or if there is no capability then messages are marked as “/MESSAGE/Update”.

FRRouting, a network routing software suite, only implemented this feature (RFC8050) in July 2021 (release 8.0) and the option to disable ADD_Path receiving capability only in Nov 2021 (release 8.1). Previous versions without this feature in their MRT implementation simply marked all peers – even with ADD_Path extensions – as “/UPDATE”. This caused parsers to react in unpredictable ways, because they first read the four bytes as the prefix length (which is only one byte) and started showing incorrect prefix announcements.

Here is an example.

Step 1: Negotiate Additional Path capability:

Step 2: BGP Update message with Additional Path details:

If you are relying on the MRT dumps and parsing them through any of the well-known BGP parsers such has bgpdump, bgpdump2, bgpscanner, bgpreader, the result will be something like this:

Because there is no difference in the UPDATE message from the MRT dump between ADD_Path or without ADD_Path ID, the first four octets (00 00 00 04) are considered as “Prefix Length” and “Prefix” making it something like shown above. RFC8050 – Multi-Threaded Routing Toolkit (MRT) Routing Information Export Format with BGP Additional Path Extensions has standardized the new subtypes for BGP Update messages.

This problem was first identified early last year and the details can be read on the RIPE-NCC/bgpdump Github repository issues section (Issue # 9).

RouteViews team member (David Teach) also found this problem as per his detailed explanation:

“RouteViews uses FRR as their BGP daemon. Unfortunately, the FRR BGP daemon supports BGP ADD-PATH (RFC 7911) but does not support add-path encodings in MRT (RFC 8050). Additionally, FRR does not provide a way to disable BGP add-path RX. So, any peer that decides to negotiate add-path TX with us will start sending add-path encoded routes. I’ve submitted a PR to the project to address this (FRRouting/frr#8066), which has been accepted and merged. However, this patch won’t be available in an FRR release until 7.7 which should be available this summer.”

This problem was eventually rectified in the latest FRRouting release [FRR8.1 (Nov 2021)], but many routers are using older versions of FRR (7.5 and older). The Equinix Ashburn MRT dumps available through Route Views still have this problem; we hope these routers and route collectors will be soon upgraded and this issue will be a thing of the past.

If you are aware of any other Network Operating Systems that don’t support RFC8050 then please let us know.

Maintaining data quality is important, but it is equally important to make sure that the tools we rely on to review the data are also providing accurate, complete, and reliable results.

Data quality and tools to measure the health of the global routing table are key focus areas of MANRS and we have been working with researchers and network operators to facilitate the development of improved data quality and tools.

If you have ideas to improve the existing publicly available tools, please reach out to us or discuss it with MANRS Research Ambassadors.