Research Of Algorithm For Physical Topology Discovery In Heterogeneous IP Network

As the scale of computer network enlarges continuously, the heterogeneity of the network is more and more strong, which now features the three aspects as follows: (1) a network is composed of many subnets; (2) it is established by different kinds of network equipments made in various factories; (3) it is configured with the VLAN. The topology discovery means a way or technique to detect the interlinkage relations among network equipments with the aid of topology tools. In recent years, it has been attracted considerable attention for a mass of researchers on networks in world, and become the hot research area of computer networks, in particular, has been widely used in network fault-location, performance measurement and count expense etc.Based on careful analysis on related theory, technique and application of the topology discovery in world, the author first proposes a new physical topology discovery algorithm (PTDA) for single subnet, next introduces the new algorithm into multi-subnet case, as a result, puts forward a new PTDA for multiple subnets.On the base of the above PTDA for single or multiple subnets, the author further puts forward another PTDA based on spanning tree protocol (STP). The latter PTDA discusses the related theorems and rules ofjudgeing the root bridge and root port as well as specifing the bridge and port, makes use of many protocols such as STP, SNMP and ARP, eventually determines the conjunction relation between router, switches and host in the network. This algorithm can solve nicely the problem of physical topology discovery for different network equipments.Finally, based on the VLAN under IEEE802.1Q, the author further presents a PTDA, which is also implemented and verified.The creativity of the work in the paper can be shown as the following four aspects:(1) For single subnet, the condition of simple link judgement is added into the PTDA,so the algorithm is improved well; (2) For multiple subnets, the PTDA becomes more effective, benefited from use of breadth-first-search algorithm of graph, port-deletion method etc;(3) Due to suitable adoption of the three protocols STP, SNMP and ARP,the PTDA based on spanning tree protocol can get very effective and correct;(4) Owing to the employment of IEEE802.1 Q, the PTDA of VLAN is all-purpose to some extent.