Fixing ally's growing pains with velocity modeling

TitleFixing ally's growing pains with velocity modeling
Publication TypeConference Papers
Year of Publication2008
AuthorsBender A, Sherwood R, Spring N
Conference NameProceedings of the 8th ACM SIGCOMM conference on Internet measurement
Date Published2008///
Conference LocationNew York, NY, USA
ISBN Number978-1-60558-334-1
Keywordsalias resolution, ally, ip identifier, velocity modeling

Mapping the router topology is an important component of Internet measurement. Alias resolution, the process of mapping IP addresses to routers, is critical to accurate Internet mapping. Ally, a popular alias resolution tool, was developed to resolve aliases in individual ISPs, but its probabilistic accuracy and need to send O(n2) probes to infer aliases among n IP addresses make it unappealing for large-scale Internet mapping. In this paper, we present RadarGun, a tool that uses IP identifier velocity modeling to improve the accuracy and scalability of the Ally-based resolution technique. We provide analytical bounds on Ally's accuracy and validate our predicted aliases against Ally. Additionally, we show that velocity modeling requires only O(n) probes and thus scales to Internet-sized mapping efforts.