The Next Generation of BGP Data Collection Platforms

The study of the global Internet infrastructure relies on public BGP data collection platforms (e.g., RIPE RIS and RouteViews) that maintain BGP peering sessions with network operators who volunteer to share (sometimes portions of) their routing tables. Originally established decades ago to support operational troubleshooting ("How do others reach my network?"), these systems have become a cornerstone for scientific and operational analysis of the Internet.

Collecting this data faces a fundamental cost-benefit trade-off. The information-hiding character of BGP requires collecting routes from as many BGP routers, a.k.a Vantage Points (VPs), as possible. But in practice the BGP protocol is chatty and widely propagates connectivity messages, leading to highly redundant (along with significant unique) data coming from each peer. The result is a huge data set of BGP routes with enormous redundancy and yet significant visibility gaps.

Significant visibility gaps

Despite expanding their peering footprint (top figure), RIS and RouteViews’ coverage - the percentage of ASes from which they collect routes - remains consistently low due to the rapid growth of the Internet (bottom figure). Currently, only 1.1% of the 75,000 ASes export their BGP routes to RIS or RouteViews. When considering only the 11,832 transit ASes (those with at least one customer), this figure is higher but still only 5.9%.

While we cannot know how much additional information we might observe from VPs that do not peer with the public collection platforms, we estimate this gap using controlled simulations. We use C-BGP to simulate "mini" Internets where each AS runs one BGP router and announces one or more prefixes. We then collect routes from a subset of ASes selected randomly and measure how well they enable achieving three objectives: peer-to-peer (p2p) link mapping, p2p link failure localisation and forged-origin hijack detection (Type 1).

The figure shows the percentage of observed p2p links (bottom), localised failures (middle), and detected forged-origin hijacks (top) as a function of the number of ASes hosting a VP (coverage). We make two key observations.

• Key observation #1: With 1% coverage of VPs, i.e., the coverage of RIS and RV combined, there are significant visibility gaps: We map only 16% of the p2p links, localise 10% of the failures and fail to detect 24% of Type-1 forged-origin hijacks, i.e., they are not visible from any VP.
• Key observation #2: Our simulations suggest that the percentage of ASes hosting a VP should grow by 25-100x to achieve the three objectives reasonably well. With 50% of ASes hosting a VP (i.e., a 50x coverage increase), 90% of p2p links are mapped, 95% of failures on p2p links can be localised, and only 4% of Type-1 hijacks remain undetected in the median case.

Large data set of BGP routes with enormous redundancy

RIPE RIS and RouteViews policies to store a snapshot of the aggregated data every few hours and from all VPs, as well as every BGP update received in between these snapshots, results in a large dataset of BGP routes that exacerbates data collection and use.

The figure below shows the growth in updates collected by RIS and RouteViews over the years. The deployment of new VPs along with the continued growth of the Internet (≈ 75k ASes and ≈ 1M globally announced prefixes) and the increasing connectivity between networks results in a quadratically increasing number of updates that are collected.

According to a survey that we conducted across a few researchers that used BGP data, they often resort to sampling the data, e.g., using only a sample of the VPs, neglecting the connectivity uniquely visible to other VPs. Worse, the VPs that they select often end up collecting very redundant BGP routes.

The next figure shows the redundancy between 100 VPs randomly selected. The colour of a cell indicates the level of redundancy between the VPs on the x and y axis. Here, we assume that two updates are redundant if they share the same prefix and are collected at the same time (with a 100s slack).

This figure shows that if a user focuses on a sample of the VPs randomly generated, they are likely to encounter a significant amount of redundant routes - 70% of these VPs have over 90% of their updates classified as redundant with another VP. In the meantime, the user might overlook more critical VPs that deliver unique BGP route updates.

GILL: High coverage, low data volume

We propose GILL, a new BGP collection platform that introduces a novel data collection paradigm - the overshoot-and-discard strategy. This approach achieves high coverage while minimising data volume. To explain this strategy, we use an analogy where VPs are like satellites orbiting the Earth, capturing images of its surface for monitoring purposes.

Current landscape

Today, with only about 1.1% of ASes hosting a VP, it’s as if there are only a few satellites in orbit, leaving large portions of the Earth’s surface off the radar.

Overshoot

GILL aims to collect BGP routes from as many VPs as possible. Even if two VPs produce highly redundant data, GILL considers them valuable as long as they provide some degree of uniqueness. This enables a more complete view of Internet routing, much like how today’s widespread satellite networks can cover the entire surface of the Earth.

Discard

While overshooting the number of VPs increases visibility, it also leads to a larger data volume and more redundancy. Simply storing every bit of data would create significant data management challenges. To address this, GILL discards redundant BGP updates and retains only the others.

By utilising high coverage and retaining only the most valuable BGP route updates, GILL produces a dataset that is more informative than other approaches, without increasing the overall data size.

Identifying and discarding redundant BGP updates to reduce loss of information

Since different objectives - such as topology mapping or convergence time analysis - require examining different BGP updates, there is no universal agreement on what constitutes data redundancy, and discarding BGP updates inevitably results in some information loss. We thus designed GILL to be highly general, minimising information loss while maximising information gain for any specific objective. This generality ensures that, regardless of the user’s goal, GILL provides richer insights without increasing the overall data size.

