The BGP Visibility Scanner

Andra Lutu — Apr 24, 2013 02:05 PM
Contributors: Olaf Maennel, Marcelo Bagnulo Braun
Filed under: , ,
We developed a tool that allows you to check if prefixes originated by your AS have limited visibility on the global routing table. In the article below we describe some of the results we found after analysing many months of global routing table data.

Introduction

Advertising a prefix is only the first step towards achieving global reachability at the interdomain level. However, complex interactions between routing policies and human errors may mean that an advertised prefix is not reachable from everywhere in the Internet. We built a tool, that looks at publicly available BGP routing data and checks the global visibility of your prefixes.

Such limited visibility can have many different causes. We had some initial talks with operators and discovered misconfigurations can be one of them, as well as the actions of third parties. We would like to turn this tool into a useful "BGP policy verification" system. In this article we report on our findings of analysing many months of global routing data.

Methodology

It is well known that not all routes make it to every routing table (RT) in the Internet. Sometimes this happens as a consequence of the specifications of the originating AS and sometimes it is due to the complex nature of the Internet. Using prefix visibility as an expression of policy interaction, the BGP Visibility Scanner analyses all data BGP routing data taken from RouteViews and the RIPE Routing Information Service (RIS) in order to quantify the visibility degree of every prefix advertised at the interdomain level. All together there are 24 different routing table collection points and more than 140 different Autonomous Systems (ASes) periodically dumping their entire routing tables.

We define Limited Visibility Prefixes (LVPs) as prefixes that are not present in every routing table, and we use the Visibility Scanner Algorithm to identify them.

Below you can see an image illustrating the methodology of the visibility scanner (you can enlarge the image by clicking on it).

BGP Visibility Scanner ImageFigure 1: BGP Visibility Scanner Methodology

Results

We demonstrate the usage of the visibility scanner on a complete sample taken on 23 October 2012. We 'cleaned' the raw data from RIPE RIS and RouteViews in order to identify all the so-called Global Routing Tables (GRTs). The GRT may be defined as a routing table which is thought to contain almost all the prefixes injected in the Internet. We separated 129 GRTs, distributed as follows:

  • 9 ASes in the Lacnic region
  • 14 ASes in the APNIC region
  • 37 ASes in the ARIN region
  • 68 ASes in the RIPE NCC region

We then polished the global routing tables for our study by eliminating 500 bogon prefixes and about 4,500 multiple origin AS prefixes. We found that, as expected, not all of the global routing tables contain all the prefixes injected at the interdomain level. In the image below you can see that about 80% of prefixes are visible in all full routing tables, and 20% are not.

Empirical CDFFigure 2: Proportion of prefixes seen in routing tables

We also do not consider internal routes. This means that for our analysis we took out prefixes that are only present in one of the routing tables with an AS-Path length of one (i.e., prefixes for which we cannot be sure that they are visible in at least 2 different monitors). In total, we filtered out 10,500 internal routes.

Each prefix then got a visibility label based on the 95% minimum visibility threshold rule, and the prevalence sieve explained in the last processing block of the methodology:

  • High visibility (HV) if the prefix is present in more than 95% of routing tables for at least one sampling time
  • Limited visibility (LV)if the prefix is present in less than 95% of routing tables at both sampling times

Out of a total of 512,000 prefixes we identified 415,576 High-Visibility prefixes (HVPs) and 98,253 Limited-Visibility prefixes (LVPs).

Dark Prefixes

The most interesting prefixes to look at are the so-called dark prefixes (DPs). These are limited-visibility prefixes that are not covered by a high-visibility prefix. This is illustrated in Figure 3 below:

Dark PrefixesFigure 3: So-called dark prefixes are not covered by a high-visibility prefix

Generally, limited-visibility prefixes are covered by a shorter high-visibility prefix. However, some limited-visibility prefixes are not covered by another prefix. This would constitute address space that may not be globally reachable (in the absence of a default route). In our sample we found around 2,400 dark prefixes in the LVP set.

