一種多接口路由器地理定位方法

朱金玉, 張 宇, 曾良偉, 余卓勛, 張宏莉

哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院 計算機網(wǎng)絡(luò)與信息安全技術(shù)研究中心 哈爾濱 中國150001

1 引言

網(wǎng)絡(luò)空間測繪研究內(nèi)容之一是實體資源定位,即確定網(wǎng)絡(luò)設(shè)備實體在地理空間中的位置。路由器作為構(gòu)建互聯(lián)網(wǎng)的基石, 對其地理定位技術(shù)就成了能否準確繪制網(wǎng)絡(luò)空間的關(guān)鍵。然而, 網(wǎng)絡(luò)空間實體多以IP地址為標(biāo)識, 而IP地址本身具有地理位置無關(guān)性, 同時, 一臺路由器擁有多個 IP地址也增加了定位的不確定性。因此如何對路由器實施定位既是網(wǎng)絡(luò)空間測繪核心問題之一, 更是一個難點問題。

以往工作通過提取和解碼路由器主機名中包含的地理信息字符串定位路由器位置, 或通過建立路徑-時延模型來定位路由器地理位置。這些方法通常需要額外測量工作, 或人工輔助解析, 難以持續(xù)更新。不僅如此, 測量通常不可重現(xiàn), 人工參與的解析結(jié)果會因人而異, 導(dǎo)致定位過程難以重現(xiàn), 定位結(jié)果難以評估。

本文提出一個種基于公開路由器級拓撲測量數(shù)據(jù)與商業(yè)IP地理信息的路由器定位方法--RLoc。該方法“站在巨人的肩膀上”, 充分利用現(xiàn)有網(wǎng)絡(luò)拓撲測量與IP地理定位的成果來實施定位。與以往工作相比, RLoc無需實施新的大規(guī)模網(wǎng)絡(luò)測量, 或構(gòu)建及校對時延-距離模型; 無需在人工輔助下解析域名、Whois、網(wǎng)頁等IP地址相關(guān)信息。

RLoc將拓撲測量與 IP定位工作獲得的數(shù)據(jù)集作為輸入, 但不依賴其獲取方法與質(zhì)量。在具備路由器級拓撲測量數(shù)據(jù)和 IP地理信息前提下, 對多接口路由器定位仍充滿挑戰(zhàn)。如圖1所示, 由于相鄰路由器間共享地址空間, 使路由器各接口 IP地址定位位置不同。該路由器共有25個接口IP地址, 位置分別在西班牙、美國、英國、德國。如圖2所示, 雖然相鄰路由器地理位置相近, 但有些路由器邏輯上相連但位置分布較遠。該路由器共有1,269臺鄰居路由器,他們的位置在西班牙、美國、德國、中國、葡萄牙, 還有部分路由器位置無法確定。

RLoc充分利用同一臺路由器擁有多個接口 IP地址但地理位置相同這一依據(jù), 提出接口選舉方法定位; 同時, 利用相連的路由器與路由器間地理位置相近這一依據(jù), 提出鄰居選舉方法定位; 結(jié)合前兩種定位依據(jù), 綜合路由器接口 IP地址位置與相鄰路由器位置信息定位多接口路由器位置。

本文主要貢獻總結(jié)如下：

1、提出一種基于公開路由器級拓撲測量數(shù)據(jù)與商業(yè)IP地理信息的多接口路由器地理定位方法——RLoc, 利用兩點事實： 同一臺路由器的不同接口 IP地址在相同位置; 相連路由器間地理位置相近。

2、將RLoc應(yīng)用于132,175臺多接口路由器的地理定位。實驗結(jié)果表明, 在覆蓋率上, 國家級達到99.84%, 城市級達到 96.00%, 比相關(guān)數(shù)據(jù)集分別高出0.93%和36.48%; 在IXP數(shù)據(jù)驗證準確率上, 國家級達到 82.51%, 城市級達到 59.45%, 比相關(guān)數(shù)據(jù)集分別高出9.91%和27.20%。

圖2 路由器的鄰居路由器定位多個位置實例圖Figure 2 Instance of router’s neighbors geolocated multi-location

