| Nowadays the network has become an important resource for people's livelihood.The consumptions of consecutive and real-time internet service have increased day by day.Routing technology,as the core technology of internet,affects the performance of internet transmission greatly.However,the single next hop routing protocols that widely used today have two important defects:First,they respond so slow to failures that can lead to high data loss rates;Second,they only choose the shortest paths that can easily increase the risk of network congestion .Multi-next hop routing technology can deal with these two problems well:When the failures make some of the next hops become useless,the router can choose the rest next hops to forward packets and avoid the intermission of internet service before the routing protocol converges again.Also, with multi-next hop routing technology,the packets can be forwarded to destination in parallel that can effectively ease the network congestion.Combined with the state 863 project"fast healing routing protocol and test system", the purpose of this the dissertation is to design a multi-next hop routing algorithm for fast network recovery and a routing protocol based on this algorithm. The main work of this thesis is outlined as follows:Three points are provided and analysed to design multi-next hop routing algorithm for fast network recovery:loop-free, local fast recovery and message overhead.Then we analyze the typical algorithm of MDVA(Multipath Distance-Vector Algorithm) and find some disadvantages according to the three points discussed above,which make it clear for how to improve MDVA and propose a new multi-next hop routing algorithm.MDVA uses directed routing graph to describe multi-next hop routing that make it easy to design the algorithm which is loop-free. A new multi-next hop routing algorithm MNHRA (Multi-Next Hop Routing Algorithm) is provided based on improved MDVA from two aspects,which include creating directed routing graph initially and modifying the directed routing graph when the topology is changed.The improvements can be discribed as follows:A new method of comparing the best cost and router ID between neighbor nodes is used by MNHRA to creat directed routing graph ,which make MNHRA exploit the resource better than MDVA;Two new schemes of"respond in advance"at the"exit"nodes and"reverse in advance"are provided by MNHRA in the process of modifying directed routing graph ,which make the network recover faster than MDVA from network failures;The method of"not enquire back"that used by MNHRA is effective to reduce the message overhead compared with MDVA. The routing protocol MNHRP(Multi-Next Hop Routing Protocol) is designed based on MNHRA form three aspects: six types of key protocol message, multi-next hop routing table based on binary tree and single linked list, the process of protocol that send or receive the protocol message and update the multi-next hop routing table.Due to the lack of simulation tool of multi-next hop routing algorithm,especially the routing algorithm based on distance-vector.The designed scheme of MNHRP has been implemented on the network simulation software SSFNet, which provides a useful simulation platform for the research of multi-next hop routing. |
PDF Full Text Request