基于維度分解的多核并行網(wǎng)包分類算法

唐志斌,曾學(xué)文,陳 曉

(1.中國科學(xué)院聲學(xué)研究所國家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心，北京 100190； 2.中國科學(xué)院大學(xué)，北京 100049)

0 引 言

網(wǎng)包分類技術(shù)是指對(duì)接收到的數(shù)據(jù)流中的網(wǎng)包與分類器中的規(guī)則集進(jìn)行匹配，并根據(jù)所匹配的規(guī)則對(duì)應(yīng)的動(dòng)作類型對(duì)網(wǎng)包進(jìn)行相應(yīng)操作處理[1]。分類器是一系列規(guī)則或者策略的集合，每一條分類規(guī)則都指定一個(gè)類別或者是一條特定的流，將收到的網(wǎng)包頭部中特定的字段與規(guī)則集中對(duì)應(yīng)的字段相比較匹配，可以判斷該包符合哪些規(guī)則，進(jìn)而判斷其所屬的類別或網(wǎng)絡(luò)流[2]。許多網(wǎng)絡(luò)服務(wù)都需要包分類功能，比如路由、防火墻、網(wǎng)絡(luò)計(jì)費(fèi)、服務(wù)質(zhì)量(QOS)保證、虛擬專網(wǎng)(VPN)等[3-4]。隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)流量和帶寬都在不斷增長(zhǎng)，對(duì)網(wǎng)絡(luò)設(shè)備的處理能力提出了越來越高的要求[5]。作為網(wǎng)絡(luò)中最基本、應(yīng)用最廣泛的功能之一，包分類性能逐漸成為各類網(wǎng)絡(luò)應(yīng)用的瓶頸，亟待提高。

許多包分類算法基于數(shù)學(xué)建模分析，在分析和仿真層面往往能取得較低的時(shí)間或者空間復(fù)雜度，但是因?yàn)榧償?shù)學(xué)層面的分析往往添加特殊條件來簡(jiǎn)化問題，而這些條件在現(xiàn)實(shí)使用中往往無法得到滿足，因此難以在實(shí)際應(yīng)用中使用。還有一些算法使用硬件來加速包分類，往往能達(dá)到極高的性能，比如現(xiàn)場(chǎng)可編程門陣列(FPGA)[6]、專用集成電路(ASIC)、三態(tài)內(nèi)容尋址存儲(chǔ)器(TCAM)，然而專用硬件往往價(jià)格昂貴，開發(fā)周期長(zhǎng)，而且往往存儲(chǔ)空間比較寶貴，不適于較大的規(guī)則集，極大地限制了硬件算法的適用性[7]。

按照文獻(xiàn)[8]的描述，包分類算法可以分為如下4種類型：窮舉搜索法、決策樹法、元組空間法和維度分解法。窮舉法思路最簡(jiǎn)單，通常由硬件實(shí)現(xiàn)，比如TCAM[9-10]，速度快，但是成本高，不適合廣泛應(yīng)用；基于決策樹的算法通常根據(jù)規(guī)則的特性構(gòu)建一系列決策樹，通過從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的逐級(jí)訪問實(shí)現(xiàn)包的分類，比如Grid-of-Tries[11]、HyperSplit[7]算法，該類算法往往針對(duì)特定類型的規(guī)則集效果較好，并不廣泛適用各類規(guī)則集，且對(duì)規(guī)則維數(shù)擴(kuò)展性差；基于元組空間的算法按照規(guī)則前綴長(zhǎng)度對(duì)規(guī)則的每一維進(jìn)行分組，并以前綴作為哈希關(guān)鍵字進(jìn)行哈希查找，多個(gè)維度的分組組合在一起就形成了元組空間，代表為TSS(Tuple Space Search)[12]，該算法空間占用小，但是哈希函數(shù)的使用使其性能不穩(wěn)定；基于維度分解的方法以一定的字節(jié)數(shù)或者比特?cái)?shù)為單位,將每一條規(guī)則分解為多個(gè)維度，每個(gè)維度先單獨(dú)進(jìn)行查找，然后經(jīng)過合并得到最終查找結(jié)果?；诰S度分解的代表性算法有BV(Bit Vector)[13]、ABV(Aggregated Bit Vector)[14]、RFC(Recursive Flow Classification)[15]、HSM(Hierarchical Space Mapping)[16]、PCIU(Packet Classification Algorithm with an Incremental Update Capability)[17]等，其中PCIU算法可以適用于各種類型的規(guī)則集，對(duì)規(guī)則集的維度沒有限制，而且具有動(dòng)態(tài)增量更新的特性，分類速度也比較快。此外，還有結(jié)合幾種類型特點(diǎn)的算法，比如HiCuts[18]、HeyperCuts[19]，通過幾何分割，把規(guī)則集映射為多維空間，再使用決策樹分割規(guī)則集，在葉子節(jié)點(diǎn)通過線性搜索完成包的分類。

