IP-to-AS映射修正粒度的系统分析

摘 要：获得精确的IP-to-AS映射表，对于网络管理人员诊断网络故障和对于网络研究人员发现AS级网络拓扑有着重要的意义。一种获得IP-to-AS映射表的方法是基于traceroute路径和BGP 的AS路径是一致的假设，通过最大化匹配traceroute和BGP路径对的数量，来修正从路由表里提取的初始的IP-to-AS映射表。关于修正这个初始的IP-to-AS映射表，有两种粒度的修正方法，一种是/24前缀粒度的修正方法[1]，另一种是IP地址粒度的修正方法[2]。IP地址粒度的修正方法相比于前缀粒度的修正方法，可以大大提高路径对的匹配度。但是前缀粒度的方法和IP地址粒度的方法各有优缺点，本文提出了一种系统化的基于分类树的分析方法，可以系统、全面和定量的分析前缀粒度方法和IP地址粒度方法各自的优缺点。

关键词 ：因特网地址；自治域；映射；修正粒度

 

1 引言

    IP-to-AS旨在为IP (Internet Protocol，互联网协议) 地址认定使用该IP地址的AS（Autonomous System，自治域）。需要特别说明的是，对于一个IP地址来说，使用它的AS，并不一定是地址注册机构将它分配给的AS，而我们的IP-to-AS指的是IP地址和AS之间的使用与被使用关系，而不是IP地址和AS之间的分配与被分配关系。

    精确的认定IP-to-AS映射表对于网络管理人员诊断故障和对于网络研究人员发现AS级网络拓扑有着重要的意义。比如，traceroute可以跟踪源到目的所经过的路由器的接口IP地址，如果能够知道接口IP地址属于的AS号，则可以使网络管理人员更方便地去解决故障。另外，利用IP-to-AS映射表还可以将IP级别的traceroute路径映射到AS级别的traceroute路径，这对于网络研究人员发现AS拓扑有着重要意义：基于Traceroute发现AS级拓扑可以补充基于BGP（Border Gateway Protocol，边界网关协议）发现的AS级拓扑，且部署traceroute监测点比部署BGP监测点要容易的多，只要一台普通的主机就可以作为traceroute监测点，而部署BGP监测点要困难的很多。

    为得到精确的IP-to-AS映射表，目前有两类方法：一类是先用路由器别名解析得到IP地址到路由器的映射，然后再将路由器映射到AS；另一类是路径对匹配方法。路径对匹配方法的基本思想是，假设转发平面路径跟控制平面路径是一致的，即假设traceroute 路径跟对应的BGP AS Path (路径)是一致的，并从路由表里提取前缀和它的发起AS作为初始的IP-to-AS映射表，但这个初始的映射表由于多种原因是不准确的，如[3]中分析的原因。路径对匹配方法就是通过最大化traceroute-BGP 路径对的数量，去修正这个初始映射表。而本文针对的是路径对匹配方法。

    [1]基于转发平面路径跟控制平面路径是一致的假设，提出了一种动态规划算法，即通过最大化路径对匹配，以/24前缀为粒度，来修正初始的IP-to-AS映射表。我们称[1]的方法为前缀粒度的修正方法。基于/24的前缀粒度去修正IP-to-AS映射的动机是网络中一般最小的前缀分配单位是/24前缀。然而网络中有大量的反例，同一个/24前缀下不同的IP地址可能映射到不同的AS号。比如，边界路由器上的某个接口地址可能使用分配给它的邻居AS的地址，而这个/24前缀下的绝大多数地址还是被它的邻居AS使用；还有网络交换点（IXP，Internet Exchange Point），网络交换点的前缀甚至没有一个主体映射的AS，它被切成零碎的IP地址，供多个AS使用，少则几个AS，多则几百个AS。基于此， [2]提出了IP地址粒度的修正方法，同样是基于路径对匹配，仍采用[1]的算法框架，然而在traceroute-BGP的路径对匹配上，有了显著的提高。

    虽然IP地址粒度的方法比前缀粒度的修正方法在路径对匹配上有了显著的提高，然而显而易见，这两种方法各有优劣：(1) 如果一个错误的映射是前缀级别的，那么用前缀粒度的方法可以将这个/24前缀下的所有IP地址的映射都修正过来，即使有些IP地址没有被训练。而用IP地址粒度的方法仅能修正被训练的IP地址的映射，/24前缀下的其它的IP地址若未被训练，则无法修正。在这点上，前缀粒度比IP地址粒度有优势；(2) 然而如果一个错误的映射仅是IP地址级别的，前缀的粒度的方法要么无法修正它，要么就会把这个/24前缀下的其它IP地址的映射修改错误，这种情况显然是IP地址粒度有优势。

    为了全面的分析前缀粒度和IP地址粒度在修正IP-to-AS映射方法上的优劣，本文提出了一种系统化的基于分类树的分析方法，可以系统、全面和定量化的分析前缀粒度和IP地址粒度的优劣及其它特性。

    本文的组织结构如下，第二章介绍了本文相关的研究工作。第三章介绍了数据收集和处理的过程。第四章介绍了前缀粒度和IP地址粒度的IP-to-AS映射修正方法。第五章提出了分类树的分析方法。第六章基于分类树的分析方法，进行了实验评价，全面和定量化的分析前缀粒度的映射修正方法和IP地址粒度的映射修正方法。第七章对本文进行了总结。

 

