張杰鑫，張 錚

（數(shù)學(xué)工程與先進(jìn)計算國家重點實驗室，鄭州450001）

1 概述

隨著密集型光波復(fù)用技術(shù)和光纖技術(shù)的發(fā)展，鏈路的速率已經(jīng)能夠滿足網(wǎng)絡(luò)數(shù)據(jù)的持續(xù)增長。路由器是十分重要的網(wǎng)絡(luò)設(shè)備，它對每一個數(shù)據(jù)包要進(jìn)行很多種操作，包括復(fù)雜的分類操作，因此，網(wǎng)絡(luò)的整體速度越來越受到路由器的處理速度的制約。隨著計算機(jī)網(wǎng)絡(luò)的飛速發(fā)展，傳統(tǒng)網(wǎng)絡(luò)盡力而為的服務(wù)模式已經(jīng)不能滿足用戶的需求?；ヂ?lián)網(wǎng)服務(wù)提供商（Internet Service Provider，ISP）希望網(wǎng)絡(luò)能夠提供更好的服務(wù)，特別是對新型業(yè)務(wù)流的檢測與控制有著強(qiáng)烈需求。網(wǎng)絡(luò)流量異?；蛘邅G包，甚至整個網(wǎng)絡(luò)的癱瘓，嚴(yán)重影響正常業(yè)務(wù)流量運行，也嚴(yán)重威脅系統(tǒng)和網(wǎng)絡(luò)安全，對互聯(lián)網(wǎng)和個人安全造成了威脅［1－2］。因此，通過有效的包分類技術(shù)，檢測和控制網(wǎng)絡(luò)中新型流量，提供不同的服務(wù)質(zhì)量保障，是當(dāng)前網(wǎng)絡(luò)運營面臨的主要挑戰(zhàn)之一［3－4］。研究有效的包分類算法及其實現(xiàn)技術(shù)是目前網(wǎng)絡(luò)技術(shù)領(lǐng)域的熱門課題［5－6］。本文通過比較基于軟件和基于硬件包分類算法，分析了不同算法設(shè)計的難點和不足。

2 包分類

2．1 包分類的概念

用一定的分類匹配規(guī)則，對數(shù)據(jù)包進(jìn)行處理的算法，稱為包分類技術(shù)。這些規(guī)則一般為數(shù)據(jù)包首部的某個字段或某些字段的組合。首先對數(shù)據(jù)包進(jìn)行協(xié)議解析和字段抽取操作，然后依據(jù)協(xié)議類型和分類字段對數(shù)據(jù)包進(jìn)行分類。目前，大多采用五元組，或者五元組的各種組合來對數(shù)據(jù)包進(jìn)行分類，五元組包括目的地址IP（32bit）、源地址IP（32bit）、目的端口號（16bit）、源端口號（16bit）、和協(xié)議類型（8bit）。

圖1是一個典型的基于IPV4的五維包分類系統(tǒng)的示意圖，其中，寬箭頭代表數(shù)據(jù)包的處理流程；細(xì)箭頭代表規(guī)則集的應(yīng)用場景。表1則描述了包分類系統(tǒng)存儲的規(guī)則。首先系統(tǒng)根據(jù)輸入包的五元組信息與規(guī)則進(jìn)行匹配，然后系統(tǒng)再依據(jù)匹配規(guī)則的決策對輸入包進(jìn)行相應(yīng)的處理，如轉(zhuǎn)發(fā)、拒絕和丟棄等。

圖1 包分類系統(tǒng)

表1 包分類規(guī)則示例

包分類規(guī)則的表示方式有2種，一種是前綴表示方式，如表1中的表示方式（其中，“＊”是通配符），另一種是范圍表示方式。前綴表示方式容易被硬件接受，而且具有特殊的性質(zhì)，如2個前綴僅有包含和不相交關(guān)系，但并不是所有IP段都能用一個前綴表示；范圍表示方式雖然可以表示所有的IP段，但是難以被硬件實現(xiàn)［7］。

2．2 規(guī)則集特征概述和管理

文獻(xiàn)［8］對大量實際的規(guī)則集進(jìn)行了研究，結(jié)果表明，實際規(guī)則集的規(guī)則數(shù)目不會太多，規(guī)則的協(xié)議域通常只有很少的幾個取值，端口號的取值范圍很廣等特征。實際統(tǒng)計結(jié)果是所有規(guī)則集的實際復(fù)雜度均遠(yuǎn)小于理論復(fù)雜度［9］。

