基于布魯姆過(guò)濾器的面向IP包識(shí)別的CPBF算法*

李龍飛 賀占莊 史陽(yáng)春

(西安微電子技術(shù)研究所 集成電路設(shè)計(jì)部， 陜西 西安 710065)

基于布魯姆過(guò)濾器的面向IP包識(shí)別的CPBF算法*

李龍飛 賀占莊 史陽(yáng)春

(西安微電子技術(shù)研究所 集成電路設(shè)計(jì)部， 陜西 西安 710065)

針對(duì)現(xiàn)有布魯姆過(guò)濾器在流識(shí)別應(yīng)用中對(duì)每個(gè)IP包進(jìn)行相同的處理，未考慮IP包識(shí)別失效代價(jià)和硬件開(kāi)銷的問(wèn)題，提出一種面向IP包識(shí)別的算法——CPBF(Classified and Pipelined Bloom Filter).該算法通過(guò)引入IP頭中服務(wù)類型作為識(shí)別失效代價(jià)的判斷依據(jù)對(duì)IP包進(jìn)行分類，根據(jù)分類結(jié)果采取不同數(shù)目的Hash函數(shù)進(jìn)行映射，降低高失效代價(jià)IP包的識(shí)別失效率；同時(shí)在Hash計(jì)算中采用流水機(jī)制加速識(shí)別速率；基于概率論、微分方程等相關(guān)知識(shí)對(duì)CPBF算法進(jìn)行了描述和理論分析，最后在FPGA上對(duì)算法進(jìn)行實(shí)現(xiàn)和實(shí)驗(yàn).結(jié)果表明，與標(biāo)準(zhǔn)布魯姆過(guò)濾器、多維布魯姆過(guò)濾器相比，CPBF在具有較低的識(shí)別失效率和硬件開(kāi)銷的同時(shí)，也能保持較高的識(shí)別速率.

布魯姆過(guò)濾器；CPBF算法；IP包識(shí)別；識(shí)別失效代價(jià)；Hash函數(shù)

隨著40 Gbps和100 Gbps以太網(wǎng)標(biāo)準(zhǔn)的相繼提出，網(wǎng)絡(luò)帶寬已經(jīng)不再是阻礙服務(wù)器性能的瓶頸.相反，CPU處理速度的增長(zhǎng)遠(yuǎn)不及網(wǎng)絡(luò)帶寬的增長(zhǎng)，且二者之間的速度差逐年增大[1].因此，在網(wǎng)絡(luò)帶寬變得越來(lái)越大，CPU處理速度保持一定的情況下，如何保證CPU對(duì)網(wǎng)絡(luò)數(shù)據(jù)流的有效處理成了國(guó)內(nèi)外學(xué)術(shù)界面臨的一項(xiàng)極具挑戰(zhàn)性的課題.

通過(guò)網(wǎng)絡(luò)流識(shí)別將用戶更關(guān)心的IP數(shù)據(jù)包優(yōu)先交付給CPU處理是一種解決CPU處理能力與網(wǎng)絡(luò)帶寬不平衡問(wèn)題的有效方案.目前主流的技術(shù)是通過(guò)IP包五元組匹配查詢.五元組是指IP包中的源IP地址、目的IP地址、源端口、目的端口、協(xié)議5部分組成的向量，表征了一個(gè)IP包的基本屬性.該技術(shù)在HPC、云計(jì)算、大數(shù)據(jù)、數(shù)據(jù)庫(kù)和高頻交易等領(lǐng)域擁有廣泛的應(yīng)用前景.

IP包識(shí)別的研究發(fā)展至今，流識(shí)別算法可以分為基于軟件的流識(shí)別算法和基于硬件的流識(shí)別算法.由于基于硬件的流識(shí)別算法并行性強(qiáng)、匹配查找速度較快，時(shí)間和空間復(fù)雜度都能很好地滿足高速網(wǎng)絡(luò)的發(fā)展需求，且易于SoC集成，因此成為流識(shí)別算法的研究熱點(diǎn).在基于硬件的流識(shí)別算法中，主要有基于三態(tài)內(nèi)容尋址存儲(chǔ)器(TCAM)的算法和基于布魯姆過(guò)濾器(BF)的算法.由于TCAM實(shí)現(xiàn)成本比較高，且其存儲(chǔ)相對(duì)獨(dú)立導(dǎo)致共享性不好，因此廣泛采用基于布魯姆過(guò)濾器的算法[2- 3].作為一種精簡(jiǎn)的信息查詢、識(shí)別方案，基于標(biāo)準(zhǔn)布魯姆過(guò)濾器(SBF)不斷衍生出多種改進(jìn)算法以滿足高帶寬下的高識(shí)別速率，這其中以文獻(xiàn)[4]中提出的多維布魯姆過(guò)濾器(MDBF)算法為代表.MDBF是通過(guò)將一維的元素分解為多維，以并行的方式來(lái)提高算法匹配速度.然而， MDBF誤判率較高，且由于其采用多個(gè)標(biāo)準(zhǔn)布魯姆過(guò)濾器，硬件資源代價(jià)大.文獻(xiàn)[5]中提出的B2PC算法采用多層的布魯姆過(guò)濾器結(jié)構(gòu)設(shè)計(jì)，對(duì)元素先分組進(jìn)行識(shí)別，最后再對(duì)組進(jìn)行識(shí)別.B2PC算法結(jié)構(gòu)復(fù)雜，采用多層結(jié)構(gòu)不僅增大了空間復(fù)雜度，而且增大了計(jì)算復(fù)雜度.MDBF與B2PC算法的共同思想是采用多個(gè)布魯姆過(guò)濾器來(lái)?yè)Q取匹配速度的提高，以硬件資源換取算法性能.文獻(xiàn)[6]中提出的CBFM算法通過(guò)構(gòu)建位矩陣，支持多維元素查詢，同時(shí)也支持過(guò)濾規(guī)則的靈活配制.但由于該算法在查詢時(shí)采用了遍歷的方式，因此在查詢效率方面略顯不足.目前已有的算法[7- 12]還存在一個(gè)共同的缺陷是未考慮IP包識(shí)別失效代價(jià)，即算法對(duì)每個(gè)IP包進(jìn)行相同的處理，然而每個(gè)IP包識(shí)別失效所引起的系統(tǒng)額外操作代價(jià)卻并不相同.

