Research On Technology Of Router-level Distributed Network Topology Discovery

Router-level distributed network topology discovery, one of the major methods to obtain the router-level network topology without administrative access, plays a crucial role in relevant research fields involving computer network.Compared to the single source network topology discovery, distributed network topology discovery is capable of discovering more network topology via collecting more information of router interface and link. Meanwhile, it tends to cause large amount of probing redundancy during the probing process, which decreases the efficiency of topology discovery and leads to a reaction towards DDo S attack from network security devices with a great probability. Consequently, ensuring maximized topology coverage and securing a minimized amount of probing redundancy has become an important issue in router-level distributed network topology discovery.The technology of distributed network topology discovery consists of source selection, destination selection and probing tactic. According to the guide going from method evaluation to method design, a series of evaluation indicators were presented based on the efficiency factors of router-level distributed network topology discovery. The effect on the efficiency of topology discovery from source, destination and probing tactic were studied. Finally, a scheme for distributed network topology discovery was proposed to provide significant theoretical reference for router-level distributed network topology discovery.The main work in this thesis is as follows.(1) In order to provide criteria for appraising relevant techniques, six evaluation indicators and appraisal method were presented in accordance with the completeness and effectiveness of router-level distributed network topology discovery.(2) The destination selection method based on stub network discovery was proposed. Though a small portion of pre-probing, this method discovers all the stub networks in the target network. On the basis of this, destinations are selected by random selection. The gained destination set was theoretically proved to be the minimum complete one. Then, the result of simulation experiment shows that with selecting less than 0.65% IP addresses as destinations in target network, this method improves the router interface discovery completeness and the router link discovery completeness to above 97% and 91% which are 16% and 20% more than existing method.(3) The source selection method based on maximum GDS was proposed. The indicator, GDS, gauging the logic distance of a source group was defined. After that, it is illustrated by simulation experimental result that source group with larger GDS tends to discovery more network topology. Then, the hybrid genetic simulated annealing algorithm was tailor-made to screening out the source group with maximum GDS. It is demonstrated by simulation experimental results that compared with existing methods this method is able to raise the gross values of router interface and link by 12% and 18%.(4) The progressive probing tactic based on rotative probing was proposed. Countree was presented though optimizing the stop set of Doubletree. Moreover, the rotative probing pattern based on source grouping was designed to implement Countree. The result of simulation experiment shows that this tactic is capable of discovering the missing topology of Doubletree. Compared with entire probing, the probing redundancy rate is reduced by over 60% and the discovery completenesses of both router interface and router link have been improved to more than 90%. Compared with Doubletree, it boosts the discovery completenesses of both router interface and router link by above 20% with less than 18% probing redundancy. Besides, the communication times and data amount among sources have been cut down to about 50% and 20%.(5) The DSP network topology discovery scheme was proposed. In this scheme, the process of router-level distributed network topology discovery is divided into 3 stages, the stage of source set selection, the stage of destination set selection and the stage of topology probing. Correspondingly, the destination selection method based on stub network discovery, the source selection method based on maximum GDS and the progressive probing tactic based on rotative probing are allocated. The result of simulation experiment proves that compared with existing scheme, DSP enhances both efficiency and completeness of network topology discovery.