Constructing minimum cost dynamic multicast trees under delay constraint

摘要

Multicast is an efficient way for group communication over the Internet. The performance of multicast relies greatly on the multicast tree constructed among the group members. Constructing a multicast tree spanning a set of group members with minimum cost is called Steiner tree problem which is a well-known NP-hard problem. Existing heuristic algorithms can build such a Steiner tree statically when the group members are known in advance. However, in many multicast tree dynamically. In addition, QoS is becoming a more important issue in multicast applications, and many applications, pose a tight bound on end-to-end delay. In this paper, we design a heuristic algorithm which can construct a delay constrained minimum cost multicast tree dynamically. Our algorithm can add or remove a group number without rerouting the path between the source and other group members. The algorithm not only avoids packet loss but also saves network bandwidth. Our algorithm guarantees that the end-to-end delay between the source and any group member is bounded with a threshold. Simulation results show that the algorithm achieves a good balance between the cost of a multicast tree and the time of the construction.