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

计算机工程与科学

• 计算机网络与信息安全 • 上一篇下一篇

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

郑露露,武继刚,陈辉

（广东工业大学计算机学院,广东广州 510006）

收稿日期:2018-06-18 修回日期:2018-08-10 出版日期:2018-11-25 发布日期:2018-11-25
基金资助:
国家自然科学基金（61672171，61702115，61702114）；广东省自然科学基金（2018B030311007）；广东省科技研发计划（2017B030305003）；中国博士后科学基金（2017M622632）

A fast recovery algorithm for survivable

spanning trees in networks

ZHENG Lulu,WU Jigang,CHEN Hui

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%.
（School of Computer,Guangdong University of Technology,Guangzhou 510006,China）

Received:2018-06-18 Revised:2018-08-10 Online:2018-11-25 Published:2018-11-25

摘要/Abstract

摘要：

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

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

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

郑露露,武继刚,陈辉. 网络可存活生成树的快速恢复算法[J]. 计算机工程与科学.

ZHENG Lulu,WU Jigang,CHEN Hui.

A fast recovery algorithm for survivable

spanning trees in networks

[J]. Computer Engineering & Science.

[1]	袁梁勇, 齐星云, 吕方旭, 罗章, 黄恒, 张庚, 王文晨, 李萌, 赖明澈. 面向Duobinary信号的时钟恢复电路研究与设计[J]. 计算机工程与科学, 2025, 47(01): 27-34.
[2]	刘庆, 王和明, 吕方旭, 张庚, 吕栋斌. 面向高性能计算机光互连的低抖动Retimer电路[J]. 计算机工程与科学, 2024, 46(11): 1940-1948.
[3]	张晓均, 李兴鹏, 张经伟, 唐伟. 智慧医疗系统中可容错的多维度密文跨域聚合方案[J]. 计算机工程与科学, 2024, 46(08): 1403-1413.
[4]	徐辉, 朱烁, 孙皓洁, 马瑞君, 梁华国, 黄正峰. 一种基于C单元的三节点翻转自恢复锁存器[J]. 计算机工程与科学, 2024, 46(01): 37-45.
[5]	李腾, 程哲, 贾东立, 贾耀清. 基于角色管理的实用拜占庭容错共识算法[J]. 计算机工程与科学, 2022, 44(02): 237-243.
[6]	张玲. MEDA芯片菊花链的自动容错设计[J]. 计算机工程与科学, 2021, 43(07): 1192-1199.
[7]	孙雨浩, 陶洋, 胡昊. 基于判别低秩矩阵恢复和协同表示的遮挡人脸识别[J]. 计算机工程与科学, 2020, 42(12): 2199-2207.
[8]	冯峰, 周清雷, 李斌. 基于多核FPGA的HMAC-SHA1口令恢复[J]. 计算机工程与科学, 2020, 42(10高性能专刊): 1859-1868.
[9]	李斌, 周清雷, 斯雪明, 冯峰. 混合可重构的DES算核高效能口令恢复方案[J]. 计算机工程与科学, 2020, 42(10高性能专刊): 1887-1896.
[10]	陈虎, 韩建国. GPU上典型存储器难散列函数的优化[J]. 计算机工程与科学, 2020, 42(10高性能专刊): 1905-1912.
[11]	王茂秋, 张江, 张晶, . 基于斯坦纳树和泰森多边形的连通恢复算法[J]. 计算机工程与科学, 2020, 42(08): 1352-1358.
[12]	欧永东，谢小鹏. 基于改进Census变换的多特性立体匹配算法[J]. 计算机工程与科学, 2020, 42(06): 1030-1036.
[13]	王洁，康俊杰，周宽久. 基于FPGA的故障修复演化技术研究[J]. 计算机工程与科学, 2018, 40(12): 2120-2125.
[14]	黄洪涛1，武继刚1，郑露露1，缪裕青2. 面向无线内容分发网络的树形拓扑生成算法[J]. 计算机工程与科学, 2018, 40(12): 2133-2140.
[15]	齐平1,2,王福成1,王必晴1,梁昌勇2. 云计算环境下基于可靠性感知的任务调度算法[J]. 计算机工程与科学, 2018, 40(11): 1925-1935.

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

A fast recovery algorithm for survivable

spanning trees in networks

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 15

编辑推荐

Metrics

本文评价