We also looked at the prefix lengths of these three categories of prefixes, i.e., LVP, HVP and DP. We observe that there are no high-visibility prefixes with a prefix length longer than /24, which is expected and complies with the BGP best recommended practices. However, the limited-visibility and dark prefixes are not only prefixes that are more specific than /24, thus cannot only be blamed on an inconsistency of filtering rules at the interdomain level. You can see the results in Figure 4 below.

Distribution of Prefix LengthsFigure 4: Distribution of prefix lengths in HVPs, LVPs and DVPs

We identified 3,570 different ASes that were originating these limited-visibility prefixes, and they were distributed as follows:

  • 30.5% in the ARIN region (~1,081 ASes)
  • 30.1% in the RIPE NCC region (~1,068 ASes)
  • 22.4% in APNIC (~795 ASes)
  • 14% in the Lacnic region (~493 ASes)
  • 1.1% in AFRINIC (~42 ASes)

Conclusion

We found that there are about 100,000 prefixes that show limited visibility and about 3,000 prefixes that do not have any less specific prefix covering them (e.g., they do not provide global connectivity in the absence of a default route).

How can this phenomena be explained? Is it something the origin AS intended or is it something that the AS is unknowingly suffering from? We would like to hear your feedback. This will help us accumulate more ground truth and possibly predict the cause of the limited visibility for the prefixes identified.

The tool itself can be found at: http://visibility.it.uc3m.es/. Using the latest routing data, you can test the visibility of the prefixes originated by a certain AS. Please also note the background paper, published in Proceedings of 16th IEEE International Global Internet Symposium (GI 2013), Turin, Italy, April, 2013.

All results of this study are also available on that web site. At the bottom of that page, you can find a contact form. Of course you can also leave comments here under this article on RIPE Labs.

2 Comments

Roque Gagliano
Roque Gagliano says:
Apr 25, 2013 06:51 AM
Hi,
Thanks for the good work.
In my personal experience, what you call "Dark Prefixes" is sometimes a feature and not a problem. When working on a LATAM service provider we had a service where we offered "regional transit" to customers. In those cases, the prefixes where not announced globally and had no less specific. Transit providers allow to regulate this regional policies using BGP communities.

Additional, I think it would be good to see the distribution of the DP across the 255 different /8. I am saying this because it may be the case that some networks have not updated their bogon for the most recent allocations. Think about 14/8, which used to be allocated to Public Data Networks (BTW APNIC did a lot of debugging activities for this block).
Andra Lutu
Andra Lutu says:
Apr 25, 2013 10:53 AM
Hi Roque,
I'm glad to see that you find the work interesting!

The scenario you're describing is very interesting, thank you for that.
We are indeed aware that some prefixes are intended to have reduced visibility or even to be dark. What is a bit more challenging is to be able to tell them apart and let operators know when a problem might be occurring. This is why feedback on these prefixes is very important at this stage.
  
We are working to update the tool as we speak and provide more query options, so it's great to learn what you think it would be interesting to add.
Out of curiosity, I've checked the LVPs and DPs from 14/8, found 4 DPs and 77 LVPs. I assume that, in at least a few of these cases, your diagnosis is correct and some networks have not updated their bogon filters yet.
Add comment

You can add a comment by filling out the form below. Only plain text is possible. Web and email addresses will be transformed into clickable links. Comments are moderated so they won't appear immediately.

Related Items
Increased Reach of RIPE Atlas Anchors

Increasing the reach of RIPE Atlas anchors is one of the highest priority goals of RIPE Atlas Team. ...

Proposing Making RIPE Atlas Data More Public

RIPE Atlas is now three years old, and is moving from a prototype to production service. Based on ...

Modifications to the IP Analyser to Reflect New Policy

We are in the process of implementing the policy regarding Post Depletion Adjustment of Procedures ...

RIPE Atlas: Improved Probe Pages

We've made it much easier to get an overview of the history and measurements for all the public ...

Visualising Bandwidth Capacity and Network Activity in RIPEstat Using M-Lab Data

As a result of the cooperation between the RIPE NCC and Measurement Lab (M-Lab), you can now ...

more ...