Resolving Anonymous Nodes Based on “Watermelon Patterns” Towards Constructing Router-Level Topology in Mesh Network

Router-level topology, portraying the connection relationship between network devices, is important for discovering key devices in network. In actual networks, there are some anonymous routers, which do not respond traceroute due to network congestion, firewall security settings, router response rate limitations, and other factors. As these anonymous routers are difficult to eliminate, it makes the constructed router-level topology huge in size. Currently, the time cost of finding key nodes is high. Resolving anonymous nodes for reducing the topology size is necessary to improve the efficiency in finding key node. Although anonymous route resolving methods have been available, they are difficult to handle two-hop anonymous route structures in mesh topologies. To this end, based on the four structures summarized in Graph Based Induction (GBI) method, we propose a method to resolve anonymous nodes based on “watermelon patterns”. Combining with Kapar, an alias IP merging method, to build router-level topologies in mesh networks. We have conducted experiments in 8 cities, such as New York, Tokyo, Seoul and so on. The experimental results show that, our method can handle the local topology containing two-hop anonymous nodes. And using our method to further reduce the size of the router-level topology built using GBI and Kapar, which is conducive to improving the efficiency of discovering key nodes in the topology.