Paper Info
Title
A GRASP heuristic for the delay-constrained multicast routing problem
Abstract
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.
Year
DOI
Venue
2006
10.1007/s11235-006-8202-2
Telecommunications Systems
Keywords
Field
DocType
GRASP,Multicast,Constrained steiner tree,QoS
Protocol Independent Multicast,Source-specific multicast,Heuristic,Steiner tree problem,Computer science,Xcast,Computer network,Pragmatic General Multicast,Multicast,Distance Vector Multicast Routing Protocol,Distributed computing
Journal
Volume
Issue
ISSN
32
1
1018-4864
Citations 
PageRank 
References 
16
0.75
6
Authors
2
Name
Order
Citations
PageRank
Nina Skorin-Kapov114314.89
Mladen Kos2213.42