本研究面向IP包識(shí)別應(yīng)用，提出一種對(duì)IP包類型敏感的識(shí)別算法——分類流水布魯姆過(guò)濾器(CPBF)；文中首先對(duì)CPBF及其實(shí)現(xiàn)方案進(jìn)行詳細(xì)描述，然后基于Xilinx的Virtex 5(model:xc5vlx110)對(duì)CPBF算法進(jìn)行了硬件實(shí)現(xiàn)，并對(duì)CPBF的性能進(jìn)行實(shí)際評(píng)估.

1 標(biāo)準(zhǔn)布魯姆過(guò)濾器

標(biāo)準(zhǔn)布魯姆過(guò)濾器識(shí)別算法核心思想是元素集S通過(guò)Hash函數(shù)組K與一個(gè)V向量建立映射關(guān)系，其原理如圖1所示.

圖1 布魯姆過(guò)濾器原理

集合S={s1,s2,…,sn}共有n個(gè)元素，通過(guò)k個(gè)相互獨(dú)立的Hash函數(shù)h1,h2，…，hk映射到長(zhǎng)度為m的位串向量V中.布魯姆過(guò)濾器在使用前應(yīng)先進(jìn)行元素插入操作，即匹配規(guī)則的設(shè)定.對(duì)于給定的元素si∈S,V中位置為hj(si)的比特都置為1，其中1≤i≤n,1≤j≤k.對(duì)于元素識(shí)別操作，在判斷一個(gè)元素x是否屬于集合S時(shí)，計(jì)算hj(x)的值，并判斷V中以該值為地址的比特位是否均為1.若各比特位都為1，則x∈S，否則x?S.

布魯姆過(guò)濾器不存在假陰性現(xiàn)象，但卻存在假陽(yáng)性現(xiàn)象，即布魯姆過(guò)濾器不會(huì)識(shí)別不出屬于集合S的元素，但卻會(huì)將本不屬于集合S的元素誤識(shí)別為屬于S，稱這種假陽(yáng)性現(xiàn)象為識(shí)別失效，對(duì)應(yīng)的假陽(yáng)性概率為識(shí)別失效率.為了下文表示方便，用{S,K,V}表示一個(gè)布魯姆過(guò)濾器.

向量V中任意一比特位為0的概率表示為p，則任意一比特位為1的概率為1-p.假設(shè)Hash函數(shù)計(jì)算值服從均勻分布，則當(dāng)集合S中所有元素與向量V映射完成后，V中任一比特位為0的概率為

(1)

當(dāng)發(fā)生假陽(yáng)性現(xiàn)象時(shí)，V中對(duì)應(yīng)的各個(gè)比特位都為1，則假陽(yáng)性的概率f為

(2)

(3)

代入f得f最小值為

(4)

同理，給定f、n可得到在給定假陽(yáng)性概率f下m與k的關(guān)系：

(5)

取m對(duì)k的導(dǎo)數(shù)，得

(6)

k=-log2f

(7)

為了降低假陽(yáng)性概率，Hash函數(shù)的個(gè)數(shù)并不是越大越好，因?yàn)閗越大向量V中的1變得稠密，假陽(yáng)性的概率會(huì)增加.當(dāng)n=200、m=2 560時(shí)，根據(jù)式(3)、式(4)得到，k=9時(shí)假陽(yáng)性概率最小，為0.002 135.注意到，k值與處理開(kāi)銷呈線性關(guān)系，每個(gè)元素的識(shí)別都需要經(jīng)過(guò)k次Hash計(jì)算和k次存儲(chǔ)器訪問(wèn).由式(4)可以看出m越大假陽(yáng)性的概率會(huì)越小，但過(guò)大的m有違布魯姆過(guò)濾器簡(jiǎn)潔、快捷的思想，因此在實(shí)際應(yīng)用中應(yīng)該根據(jù)式(5)、式(7)選擇最優(yōu)的m以保證占用空間最小且符合指定的假陽(yáng)性概率.

2 面向IP包識(shí)別的CPBF算法

2.1 算法思路

在IP包識(shí)別的過(guò)程中，當(dāng)發(fā)生識(shí)別失效現(xiàn)象后，本應(yīng)正常處理的IP包被視為優(yōu)先處理的IP包，并被系統(tǒng)優(yōu)先進(jìn)行處理.然而，采用IP包識(shí)別方法的根本目的是為了解決系統(tǒng)處理能力和網(wǎng)絡(luò)帶寬之間不平衡的問(wèn)題，以保證用戶更關(guān)心的數(shù)據(jù)包被系統(tǒng)優(yōu)先處理，因此識(shí)別失效現(xiàn)象的發(fā)生會(huì)給系統(tǒng)資源帶來(lái)更大的壓力，造成系統(tǒng)性能的下降，稱這種不利的影響為識(shí)別失效代價(jià).因?yàn)樽R(shí)別失效現(xiàn)象會(huì)造成系統(tǒng)對(duì)用戶指定數(shù)據(jù)包處理耗時(shí)的增加，即增大了延遲，這對(duì)于用戶來(lái)說(shuō)是識(shí)別失效代價(jià)最直接的表現(xiàn)，因此其可以作為識(shí)別失效代價(jià)大小的判定依據(jù).

