Pregled bibliografske jedinice broj: 121450
The Application of Steiner Trees to Delay Constrained Multicast Routing: a Tabu Search Approach
The Application of Steiner Trees to Delay Constrained Multicast Routing: a Tabu Search Approach // ConTEL 2003 : proceedings of the 7th International Conference on Telecommunications / Jevtić, Dragan ; Mikuc, Miljenko (ur.).
Zagreb: Fakultet elektrotehnike i računarstva Sveučilišta u Zagrebu, 2003. str. 443-448 (predavanje, međunarodna recenzija, cjeloviti rad (in extenso), znanstveni)
CROSBI ID: 121450 Za ispravke kontaktirajte CROSBI podršku putem web obrasca
Naslov
The Application of Steiner Trees to Delay Constrained Multicast Routing: a Tabu Search Approach
Autori
Skorin-Kapov, Nina ; Kos, Mladen
Vrsta, podvrsta i kategorija rada
Radovi u zbornicima skupova, cjeloviti rad (in extenso), znanstveni
Izvornik
ConTEL 2003 : proceedings of the 7th International Conference on Telecommunications
/ Jevtić, Dragan ; Mikuc, Miljenko - Zagreb : Fakultet elektrotehnike i računarstva Sveučilišta u Zagrebu, 2003, 443-448
ISBN
953-184-052-0
Skup
7th International Conference on Telecommunications : ConTEL 2003
Mjesto i datum
Zagreb, Hrvatska, 11.06.2003. - 13.06.2003
Vrsta sudjelovanja
Predavanje
Vrsta recenzije
Međunarodna recenzija
Ključne riječi
multicast; constrained Steiner Tree; tabu search; QoS
Sažetak
With today's deveopment of information technology comes the increased development of numerous real-time multimedia network applications. Some examples include video and tele-conferencing, tele-medicine, video-on-demand, distance education, applications in finance, etc. Several of these applications require multicasting with a certain Quality of Service (QoS). One of the most important QoS parameters is the maximum end-to-ed delay from the source to any destination in a multicast session. This paper deals with the problem of Delay-Constrained Multicast Routing (DCMR). The DCMR problem can be reduced to the Constrained Minimum Steiner Tree Problem in Graphs (CMStTG). Since the minimum Steiner Tree Problem in Graphs (MStTG) has been proven to be NP-complete, several heuristics have been developed for solving MStTG and CMStTG. In this paper, we suggest a tabu search heuristic for the DCMR problem. This heuristic was developed on the basis of a tabu search heuristic designed for solving unconstrained minimum Steiner tree problems. Preliminary testing on data from a publically available library, SteinLib, has shown that this heuristic gives near optimal solutions in moderate time and a moderate number of iterations for medium sized problems (50-100 nodes). Comparing with a well known algorithm for solving the CMStTG problem, tests have shown that our tabu search heuristic is superior in quality for medium sized problems.
Izvorni jezik
Engleski
Znanstvena područja
Elektrotehnika
