Abstract:

How to cope with the failures of network links is one of the most challenging problems. Existing research usually adopts a survivable spanning connection (SSC) with two spanning trees to avoid link failures. Due to the rapid growth of network data transmission rate, the spanning trees in SSC all become invalid when the shared links of a pair of two spanning tree fail. We propose a fast recovery algorithm for survivable spanning trees in case of shared link failures in SSC. The algorithm searches the replaceable link set of invalid links and adds the links with least probability of failure into the spanning trees in the original SSC, thus generating a new SSC. Experimental results show that the proposed algorithm can keep the close-to-optimal survivability of the network while significantly reducing recovery time and time complexity. The recovery time is optimized by up to 34.42% when the number of network nodes changes from 10 to 100, and the error in survivability does not exceed 1%.

Key words: survivability, recovery, spanning tree, failure link, fault tolerance