Universita' degli Studi di Napoli ''Federico II'' (Italy)
An accurate knowledge of the Internet topology is essential for a deep understanding of such a complex and ever-evolving system. In the last decade many attempts have been done to overcome the incompleteness of BGP-derived AS-level topologies using traceroute. One source of inaccuracy is represented by third-party (TP) addresses.
Problem and impact
TP addresses are associated to interfaces which are not actually traversed by the IP packets sent toward the traceroute destination. In fact, according to RFC 1812, the source address of an ICMP error packet should correspond to the outgoing interface of the ICMP reply, rather than the interface on which the packet triggering the error was received. This behavior can cause a traceroute IP path to include a TP address. For instance, in the following figure the trace from a source S to a destination D contains the sequence (a,b,c) of IP addresses, where a and b are associated to the incoming interfaces of router A and B respectively while c is the interface used by router C to send ICMP replies to the traceroute originator, i.e. it is a third-party IP.
The occurrence of TP addresses can have a significant impact on some traceroute applications. The major impact is related to the inference of AS-level links from traceroute traces because TP addresses may cause the inference of false AS links. In figure, if b belongs to ASx and c belongs to ASz addressing space, then the IP-to-AS mapping of the trace will induce the wrong inference of the link ASx-ASz, while ASy, tough traversed, is totally hidden.
TP addresses may also impact subnet positioning and alias resolution.
To solve the TP address problem we propose the first active probing technique able to directly detect the presence of TP addresses in traceroute IP path. The technique requires two probes to understand if an IP address discovered by traceroute lies on the path (OP) or not (TP).
TP address detection technique is based in the IP prespecified timestamp option and requires no previous knowledge about routers interfaces, nor AS path provided by BGP or IP-to-AS mapping. Hereafter we adopt the notation PROBE X|ABCD, where PROBE is the probe type, X is the targeted destination and ABCD is the ordered list of prespecified IPs from which a timestamp is requested.
In order to understand if the hop Y discovered by traceroute toward D is a TP address, the proposed technique works according to the following steps:
The first step is necessary because there are other less common router behaviors that may lead the technique to misleading results. Indeed, adopting a conservative approach, a traceroute hop Y is considered non-classifiable every time there is no clear evidence that its router has a per network interface stamping behavior, as in the following circumstances:
In other words, a traceroute hop Y is considered classifiable only if it provides from 1 to 3 timestamps when directly probed with ICMP Echo Request Y|YYYY.
We also implemented and made publicly available an enhanced GNU GPLv3 traceroute version, based on Paris-Traceroute, which applies our technique to classify the hops discovered along the path toward the destination. Click here for the code and documentation.
Performing a large scale measurement campaign, we evaluate the technique showing that:
After removing the traces affected by filtering, the final dataset consisted of ~12M traces for a total number of ~ 443K addresses. The obtained results highlight an unexpected general trend: most traceroute traces contain many more TP than OP addresses. Hence, according to the router behaviour desribed above, most of the intermediate routers encountered along the path reply to the traceroute originator using an interface different from the ones traversed by the packets sent to the targeted destination.
Our dataset is publicly available at this link: http://traffic.comics.unina.it/tpa/pam2013_dataset.tgz
CitingWhen refering to our active probing technique or/and its implementation or the dataset please cite the following Reference:
If you are interested in collaborating with us or in opportunities in Traffic, please send an e-mail to Antonio Pescapè