Design And Implementation Of Multi-path Topology Active Discovery Algorithm Based On Traceroute

With the increasing scale and complexity of the Internet network,network topology detection technology is facing the challenges brought by the heterogeneity,diversity,and large scale of the network.Active network topology detection technology is a network detection technology with high generality which mainly uses the relevant mechanisms in the network protocol to detect the network topology.Traceroute is the most basic network topology active detection technology.Load balancing is ubiquitous in today's networks,simple traceroute detection is difficult to identify the parallel path in load balancing.The multi-path detection algorithm(MDA)was proposed to solve this problem.However,MDA consumes a lot of probe packets and its execution efficiency is low.Aiming at the above problems,this thesis analyzed the performance limitations of MDA and proposed the corresponding improvement scheme.According to the improvement scheme,a multipath detection algorithm based on state iteration was proposed,and the algorithm was implemented systematically in this thesis.Under the condition of ensuring the detection effect,the execution efficiency of multi-path detection is improved.The main work of this thesis can be summarized as follows.Multi-path detection model and algorithm have been studied.By analyzing the execution process of the traditional multi-path detection algorithm,three performance limitations of the traditional multi-path detection algorithm were proposed.Firstly,redundancy exists in the sending of probe packets.Secondly,the node detection process between adjacent TTLs is strongly coupled,which is difficult to realize parallelization.Thirdly,the number of probe packets in the detection process is unevenly distributed with TTLs.A multi-path detection algorithm based on state iteration was proposed.Three improvement points were proposed to solve the performance bottleneck of MDA.Firstly,introducing a record table to deal with redundant detection.Secondly,by introducing the intermediate state of node detection and analysis,the node analysis process is completed iteratively based on the node state,which is convenient for parallelization.Thirdly,the detection mode is changed from breadth-first search to iterative search.At the same time,the timeout management is carried out for the detection process to reduce the impact of abnormal conditions such as network congestion on the operation stability of the algorithm.On basis of the multi-path algorithm based on state iteration,a parallel network topology detection system was designed.The detection system automatically generates the detection task set according to the detection destination address set,and creates multiple parallel detection actuators according to the parameter setting.Each actuator can execute the multi-path detection algorithm independently and update the detection results synchronously.The whole system is based on modular design and has good maintainability and expansibility.Finally,the feasibility of the algorithm and system was verified by experiments.The experimental results show that the proposed method has good advantages over the traditional MDA in terms of probe packet consumption and detection time consumption.In terms of bandwidth occupation,it has better stability than traditional MDA.In terms of detection effect,such as the number of nodes found,the algorithm proposed in this thesis is slightly reduced compared with traditional MDA,but it remains at the same order of magnitude.