聯(lián)合元組空間和位圖設計的二維分組分類算法

謝鯤，趙姣姣，張大方

（湖南大學 信息科學與工程學院，湖南 長沙 410082）

1 引言

隨著新型網(wǎng)絡設備及新型網(wǎng)絡服務的提出和發(fā)展，傳統(tǒng)單維分組分類算法已不能滿足網(wǎng)絡應用和服務的需求，多維分組分類算法成為分組分類技術研究的重點。多維分組分類算法將IP分組頭多個域的信息在相應的規(guī)則庫中進行多維匹配，以獲得匹配規(guī)則。網(wǎng)絡設備根據(jù)匹配規(guī)則中對應的策略對數(shù)據(jù)分組采取相應的措施，以完成相應的新型服務。

維度分解是解決多維分組分類問題的基本方法。利用維度分解，多維分組分類問題首先被分解成多個簡單一維匹配問題，然后通過某種數(shù)據(jù)結構，將多個一維的匹配結果相關聯(lián)得到最終的匹配規(guī)則?，F(xiàn)有的基于維度分解的多維分組分類算法主要有：ABV[1]算法，P2C[2]算法和RSFR算法[3]。

ABV算法為每一維SIP、DIP分別建立Tire樹結構，在掛規(guī)則的Tire節(jié)點中存放一個Nbit的向量，以標示規(guī)則庫中與該節(jié)點相匹配的所有規(guī)則（N為規(guī)則條數(shù)）。對每維處理后，取出各維匹配節(jié)點的Nbit向量，求交集得到最后匹配結果。ABV主要依據(jù)Nbit向量關聯(lián)出最后結果，然而每個規(guī)則節(jié)點均需要存儲Nbit向量，空間占用大，不易擴展到大規(guī)模規(guī)則庫。P2C算法在維度分解后利用硬件TCAM（ternary content addressable memory）[4]來解決單維到多維的關聯(lián)，匹配速度快，但是需要耗費硬件資源來支撐，并且TCAM存在高功耗、價格高、集成度低等缺點，只能用于小規(guī)模規(guī)則庫。RSFR算法采用元組空間 （TS, tuple space）[5]進行算法設計，其核心是用規(guī)則重編碼對 RS算法[5]進行改進。RSFR首先對各維進行一維處理，而后利用RS算法查找結構關聯(lián)出最終結果。RSFR時間性能較其他多維分解算法優(yōu)越，易于向大規(guī)模規(guī)則庫擴展。然而RSFR算法為了減少訪問元組空間的個數(shù)，提高匹配速度，除了對規(guī)則重編碼外，還需要兩項復雜的預處理操作：插入偽規(guī)則和計算每條規(guī)則的BMP（最優(yōu)匹配規(guī)則）。這使得RSFR空間耗費過大，需要存儲真實規(guī)則和偽規(guī)則（最壞情況需要插入40%×N條偽規(guī)則（N為規(guī)則數(shù)目）），還有每條規(guī)則的 BMP（BMP作為規(guī)則的屬性存放）。另外，規(guī)則庫更新復雜度也增加，增加刪除規(guī)則都需要處理所需的偽規(guī)則，并重新計算所有受影響的BMP。

一方面，維度分解可降低多維分組分類算法的難度，算法的整體性能取決于關聯(lián)數(shù)據(jù)結構的設計，因此，如何設計高效的關聯(lián)數(shù)據(jù)結構，以聯(lián)合各維匹配結果得出最終匹配規(guī)則成為高效多維數(shù)據(jù)分組分類算法設計的關鍵。另一方面，現(xiàn)有研究表明，大規(guī)模規(guī)則庫中與前兩維匹配的子規(guī)則庫規(guī)模非常小，處理多維分組分類可以首先進行二維分組分類[6]（二維分組分類通常根據(jù) IP分組中的源IP（SIP）、目的IP（DIP）2個域進行規(guī)則匹配），而后在規(guī)模有限的子規(guī)則庫中對其他維進行簡單的線性匹配即可。

