王則林，郝水俠

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

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

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

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

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

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

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

包匹配是模式匹配的一種特殊應用領域，在這過去幾年里，運用機器學習來進行目標識別方法中的特征提取逐漸成為研究熱點。受此啟發(fā)，本文提出運用差分演化算法去尋找每層的基礎基，把各層的特征融合起來進行包匹配。

1 相關工作

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

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

2 多層基礎基的提取

2.1 基本思想

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

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

Fig. 1Streamformatfordatapackets

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

圖2 比特基提取過程

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

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

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

Fig. 3IPV6globalunicastaddressformatFig. 4Portsegmentation

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

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

可根據(jù)解決問題的實際規(guī)模來選擇用幾層比特實體基。可以設置閾值λ，當分類中的規(guī)則數(shù)規(guī)模小于λ，就不再增加層進行比特實體基提取。

2.2 差分演化算法

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

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

2.2.2 本文的基本思想

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

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

(1)

交叉算子

(2)

Cr=1-Ecur

(3)

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

選擇算子

(4)

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

(5)

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

(6)

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

適應值函數(shù)設計

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

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

(7)

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

(8)

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

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

(9)

(10)

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

(11)

2.3 算法框架

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

運用差分演化算法進行包匹配多層基礎基提取的算法(DEMBBPM)如下：

1)

fori=1：3

2)

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

3)

End for

4)

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

5)

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

6)

k=k+1

7)

fori=1 ：18

8)

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

9)

end for

10)

對18個局部塊的比特基進行整合得出288位的比特基

11)

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

12)

Fori=1:10

13)

對每一類進行實體基的提取

14)

End for

15)

對10個部分進行整合得到實體基

16)

針對實體基對規(guī)則進行分類

17)

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

18)

end while

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

1)

提取數(shù)據(jù)包相關信息(賦值給結構數(shù)據(jù)的各個元素)

2)

Fori=0:k

3)

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

4)

對步驟3)的結果和i層實體基進行位運算

5)

End for

6)

在小于λ個規(guī)則的規(guī)則鏈中進行順序搜索，如搜索到相應的規(guī)則，轉7)，否則轉8)

7)

按規(guī)則中的行為對規(guī)則進行處理

8)

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

2.4 性能分析

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

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

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

3 數(shù)值實驗和分析

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

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

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

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

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

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

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

表2顯示在最壞情況下，RDEPM各項性能都比DEMBBPM差，甚至在平均性能比較中占優(yōu)勢的預處理時間也風光不再。因為RDEPM主觀假設規(guī)則庫的規(guī)則和映射空間之間是線性關系，這是一個致命的假設。因為當它們之間不是線性關系時，就會導致性能惡化。而本算法(DEMBBPM)沒有假設這種線性關系。

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

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

4 結語

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

)

[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].電子學報，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] 汪慎文,丁立新,謝承旺,等.應用精英反向學習策略的混合差分演化算法[J].武漢大學學報(理學版),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。

國家自然科學基金資助項目(61070008)；南通市科技局應用研究項目(BK2014057)。

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

1001- 9081(2017)03- 0777- 05

10.11772/j.issn.1001- 9081.2017.03.777

TP393

A