Ricardo Oliveira
Abstract
Despite significant efforts to obtain an accurate picture of the Internet's connectivity structure at the level of individual autonomous systems (ASes), much has remained unknown in terms of the quality of the inferred AS maps that have been widely used by the research community. In this paper, we assess the quality of the inferred Internet maps through case studies of a sample set of ASes. These case studies allow us to establish the ground truth of connectivity between this set of ASes and their directly connected neighbors. A direct comparison between the ground truth and inferred topology maps yield insights into questions such as which parts of the actual topology are adequately captured by the inferred maps, which parts are missing and why, and what is the percentage of missing links in these parts. This information is critical in assessing, for each class of real-world networking problems, whether the use of currently inferred AS maps or proposed AS topology models is, or is not, appropriate. More importantly, our newly gained insights also point to new directions towards building realistic and economically viable Internet topology maps.
- AOL Peering Requirements, {Online}. Available: http://www.atdn.net/ settlement_free_int.shtmlGoogle Scholar
- AT&T Peering Requirements, {Online}. Available: http://www.corp.att. com/peering/Google Scholar
- CERNET BGP Feeds, {Online}. Available: http://bgpview.6test.edu.cn/ bgp-view/Google Scholar
- European Internet Exchange Association, {Online}. Available: http:// www.euro-ix.netGoogle Scholar
- Geant2 Looking Glass, {Online}. Available: http://stats.geant2.net/lg/Google Scholar
- Good Practices in Internet Exchange Points, {Online}. Available: http://www.pch.net/resources/papers/ix-documentation-bcp/ix-documentation-bcp-v14en.pdfGoogle Scholar
- Internet Routing Registry, {Online}. Available: http://www.irr.net/Google Scholar
- Packet Clearing House IXP Directory, {Online}. Available: http://www.pch.net/ixpdir/Main.plGoogle Scholar
- PeeringDB Website, {Online}. Available: http://www.peeringdb.com/Google Scholar
- Personal Communication with Bill Woodcock at PCH.Google Scholar
- RIPE Routing Information Service Project, {Online}. Available: http:// www.ripe.net/Google Scholar
- RouteViews Routing Table Archive, {Online}. Available: http://www. routeviews.org/Google Scholar
- Skitter AS Adjacency List, {Online}. Available: http://www.caida.org/ tools/measurement/skitter/as_adjacencies.xmlGoogle Scholar
- The Abilene Observatory Data Collections, {Online}. Available: http:// abilene.internet2.edu/observatory/data-collections.htmlGoogle Scholar
- H. Ballani, P. Francis, and X. Zhang, "A study of prefix hijacking and interception in the Internet," in Proc. ACM SIGCOMM, 2007, pp. 265-276. Google Scholar
- H. Chang, "An economic-based empirical approach to modeling the Internet inter-domain topology and traffic matrix," Ph.D. dissertation, Univ. Michigan, Ann Arbor, MI, 2006. Google Scholar
- H. Chang, R. Govindan, S. Jamin, S. J. Shenker, and W.Willinger, "Towards capturing representative AS-level Internet topologies," Comput. Netw. J., vol. 44, no. 6, pp. 737-755, 2004. Google Scholar
- H. Chang, S. Jamin, and W. Willinger, "Inferring AS-level Internet topology from router-level path traces," in SPIE ITCom, 2001.Google Scholar
- H. Chang and W. Willinger, "Difficulties measuring the Internet's AS-level ecosystem," in Proc. Annu. CISS, 2006, pp. 1479-1483.Google Scholar
- X. Dimitropoulos, D. Krioukov, M. Fomenkov, B. Huffaker, Y. Hyun, kc claffy, and G. Riley, "AS relationships: Inference and validation," Comput. Commun. Rev., vol. 37, no. 1, pp. 29-40, 2007. Google Scholar
- D. Dolev, S. Jamin, O. Mokryn, and Y. Shavitt, "Internet resiliency to attacks and failures under BGP policy routing," Comput. Netw., vol. 50, no. 16, pp. 3183-3196, 2006. Google Scholar
- L. Gao, "On inferring autonomous system relationships in the Internet," IEEE/ACM Trans. Netw., vol. 9, no. 6, pp. 733-745, Dec. 2001. Google Scholar
- B. Hummel and S. Kosub, "Acyclic type-of-relationship problems on the internet: An experimental analysis," in Proc. ACM IMC, 2007, pp. 221-226. Google Scholar
- Y. Hyun, A. Broido, and kc claffy, "On third-party addresses in traceroute paths," presented at the PAM Workshop, 2003.Google Scholar
- M. Lad, R. Oliveira, B. Zhang, and L. Zhang, "Understanding the resiliency of Internet topology against false origin attacks," presented at the IEEE DSN, 2007. Google Scholar
- H. Madhyastha, T. Isdal, M. Piatek, C. Dixon, T. Anderson, A. Krishnamurthy, and A. Venkataramani, "iPlane: An information plane for distributed services," in Proc. OSDI, 2006, pp. 367-380. Google Scholar
- R. Mahajan, D. Wetherall, and T. Anderson, "Understanding BGP misconfiguration," in Proc. ACM SIGCOMM, 2002, pp. 3-16. Google Scholar
- Z. M. Mao, L. Qiu, J. Wang, and Y. Zhang, "On AS-level path inference," in Proc. SIGMETRICS, 2005, pp. 339-349. Google Scholar
- Z. M. Mao, J. Rexford, J. Wang, and R. H. Katz, "Towards an accurate AS-level traceroute tool," in Proc. ACM SIGCOMM, 2003, pp. 365-378. Google Scholar
- W. Mühlbauer, A. Feldmann, O. Maennel, M. Roughan, and S. Uhlig, "Building an AS-topology model that captures route diversity," in Proc. ACM SIGCOMM, 2006, pp. 195-206. Google Scholar
- W. Mühlbauer, S. Uhlig, B. Fu, M. Meulle, and O. Maennel, "In search for an appropriate granularity to model routing policies," in Proc. ACM SIGCOMM, 2007, pp. 145-156. Google Scholar
- R. Oliveira, B. Zhang, D. Pei, R. Izhak-Ratzin, and L. Zhang, "Quantifying path exploration in the Internet," in Proc. ACM IMC, Oct. 2006, pp. 269-282. Google Scholar
- R. Oliveira, B. Zhang, and L. Zhang, "Observing the evolution of Internet AS topology," in Proc. ACM SIGCOMM, 2007, pp. 313-324. Google Scholar
- D. Raz and R. Cohen, "The Internet dark matter: On the missing links in the AS connectivity map," in Proc. IEEE INFOCOM, 2006, pp. 1-12.Google Scholar
- Y. Rekhter, T. Li, and S. Hares, "Border Gateway Protocol 4," Internet Engineering Task Force, 2006, RFC 4271.Google Scholar
- M. Roughan, S. J. Tuke, and O. Maennel, "Bigfoot, sasquatch, the yeti and other missing links: What we don't know about the as graph," in Proc. ACM IMC, 2008, pp. 325-330. Google Scholar
- Y. Shavitt and E. Shir, "DIMES: Let the Internet measure itself," Comput. Commun. Rev., vol. 35, no. 5, pp. 71-74, 2005. Google Scholar
- G. Siganos and M. Faloutsos, "Analyzing BGP policies: Methodology and tool," in Proc. IEEE INFOCOM, 2004, pp. 1640-1651.Google Scholar
- L. Subramanian, S. Agarwal, J. Rexford, and R. Katz, "Characterizing the Internet hierarchy from multiple vantage points," in Proc. IEEE INFOCOM, 2002, pp. 618-627.Google Scholar
- L. Subramanian, M. Caesar, C. T. Ee, M. Handley, M. Mao, S. Shenker, and I. Stoica, "HLP: A next generation inter-domain routing protocol," in Proc. ACM SIGCOMM, 2005, pp. 13-24. Google Scholar
- L. Wang, M. Saranu, J. M. Gottlieb, and D. Pei, "Understanding BGP session failures in a large ISP," in Proc. IEEE INFOCOM, 2007, pp. 348-356.Google Scholar
- J. Wu, Y. Zhang, Z. Mao, and K. Shin, "Internet routing resilience to failures: Analysis and implications," in Proc. ACM CoNEXT, 2007, Article No. 25. Google Scholar
- Y. He, G. Siganos, M. Faloutsos, and S. V. Krishnamurthy, "A systematic framework for unearthing the missing links: Measurements and impact," presented at the NSDI, 2007. Google Scholar
- B. Zhang, R. Liu, D. Massey, and L. Zhang, "Collecting the Internet AS-level topology," Comput. Commun. Rev., vol. 35, no. 1, pp. 53-61, Jan. 2005. Google Scholar
- C. Zheng, L. Ji, D. Pei, J. Wang, and P. Francis, "A light-weight distributed scheme for detecting IP prefix hijacks in real-time," in Proc. ACM SIGCOMM, 2007, pp. 277-288. Google Scholar
Index Terms
- The (in)completeness of the observed internet AS-level structure
Recommendations
Quantifying path exploration in the internet
Previous measurement studies have shown the existence of path exploration and slow convergence in the global Internet routing system, and a number of protocol enhancements have been proposed to remedy the problem. However, existing measurements were ...
Obtaining provably legitimate internet topologies
What topologies should be used to evaluate protocols for interdomain routing? Using the most current Internet topology is not practical since its size is prohibitive for detailed, packet-level interdomain simulations. Besides being of moderate size, the ...
Incentive-compatible interdomain routing
EC '06: Proceedings of the 7th ACM conference on Electronic commerceThe routing of traffic between Internet domains, or Autonomous Systems (ASes), a task known as interdomain routing, is currently handled by the Border Gateway Protocol (BGP) [17]. Using BGP, autonomous systems can apply semantically rich routing ...
Comments