王則林，郝水俠

(1.南通大學(xué) 杏林學(xué)院，江蘇 南通 226000； 2.南通大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南通 226000； 3.江蘇師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，江蘇 徐州 221116) (*通信作者電子郵箱sxhao@jsnu.edu.cn)

運(yùn)用差分演化算法實(shí)現(xiàn)包匹配多層核心基的提取

王則林1,2，郝水俠3*

(1.南通大學(xué) 杏林學(xué)院，江蘇 南通 226000； 2.南通大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南通 226000； 3.江蘇師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，江蘇 徐州 221116) (*通信作者電子郵箱sxhao@jsnu.edu.cn)

針對(duì)網(wǎng)絡(luò)防火墻、路由器等設(shè)備中包匹配的速度問題，提出運(yùn)用差分演化算法實(shí)現(xiàn)包匹配多層核心基的提取。該算法運(yùn)用多層基礎(chǔ)基描述包的多層特征，在每層中分別運(yùn)用差分演化算法進(jìn)行比特基和實(shí)體基的提取，運(yùn)用平均自信息和平均互信息量衡量基礎(chǔ)基選擇的優(yōu)劣。這種方法可以根據(jù)規(guī)則庫(kù)實(shí)際規(guī)模選擇提取比特實(shí)體基的層數(shù)，非常適應(yīng)規(guī)則庫(kù)的增長(zhǎng)。實(shí)驗(yàn)結(jié)果表明，所提算法在時(shí)間效率、空間效率方面相對(duì)于已有的遞歸數(shù)據(jù)流匹配算法和基于實(shí)數(shù)編碼的差分演化的包匹配算法，綜合性能最優(yōu)。

包匹配；差分演化算法；平均自信息；平均互信息

在防火墻、路由器等網(wǎng)絡(luò)設(shè)備中，包匹配的速度決定著網(wǎng)絡(luò)性能。對(duì)于包匹配的研究許多學(xué)者提出了很多思路。大體可以分成兩類：傳統(tǒng)的方法[1-9]和基于智能處理的方法[10-12]。傳統(tǒng)的方法在速度和內(nèi)存消耗之間進(jìn)行權(quán)衡，例如遞歸數(shù)據(jù)流匹配(Recursive Flow Classification, RFC)算法[8-9]，此方法在時(shí)間效率上目前比較理想，但內(nèi)存消耗非常大，在高維大規(guī)模的情況下根本不現(xiàn)實(shí)；有的方法像分層智能分割(Hierarchical Intelligent Cuttings, HiCuts)算法[6]，網(wǎng)格特里樹(Grid-of-Trie)[5]，時(shí)間、空間消耗比較均衡，但只適合于二維情況。這些傳統(tǒng)方法目前都很難適應(yīng)網(wǎng)絡(luò)發(fā)展對(duì)包匹配速度的要求?；谥悄艿乃惴?，在文獻(xiàn)[10]中，雖然解決了包的高速匹配問題，但也只是考慮二維小規(guī)模的情況。在文獻(xiàn)[11]中，運(yùn)用實(shí)數(shù)進(jìn)行編碼，對(duì)差分演算法的交叉算子的參數(shù)進(jìn)行了研究并且實(shí)驗(yàn)論證了此算法適合處理高維大規(guī)模問題，但是由于對(duì)變異算子的參數(shù)沒有動(dòng)態(tài)考慮以及變異算子本身的動(dòng)態(tài)變化也沒有考慮，這些因素造成算法的預(yù)處理時(shí)間不夠理想。

包匹配是模式匹配的一種特殊應(yīng)用領(lǐng)域，在這過去幾年里，運(yùn)用機(jī)器學(xué)習(xí)來進(jìn)行目標(biāo)識(shí)別方法中的特征提取逐漸成為研究熱點(diǎn)。受此啟發(fā)，本文提出運(yùn)用差分演化算法去尋找每層的基礎(chǔ)基，把各層的特征融合起來進(jìn)行包匹配。

1 相關(guān)工作

