网络可存活生成树的快速恢复算法

如何应对网络链接失效是具有挑战性的问题之一，通常采用包含两棵生成树的可存活连接来预防链接失效。由于网络数据传输速率的高速增长，当两棵生成树的共享链接失效时，可存活连接中的生成树将全部失效。针对可存活连接中共享链接的失效提出了一种快速恢复算法，该算法通过搜索失效链接的可替换链接集，将失效概率最小的链接加入原可存活连接中的生成树，生成新的可存活连接。实验结果表明，该算法能够在显著降低恢复时间和时间复杂度的情形下，同时保证可存活连接的存活度接近当前网络的最优存活度。当网络节点数在10～100变化时，提出的算法比现有算法在恢复时间上的平均优化高达34.42%，同时在存活度上的误差不超过1%。

A fast recovery algorithm for survivable spanning trees in networks

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%.