The BGP Visibility Scanner

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).

Figure 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.

Figure 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:

Figure 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.

Figure 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.