基于FPGA的報文分類技術

王 敏，邰 銘

（1.信息工程大學 網絡空間安全學院，河南 鄭州450001；2.信息工程大學數學工程與先進計算國家重點實驗室，河南 鄭州450001）

0 引 言

隨著快速增長的網絡鏈路速率與分類規則的增多，多維報文分類問題成為設計高速路由器的一個基本挑戰。例如，當主干網鏈路速率達到80Gbps時，在報文長度為40字節時，需要每4ns內處理一個數據報，這個速度用現在的軟件算法不可能實現。

為了滿足以上網絡速率的需要，研究人員尋求硬件上的解決方 案，三 態 內 容 存 儲 器［1］（ternary content addressable memory－TCAM）是一個不錯的選擇，它能夠對輸入的關鍵字進行并行查找，最大的優點是分類速度快，但也有如下一些缺點，如存儲面積大、價格高，特別是TCAM不支持直接的范圍匹配等。另一方面，由于FPGA具有可重構性和并行性，結合了軟件的靈活性與硬件的高效性，使它成為實現實時網絡處理引擎一個很好的選擇。現在，研究人員已經開始在FPGA上實現一些現有分類算法［2－4］，可以達到很高的吞吐量，由于存儲需求過多，這些算法很少有能夠支持大的規則集 （超過10K）。本文主要針對基于決策樹類的分類算法在FPGA中的實現做了深入研究，解決了在規則集較大的情況下對報文進行快速分類的問題。

1 分類算法的定義及評估方法

1.1 分類算法的定義

報文分類問題有許多定義，它們基本上是等價的，描述如下：報文頭部H包含K個域，分別表示成H［1］、H［2］…H［K］，一條過濾規則F相應地也具有K個域，其中F［i］（F的第i部分）是H［i］的正則表達式，如果對任意的H ［i］滿足正則表達式F［i］，則稱報文P與規則F相匹配。

對具有N條過濾規則的分類器R來說，為了解決同一個報文與分類器R中多條規則相匹配的問題，在定義過濾規則F時，對每條規則指定了一個優先級，當有多條規則與報文頭部匹配時，選擇一個優先級最高的作為最終匹配規則。與每條規則相關聯還有一個動作，它指出了當報文與此規則相匹配時，下一步所執行的操作，一個包含10規則的簡單分類器見表1。

表1 10個規則的分類器例子 （IP地址8位；端口號4位；協議域2位）

也可以從計算機幾何中的點定位問題來看待多維報文分類問題，一個D維的分類規則相當于D維空間中的一個超矩形，D維空間中的N個規則至多可構成 （2N－1）D個互不重疊的超矩形，而一個報文則相當于D維空間中的一個點，所以，多維報文分類轉化為找到包含這個點的超矩形。由此可得到，多維報文分類的時間復雜度為O（logN），空間復雜度為O（ND），或是在時間度為O（logD－1N）的情況下，空間復雜度為O（N）。從上面的分析可以看到，多維報文分類問題是一個非常復雜的問題，幸運的是，現實情況要比這好，真實的分類器沒這么復雜，它們有一些自身特點，我們可以在實際中加以利用，可以使分類算法得到簡化。

1.2 分類算法的評估方法

由于IP分類問題可以抽象成一個查找表項巨大的多關鍵字查找問題，因此衡量一個算法好壞的關鍵是查詢速度快，再就是用分類規則來構建查找表數據結構時所占內存要少。考慮到分類算法自身的特點，其它評估方法還有過濾規則的插入與刪除速度快，維數 （查找中關鍵字個數）易擴展以及能夠根據規則中各個域的不同表現形式，支持多種查詢 （匹配）方式等。總的來說，算法的關鍵是怎么找到時間與空間的平衡點。

2 現有的分類算法

現有的分類算法很多，文獻 ［5］對各類算法進行了總結，并對每種類型的算法，列舉出了相關的例子；文獻［6］根據分類算法對規則進行預處理情況，把它們分為基于分解、基于分割和基于決策樹3種情況。

基于分解算法的主要思想是對報文頭部的每個域進行獨立的搜索，最后把每個域查詢結果結合起，就可得到最終匹配規則，該類型的算法適合于硬件實現，典型代表是平行位向量 （parallel bit vector）（BV）算法。

