Detecting IXPs in Traceroute Paths Using traIXroute

Challenges

“Is observing an IP address from an IXP prefix sufficient evidence to conclude that a traceroute path crossed an IXP?”

Taking into account that (i) routers can reply to traceroute probes with third-party IP addresses from IXP subnets; (ii) the available IXP IP address prefix data may be inaccurate; and (iii) IXPs could use allocated addresses not only in the IXP subnet but also in other operational subnets, the answer to the question above should be negative.

To illustrate point (i) especially, consider the example shown in Figure 1: a router connected to the IXP fabric could reply to traceroute probes using a source IP address from any of its interfaces, including the interface on the IXP subnet. Traceroute paths that do not cross the IXP, like the dotted one in Figure 1, can include a reply with a source IP address from the IXP subnet. Therefore, the path appears to have an IP address from an IXP subnet, even if the IXP is not crossed. Our goal is to detect paths that cross the IXP fabric like the dashed one in Figure 1.


Figure 1: An IXP fabric connected to two ASes. The dashed path crosses the IXP, while the dotted path does not cross the IXP, although it can yield an IXP address in traceroute replies.

Datasets

traIXroute uses data from the PeeringDB (PDB),  Packet Clearing House (PCH) and Route Views to detect IXPs in traceroute paths. It uses in particular three types of data:

1. IXP membership data : triplets of the form {IP address → IXP Name, ASN} retrieved from the PDB and PCH that provide 1) the exact IP addresses of router interfaces connected to the IXP network; and 2) the ASes that these routers belong to. This information maps an IXP IP address to its AS.

2. IXP IP address prefixes data: tuplets of the form {IP Prefix → IXP} also retrieved from the PDB and PCH, which map IPv4 address prefixes to IXPs.

3. Route Views Prefix to AS mapping dataset : tuplets of the form {IP prefix → AS} provided by CAIDA based on data from Route Views. This data specifies which IP prefixes are associated with which ASes. They are used to map IPv4 addresses to ASNs.

IXP Detection Mechanism

traIXroute detects and identifies at which hop an IXP is crossed in traceroute paths, following a three-step process that exploits the available information in the three datasets. Using a sliding window of one or two hops on traceroute paths, the tool applies the following steps to infer an IXP crossing:

Step 1: It detects IXP IPs in traceroute paths based on IXP membership triplets or  IXP prefixes.

Step 2: It resolves IP addresses to ASes and checks the IXP membership of the ASes adjacent to the observed IXP address(es).

Step 3: It checks custom 16 IXP detection rules [1] , which formalise expert knowledge and careful reasoning on the available data, that identify IXPs when multiple evidence concurs.

Evaluation

To evaluate our methodology, we used 31.8 million traceroute paths collected from  CAIDA’s ARK measurement infrastructure in January 2015. We applied our IXP detection rules and made the following interesting observations (among others [1]): 

• In 76,86% of the IXP paths, we can detect the IXP using what we call strong evidence rules [1], which match multiple criteria to identify an IXP crossing more reliably than with just IXP prefixes.
   
• In 81,79% of the IXP paths, we match IXP membership data (i.e., triplets of the form {IP address → IXP Name, ASN}, which include more specific data compared to IP prefixes), which shows that PDB and PCH provide rich IXP membership data for the purpose of IXP detection .

• The IXP link is almost always before the observed IXP address (as expected). This is because routers typically reply with the IP address of the inbound interface.

• In 1.36% of the IXP paths, we observe two consecutive IXP IPs from the same IXP subnet. This points to i) inefficient routing due to the BGP path selection process that relies on AS-level paths and ignores layer-2 topologies; or ii) replies from the outbound and inbound interfaces of consecutive BGP routers on the IXP. In addition, in  1.2% of the IXP paths, we observe two consecutive IXP IP addresses from different IXP prefixes. 

Use Case

Trying to answer what we can learn about IXPs in traceroute paths using traIXroute, we found that in the used traceroute dataset from CAIDA:

• Approximately 20% of all paths cross an IXP.

• The IXP hop is located near the middle of the path, on average at approximately the sixth IP hop. 

As a next step, we analysed: 1) which IXPs attract the most paths; and 2) how the number of paths an IXP attracts compares with the number of their member ASes.

Figure 2 shows a scatter plot of the number of AS members per IXP versus the number of paths that cross the IXP. We see that  the top three IXPs in terms of paths are located in Europe: AMS-IX, LINX and DE-CIX. However, they are close to the 95th-percentile confidence intervals, which means that compared to the average, they have more members than paths. In contrast, many US IXPs (shown with brown colour) have more paths than their number of members indicates. 

Figure 2: Scatter plot of number of AS members vs. number of paths per IXP along with fitted line and 95% confidence intervals. IXPs are grouped by continent.  The correlation coefficient between the number of IXP members and IXP paths is 0.8. 

Design & Functionalities

traIXroute is a Python 3 tool following a modular design that offers full customisation for users and can be easily extended with new IXP detection rules. In the background, traIXroute uses the standard traceroute tool or the scamper tool [2], which implements the Paris traceroute technique to deal with inaccurate paths due to load balancers [3].

Besides the flexibility to choose between scamper and traceroute, the tool also offers a new dataset with IXP membership and prefixes data after merging the PDB and PCH databases, which can be updated automatically from the command line. For merging, it uses heuristics to avoid artifacts due to inconsistent IXP identifiers in the two databases.

Another advantage of traIXroute is that a user can import .json files containing external traceroute measurements. This drastically limits the workload of the tool since no probing has to be performed.

Finally, in the next release (ver. 2.0), traIXroute will include features to enhance inter-operability with the RIPE Atlas project. In particular, a user will be able to import .json files produced from RIPE Atlas or fetch the results of any measurement directly from the RIPE database by setting the measurement ID and other optional filters (i.e. start date, end date, probes) in the command line.  In addition, traIXroute will offer the flexibility to create a new traceroute-based measurement in the RIPE Atlas platform and detect IXP crossing links after finishing the measurement without visiting the RIPE Atlas web interface to create and start a new measurement.

Conclusion

Internet users, network operators, and researchers would benefit from knowing which IXPs packets go through. To help achieve this goal, traIXroute is available here [4]. All the necessary information to download, install, and use traIXroute can be found on the website. The first version (1.0) of traIXroute was released in May 2016.

traIXroute was used in the RIPE Atlas hackathon that took place in Copenhagen in May 2016. One hackathon team integrated traIXroute with the IXP Country Jedi project, which maps and visualises the use of IXPs in different countries. The team used traIXroute to more accurately infer IXP crossings. We are continuing this collaboration and are planning further improvements to the IXP Country Jedi project. Watch this space for updates!

References

[1] G. Nomikos, X. Dimitropoulos. “ traIXroute: Detecting IXPs in traceroute paths ". In: Proc. PAM (2016)

[2] Luckie, M.: Scamper: a scalable and extensible packet prober for active measurement of the internet. In: Proc. ACM IMC (2010)

[3] Augustin, B., Friedman, T., Teixeira, R.: Multipath tracing with paris traceroute. In: Proc. IEEE End-to-End Monitoring Techniques and Services Workshop (2007)

[4] traIXroute, www.inspire.edu.gr/traIXroute