3、RLoc易于實施與重復(fù), 結(jié)果易于更新和評估。為此, 公開了對132,175臺多接口路由器定位結(jié)果。( 百 度 網(wǎng) 盤 下 載 鏈 接 ： https：//pan.baidu.com/s/1mr6a8vDFMHKaM6-cWwEqwg)

本文的以下章節(jié)內(nèi)容按照以下組織： 第二章介紹相關(guān)工作; 第三章提出多接口路由器地理定位方法RLoc;第四章給出實驗及結(jié)果分析; 第五章是方法的局限性; 第六章總結(jié)了全文并展望未來工作。

2 相關(guān)工作

互聯(lián)網(wǎng)拓撲測量和分析研究方向已有二十多年,其中包含AS、POP、路由器、接口級拓撲。IP地理定位技術(shù)伴隨著云計算和社交網(wǎng)絡(luò)等新型網(wǎng)絡(luò)應(yīng)用的不斷發(fā)展, 逐漸受到了越來越多的關(guān)注。而本文提出的路由器地理定位方法以路由器級拓撲測量數(shù)據(jù)和 IP地理定位數(shù)據(jù)為基礎(chǔ), 實現(xiàn)對網(wǎng)絡(luò)空間測繪中實體資源路由器的定位, 從而實現(xiàn)大規(guī)模網(wǎng)絡(luò)邏輯拓撲與地理位置的映射。

路由器級拓撲測量： 路由器級拓撲通常是屬于同一臺路由器的接口組合, 一個節(jié)點代表著一個主機或一個多接口的路由器。如果節(jié)點間相互連接, 則節(jié)點間一定有接口位于同一個 IP廣播域。在Traceroute測量數(shù)據(jù)中, 存在不可忽略的路由陷阱,如： 負載均衡和路由改變情況等。路由陷阱需要進行別名解析, 把屬于同一臺路由器的 IP地址映射到該路由器上。

Motamedi 等[1]對網(wǎng)絡(luò)拓撲發(fā)現(xiàn)各層級拓撲數(shù)據(jù)收集的技術(shù)和工具深度分析。CAIDA[2]在2000年采用相同源地址方法實現(xiàn)了 Iffinder別名解析工具。Spring等[3]在 2002年采用 IPID計數(shù)器實現(xiàn)了 Ally別名解析工具。Bender等[4]提出了 RadarGun工具,降低了復(fù)雜度。Keys等[5]在 2016年提出基于 IPID的MIDAR別名解析技術(shù), 比Ally和RadarGun準確率更高。本文綜合考量各類拓撲數(shù)據(jù)質(zhì)量, 選擇使用CAIDA的Macroscopic Internet Topology Data Kit(ITDK)[6]項目中, MIDAR和IFFINDER共同使用作為別名解析工具所生成的路由器級拓撲數(shù)據(jù)集, 它較相同IP級拓撲數(shù)據(jù)作為輸入的Kapar等方法具有高置信度和低誤報率, 較其他平臺拓撲測量覆蓋率更高。

IP地理定位技術(shù)： IP地址定位是確定一個網(wǎng)絡(luò)目標(biāo)節(jié)點在某個粒度層次的地理位置, 由于每一個直接與互聯(lián)網(wǎng)相連的主機都被一個唯一的IP地址所表標(biāo)識, 通常利用 IP地址來尋找其地理坐標(biāo)映射。根據(jù)近年的研究方法, 定位技術(shù)可以分為三類, 分別為基于主動測量、數(shù)據(jù)挖掘分析和數(shù)據(jù)庫推測的定位技術(shù)。

Gueye等[7]采用三角定位方法確定被測 IP地址位置。Katz-Bassett等[8]采用網(wǎng)絡(luò)路徑信息作為目的IP和中間節(jié)點的約束條件從而確定待定位IP的位置區(qū)間。Wong等[9]利用時延-距離關(guān)系測量城市位置,使用貝塞爾曲線表示 IP地址可能出現(xiàn)的區(qū)域, 通過不斷迭代確定IP所在區(qū)域。基于主動測量的方法準確度受時延-距離模型影響較大, 且需要大量測量點和地標(biāo)點, 定位一個目標(biāo) IP地址所需時間也較長。Liu等[10]利用用戶自愿提供的位置信息來定位, 誤差中位數(shù)為799m。這類數(shù)據(jù)挖掘方法雖然可得到更加精確的定位, 但覆蓋率和普適性不高?；跀?shù)據(jù)庫推測的定位技術(shù)通過推測 DNS、Whois、BGP等數(shù)據(jù)中直接或間接提供的位置信息定位 IP地址。Moore等[11]通過直接查詢 Whois數(shù)據(jù)庫來推測主機位置信息。Padmanabhan等[12]通過挖掘主機名字中可能包含的不同粒度的地理位置信息推測主機的位置。

