基于路由跳數(shù)的網(wǎng)絡(luò)實(shí)體地標(biāo)篩選

朱 光, 李 珂

(1.中原工學(xué)院 計(jì)算機(jī)學(xué)院， 河南 鄭州 450007； 2.河南省檔案局， 河南 鄭州 450003)

網(wǎng)絡(luò)實(shí)體定位，即獲取網(wǎng)絡(luò)實(shí)體IP地址與其地理位置之間的映射關(guān)系[1]。在互聯(lián)網(wǎng)中，IP地址通常能夠唯一標(biāo)識(shí)一個(gè)網(wǎng)絡(luò)實(shí)體，因此也稱IP定位。隨著網(wǎng)絡(luò)空間安全領(lǐng)域逐漸受到重視，IP定位技術(shù)也發(fā)揮著重要的作用，如IP定位技術(shù)可以追蹤網(wǎng)絡(luò)敏感目標(biāo)和鎖定網(wǎng)絡(luò)謠言散播者，為防恐維穩(wěn)提供技術(shù)支持；IP定位技術(shù)可應(yīng)用于商業(yè)領(lǐng)域中基于位置的服務(wù)；也可為電視節(jié)目、廣播和數(shù)字音像的區(qū)域版權(quán)保護(hù)提供技術(shù)支持等。

現(xiàn)有的網(wǎng)絡(luò)實(shí)體定位技術(shù)主要分為基于非測(cè)量方式和基于測(cè)量方式。前者利用互聯(lián)網(wǎng)公開(kāi)的IP數(shù)據(jù)庫(kù)(如Whois、IP2Location等)查詢IP地址的地理位置；后者測(cè)量探測(cè)源、地標(biāo)(已知地理位置的網(wǎng)絡(luò)實(shí)體)與目標(biāo)之間的時(shí)延、拓?fù)涞刃畔ⅲ瑥亩浪愠瞿繕?biāo)IP的地理位置，如GeoPing[2]、LBG[3]、Spotter[4]、CBG[5]、Octant[6]、SLG[7]算法等。

在上述基于測(cè)量的網(wǎng)絡(luò)實(shí)體定位方法中，將地標(biāo)所在位置作為目標(biāo)的位置估計(jì)(即基于地標(biāo)的網(wǎng)絡(luò)實(shí)體定位技術(shù))是獲取高精度定位結(jié)果的重要方式之一[8]。然而，現(xiàn)有的網(wǎng)絡(luò)實(shí)體地標(biāo)采集與評(píng)估算法較少，主要有Strcuton[9]、基于Web與在線地圖相結(jié)合的地標(biāo)挖掘算法(簡(jiǎn)稱基于Web的地標(biāo)挖掘方法)[7]以及基于互聯(lián)網(wǎng)論壇的地標(biāo)挖掘算法[10]。

基于Web的地標(biāo)挖掘算法是利用在線地圖查詢地理位置的方式實(shí)現(xiàn)Web網(wǎng)站的IP地址與其地理位置之間的映射，其算法流程見(jiàn)圖1。在提供在線地圖服務(wù)的網(wǎng)頁(yè)中輸入“公司”“大學(xué)”“政府”等組織機(jī)構(gòu)的關(guān)鍵字和郵政編碼后，地圖服務(wù)器返回該郵政編碼區(qū)域內(nèi)的相關(guān)單位的網(wǎng)站域名，可將這些網(wǎng)站域名(或IP地址)與其地理位置建立映射關(guān)系。

圖1 基于Web的地標(biāo)挖掘方法流程

基于Web的地標(biāo)挖掘算法獲取的地標(biāo)粒度為街道級(jí)，可滿足高精度定位算法的需求，然而，由于Web服務(wù)器可能存在主機(jī)托管、共享主機(jī)以及CDN(Content Delivery Network)網(wǎng)絡(luò)等情況，從在線地圖中獲取的域名與服務(wù)器的IP地址并不能保證一對(duì)一關(guān)系，且獲取的地理位置與Web服務(wù)器所在的地理位置也不能保證一一對(duì)應(yīng)。雖然，基于Web的地標(biāo)挖掘算法中對(duì)存在上述問(wèn)題的候選地標(biāo)進(jìn)行了評(píng)估，但效果并不理想，基于Web方式獲取的網(wǎng)絡(luò)實(shí)體地標(biāo)精度雖高，但可靠性不能得到保證。

