Abstract
To describe, analyze, and model the topological and structural characteristics of the Internet, researchers use Internet maps constructed at the router or autonomous system (AS) level. Although progress has been made on each front individually, a dual graph representing connectivity of routers with AS labels remains an elusive goal. We take steps toward merging the router-level and AS-level views of the Internet. We start from a collection of traces, i.e. sequences of IP addresses obtained with large-scale traceroute measurements from a distributed set of vantage points. We use state-of-the-art alias resolution techniques to identify interfaces belonging to the same router. We develop novel heuristics to assign routers to ASes, producing an AS-router dual graph. We validate our router assignment heuristics using data provided by tier-1 and tier-2 ISPs and five research networks, and show that we successfully assign 80% of routers with interfaces from multiple ASes to the correct AS. When we include routers with interfaces from a single AS, the accuracy drops to 71%, due to the 24% of total inferred routers for which our measurement or alias resolution fails to find an interface belonging to the correct AS. We use our dual graph construct to estimate economic properties of the AS-router dual graph, such as the number of internal and border routers owned by different types of ASes. We also demonstrate how our techniques can improve IP-AS mapping, including resolving up to 62% of false loops we observed in AS paths derived from traceroutes.
Support for this work is provided by DHS N66001-08-C-2029 and NSF 05-51542.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Canet4 topology data, http://dooka.canet4.net/
Geant topology data, http://stats.geant2.net/lg/
I-light topology data, http://routerproxy.grnoc.iu.edu/ilight/
Internet2 topology data, http://vn.grnoc.iu.edu/Internet2
National lambdarail topology data, http://routerproxy.grnoc.iu.edu/nlr2/
Augustin, B., Cuvellier, X., Orgogozo, B., Viger, F., Friedman, T., Latapy, M.: Avoiding Traceroute Anonmalies with Paris Traceroute. In: Proc. Internet Measurement Conference, IMC (2006)
Augustin, B., Krishnamurthy, B., Willinger, W.: IXPs: Mapped?. In: Proc. Internet Measurement Conference, IMC (2009)
Bender, A., Sherwood, R., Spring, N.: Fixing Ally’s Growing Pains with Velocity Modelling. In: Proc. Internet Measurement Conference, IMC (2008)
Cohen, R., Raz, D.: The Internet Dark Matter - On the Missing Links in the AS Connectivity Map. In: Proc. IEEE Infocom (2006)
Dimitropoulos, X., Krioukov, D., Fomenkov, M., Huffaker, B., Hyun, Y., Claffy, K., Riley, G.: AS Relationships: Inference and Validation. In: ACM SIGCOMM CCR (2007)
Dimitropoulos, X., Krioukov, D., Vahdat, A., Riley, G.: Graph annotations in Modeling Complex Network Topologies. ACM Transactions on Modeling and Computer Simulation 19(4) (2009)
Faloutsos, M., Faloutsos, P., Faloutsos, C.: On Power-law Relationships of the Internet Topology. In: Proc. ACM SIGCOMM (1999)
Govindan, R., Tangmunarunkit, H.: Heuristics for Internet Map Discovery. In: Proc. IEEE INFOCOM (2000)
Gunes, M.H.: APAR tool, http://itom.utdallas.edu/data/APAR.tar.gz (accessed 2008-07-02)
Gunes, M.H., Sarac, K.: Analytical IP Alias Resolution. In: Proc. IEEE International Conference on Communications, ICC (2006)
He, Y., Siganos, G., Faloutsos, M., Krishnamurthy, S.V.: A Systematic Framework for Unearthing the Missing Links: Measurements and Impact. In: Proc. USENIX/SIGCOMM NSDI (2007)
Hyun, Y.: Archipelago Infrastructure, http://www.caida.org/projects/ark/
Hyun, Y., Broido, A., Claffy, K.: On Third-party Addresses in Traceroute Paths. In: Proc. Passive and Active Measurement Conference, PAM (2003)
Keys, K.: Internet-Scale IP Alias Resolution Techniques. In: ACM SIGCOMM CCR (2010)
Madhyastha, H.V., Katz-Bassett, E., Anderson, T., Krishnamurthy, A., Venkataramani, A.: iPlane: An Information Plane for Distributed Services. In: Proc. USENIX OSDI (2006)
Mahadevan, P., Hubble, C., Krioukov, D., Huffaker, B., Vahdat, A.: Orbis: Rescaling Degree Correlations to Generate Annotated Internet Topologies. In: Proc. ACM SIGCOMM (2007)
Mahadevan, P., Krioukov, D., Fomenkov, M., Huffaker, B., Dimitropoulos, X., Claffy, K., Vahdat, A.: The Internet AS-Level Topology: Three Data Sources and One Definitive Metric. In: ACM SIGCOMM CCR (2005)
Mao, Z.M., Rexford, J., Wang, J., Katz, R.H.: Towards an Accurate AS-level Traceroute Tool. In: Proc. ACM SIGCOMM (2003)
Oliveira, R., Pei, D., Willinger, W., Zhang, B., Zhang, L.: In Search of the Elusive Ground Truth: The Internet’s AS-level Connectivity Structure. In: Proc. ACM SIGMETRICS (2008)
RIPE NCC. Rcc12 bgp collector, http://www.ripe.net/projects/ris/rawdata.html
University of Oregon RouteViews Project, http://www.routeviews.org/
Shavitt, Y., Shir, E.: DIMES: Let the Internet Measure Itself. In: ACM SIGCOMM CCR (October 2005)
Spring, N., Dontcheva, M., Rodrig, M., Wetherall, D.: How to Resolve IP Aliases. Technical Report UW-CSE-TR 04-05-04 (2004)
Spring, N., Mahajan, R., Wetherall, D.: Measuring ISP Topologies with Rocketfuel. In: Proc. ACM SIGCOMM (2002)
Tangmunarunkit, H., Doyle, J., Govindan, R., Willinger, W., Jamin, S., Shenker, S.: Does AS Size Determine Degree in AS Topology? In: ACM SIGCOMM CCR (2001)
Tangmunarunkit, H., Govindan, R., Shenker, S., Estrin, D.: The Impact of Routing Policy on Internet Paths. In: Proc. IEEE INFOCOM (2001)
Zhang, B., Liu, R., Massey, D., Zhang, L.: Collecting the Internet AS-level Topology. In: ACM SIGCOMM CCR (2005)
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
Huffaker, B., Dhamdhere, A., Fomenkov, M., claffy, k. (2010). Toward Topology Dualism: Improving the Accuracy of AS Annotations for Routers. 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_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-12334-4_11
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)