A New Hybrid GRASP with the Pilot Method Forthe Delay-Constrained Multicast Routing Problem

Ying Xu; Xiong Fei  Zheng; Ren Fa  Li

doi:10.4028/www.scientific.net/AMR.756-759.3647

Paper Titles

Code-Switching Speech Detection Method by Combination of Language and Acoustic Information
p.3622

The Strong Convergence of a New Iterative Algorithm for Asymptotically Nonexpansive Mappings
p.3628

Algebraic Techniques in Linear Cryptanalysis
p.3634

An Evaluation Method of Combat Service Operation Performance for Surface-to-Air Missile Based on FNN
p.3640

A New Hybrid GRASP with the Pilot Method Forthe Delay-Constrained Multicast Routing Problem
p.3647

Imbalanced Data Detection Kernel Method in Closed Systems
p.3652

Parallel Outlier Detection in Dial-Back Fraud Calls
p.3659

Application of Two Unknown Quantities and Three Points Interpolation in the Atmospheric Transmittance of Infrared Radiation
p.3665

Retrieval Technology by Example during Product Development of Auto Parts
p.3669

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 756-759A New Hybrid GRASP with the Pilot Method Forthe...

A New Hybrid GRASP with the Pilot Method Forthe Delay-Constrained Multicast Routing Problem

Abstract:

Multicast routing problem is a well know optimization problem for transmitting real-time multimedia applications in telecommunication networks. As the underpinning mathematical model, the constrained minimum Steiner tree problem in graphs is a well-known NP-complete problem. In this paper we investigate a new hybrid GRASP (Greedy Randomized Adaptive Search Procedure) approach where a pilot method is applied to further enhance the search for the Delay-Constrained Least-Cost (DCLC) multicast routing problem. Experimental results demonstrate the efficiency of the hybrid GRASP algorithm and the contributions of the post-processing pilot method to better solutions in most cases. The proposed GRASP approach is a competitive approach in solving the DCLC multicast routing problem.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 756-759)

Pages:

3647-3651

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.756-759.3647

Citation:

Cite this paper

Online since:

September 2013

Authors:

Ying Xu, Xiong Fei Zheng, Ren Fa Li

Keywords:

Greedy Randomised Adaptive Search Procedure (GRASP), Multicast Routing, Pilot Method

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] H.F. Salama, D.S. Reeves, and Y. Viniotis, Evaluation of multicast routing algorithms for real-time communication on high-speed networks, IEEE Journal on Selected Areas in Communications, Vol. 15, No. 3, 1997, pp.332-345.

DOI: 10.1109/49.564132

Google Scholar

[2] C.K. Yeo, B.S. Lee, and M.H. Er, A survey of application level multicast techniques, Computer Communications, Vol. 27, No. 15, 2004, pp.1547-1568.

DOI: 10.1016/j.comcom.2004.04.003

Google Scholar

[3] X. Masip-Bruin, M. Yannuzzi, and J. Domingo-Pascual, A. Fonte, M. Curado, E. Monteiro, F. Kuipers, P. Van Mieghem, S. Avallone, G. Ventre, P. Aranda-Gutierrez, M. Hollick, R. Steinmetz, L. Iannone, K. Salamatian, Research challenges in QoS routing, Computer Communications, Vol. 29, No. 5, 2006, pp.563-581.

DOI: 10.1016/j.comcom.2005.06.008

Google Scholar

[4] X. Cheng, and D.Z. Du, (eds. ), Steiner Trees in Industry, Kluwer Academic Publishers, Dordrecht, Netherlands, (2001).

Google Scholar

[5] M.R. Garey, and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, New York, (1979).

Google Scholar

[6] L. Guo, and I. Matta, QDMR: An efficient QoS dependent multicast routing algorithm, Proc. of the 5th IEEE RealTime Technology and Applications Symposium, 1999, pp.213-222.

DOI: 10.1109/rttas.1999.777674

Google Scholar

[7] C. Diot, W. Dabbous, and J. Crowcroft, Multipoint communication: a survey of protocols, functions, and mechanisms, IEEE Journal on Selected Areas in Communications, Vol. 15, No. 3, 1997, pp.277-290.

DOI: 10.1109/49.564128

Google Scholar

[8] C.A.S. Oliveira, and P.M. Pardalos, A survey of combinatorial optimization problems in multicast routing, Computers & Operations Research, Vol. 32, No. 8, 2005, p.1953-(1981).

DOI: 10.1016/j.cor.2003.12.007

Google Scholar

[9] N. Skorin-Kapov, and M. Kos, A GRASP heuristic for the delay-constrained multicast routing problem, Telecommunication Systems. Vol. 32, No. 1, 2006, pp.55-69.

DOI: 10.1007/s11235-006-8202-2

Google Scholar