為能滿足更廣泛的應(yīng)用, 如定向廣告、詐欺監(jiān)測、網(wǎng)站流量分析、地理目標(biāo)定位、數(shù)字版權(quán)管理等, 國內(nèi)外IP商業(yè)地理定位數(shù)據(jù)庫, 如： MaxMind、IP2Location、Netacuity、IPMarker、IPIP.NET等, 利用測量、數(shù)據(jù)挖掘、數(shù)據(jù)庫推測等各方法對IP地理定位, 精確度可為國家、城市、甚至于郵編級。宋健等[13]提出了一種基于IP地址庫之間差異對比來評估可信程度的方法, 并發(fā)現(xiàn)IP地址庫之間差異所存在的規(guī)律。王婷等[14]提出IPGEL方法有效提高已有 IP定位數(shù)據(jù)庫的可用性。Gharaibeh等[15]評估了多種地理定位數(shù)據(jù)庫在路由器定位的可靠性。本文綜合各類商業(yè)IP地理定位數(shù)據(jù)庫質(zhì)量, 選擇使用IP2location數(shù)據(jù)庫為路由器各接口IP地址地理定位, 它較MaxMind等數(shù)據(jù)庫的國家城市粒度更精細。

路由器定位方法： Huffaker等[16]提取和解碼路由器主機名中包含的地理信息字符串從而定位路由器位置。該方法需要不斷收集具有地理字符串的數(shù)據(jù), 提出規(guī)則將其與實際物理位置聯(lián)系起來, 需要大量的人工分析編譯, 但人工解析結(jié)果因人而異且規(guī)則只能識別帶有主機名信息的IP地址的位置, 無法適用于大規(guī)模的路由器地理定位。Laki等[17,18]提出了一個路徑-時延模型來定位路由器地理位置。該方法需要進行大規(guī)模的拓撲測量并構(gòu)建時延-距離模型, 但測量通常不可重現(xiàn), 模型校對需要大量的地標(biāo)點和測量工作, 而且時延受網(wǎng)絡(luò)擁塞等外界條件影響較大。

CAIDA利用 ITDK的路由器級拓撲數(shù)據(jù), IXP、DNS、MaxMind數(shù)據(jù)庫信息對路由器進行地理定位。當(dāng)路由器至少一個接口IP地址屬于IXP地址空間且該地址空間只有一個地理位置, 則定位該路由器; 余下路由器利用DDec主機名映射, 當(dāng)路由器至少一個接口IP地址的主機名解析了地理位置且所有能夠解析的接口結(jié)果一致, 則定位該路由器; 除此之外的路由器,根據(jù)MaxMind數(shù)據(jù)庫定位接口IP地址, 當(dāng)所有接口IP地址定位在同一位置, 則定位該路由器位置。同時,CAIDA公開了路由器位置數(shù)據(jù)。但該方法過多的依賴于公開數(shù)據(jù)集的數(shù)據(jù), 受到IXP、DNS、MaxMind數(shù)據(jù)庫等信息的質(zhì)量影響較大, 且每個 IXP有多個互聯(lián)設(shè)施可能分布在不同的地方, 這導(dǎo)致能夠利用IXP數(shù)據(jù)定位的路由器數(shù)量不多; 使用MaxMind數(shù)據(jù)庫定位精度在城市級粒度上能夠定位的路由器數(shù)量不多。