通常采用通過簡單的單向隊列操作、集中管理的方式和分布式的并行方式對規(guī)則集進(jìn)行管理。

2．3 包分類算法評價指標(biāo)

包分類算法評價指標(biāo)如下：

（1）時間復(fù)雜度：該指標(biāo)用于定義在執(zhí)行分類操作時，所需要的步驟數(shù)或者循環(huán)數(shù)的最大邊界O（f）。f是一個以規(guī)則數(shù)目N，維度d和字段寬度W為自變量的函數(shù)。

（2）空間復(fù)雜度：該指標(biāo)用于定義在執(zhí)行包分類操作時，用于保存分類器和相關(guān)數(shù)據(jù)結(jié)構(gòu)所需要存儲空間的最大邊界O（f）。此指標(biāo)不僅包括存儲規(guī)則集本身所占用的內(nèi)存空間，還包括為實現(xiàn)快速查找所建立的數(shù)據(jù)結(jié)構(gòu)，以及在查找計算過程中動態(tài)分配的空間［10－11］。

（3）更新復(fù)雜度：該指標(biāo)用于定義對分類器進(jìn)行更新規(guī)則集之后，修改數(shù)據(jù)結(jié)構(gòu)所需要的步驟數(shù)或者循環(huán)數(shù)的最大邊界O（f）。

（4）可擴(kuò)展性：可擴(kuò)展性不僅包括在縱向上對分類的規(guī)則數(shù)目上具有可擴(kuò)展性，在橫向上對分類的維數(shù)具有可擴(kuò)展性，而且包括在分類的層次上還應(yīng)具有可擴(kuò)展性。

（5）最壞情況下的性能：不能只在平均情況下討論一個算法的好壞，還應(yīng)該在最壞情況下分析它的性能。因為有時候平均性能不能完整地反映分類算法的性能，極端情況下算法的性能對于綜合評價算法是十分必要的。

3 基于軟件的包分類算法

3．1 Grid－of－Tries算法

Grid－of－Tries算法［12］是基于決策樹算法的包分類算法，主要解決涉及目的地址和源地址前綴的包分類問題。該算法在有向非循環(huán)圖的基礎(chǔ)上做了改進(jìn)。雖然其可以消除多余子樹，但是它沒有徹底解決規(guī)則的復(fù)制問題。算法使用了一種有效消除規(guī)則復(fù)制的算法，主要思想是把一條規(guī)則僅存儲在一個結(jié)點中，再用轉(zhuǎn)移指針指向潛在匹配的規(guī)則或者規(guī)則子集，圖2展示了依據(jù)表1的算法示意圖，虛線指針為目的地址樹到源地址樹的指針，密集虛線指針為轉(zhuǎn)移指針。

圖2 Grid－of－Tries算法示意圖

假設(shè)N是規(guī)則數(shù)目，W是目的地址或源地址的位寬，那么Grid－of－Tries算法的空間復(fù)雜度為O（NW），時間復(fù)雜度為O（W）。雖然Grid－of－Tries算法是地址前綴分類的有效技術(shù)，但是它不能延伸到規(guī)則的其他字段。

3．2 EGT算法

擴(kuò) 展 的 樹 型 網(wǎng) 格 （Extended Grid－of－Tries，EGT）算法［13］在 Grid－of－Tries算法的基礎(chǔ)上進(jìn)行了改進(jìn)，通過改變Grid－of－Tries算法的數(shù)據(jù)結(jié)構(gòu)，使得該算法能夠支持多字段查找。EGT算法將Grid－of－Tries算法的轉(zhuǎn)移指針改為跳轉(zhuǎn)指針，跳轉(zhuǎn)指針直接指向所有可能匹配的規(guī)則，而不是Grid－of－Tries算法中的最長前綴匹配規(guī)則。源地址樹的結(jié)點指一個規(guī)則列表，列表由若干規(guī)則組成，規(guī)則包含了除地址域外的其他字段。在列表中進(jìn)行線性查找進(jìn)而找到最佳匹配。需要注意的是在源地址樹中跳轉(zhuǎn)指針直接指向所有可能的規(guī)則集。

