A Delay-Constrained Multicast Routing Balanced-Optimization Algorithm of Link-Sharing

Abstract:

In multimedia network, Quality of service (QoS) provisioning generally assumes more than one QoS measure which implies that QoS routing can be categorized as an instance of routing subject to multiple constraints: delay, cost, bandwidth, etc. We study the problem of constructing multicast trees to meet the QoS requirements of real-time applications where it is necessary to provide bounded delays among the source and all destinations while keeping overall cost of the multicast tree low. So the cost and computational complexity are analyzed as constructing delay-constrained multicast tree. So as to optimize shortest paths, a new algorithm of ORLSB(optimal routing algorithm for link-sharing balance) is proposed.The link selection function of the algorithm not only considers the priority of the destination nodes, but also takes into account the priority of the low delay path based on local information. Because the multicast tree has fewer possible path, the algorithm reduces the probability of creating multicast tree through the minimum delay path and improves the sharing paths. Simulation results show that this algorithm has balanced cost, delay and computational complexity, and has better overall performance.

• Periodical: Applied Mechanics and Materials (Volumes 152-154)
• Pages: 1834-1839
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.152-154.1834
• Online since: January 2012
• Authors: Wei Qun Liu, Xiang Kui Chen
• Keywords: Link-Sharing, Local Information, Minimum Steiner Tree, Multicast Communication, QoS, Selection Function

References

[1] AISSA M, MNAOUER A B. A new delay-constrained algorithm for multicast routing tree construction [ J]. International Journal of Communication Systems, 2004, 17(10): 985-1000.

DOI: 10.1002/dac.685

[2] KOMPELLA V P, PASQUAL J C, POLYZOS G C. Multicast routing for multimedia communication [J]. IEEE/ACM Trans on Networking , 1993, 1(3): 286-292.

DOI: 10.1109/90.234851

[3] 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

[4] ZHU Q, PARSA M C, GARCIA-LUNA-ACEVES J J. A source-based algorithm for delay-constrained minimum-cost multicasting[C]. Proceedings of IEEE INFOCOM'95, 1995: 377-385.

DOI: 10.1109/infcom.1995.515898

[5] SHAIKH A, SHIN K G. Destination-driven routing for low-cost multicast[J]. IEEE Journal on Selected Areas in Communications, 1997, 15(3): 373-381.

DOI: 10.1109/49.564135

[6] L GUO, I MATTA. QMDR: An efficient QoS dependent multicast routing Algorithm[C]. Proc of the 5th IEEE Real-Time Technology and Applications Symposium, 1999: 213-222.

DOI: 10.1109/rttas.1999.777674

[7] WANG Xin-mei, ZHU Min. A Delay-Constrained Multicast Routing Algorithm Based on Edge Selection Function [J]. Journal of Shanghai University(Natural Science Edition), 2008, 14(2): 116-120.

[8] LI Yuan-chen, LIU Wei-qun. Delay-constrained multicast routing algorithm based on shared edges [J]. Journal of Computer Applications, 2009, 29(11): 2901-2903.

DOI: 10.3724/sp.j.1087.2009.02901

[9] WANG Heng; SUN Ya-min. A Delay-constrained Multicast Routing Algorithm Based on Link Optimizing[J]. Journal of Nanjing University of Science and Technology, 2004, 1(28): 80-84.