Unicast Routing Protocol For Rapid Convergence Of Research And Application Of The Algorithm

Single-Source Shortest Path as a basic problem of Graph theory, is widely used in the real world. In these applications, SPT need store and update after topology changed. Static SPT algorithms have to recomputed a new SPT after topology changed for they unable to use the information of the old SPT. Yet dynamic SPT algorithms update the old SPT to incremental compute a new SPT, therefore promote the efficiency of SPT computing.In routing area, dynamic SPT algorithms are called ISPF(Incremental Shorest Path First), which only updates the nodes those path changed on SPT, thus improves the efficiency of routing protocols and reduces shocking of nework routing.Morever, the realization of ISPF is in favor of PRC(Partial Route Compute). PRC is significative to improve the running efficiency of routing protocols.The research of dynamic SPT algorithms now is ripe. But most dynamic SPT algortihms are node updating algorithms, although XiaoBin algorithm for multiple links'decrement is a batch update algorithm, there have been rare research on batch update algorithms for multi-links'increment, furthermore, all of existed dynamic SPT algorithms don't support load balancing, which is a precondition of PRC in Routing Protocols. Base on the problems above, after deeply analyzing of the existing dynamic SPT algorithms, research of this paper mainly focuses on the following four aspects.1. A dynamic SPT algorithm for multi-links'weight increment is proposed, simul- ation shows that compared to XiaoBin node update algorithm, this algorithm has better time efficientcy and less redundant computation.2. In order to realize PRC, a next-hop incremental compute algorithm based on dynamic algorithms is put forward.3. In order to apply dynamic SPT algorithms to routing protocols, a method of load balancing expansion for dynamic SPT algorithms is proposed and then used to expanse two semi-dynamic SPT algorithms.4. Combining with expansed dynamic SPT algorithms and next-hop incmremental compute algorthim, we propose a implementation scheme of PRC.