基于譜聚類的路由IP地理定位方法

陳嘉欣，許 博，胡 超，張國(guó)敏，王占豐

(1.陸軍工程大學(xué) 指揮控制工程學(xué)院，江蘇 南京 210007；2.南京萊克貝爾信息技術(shù)有限公司，江蘇 南京 210007)

0 引言

IP的地理定位是將IP地址映射到連接互聯(lián)網(wǎng)設(shè)備的真實(shí)地理位置信息。IP定位雖然定位精度低于GPS定位,但是由于不需要雙方協(xié)作且具有更好普適性,目前已被廣泛應(yīng)用于網(wǎng)絡(luò)服務(wù)優(yōu)化、網(wǎng)絡(luò)定向廣告和網(wǎng)絡(luò)安全監(jiān)管等領(lǐng)域[1]。

獲取更加精準(zhǔn)的IP地理位置信息依然是當(dāng)前研究的重點(diǎn),目前IP地理定位技術(shù)主要包括3類方法:數(shù)據(jù)庫(kù)查詢、數(shù)據(jù)挖掘以及網(wǎng)絡(luò)測(cè)量[2]?；跀?shù)據(jù)庫(kù)查詢的方式速度更快,諸多商業(yè)數(shù)據(jù)庫(kù)提供在線和離線接口便于用戶進(jìn)行查詢,主要包括IP2location[3]、Maxmind[4]、IPIP[5]、IP138[6]、Chunzhen[7]和IPCN[8]等?；跀?shù)據(jù)挖掘的定位方法需要查詢IP關(guān)聯(lián)的主機(jī)名、域名和網(wǎng)站等信息,并以此推斷其地理位置信息,如利用IP關(guān)聯(lián)網(wǎng)站文本數(shù)據(jù)和反向DNS主機(jī)名找尋其中可能包含的地理信息[9-10],或者是利用客戶端應(yīng)用程序,收集用戶上報(bào)的IP和地理位置信息等,如利用搜索引擎點(diǎn)擊日志信息改進(jìn)IP地理定位[11]。相較前2種方法,基于網(wǎng)絡(luò)測(cè)量的IP地理定位方法通用性更強(qiáng),也是目前主要的研究方向。這類方法通過(guò)網(wǎng)絡(luò)測(cè)量收集探測(cè)源和目標(biāo)之間的時(shí)延、拓?fù)涞认嚓P(guān)信息,結(jié)合大量地標(biāo)節(jié)點(diǎn),構(gòu)建條件約束模型,從而推斷測(cè)量目標(biāo)IP的地理位置信息。目前典型的網(wǎng)絡(luò)測(cè)量IP定位方法主要包括基于約束的地理定位(Constraint-Based Geolocation,CBG)[12]、基于網(wǎng)絡(luò)拓?fù)涞牡乩矶ㄎ?Topology Based Geolocation,TBG)[13]、Octant[14]和街道級(jí)地理定位(Street-Level Geolocation,SLG)[15]等。

盡管目前的IP定位商業(yè)數(shù)據(jù)庫(kù)宣稱其精度和準(zhǔn)確性較高,但依然存在著部分IP地理位置缺失和錯(cuò)誤的情況,特別是路由IP定位準(zhǔn)確率較低[16]。目前主流的IP地理定位研究方法大多針對(duì)端IP,關(guān)于路由IP定位的研究依然較少,且這些方法通常依賴于網(wǎng)絡(luò)探測(cè)節(jié)點(diǎn)以及地標(biāo)節(jié)點(diǎn)的位置和數(shù)量,導(dǎo)致在節(jié)點(diǎn)資源匱乏的情況下難以實(shí)現(xiàn)大規(guī)模路由IP地理定位。為了解決上述問題,本文主要在網(wǎng)絡(luò)路徑測(cè)量的基礎(chǔ)上,利用有限的探測(cè)資源,結(jié)合開源的IP地理定位數(shù)據(jù)庫(kù),實(shí)現(xiàn)高準(zhǔn)確度的大規(guī)模路由IP地理定位。

本文第1節(jié)詳細(xì)分析了當(dāng)前基于網(wǎng)絡(luò)測(cè)量的幾種典型IP地理定位方法,第2節(jié)介紹了定位方法基本思想,第3節(jié)詳細(xì)介紹了該方法的設(shè)計(jì)與實(shí)現(xiàn),第4節(jié)介紹了方法的實(shí)驗(yàn)評(píng)估結(jié)果,并與其他典型方法進(jìn)行比較,第5節(jié)對(duì)全文進(jìn)行了總結(jié)。

1 相關(guān)工作