軟件包分類算法大多為串行的、面向單核的，其性能依賴于處理器的單核性能。而根據(jù)目前的處理器發(fā)展，單核集成度已經(jīng)接近極限，性能提升越來越難，摩爾定律正在走向終結(jié)，處理器的發(fā)展方向轉(zhuǎn)向多核化，雖然單核主頻較低，但通過增加處理器核心數(shù)量可以提升整體處理器的性能。串行的算法并不能很好適應(yīng)多核處理器，常常無法充分利用處理器資源，限制了其性能。因此，如果能結(jié)合多核處理器的特性，將包分類算法進(jìn)行并行化的調(diào)整和優(yōu)化，可以提升分類性能。

目前已經(jīng)有一些對(duì)包分類的并行化研究，比如文獻(xiàn)[20-21]提出的基于FPGA、多核處理器和GPU的并行包分類系統(tǒng)、文獻(xiàn)[22]提出的STORM并行分類方案，以及文獻(xiàn)[23]提出的基于GPU和CUDA的并行報(bào)文分類方法。但是這些都是包級(jí)別的并行方案，因?yàn)槊總€(gè)包的處理時(shí)間不一定相同，在分類過程中會(huì)導(dǎo)致包輸入與輸出順序不一致?？紤]到維度分解法的特性，每個(gè)維度的單獨(dú)查找可以指定某個(gè)核，或者多個(gè)核并行處理，多個(gè)維度查找結(jié)果的合并也可以由多核完成，實(shí)現(xiàn)包內(nèi)級(jí)別的并行。因此，本文基于維度分解的思想，提出一種包內(nèi)并行分類算法IPPC(Intra-Packet Parallelism Classification)，實(shí)現(xiàn)包內(nèi)級(jí)別的并行，將每個(gè)包的分類過程用多個(gè)核心并行執(zhí)行，實(shí)現(xiàn)數(shù)據(jù)包分類的并行加速，同時(shí)能保持包的輸出順序與輸入順序一致，避免通常多核并行處理數(shù)據(jù)包時(shí)容易出現(xiàn)的亂序問題。

1 方案分析與選擇

1.1 串行方案分析

以BV、PCIU算法為代表的基于維度分解的包分類算法，在將整個(gè)規(guī)則的多元組劃分成更小的多個(gè)維度之后，匹配工作可以在每個(gè)維度上單獨(dú)進(jìn)行，再將每個(gè)維度的匹配結(jié)果合并在一起，以得到最終的整體匹配結(jié)果。每個(gè)維度的匹配結(jié)果都產(chǎn)生一個(gè)位向量(BV)，需要將各個(gè)維度的BV全部合并，得到最終的BV以得出匹配結(jié)果。在整個(gè)包的匹配過程中，各維度的匹配結(jié)果合并的過程所耗費(fèi)的時(shí)間遠(yuǎn)遠(yuǎn)多于每個(gè)維度上的匹配時(shí)間，因此主要關(guān)注的是合并過程。如果這一過程是串行的，假設(shè)2個(gè)BV合并一次的時(shí)間為t，一條規(guī)則經(jīng)過維度分解產(chǎn)生K個(gè)維度，那么K個(gè)維度的合并時(shí)間為(K-1)t。

