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

摘要：

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

关键词：组播路由、初始组播树、多核心组播树、延迟及延迟变化约束

所属期刊栏目：47

分类号：TP393.03(计算技术、计算机技术)

资助基金：百万册数字图书馆服务系统Ipv6升级资助项目CNGI2008-112

在线出版日期：2013-05-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：29-36