本文提出了一種新的多接口路由器地理定位方法—RLoc, 基于IP2Location商業(yè)數(shù)據(jù)庫和路由器級拓撲數(shù)據(jù), 減少了大量的測量時間, 與人工收集解析過程,提出啟發(fā)式方法, 不僅利用路由器接口IP地址映射的位置定位路由器, 而且利用路由器位置與接口IP地址位置間關(guān)系和鄰居路由器間位置關(guān)系定位。RLoc與CAIDA定位相同的路由器, 與CAIDA公開的數(shù)據(jù)集相比擁有更高的覆蓋率與準確率。

3 多接口路由器地理定位方法

RLoc利用兩點事實： 1.同一臺路由器的不同接口IP地址在相同位置; 2.相連路由器間地理位置相近。提出了三種啟發(fā)式方法, 如圖 3所示, 接口選舉(Interface Election, IE)、鄰居選舉(Neighbor Election,NE)和綜合法(IE+NE)。

圖3 三種啟發(fā)式方法定位多接口路由器示意圖Figure 3 Three heuristic methods to geolocate multi-interface routers

3.1 接口選舉

RLoc充分利用同一臺路由器上不同接口 IP地址在相同位置這一事實, 提出IE方法。該方法以路由器各接口 IP地址和商業(yè) IP地理數(shù)據(jù)庫為輸入, 為每臺路由器的接口IP地址地理定位。路由器的接口IP地址由于路由器間交換地址空間導(dǎo)致地理位置不同, 因此為每臺路由器建立位置頻數(shù)矩陣：

I中Li表示路由器接口IP地址的第i個位置,Fi表示第i個位置出現(xiàn)的頻數(shù),CIi表示第i個位置作為路由器位置的置信度。其中CIi表示為：

在位置頻數(shù)矩陣中選擇置信度最大的結(jié)果作為路由器的位置。在圖3 IE方法示意圖中, 一臺路由器有四個接口IP地址, 地理位置分別為A、A、A、B, 則建立路由器位置頻數(shù)矩陣為：

路由器可能的位置為A和B, 其中A的位置置信度更大, 則路由器的位置為A, 置信度0.75。

以路由器定位的實例圖1為例, 一臺路由器有25個接口IP地址, 分別定位地理位置, 并建立位置頻數(shù)矩陣：

路由器可能的位置為西班牙、美國、德國、英國, 其中西班牙的置信度更大, 則該路由器位置為西班牙, 置信度為0.88。

IE方法會出現(xiàn)位置歧義, 即路由器有兩個或幾個位置擁有相同的置信度, 導(dǎo)致定位失敗的情況。

3.2 鄰居選擇

RLoc充分利用相連路由器間地理位置相近這一事實, 提出NE方法。該方法以路由器間連接關(guān)系、單接口路由器和商業(yè)IP地理數(shù)據(jù)庫為輸入, 為每臺單接口路由器地理定位, 通過鄰居路由器位置的不斷迭代從而定位路由器位置。單接口路由器,如圖3中1所示, 只有一個接口IP地址, 其位置為接口 IP地址的位置。根據(jù)路由器間關(guān)系, 確定每臺路由器的鄰居路由器, 利用已知的單接口路由器位置, 建立每臺路由器的鄰居路由器位置頻數(shù)矩陣：

N中ri表示鄰居路由器的第i個位置,Ii表示第i個位置出現(xiàn)的頻數(shù),CNi表示第i個位置作為路由器位置的的置信度。其中CNi表示為：

單接口路由器的位置填入了初始鄰居路由器位置頻數(shù)矩陣中, 通過不斷迭代增加多接口路由器的鄰居路由器的位置頻數(shù), 直至頻數(shù)矩陣中不再增加新數(shù)據(jù)為止。在實際數(shù)據(jù)中, 路由器可能有上千個鄰居路由器(通過物理鏈路層等相互連接等), 為能夠得到完整的頻數(shù)矩陣會造成無限循環(huán)迭代等問題, 使數(shù)據(jù)規(guī)模龐大, 無法得到數(shù)據(jù)。因此, 本文將NE方法迭代次數(shù)設(shè)置最高閾值為10。迭代10次后, 頻數(shù)矩陣中置信度最大的位置作為路由器位置。在圖 3 NE方法示意圖中, 路由器 N1與三臺單接口路由器位置分別為B、B、A和一臺多接口路由器N2相連;路由器N2與三臺單接口路由器A、A、A和一臺多接口路由器N1相連。為N1、N2路由器建立初始位置頻數(shù)矩陣為：