1.2 包級(jí)并行方案分析

如果采用數(shù)據(jù)包級(jí)別的并行，多個(gè)核心使用完全RTC(Run to Completion)的并行結(jié)構(gòu)[24]，即每個(gè)核心執(zhí)行一個(gè)獨(dú)立的包分類算法，輸入的數(shù)據(jù)包被分配到不同的核心去進(jìn)行匹配，每個(gè)核心獨(dú)立完成包分類匹配的所有操作，因此每個(gè)包K個(gè)維度的BV合并過程是在同一個(gè)核心上串行執(zhí)行的。由于多個(gè)核心可以同時(shí)并行執(zhí)行多個(gè)包的分類匹配，相比于單核系統(tǒng)，包級(jí)別的并行處理可以明顯提高系統(tǒng)整體的吞吐。但是，值得注意的是，每個(gè)包的BV合并時(shí)間仍為(K-1)t，單個(gè)包的整體匹配時(shí)延也沒有縮短。而且，由于每個(gè)包在各自的核心上的處理時(shí)間不一定是相同的，導(dǎo)致多個(gè)包同時(shí)經(jīng)過多個(gè)核心處理之后，輸出的順序與輸入的順序可能會(huì)不同，即無法保證輸出與輸入包的順序一致。對(duì)于屬于同一條流的數(shù)據(jù)包，如果經(jīng)過分類之后順序發(fā)生了改變，會(huì)導(dǎo)致這一條流出現(xiàn)意外的亂序事件，增加后續(xù)操作的重排序開銷，甚至造成意外的程序故障。

1.3 包內(nèi)并行方案分析

除了包級(jí)別的并行，還可以采用包內(nèi)并行處理，即同一個(gè)包的分類匹配過程由多個(gè)核心來同時(shí)執(zhí)行。經(jīng)過維度分解之后的各個(gè)維度一共產(chǎn)生K個(gè)BV，K個(gè)BV合并的過程由多個(gè)核心同時(shí)進(jìn)行，在一個(gè)合并周期t內(nèi)可以完成多次相互獨(dú)立的合并，如圖1所示。經(jīng)過簡(jiǎn)單的分析可知，當(dāng)處理器核心數(shù)目大于等于K/2時(shí)，合并過程的時(shí)間可以縮短到「log(K)?個(gè)周期，即「log(K)?t，大幅縮短單個(gè)包的匹配時(shí)延。以五元組的規(guī)則集為例，其5個(gè)字段共13 Byte，以1 Byte為一個(gè)維度，可分解產(chǎn)生13個(gè)維度，即K為13，如果用串行方式合并，需要12個(gè)計(jì)算周期才能完成13個(gè)位向量的合并，而如果使用6個(gè)核心去并行執(zhí)行13個(gè)位向量的合并，只需要4個(gè)計(jì)算周期即可完成。另外，盡管匹配是多核并行處理的，但由于是在包內(nèi)級(jí)別的并行，先輸入的包總是被先處理完，因此整個(gè)系統(tǒng)仍然是按照包輸入的順序在逐包匹配，輸出結(jié)果是保序的。

圖1 多核并行合并BV過程

1.4 并行方案選擇

基于以上分析，本文的算法設(shè)計(jì)運(yùn)用維度分解及BV的思想，并采用包內(nèi)級(jí)別的并行方案，在提高系統(tǒng)吞吐的同時(shí)，實(shí)現(xiàn)保序的并行分類，并減少單個(gè)包的分類時(shí)延。

2 算法設(shè)計(jì)

2.1 預(yù)處理過程

