计算机工程 ›› 2012, Vol. 38 ›› Issue (10): 83-85.doi: 10.3969/j.issn.1000-3428.2012.10.024

• 网络与通信 • 上一篇    下一篇

一种改进的时延受限多播路由算法

杨春德 a,秦宗伟 b   

  1. (重庆邮电大学 a. 数理学院;b. 计算机科学与技术学院,重庆 400065)
  • 收稿日期:2011-09-19 出版日期:2012-05-20 发布日期:2012-05-20
  • 作者简介:杨春德(1964-),男,教授,主研方向:网络优化,随机系统分析;秦宗伟,硕士研究生
  • 基金项目:
    重庆市教委科学技术研究基金资助项目(KJ090509)

Improved Delay-constrained Multicast Routing Algorithm

YANG Chun-de a, QIN Zong-wei b   

  1. (a. College of Mathematics and Physics; b. College of Computer Science and Technology, Chongqing University of Posts and Telecommunication, Chongqing 400065, China)
  • Received:2011-09-19 Online:2012-05-20 Published:2012-05-20

摘要: 针对DCMPH算法不能合理选择连接路径的问题,提出一种改进的满足时延限制的多播路由算法。该算法对不能用最小代价路径连接到多播树上的目的节点,求出其到多播树上所有节点的最小时延路径,再从中选出一条能满足时延限制的费用最小的路径,添加到多播树上。实验结果表明,与DCMPH算法相比,该算法构造多播树的代价更低。

关键词: 多播路由算法, 时延受限, 服务质量, Steiner树, 多播树, NP完全问题

Abstract: Aiming at the problem of DCMPH algorithm can not choose the connection path reasonably, an improved meeting delay-constrained multicast routing algorithm is proposed in this paper. In the algorithm, if the destination nodes can not use the least-cost path to join the multicast tree, it calculates the least-delay path to all the nodes in the multicast tree, and then selects the least-cost path which meets the delay constraint to add to the multicast tree. Experimental results show that the cost of the new algorithm in constructing multicast routing tree is superior to DCMPH algorithm.

Key words: multicast routing algorithm, delay-constrained, Quality of Service(OoS), Steiner tree, multicast tree, NP-complete problem

中图分类号: