An efficient algorithm for bandwidth-delay constrained least cost multicast routing

Rana Forsati, Mehrdad Mahdavi, Abolfazl Torghy Haghighat, Azadeh Ghariniyat

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationIEEE Canadian Conference on Electrical and Computer Engineering, Proceedings, CCECE 2008
Pages1641-1645
Number of pages5
DOIs
StatePublished - Sep 22 2008
EventIEEE Canadian Conference on Electrical and Computer Engineering, CCECE 2008 - Niagara Falls, ON, Canada
Duration: May 4 2008May 7 2008

Publication series

NameCanadian Conference on Electrical and Computer Engineering
ISSN (Print)0840-7789

Other

OtherIEEE Canadian Conference on Electrical and Computer Engineering, CCECE 2008
Country/TerritoryCanada
CityNiagara Falls, ON
Period5/4/085/7/08

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'An efficient algorithm for bandwidth-delay constrained least cost multicast routing'. Together they form a unique fingerprint.

Cite this