近年来，域间路由系统面临的安全防护压力逐步加大^[1-3]，边界网关协议低速拒绝服务(BGP-LDoS，border gateway protocol-low-rate denial of service)攻击的攻击威胁与复杂程度不断攀升^[4]. Schuchar和Kan的实验结果均证明，BGP-LDoS攻击能够导致域间路由系统局部乃至整体失效.伴随物联网的发展，以大规模僵尸网络为基础攻击条件的BGP-LDoS将给域间路由系统带来更为深远的影响.

域间路由系统失效恢复，旨在利用多种路由恢复技术保障网络遭袭后生存节点的通信.按照失效自治域和域间链路的数量，可将已有路由失效恢复算法划分为基于单链/单域失效的路由恢复和基于多链/多域失效的路由恢复.前者以路径拼接^[5]和混合抗干扰方法^[6]为代表，难以应对BGP-LDoS攻击造成的多点无关联区域失效场景.后者指无邻接关系的多个自治域区域近乎同时并发呈现通信中断态势下，针对尚存活自治域实施报文转发路径的动态切换，以IP快速重路由^[7]和多级可信传输机制(CETML，credible transmission with multiple levels)^[8]为代表.此类算法在预计算备份子图生成方面存在时间复杂度较高的问题，且BGP-LDoS攻击以高度聚合的中心节点为攻击目标，已有CETML等算法未考虑对生成子图中节点度的控制，因此在面对BGP-LDoS攻击时其生成的备份子图大都具有高中心度节点特性，导致其二次抗毁性较差.

综上，借鉴中心化网络控制的设计理念，通过定义BGP-LDoS袭击域间路由系统后生存路由的规划，提出一种基于度约束最小生成树的路由失效恢复算法(DR，degree-constrained minimum spanning tree based failure recovery).笔者的主要贡献为：①基于DR算法实现的域间路由失效恢复方案，在产生最小生成树，即路由系统恢复拓扑的过程中能够有效控制节点的聚合，避免生成具有过高度数节点；②针对已有多链/多域恢复算法在备份子图生成方面存在时间耗费较高的问题，DR算法能够有效降低恢复路由的生成时长.

1 域间路由系统路由失效恢复

针对自治域(AS，autonomous system)和域间路由系统拓扑开展研究.应用互联网数据分析中心(CAIDA，center for applied internet data analysis)^[9]针对来自多个数据源的AS级拓扑特性的统计表明，平均度值的范围基本落于[4, 6]，数据源中的最大度值范围为[2 607，4 386].由CAIDA基于ARK(Archipelago)和基于traceroute的计算节点度值的统计可知，度值大于10的节点概率均为0.09左右，大于1 000的节点概率约为0.005，表明大多数节点的度值小于10.

1.1 度约束最小生成树

度约束最小生成树(DCMST，degree-constrained minimum spanning tree)，即如果针对最小生成树中各顶点的度数加上一定的数目限制，则满足条件的最小生成树记为度约束最小生成树.对于连通图G=(V, E)，其节点集合V={v₁, v₂, …, v_n}，节点个数为|V|；边的集合E={e₁, e₂, …, e_k}，边的个数为k；每条边对应的权值为w_ij；假定T表示G中所有满足度约束的生成树集合.

1.2 生成树编码

针对域间路由系统中面对的BGP-LDoS攻击，提出一种节点表示法(NR，node representation)，便于图中节点编码.对于一个简单无向图G=(V, E)，存在一个生成森林F=(V, E_F)是G的无环子图，F中的一棵树T=(V_T, E_T)是F中的一个连接部分，有V_T⊆V.对于一个图G及其中一棵树T，G^T=(V_G^T, E_G^T)是由节点集合V_T生成的一个子图，即E_G^T包含的所有边(x, y)∈E，均满足x∈V_T和y∈V_T.

对于一棵树T，根为Root，定义节点n的进深为从n到Root的路径长度，记为p(n). N_G(n)表示G中毗邻节点n的节点集合. G中一个节点的度表示为d_G(x)，T中一个节点的度表示为d_T(x). G中一棵树T的度记为d_G(T)，是指对于G的边集E，射入属于V_T集合节点的边的总数.与之类似，T中边的个数为d_T(T)=|V_T|-1.

一棵树T的NR为一个有序列表，其中每个NR涵盖4个元素(n，I，p，d)：分别表示节点、索引、节点进深和节点度值.对于一个节点n，I(n)表示其索引值，p(n)和d_G(n)分别表示其进深和度值.对于T，考虑到深度优先搜索对于节点的顺序特性，基于深度优先法则实施NR编码时，搜寻到一个未访问过的节点，则可将该节点以及对应的进深、度值加入NR编码序列.