本文結(jié)合BV與PCIU算法的思想對(duì)規(guī)則集進(jìn)行構(gòu)建預(yù)處理。預(yù)處理步驟如下：

1)將各種形式的規(guī)則集，比如表1中前綴匹配形式轉(zhuǎn)換為由最小值和最大值組合成的范圍表示形式，如表2所示。

2)將規(guī)則集分解成1 Byte大小的子塊，每個(gè)子塊為一個(gè)維度，在該維度上每條規(guī)則的取值有其上限和下限值，如表3所示。每個(gè)維度的取值范圍為0～255，即每個(gè)維度的搜索空間大小為28，因此為每個(gè)維度分配一個(gè)大小為28的查找表來列舉該維度的所有取值。

圖2 維度1對(duì)應(yīng)的查找表和位向量

3)每個(gè)維度查找表中的每一個(gè)取值，都與該維度下的所有規(guī)則比對(duì)，檢查是否滿足規(guī)則，并分配一個(gè)BV，記錄每個(gè)取值所滿足的規(guī)則。位向量BV是一串比特串，長(zhǎng)度為規(guī)則數(shù)N，比特串中的每一個(gè)比特位表示對(duì)應(yīng)的規(guī)則的編號(hào)ID，如果滿足規(guī)則該位置為1，不滿足則置為0。如圖2所示為表1規(guī)則的第1個(gè)維度對(duì)應(yīng)的查找表和BV，取值83落在第0、1、2、4條規(guī)則的范圍之內(nèi)，即該值滿足第0、1、2、4條規(guī)則，則其對(duì)應(yīng)的位向量為BV=10111b(N為5)。位向量生成的偽代碼如算法1所示。

算法1預(yù)處理及位向量生成偽代碼。

1:for m=0, m

2:for i=0, i<256, i++// 查找表的取值范圍為0～255

3:VecPos=1;

4:BV=0;

5:for id=0, id

6:if i≥Rule[id].low and i≤Rule[id].high then

7:BV=BV|VecPos//按位或，將BV對(duì)應(yīng)位置1

8:end if

9:VecPos=left_shift(VecPos); //左移一位

10:end for

11:Chunk[m][i]=BV; //Chunk[m]為第m個(gè)維度，

//Chunk[m][i]為該維度對(duì)應(yīng)查找表的第i個(gè)取值

12:end for

13:end for;

表1 規(guī)則集示例

規(guī)則源IP(32bits)目的IP(32bits)源端口(16bits)目的端口(16bits)協(xié)議號(hào)(8bits)00.0.0.0/00.0.0.0/00～6553521～210/ff10.83.1.0/240.0.4.6/320～6553520～3017/ff20.83.4.0/220.0.0.0/00～6553521～210/030.0.9.0/240.0.0.0/00～655350～655356/ff40.83.0.77/320.0.4.6/320～655350～6553517/ff

表2 以范圍形式表示的規(guī)則集

規(guī)則源IP(32bits)目的IP(32bits)源端口(16bits)目的端口(16bits)協(xié)議號(hào)(8bits)00.0.0.0～255.255.255.2550.0.0.0～255.255.255.2550～6553521～210～010.83.1.0～0.83.1.2550.0.4.6～0.0.4.60～6553520～3017～1720.83.4.0～0.83.7.2550.0.0.0～255.255.255.2550～6553521～210～25530.0.9.0～0.0.9.2550.0.0.0～255.255.255.2550～655350～655356～640.83.0.77～0.83.0.770.0.4.6～0.0.4.60～655350～6553517～17

表3 維度分解后的規(guī)則集

規(guī)則源IP(32bits)目的IP(32bits)源端口(16bits)目的端口(16bits)協(xié)議號(hào)(8bits)維度0維度1維度2維度3維度4維度5維度6維度7維度8維度9維度10維度11維度1200～2550～2550～2550～2550～2550～2550～2550～2550～2550～2550～021～210～010～083～831～10～2550～00～04～46～60～2550～2550～020～3017～1720～083～834～70～2550～2550～2550～2550～2550～2550～2550～021～210～25530～00～09～90～2550～2550～2550～2550～2550～2550～2550～2550～2556～640～083～830～077～770～2550～2550～2550～2550～2550～2550～2550～25517～17

