一種基于位向量流分類算法的改進(jìn)

賀亞威，　侯整風(fēng)，　吳亮亮

(合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽 合肥　230009)

?

一種基于位向量流分類算法的改進(jìn)

賀亞威，侯整風(fēng)，吳亮亮

(合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽 合肥230009)

摘要:在流分類算法中，聚合位向量(ABV)算法分類速度快、并行性好,但內(nèi)存開銷過大;位向量折疊(AFBV)算法對ABV算法進(jìn)行了改進(jìn),降低了運(yùn)行時(shí)內(nèi)存的消耗,但其冗余計(jì)算增加了時(shí)間開銷。針對上述不足,文章提出一種改進(jìn)的位向量流分類算法,該算法無需進(jìn)行位向量聚合,減少了內(nèi)存開銷,并按規(guī)則的源/目的IP地址前綴建立分組表,根據(jù)表中分組所包含IP地址數(shù)目降序排列,使得算法具有良好的時(shí)間性能。實(shí)驗(yàn)結(jié)果表明，本算法在大規(guī)模規(guī)則庫下具有良好的時(shí)間和空間效率。

關(guān)鍵詞:流分類;聚合位向量(ABV)算法;位向量折疊(AFBV)算法;位向量

流分類技術(shù)將數(shù)據(jù)包按照指定的訪問控制規(guī)則分類成特定的數(shù)據(jù)流,廣泛應(yīng)用于流量計(jì)費(fèi)[1]、防火墻包過濾[2]、區(qū)分服務(wù)[3]、虛擬專用網(wǎng)[4]等。典型的流分類算法包括BV算法、ABV算法、TCAM算法[5]、RFC算法[6-7]等。目前,流分類研究主要集中在多維、大規(guī)模規(guī)則庫下如何提高流分類的時(shí)空效率。

文獻(xiàn)[8] 提出的BV(bit vector)算法主要解決多維匹配問題,但隨著規(guī)則數(shù)的增加,BV算法的時(shí)間性能和空間性能會隨之降低;文獻(xiàn)[9]在BV算法的基礎(chǔ)上,提出了聚合位向量(aggregated bit vector, ABV)算法,通過位圖聚合的方式,改善了BV算法在平均情況下的執(zhí)行時(shí)間,但算法運(yùn)行時(shí)的內(nèi)存消耗依然很大;文獻(xiàn)[10]在ABV算法的基礎(chǔ)上提出位向量折疊(AFBV)算法,減少了算法的空間開支,但算法的冗余計(jì)算降低了時(shí)間效率;文獻(xiàn)[11]在位向量折疊思想的基礎(chǔ)上,提出了元組向量折疊流分類算法,該算法在空間存儲和內(nèi)存讀取上都有很大進(jìn)步,但時(shí)間效率依然不理想。

針對ABV和AFBV算法存在的問題,本文提出了一種改進(jìn)的位向量流分類算法,該算法將規(guī)則集按源/目的IP地址的前綴建立前綴分組表,并按分組所包含IP地址數(shù)目進(jìn)行降序排列;再對源/目的端口號字段進(jìn)行值域劃分,建立位向量圖;根據(jù)數(shù)據(jù)包包頭中所對應(yīng)字段的值,在前綴分組表和位向量圖中分別進(jìn)行匹配,并將2個(gè)匹配結(jié)果取交集,得到最終分類結(jié)果。相比于ABV和AFBV算法,該算法在大規(guī)模規(guī)則庫下具有良好的時(shí)間和空間性能,且能較好地支持規(guī)則集的動(dòng)態(tài)更新。

1ABV算法

1.1　ABV算法描述

ABV算法對BV算法進(jìn)行了改進(jìn),屬于多維分類方式,通過源IP地址、目的IP地址、源端口、目的端口、協(xié)議類型5維字段來構(gòu)建分類規(guī)則庫。ABV算法將規(guī)則中的每個(gè)字段分別與數(shù)據(jù)包頭中的相應(yīng)字段進(jìn)行匹配,從而得到分類結(jié)果。

二元規(guī)則庫示例見表1所列。

表1　二元規(guī)則庫示例