2 相关工作

    关于traceroute-BGP路径对匹配上有如下相关工作。[4]指出IXP是导致traceroute-BGP 路径对不匹配的重要原因。[3]更全面的分析了traceroute-BGP 路径对不匹配的原因，并启发式的修正IP-to-AS 映射，但人工量大。于是[1]设计了一种系统化的修正IP-to-AS 映射的方法，但是以/24前缀作为粒度进行修改。最近几年，我们在[5][6]中定量化了traceroute-BGP 路径对不匹配的原因，同时也发现了[1]的缺陷，就是/24前缀的粒度仍然不足够精细。于是即针对[1]的缺陷， [2]中提出了一种IP地址粒度的修正方法，大大提高了路径对匹配度。但IP地址粒度和前缀粒度从定性分析上各有优劣，而本文就是要系统化、全面化和量化地去分析两者在修正IP-to-AS映射上的优劣。

 

3 数据收集

    数据收集的主要任务是（1）从路由表中提取初始的IP-to-AS映射表，这个初始的映射表有很多的错误映射，需要借助IP-to-AS映射修正方法进行修正。（2）收集traceroute探测包和相应的BGP路由表，处理成traceroute-BGP 路径对，IP-to-AS映射修正方法就是通过最大化匹配的路径对来修正初始的映射。（3）构造训练数据集、测试数据集和标准映射。

3.1 提取初始IP-to-AS映射表

    我们从Routeviews[7]和RIPE[8]上总计10个收集点下载2010年4月22日一天内的路由表。提取出路由表条目的前缀和发起AS，来构成前缀到AS的映射，这就是我们的初始的IP-to-AS映射表。

3.2 处理成traceroute-BGP 路径对

    为了能处理成traceroute-BGP路径对，我们需要traceroute监测点和BGP监测点在同一个AS。CAIDA[9]有以下四个traceroute监测点：nrt-jp (AS7660), she-cn(AS4538), jfk-us(AS6939)和lax-us(AS2152)，可在Routeviews[7]和RIPE[8]上找到这些traceroute监测点所在AS的路由表。我们使用2010年4月22日的Traceroute 数据和BGP路由表，处理成traceroute-BGP路径对，得到的路径对的概要信息如表1所示。处理成traceroute-BGP路径对的方法如下：首先在对应的BGP路由表中，查找traceroute路径的目的地址的最长匹配前缀，最长匹配前缀的AS Path，即该traceroute路径对应的控制平面的BGP AS Path。该traceroute的IP地址级别的路径和路由表里的BGP AS路径便构成一个traceroute-BGP路径对。

