Research On Path Planning Algorithm For Complex Network Topology

With the popularization of the network,providing high-quality,high-efficiency,and stable services has become an immediate issue for every network operator.The network structure is becoming more and more complex,and how to perform faster and better path planning in complex networks has gradually become a hot topic in network topology research in recent years.Especially after the emergence of Software Defined Network,it has provided better technical support for research.Based on the knowledge of network topology and graph theory,combined with the characteristics and requirements of complex network topology,this thesis studies path planning algorithms in complex networks.The main research work of this thesis is as follows:(1)A routing algorithm suitable for complex network topologies is proposed.This thesis first studied the structure of complex network topologies and routing algorithms.Traditional routing algorithms are aimless when searching for nodes,which results in a large search space and affects the algorithm's runtime.In this thesis,the A * algorithm is used in the routing of complex network topology,and the evaluation function of the A * algorithm in the complex network topology is calculated through landmark nodes and triangle inequality(ALT algorithm).An improved method of greedy discrete selection is proposed for the selection of landmark nodes in the ALT algorithm,and a two-way pre-calculation is performed during the pre-calculation to fully utilize the value of the landmark nodes.(2)This thesis studies the enhanced ring network structure designed to solve the problems of high network delay and low transmission efficiency of the traditional ring network structure.An improved routing algorithm PRR(Preprocessing,Recovering Nodes,Recovering Path)algorithm based on complex ring network topology with enhanced ring network structure is proposed.The algorithm is divided into three parts:preprocessing,source trace node recovering and path recovering.The core idea of the algorithm is to "divide and conquer" in combination with the characteristics of the multi-ring network,transform the original network into a small-scale directed network through preprocessing,and turn the complex routing problem in the multi-ring network into a simple routing problem in the single-ring network.,and finally the network is undistorted by the reduction algorithm.This thesis proves theoretically and experimentally that the optimal path obtained by the PRR algorithm is error-free and the algorithm performe better than the traditional algorithm.(3)After researching and analyzing the traditional KSP algorithm,this thesis proposes a lossless KSP algorithm that does not need to repeatedly run the routing algorithm and a KSP algorithm that can obtain a set of k paths with smaller coincidence.The KSP algorithm is used to solve the path planning problem that only the shortest path cannot meet the needs.The traditional Yen algorithm calculation process will constantly call the routing algorithm.The KSP algorithm based on the A * algorithm proposed in this thesis only needs to run the algorithm once to obtain the lossless first k shortest path.And a KSP algorithm based on penalty factor is proposed.Although the result of this algorithm is lossy,the degree of overlap between paths is lower,so it has higher practical significance and value.