应用层组播的最小延迟生成树算法

• 作者: 曹佳 鲁士文
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 应用层组播 最小延迟生成树 NP-hard 实时传输
• 年，卷（期）: 2005,（10）
• 所属期刊栏目: 计算机网络与信息安全
• 页码范围: 1766-1773
• 页数: 8页
• 分类号: TP393
• 字数: 7788字
• 语种: 中文

摘要

实时传输是应用层组播技术的一个主要应用领域,对网络延迟有严格的限制.保证低延迟组播成功的关键在于构建高效的应用层组播树,研究构建最小延迟应用层组播树的算法.首先分析影响延迟的3个因素:链路的传输时间、结点的发送/转发时间和结点度,然后把求解应用层组播树的问题抽象成对边和点都带权的有向图求解"度约束最小延迟生成树"的问题,同时证明这个问题属于NP-hard,并且提出了两类启发式近似算法:基于度的算法和基于最大延迟路径的算法.最后通过模拟实验说明了所提出算法的有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	鲁士文	中国科学院计算技术研究所	74	658	13.0	22.0