基于FPGA的報(bào)文分類技術(shù)

王 敏，邰 銘

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

0 引 言

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

1 分類算法的定義及評(píng)估方法

1.1 分類算法的定義

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

對(duì)具有N條過(guò)濾規(guī)則的分類器R來(lái)說(shuō)，為了解決同一個(gè)報(bào)文與分類器R中多條規(guī)則相匹配的問(wèn)題，在定義過(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)單分類器見表1。

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

也可以從計(jì)算機(jī)幾何中的點(diǎn)定位問(wèn)題來(lái)看待多維報(bào)文分類問(wèn)題，一個(gè)D維的分類規(guī)則相當(dāng)于D維空間中的一個(gè)超矩形，D維空間中的N個(gè)規(guī)則至多可構(gòu)成 （2N－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－1N）的情況下，空間復(fù)雜度為O（N）。從上面的分析可以看到，多維報(bào)文分類問(wèn)題是一個(gè)非常復(fù)雜的問(wèn)題，幸運(yùn)的是，現(xiàn)實(shí)情況要比這好，真實(shí)的分類器沒(méi)這么復(fù)雜，它們有一些自身特點(diǎn)，我們可以在實(shí)際中加以利用，可以使分類算法得到簡(jiǎn)化。

1.2 分類算法的評(píng)估方法

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

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

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

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

基于分割算法的主要思想是把原來(lái)的規(guī)則集劃分為若干個(gè)子集，每個(gè)子集中的規(guī)則在單個(gè)或多個(gè)域之間是沒(méi)有重疊的，獨(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ò)規(guī)則集劃分后，空間復(fù)雜度減少為原來(lái)的1／KD－1。算法面臨的主要挑戰(zhàn)是獨(dú)立規(guī)則集劃分個(gè)數(shù)的不確定性和過(guò)多。

決策樹類的代表算法是HiCuts，它通過(guò)對(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)行了切割，帶來(lái)了規(guī)則的復(fù)制，增加了存儲(chǔ)空間。HyperCuts算法是Hi－Cuts的改進(jìn)版本，HiCuts是通過(guò)局部?jī)?yōu)化的方法在每個(gè)結(jié)點(diǎn)選擇哪一維和 “切割”多少份來(lái)建立決策樹，而Hyper－Cuts算法允許每一步選擇多個(gè)維度進(jìn)行 “切割”，其結(jié)果是樹的寬度變大，深度減少。例如對(duì)表1中前5個(gè)規(guī)則所建立的決策樹如圖1所示 （只選擇源／目的端口），可以看到對(duì)規(guī)則集端口域采用HyperCuts算法 “切割”后，決策樹的深度從3變成2了。

圖1 HiCuts與HyperCuts算法建立決策樹的例子。（（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) ［6］是基于分割算法在FPGA中的實(shí)現(xiàn)，為了避免分割的子集過(guò)多，該文獻(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) ［7］把基于分割算法與決策樹算法結(jié)合起來(lái)，即先把規(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ì)算幾何的角度來(lái)看，每個(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［8］算法分別建立決策樹，再把每棵決策樹映射到專有的流水線上，由于這個(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í)，雖然能減少樹的深度，但并沒(méi)有消除規(guī)則復(fù)制，從圖2中我們可以看到，在兩棵決策樹中，規(guī)則R1、R2和R4都得復(fù)制到它們多個(gè)孩子結(jié)點(diǎn)中。通過(guò)觀察可以發(fā)現(xiàn)，規(guī)則復(fù)制有兩個(gè)來(lái)源，一是不同的規(guī)則之間相互重疊，上例中R1與R3、R5都重疊，無(wú)論怎么切割，R1都要復(fù)制到包含R3與R5的結(jié)點(diǎn)中去；二是在每個(gè)維度上進(jìn)行均勻切割，如R2與R4都要復(fù)制一次，雖然它們沒(méi)有與任何規(guī)則相重疊。需要說(shuō)明的是第二點(diǎn)對(duì)用前綴表示的IP地址來(lái)說(shuō)并不存在，因?yàn)镮P地址查找是從最高有效位到最低有效位，等同于均勻切割。針對(duì)上面的問(wèn)題，我們提出了兩個(gè)優(yōu)化的方法 （圖2），一是把需要復(fù)制到多個(gè)孩子結(jié)點(diǎn)的規(guī)則，存儲(chǔ)到附加在內(nèi)部結(jié)點(diǎn)的一條鏈中，這個(gè)鏈叫做內(nèi)部規(guī)則鏈，例如上面的R1，就可以把它選出來(lái)放在附加在根結(jié)點(diǎn)中的規(guī)則鏈中；第二種方法叫做精確范圍切割，當(dāng)我們對(duì)端口域進(jìn)行切割時(shí)，選擇能導(dǎo)致最小復(fù)制的切割點(diǎn)，如圖2所示，重新選擇切割點(diǎn)后，R2與R4就不用復(fù)制了。

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

3.1 決策樹的建立

