Research And Implementation On Recovery Algorithm Of Internet Topological Connectivity

The Internet's complexity, heterogeneity and other issues seriously restrict the research on the Internet's behavior, so network simulation has become an important means to research Internet. Network topology data as basic data of network simulation, it directly impacts on the authenticity of all other operations. Therefore, the true and accurate network topology data is a necessary preparation for network simulation. All the topology data in used comes from network topology measurements. However, restricts of measuring technology and other factor(packet loss, privacy zone, router dose not respond, et.), the topological graph usually does not get connected. To make more authenticity for network simulation, improve simulation scale, and provide basis for the topological classification, it is necessary to recovery network topological connectivity.In this paper, the recovery algorithm of network topological connectivity is based on the research to Internet topological structure. Complex network theory will be used in characterizing topological properties, some of its basic concepts (betweenness, average path length, clustering coefficient, et.) have been well used to describe the network topology characteristics. Internet topology can be divided into autonomous level and router level. This research is at router level. For the recovery of network topological connectivity at router level, not only to study the topological properties but also consider the basic principles of building network topology.This paper proposes three options for the candidate nodes and two topological connectivity recovery algorithms.The property of node ownership explains that not every node has connection right. The program of choosing candidate nodes gives specific solutions. It is based on three main factors: network construction factors, geographical factors, scale factors. How choosing candidate nodes is based on the three factors.Network topological connectivity recovery algorithm based on small-world phenomenon: It is based on the small-world phenomenon, combined with the basic principles of Internet service providers building network topology, key nodes connect to each other and the number of edges is controlled by the threshold. The algorithm applies to the scale of the two connected components are very similar or both big.Network topological connectivity recovery algorithm based on hierarchical structure: It is based on topological hierarchical structure and through data statistics and analysis, do some of selective connection operation. The algorithm applies to the scale of the two connected components are very intervallic.Experiments show that both the two algorithms are good and reasonable for topological connectivity recovery.