1 基于路由跳數(shù)的網(wǎng)絡(luò)實(shí)體地標(biāo)篩選算法

1.1 算法思想與原理架構(gòu)

文獻(xiàn)[11]和[12]指出，同一網(wǎng)絡(luò)服務(wù)提供商在配置網(wǎng)絡(luò)環(huán)境和路由轉(zhuǎn)發(fā)策略時(shí)，數(shù)據(jù)包在骨干網(wǎng)上的轉(zhuǎn)發(fā)路徑往往相對(duì)穩(wěn)定，即對(duì)于同一區(qū)域的數(shù)據(jù)包到達(dá)另一區(qū)域時(shí)，數(shù)據(jù)包所經(jīng)歷的路由路徑往往相同或相似，由此通過(guò)多個(gè)探測(cè)源可量化出探測(cè)源到某個(gè)城市的路由跳數(shù)向量。

基于路由跳數(shù)的網(wǎng)絡(luò)實(shí)體地標(biāo)篩選算法原理架構(gòu)如圖2所示。首先，通過(guò)多個(gè)IP位置數(shù)據(jù)庫(kù)獲取候選地標(biāo)可能所處的地理位置，并在這些位置部署相應(yīng)的探測(cè)源，選取已知的高可靠的城市級(jí)地標(biāo)為基準(zhǔn)節(jié)點(diǎn)，測(cè)量探測(cè)源到所有基準(zhǔn)節(jié)點(diǎn)的路由路徑與路由跳數(shù)，統(tǒng)計(jì)出每個(gè)探測(cè)源到每座城市的平均路由跳數(shù)以及每座城市內(nèi)部的平均跳數(shù)，為每一座城市建立跳數(shù)向量，稱為基準(zhǔn)跳數(shù)向量；然后，依據(jù)上述方法，對(duì)待評(píng)估的候選地標(biāo)建立候選地標(biāo)跳數(shù)向量；最后，計(jì)算基準(zhǔn)跳數(shù)向量與候選地標(biāo)跳數(shù)向量的相似度，將相似度最高的基準(zhǔn)跳數(shù)向量所對(duì)應(yīng)的城市作為候選地標(biāo)的地理位置。

圖2 基于路由跳數(shù)的網(wǎng)絡(luò)實(shí)體地標(biāo)篩選原理架構(gòu)

1.2 算法步驟

輸入：待評(píng)估的候選地標(biāo)；

輸出：篩選后的高可靠地標(biāo)；

Step1：基準(zhǔn)節(jié)點(diǎn)選取與探測(cè)源部署。通過(guò)現(xiàn)有的多個(gè)IP位置數(shù)據(jù)庫(kù)獲取候選地標(biāo)可能所處的城市，選取一定數(shù)量的位于這些候選城市的高可靠網(wǎng)絡(luò)實(shí)體地標(biāo)為基準(zhǔn)節(jié)點(diǎn)(應(yīng)屬于同一ISP)，基準(zhǔn)節(jié)點(diǎn)在地理位置上應(yīng)均勻分布，且位于不同網(wǎng)段。在部署探測(cè)源時(shí)，應(yīng)在候選地標(biāo)可能所在的城市周邊均勻部署多個(gè)探測(cè)源(探測(cè)源與基準(zhǔn)節(jié)點(diǎn)應(yīng)屬于同一ISP)，探測(cè)源的數(shù)量一般由用戶對(duì)篩選精度的需求來(lái)確定。

Step2：路徑測(cè)量與跳數(shù)統(tǒng)計(jì)。利用Traceroute工具，使探測(cè)源發(fā)送數(shù)據(jù)包，測(cè)量探測(cè)源到所有基準(zhǔn)節(jié)點(diǎn)的路由路徑，路由路徑包含探測(cè)源到基準(zhǔn)節(jié)點(diǎn)之間經(jīng)過(guò)的所有路由器以及對(duì)應(yīng)的跳數(shù)信息。針對(duì)任一探測(cè)源，根據(jù)路由路徑分析，統(tǒng)計(jì)出該探測(cè)源到每座城市的平均路由跳數(shù)α以及每個(gè)城市內(nèi)部的平均跳數(shù)δ。