包匹配是對(duì)每一個(gè)進(jìn)入網(wǎng)絡(luò)或主機(jī)的數(shù)據(jù)包進(jìn)行掃描，并把它和規(guī)則庫(kù)里數(shù)據(jù)包進(jìn)行匹配，在規(guī)則庫(kù)中尋找到相應(yīng)數(shù)據(jù)包，并根據(jù)相應(yīng)行為描述對(duì)進(jìn)入的數(shù)據(jù)包進(jìn)行相應(yīng)處理。在核心服務(wù)器中相應(yīng)規(guī)則數(shù)都比較大，而且隨著網(wǎng)絡(luò)硬件發(fā)展以及應(yīng)用范圍擴(kuò)大，對(duì)網(wǎng)速要求也越來越高。光纖普及使各種核心硬件設(shè)備處理速度成為網(wǎng)絡(luò)瓶頸，其中一個(gè)重要處理就是包匹配。當(dāng)今互聯(lián)網(wǎng)都要求核心設(shè)備以線速進(jìn)行相應(yīng)處理，這樣包匹配工作就要求在大規(guī)模情況下線速處理。另外，在IPV6環(huán)境下，一個(gè)進(jìn)入數(shù)據(jù)包根據(jù)它的目的IP地址、源IP地址、源端口、目的端口以及上層協(xié)議進(jìn)行匹配，而且其中每個(gè)具體的維又是由多位二進(jìn)制數(shù)組成。像源IP地址由128位二進(jìn)制數(shù)組成。這樣為了適應(yīng)如今互聯(lián)網(wǎng)的需求，包匹配必須是大規(guī)模多維線速包匹配。

傳統(tǒng)包匹配算法有基于基本數(shù)據(jù)結(jié)構(gòu)的算法、基于空間分割的算法、啟發(fā)式算法、基于硬件的算法等。比較有代表性的具體算法有Hierarchical Tires(分層特里樹)[2]、Set-pruning Trie(截枝特里樹)[3]、Grid-of-Trie，改進(jìn)的帶路徑壓縮的擴(kuò)展特里網(wǎng)格樹(EGT-PC)[5]、HiCuts、超分層智能分割算法(HyperCuts)[7]、RFC和三態(tài)內(nèi)容可訪問存儲(chǔ)器(Ternary Content Addressable Memory,TCAM)算法。這些算法有些是在時(shí)間和空間效率之間進(jìn)行權(quán)衡，有些雖然在一般情況下性能很好，但在極端的情況下性能卻急劇惡化，有些只適合低維、甚至一維的情況卻無法適用于多維包匹配的現(xiàn)實(shí)要求。因?yàn)殡S著維數(shù)的增加，性能會(huì)指數(shù)惡化。總體而言，傳統(tǒng)的算法都無法支持包的線速匹配?；谥悄艿乃惴ㄓ谢谙伻簝?yōu)化(Ant Colony Optimization, ACO)的算法[9]、基于差分演化(Differential Evolution, DE)的優(yōu)化算法以及基于神經(jīng)網(wǎng)絡(luò)的算法。基于ACO算法解決組合優(yōu)化問題的優(yōu)勢(shì)沒有得到充分體現(xiàn), 此算法在處理包時(shí)需要對(duì)規(guī)則進(jìn)行排序，導(dǎo)致時(shí)間和空間消耗都比較大。另外時(shí)間消耗隨規(guī)則數(shù)的增長(zhǎng)顯著增長(zhǎng)，從而也不太適合大規(guī)模的規(guī)則庫(kù)的匹配?；贒E的算法當(dāng)數(shù)據(jù)的特征和它們的映射不成線性關(guān)系時(shí)很難計(jì)算出最優(yōu)或近優(yōu)的α和β組合，通過演化代數(shù)對(duì)演化進(jìn)行限制會(huì)造成映射的數(shù)據(jù)空間的分布性能很差?；谏窠?jīng)網(wǎng)絡(luò)的算法，預(yù)處理時(shí)間相比較沒有優(yōu)勢(shì)，說明很難找到關(guān)鍵基礎(chǔ)基。本文受深度學(xué)習(xí)的啟發(fā)，提出尋找多層關(guān)鍵基礎(chǔ)基的思想，在每層關(guān)鍵基礎(chǔ)基上對(duì)進(jìn)入的數(shù)據(jù)包進(jìn)行識(shí)別，在比特基的提取時(shí)，對(duì)數(shù)據(jù)包進(jìn)行分塊局部處理。