3.3 构造训练数据集、测试数据集和标准映射

    通过上一小节的处理，我们已经获得了以上四个监测点的traceroute-BGP 路径对。这一小节，我们将：(1) 构造训练数据集，用来训练IP-to-AS 映射表；(2) 并构造测试数据集，用来测试训练的IP-to-AS映射表的准确度，用使测试数据集的路径对达到的匹配度来衡量映射表的准确度；(3) 并为测试数据集构造标准映射表，来近似作为我们的正确的映射表。

   我们用其中三个监测点的路径对做训练数据集，剩下一个监测点的路径对做为测试数据集，共可得到四组训练和测试数据集。如表2所示。其中测试数据集剔除了大约2% 的IP地址粒度的方法也无法使其匹配的路径对，这部分路径对很可能是路由不稳定或者是受数据收集限制等因素导致的本身就不匹配的坏的路径对，因为这部分坏的路径对大约50%有三个以上的错误，显然是由两个不同的traceroute路径和BGP AS路径构成的。经过以上处理的测试数据集，在其上运行IP地址粒度的算法，可得到一个IP-to-AS映射表，使测试数据集100%匹配，这个IP-to-AS映射表，我们称作标准。

    映射表，即本文中，我们所指的正确的映射表。目前还不存在找到真正的正确IP-to-AS映射表的方法，而本文的分析需要这样正确的映射表，基于路径对匹配方法的假设，我们只能以路径匹配度来衡量IP-to-AS映射表的准确性，也就是说使路径对匹配度越高的IP-to-AS映射表我们就认为越准确。基于此，我们把我们构造的标准映射表近似看成是正确的映射表，因为我们构造的标准映射表可以使测试数据集的路径对100%匹配，没有其它映射表能达到更高的路径对匹配度。

4 IP-to-AS映射方法

    本章在4.1中介绍了前缀粒度和IP地址粒度的IP-to-AS映射修正方法，在4.2中对这两种粒度的方法的优劣进行了定性的分析。

4.1 前缀粒度和IP地址粒度的IP-to-AS映射修正方法

    路径对匹配方法修正映射的目标是：最大化路径对的匹配数量，但是还不存在最大化路径对匹配数量的最优解算法，前缀粒度和IP地址粒度的IP-to-AS映射修正方法都是启发式的方法。前缀粒度和IP地址粒度的修正方法的算法框架是相同的，本质的区别就是修改的粒度。算法的框架都是[1]中的动态规划加迭代修正的框架。

    算法框架是：首先面向每一个路径对用动态规划算法求最佳匹配，最佳匹配是指将traceroute路径上的IP地址匹配到对应的BGP AS path的AS号，并且使这个IP-to-AS匹配关系跟当前的IP-to-AS映射相比有最少数量的不一致；然后综合全部的路径对的最佳匹配，决策出IP地址应该映射到的AS，如果与当前的映射不相同，则更新映射表。若映射表发生变化，再以新的映射表为起始点，进行下一轮迭代，直到映射表没发生变化为止。初始的IP-to-AS映射表作为迭代的起始点。

    [1]中的前缀粒度的方法，为了缓和前缀粒度的缺陷，允许一个/24前缀映射到两个及以上的AS号，但这会导致映射的模糊性。本文重点分析的是前缀粒度和IP地址粒度的优劣，为了保证对比的公平性，本文中进行比对的前缀粒度的方法，只允许一个/24前缀映射到一个唯一的AS，这个AS是使路径对匹配最多的那个AS；IP地址粒度的方法也同样的使一个IP地址只映射到一个AS。

    本文的重点是分析IP地址粒度和前缀粒度的方法的优劣，而不是算法本身。由于空间有限，对于这两个方法本文仅作简要说明，详细的方法细节请参见[1][2]。IP地址粒度和前缀粒度的方法一次迭代过程如下：首先为所有的路径对求最佳匹配，同一个IP地址，在不同的路径对中最佳匹配的AS可能不同，每个最佳匹配过的AS都是候选AS。然后为每个IP地址统计候选AS的集合及候选AS得分。一个IP地址的候选AS集合即该IP地址在所有路径对上最佳匹配的AS的并集；候选AS得分，即该候选AS在多少路径对中，是该IP地址的最佳匹配。IP地址粒度的方法以IP地址（/32前缀）为粒度修改映射，每个IP地址都选择映射到它的得分最高的那个候选AS。前缀粒度的方法以/24前缀为粒度修改映射，每个/24前缀都选择映射到它的得分最高的那个候选AS。如表3举例说明了IP地址粒度和前缀粒度的方法是如何修改映射的。我们下面对表3进行一下解释，在表3中有一个/24前缀: 5.5.5.0/24，初始映射为AS0，该前缀在训练数据集中有三个IP地址，分别为IP1、IP、IP3。各个IP地址的候选AS及得分如表3的第三行，第四行所示。IP地址粒度的方法选择的映射是：IP1->AS1; IP2->AS2; IP3->AS3。而前缀粒度的方法是以/24前缀为修改粒度，5.5.5.0/24的候选映射是AS1、AS2、AS3，得分依次是79+1=80，2+13=15，5。所以前缀粒度的方法使5.5.5.0/24映射到得分最高的AS1。

