Fixing ally's growing pains with velocity modeling

ABSTRACT

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(n²) 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.

REFERENCES

• 1: Brice Augustin , Xavier Cuvellier , Benjamin Orgogozo , Fabien Viger , Timur Friedman , Matthieu Latapy , Clémence Magnien , Renata Teixeira, Avoiding traceroute anomalies with Paris traceroute, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177100]
• 2: Steven M. Bellovin, A technique for counting natted hosts, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637243]
• 3: Benoit Donnet , Philippe Raoult , Timur Friedman , Mark Crovella, Efficient algorithms for large-scale topology discovery, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 4: Nick Feamster , David G. Andersen , Hari Balakrishnan , M. Frans Kaashoek, Measuring the effects of internet path faults on reactive routing, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 5: R. Govindan and H. Tangmunarunkit. Heuristics for Internet map discovery. In Infocom, 2000.
• 6: M. H. Gunes and K. Sarac. Analytical IP alias resolution. In International Conference on Communications, 2006.
• 7: M. H. Gunes and K. Sarac. Importance of IP alias resolution in sampling Internet topologies. In Global Internet Symposium, 2007.
• 8: Ningning Hu , Li (Erran) Li , Zhuoqing Morley Mao , Peter Steenkiste , Jia Wang, Locating internet bottlenecks: algorithms, measurements, and implications, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 9: Lun Li , David Alderson , Walter Willinger , John Doyle, A first-principles approach to understanding the internet's router-level topology, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 10: Harsha V. Madhyastha , Thomas Anderson , Arvind Krishnamurthy , Neil Spring , Arun Venkataramani, A structural approach to latency prediction, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177092]
• 11: Ratul Mahajan , Neil Spring , David Wetherall , Thomas Anderson, User-level internet path diagnosis, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 12: Jean-Jacques Pansiot , Dominique Grad, On routes and multicast trees in the Internet, ACM SIGCOMM Computer Communication Review, v.28 n.1, p.41-50, Jan. 1998 [doi>10.1145/280549.280555]
• 13: Larry Peterson , Tom Anderson , David Culler , Timothy Roscoe, A blueprint for introducing disruptive technology into the Internet, ACM SIGCOMM Computer Communication Review, v.33 n.1, p.59-64, January 2003 [doi>10.1145/774763.774772]
• 14: Rob Sherwood , Adam Bender , Neil Spring, Discarte: a disjunctive internet cartographer, Proceedings of the ACM SIGCOMM 2008 conference on Data communication, August 17-22, 2008, Seattle, WA, USA
• 15: Rob Sherwood , Neil Spring, Touring the internet in a TCP sidecar, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177093]
• 16: Robert H. Shumway , David S. Stoffer, Time Series Analysis and Its Applications (Springer Texts in Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 17: Neil Spring , Ratul Mahajan , David Wetherall, Measuring ISP topologies with rocketfuel, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 18: Neil Spring , David Wetherall , Tom Anderson, Scriptroute: a public internet measurement facility, Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems, p.17-17, March 26-28, 2003, Seattle, WA
• 19: Renata Teixeira , Keith Marzullo , Stefan Savage , Geoffrey M. Voelker, In search of path diversity in ISP networks, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948247]
• 20: Garrett R. Yaun , David Bauer , Harshad L. Bhutada , Christopher D. Carothers , Murat Yuksel , Shivkumar Kalyanaraman, Large-scale network simulation techniques: examples of TCP and OSPF models, ACM SIGCOMM Computer Communication Review, v.33 n.3, July 2003 [doi>10.1145/956993.956999]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring

General Terms:
Experimentation, Measurement

Keywords:
alias resolution, ally, ip identifier, velocity modeling