基于谱聚类的路由IP地理定位方法

陈嘉欣，许 博，胡 超，张国敏，王占丰

(1.陆军工程大学 指挥控制工程学院，江苏 南京 210007；2.南京莱克贝尔信息技术有限公司，江苏 南京 210007)

0 引言

IP的地理定位是将IP地址映射到连接互联网设备的真实地理位置信息。IP定位虽然定位精度低于GPS定位,但是由于不需要双方协作且具有更好普适性,目前已被广泛应用于网络服务优化、网络定向广告和网络安全监管等领域[1]。

获取更加精准的IP地理位置信息依然是当前研究的重点,目前IP地理定位技术主要包括3类方法:数据库查询、数据挖掘以及网络测量[2]。基于数据库查询的方式速度更快,诸多商业数据库提供在线和离线接口便于用户进行查询,主要包括IP2location[3]、Maxmind[4]、IPIP[5]、IP138[6]、Chunzhen[7]和IPCN[8]等。基于数据挖掘的定位方法需要查询IP关联的主机名、域名和网站等信息,并以此推断其地理位置信息,如利用IP关联网站文本数据和反向DNS主机名找寻其中可能包含的地理信息[9-10],或者是利用客户端应用程序,收集用户上报的IP和地理位置信息等,如利用搜索引擎点击日志信息改进IP地理定位[11]。相较前2种方法,基于网络测量的IP地理定位方法通用性更强,也是目前主要的研究方向。这类方法通过网络测量收集探测源和目标之间的时延、拓扑等相关信息,结合大量地标节点,构建条件约束模型,从而推断测量目标IP的地理位置信息。目前典型的网络测量IP定位方法主要包括基于约束的地理定位(Constraint-Based Geolocation,CBG)[12]、基于网络拓扑的地理定位(Topology Based Geolocation,TBG)[13]、Octant[14]和街道级地理定位(Street-Level Geolocation,SLG)[15]等。

尽管目前的IP定位商业数据库宣称其精度和准确性较高,但依然存在着部分IP地理位置缺失和错误的情况,特别是路由IP定位准确率较低[16]。目前主流的IP地理定位研究方法大多针对端IP,关于路由IP定位的研究依然较少,且这些方法通常依赖于网络探测节点以及地标节点的位置和数量,导致在节点资源匮乏的情况下难以实现大规模路由IP地理定位。为了解决上述问题,本文主要在网络路径测量的基础上,利用有限的探测资源,结合开源的IP地理定位数据库,实现高准确度的大规模路由IP地理定位。

本文第1节详细分析了当前基于网络测量的几种典型IP地理定位方法,第2节介绍了定位方法基本思想,第3节详细介绍了该方法的设计与实现,第4节介绍了方法的实验评估结果,并与其他典型方法进行比较,第5节对全文进行了总结。

1 相关工作

目前许多研究表明,商业数据库在定位精度和准确度方面依然存在诸多问题,多个数据库之间在国家级别定位一致性较高,在其下级行政单位地理定位存在较大差异,特别是路由IP定位[16],因此通过定位数据库来进行IP地理定位存在较大的精度问题。而利用网络爬虫等技术采集的大量IP及其相关的地理位置信息数据较为纷乱和复杂,大量噪声数据也会影响判断结果,难以在较短的时间范围内得到准确的大规模IP地理定位结果,只能获取有限的定位数据,在实际应用过程中,常作为数据库的补充。

利用网络测量的方式是目前IP地理定位方法的主流,网络测量主要是利用一些软硬件探针获取网络环境中的性能指标,包括时延、拓扑信息等。常见的网络测量工具有Ping和Traceroute。依据这些测量特性,目前的IP地理定位方法主要分为:基于时延测量的定位方法和基于路径测量的定位方法。

1.1 基于时延测量的定位方法

基于时延测量的定位方法基本原理在于测量时延和地理距离的一致性约束原则,主要利用报文端到端的传输时间来估算2点间的距离,其具体传输速度约为光速的2/3[17],如通过Ping工具即可获取端到端ICMP报文往返时延。

基于时延测量目前比较典型的是CBG方法[12]、Octant方法[14]以及GeoWeight方法[17]。其中CBG方法利用分布式的测量方式,将多个测量源到目标地址的网络时延转换为地理距离约束,基于该多边化的距离约束机制从而估计目标主机所在地理区域,并将区域的质心作为目标的点估计。此外,CBG方法假设时延和地理距离之间满足一定的线性关系,并据此利用多个测量源之间的互测网络时延,拟合出整体失真最小的最佳线性关系。据此线性关系预估探测目标IP同多个探测源节点之间的距离,以该距离为半径,源地标节点为圆心绘制维恩图,将其中交叉区域作为目标IP的估计地理位置。