4.2 前缀粒度和IP地址粒度优劣定性分析

    前缀粒度的方法将前缀上的IP地址绑定在一起训练，是一种紧耦合的方法。IP地址粒度的方法针对离散的IP地址进行训练，是一种松耦合的方法。这两种方法各有优劣，如在引言中分析的。本节我们以前缀粒度为例，说明前缀粒度的优点和弱点，与之相反的就是IP地址粒度的弱点和优点。结合训练数据集和测试数据集进行分析，前缀粒度的优点和弱点如下：

    前缀粒度弱点：前缀粒度的方法将/24前缀上的IP地址绑定在一起映射到同一个AS号，但其中有些IP地址可能映射到其它不同的AS号，前缀粒度的方法无法将这些例外的IP地址的映射修正正确；而IP粒度方法针对单个IP地址进行修正却可以。前缀粒度方法的这种弱点我们成为前缀绑定缺陷。

    前缀粒度优点：如果IP地址的初始映射是错误的，但这些IP地址不在训练数据集中，前缀粒度的方法以24前缀为粒度进行修改，或许可以将它们一并修正；而IP地址粒度的方法以IP地址为粒度进行修正，却肯定不可以。前缀粒度的方法的这种优点，我们称作前缀的粗粒度优势。

 

5 分类树分析方法

    我们将测试数据集中的IP地址基于初始映射、训练映射、标准映射进行分类分析。初始映射表是指从路由表直接提取出来的前缀和发起AS之间的映射，记作OM （Original Mapping）。训练映射表是指用前缀粒度的方法或者IP地址粒度的方法修正之后得到的映射表，记作TM（Trained Mapping）。标准映射表是指使测试数据集100%匹配的映射，记作SM（Standard Mapping）。OM[IP]，TM[IP]，SM[IP]分别返回IP在各自的映射系统中映射到的AS号。Pre[IP]返回IP的/24前缀。

    分类原则：（1）IP地址是否在训练数据集中；对于前缀粒度的方法，还需要考察IP地址的/24前缀是否在训练数据集中；（2）IP地址的映射是否被修改，即TM[IP]是否等于OM[IP]；（3）IP地址的映射是否被修改正确，即TM[IP]是否等于SM[IP]；（4）初始映射是否正确，即OM[IP]是否等于SM[IP]。

    基于以上分类原则，对于IP地址粒度的方法，可以将测试数据集中的IP地址分成7类，如图1所示。对于前缀粒度的方法，可以将测试数据集中的IP地址分成12类，如图2所示。对每一类型的IP地址我们都做以下两种操作：（1）计算相对初始映射的增益。即起初所有的IP地址都用初始映射，然后将相应类型IP地址的初始映射替换成训练得到的映射，使测试数据集中的路径对提高的匹配度。如果正值，则表示相比于初始映射提高了匹配度，负值则表示相比于初始映射降低了匹配度。相对初始映射的增益反映了训练方法修正初始映射的多与少，修正的越多其值越大，且是正值，若错误的修改越多，其绝对值也越大，但是负值。（2）计算相对标准映射的增益。即起初所有的IP地址都用标准映射，然后将相应类型的IP地址的标准映射替换成训练得到的映射，使测试数据集中的路径对提高的匹配度。由于标准映射匹配度是100%，所以替换后，匹配度必然相等或降低，即增益都是零或负值。相对于标准映射的增益，反映了训练方法还有多少映射没有修正。下面介绍分类树中每种类型的IP地址的含义。

    对于IP地址粒度的方法，分类树中各个类型的的含义如下：

?类型1：IP地址在训练数据集中，初始映射是错误的，进行了修改，且修改正确。

?类型2：IP地址在训练数据集中，初始映射是正确的，但给修改错误了。

?类型3：IP地址在训练数据集中，初始映射是错误的，进行了修改，但没修改正确。

?类型4：IP地址在训练数据集中，初始映射是正确的，未进行修改

?类型5：IP地址在训练数据集中，初始映射是错误的，未进行修改。