2 多層基礎(chǔ)基的提取

2.1 基本思想

首先把進(jìn)入的數(shù)據(jù)包看作一串二進(jìn)制流，如圖1所示：找到這296位除去8位協(xié)議的基礎(chǔ)基，就是那關(guān)鍵N位的位點(diǎn)，使規(guī)則庫(kù)中規(guī)則達(dá)到平均自信息最大。這些位點(diǎn)定義為比特基。

圖1 數(shù)據(jù)包的流格式

Fig. 1Streamformatfordatapackets

在比特基提取過程中，為了統(tǒng)一化、簡(jiǎn)化處理本文引入圖像處理中常用的局部塊基思想，如圖2。把296位以16位為單位分為18個(gè)局部塊。分別找到每個(gè)局部塊中的比特基，進(jìn)一步進(jìn)行整合，最后提取到整個(gè)288位的比特基。各個(gè)局部塊假設(shè)彼此獨(dú)立。

圖2 比特基提取過程

把圖1中的128位源IP地址分為三個(gè)部分，見圖2，即45位全網(wǎng)ID，16位子網(wǎng)ID，64位接口ID，同樣目的IP地址也分為圖3所示的三部分。

源端口分為知名端口和動(dòng)態(tài)端口兩部分，而且知名端口的范圍是0～1023。同樣把目的端口也分為兩部分，如圖4所示。

圖3IPV6全球單播地址格式 圖4 端口分割

Fig. 3IPV6globalunicastaddressformatFig. 4Portsegmentation

這樣源IP地址的三部分、目的IP地址的三部分、源端口的兩部分、目的端口的兩部分共10部分分別視為不可分割的整體。找出10部分中的基礎(chǔ)基。在對(duì)10部分實(shí)體基提取時(shí)，染色體含有8個(gè)基因，對(duì)于超過10位的實(shí)體，采取隨機(jī)選擇實(shí)體中的8位，對(duì)于不足8位，像知名端口部分，低位補(bǔ)零。最后把10個(gè)部分的實(shí)體基進(jìn)行整合，使規(guī)則庫(kù)中的平均自信息達(dá)到最大。這些基礎(chǔ)基定義為實(shí)體基。

對(duì)進(jìn)入數(shù)據(jù)包進(jìn)行比特基提取，然后進(jìn)行實(shí)體基提取。這兩個(gè)提取過程組成一層基的提取。定義為比特實(shí)體基提取。

可根據(jù)解決問題的實(shí)際規(guī)模來選擇用幾層比特實(shí)體基?？梢栽O(shè)置閾值λ，當(dāng)分類中的規(guī)則數(shù)規(guī)模小于λ，就不再增加層進(jìn)行比特實(shí)體基提取。

2.2 差分演化算法

2.2.1 差分演化算法的現(xiàn)狀

每層中比特基和實(shí)體基提取都是采用差分演化算法(DE)。差分演化算法是一種高效且簡(jiǎn)單的優(yōu)化算法，因其簡(jiǎn)單易用，魯棒性能良好，被成功運(yùn)用于各個(gè)領(lǐng)域。近年很多學(xué)者對(duì)DE算子以及參數(shù)進(jìn)行改善。這些改善是為了在某種程度上去平衡算法的勘探和開采能力。目前改善算法可以分為兩類:1)融合其他的技術(shù)改進(jìn)DE算子，從而改善算法收斂性能，如，文獻(xiàn)[13]提出使用反向?qū)W習(xí)初始化種群和產(chǎn)生反向解的反向差分算法；也有考慮相異的變異策略具有相異性能，如，文獻(xiàn)[14]提出了一種多變異策略自適應(yīng)差分算法；另外2013年，文獻(xiàn)[15]提出應(yīng)用精英反向策略去改善DE算子，提高算法的收斂速度。2)考慮傳統(tǒng)差分算法對(duì)縮放因子和雜交概率兩個(gè)參數(shù)的敏感性，如，文獻(xiàn)[16-17]利用演化過程中的反饋信息來自適應(yīng)調(diào)整參數(shù)的自適應(yīng)差分算法；文獻(xiàn)[17]把參數(shù)編碼到個(gè)體中同時(shí)進(jìn)行進(jìn)化的參數(shù)自適應(yīng)差分算法。2011年，Wang等[18]同時(shí)考慮變異策略敏感性和參數(shù)敏感性問題，在構(gòu)建策略知識(shí)庫(kù)和參數(shù)知識(shí)庫(kù)的基礎(chǔ)上，提出一種隨機(jī)選取策略和參數(shù)組合差分演化算法。如上簡(jiǎn)述，研究人員已對(duì)DE進(jìn)行了大量研究，并且也取得了很多重要的成果。