目前許多研究表明,商業(yè)數(shù)據(jù)庫(kù)在定位精度和準(zhǔn)確度方面依然存在諸多問題,多個(gè)數(shù)據(jù)庫(kù)之間在國(guó)家級(jí)別定位一致性較高,在其下級(jí)行政單位地理定位存在較大差異,特別是路由IP定位[16],因此通過(guò)定位數(shù)據(jù)庫(kù)來(lái)進(jìn)行IP地理定位存在較大的精度問題。而利用網(wǎng)絡(luò)爬蟲等技術(shù)采集的大量IP及其相關(guān)的地理位置信息數(shù)據(jù)較為紛亂和復(fù)雜,大量噪聲數(shù)據(jù)也會(huì)影響判斷結(jié)果,難以在較短的時(shí)間范圍內(nèi)得到準(zhǔn)確的大規(guī)模IP地理定位結(jié)果,只能獲取有限的定位數(shù)據(jù),在實(shí)際應(yīng)用過(guò)程中,常作為數(shù)據(jù)庫(kù)的補(bǔ)充。

利用網(wǎng)絡(luò)測(cè)量的方式是目前IP地理定位方法的主流,網(wǎng)絡(luò)測(cè)量主要是利用一些軟硬件探針獲取網(wǎng)絡(luò)環(huán)境中的性能指標(biāo),包括時(shí)延、拓?fù)湫畔⒌?。常見的網(wǎng)絡(luò)測(cè)量工具有Ping和Traceroute。依據(jù)這些測(cè)量特性,目前的IP地理定位方法主要分為:基于時(shí)延測(cè)量的定位方法和基于路徑測(cè)量的定位方法。

1.1 基于時(shí)延測(cè)量的定位方法

基于時(shí)延測(cè)量的定位方法基本原理在于測(cè)量時(shí)延和地理距離的一致性約束原則,主要利用報(bào)文端到端的傳輸時(shí)間來(lái)估算2點(diǎn)間的距離,其具體傳輸速度約為光速的2/3[17],如通過(guò)Ping工具即可獲取端到端ICMP報(bào)文往返時(shí)延。

基于時(shí)延測(cè)量目前比較典型的是CBG方法[12]、Octant方法[14]以及GeoWeight方法[17]。其中CBG方法利用分布式的測(cè)量方式,將多個(gè)測(cè)量源到目標(biāo)地址的網(wǎng)絡(luò)時(shí)延轉(zhuǎn)換為地理距離約束,基于該多邊化的距離約束機(jī)制從而估計(jì)目標(biāo)主機(jī)所在地理區(qū)域,并將區(qū)域的質(zhì)心作為目標(biāo)的點(diǎn)估計(jì)。此外,CBG方法假設(shè)時(shí)延和地理距離之間滿足一定的線性關(guān)系,并據(jù)此利用多個(gè)測(cè)量源之間的互測(cè)網(wǎng)絡(luò)時(shí)延,擬合出整體失真最小的最佳線性關(guān)系。據(jù)此線性關(guān)系預(yù)估探測(cè)目標(biāo)IP同多個(gè)探測(cè)源節(jié)點(diǎn)之間的距離,以該距離為半徑,源地標(biāo)節(jié)點(diǎn)為圓心繪制維恩圖,將其中交叉區(qū)域作為目標(biāo)IP的估計(jì)地理位置。

Octant方法在CBG方法的基礎(chǔ)上,將距離的最大界限定義為正約束和負(fù)約束,正約束表示目標(biāo)節(jié)點(diǎn)到測(cè)量節(jié)點(diǎn)的最遠(yuǎn)距離,負(fù)約束則表示最近距離。從圖形上看則是將原先的圓形區(qū)域限制在了一個(gè)環(huán)形區(qū)域內(nèi),從而減少了目標(biāo)區(qū)域范圍,提升了定位精度。

GeoWeight方法則是在以上2種方法的基礎(chǔ)上做了改進(jìn),該方法利用統(tǒng)計(jì)學(xué)的思想,依據(jù)探測(cè)節(jié)點(diǎn)獲取的時(shí)延-距離信息,將原本的圓形區(qū)域進(jìn)一步劃分成n個(gè)等距的環(huán)形區(qū)域,每一個(gè)區(qū)域依據(jù)概率大小設(shè)置不同的權(quán)重,來(lái)自多個(gè)地標(biāo)的時(shí)延測(cè)量將產(chǎn)生交叉區(qū)域,每個(gè)交叉區(qū)域中有不同數(shù)量的重疊環(huán)形區(qū)域。每個(gè)相交區(qū)域的最終權(quán)值為相交區(qū)域的權(quán)值之和。將權(quán)重最大的區(qū)域作為目標(biāo)的約束區(qū)域,并將該區(qū)域的質(zhì)心估計(jì)為目標(biāo)位置。