圖3展示了依據(jù)表1的算法示意圖，密集虛線指針為跳轉(zhuǎn)指針，虛線為源地址樹的跳轉(zhuǎn)指針，虛線指針為目的地址樹到源地址樹的指針。EGT算法的時空復(fù)雜度與Grid－of－Tries算法相同，最壞情況下訪存次數(shù)是O（W2），其中，W是地址位寬。

圖3 EGT算法示意圖

3．3 HiCuts算法

HiCuts算法［10］采用了切割的算法，從幾何角度解決包分類問題，該算法適合應(yīng)用于范圍類型的規(guī)則。HiCuts算法使用決策樹作為數(shù)據(jù)結(jié)構(gòu)進(jìn)行快速搜索。決策樹的內(nèi)部結(jié)點存儲的不是規(guī)則，而是適當(dāng)?shù)姆诸悓?dǎo)向信息。決策樹的外部結(jié)點（葉結(jié)點）包含一個相對較小的規(guī)則子集。一旦輸入包到來，HiCuts算法將貫穿決策樹，直到一個葉結(jié)點。然后在這個規(guī)則子集中通過線性查找來找到最佳匹配。在構(gòu)造決策樹時，需要對葉結(jié)點內(nèi)所存儲的規(guī)則數(shù)目進(jìn)行限制，使其不超過一個常數(shù)——binth（即in－threshold）。

圖4以表2的源地址（4bit）和目的地址（4bit）為例，當(dāng)binth＝3時的HiCuts算法示意圖，不同顏色的區(qū)域代表不同規(guī)則的在空間中所占的區(qū)域，R1～R9是表2中的9條規(guī)則。

圖4 HiCuts算法示意圖

表2 源地址和目的地址對應(yīng)關(guān)系

HiCuts算法結(jié)合了線性查找算法與決策樹算法，使得該算法不但具有較好的性能，而且具有也比較高的靈活性。當(dāng)binth＝N時，算法將會退化為線性查找。當(dāng)分類維度為d，規(guī)則數(shù)為N時，算法的時間復(fù)雜度為O（d），空間復(fù)雜度為O（Nd）。

3．4 Parallel BV 算 法

并行位向量（Parallel Bit－Vector）算法［11］假設(shè)所有規(guī)則已經(jīng)按照優(yōu)先級排序。假設(shè)有N條規(guī)則，對于規(guī)則的每一維最多可以劃分出2N＋1個基本間隔，如圖5所示。每一維的各個基本間隔都對應(yīng)一個N位的位向量，向量的每一位對應(yīng)一條規(guī)則。

圖5 基本間隔原理

在初始化位向量時，首先將其所有位均被置為“0”，然后將該向量中那些與該基本間隔重合的規(guī)則所對應(yīng)的位全部置為“1”。一旦計算出全部位向量和d個數(shù)據(jù)結(jié)構(gòu)，那么查找也變得簡單。在查找時，因為每一維都有一個數(shù)據(jù)結(jié)構(gòu)，所以可以獨立進(jìn)行對各維的查找。首先在各維中找到一個位向量，待查找完畢，則一共找到d個位向量。然后，對d個位向量執(zhí)行“與”操作，進(jìn)而得到了一個最終的位向量。在此位向量中，所有位為“1”的位所對應(yīng)的規(guī)則都是匹配規(guī)則，而最佳匹配規(guī)則是與其中最高一個“1”位對應(yīng)的規(guī)則。

該算法的時間復(fù)雜度為O（lbN），空間復(fù)雜度為O（N2）。該算法也適合于硬件實現(xiàn)。假設(shè)內(nèi)存接口寬度為W，那么訪問一個N位向量需要次訪存。

3．5 RFC算法