Without delving too deeply into the technical details, GILL identifies redundancies in BGP data using two key ingredients:

• Key Ingredient #1: Data-Driven Approach: GILL identifies redundancy in the BGP data by analysing past updates. We developed new algorithms that identify redundancy in a general manner, without optimising for any specific objective. This is possible because we discovered that BGP updates behave similarly to pixels in an image. Just like image compression algorithms, our algorithms aim to find a subset of BGP updates that can reconstruct the original set with the highest possible precision.
• Key Ingredient #2: Two levels of data redundancy: Some studies require the full Routing Information Base (RIB) of a VP, while others may need all updates for a given prefix across multiples VPs - even if it includes redundancy. To address this, GILL assesses redundancy at two levels: the granularity of the VPs and the granularity of the updates. GILL retains all updates from the most valuable VPs - the set of the least redundant VPs - while discarding redundant updates from the less valuable VPs. As a result, a broad range of studies can benefit from GILL. For example, GILL’s potential high coverage is useful for topology mapping, while its focus on valuable VPs enables a comprehensive analysis of convergence times.

We have publicly released the code of our algorithms and also provide their output at bgproutes.io, so you can access the results without needing to run the code yourself.

If you frequently work with BGP data, or if you operate a BGP route collection platform and find data retention challenging, the output of these algorithms can be useful. They allow to sample BGP data more strategically, avoiding the pitfalls of random VP selection or other single-objective sampling methods. GILL’s smarter approach can significantly enhance the accuracy and performance of your measurement studies and tools. For example, our algorithms have demonstrated the ability to uncover 16% more AS links compared to the CAIDA AS relationship dataset and detect 31% more potential forged-origin hijacks when using DFOH, all without increasing the data processing load compared to existing tools.

A prototype of GILL is already running at bgproutes.io

A prototype of GILL runs at bgproutes.io and currently collects BGP updates from a few routers. After identifying redundancies in the BGP data, GILL generates and applies filters to the BGP sessions. Updates that match these filters are discarded, while all other updates are stored in our database in MRT format and made publicly accessible.

Due to the high level of redundancy in BGP data, GILL discards a large fraction of updates. For instance, when mimicking BGP sessions from RIPE RIS and RouteViews, GILL typically discards over 90% of BGP updates, freeing up resources to handle additional BGP sessions.

The success of GILL will largely depend on its widespread adoption and the number of ASes that choose to peer with it. As a first step, we’ve streamlined the peering process as much as possible. Setting up new VPs is fully automated - operators can connect their BGP routers to GILL by simply submitting a form on our website and sending us an email to authenticate the BGP session. The entire process takes just five minutes to complete and there is no need to be present at some peering locations as GILL uses remote BGP sessions.

If you wish to contribute BGP data and give momentum to our project, we invite you to peer with GILL. Our data-sharing policy is transparent and readily available on our website. Our guiding principle is that all data stored on our servers will remain publicly accessible.

Should GILL achieve widespread success and gather data from thousands of ASes, we anticipate a significant reduction in current visibility gaps. For example, our simulations of a scenario where 50% of ASes peer with GILL showed a threefold increase in the number of peer-to-peer links observed, a doubling in the number of Internet failures we could localise, and a 33% reduction in undetected forged-origin hijacks—all without processing more data than what RIS and RouteViews handle today!

Is GILL yet another BGP data collection platform?

There are many BGP data collection platforms available, so it’s understandable to question whether peering with GILL is worth it.

The figure below gives an overview of the BGP route collection platforms landscape. Unlike other public platforms that selectively accept new peers based on criteria such as data uniqueness or feed location, GILL distinguishes itself with a more inclusive approach, welcoming BGP data from every AS.

Whether you’re a large Tier-1, a small stub AS, or any other AS on the Internet, you can easily set up a remote peering session with GILL and contribute BGP data to help our community gain better visibility into Internet routing.

We plan for GILL to integrate data from RIPE RIS and RouteViews by leveraging their live stream services, effectively mimicking their BGP sessions. This approach allows GILL to start with over 1,000 peers right from the outset. However, this capability will only be fully realised once GILL transitions from prototype to production mode - and we are working hard to make that happen!

Therefore, if you’re already peering with a public BGP collection platform like RIPE RIS, there’s no immediate need to set up redundant peering sessions from the same router(s) with GILL. That said, you’re welcome to peer with GILL from other routers, which may provide unique and valuable insights.

To learn more about GILL and see how you can contribute to a more transparent public Internet - one where critical routing information is more easily available to the global community - we encourage you to visit our website at bgproutes.io, read our SIGCOMM ’24 paper (which won the Best Paper Award!) or watch our SIGCOMM presentation.

Acknowledgments

Finally, we would like to take this opportunity to express our gratitude to the RIPE NCC for generously funding our research through the RIPE NCC Community Projects Fund.

This material was also in part sponsored by the ArtIC project (grant ANR-20-THIA-0006-01), Région Grand Est, Inria Nancy-Grand Est, IHU of Strasbourg, University of Strasbourg, University of HauteAlsace, Silicon Valley Foundation for Cisco (CG1318167 and CG1348196) and by the National Science Foundation (NSF) grant CNS-2120399 and OAC-2131987. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of NSF.