一棵生成树F的NR编码，记为森林表示(FoR，forest representation)，是F中每棵树T的NR合并.由于一片森林包含多棵树，则可用一个对偶(h_T，d_T)表示一棵树，前者表示指向树T的指针，后者表示该树的度值.

1.3 DR算法建立

1) 对于代表多个自治域组成的域间路由系统，其对应原始图G.在应对路由失效而生成DCMST时，由于域间路由节点在不断迁移和变化，因此通过创建并逐步完善编码矩阵的方式记录该过程.

子算法1  节点迁移编码TransferNodesEncode()

输入：图G(代表多个自治域组成的域间路由系统). 输出：节点的迁移编码矩阵M_N.

① 对于G中一棵树F_i中的某节点n，创建其对应的组数A_n=[i, H_i, I(n)_i]，i表示该节点所属树的序号，H_i为指向树F_i对应NR编码的指针，最后的I(n)_i为NR中n对应的索引值；②假设F₁是来自G的首个森林，在F₁的基础上，随着节点或子树的裁剪和迁移，不断生成的森林序列记为L=[F₁，F₂，…，F_i]；③若节点n所在的一棵子树SubTr，从树F_j迁移至树F_k，则节点n将被重新定位，该节点的迁移编码矩阵记为M_n=[A₁^T, …, A_j^T, A_k^T].

2) DR算法通过定义FundamentalTransfer(FT)和ComplexTransfer(CT)以产生新的生成森林，即从已有生成森林F对应的森林表示FoR，产出新生成森林F′的FoR. FT和CT操作的目标是从森林中的T_origin(一组树)里的子树迁移至另一棵树T_dst.

子算法2  基础迁移FundamentalTransfer()，FTFT针对BGP-LDoS攻击后，导致域间路由系统中某一关键节点失效的典型场景，针对该问题构建新的森林，并有效满足度约束值.

输入：森林F的FoR序列中树T_origin和T_dst的索引；被迁移子树T_origin中的根r，此时也称之为修剪节点；新树T_dst中的节点t，t满足在图G中与r相邻；度约束值c. 输出：新生成森林F′的FoR.

① 寻找T_origin中修剪节点r所属子树，其对应的索引范围是[I(r)，I(m)]，该范围涵盖了节点r及其后继节点m等，且满足p(r)值小于后继节点.考虑到I(r)值已知，通过顺序搜索可发现后继节点的I(m)；②临时创建一个中间树T_mid，用于存放迁移过程中的节点及子树；③将T_origin中索引范围[I(r)，I(m)]内的NR编码放入临时T_mid，按照p(n)-p(r)+p(t)+1计算T_mid每个n的I(n)；④创建一个序列T′_dst，包含T_dst和T_mid所有节点.通过生成一棵新树，将以r为根的子树迁移至T′_dst.仅当满足d(t)＜c+1时，将T_mid插入T′_dst的[I(t)+1]索引处，之后修正p(t)=p(t)+1；若不满足则跳转到步骤④，对t之后的下一节点进行判断；如果t已是T_dst中最后节点，则表明c过小，FT结束；⑤创建序列T′_origin，包含排除T_mid所含节点以外T_origin中的所有节点，之后修正T_origin中d(r)=d(r)-1；⑥复制F对应的NR，生成一个新的F′.将指向F′中新旧两棵树的指针分别记为h_T′_origin和h_T′_dst；⑦计算d_G(T′_origin)和d_G(T′_dst)，并存储于F′；⑧对矩阵M_N中T′_origin和T′_dst的每个节点n修正.

子算法3  复杂迁移ComplexTransfer()，CT

针对域间路由系统在遭受BGP-LDoS攻击后，导致毗邻的多个自治域节点失效场景，设计CT子算法生成度约束最小生成树，予以实施路由恢复.

输入：森林F的FoR序列中树T_origin和T_dst的索引；被迁移树T_origin中的根r；修剪节点f；新树T_dst中的节点t，t满足在图G中与r相邻；度约束值c. 输出：新生成森林F′的FoR.

