Loading...
Please wait, while we are loading the content...
Similar Documents
E.H.-M.Sha, “Dynamic Update of Shortest Path Tree in OSPF (2004)
| Content Provider | CiteSeerX |
|---|---|
| Author | Xiao, Bin Cao, Jiannong Zhuge, Qingfeng Shao, Zili Sha, Edwin H. -M. |
| Description | The Shortest Path Tree (SPT) construction is a critical is-sue to the high performance routing in an interior network using link state protocols, such as Open Shortest Path First (OSPF) and IS-IS. In this paper, we propose a new efficient algorithm for dynamic SPT update to avoid the disadvan-tages (e.g. redundant computation) caused by static SPT update algorithms. The new algorithm is based on the un-derstanding of the update procedure to reduce redundancy. Only significantly elements that contribute to the construc-tion of new SPT from the old one will be focused on. The efficiency of our algorithm is improved because it only pay attention to the edges really count for the update process. The running time for the proposed algorithm is maximum reduced, which is shown through experimental results. Fur-thermore, our algorithm can be easily generalized to solve the SPT updating problem in a graph with negative weight edges and applied to the scenario of multiple edge weight changes. 1 |
| File Format | |
| Language | English |
| Publisher Date | 2004-01-01 |
| Publisher Institution | in Proceedings of the 7th International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN’04 |
| Access Restriction | Open |
| Subject Keyword | Dynamic Update New Spt Open Shortest Path First Update Process Multiple Edge Weight Change New Algorithm Negative Weight Edge Critical Is-sue Spt Updating Problem Redundant Computation Interior Network Dynamic Spt Update Running Time Static Spt Update Algorithm Shortest Path Tree Experimental Result E.h. M.s Ha Update Procedure Link State Protocol High Performance Routing New Efficient Algorithm |
| Content Type | Text |
| Resource Type | Article |
