Naslov
A GRASP Heuristic for the Delay-Constrained Multicast Routing Problem

Autori
Skorin-Kapov, Nina ; Kos, Mladen

Vrsta, podvrsta i kategorija rada
Radovi u zbornicima skupova, cjeloviti rad (in extenso), znanstveni

Izvornik
The Proceedings of the 12th International Conference on Telecommunication Systems Management : ICTSM12 / Gavish, Bezalel ; Bordetsky, Alex - Monterey (CA), 2004, 1-10

Skup
12th International Conference on Telecommunication Systems

Mjesto i datum
Monterey (CA), Sjedinjene Američke Države, 22.07.2004. - 25.07.2004

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
multicast; constrained Steiner Tree; GRASP; QoS

Sažetak
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.

Izvorni jezik
Engleski

Znanstvena područja
Elektrotehnika

POVEZANOST RADA