本文從維度分解出發(fā)，設計并實現(xiàn)了一種新的二維分組分類算法（TB, joint tuple space and bitmap）。TB將元組空間和位圖相結合作為一維匹配后的關聯(lián)結構，并利用交叉組合思想形成需要訪問的TS路線，利用位圖過濾減少需要訪問的TS數(shù)目，可以高效快速的匹配出最終結果，并且可以克服RSFR算法的缺點。TB算法結構簡潔，易于實現(xiàn)，具有良好的時空性能。另外，TB預處理操作簡單，規(guī)則庫更新較易且具有良好的擴展性能。

本文的行文安排為：第2節(jié)介紹TB算法設計的基本思想，第3節(jié)對TB算法各部分進行具體實現(xiàn)，第4節(jié)分析TB算法的性能，第5節(jié)從不同場景實驗測試TB算法的性能，第6節(jié)是結束語。

2 TB設計的基本思想

TB算法結構框架如圖 1所示。算法可分為 3部分，第1部分：分別對SIP、DIP進行AMP匹配，并利用前綴長度交叉組合成TS。第2部分：在位圖上驗證交叉元組空間是否存在，過濾掉不存在的TS。第3部分：在通過位圖驗證的相應TS中進行查找以獲得最終匹配的多維規(guī)則。

圖1 TB算法結構

TB算法包括以下3點基本設計思想。

1) 維度分解設計思想。

TB算法的第一部分分別對SIP、DIP進行所有匹配規(guī)則的查找即求AMP。不同于RSFR算法中只求最長前綴匹配（LMP, longest prefix match），TB算法不僅求LMP，還要求出所有和SIP、DIP匹配的嵌套子規(guī)則（如果規(guī)則Px是規(guī)則Py前綴的子串，則稱Px為Py的一條嵌套子規(guī)則）。如圖2所示，若 SIP匹配的 LMP為規(guī)則 P4，TB算法第一步AMP(SIP)的結果為 P4、P3、P1。

圖2 規(guī)則編碼實例

2) 利用規(guī)則庫嵌套特征進行優(yōu)化設計。

基于規(guī)則庫嵌套原理，TB算法有2處設計：第一，對于一維的AMP結果，進行交叉組合。第二，引入規(guī)則重編碼，減少TS的個數(shù)。

在真實規(guī)則庫中，單維規(guī)則最大嵌套層次數(shù)目（稱為S）遠遠小于規(guī)則中不同前綴長度的個數(shù)，S一般小于3，最壞情況下為5。例如規(guī)則0*和規(guī)則0100*都是規(guī)則010000*的嵌套子規(guī)則，且嵌套層次為3。換句話描述，對一個IP分組的SIP或者DIP進行單維的AMP匹配，AMP中包含的規(guī)則數(shù)目即為S，因此可知AMP規(guī)則數(shù)目與嵌套層次相同一般小于3。這就是規(guī)則嵌套的基本特征。文獻[1,3,7,8]均調研得出如此結論，且此結論也用在許多經典的算法設計中[1,6,9]，本文通過實驗也證明了此特征。

基于規(guī)則的嵌套特征，TB算法運用交叉組合思想進行算法設計。第一部分對SIP、DIP求得AMP后，分別取 SIP、DIP各個匹配規(guī)則的前綴長度，將其交叉組合成元組空間，由于S數(shù)目很小，因此交叉組合形成的TS個數(shù)也很小，一般小于9最壞情況下為25，下一步只需要在這些數(shù)目規(guī)模有限的TS中進行訪問，時間性能得到第一步保證。因為和二維均匹配的規(guī)則必在這些交叉元組空間中，這是TB算法關聯(lián)各維結果后形成的TS訪問路線。例如SIP的AMP長度為2、3，DIP的AMP長度為1、4，那么交叉組合形成的TS分別為TS（2，1）、TS（2，4）、TS（3，1）、TS（3，4），在這些 TS 中訪問一定可以找到與二維均匹配的最優(yōu)規(guī)則。

