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

摘要：

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

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

所属期刊栏目：40

分类号：TP393(计算技术、计算机技术)

资助基金：国家自然科学基金61672171,61702115,61702114;广东省自然科学基金2018B030311007;广东省科技研发计划2017B030305003;中国博士后科学基金2017M622632

在线出版日期：2018-12-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：1967-1973