基于拓扑分析的区域级网络抗毁性研究

安常青，刘玉家，王会，郑志延，喻涛，王继龙,3

（1.清华大学网络科学与网络空间研究院北京信息科学与技术国家研究中心，北京 100084；2.鹏城实验室，广东 深圳 518000；3.清华大学奇安信联合研究中心，北京 100084）

1 引言

全球互联网的重要性日益提高，已成为人们生活各个方面所依赖的关键基础设施之一，网络的安全性是保证正常通信的基础。

对于网络拓扑，目前区域或地区受到多方面的安全威胁。首先，各种类型的恶意行为者针对网络拓扑弱点破坏、拦截互联网流量[1-2]，通过对网络进行攻击，实现各种政治、经济等目标。

其次，已有研究发现部分区域或地区具有与互联网断开的可能，Dyn 针对与国外互联网服务提供商（ISP,Internet service provider）有直接联系的国内互联网服务提供商进行分析，发现只有30 个区域或地区没有与全球互联网脱钩的风险。目前有专业的机构进行网络断网事件的监测并实时报告，如千眼、互联网健康报告。

除上述特定的恶意攻击外，自然灾害对网络设施的威胁也是巨大的[3]，通常会影响特定地理区域的所有目标，即使是很发达的区域，也会由于自然灾害的原因受到影响，例如2012 年美国东海岸桑迪飓风导致的断网[4]。

学术界在网络拓扑弹性、安全性及抗毁性方面持续有相关研究。早期工作大致可总结为两类，针对网络拓扑建模并对网络特点开展相关分析或是基于早期测量数据进行抗毁性分析。Albert 等[5]通过随机性删除网络节点，分析了复杂网络的错误和攻击容忍度，发现互联网具有“意外程度的稳健性”，甚至不切实际的高故障率也不会影响节点的通信能力。一些有关互联网拓扑弹性的工作[6]基于简化的拓扑图，没有加入路由策略的限制，从图论的角度对拓扑进行分析。

之后研究扩展到具有路由策略的实际拓扑，进一步分析链路故障的位置如何影响互联网。Wu 等[7]和Dolev 等[8]从破坏性角度分析网络拓扑的弹性。Dombrowski 等[9]从图论的角度分析云服务的拓扑连通性，模拟了随机和有针对性的节点攻击，并评估了云服务的相应漏洞。Omer 等[10]提出了用于测量网络弹性的模型，定义了网络中断前后的传输价值来衡量网络的基本弹性，基于现有的容量和流量信息，分析光缆网络的全局弹性。

学术界逐步由关注网络整体变为关注于网络中区域本身或某些重要组件的安全性。近期研究工作更多地集中在对区域整体以及区域间直连自治系统（AS,autonomous system）链路的分析，即边界AS 链接。Leyba 等[11]定义国家关键点潜力（NCP,national chokepoint potential），通过NCP 评估边界AS 在区域拓扑的影响力。Alexander 研究传输运营商在区域层面的影响力，主要是每个区域中最具影响力的AS，以及那些严重依赖传输AS 的区域。CAIDA项目MapKit研究互联网拓扑对区域/地区级连接中断的敏感性。项目提案中提出构建网络的多层拓扑图，涵盖网络层、链路层、物理层，识别并量化区域对攻击的敏感性。针对区域的拓扑结构，上述研究并未定量分析区域的抗毁性差异。

本文主要贡献如下，提出了区域抗毁性评估方法，定义了抗毁性度量，分别从内部拓扑网络和外部通信拓扑2 个方面对区域的抗毁性度量差异进行评估。基于显著性检验，分别从网络整体水平和网络特殊薄弱点2 个方面对抗毁性度量排名，该方法具有普适性，能给发现区域之间拓扑的本质差异。数据层面考虑到探测点的局限性，进行区域之间直连链路预测，完善拓扑数据。

2 定义

本节描述本文涉及的主要定义及相应的含义。

1) AS 抗毁性：一个事件发生后AS 与其他节点间通信情况的变化称为AS 对一个事件的抗毁性。AS针对多次破坏的抗毁性形成一维向量称为AS的抗毁性样本。

2) 区域抗毁性：区域抗毁性是对区域内AS 抗毁性的加权综合度量。

3) 路由影响力：描述其他节点需要经过该AS进行转发的依赖程度，即AS 在区域的路由影响。

4) 资源权重：描述节点在区域中持有的资源比例，即占该区域所有资源的比例。节点资源权重越高，被破坏后对区域的影响越大，用于量化破坏事件的影响。本文从用户数量、域名等多个角度分析节点的资源权重，形成不同视角下的抗毁力评估。

6) 边界AS：与其他区域有直接的拓扑链接。

7) 内部AS：没有与其他区域的直接拓扑链接。

8) 边界AS 链接：不同区域边界AS 之间的链接。

下面，详细介绍节点抗毁性、路由影响力和区域抗毁性度量的含义和计算方法。

2.1 节点抗毁性

事件发生后AS 与其他节点间连通情况的变化称为节点对一次事件的抗毁性。针对多次破坏的抗毁性形成一维向量，即节点的抗毁性样本，对样本的综合分析形成节点抗毁性度量。本节重点介绍节点抗毁性样本的定义。

