Abstract: Multicasting is a communication service that allows a source to efficiently transmit copies of data packet to destination nodes for meeting end-to-end QoS （Quality of Service） requirements of real-time applications and its algorithm must be NP-completeness. QoS provisioning generally assumes more than one QoS measure which implies that a routing algorithm may have multiple constraints：delay, delay-variation and cost, etc. After research of related algorithm for constructing the multicast tree, a delay and delay-variation bounded minimum cost multicast routing algorithm（DDVMC） is proposed in this paper. The DDVMC algorithm uses a greedy strategy based on Dijkstra minimal spanning trees and local information to construct lower cost multicast tree. Furthermore, this algorithm offers a good balance between tree cost, delay and delay-variation. Simulation results show that this algorithm not only can construct constrained multicast tree correctly, but also has a less cost and a lower computational complexity.

Key words: multicast communication, local information, Dijkstra SPT, end-to-end quality of service, Steiner tree

摘要： 组播通信是从一个源节点同时向网络中的多个目的节点发送分组的通信服务，它一般提供一个以上的端到端的服务约束，实际的路由算法在应用时可以受到多重约束，解决这类问题的组播路由算法是NP完全的。在研究了构建组播树的相关算法后，提出了一种新的时延和时延差约束的低代价组播路由算法—DDVMC。该算法采用基于贪婪策略的Dijkstra最小生成树算法，利用局部信息来构建低代价组播树，很好地平衡了树的代价、时延和时延差。仿真表明，该算法能正确地构造出满足约束的组播树，同时还具有较低的代价和计算复杂度。

关键词: 组播通信, 局部信息, Dijkstra 最小生成树, 端到端服务质量, Steiner树