2.2.2 本文的基本思想

本文采用精英反向?qū)W習(xí)演化算法實(shí)現(xiàn)比特基、實(shí)體基的提取，前者采用二進(jìn)制編碼，后者采用實(shí)數(shù)編碼，比特基提取時(shí)染色體的位數(shù)為16位，實(shí)體基提取時(shí)染色體位數(shù)為8位。

變異算子 變異算子是差分演化算法產(chǎn)生新個(gè)體的重要方式，它利用群體中不同個(gè)體之間差異來對(duì)相應(yīng)個(gè)體進(jìn)行擾動(dòng)，因而就必須采用不同策略來選擇相異個(gè)體，而且對(duì)兩個(gè)相異個(gè)體產(chǎn)生的距離，縮放因子的取值采取不同策略。這兩個(gè)問題都是差分演化研究的熱點(diǎn)。對(duì)相異個(gè)體選擇,本文采用“DE/rand/1”。

(1)

交叉算子

(2)

Cr=1-Ecur

(3)

其中Ecur為被處理的規(guī)則庫(kù)的信息熵。

選擇算子

(4)

精英反向演化算法，要針對(duì)精英個(gè)體，求出精英的反向個(gè)體，思想就是平衡勘探和開采能力，增強(qiáng)多樣性，增強(qiáng)尋找全局最優(yōu)解的能力，避免早熟。在當(dāng)前群中找出精英個(gè)體，也就是最優(yōu)個(gè)體，比特基提取時(shí)根據(jù)下面的式(5)求出精英反向個(gè)體：

(5)

實(shí)體基提取時(shí)根據(jù)下面的式(6)求出精英反向個(gè)體：

(6)

其中：Xe(xe,1,xe,2,…,xe,D)為D維的精英個(gè)體。k取[0，1]的隨機(jī)數(shù)，μi，li為xe,i的上下界。

適應(yīng)值函數(shù)設(shè)計(jì)

在比特基提取時(shí)，如果提取的比特基能把規(guī)則庫(kù)中的規(guī)則分成兩類，并且兩類中的規(guī)則數(shù)目近似，此時(shí)的平均自信息最大，系統(tǒng)也就處于一種均衡狀態(tài)。

假設(shè)規(guī)則庫(kù)中的規(guī)則被分成N類，每類中規(guī)則數(shù)分別為(m1,m2,…,mN)，此時(shí)規(guī)則庫(kù)的平均自信息按式(7)進(jìn)行計(jì)算:

(7)

在比特基提取中，當(dāng)進(jìn)行局部塊整合時(shí)，依據(jù)下面的公式計(jì)算平均自信息：

(8)

其中：M為規(guī)則庫(kù)規(guī)則總數(shù)目。

在實(shí)體基提取過程中，必須比較它相對(duì)于比特基的信息增長(zhǎng)量，運(yùn)用平均互信息量來衡量，公式如式(9)～(11)：

(9)

(10)

N1、N2分別為比特基中類的數(shù)目以及實(shí)體基中的類的數(shù)目。X為比特基中的類變量，Y為實(shí)體基類變量。式(9)和(10)分別站在不同的角度觀察信息量的平均變化。

(11)

2.3 算法框架

