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

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

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

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

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

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

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

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

1 相關工作

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

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

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

2.1 路由器排序

若：

分組內排序：

分組間排序：

去重：

2.2 路徑聚類

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

其中，是簇的個數，是第個簇，是簇中的點，m是簇中心。

在使用最優值聚類得到的個簇中，統計每個簇中屬于同一C類網的節點數，計算與該C類網中在線IP數量的比值：

若：

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

3 方法分析

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

3.1 網絡路徑與地理位置相似性分析

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

圖1 兩種網絡架構

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

3.2 路由穩定性分析

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

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

由圖2可知，在對網絡中的目標進行網絡測量時，超過95%的數據包經相同的路由器進行轉發，這表明網絡中的路由是穩定的。

4 實驗

4.1 數據源

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

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

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

4.2 實驗環境

實驗環境為Ubuntu 16.04，32核CPU，512G內存，2*2080Ti顯卡，Python 3.7。

4.3 實驗方法

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

表1 各城市IP存活情況

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

4.4 實驗結果

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

表2 各城市可靠地標數量

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

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

表3 目標城市級定位測試

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

5 結束語

本文基于IP拓撲路徑上的相似性，使用K-Means聚類方法將IP進行聚類，從而實現對IP位置數據庫中在線IP的可靠性評估，實驗結果表明，本章方法評估后的可靠地標比例較數據庫的可靠性，提高了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定位方法研究與實現[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年重點聯合基金項目圖像隱蔽通信的行為發現與主體定位關鍵問題研究（U1804263）