真實規(guī)則集包含了大量的結(jié)構(gòu)和冗余，迭代流分類（Recursive Flow Classification，RFC）算法［14］很好解決了這一問題。RFC算法的基本思想是使用多階段映射的算法，通過這種算法將一個較大的集合映射成多個較小的集合。RFC的映射是一個遞歸過程，通過映射實現(xiàn)包頭中S比特串?dāng)?shù)據(jù)到T（T＜＜S）位eqID的映射（每個階段映射稱為縮減）。RFC算法包含Q個階段，每一個階段又包含一系列的并行查找。為了方便查找，RFC算法定義了合并表（Aggreation Table）和段表（Chunk Table）。算法又利用Index在2個表中查找，該Index就是前一階段查找得到的eqID。經(jīng)過多個階段查找，得到一個最終的eqID，并由此eqID指明對輸入包的決策動作。RFC算法執(zhí)行過程如圖6所示。當(dāng)分類維度為d，規(guī)則數(shù)為N時，時間復(fù)雜度為O（d），空間復(fù)雜度為O（Nd）。RFC算法擁有較高的吞吐率，但其高效的查找是以內(nèi)存為代價的，因此，RFC算法面臨著內(nèi)存膨脹的危險，而且RFC算法不支持增量更新，只能重建。

圖6 RFC算法執(zhí)行過程示意圖

3．6 元組空間法

元組空間法是利用元組（Tuple）把規(guī)則集進(jìn)行分割，進(jìn)而到達(dá)快速縮短多維查找范圍的目的。基本的元組空間法是窮盡查找，文獻(xiàn)［15］提出若干利用元組空間法的查找算法。元組定義了規(guī)則的某個字段的若干位。

表3給出了一個五維規(guī)則集的例子，其中，源地址和目的地址為4bit，源端口號和目的端口號為4bit，協(xié)議為8bit，最后一列給出了元組的形式。

表3 五維規(guī)則集示例

對于所有使用了元組空間法的包分類算法，對涉及對元組空間或者其一個子集的查找是可以獨立進(jìn)行的，所以，元組空間法是能夠并行實現(xiàn)的。然而，待查找的元組空間或者它的子集的大小是無法預(yù)測的，所以，采用并行實現(xiàn)是不容易的。采用元組空間法，能夠有效地對規(guī)則集進(jìn)行壓縮，進(jìn)而到達(dá)節(jié)省存儲空間的目的。

元組空間法的時間復(fù)雜度和空間復(fù)雜度均為O（N），當(dāng)規(guī)則集中有許多通配符時，與空間復(fù)雜度為的窮盡查找相比，元組空間法更能節(jié)省存儲空間。

3．7 算法比較

表4列出線性查找（Linear Search）算法、HiCuts算法［10］、并行位向量算法［11］、Grid－of－Tries算法［12］、擴(kuò)展的樹型網(wǎng)格（Extended Grid－of－Tries）算 法［13］、迭代流分類（Recursive Flow Classification）算法［14］和元組空間（Tuple）算法［15］的時間復(fù)雜度和空間復(fù)雜度分析。假設(shè)N為規(guī)則數(shù)目，W為地址域關(guān)鍵字的長度，d為規(guī)則的維度。

表4 包分類算法性能比較

4 基于硬件的包分類算法

4．1 基于三態(tài)內(nèi)容可尋址存儲器的包分類算法

三態(tài)內(nèi)容可尋址存儲器（Ternary Content Addressable Memory，TCAM）是一種與傳統(tǒng)的內(nèi)容尋址內(nèi)存（Content Addressable Memory，CAM）不同的三態(tài)內(nèi)容查詢的存儲器。因其具有操作簡單、匹配時間固定和查詢速度快等優(yōu)點而被應(yīng)用于包分類和路由表查詢等領(lǐng)域。TCAM的每一位具有3種狀態(tài)：0，1和“＊”（通配符），正是因為它具有3種狀態(tài)的特性使其既可以進(jìn)行精確匹配，又可以進(jìn)行模糊匹配。在存儲時，TCAM是以表項作為基本的存儲單位，表項的地址越低其優(yōu)先級就越高，而且每一條表項只能被配置成固定位寬。在查詢時，TCAM將關(guān)鍵字與所有的表項進(jìn)行并行匹配，返回優(yōu)先級最高的表項的地址。

TCAM的查詢速度與表項的數(shù)目無關(guān)，其時間復(fù)雜度為O（1）。雖然TCAM具有良好的查詢性能，但它也存在不足，TCAM的價格昂貴、集成度低 、能 耗 驚 人［16－17］，更 為 重 要 的 是 ，TCAM 不 能 直接進(jìn)行非字段和范圍字段匹配，并且其每次匹配只能輸出一個結(jié)果。因此，在設(shè)計中必須考慮TCAM的成本、功耗和體積，并充分利用TCAM的每個比特［18］。

