Algorithms For Automatic Topology Discovery Of Networks

At present, most of the network automatic discovery algorithms are developed to discover logical topologies within administrative domains by accessing routing table of MIBs in managed objects using SNMP. But as more layer-2 devices are deployed in heterogeneous IP networks to provide more bandwidth through subnet micro-segmentation, the portions of the network infrastructure that are invisible to a layer-3 mapping will continue to grow. Besides, Internet has been the new focus of much work on topology discovery because it has formed the bottleneck for nearly all wide-area applications, server selection and placement.From above, we can see that logical topology discovery within administrative domain alone is far away from meeting the needs of these issues. In this paper, an improved logical topology discovery algorithm for administrative domain is proposed. Moreover, automatic discovery algorithms for physical topology of administrative domain and topology of Internet are discussed respectively.Firstly, the functions of several main network nodes (such as bridge and router) important to the design of topology discovery algorithms are introduced. Then common topologies of networks are described. Four topologies are associated with LANs: bus, ring, star, and hybrid. WANs are connected in either a mesh topology or a tree topology. After comparing the advantages and disadvantages of basic tools for topology discovery, there comes the conclusion: we should choose appropriate tool or combines several tools in the process of topology discovery according to the real condition of object network.Traditional logical topology discovery algorithms within administrative domain can only discover the devices that have implemented SNMP. While for those devices that do not support SNMP, traditional algorithms seem incapable. So the algorithm in this paper combine the tools of SNMP and ping/traceroute based on ICMP, which makes the results of logical topology discovery more complete.After discovering layer-2 devices, existing physical topology discovery algorithms for administrative domain try to identify direct connections between port peers of these devices, which needs to ensure the completion of AFT (Address Forward Table) information collected in every nodes' SNMP MIBs through generating extra traffic in networks. The algorithm presented in this paper not onlyjudges physical connections between port peers directly, but also tries to eliminate those port peers that cannot have simple connection relationship from the set consisting of all the possible port peers. This algorithm is more efficient and gains more accurate results.At last, after analyzing the shortcomings of basic topology discovery algorithms for Internet, such as the backbone topology discovery algorithm developed by CNRG (Cornell Network Research Group), the main problems that need to be solved in topology discovery of Internet are presented. Afterwards, heuristics for Internet map discovery that can address these problems in much degree are discussed, including basic path probing using traceroute, informed random address probing, source-routed path probing for cross-links and alias resolution of routers.