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

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