?类型6：IP地址不在训练数据集中，自然没有修改它的映射，初始映射是正确的。

?类型7：IP地址不在训练数据集中，自然没有修改它的映射，但初始映射是错误的。

在前缀粒度的方法的分类树中，类型1到类型5跟IP地址粒度的方法的含义是相同的。类型1-2到类型7-2实际上根据/24前缀是否在训练数据集中，对IP地址粒度方法的类型6和类型7的进一步细分。类型1-2到类型7-2的含义如下所示。

?类型1-2：IP地址不在训练数据集中，但它的/24前缀在训练数据集中，初始映射是错误的，进行了修改，且修改正确。

 

6 实验评价

    我们首先在四组训练数据集中分别运行前缀粒度的方法和IP地址粒度的方法，得到它们各自训练的IP-to-AS映射表。这时初始映射表，训练映射表和标准映射表就都有了。然后利用分类树的分析方法，将测试数据集中的IP地址进行分类，并分别为每一类型的IP地址，计算相对初始映射的增益和相对标准映射的增益。

    对于IP地址粒度的方法，我们可以将测试数据集中的IP地址分成7类，而对于前缀粒度的方法，我们可以将测试数据集中的IP地址分成12类。按照第5章，初始映射增益和标准映射增益的计算方法，我们对IP地址粒度的方法和前缀粒度的方法，分别为各个类型IP地址的训练后的映射，计算相对初始映射和标准映射的增益，如表4和表5所示。单元格内的值就是对应类型的IP地址的相对初始映射或标准映射的增益。（注意：计算增益的路径对，都是指测试数据集中的路径对，而不是训练数据集中的路径对）。

    我们解释一下表4和表5中的两个特殊字段的含义。“全集IP”是指先将所有类型的IP地址并起来（即测试集的IP地址全集），再求整体的增益。“累加”是指先对单个类型的IP地址求增益，然后再将各个类型IP地址的增益进行累加。累加”的值略微小于“全集IP”的值，是因为有些路径对的不匹配是由两个不同类型以上的IP地址导致的，“全集IP”可以修正它们，而仅单个类型的不可以。“全集IP”和“累加”的值相近，说明绝大多数不匹配的路径对是由同一个类型内的IP地址导致的。而甚至实际上绝大多数路径对的不匹配仅是一个单独的IP地址导致的，因为大约80%的不匹配的路径对仅有一个错误。

    本文的假设是转发平面路径 (Traceroute路径)跟控制平面路径 (BGP AS Path)是一致的，基于这个假设，IP-to-AS映射使traceroute-BGP路径对匹配的越多，则我们就认为这个映射就越准确。结合分类树和相对初始映射和标准映射的增益，我们做如下几个分析。（1）定量化前缀粒度相比于IP地址粒度的劣势。（2）定量化前缀粒度相比于IP地址粒度的优势。（3）前缀粒度和IP地址粒度相结合的方法是否会更好。（4）其它类型的分析。

    为方便描述，我们定义如下几个函数。

?I_O(Type i): 对IP地址粒度的方法，类型i的IP地址的初始映射增益。

?P_O(Type i): 对前缀粒度的方法，类型i的IP地址的初始映射增益。

?I_S(Type i): 对IP地址粒度的方法，类型i的IP地址的标准映射增益。

?P_S(Type i): 对前缀粒度的方法，类型i的IP地址的标准映射增益。