2.1.1 单次事件抗毁性

互联网的核心是“互连”，学术界定义网络破坏的度量中，常用且可解释性好的就是连通性，可以直观反映破坏后节点的通信情况。本文使用连通性来表征破坏的影响，即发生破坏性事件后，网络间节点对的连通性变化程度。

对于区域中的某个AS，一次破坏事件可以使其与某些节点无法连通，而区域内各个节点所持有资源的比例不同，如对于AS 节点，从用户角度，拥有更多用户的AS 资源比例更高。

破坏事件影响定义为破坏后该区域可与其连通的节点资源之和与该区域所有节点资源之和的比值，即

其中，eix表示对于节点i，第x次破坏事件的破坏影响；O表示区域节点集合；B表示这次破坏事件后可以与节点i通信的节点集合；r表示某个节点的资源，如用户数量。

本节从不同角度出发，实现了多种节点资源r的定义。在区域内部，关注各个AS 节点的连通，在4.2.1节定义AS 节点的资源。在区域外部，关注各个区域之间是否连通，在4.3.1 节定义区域节点的资源。

2.1.2 抗毁性采样

对于每个节点i，模拟破坏事件集合为[f i1,fi2,…,fim]，计算节点i面对一次破坏事件fiq对应的单次事件抗毁性为eiq，可以得到节点i的抗毁性采样Ei=[ei1,ei2,…,eim]。

下面，只讨论破坏节点的情况，破坏链接的情况类似。区域内节点数量为n，假设破坏一个节点的发生概率为p，则破坏x个节点的概率为px。总事件A={A1,A2,…,An}，其中事件Ax为x个节点被同时破坏，事件Ax发生的期望为y=C(n,x)px，那么对于总事件A，所有破坏事件发生的期望为。

图1 为y=C(n,x)px的分布。从图1 中可以看到，首先随着破坏数量x的增大，实际破坏事件的发生期望y也急剧增多，x=5 前就达到最高点，之后y迅速减小。当x≥10 时，y均小于0.1；当x≤6 时，期望值是所有破坏数量下总期望值，而x≤8 时达到99.9%。

本文用分层概率采样的方法，破坏节点数量x不同时采样概率不同，当破坏数量较大时，实际发生次数y很小，采样概率设为0。

2.2 路由影响力

路由影响力衡量具体的AS 节点在某个区域中为其他AS 提供的路由服务，即其他的路由路径有多大比例经过该AS。

理想情况下，位于区域c的ASb对于内部某个ASo的路由影响力可定义为，其中P(ASb,ASo)计算ASo路由经过ASb的次数，r(ASo)为ASo实际路由的次数。

但是，BGP 数据收集严重偏向探测点看到的数据。由于探测点在区域之间分布不均匀，而且许多区域和大多数AS 都没有设置探测点，获得的数据均为通往探测点的路径进行过度采样的结果。为了度量AS 在区域内部的实际影响力，需要计算其在实际路径中的出现比例，而探测点自身的有限性和偏见性对该结果有较大影响[12]。

本文设计了过滤器，通过对探测点进行过滤，减轻计算结果受到探测点自身局限的影响。

位于区域c的ASb路由影响力wc(ASb)定义为

其中，O表示区域c内所有AS 集合，URc(ASb,ASo)表示ASb对ASo的用户影响力，θo表示区域c中ASo的用户比例。以用户比例作为权重，总路由影响力为ASb对区域内所有AS用户影响力的加权和。式(3)计算用户影响力UR，其中R为一维向量，存储所有探测点实际观测到ASo经过ASb的比例。式(4)计算观测到经过ASo的所有路径中，ASb经过ASo的路径比例，其中Pi(ASb,ASo)为探测点i观测到的ASo经过ASb的路径数量，ri(ASo)为探测点i观测到ASo的数量。式(5)中，R存储所有探测点的数据，并按照ri(ASo)排序，函数fvp(R) 为探测点过滤器，过滤距离ASb过近和过远的探测点。

2.3 区域抗毁性

本文通过多次模拟破坏事件，获得区域抗毁性采样。设计显著性检验器，比较不同区域抗毁性采样的差异，得到各个区域的抗毁性度量。

图2 描述了区域抗毁性的计算流程。对于每个区域，选择重要的AS 集合，并计算每个AS 的抗毁性采样，在4.2.2 节和4.3.2 节分别说明AS 的选择标准。通过加权上采样，将区域内AS 的抗毁性采样转换为区域的抗毁性加权采样。最后通过显著性检验器，比较不同区域抗毁性加权采样的差异，得到区域抗毁性度量。

下面分别讲述加权上采样和显著性检验器的实现，然后通过采样实验和方法分析说明抗毁性计算方法的合理性。

2.3.1 加权上采样

通过加权上采样，获得区域的抗毁性采样，输入为区域中AS 的抗毁性采样，输出为区域的抗毁性加权采样。

