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

关键词：存活度 恢复 生成树 链接失效 容错 

单位：广东工业大学计算机学院; 广东广州510006