為減少所需形成TS的數(shù)目，TB算法還引入規(guī)則重編碼設計。規(guī)則重編碼思想廣泛應用于分組分類算法設計中，因為重編碼可以大大降低形成的元組空間個數(shù)，減少交叉元組空間在位圖上的命中率，提高匹配速度。在TB中，根據(jù)規(guī)則P所有嵌套子規(guī)則的前綴長度，將規(guī)則P分成多個子串，并歸入不同的層次。為了理解編碼過程，圖2是取自文獻[3]的編碼實例，規(guī)則P4（010000）有2個嵌套子規(guī)則分別為P1（0）、P3（0100），因此，將P4 分為3 個位串＜0＞＜100＞＜00＞，將這3個位串分別歸入第一層，第二層和第三層。對所有規(guī)則如此處理后，為每一層的位串賦予新的 ID如圖2所示，規(guī)則新的編碼為連接該規(guī)則在各層相關位串的新ID。例如規(guī)則P4編碼后為（0000100）?？梢?，編碼后規(guī)則不同長度的數(shù)目將大大減少，即從W（W為IP地址的長度）降低為規(guī)則庫的最大嵌套層次數(shù)S。RSFR算法正是基于此將RS的時間性能從O(2W?1)提升為O(2S?1)。圖2中，實例規(guī)則庫的嵌套層次為3，編碼后規(guī)則不同長度個數(shù)由7降至3，長度分別為2、5、7。

3) 元組空間和位圖相結合的關聯(lián)結構。

在進行多維關聯(lián)數(shù)據(jù)結構設計時，交叉組合形成的TS并不一定真正存在，為了進一步減少訪問TS的個數(shù)，利用位圖技術來對所需訪問的TS進行空間的過濾。若沒有通過位圖，則不需要訪問對應TS；若通過位圖，則在相應的TS中查找所匹配的規(guī)則。位圖技術是TB算法時間性能的第二步保證，結合規(guī)則庫嵌套原理使得TB算法在平均時間性能上仍優(yōu)于RSFR算法。

3 TB算法具體實現(xiàn)

圖1給出了TB算法的匹配數(shù)據(jù)結構框架，本節(jié)具體說明算法3個部分的實現(xiàn)。

算法第1部分，分別求出與IP分組的SIP、DIP匹配的所有規(guī)則，此部分需要一個查找AMP的一維包匹配算法。TB算法與RSFR算法一樣均采用文獻[10]提出的BSH（binary search on hash table）算法實現(xiàn)。BSH算法是一維分組分類算法，根據(jù)IP分組的SIP或者DIP在散列表上進行折半查找，最終查找出與一維地址匹配的最長匹配規(guī)則即LMP。文獻[10]指出 BSH算法一次查找最多需要lbW次散列訪問，W為IP地址的位寬。因此對于IPv4最多需要lb 32，即 5次散列訪問，對于 IPv6需要lb128即7次。本文采用BSH一是便于與RSFR比較，因為2個算法該部分均可根據(jù)需要換取效率更高的一維匹配算法，二是BSH算法查找性能較好，訪問內存次數(shù)只與IP地址位寬有關，與規(guī)則庫大小無關，因此易于向大規(guī)模規(guī)則庫和IPv6擴展。

然而BSH是針對LMP的一維算法，TB需要的一維匹配算法需要匹配出AMP。因此，在TB算法設計中，將規(guī)則重編碼思想和 BSH相結合，以得到AMP結果。算法在規(guī)則重編碼階段已經記錄了編碼后所有規(guī)則的長度，如圖2實例中，編碼后不同規(guī)則長度數(shù)目為 3，分別為 2、5、7，因此當求得SIP、DIP的LMP后，可根據(jù)此LMP的前綴長度以及編碼后所有規(guī)則的長度，直接求得AMP，例如在圖2中若某SIP的LMP規(guī)則為P4，其長度為7，則與此SIP匹配的所有AMP的長度一定分別為2、5、7，具體值即為取P4的前2、5位組成的規(guī)則，即 P1、P3。然而在 TB算法中只需要記錄AMP規(guī)則的長度即可。因此采用BSH算法實現(xiàn)TB算法第1部分，則TB算法和RSFR算法此部分內存訪問次數(shù)相同。