将AS 的路由影响力作为该AS 对应的采样权重。AS 的路由影响力越高，区域内依赖其通信的AS 数量越多，且实际路由中需要经AS 进行路由转发的次数越高，AS 的抗毁性直接影响这些依赖它的AS 的连通性。

加权上采样思路如下，对于每个区域，输入为[E1,E2,…,Em]和[w1,w2,…,wm]，其中Ei和wi分别表示第i个AS 的抗毁性采样和采样权重，获得输入采样权重的最小值wmin，抗毁性采样结果Ei的采样次数为，最后该区域抗毁性采样长度为表示iE的长度。

2.3.2 显著性检验器

显著性检验器旨在发现区域抗毁性采样的相对差异，排除随机模拟破坏对抗毁性采样结果造成的波动，发现不同区域抗毁性度量的真实差异。

本节从2 个角度出发，设计2 个显著性检验器。第一个角度是破坏结果的整体水平，该角度反映多次随机破坏下区域拓扑的受破坏情况，经典的统计量有平均值、中位数。第二个角度是破坏结果的波动程度，波动较大表明存在某些薄弱区域，经典的统计量有方差。

显著性检验器的输入输出定义如下，输入为n个一维向量，每个一维向量代表一个区域抗毁性采样，输出为 [ravg1,…ravgn,rstd1,…rstdn]，ravgi表示第i个区域在整体水平的显著性评估结果，该值也表示区域i在整体情况下的抗毁性排名，2 个差异性不显著的区域有相同的抗毁性排名；rstdi表示第i个区域在波动水平的显著性评估结果，同时也表示区域i在波动水平下的抗毁性排名。区域抗毁性度量不是确定值，而是经过显著性检验器处理后的各个区域破坏结果的比较排名值。

显著性检验器实现思路如下。整体水平下的显著性检验器使用Kruskal-Wallis 检验[13]，该检验判断中位数是否具有显著性差异，在有显著性差异下，通过Steel-Dwass 事后检验获得两两比较的结果。根据2.3.3 节的模拟破坏数据和后续区域破坏数据，通过K-S 正态检验和方差齐性检验，发现抗毁性破坏结果满足正态分布，而不同区域的破坏结果不满足方差齐性，Kruskal-Wallis 检验方法适用于破坏数据。通过方差齐性Hartley 检验进行波动水平的比较，看两两方差的差值是否有显著性差异。

2.3.3 采样实验

为了验证随机模拟采样以及使用显著性检验比较的合理性，模拟分别随机生成30、40 个节点的有向图，链接的数量均为100，破坏链接数量设置为1、2、3，对应的单个事件发生概率分别为p、p2、p3。所有破坏组合事件的数量为 166 750（C(100,3)+C(100,2)+C(100,1)）。根据连通性计算所有破坏情况下的破坏影响，即网络中无法连通的节点对的比例，计算每个破坏的结果，用破坏影响乘以发生概率，将所有破坏结果累积获得结果向量。

随机从结果向量中抽取部分样本，比较样本和结果向量在2 个角度下是否有显著性差异，图3 为采样结果，纵坐标格式为“节点数量−边数量−检验方法”，包括2 个图的2 种检验方法的结果。图中用符号“+”表明有显著性差异，发现在采样样本数量大于18 000 时，即采样概率超过11%时，结果不存在显著性差异。

该结果表明，采样率超过11%时能反映完整的破坏结果的分布，采样造成的信息损失并不大。

2.3.4 方法评价

已有大量工作针对网络和节点的抗毁性进行分析。其中部分工作根据节点的重要性和网络的脆弱点，提出一些量化指标。一些工作定义度中心性[14]、介数中心性[15]来表征节点的中心性。许进[16]和王梓行[17]分别提出核与核度、冗余度来表征系统节点的重要性。指标具有可比性，但是仅针对复杂网络，并未加入互联网的路由策略。

此外，大量工作研究复杂网络和互联网的抗毁性。设计不同的破坏角度和方法，包括随机破坏、有针对性破坏、基于互联网的层次结构破坏等。定义衡量破坏的指标主要包括连通度、破坏前后平均路径长度等。文献根据网络在不同破坏模拟下的结果进行分析和讨论。但是此类工作并不能给出具体网络的抗毁性的量化值，因此可比性较差。

目前也有针对区域进行横向比较的工作，但是这些工作均从某些特殊角度进行切入。Leyba 定义NCP，通过NCP 评估边界AS 在区域拓扑的影响力，横向对比8 个区域，分析NPC 的变化与差异。Alexander 研究传输运营商在区域层面的影响力，发现哪些区域的流量更不易被其他区域的传输运营商观察和操控流量，具有更高的安全性。

目前尚未调研到有区域整体抗毁性定量比较的方法，本文根据区域抗毁性度量为区域进行排名，排名方法设计的合理性是至关重要的。本文借鉴经济、社会等领域进行量化排名的已有工作的思想，以量化和比较为目的，并增加互联网资源的权重度量等因素，提出区域抗毁性度量，使排名具有多个角度和更大的灵活性。以下具体说明本文方法考虑的因素及其合理性。

