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

发布时间：2018-04-25 12:45

本文选题：组播路由 + 初始组播树　；参考：《浙江大学学报(工学版)》2013年01期

【摘要】：为了解决在具有延迟及延迟变化约束组播树的构建问题中存在的算法实用性差、复杂度高和重构代价大等问题,提出基于扁平多核心树结构的、采用基于延迟变化过滤窗口的多核心节点选取机制的组播树快速构建算法.该算法极大地拓展了初始组播树的寻解空间,且能够找到具有最严格的延迟变化约束的目标树.该算法实用性强,目标树的可维护性好且局部恢复代价小.理论上,该算法在时间复杂度上与该项性能最好的延迟及延迟变化约束算法(DDVCA)相同.模拟实验中,在相同的延迟及延迟变化约束条件下构建大规模组播树,该算法相比延迟及延迟变化约束算法最多能够节省60%的执行时间.模拟实验还表明,随着延迟变化约束越来越小,与延迟变化约束性能最好的链式算法相比,该算法能够以更大的概率找到合适的组播树;该算法能够获得最紧密的延迟变化约束性能.
[Abstract]:In order to solve the problems in constructing multicast tree with delay and delay constraints, such as poor practicability, high complexity and high cost of reconstruction, a flat multi-core tree structure is proposed. A fast algorithm for constructing multicast tree based on multi-core node selection mechanism based on delay change filtering window is proposed. The algorithm greatly extends the search space of the initial multicast tree and can find the target tree with the strictest delay variation constraint. The algorithm has strong practicability, good maintainability of target tree and low local recovery cost. Theoretically, the time complexity of this algorithm is the same as that of delay and delay variation constraint algorithm (DDVCA). In the simulation experiment, the large scale multicast tree is constructed under the same constraints of delay and delay variation. The algorithm can save up to 60% of the execution time compared with the delay and delay variation constraint algorithm. The simulation results also show that with the change of delay constraints becoming smaller and smaller, compared with the best chain algorithm, the algorithm can find the appropriate multicast tree with a higher probability. The algorithm can obtain the closest delay variation constraint performance.
【作者单位】：浙江大学计算机科学与技术学院;
【基金】：百万册数字图书馆服务系统Ipv6升级资助项目(CNGI2008-112)
【分类号】：TP393.02

【相似文献】