CPBF算法的基本思想是，根據(jù)IP包識(shí)別失效代價(jià)的不同，將較多數(shù)目的Hash函數(shù)映射給識(shí)別失效代價(jià)較高的IP包，以降低識(shí)別失效率；將較少數(shù)目的Hash函數(shù)映射給識(shí)別失效代價(jià)較低的IP包，在稍許增加識(shí)別失效率的同時(shí)提高識(shí)別速率，并減小總的識(shí)別失效代價(jià).另外，在Hash函數(shù)計(jì)算中采用流水機(jī)制加速算法對(duì)IP包的識(shí)別，其原理結(jié)構(gòu)如圖2所示.

不同于現(xiàn)有的IP包識(shí)別算法，CPBF首先會(huì)對(duì)接收到的IP包分類.本研究希望根據(jù)識(shí)別失效代價(jià)對(duì)IP包進(jìn)行分類，然而這卻是一個(gè)難題.因?yàn)閷?duì)于一個(gè)未知的IP包，現(xiàn)有的算法無(wú)法判斷它的識(shí)別失效代價(jià)有多大，換句話說(shuō)，只有該IP包通過(guò)了識(shí)別和系統(tǒng)的處理，其識(shí)別失效代價(jià)才能得以體現(xiàn).這是一個(gè)相互制約的問(wèn)題.本研究為CPBF設(shè)計(jì)了一個(gè)基于服務(wù)類型的IP包分類方法，在IP包進(jìn)入布魯姆過(guò)濾器之前估計(jì)出其識(shí)別失效代價(jià)，保證CPBF能夠按類對(duì)IP包進(jìn)行識(shí)別處理.

圖2 CPBF原理結(jié)構(gòu)

根據(jù)IP協(xié)議，在IP數(shù)據(jù)包頭部有一個(gè)8位的服務(wù)類型(ToS).ToS字段最初在RFC 791標(biāo)準(zhǔn)中定義，被劃分為2個(gè)子字段，前3位為數(shù)據(jù)包的Precedence域，這3位可劃分8個(gè)優(yōu)先級(jí)，數(shù)值越大表示優(yōu)先級(jí)越高，從而使數(shù)據(jù)包對(duì)應(yīng)著不同的服務(wù)類別.D、T、R和C四位(DTRC域)表示數(shù)據(jù)包所希望的服務(wù)類別.其中，D代表低延遲，T代表高吞吐率，R代表高可靠性，C表示開(kāi)銷低的路由.為了表示更多的優(yōu)先級(jí)，RFC 2474標(biāo)準(zhǔn)對(duì)ToS字段進(jìn)行了不同的定義，把前6位定義為差分服務(wù)代碼點(diǎn)(DSCP域)，用來(lái)標(biāo)記數(shù)據(jù)包的服務(wù)類別；后2位用來(lái)攜帶顯式擁塞通知信息(ECN域)，比如數(shù)據(jù)包是否經(jīng)歷了擁塞.與Precedence域定義的8個(gè)優(yōu)先級(jí)相比，DSCP域提供了64個(gè)不同的優(yōu)先級(jí)，可以滿足更多業(yè)務(wù)的需求[13].

在IETF 制定的這兩個(gè)標(biāo)準(zhǔn)中，ToS字段只是用戶表示的請(qǐng)求，不具有強(qiáng)制性.因此在以往服務(wù)種類單一、業(yè)務(wù)量少的網(wǎng)絡(luò)環(huán)境中，網(wǎng)絡(luò)硬件設(shè)備(例如交換機(jī)和路由器)通常會(huì)忽略ToS字段.然而現(xiàn)在的網(wǎng)絡(luò)已經(jīng)從面向單一的數(shù)據(jù)應(yīng)用轉(zhuǎn)變?yōu)槊嫦驈?fù)雜的綜合業(yè)務(wù)環(huán)境.在這種情況下，網(wǎng)絡(luò)硬件設(shè)備均會(huì)采用ToS字段作為判斷依據(jù)來(lái)為不同的業(yè)務(wù)提供相應(yīng)的服務(wù).這也意味著越來(lái)越多的業(yè)務(wù)開(kāi)始采用ToS字段來(lái)標(biāo)記其所希望的服務(wù)類別，以保證業(yè)務(wù)質(zhì)量[14- 15].