4．1．1 基于范圍匹配的TCAM算法

前綴擴(kuò)展算法［12］是傳統(tǒng)的范圍匹配算法，該算法將用范圍表示的規(guī)則轉(zhuǎn)化為一組前綴表示的形式。假設(shè)W 為范圍的位寬，則算法的最差擴(kuò)展系數(shù)為2（W－1）。對于目的端口號和源端口號而言，在最壞情況下，一條規(guī)則就需要900條TCAM表項。Taylor用前綴擴(kuò)展法對多個實際的規(guī)則集進(jìn)行轉(zhuǎn)換實驗，結(jié)果表明這種算法的平均擴(kuò)展系數(shù)為6倍多，TCAM空間利用率僅為16．12%［19］。該算法的優(yōu)點在于實現(xiàn)簡單，且更新性能優(yōu)秀，缺點是TCAM的空間利用率很低。

基于映射區(qū)間（Mapping Range，MR）算法［20］，來解決基于TCAM包分類算法中普遍存在的“區(qū)間膨脹”問題。MR算法的主要思想是對造成“區(qū)間膨脹”的源／目的端口進(jìn)行重新編碼，為每個源／目的端口分配特有的比特位進(jìn)行表示。MR算法可以完全解決區(qū)間膨脹問題，不過該算法對源／目的端口域中的范圍區(qū)間編碼效果不理想，當(dāng)范圍區(qū)間的數(shù)目增多時，其所需的編碼比特數(shù)目也將大幅增加。而且該算法的更新過程是十分復(fù)雜的，因為它需要維護(hù)整個規(guī)則集中不同范圍之間的相互關(guān)系。

由于TCAM具有三態(tài)特性，其通配符可以出現(xiàn)在掩碼的任意位置，因此范圍不僅可以轉(zhuǎn)化為前綴形式，也可以轉(zhuǎn)化為任意掩碼形式。另外，TCAM的位寬固定，規(guī)則的位寬小于表項的位寬，每一條表項會有部分剩余比特位，因此，可以利用這些剩余比特來存儲一些附加信息。動態(tài)區(qū)間編碼（Dynamic Range Encoding Scheme，DRES）算法［21］的主要思想是充分利用未使用的比特位來對區(qū)間進(jìn)行選擇性編碼，達(dá)到提高TCAM空間存儲效率的目的。這種選擇性的區(qū)間編碼方案可以有效緩解“區(qū)間膨脹”問題，同時也不會造成規(guī)則寬度大幅增加，可以達(dá)到提高TCAM空間的存儲效率的目的。但該算法未能從根本上解決區(qū)間膨脹問題，不能對編碼之后的規(guī)則位寬進(jìn)行壓縮，而且算法的更新性能不佳。

4．1．2 基于前綴匹配的TCAM算法

由于IP路由查找可以看成是一維的報文分類問題，而TCAM能夠有效存儲IP地址，因此利用TCAM可解決IP理由查找問題。最優(yōu)路由表結(jié)構(gòu)（Optimal IP Routing Tables Construction，ORTC）算法［22］是針對IP路由表的存儲優(yōu)化問題的一種空間壓縮算法，該算法可使用最少的前綴來表示所需查找的IP路由表。該算法利用二叉樹的算法，將IP地址存儲于二叉樹中，通過修改、合并、刪除二叉樹進(jìn)而使得規(guī)則在縱向上壓縮。雖然該算法支持批量更新，但其更新效果并不理想。

4．1．3 基于非匹配的TCAM算法

反向擴(kuò)展法的基本思想是為每非字段的每一個匹配位對應(yīng)一條表項。在存儲時，將非字段的某些位取反，其余位用“＊”表示，如圖7（a）所示。非規(guī)則一般被應(yīng)用于排除指定的子網(wǎng)，所以，其非字段的匹配位較多，這就造成了反向擴(kuò)展法的空間復(fù)雜度較高、更新性能較差，實際應(yīng)用中一般不采用這種算法。因為TCAM只返回優(yōu)先級最高的一條匹配結(jié)果，正向否定法［23］利用了這一特性，在存儲時，每條非規(guī)則只占用2條TCAM表項，如圖7（b）所示。首先在TCAM中存儲一條正向非字段的表項，但是其SRAM中的匹配結(jié)果為空，即若命中此表項則表示不滿足此非規(guī)則。然后在此表項的高地址上存儲一條將非字段全置為“＊”的表項，若命中此表項則表示滿足此非規(guī)則。