1) 从整体水平和波动水平的角度来共同衡量区域抗毁性。具体原因如下，已通过K-S 正态检验发现区域的破坏结果数据服从正态分布，而正态分布仅由均值和方差决定，所以整体水平和波动水平一起能捕捉到正态分布数据完整特性。此外，均值和方差在统计学具有重要地位，也应用于各个方面，如Markowitz 均值−方差模型用来求解最优资产配置的比例，社会收入也会从整体水平和波动水平（基尼系数）来分别讨论，此类工作从不同分析角度出发，评价区域的差异性，对本文工作具有借鉴意义。

2) 用分层概率破坏模拟破坏结果性。大量的文献在研究网络抗毁性时会使用随机破坏的方法，由于随机模拟的无差异性和宏观性，对各个区域的模拟方法相同，使抗毁性比较更具有客观性，抗毁性结果更具有可比性。本文在进行破坏时充分考虑了事件发生的概率，根据事件发生概率模拟破坏事件，符合互联网运行规律。

3) 在区域抗毁性计算中包含多种权重的定义。通过定义区域节点的资源权重（2.1.1 节），衡量不同节点被破坏的差异性。多角度定义的权重支持了模型的可扩展性，提供了多个角度的抗毁性结果，增加了说服力，也让抗毁性结果更加丰富。

4) 聚类并进行分组分析。利用整体水平和波动水平下区域抗毁性的排名结果，对区域进行聚类分组。聚类算法[18]应用广泛，如构建用户画像、进行恶意流量识别、搜索引擎流量推荐等。本文通过聚类发现组内区域之间的相似性和组间区域之间的差异性。

3 挑战与方法

3.1 计算连通性的高复杂度

计算区域内部的抗毁性度量时，需要知道各个破坏事件下区域内部所有AS 节点对之间的连通性变化，具有较高的复杂度O(n3)，n为区域中AS 的个数。表1 列出了各区域的AS 数量和AS链接数量，数据去掉了没有客户的AS 节点。其中美国有2 119 个AS 节点，并有25 个区域AS 的数量大于100，降低计算连通性的时间复杂度是很有必要的。

表1 各区域的AS 数量和AS 链接数量（除去没有客户的AS）

本文通过数据预处理来降低计算复杂度，将区域的抗毁性采样转化为区域中AS 的抗毁性采样。

已有工作[19]提出了路由树的构建方法，以AS节点ASbase为基础，路由树通过3 个步骤的广度优先算法，构建出具有路由策略的连通关系树，后文称为ASbase的路由树。网络中可与ASbase进行通信的AS 在且仅在ASbase的路由树中。计算路由树破坏的连通性复杂度最坏情况下为O(m+n)，m为链接数量，n为AS 数量。本文首先构建各个节点的路由树，从计算节点的两两连通性的O(n3)转变为各个节点路由树内与其他节点的连通性，复杂度为O(n×(m+n))。

考虑到各个AS 的路由影响力不同，只选取重要AS 来构造路由树并模拟破坏，将复杂度降为O(m+n)，得到更加轻量级的计算模型。

3.2 测量数据的缺失

基于探测点收集的AS 路径数据，很容易缺失关键链路的信息。区域之间边界AS 的链接对评估区域间通信的抗毁性至关重要。

本文通过发现隐藏链接之间的内在相似性进行缺失链接推断。文献[20]发现隐藏链接的存在，并发现部分隐藏链接的特点。对于只有一个探测点被观察到的链接，将其称为单例链接。如果探测点发生更改，则可能观察不到该链接，造成此类链接的丢失。比如某个观测点观察到路由路径为ASA−ASB1−…ASBn−ASC(n≥ 1)，但是另一观测点观察到ASA和ASC也具有直接相连的链接，称为单例链接的绕行路径，用符号LAC表示该链接。此外该论文观察到在所有绕行链接中，连续两跳路径（n=1)是某个单例链接绕行路径的概率为80.8%，为大多数情况。

考虑边界AS 之间的链接，对n=1 时绕道而行的单例链接进行预测。为了生成训练数据的负样本，当A 距离观测点的跳数小于或等于1 时，如果并未观测到链接，则表示不存在该链接，称为负样本。而实际观测到的单例链接则称为正样本。

针对边界链接的特点，表2 列出了输入特征。本文分别使用K 近邻回归器、回归树、提升树、随机森林、极端森林、XGB 进行分类预测，通过交叉验证发现，所有算法的准确率均高于91%，其中极端森林效果最好，准确率高达98%。

表2 边界AS 链接预测特征分类及描述

本文通过该算法预测到261 条隐含边界AS 链接。

3.3 地理定位的准确性

3.3.1 IP 地理定位

IP 定位数据库在区域精度上准确度相对较精确，本文基于IP 定位数据库实现IP 的地理定位。为了提高IP 定位结果的准确率，使用Team Cymru、Maxmind、IP2location、RIPE IPmap 这4 个数据库。这4 个数据库用来对某个IP 地址查询，可能会发生错误结果的数量大于正确结果的数量的情况，例如3 个一致的错误结果与一个正确结果。基于合理的假设，认为该现象的发生是较少数，设计基于投票的方法将4 个数据库的结果进行融合。基于投票的方法步骤如下。

