基于路由跳数的网络实体地标筛选

朱 光, 李 珂

(1.中原工学院 计算机学院， 河南 郑州 450007； 2.河南省档案局， 河南 郑州 450003)

网络实体定位，即获取网络实体IP地址与其地理位置之间的映射关系[1]。在互联网中，IP地址通常能够唯一标识一个网络实体，因此也称IP定位。随着网络空间安全领域逐渐受到重视，IP定位技术也发挥着重要的作用，如IP定位技术可以追踪网络敏感目标和锁定网络谣言散播者，为防恐维稳提供技术支持；IP定位技术可应用于商业领域中基于位置的服务；也可为电视节目、广播和数字音像的区域版权保护提供技术支持等。

现有的网络实体定位技术主要分为基于非测量方式和基于测量方式。前者利用互联网公开的IP数据库(如Whois、IP2Location等)查询IP地址的地理位置；后者测量探测源、地标(已知地理位置的网络实体)与目标之间的时延、拓扑等信息，从而估算出目标IP的地理位置，如GeoPing[2]、LBG[3]、Spotter[4]、CBG[5]、Octant[6]、SLG[7]算法等。

在上述基于测量的网络实体定位方法中，将地标所在位置作为目标的位置估计(即基于地标的网络实体定位技术)是获取高精度定位结果的重要方式之一[8]。然而，现有的网络实体地标采集与评估算法较少，主要有Strcuton[9]、基于Web与在线地图相结合的地标挖掘算法(简称基于Web的地标挖掘方法)[7]以及基于互联网论坛的地标挖掘算法[10]。

基于Web的地标挖掘算法是利用在线地图查询地理位置的方式实现Web网站的IP地址与其地理位置之间的映射，其算法流程见图1。在提供在线地图服务的网页中输入“公司”“大学”“政府”等组织机构的关键字和邮政编码后，地图服务器返回该邮政编码区域内的相关单位的网站域名，可将这些网站域名(或IP地址)与其地理位置建立映射关系。

图1 基于Web的地标挖掘方法流程

基于Web的地标挖掘算法获取的地标粒度为街道级，可满足高精度定位算法的需求，然而，由于Web服务器可能存在主机托管、共享主机以及CDN(Content Delivery Network)网络等情况，从在线地图中获取的域名与服务器的IP地址并不能保证一对一关系，且获取的地理位置与Web服务器所在的地理位置也不能保证一一对应。虽然，基于Web的地标挖掘算法中对存在上述问题的候选地标进行了评估，但效果并不理想，基于Web方式获取的网络实体地标精度虽高，但可靠性不能得到保证。

1 基于路由跳数的网络实体地标筛选算法

1.1 算法思想与原理架构

文献[11]和[12]指出，同一网络服务提供商在配置网络环境和路由转发策略时，数据包在骨干网上的转发路径往往相对稳定，即对于同一区域的数据包到达另一区域时，数据包所经历的路由路径往往相同或相似，由此通过多个探测源可量化出探测源到某个城市的路由跳数向量。

基于路由跳数的网络实体地标筛选算法原理架构如图2所示。首先，通过多个IP位置数据库获取候选地标可能所处的地理位置，并在这些位置部署相应的探测源，选取已知的高可靠的城市级地标为基准节点，测量探测源到所有基准节点的路由路径与路由跳数，统计出每个探测源到每座城市的平均路由跳数以及每座城市内部的平均跳数，为每一座城市建立跳数向量，称为基准跳数向量；然后，依据上述方法，对待评估的候选地标建立候选地标跳数向量；最后，计算基准跳数向量与候选地标跳数向量的相似度，将相似度最高的基准跳数向量所对应的城市作为候选地标的地理位置。

图2 基于路由跳数的网络实体地标筛选原理架构

1.2 算法步骤

输入：待评估的候选地标；

输出：筛选后的高可靠地标；

Step1：基准节点选取与探测源部署。通过现有的多个IP位置数据库获取候选地标可能所处的城市，选取一定数量的位于这些候选城市的高可靠网络实体地标为基准节点(应属于同一ISP)，基准节点在地理位置上应均匀分布，且位于不同网段。在部署探测源时，应在候选地标可能所在的城市周边均匀部署多个探测源(探测源与基准节点应属于同一ISP)，探测源的数量一般由用户对筛选精度的需求来确定。

Step2：路径测量与跳数统计。利用Traceroute工具，使探测源发送数据包，测量探测源到所有基准节点的路由路径，路由路径包含探测源到基准节点之间经过的所有路由器以及对应的跳数信息。针对任一探测源，根据路由路径分析，统计出该探测源到每座城市的平均路由跳数α以及每个城市内部的平均跳数δ。

计算α时，根据现有IP位置数据库查询方式确定每条路由路径中到达该城市的第一个路由器R，并将R之后的所有路径移除；然后统计探测源到路由器R之间的路由跳数进而计算出该探测源到每座城市的平均路由跳数α。计算δ时，将路由器R之前的所有路径移除，统计路由器R到基准节点之间的路由跳数，计算每座城市内部的平均跳数δ。