Octant方法在CBG方法的基础上,将距离的最大界限定义为正约束和负约束,正约束表示目标节点到测量节点的最远距离,负约束则表示最近距离。从图形上看则是将原先的圆形区域限制在了一个环形区域内,从而减少了目标区域范围,提升了定位精度。

GeoWeight方法则是在以上2种方法的基础上做了改进,该方法利用统计学的思想,依据探测节点获取的时延-距离信息,将原本的圆形区域进一步划分成n个等距的环形区域,每一个区域依据概率大小设置不同的权重,来自多个地标的时延测量将产生交叉区域,每个交叉区域中有不同数量的重叠环形区域。每个相交区域的最终权值为相交区域的权值之和。将权重最大的区域作为目标的约束区域,并将该区域的质心估计为目标位置。

1.2 基于路径测量的定位方法

网络路径测量是获取网络路由IP的重要方式,网络数据包通常从源端经过多个路由器转发才能到达目的地,该类方法利用Traceroute等探测工具获取经过的每一跳路由的基本信息,并分析其网络路径上的典型特征,结合可靠地标节点地理位置信息从而实现对目标IP的定位。

此类方法按照定位侧重点主要分为端IP定位和路由IP定位。

① 端IP定位

TBG方法主要解决探测源距离目标节点较远的情况下,时延测量定位结果误差较大的问题。使用Traceroute工具获取源端到目标主机之间经过的路由IP以及单跳时延,利用时延的强弱时延约束条件,对路由IP进行地理定位,再利用路由IP充当新的地标节点对目标IP进行定位。TBG有效减少了地标和目标主机之间相距较远导致的定位误差,利用网络拓扑结构以及强弱约束条件实现路由器级别的地理定位,进一步验证目标IP的定位结果,提高了定位精度。

SLG方法则在CBG方法的基础上进一步提升了精度,面向街道级进行IP定位。该方法采用“逐层逼近”的思想,利用路径测量的局部时延分析路由、地标以及目标节点三者之间的时延-距离约束关系,从而实现街道级定位。

② 路由IP定位

关于大规模路由IP地理定位的问题,Tian等[18]提出了一种基于网络拓扑地理聚类的启发式定位方法,改进现有的地理定位数据库。该方法从网络拓扑的边缘路由出发,逐渐逼近位于网络核心的骨干路由,主要步骤包括:单路由集群、非骨干路由集群、骨干路由集群以及合并小集群,采用集群内部定位投票的方式获取该集群的地理位置。该方法一定程度上解决了探测节点依赖的问题,并改进了商业数据库的定位结果,但也由于投票规则过于简单、集群合并缺少依据,导致定位结果并不理想。

Li等[19]在此基础上提出了一种基于网络拓扑社区检测的IP地理定位方法(NCC),该方法主要包括:获取完整路径、构建网络拓扑、分离骨干网与非骨干网、社区发现、投票定位社区和目标IP定位这6个步骤,其中社区发现采用Louvain方法,通过模块度优化和网络凝聚这2个阶段实现聚类,模块度是一种常见的用来衡量社区划分强度的度量值,模块度越接近1,社区的划分效果越明显。相较而言,NCC定位方法的通用性更好、容错率更低,但是该方法依然存在聚类方法特征不全、投票规则较为简单、无法适应非完整路径IP定位需求等问题。

近两年,Dan等[20]提出了一种基于路径测量定位传播的IP地理定位方法(TLP),该方法利用“IP范围插值”的概念,并将其与路径测量中“延迟邻居”相结合,用于IP地理定位。同一子网范围内的IP地址往往地理距离较近,IP范围插值则是在此基础上,若某个IP地址范围存在多个可靠地标IP,且地标IP的地理位置相对较近,则将地标IP地理位置中心作为整个IP范围的定位结果,从而扩大地标集,且评估结果表明,选取256大小的IP地址范围,准确性和覆盖率较高。同时利用Traceroute测量路径上延迟差小于阈值(如2 ms)的IP对(即延迟邻居)将地标地理位置传播到未知定位路由IP,进而实现路由IP地理定位推断。

2 算法基本思想

目前的路由IP地理定位方法所选特征相对单一,难以在探测节点资源匮乏等特殊情况下实现有效的IP地理定位。如NCC定位方法缺少测量时延这一重要特征,且投票规则较为简单,易产生错误聚类的情况;而TLP方法中“IP范围插值”的概念过于简化地标节点扩散方式,且在探测时延较大的情况下,时延地理一致性约束原则易受影响,难以实现大规模路由IP地理定位。