本文預(yù)處理算法與PCIU算法的不同之處在于，本文為查找表的每個(gè)取值都分配一個(gè)位向量BV，而PCIU算法針對(duì)規(guī)則分解之后各個(gè)維度上可能存在的冗余，采用了分組的方式，將冗余規(guī)則合并，滿足同樣規(guī)則的取值被分為同一組，每個(gè)組分配一個(gè)位向量BV，這樣可以減少總的BV數(shù)量，進(jìn)而減少內(nèi)存開銷。然而，當(dāng)規(guī)則集規(guī)模增大，規(guī)則更為復(fù)雜的時(shí)候，冗余度會(huì)下降，存在的分組數(shù)會(huì)增多，最差的情況是每個(gè)取值所滿足的規(guī)則組合都不同，即退化到分組數(shù)與查找表大小相同的水平，因此，分組操作在實(shí)際使用中能帶來的內(nèi)存節(jié)約水平有限。然而分組的操作反而會(huì)增加預(yù)處理的復(fù)雜度，因?yàn)樵诖_定分組時(shí)，需要將一個(gè)BV與所有已經(jīng)存在的分組對(duì)應(yīng)的BV比較是否一致，進(jìn)而確定該BV屬于已存在的某個(gè)分組還是一個(gè)新分組，而BV比較的時(shí)間復(fù)雜度是O(N)，即規(guī)則集越大，計(jì)算開銷越大。在規(guī)則集更新時(shí)，PCIU算法需要對(duì)所有分組進(jìn)行重新構(gòu)建，相當(dāng)于重建整個(gè)規(guī)則集，時(shí)間開銷巨大，而提升規(guī)則集更新速度在SDN等場(chǎng)景下是至關(guān)重要的[25]。本文的算法在更新規(guī)則集時(shí)，只需要更新每個(gè)BV的對(duì)應(yīng)位，而不用重新構(gòu)建。因此綜合看來，在規(guī)則集較大的情形下，分組所帶來的內(nèi)存節(jié)約的好處可能無法掩蓋其處理開銷增大的代價(jià)。本文的預(yù)處理方式需要比PCIU更多的內(nèi)存空間，但與PCIU處于同一數(shù)量級(jí)，而且消除了分組的時(shí)間開銷，大大提高了預(yù)處理和增量更新的速度。

2.2 分類過程

到達(dá)分類器的數(shù)據(jù)包，先將包頭中用于分類的字段切分成與預(yù)處理階段相對(duì)應(yīng)的1 Byte大小的子塊。用該數(shù)據(jù)包頭每個(gè)子塊的取值，分別在預(yù)處理階段構(gòu)建好的查找表中找到對(duì)應(yīng)的位向量BV，K個(gè)維度共得到K個(gè)BV。然后，將這所有維度得到的BV執(zhí)行按位相與操作，得到一個(gè)最終的BV，在這最終的BV中，置1的位表示這個(gè)包最終所滿足的規(guī)則。如果在最終BV中有不止一個(gè)置1的位，則表明滿足多條規(guī)則，考慮到規(guī)則集通常是按照優(yōu)先級(jí)先后的順序排列的，因此選擇第一個(gè)置1位作為最終的結(jié)果輸出。

2.3 分類過程多核并行化

