低代价最短路径树的快速算法

A Fast Low-Cost Shortest Path Tree Algorithm

低代价最短路径树是一种广泛使用的多播树.它能够在保证传送时延最小的同时尽量降低带宽消耗.在DDSP(destination-driven shortest path)算法的基础上,通过改进节点的搜索过程,提出了快速低代价最短路径树算法FLSPT(fast low-cost shortest path tree).该算法构造的最短路径树与DDSP算法构造的树具有相同的性能,但其时间复杂度低于DDSP算法.随机网络模型的仿真结果表明,FLSPT算法效率更高.

Low-Cost Shortest Path Tree is a commonly-used multicast tree type, which can minimize the end-to-end delay and at the same time reduce the bandwidth requirement if possible. Based on the low-cost shortest path tree algorithm DDSP (destination-driven shortest path) and through improving on the search procedure, a Fast Low-cost Shortest Path Tree (FLSPT) algorithm is presented in this paper. The Shortest Path Tree constructed by the FLSPT algorithm is the same as that constructed by the DDSP algorithm, but its computation complexity is lower than that of the DDSP algorithm. The simulation results with random network models show that FLSPT algorithm is more effective.