計(jì)算α?xí)r，根據(jù)現(xiàn)有IP位置數(shù)據(jù)庫(kù)查詢方式確定每條路由路徑中到達(dá)該城市的第一個(gè)路由器R，并將R之后的所有路徑移除；然后統(tǒng)計(jì)探測(cè)源到路由器R之間的路由跳數(shù)進(jìn)而計(jì)算出該探測(cè)源到每座城市的平均路由跳數(shù)α。計(jì)算δ時(shí)，將路由器R之前的所有路徑移除，統(tǒng)計(jì)路由器R到基準(zhǔn)節(jié)點(diǎn)之間的路由跳數(shù)，計(jì)算每座城市內(nèi)部的平均跳數(shù)δ。

Step3：建立基準(zhǔn)跳數(shù)向量。依據(jù)上述方法，確定每座城市的平均路由跳數(shù)α及每座城市內(nèi)部的平均路由跳數(shù)δ。對(duì)任一城市，為每一個(gè)探測(cè)源建立到該城市的跳數(shù)向量Hi=(αi,(αi+δi))，其中，i表示第i個(gè)探測(cè)源，進(jìn)而建立所有探測(cè)源到該城市的基準(zhǔn)跳數(shù)向量。為便于計(jì)算，將每座城市的基準(zhǔn)跳數(shù)向量記為DH，如式(1)所示，其中，m為探測(cè)源數(shù)量，i表示第i個(gè)探測(cè)源，其數(shù)量根據(jù)用戶對(duì)篩選精度的需求而定，hi,1與hi,2分別為候跳數(shù)向量Hi中的兩個(gè)元素。

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

(1)

Step4：建立候選地標(biāo)跳數(shù)向量。所有探測(cè)源發(fā)送探測(cè)包測(cè)量候選地標(biāo)的路由路徑，獲取探測(cè)源到候選地標(biāo)之間的路由跳數(shù)α以及城市內(nèi)部的跳數(shù)δ，為候選地標(biāo)的所有可能城市分別建立候選地標(biāo)跳數(shù)向量Tj=(αj,(αj+δj))，其中j表示第j個(gè)探測(cè)源，α與δ的計(jì)算方法同Step2，進(jìn)而為候選地標(biāo)建立多個(gè)跳數(shù)向量DT，如式(2)所示，其中，k表示候選地標(biāo)可能所處的第k座候選城市，m為探測(cè)源數(shù)量，tj,1與tj,2分別為候選地標(biāo)跳數(shù)向量Tj中的兩個(gè)元素。

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

(2)

Step5：候選地標(biāo)篩選。計(jì)算候選地標(biāo)跳數(shù)向量DTk和每座城市的基準(zhǔn)跳數(shù)向量DH相似度，計(jì)算方法見(jiàn)式(3)，其中i表示第i個(gè)探測(cè)源。其中Ek為候選地標(biāo)與第k座候選城市的誤差值，將與Ek最小的基準(zhǔn)跳數(shù)向量所對(duì)應(yīng)的城市作為候選地標(biāo)所在的城市，將候選地標(biāo)宣稱的地理位置與評(píng)估出來(lái)的位置進(jìn)行比較，兩者所處地理位置不一致的候選地標(biāo)認(rèn)為是可靠性低的地標(biāo)，兩者地理位置一致的候選地標(biāo)認(rèn)為是高可靠的地標(biāo)，進(jìn)而完成對(duì)候選地標(biāo)的篩選。

(3)

2 實(shí)驗(yàn)結(jié)果及分析

為驗(yàn)證本文提出的基于路由跳數(shù)的網(wǎng)絡(luò)實(shí)體地標(biāo)篩選算法，以SLG與LBG定位算法為基準(zhǔn)，采用兩類地標(biāo)集：傳統(tǒng)的基于Web的地標(biāo)挖掘算法得到的地標(biāo)集(以下簡(jiǎn)稱WBL)和本文算法對(duì)其篩選后的地標(biāo)集(以下簡(jiǎn)稱FWBL)，分別作為SLG與LBG定位算法的輸入，對(duì)分布在6座城市的300個(gè)已知地理位置的目標(biāo)IP進(jìn)行定位，比較兩種地標(biāo)集對(duì)上述兩種定位算法精度的影響。

2.1 SLG與LBG算法基本原理

