A Tabu Search Based Algorithm for Multicast Routing with QoS Constraints

Author

Ghaboosi, Nejla ; Haghighat, Abolfazl T.

Author_Institution

Islamic Azad Univ., Tehran

fYear

2006

fDate

18-21 Dec. 2006

Firstpage

33

Lastpage

39

Abstract

The advent of various real-time multimedia applications in high-speed networks prompt the necessity of quality of service (QoS) based multicast routing and the constrained Steiner tree as the mathematical structure behind it which is a well- known NP-complete problem. Two important QoS constraints are the bandwidth constraint and the end-to-end delay constraint. In this paper, an algorithm is proposed to solve the bandwidth-delay- constrained least-cost multicast routing problem based on Tabu Search (TS). Computational results for various random generated networks show that the proposed algorithm outperforms other existing TS-based algorithms and heuristics.

Keywords

bandwidth allocation; multicast communication; multimedia communication; optimisation; quality of service; search problems; telecommunication network routing; telecommunication network topology; trees (mathematics); NP-complete problem; QoS constraints; TS based algorithm; bandwidth-delay-constrained least-cost multicast routing problem; constrained Steiner tree; end-to-end delay constraint; high-speed networks; mathematical structure; quality of service; real-time multimedia applications; tabu search based algorithm; Application software; Computer networks; Costs; Delay; Heuristic algorithms; Iterative algorithms; Multicast algorithms; Quality of service; Routing; Tree graphs; Constrained Steiner tree; Multicast routing; Quality of Service; Tabu Search;

fLanguage

English

Publisher

ieee

Conference_Titel

Information Technology, 2006. ICIT '06. 9th International Conference on

Conference_Location

Bhubaneswar

Print_ISBN

0-7695-2635-7

Type

conf

DOI

10.1109/ICIT.2006.22

Filename

4273146