More Web Proxy on the site http://driver.im/

Article

Toward topology dualism: improving the accuracy of AS annotations for routers

Authors:

Bradley Huffaker,

Amogh Dhamdhere,

Marina Fomenkov,

Kc ClaffyAuthors Info & Claims

PAM'10: Proceedings of the 11th international conference on Passive and active measurement

Pages 101 - 110

Published: 07 April 2010 Publication History

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.

References

[1]

Canet4 topology data, http://dooka.canet4.net/

[2]

Geant topology data, http://stats.geant2.net/lg/

[3]

I-light topology data, http://routerproxy.grnoc.iu.edu/ilight/

[4]

Internet2 topology data, http://vn.grnoc.iu.edu/Internet2

[5]

National lambdarail topology data, http://routerproxy.grnoc.iu.edu/nlr2/

[6]

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).

Digital Library

[7]

Augustin, B., Krishnamurthy, B., Willinger, W.: IXPs: Mapped?. In: Proc. Internet Measurement Conference, IMC (2009).

Digital Library

[8]

Bender, A., Sherwood, R., Spring, N.: Fixing Ally's Growing Pains with Velocity Modelling. In: Proc. Internet Measurement Conference, IMC (2008).

Digital Library

[9]

Cohen, R., Raz, D.: The Internet Dark Matter - On the Missing Links in the AS Connectivity Map. In: Proc. IEEE Infocom (2006).

[10]

Dimitropoulos, X., Krioukov, D., Fomenkov, M., Huffaker, B., Hyun, Y., Claffy, K., Riley, G.: AS Relationships: Inference and Validation. In: ACM SIGCOMM CCR (2007).

Digital Library

[11]

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).

Digital Library

[12]

Faloutsos, M., Faloutsos, P., Faloutsos, C.: On Power-law Relationships of the Internet Topology. In: Proc. ACM SIGCOMM (1999).

Digital Library

[13]

Govindan, R., Tangmunarunkit, H.: Heuristics for Internet Map Discovery. In: Proc. IEEE INFOCOM (2000).

[14]

Gunes, M.H.: APAR tool, http://itom.utdallas.edu/data/APAR.tar.gz (accessed 2008-07-02).

[15]

Gunes, M.H., Sarac, K.: Analytical IP Alias Resolution. In: Proc. IEEE International Conference on Communications, ICC (2006).

[16]

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).

Digital Library

[17]

Hyun, Y.: Archipelago Infrastructure, http://www.caida.org/projects/ark/

[18]

Hyun, Y., Broido, A., Claffy, K.: On Third-party Addresses in Traceroute Paths. In: Proc. Passive and Active Measurement Conference, PAM (2003).

[19]

Keys, K.: Internet-Scale IP Alias Resolution Techniques. In: ACM SIGCOMM CCR (2010).

Digital Library

[20]

Madhyastha, H.V., Katz-Bassett, E., Anderson, T., Krishnamurthy, A., Venkataramani, A.: iPlane: An Information Plane for Distributed Services. In: Proc. USENIX OSDI (2006).

Digital Library

[21]

Mahadevan, P., Hubble, C., Krioukov, D., Huffaker, B., Vahdat, A.: Orbis: Rescaling Degree Correlations to Generate Annotated Internet Topologies. In: Proc. ACM SIGCOMM (2007).

Digital Library

[22]

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).

Digital Library

[23]

Mao, Z.M., Rexford, J., Wang, J., Katz, R.H.: Towards an Accurate AS-level Traceroute Tool. In: Proc. ACM SIGCOMM (2003).

Digital Library

[24]

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).

Digital Library

[25]

RIPE NCC. Rcc12 bgp collector, http://www.ripe.net/projects/ris/ rawdata.html

[26]

University of Oregon RouteViews Project, http://www.routeviews.org/

[27]

Shavitt, Y., Shir, E.: DIMES: Let the Internet Measure Itself. In: ACM SIGCOMM CCR (October 2005).

Digital Library

[28]

Spring, N., Dontcheva, M., Rodrig, M., Wetherall, D.: How to Resolve IP Aliases. Technical Report UW-CSE-TR 04-05-04 (2004).

[29]

Spring, N., Mahajan, R., Wetherall, D.: Measuring ISP Topologies with Rocketfuel. In: Proc. ACM SIGCOMM (2002).

Digital Library

[30]

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).

Digital Library

[31]

Tangmunarunkit, H., Govindan, R., Shenker, S., Estrin, D.: The Impact of Routing Policy on Internet Paths. In: Proc. IEEE INFOCOM (2001).

[32]

Zhang, B., Liu, R., Massey, D., Zhang, L.: Collecting the Internet AS-level Topology. In: ACM SIGCOMM CCR (2005).

Digital Library

Cited By