SLG算法采用三層定位的思想逐層縮小目標(biāo)的位置估計(jì)[7]。第一層利用改進(jìn)的CBG算法為目標(biāo)限定一個(gè)粗粒度區(qū)域。第二層在第一層估計(jì)區(qū)域的基礎(chǔ)上，結(jié)合區(qū)域內(nèi)的網(wǎng)絡(luò)實(shí)體地標(biāo)，計(jì)算地標(biāo)與目標(biāo)之間的相對(duì)時(shí)延，進(jìn)一步縮小目標(biāo)估計(jì)區(qū)域。首先，找到地標(biāo)與目標(biāo)相連的所有共同路由器，計(jì)算它們的相對(duì)時(shí)延。然后，將與目標(biāo)相對(duì)時(shí)延最小的地標(biāo)作為目標(biāo)的位置估計(jì)。

LBG算法利用具有較低計(jì)算復(fù)雜度的樸素貝葉斯模型解決機(jī)器學(xué)習(xí)的分類問(wèn)題[3]。該算法通過(guò)測(cè)量方式獲取探測(cè)源到大量地標(biāo)的往返時(shí)延和跳數(shù)信息，并將時(shí)延和跳數(shù)劃分為不同的區(qū)間，根據(jù)劃分后的區(qū)間，分別統(tǒng)計(jì)出探測(cè)源到地標(biāo)的概率分布，并建立相應(yīng)的概率分布模型。當(dāng)定位目標(biāo)時(shí)，利用探測(cè)源到目標(biāo)的時(shí)延與跳數(shù)信息，并結(jié)合概率分布模型，將目標(biāo)定位到符合該概率分布模型的區(qū)域。

2.2 候選地標(biāo)評(píng)估

2.2.1 基準(zhǔn)跳數(shù)向量計(jì)算

對(duì)中國(guó)主流的IP位置數(shù)據(jù)庫(kù)QQWry(實(shí)驗(yàn)使用版本為2015.05.15版)、IP138和IPcn進(jìn)行解析與比對(duì)，篩選出鶴壁、許昌、鄭州、深圳、上海及西安等6座城市的所有網(wǎng)吧IP，保留IP位置數(shù)據(jù)庫(kù)查詢結(jié)果均處于同一城市的IP，挑選出IP地址16 828個(gè)(均屬于中國(guó)電信)作為基準(zhǔn)節(jié)點(diǎn)的樣本集，利用部署在北京、杭州、青島和深圳的4個(gè)探測(cè)源，在每天的不同時(shí)間段，對(duì)上述樣本集進(jìn)行重復(fù)測(cè)量，共計(jì)20次，獲取探測(cè)源到16 828個(gè)基準(zhǔn)節(jié)點(diǎn)的路由路徑1 137 456條。統(tǒng)計(jì)出探測(cè)源到每座城市的平均路由跳數(shù)α以及每座城市內(nèi)部的平均路由跳數(shù)δ，如表1所示。根據(jù)每座城市的α與δ構(gòu)建鶴壁、許昌、鄭州、深圳、上海及西安等6座城市的基準(zhǔn)跳數(shù)向量，如表2所示。

表1 探測(cè)源到6座城市的平均路由跳數(shù)及城市內(nèi)部平均路由跳數(shù)

表2 6座城市的基準(zhǔn)跳數(shù)向量

2.2.2 候選地標(biāo)跳數(shù)向量計(jì)算

通過(guò)基于Web的地標(biāo)挖掘算法從上述6座城市采集與評(píng)估候選地標(biāo)1 500個(gè)，構(gòu)建WBL地標(biāo)集，利用部署在北京、杭州、青島和深圳4座城市的探測(cè)源，在每天不同時(shí)間段發(fā)送探測(cè)包對(duì)WBL地標(biāo)集進(jìn)行重復(fù)測(cè)量，共20次。獲取探測(cè)源到WBL地標(biāo)集的路由路徑 117 659條，統(tǒng)計(jì)出每個(gè)候選地標(biāo)的平均路由跳數(shù)α以及該地標(biāo)所在城市內(nèi)部的平均路由跳數(shù)δ。根據(jù)表2中每座城市的基準(zhǔn)跳數(shù)向量，對(duì)每個(gè)待評(píng)估的WBL地標(biāo)進(jìn)行相似度比較。篩選后的WBL地標(biāo)集稱為FWBL地標(biāo)集，WBL與FWBL地標(biāo)集數(shù)量如表3所示。地標(biāo)篩選前后的地理分布如圖3所示。

