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

摘要

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