Abstract
Active and passive measurements for topology discovery have known an impressive growth during the last decade. If a lot of work has been done regarding inter-domain topology discovery and modeling, only a few papers raise the question of how to extract intra-domain topologies from measurements results.
In this paper, based on a large dataset collected with mrinfo, a multicast tool that silently discovers all interfaces of a router, we provide a mechanism for retrieving intra-domain topologies. The main challenge is to assign an AS number to a border router whose IP addresses are not mapped to the same AS. Our algorithm is based on probabilistic and empirical IP allocation rules. The goal of our pool of rules is to converge to a consistent router to AS mapping. We show that our router-to-AS algorithm results in a mapping in more than 99% of the cases. Furthermore, with mrinfo, point-to-point links between routers can be distinguished from multiple links attached to a switch, providing an accurate view of the collected topologies. Finally, we provide a set of large intra-domain topologies in various formats.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Donnet, B., Friedman, T.: Internet topology discovery: a survey. IEEE Communications Surveys and Tutorials 9(4), 2–15 (2007)
Gunes, M.H., Sarac, K.: Importance of IP alias resolution in sampling Internet topologies. In: Proc. IEEE Global Internet Symposium (May 2007)
Spring, N., Mahajan, R., Wetherall, D.: Measuring ISP topologies with Rocketfuel. In: Proc. ACM SIGCOMM (August 2002)
Jacobson, V.: Mrinfo (1995), http://cvsweb.netbsd.org/bsdweb.cgi/src/usr.sbin/mrinfo/?only_with_tag=MAIN
Mérindol, P., Van den Schriek, V., Donnet, B., Bonaventure, O., Pansiot, J.J.: Quantifying ASes multiconnectivity using multicast information. In: Proc. ACM USENIX Internet Measurement Conference (IMC) (November 2009)
Pansiot, J.J.: Mrinfo dataset, http://svnet.u-strasbg.fr/mrinfo/
Pansiot, J., Mérindol, P., Donnet, B., Bonaventure, O.: Internet topology discovery through mrinfo probing. TR 2009-01, Université catholique de Louvain (UCL), (October 2009), http://inl.info.ucl.ac.be/content/mrinfo
Deering, S.: Host extensions for IP multicasting. In: RFC 1112, Internet Engineering Task Force (August 1989)
Zhao, X., Pei, D., Wang, L., Massey, D., Mankin, A., Wu, S.F., Zhang, L.: An analysis of BGP multiple origin AS (MOAS) conflicts. In: Proc. ACM SIGCOMM Internet Measurement Workshop (IMW) (October 2001)
Claffy, K., Hyun, Y., Keys, K., Fomenkov, M., Krioukov, D.: Internet mapping: from art to science. In: Proc. IEEE Cybersecurity Applications and Technologies Conference for Homeland Security CATCH (March 2009)
CAIDA: AS relationships (2009), http://www.caida.org/data/active/as-relationships/index.xml
Zhang, M., Ruan, Y., Pai, V., Rexford, J.: How DNS misnaming distorts internet topology mapping. In: Proc. USENIX Annual Technical Conference (May/June 2006)
Teixeira, R., Marzullo, K., Savage, S., Voelker, G.: In search of path diversity in ISP networks. In: Proc. ACM SIGCOMM Internet Measurement Conference (IMC) (October 2003)
Sherwood, R., Bender, A., Spring, N.: DisCarte: A disjunctive Internet cartographer. In: Proc. ACM SIGCOMM (August 2008)
Mao, Z.M., Rexford, J., Wang, J., Katz, R.H.: Towards an accurate AS-level traceroute tool. In: Proc. ACM SIGCOMM (August 2003)
Mao, Z., Johnson, D., Rexford, J., Wang, J., Katz, R.: Scalable and accurate identification of AS-level forwarding paths. In: Proc. IEEE INFOCOM (April 2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pansiot, JJ., Mérindol, P., Donnet, B., Bonaventure, O. (2010). Extracting Intra-domain Topology from mrinfo Probing. In: Krishnamurthy, A., Plattner, B. (eds) Passive and Active Measurement. PAM 2010. Lecture Notes in Computer Science, vol 6032. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12334-4_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-12334-4_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12333-7
Online ISBN: 978-3-642-12334-4
eBook Packages: Computer ScienceComputer Science (R0)