圖7 反向擴(kuò)展法、正向否定法示意圖

4．1．4 基于改進(jìn)硬件的TCAM算法

擴(kuò)展的三態(tài)內(nèi)容尋址存儲器（Extended TCAM，E－TCAM）算法［24］針對 TCAM 硬件空間利用率低以及能耗大的問題。E－TCAM的主要思想是改變TCAM的硬件結(jié)構(gòu)，使得硬件可以直接支持范圍匹配，從而提高空間利用率。考慮到TCAM的并行查找模式能耗極大，因此，在實現(xiàn)時，E－TCAM將整個設(shè)備分為多個可以容納數(shù)百條規(guī)則的區(qū)域。在查找時，設(shè)備的每個區(qū)域都能夠正常查找，但ETCAM每次只激活部分區(qū)域，進(jìn)而限制設(shè)備中每次查找的活躍區(qū)域的數(shù)目，從而達(dá)到降低能耗的目的。為了使查找關(guān)鍵字能夠激活正確的區(qū)域，E－TCAM采用多階段的分割算法。為了組織規(guī)則進(jìn)入適當(dāng)?shù)膮^(qū)域，硬件體系結(jié)構(gòu)嚴(yán)格限制了E－TCAM中“決策樹”的高度，而且每次查找可能并行地在若干分支之間執(zhí)行。

E－TCAM通過對原始TCAM硬件的改變，有效地解決了TCAM硬件空間利用率低和能耗大的問題。但是隨著TCAM的大規(guī)模應(yīng)用，修改TCAM硬件會造成巨大的成本開銷，同時降低了TCAM硬件的靈活性。

4．2 基于Bloom過濾器的包分類算法

Bloom 過濾器（Bloom Filter）［25］是一種二進(jìn)制向量的數(shù)據(jù)結(jié)構(gòu)，可以用簡潔的位數(shù)組表示大規(guī)模的數(shù)據(jù)集合，并快速對關(guān)鍵字進(jìn)行查找，判斷待查找元素是否屬于集合中。假設(shè)數(shù)據(jù)集合S共有n個元素，Bloom Filter通過k個哈希函數(shù)將各個元素映射到長度為m位的向量V中，每一個哈希函數(shù)的取值范圍為［0，m－1］，且函數(shù)之間相互獨立。將每個元素代入k個哈希函數(shù)中進(jìn)行計算，得到k個相應(yīng)的哈希函數(shù)值，Bloom Filter根據(jù)k個函數(shù)值，將相應(yīng)的V向量對應(yīng)的位置設(shè)置為1。查找時將待匹配查找的關(guān)鍵字，通過k個哈希函數(shù)產(chǎn)生k個哈希函數(shù)值，只有發(fā)現(xiàn)所有的k個哈希值對應(yīng)的V向量的比特都被置1時，Bloom Filter認(rèn)為該關(guān)鍵字屬于V向量代表的集合，否則不屬于該集合。對于一個元素，如果判斷不通過，那么該元素一定不屬于該集合，然而若通過，也不能代表該元素一定屬于集合，因為該元素哈希函數(shù)值的位置可能被其他元素置1。這種某元素不屬于集合而被認(rèn)定為該集合的可能性，稱為假陽性誤判。

Bloom Filter的優(yōu)點是它的查詢和插入時間都是常數(shù)。但它的缺點也是顯而易見的，假陽性誤判的概率隨著插入元素的數(shù)目增大而增大。另外，在Bloom Filter結(jié)構(gòu)中的某一位可能被多個元素的哈希值同時占用，所以，在Bloom Filter也不能隨意刪除一個元素，一旦刪除了某一個比特位，就可能會影響多個元素的檢測?；贐loom Filter的硬件包分類算法耗費資源過多，并且影響匹配速度，另外，算法動態(tài)更新比較困難。