由于Precedence域和DSCP域的可讀性較差，其表示的優(yōu)先級(jí)并不能直接反應(yīng)出數(shù)據(jù)包所希望的服務(wù)類別，相比之下DTRC域具有更明確的指向性，因此本研究使用RFC 791標(biāo)準(zhǔn)中的DTRC域?qū)P包進(jìn)行分類.通過(guò)對(duì)當(dāng)前流行的應(yīng)用進(jìn)行分析，得到部分應(yīng)用層協(xié)議的服務(wù)類型，如表1所示.對(duì)于對(duì)延遲敏感的IP包，其多為通訊、語(yǔ)音數(shù)據(jù)，數(shù)據(jù)包長(zhǎng)度小，但單位時(shí)間內(nèi)數(shù)量大，一旦布魯姆過(guò)濾器誤將其判斷為用戶更關(guān)心的IP包，則會(huì)有大量的數(shù)據(jù)流優(yōu)先占用系統(tǒng)資源，從而造成系統(tǒng)的額外開(kāi)銷和較大的處理延遲.因此，可以將對(duì)延遲敏感的IP包認(rèn)為是識(shí)別失效代價(jià)高的IP包.同理，對(duì)吞吐率敏感的IP包多為文件傳輸應(yīng)用，其發(fā)生誤識(shí)別同樣會(huì)引起大量IP包搶占系統(tǒng)資源的現(xiàn)象，因此其也屬于識(shí)別失效代價(jià)較高的IP包.對(duì)于可靠性敏感、開(kāi)銷敏感的IP包，其多為系統(tǒng)控制應(yīng)用和一般應(yīng)用，發(fā)生誤識(shí)別不會(huì)引起大量的資源被搶占，屬于識(shí)別失效代價(jià)較低的IP包.

表1 部分協(xié)議的服務(wù)類型

設(shè)集合S被分為T類，S={{S1},{S2},…,{ST}}，每一類Si所對(duì)應(yīng)的元素個(gè)數(shù)為ni，Hash函數(shù)個(gè)數(shù)為ki，識(shí)別失效代價(jià)為ci，且當(dāng)icj(1≤i,j≤T).根據(jù)式(2)得到每一類Si對(duì)應(yīng)的假陽(yáng)性概率為fi，因此集合S的識(shí)別失效總代價(jià)F為

(8)

由于c1>c2>…>cT，因此降S1低類的假陽(yáng)性概率f1可以顯著減小失效總代價(jià).更進(jìn)一步，即使fT增大，只要f1足夠小，失效總代價(jià)仍然會(huì)降低.

當(dāng)集合S中任意一元素映射到向量V后，V中任一比特位為0的概率為

(9)

每類子集合出現(xiàn)假陽(yáng)性的概率fi(1≤i≤T)為

fi=(1-p)ki=ekiln(1-p)

(10)

令gi=kiln(1-p)，則gi∶g1=ki∶k1.取gi對(duì)ki的導(dǎo)數(shù)并令其為0，使gi取最小值時(shí)，得

(11)

將kmin代入式(10)，得每類子集合假陽(yáng)性概率的最小值：

(12)

將每類子集合Si的最小假陽(yáng)性概率代入式(8)，得到S的識(shí)別失效總代價(jià)的最小值Fmin：

(13)

對(duì)分類后的元素進(jìn)行Hash計(jì)算時(shí)，CPBF會(huì)建立流水加速計(jì)算速率，同時(shí)降低資源開(kāi)銷.在實(shí)際操作中，用戶關(guān)心的IP包只是海量IP包中很小的一部分，換句話說(shuō)，會(huì)有大量的IP包不能通過(guò)CPBF的識(shí)別[16].由于布魯姆過(guò)濾器的特性，只有當(dāng)所有的Hash函數(shù)查詢值為1時(shí)才會(huì)視為識(shí)別，因此對(duì)于不能識(shí)別的IP包，CPBF并不需要計(jì)算所有的Hash函數(shù).

設(shè)Hash函數(shù)組K被分為Q級(jí)，在平均分配的情況下，每一級(jí)的Hash函數(shù)的個(gè)數(shù)為k/Q.CPBF首先計(jì)算第一級(jí)Hash函數(shù)，只有當(dāng)?shù)谝患?jí)Hash函數(shù)查詢值全部為1時(shí)，才開(kāi)始第二級(jí)計(jì)算，依次類推；否則，直接判斷最終結(jié)果為不匹配.Q級(jí)中任一級(jí)流水判斷出元素不匹配的概率為

(14)

2.2 算法描述

CPBF算法中使用的參數(shù)除了SBF算法中的{S,K,V}外，還包括IP包類別T和流水級(jí)數(shù)Q，因此可用{S,K,V,T,Q}表示一個(gè)CPBF.對(duì)于一個(gè)參數(shù)確定的CPBF，T種分類所對(duì)應(yīng)的Hash函數(shù)的個(gè)數(shù)是唯一確定的，因此同時(shí)可以根據(jù)參數(shù)Q確定每一級(jí)流水中Hash函數(shù)的個(gè)數(shù).

CPBF算法的偽代碼描述如下：

1. Configure the parameters of CPBF;

2. Mapping kito Sirespectively;

3. Input IP packet P;

4. Get the 5-tuple and ToS values of the packet;

5. CASE (ToS) ∥ value of DTRC

6.the highest invalidation cost: THEN

7.classify P into S1;

8.the medium invalidation cost: THEN

9.classify P into S2;

10.the lowest invalidation cost : THEN

11.classify P into S3;

12.DEFAULT : THEN classify P into S3;

13. Set up the pipeline based on classification;

14. FOR(i=1;i≤Q;i++),THEN ∥Hash pipeline

15.Update the ith level’s Hash key;

16.Calculate 5-tuple’s the ith level Hash result;

17.Check the value in look-up table;

18.IF matching THEN

19. IF i≤Q,THEN

20.Forward back;∥prospective target packet

21. Else

22.packet P is the target packet;EXIT;

23.Else

24.packet P is a normal packet;EXIT;

2.3 算法分析

從下面空間復(fù)雜度(指硬件實(shí)現(xiàn)時(shí)的資源開(kāi)銷)、計(jì)算時(shí)間(指映射后進(jìn)行Hash函數(shù)計(jì)算的時(shí)間)、識(shí)別失效率(即假陽(yáng)性概率)3個(gè)性能指標(biāo)來(lái)進(jìn)行理論分析，從而比較CPBF和SBF以及MDBF的性能.