1.2 基于路徑測(cè)量的定位方法

網(wǎng)絡(luò)路徑測(cè)量是獲取網(wǎng)絡(luò)路由IP的重要方式,網(wǎng)絡(luò)數(shù)據(jù)包通常從源端經(jīng)過(guò)多個(gè)路由器轉(zhuǎn)發(fā)才能到達(dá)目的地,該類方法利用Traceroute等探測(cè)工具獲取經(jīng)過(guò)的每一跳路由的基本信息,并分析其網(wǎng)絡(luò)路徑上的典型特征,結(jié)合可靠地標(biāo)節(jié)點(diǎn)地理位置信息從而實(shí)現(xiàn)對(duì)目標(biāo)IP的定位。

此類方法按照定位側(cè)重點(diǎn)主要分為端IP定位和路由IP定位。

① 端IP定位

TBG方法主要解決探測(cè)源距離目標(biāo)節(jié)點(diǎn)較遠(yuǎn)的情況下,時(shí)延測(cè)量定位結(jié)果誤差較大的問題。使用Traceroute工具獲取源端到目標(biāo)主機(jī)之間經(jīng)過(guò)的路由IP以及單跳時(shí)延,利用時(shí)延的強(qiáng)弱時(shí)延約束條件,對(duì)路由IP進(jìn)行地理定位,再利用路由IP充當(dāng)新的地標(biāo)節(jié)點(diǎn)對(duì)目標(biāo)IP進(jìn)行定位。TBG有效減少了地標(biāo)和目標(biāo)主機(jī)之間相距較遠(yuǎn)導(dǎo)致的定位誤差,利用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)以及強(qiáng)弱約束條件實(shí)現(xiàn)路由器級(jí)別的地理定位,進(jìn)一步驗(yàn)證目標(biāo)IP的定位結(jié)果,提高了定位精度。

SLG方法則在CBG方法的基礎(chǔ)上進(jìn)一步提升了精度,面向街道級(jí)進(jìn)行IP定位。該方法采用“逐層逼近”的思想,利用路徑測(cè)量的局部時(shí)延分析路由、地標(biāo)以及目標(biāo)節(jié)點(diǎn)三者之間的時(shí)延-距離約束關(guān)系,從而實(shí)現(xiàn)街道級(jí)定位。

② 路由IP定位

關(guān)于大規(guī)模路由IP地理定位的問題,Tian等[18]提出了一種基于網(wǎng)絡(luò)拓?fù)涞乩砭垲惖膯l(fā)式定位方法,改進(jìn)現(xiàn)有的地理定位數(shù)據(jù)庫(kù)。該方法從網(wǎng)絡(luò)拓?fù)涞倪吘壜酚沙霭l(fā),逐漸逼近位于網(wǎng)絡(luò)核心的骨干路由,主要步驟包括:單路由集群、非骨干路由集群、骨干路由集群以及合并小集群,采用集群內(nèi)部定位投票的方式獲取該集群的地理位置。該方法一定程度上解決了探測(cè)節(jié)點(diǎn)依賴的問題,并改進(jìn)了商業(yè)數(shù)據(jù)庫(kù)的定位結(jié)果,但也由于投票規(guī)則過(guò)于簡(jiǎn)單、集群合并缺少依據(jù),導(dǎo)致定位結(jié)果并不理想。

Li等[19]在此基礎(chǔ)上提出了一種基于網(wǎng)絡(luò)拓?fù)渖鐓^(qū)檢測(cè)的IP地理定位方法(NCC),該方法主要包括:獲取完整路徑、構(gòu)建網(wǎng)絡(luò)拓?fù)?、分離骨干網(wǎng)與非骨干網(wǎng)、社區(qū)發(fā)現(xiàn)、投票定位社區(qū)和目標(biāo)IP定位這6個(gè)步驟,其中社區(qū)發(fā)現(xiàn)采用Louvain方法,通過(guò)模塊度優(yōu)化和網(wǎng)絡(luò)凝聚這2個(gè)階段實(shí)現(xiàn)聚類,模塊度是一種常見的用來(lái)衡量社區(qū)劃分強(qiáng)度的度量值,模塊度越接近1,社區(qū)的劃分效果越明顯。相較而言,NCC定位方法的通用性更好、容錯(cuò)率更低,但是該方法依然存在聚類方法特征不全、投票規(guī)則較為簡(jiǎn)單、無(wú)法適應(yīng)非完整路徑IP定位需求等問題。