第一次迭代的位置頻數(shù)矩陣為：

不斷迭代, 至頻數(shù)矩陣中不再增加新的位置為止或達到迭代閾值10次為止。假設(shè)以第一次迭代后結(jié)果為最終結(jié)果, 則N1位置為B, 置信度為0.5;N2位置為A, 置信度為0.8125。

以為路由器定位的實例圖2為例, 一臺路由器有1,269臺鄰居路由器, 位置為西班牙、美國、德國、葡萄牙、中國、有170臺路由器未定位位置, 建立位置頻數(shù)矩陣：

其中有部分鄰居路由器沒有位置信息, 但置信度不高, 則路由器位置為西班牙, 置信度為0.8605。

NE方法會出現(xiàn)兩種定位失敗的情況： 位置歧義;鄰居缺失, 即鄰居路由器無法定位導(dǎo)致的頻數(shù)矩陣缺失。

3.3 綜合法

RLoc充分利用以上兩種方法的事實依據(jù), 提出IE+NE方法。該方法以IE方法和NE方法獲得的位置頻數(shù)矩陣為輸入, 結(jié)合兩個矩陣, 為每臺路由器地理定位。兩個方法的位置頻數(shù)矩陣結(jié)合：

R中I與N表示各方法獲得的位置頻數(shù)矩陣, ⊕表示：

當(dāng)I中元素Li和N中元素ri相同時, 兩個元素對應(yīng)的頻數(shù)、置信度分別均為

當(dāng)I中元素Li和N中元素ri不相同時,Li元素對應(yīng)的頻數(shù)、置信度分別為;ri元素對應(yīng)的頻數(shù)、置信度分別為

在位置頻數(shù)矩陣中置信度最大的結(jié)果作為路由器位置。在圖3 IE+NE方法示意圖中, 路由器N1有三個接口 IP地址, 與三臺單接口路由器和一臺多接口路由器相連; 路由器N2有四個接口 IP地址, 與三臺單接口路由器和一臺多接口路由器相連; 基于IE和 NE方法獲得的最終的位置頻數(shù)矩陣, 建立IE+NE方法的位置頻數(shù)矩陣, 路由器 N1的位置頻數(shù)矩陣為：

則路由器N1的位置為B,置信度為0.5834。

路由器N2的位置頻數(shù)矩陣為：

則路由器N2位置為A,置信度為0.7813。

圖 1-2是同一臺路由器不同方法定位的實例圖,使用IE+NE方法為路由器建立位置頻數(shù)矩陣：

該路由器位置為西班牙, 置信度為0.8703。

IE+NE方法會出現(xiàn)位置歧義導(dǎo)致定位失敗的情況。該方法消除了NE方法中鄰居缺失而影響定位的情況。

4 實驗及結(jié)果分析

4.1 實驗過程

4.1.1 實驗數(shù)據(jù)

以CAIDA ITDK提供的2017年10月MIDAR和 IFFINDER別名解析后獲得數(shù)據(jù)作為路由器級拓撲數(shù)據(jù)。對路由器級拓撲數(shù)據(jù) 76,520,865臺路由器進行篩選及分析, 刪除為主機的 IP地址, 獲得41,798,800臺路由器, 其中132,175臺多接口的路由器, 41,666,625臺單接口路由器。以2018年3月的IP2location商業(yè)地理數(shù)據(jù)庫定位 IP地址, 總計定位42,186,037個IP地址?；谝陨蠑?shù)據(jù), 利用本文提出的RLoc方法為132,175臺多接口路由器定位地理位置。

為評價RLoc方法的準確率, 以2017年12月IXP數(shù)據(jù)集、2018年3月DDEC工具獲取的IP地址主機名映射的位置數(shù)據(jù)作為驗證數(shù)據(jù)。其中, IXP數(shù)據(jù)是CAIDA發(fā)布IXP的json文件中提取IP前綴和位置映射關(guān)系, 從而定位路由器。當(dāng)路由器至少一個接口IP地址在IXP的IP前綴中, 則IP前綴的位置定位為路由器真實位置, 有些路由器接口 IP地址可能對應(yīng)的多個 IP前綴有多個位置, 將所有位置均定位為路由器的位置, IXP可定位1,929臺路由器。DDEC數(shù)據(jù)以DDEC工具對路由器接口IP地址的反向域名獲取帶有位置字符串的信息來定位。當(dāng)路由器至少一個接口 IP地址解析到位置, 則該位置定位為路由器真實位置, 有些路由器多個接口 IP均解析地理位置且位置不同時, 將所有可能的位置均定位為路由器的位置, DDEC數(shù)據(jù)可定位26,566臺路由器。

