TY - GEN

T1 - Reduce, Reuse, Recycle

T2 - 20th ACM Internet Measurement Conference, IMC 2020

AU - Giotsas, Vasileios

AU - Koch, Thomas

AU - Fazzion, Elverton

AU - Cunha, Ítalo

AU - Calder, Matt

AU - Madhyastha, Harsha V.

AU - Katz-Bassett, Ethan

N1 - 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.

PY - 2020/10/27

Y1 - 2020/10/27

N2 - 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.

AB - 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.

KW - Internet topology

KW - measurements

KW - path changes

KW - routing

KW - traceroute

U2 - 10.1145/3419394.3423654

DO - 10.1145/3419394.3423654

M3 - Conference contribution/Paper

AN - SCOPUS:85097272778

T3 - Proceedings of the ACM SIGCOMM Internet Measurement Conference, IMC

SP - 247

EP - 265

BT - IMC 2020 - Proceedings of the 2020 ACM Internet Measurement Conference

PB - Association for Computing Machinery (ACM)

Y2 - 27 October 2020 through 29 October 2020

ER -