艦船網(wǎng)絡(luò)別名解析算法研究

孫明思，李 斌

（1.吉林農(nóng)業(yè)科技學(xué)院電氣與信息工程學(xué)院，吉林吉林 132101；2.哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院，黑龍江哈爾濱 150001）

0 引 言

近年來，無線通信技術(shù)、半導(dǎo)體技術(shù)、物聯(lián)網(wǎng)技術(shù)和計算機網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展，船舶通信和網(wǎng)絡(luò)系統(tǒng)能力得到了很大提升。但是，隨著艦載數(shù)據(jù)中心[1]、艦載物聯(lián)網(wǎng)和艦載通信技術(shù)的引入，艦載通信系統(tǒng)具有艦間通信、艦岸通信和艦空通信等三維立體通信能力。艦船具有跨域航行特點[2]，導(dǎo)致艦船與岸基網(wǎng)絡(luò)通信時，無法及時有效地解析IP 地址。

傳統(tǒng)的單調(diào)別名解析方法（Monotonic ID-based Alias Resolution，MIDAR）屬于穩(wěn)定拓撲解析，不存在由于艦船跨域或者跨國家行駛，導(dǎo)致被解析地址變更和延遲問題。所以，傳統(tǒng)的MIDAR 無法提供穩(wěn)定的跨域域名解析服務(wù)。艦船網(wǎng)絡(luò)規(guī)模和行駛范圍越來越大，網(wǎng)絡(luò)構(gòu)成越來越復(fù)雜。準確地描繪網(wǎng)絡(luò)的拓撲結(jié)構(gòu)有助于發(fā)現(xiàn)網(wǎng)絡(luò)瓶頸，定位網(wǎng)絡(luò)故障，為艦載數(shù)據(jù)中心和艦載信息系統(tǒng)提供穩(wěn)定的網(wǎng)絡(luò)服務(wù)，從而進一步保障艦船行駛安全。

目前MIDAR 算法[3]在已有的基于IP ID 別名解析算法的基礎(chǔ)上，提高了IP 別名對的準確率，增加了探測的規(guī)模，在實際網(wǎng)絡(luò)探測中取得了比較好的效果。本文在MIDAR 算法的基礎(chǔ)上，通過大數(shù)據(jù)IP 地址分類和IP 別名解析對的“噪音”過濾來降低艦船跨域網(wǎng)絡(luò)解析問題，通過響應(yīng)時間消除潛在別名解析對提高解析準確率。

1 艦船網(wǎng)絡(luò)IP 別名問題描述

路由器通常有多個接口，每個接口至少配置一個IP地址，路由級拓撲發(fā)現(xiàn)是將路由器的不同接口在網(wǎng)絡(luò)中用一個節(jié)點表示的過程[4]。如果不能將路由器的不同接口合并，會出現(xiàn)一個路由器因為有多個接口存在而在網(wǎng)絡(luò)中用多個節(jié)點表示的情況，生成的拓撲不能反映真實的網(wǎng)絡(luò)連接情況[5]。與此同時，在對網(wǎng)絡(luò)拓撲進行探測的過程中，難以用唯一的標識來表示一臺路由器，這樣就使正確描繪網(wǎng)絡(luò)拓撲情況變得非常困難，對了解真實網(wǎng)絡(luò)的拓撲結(jié)構(gòu)帶來挑戰(zhàn)。

在圖1 的艦船網(wǎng)絡(luò)中，艦船A 的網(wǎng)絡(luò)設(shè)備和艦船B的網(wǎng)絡(luò)設(shè)備是探測源點。艦船A 通過衛(wèi)星通信連接岸基衛(wèi)星基站登錄互聯(lián)網(wǎng)，艦船B 通過近岸基站連接互聯(lián)網(wǎng)。R 作為中間進行轉(zhuǎn)發(fā)數(shù)據(jù)包的路由器，其中I1，I2和I3 是路由器R 的不同接口地址，C 是探測的目的節(jié)點，即遠端數(shù)據(jù)中心。圖2 展示了艦船網(wǎng)絡(luò)的探測路徑。通過IP 探測技術(shù)，船舶A 和B 分別經(jīng)過兩條單獨的IP 路徑訪問云端數(shù)據(jù)中心。而在實際的艦船網(wǎng)絡(luò)中，艦船A 和B 經(jīng)過同一路由器的相同端口訪問云端數(shù)據(jù)中心，這樣就產(chǎn)生了IP 別名解析誤差，需要這種符合實際的物理端口進行合并。

圖1 艦船網(wǎng)絡(luò)實際路由鏈路Fig.1 Real router link in the ship network

圖2 艦船網(wǎng)絡(luò)探測的IP 鏈路Fig.2 Probed IP link in the ship network

2 艦船網(wǎng)絡(luò)別名解析算法

