满足时延及时延差别约束的组播路由问题研究

摘要

组播是一种点到多点的网络数据传播技术，在视频点播、电视会议、网络游戏等方面具有很好的应用价值。组播路由算法的目标是寻找一棵连接源节点和多个目的节点的组播树，同时满足各种服务质量需求。在实时交互性组播应用中，时延和时延差别等服务质量因素显得尤为重要。为此，本文研究受时延和时延差别约束的组播路由问题。 本文首先研究时延约束下的组播路由问题。该问题的目标是创建一棵覆盖源节点和目的节点的代价最小树，且满足端到端时延要求。这个问题被证明是NP完全问题。我们在研究已有算法的基础上，提出一个新的启发式算法，称为STBMR算法。该算法在构造满足时延约束的组播树过程中，先构造最小生成树作为初始树，然后以时延最小路径代替树中的时延越界路径，直至树的根节点到所有目的节点的路径满足时延要求。该算法简单、易实现，与经典的KPP算法相比，有较小的算法复杂性，但性能稍差。实验表明，STBMR算法构造的组播树费用比KPP算法构造的约大4％，算法执行时间比KPP算法约少54％。 然后，本文分析限制时延差别对某些组播应用的重要意义，并就时延及时延差别约束的组播路由问题，提出一启发式算法EDVCMR。该算法首先将时延上限值分成若干区间段，再分别找出时延在各个区间段的路径，显然这些路径都会满足时延约束。然后，从得到的若干路径中选取满足时延差别约束的源节点到各目的节点的路径，从而得到一棵满足时延和时延差别约束的组播树。通过模拟实验比较该算法与其它已发表算法的性能，包括算法运行时间以及算法的成功率。

目录

文摘

英文文摘

论文说明：插图索引及附表索引

湖南大学学位论文原创性声明和学位论文版权使用授权书

第1章绪论

第2章服务质量约束的组播路由问题

第3章时延约束的组播路由问题

第4章时延及时延差别约束的组播路由问题

结论

参考文献

附录A攻读学位期间所完成学术论文及参与项目目录

致谢