艦船網絡別名解析算法研究

摘" 要： 針對當前IP別名解析算法效率低和準確度不高的問題，在單調別名解析（MIDAR）算法基礎上，提出策略優化的改進算法。該算法通過IP地址分類和IP別名解析對的“噪音”過濾解決艦船跨域行駛的IP解析問題，極大地降低了別名解析規模，通過IP響應時間消除潛在的別名對，實現了文中的改進算法。實驗結果表明，在Ramp;E和Tier?1兩個數據集上驗證了所提算法的有效性，并且模擬艦船跨域行駛時大規模別名解析環境，相比傳統MIDAR算法，所提算法準確率提高了17%。

關鍵詞： 艦船網絡; IP別名解析; 單調別名解析算法; IP地址分類; IP身份探測; 算法驗證

中圖分類號： TN915.07?34; TP393" " " " " " " " " 文獻標識碼： A" " " " " " " " " 文章編號： 1004?373X（2019）21?0032?04

Abstract： An improved algorithm of strategy optimization is proposed in this paper on the basis of MIDAR algorithm to solve the problem of low efficiency and low accuracy of IP alias analysis algorithm. This algorithm can solve IP parsing problem in ship′s cross?domaim navigation by IP address classification and noise filtering in the alias pairs， greatly reduce the scale of alias resolution， and eliminate the potential alias pairs by IP response time， so as to implement the improved algorithm proposed in this paper. The effectiveness of the proposed algorithm has been verified on the R amp; E and Tier?1 data sets in an experiment. The environment of large?scale aliases resolution during ship navigation was simulated. In comparison with the traditional MIDAR， the accuracy of this algorithm is increased by 17%.

Keywords： ship network; IP alias resolution; monotonic ID?based alias resolution algorithm; IP address classification; IP identification probing; algorithm verification

0" 引" 言

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

傳統的單調別名解析方法（Monotonic ID?based Alias Resolution，MIDAR）屬于穩定拓撲解析，不存在由于艦船跨域或者跨國家行駛，導致被解析地址變更和延遲問題。所以，傳統的MIDAR無法提供穩定的跨域域名解析服務。艦船網絡規模和行駛范圍越來越大，網絡構成越來越復雜。準確地描繪網絡的拓撲結構有助于發現網絡瓶頸，定位網絡故障，為艦載數據中心和艦載信息系統提供穩定的網絡服務，從而進一步保障艦船行駛安全。

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

1" 艦船網絡IP別名問題描述

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

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

2" 艦船網絡別名解析算法

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

2.1" IP地址集分類

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

具體做法為：首先從收集到的IP地址中過濾出所有私有IP地址，即保留的和適用于局域網內的IP地址;然后采用Geo IP數據庫查詢IP地理信息，IP地理信息主要包括洲、國家、省/州、市和街道，以及相應的經緯度。依據地理信息建立樹形結構，并根據查詢結果將IP地址放入到對應的節點上。最后，統計每個地區路由器接口地址出現的次數。

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

2.2" IP別名解析對降維

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

接下來對這些數據進行統計發現，出現1次的IP地址共有10 266 454個，占探測到的IP地址數量的94%。由于探測過程中可能引入“噪聲”，所以在探測周期內出現1次的IP地址有兩種可能：

1） 來自路由器接口地址，該接口在探測周期內只被探測到一次;

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

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

2.3" 潛在IP別名對的消除

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

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

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

3" 實驗驗證與分析

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

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

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

4" 結" 論

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

參考文獻

[1] 楊官霞.船舶移動網絡中節點跨域訪問方法的研究[J].艦船科學技術，2018，40（7A）：142?144.

YANG Guanxia. Research on node cross domain access method in ship mobile network [J]. Ship science and technology， 2018， 40（7A）： 142?144.

[2] 王寧，張聰沛.艦船云存儲數據中心密文訪問控制機制的優化技術[J].艦船科學技術，2018，40（4A）：118?120.

WANG Ning， ZHANG Congpei. Optimization technology of cipher access control mechanism in ship cloud storage data center [J]. Ship science and technology， 2018， 40（4A）： 118?120.

[3] KARDES H， GUNES M H， SARAC K. Graph Based Induction of unresponsive routers in Internet topologies [J]. Computer networks， 2015， 81： 178?200.

[4] KEYS K， HYUN Y， LUCKIE M， et al. Internet?scale IPv4 alias resolution with MIDAR [J]. IEEE/ACM transactions on networking， 2013， 21（2）： 383?399.

[5] HE Y H， CHEN X， WANG H. Modeling correlated samples via sparse matrix Gaussian graphical models [J]. Frontiers of information technology amp; electronic engineering， 2013， 14（2）： 107?117.

[6] YINGWEI L， SUNDARARAJAN N， SARATCHANDRAN P. Performance evaluation of a sequential minimal radial basis function （RBF） neural network learning algorithm [J]. IEEE transactions on neural networks， 1998， 9（2）： 308?318.

[7] 王文，鄭建生.基于FPGA的TCP/IP網絡通信系統的設計與實現[J].現代電子技術，2018， 41（8）：5?9.

WANG Wen， ZHENG Jiansheng. Design and implementation of TCP/IP network communication system based on FPGA [J]. Modern electronics technique， 2018， 41（8）： 5?9.

[8] KEYS K. Internet?scale IPv4 alias resolution with MIDAR： system architecture [J]. IEEE/ACM transactions on networking， 2013， 21（2）： 383?399.

[9] 馬海波，周景森，王德廣.結合自治系統號擴展IP地址空間的研究[J].計算機應用與軟件，2015，32（7）：119?122.

MA Haibo， ZHOU Jingsen， WANG Deguang. Study on expansion of IP address space combining with autonomous system number [J]. Computer applications and software， 2015， 32（7）： 119?122.

[10] HOLBERT B， TATI S， SILVESTRI S， et al. Network topology inference with partial information [J]. IEEE transactions on network amp; service management， 2015， 12（3）： 406?419.