A Novel Method for Router-to-AS Mapping Based on Graph Community Discovery

Abstract

The last decades have witnessed the progressive development of research on Internet topology at the router or autonomous systems (AS) level. Routers are essential components of ASes, which dominate their behaviors. It is important to identify the affiliation between routers and ASes because this contributes to a deeper understanding of the topology. However, the existing methods that assign a router to an AS, based on the origin AS of its IP addresses do not make full use of the information during the network interaction procedure. In this paper, we propose a novel method to assign routers to their owners’ AS, based on community discovery. First, we use the initial AS information along with router-pair similarities to construct a weighted router level graph; secondly, with the large amount of graph data (more than 2M nodes and 19M edges) from the CAIDA ITDK project, we propose a fast hierarchy clustering algorithm with time and space complexity, which are both linear for graph community discovery. Finally, router-to-AS mapping is completed, based on these AS communities. Experimental results show that the effectiveness and robustness of the proposed method. Combining with AS communities, our method could have the higher accuracy rate reaching to 82.62% for Routers-to-AS mapping, while the best accuracy of prior works is plateaued at 65.44%.

Keywords

• Router-to-AS mapping
• community discovery
• global router topology
• fast hierarchy clustering