高级检索
    夏怒, 李伟, 陆悠, 蒋健, 单冯, 罗军舟. 可保障数据无中断传输的冗余树算法研究[J]. 计算机研究与发展, 2016, 53(9): 2016-2029. DOI: 10.7544/issn1000-1239.2016.20150380
    引用本文: 夏怒, 李伟, 陆悠, 蒋健, 单冯, 罗军舟. 可保障数据无中断传输的冗余树算法研究[J]. 计算机研究与发展, 2016, 53(9): 2016-2029. DOI: 10.7544/issn1000-1239.2016.20150380
    Xia Nu, Li Wei, Lu You, Jiang Jian, Shan Feng, Luo Junzhou. The Redundant Tree Algorithm for Uninterrupted Data Delivery[J]. Journal of Computer Research and Development, 2016, 53(9): 2016-2029. DOI: 10.7544/issn1000-1239.2016.20150380
    Citation: Xia Nu, Li Wei, Lu You, Jiang Jian, Shan Feng, Luo Junzhou. The Redundant Tree Algorithm for Uninterrupted Data Delivery[J]. Journal of Computer Research and Development, 2016, 53(9): 2016-2029. DOI: 10.7544/issn1000-1239.2016.20150380

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

    The Redundant Tree Algorithm for Uninterrupted Data Delivery

    • 摘要: 随着大数据应用的发展,保障数据无中断传输的需求日益增强.针对单点或单链路失效的情况,现有的保障数据无中断传输方法存在主/备份路径的数据传输性能较低、抵御多节点/边失效能力不强等问题.为解决以上问题,提出一种可保障数据无中断传输的按边序选环的冗余树算法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.

       

    /

    返回文章
    返回