ABV算法對每個(gè)字段建立初始位向量圖(以下簡稱位圖),位圖的長度和規(guī)則的個(gè)數(shù)是相同的,位圖的第n位對應(yīng)規(guī)則庫的第n條規(guī)則,根據(jù)預(yù)先劃分的區(qū)間,當(dāng)該區(qū)間的取值與規(guī)則有重疊時(shí),則該規(guī)則對應(yīng)位的取值為1,否則為0。對表1的規(guī)則,源端口的值域?yàn)?～65535,如果將其劃分為0～80、81～1023、1024～65535這3個(gè)區(qū)間,則屬于0~80區(qū)間的位圖為000101,R4、R6均在0~80區(qū)間中,所以它們對應(yīng)位置的值為1。位圖長度和規(guī)則數(shù)相同,都是6。

然后,ABV算法對初始位圖進(jìn)行聚合,其過程如下:將初始位圖按照聚合因子a進(jìn)行聚合操作,得到聚合位圖,聚合因子將初始位圖中a個(gè)比特位聚合為聚合位圖中的1位;如果a位中的位向量至少有1位為1,則聚合之后的結(jié)果為1,若全為0,則聚合之后的結(jié)果為0。

分類時(shí),先運(yùn)算聚合位圖,找到聚合位圖中位置為1的點(diǎn),再對初始位圖所對應(yīng)的位置進(jìn)行定點(diǎn)查找,有效地提高了算法的時(shí)間性能。

例如,表1的源端口字段中,端口號在0～80區(qū)間的初始位圖為“000101”,此時(shí)若取聚合因子a=3,由于前3位位圖中均為0,后3位中存在“1”,那么該初始位圖聚合之后的結(jié)果則為“01”,比之前長度減小了4位,使得匹配時(shí)位圖的長度大幅縮短,減少了算法的訪存次數(shù)。

通過位圖聚合的方式,ABV算法減少了讀取位圖的位數(shù),從而減少了訪存次數(shù),提高了算法的時(shí)間效率。

1.2　ABV算法的缺點(diǎn)

ABV算法采用聚合位圖的方式,提高了算法的時(shí)間性能，但在運(yùn)行過程中,ABV算法不僅要存儲初始位圖,還需要存儲聚合位圖,當(dāng)規(guī)則庫較多時(shí),聚合位圖的層次也會增加,導(dǎo)致存儲空間的開銷巨大。

設(shè)規(guī)則庫規(guī)則數(shù)為N,字段的值域區(qū)間個(gè)數(shù)為C,聚合因子為a,聚合位圖的層次為m,規(guī)則字段個(gè)數(shù)為k,那么初始位圖所占用的空間為kCN;而ABV算法所占用空間為k(CN+CN/a+CN/2a+…+CN/ma)[12]。隨著規(guī)則數(shù)增加,聚合位圖的層次m隨之增加,ABV算法所占用的空間急劇增大。

2AFBV算法

與ABV算法的聚合思想不同,AFBV對于位向量的處理不是聚合,而是將初始位向量折疊成一個(gè)較短的折疊位向量。設(shè)折疊位向量長度為f,如果折疊位向量第k位為1,可以計(jì)算出初始向量中可能為1的比特位的位置是(if+k)。假設(shè)初始位向量有4 096位,折疊長度f為128,則折疊位向量只有128位,存儲空間大幅減少了。

AFBV算法使用位向量折疊思想,降低了空間開銷。但是在實(shí)際應(yīng)用中,數(shù)據(jù)包都是多維的,對每一維的位向量都進(jìn)行多次的折疊和還原需要消耗大量的時(shí)間,特別當(dāng)規(guī)則庫較大時(shí),位向量折疊方式對算法的時(shí)間效率影響尤為明顯。

3改進(jìn)的位向量流分類算法

ABV算法的空間開銷大,AFBV算法的時(shí)間效率低,針對上述問題,本文提出一種改進(jìn)的位向量流分類算法,該算法通過構(gòu)建前綴分組表,無需進(jìn)行位向量聚合,減少了算法的空間開銷,并將前綴分組表按分組所包含IP地址數(shù)目降序排列,使得算法具有良好的時(shí)間性能。

算法按源/目的IP地址前綴,將所有規(guī)則劃分成若干個(gè)前綴分組,即每個(gè)前綴分組所對應(yīng)規(guī)則的源/目的IP地址前綴是相同的,并按前綴分組所包含的IP地址數(shù)目大小降序排列,以提高匹配效率;再對源/目的端口號字段進(jìn)行值域劃分,建立位向量圖。當(dāng)數(shù)據(jù)包到達(dá)時(shí),根據(jù)其包頭中所對應(yīng)字段的值,分別在前綴分組表和位向量圖中匹配,并取2個(gè)匹配結(jié)果的交集,再根據(jù)數(shù)據(jù)包協(xié)議字段的內(nèi)容與交集中的規(guī)則進(jìn)行匹配,得到最終分類結(jié)果。

