Moreover, policy makers aiming at adhering to potential national communication policies might mandate that all intra-country communication be confined within national boundaries.

Figure 1: A visualisation of the most stable detour we observed from Russia on 2 May 2016 (visualisation is done using OpenIPMap)

Past studies have focused on studying these detours only at the data plane. A common approach followed by many is to run data plane measurements (traceroutes) between two vantage points with known locations. By geolocating each IP address in the traceroute you can check if the path crossed international boundaries. The IXP-country-jedi (provided by the RIPE NCC) follows this approach to detect paths traversing an IXP or not. Traceroutes are launched from selected RIPE Atlas probes in one country to other probes in the same country. This provides a quick insight about the reachability of networks that host a RIPE Atlas probe. However, this misses out on networks that do not host a RIPE Atlas probe. Additionally, data plane-based methods are limiting in some sense. Continuously generating traffic to detect detours may not be a solution that every network operator prefers.

We aim to create a methodology that can detect routing detours for all visible prefixes and answer a broader question: Can we detect detours in near-real time using a current public measurement infrastructure? Moreover, we aim to analyse who causes most detours and which countries are affected most.

We chose to look at the problem from a control plane point of view and used the RIPE Atlas platform only to validate the detours. Currently, there are more than 400+ BGP peers all over the world that feed their Routing Information Bases (RIBs) to RouteViews or the RIPE Routing Information Service (RIS). Each RIB provides its view of the global prefix table.

Detecting detours

To detect detours using the control plane we proposed to geolocate each Autonomous System (AS) in the AS path of the prefix entry and detect all paths that start and end in the same country but traverse at least one AS that didn't have a presence in the origin country.

Geolocation of an AS is loosely defined. For the work of inferring possible country level paths, we wanted to create a set of all the countries an AS can have a presence in. We identified three possible cases that indicate the presence of an AS in a specific country:

• The AS announces a prefix that geolocates to a specific country
• The AS has infrastructure (physical routers/switches) in a specific country
• The AS participates at an IXP in a specific country

We geolocated all the prefixes announced by each AS in the global routing table. Then we fetched IXP mappings from PeeringDB, PCH and by crawling 300+ IXP websites. We then geolocated infrastructure IP addresses that may not have appeared in BGP but appeared in CAIDA’s Ark traceroutes. The result is an AS-to-country set listing all those countries an AS is visibly present (based on a public measurement dataset). These results are available publicly at geoinfo.bgpmon.io using a RESTful API. We encourage network operators to use this dataset and contribute with ground truth about their ASes.

Using RIPE Atlas to validate

We validated our control plane-based methodology by running data plane measurements. To do this, we used RIPE Atlas probes. Every time a detour is detected in the control plane and if there is a RIPE Atlas probe hosted in the AS involved in the detour, we launched a traceroute from that probe to the detoured prefix. The methodology of running data plane measurements is shown in the following figure.

 Figure 2: Methodology used to run data plane measurements

There were a few cases where more than two RIPE Atlas probes were present in the selected AS. In those cases, we selected two probes that were geographically farthest from each other. By doing this, we aimed to account for cases where routes seen from geographically distant vantage points within the same AS are different. To select target IP addresses from detoured prefixes, we broke the prefix into its constituent /24s and randomly selected an IP address from each /24. For example, in a /23 prefix we selected two IP addresses belonging to different /24s. By doing this, we accounted for cases where a large prefix, even though in the same country, had different connectivity via different upstream providers.

Results from live detour detection

During a 12-hour live run (on 2 May 2016), we detected 6,175 detours. Out of these 5,787 were unique detours ({peer,prefix,aspath} tuple). Only 72 BGP peers saw the 6,175 detours and the 72 peers belong to only 63 ASes. From these 63 ASes we then selected those ASes that also have active RIPE Atlas probes. There were only 10 ASes that saw a detour and also host a RIPE Atlas probe. 169 detours were seen from these 10 ASes corresponding to six countries: Brazil, Italy, Norway, Russia, United States and South Africa. From the 169 traceroutes we initiated to detoured prefixes, we discarded six traceroutes where less than three hops responded since drawing detour conclusion from these was not possible. Finally, we were left with 163 traceroutes that could be used for validation.

Selecting Congruent Paths for validation

In total, we detected 85 prefixes (corresponding to the 163 traceroutes) that suffered a detour that was visible from an AS that hosts a RIPE Atlas probe. There were challenges in correlating control plane and data plane AS paths. We found many cases where AS paths seen in the control plane and AS paths seen in the data plane did not match. It is possible that ASes that were not seen in BGP appear in the data plane path. Similarly, some ASes might have disappeared in the data plane. Or there could have been a mix of both insertion and deletions. However, these paths could still show detours if the detour origin AS and the detour destination AS were still present in the traceroute observed AS path. We called such AS paths congruent. More specifically, we considered the detour AS path congruent only if the detour origin AS and the detour return AS both were present in the traceroute-observed AS path in the same order (detour origin first). For example, if an AS path ‘A B C D E’ in the control plane changed to ‘A X B C E’ in the data plane where ‘B’ was the detour origin and ‘C’ was the detour destination, we considered it a congruent path.

