An Efficient Heuristic Algorithm for QoS-Driven Multicast Tree Generation
Manas Ranjan Kabat, Sandeep Kumar Mohanty, Rajib Mall, Chitta Ranjan Tripathy · 2006
Many multimedia communication applications require a source to transmit messages to multiple destinations subject to quality of service (QoS) delay constraint. The problem to be solved is to find a minimum cost multicast tree where each source to destination path is constrained by a delay bound. This problem has been proven to be NP-Complete. In this paper, we present a more efficient heuristic algorithm, namely, Cost Sensitive Delay Constrained Multicast (CSDCM) algorithm, based on a novel heuristic function, to construct a minimum cost delay bounded multicast tree. A noteworthy feature of this algorithm is that it has very high probability of finding the optimal solution in polynomial time with low computational complexity.