3.1　算法描述

算法分為如下2個(gè)階段：

(1) 預(yù)處理階段。建立前綴分組表和位向量圖,并對前綴分組表進(jìn)行降序排列。

(2) 數(shù)據(jù)包分類階段。當(dāng)數(shù)據(jù)包到達(dá)時(shí),根據(jù)預(yù)處理階段建立的前綴分組和位向量圖,對數(shù)據(jù)包進(jìn)行分類。

3.1.1預(yù)處理過程

(1) 將規(guī)則集中,所有規(guī)則按照源/目的IP地址映射到前綴分組表中,表中屬于同一個(gè)分組的規(guī)則具有相同的源/目的IP地址前綴;然后,將前綴分組表存儲在一個(gè)結(jié)構(gòu)體中,并記錄分組的前綴和數(shù)目。

(2) 對前綴分組表中的分組,按其源/目的IP地址數(shù)目的大小降序排列,使得數(shù)據(jù)包能更快找到與其相匹配的前綴分組,提高算法分類效率。

(3) 端口號的值域?yàn)?～65535,鑒于23、80和1024端口號的特殊性,本算法將端口號的值域區(qū)間劃分為0～22、23、24～79、80、81～1023、1024～65535這6個(gè)區(qū)間,以便更快地完成匹配。

(4) 根據(jù)上述區(qū)間劃分,建立與規(guī)則庫相對應(yīng)的位向量圖。

3.1.2分類過程

設(shè)數(shù)據(jù)包為P(p1,p2,p3,p4,p5),p1～p5字段的順序?yàn)?源地址、目的地址、源端口、目的端口、協(xié)議。分類過程如下:

(1) 在前綴分組表中查找與p1、p2相匹配的分組,將這些分組對應(yīng)的規(guī)則保存在集合S1中。

(2) 根據(jù)p3、p4所屬值域區(qū)間,查找并取出其值域區(qū)間所對應(yīng)的位向量圖。將p3、p4所屬值域區(qū)間對應(yīng)的位向量圖進(jìn)行邏輯與操作,將操作結(jié)果中為1的位所對應(yīng)的規(guī)則保存在集合S2中。

(3) 對S1和S2規(guī)則集進(jìn)行交集運(yùn)算,并將結(jié)果保存在集合S3中。

(4) 將S3中所有規(guī)則的協(xié)議字段和P中的協(xié)議字段S5進(jìn)行匹配,得到P的最終分類結(jié)果。

3.2　算法示例

規(guī)則表見表2所列。

表2　規(guī)則表

由表2中的規(guī)則,建立源/目的地址前綴分組表,并按分組前綴所包含IP地址數(shù)目降序排列,見表3所列。

表3　源/目的地址前綴分組表

表3的分組中,源/目的地址數(shù)目較大的排在前面,以便分類時(shí)能更快地找到與數(shù)據(jù)包所匹配的前綴分組,提高算法的分類效率。

類似于ABV算法,本算法按源/目的端口號的值域劃分,建立與表2所列規(guī)則庫對應(yīng)的位圖,如圖1所示。

設(shè)數(shù)據(jù)包為P(10100,10110,8080,8080,TCP),分類過程如下:

(1) 在表3中查找符合P的前綴分組,找到符合條件的分組為ed3,所對應(yīng)規(guī)則為R11、R12。

(2)P的源端口號為8080,屬于1024～65535區(qū)間,在圖1a上查找符合P信息的位圖為010010001011;P的目的端口也為8080,在圖1b上查找符合P信息的位圖為111110001111,將2個(gè)位圖邏輯與,可得位圖為010010001011,其所對應(yīng)的規(guī)則有R2、R5、R9、R11、R12。

(3) 取上面2個(gè)集合的交集,得到規(guī)則R11、R12，然后將R11、R12的協(xié)議字段和P進(jìn)行匹配,得到分類結(jié)果為R12。

圖1　源端口、目的端口值域區(qū)間位圖

4算法比較

假設(shè)規(guī)則庫規(guī)則數(shù)為N,規(guī)則的維數(shù)為k,聚合因子為a,折疊數(shù)目為f,聚合層次為m,字段值域區(qū)間個(gè)數(shù)為C。

