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

doi:10.13190/j.jbupt.2019-198

北京邮电大学学报 ›› 2020, Vol. 43 ›› Issue (4): 113-119.doi: 10.13190/j.jbupt.2019-198

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

王禹^1,2,3, 张连成^2,3, 张宏涛^2,3,4, 郭毅^2,3

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

收稿日期:2019-08-28 发布日期:2020-08-15
作者简介:王禹(1984-),男,讲师,E-mail:stonchor@163.com.
基金资助:
国家自然科学基金项目（61802115）；河南省高等学校重点科研项目（18A520004，9A520008）；河南省科技攻关计划项目（182102310925，192102310445，192102210283）

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

WANG Yu^1,2,3, ZHANG Lian-cheng^2,3, ZHANG Hong-tao^2,3,4, GUO Yi^2,3

1. School of Computer Science, Henan University of Engineering, Zhengzhou 451191, China;
2. Network Cryptography Laboratory, State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450002, China;
3. School of Cyberspace Security, PLA Information Engineering University, Zhengzhou 450002, China;
4. Network Management Center, Zhengzhou University, Zhengzhou 450001, China

Received:2019-08-28 Published:2020-08-15

摘要/Abstract

摘要： 低速拒绝服务攻击对于域间路由系统造成威胁，已有失效恢复算法未能有效解决恢复拓扑计算的时间复杂度高和节点聚合控制等问题，为此，提出一种基于度约束最小生成树的失效恢复算法.通过设计基础迁移子算法和复杂迁移子算法，在满足度约束的条件下根据遭袭路由系统生存拓扑构建新的恢复拓扑，并针对上述两类迁移子算法，分别提出关键点选择子算法，用于判定和计算迁移过程所需的关键节点.理论分析和仿真实验结果证明，该算法生成的恢复拓扑在有效控制节点度的同时，具有较优的性能.

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

Abstract: 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.

Key words: inter-domain routing system, failure recovery, degree-constrained minimum spanning tree, time complexity, control of node aggregation

中图分类号:

TP393

王禹, 张连成, 张宏涛, 郭毅. 基于度约束最小生成树的域间路由恢复算法[J]. 北京邮电大学学报, 2020, 43(4): 113-119.

WANG Yu, ZHANG Lian-cheng, ZHANG Hong-tao, GUO Yi. A Failure Recovery Algorithm for Inter-Domain Routing System Based on Degree-Constrained Minimum Spanning Tree[J]. Journal of Beijing University of Posts and Telecommunications, 2020, 43(4): 113-119.

参考文献

[1] Sermpezis P, Kotronis V, Dainotti A, et al. A survey among network operators on BGP prefix hijacking[J]. ACM SIGCOMM Computer Communication Review, 2018, 48(1):64-69.
[2] Florian S, Franziska L, Robert B, et al. BGP communities:even more worms in the routing can[C]//Internet Measurement Conference. Boston:ACM Press, 2018:279-292.
[3] Brivaldo J, Ronaldo A F, Italo C, et al. High-fidelity interdomain routing experiments[C]//ACM SIGCOMM Conference on Posters and Demos. Budapest:ACM Press, 2018:36-38.
[4] Li Heshuai, Zhu Junhu, Wang Qingxian, et al. LAAEM:a method to enhance LDoS attack[J]. IEEE Communications Letters, 2016, 20(4):708-711.
[5] Motivala M, Elmore M, Feamster N, et al. Path splicing[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(4):27-38.
[6] 孙子文, 张炎棋, 徐宜敏. 一种采用混合抗干扰方法的路由恢复机制[J]. 系统仿真学报, 2019, 32(5):874-884. Sun Ziwen, Zhang Yanqi, Xu Yimin. A route recovery mechanism using hybrid anti-interference method[J]. Journal of System Simulation, 2019, 32(5):874-884.
[7] Gopalan A, Ramasubramanian S. IP fast rerouting and disjoint multipath routing with three edge-independent spanning trees[J]. IEEE/ACM Transactions on Networking, 2016, 24(3):1336-1349.
[8] 陈文龙, 赵一荣, 肖融, 等. 基于虚拟拓扑的多级可信传输体系及路由计算[J]. 计算机研究与发展, 2018, 55(4):729-737. Chen Wenlong, Zhao Yirong, Xiao Rong, et al. Packets transmission with multiple levels of credibility and routing calculation based on virtual topologies[J]. Journal of Computer Research and Development, 2018, 55(4):729-737.
[9] CAIDA. CAIDA's internet topology data comparison[EB/OL]. 2012(2012-05-15)[2019-08-26]. http://www.caida.org/research/topology/topo_comparison.
[10] Raidl G R. Edge sets:an effective evolutionary coding of spanning trees[J]. IEEE Transactions on Evolutionary Computation, 2003, 7(3):225-239.
[11] Thang N B, Xianghua D, Catherine M Z. An improved ant-based algorithm for the degree-constrained minimum spanning tree problem[J]. IEEE Transactions on Evolutionary Computation, 2012, 16(2):266-278.
[12] Singh K, Sundar S. A hybrid genetic algorithm for the degree-constrained minimum spanning tree problem[J]. Soft Computing, 2019, 24, 2169-2186.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价