2.3.1 空間復(fù)雜度

在參數(shù)相同的情況下，SBF的硬件開(kāi)銷最小，最易實(shí)現(xiàn).CPBF在SBF的基礎(chǔ)上增加了分類、流水結(jié)構(gòu)，會(huì)增加一定的硬件開(kāi)銷.但流水結(jié)構(gòu)中可以實(shí)現(xiàn)硬件復(fù)用，如果流水級(jí)數(shù)足夠大，一定程度上可以減小硬件開(kāi)銷，但犧牲了對(duì)匹配元素的計(jì)算速率.因此，同計(jì)算時(shí)間一樣，CPBF的硬件資源開(kāi)銷會(huì)受到流水級(jí)數(shù)的直接影響.流水級(jí)數(shù)為2時(shí)硬件開(kāi)銷最大，但此時(shí)CPBF中的Hash函數(shù)的硬件開(kāi)銷仍然為SBF中Hash函數(shù)硬件開(kāi)銷的一半(設(shè)CPBF和SBF中一個(gè)Hash函數(shù)硬件開(kāi)銷相同).對(duì)于MDBF，由于其采用了并行處理的方式，無(wú)法實(shí)現(xiàn)Hash函數(shù)的硬件復(fù)用，因此在相同的參數(shù)下，其硬件開(kāi)銷在三者中最大.

2.3.2 計(jì)算時(shí)間

假設(shè)每個(gè)Hash函數(shù)一次計(jì)算所需的時(shí)間均相等，且時(shí)間為t.對(duì)于參數(shù)為{S,K,V,T,Q}的CPBF，子集合Si中的元素需要進(jìn)行ki次的Hash計(jì)算，那么其總計(jì)算時(shí)間為

TCPBF=(n1k1+n2k2+…+nTkT)t

(15)

因?yàn)镃PBF和SBF的總元素個(gè)數(shù)相同，因此可以得到SBF總計(jì)算時(shí)間為

TSBF=(n1+n2+…+nT)kt

(16)

假設(shè)CPBF中識(shí)別失效代價(jià)最高的子集合對(duì)應(yīng)的Hash函數(shù)個(gè)數(shù)等于SBF的Hash函數(shù)個(gè)數(shù)，即k1=k，那么可知k≥k2≥k3≥…≥kT.因此可以得到TCPBF≤TSBF.因?yàn)椴捎昧肆魉绞?，在?shí)際操作中對(duì)于不匹配的元素CPBF所需進(jìn)行的Hash計(jì)算次數(shù)會(huì)比n值小，因此總計(jì)算時(shí)間會(huì)進(jìn)一步減小.根據(jù)式(14)得到在采用平均分配流水的方式下，n=200、m=2 560時(shí)，CPBF中Q級(jí)流水的第1級(jí)判斷出的元素不匹配的概率如表2所示.

表2 第1級(jí)流水判斷出不匹配的概率

Table 2 Probability of mismatching by the detection of the first level pipeline

Qpk=12k=2420.94940.730930.86320.562640.77500.455060.63170.3277

由表2可見(jiàn)，在2級(jí)流水、k=12的情況下，第1級(jí)流水有接近95%的概率可以判斷出元素不匹配，那么下級(jí)流水中的Hash函數(shù)將不會(huì)再計(jì)算，因此總計(jì)算時(shí)間會(huì)減小一半.然而在流水級(jí)數(shù)較多的情況下，CPBF會(huì)進(jìn)行多次的計(jì)算、查找的切換，特別是對(duì)最終結(jié)果匹配的元素，從而造成總計(jì)算時(shí)間的增大.因此在流水劃分時(shí)，應(yīng)根據(jù)實(shí)際需求選擇合適的流水級(jí)數(shù)，保證CPBF的計(jì)算時(shí)間穩(wěn)定.

MDBF采用多布魯姆過(guò)濾器并行計(jì)算，因此其總計(jì)算時(shí)間由計(jì)算時(shí)間最長(zhǎng)的布魯姆過(guò)濾器決定.在MDBF中，每個(gè)布魯姆過(guò)濾器中Hash函數(shù)的個(gè)數(shù)較SBF少，因此其總計(jì)算時(shí)間TMDBF≤TSBF.對(duì)于一個(gè)確定的MDBF，無(wú)論最終識(shí)別結(jié)果如何，TMDBF是一個(gè)定值.然而對(duì)于CPBF來(lái)說(shuō)，受到流水劃分和識(shí)別結(jié)果的影響，TCPBF是一個(gè)變值.在參數(shù)相同的情況下，以2級(jí)流水CPBF為例，對(duì)于最終結(jié)果匹配的元

素，TCPBF≥TMDBF；對(duì)于最終結(jié)果不匹配的元素，TCPBF≤TMDBF.如前文所述，在實(shí)際操作中，最終匹配的IP包只是很小一部分，因此對(duì)于最終結(jié)果匹配時(shí)，TCPBF≥TMDBF是可以接受的.

2.3.3 識(shí)別失效率