(1) 空間性能。ABV算法所占空間為k(CN+CN/a+CN/2a+…+CN/ma)[12],因ABV算法需要存儲聚類位圖,當(dāng)規(guī)則數(shù)較多時(shí),需要存儲多層聚類位圖,所耗空間巨大;AFBV算法所占空間為kf[13];本文算法中前綴分組表所占用空間為N,位向量圖所占空間為N (k-1)/2,總共占用空間為N+N (k-1)/2=N(k+1)/2。故本文算法在空間性能上優(yōu)于ABV算法,與AFBV算法相當(dāng)。

(2) 時(shí)間性能。設(shè)聚合位圖中1的個(gè)數(shù)為M,折疊位圖中1的個(gè)數(shù)為L,所以ABV算法需要讀取源位圖的次數(shù)為M,ABV算法的訪存次數(shù)為k(N/a+Ma)[12];AFBV算法由于折疊之后的冗余計(jì)算,所以時(shí)間性能較差,分類時(shí)的訪存次數(shù)為kLN[13];本文算法的訪存次數(shù)為(k-1)N。一般情況下M

(3) 規(guī)則動(dòng)態(tài)更新。當(dāng)有新規(guī)則加入時(shí),ABV算法需要對原來區(qū)間上對應(yīng)字段的區(qū)間聚合位圖進(jìn)行重建,AFBV算法需要重新生成折疊向量圖,而本文算法只需將新加入的規(guī)則映射到前綴集分組表和源/目的端口號區(qū)間位圖中即可。

5算法性能測試

本測試是對本文算法、ABV算法以及AFBV算法的分類速度和占用空間進(jìn)行對比,規(guī)則庫的規(guī)則由程序生成,每條規(guī)則由源/目的IP地址、源/目的端口號以及協(xié)議類型5元組組成。

5.1　實(shí)驗(yàn)環(huán)境

測試是在研華FWA-6500多核網(wǎng)絡(luò)安全平臺 (Intel Xeon 5500系列雙/四核處理器) 上進(jìn)行的,操作系統(tǒng)為Ubuntu10.04(系統(tǒng)內(nèi)核為linux-2.6.32);測試軟件為Webserver Stress Tool,該軟件可模擬用戶瀏覽網(wǎng)頁,通過設(shè)置用戶的數(shù)量與點(diǎn)擊網(wǎng)頁鏈接的頻率,使得數(shù)據(jù)流多樣化。

測試平臺如圖2所示,網(wǎng)絡(luò)安全平臺中安裝了流分類器,分別采用本文算法、ABV算法和AFBV算法進(jìn)行測試,客戶機(jī)上安裝了Webserver Stress Tool軟件,數(shù)據(jù)包經(jīng)過網(wǎng)絡(luò)安全平臺防火墻中流分類器進(jìn)行分類處理后發(fā)送到下面的PC機(jī)上。

圖2　測試平臺示意圖

Webserver Stress Tool的用戶數(shù)量設(shè)置為100,即每臺客戶端同時(shí)模擬100個(gè)IP用戶。在測試中客戶端不斷地提出網(wǎng)頁請求,服務(wù)器持續(xù)地向客戶端發(fā)送數(shù)據(jù)包,數(shù)據(jù)包經(jīng)過網(wǎng)絡(luò)安全平臺中的流分類器進(jìn)行分類處理。

5.2　實(shí)驗(yàn)結(jié)果

規(guī)則庫規(guī)則數(shù)分別取1 000、2 000、5 000、10 000、20 000、30 000條，分別測試本算法、ABV算法、AFBV算法的平均分類時(shí)間和空間消耗。

(1) 空間性能。本文算法、ABV算法以及AFBV算法的空間消耗如圖3所示。

圖3　算法的空間消耗

由圖3可知，隨著規(guī)則數(shù)的增加，ABV算法的內(nèi)存占用量急劇增大，而AFBV算法和本算法漲幅較為緩和；當(dāng)規(guī)則庫規(guī)模為30 000條時(shí)，本文算法消耗僅為ABV算法的1/10左右。本文算法在空間性能上明顯優(yōu)于ABV算法，略好于AFBV算法。

(2)時(shí)間性能。本文算法、ABV算法以及AFBV算法的時(shí)間性能對比如圖4所示。

圖4　算法的平均分類時(shí)間

由圖4可以看出，本文算法在時(shí)間性能上與ABV算法相差不大，明顯好于AFBV算法。

6結(jié)束語

