Delay and Delay-Variation Constrained Multicast Routing Algorithm Based on Core Selection

Abstract:

With the development of multimedia network, more and more real-time multimedia applications require a network capable of satisfying QoS constraints such as delay and delay-variation bound so that the messages reach each destination node at almost the same time within a certain specified time limit, and certain application also demand that different streams for each different destination node should reach with minimum cost under the constraints. Therefore, the delay and delay-variation constraint multicast routing problem is studied and a new strategy in core selection methods is proposed. The algorithm we propose guarantees that the delay from the source to any destination does not exceed a real-time constraint satisfying the delay-variation constraint under cost minimization. In addition, this core selection methods achieve a balance of optimizing cost and delay of the multicast tree. Simulation results show that the algorithm has low complexity and balances between the computational complexity and performance, it can also meet the requirements of real-time network communication.

• Periodical: Applied Mechanics and Materials (Volumes 373-375)
• Pages: 1182-1187
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.373-375.1182
• Online since: August 2013
• Authors: Yuan Chen Li, Wei Qun Liu
• Keywords: Core Selection, Multicast Routing Algorithm, Routing Optimization, Steiner Tree

References

[1] Rouskas G N, Baldine I. Multicast Routing with End-to-end Delay and Delay Variation Constraints[J]. IEEE Journal on Selected Areas in Communications, 1997, 15(3): 346-356.

DOI: 10.1109/49.564133

[2] D. W. Wall. Mechanisms for Broadcast and Selective Broadcast, PhD thesis, Stanford University, (1980).

[3] S. M Chung, C. H Youn. Core selection algorithm for multicastrouting under multiple QoS constraints, 2000, 36, 378–379.

DOI: 10.1049/el:20000315

[4] M. Kim, Y. C Bang, H. J. Lim, H. Choo. On efficient core selection for reducing multicast delay variation under delay constraints, IEICE Transactions on Communications, 2006, E89, 2385–2393.

DOI: 10.1093/ietcom/e89-b.9.2385

[5] Oliveira C. A. S, Pardalos P. M. A survey of combinatorial optimization problems in multicast routing[J]. Computers and Operations Research, 2005, 32: 1953-(1981).

DOI: 10.1016/j.cor.2003.12.007

[6] Pi-Rong Sheu, Shan-Tai Chen. A fast and efficient heuristic algorithmfor the delay- and delay variation-bounded multicast tree problem[J]. Computer Communications, 2002, 8(25): 825-833.

DOI: 10.1016/s0140-3664(01)00404-2

[7] Ahn S, Kim M, Choo H. Efficient Algorithm for Reducing Delay Variation on Delay-Bounded Multicast Trees in Heterogeneous Networks[C]. IEEE Communication Society, WCNC proceedings, 2008: 2741-2746.

DOI: 10.1109/wcnc.2008.480

[8] Sahoo S P, Kabat M R, Sahoo A K. Tabu Search Algorithm for Core Selection in Multicast Routing[C]. International Conference on Communication Systems and Network Technologies, 2011: 17-21.

DOI: 10.1109/csnt.2011.11

[9] A Heuristic Algorithm for Delay Delay-Variation Bounded Least Cost Multicast Routing [J]. IEEE 2nd International Advance Computing Conference, 2010: 261-266.

DOI: 10.1109/iadcc.2010.5423000

[10] L Kou, G Markowsky, L Berman. A fast algorithm for Steiner trees in graphs[J]. Acta Informatica, 1981, 15(2): 141-145.

DOI: 10.1007/bf00288961