近兩年,Dan等[20]提出了一種基于路徑測(cè)量定位傳播的IP地理定位方法(TLP),該方法利用“IP范圍插值”的概念,并將其與路徑測(cè)量中“延遲鄰居”相結(jié)合,用于IP地理定位。同一子網(wǎng)范圍內(nèi)的IP地址往往地理距離較近,IP范圍插值則是在此基礎(chǔ)上,若某個(gè)IP地址范圍存在多個(gè)可靠地標(biāo)IP,且地標(biāo)IP的地理位置相對(duì)較近,則將地標(biāo)IP地理位置中心作為整個(gè)IP范圍的定位結(jié)果,從而擴(kuò)大地標(biāo)集,且評(píng)估結(jié)果表明,選取256大小的IP地址范圍,準(zhǔn)確性和覆蓋率較高。同時(shí)利用Traceroute測(cè)量路徑上延遲差小于閾值(如2 ms)的IP對(duì)(即延遲鄰居)將地標(biāo)地理位置傳播到未知定位路由IP,進(jìn)而實(shí)現(xiàn)路由IP地理定位推斷。

2 算法基本思想

目前的路由IP地理定位方法所選特征相對(duì)單一,難以在探測(cè)節(jié)點(diǎn)資源匱乏等特殊情況下實(shí)現(xiàn)有效的IP地理定位。如NCC定位方法缺少測(cè)量時(shí)延這一重要特征,且投票規(guī)則較為簡(jiǎn)單,易產(chǎn)生錯(cuò)誤聚類的情況;而TLP方法中“IP范圍插值”的概念過(guò)于簡(jiǎn)化地標(biāo)節(jié)點(diǎn)擴(kuò)散方式,且在探測(cè)時(shí)延較大的情況下,時(shí)延地理一致性約束原則易受影響,難以實(shí)現(xiàn)大規(guī)模路由IP地理定位。

基于該現(xiàn)狀,本文結(jié)合IP所屬自治域系統(tǒng)(Autonomous System,AS)相關(guān)信息,利用譜聚類算法實(shí)現(xiàn)對(duì)路由IP地址的地理定位。

2.1 AS路徑的地理約束性

IP地理定位通常借助于網(wǎng)絡(luò)時(shí)延的約束性,即利用時(shí)延與地理距離的線性映射關(guān)系來(lái)估計(jì)地理距離的遠(yuǎn)近[21],但這種方式易受迂回路徑和時(shí)延抖動(dòng)的影響,造成時(shí)延約束性減弱。在此基礎(chǔ)上,本文采用AS路徑的地理約束性進(jìn)一步優(yōu)化IP地理定位。

受網(wǎng)絡(luò)業(yè)務(wù)提供商(ISP)之間商業(yè)關(guān)系的約束,互聯(lián)網(wǎng)的AS路徑通常滿足“無(wú)谷底”路徑模式(Valley-Free Path Model),即一個(gè)AS不能在它的2個(gè)提供商AS(對(duì)等AS)之間轉(zhuǎn)發(fā)流量,這也導(dǎo)致了AS路徑具有嚴(yán)格的層次關(guān)系和邏輯級(jí)別,通常情況下路由選路滿足從接入路由到骨干路由再到接入路由的過(guò)程,骨干路由又分為省際和省內(nèi)骨干,致使AS路徑的邏輯級(jí)別往往與行政區(qū)域劃分一致[22]。對(duì)于國(guó)內(nèi)的網(wǎng)絡(luò)而言,一個(gè)大型ISP通常包括省際和省內(nèi)骨干網(wǎng),省內(nèi)又包含諸多城域網(wǎng),這些骨干網(wǎng)絡(luò)對(duì)應(yīng)著不同級(jí)別的自治域,并按照級(jí)別從低到高再到低的順序進(jìn)行流量轉(zhuǎn)發(fā),這也意味著AS路徑本身與行政區(qū)域級(jí)別保持一致,相同的AS路徑通常對(duì)應(yīng)著相同的目標(biāo)區(qū)域。

以廣東省的目標(biāo)IP探測(cè)結(jié)果為例,其中探測(cè)節(jié)點(diǎn)選取的是中國(guó)山東省移動(dòng)網(wǎng)絡(luò)服務(wù)器,經(jīng)過(guò)AS24444(中國(guó)移動(dòng))—AS9808(移動(dòng)骨干網(wǎng))—AS4837(聯(lián)通骨干網(wǎng))—AS17623(中國(guó)聯(lián)通)這一AS路徑的目標(biāo)IP地址主要位于“中國(guó)廣東省深圳市”。