針對ABV算法和AFBV算法存在的問題,本文提出了一種改進(jìn)的位向量流分類算法。改進(jìn)的算法無需進(jìn)行位向量聚合,減少了內(nèi)存開銷,并對前綴分組表按分組的IP地址數(shù)目降序排列,提高了其匹配效率。實(shí)驗(yàn)結(jié)果表明，當(dāng)規(guī)則集中所包含的規(guī)則較多時(shí),ABV算法需要占用龐大的內(nèi)存空間,AFBV算法則時(shí)間效率較低,而本算法在各個(gè)方面的性能相對均衡,有一定的應(yīng)用前景。

[參考文獻(xiàn)]

[1]湯小波,龔儉,孫毅.基于 NetFlow 的網(wǎng)絡(luò)流量實(shí)時(shí)計(jì)算模型[J].中國教育網(wǎng)絡(luò),2008 (Z1):101-104.

[2]Morandi O, Risso F, Baldi M, et al. Enabling flexible packet filtering through dynamic code generation[C]//ICC2008.Beijing:IEEE,2008:5849-5856.

[3]Chen R R,Khorasani K. A guaranteed cost congestion control strategy for a network of multi-agent systems subject to differentiated services traffic[C]//Proceedings of the 2011 Chinese Control and Decision Conference.Mianyang:IEEE,2011:734-741.

[4]Khamket T, Chomsiri T, Sripara P, et al. Designing the network access control using reverse VPN[C]//Proceedings of 2011 1st International Conference on Network and Electronics Engineering.Tokyo:ICNEE,2011. 2011:27-34.

[5]Shah D, Gupta P. Fast updating algorithms for TCAM[J]. Micro IEEE,2001,21(1):36-47.

[6]Gupta P, McKeown N. Packet classification on multiple fields[J]. ACM SIGCOMM Computer Communication Review, 1999, 29(4): 147-160.

[7]孫毅,劉彤,蔡一兵,等.報(bào)文分類算法研究[J].計(jì)算機(jī)應(yīng)用研究,2007,24(4):5-11.

[8]Lakshman T V, Stiliadis D. High-speed policy-based packet forwarding using efficient multi-dimensionalrange matching[J]. ACM SIGCOMM Computer Communication Review,1998, 28(4): 203-214.

[9]Baboescu F, Varghese G. Scalable packet classification[J].ACM SIGCOMM Computer Communication Review. ACM, 2001, 31(4): 199-210.

[10]Li J, Liu H,Sollingns K.Scalable packet classification using bit vector aggregating and folding,MA02139[R].Cambridge:MIT Laboratory for Computer Science,2003.

[11]王學(xué)光.位并行多維數(shù)據(jù)包分類算法研究[J].計(jì)算機(jī)工程,2007,33(14):46-48.

[12]胡茂福,侯整風(fēng),韓江洪,等.基于交叉位圖的多維流分類算法[J].計(jì)算機(jī)應(yīng)用研究,2010,27(8):3060-3063.

[13]侯整風(fēng)，江鵬.對基于元組向量折疊的包分類算法的改進(jìn)[J].合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，32(8):1132-1136.

(責(zé)任編輯胡亞敏)

侯整風(fēng)(1958-),男,安徽和縣人,合肥工業(yè)大學(xué)教授,碩士生導(dǎo)師.

An improved flow classification algorithm based on bit vector

HE Ya-wei，HOU Zheng-feng,WU Liang-liang

(School of Computer and Information, Hefei University of Technology, Hefei 230009, China)

Abstract:In view of flow classification, aggregated bit vector(ABV) algorithm is faster and has good parallelism, but the memory overhead is too large.The aggregated and folded bit vector(AFBV) algorithm improves ABV algorithm with less run-time memory consumption, but its redundant computation increases time overhead. An improved flow classification algorithm based on bit vector is proposed, which does not require bit vector aggregation, reduces memory overhead, establishes prefix grouped table according to the source/destination IP address prefix of rules, and makes the descending order by the number of IP addresses contained in the groups of table, so that the algorithm can have good time performance. The experimental results show that the algorithm has good time and space efficiency for large-scale rule base.

Key words:flow classification; aggregated bit vector(ABV) algorithm; aggregated and folded bit vector(AFBV) algorithm; bit vector(BV)

中圖分類號:TP393.0

文獻(xiàn)標(biāo)識碼：A

文章編號：1003-5060(2015)03-0331-05

doi:10.3969/j.issn.1003-5060.2015.03.009

作者簡介：賀亞威(1989-),男,安徽滁州人,合肥工業(yè)大學(xué)碩士生;

基金項(xiàng)目：安徽省自然科學(xué)基金資助項(xiàng)目(11040606M138)

收稿日期：2014-02-18；修回日期：2014-04-10