ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2016, Vol. 53 ›› Issue (9): 2016-2029.doi: 10.7544/issn1000-1239.2016.20150380

• 网络技术 • 上一篇    下一篇

可保障数据无中断传输的冗余树算法研究

夏怒,李伟,陆悠,蒋健,单冯,罗军舟   

  1. (东南大学计算机科学与工程学院 南京 211189) (xia_nu@seu.edu.cn)
  • 出版日期: 2016-09-01
  • 基金资助: 
    国家自然科学基金项目(61320106007);国家“八六三”高技术研究发展计划基金项目(2013AA013503);江苏省未来网络创新研究院未来网络前瞻性研究项目(BY2013095-2-07);教育部计算机网络与信息集成重点实验室(东南大学)基金项目(93K-9);江苏省网络与信息安全重点实验室基金项目(BM2003201);无线通信技术协同创新中心资助项目;软件新技术与产业化协同创新中心部分资助项目;住建部科研项目(2015-K6-012)

The Redundant Tree Algorithm for Uninterrupted Data Delivery

Xia Nu, Li Wei, Lu You, Jiang Jian, Shan Feng, Luo Junzhou   

  1. (School of Computer Science & Engineering, Southeast University, Nanjing 211189)
  • Online: 2016-09-01

摘要: 随着大数据应用的发展,保障数据无中断传输的需求日益增强.针对单点或单链路失效的情况,现有的保障数据无中断传输方法存在主/备份路径的数据传输性能较低、抵御多节点/边失效能力不强等问题.为解决以上问题,提出一种可保障数据无中断传输的按边序选环的冗余树算法CSES(circle selecting by edge sorting based redundant tree algorithm for uninterrupted data delivery),可用于构建数据传输性能优化的主/备份路径,并使数据传输具有较强的抵御多节点/边失效的能力. 该算法首先根据网络拓扑构建以数据源为根节点的最小传输树,以最小化主传输路径上的转发跳数;其次,为了减少备份路径的转发跳数并提高数据传输抵御多节点/边失效的能力,对拓扑中不在最小传输树上的边进行排序,将树上根节点到边上2个端点的路径上节点数量之和较小的边排在前列. 随后按序将边添加到最小传输树上以构建冗余环,并基于冗余环生成冗余枝添加到最小传输树上,最终形成以数据源为根节点的冗余树.实验结果表明,相比于其他冗余树算法,基于CSES算法构建的冗余树所生成的主/备份路径的转发跳数更少且抵御多节点/边失效的能力更强.

关键词: 数据无中断传输, 最小传输树, 边排序, 冗余环, 冗余树

Abstract: With the development of the big data applications, the requirement for guaranteeing un-interrupted data delivery is growing gradually. To address the problem of single node/link failure, researchers had conducted lots of work. However, current methods for guaranteeing uninterrupted data delivery face the deficiencies of low performance of the primary/secondary delivery paths and the low resistant ability to the multiple nodes/links failure. In order to solve the above problems, a circle selecting by edge sorting based redundant tree algorithm for uninterrupted data delivery CSES is presented. At first, a minimal delivery tree with the data source as the root node is built in this algorithm, on which the routing hop count of the primary paths is the smallest. Secondly, in order to reduce the hop count of the secondary paths and to enhance the resistant ability of the multiple nodes/edges failure, the edges in network topology but not included in the tree are sorted based on the sum of the nodes on the paths between the root node and the two nodes of the edge. Then, the edges are added to the minimal tree to form the redundant circles and the redundant branches of the redundant circles are added to the minimal tree. Finally, a redundant tree rooted by the data source is built. The experimental results show that, compared with the other redundant tree algorithms, the hop count of the primary/secondary paths on the redundant tree built by CSES algorithm is smaller and the resistant ability of multiple nodes/edges failure of CSES algorithm is better.

Key words: the uninterrupted data delivery, the minimal delivery tree, edge sorting, the redundant circle, the redundant tree

中图分类号: