首页 | 本学科首页   官方微博 | 高级检索  
     

时延及时延抖动限制的最小代价多播路由策略
引用本文:王明中,谢剑英,张敬辕. 时延及时延抖动限制的最小代价多播路由策略[J]. 计算机学报, 2002, 25(5): 534-541
作者姓名:王明中  谢剑英  张敬辕
作者单位:上海交通大学控制工程及网络技术研究室,上海,200030
摘    要:满足多种服务质量请求的多播路由问题是目前多播通信中的重要课题之一。该文作者在研究受端到端时延及时延抖动限制的多播路由问题的过程中,发现当前许多算法所普遍使用的两个最佳链路选择函数并不能完全体现路由的动态过程,同时它们还存在一定的缺陷。而正是由于这种缺陷,在某些情况下通过这两个最佳链路选择函数所得到的结果树可能不包含所有的目标节点,文中称这种情况为“多播不可达”。针对上述问题,该文提出了“多播可达”的假设条件以及一个新的最佳链路选择函数,并在此基础上提出了一个满足时延及时延抖动双重限制的最小代价多播树的建立算法(DDVBMRA)以及一种动态重组多播组目标节点的方法。仿真结果表明本算法具有很好的延抖动及代价性能。

关 键 词:多播路由策略 服务质量 链路选择函数 时延 时延抖动 计算机网络
修稿时间:2001-05-24

Strategy of Constructing Minimum Cost Multicast Routing Tree with Delay and Delay Variation Bounds
WANG Ming Zhong XIE Jian Ying ZHANG Jing Yuan. Strategy of Constructing Minimum Cost Multicast Routing Tree with Delay and Delay Variation Bounds[J]. Chinese Journal of Computers, 2002, 25(5): 534-541
Authors:WANG Ming Zhong XIE Jian Ying ZHANG Jing Yuan
Abstract:This paper studies the problem of constructing multicast routing tree with delay and delay variation bounds. This problem can be formulated as that of finding a minimum cost Steiner Tree, which satisfies the constraints above mentioned and is known to be computationally intractable, being NP complete. While researching into the problem of constructing multicast routing tree with delay and delay variation bounds, we find that two best edge selection functions,which are betaken abroad to constructing multicast routing tree in many algorithms have some limitations. And just because of their limitations, on a certain occasion, the final tree constructed through them can not span all the destinations. At the same time they can not represent the dynamic characteristics of the routing process completely. Therefore, we propose a "destination reachable qualification" and a new edge selection function. In addition to the problem of delay and delay variation bounded multicast routing, based on our edge selection function, we put forward a heuristic algorithm called Delay and Delay Variation Bounded Multicast Routing Algorithm (DDVBMRA) by which a minimum cost multicast tree can be constructed. Besides, a method of adjusting to the dynamic change of multicast membership is introduced. It is shown that, in terms of delay variation and cost, the heuristic algorithm demonstrates good average case behavior through simulations on a large number of graphs.
Keywords:QoS  multicast routing  edge selection function  delay  delay variation  
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号