Home > Research > Publications & Outputs > Reduce, Reuse, Recycle

Text available via DOI:

View graph of relations

Reduce, Reuse, Recycle: Repurposing Existing Measurements to Identify Stale Traceroutes

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNConference contribution/Paperpeer-review

  • Vasileios Giotsas
  • Thomas Koch
  • Elverton Fazzion
  • Ítalo Cunha
  • Matt Calder
  • Harsha V. Madhyastha
  • Ethan Katz-Bassett


Many systems rely on traceroutes to monitor or characterize the Internet. The quality of the systems' inferences depends on the completeness and freshness of the traceroutes, but the refreshing of traceroutes is constrained by limited resources at vantage points. Previous approaches predict which traceroutes are likely out-of-date in order to allocate measurements, or monitor BGP feeds for changes that overlap traceroutes. Both approaches miss many path changes for reasons including the difficulty in predicting changes and the coarse granularity of BGP paths. This paper presents techniques to identify out-of-date traceroutes without issuing any measurements, even if a change is not visible at BGP granularity. We base our techniques on two observations. First, although BGP updates encode routes at AS granularity, routers issue updates when they change intra-domain routes or peering points within the same AS path. Second, route changes correlate across paths, and many publicly available traceroutes exist. Our techniques maintain an atlas of traceroutes by monitoring BGP updates and publicly available traceroutes for signals to mark overlapping atlas traceroutes as stale. We focus our analysis of traceroute path changes at the granularity of border router IPs which provides an abstraction finer than AS- or PoP-level but is not affected by the periodicity of intra-domain load balancers. Our evaluation indicates that 80% of the traceroutes that our techniques signal as stale have indeed changed, even though the AS hops remained the same. Our techniques combine to identify 79% of all border IP changes, without issuing a single online measurement.

Bibliographic note

Funding Information: Our work overcomes this tradeoff by inferring which traceroutes in a corpus have gone stale due to path changes, allowing other traceroutes to be safely used for long periods of time and avoiding wasting measurements on unchanged paths. Our techniques use patterns in BGP updates as signals for changes not explicitly visible in the updates, and they monitor publicly available traceroutes to look for changes that overlap the corpus. Combined, they detect 81% of path changes. By recycling publicly available data, our techniques enable the safe reuse of traceroutes known to be unchanged and reduce the measurement budget needed to keep a corpus fresh. Acknowledgements. This paper has been partially funded by a RIPE NCC Community Projects Fund, NSF grant 1836872, CAPES, CNPq, and FAPEMIG. We would like to thank the anonymous reviewers and our shepherd Cristel Pelsser for their insightful comments, and Kevin Vermeulen for aiding in the evaluation of the impact of interdomain load balancers on our techniques. Publisher Copyright: © 2020 ACM. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.