步骤1计算4 个数据库的一致性百分比

1) 对于每个数据库Di，对每个IPi获得定位结果Ci。

2) 用其他3 个数据库对IPi进行地理定位，确定4 个地理定位结果的多数，并检查4 个数据库的定位结果是否与多数一致，即是否存在一致性。

3) 计算一致性出现的比例，获得数据库Di的一致性百分比DCRi。

步骤2根据一致性百分比进行定位结果的投票1) 对于每个IPi，4 个数据库结果分别为C1、C2、C3、C4。

2) 每个数据库Di对自己的结果进行投票，投票分数为DCRi。

3) 获得投票总分数最多的结果即IPi的定位结果。

3.3.2 AS 地理定位

目前，没有直接方法进行AS 的地理定位。AS路径进行地理映射的最大难点在于存在跨越数个区域的AS，难以对其进行地理定位。虽然地区性互联网注册机构（RIS,regional internet registry）在为每个区域分配AS 号时登记了每一个AS 所属的区域，但是登记的只是每个AS 法律意义上的所属区域，实际上的AS 路径可能实际经过了其他的区域。结合IP 定位数据库和Traceroute 数据，本文提出AS 地理定位的快速方案。

本文处理思路如下。首先获得AS 在各个区域的分布，IP 定位数据库中将IP 地址定位到AS 和区域，以IP 为媒介，能够获得AS 和区域的对应关系。其次，对于位于单个区域的AS，可以直接实现区域定位。计算发现，仅有6.8%的AS 位于多个区域，对于这部分AS，结合该AS 的上下文环境（AS 路径中该AS 的前后AS）进行针对性计算。

借鉴Karlin 等[21]提出的区域路径推测算法，本文设计了轻量级的匹配方法，对位于多个区域的AS 进行地理定位。Traceroute 主动测量能体现自治域内路由的情况，首先将Traceroute 数据中IP路径定位到AS 和区域，获得AS 路径和区域路径的对应关系数据库。特别地，对于某个链接，其是位于不同区域的相同AS 之间的链接，在AS 路径中合并为一个AS，这个AS 的地理定位是2 个区域。图4 描述了位于多个区域的AS 地理定位的4 个步骤，具体描述如下。

1) 对于AS 路径P中需要地理定位的ASα。

2) 提取在Traceroute 数据中出现ASα的AS 路径Q。

3) 对于每个AS 路径iQ，将Qi和P进行匹配，具体为，以ASα为起点，向前向后获得最长匹配子串Mi。

4) 最长的子串Mx中ASα的定位即AS 路径P中ASα的定位。

4 抗毁性计算

本节首先介绍数据处理，目标为构建具有区域定位标签的全球AS 拓扑，之后分别介绍区域内部和外部的抗毁性度量的计算细节，抗毁性计算的方法已在2.3 节介绍。

4.1 数据处理

数据为从RIPE Atlas 平台收集到的Traceroute数据以及从Routeview 平台收集到的BGP 数据，二者均为2020 年3 月平台的全部数据。此外，由于探测点的局限，预测未发现的边界AS 链路作为拓扑图的补充。

在数据处理中，需要构建具有区域标签的AS级拓扑图。AS 拓扑图中，以AS 为节点，AS 间建立付费关系P2C（provider to customer）或对等关系P2P（provider to provider）为边。

这一部分主要包括2 个步骤：第一，需要分别把Traceroute 和BGP 数据中的IP、AS 定位到具体的AS 和区域，形成拓扑图中具有区域标签的AS节点；第二，为了在后续分析中考虑加入路由策略的限制，需要给每个AS 链接打上关系标签，学术界普遍将链接的关系分类为P2C 和P2P。

学术界有很多推测AS 关系的工作[22-24]，并发布了对应的数据集。利用已有的4 个AS 关系数据集（AS Rank、Problink、Toposcope、在Toposcope 中加入发现的隐藏链接后得到的数据集h-Toposcope）。

4.2 区域内部抗毁性计算

区域内部关注区域内部拓扑中AS 之间的连通性。在计算AS 破坏事件度量时，关注该AS 与其余AS 节点的连通。下面具体描述在区域内部，AS节点资源的定义，以及区域内需要计算抗毁性采样的AS 的选择。

4.2.1 节点资源定义

从3 个角度定义AS 节点i的资源权重ri。

1) 从连通性角度，ri恒为1。

2) 从用户影响力角度，ri为ASi的用户数量。

3) 从域名影响力角度，ri为ASi的域名重要性影响。

其中，连通性角度默认各个AS 的资源权重相同，关注于连通的AS 数量。考虑到网络中各个AS的用户数量并不相同，用户影响力角度计算AS 在全区域用户数量。文献[25]使用前缀顶级列表，将基于域的顶级列表聚合到网络前缀中，获得各个AS 基于域名重要性的影响度量。使用该工作的结果作为域名重要性影响。

4.2.2 重要AS 集合的选择

