Exact algorithm for delay-constrained capacitated minimum spanning tree network
作者： Y.J. Lee , M. Atiquzzaman
关键词:
摘要: The delay-constrained capacitated minimum spanning tree (DC-CMST) problem of finding several broadcast trees from a source node is discussed. While the traditional CMST deals with only traffic capacity constraint served by port node, and (DCMST) considers maximum end–end delay constraint, DC-CMST both mean network constraints. consists set cost to link end-nodes satisfying requirements at required network. In problem, objective function minimise total cost. A dynamic programming-based three-phase algorithm that solves proposed. first phase, generates feasible solutions satisfy constraint. It finds CMSTs in second allocates optimal capacities third phase. Performance evaluation shows proposed has good efficiency for any less than 30 nodes light traffic. can be applied regardless its configuration, used topological design local networks efficient routing algorithms capable constructing least trees.
aip.org
sci-hub.se 参考文章(18)
Shakil Akhtar, Youlu Zheng, Networks for Computer Scientists and Engineers ,(2001)
Yong-Jin Lee, M. Atiquzzaman, Least cost multicast spanning tree algorithm for local computer network international conference on networking. pp. 268- 275 ,(2005) , 10.1007/11534310_30
Wang Zhengying, Shi Bingxin, Zou Ling, A Delay-Constrained Least-Cost Multicast Routing Heuristic for Dynamic Multicast Groups Electronic Commerce Research. ,vol. 2, pp. 323- 335 ,(2002) , 10.1023/A:1020503130270
Yuri Breitbart, Minos Garofalakis, Cliff Martin, Rajeev Rastogi, S Seshadri, Avi Silberschatz, None, Topology discovery in heterogeneous IP networks international conference on computer communications. ,vol. 1, pp. 265- 274 ,(2000) , 10.1109/INFCOM.2000.832196
Zhang Kun, Wang Heng, Liu Feng-Yu, Distributed multicast routing for delay and delay variation-bounded Steiner tree using simulated annealing Computer Communications. ,vol. 28, pp. 1356- 1370 ,(2005) , 10.1016/J.COMCOM.2004.12.003
B. Donnet, P. Raoult, T. Friedman, M. Crovella, Deployment of an Algorithm for Large-Scale Topology Discovery IEEE Journal on Selected Areas in Communications. ,vol. 24, pp. 2210- 2220 ,(2006) , 10.1109/JSAC.2006.884019
Zhengquan Xu, Lin Chen, An effective algorithm for delay-constrained dynamic multicasting Knowledge Based Systems. ,vol. 19, pp. 172- 179 ,(2006) , 10.1016/J.KNOSYS.2005.10.009
Sheng-Yuan Tseng, Yueh-Min Huang, Chang-Chun Lin, Genetic algorithm for delay- and degree-constrained multimedia broadcasting on overlay networks Computer Communications. ,vol. 29, pp. 3625- 3632 ,(2006) , 10.1016/J.COMCOM.2006.06.003
Yong-Jin Lee, M. Atiquzzaman, Least cost heuristic for the delay-constrained capacitated minimum spanning tree problem Computer Communications. ,vol. 28, pp. 1371- 1379 ,(2005) , 10.1016/J.COMCOM.2005.01.001
C. Mala, S. Selvakumar, Construction of an optimal multicast tree for group communication in a cellular network using genetic algorithm Computer Communications. ,vol. 29, pp. 3306- 3312 ,(2006) , 10.1016/J.COMCOM.2006.05.011