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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

2 相關(guān)工作

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

路由器級(jí)拓?fù)錅y量： 路由器級(jí)拓?fù)渫ǔＪ菍儆谕慌_(tái)路由器的接口組合, 一個(gè)節(jié)點(diǎn)代表著一個(gè)主機(jī)或一個(gè)多接口的路由器。如果節(jié)點(diǎn)間相互連接, 則節(jié)點(diǎn)間一定有接口位于同一個(gè) IP廣播域。在Traceroute測量數(shù)據(jù)中, 存在不可忽略的路由陷阱,如： 負(fù)載均衡和路由改變情況等。路由陷阱需要進(jìn)行別名解析, 把屬于同一臺(tái)路由器的 IP地址映射到該路由器上。

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

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

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

為能滿足更廣泛的應(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ù)庫推測等各方法對(duì)IP地理定位, 精確度可為國家、城市、甚至于郵編級(jí)。宋健等[13]提出了一種基于IP地址庫之間差異對(duì)比來評(píng)估可信程度的方法, 并發(fā)現(xiàn)IP地址庫之間差異所存在的規(guī)律。王婷等[14]提出IPGEL方法有效提高已有 IP定位數(shù)據(jù)庫的可用性。Gharaibeh等[15]評(píng)估了多種地理定位數(shù)據(jù)庫在路由器定位的可靠性。本文綜合各類商業(yè)IP地理定位數(shù)據(jù)庫質(zhì)量, 選擇使用IP2location數(shù)據(jù)庫為路由器各接口IP地址地理定位, 它較MaxMind等數(shù)據(jù)庫的國家城市粒度更精細(xì)。

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

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

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

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

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

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

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

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

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

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

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

3.2 鄰居選擇

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

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

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

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

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

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

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

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

3.3 綜合法

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

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

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

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

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

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

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

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

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

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

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

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

4.1 實(shí)驗(yàn)過程

4.1.1 實(shí)驗(yàn)數(shù)據(jù)

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

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

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

4.1.2 定位實(shí)驗(yàn)

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

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

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

4.1.3 數(shù)據(jù)驗(yàn)證

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

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

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

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

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

圖5 在NE方法下路由器定位結(jié)果實(shí)例圖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)致無法定位的情況, 同時(shí)也減少了IE和NE方法出現(xiàn)位置歧義情況。CAIDA數(shù)據(jù)的國家級(jí)覆蓋率與城市級(jí)覆蓋率相差較大, 這是由于IP地理定位數(shù)據(jù)庫在城市級(jí)對(duì)路由器接口定位在同一位置的情況較低, 導(dǎo)致路由器無法在城市級(jí)粒度上定位。

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

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

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

4.3 準(zhǔn)確性

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

圖6 DDEC驗(yàn)證國家級(jí)各方法的準(zhǔn)確率Figure 6 Country-level accuracy by DDEC validation

圖7 DDEC驗(yàn)證城市級(jí)各方法的準(zhǔn)確率Figure 7 City-level accuracy by DDEC validation

圖8 IXP驗(yàn)證國家級(jí)各方法的準(zhǔn)確率Figure 8 Country-level accuracy by IXP validation

圖9 IXP驗(yàn)證城市級(jí)各方法的準(zhǔn)確率Figure 9 City-level accuracy by IXP validation

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

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

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

5 局限性

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

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

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

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

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

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

6 結(jié)論

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

RLoc無需實(shí)施新的大規(guī)模網(wǎng)絡(luò)測量, 或構(gòu)建及校對(duì)時(shí)延-距離模型; 無需在人工輔助下解析域名、Whois、網(wǎng)頁等 IP地址相關(guān)信息; 易于實(shí)施與重復(fù),結(jié)果易于更新和評(píng)估。適用于對(duì)大規(guī)模路由器級(jí)網(wǎng)絡(luò)拓?fù)溆成涞乩砦恢谩?/p>

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