Abstract: This paper presents a fast low-cost algorithm of delay-constrained dynamic multicast routing. When adding multicast nodes, it uses improved delay-constrained shortest path subgraph to avoid searching non-delay-constrained shortest path, which greatly improves the efficiency of the algorithm. By sharing longest shortest path as much as possible, it greatly reduces total cost of constructing multicast tree. Simulation results show that this algorithm has less computation time and low multicast tree total cost than Shortest Best Path Ttree(SBPT) algorithm, and multicast tree is more stable.

Key words: Steiner tree, shortest path subgraph, dynamic multicast routing, delay-constrained, fast low-cost algorithm

摘要： 提出一种时延约束动态组播路由的快速低代价算法。该算法利用改进的时延约束最短路径子图，在加入组播节点时避免非时延约束最短路径的搜索，提高算法的计算效率。通过使新加入节点与树上已有节点共享最短路径，降低整棵组播树的代价。仿真结果表明，该算法计算时间少，组播树总代价低，能使组播树更稳定。

关键词: Steiner树, 最短路径子图, 动态组播路由, 时延约束, 快速低代价算法

CLC Number: 

• TP393