基于该现状,本文结合IP所属自治域系统(Autonomous System,AS)相关信息,利用谱聚类算法实现对路由IP地址的地理定位。

2.1 AS路径的地理约束性

IP地理定位通常借助于网络时延的约束性,即利用时延与地理距离的线性映射关系来估计地理距离的远近[21],但这种方式易受迂回路径和时延抖动的影响,造成时延约束性减弱。在此基础上,本文采用AS路径的地理约束性进一步优化IP地理定位。

受网络业务提供商(ISP)之间商业关系的约束,互联网的AS路径通常满足“无谷底”路径模式(Valley-Free Path Model),即一个AS不能在它的2个提供商AS(对等AS)之间转发流量,这也导致了AS路径具有严格的层次关系和逻辑级别,通常情况下路由选路满足从接入路由到骨干路由再到接入路由的过程,骨干路由又分为省际和省内骨干,致使AS路径的逻辑级别往往与行政区域划分一致[22]。对于国内的网络而言,一个大型ISP通常包括省际和省内骨干网,省内又包含诸多城域网,这些骨干网络对应着不同级别的自治域,并按照级别从低到高再到低的顺序进行流量转发,这也意味着AS路径本身与行政区域级别保持一致,相同的AS路径通常对应着相同的目标区域。

以广东省的目标IP探测结果为例,其中探测节点选取的是中国山东省移动网络服务器,经过AS24444(中国移动)—AS9808(移动骨干网)—AS4837(联通骨干网)—AS17623(中国联通)这一AS路径的目标IP地址主要位于“中国广东省深圳市”。

探测过程中主要经过的AS路径示意如图1所示。

图1 AS路径示意Fig.1 Schematic diagram of AS path

2.2 算法框架

基于上述发现,本文在此基础上提出了一种基于谱聚类的路由IP地理定位(Spectral Clustering Based Router IP Geolocation,SCRG)方法,相比于现有的NCC和TLP方法,SCRG方法主要优势体现在以下方面:

① 采用了谱聚类算法:加入路径时延特征,利用谱聚类算法代替“延迟邻居”定位传播方式合并IP节点。谱聚类算法可以构造稀疏相似矩阵,对较大数据集表现优于其他算法,同时能够在任意形状的样本空间上聚类,相比于NCC方法中的Louvain算法,不容易将较小的簇合并。

② 引入了AS路径概念:相同的AS路径其目的地通常较为接近,利用网络测量路径上的AS及组织信息可对聚类结果做进一步处理,从而划分较大的簇以及合并较小的簇,这也是目前主要的IP地理定位方法容易忽略的路径特征信息。

③ 设计了簇内投票机制:对簇内路由IP利用多数据库对比定位结果作为投票基准,通常容易出现投票冲突的情况,即簇内无明显票数优势的地理位置信息,SCRG方法选取其中票数最高的3个地理位置作为候选,将候选位置分别代入到其所在的测量路径上,若满足更多无迂回城市(如出现北京—上海—北京的路由线路)路径的情况,则将其作为最优投票结果。

SCRG方法主要步骤如图2所示。

图2 SCRG方法主要步骤Fig.2 Main steps of SCRG method

其中,IP活跃性探测采用Zmap工具[23],其作为开源扫描工具,Zmap支持多种方式存活性探测,能够在极短的时间内完成大规模IP活跃性探测的任务。

在获取完活跃IP后,SCRG方法利用开源主动测量工具Scamper[24]进行Traceroute测量,该工具是由CAIDA组织开发使用的,用于替代原来的Skitter工具,支持自定义发包速度,同时提供ICMP、UDP、TCP和Paris-style等多种方式实现Traceroute测量,能够针对负载均衡的网络进行有效的IP地址发现,获取较为完整的网络拓扑结构。之后利用谱聚类算法对路由IP进行聚类,借助Routeviews[25]和RIPE RIS[26]两个开源数据查询IP所属AS信息并获取AS路径,通过AS路径对聚类簇做进一步划分与合并,最终利用簇内投票规则获取路由IP正确地理定位(详细内容见第3节)。

3 设计与实现

3.1 谱聚类

谱聚类是目前较为流行的聚类算法之一,因其良好的性能和简单的实现受到广泛的关注。谱聚类可以忽略样本空间的形状,在非凸数据集上也能聚类收敛到全局最优,谱聚类算法将数据集中的每个点视为图形的顶点,并将任意2个点之间的相似度视为连接2个顶点的边的权重,从而构造无向加权图。然后,根据图划分方法,将图划分为几个不相连的子图,子图中包含的点集就是聚类后生成的簇[27]。