對(duì)于SBF，在參數(shù){S,K,V}一定時(shí)，其識(shí)別失效率為定值；對(duì)于MDBF，在參數(shù)相同的情況下，由于其采用多個(gè)布魯姆過(guò)濾器，且每個(gè)布魯姆過(guò)濾器中Hash函數(shù)的個(gè)數(shù)較SBF少，因此由式(2)可知其識(shí)別失效率較SBF大.由于 CPBF根據(jù)元素的識(shí)別失效代價(jià)不同而采取不同的處理，因此其識(shí)別失效率隨元素的改變而動(dòng)態(tài)變化.對(duì)于高識(shí)別失效代價(jià)元素，CPBF采用較多數(shù)目Hash函數(shù)進(jìn)行映射，因此fCPBF≤fSBF；對(duì)于低識(shí)別失效代價(jià)元素，fCPBF≥fSBF，然而在不考慮識(shí)別速率的情況下，可以令Hash函數(shù)個(gè)數(shù)與SBF中Hash函數(shù)個(gè)數(shù)相等，從而使fCPBF=fSBF.

2.4 CPBF集成方案實(shí)現(xiàn)

IP包識(shí)別在計(jì)算機(jī)網(wǎng)絡(luò)ISO標(biāo)準(zhǔn)的數(shù)據(jù)鏈路層中實(shí)現(xiàn)[17].數(shù)據(jù)鏈路層由MAC子層和LLC子層(邏輯鏈路控制子層)構(gòu)成.由于MAC子層功能明確、邏輯復(fù)雜，在MAC子層進(jìn)行集成風(fēng)險(xiǎn)較大，因此本研究選擇在LLC層實(shí)現(xiàn)CPBF與NIC的集成，其耦合方案如圖3所示.CPBF與MAC之間采用標(biāo)準(zhǔn)的64位ARI接口，且對(duì)MAC透明.CPBF對(duì)IP包的處理與IP包緩存相互獨(dú)立，因此在CPBF不使能的情況下不會(huì)對(duì)IP包的正常處理造成影響，具有良好的可擴(kuò)展性.其工作流程如下：IP頭提取模塊提取出IP包中的IP五元組和ToS，由分類模塊根據(jù)ToS判斷出IP包的識(shí)別失效代價(jià)并進(jìn)行分類.Hash計(jì)算流水控制模塊根據(jù)分類結(jié)果控制Hash函數(shù)模塊對(duì)IP五元組進(jìn)行不同的處理.Hash函數(shù)模塊中采用Toeplitz Hash，因?yàn)橹恍枰薷腡oeplitz Hash中的Key值便可實(shí)現(xiàn)多個(gè)不同的Hash函數(shù).因此在流水結(jié)構(gòu)中復(fù)用了Hash函數(shù)模塊等諸多的硬件資源，通過(guò)Key值更新模塊來(lái)實(shí)現(xiàn)不同Hash函數(shù)的切換，進(jìn)一步節(jié)省了硬件資源.最終輸出模塊根據(jù)識(shí)別結(jié)果調(diào)用DMA將IP包搬移到指定的存儲(chǔ)空間.

3 性能評(píng)估

基于Xilinx的Virtex 5(model:xc5vlx110)對(duì)文中提出的CPBF算法進(jìn)行硬件實(shí)現(xiàn)，所有實(shí)驗(yàn)結(jié)果使用Xilinx的ISE仿真平臺(tái)獲取.為了對(duì)CPBF的性能進(jìn)行實(shí)際評(píng)估，同時(shí)也實(shí)現(xiàn)了SBF算法和MDBF算法.CPBF實(shí)現(xiàn)中將IP包根據(jù)ToS分為3類，延遲敏感的IP包識(shí)別失效代價(jià)最高，吞吐率敏感的IP包次之，其他IP包識(shí)別失效代價(jià)最低，分別對(duì)應(yīng)的Hash函數(shù)個(gè)數(shù)為24、12、9.MDBF實(shí)現(xiàn)中維數(shù)為5.其他參數(shù)三者均相同，分別為n=200、m=4 096、k=12.綜合后得到硬件開(kāi)銷如表3所示.

由表3可見(jiàn)，CPBF的硬件開(kāi)銷與流水等級(jí)成反比關(guān)系.與MDBF相比，CPBF的Slices的使用最大減少了14.9%(Q=6)，最小減少了9.8%(Q=2)，平均減少了12.4%.與SBF相比，CPBF在流水級(jí)數(shù)為2、3、4時(shí)，Slices的使用分別增加了14.0%、8.1%、2.0%，在流水級(jí)數(shù)為6時(shí)減少了2.1%.隨著流水級(jí)數(shù)的增大，CPBF的Slices開(kāi)銷逐漸減小，主要是因?yàn)镠ash函數(shù)模塊在硬件開(kāi)銷中所占的比例逐漸減小.CPBF的BRAMs較SBF增加了12.9%，主要原因是增加了流水機(jī)制后，CPBF需要緩存IP包和不同Hash函數(shù)的Key值.

表3 不同方案硬件開(kāi)銷對(duì)比

Table 3 Comparison of hardware costs under different solutions

算法硬件開(kāi)銷SlicesBRAMsCPBFQ=2827854Q=3783654Q=4740754Q=6711254SBF726247MDBF917572

圖3 CPBF與NIC耦合示意圖

文中使用PALAC中的TGEN模塊生成3組IP包對(duì)CPBF的識(shí)別速率進(jìn)行評(píng)估.PALAC是斯坦福大學(xué)計(jì)算機(jī)系統(tǒng)實(shí)驗(yàn)室公開(kāi)的包分類和測(cè)試平臺(tái)[18].3組IP包個(gè)數(shù)均為2 000，每個(gè)IP包大小為300字節(jié).在生成的3組IP包中，目標(biāo)IP包，即需要CPBF識(shí)別出的IP包分別占總IP包的10%、30%和50%.CPBF和SBF均采用數(shù)據(jù)總線為64位寬的ARI接口與IP包模塊相連，時(shí)鐘頻率為125 MHz，分別得到SBF和CPBF的總識(shí)別時(shí)間.對(duì)SBF的時(shí)間做歸一化處理，如圖4所示.