2.3 定位結(jié)果比較

選取鶴壁、許昌、鄭州、深圳、上海及西安等6座城市的可靠地標(biāo)各50個(gè)，共計(jì)300個(gè)，作為待定位目標(biāo)集。分別使用WBL地標(biāo)集和FWBL地標(biāo)集作為SLG算法及LBG定位算法的輸入，對(duì)目標(biāo)集進(jìn)行定位，實(shí)驗(yàn)結(jié)果分別見(jiàn)表4和表5。

表3 WBL與FWBL地標(biāo)集數(shù)量

(a-1)鶴壁篩選前的地標(biāo)分布 (a-2)鶴壁篩選后的地標(biāo)分布

(b-1)許昌篩選前的地標(biāo)分布 (b-2)許昌篩選后的地標(biāo)分布

(c-1)鄭州篩選前的地標(biāo)分布 (c-2)鄭州篩選后的地標(biāo)分布

(d-1)深圳篩選前的地標(biāo)分布 (d-2)深圳篩選后的地標(biāo)分布

(e-1)上海篩選前的地標(biāo)分布 (e-2)上海篩選后的地標(biāo)分布

(f-1)西安篩選前的地標(biāo)分布 (f-2)西安篩選后的地標(biāo)分布 圖3 各城市地標(biāo)篩選前后的地理位置分布比較表4 兩類地標(biāo)集對(duì)SLG算法定位的結(jié)果比較

城市WBL地標(biāo)集定位正確數(shù)量準(zhǔn)確率/%FWBL地標(biāo)集定位正確數(shù)量準(zhǔn)確率/%鶴壁43864690許昌45904896鄭州44884896深圳43864794上海44884794西安43864588合計(jì)26287．3328193．67

由表4可知，SLG算法對(duì)300個(gè)目標(biāo)定位實(shí)驗(yàn)中，WBL地標(biāo)集定位正確數(shù)量為262個(gè)，準(zhǔn)確率為87.33%；篩選后的FWBL地標(biāo)集定位正確數(shù)量為281個(gè)，準(zhǔn)確率為93.67%，相比于WBL地標(biāo)集，提高了6.33%。因此，篩選后的地標(biāo)能夠提高SLG定位算法的準(zhǔn)確率。通過(guò)對(duì)定位結(jié)果的誤差分析可知，WBL產(chǎn)生的平均誤差為51.98 km，中值誤差為19.70 km，F(xiàn)WBL產(chǎn)生的平均誤差為45.71 km，中值誤差為10.28 km，F(xiàn)WBL的定位結(jié)果的誤差明顯小于WBL。因此，從定位精度上看，F(xiàn)WBL優(yōu)于WBL。

表5 兩類地標(biāo)集對(duì)LBG算法定位的結(jié)果比較

由表5可知，LBG算法對(duì)300個(gè)目標(biāo)進(jìn)行定位實(shí)驗(yàn)中，采用WBL地標(biāo)集定位正確數(shù)量為246個(gè)，正確率為82%；FWBL地標(biāo)集定位正確數(shù)量為269個(gè)，正確率為89.67%，相比于WBL地標(biāo)集，提高了7.67%。通過(guò)對(duì)定位結(jié)果的誤差分析可知，WBL產(chǎn)生的平均誤差為57.33 km，中值誤差為23.42 km，F(xiàn)WBL產(chǎn)生的平均誤差為49.61 km，中值誤差為14.23 km，從定位精度上看，F(xiàn)WBL地標(biāo)集優(yōu)于WBL地標(biāo)集。

3 結(jié) 語(yǔ)

針對(duì)基于Web的候選地標(biāo)評(píng)估算法中難以對(duì)候選地標(biāo)進(jìn)行有效評(píng)估的問(wèn)題，提出了一種基于路由跳數(shù)的網(wǎng)絡(luò)實(shí)體地標(biāo)篩選算法。實(shí)驗(yàn)結(jié)果表明：本文算法能夠提高候選地標(biāo)的可靠性，提高SLG定位算法及LBG定位算法的精度，為高可靠網(wǎng)絡(luò)實(shí)體城市級(jí)地標(biāo)提供了一種新的篩選與評(píng)估算法。

[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] 王占豐,馮徑,邢長(zhǎng)友,等.IP定位技術(shù)的研究[J].軟件學(xué)報(bào),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.