探測(cè)過(guò)程中主要經(jīng)過(guò)的AS路徑示意如圖1所示。

圖1 AS路徑示意Fig.1 Schematic diagram of AS path

2.2 算法框架

基于上述發(fā)現(xiàn),本文在此基礎(chǔ)上提出了一種基于譜聚類的路由IP地理定位(Spectral Clustering Based Router IP Geolocation,SCRG)方法,相比于現(xiàn)有的NCC和TLP方法,SCRG方法主要優(yōu)勢(shì)體現(xiàn)在以下方面:

① 采用了譜聚類算法:加入路徑時(shí)延特征,利用譜聚類算法代替“延遲鄰居”定位傳播方式合并IP節(jié)點(diǎn)。譜聚類算法可以構(gòu)造稀疏相似矩陣,對(duì)較大數(shù)據(jù)集表現(xiàn)優(yōu)于其他算法,同時(shí)能夠在任意形狀的樣本空間上聚類,相比于NCC方法中的Louvain算法,不容易將較小的簇合并。

② 引入了AS路徑概念:相同的AS路徑其目的地通常較為接近,利用網(wǎng)絡(luò)測(cè)量路徑上的AS及組織信息可對(duì)聚類結(jié)果做進(jìn)一步處理,從而劃分較大的簇以及合并較小的簇,這也是目前主要的IP地理定位方法容易忽略的路徑特征信息。

③ 設(shè)計(jì)了簇內(nèi)投票機(jī)制:對(duì)簇內(nèi)路由IP利用多數(shù)據(jù)庫(kù)對(duì)比定位結(jié)果作為投票基準(zhǔn),通常容易出現(xiàn)投票沖突的情況,即簇內(nèi)無(wú)明顯票數(shù)優(yōu)勢(shì)的地理位置信息,SCRG方法選取其中票數(shù)最高的3個(gè)地理位置作為候選,將候選位置分別代入到其所在的測(cè)量路徑上,若滿足更多無(wú)迂回城市(如出現(xiàn)北京—上?！本┑穆酚删€路)路徑的情況,則將其作為最優(yōu)投票結(jié)果。

SCRG方法主要步驟如圖2所示。

圖2 SCRG方法主要步驟Fig.2 Main steps of SCRG method

其中,IP活躍性探測(cè)采用Zmap工具[23],其作為開源掃描工具,Zmap支持多種方式存活性探測(cè),能夠在極短的時(shí)間內(nèi)完成大規(guī)模IP活躍性探測(cè)的任務(wù)。

在獲取完活躍IP后,SCRG方法利用開源主動(dòng)測(cè)量工具Scamper[24]進(jìn)行Traceroute測(cè)量,該工具是由CAIDA組織開發(fā)使用的,用于替代原來(lái)的Skitter工具,支持自定義發(fā)包速度,同時(shí)提供ICMP、UDP、TCP和Paris-style等多種方式實(shí)現(xiàn)Traceroute測(cè)量,能夠針對(duì)負(fù)載均衡的網(wǎng)絡(luò)進(jìn)行有效的IP地址發(fā)現(xiàn),獲取較為完整的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。之后利用譜聚類算法對(duì)路由IP進(jìn)行聚類,借助Routeviews[25]和RIPE RIS[26]兩個(gè)開源數(shù)據(jù)查詢IP所屬AS信息并獲取AS路徑,通過(guò)AS路徑對(duì)聚類簇做進(jìn)一步劃分與合并,最終利用簇內(nèi)投票規(guī)則獲取路由IP正確地理定位(詳細(xì)內(nèi)容見第3節(jié))。

3 設(shè)計(jì)與實(shí)現(xiàn)

3.1 譜聚類

譜聚類是目前較為流行的聚類算法之一,因其良好的性能和簡(jiǎn)單的實(shí)現(xiàn)受到廣泛的關(guān)注。譜聚類可以忽略樣本空間的形狀,在非凸數(shù)據(jù)集上也能聚類收斂到全局最優(yōu),譜聚類算法將數(shù)據(jù)集中的每個(gè)點(diǎn)視為圖形的頂點(diǎn),并將任意2個(gè)點(diǎn)之間的相似度視為連接2個(gè)頂點(diǎn)的邊的權(quán)重,從而構(gòu)造無(wú)向加權(quán)圖。然后,根據(jù)圖劃分方法,將圖劃分為幾個(gè)不相連的子圖,子圖中包含的點(diǎn)集就是聚類后生成的簇[27]。

