Algorithm Research Of Topology Discovery On Ethernet Data-link Layer

With the rapid development and wide application of network technology, computer network has come into every field of society and plays a greater role in social economy. Meanwhile as the scale of network has been expanding and its structure becomes more and more complicated, the demand of Network Management System becomes more urgent. The Network Management System is based on the network topology information which is important obviously. The correct and advanced network topology information can provide the holistic network structure and state to network managers effectively. It is a common issue for those network institutes to automatically discover and obtain network topology information with completeness, robustness, accuracy and efficiency. The study is transferred from network layer to data link layer. The link layer topology discovery can discover the physical topology internal a LAN, which the network layer topology discovery can not discover. This paper focuses on the study of various link layer topology discovery algorithms.Firstly, this paper introduces the related knowledge,concepts and commonly-used technology about network topology discovery. Through researching on the current network topology discovery algorithms, this paper proposes three improved theorems which are used to determine the connection state between Ethernet devices. Based on these theorems an improved algorithm is introduced. Compared with the original algorithm, this improved algorithm can discovery more devices, and can decreases the requirements of AFT of switches. Furthermore, it can detect dumb devices and the link relationship with other devices around them. It can be used for a wider range of applications, adaptive stronger closer to the actual circumstances. This algorithm can discover physical layer topology in a simple, complete and efficient way.Furthermore, the paper describes the realization of topology discovery system. New algorithm has been used into this topology discovery system and it has been implemented and tested in the real networks. It is shown that the new algorithm is efficient and accurate.Finally, the thesis uses the WinSNMP API to achieve topology discovering system on the development platform of Visual C++ and minutely analyses Subnet-level topology discovery technology based on SNMP. The thesis also analyses the technology of analysis and topology graph minutely.There are many points need to be improved in this research. The last chapter summarizes the whole work, and points out the later work.