算法第2部分，采用位圖標識各個TS的存在狀態(tài)，對于IPv4，所有可能的規(guī)則前綴長度為從0到32，因此所有可能形成的TS個數(shù)為33×33。因此位圖的大小設為 33×33bit，稱之為bitMap[33][33]。位圖初值為0，標識各TS不存在，即沒有規(guī)則屬于此TS。當將編碼后形成的規(guī)則放入對應的TS時初始化位圖相應位置的值為1，標識此TS存在。例如二維規(guī)則（0000100*，01011*）屬于TS（7,5），設位圖bitMap[7][5]值為true即為1。將第一部分形成的交叉元組在位圖上進行過濾查找時，相應位置為0則過濾掉，不必進行算法第3部分查找。位圖結構簡單，可以用軟件或者硬件實現(xiàn)，若用片上硬件實現(xiàn)，則可加快驗證速度。

算法第3部分，需要在通過位圖的相應TS中進行查找，在具體一個TS中用散列進行匹配，算法時間性能取決于訪問TS的個數(shù)，因此本文記錄算法訪問TS的個數(shù)。

圖3是TB算法具體匹配過程的實例，算法匹配過程非常簡潔：對于某IP分組，若匹配出SIP的AMP分別為規(guī)則P4、P3、P1，由圖2可知這些規(guī)則編碼后對應的長度分別為7、5、2，同樣對于DIP，P14、P12對應的長度為 5、2，利用這些規(guī)則長度交叉組合成 6個 TS 分別為 TS（7，5）、TS（7，2）、TS（5，5）、TS（5，2）、TS（2，5）、TS（2，2）。而后，將上述6個TS在位圖上過濾，位圖相應位置為1表明此TS存在，則在該TS中匹配，若匹配到即將此規(guī)則作為當前IP分組匹配的最優(yōu)規(guī)則，若后續(xù)在其他TS中匹配到優(yōu)先級更高的規(guī)則，則替換，最終找到最優(yōu)的匹配規(guī)則。

圖3 TB算法分組匹配實例

4 TB算法性能分析

本節(jié)分析TB算法和RSFR算法時空需求并比較各方面的性能。TB算法空間需求為：BSH算法空間+位圖+TS中規(guī)則，RSFR空間為：BSH算法空間+RS算法空間（包括偽規(guī)則和規(guī)則）；TB算法內存訪問次數(shù)為：AMP（SIP）.access + AMP（DIP）.access+交叉組合形成的元組空間中通過位圖即存在的元組空間個數(shù)，其中access表示相應算法的訪問內存次數(shù)。RSFR算法內存訪問次數(shù)為：LMP（SIP）.access+LMP（DIP）.acces+RS.access。2 種算法在一維處理上均采用BSH算法，雖然TB求解一維的AMP，RSFR求解一維的LMP，但由上節(jié)算法具體實現(xiàn)可知，這部分的內存訪問次數(shù)和空間需求與RSFR算法相同，因此時空性能主要取決于第2部分。下面可以暫不考慮一維的開銷，對2種算法性能進行比較分析。

1) 預處理復雜度：TB和RSFR均需要對規(guī)則進行重編碼，此外，TB預處理中只需要將每條規(guī)則存放入相應的元組空間，并根據(jù)形成的元組空間初始化位圖。而RSFR除了存放規(guī)則外，還需要插入需要的偽規(guī)則，并計算各條規(guī)則的 BMP規(guī)則。顯然TB預處理操作簡單，所需時間少。

2) 更新復雜度：TB算法不需要RSFR中2項復雜的預處理，因此規(guī)則庫更新較易，因為不需要為增加刪除規(guī)則處理偽規(guī)則，并重新計算所有受到影響的BMP。