根据区域节点AS cone 值选择重要AS，AS cone定义为其直接和间接客户AS 的数量。由于只希望选择对本区域抗毁性表征力较强的节点AS 集合，这里只计算位于本区域的直接和间接客户的AS 数量。

希望尽可能捕捉到本区域的整体情况，选择方式如下，首先选择AS cone 排名前5 的AS，之后按照AS cone 排名逐步添加AS，直到所有AS 的直接和间接客户覆盖区域90%的AS。

4.3 区域外部抗毁性计算

区域外部抗毁性关注本区域和其他区域的连通性。下面具体描述在区域外部中，区域节点资源的定义，以及需要计算抗毁性采样的AS 的选择。

4.3.1 节点资源定义

区域外部抗毁性关注本区域和其他区域的连通性，对于区域i，从3 个角度定义其资源权重ri。

1) 从连通性角度，ri恒为1。

2) 从区域经济影响力角度，ri为区域i人均GDP 的Zipf 权重。

3) 从域名影响力角度，ri为区域i的域名重要性影响。

其中，连通性角度默认各个区域的资源权重相同，关注于连通的区域数量。从区域经济实力出发，用区域人均GDP 度量区域资源大小。已知在互联网中的大量事件流行遵循Zipf 分布[26-27]，为了防止区域间人均GDP 数值差距过大，用Zipf 分布对人均GDP 数据重新处理，得到的Zipf 权重为区域的人均GDP 权重ri。与AS 资源权重类似，从域名角度统计区域内部所有AS 的资源权重作为ri。

4.3.2 重要AS 集合的选择

选择区域的所有边界AS 作为重要节点集合，边界AS 是本区域和其他区域通信的“出入口”，边界AS 的抗毁性采样结果能全面反映本区域和其他区域通信的情况。

5 实验结果与分析

本节展示抗毁性评价的结果，由于探测点地理分布的差异，有部分区域的测量数据很少。根据测量数据，去除AS 链接数量太少的区域。本文研究48 个区域的抗毁性，其中欧洲区域24 个，亚洲区域14 个，非洲区域2 个，北美洲区域3 个，南美洲区域3 个，大洋洲区域2 个。

5.1 区域内部抗毁性

实验具体设计如下，使用4.1 节提到的4 个AS关系数据集和算法，使用4.2 节提到的3 种节点资源权重。观察区域内部抗毁性结果受AS 关系和AS资源权重的影响。模拟破坏节点数量为1～6，破坏后该节点所有相连的链接被断开。

图5(a)和图5(b)分别描述整体水平和波动水平下，各个区域内部抗毁性度量的排名值。类别1～类别4 分别表示AS Rank、Problink、Toposcope、h-Toposcope 数据，b、u、d 分别表示连通性、用户数量、域名重要性。将区域抗毁性度量结果用灰度图显示，区域抗毁性度量即相对排名，排名越高，区域抗毁性越好，灰度越低。灰度图的横坐标表示48 个区域，用区域代码表示，纵坐标表示不同的AS 关系数据集和资源权重组合，按照第一个组合下区域抗毁性排名对区域排序展示。

首先分析图5(a)在整体水平下区域抗毁性度量排名。在12 种组合下，巴西BR、美国US、俄罗斯RU 抗毁性度量排名并列第一。此外，德国DE、英国GB、荷兰NL、法国FR、南非ZA、澳大利亚AU、意大利IT、加拿大CA、日本JP、乌克兰UA、波兰PL 抗毁性排名紧随其后，除了以连通性作为资源权重的情况，其余组合中排名大多区域并列第一。可以发现，排名位于前列的区域大多位于欧洲，南非ZA 在非洲排名第一，日本JP 在亚洲排名第一，澳大利亚AU 在大洋洲排名第一。

图5(b)展示各个区域在波动水平下的区域抗毁性度量的排名。该排序和整体水平下的区域抗毁性度量排名相差很大，中位数和方差没有明显的相关关系，这也间接说明2 个指标联合评价的合理性。

综合2 个角度下的区域抗毁性度量，对区域进行聚类，图6 展示聚类结果。

图6(a)综合2 个角度下的区域抗毁性度量排名（12 个组合），对区域进行聚类，将结果分为六类。横纵坐标分别是整体水平（中位数）和方差角度在12 个角度下区域抗毁性度量的总和，每个类别按照横坐标由小到大排序。

类别1 在2 个角度下都表现较好，特别是俄罗斯RU、德国DE、英国GB、澳大利亚AU、乌克兰UA，在整体水平和波动水平下都有较高的抗毁性值。类别2 和类别3 有很好的整体水平，但是波动水平下的抗毁性度量稍差。其中美国US 和巴西BR 平均水平最好，但是方差角度下抗毁性稍差，属于类别3。具体观察图6(b)方差结果，各个区域只有在连通性度量下有明显的差异。这一类的区域有部分关键链路，破坏后会影响部分节点的连通，但这些节点重要程度较小，导致对整体网络影响很小。类别4、类别5 在48 个区域中抗毁性处于中等，其中类别4 在波动水平下抗毁性更好。最后类别6表现较差，较之前面类别的区域，受到破坏后对本区域通信的影响较大。