基于分割算法的主要思想是把原來的規則集劃分為若干個子集，每個子集中的規則在單個或多個域之間是沒有重疊的，獨立集合算法 （independent sets algorithm））就屬于這類。我們知道，對于有N條分類規則的D維分類器，算法所需要的空間復雜度為O（ND），現假設把規則集R均勻地劃分為K組，每組有N／K個規則，劃分后的空間復雜度為O（K＊（N／K）D），所以通過規則集劃分后，空間復雜度減少為原來的1／KD－1。算法面臨的主要挑戰是獨立規則集劃分個數的不確定性和過多。

決策樹類的代表算法是HiCuts，它通過對分類器的預處理，建立決策樹這種數據結構，樹的根點代表整個搜索空間，它 “包含”了規則集中的所有規則，對決策樹中的每個內部點，都遞歸地進行如下操作，根據預先定義的某種標準，選擇在某一維方向上，相等地切割多少份，直到該結點所 “包含”的規則數少于預先定義的某個定值為止，不再進行切割，該結點為葉子結點。每當有報文達到時，對決策樹進行遍歷，找到葉子結點，由于葉子結點中的規則數較少，可以進行線性搜索，找到最佳匹配規則。Hi－Cuts算法的主要缺點是由于對搜索空間進行了切割，帶來了規則的復制，增加了存儲空間。HyperCuts算法是Hi－Cuts的改進版本，HiCuts是通過局部優化的方法在每個結點選擇哪一維和 “切割”多少份來建立決策樹，而Hyper－Cuts算法允許每一步選擇多個維度進行 “切割”，其結果是樹的寬度變大，深度減少。例如對表1中前5個規則所建立的決策樹如圖1所示 （只選擇源／目的端口），可以看到對規則集端口域采用HyperCuts算法 “切割”后，決策樹的深度從3變成2了。

圖1 HiCuts與HyperCuts算法建立決策樹的例子。（（a）X軸與Y軸分別表示表1中規則R1至R5所代表的源端口域與目的端口域，（b）（c）圓矩形框表示樹的內部結點，長方形框表示樹的葉子結點）

現在，這幾類算法都能在FPGA中實現，文獻 ［6］是基于分割算法在FPGA中的實現，為了避免分割的子集過多，該文獻對Independent Sets algorithm進行改進，提出了coarse－grained獨立集合算法，該算法把原始規則集劃分為若干個coarse－grained獨立集合，進行并行搜索，剩下的規則建立cross－producting表進行查詢。由于對獨立集合算法進行了改進，可以在coarse－grained中存放更多的規則，這樣規則子集數就減少了，在Xilinx Virtex－5FPGA上實現結果表明，在消耗較少片內資源情況下，在單個FPGA芯片中能夠存儲10K的實時規則，在最小報文長度為40字節時，可以維持80Gbps的吞吐量。

文獻 ［7］把基于分割算法與決策樹算法結合起來，即先把規則集分割成若干個子集，再對各個子集分別建立決策樹，當報文達到時，可以對各個決策樹進行并行搜索。為了使對規則的劃分達到最優，作者采用范圍到點轉換（range－point conversion）的思想，也就是F維空間中的一個超矩形能夠在2F空間中轉換成一個點。從計算幾何的角度來看，每個D維分類規則可以看作是D維空間中的一個超矩形，也就是2D空間中的一個點，再用組合優化的方法把這些 “點”劃分成不同的集合，為了使劃分達到近似最優，使用模擬退伙的方法，在各個集合之間進行相應的規則調整。當近似優化劃分完成后，對每個子集用Hyper－Split［8］算法分別建立決策樹，再把每棵決策樹映射到專有的流水線上，由于這個設計消耗的資源較少，多個這樣的機制能夠在單個FPGA中實現，達到更高的吞吐量。

3 改進的HyperCuts算法在FPGA中的實現

雖然HyperCuts算法對HiCuts有很多改進，但是在建立決策樹時，雖然能減少樹的深度，但并沒有消除規則復制，從圖2中我們可以看到，在兩棵決策樹中，規則R1、R2和R4都得復制到它們多個孩子結點中。通過觀察可以發現，規則復制有兩個來源，一是不同的規則之間相互重疊，上例中R1與R3、R5都重疊，無論怎么切割，R1都要復制到包含R3與R5的結點中去；二是在每個維度上進行均勻切割，如R2與R4都要復制一次，雖然它們沒有與任何規則相重疊。需要說明的是第二點對用前綴表示的IP地址來說并不存在，因為IP地址查找是從最高有效位到最低有效位，等同于均勻切割。針對上面的問題，我們提出了兩個優化的方法 （圖2），一是把需要復制到多個孩子結點的規則，存儲到附加在內部結點的一條鏈中，這個鏈叫做內部規則鏈，例如上面的R1，就可以把它選出來放在附加在根結點中的規則鏈中；第二種方法叫做精確范圍切割，當我們對端口域進行切割時，選擇能導致最小復制的切割點，如圖2所示，重新選擇切割點后，R2與R4就不用復制了。