3) 空間占用：TB算法只需要在TS中存儲規(guī)則，不需插入任何偽規(guī)則，也不需要在預處理中為規(guī)則存放 BMP，大大降低了空間耗費。TB算法中增加的位圖空間相比RSFR中插入的很多偽規(guī)則，空間占用非常小，TB空間性能大大優(yōu)于RSFR。

4) 時間性能分析：2種算法均不考慮2個一維匹配過程，對于RSFR算法最多訪問元組空間個數(shù)為O(2S?1)（S為規(guī)則庫嵌套的最大層次），TB算法第一部分求出AMP的個數(shù)分別為S，交叉組合形成的元組空間個數(shù)為S×S，算法需要訪問的元組空間個數(shù)最多為O(S×S)。但是由規(guī)則嵌套特征可知S數(shù)目很小，因此O(S×S)不會非常大于O(2S?1)。雖然從分析看TB時間性能不如RSFR，但是TB算法通過兩點降低了訪問元組空間的個數(shù)，第一，算法采用位圖過濾，S×S個TS中只有標示存在才需要訪問，大大降低了訪問TS的個數(shù)。第二，TB算法形成的TS個數(shù)少于RSFR算法，因為雖然兩算法均通過規(guī)則重編碼使得元組空間個數(shù)很少，但是在RSFR算法中仍有一些TS是純粹的偽規(guī)則組成，這些TS在TB算法中不存在。分析可知，TB算法的時間性能主要取決于規(guī)則庫嵌套層次和位圖的過濾效果，嵌套層次決定了交叉形成的TS個數(shù)，位圖過濾決定了真正需要訪問的TS個數(shù)。然而實際中，每個數(shù)據(jù)分組交叉形成的TS中有大部分并不真正存在，可以通過位圖過濾掉。本文實驗仿真的數(shù)據(jù)是通過多個大規(guī)模流量文件測試并取得其平均值，可見TB算法除了空間性能優(yōu)越外，時間性能通過位圖過濾仍然優(yōu)于RSFR。

5) 重編碼的依賴程度：重編碼降低了TS的個數(shù)，有利于提高匹配速度，然而對算法的更新帶來了困難。RSFR算法的性能完全依賴于重編碼，否則退化為RS算法。而TB算法中就算不引入重編碼，訪問的TS個數(shù)由規(guī)則庫嵌套原理可知，也是極其有限的，時間性能上不會有很大波動。因此TB算法在設計的選擇上有更大的自由空間。

5 仿真實驗

仿真平臺由C++語言編寫完成，運行環(huán)境為：Pentium 4 3.00GHz CPU，512MB內存，Windows XP操作系統(tǒng)。仿真實驗采用PALAC（packet lookup and classification simulator）平臺[11]的流量生成器生成網(wǎng)絡流量。為了有效驗證算法性能，本文采用華盛頓大學開發(fā)的ClassBench平臺[8]生成仿真所用的規(guī)則庫。ClassBench是一組工具，它將真實的規(guī)則庫作為種子，通過高層參數(shù)的調控生成符合真實規(guī)則庫特征的規(guī)則庫，與其他研究中運用路由表生成規(guī)則庫相比，能更準確真實的模擬了分組分類算法的運行環(huán)境。本文運用ClassBench生成大小不同且類型不同的規(guī)則庫，規(guī)則庫3種類型分別是 Access Control List（ACL）、Firewall（FW）、IP Chain（IPC）。

