Traceroute probe method and forward IP path inference

ABSTRACT

Several traceroute probe methods exist, each designed to perform better in a scenario where another fails. This paper examines the effects that the choice of probe method has on the inferred forward IP path by comparing the paths inferred with UDP, ICMP, and TCP-based traceroute methods to (1) a list of routable IP addresses, (2) a list of known routers, and (3) a list of well-known websites. We further compare methods by examining seven months of macroscopic Internet topology data collected by CAIDA's Archipelago infrastructure.

We found significant differences in the topology observed using different probe methods. In particular, we found that ICMP-based traceroute methods tend to successfully reach more destinations, as well as collect evidence of a greater number of AS links. UDP-based methods infer the greatest number of IP links, despite reaching the fewest destinations. We hypothesise that some per-flow load balancers implement different forwarding policies for TCP and UDP, and run a specific experiment to confirm this hypothesis.

REFERENCES

• 1: Van Jacobson. traceroute. ftp://ftp.ee.lbl.gov/traceroute.tar.gz.
• 2: Ehud Gavron. NANOG traceroute. http://momo.lcs.mit.edu/traceroute/traceroute.c.
• 3: J. C. Mogul , S. E. Deering, Path MTU discovery, RFC Editor, 1990
• 4: Michael Toren. tcptraceroute. http://michael.toren.net/code/tcptraceroute/.
• 5: Dan Kaminsky. paratrace. http://www.doxpara.com/read.php/docs/paratrace.html.
• 6: 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]
• 7: Alexa. http://www.alexa.com/.
• 8: R-fx Networks. Advanced policy firewall (APF). http://www.r-fx.ca/downloads/apf-0.9.6-3.tar.gz.
• 9: Bradley Huffak r , Daniel Plummer , David Moore , and k. Claffy, Topology Discovery by Active Probing, Proceedings of the 2002 Symposium on Applications and the Internet (SAINT) Workshops, p.90, January 28-February 01, 2002
• 10: Stefan Savage, Sting: a TCP-based network measurement tool, Proceedings of the 2nd conference on USENIX Symposium on Internet Technologies and Systems, p.7-7, October 11-14, 1999, Boulder, Colorado
• 11: 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]
• 12: Matthew Luckie. {patch} sys/netinet/udp_usrreq.c modifies received udp checksum, May 2007. http://www.freebsd.org/cgi/query-pr.cgi?pr=112471.
• 13: Matthew Luckie. scamper. http://www.wand.net.nz/scamper/.
• 14: P. V. Mockapetris, Domain names - implementation and specification, RFC Editor, 1987
• 15: Brice Augustin , Timur Friedman , Renata Teixeira, Measuring load-balanced paths in the internet, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA [doi>10.1145/1298306.1298329]
• 16: Routeviews shcip bgp snapshots. http://archive.routeviews.org/oix-route-views/.
• 17: Zhuoqing Morley Mao , Jennifer Rexford , Jia Wang , Randy H. Katz, Towards an accurate AS-level traceroute tool, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863996]
• 18: Young Hyun. Archipelago measurement infrastructure. http://www.caida.org/projects/ark/.
• 19: Patrick Verkaik. rv2atoms-0.4. http://www.caida.org/funding/routing/atoms/download/rv2atoms-0.4/.
• 20: Team Cymru. Bogon bit notation list v4.0 25 JAN 2008. http://www.cymru.com/Documents/bogon-bn.html.
• 21: Alberto Medina , Mark Allman , Sally Floyd, Measuring the evolution of transport protocols in the internet, ACM SIGCOMM Computer Communication Review, v.35 n.2, April 2005 [doi>10.1145/1064413.1064418]
• 22: John Heidemann, Yuri Pradkin, Ramesh Govindan, Christos Papadopoulos, Genevive Bartlett, and Joseph Bannister. Census and survey of the visible Internet (extended). ISI-TR 2008-649, USC/Information Sciences Institute, February 2008.
• 23: J. Postel, Internet Control Message Protocol, RFC Editor, 1981
• 24: Ramesh Govindan and Hongsuda Tangmunarunkit. Heuristics for Internet map discovery. In INFOCOM 2000, pages 1371--1380, Tel-Aviv, Israel, Mar 2000.
• 25: 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]
• 26: David Gelernter , Nicholas Carriero, Coordination languages and their significance, Communications of the ACM, v.35 n.2, p.97-107, Feb. 1992 [doi>10.1145/129630.129635]
• 27: Sascha Ossowski , Ronaldo Menezes, On coordination and its significance to distributed and multi-agent systems: Research Articles, Concurrency and Computation: Practice & Experience, v.18 n.4, p.359-370, April 2006 [doi>10.1002/cpe.v18:4]
• 28: David Gelernter, Generative communication in Linda, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.1, p.80-112, Jan. 1985 [doi>10.1145/2363.2433]
• 29: Nicholas Carriero , David Gelernter, How to write parallel programs: a first course, MIT Press, Cambridge, MA, 1990
• 30: CAIDA IPv4 routed /24 topology dataset. http://imdc.datcat.org/collection/1-0360-J.
• 31: Randy Bush , James Hiebert , Olaf Maennel , Matthew Roughan , Steve Uhlig, Testing the reachability of (new) address space, Proceedings of the 2007 SIGCOMM workshop on Internet network management, August 27-31, 2007, Kyoto, Japan [doi>10.1145/1321753.1321756]
• 32: 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
• 33: Ethan Katz-Bassett , Harsha V. Madhyastha , John P. John , Arvind Krishnamurthy , David Wetherall , Thomas Anderson, Studying black holes in the internet with Hubble, Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation, p.247-262, April 16-18, 2008, San Francisco, California

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

General Terms:
Measurement

Keywords:
macroscopic internet topology discovery, traceroute