MVP

Measuring Internet Routing from the Most Valuable Points


BGP extensively propagates reachability messages, causing BGP Vantage Points (VPs) to observe highly redundant route updates, which provide low value but increase processing requirements.

MVP is tool that computes redundancy between VPs and advises users on which VPs to use to maximize the value of collected BGP route updates while staying within their processing budget.

MVP uses data-driven algorithms designed to compute redundancy without optimizing for a specific objective. Therefore, MVP is beneficial for users regardless of how they intend to use the data.

Watch our RIPE 85 presentation
or read our technical report.


MVP returns a list of the most valuable VPs of GILL
It takes as input a year and a volume of data and gives a set of VPs that generates an expected volume of data lower than the volume specified as input. Get Your MVPs!
MVP returns redundancy scores for each pair of VPs Thus, You can compute your own set of complementary VPs based on these redundancy scores and some additional constraints that you might have. See redundancy scores!

Why using MVP

We found users often only focus on a few VPs because they observe a huge number of route updates that is expensive to process. We conducted a survey on authors of nine research papers published in top conferences to understand how they use the BGP data.

We show on the right the collected answers for the question "How did you select your VPs ?". We find that users often select VPs using naive strategies.
DFOH Slide





Unfortunately, users often end up with many redundant VPs when they select them naively. The matrix on the left displays redundancy scores for ten randomly selected pairs of VPs.

Each cell indicates redundancy between the VPs on the x and y-axis. A blue cell means the two VPs tend to observe route updates for the same prefix at the same time. A green cell signifies that the two VPs are not redundant. You can hover your mouse over a cell to identify the VPs and view their redundancy score.

Since many cells are blue, we conclude that a significant number of the selected VPs are redundant.

What you can expect from MVP

If you cannot or do not want to process all the data from RIS and RouteViews, then selecting the VPs from which to process the data using MVP will significantly improve the performance and accuracy of your tool and studies.

Use Case Data Reduction Factor
We define the reduction factor to capture how much MVP reduces the number of BGP updates required to fulfill a particular objective.

A reduction factor of 2 means that we can fulfill a given objective with half as many updates when using MVP compared to when using a baseline. Here, the baseline is a random selection of the VPs.
Transient Path Detection
Transient paths are BGP routes visible for less than five minutes, a typical BGP convergence delay, and which can be attributed to e.g., path exploration.

We focus on 20000 transient path events randomly selected.
1.55
This means that with MVP, we can detect 50% of the transit path events with 1.55 times fewer updates compared to when randomly selecting the VPs.
MAOS Hijack Detection
MOAS prefixes are announced by multiple distinct ASes, which can be caused by legitimate or malicious actions

We focus on 20000 randomly selected MOAS events.
2.35
This means that with MVP, we can detect 50% of the MOAS events with 2.35 times fewer updates compared to when randomly selecting the VPs.
AS Topology Mapping
This is useful for e.g., inferring BGP policies or AS paths.

For each VP, we process the first RIB dump of May 2023 as well as the updates collected during the 100 one-hour periods and focus on all distinct AS links observed.
2.59
This means that with MVP, we can map 50% of the known AS links with 2.59 times fewer updates compared to when randomly selecting the VPs.
Traffic Engineering Detection
We focus on updates for which a path change coincides with the appearance of an action community. Action communities are associated with traffic engineering actions. We focus on 8000 path changes.
4.59
This means that with MVP, we can detect 50% of the path change events with 4.59 times fewer updates compared to when randomly selecting the VPs.
Unnecessary Updates Detection
An unnecessary update is a BGP update that only signals a change in the community values but not in the AS path. We consider 20000 unnecessary updates.
1.72
This means that with MVP, we can detect 50% of the unnecessary updates with 1.72 times fewer updates compared to when randomly selecting the VPs.

We benchmarked MVP on five use cases and found that it outperforms current VPs selection strategies.
The table on the right shows the data reduction factor, a metric that indicates the gain it terms of number of update the process when using MVP.
With MVP, we can achieve a use case while processing between 1.55 and 4.59 fewer updates compared to when selection VPs randomly. You can move your mouse on the table to find further information.