通常譜聚類算法主要由3個(gè)部分組成:再處理、譜表示以及聚類,具體包括構(gòu)建節(jié)點(diǎn)的相似矩陣以及圖的拉普拉斯矩陣,然后選取特征向量進(jìn)行聚類。

SCRG方法采用譜聚類算法對(duì)路由IP進(jìn)行聚類,采用k-近鄰法(KNN),即遍歷所有的樣本點(diǎn),取每個(gè)樣本最近的k個(gè)點(diǎn)作為近鄰,從而構(gòu)建圖的相似矩陣W。相似矩陣W中各個(gè)元素采用式(1)計(jì)算得到:

(1)

式中:wij為路由節(jié)點(diǎn)xi和xj之間的相似度數(shù)值,disij為節(jié)點(diǎn)xi和xj之間的距離,在SCRG方法中可用路由IP之間的最短路徑時(shí)延代替,時(shí)延越高,表示距離越遠(yuǎn),相似度越低;σ為控制參數(shù),通常取1。

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

(2)

將Y的每一行當(dāng)作一個(gè)點(diǎn),使用近鄰傳播(AP)聚類將其劃分為簇,將原始點(diǎn)xi分配給聚類j當(dāng)且僅當(dāng)矩陣Y的第i行分配給聚類j,利用AP聚類的“消息傳遞”機(jī)制可有效解決傳統(tǒng)譜聚類算法的敏感初始化問題[28],相較于傳統(tǒng)的k-均值算法或k中心點(diǎn)算法,AP聚類算法主要有以下5點(diǎn)優(yōu)勢(shì):

① 無(wú)需手動(dòng)指定最終聚類簇的個(gè)數(shù);

② 并未生成新的簇中心,而是使用已有的點(diǎn)作為聚類中心;

③ 算法對(duì)數(shù)據(jù)的初始值不敏感;

④ 對(duì)數(shù)據(jù)相似度矩陣的對(duì)稱性沒有要求;

⑤ 算法結(jié)果的平方差誤差較小。

3.2 簇劃分與合并

由于探測(cè)得到的時(shí)延存在較大誤差,路徑上的不響應(yīng)路由也會(huì)產(chǎn)生大量的中斷路徑,導(dǎo)致路由聚類的結(jié)果誤差較大,存在大量?jī)?nèi)部節(jié)點(diǎn)過(guò)多和過(guò)少的簇,這也使得在下一步的投票過(guò)程中出現(xiàn)2種極端情況:

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

② 簇內(nèi)IP過(guò)少導(dǎo)致投票步驟無(wú)法進(jìn)行。

本文主要利用路由IP的AS路徑同地理位置的一致性約束原則(見2.1節(jié)),對(duì)聚類簇做進(jìn)一步劃分與合并,具體處理流程如圖3所示。

圖3 簇劃分與合并流程Fig.3 Cluster partitioning and merging process

首先,利用公共BGP快照的CIDR IP地址塊(Routeviews[25]and RIPE RIS[26])查詢所有路由IP的AS號(hào),IP查詢結(jié)果為空的AS號(hào)可用0替代。

其次,按照探測(cè)路徑順序構(gòu)建每個(gè)路由IP所屬AS路徑,優(yōu)先選取較為完整的AS路徑作為該IP的特征信息。

在此基礎(chǔ)上,針對(duì)聚類簇內(nèi)IP,以其AS路徑特征信息作區(qū)分,以簇平均大小C作為閾值,將節(jié)點(diǎn)數(shù)超過(guò)C的簇進(jìn)一步劃分成子簇。以廣東省IP探測(cè)結(jié)果為例,聚類后的簇平均大小在100左右,對(duì)節(jié)點(diǎn)數(shù)超過(guò)100的簇按AS路徑信息做進(jìn)一步劃分,表1為聚類簇A中挑選的部分路由IP及其AS路徑,表2為其劃分后的結(jié)果,將簇A劃分成A1、A2和A3這3個(gè)子簇。

表1 聚類簇A中部分路由IP及AS路徑

表2 簇A劃分后的結(jié)果

其次為了提升后續(xù)簇內(nèi)定位投票的效果,將內(nèi)部IP節(jié)點(diǎn)數(shù)目小于5的簇合并至存在相同AS路徑IP的其他簇中,合并的過(guò)程優(yōu)先選取IP所屬同一C類網(wǎng)段且地址較為接近的其他簇,這也是由于同一子網(wǎng)范圍內(nèi)的IP地址往往地理距離較近[20]。表3和表4分別為聚類簇合并前后的示例。

表3 待合并的聚類簇

表4 合并后的聚類簇