通常谱聚类算法主要由3个部分组成:再处理、谱表示以及聚类,具体包括构建节点的相似矩阵以及图的拉普拉斯矩阵,然后选取特征向量进行聚类。

SCRG方法采用谱聚类算法对路由IP进行聚类,采用k-近邻法(KNN),即遍历所有的样本点,取每个样本最近的k个点作为近邻,从而构建图的相似矩阵W。相似矩阵W中各个元素采用式(1)计算得到:

(1)

式中:wij为路由节点xi和xj之间的相似度数值,disij为节点xi和xj之间的距离,在SCRG方法中可用路由IP之间的最短路径时延代替,时延越高,表示距离越远,相似度越低;σ为控制参数,通常取1。

L=D-1/2WD-1/2。

(2)

将Y的每一行当作一个点,使用近邻传播(AP)聚类将其划分为簇,将原始点xi分配给聚类j当且仅当矩阵Y的第i行分配给聚类j,利用AP聚类的“消息传递”机制可有效解决传统谱聚类算法的敏感初始化问题[28],相较于传统的k-均值算法或k中心点算法,AP聚类算法主要有以下5点优势:

① 无需手动指定最终聚类簇的个数;

② 并未生成新的簇中心,而是使用已有的点作为聚类中心;

③ 算法对数据的初始值不敏感;

④ 对数据相似度矩阵的对称性没有要求;

⑤ 算法结果的平方差误差较小。

3.2 簇划分与合并

由于探测得到的时延存在较大误差,路径上的不响应路由也会产生大量的中断路径,导致路由聚类的结果误差较大,存在大量内部节点过多和过少的簇,这也使得在下一步的投票过程中出现2种极端情况:

① 大量不同地理位置路由IP聚类成簇;

② 簇内IP过少导致投票步骤无法进行。

本文主要利用路由IP的AS路径同地理位置的一致性约束原则(见2.1节),对聚类簇做进一步划分与合并,具体处理流程如图3所示。

图3 簇划分与合并流程Fig.3 Cluster partitioning and merging process

首先,利用公共BGP快照的CIDR IP地址块(Routeviews[25]and RIPE RIS[26])查询所有路由IP的AS号,IP查询结果为空的AS号可用0替代。

其次,按照探测路径顺序构建每个路由IP所属AS路径,优先选取较为完整的AS路径作为该IP的特征信息。

在此基础上,针对聚类簇内IP,以其AS路径特征信息作区分,以簇平均大小C作为阈值,将节点数超过C的簇进一步划分成子簇。以广东省IP探测结果为例,聚类后的簇平均大小在100左右,对节点数超过100的簇按AS路径信息做进一步划分,表1为聚类簇A中挑选的部分路由IP及其AS路径,表2为其划分后的结果,将簇A划分成A1、A2和A3这3个子簇。

表1 聚类簇A中部分路由IP及AS路径

表2 簇A划分后的结果

其次为了提升后续簇内定位投票的效果,将内部IP节点数目小于5的簇合并至存在相同AS路径IP的其他簇中,合并的过程优先选取IP所属同一C类网段且地址较为接近的其他簇,这也是由于同一子网范围内的IP地址往往地理距离较近[20]。表3和表4分别为聚类簇合并前后的示例。

表3 待合并的聚类簇

表4 合并后的聚类簇

经过聚类簇的划分与合并之后,使得簇内节点数量相对更加合理,相比于其他定位方法只是依据集群的拓扑连接关系做简单的合并更具合理性,同时也无需划分骨干网和非骨干网进行聚类。

3.3 簇内投票

对于聚类后的每个簇ci=(x1,x2,…,xn),其中对每个IP节点xi查询IP138[6]、Chunzhen[7]和IPCN[8]数据库的定位结果,将2个及以上数据库定位一致的地理位置作为多库定位的结果,若3库均不相同,则随机选取其中定位精度达到城市级的地理位置作为该IP的多库定位结果。

其次,对簇内IP不同的地理位置进行投票,并按照票数由高到低进行排名,得到不同城市票数集合{Num(l1),Num(l2),…,Num(lk)},若Num(l1)/n≥1/2,则将l1作为该簇的定位结果,若Num(l1)/n<1/2,选取票数最高的3个地理位置{l1,l2,l3}作为候选结果。

通常情况下,从避免路由环路的角度来看,网络路径不太可能出现迂回城市的情况(如出现北京—上海—北京的路由线路),迂回情况的发生大概率是由于IP地理定位出错。因此将簇内定位的候选结果分别代入到测量路径中,得到城市级路由线路,将出现迂回城市路径最少的候选结果作为该簇的定位结果:

(3)

式中:Cli为出现迂回城市的路径数,li∈{l1,l2,l3}为候选的定位结果。

投票后聚类簇的定位结果作为簇内所有路由IP的最终定位结果,进而可以快速实现规模化的路由IP城市级地理定位。

4 实验评估

为了验证本文提出的SCRG定位方法的性能,利用位于山东省的2台移动网络服务器进行路径测量,测量采用的工具是Scamper,该工具支持Paris-style Traceroute探测。

实验所用到的IP地址数据是2023年3月15日纯真发布的免费IP库社区版,提取该数据库中国广东省的IP地址作为探测目标,其中广东省IP总数为37 770 954,活跃IP总数为3 409 280。共探测得到广东省路由IP总数为31 612,如表5所示。

表5 广东省各城市IP数(纯真数据库)

通过对路由IP地址进行定位,最终修改了16 949条路由IP定位结果,修改后的广东省各城市路由IP数如表6所示。

表6 重新定位后广东省各城市路由IP数

由表6可以看出,修改后的路由IP定位结果大多位于广州市,这也是由于多个数据库本身对于路由IP并未精确到城市级且大多位于广州市,导致聚类后簇内优先投票到广州市。

为了更好地说明SCRG方法的准确性和普适性,将其分别与NCC和TLP定位方法进行比较。此外由于TLP方法使用的测量数据和地标数据较为老旧,且地标数据难以直接获取,本文实验过程在现有测量数据的基础上对方法进行简单调整,选取3个商业数据库定位结果一致的端IP作为地标节点,执行插值的IP范围大小为256,即/24子网划分,而进行地理位置传播的延迟邻居选取时延差在2 ms以内的IP对。

定位结果显示,SCRG方法相比于NCC和TLP方法存在定位差异的路由IP分别为2 803条和 6 236条。本次实验利用IP站点Ping工具来验证路由IP的准确定位结果,选取Ping时延在2 ms以内的测量节点所在位置作为正确定位结果,实验每次随机选取20条不同定位的路由IP,共进行5次验证,验证结果如图4和图5所示,可以看出SCRG的定位正确率要明显高于NCC和TLP方法。

图4 与NCC不同定位路由IP的5轮样本验证结果Fig.4 5 rounds of sample verification results for rou- ter IP with different location from NCC

图5 与TLP不同定位路由IP的5轮样本验证结果Fig.5 5 rounds of sample verification results for router IP with different location from TLP

为了更好地说明定位效果,实验将广东省院校、政府单位IP地址及其所在城市作为可靠地标节点使用,IP地址为其官网域名解析的IPv4地址,最终获取374条可靠地标IP,其中院校IP 152条,政府单位IP 222条。这些地标IP经过路径测量,默认最后一跳路由IP的正确地理位置为地标节点所在城市。分别利用SCRG、NCC以及TLP方法进行多次聚类,并对最后一跳路由IP地址进行定位,最终定位的正确率如图6所示。

图6 最后一跳路由IP的不同方法定位正确率Fig.6 The accuracy of different methods for locating the last hop router IP

由图6可以看出,SCRG方法整体要优于其他2种定位方法,平均正确率达到87.1%。造成这一结果的原因可能在于NCC方法并未考虑路径时延信息,同时缺少有效的集群划分与合并方式,导致聚类结果并不准确;而TLP方法在测量资源和地标节点有限的情况下,仅仅依靠延迟邻居传播地理位置并不可靠,且对路由IP来说,即便属于同一网段,其依然可能位于不同城市,加上原文选取延迟邻居时,设置源到节点IP往返时延阈值上限为9 ms,也导致此方法难以适用于探测节点较远的路径测量数据。

5 结束语

本文旨在利用有限的资源实现大规模路由IP地理定位的过程,提出了一种 SCRG方法,该方法使用谱聚类算法,利用链路时延特征计算节点之间的距离,对整个网络路由拓扑进行聚类,利用IP社会属性,即AS路径信息实现大簇划分以及小簇合并,在此基础上提出一种簇内投票的冲突解决方式,获取最优投票结果,并将其作为整个簇内路由IP的正确定位结果。相较于NCC和TLP这2种定位方法,SCRG方法的聚类特征更加全面,投票规则更加合理,在探测节点和地标节点资源有限的情况下,对特定地标路由的定位结果的平均正确率达到87.1%,明显优于其他2种定位方法。在未来的研究工作中,计划利用数据挖掘方式获取更多的地标数据,结合地标IP的高精度定位结果,寻找与其潜在的相似性特征,从而实现区县级以及街道级的准确定位。