王 敏，邰 銘

（1.信息工程大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院，河南 鄭州450001；2.信息工程大學(xué)數(shù)學(xué)工程與先進(jìn)計算國家重點(diǎn)實(shí)驗(yàn)室，河南 鄭州450001）

0 引 言

隨著快速增長的網(wǎng)絡(luò)鏈路速率與分類規(guī)則的增多，多維報文分類問題成為設(shè)計高速路由器的一個基本挑戰(zhàn)。例如，當(dāng)主干網(wǎng)鏈路速率達(dá)到80Gbps時，在報文長度為40字節(jié)時，需要每4ns內(nèi)處理一個數(shù)據(jù)報，這個速度用現(xiàn)在的軟件算法不可能實(shí)現(xiàn)。

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

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

1.1 分類算法的定義

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

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

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

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

1.2 分類算法的評估方法

由于IP分類問題可以抽象成一個查找表項(xiàng)巨大的多關(guān)鍵字查找問題，因此衡量一個算法好壞的關(guān)鍵是查詢速度快，再就是用分類規(guī)則來構(gòu)建查找表數(shù)據(jù)結(jié)構(gòu)時所占內(nèi)存要少?？紤]到分類算法自身的特點(diǎn)，其它評估方法還有過濾規(guī)則的插入與刪除速度快，維數(shù) （查找中關(guān)鍵字個數(shù)）易擴(kuò)展以及能夠根據(jù)規(guī)則中各個域的不同表現(xiàn)形式，支持多種查詢 （匹配）方式等?？偟膩碚f，算法的關(guān)鍵是怎么找到時間與空間的平衡點(diǎn)。

2 現(xiàn)有的分類算法

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

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

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

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

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

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

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

3 改進(jìn)的HyperCuts算法在FPGA中的實(shí)現(xiàn)

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

圖2 改進(jìn)后的切割方法

3.1 決策樹的建立

結(jié)合上面兩種優(yōu)化思想，用以下步驟來建立決策樹，首先，從根結(jié)點(diǎn)開始，根結(jié)點(diǎn) “包含”了規(guī)則集中的所有規(guī)則，對決策樹結(jié)點(diǎn)進(jìn)行遞歸地切割，直到葉子，葉子結(jié)點(diǎn) “包含”規(guī)則小于等于預(yù)先定義的參數(shù)binth。在每個內(nèi)部結(jié)點(diǎn)，需要計算出對哪些維進(jìn)行切割，每一維切割多少份，規(guī)則切割次數(shù)的上限為64，所以每個內(nèi)部結(jié)點(diǎn)有2、4、8、16、32或64個孩子。對于端口域需要尋找精確的切割點(diǎn)，而不是切割多少份，可以限定端口域最大的切割數(shù)為2。因此沒有對協(xié)議域進(jìn)行切割，因?yàn)樵趯?shí)時規(guī)則集中，前四維就可以滿足分類要求了。當(dāng)選擇哪些維進(jìn)行切割和在源、目的IP地址上切割多少份時，標(biāo)準(zhǔn)與HiCuts和Hyper－Cuts算法一樣，不同之處在于，當(dāng)選擇端口域進(jìn)行切割時，選擇的切割點(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為止。按上述方法對表1建立的決策樹如圖3所示。

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

3.2 決策樹映射到流水線

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

3.3 搜索過程

圖4 決策樹的流水線映射

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

3.4 規(guī)則更新

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

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

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

表2 不同規(guī)則集下算法性能比較

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

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

表4 實(shí)驗(yàn)結(jié)果對比

5 結(jié)束語

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

［1］TIAN Le.Research on storage and power efficiency packet classification algorithm based on TCAM ［D］.Zhengzhou：Information Engineering University，2013 （in Chinese）.［田樂.面向存儲和功耗優(yōu)化的TCAM報文分類算法研究 ［D］.鄭州：信息工程大學(xué)，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）. ［亓亞烜，李軍.高性能網(wǎng)包分類理論與算法綜述 ［J］.計算機(jī)學(xué)報，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.