TY - GEN
T1 - An efficient algorithm for bandwidth-delay constrained least cost multicast routing
AU - Forsati, Rana
AU - Mahdavi, Mehrdad
AU - Haghighat, Abolfazl Torghy
AU - Ghariniyat, Azadeh
PY - 2008/9/22
Y1 - 2008/9/22
N2 - The advent of various real-time multimedia applications in high-speed networks creates a need for quality of service (QoS) based multicast routing. Two important QoS constraints are the bandwidth constraint and the end-to-end delay constraint. The QoS based multicast routing problem is a known NP-complete problem that depends on (1) bounded end-to-end delay and link bandwidth along the paths from the source to each destination, and (2) minimum cost of the multicast tree. In this paper we describe a new representation, called node parent index (NPI) representation, for representing trees and describe harmony operations accord to this representation. The presented algorithm is based on the harmony search (HS) algorithm and finds near-optimal solutions in polynomial time. We evaluate the performance and efficiency of the proposed method with a modified version of the bounded shortest multicast algorithm (BSMA) which is the best known deterministic heuristic algorithm to delay-constrained multicast problem. Simulation results reveal that the proposed algorithm can achieve a smaller average tree costs than modified BSMA with a much smaller running time for relatively large networks.
AB - The advent of various real-time multimedia applications in high-speed networks creates a need for quality of service (QoS) based multicast routing. Two important QoS constraints are the bandwidth constraint and the end-to-end delay constraint. The QoS based multicast routing problem is a known NP-complete problem that depends on (1) bounded end-to-end delay and link bandwidth along the paths from the source to each destination, and (2) minimum cost of the multicast tree. In this paper we describe a new representation, called node parent index (NPI) representation, for representing trees and describe harmony operations accord to this representation. The presented algorithm is based on the harmony search (HS) algorithm and finds near-optimal solutions in polynomial time. We evaluate the performance and efficiency of the proposed method with a modified version of the bounded shortest multicast algorithm (BSMA) which is the best known deterministic heuristic algorithm to delay-constrained multicast problem. Simulation results reveal that the proposed algorithm can achieve a smaller average tree costs than modified BSMA with a much smaller running time for relatively large networks.
UR - http://www.scopus.com/inward/record.url?scp=51849090691&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=51849090691&partnerID=8YFLogxK
U2 - 10.1109/CCECE.2008.4564820
DO - 10.1109/CCECE.2008.4564820
M3 - Conference contribution
AN - SCOPUS:51849090691
SN - 9781424416431
T3 - Canadian Conference on Electrical and Computer Engineering
SP - 1641
EP - 1645
BT - IEEE Canadian Conference on Electrical and Computer Engineering, Proceedings, CCECE 2008
T2 - IEEE Canadian Conference on Electrical and Computer Engineering, CCECE 2008
Y2 - 4 May 2008 through 7 May 2008
ER -