結(jié)合上面兩種優(yōu)化思想，用以下步驟來(lái)建立決策樹，首先，從根結(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。因此沒(méi)有對(duì)協(xié)議域進(jìn)行切割，因?yàn)樵趯?shí)時(shí)規(guī)則集中，前四維就可以滿足分類要求了。當(dāng)選擇哪些維進(jìn)行切割和在源、目的IP地址上切割多少份時(shí)，標(biāo)準(zhǔn)與HiCuts和Hyper－Cuts算法一樣，不同之處在于，當(dāng)選擇端口域進(jìn)行切割時(shí)，選擇的切割點(diǎn)能導(dǎo)致最少規(guī)則復(fù)制；當(dāng)切割方法決定下來(lái)后，把在當(dāng)前結(jié)點(diǎn)中復(fù)制次數(shù)最多的規(guī)則挑選出來(lái)，加到當(dāng)前結(jié)點(diǎn)的內(nèi)部規(guī)則鏈中，直到鏈中規(guī)則數(shù)達(dá)到上界binth為止。按上述方法對(duì)表1建立的決策樹如圖3所示。

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

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)文的吞吐量。由于在這種體系中存在著兩種流水線組織，因此，不僅在樹流水線中，而且也要規(guī)則流水線中考慮各個(gè)階段的存儲(chǔ)分布情況，規(guī)則流水線中每個(gè)階段需要的存儲(chǔ)量取決于樹的結(jié)點(diǎn)數(shù)，所以樹到流水線映射的方式中，既要平衡存儲(chǔ)分配情況，也要平衡各個(gè)階段的結(jié)點(diǎn)分布情況。在把決策樹映射到線性流水線的過(guò)程中，可以考慮把同一層的結(jié)點(diǎn)映射到流水線的不同階段上去，這就為樹結(jié)點(diǎn)映射提供了更多的靈活性，這樣在每個(gè)階段中能平衡存儲(chǔ)和結(jié)點(diǎn)分布，需要的一個(gè)約束是，如果在決策樹中結(jié)點(diǎn)A是結(jié)點(diǎn)B的祖先，則A映射到的階段要先于B的映射。其具體映射模式如圖4所示。

3.3 搜索過(guò)程

圖4 決策樹的流水線映射

當(dāng)報(bào)文達(dá)到樹流水線的某個(gè)階段進(jìn)行存儲(chǔ)訪問(wèn)時(shí)，它同時(shí)也得到了與當(dāng)前樹結(jié)點(diǎn)相聯(lián)系的規(guī)則鏈指針，報(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ī)則后，遍歷過(guò)程并沒(méi)有結(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)行重建。這里用文獻(xiàn) ［9］中的write－bubbles方法，即通過(guò)插入write－bubbles到各自的流水線上，可以在硬件中實(shí)現(xiàn)即時(shí)更新 （即在更新過(guò)程中，分類操作并沒(méi)有停止）。然而，大規(guī)模的改變數(shù)據(jù)結(jié)構(gòu)需要更有效方法，即緩存?zhèn)浞荩@個(gè)方法需要建立額外的流水線來(lái)存放需要更新的數(shù)據(jù)，當(dāng)這個(gè)流水線準(zhǔn)備好了以后，與需要更新的流水線進(jìn)行交換，這種方法犧牲了FPGA中的邏輯與RAM，但是帶來(lái)了更有效的即時(shí)更新。

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

實(shí)驗(yàn)所用分類規(guī)則是訪問(wèn)控制鏈規(guī)則 （acl＿num），規(guī)則 個(gè) 數(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ī)則集。由于這個(gè)算法主要是在Hyper－Cuts算法中做了相應(yīng)的改進(jìn)，所以對(duì)這兩種算法在兩個(gè)參數(shù)上進(jìn)行了比較，一是每個(gè)規(guī)則消耗的存儲(chǔ)大小，主要用來(lái)說(shuō)明算法的可擴(kuò)展性；二是決策樹的高度，用來(lái)指出樹流水線的階段數(shù)。比較結(jié)果見表2，從表中可以看到，隨著規(guī)則數(shù)的增加，每個(gè)規(guī)則所需要的存儲(chǔ)空間基本上保持不變，這說(shuō)明了整個(gè)存儲(chǔ)空間需求與存儲(chǔ)規(guī)則數(shù)呈線性增長(zhǎng)關(guān)系，易于擴(kuò)展；同時(shí)，由于優(yōu)化了切割方法，決策樹的深度也降低了，減少了報(bào)文遍歷決策樹的延遲。

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

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

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

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

5 結(jié)束語(yǔ)

隨著網(wǎng)絡(luò)帶寬的快速發(fā)展，線速多維報(bào)文分類問(wèn)題成為了設(shè)計(jì)下一代網(wǎng)絡(luò)處理設(shè)備的主要挑戰(zhàn)，傳統(tǒng)的軟件算法已經(jīng)無(wú)法滿足需要。本文針對(duì)HyperCuts算法中規(guī)則復(fù)制的兩個(gè)來(lái)源進(jìn)行了相應(yīng)改進(jìn)，解決了該算法存儲(chǔ)需求過(guò)多的缺點(diǎn)，基于FPGA的實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法能夠在單個(gè)芯片上能夠支持10K的規(guī)則，同時(shí)在報(bào)文長(zhǎng)度為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）.［田樂(lè).面向存儲(chǔ)和功耗優(yōu)化的TCAM報(bào)文分類算法研究 ［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ì)算機(jī)學(xué)報(bào)，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.