基于度约束最小生成树的域间路由恢复算法  

A Failure Recovery Algorithm for Inter-Domain Routing System Based on Degree-Constrained Minimum Spanning Tree

作　　者：王禹 张连成[2,3] 张宏涛 郭毅[2,3] WANG Yu;ZHANG Lian-cheng;ZHANG Hong-tao;GUO Yi(School of Computer Science,Henan University of Engineering,Zhengzhou 451191,China;Network Cryptography Laboratory,State Key Laboratory of Mathematical Engineering and Advanced Computing,Zhengzhou 450002,China;School of Cyberspace Security,PLA Information Engineering University,Zhengzhou 450002,China;Network Management Center,Zhengzhou University,Zhengzhou 450001,China)

机构地区：[1]河南工程学院计算机学院,郑州451191 [2]数学工程与先进计算国家重点实验室网络密码研究室,郑州450002 [3]解放军信息工程大学网络空间安全学院,郑州450002 [4]郑州大学网络管理中心,郑州450001

出　　处：《北京邮电大学学报》2020年第4期113-119,共7页Journal of Beijing University of Posts and Telecommunications

基　　金：国家自然科学基金项目(61802115);河南省高等学校重点科研项目(18A520004,9A520008);河南省科技攻关计划项目(182102310925,192102310445,192102210283)。

摘　　要：低速拒绝服务攻击对于域间路由系统造成威胁,已有失效恢复算法未能有效解决恢复拓扑计算的时间复杂度高和节点聚合控制等问题,为此,提出一种基于度约束最小生成树的失效恢复算法.通过设计基础迁移子算法和复杂迁移子算法,在满足度约束的条件下根据遭袭路由系统生存拓扑构建新的恢复拓扑,并针对上述两类迁移子算法,分别提出关键点选择子算法,用于判定和计算迁移过程所需的关键节点.理论分析和仿真实验结果证明,该算法生成的恢复拓扑在有效控制节点度的同时,具有较优的性能.In view of the threat of low-rate denial of service attacks on inter-domain routing system,the existing failure recovery methods fail to solve problems including high time complexity and node aggregation control. A failure-recovery algorithm based on degree-constrained minimum spanning tree named degree-constrained minimum spanning tree based failure recovery( DR) is proposed. By designing the Fundamental Transfer sub-algorithm and the complex transfer sub-algorithm,a new recovery topology can be constructed according to the survival topology of the attacked routing system under the condition of given degree constraint. For the above two types of transfer sub-algorithms,two selection sub-algorithms are respectively advanced for the determination and calculation of key nodes. Theoretical analysis and simulation experiments verify that the recovery topology generated by DR has better performance while effectively controlling the node degree.

关 键 词：域间路由系统 失效恢复 度约束最小生成树 时间复杂度 节点聚合控制 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]