The Internet topology at the autonomous system (AS) level is of great importance, and traceroute has been known to be a potential tool to obtain a complete AS topology. The original IP-to-AS mapping table maps the IP addresses in traceroute paths to their origin ASes, which may cause false AS links. The existing methods refine the original mapping table based on traceroute-BGP path pairs or alias resolution data. However, the information extracted from either of them is inaccurate and incomplete. In this paper, we present a two-type information fusion based method to refine the original mapping table. We extract four kinds of information from path pair and alias resolution data. Based on these information, we build a candidate AS set for each router. Then we choose the AS that is consistent with the existing information to be the owner AS of each router and map all of the IP addresses on the router to it. We validate the result with the ground truth from PeeringDB and Looking Glass severs. Compared with the existing methods, our method produces a more accurate mapping table. In addition, we discuss the coverage of our method and show that our method is convergent and more robust against the reduction of information or the increase of incorrect information.
This work was partially supported by the National Natural Science Foundation for Distinguish Young Scholars of China under Grant No. 61301274 and the National Natural Science Foundation of China under Grant No. 61471101.
通讯作者: Guang-Min Hu
About author: Qing Jiang is a Ph.D. candidate in School of Communication and Information Engineering, University of Electronic Science and Technology of China (UESTC), Chengdu. Her research interests include Internet topology discover and complex network. In 2013, she received her B.S. degree in communication engineering from UESTC, Chengdu.
Qing Jiang, Hang-Yu Hu, Guang-Min Hu.基于两类信息融合的IP-to-AS映射表修正[J] Journal of Computer Science and Technology , 2017,V32(3): 571-584
Qing Jiang, Hang-Yu Hu, Guang-Min Hu.Two-Type Information Fusion Based IP-to-AS Mapping Table Refining[J] Journal of Computer Science and Technology, 2017,V32(3): 571-584
 Boguna M, Papadopoulos F, Krioukov D. Sustaining the Internet with hyperbolic mapping. Nature Communications, 2010, 1(6): Article No. 62. Papadopoulos F, Krioukov D, Bogua M, Vahdat A. Greedy forwarding in dynamic scale-free networks embedded in hyperbolic metric spaces. In Proc. the 29th IEEE INFOCOM, March 2010, pp.2973-2981. Gao L. On inferring autonomous system relationships in the Internet. IEEE/ACM Trans. Networking, 2001, 9(6): 733-745. Mao Z M, Rexford J, Wang J, Katz R H. Towards an accurate AS-level traceroute tool. ACM SIGCOMM Computer Communication Review, 2003, 33(4): 365-378. Mao Z M, Johnson D, Rexford J, Wang J, Katz R. Scalable and accurate identification of AS-level forwarding paths. In Proc. the 23rd IEEE INFOCOM, Mar. 2004, pp.1605-1615. Zhang B, Bi J, Wang Y, Zhang Y, Wu J. Refining IP-to-AS mappings for AS-level traceroute. In Proc. the 22nd IEEE Computer Communications and Networks (ICCCN), July 30-Aug. 2, 2013. Zhang B, Bi J, Wang Y, Wang Y, Zhang Y, Wu J. Revisiting IP-to-AS mapping for AS-level traceroute. In Proc. ACM CoNEXT Student Workshop, Dec. 2011, pp.900-902. Huffaker B, Dhamdhere A, Fomenkov M, Claffy K. Toward topology dualism: Improving the accuracy of AS annotations for routers. In Proc. the 11th International Conference on Passive and Active Measurement (PAM), Apr. 2010, pp.101-110. Pansiot J J, Merindol P, Donnet B, Bonaventure O. Extracting intra-domain topology from mrinfo probing. In Proc. the 11th International Conference on Passive and Active Measurement (PAM), Apr. 2010, pp.81-90. He Y, Siganos G, Faloutsos M, Krishnamurthy S. Lord of the links: A framework for discovering missing links in the Internet topology. IEEE/ACM Trans. Networking, 2009, 17(2): 391-404. Shavitt Y, Shir E. DIMES: Let the Internet measure itself. ACM Computer Communication Review (CCR), 2005, 35(5): 71-74. Giotsas V, Smaragdakis G, Huffaker B et al. Mapping peering interconnections to a facility. In Proc. ACM International Conference on Emerging Networking Experiments and Technologies (CoNEXT), Dec. 2015, pp.37:1-37:13. Zhang Y, Oliveira R, Wang Y, Su S, Zhang B, Bi J, Zhang H, Zhang L. A framework to quantify the pitfalls of using traceroute in AS-level topology measurement. IEEE Journal on Selected Areas in Communications, 2011, 29(9): 1822-1836. Chen K, Choffnes D R, Potharaju R, Chen Y, Bustamante F E, Pei D, Zhao Y. Where the sidewalk ends: Extending the Internet as graph using traceroutes from P2P users. In Proc. the 5th International Conference on Emerging Networking Experiments and Technologies, Dec. 2009, pp.217- 228. Amini L, Shaikh A, Schulzrinne H. Issues with inferring Internet topological attributes. Computer Communication, 2004, 27(6): 557-567. Luckie M, Claffy K. A second look at detecting third-party addresses in traceroute traces with the IP timestamp option. In Proc. the 15th PAM, Mar. 2014, pp.46-55. Keys K, Hyun Y, Luckie M, Claffy K. Internet-scale IPv4 alias resolution with MIDAR. IEEE/ACM Trans. Networking, 2013, 21(2): 383-399. Pansiot J J, Grad D. On routes and multicast trees in the Internet. ACM SIGCOMM Computer Communication Review, 1998, 28(1): 41-50. Keys K. Internet-scale IP alias resolution techniques. ACM SIGCOMM Computer Communication Review, 2010, 40(1): 50-55. Durairajan R, Sommers J, Barford P. Layer 1-informed Internet topology measurement. In Proc. ACM IMC, Nov. 2014, pp.381-394.