為對比評價方法, 本文與2017年10月CAIDA發(fā)布的路由器位置數(shù)據(jù)集比較。RLoc以路由器級拓撲數(shù)據(jù)集和 IP2location商業(yè)地理數(shù)據(jù)庫為輸入, 定位路由器級拓撲數(shù)據(jù)集相同, 可直接比較定位結(jié)果數(shù)據(jù)集。為評價輸入數(shù)據(jù)在地理定位中能夠獲得準確率的極值, 本文增加兩個極值參照數(shù)據(jù)： 真值極大、真值極小。這兩個數(shù)據(jù)可以獲得相同輸入數(shù)據(jù)情況RLoc最大、最小的準確率。

4.1.2 定位實驗

IE方法以132,175臺多接口路由器、IP2location定位數(shù)據(jù)庫為輸入, 為每臺路由器建立位置頻數(shù)矩陣, 選擇置信度最大的位置作為路由器位置。定位路由器數(shù)量在國家級、城市級數(shù)量分別為 129,223和110,989; 由于位置歧義無法定位的數(shù)量分別為2,952和 21,186。

NE方法以41,666,625臺單接口路由器、路由器間連接關(guān)系、IP2location定位數(shù)據(jù)庫為輸入, 為每臺路由器建立鄰居位置頻數(shù)矩陣, 選擇置信度最大的位置作為路由器位置。定位路由器在國家級、城市級數(shù)量分別為 120,990和 118,004; 由于位置歧義無法定位的數(shù)量分別為35和2,415; 由于鄰居缺失無法定位的數(shù)量分別為477和1083。

IE+NE方法以IE與NE方法得到的位置頻數(shù)矩陣為輸入, 結(jié)合兩個矩陣, 建立新的位置頻數(shù)矩陣, 選擇置信度最大的位置作為路由器位置。定位路由器在國家級、城市級數(shù)量分別為 131,967和126,893; 由于位置歧義無法定位的數(shù)量分別為208和5,282。

4.1.3 數(shù)據(jù)驗證

以IXP、DDEC定位的位置作為真實路由器位置,評估RLoc提出的三種方法定位的準確率。當(dāng)路由器定位結(jié)果與 IXP定位的路由器結(jié)果一致時, 定位正確, 反之, 錯誤。如圖1-2所示, 路由器使用RLoc提出的三種方法中定位結(jié)果為西班牙, IXP定位位置也是西班牙, 則路由器地理定位結(jié)果準確。

如下圖4-5所示, 分別為路由器使用IE、NE方法定位實例圖。從圖中可知, 該路由器 IE、NE和IE+NE方法定位位置為印度, 但在 IXP定位位置為新加坡, 此時該方法定位結(jié)果錯誤。路由器定位雖然結(jié)果錯誤, 但在位置頻數(shù)矩陣中都存在真值位置,新加坡。

為獲得 RLoc方法準確率的最大最小值, 利用EI+NE方法構(gòu)建的路由器位置頻數(shù)矩陣中的位置信息, 作為路由器的所有可能位置。真值極大數(shù)據(jù)為獲得最大的準確率, 即選擇與真實位置一致的位置作為路由器的位置。真值極小數(shù)據(jù)為獲得最小的準確率, 即選擇與真實數(shù)據(jù)不一致的位置作為路由器的位置。如圖4-5所示的路由器定位中, IE+NE方法得到的位置數(shù)據(jù)有印度、新加坡、澳大利亞、美國、德國、孟加拉國、肯尼亞、印度尼西亞。真值極大數(shù)據(jù)選擇新加坡為路由器的位置。相反, 真值極小數(shù)據(jù)選擇除新加坡以外的位置為路由器的位置。

