An efficient approach to multi-level route analytics

Contrasting multi-level routes (e.g., IP, subnet, AS levels) is an analytical primitive underpinning many applications, such as route asymmetry and/or diversity measurement, route change characterization, efficient route-tracing design, and others. We are the first to identify that current approaches incur redundant node comparisons, because they treat each level independently. We propose a new approach called rtd that eliminates the redundancy, therefore improves the analysis efficiency, by integrating all levels recursively. Our extensive evaluations on simulated traces and real data from Ark, FastMapping, and iPlane datasets show that rtd eliminates 85% comparisons on average and doubles the analysis speed. Finally, we design a route clustering application using rtd, and demonstrate how it aids the monitoring of an ISP transition.