由于艦船經(jīng)常大范圍跨域移動，導(dǎo)致別名解析準確率低的問題，并且在別名解析過程中對網(wǎng)絡(luò)流量產(chǎn)生很大影響。因此，本文以MIDAR 為基礎(chǔ)，從IP 地址分類、別名對降維和潛在別名對消除等三個方面入手，減少別名解析規(guī)模，提高解析的效率和精度。本文使用Caida Ark 項目提供的IP 鏈路探測數(shù)據(jù)集，并根據(jù)該數(shù)據(jù)集模擬船舶大范圍航行引起的大規(guī)模別名解析環(huán)境。

2.1 IP 地址集分類

根據(jù)IP 地址劃分IP 物理位置，可以大大減少后續(xù)別名解析對的匹配過程，提高匹配效率和準確性。屬于同一個路由器的IP 地址必然具有相同的地理位置，不同路由器的IP 地址可能具有不同的地理位置。因此，基于以上思想建立IP 地址相似性的樹形聚類算法。

具體做法為：首先從收集到的IP 地址中過濾出所有私有IP 地址，即保留的和適用于局域網(wǎng)內(nèi)的IP 地址；然后采用Geo IP 數(shù)據(jù)庫查詢IP 地理信息，IP 地理信息主要包括洲、國家、省/州、市和街道，以及相應(yīng)的經(jīng)緯度。依據(jù)地理信息建立樹形結(jié)構(gòu)，并根據(jù)查詢結(jié)果將IP地址放入到對應(yīng)的節(jié)點上。最后，統(tǒng)計每個地區(qū)路由器接口地址出現(xiàn)的次數(shù)。

在一個完整探測周期內(nèi)探測到10 918 370 個不同的IP 地址，按照地理位置劃分了75 606 個不同的國家和地區(qū)。這就將原問題的求解過程轉(zhuǎn)換為75 606 個子問題的求解過程，降低問題的規(guī)模。出現(xiàn)路由器接口數(shù)量最多的地區(qū)是美國，大約有150 萬個不同的IP 地址。如圖3 所示為各地區(qū)IP 地址數(shù)量。

圖3 各地區(qū)IP 地址數(shù)量Fig.3 Number of IP address in diverse areas

2.2 IP 別名解析對降維

首先收集了分布在世界30 個探測點的全球網(wǎng)絡(luò)進行探測數(shù)據(jù)，探測空間是IPv4 前24 位所有的地址共生成10 129 123 條探測路徑[6-7]。在完整探測周期內(nèi)，共探測到132 371 209 個IP 地址，去掉重復(fù)出現(xiàn)的地址以后得到10 918 370 個各不相同的IP 地址。這種現(xiàn)象從側(cè)面可以反映出探測過程中存在大量的探測冗余。統(tǒng)計各個IP 地址在探測過程中出現(xiàn)的次數(shù)，可以明顯發(fā)現(xiàn)探測過程中只出現(xiàn)1 次的IP 地址占了絕大多數(shù)。通過分析在一個完整的探測周期內(nèi)只出現(xiàn)一次的IP 地址很大可能是網(wǎng)絡(luò)的邊緣節(jié)點，但通過直觀感覺網(wǎng)絡(luò)中的邊緣節(jié)點不可能占有那么大的比例。

接下來對這些數(shù)據(jù)進行統(tǒng)計發(fā)現(xiàn)，出現(xiàn)1 次的IP 地址共有10 266 454 個，占探測到的IP 地址數(shù)量的94%。由于探測過程中可能引入“噪聲”，所以在探測周期內(nèi)出現(xiàn)1 次的IP 地址有兩種可能：

1）來自路由器接口地址，該接口在探測周期內(nèi)只被探測到一次；

2）非路由器接口地址，只有一種可能就是該地址來自探測的目標地址集合。

首先將只出現(xiàn)一次的IP 地址加入一個集合S1中，從收集到的原始探測數(shù)據(jù)中找出所有的目的地址，將這些目標地址加入到集合S2中，然后從集合S1中去掉S1和S2的交集。通過計算得出10 266 454 個（S1）出現(xiàn)1 次的IP 地址中有307 428 個IP 地址來自路由器接口地址，有9 959 026 個IP 地址是來自探測的目標地址集合S2。這些來自探測目標地址集合的IP 地址一部分是未分配的IP 地址，一部分是分配給主機的IP 地址。所以需要將這9 959 026 個IP 地址從探測到的IP 地址集合中去除，這樣就將探測到的IP 地址空間從千萬級降低到百萬級別，大大降低問題的規(guī)模，為后續(xù)階段的處理提供方便。

2.3 潛在IP 別名對的消除

用MIDAR 算法對所屬同一個IP 地址集合進行別名解析，將IP 地址集合用具有相似IP ID 的增長率的IP 地址進一步劃分成更小的集合。得到的IP 地址集合是潛在的IP 別名對，對這些潛在別名對用以下基于響應(yīng)時間的別名解析算法進行處理，得到最終處理的IP 別名對，達到IP 別名解析的目的。