① 寻找T_origin中根节点r所属子树，其对应索引范围[I(r)，I(m)]，该范围涵盖节点r及其后继节点m等，且满足p(r)值小于后继节点；②临时创建2个中间树T_mid1和T_mid2，用于存放迁移过程中的节点及子树；③将T_origin中索引范围[I(r)，I(m)]内的NR编码，放入临时T_mid1，按照p(x)-p(r)+p(t)+1计算T_mid1每个节点n的I(n)；④ T_origin中从r到f的路径中节点，标记为[r₁，r₂, …，r_n]，对应于r=r₁，以及f=r_n；⑤寻找从r到f的路径.初始化T_mid2为空NR，对于每个i(1＜i≤n)，仅当满足d(i)＜c+1时，复制以r_i为根的子树(但不包括以r_i-1为根的子树)到T_mid2的末端，同时，按照p(n)-p(r)+i+p(t)+1方式修正每个加入T_mid2的节点n的进深值；之外，执行p(r)=p(r)+1和p(f)=p(f)-1以修正节点r和f；若不满足d(i)＜c+1，在跳转至步骤⑤，对下一个节点r_i+1判断；如果r_i已是T_dst中最后节点，则表明c过小，CT结束；⑥将被裁剪子树和T_dst连接组合成新树T′_dst，即包含T_dst，T_mid1和T_mid2，以[T_mid1T_mid2]序列方式置于T′_dst的(t+1)处，执行d(t)=d(t)+1修正t的度值；⑦利用T_origin中[T_tmp1T_tmp2]之外的节点创建T′_origin，将原T_origin中f的前趋节点度值减1；⑧复制F对应的NR生成一个新的森林F′，将指向F′中新旧两棵树的指针分别记为h_T′_origin和h_T′_dst；计算d_G(T′_origin)和d_G(T′_dst)并存于F′；⑨修正矩阵M_N中T′_origin和T′_dst中的每个节点n.

子算法4  单树森林修正算法UpdateForSingleTree()

上述算法在应用CT与FT时，均假设一个森林中至少存在两棵树.为了扩展算法的适用性，可将仅有一棵树的森林予以修正，依照特殊方式实施操作.

输入：森林F的唯一树T_origin. 输出：新生成森林F′的FoR.

① 建立一棵树T_sup进行辅助，假设该树仅包含一个节点n，此时该节点n∉G，且n与T_origin中每个节点均保持连接；②令T_dst为T_sup，执行FT，由此可将T_origin中一棵子树变为T_sup中n的后继；③利用FT或CT操作，将以n为根子树变为原始树，从而生成一个新的森林F′.

子算法5  FT关键节点选择KeyNodeSelectionForFT()

输入：森林F的FoR序列. 输出：FT中新树T_dst中节点t，被迁移子树T_origin中的根r.

① 随机寻找F中一棵树T，需满足d_G(T)大于d_T(T)，令T_origin为T.若无法找到，则说明图G本身即单个森林，停止该过程；②从T_origin中随机确定一个非根节点r，d_G(r)大于d_T(r)；③从N_G(r)随机选择一个节点n，若边(n，r)不属于E_T，则令t为n，否则跳过本步骤；之后通过搜寻矩阵以确定节点t在森林F中的索引I(t)；④若t属于T_origin的节点集合，则执行单树森林操作；否则执行FT.

子算法6  CT关键节点选择KeyNodeSelectionForCT()

输入：森林F的FoR序列. 输出：被迁移树T_origin中的根r；修剪节点f；新树T_dst中的节点t.

① 随机寻找F中一棵树T，需满足d_G(T)大于d_T(T)，令T_origin为T.若无法找到，则说明图G本身即单个森林，停止该过程；②从T_origin中随机确定一个非根节点r，d_G(r)大于d_T(r)；③寻找r至T_origin根的路径，令i为1且r_i为r，以向根的方向从T_origin中I(r)开始遍历，步长为1，同时判别遍历过程中的每个节点n，若p(n)小于p(r_i)，则令r_i+1为n.若i>2，则在[2, …, i-1]范围内随机选择j，令f为r_j；若整个路径仅包含节点r和根，则令f为r；④从N_G(r)中随机选择一个节点n，若边(n, f)不属于E_T，则令t为n，否则重复本步骤；之后，通过搜寻矩阵以确定节点t在森林F中的索引I(t)；⑤若t属于T_origin的节点集合，则执行单树森林操作；否则执行FT.

1.4 基于DR算法的恢复路由生成流程