首先對(duì)規(guī)則庫(kù)中的規(guī)則進(jìn)行預(yù)處理，根據(jù)8位協(xié)議的值對(duì)數(shù)據(jù)進(jìn)行分類。規(guī)則庫(kù)中的規(guī)則以8位協(xié)議的值為6的TCP和17的UDP居多，其次為1的ICMP和2的IGMP以及為89的OSPF，研究分析得出規(guī)則庫(kù)中規(guī)則的8位協(xié)議TCP、UDP所占的比重可以讓別的協(xié)議忽略不計(jì)。這樣就可以根據(jù)8位協(xié)議把數(shù)據(jù)包分為三類TCP、UDP以及其他三類(值分別定義為：0，1，2)。

運(yùn)用差分演化算法進(jìn)行包匹配多層基礎(chǔ)基提取的算法(DEMBBPM)如下：

1)

fori=1：3

2)

根據(jù)圖1的8位協(xié)議對(duì)規(guī)則預(yù)處理

3)

End for

4)

k=0 (初始化層數(shù))

5)

while最大類規(guī)則數(shù)目大于閾值λ

6)

k=k+1

7)

fori=1 ：18

8)

根據(jù)精英反向差分演化算法對(duì)i局部塊進(jìn)行比特基的提取

9)

end for

10)

對(duì)18個(gè)局部塊的比特基進(jìn)行整合得出288位的比特基

11)

根據(jù)比特基對(duì)規(guī)則分類

12)

Fori=1:10

13)

對(duì)每一類進(jìn)行實(shí)體基的提取

14)

End for

15)

對(duì)10個(gè)部分進(jìn)行整合得到實(shí)體基

16)

針對(duì)實(shí)體基對(duì)規(guī)則進(jìn)行分類

17)

求最大類規(guī)則數(shù)目

18)

end while

對(duì)進(jìn)入數(shù)據(jù)包進(jìn)行匹配：

1)

提取數(shù)據(jù)包相關(guān)信息(賦值給結(jié)構(gòu)數(shù)據(jù)的各個(gè)元素)

2)

Fori=0:k

3)

對(duì)進(jìn)入的數(shù)據(jù)包的相應(yīng)位和i層比特基進(jìn)行位運(yùn)算

4)

對(duì)步驟3)的結(jié)果和i層實(shí)體基進(jìn)行位運(yùn)算

5)

End for

6)

在小于λ個(gè)規(guī)則的規(guī)則鏈中進(jìn)行順序搜索，如搜索到相應(yīng)的規(guī)則，轉(zhuǎn)7)，否則轉(zhuǎn)8)

7)

按規(guī)則中的行為對(duì)規(guī)則進(jìn)行處理

8)

拒絕處理，同時(shí)把此規(guī)則寫入相應(yīng)的文件

2.4 性能分析

運(yùn)用差分演化算法進(jìn)行包匹配多層基礎(chǔ)基提取,雖然算法比較耗時(shí)耗空間，但是它只運(yùn)行一次。在各層的比特基和實(shí)體基提取后。對(duì)進(jìn)入的數(shù)據(jù)包，進(jìn)行包匹配時(shí)，對(duì)進(jìn)入的數(shù)據(jù)包的比特流和各個(gè)基礎(chǔ)基進(jìn)行與操作，尋找到小于λ的類，再按順序進(jìn)行匹配 。

時(shí)間復(fù)雜度分析，進(jìn)入的數(shù)據(jù)包在每層比特基與操作中，只需要比特位操作16次，在實(shí)體基的與操作中只需要比特位操作8次。這樣每層比特實(shí)體基的匹配中只需要24次位操作，而比特實(shí)體基的層數(shù)小于logN，成功搜索到相應(yīng)規(guī)則，需要再平均耗時(shí)λ/2單位，如不成功再耗時(shí)λ單位，故時(shí)間復(fù)雜度為O(26 logN+λ)即O(logN)。

每次比特基匹配時(shí)，只需要16位的比特基空間，而實(shí)體基匹配時(shí)只需要8位的比特空間，空間復(fù)雜度為O(1)。

3 數(shù)值實(shí)驗(yàn)和分析