判斷兩個候選別名IP ID 值的順序是否一致，也就是說，所產(chǎn)生的值的遞增順序應(yīng)該與使用共享計數(shù)器一致。因為IP ID 值的范圍是0～65 535，定義符號X＜Y表示序列空間的小于關(guān)系。使用下列步驟來判斷地址A和B是否是別名。首先，發(fā)送一個探測數(shù)據(jù)包給A，等待1 ms，然后發(fā)送探測數(shù)據(jù)包給B。假設(shè)響應(yīng)數(shù)據(jù)包的IP ID 值分別為A1和B1。檢查A1和B1順序是否一致，并且彼此靠近，即A1-10＜B1＜A1+200。如果在這個范圍，等待400 ms，發(fā)送探測數(shù)據(jù)包給B，等待1 ms，然后發(fā)送探測數(shù)據(jù)包給A。隨后檢查B2和A2的IP ID 的值是否在B2-10＜A2＜B2+200 的區(qū)間，并滿足A1＜A2和B1＜B2的條件。如果這些條件都能得到滿足，則判斷A和B是別名，否則判斷A和B不是別名。

由于無法知道收集到的IP ID 生成的確切時間，因此在比較值的時候使用了一個誤差范圍。間隔1 ms 發(fā)送探測數(shù)據(jù)包，由于網(wǎng)絡(luò)中存在負載平衡等其他因素，會導(dǎo)致數(shù)據(jù)包在網(wǎng)絡(luò)中出現(xiàn)路由不一致的現(xiàn)象。但是這并不影響對兩個IP 別名對的判斷。

3 實驗驗證與分析

使用兩組真實的數(shù)據(jù)集對算法進行驗證。R&E是由研究和教育網(wǎng)絡(luò)提供的一個已知網(wǎng)絡(luò)拓撲（CAnet，CENIC，GEANT，I-Light，Internet2 和NLR），Tier1 是一個由一級ISP 提供的已知網(wǎng)絡(luò)拓撲。首先采用隨機選取不同物理地址的方式模擬艦船大范圍跨域航行，并在該條件下驗證算法是否能與已知網(wǎng)絡(luò)拓撲的別名情況達成一致。

本文采用2017 年3 月份的數(shù)據(jù)進行實驗對比，用TCP 的探測方式對Tier1 和R&E 數(shù)據(jù)集分別做探測，分別用時30.1 s 和13.1 s。請注意，該測試沒有針對整個MIDAR 系統(tǒng)，特別是沒有測試多個測量方法、多個階段或自適應(yīng)探測間距。本文算法和MIDAR 的運行結(jié)果如表1 所示。表1 中，TP 為判斷正確的正確率，F(xiàn)P 為判斷錯誤的正確率，PPV 為精確率，即計算為正確的數(shù)據(jù)中計算正確的數(shù)量，PPV 由TP（/TP+FP）計算而得。

表1 實驗結(jié)果對比Table 1 Experimental results of different methods

如表1所示，Tier1和R&E 數(shù)據(jù)集的待測試別名對數(shù)量分別為62 817和2 307。Tier1是R&E 數(shù)據(jù)量的27倍，說明Tier1 解析范圍更大。對比較大的數(shù)據(jù)集Tier1，本文算法在別名解析的精確率上好于MIDAR 算法，得到的錯誤別名對也少于MIDAR 算法。相比MIDAR 算法，本文提出的算法精度提高了17%。在Tier1 數(shù)據(jù)集上，本文提出的算法與傳統(tǒng)的MIDAR 算法正確判斷的正確率相當，解析錯誤判斷的正確率優(yōu)于傳統(tǒng)MIDAR。從而，本文提出算法精確率優(yōu)于傳統(tǒng)MIDAR。但是對于R&E 規(guī)模較小，無法體現(xiàn)大規(guī)模解析環(huán)境，這兩個算法沒有明顯區(qū)別，別名解析的正確率和錯誤的別名對數(shù)量都相差不大。因此可以得出結(jié)論，本文算法在別名解析的精度方面提高顯著。

4 結(jié) 論

艦船網(wǎng)絡(luò)的穩(wěn)定對艦船安全行駛具有重要作用。艦船跨域行駛對傳統(tǒng)固定IP 別名解析方法提出了挑戰(zhàn)。特別是在跨區(qū)域、跨國家的行駛過程中容易產(chǎn)生錯誤解析別名對數(shù)量呈非線性增長的情況。本文通過改進MIDAR 算法，通過IP 地理和主機劃分兩種策略，在解析前縮減解析規(guī)模，并且將問題劃分為若干個互不相關(guān)的子問題進行別名解析，在準確性和效率等方面都取得了良好的效果。在后期通過響應(yīng)時間對解析出的潛在別名對進行驗證，相較傳統(tǒng)MIDAR 方法，本文方法提高了17%的準確率。因此，本文提出的方法實現(xiàn)了艦船跨域行駛中的艦船網(wǎng)絡(luò)別名解析功能，并具有較高的準確率，為艦船網(wǎng)絡(luò)的安全穩(wěn)定提供了一個有效的解決思路。