同時, 利用相同的驗證數(shù)據(jù)集評價2017年10月CAIDA發(fā)布的路由器位置數(shù)據(jù)集的覆蓋率和準確率并與RLoc結(jié)果比較。

圖4 在IE方法下路由器定位結(jié)果實例圖Figure 4 Instance of router geolocation’s result in IE

圖5 在NE方法下路由器定位結(jié)果實例圖Figure 5 Instance of router geolocation’s result in NE

4.2 覆蓋率

RLoc提出的EI、NI、EI+NI獲得的數(shù)據(jù)與CAIDA數(shù)據(jù)的路由器定位覆蓋率如表1所示。

就覆蓋率而言, IE+NE方法更好, 能夠消除 NE方法中鄰居缺失而導(dǎo)致無法定位的情況, 同時也減少了IE和NE方法出現(xiàn)位置歧義情況。CAIDA數(shù)據(jù)的國家級覆蓋率與城市級覆蓋率相差較大, 這是由于IP地理定位數(shù)據(jù)庫在城市級對路由器接口定位在同一位置的情況較低, 導(dǎo)致路由器無法在城市級粒度上定位。

表1 各方法定位多接口路由器覆蓋率Table 1 The coverage of various methods to geolocate multi-interface routers

IE在國家級優(yōu)于NE,但NE在城市級優(yōu)于IE。在國家級定位中, IE方法在IP地理定位數(shù)據(jù)庫中對路由器接口 IP地址定位結(jié)果一致性更高, 出現(xiàn)位置歧義情況較小; 而NE方法不僅受位置歧義情況影響, 鄰居路由器位置缺失也降低了定位的覆蓋率。在城市級定位中, 由于 IP地理定位數(shù)據(jù)庫在城市級定位粒度更加精細, 使路由器可能的城市位置增加, IE方法產(chǎn)生了較多的位置歧義情況;而NE方法以單接口路由器的位置作為輸入, 在原有國家級定位失敗的基礎(chǔ)上并未產(chǎn)生更多位置歧義情況。

綜合而言, 在國家級, RLoc方法定位了91.54%~99.84%, CAIDA 定位了 98.90%, 兩數(shù)據(jù)基本持平。在城市級, RLoc方法定位了83.97%~96.00%,CAIDA定位了59.52%, RLoc比CAIDA數(shù)據(jù)高出了24.45%~36.48%。

4.3 準確性

以DDEC與IXP數(shù)據(jù)分別評價RLoc方法獲得的數(shù)據(jù)、極值數(shù)據(jù)和CAIDA數(shù)據(jù), 在國家級、城市級路由器定位的準確率, 如下圖 6-9所示： 其中, 堆積柱形圖表示各方法驗證路由器的總數(shù), 灰色柱形表示驗證正確的數(shù)量, 白色柱形表示驗證錯誤的數(shù)量。折線圖表示各方法的準確率。

圖6 DDEC驗證國家級各方法的準確率Figure 6 Country-level accuracy by DDEC validation

圖7 DDEC驗證城市級各方法的準確率Figure 7 City-level accuracy by DDEC validation

圖8 IXP驗證國家級各方法的準確率Figure 8 Country-level accuracy by IXP validation

圖9 IXP驗證城市級各方法的準確率Figure 9 City-level accuracy by IXP validation

就準確率而言, 在國家級利用 DDEC驗證極值范圍為 18.50%~85.27%。RLoc為 60.38%~63.20%,CAIDA為 59.11%。利用 IXP驗證極值范圍為0.62%~100.00%, RLoc為79.15%~84.78%, CAIDA為72.60%。在城市級利用 DDEC驗證極值范圍為4.73%~52.15%, RLoc為25.23%~34.69%, CAIDA為19.15%。利用 IXP驗證極值范圍為 0.57%~96.63%,RLoc為46.01%~64.95%, CAIDA為32.25%。RLoc數(shù)據(jù)無論國家級、城市級的準確率均較CAIDA的數(shù)據(jù)有顯著提升。對于輸入數(shù)據(jù)獲得最大、最小的準確率而言, RLoc方法的準確率還有一定的上升空間。

