陳嘉欣，許 博，胡 超，張國敏，王占豐

(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ù)庫查詢、數(shù)據(jù)挖掘以及網(wǎng)絡(luò)測量[2]?；跀?shù)據(jù)庫查詢的方式速度更快,諸多商業(yè)數(shù)據(jù)庫提供在線和離線接口便于用戶進(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ò)測量的IP地理定位方法通用性更強(qiáng),也是目前主要的研究方向。這類方法通過網(wǎng)絡(luò)測量收集探測源和目標(biāo)之間的時延、拓?fù)涞认嚓P(guān)信息,結(jié)合大量地標(biāo)節(jié)點(diǎn),構(gòu)建條件約束模型,從而推斷測量目標(biāo)IP的地理位置信息。目前典型的網(wǎng)絡(luò)測量IP定位方法主要包括基于約束的地理定位(Constraint-Based Geolocation,CBG)[12]、基于網(wǎng)絡(luò)拓?fù)涞牡乩矶ㄎ?Topology Based Geolocation,TBG)[13]、Octant[14]和街道級地理定位(Street-Level Geolocation,SLG)[15]等。

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

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

1 相關(guān)工作

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

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

1.1 基于時延測量的定位方法

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

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

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

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

1.2 基于路徑測量的定位方法

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

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

① 端IP定位

TBG方法主要解決探測源距離目標(biāo)節(jié)點(diǎn)較遠(yuǎn)的情況下,時延測量定位結(jié)果誤差較大的問題。使用Traceroute工具獲取源端到目標(biāo)主機(jī)之間經(jīng)過的路由IP以及單跳時延,利用時延的強(qiáng)弱時延約束條件,對路由IP進(jìn)行地理定位,再利用路由IP充當(dāng)新的地標(biāo)節(jié)點(diǎn)對目標(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ìn)一步驗(yàn)證目標(biāo)IP的定位結(jié)果,提高了定位精度。

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

② 路由IP定位

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

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

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

2 算法基本思想

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

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

2.1 AS路徑的地理約束性

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

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

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

探測過程中主要經(jīng)過的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)勢體現(xiàn)在以下方面:

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

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

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

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

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

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

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

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

3.1 譜聚類

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

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

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

(1)

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

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

(2)

將Y的每一行當(dāng)作一個點(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ù);

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

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

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

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

3.2 簇劃分與合并

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

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

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

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

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

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

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

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

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

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

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

表3 待合并的聚類簇

表4 合并后的聚類簇

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

3.3 簇內(nèi)投票

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

其次,對簇內(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個地理位置{l1,l2,l3}作為候選結(jié)果。

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

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

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

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

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

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

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

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

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

定位結(jié)果顯示,SCRG方法相比于NCC和TLP方法存在定位差異的路由IP分別為2 803條和 6 236條。本次實(shí)驗(yàn)利用IP站點(diǎn)Ping工具來驗(yàn)證路由IP的準(zhǔn)確定位結(jié)果,選取Ping時延在2 ms以內(nèi)的測量節(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

為了更好地說明定位效果,實(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)過路徑測量,默認(rèn)最后一跳路由IP的正確地理位置為地標(biāo)節(jié)點(diǎn)所在城市。分別利用SCRG、NCC以及TLP方法進(jìn)行多次聚類,并對最后一跳路由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方法并未考慮路徑時延信息,同時缺少有效的集群劃分與合并方式,導(dǎo)致聚類結(jié)果并不準(zhǔn)確;而TLP方法在測量資源和地標(biāo)節(jié)點(diǎn)有限的情況下,僅僅依靠延遲鄰居傳播地理位置并不可靠,且對路由IP來說,即便屬于同一網(wǎng)段,其依然可能位于不同城市,加上原文選取延遲鄰居時,設(shè)置源到節(jié)點(diǎn)IP往返時延閾值上限為9 ms,也導(dǎo)致此方法難以適用于探測節(jié)點(diǎn)較遠(yuǎn)的路徑測量數(shù)據(jù)。

5 結(jié)束語

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