實驗中，將論文所提出的TB算法與RSFR算法進行性能比較。5.1節(jié)中為了驗證算法在小規(guī)模規(guī)則庫中運行的性能，規(guī)則庫大小為300～6 000條不等。為了驗證算法的擴展性能，在5.2節(jié)規(guī)則庫大小為5 000～100 000條不等。對這些規(guī)則庫進行實驗分析可知它們均符合規(guī)則庫的嵌套特征。分組分類算法主要性能衡量指標為時間性能即數(shù)據(jù)分組匹配速度及算法存儲空間占用2個方面。時間性能方面通過統(tǒng)計各算法的平均內存訪問次數(shù)來衡量?？臻g占用方面，統(tǒng)計各算法需要存儲的規(guī)則和偽規(guī)則，規(guī)則的每一維度占用40bit（32bit存儲IP地址，8bit用來表示前綴長度）。需要注意的是，2個算法均統(tǒng)計兩個一維算法 BSH占用的空間，并且對于 TB算法需要統(tǒng)計位圖的空間，RSFR算法需要統(tǒng)計其偽規(guī)則所需空間。

5.1 小規(guī)模規(guī)則庫性能分析

已有研究表明，真實規(guī)則庫的大小一般為5 000條左右。首先測試算法在小規(guī)模規(guī)則庫（300～6 000條）上運行的性能。圖4(a)為TB算法和RSFR算法的平均訪問內存次數(shù)，圖4(b)是2種算法空間大小需求。表1統(tǒng)計了2種算法數(shù)據(jù)結構形成的TS的個數(shù)以及最壞的內存訪問次數(shù)。

需要指出的是，雖然兩算法第1部分的單維匹配算法可通過并行提高速度，但測試中仍按照串行進行測試，即按照第4節(jié)分析的性能公式計算。由圖 4(a)可知，算法 TB平均內存訪問次數(shù)優(yōu)于RSFR算法，平均低于RSFR算法26.6%。注意此平均訪問次數(shù)中均包含2個一維算法BSH的訪問次數(shù)，而由具體實現(xiàn)可知2種算法一維匹配算法性能相同，因此實驗結果表明若不計算一維算法，TB算法的平均內存訪問次數(shù)仍優(yōu)于RSFR算法。這證明了在第 4節(jié)分析的結果，雖然不考慮一維，RSFR算法的訪問次數(shù)為O(2S?1)，TB算法訪問次數(shù)為O(S×S)，但是TB算法通過位圖過濾和減少 TS個數(shù)保證了算法平均訪問次數(shù)仍然優(yōu)于RSFR算法。因為由一維匹配結果交叉形成的S×S個 TS中大部分并不存在，可通過位圖排除，且由表 1統(tǒng)計的 TS個數(shù)可知，TB算法不需要插入偽規(guī)則，所以不存在由純粹偽規(guī)則組成的TS，形成的TS個數(shù)少于RSFR算法，有利于降低位圖命中率，提高速度。然而TB算法在最壞內存訪問次數(shù)性能方面不如RSFR算法穩(wěn)定，如表1所示，雖然2種算法最壞訪問次數(shù)彼此相差不大，但是RSFR算法較為穩(wěn)定。這是由于 TB算法最壞內存訪問次數(shù)取決于交叉形成的S×S個TS在位圖中的命中率。

圖4 小規(guī)模規(guī)則庫（300～6 000條）性能測試

表1 TS個數(shù)及最壞內存訪問次數(shù)

圖4(b)為2個算法空間需求性能比較，由圖可見雖然兩算法都隨規(guī)則庫規(guī)模增大而線性增長，但是TB算法較RSFR算法節(jié)省大量空間，平均降低35.1%的空間需求。因為TB算法不需要插入任何偽規(guī)則，且隨著規(guī)則庫規(guī)模增大空間優(yōu)勢越明顯。

綜上分析，TB算法在空間和時間性能上均優(yōu)于RSFR，實驗證明了TS和位圖相結合的優(yōu)勢。

5.2 大規(guī)模規(guī)則庫性能分析

圖5 大規(guī)模規(guī)則庫（5 000～100 000條）性能測試