首先，基于节点表示法NR，对由多个AS组成的路由系统编码，将系统表示为含有多棵树的森林，记为FoR；其次，如果目前FoR代表仅含单树的森林，由于后续的基础迁移FT和复杂迁移CT算法均假设森林中至少存在两棵树，因此为拓展算法的适用性，利用单树森林修正算法UpdateForSingleTree()对该森林修正.反之，则直接进行失效AS节点迁移操作；再次，路由系统遭袭后通常会造成单个失效自治域节点或多个毗邻失效自治域节点，根据2种不同的情况，分别采用FT关键节点选择算法和CT关键节点选择算法，率先计算出2种情况下的关键节点；之后，分别利用FT算法和CT算法，实施失效节点的迁移操作，完成域间路由系统恢复.

2 时间复杂度分析

分析度约束最小生成树的时间复杂度.对于多域社团抽象出的连通图G，包含的自治域数目为n.

定义1  s=|T_origin|+|T_dst|，其中|T_origin|和|T_dst|分别表示参与节点交换的两棵树的容量大小，s即代表交换操作的时间复杂度，其平均值为s.

定义2  t=|T|表示G中生成森林中树的个数.

定义3  s_op=s_FT+s_CT，表示FT和CT操作的时间复杂度，其平均值为s_op.

定义4  s_init为初始化子树指针h、新树根r_new、备选节点序列等参数的复杂度，其平均值为s_init.

度约束最小生成树的时间复杂度C=s_op+s_init.

1) 计算s.如果连通图G中的n个节点均匀分布于t棵树(假定$ t = \left\lceil {\sqrt n } \right\rceil $)，令K为森林中的不同树对组成的集合，则s的平均大小为

$ \overline s = \sum\limits_{|i, j| \in K} {\frac{{|{T_i}| + |{T_j}|}}{{|K|}}} $

其中，若固定i不变，则对于|T_i|+|T_j|有t-1组，此时|T_i|+|T_j|之和为

$ \left( {t - 1} \right)|{T_i}| + \sum\limits_j {|{T_j}| - |{T_i}|} $

之后对每种T_i情形累加，求和可得

$ \overline s = \sum\limits_{\left\{ {i, j} \right\} \in K} {\frac{{|{T_i}| + |{T_j}|}}{{|K|}} = \frac{{2n}}{t} = O\left( {\frac{n}{t}} \right) = O\left( {\sqrt n } \right)} $

2) 计算s_op.根据FT和CT操作步骤，可知

$ {s_{{\rm{op}}}} = O\left( {|{T_{{\rm{origin}}}}| + |{T_{{\rm{dst}}}}| + t} \right) = O\left( {s + t} \right) $

由上述1)结论，则有

$ {\overline s _{{\rm{op}}}} = O\left( {\overline s + \overline t } \right) = O\left( {\sqrt n } \right) $

3) 计算s_init.根据初始化过程可知

$ {\overline s _{{\rm{init}}}} = O\left( t \right) + O\left( {3|{T_{{\rm{init}}}}|} \right) + O\left( {\overline s + \frac{n}{s}} \right) $

|T_init|的上限为|T_origin|+|T_dst|，则由1)、2)可知

$ \begin{array}{c} O\left( {3|{T_{{\rm{init}}}}|} \right) = O\left( {s + t} \right)\\ {\overline s _{{\rm{init}}}} = O\left( {\overline s + t + \frac{n}{{\overline s }}} \right) = O\left( {\sqrt n } \right) \end{array} $

4) 度约束最小生成树的时间复杂度C

$ \overline C = {\overline s _{{\rm{op}}}} + {\overline s _{{\rm{init}}}} = O\left( {\sqrt n } \right) $

分析可知，度约束最小生成树的平均时间复杂度为$ O\left( {\sqrt n } \right) $，根据CNM(Clauset Newman Moore)算法对AS级域间路由系统的分解，约70%的社团AS数目小于100，因此基于度约束最小生成树的恢复算法在时间耗费方面完全能够满足多域环境下恢复路由的快速生成.

3 验证和比较

利用锦标赛选择法挑选子代，操作数选择为2，分别对应FT操作和CT操作.基于精英选择策略，通过对收敛速度的判别，确保仅有最佳解决方案被用于构建下一代生成树.

3.1 基于随机图的仿真

利用拓扑产生器，基于广义线性优先(GLP，generalized linear preference)模型生成随机图，代表路由系统AS级拓扑.设置随机图节点个数分别为10、50、100、200、400、600、800、1 000.模拟BGP-LDoS对上述随机图实施袭击，针对存活节点及链路，分别利用DR算法同边集表示(ESR，edge set representation)^[10]、基于蚁群的度约束生成树(AB-DCST，ant-based algorithm for degree constrained spanning trees)^[11]和混合稳定态遗传算法(HSSGA，hybrid approach combining a steady-state genetic algorithm)^[12]3种算法生成DCMST.对生成树节点度值范围限定在[3,6]；GLP生成的随机图平均节点度为4.1.