圖4 不同目標(biāo)IP包比例下識(shí)別時(shí)間對(duì)比

Fig.4 Comparison of matching time under different probabilities of target IP

由于3組實(shí)驗(yàn)中的IP包個(gè)數(shù)相等，因此SBF的識(shí)別時(shí)間為定值，為448 μs.對(duì)于CPBF，其識(shí)別時(shí)間隨流水級(jí)數(shù)和目標(biāo)IP包的不同而變化.在目標(biāo)IP包占總IP包10%和30%的兩組實(shí)驗(yàn)中，在2級(jí)流水的情況下CPBF的識(shí)別時(shí)間均小于SBF，分別減小了22%和5%；在6級(jí)流水的情況下，識(shí)別時(shí)間明顯增加.在目標(biāo)IP包占總IP包50%的實(shí)驗(yàn)中，無(wú)論采用幾級(jí)流水，CPBF的識(shí)別時(shí)間均超過(guò)了SBF的識(shí)別時(shí)間，且流水級(jí)數(shù)越大，識(shí)別時(shí)間越長(zhǎng)，在6級(jí)流水情況下識(shí)別時(shí)間為SBF的3.23倍.造成CPBF識(shí)別時(shí)間增大的主要原因是：①CPBF是面向偶發(fā)性或間歇性的IP包識(shí)別，適宜目標(biāo)IP包占總IP包比例較小的情況；②流水級(jí)數(shù)過(guò)大造成對(duì)目標(biāo)IP包識(shí)別速率的降低,從而導(dǎo)致總識(shí)別時(shí)間增大.因此在實(shí)際使用中，CPBF流水級(jí)數(shù)不應(yīng)過(guò)大，且以2級(jí)、3級(jí)流水為宜.

為了對(duì)CPBF在實(shí)際的網(wǎng)絡(luò)環(huán)境中進(jìn)行測(cè)試，采用某單位工作站網(wǎng)絡(luò)出口10 min的網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行評(píng)測(cè).該工作站有效用戶約300人.目標(biāo)IP包為指定客戶機(jī)與服務(wù)器之間的郵件應(yīng)用.分別進(jìn)行了3次采樣，采用L7-filter軟件的測(cè)試結(jié)果作為目標(biāo)IP包數(shù)量的真值[19]，具體描述如表4所示.

表4 測(cè)試數(shù)據(jù)集

圖5 實(shí)際網(wǎng)絡(luò)環(huán)境中不同識(shí)別算法的實(shí)驗(yàn)結(jié)果

Fig.5 Experimental results of different matching algorithms under realistic situation

實(shí)驗(yàn)中CPBF采用3級(jí)流水，其他各項(xiàng)參數(shù)以及SBF、MDBF各項(xiàng)參數(shù)、實(shí)現(xiàn)環(huán)境均保持不變.3種算法識(shí)別結(jié)果與耗時(shí)如圖5所示.實(shí)驗(yàn)結(jié)果表明，對(duì)于3個(gè)樣本，CPBF的IP包識(shí)別數(shù)目均更接近于真實(shí)值，即識(shí)別失效的IP包數(shù)目較SBF和MDBF更低.計(jì)算得到3次樣本實(shí)驗(yàn)中CPBF平均識(shí)別失效率較SBF降低了43.2%，較MDBF降低了61.8%；在識(shí)別耗時(shí)方面，CPBF的識(shí)別耗時(shí)較SBF平均減少了17%，但較MDBF平均增加了7.8%.綜合識(shí)別結(jié)果和識(shí)別耗時(shí)，CPBF在識(shí)別失效率和識(shí)別速率兩方面比MDBF表現(xiàn)出了更好的平衡性.

4 結(jié)論

本研究立足于識(shí)別失效率、硬件實(shí)現(xiàn)開(kāi)銷和識(shí)別速率，提出一種面向IP包識(shí)別的算法CPBF.該算法首先引入了識(shí)別失效代價(jià)的概念，采用ToS對(duì)IP包進(jìn)行分類，對(duì)不同類別的IP包分配不同數(shù)目的Hash函數(shù)，并采用流水結(jié)構(gòu)加速Hash結(jié)構(gòu)對(duì)IP包的識(shí)別；給出了一種CPBF算法的硬件實(shí)現(xiàn)方式，采用更新Key值和硬件復(fù)用的方式進(jìn)一步減小了硬件消耗；最后，通過(guò)實(shí)驗(yàn)對(duì)CPBF的性能進(jìn)行了評(píng)估，并與SBF和MDBF進(jìn)行了比較，結(jié)果表明，CPBF的識(shí)別失效率、硬件開(kāi)銷以及識(shí)別速率等方面都有較大改善.針對(duì)CPBF還可以進(jìn)一步關(guān)注和探討如何動(dòng)態(tài)更新CPBF的識(shí)別規(guī)則集以適應(yīng)未來(lái)更多的應(yīng)用.

[1] GADELRAB SERAG.10-Gigabit ethernet connectivity for computer servers [J].IEEE Micro,2007,27(3):94- 105.

[2] YU F,KATZ RANDY H,LAKSHMAN T V.Gigabit rate packet pattern-matching using TCAM [C]∥Proceedings of the 12th IEEE International Conference on Network Protocols.Berlin:IEEE,2004:174- 183.

[3] CHAVAN M K,AGARKAR B S.Application of bloom filters in fast packet classification [J].Research Journal of Engineering and Technology,2014,5(2):77.

