Fast Recovery Algorithms For Survivable Spanning Tree In Network

With the rapid development of the Internet,the data transmission rate has exploded,and the link failure of network infrastructure definitely poses a great threat to the data transmission.The failure of links in the network is random and unpredictable.How to cope with network link failure has become one of the challenging problems.The survivable spanning connection(SSC)including several spanning trees have been extensively used to prevent link failure in existing works,and the spanning trees includes shared links and unshared links.When unshared link fails,the SSC can quickly use the backup spanning tree to restore data transmission to normal.However,the spanning trees in SSC all invalid when the shared link fails,and a new survivable connection must be regenerated at this time.This usually increases the recovery time and causes a large amount of data loss.Based on the existing SSC,the recovery problem of the spanning trees is studied when link fails,which is important for the reduction of the data loss.For the failure of unshared links and shared links,two fast recovery algorithms(USLMS and SLMS)are proposed to recover the invalid spanning trees.Different from the existing algorithms,this paper restore the invalid spanning trees by adjusting the link on the original spanning tree structure instead of discarding the failed spanning tree.For the unshared link,only one spanning tree invalid.At this time,the backup spanning tree is activated as the transmission path,and the failed spanning tree is adjusted and updated.First,the failure spanning tree is divided into two subtrees.Then,the USLMS algorithm searches the available links between the subtrees as the alternative link and adds the link with the minimum probability of failure into the invalid spanning tree in the original SSC,to generate a new SSC.For the shared link,all spanning trees in the survivable connection invalid,and the all invalid spanning trees are restored simultaneously.First,the SLMS algorithm searches the available links of each spanning tree,then analyze the relationship between all available link sets,and adds the link with the minimum probability of failure into the invalid spanning trees.Through the theoretical analysis and demonstration,the proposed algorithm can quickly restore the invalid spanning trees and form a new SSC.The experimental results show that the nearly optimal survivability of the network can be maintained by the proposed algorithms,while significantly reducing the recovery time and time complexity,compared with the existing method.The improvement of the proposed algorithm over the existing work is up to 34.42% in terms of recovery time,when the number of network nodes changes from 10 to 100.Meanwhile,the error in survivability is no more than 1%.