Please wait a minute...
浙江大学学报(工学版)
J4  2013, Vol. 47 Issue (1): 29-36    DOI: 10.3785/j.issn.1008-973X.2013.01.005
    
Tightest delay-variation multi-cores based multicast tree
fast constructing algorithm
ZHAN Zhi-feng, XING Wei, LU Dong-ming
College of Computer Science and Technology,Zhejiang University, Hangzhou 310027,China
Download:   PDF(0KB) HTML
Export: BibTeX | EndNote (RIS)      

Abstract  

In order to solve the problems such as bad practicability, high complexity and costly reconstruction in the constructing of delay and delay-variation bounded multicast tree,  a fast multicast tree constructing algorithm was presented, which is based on the novel plain structure of multi-cores tree and using the sliding delay-variation window for multiple cores selection mechanism. The algorithm provides large solution seeking space for initial multicast tree and the tightest delay-variation bounded constraint for the result tree. The practicability for the algorithm is good, and the result tree has good performance of maintainability and small cost of local reconstruction. In theory, the time complexity for the algorithm is equal to delay and delay variation constraint algorithm (DDVCA), which has the best performance in time complexity. In simulated experiments to construct the largescale multicast tree, the execution time of our algorithm is at most 60% shorter than DDVCA under the same constraints on delay and delay-variation bounds. With more shoter delay-variation constraint, comparing with Chains algorithm that has the tightest delay-variation constraint so far as I know, our algorithm can find result multicast tree with much more probability. Extensive experiments show that the tightest delay-variation constaint can be obtained by the algorithm．

Published: 01 January 2013
CLC:  TP 393.03  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Cite this article:

ZHAN Zhi-feng, XING Wei, LU Dong-ming. Tightest delay-variation multi-cores based multicast tree
fast constructing algorithm. J4, 2013, 47(1): 29-36.

URL:

http://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2013.01.005     OR     http://www.zjujournals.com/eng/Y2013/V47/I1/29


延迟变化紧密的多核心组播树快速构建算法

为了解决在具有延迟及延迟变化约束组播树的构建问题中存在的算法实用性差、复杂度高和重构代价大等问题,提出基于扁平多核心树结构的、采用基于延迟变化过滤窗口的多核心节点选取机制的组播树快速构建算法.该算法极大地拓展了初始组播树的寻解空间,且能够找到具有最严格的延迟变化约束的目标树.该算法实用性强,目标树的可维护性好且局部恢复代价小.理论上,该算法在时间复杂度上与该项性能最好的延迟及延迟变化约束算法(DDVCA)相同.模拟实验中,在相同的延迟及延迟变化约束条件下构建大规模组播树,该算法相比延迟及延迟变化约束算法最多能够节省60%的执行时间.模拟实验还表明,随着延迟变化约束越来越小,与延迟变化约束性能最好的链式算法相比,该算法能够以更大的概率找到合适的组播树；该算法能够获得最紧密的延迟变化约束性能.

［1］ RAMALHO M. Intra-and inter-domain multicast routing protocols: a survey and taxonomy ［J］. Communications Surveys and Tutorials, IEEE, 2009, 3(1): 225．
［2］ KOBAYASHI M, NAKAYAMA H, ANSARI N, et al. Robust and efficient stream delivery for application layer multicasting in heterogeneous networks ［J］.  IEEE Transactions on Multimedia, 2009, 11(1): 166-176．
［3］ SHEU P R, CHEN S T. A fast and efficient heuristic algorithm for the delay and delay variation-bounded multicast tree problem ［J］. Computer Communications, 2002, 25(8): 825-833．
［4］ BANIK S M, RADHAKRISHNAN S, SEKHARAN C N. Multicast routing with delay and delay variation constraints for collaborative applications on overlay networks ［J］. IEEE Transactions on Parallel and Distributed Systems, 2007, 18(3): 421-431．
［5］ 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．
［6］ WANG F, XIONG Y, LIU J. Mtreebone: A collaborative treemesh overlay network for multicast video streaming ［J］. IEEE Transactions on Parallel and Distributed Systems, 2010, 21(3): 379-392．
［7］ MOUSSAOUI O, KSENTINI A, NAMI M, et al. Multicast tree construction with qos guaranties. management of multimedia networks and services ［M］. Heidelberg: Springer, 2005: 96-108．
［8］ KAPOOR S, RAGHAVAN S. Improved multicast routing with delay and delay variation constraints ［C］∥ Global Telecommunications Conference, 2000. GLOBECOM’00.  San Francisco: IEEE, 2000: 476-480．
［9］ KOBAYASHI M, NAKAYAMA H, ANSARI N, et al. Reliable application layer multicast over combined wired and wireless networks ［J］. IEEE Transactions on Multimedia, 2009, 11(8): 1466-1477．
［10］ TAMMA B R, BADAM A, MURTHY C S R, et al. K-tree: a multiple tree video multicast protocol for ad hoc wireless networks ［J］. Computer Networks, 2010, 54(11): 1864-1884．
［11］ ZENG G, WANG B, DING Y, et al. Efficient multicast algorithms for multichannel wireless mesh networks ［J］. IEEE Transactions on Parallel and Distributed Systems, 2010, 21(1): 86-99．
［12］ LI J, WANG Y, XUE M, et al. A short delay degree-constrained hierarchical application layer multicast protocol ［C］∥ International Conference on Web Information Systems and Mining. Shanghai: IEEE, 2009: 674-681．
［13］ FEI Z, YANG M. A proactive tree recovery mechanism for resilient overlay multicast ［J］. IEEE/ACM Transactions on Networking (TON), 2007, 15(1): 173-186．
［14］ KARAMAN A, HASSANEIN H. Core-selection algorithms in multicast routing-comparative and complexity analysis ［J］. Computer Communications, 2006, 29(8): 998-1014．
［15］ CORMEN T H, LEISERSON C E, RIVEST R L, et al. Introduction to algorithms ［M］. 2nd ed. Cambridge: MIT, 2002．
［16］ Boost. \
[2011-10-20\]. http:∥www.boost.org/.
［17］ STL. \
[2011-10-20\]. http:∥www.sgi.comtechstl/index.html.
［18］ GTITM. \
[2011-10-20\]. http:∥www.cc.gatech.edu/projects/gtitm/.
[1] SONG An-Hua, JIA Ying-Jie, ZHENG Yao, MAO Xiao-Yun. P2P loadbalance model based on multi-layer Bayesian trust network[J]. J4, 2010, 44(9): 1676-1680.
[2] JIA Ying-Jie, SONG An-Hua, SHU Meng-Zhe, et al. Trusted small world P2P model based on zero knowledge interactive proof and Bayesian trust network[J]. J4, 2010, 44(1): 56-60.