Celebrating a BGP Monitoring Milestone & Catchpoint’s First Patent

Catchpoint recently celebrated a significant milestone, our first patent. The patent protects the work of its inventors, Staff Engineers Alessandro Improta and Luca Sani, VP of Engineering Sergey Katsev, and Chief Product and Technology Officer Dritan Suljoti. The patent creates a “method and system to reduce a number of border gateway protocol neighbors crossed to reach target autonomous systems.” In the words of Staff Engineer Luca Sani, “The question the patent seeks to answer is: What is the fewest number of peers that an autonomous system (AS) needs to peer with to maximize reachability (and consequently resilience)? Of course, for Catchpoint, there’s an additional benefit: It allows us to determine the optimal locations for gathering BGP data to minimize costs and maximize monitoring coverage.”

In this blog, we sat down with the team as they laid out the following:

• The problem the patent set out to solve and how it effectively addresses it.
• The milestone the patent represents for Catchpoint and how it adds to our Network Experience solution.
• The importance of our BGP data sources and why we continue to add dedicated peers in addition to RIS and Route Views peers.  
• Their favorite BGP joke – for some light humor only AI (Alessandro Improta) could supply.

The problem of AS-level data incompleteness

For Alessandro Improta, the patent aims to solve the problem of BGP data incompleteness in route collectors, which he and Luca, along with several others, first identified in a co-publication in IEEE/ACM Transactions on Networking in 2015. Route collectors like the Routing Information Service (RIS) deployed by RIPE NCC and the Route Views project deployed by the University of Oregon are extremely valuable for researchers and network operators, as they are the most reliable source of information regarding the inter-AS infrastructure of the Internet. Thanks to them, it is possible to identify prefix hijacks and route leaks and ensure that other ASes/players on the Internet can reach their destination. However, they collect BGP data only from a small set of ASes compared with the total number of ASes on the Internet – thus limiting the quality of the inferences that can be drawn from their analysis. For example, most of the data available in 2015 was from Europe and North America, with less available from other parts of the world.  

Effectively, the research performed in this publication has formed the foundation for the work Alessandro and Luca have spearheaded at Catchpoint in “filling the gaps” of data incompleteness. It also was the initial proposal for the AS distance metric, which was extended in our patent.

How the patent improves BGP visibility

From the PATENT ABSTRACT:

“The disclosed method and system increase routing efficiency by identifying a set of candidate Autonomous Systems (ASes) able to reduce average AS distances towards a set of target ASes. Starting from a list of Routing Information Base (RIB) snapshots and a set of target ASes, candidate ASes are ranked based on the gain they would provide in terms of AS distance if they were connected to the network administrator AS. A set of starting ASes may represent the ASes to which the administrator is already connected, and a set of forbidden ASes may represent the ASes to which the administrator does not want to connect. An exemplary web-based interface may show gains of candidate ASes, allowing the administrator to understand better how much an average AS distance toward the set of target ASes would improve.”

To summarize, it helps understand the connectedness between ASes and improve visibility into BGP, which, after all, is an essential component of the Internet that can represent a weak spot in any organization’s Internet Stack (find out more about that here).

At Catchpoint, there are a few ways that we are planning to use this information – the first of which is already in place. By applying the system described in the patent, we can ensure that Catchpoint’s BGP monitoring solution can maximize coverage - thus maximizing the infrastructure’s capability to reveal routing anomalies. The system helps us identify the most useful ASes to observe to obtain a complete picture of the state of BGP worldwide.

Think of it this way: As the number of AS hops increases between a BGP speaker and the origin of a routing anomaly, the probability rises that the anomaly will be filtered out via the BGP decision process implemented by any of the ASes encountered along the route, leaving the route collectors potentially blind to the event. Indeed, when multiple routes to reach the same destination are available, the BGP decision process selects one route to propagate to neighbors, effectively concealing the other routes. Thus, the usefulness of a BGP collector can be assessed on its proximity to the source of any BGP event of interest, such as a hijack or a leak, represented by each AS within the Internet. Please note this is a simplified overview of the concept; please refer to the patent if you want to dive deeper.

The objective of the patented system is to increase the probability of having the AS under monitoring within a few hops away from a collector. It’s important to consider that BGP is operational worldwide and each BGP speaker deployed worldwide has a distinct route to reach every AS network. Expanding on this goal, we aim to maximize the likelihood that the AS and customer or transit networks being monitored are only a few hops away from a collector. In so doing, we can ensure the best possible BGP monitoring network – precisely what Catchpoint is implementing through the system described in this patent.

Consider the AS network depicted by the gray circles. It is evident that certain locations are more advantageous than others for deploying route collectors. We show two sample locations – one much better than the other. Also, if two collectors are already present, the patent mechanism helps us choose the best place to locate a third collector. A network engineer who isn’t looking to set up their own BGP monitoring network can use the same mechanism to help decide the best ASes to peer with to maximize the reliability of the reachability of a set target of ASes. Of course, details such as economic relationships and IXP vs transit ASes can further complicate the computation.  

In the first image, the distance from any AS to the nearest collector is 2.6 hops. The second image improves the collector placement so that the distance shrinks to only 2 hops! The third image shows that starting with a given configuration, we can use the patent to decide where to insert an additional collector – in this case shrinking the distance to 2, but with one extra collector versus the ideal scenario. Similarly, for the network engineer case – ASes 1 and 9 would be the “ideal” transit to get as close as possible to other ASes in the network.

‍The importance of quality and diversity in BGP monitoring infrastructure

We did promise you the team’s favorite BGP joke. Here it is in all its glory:  

Why did the BGP speaker go to therapy?
Because it had trouble letting routes go and couldn’t stop announcing itself!

According to Alessandro Improta (who takes full responsibility for the above joke), BGP monitoring serves as a perfect example that corroborates the argument that quality matters more than quantity. “At Catchpoint, we prioritize identifying incidents from all over the globe to our customers. This patent represents a significant step towards establishing a more diverse and distributed BGP route collecting infrastructure. You may have thousands of different BGP sessions from thousands of different ASes, but if they are coming from the very same location or facility, or the peers and upstream providers of these ASes are the same, you are likely to fail in being able to reveal nasty prefix hijacks impacting your network from other sources. And as the saying goes, what goes unnoticed by the eyes, the wallet DEFINITELY regrets!”

“The patented methodology provides a clear roadmap with a list of networks to add to our private collectors’ network,” says Gael Hernandez, Director of ISP/Peering Strategy. Our first patent represents a significant milestone in our commitment to improving the monitoring of Border Gateway Protocol (BGP) and addressing the problem of AS-level data incompleteness. Not only does it showcase our dedication to providing high-quality and diverse BGP data sources, but it also underlines our commitment to comprehensive monitoring to identify and mitigate potential network incidents. It’s a remarkable leap forward in BGP monitoring, solidifying our position as a trailblazer in the pursuit of network excellence.

Learn more

• Read our patent in full
• White Paper: The Comprehensive Guide to BGP
• Blog Post: BGP Beyond Preventing Outages