观察到波动水平的结果中，不同资源权重下的结果很不相同，进一步用资源权重划分结果。

图6(b)展示了资源权重为连通性的聚类结果，划分为七类，该结果与12 个组合下的聚类结果很相近。主要原因为，在波动水平下，各个区域在其他度量下的排名基本相似，而在整体水平中，各个区域在其他度量下的差异也小于连通性资源权重的差异。

图6(c)和图6(d)分别展示了资源权重为用户数量和域名重要性的聚类结果，二者结果相近，且该结果与图6(b)有较大差异。两张图中，所有区域的方差几乎相同，基本依赖区域的整体水平进行聚类。其中，类别1 表现最好，该集合数量也很多超过20 个。之后是类别2 和类别3，其抗毁性度量也较接近。前3 个类别共涉及一半以上的区域，超过一半的区域抗毁性情况相近且均很优秀。之后类别4和类别5 差异增加，抗毁性变差。

从不同度量下的聚类结果可以看出，超过一半的区域有较优秀的抗毁性能力，其中各个区域有一些细微差异而导致波动水平下排名的区别，主要体现在一些区域有部分较脆弱的节点集合，在某些破坏事件下无法连通，但节点集合的总影响力很小。从多个资源权重评价结果是合理且很有意义的，连通性度量更能捕捉网络的差异性，发现网络的轻微变化，但也会导致一些影响结果的“误判”，无法分辨破坏的真实影响力，将用户数量、域名重要性作为资源度量参考有效避免了该问题。

下面，讲述在内部抗毁性结果中的一些发现。

部分区域有抗毁性较差的外围AS 集群。从图6(a)发现，AS 关系的变化对区域抗毁性排名影响很小，而不同资源权重下区域的抗毁性具有一定差异。在连通性度量中，各个区域差异性更大。其原因为区域外围有部分AS 资源权重很小，被破坏后的影响很小。连通性度量认为各个AS 重要性相同，更加受到该类AS 的影响。从图6 中可以发现，意大利IT、加拿大CA、日本JP、乌克兰UA、波兰PL、印尼ID、印度IN 这些区域在用户数量、域名重要度量下排名前列，但是在连通性角度下与巴西BR 等排名最前的区域差异增大，这些区域都具有抗毁性较高的区域内核AS 集群，同时区域外围一些资源权重较低的AS 更易被破坏。

资源权重较高的节点不会被某些破坏事件突然摧毁。图6(b)中，只有在资源权重为连通性时，各区域才出现明显的差异，在其余的资源权重指标下，各个区域排名极其接近。该数据说明在各个破坏情况下，被破坏后无法通信的节点数量相差比较大，但是总体其在用户数量和域名重要性角度下，相差很小，间接反映了各个区域有较高用户数量和域名重要性的节点很少会因为某些特别的攻击而受到直接的影响。

所有区域对别的区域管理的AS 依赖性很小。对于每个区域，图7 只破坏区域内部由其他区域管理的AS，旨在发现是否有部分区域内部拓扑大大依赖于其他区域管理的AS。与图5(a)相比，3 个资源权重下区域之间的差异减小，在资源权重为用户数量和域名重要度下，大约30 个区域的排名均处于第一和第二，这些区域中非本区域管理的AS 对区域核心AS 集群影响很小。多数区域的排名均提高，其中澳大利亚AU、南非ZA、瑞士CH、印度IN 在资源权重为连通性时排名大大提高，整体排名也随之得到提高。伊朗IR、马来西亚MY 在资源权重为用户数量和域名重要性下的提高很明显，二者在图5(a)中3 个度量下的排名均大于10，但在图7中用户数量和域名重要性中排名均上升到前两名。说明2 个区域虽然整体安全抗毁性较差，但其他区域管理的AS 在该区域重要性很低，该区域能较好地抵御其他区域管理AS 的针对破坏。

5.2 区域外部抗毁性

区域外部抗毁性观察区域之间的连通，使用4.3 节提到的3 种区域节点资源权重。观察抗毁性结果发现，不同AS 数据集的结果差异很小，因此图中只展示了使用AS Rank 数据集的结果。

从2 个角度出发，图8(a)描述各个区域外部抗毁性度量即排名值。灰度图横坐标表示48 个区域，纵坐标b、g、d 分别表示连通性、经济影响力、域名重要性度量，var 表示方差角度，无标注表示中位数角度。按照6 个组合下区域抗毁性排名的均值对区域排序。与区域内部抗毁性结果图5 相比，各区域的抗毁性差距拉大，很少存在并列排名，各区域的具体排名也有变化。从图8 中可以发现，不同资源权重下结果差距很小，分析原因是各区域边界AS 数量有较大差异，所以资源权重对结果影响很小。

图9 展示区域外部抗毁性在整体水平和波动水平2 个角度下的聚类结果，由于不同资源权重下结果差异很小，这里只展示了全部组合的聚类结果。从聚类结果可以看到，整体水平和波动水平的结果高度正相关，将各个区域划分为5 个类别，其中类别1和类别2 区域外部抗毁性较好，美国US、德国DE、英国GB、加拿大CA 和俄罗斯RU 属于类别1，抗毁性最好。不同于区域内部抗毁性结果中大量区域集中在较好的类别，区域外部抗毁性中大量区域集中在较差的类别，其中超过80%的区域都在后3 个类别中。

