延迟变化紧密的多核心组播树快速构建算法

Tightest delay-variation multi-cores based multicast tree fast constructing algorithm

为了解决在具有延迟及延迟变化约束组播树的构建问题中存在的算法实用性差、复杂度高和重构代价大等问题,提出基于扁平多核心树结构的、采用基于延迟变化过滤窗口的多核心节点选取机制的组播树快速构建算法.该算法极大地拓展了初始组播树的寻解空间,且能够找到具有最严格的延迟变化约束的目标树.该算法实用性强,目标树的可维护性好且局部恢复代价小.理论上,该算法在时间复杂度上与该项性能最好的延迟及延迟变化约束算法(DDVCA)相同.模拟实验中,在相同的延迟及延迟变化约束条件下构建大规模组播树,该算法相比延迟及延迟变化约束算法最多能够节省60%的执行时间.模拟实验还表明,随着延迟变化约束越来越小,与延迟变化约束性能最好的链式算法相比,该算法能够以更大的概率找到合适的组播树;该算法能够获得最紧密的延迟变化约束性能.

In order to solve the problems such as bad practicability, high complexity and costly reconstruc- tion in the constructing of delay and delay-variation bounded multicast tree, a fast multicast tree construc- ting algorithm was presented, which is based on the novel plain structure of multi-cores tree and using the sliding delay-variation window for multiple cores selection mechanism. The algorithm provides large solu- tion seeking space for initial multicast tree and the tightest delay-variation bounded constraint for the result tree. The practicability for the algorithm is good, and the result tree has good performance of maintain- ability and small cost of local reconstruction. In theory, the time complexity for the algorithm is equal to delay and delay variation constraint algorithm （DDVCA）, which has the best performance in time com- plexity. In simulated experiments to construct the large-scale multicast tree, the execution time of our al- gorithm is at most 60% shorter than DDVCA under the same constraints on delay and delay-variation bounds. With more shoter delay-variation constraint, comparing with Chains algorithm that has the tigh- test delay-variation constraint so far as I know, our algorithm can find result multicast tree with much more probability. Extensive experiments show that the tightest delay-variation constaint can be obtained by the algorithm.