經(jīng)過(guò)聚類簇的劃分與合并之后,使得簇內(nèi)節(jié)點(diǎn)數(shù)量相對(duì)更加合理,相比于其他定位方法只是依據(jù)集群的拓?fù)溥B接關(guān)系做簡(jiǎn)單的合并更具合理性,同時(shí)也無(wú)需劃分骨干網(wǎng)和非骨干網(wǎng)進(jìn)行聚類。

3.3 簇內(nèi)投票

對(duì)于聚類后的每個(gè)簇ci=(x1,x2,…,xn),其中對(duì)每個(gè)IP節(jié)點(diǎn)xi查詢IP138[6]、Chunzhen[7]和IPCN[8]數(shù)據(jù)庫(kù)的定位結(jié)果,將2個(gè)及以上數(shù)據(jù)庫(kù)定位一致的地理位置作為多庫(kù)定位的結(jié)果,若3庫(kù)均不相同,則隨機(jī)選取其中定位精度達(dá)到城市級(jí)的地理位置作為該IP的多庫(kù)定位結(jié)果。

其次,對(duì)簇內(nèi)IP不同的地理位置進(jìn)行投票,并按照票數(shù)由高到低進(jìn)行排名,得到不同城市票數(shù)集合{Num(l1),Num(l2),…,Num(lk)},若Num(l1)/n≥1/2,則將l1作為該簇的定位結(jié)果,若Num(l1)/n<1/2,選取票數(shù)最高的3個(gè)地理位置{l1,l2,l3}作為候選結(jié)果。

通常情況下,從避免路由環(huán)路的角度來(lái)看,網(wǎng)絡(luò)路徑不太可能出現(xiàn)迂回城市的情況(如出現(xiàn)北京—上?！本┑穆酚删€路),迂回情況的發(fā)生大概率是由于IP地理定位出錯(cuò)。因此將簇內(nèi)定位的候選結(jié)果分別代入到測(cè)量路徑中,得到城市級(jí)路由線路,將出現(xiàn)迂回城市路徑最少的候選結(jié)果作為該簇的定位結(jié)果:

(3)

式中:Cli為出現(xiàn)迂回城市的路徑數(shù),li∈{l1,l2,l3}為候選的定位結(jié)果。

投票后聚類簇的定位結(jié)果作為簇內(nèi)所有路由IP的最終定位結(jié)果,進(jìn)而可以快速實(shí)現(xiàn)規(guī)?；穆酚蒊P城市級(jí)地理定位。

4 實(shí)驗(yàn)評(píng)估

為了驗(yàn)證本文提出的SCRG定位方法的性能,利用位于山東省的2臺(tái)移動(dòng)網(wǎng)絡(luò)服務(wù)器進(jìn)行路徑測(cè)量,測(cè)量采用的工具是Scamper,該工具支持Paris-style Traceroute探測(cè)。

實(shí)驗(yàn)所用到的IP地址數(shù)據(jù)是2023年3月15日純真發(fā)布的免費(fèi)IP庫(kù)社區(qū)版,提取該數(shù)據(jù)庫(kù)中國(guó)廣東省的IP地址作為探測(cè)目標(biāo),其中廣東省IP總數(shù)為37 770 954,活躍IP總數(shù)為3 409 280。共探測(cè)得到廣東省路由IP總數(shù)為31 612,如表5所示。

表5 廣東省各城市IP數(shù)(純真數(shù)據(jù)庫(kù))

通過(guò)對(duì)路由IP地址進(jìn)行定位,最終修改了16 949條路由IP定位結(jié)果,修改后的廣東省各城市路由IP數(shù)如表6所示。

表6 重新定位后廣東省各城市路由IP數(shù)

由表6可以看出,修改后的路由IP定位結(jié)果大多位于廣州市,這也是由于多個(gè)數(shù)據(jù)庫(kù)本身對(duì)于路由IP并未精確到城市級(jí)且大多位于廣州市,導(dǎo)致聚類后簇內(nèi)優(yōu)先投票到廣州市。

為了更好地說(shuō)明SCRG方法的準(zhǔn)確性和普適性,將其分別與NCC和TLP定位方法進(jìn)行比較。此外由于TLP方法使用的測(cè)量數(shù)據(jù)和地標(biāo)數(shù)據(jù)較為老舊,且地標(biāo)數(shù)據(jù)難以直接獲取,本文實(shí)驗(yàn)過(guò)程在現(xiàn)有測(cè)量數(shù)據(jù)的基礎(chǔ)上對(duì)方法進(jìn)行簡(jiǎn)單調(diào)整,選取3個(gè)商業(yè)數(shù)據(jù)庫(kù)定位結(jié)果一致的端IP作為地標(biāo)節(jié)點(diǎn),執(zhí)行插值的IP范圍大小為256,即/24子網(wǎng)劃分,而進(jìn)行地理位置傳播的延遲鄰居選取時(shí)延差在2 ms以內(nèi)的IP對(duì)。