Step3：建立基准跳数向量。依据上述方法，确定每座城市的平均路由跳数α及每座城市内部的平均路由跳数δ。对任一城市，为每一个探测源建立到该城市的跳数向量Hi=(αi,(αi+δi))，其中，i表示第i个探测源，进而建立所有探测源到该城市的基准跳数向量。为便于计算，将每座城市的基准跳数向量记为DH，如式(1)所示，其中，m为探测源数量，i表示第i个探测源，其数量根据用户对筛选精度的需求而定，hi,1与hi,2分别为候跳数向量Hi中的两个元素。

DH=(h1,1,h1,2,…,hi,1,hi,2,…,hm,1,hm,2)

(1)

Step4：建立候选地标跳数向量。所有探测源发送探测包测量候选地标的路由路径，获取探测源到候选地标之间的路由跳数α以及城市内部的跳数δ，为候选地标的所有可能城市分别建立候选地标跳数向量Tj=(αj,(αj+δj))，其中j表示第j个探测源，α与δ的计算方法同Step2，进而为候选地标建立多个跳数向量DT，如式(2)所示，其中，k表示候选地标可能所处的第k座候选城市，m为探测源数量，tj,1与tj,2分别为候选地标跳数向量Tj中的两个元素。

DTk=(t1,1,t1,2,…,tj,1,tj,2,…,tm,1,tm,2)

(2)

Step5：候选地标筛选。计算候选地标跳数向量DTk和每座城市的基准跳数向量DH相似度，计算方法见式(3)，其中i表示第i个探测源。其中Ek为候选地标与第k座候选城市的误差值，将与Ek最小的基准跳数向量所对应的城市作为候选地标所在的城市，将候选地标宣称的地理位置与评估出来的位置进行比较，两者所处地理位置不一致的候选地标认为是可靠性低的地标，两者地理位置一致的候选地标认为是高可靠的地标，进而完成对候选地标的筛选。

(3)

2 实验结果及分析

为验证本文提出的基于路由跳数的网络实体地标筛选算法，以SLG与LBG定位算法为基准，采用两类地标集：传统的基于Web的地标挖掘算法得到的地标集(以下简称WBL)和本文算法对其筛选后的地标集(以下简称FWBL)，分别作为SLG与LBG定位算法的输入，对分布在6座城市的300个已知地理位置的目标IP进行定位，比较两种地标集对上述两种定位算法精度的影响。

2.1 SLG与LBG算法基本原理

SLG算法采用三层定位的思想逐层缩小目标的位置估计[7]。第一层利用改进的CBG算法为目标限定一个粗粒度区域。第二层在第一层估计区域的基础上，结合区域内的网络实体地标，计算地标与目标之间的相对时延，进一步缩小目标估计区域。首先，找到地标与目标相连的所有共同路由器，计算它们的相对时延。然后，将与目标相对时延最小的地标作为目标的位置估计。

LBG算法利用具有较低计算复杂度的朴素贝叶斯模型解决机器学习的分类问题[3]。该算法通过测量方式获取探测源到大量地标的往返时延和跳数信息，并将时延和跳数划分为不同的区间，根据划分后的区间，分别统计出探测源到地标的概率分布，并建立相应的概率分布模型。当定位目标时，利用探测源到目标的时延与跳数信息，并结合概率分布模型，将目标定位到符合该概率分布模型的区域。

2.2 候选地标评估

2.2.1 基准跳数向量计算

对中国主流的IP位置数据库QQWry(实验使用版本为2015.05.15版)、IP138和IPcn进行解析与比对，筛选出鹤壁、许昌、郑州、深圳、上海及西安等6座城市的所有网吧IP，保留IP位置数据库查询结果均处于同一城市的IP，挑选出IP地址16 828个(均属于中国电信)作为基准节点的样本集，利用部署在北京、杭州、青岛和深圳的4个探测源，在每天的不同时间段，对上述样本集进行重复测量，共计20次，获取探测源到16 828个基准节点的路由路径1 137 456条。统计出探测源到每座城市的平均路由跳数α以及每座城市内部的平均路由跳数δ，如表1所示。根据每座城市的α与δ构建鹤壁、许昌、郑州、深圳、上海及西安等6座城市的基准跳数向量，如表2所示。

表1 探测源到6座城市的平均路由跳数及城市内部平均路由跳数

表2 6座城市的基准跳数向量

2.2.2 候选地标跳数向量计算

通过基于Web的地标挖掘算法从上述6座城市采集与评估候选地标1 500个，构建WBL地标集，利用部署在北京、杭州、青岛和深圳4座城市的探测源，在每天不同时间段发送探测包对WBL地标集进行重复测量，共20次。获取探测源到WBL地标集的路由路径 117 659条，统计出每个候选地标的平均路由跳数α以及该地标所在城市内部的平均路由跳数δ。根据表2中每座城市的基准跳数向量，对每个待评估的WBL地标进行相似度比较。筛选后的WBL地标集称为FWBL地标集，WBL与FWBL地标集数量如表3所示。地标筛选前后的地理分布如图3所示。

2.3 定位结果比较

