◆劉淵博 甘勇 張鶴林 賈東偉

基于拓撲路徑聚類的城市級地標評估方法

◆劉淵博1甘勇1，2張鶴林1賈東偉1

（1.鄭州輕工業(yè)大學（鄭州） 計算機與通信工程學院 河南 450002；2.鄭州工程技術學院（鄭州） 河南 450044）

從IP位置數(shù)據(jù)庫中獲得城市級地標，是地標獲取的最直接的方法。但由于當前IP位置數(shù)據(jù)庫存在初始數(shù)據(jù)來源不明、數(shù)據(jù)庫構建方法不公開及地標可靠性低的問題，為此本文提出了一種基于拓撲路徑聚類的城市級地標評估方法，通過對IP2Location數(shù)據(jù)庫中地標的存活性探測，以北京、上海、紐約、東京四個城市為例獲取數(shù)據(jù)庫中在線地標的拓撲路徑，并將排序后的IP地址映射到路由器空間中，使用K-Means算法進行聚類，實現(xiàn)對地標的可靠性評估。實驗結(jié)果表明，評估后的地標可靠性提高了15%以上，可用于支撐高可靠定位。

拓撲路徑探測；地標評估；聚類算法

網(wǎng)絡實體定位技術是利用已知IP標識的網(wǎng)絡實體設備來確定其地理位置，它可以用來提高網(wǎng)絡空間的安全，優(yōu)化網(wǎng)絡性能以及提供基于位置的服務等[1]?，F(xiàn)如今，網(wǎng)絡實體地標作為定位技術所需的關鍵數(shù)據(jù)，主要有兩類：城市級地標和街道級地標，本文主要關注城市級地標。網(wǎng)絡實體地標是將網(wǎng)絡實體映射到地理位置的基準點，根據(jù)現(xiàn)有的研究進展，國內(nèi)外一些研究機構組織并構建了IP位置數(shù)據(jù)庫，如Whois[2]、MaxMind[3]、IP2Location[4]、百度[5]等。在上述數(shù)據(jù)庫中，此類地標多用于實驗研究，實驗通常選取交集，即選取多個位置數(shù)據(jù)庫中地理位置一致的IP 地址[6]。但是該方法存在很多限制條件，數(shù)據(jù)來源不準確、可靠性差等問題都會影響定位技術的準確率，因此從IP 位置數(shù)據(jù)庫直接獲取地標的方法需要更進一步的研究改進。

1 相關工作

針對當前IP位置數(shù)據(jù)庫存在的問題有很多學者做了大量研究，文獻[7]提出了一種基于Internet論壇的城市級地標獲取算法，明顯提高了城市級網(wǎng)絡實體地理的準確率。文獻[8]提出了一種基于投票的城市級地標評估方法，該方法分析了中國大陸不同地理粒度的IP地址和數(shù)據(jù)塊的分布和特征，并進行了比較，最后得到初步評估結(jié)果。文獻[9]提出了一種城市級地標評估方法GeoCop（Geolocation Cop），利用邊緣路由器關聯(lián)的候選地標，進行位置投票確定路由器的位置，從而實現(xiàn)數(shù)據(jù)庫中城市級地標的評估。文獻[10]提出了一種基于路由識別的城市級地標評估算法，有效減少了路由器標識的開銷，城市級地標的準確率也更高。文獻[11]提出了基于 POP 網(wǎng)絡分析的城市級地標評估方法，該方法根據(jù)節(jié)點的位置來進行準確性評估，評估結(jié)果可靠且效率高。綜上，結(jié)合路由器、POP網(wǎng)絡、多庫查詢的城市級地標評估方法在一定程度上提高了地標的準確率，但這些方法在數(shù)據(jù)量不足的情況下是無法進行有效評估的。

2 本文基本原理及主要步驟

本文首先對數(shù)據(jù)庫中聲稱位于同一城市的在線IP進行網(wǎng)絡路徑測量，獲得從探測源到各IP的網(wǎng)絡路徑；其次提取各IP網(wǎng)絡路徑上的路由器，將所有路徑上的路由器進行排序，并以排序結(jié)果為基準構建多維路由器空間；其后根據(jù)IP的拓撲路徑，將IP映射到路由器空間中，并使用K-Means算法對IP進行聚類，得到多個聚類簇；最后，依據(jù)數(shù)據(jù)庫的平均準確率選擇可靠的IP簇。主要分為以下幾個過程：

