Research On LAP Routing Algorithm Based On Traversal Tree

Routing algorithms can be classified into two categories:distance vector routing algorithm and link-state routing algorithm.The link-state routing algorithm is that each router collects complete information of network topology and selects an optimal path for routing according to the collected information.In fact,the complete information convergence of the full network topology is performed by the flooding algorithm.Flooding algorithm leverages the diffusion way to deliver the information.However,it generates a lot of duplication of redundant information and wastes of the communication resources of network especially when more links in network.The convergence algorithm has recently attracted much attention from a lot of researchers since the current Internet has developed from small-scale network to large and complex scale network.First,the thesis introduces the principle of the LAP routing algorithm and discusses the next period of research;Then,on the basis of LAP routing algorithm,traversal tree LAP routing algorithm is used in general network and the implementation steps of the algorithm is given in the thesis;Next,the algorithm is analyzed and proved in theory;Finally,simulation experiment results illustrate that the algorithm completes the information convergence which is better performance compared with the original algorithm in the complex link network environment.In the NS2 simulation platform,the simulation experiments are carried out,and completed the comparison between the LAP routing algorithm and the Flooding algorithm.Thus draws the following conclusion:if the network routing node number is a fixed value,with the increase of the number of links between the nodes,the times of communication gradually increase in Flooding algorithm,and the times of communication gradually reduce in the breadth first traversal LAP routing algorithm.When the link is increased to the same time that the number of communication is equal in both,it is called the critical point.Below the critical point,the times of flooding algorithm communication is less than breadth first traversal of the tree routing algorithm with LAP times of communication;more than the critical point,the breadth first traversal of the tree lap routing algorithm of communication times less than flooding algorithm of the number of communications.