To resolve traceroute paths to AS paths, we used the CAIDA ITDK IP-to-AS mappings. In cases where no match was found we used the longest prefix match on the global routing table for the hop IP address. Then we mapped the longest prefix match to the AS that originated it. We observed 113 congruent AS paths. This included three cases: insertions, deletions and mix of both. We saw 73 deletions, 29 insertions, four times a mix of insertions and deletions. The remaining seven AS paths were exact matches. Note that these insertions and deletions occurred only for ASes that were not involved in the detour.

Validating paths

We performed two tests on the traceroute. First, we geolocated IP hops and verified if the path left the country. Secondly, we looked for a magnitude of jump in the RTT. The intuition here is that if the path did cross international boundaries, the RTT would increase.

Out of 113 detours, 97 did show IP addresses in the traceroute that were located in other countries and 102 detours that showed a magnitude jump in their RTT. The overlap was also significant (see Figure 3 below).

 Figure 3: Number of paths validated

We further investigated the nine detours that were seen in the country-based method but not in the RTT. These detours covered a small geographic area: four from Italy to France, two from Norway to Sweden, two from Brazil to the US and one from Russia to Sweden. RTTs between these countries have been previously reported to be low. Next, we investigated 14 cases that were captured in the RTT measurements but not in country-based method. All of these paths did cross international boundaries. For 12 of these cases, due to a large number of traceroute hops (especially towards the end of the traceroute) not responding, we didn’t see the route returning to the origin country, hence they were not detected by the country-based method. We attributed the remaining two cases as false positives due to inaccurate AS geolocation.

It was also convenient to visualise these detours. Since we use RIPE Atlas measurements, by using the corresponding measurement ID, detours can be visualised using OpenIPMap. Check out our tool Netra that we used to perform above presented detection and validation.

The results of using RIPE Atlas for validating detours seen in the control plane are promising. It showed that it is possible to perform a large-scale analysis using the control plane only and still achieve 85-90% accuracy.

Characterisation

The ability to use only control plane data for detection allowed us to run a large-scale analysis. Here, we present our results from an analysis of historical data from January 2016 of 416 BGP peers that spanned more than 30 countries. As shown in the following table, we analysed more than 14 billion RIB entries. Only 659,569 showed a detour out of which 115,085 had a known peering relationship. Thus, we are left with 544,484 detours out of which only 18,995 are unique (prefix, AS Path tuple).

To provide an understanding on the number of detours per peer in each country, we normalised the data by dividing the number of detours by the number of peers in the country. The reason to normalise the data is simple: RouteViews and RIPE RIS peers are not evenly distributed among different countries. Therefore, it is possible that more detours are seen in countries that have more peers due to more visibility.

An average number of detours per peer per country provides better insight. Out of 30 countries, only 12 countries observed a detour, with Russia showing most number of average detours (as shown in Figure 4).

 Figure 4: The average number of detours per peer per country provides better insight

Next, we studied the persistence of detours in terms of the number of hours they were seen alive. We found that 90% of the detours were transient; they lasted less than 72 hours. It is our expectation that detours that are caused by conscious traffic engineering should not show this transience. To further study the behaviour of detours, we defined two metrics:

• Flap Rate: measure of stability of a detour; how many times a detour disappeared and reappeared
• Duty Cycle: measure of uptime of a detour throughout the monthly measurement period

 Figure 5: Two metrics: flap rate and duty cycle

In the dataset we chose - January 2016 - Brazil, Russia and the US accounted for 90% of the detours. A scatter plot of flap rate vs. duty cycle is shown above. We observed that detours through the US are much more stable than detours in Brazil or Russia. Also, detours through Russia tended to have a much lower duty cycle.

We also studied a similar scatter plot for detours in Africa. In this case, most detours that appeared in the second quadrant (like the US) indicated very stable detours which are a result of conscious traffic engineering.

Our analysis has shown that while detours are common on the Internet, their behaviour may differ based on where they occur. Local peering and IXP conditions and the stability of the networks themselves may contribute to such distinct geographic characteristics.

What’s next?

Our work lays the ground for an important conversation about the challenges new regulatory frameworks will pose to researchers, industry and network operators. It provides some answers, but also brings attention to the problem and will hopefully stimulate more work in this area. Detecting routing detours either in the control plane or in the data plane requires reliable geolocation of IP addresses. Public databases lose accuracy at city-level geolocation. With the intention of geolocating infrastructure IP addresses, the RIPE NCC started the OpenIPMap project. We encourage researchers and network operators to contribute to it. Another challenge that our work faces is a lack of knowledge about peering relationships. With better peering detection systems and datasets, detour detection will improve as well. We encountered difficulty in finding measurement points with both control (BGP peers) and data (RIPE Atlas probes) monitors to correlate results. This problem cannot be easily solved, as it would take substantial effort to scale the existing infrastructures and we recommend hosting RIPE Atlas probes especially in those ASes that have BGP feeds to RouteViews or RIS.

Our tool, Netra, is currently running live and detecting detours from 300+ BGP peers. Visit detours.bgpmon.io and use RESTful API to find out if your prefix suffered a detour and send us feedback/feature requests.