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