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

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

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

0 引言

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

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

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

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

1 相關工作

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

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

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

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

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

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

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

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

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

此類方法按照定位側重點主要分為端IP定位和路由IP定位。

① 端IP定位

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

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

② 路由IP定位

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

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

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

2 算法基本思想

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

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

2.1 AS路徑的地理約束性

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

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

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

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

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

2.2 算法框架

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

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

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

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

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

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

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

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

3 設計與實現(xiàn)

3.1 譜聚類

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

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

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

(1)

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

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

(2)

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

① 無需手動指定最終聚類簇的個數(shù);

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

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

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

⑤ 算法結果的平方差誤差較小。

3.2 簇劃分與合并

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

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

② 簇內IP過少導致投票步驟無法進行。

本文主要利用路由IP的AS路徑同地理位置的一致性約束原則(見2.1節(jié)),對聚類簇做進一步劃分與合并,具體處理流程如圖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路徑,優(yōu)先選取較為完整的AS路徑作為該IP的特征信息。

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

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

表2 簇A劃分后的結果

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

表3 待合并的聚類簇

表4 合并后的聚類簇

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

3.3 簇內投票

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

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

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

(3)

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

投票后聚類簇的定位結果作為簇內所有路由IP的最終定位結果,進而可以快速實現(xiàn)規(guī)模化的路由IP城市級地理定位。

4 實驗評估

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

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

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

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

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

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

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

定位結果顯示,SCRG方法相比于NCC和TLP方法存在定位差異的路由IP分別為2 803條和 6 236條。本次實驗利用IP站點Ping工具來驗證路由IP的準確定位結果,選取Ping時延在2 ms以內的測量節(jié)點所在位置作為正確定位結果,實驗每次隨機選取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地址及其所在城市作為可靠地標節(jié)點使用,IP地址為其官網(wǎng)域名解析的IPv4地址,最終獲取374條可靠地標IP,其中院校IP 152條,政府單位IP 222條。這些地標IP經(jīng)過路徑測量,默認最后一跳路由IP的正確地理位置為地標節(jié)點所在城市。分別利用SCRG、NCC以及TLP方法進行多次聚類,并對最后一跳路由IP地址進行定位,最終定位的正確率如圖6所示。

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

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

5 結束語

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