在進(jìn)行包內(nèi)級(jí)別的并行方案的設(shè)計(jì)時(shí)，如果按照?qǐng)D1的并行流程，首先為每2個(gè)BV分配一個(gè)核心進(jìn)行第一個(gè)周期的計(jì)算，計(jì)算結(jié)果保存在其中一個(gè)BV中，然后對(duì)上一個(gè)周期計(jì)算生成的新BV重復(fù)這一合并過程，直到最終只剩一個(gè)BV，即為最終的匹配結(jié)果。從這樣的并行合并過程可以看出，隨著每個(gè)計(jì)算周期的逐步進(jìn)行，同一個(gè)包所需要的核心數(shù)在減少，上一個(gè)周期用到的核在下一個(gè)周期會(huì)出現(xiàn)空閑，比如圖1中，在第二和第三個(gè)計(jì)算周期只有Core1在工作，Core2和Core3處于空閑狀態(tài)。核心空閑是對(duì)計(jì)算資源的浪費(fèi)，這是并行算法設(shè)計(jì)中不應(yīng)該出現(xiàn)的。因此，為了提高核心的利用率，在一個(gè)包處理過程中空閑的核心應(yīng)該被用于處理下一個(gè)包，避免核心空閑。

本文的算法通過多核心并行搶占BV的方式來實(shí)現(xiàn)這一目標(biāo)。每個(gè)包經(jīng)過K個(gè)維度的匹配得到K個(gè)待合并BV，所有待合并處理的包按照到達(dá)的順序排列，形成一個(gè)先進(jìn)先出隊(duì)列。所有核心同時(shí)不斷地嘗試從隊(duì)列的第一個(gè)包中獲取2個(gè)相鄰的BV進(jìn)行合并，并將這2個(gè)BV標(biāo)記為已搶占，避免被其他核心獲取。合并完成之后，被搶占的2個(gè)BV中，一個(gè)用于存入合并結(jié)果，成為新的BV，并解除該BV的搶占狀態(tài)，另一個(gè)BV則清空，且保持搶占狀態(tài)，然后重復(fù)此過程。如果隊(duì)列頭部的包內(nèi)無法獲得2個(gè)未被搶占的BV，表明該包的所有BV都已經(jīng)被搶占且正在合并中，則進(jìn)入下一個(gè)包嘗試獲取BV。當(dāng)一個(gè)包僅剩唯一一個(gè)BV，其余BV全為空時(shí)，該包匹配完成，從最終的BV中獲得最終的分類結(jié)果。并行合并過程偽代碼如算法2所示。

算法2并行合并過程偽代碼(所有核心同時(shí)運(yùn)行相同代碼)。

1: while(true) do

2: P=P0; //獲取第一個(gè)數(shù)據(jù)包

3: while P !=NULL do

4: for i=0, i

5: if BV[i].occupied==false then //未被搶占

6: BV1=BV[i]; break;

7: end if

8: end for

9: for j=i+1, j

10: if BV[j].occupied==false then

11: BV2=BV[j]; break;

12: end if

13: end for;

14: if BV1!=NULL and BV2!=NULL then

15: BV1.occupied=true; BV2.occupied=true;

16: BV[i]=BV1& BV2; BV[j]=NULL;//按位與

17: BV[i].occupied=false;

18: if BV[i] is the final BV in P then

// BV[i]是最終的合并結(jié)果

19: rule[P]=get_rule(BV[i]); P->OUT;

//根據(jù)BV[i]獲得數(shù)據(jù)包P的最終匹配規(guī)則并輸出

20: P0=next(P0);

21: end if

22: break;

23: else

24: P=next(P);

25: continue:

26: end if

27: end while

28: end while

以3個(gè)核且維度為6的情況為例，圖3和圖4分別從每個(gè)核心的角度和每個(gè)包的角度描述了并行合并的過程。圖3描述了每個(gè)核心的搶占BV的過程，其中1(1,2)表示第1個(gè)包的第1個(gè)和第2個(gè)BV；圖4描述的為相應(yīng)的每個(gè)包的BV合并過程。

圖3 每個(gè)核心的處理流程

圖4 每個(gè)包的BV合并過程

