Extracting Routing Events from Traceroutes: a Matter of Empathy

With the increasing diffusion of Internet probing technologies, a large amount of regularly collected traceroutes are available for Internet service providers (ISPs) at low cost. We show how it is possible, given solely an arbitrary set of traceroutes, to spot routing paths that change similarly over time and aggregate them into inferred routing events. With respect to previous works, our approach does not require any knowledge of the network, does not need complex integration of several data sources, and exploits the asynchronicity of measurements to accurately position events in time. The formal model at the basis of our methodology revolves around the notion of empathy, a relation that binds similarly behaving traceroutes. The correctness and completeness of our approach are based on structural properties that are easily expressed in terms of empathic measurements. We perform experiments with data from public measurement infrastructures like RIPE Atlas, showing the effectiveness of our algorithm in distilling significant events from a large amount of traceroute data. We also validate the accuracy of the inferred events against ground-truth knowledge of routing changes originating from induced and spontaneous routing events. Given these promising results, we believe that our methodology can be an effective aid for troubleshooting at the ISPs level. The source code of our algorithm is publicly available at https://github.com/empadig.