[4] DEKE G,HONGHUI C,JIE W,et al.Theory and network application of dynamic bloom filters [C]∥Proceedings of the 25th IEEE International Conference on Computer Communications.Barcelona:IEEE,2006:1- 12.

[5] IOANNIS PAPAEFSTATHIOU.Memory-efficient 5D packet classification at 40Gbps [C]∥Proceedings of the 26th IEEE International Conference on Computer Communications.Anchorage:IEEE,2007:1370- 1378.

[6] 王勇,云曉春,王樹(shù)鵬,等.CBFM:支持屬性刪減的布魯姆過(guò)濾器矩陣多維元素查詢算法 [J].通信學(xué)報(bào),2016,37(3):139- 147.

WANG Yong,YUN Xiao-chun,WANG Shu-peng,et al.CBFM：cutted bloom filter matrix for multi-dimensional membership query [J].Journal on Communications,2016,37(3):139- 147.

[7] 亓亞烜,李軍.高性能網(wǎng)包分類理論與算法綜述 [J].計(jì)算機(jī)學(xué)報(bào),2013,36(2):408- 421.

QI Ya-xuan,LI Jun.Theoretical analysis and algorithm design of high-performance packet classification algorithms [J].Chinese Journal of Computers,2013,36(2):408- 421.

[8] QUAN WEI,XU C,VASILAKOS A V,et al.TB2F:Tree-bitmap and bloom-filter for a scalable and efficient name lookup in content-centric networking [C]∥ 2014 Networking Conference of International Federation for Information Processing.Trondheim:IEEE,2014:1- 9.

[9] YANG TONG,XIE G,SUN X,et al.Towards practical use of bloom filter based IP lookup in operational network [C]∥Network Operations and Management Symposium.Krakow:IEEE,2014:1- 4.

[10] LIM H,LIM K,LEE N,et al.On adding bloom filters to longest prefix matching algorithms [J].IEEE Transactions on Computers,2014,63(2):411- 423.

[11] WU H,GONG J,YANG W.Algorithm based on double counter bloom filter for large flows identification [J].Journal of Software,2010,21(5):1115- 1126.

[12] 周舟,付文亮,嵩天,等.一種基于并行 Bloom Filter 的高速 URL 查找算法 [J].電子學(xué)報(bào),2015,43(9):1833- 1840.

ZHOU Zhou,FU Wen-liang,SONG Tian,et al.Fast URL lookup using parallel bloom filters [J].Chinese Journal of Electronics,2015,43(9):1833- 1840.

[13] ANDREW S,TANENBAUM.Computer networks [M].5th ed.New Jersey:Prentice Hall,2011:439.

[14] MOMANY E O,ODUOL V K,MUSYOKI S.First in first out (FIFO) and priority packet scheduling based on type of service (TOS) [J].Journal of Information Engineering and Applications,2014,4(7):22- 36.

[15] FENG S,HU C,MA K,et al.Implementation and application of QoS in power ethernet switch [J].Advanced Materials Research,2014,49(1):338- 343.

[16] TATE J,BECK P,CLEMENTS P,et al.IBM and Cisco:together for a world class data center [M].New York:IBM Redbooks,2013:287.

[17] MOORE A W,PAPAGIANNAKI K.Toward the accurate identification of network applications [C]∥ International Workshop on Passive and Active Network Measurement.Berlin:Springer,2005:41- 54.

[18] GUPTA P,BALKMAN J.PALAC:Packet look up and classification simulator [Z].San Francisco:Stanford University,2000.

[19] ACETO G,DAINOTTI A,DE DONATO W,et al.PortLoad:taking the best of two worlds in traffic classification [C]∥Proceedings of the 29th IEEE International Conference on Computer Communications.San Diego:IEEE,2010:1- 5.

CPBF:anIPPackageIdentificationAlgorithmUsingBloomFilter

LILong-feiHEZhan-zhuangSHIYang-chun

(Department of Integrated Circuit Design, Xi’an Microelectronics Technology Institute, Xi’an 710065, Shaanxi, China)

As the traditional Bloom filters adopt the same process for different IP packages and ignore not only IP package identification invalidation cost but also hardware resource in the process of flow identification, an algorithm called CPBF (Classified and Pipelined Bloom Filter) for IP package identification is presented. CPBF differentiates IP packages depending on ToS (Type of Service), which can reflect their identification invalidation cost in some ways. In order to minimize the identification invalidation rate, different numbers of Hash functions are applied to different types of IP packages. Specifically, pipelined Hash functions are adopted to accelerate the identification speed. Moreover, on the basis of the theories of probability and differential equation, the description and analytical expression of CPBF are deduced. Finally, an implementation of CPBF is conducted on FPGA. The results indicate that CPBF is superior to standard Bloom filter and multi-dimensional Bloom filter because it helps achieve lower identification invalidation rate and hardware resource cost without sacrificing identification speed.

Bloom filter;CPBF algorithm;IP package identification;identification invalidation cost;Hash function

2016- 05- 18

總裝備部軍用電子元器件型譜系列科研項(xiàng)目(1407XJ0900)

*Foundationitem: Supported by the Scientific Research Project of Military Electronic Components Portfolio of General Armament Department(1407XJ0900)

李龍飛(1988-)，男，博士生，主要從事計(jì)算機(jī)網(wǎng)絡(luò)硬件加速技術(shù)研究.E-mail:longfeisos@163.com

1000- 565X(2017)07- 0090- 08

TP 301.6

10.3969/j.issn.1000-565X.2017.07.013