Prehn LFeldmann ALevin DMislove AAmann JLuckie M(2021)How biased is our validation (data) for AS relationships?Proceedings of the 21st ACM Internet Measurement Conference10.1145/3487552.3487825(612-620)Online publication date: 2-Nov-2021
https://dl.acm.org/doi/10.1145/3487552.3487825
Motamedi RYeganeh BChandrasekaran BRejaie RMaggs BWillinger W(2019)On Mapping the Interconnections in Today’s InternetIEEE/ACM Transactions on Networking10.1109/TNET.2019.294036927:5(2056-2070)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1109/TNET.2019.2940369
Marder ALuckie MDhamdhere AHuffaker Bclaffy kSmith J(2018)Pushing the Boundaries with bdrmapITProceedings of the Internet Measurement Conference 201810.1145/3278532.3278538(56-69)Online publication date: 31-Oct-2018
https://dl.acm.org/doi/10.1145/3278532.3278538
Show More Cited By

Recommendations

Optimal Route Reflection Topology Design
LANC '18: Proceedings of the 10th Latin America Networking Conference

Autonomous Systems (ASes) exchange routing information about networks they can reach in the Internet, and the most widely extended way to connect them is by means of Border Gateway Protocol (BGP) sessions. ASes set up external BGP (eBGP) sessions ...
Collecting the internet AS-level topology

At the inter-domain level, the Internet topology can be represented by a graph with Autonomous Systems (ASes) as nodes and AS peerings as links. This AS-level topology graph has been widely used in a variety of research efforts. Conventionally this ...
An OSPF topology server: design and evaluation

In large scale, operational Internet protocol networks, creating timely, accurate and network-wide views of the intradomain topology is a fundamental problem. Topical network backbones consist of hundreds of routers, which establish routing adjacencies ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

PAM'10: Proceedings of the 11th international conference on Passive and active measurement

April 2010

232 pages

ISBN:3642123333

Editors:
Arvind Krishnamurthy
Department of Computer Science and Engineering, University of Washington, Seattle, WA
,
Bernhard Plattner
Computer Engineering and Networks Laboratory, Swiss Federal Institute of Technology, Zurich, Switzerland

Sponsors

COST Action TMA
Endace
armasuisse
Cisco Systems

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 07 April 2010

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Prehn LFeldmann ALevin DMislove AAmann JLuckie M(2021)How biased is our validation (data) for AS relationships?Proceedings of the 21st ACM Internet Measurement Conference10.1145/3487552.3487825(612-620)Online publication date: 2-Nov-2021
https://dl.acm.org/doi/10.1145/3487552.3487825
Motamedi RYeganeh BChandrasekaran BRejaie RMaggs BWillinger W(2019)On Mapping the Interconnections in Today’s InternetIEEE/ACM Transactions on Networking10.1109/TNET.2019.294036927:5(2056-2070)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1109/TNET.2019.2940369
Marder ALuckie MDhamdhere AHuffaker Bclaffy kSmith J(2018)Pushing the Boundaries with bdrmapITProceedings of the Internet Measurement Conference 201810.1145/3278532.3278538(56-69)Online publication date: 31-Oct-2018
https://dl.acm.org/doi/10.1145/3278532.3278538
Kiedanski DGrampín EAlvarez-Hamelin JVillas LBraga JRosário DGamess E(2018)The Atlas Vision of IPv6 in Latin AmericaProceedings of the 10th Latin America Networking Conference10.1145/3277103.3277122(40-47)Online publication date: 3-Oct-2018
https://dl.acm.org/doi/10.1145/3277103.3277122
Marder ASmith JGill PHeidemann JByers JGovindan R(2016)MAP-ITProceedings of the 2016 Internet Measurement Conference10.1145/2987443.2987468(397-411)Online publication date: 14-Nov-2016
https://dl.acm.org/doi/10.1145/2987443.2987468
Luckie MDhamdhere AHuffaker BClark Dclaffy kGill PHeidemann JByers JGovindan R(2016)bdrmapProceedings of the 2016 Internet Measurement Conference10.1145/2987443.2987467(381-396)Online publication date: 14-Nov-2016
https://dl.acm.org/doi/10.1145/2987443.2987467
Luckie MDhamdhere AClark DHuffaker Bclaffy kWilliamson CAkella ATaft N(2014)Challenges in Inferring Internet Interdomain CongestionProceedings of the 2014 Conference on Internet Measurement Conference10.1145/2663716.2663741(15-22)Online publication date: 5-Nov-2014
https://dl.acm.org/doi/10.1145/2663716.2663741
Choi HYoo JChung TChoi NKwon TChoi YPrasanna VBrebner GKeslassy I(2014)CoRCProceedings of the tenth ACM/IEEE symposium on Architectures for networking and communications systems10.1145/2658260.2658275(161-172)Online publication date: 20-Oct-2014
https://dl.acm.org/doi/10.1145/2658260.2658275
Shavitt YZilberman N(2013)Internet pop level mapsDataTraffic Monitoring and Analysis10.5555/2555672.2555677(82-103)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.5555/2555672.2555677
Donnet B(2013)Internet topology discoveryDataTraffic Monitoring and Analysis10.5555/2555672.2555676(44-81)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.5555/2555672.2555676
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents