Matthew Luckie
David Clark
ABSTRACT
We tackle the tedious and unsolved problem of automatically and correctly inferring network boundaries in traceroute. We explain why such a conceptually simple task is so hard in the real world, and how lack of progress has impeded a wide range of research and development efforts for decades. We develop and validate a method that uses targeted traceroutes, knowledge of traceroute idiosyncrasies, and codification of topological constraints in a structured set of heuristics, to correctly identify interdomain links at the granularity of individual border routers. In this study we focus on the network boundaries we have most confidence we can accurately infer in the presence of sampling bias: interdomain links attached to the network launching the traceroute. We develop a scalable implementation of our algorithm and validate it against ground truth information provided by four networks on 3,277 links, which showed 96.3% -- 98.9% of our inferences were correct.
With 19 vantage points (VPs) distributed across a large U.S. broadband provider, we use our method to reveal the tremendous density of router-level interconnection between some ASes. In January 2016, the broadband provider had 45 router-level links with a Tier-1 peer. We also quantify the VP deployment required to observe this ISP's interdomain connectivity, with 17 VPs required to observe all 45 links. Our method forms the cornerstone of the system we are building to map interdomain performance, and we release our code.
- B. Ager, N. Chatzis, A. Feldmann, N. Sarrar, S. Uhlig, and W. Willinger. Anatomy of a large European IXP. In SIGCOMM, 2012. Google Scholar
Digital Library
- B. Augustin, X. Cuvellier, B. Orgogozo, F. Viger, T. Friedman, M. Latapy, C. Magnien, and R. Teixeira. Avoiding traceroute anomalies with Paris traceroute. In IMC, Oct. 2006. Google ScholarDigital Library
- B. Augustin, B. Krishnamurthy, and W. Willinger. IXPs: Mapped? In IMC, 2009. Google ScholarDigital Library
- F. Baker. Requirements for IP version 4 routers, June 1995.Google Scholar
- A. Bender, R. Sherwood, and N. Spring. Fixing Ally's growing pains with velocity modeling. In IMC, pages 337--342, Oct. 2008. Google ScholarDigital Library
- X. Cai, J. Heidemann, B. Krishnamurth, and W. Willinger. Towards an AS-to-organization map. In IMC, pages 199--205, Nov. 2010. Google ScholarDigital Library
- B. Chandrasekaran, G. Smaragdakis, A. Berger, M. Luckie, and K.-C. Ng. A server-to-server view of the Internet. In CoNEXT, 2015. Google ScholarDigital Library
- 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 CoNEXT, Dec. 2009. Google ScholarDigital Library
- K. Claffy, A. Dhamdhere, M. Luckie, D. Clark, and S. Bauer. Mapping interconnection in the Internet: Colocation, connectivity and congestion. http://www.caida.org/funding/nets-congestion/.Google Scholar
- B. Donnet, T. Friedman, and M. Crovella. Improved algorithms for network topology discovery. In PAM, pages 149--162, Mar. 2005. Google ScholarDigital Library
- R. Durairajan, P. Barford, J. Sommers, and W. Willinger. InterTubes: A study of the US long-haul fiber-optic infrastructure. In SIGCOMM, Aug. 2015. Google ScholarDigital Library
- Federal Communications Commission. MB Docket No. 14--90), Memorandum Opinion and Order, FCC 15--94, July 2015. https://apps.fcc.gov/edocs_public/attachmatch/FCC-15--94A1.pdf.Google Scholar
- V. Giotsas, G. Smaragdakis, B. Huffaker, M. Luckie, and k claffy. Mapping peering interconnections to a facility. In CoNEXT, 2015. Google ScholarDigital Library
- V. Giotsas, S. Zhou, M. Luckie, and k claffy. Inferring multilateral peering. In CoNEXT, Dec. 2013. Google ScholarDigital Library
- R. Govindan and H. Tangmunarunkit. Heuristics for Internet map discovery. In INFOCOM, pages 1371--1380, Mar. 2000.Google ScholarCross Ref
- M. Gunes and K. Sarac. Analytical IP alias resolution. In IEEE International Conf. on Communications, pages 459--464, 2006.Google ScholarCross Ref
- B. Huffaker, A. Dhamdhere, M. Fomenkov, and kc claffy. Toward topology dualism: Improving the accuracy of AS annotations for routers. In PAM, Apr. 2010. Google ScholarDigital Library
- B. Huffaker, K. Keys, R. Koga, M. Luckie, and kc claffy. CAIDA inferred AS to organization mapping dataset. https://www.caida.org/data/as-organizations/.Google Scholar
- K. Keys. Internet-scale IP alias resolution techniques. CCR, 40(1):50--55, 2010. Google ScholarDigital Library
- K. Keys. iffinder alias resolution tool, 2012. http://www.caida.org/tools/measurement/iffinder/.Google Scholar
- K. Keys, Y. Hyun, M. Luckie, and k claffy. Internet-scale IPv4 alias resolution with MIDAR: System architecture. IEEE/ACM Transactions on Networking, 21(2):383--399, Apr. 2013. Google ScholarDigital Library
- A. Lakhina, J. W. Byers, M. Crovella, and P. Xie. Sampling biases in IP topology measurements. In INFOCOM, Apr. 2003.Google ScholarCross Ref
- M. Luckie. Scamper: a scalable and extensible packet prober for active measurement of the Internet. In IMC, pages 239--245, Nov. 2010. Google ScholarDigital Library
- M. Luckie, A. Dhamdhere, D. Clark, B. Huffaker, and k claffy. Challenges in inferring Internet interdomain congestion. In IMC, Nov. 2014. Google ScholarDigital Library
- M. Luckie, B. Huffaker, A. Dhamdhere, V. Giotsas, and k claffy. AS relationships, customer cones, and validation. In IMC, Oct. 2013. Google ScholarDigital Library
- M. Luckie and kc claffy. A second look at detecting third-party addresses in traceroute traces with the IP timestamp option. In PAM, Mar. 2014. Google ScholarDigital Library
- M-Lab Research Team. ISP interconnection and its impact on consumer Internet performance - a measurement lab consortium technical report. http://www.measurementlab.net/publications/, 2014.Google Scholar
- Z. M. Mao, D. Johnson, J. Rexford, J. Wang, and R. Katz. Scalable and accurate identification of AS-Level forwarding paths. In INFOCOM, Mar. 2004.Google Scholar
- Z. M. Mao, J. Rexford, J. Wang, and R. H. Katz. Towards an accurate AS-level traceroute tool. In SIGCOMM, pages 365--378, Aug. 2003. Google ScholarDigital Library
- A. Marder and J. M. Smith. MAP-IT: Multipass accurate passive inferences from traceroute. In IMC, 2016. Google ScholarDigital Library
- J.-J. Pansoit and D. Grad. On routes and multicast trees in the Internet. In SIGCOMM, 1998. Google ScholarDigital Library
- Packet Clearing House. https://prefix.pch.net/applications/ixpdir/menu_download.php.Google Scholar
- PeeringDB. https://www.peeringdb.com/.Google Scholar
- RIPE RIS. http://www.ripe.net/ris/.Google Scholar
- U. Oregon Route Views Project. http://www.routeviews.org/.Google Scholar
- S. Roy and N. Feamster. Characterizing correlated latency anomalies in broadband access networks. In SIGCOMM, pages 525--526, Aug. 2013. Google ScholarDigital Library
- M. Sanchez, F. Bustamante, B. Krishnamurthy, W. Willinger, G. Smaragdakis, and J. Erman. Inter-domain traffic estimation for the outsider. In IMC, Nov. 2014. Google ScholarDigital Library
- J. Sherry, E. Katz-Bassett, M. Pimenova, H. V. Madhyastha, T. Anderson, and A. Krishnamurthy. Resolving IP aliases with prespecified timestamps. In IMC, pages 172--178, 2010. Google ScholarDigital Library
- R. Sherwood, A. Bender, and N. Spring. DisCarte: A disjunctive Internet cartographer. In SIGCOMM, pages 303--314, Aug. 2008. Google ScholarDigital Library
- N. Spring, R. Mahajan, and D. Wetherall. Measuring ISP topologies with Rocketfuel. In SIGCOMM, pages 133--145, Aug. 2002. Google ScholarDigital Library
- S. Sundaresan, S. Burnett, N. Feamster, and W. de Donato. BISmark: A testbed for deploying measurements and applications in broadband access networks. In USENIX, June 2014. Google ScholarDigital Library
- R. Teixeira, A. Shaikh, T. Griffin, and J. Rexford. Dynamics of hot-potato routing in IP networks. In SIGMETRICS, June 2004. Google ScholarDigital Library
- W. Willinger, D. Alderson, and J. C. Doyle. Mathematics and the Internet: a source of enormous confusion and great potential. Notices of AMS, 56(5), May 2009.Google Scholar
- Y. Zhang, R. Oliveira, H. Zhang, and L. Zhang. Quantifying the pitfalls of traceroute in AS connectivity inference. In PAM, 2010. Google ScholarDigital Library
Index Terms
- bdrmap: Inference of Borders Between IP Networks
Recommendations
Towards an accurate AS-level traceroute tool
SIGCOMM '03: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communicationsTraceroute is widely used to detect routing problems, characterize end-to-end paths, and discover the Internet topology. Providing an accurate list of the Autonomous Systems (ASes) along the forwarding path would make traceroute even more valuable to ...
RealNet: A Topology Generator Based on Real Internet Topology
AINAW '08: Proceedings of the 22nd International Conference on Advanced Information Networking and Applications - WorkshopsOne of the challenges of large-scale network simulations is the lack of scalable and realistic Internet topology generators. Previous topology generators are either not scalable to millions of nodes, or not able to capture characteristics of the ...
Design and simulation of a supplemental protocol for BGP
Internet policy routing has attracted a lot of attention in the last decade and it is believed that this topic will become even more important in the foreseeable future. The growing diversity of the Internet brings in many organizations under different ...
Comments