Naslov
A GRASP heuristic for the delay-constrained multicast routing problem

Autori
Skorin-Kapov, Nina ; Kos, Mladen

Izvornik
Telecommunication Systems (1018-4864) 32 (2006), 1; 55-69

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
GRASP; Multicast; Constrained steiner tree; 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