下面，讲述在外部抗毁性结果中的一些发现。

不存在一些区域大量依靠其他区域管理的边界AS 服务。考虑到区域外部抗毁性和边界AS 抗毁性高度相关，但是位于本区域的边界AS 并不一定由本区域管理，本文只计算位于本区域且由本区域管理的边界AS，图8(b)展示该实验的抗毁性结果。和图8(a)相比较，各个区域排名都很类似，差距不大，所以不存在一些区域大量依靠其他区域管理的边界AS 传输稳定的服务。

各个区域边界AS 数量差异明显。表3 列出了各个区域边界AS 的具体数量，用Mb表示该区域管理的边界AS 集合，用Lb表示位于该区域的边界AS 集合。表3 中数据证明，各个区域边界AS 数量差距很大，美国US 有超过500 的边界AS，而有5 个区域数量小于10。Mb&Lb表示二者交集，即位于本区域且由本区域管理的边界AS；Mb−Lb表示二者差集，即位于本区域且不由本区域管理的边界AS。这两行数据可以得到区域内部边界AS 由本区域管理的比例，比较各个区域的数据，除了边界AS 数量较小的区域，约80%都由本区域管理，其中俄罗斯RU 的比例特别大，95%的边界AS 均由自己管理。但是新加坡SG 有44%的AS 由其他区域管理。

表3 区域边界AS 的数量情况

抗毁性排名和区域的边界AS 数量排名接近。比较抗毁性排名和边界AS 数量排名，发现二者趋势相同，但也有部分区域不太一致，其中加拿大CA、日本JP 边界AS 数量较少，但是抗毁性排名高，说明该区域具有抗毁性排名较高的边界AS，也有波兰PL、保加利亚BG、印度IN，边界AS 数量较多，但是抗毁性排名相对偏低，说明该区域边界AS 的通信质量拖了后腿。进一步探究原因，将所有区域所有边界AS 的抗毁性采样输入显著性检验器，得到区域边界AS 的抗毁性排名。图10 绘制了7 个区域的边界AS 抗毁性度量的排名分布。横坐标为边界AS 抗毁性排名，纵坐标为对应AS 的路由影响力占比。从图10 中可以发现，加拿大CA 和日本JP 在第一名的路由影响力比例是最高的。

5.3 区域通信服务影响力与抗毁性的关系

各个区域边界AS 的抗毁性决定了全球通信的抗毁性，从抗毁性的角度出发，分析各个区域管理的边界AS 在全球通信服务的重要性，即该区域通信服务的影响力。

思路概括如下。对于每个区域，每次只破坏该区域管理的边界AS，模拟破坏区域边界AS 的数量为1～25，破坏一个边界AS 即破坏该边界AS 的全部边界AS 链接。计算该破坏下全部区域所有边界AS 的抗毁性采样，汇总得到区域的通信服务影响力。

通信服务影响力和抗毁性排名差异很大。图11绘制区域通信服务的影响力排名。横坐标为各个区域，纵坐标为3 种资源权重。从图11 中可以发现，约一半的区域影响力都非常小，只破坏这些区域管理的边界AS，对区域间的通信几乎不造成任何影响。美国US 和德国GB 依旧排名靠前，其余与区域抗毁性排名很不一致，如法国FR、乌克兰UA、奥地利AT 在区域抗毁性中都排名靠前，但是服务影响力排名靠后。相反，印尼ID、捷克CZ、新西兰NZ 抗毁性排名较低，区域管理的边界AS 数量Mb较少，但是服务影响力排名位于前列。

进一步分析原因，表4 列出7 个区域的边界AS 抗毁性度量排名前五级的数量。和服务影响力排名一致，美国有很强的影响力，抗毁性排名第一级的边界AS 数量很多。法国FR、乌克兰UA 和奥地利AT 抗毁性排名前五级的边界AS 数量只有一个或2 个，远不如其他区域。印尼ID、捷克CZ、新西兰NZ 抗毁性排名前两级数量很少，但是前五级的数量很多。法国FR、乌克兰UA 和奥地利AT 的区域通信影响力低的原因在于它们的边界AS 有很丰富的AS 链接，且该区域与周围区域也有丰富的AS 链接，导致破坏该区域管理的边界AS 对互联网破坏力很小。与之对应的印尼ID、捷克CZ、新西兰NZ 对一些区域有较高的通信影响。

表4 通信服务影响力下部分区域边界AS 抗毁性排名数量

6 结束语

全球互联网的重要性与日俱增，网络拓扑是互联网通信的基础。本文采集多方数据，建立了较完善的区域粒度的网络拓扑。量化不同区域网络拓扑的抗毁性，定义显著性检验器，从内部拓扑和外部通信2 个方面对区域抗毁性进行排名并发现区域差异。后续工作将重点考虑发现并定位拓扑中薄弱点，精准给出区域拓扑优化建议。