吉林大学学报(工学版)

• • Previous Articles     Next Articles

Complete dynamic algorithm for updating shortest path tree

Sun Zhi-xin1, Gao Yan-juan1，Wang Wen-ding2   

  1. 1.School of Computer Science and Technology, Nanjing University of Posts and Telecommunications, Nanjing 210003, China; 2. School of Communication, Nanjing University of Posts and Telecommunications, Nanjing 210003, China
  • Received:2006-07-14 Revised:2006-09-23 Online:2007-07-01 Published:2007-07-01
  • Contact: Sun Zhi-xin

PDF (PC)

395

Abstract: A new complete dynamic algorithm for updating shortest path (CD-SPT) tree was proposed by combining the existing algorithm for updating shortest path tree (SPT) and the solution for SPT when a node is added or deleted. When the network topology changes, the increase or decrease of edge-weight and the addition or deletion of nodes can be processed by the CD-SPT algorithm respectively. This algorithm pays attention only to the changes of nodes and edges by taking fully use of the useful information provided by the existing SPT. Computation of the redundancy can be reduced by minimizing the computation scope, thus the total computation can be significantly reduced. Simulation experiment verifies the good performance and high efficiency of the CDSPT algorithm.

Key words: computer systems organization, routing protocol, SPF algorithm, shortest path tree, dynamic update

CLC Number: 

  • TP393
[1] ZHANG Wei-wei, HE Jia-feng, GAO Guo-wang, REN Li-li, SHEN Xuan-jing. Wireless Mesh network routing and channel allocation union optimization algorithm based on game theory [J]. 吉林大学学报(工学版), 2018, 48(3): 887-892.
[2] DONG Jian-feng, ZHANG Yu-feng, DAI Zhi-qiang. Improved recommendation algorithm based on DPM model [J]. 吉林大学学报(工学版), 2018, 48(2): 596-604.
[3] LIU Lei, LIU Li-juan, WU Xin-wei, ZHANG Peng. Compiler testing method based on ECP metamorphic relation [J]. 吉林大学学报(工学版), 2017, 47(4): 1262-1267.
[4] DONG Li-yan, WANG Yue-qun, HE Jia-nan, SUN Ming-hui, LI Yong-li. Collaborative filtering recommendation algorithm based on time decay [J]. 吉林大学学报(工学版), 2017, 47(4): 1268-1272.
[5] DENG Chang-yi, GUO Rui-feng, ZHANG Yi-wen, WANG Hong-liang. Lower power dynamic scheduling algorithm for sporadic tasks based on balance factor [J]. 吉林大学学报(工学版), 2017, 47(2): 591-600.
[6] FENG Xiao-ning, WANG Zhuo, ZHANG Xu. Formal method for routing protocol of WSN based on L-π calculus [J]. 吉林大学学报(工学版), 2015, 45(5): 1565-1571.
[7] WU Yu-cheng, FU Hong-yu. Routing strategy for emergency monitoring of large-scale wireless sensor network [J]. 吉林大学学报(工学版), 2013, 43(03): 801-806.
[8] ZHANG Hua, PENG Lai-hu, HU Xu-dong, WANG Xian-mei. Model of enterprise cloud manufacture applying to textile machining industry [J]. 吉林大学学报(工学版), 2012, 42(增刊1): 337-340.
[9] WANG Xin-ying, LIU Gang, GU Fang-ming, XIAO Wei. Heterogeneous feature fusion method based on semantic and shape for 3D model retrieval [J]. 吉林大学学报(工学版), 2012, 42(增刊1): 359-363.
[10] WU Xiao-xuan, NI Zhi-wei, NI Li-ping. Clustering ensembles algorithm based on fractal dimension [J]. 吉林大学学报(工学版), 2012, 42(增刊1): 364-367.
[11] LIU Zhuang, FANG Zhi-yi, ZHANG Chun-fei, CHEN Lin, ZHAO Yang. Energy-efficient amendatory algorithm based on energy-consumption transference and data gravitation in wireless sensor networks [J]. , 2012, 42(05): 1237-1242.
[12] LIU Xian, GUO Rui-feng, DING Wan-fu. Schedulability of rollback recovery fault-tolerant real-time system based on priority mixed strategy [J]. , 2012, 42(05): 1243-1250.
[13] CHAI Zheng-yi, WU Hui-xin, WU-Yong. Optimization algorithm for immune real-value detector generation [J]. , 2012, 42(05): 1251-1256.
[14] LI Min, JIA Chun-fu, LI Jing-wei, LIU Zhe-li, DONG Zong-qing. Format-preserving encryption for variable-length encoding character data [J]. , 2012, 42(05): 1257-1261.
[15] LIU Yan-heng, FU Feng, ZHU Jian-qi, SUN Xin. DoS detection model base on alive entropy [J]. 吉林大学学报(工学版), 2011, 41(4): 1059-1064.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd