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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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