基于布魯姆過濾的最長前綴匹配（Longest Prefix Matching Using Bloom Filters，LMP－Bloom）算 法［26］是運用Bloom Filter來實現(xiàn)最長前綴匹配的算法，即一維前綴匹配算法。首先將規(guī)則庫中的規(guī)則按照規(guī)則前綴的長度分成子規(guī)則集，子規(guī)則集數(shù)目與規(guī)則庫中前綴長度的個數(shù)相同，假設(shè)分成了W 個子規(guī)則集，那么算法需要W個Bloom Filter，分別存儲在對應(yīng)的W個子規(guī)則庫。當(dāng)數(shù)據(jù)包到達(dá)時，首先IP地址中各種不同長度的前綴被提取出來，再送入對應(yīng)長度的Bloom Filter中進(jìn)行查找，W 個Bloom Filter分別輸出匹配結(jié)果，當(dāng)發(fā)生有多個匹配結(jié)果時，按照最長前綴原則選擇。該算法中W 個Bloom Filter可以并行查找，匹配速度相當(dāng)快，但是消耗硬件資源較多。

分布式跨域符號生成（Distributed Crossproducting of Field Labels，DCFL）算 法［3］是 一 種 基 于 Bloom Filter的多維包分類算法，該算法將硬件設(shè)計與維度分解相結(jié)合。首先將多維匹配分解為多個一維匹配，分別在對應(yīng)的一維規(guī)則庫中進(jìn)行匹配，然后對每二維的匹配結(jié)果做叉積，與二維均匹配的規(guī)則必在這些叉積中，但是有些叉積并不屬于規(guī)則集。再將2個二維匹配結(jié)果再做叉積，再在四維叉積中匹配查找，以此類推進(jìn)而得到多維匹配結(jié)果。DCFL算法運用Bloom Filter數(shù)組完成叉積的查找，降低內(nèi)存訪問次數(shù)和假陽性概率。

5 結(jié)束語

包分類算法是包分類技術(shù)的核心。本文從包分類算法背景、基本概念等方面介紹包分類算法的研究狀況?？偨Y(jié)和歸納經(jīng)典的包分類算法，比較了它們的性能和特點，指出包分類算法設(shè)計的不足和缺點。隨著互聯(lián)網(wǎng)的高速發(fā)展，云計算、移動互聯(lián)網(wǎng)、大規(guī)模物聯(lián)網(wǎng)、軟件定義網(wǎng)絡(luò)（Software Defined Networking，SDN）的概念和OpenFlow等技術(shù)的興起，包分類問題的研究將面臨新的挑戰(zhàn)［27］。在性能上，應(yīng)支持超大規(guī)則集，滿足骨干網(wǎng)絡(luò)和數(shù)據(jù)中心網(wǎng)絡(luò)的帶寬。在業(yè)務(wù)上，應(yīng)具備識別應(yīng)用層包分類的能力，在網(wǎng)絡(luò)業(yè)務(wù)的管理和服務(wù)質(zhì)量上提供保障。同時，包分類技術(shù)將推動下一代互聯(lián)網(wǎng)和相關(guān)設(shè)備的發(fā)展。

［1］陳正虎，藍(lán)巨龍，黃萬偉，等．一種基于Bloom－filter表項壓縮的TCAM業(yè)務(wù)識別算法［J］．電子與信息學(xué)報，2011，33（9）：2212－2218．

［2］Lunterenvan J，Engbersen T．Fast and Scalable Packet Classification［J］．IEEE Journal on Selected Areas in Communications，2003，21（4）：560－571．

［3］Taylor D E，Turner J S．Scalable Packet Classification Using Distributed Crossproducing of Field Labels［C］／／Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies．Washington D．C．，USA：IEEE Press，2005：269－280．

［4］馬 騰，陳庶樵，張校輝．改進(jìn)的HyperSplit報文分類算法［J］．計算機(jī)工程，2014，40（1）：258－262．

［5］Yang Baohua，Jeffrey F，Jiang Weirong，et al．Practical Multi－tuple Packet Classification Using Dynamic Discrete Bit Selection［J］．IEEE Transactions on Computers，2014，63（2）：424－434．

［6］Kallath D．Trust in Trusted Computing——The End of Security as We Know It［J］．Computer Fraud and Security，2005，12（12）：4－7．

［7］Li Xiong，Liu Ling．PeerTrust：Supporting Reputation——Based Trust for Peer－to－peer Electronic Communities［J］．IEEE Transactions on Knowledge and Data Engineering，2004，16（7）：843－857．

