Research On The Discovery Mechanism Of Critical Nodes In The Internet Topology Based On Traceroute

With the development of the Internet technology, the Internet topology, which is formed by the interconnection of Internet infrastructures, has become more and more complex. The research showed that the Internet topology is a scale-free network?This makes the Internet is vulnerable to network attacks, which means that the destruction of a few specific nodes can lead to a great impact on the network performance. Therefore, finding the critical nodes in the Internet topology is very important in the Internet security, management and optimization.Many researches had explored the critical nodes discovery algorithms in complex networks. In these researches, one kind of algorithm is based on the idea that the significance is equivalent to the importance. Algorithms based on this idea evaluate the importance of a node by calculating some centrality properties of that node in the network.Another kind of algorithm is based on the idea that the consequence is equivalent to the importance. Base on this idea, the importance of a node is measured by evaluating the influence to the network performance after destroying that node. However, these algorithms do not consider using the actual operation data of the network, which lead them far from the practice.Based on the existing achievements, this paper proposes a new algorithm of critical node discovery for the Internet topology. The algorithm is based on the idea that the consequence is equivalent to the importance. In this algorithm, the link delay and load properties of the Internet are added to the algorithm and the process of routing path selection is also simulated. In this paper, we construct a router level Internet topology and extract the delay and load data from the traceroute measurement results. After that, the importance degrees of some nodes in that topology are calculated using the algorithm we have developed. It is found that the time complexity of the algorithm is O(n ), which is higher than the algorithms that are based on the idea that the significance is equivalent to the importance, while lower than the cascade algorithm that is based on the idea that the consequence is equivalent to the importance.What's more, the algorithm could identify the nodes which have heavy load but low importance. Therefore, the accuracy of the result for our algorithm is higher than the result produced by other algorithms that are based on the load of the node.