基于FPGA的報(bào)文分類技術(shù)研究_優(yōu)秀論文

1、 基于FPGA的報(bào)文分類技術(shù)研究 引 言 隨著快速增長(zhǎng)的網(wǎng)絡(luò)鏈路速率與分類規(guī)則的增多, 多維報(bào)文分類問題成為設(shè)計(jì)高速路由器的一個(gè)基本挑戰(zhàn)。例如, 當(dāng)主干網(wǎng)鏈路速率達(dá)到80Gbps時(shí), 在報(bào)文長(zhǎng)度為40字節(jié)時(shí), 需要每4ns內(nèi)處理一個(gè)數(shù)據(jù)報(bào), 這個(gè)速度用現(xiàn)在的軟件算法不可能實(shí)現(xiàn)。 為了滿足以上網(wǎng)絡(luò)速率的需要, 研究人員尋求硬件上的解決方案, 三態(tài)內(nèi)容存儲(chǔ)器(ternary content addressable memory-TCAM)是一個(gè)不錯(cuò)的選擇, 它能夠?qū)斎氲年P(guān)鍵字進(jìn)行并行查找, 最大的優(yōu)點(diǎn)是分類速度快, 但也有如下一些缺點(diǎn), 如存儲(chǔ)面積大、價(jià)格高, 特別是TCAM不支持直接的范圍匹配

2、等。另一方面, 由于FPGA具有可重構(gòu)性和并行性, 結(jié)合了軟件的靈活性與硬件的高效性, 使它成為實(shí)現(xiàn)實(shí)時(shí)網(wǎng)絡(luò)處理引擎一個(gè)很好的選擇?，F(xiàn)在, 研究人員已經(jīng)開始在FPGA上實(shí)現(xiàn)一些現(xiàn)有分類算法, 可以達(dá)到很高的吞吐量, 由于存儲(chǔ)需求過多, 這些算法很少有能夠支持大的規(guī)則集(超過10K)。本文主要針對(duì)基于決策樹類的分類算法在FPGA中的實(shí)現(xiàn)做了深入研究, 解決了在規(guī)則集較大的情況下對(duì)報(bào)文進(jìn)行快速分類的問題。 1 分類算法的定義及評(píng)估方法 1.1 分類算法的定義 報(bào)文分類問題有許多定義, 它們基本上是等價(jià)的, 描述如下：報(bào)文頭部H 包含K個(gè)域, 分別表示成H1、H2HK, 一條過濾規(guī)則F相應(yīng)地也具有K

3、 個(gè)域, 其中Fi(F的第i部分)是Hi的正則表達(dá)式, 如果對(duì)任意的H i滿足正則表達(dá)式F i, 則稱報(bào)文P與規(guī)則F相匹配。 對(duì)具有N條過濾規(guī)則的分類器R來說, 為了解決同一個(gè)報(bào)文與分類器R中多條規(guī)則相匹配的問題, 在定義過濾規(guī)則F時(shí), 對(duì)每條規(guī)則指定了一個(gè)優(yōu)先級(jí), 當(dāng)有多條規(guī)則與報(bào)文頭部匹配時(shí), 選擇一個(gè)優(yōu)先級(jí)最高的作為最終匹配規(guī)則。與每條規(guī)則相關(guān)聯(lián)還有一個(gè)動(dòng)作, 它指出了當(dāng)報(bào)文與此規(guī)則相匹配時(shí), 下一步所執(zhí)行的操作, 一個(gè)包含10規(guī)則的簡(jiǎn)單分類器。 也可以從計(jì)算機(jī)幾何中的點(diǎn)定位問題來看待多維報(bào)文分類問題, 一個(gè)D維的分類規(guī)則相當(dāng)于D維空間中的一個(gè)超矩形, D維空間中的N個(gè)規(guī)則至多可構(gòu)成(2

4、N-1)D 個(gè)互不重疊的超矩形, 而一個(gè)報(bào)文則相當(dāng)于D維空間中的一個(gè)點(diǎn), 所以, 多維報(bào)文分類轉(zhuǎn)化為找到包含這個(gè)點(diǎn)的超矩形。由此可得到, 多維報(bào)文分類的時(shí)間復(fù)雜度為O(logN), 空間復(fù)雜度為O(ND), 或是在時(shí)間度為O(logD-1 N)的情況下, 空間復(fù)雜度為O(N)。從上面的分析可以看到, 多維報(bào)文分類問題是一個(gè)非常復(fù)雜的問題, 幸運(yùn)的是, 現(xiàn)實(shí)情況要比這好, 真實(shí)的分類器沒這么復(fù)雜, 它們有一些自身特點(diǎn), 我們可以在實(shí)際中加以利用, 可以使分類算法得到簡(jiǎn)化。 1.2 分類算法的評(píng)估方法 由于IP分類問題可以抽象成一個(gè)查找表項(xiàng)巨大的多關(guān)鍵字查找問題, 因此衡量一個(gè)算法好壞的關(guān)鍵是查詢

5、速度快, 再就是用分類規(guī)則來構(gòu)建查找表數(shù)據(jù)結(jié)構(gòu)時(shí)所占內(nèi)存要少?？紤]到分類算法自身的特點(diǎn), 其它評(píng)估方法還有過濾規(guī)則的插入與刪除速度快, 維數(shù)(查找中關(guān)鍵字個(gè)數(shù))易擴(kuò)展以及能夠根據(jù)規(guī)則中各個(gè)域的不同表現(xiàn)形式, 支持多種查詢(匹配)方式等?？偟膩碚f, 算法的關(guān)鍵是怎么找到時(shí)間與空間的平衡點(diǎn)。 2 現(xiàn)有的分類算法 現(xiàn)有的分類算法很多, 文獻(xiàn)對(duì)各類算法進(jìn)行了總結(jié), 并對(duì)每種類型的算法, 列舉出了相關(guān)的例子;文獻(xiàn)根據(jù)分類算法對(duì)規(guī)則進(jìn)行預(yù)處理情況, 把它們分為基于分解、基于分割和基于決策樹3種情況。 基于分解算法的主要思想是對(duì)報(bào)文頭部的每個(gè)域進(jìn)行獨(dú)立的搜索, 最后把每個(gè)域查詢結(jié)果結(jié)合起, 就可得到最終匹配

6、規(guī)則, 該類型的算法適合于硬件實(shí)現(xiàn), 典型代表是平行位向量(parallel bit vector)(BV)算法。基于分割算法的主要思想是把原來的規(guī)則集劃分為若干個(gè)子集, 每個(gè)子集中的規(guī)則在單個(gè)或多個(gè)域之間是沒有重疊的, 獨(dú)立集合算法(independent sets algorithm)就屬于這類。我們知道, 對(duì)于有N 條分類規(guī)則的D維分類器, 算法所需要的空間復(fù)雜度為O(ND), 現(xiàn)假設(shè)把規(guī)則集R均勻地劃分為K組, 每組有N/K個(gè)規(guī)則, 劃分后的空間復(fù)雜度為O(K*(N/K)D), 所以通過規(guī)則集劃分后, 空間復(fù)雜度減少為原來的1/KD-1。算法面臨的主要挑戰(zhàn)是獨(dú)立規(guī)則集劃分個(gè)數(shù)的不確定性

7、和過多。 決策樹類的代表算法是HiCuts, 它通過對(duì)分類器的預(yù)處理, 建立決策樹這種數(shù)據(jù)結(jié)構(gòu), 樹的根點(diǎn)代表整個(gè)搜索空間, 它包含了規(guī)則集中的所有規(guī)則, 對(duì)決策樹中的每個(gè)內(nèi)部點(diǎn), 都遞歸地進(jìn)行如下操作, 根據(jù)預(yù)先定義的某種標(biāo)準(zhǔn), 選擇在某一維方向上, 相等地切割多少份, 直到該結(jié)點(diǎn)所包含的規(guī)則數(shù)少于預(yù)先定義的某個(gè)定值為止, 不再進(jìn)行切割, 該結(jié)點(diǎn)為葉子結(jié)點(diǎn)。每當(dāng)有報(bào)文達(dá)到時(shí), 對(duì)決策樹進(jìn)行遍歷, 找到葉子結(jié)點(diǎn), 由于葉子結(jié)點(diǎn)中的規(guī)則數(shù)較少, 可以進(jìn)行線性搜索, 找到最佳匹配規(guī)則。Hi-Cuts算法的主要缺點(diǎn)是由于對(duì)搜索空間進(jìn)行了切割, 帶來了規(guī)則的復(fù)制, 增加了存儲(chǔ)空間。HyperCuts算

8、法是Hi-Cuts的改進(jìn)版本, HiCuts是通過局部?jī)?yōu)化的方法在每個(gè)結(jié)點(diǎn)選擇哪一維和切割多少份來建立決策樹, 而Hyper-Cuts算法允許每一步選擇多個(gè)維度進(jìn)行切割, 其結(jié)果是樹的寬度變大, 深度減少。例如對(duì)表1中前5個(gè)規(guī)則所建立的決策樹如圖1所示(只選擇源/目的端口), 可以看到對(duì)規(guī)則集端口域采用HyperCuts算法切割后, 決策樹的深度從3變成2了。 (a)X軸與Y軸分別表示表1中規(guī)則R1至R5所代表的源端口域與目的端口域, (b)(c)圓矩形框表示樹的內(nèi)部結(jié)點(diǎn), 長(zhǎng)方形框表示樹的葉子結(jié)點(diǎn))現(xiàn)在, 這幾類算法都能在FPGA中實(shí)現(xiàn), 文獻(xiàn)是基于分割算法在FPGA中的實(shí)現(xiàn), 為了避免分割

9、的子集過多, 該文獻(xiàn)對(duì)Independent Sets algorithm 進(jìn)行改進(jìn), 提出了coarse-grained獨(dú)立集合算法, 該算法把原始規(guī)則集劃分為若干個(gè)coarse-grained獨(dú)立集合, 進(jìn)行并行搜索, 剩下的規(guī)則建立cross-producting表進(jìn)行查詢。由于對(duì)獨(dú)立集合算法進(jìn)行了改進(jìn), 可以在coarse-grained中存放更多的規(guī)則, 這樣規(guī)則子集數(shù)就減少了, 在Xilinx Virtex-5FPGA上實(shí)現(xiàn)結(jié)果表明, 在消耗較少片內(nèi)資源情況下, 在單個(gè)FPGA芯片中能夠存儲(chǔ)10K的實(shí)時(shí)規(guī)則, 在最小報(bào)文長(zhǎng)度為40字節(jié)時(shí), 可以維持80Gbps的吞吐量。 文獻(xiàn)把基于

10、分割算法與決策樹算法結(jié)合起來, 即先把規(guī)則集分割成若干個(gè)子集, 再對(duì)各個(gè)子集分別建立決策樹, 當(dāng)報(bào)文達(dá)到時(shí), 可以對(duì)各個(gè)決策樹進(jìn)行并行搜索。為了使對(duì)規(guī)則的劃分達(dá)到最優(yōu), 作者采用范圍到點(diǎn)轉(zhuǎn)換(range-point conversion)的思想, 也就是F維空間中的一個(gè)超矩形能夠在2F空間中轉(zhuǎn)換成一個(gè)點(diǎn)。從計(jì)算幾何的角度來看, 每個(gè)D維分類規(guī)則可以看作是D維空間中的一個(gè)超矩形, 也就是2D空間中的一個(gè)點(diǎn), 再用組合優(yōu)化的方法把這些點(diǎn)劃分成不同的集合, 為了使劃分達(dá)到近似最優(yōu), 使用模擬退伙的方法, 在各個(gè)集合之間進(jìn)行相應(yīng)的規(guī)則調(diào)整。當(dāng)近似優(yōu)化劃分完成后, 對(duì)每個(gè)子集用Hyper-Split算法

11、分別建立決策樹, 再把每棵決策樹映射到專有的流水線上, 由于這個(gè)設(shè)計(jì)消耗的資源較少, 多個(gè)這樣的機(jī)制能夠在單個(gè)FPGA中實(shí)現(xiàn), 達(dá)到更高的吞吐量。 3 改進(jìn)的HyperCuts算法在FPGA中的實(shí)現(xiàn)雖然HyperCuts算法對(duì)HiCuts有很多改進(jìn), 但是在建立決策樹時(shí), 雖然能減少樹的深度, 但并沒有消除規(guī)則復(fù)制, 從圖2中我們可以看到, 在兩棵決策樹中, 規(guī)則R1、R2和R4都得復(fù)制到它們多個(gè)孩子結(jié)點(diǎn)中。通過觀察可以發(fā)現(xiàn), 規(guī)則復(fù)制有兩個(gè)來源, 一是不同的規(guī)則之間相互重疊, 上例中R1與R3、R5都重疊, 無論怎么切割, R1都要復(fù)制到包含R3與R5的結(jié)點(diǎn)中去;二是在每個(gè)維度上進(jìn)行均勻切割