圖2 改進后的切割方法

3.1 決策樹的建立

結合上面兩種優化思想，用以下步驟來建立決策樹，首先，從根結點開始，根結點 “包含”了規則集中的所有規則，對決策樹結點進行遞歸地切割，直到葉子，葉子結點 “包含”規則小于等于預先定義的參數binth。在每個內部結點，需要計算出對哪些維進行切割，每一維切割多少份，規則切割次數的上限為64，所以每個內部結點有2、4、8、16、32或64個孩子。對于端口域需要尋找精確的切割點，而不是切割多少份，可以限定端口域最大的切割數為2。因此沒有對協議域進行切割，因為在實時規則集中，前四維就可以滿足分類要求了。當選擇哪些維進行切割和在源、目的IP地址上切割多少份時，標準與HiCuts和Hyper－Cuts算法一樣，不同之處在于，當選擇端口域進行切割時，選擇的切割點能導致最少規則復制；當切割方法決定下來后，把在當前結點中復制次數最多的規則挑選出來，加到當前結點的內部規則鏈中，直到鏈中規則數達到上界binth為止。按上述方法對表1建立的決策樹如圖3所示。

圖3 對表1中規則所建立決策樹（SA／DA表示源／目的IP地址，DP表示源端口號，圓括號中的數字表示對端口號的切割點）

3.2 決策樹映射到流水線

為了把決策樹映射到流水線去，流水線每一階段需要的存儲大小都需要在FPGA實現之前確定，一般采用的方法是，把決策樹相同層次上的結點映射到單獨的階段中去，由于存儲分布在每個階段變化很大，如果在每個階段分配最大的存儲量，將造成浪費。可以考慮把決策樹映射到線性流水線中去，達到在每個階段平衡存儲分布的目的，同時還可以維持每個時鐘周期處理一個報文的吞吐量。由于在這種體系中存在著兩種流水線組織，因此，不僅在樹流水線中，而且也要規則流水線中考慮各個階段的存儲分布情況，規則流水線中每個階段需要的存儲量取決于樹的結點數，所以樹到流水線映射的方式中，既要平衡存儲分配情況，也要平衡各個階段的結點分布情況。在把決策樹映射到線性流水線的過程中，可以考慮把同一層的結點映射到流水線的不同階段上去，這就為樹結點映射提供了更多的靈活性，這樣在每個階段中能平衡存儲和結點分布，需要的一個約束是，如果在決策樹中結點A是結點B的祖先，則A映射到的階段要先于B的映射。其具體映射模式如圖4所示。

3.3 搜索過程

圖4 決策樹的流水線映射

當報文達到樹流水線的某個階段進行存儲訪問時，它同時也得到了與當前樹結點相聯系的規則鏈指針，報文利用這個指針與該規則鏈中的所有規則進行匹配，由于FP－GA提供了足夠的字寬，每條規則作為一個字存儲在規則流水線的某個階段上。在規則流水線的某個階段上，報文利用指針找到一個規則，并用報文頭部與該規則進行比較，對不同的域，可采用不同的比較方法，如范圍、前綴、定值比較。當它在當前規則流水線階段找到匹配的規則后，遍歷過程并沒有結束，它需要記下當前規則優先級，以便與下一個匹配規則相比較。

3.4 規則更新

當有規則需要添加或刪除時，也就是規則更新，一般采用增量更新的方法，這種方法消耗存儲空間較少，但是頻繁的添加與刪除操作將導致決策樹的不穩定，最終得對決策樹進行重建。這里用文獻 ［9］中的write－bubbles方法，即通過插入write－bubbles到各自的流水線上，可以在硬件中實現即時更新 （即在更新過程中，分類操作并沒有停止）。然而，大規模的改變數據結構需要更有效方法，即緩存備份，這個方法需要建立額外的流水線來存放需要更新的數據，當這個流水線準備好了以后，與需要更新的流水線進行交換，這種方法犧牲了FPGA中的邏輯與RAM，但是帶來了更有效的即時更新。