在 DDEC數(shù)據(jù)驗證準確率時, 無論國家級或城市級, 無論各方法和真值的極大均不高。這可能是因為DDEC方法對路由器接口IP地址定位準確率不高或該方法獲得的數(shù)據(jù)并非路由器真實的位置導(dǎo)致。城市級定位的準確率均較國家級準確率低。這可能是IP2location商業(yè)數(shù)據(jù)庫對IP地址定位城市級準確率不高導(dǎo)致。

RLoc提出的方法中, IE+NE較IE準確率低, 這是由于NE準確率比IE的準確率低, 導(dǎo)致IE+NE方法將兩個數(shù)據(jù)結(jié)合后準確率比IE方法低, 比NE方法高。均衡各方法的路由器定位覆蓋率和準確率,IE+NE方法結(jié)合了路由器的接口位置信息與鄰居路由器的位置信息, 效果更好。

5 局限性

本文提出了一種多接口路由器地理定位方法—RLoc, 雖然定位路由器的覆蓋率和準確率均較現(xiàn)有數(shù)據(jù)有明顯提升, 但仍存在局限性。RLoc方法以路由器級拓撲數(shù)據(jù)、商業(yè)地理定位數(shù)據(jù)庫為輸入,如果沒有這兩項工作, 該方法無法實現(xiàn)對路由器地理定位。同時, 輸入數(shù)據(jù)的質(zhì)量也將影響定位結(jié)果的質(zhì)量。

RLoc方法在實際應(yīng)用中前提條件有以下幾點：

1、每臺路由器的各接口IP地址均被發(fā)現(xiàn)。當(dāng)IP地址被正確別名解析, 且路由器的各接口 IP地址均被發(fā)現(xiàn)時, 保證了路由器的接口的完整性, 使 IE方法定位路由器定位更加準確。

2、路由器間連接關(guān)系完整并正確。當(dāng)每臺路由器的連接關(guān)系完整并正確推斷時, 保證了每臺路由器的鄰居路由器的完整性, 使NE方法定位路由器位置更加準確。

3、IP地理定位數(shù)據(jù)庫的準確性和覆蓋率高。每臺路由器接口IP地址與單接口路由器的地理定位結(jié)果直接影響了對路由器地理定位結(jié)果。

RLoc方法更適用于在路由器組網(wǎng)中, 一臺路由器的接口IP地址大多數(shù)被分配來自相同IP地址段,路由器與路由器相互通信、連接, 其位置分布也臨近。在這樣的網(wǎng)絡(luò)中, RLoc方法的準確率和覆蓋率更高。

6 結(jié)論

RLoc充分利用同一臺路由器上不同接口 IP地址在相同位置和相連路由器間地理位置相近這兩個事實, 具有比現(xiàn)有公開數(shù)據(jù)的更高的覆蓋率和準確率。本文綜合定位覆蓋率和準確率兩個方面, 選擇IE+NE方法。覆蓋率上, 國家級達到99.80%, 城市級達到 96.00%, 比 CAIDA數(shù)據(jù)分別高出 0.93%和36.48%; 準確率上, IXP驗證國家級達到82.51%, 城市級達到59.45%, 比CAIDA數(shù)據(jù)分別高出9.91%和27.20%; DDEC驗證國家級到達62.70%, 城市級達到32.96%, 比CAIDA數(shù)據(jù)分別高出3.59%和13.81%。

RLoc無需實施新的大規(guī)模網(wǎng)絡(luò)測量, 或構(gòu)建及校對時延-距離模型; 無需在人工輔助下解析域名、Whois、網(wǎng)頁等 IP地址相關(guān)信息; 易于實施與重復(fù),結(jié)果易于更新和評估。適用于對大規(guī)模路由器級網(wǎng)絡(luò)拓撲映射地理位置。

本文在定位多接口路由器時, 發(fā)現(xiàn)當(dāng)一個多接口路由器出現(xiàn)多個位置時, 可能由于路由器間共享IP地址空間所導(dǎo)致。那么, 這樣的多位置的路由器可能是國家間或城市間的網(wǎng)絡(luò)邊界點的路由器, 也是國家內(nèi)或城市內(nèi)的骨干路由器。在未來的工作中, 將著重研究多位置路由器在識別國家邊界、識別骨干路由器方面的問題。