通常，包內(nèi)并行方式往往涉及多個(gè)核心對(duì)同一個(gè)包共享資源的競(jìng)爭(zhēng)和互斥訪問，導(dǎo)致額外的加解鎖以及等待開銷，但是結(jié)合代碼和圖例分析可知，本文描述的包內(nèi)級(jí)別并行算法，并不涉及資源的共享訪問，而是將BV視為任務(wù)，由核心進(jìn)行主動(dòng)搶占，如果處理核心發(fā)現(xiàn)一個(gè)BV已被搶占，它不會(huì)等待這個(gè)BV釋放，而是繼續(xù)去搶占下一個(gè)BV，沒有空閑等待，因此不會(huì)增加核心間的競(jìng)爭(zhēng)開銷。

3 實(shí)驗(yàn)對(duì)比分析

3.1 測(cè)試環(huán)境和數(shù)據(jù)集

實(shí)驗(yàn)部分在Cavium OCTEON CN6645多核網(wǎng)絡(luò)處理器平臺(tái)上開展，對(duì)本文描述的包內(nèi)并行分類方法進(jìn)行實(shí)現(xiàn)，并將其性能與同平臺(tái)下包級(jí)并行RTC實(shí)現(xiàn)方案的HiCut和PCIU算法進(jìn)行對(duì)比。該平臺(tái)具有10個(gè)工作頻率1100 MHz 的MIPS架構(gòu)通用處理核心，每個(gè)核心具有37 kB的L1 I-Cache， 32 kB L1 D-Cache，以及2 MB共享L2 cache和8 GB DDR3 SDRAM內(nèi)存，2個(gè)10 Gbps網(wǎng)絡(luò)接口。每個(gè)核心可以運(yùn)行Linux操作系統(tǒng)或簡(jiǎn)單執(zhí)行(Simple Execution, SE)高效環(huán)境2種模式之一，其中一個(gè)核心運(yùn)行Linux模式，用來對(duì)平臺(tái)進(jìn)行管理和控制，其余核心均運(yùn)行SE模式來實(shí)現(xiàn)分類算法，以提高數(shù)據(jù)包處理的能力。

實(shí)驗(yàn)所用規(guī)則集和數(shù)據(jù)包流來自ClassBench[26]公開數(shù)據(jù)集，并由相應(yīng)的程序生成，所有規(guī)則集均使用五元組，其中32位的源和目的IP地址為前綴匹配形式，這里使用了100～10000大小的訪問控制列表(Access Control List, ACL)規(guī)則集。使用ClassBench生成的數(shù)據(jù)包流只包含包頭信息，在實(shí)際吞吐測(cè)試中，使用IXIA XT80流量測(cè)試設(shè)備生成64 Byte～1500 Byte大小的包組成的數(shù)據(jù)流，包頭對(duì)應(yīng)的字段替換成ClassBench生成的包頭信息。

3.2 測(cè)試結(jié)果

3.2.1 內(nèi)存占用

不同大小的規(guī)則集在構(gòu)建過程中，3種算法所占用的內(nèi)存情況如圖5所示。從結(jié)果圖中可以看出，內(nèi)存占用最小的是PCIU算法，然而隨著規(guī)則集的增大，本文提出的包內(nèi)并行分類算法占用內(nèi)存與PCIU逐漸接近，這是因?yàn)楸疚牡乃惴ㄔ陬A(yù)處理過程中并未對(duì)規(guī)則集的冗余進(jìn)行壓縮，所以理論上內(nèi)存占用比PCIU算法多，但是當(dāng)規(guī)則集增大時(shí)，PCIU的利用冗余進(jìn)行壓縮的效果變差，導(dǎo)致其內(nèi)存占用情況逐漸接近本文的算法。而本文的算法在處理10000大小規(guī)則集時(shí)內(nèi)存占用僅約為4.2 MB，當(dāng)今大多數(shù)的網(wǎng)包處理設(shè)備都容易滿足。

圖5 內(nèi)存占用對(duì)比

3.2.2 預(yù)處理時(shí)間