12、, 如R2與R4都要復(fù)制一次, 雖然它們沒有與任何規(guī)則相重疊。需要說明的是第二點(diǎn)對(duì)用前綴表示的IP地址來說并不存在, 因?yàn)镮P地址查找是從最高有效位到最低有效位, 等同于均勻切割。針對(duì)上面的問題, 我們提出了兩個(gè)優(yōu)化的方法(圖2), 一是把需要復(fù)制到多個(gè)孩子結(jié)點(diǎn)的規(guī)則, 存儲(chǔ)到附加在內(nèi)部結(jié)點(diǎn)的一條鏈中, 這個(gè)鏈叫做內(nèi)部規(guī)則鏈, 例如上面的R1, 就可以把它選出來放在附加在根結(jié)點(diǎn)中的規(guī)則鏈中;第二種方法叫做精確范圍切割, 當(dāng)我們對(duì)端口域進(jìn)行切割時(shí), 選擇能導(dǎo)致最小復(fù)制的切割點(diǎn), 重新選擇切割點(diǎn)后, R2與R4就不用復(fù)制了。 3.1 決策樹的建立 結(jié)合上面兩種優(yōu)化思想, 用以下步驟來建立決策樹,

13、首先, 從根結(jié)點(diǎn)開始, 根結(jié)點(diǎn)包含了規(guī)則集中的所有規(guī)則, 對(duì)決策樹結(jié)點(diǎn)進(jìn)行遞歸地切割, 直到葉子, 葉子結(jié)點(diǎn)包含規(guī)則小于等于預(yù)先定義的參數(shù)binth。在每個(gè)內(nèi)部結(jié)點(diǎn), 需要計(jì)算出對(duì)哪些維進(jìn)行切割, 每一維切割多少份, 規(guī)則切割次數(shù)的上限為64, 所以每個(gè)內(nèi)部結(jié)點(diǎn)有2、4、8、16、32或64個(gè)孩子。對(duì)于端口域需要尋找精確的切割點(diǎn), 而不是切割多少份, 可以限定端口域最大的切割數(shù)為2。因此沒有對(duì)協(xié)議域進(jìn)行切割, 因?yàn)樵趯?shí)時(shí)規(guī)則集中, 前四維就可以滿足分類要求了。當(dāng)選擇哪些維進(jìn)行切割和在源、目的IP地址上切割多少份時(shí), 標(biāo)準(zhǔn)與HiCuts和Hyper-Cuts算法一樣, 不同之處在于, 當(dāng)選擇端口

14、域進(jìn)行切割時(shí), 選擇的切割點(diǎn)能導(dǎo)致最少規(guī)則復(fù)制;當(dāng)切割方法決定下來后, 把在當(dāng)前結(jié)點(diǎn)中復(fù)制次數(shù)最多的規(guī)則挑選出來, 加到當(dāng)前結(jié)點(diǎn)的內(nèi)部規(guī)則鏈中, 直到鏈中規(guī)則數(shù)達(dá)到上界binth為止。 3.2 決策樹映射到流水線 為了把決策樹映射到流水線去, 流水線每一階段需要的存儲(chǔ)大小都需要在FPGA實(shí)現(xiàn)之前確定, 一般采用的方法是, 把決策樹相同層次上的結(jié)點(diǎn)映射到單獨(dú)的階段中去, 由于存儲(chǔ)分布在每個(gè)階段變化很大, 如果在每個(gè)階段分配最大的存儲(chǔ)量, 將造成浪費(fèi)?？梢钥紤]把決策樹映射到線性流水線中去, 達(dá)到在每個(gè)階段平衡存儲(chǔ)分布的目的, 同時(shí)還可以維持每個(gè)時(shí)鐘周期處理一個(gè)報(bào)文的吞吐量。由于在這種體系中存在著兩

