可擴展報文分類算法研究與評測
2009-01-01 00:00:00周粳迪程東年劉勤讓曹敏
計算機應用研究 2009年3期
(國家數字交換系統工程技術研究中心， 鄭州 450002)
摘 要：針對報文分類算法的可擴展性，深入分析了典型可擴展報文分類算法的時間、空間復雜度；基于ClassBench工具集開發出可擴展報文分類算法評測系統，利用該系統對典型算法在不同模擬場景下進行評測，并對各算法的性能差異和適用條件進行了系統分析。最后，對今后可擴展報文分類算法的發展趨勢作出了展望。
關鍵詞：報文分類； 可擴展性； 復雜度； 評測系統
中圖分類號：TP301 文獻標志碼：A
文章編號：10013695(2009)03081405
Research and evaluation of scalable packet classification algorithms
ZHOU Jingdi， CHENG Dongnian， LIU Qinrang， CAO Min
(National Digital Switching System Engineering Technological R D Center， Zhengzhou 450002， China)
Abstract:Focused on the scalability of packet classification algorithms，analyzed the time and space complexities of classic scalablepacket classification algorithms indepthly. Developed a ClassBenchbased evaluation system for scalable packet classification algorithms， utilized the system to evaluate the classic algorithms in different simulated scenes， analyzed the performance differences and suitable application conditions of the algorithms systematically.Finally prospected the future development of scalablepacket classification algorithms.
Key words：packet classification;scalability;complexity; evaluation system
隨著現代網絡技術的迅猛發展，人們對網絡帶寬和服務質量的要求日益提高，而網絡帶寬和服務質量的改善不僅需要有良好的鏈路，還需要具有相應功能的網絡設備和服務的支持。報文分類技術在網絡技術領域應用廣泛，諸如虛擬專用網VPN[1]、防火墻(firewall)[2]、基于策略的路由(policybased routing)[3]、區分服務(differentiated qualities of service)[4]、QoS[5]、報文深度檢測(DPI)[6，7]等網絡應用都必須以高效的報文分類技術作為支撐。一方面，分類規則早已超出了傳統五元組的限制，越來越多的新網絡應用需要用到五元組以外的字段甚至負載域來對報文進行有效分類；另一方面，隨著Internet各種業務的爆炸式發展，分類規則的更新愈發頻繁、分類規則庫的規模也日益擴大。所有這些都給報文分類技術的可擴展性提出了新的挑戰。
1 問題描述
為了更準確地對算法進行分析，首先結合報文分類的基本定義[8~10]給出報文分類的數學描述。
定義1地址D是一個長度為W bit的二進制串。
定義2地址前綴P是一個長度在0~W bit的二進制串，length(P)表示前綴P的二進制長度。
定義3如果D開始的length(P)個比特與P相同，稱前綴P與地址D匹配。
定義4報文頭H是有k個域的實體，報文頭的各個域分別表示為H[1]，H[2]，…，H[k]，每個域都由二進制串表示。
定義5過濾規則F含有k個匹配域，分別表示為F[1]，F[2]，…，F[k]，每個域對應報文頭部的一個字段。規則由三部分組成：a)用于匹配報文相關信息(一般是報文的頭部字段信息)的匹配域部分F[i]，i∈(1，k)；b)當報文匹配這條規則時對報文的操作（operation）；c)當報文匹配規則時的匹配代價cost(F)。
過濾規則的匹配域有四種表達形式，即精確值、前綴(常用于地址匹配)、范圍(常用于端口號匹配)和通配符；規則的匹配方式則有三種，即精確匹配(exact match)、前綴匹配(prefix match)和范圍匹配(range match)。
定義6域F[i]通過一個數值f來指定，當報文頭H第i個域H[i]的值h滿足h=f時，稱H[i]與F[i]精確匹配。
定義7域F[i]通過一個前綴P來指定，當報文頭H第i個域H[i]前length(P)位的值hp滿足hp=P時，稱H[i]與F[i]前綴匹配。
定義8域F[i]通過一個范圍指定，即F[i]=(val1，val2)。當報文頭H第i個域H[i]的值h滿足val1≤h≤val2時，稱H[i]與F[i]范圍匹配。
定義9當且僅當報文頭H的所有域H[i]（i∈(1，k)）與過濾規則F相應的域F[i]（i∈(1，k)）匹配時，稱規則F與報文頭H匹配。H[i]與F[i]的匹配方式由F[i]的形式指定。
定義10時間復雜度是算法分類速度的衡量指標，理論分析中用訪存次數作為評價依據。由于處理器的運行速度遠高于存儲器的訪問速度，分類性能主要取決于訪存次數。
時間復雜度包括三種情況：a)最壞情況，報文分類查找時間的最壞可能情況；b)平均情況，隨機條件下報文分類查找時間的平均值；c)統計情況，在報文被指定或規則具有確定的匹配率分布的條件下，報文分類查找時間的平均值。
定義11空間復雜度是算法存儲需求的衡量指標，理論分析中用分類算法建立的各種數據結構所占用的內存空間大小作為評價依據。
一般地，復雜數據結構可加快檢索速度，但要消耗更多的存儲空間，在實際應用中必須權衡分類速度與存儲需求。
報文分類的可擴展性包括兩個方面[11]：規則庫規模的可擴展性以及分類規則維數的可擴展性。好的分類算法應當滿足在規則數目增多的情況下對報文分類處理的性能不會下降很快，而且能夠很好地適應規則維數的增加。現在許多可擴展分類算法雖然具有良好的可擴展性，但是處理速度卻往往難以達到線速要求。基于TCAM[12]的分類技術在高速報文分類中表現良好，但是它的一些固有缺點，如功耗高、容量小、價格昂貴、更新復雜，導致其在規則庫規模較大以及規則更新較頻繁的應用場景下性能大為下降。
綜上所述，設計可擴展報文分類算法的主要目標是發掘算法的可擴展性以適應新的服務和管理策略，并保證算法以盡量低的開銷達到線速處理的要求。
2 典型可擴展算法
2.1 Crossproducting算法
Crossproducting算法[13]是一種基于緩存策略的分類算法，可適應任意多維的域。該算法的主要思想是：首先提取報文頭部各個域進行獨立查找，然后把各域的最優匹配結果交叉組合成Crossproduct，最后只需要一次哈希查表就可以得到最佳匹配規則?？梢宰C明:Crossproduct所對應的最佳匹配規則就是報文的最佳匹配規則。Crossproducting算法的cache策略是對Crossproduct進行緩存，這相對于單個報文信息的緩存具有更高的效率。
Crossproducting在最壞情況下空間復雜度達到O(Nd)，嚴重時可能發生內存爆炸(N是規則數，d是規則維數)。Crossproducting的改進算法為減少內存需求，只緩存固定數量的最佳匹配規則，稱為softcache[12]。當報文無法匹配時，算法用當前的Crossproduct替換出softcache中的一個使用頻率低的Crossproduct。Softcache的采用，一方面減少了算法的存儲需求以及數據結構的初始化時間；另一方面由于softcache中內容的動態更新性，導致了分類時間的不穩定。
2.2 RFC算法
RFC(recursive flow classification，遞歸流分類)[10]算法是一種多維分類快速查找算法，其思想是通過多階段處理，將報文頭的S bit映射到T bit的classID(其中T=log N，且T<
RFC算法縮減樹的形狀取決于兩個啟發式的條件：a)合并相關性最強的部分；b)在內存允許的情況下，盡可能多地進行合并。RFC算法在縮減樹建立的每一階段都生成一個從索引到eqID的映射表，由于上述工作是由軟件完成的，需要巨大的內存和預處理時間，該算法只適用于規則變化緩慢的分類器。在階段數P和縮減樹形狀固定的情況下，內存消耗量會隨著規則數N的增加而增加；在規則庫固定的情況下，P越大內存消耗越少、查找時間越長，所以必須根據實際需要權衡時間與空間。RFC算法的主要缺點是不能用于大型規則庫，不支持快速動態更新，預處理時間較長。
2.3 BV算法
BV[14](bit vector，位向量)算法是一種面向硬件實現的多域報文分類算法，它利用硬件位層次的并行機制(bitlevel parallelism)加速分類。BV算法將所有規則(d維)按優先級存儲，然后映射到d維空間，具體做法如下(如圖2所示，參照表1)：a)將規則庫各個值域空間映射到相應的坐標軸上;b)利用規則分割坐標軸，從而將d條坐標軸分割成數目不等的小區間，稱為基本區間；c)為每個基本區間定義一個N bit的位向量，位向量的每一個比特位對應規則庫中的一條規則。如果某條規則與該向量對應的基本區間相交疊，那么將該向量中對應這條規則的比特位置1；所有位向量被初始化為全0。
搜索過程相對簡單，報文到來時，根據報文頭部的各個域獨立搜索d個數據結構，然后將得到d個位向量做按位與操作。結果向量中優先級最高的置1位所對應的規則就是最高優先級的匹配規則，同理可以通過檢察結果向量中所有的置1位得到多匹配結果。
文獻[14]中指出，使用33 MHz時鐘周期的FPGA與五個128 KB的SRAM執行五域查詢，可支持512條規則且查找速度達到每秒1 M次。如果在基本區間使用二分查找技術，并行BV的時間復雜度為O(log N)，但空間復雜度則高達O(N2)。為減少內存消耗提出了一種使用增量讀取的改進算法，空間復雜度降到O(N log N)，其主要思路是：每個域只存儲一個位向量，另外用N個大小為log N的指針來記錄各基本區間之間比特位的變化。
2.4 ABV算法
ABV(aggregated bitvector，聚合位相量)[11]算法利用對真實規則庫的統計觀察改進并行BV技術的性能，進一步減少訪存次數。在真實規則庫中，一條報文所能匹配的最大規則數是有限的，所以位向量常會表現出稀疏性。ABV利用位圖聚類技術將N bit位向量劃分為A個向量塊(chunk)，只保留含有1的向量塊，每個向量塊的大小為「N/A。接下來定義一個A bit的聚合向量V，每個向量塊對應V的一個比特。如果某向量塊中含有1，那么聚合向量V中與之相對應的那一位就被置為1，如圖3所示。
ABV同樣按優先級順序來排列規則，并可以通過規則重排機制使位相量中的1聚集成串，達到減少訪存次數和消除假匹配現象的目的。對真實數據庫的仿真得出ABV的時間復雜度比BV算法減少了一個常數參數，但是ABV將全部規則域轉換為前綴，導致了過多的內存消耗。
2.5 EGTPC算法
EGTPC (extended gridoftrie with path compression，帶路徑壓縮的擴展網格樹)[15]算法是在二維算法gridoftrie[13]基礎上提出的，它對gridoftrie加以改進以應對多維分類的需要。該算法基于對真實規則庫的觀察發現：無論規則庫中的規則數目有多少，對于一個給定報文，如果只根據源、目的地址進行查找，匹配上的規則通常只有5條左右，最多不超過20條。所以，首先根據源、目的地址對報文進行二維分類，然后在命中的規則中根據報文其他域的信息進行簡單的線性查找就可以得到最佳匹配規則。
EGTPC算法仍然使用源、目的地址前綴構造標準的gridoftrie，但除了需要在源地址前綴節點存儲匹配規則外，還要存儲一個指向規則鏈表的跳轉指針。通過觀察可以發現，規則鏈表的規模遠小于核心路由器的規則庫，因此可以采用線性搜索。此外，EGTPC采用路徑壓縮技術去除了trie結構中的單分支路徑，使節點數目顯著減少，達到節省了存儲空間的效果。EGTPC算法的優點是能夠用于檢索大型分類數據庫，但由于數據結構初始化時間較長而且更新復雜，該算法不適合規則變化過快的場景。
2.6 DCFL算法
DCFL(distributed crossproducting of field labels，域標簽分布式叉級)[16]是基于分域處理的典型算法，它利用規則庫的特性、域分解以及標簽Crossproduct技術構建出一種高性能報文分類技術。算法基于兩個觀察：a)對于一個給定報文，在真實規則庫中匹配上該報文的不同域值的數目是有限的；b)匹配上給定報文的不同域值的組合數目也是有限的。利用硬件的高度并行機制，DCFL對每一個域采用獨立的搜索引擎，然后將各個域的查找結果分布式地聚合起來。由于分布式的聚合方式，DCFL不會像Crossproducting算法那樣出現時空復雜度指數增長的情況。
DCFL的關鍵在于為各個域的不同域值分配惟一的標簽。如同Crossproducting算法，DCFL首先將規則庫按域分割，然后給每個域值分配一個局部惟一標簽，并用計數器記錄包含該域值的規則數目作為更新與否的標志。如果給定各個域的標簽集，就可以通過將某條規則所有的域值標簽級聯起來的方法得到該規則的惟一標簽，所以DCFL的數據結構只需要存儲域值標簽和域值組合標簽。如圖4所示，第一個聚合節點(aggregation node)存儲的是端口—協議標簽庫(portprotocol label set)，該節點將端口域、協議域的域值標簽級聯起來形成端口—協議組合值的惟一標志，并送往下一級聚合節點與地址域進行聚合。
分類過程分為單域并行查找和標簽聚合兩個階段。首先并行搜索報文各域得到匹配標簽集合；然后把匹配標簽集合送到相應聚合節點得到聚合標簽查詢集Fquery。在預處理過程中，各聚合節點已經存儲了從原規則庫中提取出來的組合標簽集合F；當且僅當Fquery中的成員包含于F時才能進入下一級聚合節點。將最后一級聚合節點輸出的標簽傳遞給優先級判決模塊，選出優先級最高的標簽，進而得到最優匹配規則。
為了減少內存需要，DCFL算法還引入了中間標簽和域分割的技術。即使增加額外的節點，每條規則的內存消耗也只會增加約12.5 Byte。由此可以得出如下結論：DCFL能夠較好地適應規則維數的擴展；另外，通過計算節點聚合的最優順序、限制域搜索引擎返回的標簽數減少規則庫的查詢次數。DCFL的主要問題是，由于節點聚合順序是通過預計算固化下來的，當更新導致某域特性急劇變化時，算法難以保持其性能。
3 評價系統
報文分類是下一代網絡服務的一項重要技術，同時也是高性能路由器的瓶頸。各種算法和分類設備的性能取決于過濾規則庫的特性以及查詢模式，如何正確評價算法之間的優劣成為研究人員與用戶共同關注的問題。盡管有強烈的需求，仍然沒有一個通用的標準規則庫和性能評估工具。本文利用ClassBench[17]工具集建立一個分類算法的評測系統對上述算法進行評估。評測系統(圖5)由以下幾個模塊組成：a）規則庫生成器(filter set generator)，生成可以精確模擬真實規則庫特性的合成規則庫，既可改變規則庫規模又可控制規則庫的成分；b)trace生成器(trace generator)，生成報文頭序列以訓練分類算法，可以指定trace的相對大小并提供簡單的控制機制；c)算法選擇器(algorithm selector)，從算法文件庫(algorithm file set)選擇算法并為算法分配初始內存空間；d)分類模塊(classification module)，利用算法文件庫提供的算法并依據合成規則庫(synthetic filter set)對合成trace進行分類；e)監控模塊(monitoring module)，實時監控分類模塊并提取出算法的內存消耗量和SMA(sequential memory accesses，完成一次查詢需要的連續訪存次數)[16]。
3.1 Trace生成流程
評測系統主要利用了三個ClassBench工具生成規則庫和trace，即規則庫分析器、規則庫生成器和trace生成器。系統根據真實規則庫的相關特性構建一個benchmark參數文件，然后利用該參數文件和一些高層輸入(highlevel input)生成合成規則庫，最后使用trace生成器生成報文頭trace送到分類模塊進行查詢。具體流程如下：a)規則庫分析器從種子規則庫(feed filter set)中提取出相關的概率分布和統計項，然后生成benchmark參數文件。參數文件中包含不同的概率分布和統計項，它的作用是引導合成規則庫的生成。b)規則庫生成器將參數文件作為輸入，并通過由size、smoothing以及scope等三個參數組成的高層控制(highlevel control)將規則從參數文件中抽象出來。其中，由平滑調整(smoothing adjustment)提供的結構機制(structured mechanism)將引入新的地址聚合(address aggregates)，用于生成合成規則庫，需要注意的是合成規則庫的規模遠大于種子規則庫；范圍調整(scope adjustment)在規則生成過程中提供BM機制(biasing mechanism[16])以支持特殊規則。c)Trace生成器在檢查合成規則庫后生成報文頭trace(synthetic header trace)，然后送入分類模塊。d)Trace生成器利用參數scale調整trace的大小，并利用參數locality調整trace中報文頭的位置。
3.2 數據提取流程
數據提取由分類模塊和監控模塊共同完成。其中：
a)分類模塊由三個工具組成，即分類器(classifier)、移位器(shifter)和移位控制器(shifter controller)。移位器的主要功能是將報文按以下規則排列：保證trace中每一個報文頭從新的內存字開始存放，這樣處理的目的是減少后續模塊工作的復雜度。移位控制器接收合成報文頭trace，提取trace中報文頭的位置信息并以此為依據控制移位器工作，同時將合成報文頭trace送給移位器。分類器從移位器接收重新排列過的trace，按照算法文件庫提供的算法，并依據合成規則庫對trace進行分類，同時在分類開始前向監控模塊發出開始工作的觸發信號。算法選擇器的主要功能是為分類模塊的分類器提供算法支持并建立初始數據結構；選擇器根據參數type從算法文件庫選擇算法，根據參數memory為算法分配初始內存。
b)監控模塊完成兩個功能。算法運行時監控分類器的工作，實時提取當前算法的內存消耗量和SMA；分類結束時，根據提取的監控數據計算算法總的內存消耗量和算法完成一次查詢的平均連續訪存次數。內存監控器(memory monitor)對算法分類時的內存消耗量進行實時監控，當算法內存需求超出算法選擇器分配的初始值后，為該算法繼續分配存儲空間，最后在分類結束時計算算法總的內存消耗量并輸出。如果出現算法內存需求超出評測系統存儲能力的情況，內存監控器將向分類器和SMA監控器發出停止工作信號，然后輸出溢出標志。SMA監控器實時監控算法執行的SMA，在分類結束時計算算法的平均SMA并輸出。如果收到內存監控器發出的停止工作信號，立即停止監控，直至收到分類器發來的工作觸發信號。
4 評價結果及分析
4.1 算法復雜度
本文對典型可擴展報文分類算法的性能差異及改進關系已經進行了較為具體的分析，表2給出了各種可擴展分類算法在最壞情況下的時間、空間復雜度。假設規則庫中規則數目為N，最大字段寬度為W，參與分類的維數為d，內存字的寬度為m。
表2 各算法時空復雜度
algorithm nametime complexityin the worst casespace complexityin the worst cast
CrossproductingdWNd
RFCdNd
BVdW+N/mdN2
ABVdNdN2
EGTPCW2W2
特別地，DCFL由于采用硬件流水線操作，只在算法啟動初期有(d-2)個流水線周期，流水線周期在10 ns級別。聚合節點使用bloom filter array時，一個節點中的內存字數目為M=「k×｜F1，…，i｜/(m×ln 2)。其中k是bloom filter array中hash函數的個數，｜F1，…，i｜是bloom filter array輸出的標簽個數。當聚合節點使用metalabel indexing時，一個節點中的內存字數目為M=∑｜F1，…，i-1｜j=1「length(i)/n 。其中：n是每個內存字中存儲的表項條目；length(j)表示節點聚合標簽表中第i條表項的長度。綜上，每個節點中總的內存需求是m×M。
4.2 評測結果
具體的測評是在虛擬環境下(Intel Pentium 1.8 GHz，512 MB DDR400，RedHat 6)對各典型算法的可擴展性能進行評測，過濾規則庫和待分類報文均利用ClassBench根據真實規則庫的分布特點生成。對于規則庫規模的可擴展性，ClassBench生成的規則庫規模從20到10k條不等，能夠充分測試出算法對于不同規模數據庫的支持能力。對于規則維數的可擴展性，本文將測評分為A、B兩種情況。其中情況A的規則是四元組(源地址、目的地址、源端口、目的端口)；情況B的規則是六元組(源地址、目的地址、源端口、目的端口、協議類型和標志段)。評測結果由兩個指標參數組成，即存儲需求和查找時間。存儲需求由算法總的內存消耗量表示，單位是KB，精確度為1 KB；特別地，對于低于1 KB的數值，精確度取到小數點后1位；查找時間由平均情況下的SMA表示，精確度為1。通過分析各算法在不同規則庫規模以及不同規則維數情況下的評測數據，得到其性能差異以及適用條件。具體評測結果如表3、4所示。
4.3 結果分析
Crossproducting算法在仿真中表現出良好時間性能的同時，也暴露出內存消耗過大的弊端。從表3可以清楚地看到，當規則數據庫超過85條以后，算法內存溢出，出現內存爆炸的現象。盡管Crossproducting的SMA僅為10，而且有著良好的規則維數可擴展性(對于A、B情況，性能差別不大)，但算法較差的規?？蓴U展性使其應用范圍大大受限，一般只能用于對分類速度要求較高的小型規則庫。
RFC的優勢在于該算法是分階段匹配的，易于采用流水線的方法實現，從而得到優良的查找性能和吞吐量。對于包含1k條規則以內的真實五維規則庫，用硬件實現的RFC可達到10 Gbps的線速，用軟件實現也可達到2.5 Gbps的處理速度。如果在實際應用中通過硬件實現RFC，在利用并行處理的情況下可以很好地適應規則維數的擴展。但是，當規則庫的規則數超過1k條后，存儲空間以及預處理時間會增長過快，因此該算法只適合應用于小型規則庫。另外，針對算法規?？蓴U展性相對較差的問題，Harvard大學的Gupta等人[10]提出一種優化方案，對于包含15 000條四維規則的規則庫可以將存儲需求降到4 MB以下。
EGTPC的時間復雜度在最壞的情況下會達到O(W2)。其中W是最大字段寬度。B情況下對不同規則庫的仿真結果顯示，規模在85~3 000條規則的規則庫，算法執行一次查詢需要32~87次訪存；規模在5k~10k條規則的規則庫，一次查詢則需要134~225次訪存，EGTPC能夠用于檢索大型分類數據庫。但是可以看出，算法在B情況下的內存消耗遠大于A情況，所以EGTPC的維數可擴展性并不理想。
從仿真結果可以看出，BV、ABV算法內存消耗在各種情況下基本一樣，但算法執行速度只在規則庫規模較小時大體相仿。當規模超過3k以后，在BV算法執行速度大幅變慢的情況下，ABV算法仍能保持較穩定的時間復雜度。總體上講，BV算法適合于中小規模規則庫，ABV算法適合于中等規模數據庫。需要指出的是，從仿真結果看ABV算法的查找性能不如EGTPC算法。實際上這是因為ABV算法是硬件實現算法，其性能取決于硬件并行性和存儲器的帶寬，所以軟件仿真無法利用硬件的優良特性致使算法性能大大降低。
DCFL通過對上述九種規則庫的仿真，得出在最壞情況下匹配一條規則的連續訪存最大次數為10次，并且對于規則庫規模、規則維數的擴展需求都能較好地支持，規則庫達到10k條規則時仍能保持其良好性能。另外文獻[16]中指出，當內存字寬度為36 bit時，存儲一條規則的最大內存需求僅為18 Byte。基于此結果，DCFL的最優化執行可以提供
100M次/s搜索，使用當前存儲的技術可以支持超過20萬條規則。因此，DCFL算法可以適用于較為廣泛的應用場景。
5 結束語
報文分類在現代網絡中應用廣泛，隨著網絡帶寬的增加和用戶對網絡服務多樣性要求的增長，具有較強可擴展性報文分類算法的網絡設備將會不斷涌現。未來的報文分類算法將更加注重可擴展性和可移植性，盡量做到在較小的硬件(內存、處理速度等)需求下提高處理速度，并且盡可能減少規則數、規則維數和匹配長度等參數對分類性能的影響。然而實現可擴展性強的高速報文分類是十分困難的，目前已有的可擴展分類算法都有其自身的缺陷，本文就快速多維可擴展算法的設計提出如下幾點思路：
a)對于規則庫規模的可擴展性。算法必須保證在規則數目增加的情況下仍能實現高效分類?？沙浞掷肁SIC和FPGA的百萬邏輯門、內置多端口存儲模塊分解多域報文分類問題[18]，采用并行查找機制優化分域處理，并利用并行部件提供的流水線功能進一步提高算法實現速度，必要時可采用DDR SRAM、QDR SRAM等高性能片外存儲技術。雖然分類速度與內存需求互相矛盾，但是只要在內存容許的前提下，可以通過適當增加內存空間達到提高分類速度的目的。
b)充分利用分域處理的優點實現算法的可擴展性。分域處理，即對報文的各個域分別進行處理。目前，RFC、CrossProducting、DCFL等基于硬件實現的算法都體現了分域處理的思想。分域處理主要有以下三個特點：充分利用各個域的特點，有針對性地采用不同的方法對各個域進行處理，用最小的代價得到最好的結果；由于對報文的各個域分開處理，可以容易地實現增量更新；充分利用硬件的并行處理特性，分類的對象可以擴展到更多域，且不會增加處理時間。
c)采用逐級聚合分域處理結果的方法降低分域處理的時空復雜度。雖然分域處理有著其優越的特性，但如何降低分域處理結果聚合時的空間復雜度仍是一個極待解決的難點：一次性將所有分域處理的結果進行聚合會導致算法的空間復雜度急劇增大，嚴重時甚至會產生內存爆炸。為此，可以考慮將分域結果按效率優先的原則逐級聚合，并在每一次聚合時排除掉不可能的聚合結果，將算法的空間復雜度降到最低。
d)增加預處理時間。首先，為避免回溯的發生可以在建立數據結構的過程中適當增加預計算的時間并添加相應指針；然后，利用節點合并、路徑壓縮、消除冗余等措施減小算法數據結構的復雜度，達到減小更新訪存次數的目的。通過預處理后的數據結構的復雜度上大為改善，對于實現算法規模的可擴展性以及算法維數的可擴展性都能產生一定的效果。
e)對于維數的可擴展性可采用分別處理前綴字段和范圍字段的方法。分類規則的表示形式主要有前綴表示或范圍表示(精確表示是范圍表示的特殊形式)，現有算法在處理時需要在兩種表示形式間進行轉換，這勢必會增加存儲負擔并致使算法性能下降。所以，分別處理前綴匹配和范圍匹配可以避免它們相互轉換產生的額外開銷所導致的性能下降，從而提高算法的時空效率。更重要的是，利用這種處理方式，規則可以增加任意形式的字段且仍然保持其原有性能。
f)充分利用分類規則的特性。規則各個字段各有其特點，充分發掘并利用這些特點可以大大提高算法效率。例如，第四層協議類型長度是8 bit，但據統計，實際應用中使用的協議類型只有八種，所以只需要3 bit就完全可以表示協議類型字段；再如，通過研究分類規則各個域的分布規律，優先查找分布最均勻的域，這樣處理往往只需要查找報文前幾個域就得到了該報文的匹配規則，從而大大縮減查找時間。
參考文獻：
［1］VENKATESWARAN R. Virtual private networks[J]. IEEE Potentials， 2001，20(1):1115.
[2]BELLOVIN S， CHESWICK W. Network firewalls[J]. IEEE Communications Magazine，1994，32(9):5057.
[3]YEH Y， CHOW R， NEWMANWOLFE R. Interdomain access control with policy routing[C]//Proc of the 6th IEEE Workshop on Future Trends of Distributed Computing Systems. Washington DC: IEEE Computer Society， 1997:4652.
[4]LI T， REKHTER Y. RFC 2430， A provider architecture for differentiated services and traffic engineering[S/OL]. (199810) [20080724]. http://www.ietf.org/rfc/rfc2430.txt.
[5]WEISS W. QoS with differentiated services[J]. Technical Journal， 1998，3(4):4862.
[6]SUNG J S， KANG S M， LEE Y， et al. A multigigabit rate deep packet inspection algorithm using TCAM[C]//Proc of IEEE Global Telecommunications Conference. Washington DC: IEEE Communications Society， 2005:453457.