本章將本文提出的算法DEMBBPM與算法RFC和基于差分演化的包匹配算法(Real-basedDifferentialEvolutionPacketMatching,RDEPM)〖13〗進(jìn)行對(duì)比實(shí)驗(yàn)，因?yàn)镽FC是目前傳統(tǒng)包匹配速度比較理想的算法，RDEPM是目前利用智能算法進(jìn)行包匹配比較理想的算法。實(shí)驗(yàn)是在模擬環(huán)境下進(jìn)行的。在模擬實(shí)驗(yàn)中，設(shè)置防火墻每秒鐘到達(dá)4×105個(gè)數(shù)據(jù)包，每一次測(cè)試時(shí)間為5s，優(yōu)化算法中的定時(shí)器初始時(shí)長(zhǎng)設(shè)為1s。仿真實(shí)驗(yàn)所用的操作系統(tǒng)平臺(tái)是LinuxRedhat9.0，CPU是CoreI7 980XM，10GB內(nèi)存；所用的模擬器是NS-2(NetworkSimulatorv2.27)。實(shí)驗(yàn)中縮放因子取定值0.7，交叉概率Cr由式(3)動(dòng)態(tài)設(shè)置。本實(shí)驗(yàn)基于6組數(shù)據(jù)，在6種情況中，當(dāng)規(guī)則數(shù)線性增長(zhǎng)時(shí)，觀察相應(yīng)研究數(shù)據(jù)各自的變化趨勢(shì)。在規(guī)則數(shù)線性增長(zhǎng)的情況下，研究三種算法的優(yōu)劣。本實(shí)驗(yàn)是以iptables建立的防火墻規(guī)則為實(shí)驗(yàn)數(shù)據(jù)，由于防火墻的規(guī)則相比路由器中的規(guī)則復(fù)雜一些，因而本實(shí)驗(yàn)使用前者更具有說服力。另外生成規(guī)則時(shí)遵循隨機(jī)生成的原則，以避免偏差和混雜變量。為了盡量減少機(jī)會(huì)誤差，表1實(shí)驗(yàn)的結(jié)果都是運(yùn)算50次的平均值，同等規(guī)模的規(guī)則庫(kù)50次是針對(duì)同一個(gè)規(guī)則庫(kù)。

表1 不同規(guī)則數(shù)的各算法性能比較

從表1的數(shù)據(jù)看出本文提出的算法在整體性能上有絕對(duì)的優(yōu)勢(shì)。

從表1顯示出本文提出的算法在各個(gè)規(guī)模下平均初始化時(shí)間消耗性能都遜色于其他兩個(gè)算法，但是本文的算法在基礎(chǔ)基的提取上只執(zhí)行一次,既不像RFC算法每次包匹配都必須初始化,也不像RDEPM需要經(jīng)常初始化。

從表1展現(xiàn)出本文提出的算法在各個(gè)規(guī)模下性能都比其他兩個(gè)算法好，特別是和RFC算法相比，優(yōu)越性更明顯。這主要因?yàn)?本文的算法初始化進(jìn)行的是多層比特實(shí)體基的提取,它能抓住規(guī)則庫(kù)中錯(cuò)綜復(fù)雜規(guī)則間的關(guān)聯(lián),找到基本的核心特征。

從表1表明本文提出的算法在內(nèi)存消耗上性能也明顯優(yōu)越于其他兩個(gè)算法，當(dāng)規(guī)模較大時(shí)，這種優(yōu)越性更明顯。特別是傳統(tǒng)的RFC算法，當(dāng)規(guī)模達(dá)到100k時(shí)內(nèi)存消耗大到算法根本無法運(yùn)行。當(dāng)規(guī)則庫(kù)和映射域之間不是線性關(guān)系時(shí)，RDEPM算法無法找到α和β的最優(yōu)組合，甚至都無法找到它們的近似組合，這樣就會(huì)導(dǎo)致規(guī)則的分布性能欠佳，從而內(nèi)存的消耗也會(huì)無效增加。

表2分別是規(guī)則數(shù)為103和5×105時(shí)，而且實(shí)驗(yàn)進(jìn)行20次，每次同樣規(guī)模的規(guī)則庫(kù)是不一樣，最壞情況下兩個(gè)智能算法的性能比較。

