The Redundant Tree Algorithm for Uninterrupted Data Delivery

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.