6.1 定量化前缀粒度相比于IP地址粒度的劣势

    若一个/24前缀，初始映射为A，前缀粒度的方法将这个/24前缀的映射修正成了B，该前缀上的一个IP地址‘IP1’本应该映射到C，结果由于前缀的绑定缺陷，也将‘IP1’的映射修改成了B，表现在分类树中IP1对应类型3（IP地址出现在训练数据集中，初始映射是错误的，训练方法对其映射进行了修改但没有修改正确）。如果该前缀上还有一个IP地址‘IP2’，应该映射到A，也就是说初始映射本来就是正确的，但前缀粒度的方法却错误的将它的映射修改成了B。‘IP2’表现在分类树中对应类型2和类型2-2。

    若一个/24前缀，初始映射为A，用前缀粒度的方法训练后，仍保持该/24前缀映射到初始的A，但其上一个IP地址‘IP1’本应该映射到B，结果由于前缀的绑定缺陷，没能将其修改成B，仍使其是初始的映射A。‘IP1’表现在分类树上是类型5。

    类型3-2、类型5-2同类型3、类型5是相同的情况，但并未把这些类型列入前缀的绑定缺陷里，是因为类型3-2和类型5-2的IP地址并不出现在训练数据集中，即使IP粒度的方法也无法修正它们，因为根本就无法获得这些映射的信息，这根本上是训练数据集不够充分的原因导致的，而不仅仅是前缀绑定缺陷导致的。而类型 2-2却把它归入了前缀绑定缺陷，是因为其本身的映射是正确的，但前缀粒度的方法却把它给修改错误了。

    我们用两种粒度的方法相比于标准映射的差来衡量它们在类型3，类型5、类型2的差距。IP粒度的方法在类型2-2上的映射即初始映射，也是标准映射，所以可用前缀粒度的方法相比于初始映射的增益来衡量它们在类型2-2上的差距。

    所以前缀粒度的方法相比于IP地址粒度的方法的劣势，用路径对来衡量的话，计算公式为：I_S(Type 3) - P_S(Type 3) + I_S(Type 5) - P_S(Type 5) + I_S(Type 2) - P_S(Type 2) - P_O(Type 2-2)。

    利用上面的计算公式，我们为四组数据集分别计算前缀粒度的方法相比于IP地址粒度的方法的劣势定量值，依次是：12.15% (第一组), 8.84% (第二组), 11.24% (第三组), 13.80% (第四组)。

    除了总和的定量值之外，我们还对四种类型的前缀绑定缺陷进行了单独分析。奇怪的是，唯独在类型2上，IP地址粒度的方法反而比前缀粒度的方法差（表现在IP地址粒度的方法距离标准映射的差距大于前缀粒度的方法距离标准映射的差距），这是因为IP地址粒度的方法比前缀粒度的方法修改要更加敏感，会导致较多的修改错误，但从表4和表5可以看出，这个差距非常的小。另外，我们还发现前缀绑定缺陷的劣势主要表现在类型3上，而类型2和类型5的比例非常小，为什么会这样，还需要进行更加深入的研究，或许可以发现一些新的现象。

6.2 定量化前缀粒度相比于IP地址粒度的优势

    若一个/24前缀，初始映射为A，将这个/24前缀的映射修正成了B，该前缀上的一个IP地址‘IP1’，‘IP1’也应该映射到B，但‘IP1’不在训练数据集中，IP地址粒度的方法自然无法修正‘IP1’的映射，而前缀粒度的方法可以。‘IP1’表现在分类树上是类型1-2（IP地址不在训练数据集中，但它的/24前缀在训练数据集中，初始映射是错误的，进行了修改，且修改正确）。

    所以，前缀粒度的方法相比于IP地址粒度的方法的优势，用路径对来衡量的话，可用前缀粒度的方法在类型1-2上相对初始映射的增益来衡量，即：P_O(Type 1-2)。在四组数据集中，前缀粒度方法相比于IP地址粒度方法优势的定量值依次是：0.69% (第一组), 0.42% (第二组), 0.71% (第三组), 1.46% (第四组)。

6.3 前缀粒度方法和IP地址粒度方法相结合的映射是否会更好

    本节将回答这个问题：将前缀粒度方法修正的/24前缀粒度的映射和IP地址粒度方法修正的/32前缀(IP地址)粒度的映射结合在一起是否会更好。

    将前缀粒度的映射和IP地址粒度的映射结合在一起，采用最长前缀匹配原则。查找一个IP地址的映射会优先匹配/32的前缀(IP粒度方法的映射)，若没有匹配的/32前缀，再查找/24前缀粒度的映射。这样对在训练数据集中的IP都会采用IP粒度修正的映射，对不在训练数据集中的IP会采用前缀粒度修正的映射。

    然而对不在训练数据集中的IP地址，前缀粒度的方法既可能将错误的映射修正正确（对应分类树类型1-2），但也可能将本来正确的映射修改错误（对应分类树类型2-2），综合来说，两种粒度的方法相结合的映射是否比IP粒度方法修正的映射效果好，取决于P_O (Type 1-2) + P_O (Type 2-2)的值，若为正值，则说明两种粒度结合起来会更好，否则说明两种粒度结合起来还不如仅IP地址粒度的。

    从表5可以看出，第一组和第二组数据集，前缀粒度方法和IP地址粒度方法两种结合的映射不如仅IP地址粒度的方法修正的映射；而第三组和第四组数据集，前缀粒度方法和IP地址粒度方法两种结合的映射要好于仅IP地址粒度的方法修正的映射。所以仅/24前缀粒度和IP地址粒度仍然是不足够的，应该探索多种不同粒度的映射修正方法，以适当的粒度去修正相应的映射。

