A GRASP heuristic for the delay-constrained multicast routing problem

The increasing development of real-time multimedia network applications, many of which require multiple participants, has created the need for efficient multicast routing algorithms. Examples of such applications include video and tele-conferencing, video-on-demand, tele-medicine, distance education, etc. Several of them require multicasting with a certain Quality of Service (QoS) with respect to elements such as delay or bandwidth. This paper deals with Delay-Constrained Multicast Routing (DCMR) where the maximum end-to-end delay in a multicast session is bounded. The DCMR problem can be reduced to the Constrained Minimum Steiner Tree Problem in Graphs (CMStTG) which has been proven to be NP-complete. As a result, several heuristics have been developed to help solve it. In this paper, we developed a GRASP heuristic for the DCMR problem. Computational experiments on medium sized problems (50-100 nodes) from literature and comparison with existing algorithms have shown that the suggested GRASP heuristic is superior in quality for this set of problems.