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

摘" 要： 針對(duì)當(dāng)前IP別名解析算法效率低和準(zhǔn)確度不高的問(wèn)題，在單調(diào)別名解析（MIDAR）算法基礎(chǔ)上，提出策略優(yōu)化的改進(jìn)算法。該算法通過(guò)IP地址分類和IP別名解析對(duì)的“噪音”過(guò)濾解決艦船跨域行駛的IP解析問(wèn)題，極大地降低了別名解析規(guī)模，通過(guò)IP響應(yīng)時(shí)間消除潛在的別名對(duì)，實(shí)現(xiàn)了文中的改進(jìn)算法。實(shí)驗(yàn)結(jié)果表明，在Ramp;E和Tier?1兩個(gè)數(shù)據(jù)集上驗(yàn)證了所提算法的有效性，并且模擬艦船跨域行駛時(shí)大規(guī)模別名解析環(huán)境，相比傳統(tǒng)MIDAR算法，所提算法準(zhǔn)確率提高了17%。

關(guān)鍵詞： 艦船網(wǎng)絡(luò); IP別名解析; 單調(diào)別名解析算法; IP地址分類; IP身份探測(cè); 算法驗(yàn)證

中圖分類號(hào)： TN915.07?34; TP393" " " " " " " " " 文獻(xiàn)標(biāo)識(shí)碼： A" " " " " " " " " 文章編號(hào)： 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" 引" 言

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

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

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

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

路由器通常有多個(gè)接口，每個(gè)接口至少配置一個(gè)IP地址，路由級(jí)拓?fù)浒l(fā)現(xiàn)是將路由器的不同接口在網(wǎng)絡(luò)中用一個(gè)節(jié)點(diǎn)表示的過(guò)程[4]。如果不能將路由器的不同接口合并，會(huì)出現(xiàn)一個(gè)路由器因?yàn)橛卸鄠€(gè)接口存在而在網(wǎng)絡(luò)中用多個(gè)節(jié)點(diǎn)表示的情況，生成的拓?fù)洳荒芊从痴鎸?shí)的網(wǎng)絡(luò)連接情況[5]。與此同時(shí)，在對(duì)網(wǎng)絡(luò)拓?fù)溥M(jìn)行探測(cè)的過(guò)程中，難以用唯一的標(biāo)識(shí)來(lái)表示一臺(tái)路由器，這樣就使正確描繪網(wǎng)絡(luò)拓?fù)淝闆r變得非常困難，對(duì)了解真實(shí)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)帶來(lái)挑戰(zhàn)。

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

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

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

2.1" IP地址集分類

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

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

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

2.2" IP別名解析對(duì)降維

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

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

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

2） 非路由器接口地址，只有一種可能就是該地址來(lái)自探測(cè)的目標(biāo)地址集合。

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

2.3" 潛在IP別名對(duì)的消除

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

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

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

3" 實(shí)驗(yàn)驗(yàn)證與分析

使用兩組真實(shí)的數(shù)據(jù)集對(duì)算法進(jìn)行驗(yàn)證。Ramp;E是由研究和教育網(wǎng)絡(luò)提供的一個(gè)已知網(wǎng)絡(luò)拓?fù)洌–Anet，CENIC，GEANT，I?Light，Internet2和NLR），Tier1是一個(gè)由一級(jí)ISP提供的已知網(wǎng)絡(luò)拓?fù)?。首先采用隨機(jī)選取不同物理地址的方式模擬艦船大范圍跨域航行，并在該條件下驗(yàn)證算法是否能與已知網(wǎng)絡(luò)拓?fù)涞膭e名情況達(dá)成一致。

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

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

4" 結(jié)" 論

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

參考文獻(xiàn)

[1] 楊官霞.船舶移動(dòng)網(wǎng)絡(luò)中節(jié)點(diǎn)跨域訪問(wèn)方法的研究[J].艦船科學(xué)技術(shù)，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] 王寧，張聰沛.艦船云存儲(chǔ)數(shù)據(jù)中心密文訪問(wèn)控制機(jī)制的優(yōu)化技術(shù)[J].艦船科學(xué)技術(shù)，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網(wǎng)絡(luò)通信系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].現(xiàn)代電子技術(shù)，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] 馬海波，周景森，王德廣.結(jié)合自治系統(tǒng)號(hào)擴(kuò)展IP地址空間的研究[J].計(jì)算機(jī)應(yīng)用與軟件，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.