选取鹤壁、许昌、郑州、深圳、上海及西安等6座城市的可靠地标各50个，共计300个，作为待定位目标集。分别使用WBL地标集和FWBL地标集作为SLG算法及LBG定位算法的输入，对目标集进行定位，实验结果分别见表4和表5。

表3 WBL与FWBL地标集数量

(a-1)鹤壁筛选前的地标分布 (a-2)鹤壁筛选后的地标分布

(b-1)许昌筛选前的地标分布 (b-2)许昌筛选后的地标分布

(c-1)郑州筛选前的地标分布 (c-2)郑州筛选后的地标分布

(d-1)深圳筛选前的地标分布 (d-2)深圳筛选后的地标分布

(e-1)上海筛选前的地标分布 (e-2)上海筛选后的地标分布

(f-1)西安筛选前的地标分布 (f-2)西安筛选后的地标分布 图3 各城市地标筛选前后的地理位置分布比较表4 两类地标集对SLG算法定位的结果比较

城市WBL地标集定位正确数量准确率/%FWBL地标集定位正确数量准确率/%鹤壁43864690许昌45904896郑州44884896深圳43864794上海44884794西安43864588合计26287．3328193．67

由表4可知，SLG算法对300个目标定位实验中，WBL地标集定位正确数量为262个，准确率为87.33%；筛选后的FWBL地标集定位正确数量为281个，准确率为93.67%，相比于WBL地标集，提高了6.33%。因此，筛选后的地标能够提高SLG定位算法的准确率。通过对定位结果的误差分析可知，WBL产生的平均误差为51.98 km，中值误差为19.70 km，FWBL产生的平均误差为45.71 km，中值误差为10.28 km，FWBL的定位结果的误差明显小于WBL。因此，从定位精度上看，FWBL优于WBL。

表5 两类地标集对LBG算法定位的结果比较

由表5可知，LBG算法对300个目标进行定位实验中，采用WBL地标集定位正确数量为246个，正确率为82%；FWBL地标集定位正确数量为269个，正确率为89.67%，相比于WBL地标集，提高了7.67%。通过对定位结果的误差分析可知，WBL产生的平均误差为57.33 km，中值误差为23.42 km，FWBL产生的平均误差为49.61 km，中值误差为14.23 km，从定位精度上看，FWBL地标集优于WBL地标集。

3 结 语

针对基于Web的候选地标评估算法中难以对候选地标进行有效评估的问题，提出了一种基于路由跳数的网络实体地标筛选算法。实验结果表明：本文算法能够提高候选地标的可靠性，提高SLG定位算法及LBG定位算法的精度，为高可靠网络实体城市级地标提供了一种新的筛选与评估算法。

[1] Muir J A, Oorschot P C V. Internet geolocation: evasion and counterevasion[J]. ACM Computing Surveys, 2009,42(1):4.

[2] Padmanabhan V N,Subramanian L.An investigation of geographic mapping techniques for internet hosts[J].ACM SIGCOMM Computer Communication Review,2001,31(4):173-185.

[3] Eriksson B, Barford P, Sommers J, et al. A learning-based approach for IP geolocation[C]//Proceedings of the 11th International Conference on Passive and Active Measurement(PAM),Zürich,2010:171-180.

[4] Laki S,Mátray P,Hága P,et al.Spotter:A model based active geolocation service[C]//Proceedings of Interna-tional Conference on Computer Communications (INFOCOM),Shanghai,2011:3173-3181.

[5] Gueye B,Ziviani A,Crovella M,et al.Constraint-based geolocation of internet hosts[J].IEEE/ACM Transactions on Networking,2006,14(6):1219-1232.

[6] Wong B,Stoyanov I.Octant: a comprehensive framework for the geolocalization of internet hosts[C]//Usenix Conference on Networked Systems Design & Implementation,San Jose,CA,2007:23-23.

[7] Wang Y,Burgener D,Flores M,et al.Towards street-level client-independent IP geolocation[C]//Proceedings of Conference on Networked Systems Design and Implementation (NSDI),San Jose,CA,2011:27-27.

[8] 王占丰,冯径,邢长友,等.IP定位技术的研究[J].软件学报,2014,25(7):1527-1540.

[9] Guo C, Liu Y, Shen W,et al.Mining the Web and the in-ternet for accurate IP address geolocations[C]//Proceedings of International Conference on Computer Communications(INFOCOM),Rio de Janeiro,2009:2841-2845.

[10] Zhu G,Luo X Y,Liu F L,et al.An algorithm of city-level landmark mining based on internet forum[C]//Proceeding of the 18th International Conference on Network-Based Information Systems (NBiS),TaiPei,2015:294-301.

[11] Zhao F,Song Y H,LiuF L,et al.City-level geolocation based on routing feature[C]//Proceeding of the 29th International Conference on Advanced Information Networking and Applications (AINA),Gwangju,2015:414-419.

[12] Eriksson B, Barford P, Nowak R. Estimating hop distance between arbitrary host pairs[C]//Proceedings of IEEE Conference on Computer Communications (INFOCOM),Rio de Janeiro,2009:801-809.