Research On Multi-next Hop Routing Algorithm

The single next hop routing algorithm which widely used today makes the transmission paths tend to centralize, leading to a waste of network resources and slow recovery from failures. Multi-Next Hop Routing technology makes each node forward packets to multiple neighbor nodes and implements parallel transmission. The mechanism can make better use of network resources, reduce transmission congestion effectively, and improve network performance. Combined with the national 863 objective orientation project "a multi-next hop routing mechanism based on node potential orientation", this dissertation proposes a Multi-Next Hop Routing Algorithm based on search sequence numbering by the prerequisite not to alter the current network work mode.The main work of this dissertation is outlined as follows:1.Two typical multi-next hop routing algorithms——SP (Shortest Path) and st numbering mechanism are analyzed. SP determines feasible next hops according to the optimal distance, which can not fully exploit the network resources; st routing may be of poor performance, because st is based on graph theory simply and network property is failed to take into account when planning the routing. The analysis of both algorithms provides research approach for algorithm design.2.Combined with potential idea, multi-next hop routing algorithm based on shortest path search sequence potential——D-SSPA (Dijkstra-Search Sequence Potential Algorithm) is proposed in this thesis. The destination nodes execute search algorithm to complete sequencing of all nodes, link transmission direction of neighbor nodes according to the size of their assignments. The algorithm fully exploits the network resources, the routing graph generated by D-SSPA is better than SP and st, and the simulation analysis indicates that, load balance of nodes and links is improved, network throughput and packet loss rate performance are also superior to the both.3.A Hierarchical Evaluation Response Algorithm(HERA)which deals with the single link failure based on multi-next hop routing mechanism is presented. Under this mechanism, failures are divided into three levels: convergence of this node, convergence of the upstream neighbors and global convergence, which makes the failure influence locally as far as possible. Simulation results show that, in networks with different connectivity, HERA can trigger global convergence as little as possible, failure recovery time is shortened, and the stability of the network is enhanced effectively. Under a single link failure, convergence time of D-SSPA decreased 21.7% than the SP, and decreased 9.5% than st.