Network Topology; IGMP Probing; MERLIN; Router level; alias resolution; traceroute
Abstract :
[en] For a long time, traceroute measurements combined with alias resolution methods have been the sole way to collect Internet router level maps. Recently, a new approach has been introduced with the use of a multicast management tool, mrinfo, and a recursive probing scheme. In this paper, after analyzing advantages and drawbacks of probing approaches based on traceroute and mrinfo, we propose a hybrid discovery tool, MERLIN (MEasure the Router Level of the INternet), mixing mrinfo and traceroute probes. Using a central server controlling a set of distributed vantage points in order to increase the exploration coverage while limiting the probing redundancy, the purpose of MERLIN is to provide an accurate router level map inside a targeted Autonomous System (AS). MERLIN also takes advantage of alias resolution methods to reconnect scattered mul- ticast components. To evaluate the performance of MERLIN, we report experimental results describing its efficiency in topology exploration and reconstruction of several ASes.
B. Donnet and T. Friedman, "Internet topology discovery: a survey", IEEE Commun. Surveys Tutorials, vol. 9, no. 4, pp. 2-15, December 2007.
H. Haddadi, G. Iannaccone, A. Moore, R. Mortier, and M. Rio, "Network topologies: Inference, modeling and generation", IEEE Commun. Surveys Tutorials, vol. 10, no. 2, pp. 48-69, April 2008.
k. claffy, Y. Hyun, K. Keys, M. Fomenkov, and D. Krioukov, "Internet mapping: from art to science", in Proc. IEEE Cybersecurity Applications and Technologies Conference for Homeland Security (CATCH), March 2009.
H. V. Madhyastha, T. Isdal, M. Piatek, C. Dixon, T. Anderson, A. Krishnamurthy, and A. Venkataramani, "iPlane: An information plane for distributed services", in Proc. USENIX Symposium on Operating Systems Design and Implementation (OSDI), November 2006.
Y. Shavitt and E. Shir, "DIMES: Let the internet measure itself", ACM SIGCOMM Computer Communication Review, vol. 35, no. 5, October 2005.
N. Spring, R. Mahajan, and D. Wetherall, "Measuring ISP topologies with Rocketfuel", in Proc. ACM SIGCOMM, August 2002.
M. Luckie, "Scamper: a scalable and extensible packet prober for active measurement of the Internet", in Proc. USENIX/ACM Internet Measurement Conference (IMC), November 2010.
V. Jacobson et al., "traceroute", UNIX", man page, 1989, see source code: ftp://ftp. ee.lbl.gov/traceroute.tar.gz.
A. Bender, R. Sherwood, and N. Spring, "Fixing Ally's growing pains with velocity modeling", in Proc. ACM/USENIX Internet Measurement Conference (IMC), October 2008.
M. H. Gunes and K. Sarac, "Resolving IP aliases in building traceroutebased internet maps", IEEE/ACM Trans. Netw. (ToN), vol. 17, no. 6, pp. 1738-1751, December 2009.
J. Sherry, E. Katz-Bassett, M. Pimenova, H. V. Madhyastha, A. Krishnamurthy, and T. Anderson, "Resolving IP aliases with prespecified timestamps", in Proc. ACM/USENIX Internet Measurement Conference (IMC), November 2010.
P. Merindol, V. Van den Schriek, B. Donnet, O. Bonaventure, and J.-J. Pansiot, "Quantifying ASes multiconnectivity using multicast information", in Proc. ACM USENIX Internet Measurement Conference (IMC), November 2009.
J.-J. Pansiot, P. Merindol, B. Donnet, and O. Bonaventure, "Extracting intra-domain topology from mrinfo probing", in Proc. Passive and Active Measurement Conference (PAM), April 2010.
P. Merindol, B. Donnet, O. Bonaventure, and J.-J. Pansiot, "On the impact of layer-2 on node degree distribution", in Proc. ACM/USENIX Internet Measurement Conference (IMC), November 2010.
B. Augustin, X. Cuvellier, B. Orgogozo, F. Viger, T. Friedman, M. Latapy, C. Magnien, and R. Teixeira, "Avoiding traceroute anomalies with Paris traceroute", in Proc. ACM/USENIX Internet Measurement Conference (IMC), October 2006.
B. Huffaker, D. Plummer, D. Moore, and k. claffy, "Topology discovery by active probing", in Proc. Symposium on Applications and the Internet Workshop (SAINTS), January 2002.
S. Deering, "Host extensions for IP multicasting", Internet Engineering Task Force, RFC 1112, August 1989.
T. Pusateri, "Distance vector multicast routing protocol version 3 (DVMRP)", Internet Engineering Task Force, Internet Draft (Work in Progress) draft-ietf-idmr-dvmrp-v3-11, October 2003.
P. Sharma, E. Perry, and R. Malpani, "IP multicast operational network management: Design, challenges, and experiences", IEEE Network, vol. 17, no. 2, pp. 49-55, March 2003.
V. Jacobson, "mrinfo", 1995, http://cvsweb.netbsd.org/bsdweb. cgi/src/usr.sbin/mrinfo/?only-with-tag=MAIN.
P. Merindol, B. Donnet, J.-J. Pansiot, M. Luckie, and Y. Hyun, "MERLIN: MEasure the Router Level of the INternet", in Proc. 7th Euro-NF Conference on Next Generation Internet (NGI), June 2011.
P. Marchetta, "An Internet topology discovery approach based on multicast", October 2010, M. S. Thesis, University of Napoli Federico II, http://wpage.unina.it/pescape/doc/MSThesisPMarchetta.pdf.
C. Magnien, F. Ouedraogo, G. Valadon, and M. Latapy, "Fast dynamics in internet topology: preliminary observations and explanations", in Proc. Fourth International Conference on Internet Monitoring and Protection (ICIMP09), 2009.
B. Huffaker, k. claffy, and E. Nemeth, "Tools to visualize the Internet multicast backbone", in Proc. International Networking Conference (INET), June 1999.
A. Botta, W. de Donato, A. Pescapé, and G. Ventre, "Discovering topologies at router level: Part II", in Proc. IEEE Global Telecommunications Conference (GLOBECOM), November 2007.
N. Spring, D. Wetherall, and T. Anderson, "Scriptroute: A public Internet measurement facility", in Proc. USENIX Symposium on Internet Technologies and Systems (USITS), March 2002.
B. Donnet, P. Raoult, T. Friedman, and M. Crovella, "Deployment of an algorithm for large-scale topology discovery", IEEE J. Sel. Areas Commun. (JSAC), Sampling the Internet: Techniques and Applications, vol. 24, no. 12, pp. 2210-2220, Dec. 2006. (Pubitemid 44955762)
K. Chen, D. R. Choffnes, R. Potharaju, Y. Chen, F. E. Bustamante, D. Pei, and Y. Zhao, "Where the sidewalk ends: Extending the Internet AS graph using traceroutes from P2P users", in Proc. ACM CoNEXT, December 2009.
J. J. Pansiot and D. Grad, "On routes and multicast trees in the Internet", ACM SIGCOMM Computer Communication Review, vol. 28, no. 1, pp. 41-50, January 1998. (Pubitemid 128566432)
K. Keys, "iffinder", a tool for mapping interfaces to routers. See http://www.caida.org/tools/measurement/iffinder/.
R. Sherwood, A. Bender, and N. Spring, "Discarte: a disjunctive Internet cartographer", in Proc. ACM SIGCOMM, August 2008.