4 實驗結果

實驗所用分類規則是訪問控制鏈規則 （acl＿num），規則 個 數 從 100 到 50000， 可 以 從 網 站：http：／／www.arl.wustl.edu／～hs1／PClassEval.html中 下 載 得 到。例如，acl＿10K表示是由classbench［10］在acl種子文件下產生的10000條件規則，實驗中用到了num數為100、1K、5K、10K的4種規則集。由于這個算法主要是在Hyper－Cuts算法中做了相應的改進，所以對這兩種算法在兩個參數上進行了比較，一是每個規則消耗的存儲大小，主要用來說明算法的可擴展性；二是決策樹的高度，用來指出樹流水線的階段數。比較結果見表2，從表中可以看到，隨著規則數的增加，每個規則所需要的存儲空間基本上保持不變，這說明了整個存儲空間需求與存儲規則數呈線性增長關系，易于擴展；同時，由于優化了切割方法，決策樹的深度也降低了，減少了報文遍歷決策樹的延遲。

表2 不同規則集下算法性能比較

FPGA器件采用當前比較先進的Xilinx Virtex－6，型號是XC6VSX475T，它包含7640Kb分布式RAM和38304Kb的塊RAM，時鐘頻率可達到115.4MHZ，其資源消耗見表3，兩種算法實現結果見表4，其中效率這一項表示為吞吐量除以每個規則消耗的存儲空間，主要用來說明時間與空間的平衡度問題。

表3 FPGA資源消耗情況 （acl＿10K）

表4 實驗結果對比

5 結束語

隨著網絡帶寬的快速發展，線速多維報文分類問題成為了設計下一代網絡處理設備的主要挑戰，傳統的軟件算法已經無法滿足需要。本文針對HyperCuts算法中規則復制的兩個來源進行了相應改進，解決了該算法存儲需求過多的缺點，基于FPGA的實驗結果表明，改進后的算法能夠在單個芯片上能夠支持10K的規則，同時在報文長度為40字節的情況下能維持100Gbps的吞吐量。

［1］TIAN Le.Research on storage and power efficiency packet classification algorithm based on TCAM ［D］.Zhengzhou：Information Engineering University，2013 （in Chinese）.［田樂.面向存儲和功耗優化的TCAM報文分類算法研究 ［D］.鄭州：信息工程大學，2013.］

［2］Ahmed O，Areibi S，Grewal G.Hardware accelerators targeting a novel group based packet classification algorithm ［J］.International Journal of Reconfigurable Computing，2013：1－30.

［3］Ahmed O，Chattha K，Areibi S，et al.PCIU：Hardware implementation of an efficient packet classification algorithm with incremental update capability ［J］.Intl Journal of Reconfigurable Computing，2011：1－21.

［4］Jiang W，Prasanna V K.Scalable packet classi＿cation on FPGA ［J］.IEEE Trans VLSI Syst，2012，20 （9）：1668－1680.

［5］QI Yahuan，LI Jun.The theory of high performance packet classification and algorithm summarizing ［J］.Journal of Computer，2013，36 （2）：408－421 （in Chinese）. ［亓亞烜，李軍.高性能網包分類理論與算法綜述 ［J］.計算機學報，2013，36 （2）：408－421.］

［6］Jiang W，Prasanna V K.A FPGA－based parallel architecture for scalable high－speed packet classification ［C］／／20th IEEE International Conference on Application－specific Systems，Architectures and Processors.IEEE，2009：24－31.

［7］Fong J，Wang X，Qi Y，et al.ParaSplit：A scalable architecture on FPGA for terabit packet classification ［C］／／IEEE 20th Annual Symposium on High－Performance Interconnects.IEEE，2012：1－8.

［8］Qi Y，Xu L，Yang B，et al.Packet classification algorithms：From theory to practice ［C］／／INFOCOM IEEE，2009：648－656.

［9］Qu Y R，Zhou S，Prasanna V K.High－performance architecture for dynamically updatable packet classification on FPGA［C］／／Proceedings of the Ninth ACM／IEEE Symposium on Architectures for Networking and Communications Systems.IEEE Press，2013：125－136.

［10］Taylor D E，Turner J S.Classbench：A packet classification benchmark ［J］.IEEE／ACM Trans Netw，2007，15 （3）：499－511.