表2顯示在最壞情況下，RDEPM各項(xiàng)性能都比DEMBBPM差，甚至在平均性能比較中占優(yōu)勢(shì)的預(yù)處理時(shí)間也風(fēng)光不再。因?yàn)镽DEPM主觀假設(shè)規(guī)則庫(kù)的規(guī)則和映射空間之間是線性關(guān)系，這是一個(gè)致命的假設(shè)。因?yàn)楫?dāng)它們之間不是線性關(guān)系時(shí)，就會(huì)導(dǎo)致性能惡化。而本算法(DEMBBPM)沒有假設(shè)這種線性關(guān)系。

表2 不同規(guī)則數(shù)最壞性能比較

表3顯示在各規(guī)模下本文提出的算法都優(yōu)越于RDEPM，反映本算法在特征提取時(shí)，提取的特征更優(yōu)越，更能反映問題的本質(zhì)。

4 結(jié)語(yǔ)

本文受深度學(xué)習(xí)的啟發(fā)，針對(duì)包匹配，創(chuàng)造性地運(yùn)用多層基礎(chǔ)基去提取包的多層特征，在每層中分別運(yùn)用精英反向差分演化算法進(jìn)行比特基和實(shí)體基的提取，運(yùn)用平均自信息作為衡量基礎(chǔ)基選擇的優(yōu)劣。本算法擴(kuò)展性能好，可以根據(jù)規(guī)則庫(kù)實(shí)際規(guī)模選擇提取層數(shù)。數(shù)值實(shí)驗(yàn)顯示，本算法效果不錯(cuò)。

)

[1]WARKHEDEP,SURIS,VARGHESEG.Fastpacketclassificationfortwo-dimensionalconflict-freefilters[C]//Proceedingsofthe20thAnnualJointConferenceoftheIEEEComputerandCommunicationsSocieties.Piscataway,NJ:IEEE, 2001: 1434-1443.

[2]GUPTAP,MCKEOWNN.Algorithmsforpacketclassification[J].IEEENetwork, 2001, 15(2): 24-32.

[3]SRINIVASANV,VARGHESEG,SURIS,etal.Fastandscalablelayerfourswitching[J].ACMSIGCOMMComputerCommunicationReview, 1998, 28(4): 191-202.

[4]FELDMANA,MUTHUKRISHNANS.Tradeoffsforpacketclassification[C]//Proceedingsofthe19thAnnualJointConferenceoftheIEEEComputerandCommunicationsSocieties.Piscataway,NJ:IEEE, 2000: 1193-1202.

[5]GUPTAP,MCKEOWNN.Packetclassificationwithhierarchicalintelligentcuttings[J].IEEEMicro, 2000, 20(1): 34-41.

[6]SINGHS,BABOESCUF,VARGHESEG,etal.Packetclassificationusingmultidimensionalcutting[C]//Proceedingsofthe2003conferenceonApplications,Technologies,Architectures,andProtocolsforComputerCommunications.NewYork:ACM, 2003: 213-224.

[7]GUPTAP,MCKEOWNN.Packetclassificationonmultiplefields[C]//Proceedingsofthe1999ConferenceonApplications,Technologies,Architectures,andProtocolsforComputerCommunication.NewYork:ACM, 1999: 147-160.

[8]TSAIC-H,CHUH-M,WANGP-C.Packetclassificationusingmulti-iterationRFC[C]//Proceedingsofthe2013IEEE37thAnnualComputerSoftwareandApplicationConferenceWorkshops.Washington,DC:IEEEComputerSociety, 2013: 748-753.

[9]VANLUNTERENJ,ENGBERSENAPJ.Multi-fieldpacketclassificationusingternaryCAM[J].ElectronicsLetters, 2002 , 38(1): 21-23.

[10]SREELAJANK,VIJAYALAKSHMIPAIGA.Antcolonyoptimizationbasedapproachforefficientpacketfilteringinfirewall[J].AppliedSoftComputing, 2010, 10(4): 1222-1236.

[11]WANGZ,WUZ,ZHANGB.Packetmatchingalgorithmbasedonimprovingdifferentialevolution[J].WuhanUniversityJournalofNaturalSciences, 2012, 17(5): 447-453.