2.1 路由器排序

若：

分組內(nèi)排序：

分組間排序：

去重：

2.2 路徑聚類

利用構建的路由器空間及各IP的探測路徑，將各IP映射到路由空間中，并使用K-Means方法對IP進行聚類。在使用K-Means聚類時，需要首先指定聚類值。本文使用elbow-method獲得聚類的最優(yōu)值為128，在最優(yōu)值下使用K-Means方法對IP進行聚類。SSE（Sum of the Squared Errors，誤差平方和）是elbow-method的核心指標：

其中，是簇的個數(shù)，是第個簇，是簇中的點，m是簇中心。

在使用最優(yōu)值聚類得到的個簇中，統(tǒng)計每個簇中屬于同一C類網(wǎng)的節(jié)點數(shù)，計算與該C類網(wǎng)中在線IP數(shù)量的比值：

若：

在篩選可靠簇時，將每個簇中的所有IP都是可靠的，則該簇為可靠簇。在得到可靠簇后，將簇中節(jié)點對應的IP與城市的地理位置相關聯(lián)，得到可靠地標，從而實現(xiàn)對地標的可靠性評估。

3 方法分析

要實現(xiàn)數(shù)據(jù)包在網(wǎng)絡中的快速準確轉(zhuǎn)發(fā)，路由器需要穩(wěn)定、簡單的路由表。為此，ISP（Internet Service Provider，互聯(lián)網(wǎng)服務提供商）通常使用CIDR（Classless Inter Domain Routing，無類別域間路由選擇）策略來減輕互聯(lián)網(wǎng)上路由器的負擔，同時，ISP通常采取穩(wěn)定的路由策略（即對同一IP開展兩次路由測量，兩次測量的路徑相同）來提高路由器的轉(zhuǎn)發(fā)效率。這使得同一區(qū)域的網(wǎng)絡實體，其IP地址在網(wǎng)絡拓撲上也體現(xiàn)出區(qū)域性。本文方法利用這一特點，基于待評估地標在網(wǎng)絡空間上的路徑相似性，實現(xiàn)地標評估。

3.1 網(wǎng)絡路徑與地理位置相似性分析

當前網(wǎng)絡構架大致可分為分層和網(wǎng)狀兩種，如下圖1所示。

圖1 兩種網(wǎng)絡架構

無論是分層架構還是網(wǎng)狀架構，當從同一探測源出發(fā)，到兩個IP所經(jīng)過的路由相似時，說明從探測源到IP所經(jīng)過的路徑大致相同，路徑的相似程度越高，說明兩個IP的探測路徑上，最后一個相同的路由器距離IP越近。當兩個IP所具有的最近路由器到IP的跳數(shù)越小，根據(jù)CIDR策略可知，這兩個IP在地理空間上的位置越接近。

3.2 路由穩(wěn)定性分析

為分析網(wǎng)絡中的路由穩(wěn)定性，本文使用探測源“8.210.164.165”對目標IP“103.1.8.254”進行了網(wǎng)絡路徑測量。探測源每間隔10秒對目標發(fā)起一次路由測量，整個路由測量持續(xù)24小時，得到8640條路徑，包含5條不同路徑，各路徑所占的比例如下圖2所示。

圖2 各探測路徑占所有路徑的比例

由圖2可知，在對網(wǎng)絡中的目標進行網(wǎng)絡測量時，超過95%的數(shù)據(jù)包經(jīng)相同的路由器進行轉(zhuǎn)發(fā)，這表明網(wǎng)絡中的路由是穩(wěn)定的。

4 實驗

4.1 數(shù)據(jù)源

VP S探測源：8.210.164.165，位于中國香港，配置為Ubuntu 16.04，4核CPU，16G內(nèi)存，10M帶寬。

待評估IP段：北京、上海、紐約、東京，每個城市選擇8個B類網(wǎng)段。

可靠地標：用于驗證評估后地標的可靠性，北京、上海、紐約、東京四個城市，每個城市100個可靠地標。

4.2 實驗環(huán)境

實驗環(huán)境為Ubuntu 16.04，32核CPU，512G內(nèi)存，2*2080Ti顯卡，Python 3.7。

4.3 實驗方法

分別對北京、上海、紐約、東京的8個B類IP網(wǎng)段進行存活性探測，得到各城市存活IP數(shù)量如表1所示。

表1 各城市IP存活情況

