Please wait a minute...
浙江大学学报(工学版)
J4  2013, Vol. 47 Issue (1): 29-36    DOI: 10.3785/j.issn.1008-973X.2013.01.005
计算机技术﹑电信技术     
延迟变化紧密的多核心组播树快速构建算法
占志峰, 邢卫, 鲁东明
浙江大学 计算机科学与技术学院,浙江 杭州 310027
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
 全文: PDF  HTML
摘要：

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

百万册数字图书馆服务系统Ipv6升级资助项目（CNGI2008-112）
通讯作者: 邢卫，男，副教授.     E-mail: wxing@zju.edu.cn
作者简介: 占志峰（1979-），男，博士生，从事无线网及融合网数据传输研究. E-mail: zhanzf@zju.edu.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　

引用本文:

占志峰, 邢卫, 鲁东明. 延迟变化紧密的多核心组播树快速构建算法[J]. J4, 2013, 47(1): 29-36.

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.

链接本文:

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

［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] 宋广华, 夏莹杰, 郑耀, 毛小云. 基于多层Bayesian信任网的P2P负载均衡模型[J]. J4, 2010, 44(9): 1676-1680.
[2] 夏莹杰, 宋广华, 朱明哲, 等. 基于零知识交互式证明和Bayesian信誉网的小世界P2P模型[J]. J4, 2010, 44(1): 56-60.