[12] 王則林,吳志健,尹蘭.IPV6環(huán)境下的高維大規(guī)模包匹配算法[J].電子學(xué)報(bào)，2013,41(11):2181-2186.(WANGZL,WUZJ,YINL.HighdimensionlargescalepacketmatchingalgorithminIPV6 [J].ActaEletronicaSinica, 2013, 41(11): 2181-2186.)

[13]RAHNAMAYANS,TIZHOOSHHR,SALAMAMMA.Opposition-baseddifferentialevolution[J].IEEETransactionsonEvolutionaryComputation, 2008, 12(1): 64-79.

[14]QINAK,HUANGVL,SUGANTHANPN.Differentialevolutionalgorithmwithstrategyadaptationforglobalnumericaloptimization[J].IEEETransactionsonEvolutionaryComputation, 2009, 13(2): 398-417.

[15] 汪慎文,丁立新,謝承旺,等.應(yīng)用精英反向?qū)W習(xí)策略的混合差分演化算法[J].武漢大學(xué)學(xué)報(bào)(理學(xué)版),2013,59(2):111-116.(WANGSW,DINGLX,XIECW,etal.Ahybriddifferentialevolutionwitheliteopposition-basedlearning[J].JournalofWuhanUniversity(NaturalScienceEdition), 2013, 59(2): 111-116.)

[16]ZHANGJ,SANDERSONAC.JADE:adaptivedifferentialevolutionwithoptionalexternalarchive[J].IEEETransactionsonEvolutionaryComputation, 2009, 13(5): 945-958.

[17]BRESTJ,GREINERS,BOSKOVICB,etal.Self-adaptingcontrolparametersindifferentialevolution:acomparativestudyonnumericalbenchmarkproblems[J].IEEETransactionsonEvolutionaryComputation, 2006, 10(6): 646-657.

[18]WANGY,CAIZ,ZHANGQ.Differentialevolutionwithcompositetrialvectorgenerationstrategiesandcontrolparameters[J].IEEETransactionsonEvolutionaryComputation, 2011, 15(1): 55-66.

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(61070008),theApplicationResearchProjectofNantongScienceandTechnologyBureau(BK2014057).

WANG Zelin, born in 1973, Ph. D., associate professor. His research interests include network security, intelligent computing.

HAO Shuixia, born in 1973, Ph. D., associate professor. Her research interest include parallel algorithm, intelligent algorithm.

Extracting kernel basis using differential evolution algorithm for packet matching

WANG Zelin1,2, HAO Shuixia3*

(1.XinglinCollege,NantongUniversity,NantongJiangsu226000,China; 2.SchoolofComputerScienceandTechnology,NantongUniversity,NantongJiangsu226000,China; 3.SchoolofMathematicsandStatistics,JiangsuNormalUniversity,XuzhouJiangsu221116,China)

Aiming at the speed of packet matching in network firewall, router and other equipment, a differential evolution algorithm was proposed to extract the multi-layer core base of package matching. The multi-layer foundation was used to describe the multi-layer characteristics of the packet. In each layer, the bit basics and entitative basics were extracted using differential evolution algorithm and average self- information and the average mutual information were used to evaluate the quality of kernel basis. This method was adapt to select the number of layers of the extracted entity base according to the actual size of rule base, which is very suitable for the growth of rule base. The experimental results show that The proposed algorithm is the first known algorithm to be applied to packet matching efficiently. Compared with RFC (Recursive Flow Classification) algorithm and RDEPM (Real-based Differential Evolution Packet Matching) algorithm, the performance of the proposed algorithm is superior in terms of time efficiency and space efficiency.

packet matching; differential evolution algorithm; average self-information; average mutual information

2016- 08- 11;

2016- 10- 24。

國(guó)家自然科學(xué)基金資助項(xiàng)目(61070008)；南通市科技局應(yīng)用研究項(xiàng)目(BK2014057)。

王則林(1973—)，男，江蘇南通人，副教授，博士，主要研究方向：網(wǎng)絡(luò)安全、智能計(jì)算； 郝水俠(1973—)，女，江蘇徐州人，副教授，博士，主要研究方向：并行算法、智能算法。

1001- 9081(2017)03- 0777- 05

10.11772/j.issn.1001- 9081.2017.03.777

TP393

A