QoS-driven multicast tree generation using Tabu search

Habib Youssef; Abdulaziz Al-Mulhem; Sadiq M. Sait; Muhammad Atif Tahir

doi:10.1016/S0140-3664(02)00029-4

QoS-driven multicast tree generation using Tabu search

Habib Youssef, Abdulaziz Al-Mulhem^*, Sadiq M. Sait, Muhammad Atif Tahir

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

44 Scopus citations

Abstract

Many multimedia communication applications require a source to transmit messages to multiple destinations subject to Quality-of-Service (QoS) delay constraint. The problem to be solved is to find a minimum cost multicast tree where each source to destination path is constrained by a delay bound. This problem has been proven to be NP-complete. In this paper, we present a Tabu Search (TS) algorithm to construct a minimum cost delay bounded multicast tree. The proposed algorithm is then compared with many existing multicast algorithms. Results show that on almost all test cases, TS algorithm exhibits more intelligent search of the solution subspace and is able to find better solutions than other reported multicast algorithms.

Original language	English
Pages (from-to)	1140-1149
Number of pages	10
Journal	Computer Communications
Volume	25
Issue number	11-12
DOIs	https://doi.org/10.1016/S0140-3664(02)00029-4
State	Published - 1 Jul 2002

Bibliographical note

Funding Information:
The authors acknowledge King Fahd University of Petroleum and Minerals, Dhahran, Saudi Arabia, for supporting this research project.

Keywords

Multicast tree
Optimization
QoS routing
Shortest path
Tabu Search

ASJC Scopus subject areas

Computer Networks and Communications

Access to Document

10.1016/S0140-3664(02)00029-4

Cite this

@article{a1589ece38d04b2286bdf06b20c4351b,

title = "QoS-driven multicast tree generation using Tabu search",

abstract = "Many multimedia communication applications require a source to transmit messages to multiple destinations subject to Quality-of-Service (QoS) delay constraint. The problem to be solved is to find a minimum cost multicast tree where each source to destination path is constrained by a delay bound. This problem has been proven to be NP-complete. In this paper, we present a Tabu Search (TS) algorithm to construct a minimum cost delay bounded multicast tree. The proposed algorithm is then compared with many existing multicast algorithms. Results show that on almost all test cases, TS algorithm exhibits more intelligent search of the solution subspace and is able to find better solutions than other reported multicast algorithms.",

keywords = "Multicast tree, Optimization, QoS routing, Shortest path, Tabu Search",

author = "Habib Youssef and Abdulaziz Al-Mulhem and Sait, \{Sadiq M.\} and Tahir, \{Muhammad Atif\}",

note = "Funding Information: The authors acknowledge King Fahd University of Petroleum and Minerals, Dhahran, Saudi Arabia, for supporting this research project. ",

year = "2002",

month = jul,

day = "1",

doi = "10.1016/S0140-3664(02)00029-4",

language = "English",

volume = "25",

pages = "1140--1149",

journal = "Computer Communications",

issn = "0140-3664",

number = "11-12",

}

TY - JOUR

T1 - QoS-driven multicast tree generation using Tabu search

AU - Youssef, Habib

AU - Al-Mulhem, Abdulaziz

AU - Sait, Sadiq M.

AU - Tahir, Muhammad Atif

N1 - Funding Information: The authors acknowledge King Fahd University of Petroleum and Minerals, Dhahran, Saudi Arabia, for supporting this research project.

PY - 2002/7/1

Y1 - 2002/7/1

N2 - Many multimedia communication applications require a source to transmit messages to multiple destinations subject to Quality-of-Service (QoS) delay constraint. The problem to be solved is to find a minimum cost multicast tree where each source to destination path is constrained by a delay bound. This problem has been proven to be NP-complete. In this paper, we present a Tabu Search (TS) algorithm to construct a minimum cost delay bounded multicast tree. The proposed algorithm is then compared with many existing multicast algorithms. Results show that on almost all test cases, TS algorithm exhibits more intelligent search of the solution subspace and is able to find better solutions than other reported multicast algorithms.

AB - Many multimedia communication applications require a source to transmit messages to multiple destinations subject to Quality-of-Service (QoS) delay constraint. The problem to be solved is to find a minimum cost multicast tree where each source to destination path is constrained by a delay bound. This problem has been proven to be NP-complete. In this paper, we present a Tabu Search (TS) algorithm to construct a minimum cost delay bounded multicast tree. The proposed algorithm is then compared with many existing multicast algorithms. Results show that on almost all test cases, TS algorithm exhibits more intelligent search of the solution subspace and is able to find better solutions than other reported multicast algorithms.

KW - Multicast tree

KW - Optimization

KW - QoS routing

KW - Shortest path

KW - Tabu Search

UR - https://www.scopus.com/pages/publications/0036643062

U2 - 10.1016/S0140-3664(02)00029-4

DO - 10.1016/S0140-3664(02)00029-4

M3 - Article

AN - SCOPUS:0036643062

SN - 0140-3664

VL - 25

SP - 1140

EP - 1149

JO - Computer Communications

JF - Computer Communications

IS - 11-12

ER -

QoS-driven multicast tree generation using Tabu search

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this