為了證明算法的擴展性能，測試算法在大規(guī)模規(guī)則庫下的性能，規(guī)則數(shù)目分別為5 000～100 000條不等。實驗結果如圖5所示，從圖5(a)可知，TB算法平均內存訪問次數(shù)優(yōu)于RSFR算法，且平均訪問次數(shù)隨規(guī)則庫規(guī)模的增大波動很小，相差不大，最大和最小訪問次數(shù)相差為 2，具有良好的擴展性，比RSFR算法擴展性能穩(wěn)定。仔細分析可知，對于RSFR算法開始的規(guī)則5 000～30 000條的訪問次數(shù)較高，是因為這些規(guī)則庫類型為 Firewall（FW），F(xiàn)W類型的規(guī)則庫嵌套層次S比較大，而這對于TB算法影響不大，因為 TB算法中運用位圖結構進行過濾，只有真正存在的 TS才進一步訪問。圖5(b)表明，對于大規(guī)模規(guī)則庫，空間上TB算法仍低于RSFR算法，且增長速度低于RSFR算法，因為RSFR算法隨著規(guī)則庫規(guī)模擴大，插入的偽規(guī)則條數(shù)亦增大。

6 結束語

本文從維度分解設計思想出發(fā)，將元組空間和位圖結構相結合作為一維處理后的關聯(lián)結構，設計并實現(xiàn)了一種新的高性能二維分組分類算法。TB算法首先進行維度分解，查找各維的AMP，然后運用交叉組合形成元組空間并在位圖上進行過濾，在各元組空間中查找后返回優(yōu)先級最高的匹配規(guī)則。相比于傳統(tǒng)的元組空間算法，TB算法不需要插入任何偽規(guī)則，大大降低了算法空間需求，并通過采用位圖過濾技術以及減少元組空間個數(shù)，提高了算法的時間性能。論文最后通過在規(guī)模不同的規(guī)則庫上進行實驗測試，證明了算法TB在空間和時間性能上均優(yōu)于 RSFR算法，且具有良好的擴展性能。

[1]BABOESCU F, VARGHESE G.Scalable packet classification[J].IEEE /ACM Transactions on Networking, 2005, 13(1):2 - 14.

[2]LUNTEREN J V, ENGBERSEN T.Fast and scalable packet classification[J].IEEE Journal of Selected Areas in Communications, 2003,21(4): 560-571.

[3]PI-CHUNG W, CHUN-LIANG L, CHIA-TAI C,et al.Performance improvement of two-dimensional packet classif i cation by filter rephrasing[J].IEEE /ACM Transactions on Networking, 2007, 15(4):906-917.

[4]ZANE F, NARLIKAR G, BASU A.Coolcams: power-efficient TCAMs for forwarding engines[A].Proc of Twenty-Second Annual Joint Conference of the IEEE Computer and Communications[C].San Francisco, 2003, 42-52.

[5]SRINIVASAN V, SURI S, VARGHESE G.Packet classification using tuple space search[A].Proc of ACMSIGCOMM 1999[C].Cambridge,Massachusetts, United States, 1999.135-146.

[6]BABOESCU F, SUMEET S, GEORGE V.Packet classification for core routers: is there an alternative to CAMs?[A]Proc of IEEE INFOCOM 2003[C].Toronho, Ontarion, Canada, 2003, 53-63.

[7]FELDMAN A, MUTHUKRISHNAN S.Tradeoffs for packet classification[J].IEEE INFOCOM, 2000.1193-1202.

[8]DAVID E T, JONATHAN S T.ClassBench: a packet classification benchmarks[A].Proceedings of IEEE/ACM Trans on Networking[C].San Francisco, CA, USA, 2007,499-511.

[9]LAKSHMAN T V, STIDIALIS D.High speed policy-based packet forwarding using efficient multi-dimensional range matching[A].Proc of.ACM SIGCOMM 1998[C].Vancouver, British Columbia, Canada,1998, 203-214.

[10]MALDVOGEL M, VARGHESE G, TURNER J,et al.Scalable high speed IP routing lookups[A].Proc of ACM SIGCOMM, Cannes,France, 1997.25-36.

[11]PANKAJ G, BALKMAN J.PALAC: Packet Lookup and Classification Simulator[Z].User's Manual, ver.4, Rev.2000.