15、種流水線組織, 因此, 不僅在樹流水線中, 而且也要規(guī)則流水線中考慮各個(gè)階段的存儲(chǔ)分布情況, 規(guī)則流水線中每個(gè)階段需要的存儲(chǔ)量取決于樹的結(jié)點(diǎn)數(shù), 所以樹到流水線映射的方式中, 既要平衡存儲(chǔ)分配情況, 也要平衡各個(gè)階段的結(jié)點(diǎn)分布情況。在把決策樹映射到線性流水線的過程中, 可以考慮把同一層的結(jié)點(diǎn)映射到流水線的不同階段上去, 這就為樹結(jié)點(diǎn)映射提供了更多的靈活性, 這樣在每個(gè)階段中能平衡存儲(chǔ)和結(jié)點(diǎn)分布, 需要的一個(gè)約束是, 如果在決策樹中結(jié)點(diǎn)A 是結(jié)點(diǎn)B的祖先, 則A映射到的階段要先于B的映射。 3.3 搜索過程 當(dāng)報(bào)文達(dá)到樹流水線的某個(gè)階段進(jìn)行存儲(chǔ)訪問時(shí), 它同時(shí)也得到了與當(dāng)前樹結(jié)點(diǎn)相聯(lián)系的規(guī)則鏈指

16、針, 報(bào)文利用這個(gè)指針與該規(guī)則鏈中的所有規(guī)則進(jìn)行匹配, 由于FP-GA提供了足夠的字寬, 每條規(guī)則作為一個(gè)字存儲(chǔ)在規(guī)則流水線的某個(gè)階段上。在規(guī)則流水線的某個(gè)階段上, 報(bào)文利用指針找到一個(gè)規(guī)則, 并用報(bào)文頭部與該規(guī)則進(jìn)行比較, 對(duì)不同的域, 可采用不同的比較方法, 如范圍、前綴、定值比較。當(dāng)它在當(dāng)前規(guī)則流水線階段找到匹配的規(guī)則后, 遍歷過程并沒有結(jié)束, 它需要記下當(dāng)前規(guī)則優(yōu)先級(jí), 以便與下一個(gè)匹配規(guī)則相比較。 3.4 規(guī)則更新 當(dāng)有規(guī)則需要添加或刪除時(shí), 也就是規(guī)則更新, 一般采用增量更新的方法, 這種方法消耗存儲(chǔ)空間較少, 但是頻繁的添加與刪除操作將導(dǎo)致決策樹的不穩(wěn)定, 最終得對(duì)決策樹進(jìn)行重建

17、。這里用文獻(xiàn)中的write-bubbles方法, 即通過插入write-bubbles到各自的流水線上, 可以在硬件中實(shí)現(xiàn)即時(shí)更新(即在更新過程中, 分類操作并沒有停止)。然而, 大規(guī)模的改變數(shù)據(jù)結(jié)構(gòu)需要更有效方法, 即緩存?zhèn)浞? 這個(gè)方法需要建立額外的流水線來存放需要更新的數(shù)據(jù), 當(dāng)這個(gè)流水線準(zhǔn)備好了以后, 與需要更新的流水線進(jìn)行交換, 這種方法犧牲了FPGA中的邏輯與RAM, 但是帶來了更有效的即時(shí)更新。 4 實(shí)驗(yàn)結(jié)果 實(shí)驗(yàn)所用分類規(guī)則是訪問控制鏈規(guī)則(aclnum), 規(guī)則個(gè)數(shù)從100 到50000, 可以從：http：//hs1/PClassEval.

18、html中下載得到。 例如, acl10K表示是由classbench在acl種子文件下產(chǎn)生的10000條件規(guī)則, 實(shí)驗(yàn)中用到了num 數(shù)為100、1K、5K、10K的4種規(guī)則集。由于這個(gè)算法主要是在Hyper-Cuts算法中做了相應(yīng)的改進(jìn), 所以對(duì)這兩種算法在兩個(gè)參數(shù)上進(jìn)行了比較, 一是每個(gè)規(guī)則消耗的存儲(chǔ)大小, 主要用來說明算法的可擴(kuò)展性;二是決策樹的高度, 用來指出樹流水線的階段數(shù)。比較結(jié)果從中可以看到, 隨著規(guī)則數(shù)的增加, 每個(gè)規(guī)則所需要的存儲(chǔ)空間基本上保持不變, 這說明了整個(gè)存儲(chǔ)空間需求與存儲(chǔ)規(guī)則數(shù)呈線性增長(zhǎng)關(guān)系, 易于擴(kuò)展;同時(shí), 由于優(yōu)化了切割方法, 決策樹的深度也降低了, 減少了報(bào)文遍歷決策樹的延遲。FPGA器件采用當(dāng)前比較先進(jìn)的Xilinx Virtex-6, 型號(hào)是XC6VSX475T, 它包含7640Kb分布式RA