时延及时延抖动限制的最小代价多播路由策略

满足多种服务质量请求的多播路由问题是目前多播通信中的重要课题之一。该文作者在研究受端到端时延及时延抖动限制的多播路由问题的过程中，发现当前许多算法所普遍使用的两个最佳链路选择函数并不能完全体现路由的动态过程，同时它们还存在一定的缺陷。而正是由于这种缺陷，在某些情况下通过这两个最佳链路选择函数所得到的结果树可能不包含所有的目标节点，文中称这种情况为“多播不可达”。针对上述问题，该文提出了“多播可达”的假设条件以及一个新的最佳链路选择函数，并在此基础上提出了一个满足时延及时延抖动双重限制的最小代价多播树的建立算法（DDVBMRA）以及一种动态重组多播组目标节点的方法。仿真结果表明本算法具有很好的延抖动及代价性能。

Strategy of Constructing Minimum Cost Multicast Routing Tree with Delay and Delay Variation Bounds

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.