對四個城市的存活IP進行網(wǎng)絡路徑測量，對每個城市的每個B類網(wǎng)段，分別構建路由器空間，并將對應網(wǎng)段中的存活IP映射到路由器空間上。

4.4 實驗結(jié)果

利用上述方法中得到的最優(yōu)k值，在每個城市的每個B類網(wǎng)段中，進行IP路徑探測，將IP地址映射到路由器空間后，使用K-Means聚類方法對IP地址進行聚類。在每個聚類簇中，統(tǒng)計屬于同一C類網(wǎng)段的IP地址數(shù)量，并計算該IP數(shù)量值與存活性探測結(jié)果中該C類網(wǎng)段中的存活IP數(shù)之比。將可靠簇中的IP與城市位置相關聯(lián)，則該地標為可靠地標，各城市的可靠地標數(shù)量如表2所示。

表2 各城市可靠地標數(shù)量

從表2可以看出，評估后的可靠地標占比大于85%，該值相比于數(shù)據(jù)庫的可靠性70%，提高了15%以上。

為驗證評估后地標的可靠性，在北京、上海、紐約、東京四個城市分別使用評估后的地標對100個已知地理位置的IP進行城市級定位。城市級定位方法如下：從同一探測源，分別對目標和地標進行網(wǎng)絡拓撲探測，獲得網(wǎng)絡路徑。從探測源到目標和地標的網(wǎng)絡路徑上，提取最后3跳路由器IP構成集合RT和RL，若RT與RL的交集不為空，則成功對目標實現(xiàn)城市級定位，當城市級定位結(jié)果與目標實際城市位置相同，意味著對目標實現(xiàn)了準確定位。各城市的定位測試結(jié)果如表3所示。

表3 目標城市級定位測試

由表3得出，使用評估后的地標對目標進行城市級定位時，所有成功定位IP均被準確定位，定位準確率超過95%。由于定位準確率依賴于地標可靠性，因此，該實驗從側(cè)面印證了本文評估方法的有效性。上述實驗測試結(jié)果也表明了本文提出的方法能夠有效對在線地標的城市級位置進行評估，評估后的地標能夠用于支撐網(wǎng)絡目標的可靠定位。

5 結(jié)束語

本文基于IP拓撲路徑上的相似性，使用K-Means聚類方法將IP進行聚類，從而實現(xiàn)對IP位置數(shù)據(jù)庫中在線IP的可靠性評估，實驗結(jié)果表明，本章方法評估后的可靠地標比例較數(shù)據(jù)庫的可靠性，提高了15%以上，使用評估后的可靠地標進行定位，城市級定位準確率達到95%以上。

[1]王占豐，馮徑，邢長友, 等. IP 定位技術的研究[J].軟件學報，2014.

[2]Whois. IP require. www.whois.com.

[3]IP2Location. http://www.ip2location.com/.

[4]MaxMind. http://www.maxmind.com/.

[5]Baidu. http://lbsyun.baidu.com.

[6]邢子娟. 基于多點路由器測量的IP定位方法研究與實現(xiàn)[D]. 東南大學，2019.

[7]Guo C，Liu Y，Shen W，et al.Mining the Web and the Internet for Accurate IP Address Geolocations[C].IEEE INFOCOM 2009.IEEE，2009：2841-2845.

[8]Li H，He Y，Xi R，et al.A Complete Evaluation of the Chinese IP Geolocation Databases[C].International Conference on Intelligent Computation Technology and Automation.IEEE，2016：13-17.

[9]Wang T，Xu K，Song J，et al.An Optimization Method for the Geolocation Databases of Internet Hosts Based on Machine Learning[J].Mathematical Problems in Engineering，2015（10）：1-17.

[10]Ma T，Liu F，Zhang F，et al.An Landmark Evaluation Algorithm Based on Router Identification and Delay Measurement[C].International Conference on Artificial Intelligence and Security.Springer，Cham，2019：163-177.

[11]Shavitt Y，Zilberman N.A Geolocation Databases Study[J].IEEE Journal on Selected Areas in Communications， 2011，29（10）：2044-2056.

[12]Manaf Gharaibeh，Anant Shah，Bradley Huffaker，et al.A Look at Router Geolocation in Public and Commercial Databases[C].Proceedings of ACM International Conference on Internet Measurement Conference，2017：463-469.

2018年重點聯(lián)合基金項目圖像隱蔽通信的行為發(fā)現(xiàn)與主體定位關鍵問題研究（U1804263）