1) DR与ESR算法对比

ESR利用特定交换和变异，由边集操作产生新树.仿真实验同样采用文献[10]中对ESR的设置，交换概率和变异概率均为0.8.

图 1和图 2分别给出了在限制度值分别为3和6的情况下，包含不同节点个数的随机图，利用ESR算法和DR算法分别生成DCMST所花费时间的对比.由图可知，2种算法下，随着度值约束的放松，即在约束值越高的情况下，随机图生成时间相对越短.整体上，同样拓扑规模对应的DCMST生成时间差距较小.

DR算法相对于ESR算法具有明显的性能优势，伴随着拓扑规模增大，性能优势越发突出.与时间复杂度理论分析相比，DR算法在随机图仿真条件下性能表现更好，优于平均时间复杂度.

2) DR与AB-DCST算法对比

AB-DCST算法模拟蚁群在图中移动，识别候选边集，从而建立度约束最小生成树. 表 1中|V|代表节点个数，生成所用时长均以s为单位，可知随着度约束值的逐步增大，DR与AB-DCST算法生成度约束最小生成树的时间均在减少.在具备同样度约束值的情况下，对于相同节点个数的随机图，DR算法的生成速度要快于AB-DCST算法.

值得注意的是，随着图中节点个数的增加，DR算法相比于AB-DCST算法的性能优势相对在扩大；其他度约束值情况下，也具有相似特征，表明DR算法在面对大规模随机图时，具有更好的生成效率.

3) DR与HSSGA算法对比

HSSGA为混合式的构建算法. 表 2所示为DR与HSSGA在度约束为3、4、5情况下的消耗时间.

由表 2可知，伴随度约束的宽松，2种算法下生成DCMST的时长都在逐步减少.对于相同节点个数和相同度约束，比较二者消耗时长，发现DR算法优于HSSGA算法.此外，需要注意的是，在相同度约束下，随着节点数的增大，DR算法相比于HSSGA算法的性能优势在逐步降低.

3.2 基于CAIDA的仿真

利用来自CAIDA的真实互联网拓扑对DR算法进行仿真，分别从名为BGP_tables和WHOIS的数据集获得样本拓扑，从2个原始数据集中抽取涵盖前3 000个AS节点的拓扑进行仿真.将取自BGP_tables的局部拓扑命名为B_tpl，平均度值为2.51；将取自WHOIS的局部拓扑命名为W_tpl，平均度值为6.53.

模拟BGP-LDoS对B_tpl和W_tpl拓扑实施攻击，针对存活节点及链路，分别利用DR算法同ESR、AB-DCST和HSSGA算法生成DCMST，作为域间路由系统遭袭后的恢复拓扑，对生成树节点度值范围也限定为[3,6].

图 3给出了B_tpl样本下，度约束范围在[3,6]内使用DR算法和其他3种算法生成DCMST的时间对比.可知，4种算法下，随着度值约束的放松，DCMST的生成时间整体上均逐步缩减；虽然DR在度约束5和度约束4情形下时间损耗基本持平，但整体趋势仍为缩减.相比于ESR、AB-DCST和HSSGA算法，DR算法具有相对一定的优势，有效降低了DCMST生成时间.

图 4所示为W_tpl样本下，度约束范围在[3,6]内使用4种算法生成DCMST的时间比较.同B_tpl样本仿真结果类似，一方面，随着度值约束条件的放松，DCMST的生成时间也在逐步缩减；另一方面，DR算法对比ESR和AB-DCST算法整体具有显著的性能优势；此外，DR相对于HSSGA算法，在度约束值为[3,5]区间内也有较优表现，在度约束为6时，二者差异较小.

4 结束语

基于DCMST的域间路由恢复算法DR，在降低生成恢复拓扑时间复杂度的同时，有效控制节点聚合问题.为记录拓扑生成时的节点迁移信息，设计了子算法TransferNodesEncode()；为从已有生成森林产出新的生成森林，设计了子算法FundamentalTransfer()/ComplexTransfer()；为了判定和计算迁移过程中的关键节点，分别提出KeyNodeSelectionForFT()/KeyNodeSelectionForCT().理论分析结果表明，DR计算DCMST的平均时间复杂度为$ O\left( {\sqrt n } \right) $，仿真实验验证了该算法在满足较小度约束条件的同时具有性能上的优越性.