定位結(jié)果顯示,SCRG方法相比于NCC和TLP方法存在定位差異的路由IP分別為2 803條和 6 236條。本次實(shí)驗(yàn)利用IP站點(diǎn)Ping工具來(lái)驗(yàn)證路由IP的準(zhǔn)確定位結(jié)果,選取Ping時(shí)延在2 ms以內(nèi)的測(cè)量節(jié)點(diǎn)所在位置作為正確定位結(jié)果,實(shí)驗(yàn)每次隨機(jī)選取20條不同定位的路由IP,共進(jìn)行5次驗(yàn)證,驗(yàn)證結(jié)果如圖4和圖5所示,可以看出SCRG的定位正確率要明顯高于NCC和TLP方法。

圖4 與NCC不同定位路由IP的5輪樣本驗(yàn)證結(jié)果Fig.4 5 rounds of sample verification results for rou- ter IP with different location from NCC

圖5 與TLP不同定位路由IP的5輪樣本驗(yàn)證結(jié)果Fig.5 5 rounds of sample verification results for router IP with different location from TLP

為了更好地說(shuō)明定位效果,實(shí)驗(yàn)將廣東省院校、政府單位IP地址及其所在城市作為可靠地標(biāo)節(jié)點(diǎn)使用,IP地址為其官網(wǎng)域名解析的IPv4地址,最終獲取374條可靠地標(biāo)IP,其中院校IP 152條,政府單位IP 222條。這些地標(biāo)IP經(jīng)過(guò)路徑測(cè)量,默認(rèn)最后一跳路由IP的正確地理位置為地標(biāo)節(jié)點(diǎn)所在城市。分別利用SCRG、NCC以及TLP方法進(jìn)行多次聚類,并對(duì)最后一跳路由IP地址進(jìn)行定位,最終定位的正確率如圖6所示。

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

由圖6可以看出,SCRG方法整體要優(yōu)于其他2種定位方法,平均正確率達(dá)到87.1%。造成這一結(jié)果的原因可能在于NCC方法并未考慮路徑時(shí)延信息,同時(shí)缺少有效的集群劃分與合并方式,導(dǎo)致聚類結(jié)果并不準(zhǔn)確;而TLP方法在測(cè)量資源和地標(biāo)節(jié)點(diǎn)有限的情況下,僅僅依靠延遲鄰居傳播地理位置并不可靠,且對(duì)路由IP來(lái)說(shuō),即便屬于同一網(wǎng)段,其依然可能位于不同城市,加上原文選取延遲鄰居時(shí),設(shè)置源到節(jié)點(diǎn)IP往返時(shí)延閾值上限為9 ms,也導(dǎo)致此方法難以適用于探測(cè)節(jié)點(diǎn)較遠(yuǎn)的路徑測(cè)量數(shù)據(jù)。

5 結(jié)束語(yǔ)

本文旨在利用有限的資源實(shí)現(xiàn)大規(guī)模路由IP地理定位的過(guò)程,提出了一種 SCRG方法,該方法使用譜聚類算法,利用鏈路時(shí)延特征計(jì)算節(jié)點(diǎn)之間的距離,對(duì)整個(gè)網(wǎng)絡(luò)路由拓?fù)溥M(jìn)行聚類,利用IP社會(huì)屬性,即AS路徑信息實(shí)現(xiàn)大簇劃分以及小簇合并,在此基礎(chǔ)上提出一種簇內(nèi)投票的沖突解決方式,獲取最優(yōu)投票結(jié)果,并將其作為整個(gè)簇內(nèi)路由IP的正確定位結(jié)果。相較于NCC和TLP這2種定位方法,SCRG方法的聚類特征更加全面,投票規(guī)則更加合理,在探測(cè)節(jié)點(diǎn)和地標(biāo)節(jié)點(diǎn)資源有限的情況下,對(duì)特定地標(biāo)路由的定位結(jié)果的平均正確率達(dá)到87.1%,明顯優(yōu)于其他2種定位方法。在未來(lái)的研究工作中,計(jì)劃利用數(shù)據(jù)挖掘方式獲取更多的地標(biāo)數(shù)據(jù),結(jié)合地標(biāo)IP的高精度定位結(jié)果,尋找與其潛在的相似性特征,從而實(shí)現(xiàn)區(qū)縣級(jí)以及街道級(jí)的準(zhǔn)確定位。