6.4 其它类型分析

    类型1反映了方法修正映射的能力，相对初始映射的增益越大，说明其修正的映射越多。从表4和表5可以看出，在类型1相对初始映射的增益上，IP地址粒度的方法比前缀粒度的方法要高出7.07%~12.43%的路径对匹配。类型1-1仅可以反映前缀粒度的方法修正不在训练数据集中的IP地址的映射的能力，IP地址粒度的方法没有这个能力，但前缀粒度方法的这个能力非常小，仅修正了0.42%~1.46%的路径对匹配。

    从表5我们可以看出，前缀粒度方法还有大量的（1.42%~21.30%）无法匹配的路径对集中在类型3-2。类型3-2跟类型3类似，类型3-2的IP地址的映射跟它的/24前缀的主体映射不一致，所以即使增加训练数据集中，使类型3-2的IP地址出现在训练数据集中，前缀粒度的方法仍然会因为前缀粒度的绑定缺陷而无法修正它们，只有用IP地址粒度的方法才可以很好的修正它们。同样，类型5-2也是如此，只是类型5-2对应的无法匹配的路径对比例很小。

    类型4，类型4-2，类型6是初始映射就正确的IP地址，且训练后依然保持正确，反映了方法的真阴性。

 

7 结论

    本文通过建立分类树，系统、全面的分析了/24前缀粒度的修正IP-to-AS映射方法和IP地址粒度的修正IP-to-AS映射方法。前缀粒度的方法将同一个/24前缀的IP地址绑定在一起映射到同一个AS，在前缀粒度方法的这种绑定缺陷上，用路径对匹配度来衡量的话，前缀粒度的绑定缺陷导致 8.84%~13.80%的路径对匹配损失。但前缀粒度的方法有修正不在训练数据集中的IP地址的映射的能力，在前缀粒度方法的这种粗粒度优势上，用路径对匹配度来衡量的话，前缀粒度的粗粒度优势可以增加0.42%~1.46%的路径对匹配。由此可见，前缀粒度的绑定缺陷远远大于前缀粒度的粗粒度优势，与之相应的，在修正映射的能力上，IP地址粒度方法自然远远大于前缀粒度方法。

 

参考文献

[1] Z. M. Mao, D. Johnson, J. Rexford, J. Wang, and R. H. Katz, “Scalable and accurate identification of AS-level forwarding paths,” in Proc. INFOCOM 2004, 2004.

[2] Baobao Zhang,Jun Bi, Yangyang Wang, Yu Zhang, Jianping Wu, “Revisiting IP-to-AS mapping for AS-level traceroute”, in Proc. CoNEXT 2011 Student Workshop, December 2011

[3] Z. Morley Mao, Jennifer Rexford, Jia Wang, and Randy Katz, “Towards an Accurate AS-level Traceroute Tool,” in Proc. SIGCOMM, September 2003.

[4] Y. Hyun, A. Broido, and kc claffy, “Traceroute and BGP AS path incongruities,” CAIDA, Tech. Rep., 2003.

[5] Yu Zhang, Ricardo Oliveira, Hongli Zhang, Lixia Zhang , "Quantifying the Pitfalls of Traceroute in AS Connectivity Inference", in Proc. PAM 2010, April 2010.

[6] Yu Zhang, Ricardo Oliveira, Yangyang Wang, Shen Su, Baobao Zhang, Hongli Zhang, Lixia Zhang, "A Framework to Quantify the Pitfalls of Traceroute in AS-level Topology Measurement", IEEE Journal of Selected Areas in Communications (JSAC), 2011, 29(9): 1822 - 1836

[7] BGP routing tables: http://archive.routeviews.org/

[8] BGP routing tables: http://www.ripe.net/data-tools/stats/ris/ris-raw-data

[9] Traceroute probes: https://topo-data.caida.org/team-probing/