Discovering and Mapping Subnet Level Topology

Abstract

The research of Internet measurement has promoted the development of router-level topology discovery, while the subnet of the network layer can provide a more detailed intermediate complementary view. To improve the current level of router-level topology discovery, some researchers have proposed subnet discovery methods. However, the existing methods do not perform well in terms of efficiency and accuracy, which leads to the failure of the final resulting topology map. In this paper, we propose a new approach to discover subnets, which consists of a network pre-processing stage and a subnet inference stage. Given a set of target IP prefixes, the network pre-processing stage introduces a minimal probing overhead to improve probing efficiency. Based on the IP address allocation principle, the subnet inference stage utilizes a set of complementary inference rules to infer subnets. The experimental results show that our method can achieve a higher accuracy in discovering subnets while keeping lower probing overhead compared with existing methods. Finally, we utilize the proposed approach to discover the subnets of six geographically dispersed public Autonomous System (AS) networks and analyze their various subnet characteristics, including degree distribution.