［8］Gupta P，McKeown N．Packet Classification on Multiple Fields［C］／／Proceedings of ACM SIGCOMM’99．New York，USA：ACM Press，1999：147－160．

［9］亓亞炬，李 軍．高性能網(wǎng)包分類理論與算法綜述［J］．計算機(jī)學(xué)報，2013，36（2）：408－421．

［10］Gupya P，McKeown N．Packet Classification Using Hierarchical Intelligent Cuttings［C］／／Proceedings of the 7th IEEE Hot Interconnects Symposium．Washington D．C．，USA：IEEE Press，2000：34－41．

［11］Lakshman T V，Stiliadis D．High－speed Policy－based Packet Forwarding Using Efficient Multidimensional Range Matching［C］／／Proceedings of ACM Sigcomm．New York，USA：ACM Press，1998：203－214．

［12］Srinivvasan V，Suri S，Varghese G，et al．Fast and Scalable Layer Four Switching［C］／／Proceedings of ACM SIGCOMM’98．New York，USA：ACM Press，1998：191－202．

［13］Baboescu F，Singh S，Baboecu F，et al．Packet Classification for Core Router：Is There an Alternative to CAMs ［C］／／Proceedings of the 22nd IEEE Conference on Computer Communications．Washington D．C．，USA：IEEE Press，2003：53－63．

［14］Gupta P，McKeown N．Packet Classification on Multiple Fields［C］／／Proceedings of SIGCOMM’99．New York，USA：ACM Press，1999：147－160．

［15］Srinivasan V，Suri S，Varghese G．Packet Classification Using Tuple Space Search［C］／／Proceedings of SIGCOMM’99．New York，USA：ACM Press，1999：135－146．

［16］Micron Technology．Micron 1Gb DDR SDRAM Data Sheet［EB／OL］．（2008－11－21）．http：／／www．micron．com／products／dram／ddr2／partlist．a(chǎn)sp．

［17］Yu Fang，Lakshman T V．Effifient Multimatch Packet Classification for Network Security Applications［J］．IEEE Journal on Selected Areas in Communications，2006，24（10）：1805－1816．

［18］朱國勝，余少華．基于 TCAM 的范圍匹配方法——C－TCAM［J］．通信學(xué)報，2012，33（1）：31－37．

［19］Taylor D E．Survey Taxonomy of Packet Classification Techniques［J］．ACM Computing Surveys，2005，37（3）：238－275．

［20］Liu Huan．Efficient Mapping of Range Classifier into Ternary－CAM［C］／／Proceedings of the 10th IEEE Symposium on High Performance Interconnects．Palo Alto，USA：IEEE Press，2002：95－100．

［21］Che Hao，Wang Zhijun，Zheng Kai，et al．DRES：Dynamic Range Encoding Scheme for TCAM Coprocessors［J］．IEEE Transactions on Computers，2008，57（7）：902－915．

［22］Draves R，King C，Venkatachary S，et al．Constructing Optimal IP Routing Tables［C］／／Proceedings of IEEE INFOCOM’99．Washington D．C．，USA：IEEE Press，1999：88－97．

［23］Yu F，Katz R H．Efficient Multi－match Packet Classification with TCAM［C］／／Proceedings of the 12th IEEE Symposium on High Perfor－mance Interconnects．Palo Alto，USA：IEEE Press，2004：28－34．

［24］Spitnagel E，Taylor D，Turner J．Packet Classification Using Extended TCAMs［C］／／Proceedings of IEEE International Conference on Network Protocols．Washington D．C．，USA：IEEE Press，2003：42－52．

［25］Bloom B H．Space／time Trade－offs in Hash Coding with Allowable Errors［J］．Communications of the ACM，1970，13（7）：422－426．

［26］Dharmapurikar S，Krishnamurthy P，Taylor D E．Longest Prefix Matching Using Bloom Filters［J］．IEEE／ACM Transactions on Networking，2006，14（2）：397－409．

［27］Ganegedara T，Jiang Weirong，Viktor K．A Scalable and Modular Architecture for High－performance Packet Classification［J］．IEEE Transactions on Parallel and Dis－tributed Systems，2014，25（5）：1135－1144．