An efficient algorithm for constructing delay bounded minimum cost multicast trees

Multimedia applications are usually resource intensive, have stringent quality of service requirements, and in many cases involve large groups of participants. Multicasting is poised to play an important role in future deployment of these applications. This paper focuses on developing delay-bounded, minimum-cost multicast trees, linking a source to a set of multicast destination nodes. The approach taken in this paper is efficient, flexible and unique in the sense that it cleverly limits its computation only to paths that originate at multicast nodes, thereby avoiding computing paths that exclusively link non-multicast nodes. The simulation results show that the multicast trees produced by the proposed heuristic are of lower cost than those produced by other well-known heuristics, including those which use an expensive k-shortest-paths procedure to minimize the cost of the multicast tree. Furthermore, the results show that, in comparison to other heuristics, the proposed scheme results in a significant reduction in the computation time required to build the multicast tree.