圖6所示為3種算法在構(gòu)建不同大小規(guī)則集的預(yù)處理過程所用時(shí)間。從結(jié)果可以看出，本文算法的預(yù)處理時(shí)間最少，而且當(dāng)規(guī)則集較大時(shí)，本文算法的預(yù)處理時(shí)間比PCIU縮短得更多，在10000規(guī)則集下，本文算法的預(yù)處理時(shí)間僅為PCIU的15%左右。這也印證了，本文算法通過犧牲一定的內(nèi)存空間，換來了預(yù)處理速度的大幅提升，預(yù)處理性能達(dá)到每秒92700條規(guī)則。

圖6 預(yù)處理時(shí)間

3.2.3 吞吐性能

在測(cè)試吞吐性能時(shí)將IXIA XT80流量生成設(shè)備與多核處理器平臺(tái)的一個(gè)10 Gbps接口直連。首先將數(shù)據(jù)包大小設(shè)置為64 Byte，測(cè)試將不同的核心數(shù)用于并行合并過程時(shí)系統(tǒng)的性能。多核處理器的10個(gè)核心中，有一個(gè)用來運(yùn)行Linux系統(tǒng)，還有一個(gè)用于查找位向量，用于位向量并行合并過程的核心數(shù)為1～8個(gè)。實(shí)驗(yàn)結(jié)果如圖7所示?？梢钥闯?，包內(nèi)并行算法的吞吐最大，且隨著核數(shù)的增多，相對(duì)于RTC并行的HiCut和PCIU算法吞吐的差值也更大，說明包內(nèi)并行算法的多核擴(kuò)展性更好。對(duì)RTC并行的HiCut和PCIU算法進(jìn)行測(cè)試時(shí)，由于數(shù)據(jù)包在多個(gè)核心之間的分配不均衡，當(dāng)流量較大時(shí)，出現(xiàn)了部分核心任務(wù)堆積而其他核空閑的情況，這是RTC并行的PCIU算法性能不如包內(nèi)并行算法的主要原因。

將并行階段的核數(shù)固定為8，即使用全部可用核心，用不同大小的包來測(cè)試系統(tǒng)的吞吐性能，其結(jié)果如圖8所示。從結(jié)果可知，當(dāng)數(shù)據(jù)包大小達(dá)到256 Byte時(shí)，包內(nèi)并行算法實(shí)現(xiàn)了10 Gbps的線速處理，而RTC并行的HiCut和PCIU分別只能達(dá)到線速的50%和80%，當(dāng)數(shù)據(jù)包大小為512 Byte時(shí)才能實(shí)現(xiàn)線速。并行算法的最大吞吐性能為5.37 Mpps(每秒5.37兆個(gè)包)。

圖7 不同并行核數(shù)下的吞吐性能

圖8 8個(gè)核下不同包大小的吞吐

4 結(jié)束語

本文提出了一種多核并行的數(shù)據(jù)包分類算法，采用包內(nèi)級(jí)別的并行方案，將一個(gè)包的分類過程用多個(gè)核來并行執(zhí)行，在并行的同時(shí)能保持?jǐn)?shù)據(jù)包輸出的順序與輸入順序一致，而不需要重新排序。實(shí)驗(yàn)結(jié)果表明，包內(nèi)級(jí)別并行算法比包級(jí)并行RTC實(shí)現(xiàn)的其他算法在預(yù)處理速度和吞吐性能上都有所提升，可以達(dá)到每秒92700條規(guī)則的預(yù)處理性能以及5.37 Mpps的吞吐性能，當(dāng)數(shù)據(jù)包大于或等于256 Byte時(shí)可以實(shí)現(xiàn)10 Gbps的線速處理。相較而言，內(nèi)存空間占用的增加并不顯著，不會(huì)造成內(nèi)存爆炸，適用于多數(shù)網(wǎng)絡(luò)處理平臺(tái)。保序的特點(diǎn)也使得該算法在需要保序的系統(tǒng)中更加適用。