報文分類算法研究
2007-01-01 00:00:00孫毅劉彤蔡一兵胡金龍石晶林
計算機應用研究 2007年4期
摘要：闡述了互聯網絡中報文分類問題的定義、幾何意義和最新研究進展。從報文分類算法的實現特征出發，對報文分類問題的各種經典算法進行了分類并逐類地詳細介紹。通過對幾種典型算法在虛擬環境下進行評測，總結了各種報文分類算法的優缺點和適用環境，并就報文分類問題的研究方向作出展望。
關鍵詞：報文分類； 服務質量； 查找性能； 存儲需求； 更新效率
中圖分類號：TP393文獻標志碼：A
文章編號：10013695(2007)04000507
現代網絡技術的發展使得越來越多的網絡設備需要支持快速準確的報文分類，如安全網關、邊緣路由器、核心路由器等。未來網絡的發展趨勢需要為用戶提供更好的服務質量，而諸如防火墻[1]、區分服務[2]、虛擬專網VPN[3]、基于策略的路由[4]、高層交換[5]等提高服務質量的機制都是基于高效報文分類技術之上的。此外，隨著光纖通信技術的普及，鏈路帶寬和傳輸速率已不再成為問題，路由轉發設備正在成為網絡瓶頸。因此研究高效的報文分類算法對于未來互聯網的發展具有極其重要的意義。
近年來，國內外很多專家學者針對互聯網絡的報文分類問題進行了大量研究，提出了一系列有效的算法以應付不同網絡設備和應用環境的需求。本文根據算法的實現特征對這些算法進行了簡要的總結和測評，并對未來的研究方向作出展望。
1報文分類的基本概念
1.1報文分類的定義
互聯網業務的多樣化和差異化要求網絡設備能夠根據網絡中報文的相關信息對報文進行差異化處理。報文分類就是為滿足網絡的這種應用趨勢產生的。它是根據報文頭部信息的關鍵字段對報文進行分類，網絡設備針對不同類別的報文可以采取不同的操作。這種分類操作由網絡設備的分類器完成。通常，分類器都包含一個分類規則庫，該規則庫由幾百到幾百萬條過濾規則（Filter）組成：F1，F2，F3，…，FN。每一條規則由三部分組成：①用于匹配報文相關信息（一般是報文的頭部字段信息）的匹配域部分；②當報文匹配這條規則時采取的對報文的操作；③當報文匹配規則時的匹配代價。
每條過濾規則Fi含有d個匹配域，形如Fi[1]，Fi[2]，…，Fi[d]；每個域都對應報文的一個頭字段。過濾規則的域有四種表達形式，可以是一個精確的值，也可以是前綴表示（常用于地址匹配）、范圍表示（常用于端口號匹配）或通配符。
每一條過濾規則的操作域都關聯一個動作，用于指示當報文匹配到該規則時執行的操作，其具體動作與分類器的應用場景有關。例如對于防火墻，動作可能是阻塞或允許通過該報文；而對于MPLS邊緣路由器，動作是轉發該報文到相應標簽交換路徑（Label Switch Path）上。
每一條過濾規則還關聯一個匹配代價。報文分類問題的實質就是對一個到達的報文根據其頭字段的信息在分類器規則庫中尋找代價最小的匹配規則。每個頭字段具體的匹配方式由過濾規則相應域的表達形式決定，共有三種不同的匹配方式：①精確匹配。報文頭字段的值與過濾規則匹配域的精確值匹配。②前綴匹配。報文頭字段的值符合過濾規則匹配域規定的前綴。③范圍匹配。報文頭字段的值落在過濾規則匹配域規定的范圍內。當一個報文的d個頭字段與一條過濾規則的d個域均匹配時，就稱該報文匹配該規則。由于過濾規則的交疊性，一個報文可能匹配規則庫中的多條過濾規則，選取這些過濾規則中代價最小的并執行該規則所關聯的動作。表1是一個簡單的分類器規則庫示例。
表1過濾規則庫示例
規則目的地址源地址目的端口源端口協議號操作代價
1.2報文分類的幾何意義
報文分類問題與計算幾何中的點定位問題[6]非常相似：規則庫中每一個d維過濾規則對應d維空間的一個封閉區域，而報文頭對應著d維空間的一個點。因此報文分類問題可以看作是尋找d維空間中包含該點的代價最小的封閉區域。
1.3分類器設計的主要目標
分類器設計的主要目標是設計分類算法以滿足不同傳輸介質的線速（Wirespeed）[7]。報文分類是以報文為單位進行處理的，報文長度從幾十個字節到幾千個字節不等。通常都是考慮最短報文長，以此計算單位時間內分類器需要處理的報文數目。
分類速度（線速）packet/s=傳輸帶寬 bps/（最短報文長Byte/packet×8 bit/Byte）
1.4報文分類算法的評判準則
評價一個分類算法，通常有三個標準[8]：
（1）分類速度。它是衡量一個分類算法最重要的標準。時間復雜性包括最壞情況、平均情況和統計意義下的三種復雜性。由于目前處理器的處理速度要比訪問存儲器的速度快很多，分類性能在很大程度上取決于算法的訪存次數。理論分析中也常用訪存次數作為評判分類算法速度的依據。
（2）內存需求。分類算法為實現快速分類而建立的各種數據結構所占用的內存空間大小也是評價一個分類算法的重要標準。一般情況下，復雜數據結構可以加快檢索速度，但是對存儲空間需求很大，實際應用中必須在分類速度和內存需求之間作出權衡。極端情況下，過于復雜的數據結構將會使高速存儲器（如SRAM）無法容納，而不得不使用低速存儲器（如DRAM），這反而會影響分類速度。
（3）易于更新性。對于一些規則變化頻繁的應用場合（如RSVP路由器），要求分類算法有較好的規則更新性能，能夠支持快速的過濾規則更新。
另外，一個好的分類算法應該具有良好的擴展性，能夠用于大型分類規則庫的分類，也能夠適應分類規則維數擴展的情形。
2經典報文分類算法介紹
2.1種類
根據算法實現的特點，報文分類算法可以分為四類：①基于硬件和硬件優化的算法，如TCAM[9]、BV[10]、ABV[7]；②基于緩存和特殊數據結構的算法，如RFC[11]、Grid of Trie[12]、CrossProducting[12]；③基于計算幾何的算法，如FIS[13]、Gfilter[14]；④基于啟發式規則的算法，如EGTPC[15]、TSS[16]、HyperCuts[17]、HiCuts[18]、DCFL[19]。
2.2基于硬件和硬件優化的報文分類算法
該類報文分類方法主要利用一些特殊的硬件或硬件設備的某些特性（如并行性、流水性等）來實現報文分類。
（1）TCAM
TCAM(Ternary Content Addressable Memory，三態內容尋址存儲器)是一種全相聯（Fully Associative）的存儲設備，它的每一個位都可以存儲三種類型的值：0、1、X。其中“X”表示無關位，用來存取過濾規則中的掩碼。分類規則庫中的過濾規則可以逐項存取在TCAM中的相應位置。當一個報文到達時，TCAM將該報文頭部信息同時匹配內存中所有的過濾規則，從而得到所有匹配該報文的規則并從中選取代價最小的規則作為分類結果。
TCAM主要利用了全相聯硬件的并行性，從而加快了分類速度。但是它也有以下弱點：①TCAM的每一位實現需要10～12個晶體管，高于SRAM（4～6個晶體管），如此多的晶體管給主板設計帶來困難。②并行比較帶來高功耗。③對于現有的路由器設備需要添加額外芯片才能支持TCAM，其升級成本高。④對于范圍匹配的規則需要先轉換成前綴的形式，從而形成了同一規則的多份拷貝。
總體來說，TCAM是一種全硬件的分類方法，時間復雜度為O(1)，空間復雜度為O(N)，N為過濾規則總數。TCAM分類速度快但實現成本高，不適用于大型分類規則庫的場景。
（2）BV
BV(Bit Vector，位向量)算法是一種利用硬件位層次的并行性（Bitlevel Parallelism）來加速分類的算法。算法的主要思想是：假設各分類規則均由d個域組成，算法首先找到每一個域所對應的值域空間，并把它映射到一條坐標軸上；接著對分類規則庫中的每一條過濾規則，取其各維的值并用此值來對該維的值域坐標軸進行分割，從而將d條值域坐標軸分割成數目不等的小區間。例如，表1所示的過濾規則1（目的端口域的值為80）將“目的端口”值域坐標軸劃分為0～79、80、81～65 535三個區間；過濾規則2（目的端口域的值＞1 023）則將“目的端口”值域坐標軸進一步劃分為0～79、80、81～1023，1024～65 535四個區間。當對d條值域坐標軸都分割完畢后，需要計算每一條值域坐標軸上每一個小區間所對應的規則位圖。假設過濾規則庫由n條規則F1，F2，F3，…，Fn組成，則區間的規則位圖包含n位，每一位對應一條過濾規則。對于第i條值域坐標軸的第j個小區間所對應的位圖，若該位圖的第m位為1，則表示此區間落在規則Fm的第i個域所指定的范圍內；反之，若Fm的第i個域所指范圍不包含此區間，則區間所對應位圖的第m位為0。圖1描述了表1所示的過濾規則庫“源端口”值域坐標軸及其各區間所對應的位圖。表1包含的過濾規則將“源端口”對應的值域坐標軸劃分為0～22、23、24～1023、1024～65535四個區間。其中0～22區間對應的位圖為10011，說明此區間落在規則庫中第1、4、5條過濾規則所指明的源端口范圍內，不包含在第2、3條過濾規則所指的源端口范圍內。
當一個報文到達時，首先對其各維頭字段分別查找對應的值域坐標軸，找到該報文的各維數據分別落在對應值域坐標軸的哪個區間內，并且取出該區間所對應的位圖。最后對各維查找所取得的區間位圖進行邏輯與，從而得到此報文所滿足的過濾規則位圖，取所有滿足的過濾規則（即位圖中置為1的位所對應的規則）中代價最小的作為對該報文的分類結果。
BV算法的優點是查找速度較快、并行性好，時間復雜度為O(N)，N為過濾規則數；缺點是存儲需求大，空間復雜度為O(N2)。所以該方法擴展性不好，不適合大型規則庫，同時該算法對過濾規則的快速更新支持不足。當添加或刪除一條過濾規則時，需要修改所有值域坐標軸上的所有區間所對應的位圖，更新復雜度高達O(N2)。
（3）ABV
ABV(Aggregated Bit Vector，聚合位向量)算法是對BV算法的改進，其目的是進一步減少訪存次數以加速分類。ABV算法的時間復雜性仍然是O(N)，N為過濾規則總數。它比BV算法改進的只是線性復雜度前面的常數項，但是這種改進通常也要超過一個數量級。
ABV算法通過位圖聚類和規則重排兩種機制減少訪存次數。位圖聚類機制利用原區間位圖的稀疏性在每個區間位圖層次上又增加一個層次，即聚類位圖。聚類位圖中的每一位對應原區間位圖的一個塊，聚類位圖的某一位為“1”當且僅當它所對應的區間位圖塊中至少有一位為“1”。當一個報文到達時，ABV首先對各維區間的聚類位圖進行邏輯與，然后僅需要檢查邏輯與得到的結果聚類位圖中置為1的位所對應的原區間位圖的塊，從而減少訪存次數。
位圖聚類會導致假匹配（False Match）現象，在極端情況下非但不能減少反而會增加訪存次數。因此，引入規則重排機制來消除假匹配現象，而且重排后規則的位圖聚類效果更好。
2.3基于緩存和特殊數據結構的報文分類算法
該類報文分類方法主要是基于緩存技術和建立一些特殊的數據結構（如搜索樹、哈希表等）來實現報文分類的方法。
2.3.1Grid of Trie
Grid of Trie（網格樹）算法是一種基于搜索樹結構的報文分類算法，它主要解決二維前綴匹配的報文分類問題，常用于VPN、MPLS等根據源目的地址對進行分類的場景。算法的主要思想是把數據結構中的Trie樹（最簡單的形式就是二叉樹）擴展到二維。首先根據規則庫中的目的地址前綴構造一棵DestTrie，此樹中的每個節點都指向一棵源地址SrcTrie。該SrcTrie中不但包含過濾規則庫中與此DestTrie節點對應的源地址前綴，還應當包含此DestTrie節點所有祖先的源地址前綴。圖2（a）給出一個簡單的規則庫，圖2（b）指示根據圖2（a）規則庫構造的Grid of Trie。
當一個報文到達時，首先根據它的目的地址頭字段在DestTrie中作最長前綴匹配，再沿著DestTrie中最長前綴匹配得到的有效節點所指向的SrcTrie進行報文源地址字段的最長前綴匹配，并記錄沿途所經節點的最小過濾規則。此規則即為對報文的分類結果。
Grid of Trie算法查找速度快且穩定，時間復雜度為O(W)，W為最長前綴長度（對地址字段即為地址寬度）。然而，原始Grid of Trie算法（亦稱為SetPruning Tries算法）中DestTrie的每個節點不但要存儲自身的源地址前綴，還要存儲其祖先的源地址前綴，使得算法空間復雜度較高，達到O(N2)，N為過濾規則總數。
為了減少算法的存儲需求，提出了改進的Grid of Trie算法。它去除了SrcTrie中的冗余拷貝，使得每個目的地址前綴節點指向的SrcTrie中只包含規則庫中與此目的地址配對的源地址前綴，而不再包含其祖先的源地址前綴。通過引入轉向指針（Switch Pointer），使算法在保持時間復雜性不變的情況下，空間復雜性由O(N2)降為線性復雜度O(WN)。
Grid of Trie算法的另一個缺點是規則動態更新效率差，特別是引入轉向指針后使得快速插入和刪除過濾規則變得更加困難。
文獻[20]提出了一種方法可以將Grid of Trie算法由二維分類擴展到多維分類，方法是對源端口、目的端口、協議三個域組織成無沖突哈希表。哈希表中的每一項指向一棵源地址、目的地址前綴組成的Grid of Trie。查找時，首先對報文的端口和協議號字段作哈希查找，然后再沿著相應的Grid of Trie作進一步匹配。該算法的不足之處在于算法在基于規則庫中端口號和協議域不同的交叉組合數較少的前提下，當交叉組合數較多或過濾規則引入其他新域時，算法因建立大型哈希表和Trie樹可能會產生空間爆炸。
2.3.2CrossProducting
CrossProducting（叉級）算法是一種基于緩存策略的分類算法。算法的主要思想是：首先對報文頭部的各個域分別作最優匹配，并把各域匹配的結果級聯起來形成CrossProduct。可以證明對此CrossProduct最佳匹配的結果就是對報文最佳匹配的結果。因此，如果預先計算出過濾規則庫中所有規則域值的不同交叉組合CrossProduct所對應的最佳匹配規則，則可以在對不同域并行查找后通過一次哈希查表就得到報文的最佳匹配規則。
在實際應用中，經常把CrossProduct的分類結果緩存起來以加快查找速度。由于CrossProduct對應于一類報文，相對于單個報文信息的緩存，該緩存策略效率更高。
CrossProducting算法的主要問題是內存爆炸問題。在最壞情況下，該算法空間復雜度可達O(Nd)，N是過濾規則數，d為過濾規則維數。為了減少算法的存儲需求，提出了改進的按需CrossProducting算法。該算法不是一次建立并緩存所有的CrossProduct匹配規則表，而是當報文到來時，首先計算它的CrossProduct，并在緩存中檢索該CrossProduct的對應項。如果檢索命中，則得到報文的匹配規則；否則利用其他方法（如線性查找）在分類規則庫中檢索該報文的匹配規則，并把匹配結果連同該報文的CrossProduct一起更新緩存。按需CrossProducting算法減小了存儲需求和數據結構的初始建立時間，但是基于緩存的策略也使得算法的分類時間存在不穩定性。
2.3.3RFC
RFC(Recursive Flow Classification，遞歸流分類)算法是常用分類算法中速度較快的一種。它把對一個報文的分類分為多個階段實現，充分利用了硬件流水線的技術，具有很高的吞吐量。
RFC算法的主要思想是把報文分類問題看作是報文頭的S bits到T bits的classID之間的一個映射（T=log N且T<<S，N為分類規則總數）。映射分為多個階段完成，每個階段都將一個較大的集合映射到一個較小的集合（等價類）；每階段查找的結果位串都要短于查找的索引位串，稱為一次縮減；最后一個階段查找的結果即為該報文的classID。在RFC算法中，每個階段由一系列并行的查找組成，而不同的階段可以通過硬件流水線來實現。
RFC算法可以看作是CrossProducting算法的改進，它在輕微增加分類時間的代價下，一定程度上減少了CrossProducting算法的存儲需求。從本質上看，RFC算法不是一次形成所有域值的CrossProduct，而是先形成部分域值的CrossProduct即等價類，然后再由等價類一步步形成最終的CrossProduct。
RFC算法的主要缺點是存儲需求大，不能用于大型數據庫；不支持過濾規則的快速動態更新；預處理時間較長。
2.4基于計算幾何的報文分類算法
此類報文分類算法主要依據計算幾何理論和分類問題的幾何意義來設計和實現。
（1）Gfilter
Gfilter（幾何過濾器）算法是一種利用對幾何空間的遞歸劃分來實現分類的算法。算法的數據結構創建過程如下：輸入一個d維幾何空間x和一組分類規則H(x)，遞歸地建立此空間的查找數據結構D(d)(x，H(x))（初始時，x為整個規則空間，H(x)為規則庫中所有分類規則）。
首先把H(x)中的每一條規則h按如下原則劃歸到四種集合之一：①如果h和x空間上不相交，則丟棄h；②否則，若h覆蓋x，則h屬于集合cover(x)；③否則，若h在d維空間的某一維j覆蓋x，則h屬于集合FBj(x)，共有d個不同FBj(x)；④否則（h被x覆蓋或h與x交叉），h屬于集合cross(x)。如圖3所示，e∈cover(x)，a∈FB1(x)，b∈FB2(x)，d、 f∈cross(x)，d∈cover(y)， f∈cross(y)。
對一個落在空間x的報文p，它一定滿足cover(x)中的任何規則，因此對cover(x)僅需要記錄其中代價最小的規則。對于FBj(x)中的規則h，p的第j維數值一定落在h的第j維范圍內，所以p滿足h當且僅當p的其他d-1維數值也滿足h。這就變成了d-1維空間中同樣的問題。對于cross(x)中的規則，p∈x得不出任何有用的匹配信息，因此將空間x進一步劃分成m個同樣的子空間，并遞歸地建立子空間的查找數據結構。綜上，數據結構D(d)(x，H(x))包含：①cover(x)中代價最小的規則；②d個指針指向d-1維數據結構D(d-1)(x，FBj(x))，1≤j≤d；③m個指針指向m個子空間數據結構D(d-1)(yj，cross(x))，1≤j≤d，yi表示子空間。
當一個報文到達后，從整個空間所對應的查找數據結構開始遞歸搜索。每次搜索需要檢查d個d-1維的數據結構和一個子空間的數據結構，并從這些檢查返回的規則以及本空間cover集合保存的規則中選取代價最小的作為報文的分類結果。
Gfilter算法查找時間穩定、可擴展性強，能用于大型分類規則庫；缺點是算法復雜、預處理時間長、對規則的快速動態更新支持不足。
（2）FIS
FIS(Fat Inverted Segment Tree，扁平倒轉分割樹)算法的主要數據結構是FIS樹。它是一棵扁平、倒轉的分割樹。所謂扁平是指樹的層數很少，而倒轉則是指樹中的每個節點都有一條指向其父節點的指針。
在FIS算法中，每一條過濾規則都看作是對多維空間的一個分割，這些分割投射在各維坐標上將坐標軸劃分為一個個基本區間。算法首先把所有過濾規則在第一維坐標軸上投射，并根據投射結果構建一棵第一維空間的FIS樹，樹中的每個節點都含有一個規范集，規范集中存放與該節點關聯的分割規則。第一維空間FIS樹的每個有效節點均指向一棵第二維空間的FIS樹。該樹依據該節點規范集中的規則集合在第二維坐標軸上的投影來構建，然后依次遞歸建立各維FIS樹，根據最后一維空間建立的FIS樹的每個基本區間（葉節點）都包含匹配此區間的最優規則。因此對一個報文的搜索過程如下：先把該報文沿第一維空間FIS樹進行匹配，然后依次遍歷匹配路徑上節點所指向的第二維空間FIS樹；如此遞歸，直到得到最后一維空間FIS樹中基本區間所保存的過濾規則作為候選規則。所有這些遞歸匹配得到的候選規則中代價最小的就是對報文的分類結果。
FIS算法的優點是：①擴展性好，可用于大型規則庫；②改進的FIS算法可以支持規則快速更新，但是會少量延長分類時間（最多兩倍）；③可以通過FIS樹的層數調節實現查找效率和內存需求的平衡。缺點是算法復雜、預處理時間長。
2.5基于啟發式規則的報文分類算法
此類報文分類算法主要根據分類規則的結構和統計信息得出一些啟發式規則，并利用這些啟發式規則設計相應的分類算法。
（1）EGTPC
EGTPC(Extended Grid of Trie with Path Compression，帶路徑壓縮的擴展網格樹)算法主要基于如下觀察：盡管過濾規則庫中的規則很多，但是一個報文根據源、目的地址對所匹配的過濾規則卻很少（通常匹配5條左右，最多不超過20條）。因此，如果對到達的報文首先進行源、目的地址的二維分類，然后再在少數匹配規則中根據其他維信息進行線性查找就可以得到一個報文的最佳匹配規則。
因為Grid of Trie是較好的二維分類方法，EGTPC算法基于它作了一些改進以應對多維分類的需要。算法首先根據目的地址前綴建立一個Trie；樹中的每個有效節點都指向一棵源地址前綴Trie；源地址前綴樹中的每個有效節點都記錄了所有目的地址精確匹配，而源地址是該節點自身或其前綴的規則集合。為了避免回溯查找，算法引入了跳轉指針（Jump Pointer），在源地址Trie的每個失敗節點均利用跳轉指針指向下一棵可能包含正確匹配規則的源地址Trie。EGTPC算法利用跳轉指針取代Grid of Trie算法中的轉向指針，目的是使得查找能夠遍歷到Trie中源、目的地址前綴匹配的所有規則，而不再像Grid of Trie算法僅僅尋找源、目的地址最長前綴匹配的規則。此外，算法對Trie結構采用了路徑壓縮技術[20]去除了樹結構中的單分支路徑，使得樹節點的數目顯著減少，節省了存儲空間。
EGTPC算法的分類流程如下：當報文到來時，首先根據其源、目的地址對信息搜索Trie；搜索結束后，再對Trie中記錄的少數規則進行線性查找，從而確定該報文的最佳匹配規則。EGTPC算法的時間復雜度為O(W2)，空間復雜度為O(W2)，W為地址寬度。它能用于大型分類數據庫的檢索，但是算法的初始數據結構建立時間較長且數據結構不宜改動，因此算法不適合過濾規則快速變化的場景。
（2）TSS
TSS(Tuple Space Search，元組空間查找)算法的出發點是：盡管規則庫中不同前綴的數目很多，但是不同前綴長度的數目卻很少，因此不同前綴長度的組合數也很少。定義元組(Tuple)為一個不同域前綴長度的組合。對于地址域，前綴長度非常直觀，而對于范圍表示的端口域，規定其嵌套深度作為它的前綴長度。將規則庫中的分類規則依據其各域的前綴長度分布劃歸到相應的元組，每一個元組中的所有分類規則都具有同樣的形式（各個域的比特位長度都相同）。因此，將所有屬于同一元組的過濾規則組成哈希表，將過濾規則中的特定比特位提取出來組成該過濾規則的哈希索引值。
當一個報文到達時，由于元組數目很少，可以線性搜索每一個元組。查找哈希表得到該元組中的匹配規則，所有元組返回的匹配規則中代價最小的規則就作為報文的分類結果。此外，還可以采用一些預處理技術來減少需要搜索的元組數目，從而進一步提高分類速度。
TSS算法平均查找時間較快，而且算法能很好地支持過濾規則的快速更新，但是該算法查找時間不穩定。當規則的前綴長度聚類性不好時，算法效率較差，并且算法擴展性不強，不能應用于大型分類規則庫。
（3）HiCuts
HiCuts(Hierarchical Intelligent Cuttings，層次化智能切分)算法利用分析規則庫結構信息得到的啟發式規則建立一棵決策樹，從而實現對報文的分類。該算法把每一條過濾規則看作是多維空間的一個超矩形（算法要求各維規則域均以范圍形式表示），選擇一個決策就意味著對這個多維空間從某一維上進行一次切分。因此決策樹的每一個中間節點都關聯如下信息：①該節點所覆蓋的各維范圍；②對該節點從哪一維上進行切分以及切分的塊數；③與該節點覆蓋范圍相交的過濾規則集合。初始時，根節點對應所有過濾規則，覆蓋整個規則空間，然后對決策樹的各節點遞歸地進行切分，切分出的節點作為原節點的子節點。當一個節點所包含的過濾規則數小于某個閾值(Binth)時就停止對該節點的進一步切分。對每一個中間節點選擇從哪一維進行切分以及切分的塊數可以根據一定的啟發式規則確定。圖4（a）是一個簡單的規則庫，對它分析后建立的決策樹如圖4（b）所示（設Binth=2）。
當報文到達后，首先遍歷決策樹，找到對應的葉節點，然后線性搜索葉節點中的過濾規則，得到報文的分類結果。HiCuts算法的主要缺點是存儲需求較大，另外算法建立數據結構的預處理時間比較長，因而對過濾規則的動態更新支持不足。
（4）HyperCuts
HyperCuts（超切分）算法是對HiCuts算法的改進，目的是減小決策樹的深度，加快搜索速度。HiCuts依據局部最優的原則切分一維數據構造決策樹，而HyperCuts可以同時選擇多維數據來分割報文狀態空間，構造決策樹，從而大大減小了決策樹的深度。對每一個中間節點從哪些維進行切分以及各維切分的塊數都是根據一定的啟發式原則確定。切分塊數越多，則決策樹深度越小，分類速度越快，但是對存儲空間的需求就越大。圖5描述了對圖4所示的規則庫構建的HyperCuts決策樹，可見采用HyperCuts算法決策樹的深度降低為1。
原始HyperCuts算法存儲需求很大，因此提出了一系列改進措施：①節點融合；②去除冗余規則；③節點覆蓋范圍壓縮；④公共過濾規則上移。這些措施有效地緩解了算法的空間需求。
HyperCuts算法的不足之處有：①數據結構復雜，預處理時間較長；②對于某些分類規則庫維數很少的情況，算法性能較HiCuts無太大改進。
（5）DCFL
DCFL(Distributed Crossproducting of Field Labels，域標簽分布式叉級)算法的設計主要基于以下啟發式規則：對一個給定的報文，其各維數據所匹配的過濾規則的不同域值數目是有限的，因而這些域值的交叉組合數目也是有限的。DCFL算法賦予過濾規則各個域的每一個不同域值一個局部唯一的標簽(Label)，把一條過濾規則各個域的標簽級聯起來就形成了該過濾規則的標簽。算法分為單域并行查找和標簽會聚兩個階段。首先對一個報文的各維數據分別作單域范圍內的匹配，得到單維匹配的標簽集合；然后把這些單維匹配的標簽集合按照一定順序送到相應的會聚節點進行標簽會聚，會聚節點中經過預處理過程已經存儲了有效特定域的不同域值標簽的Crossproduct集合。對會聚節點輸入不同域標簽的每一個交叉組合，當且僅當它屬于該會聚節點所存儲的Crossproduct集合時，才能通過此次標簽會聚進入下一個會聚節點。最后一個會聚節點的輸出即為報文滿足的所有過濾規則的標簽形式，從中選擇代價最小的規則作為對該報文的分類結果。
DCFL算法通過分布式地而非一次性地形成各個域不同值的Crossproduct，從而避免了CrossProducting算法的空間爆炸問題。該算法的擴展性良好，在過濾規則維數增加或過濾規則庫規模增大時仍能保持較快的分類速度；同時該算法融入并行性和流水性等特征，比較易于硬件實現。DCFL算法的主要問題是它是面向硬件特性設計的，單純使用軟件實現時分類性能會有所下降。
3評測和比較
表2是本文所涉及的常用算法中最壞情況下時間復雜度和空間復雜度表達式的匯總。為描述方便，N表示規則庫中規則的數目，W代表各維中最長的前綴長度，d代表維數目，memwidth代表存儲器的帶寬，L代表FIS算法中樹的深度。表2文獻中部分算法最壞情況下時間復雜度和空間復雜度表達式
算法最壞情況下的時間復雜度最壞情況下的空間復雜度
線性查找NN
為進一步比較具體算法的實際性能，本文選擇幾種典型算法[21]在虛擬環境下（IntelCeleronD315 2.26 GHz，256 MB DDR400，Fedora 2Linux）進行評測。評測主要圍繞算法的平均查找時間、初始數據結構建立時間以及數據結構存儲需求三個指標展開。過濾規則庫和分類報文均通過ClassBench[22，23]工具根據真實規則庫的分布特點生成。為了充分測試所選算法在多維報文分類情況下的性能，使所生成規則庫的每條規則均是有效的五維規則，然后依據每種算法不同的輸入格式進行轉換。測評的結果如表3所示。
EGTPC算法是基于啟發式規則的一個典型算法，其主要數據結構是一棵兩維的搜索樹，查找過程也主要是搜索這個兩維樹結構。因為樹的深度相對固定（由地址最長前綴長度決定），所以EGTPC算法的查找時間受規則增加的影響不大，但是初始數據結構建立時間和平均消耗的存儲空間隨規則的增加而顯著增加。
ABV算法是基于硬件BV算法的一個改進算法。BV算法的瓶頸集中在規則庫對應位圖向量的讀取和比較上。ABV通過聚合部分規則來減少這個位圖向量的長度，從而減輕讀取位圖向量的壓力，達到比BV算法更優的性能。但是由于連續規則的聚合，會導致假匹配的現象，從而限制了其性能。當聚合情況不好時，算法性能甚至不如BV算法。在聚合時需要對規則庫的規則進行重排，以保證聚合后的性能。從實驗中可以看出，當規則規模不是很大時，查找的時間接近。但當規則達到一定規模時（大于50 KB時），由于聚合后的位圖向量也將變得很大，讀取該位圖向量的開銷增加，算法的查找性能急劇下降，同時算法初始化時間開銷和所消耗的存儲空間也隨規則的增多而增加。從實驗結果來看，ABV算法的查找性能不如EGTPC算法，這是因為ABV算法是使用硬件實現的算法，其查找性能取決于存儲器的帶寬和硬件的并行性。而用軟件實現時，無法利用這些優良的硬件特性使算法性能大大降低。
RFC算法是基于特殊數據結構的一個典型算法，其基本思想來自于CrossProducting算法。CrossProducting算法會出現內存爆炸的情況，RFC通過分階段將規則庫的規則映射成若干等價類集合來避免這種情況。從本文實驗看出，RFC算法的內存消耗量是巨大的，并且為建立用于分階段查找的數據結構的時間開銷也較大。RFC的優勢在于該算法是分階段匹配的，很易于采用流水線的方法實現，從而達到非常優秀的查找性能和吞吐量。由于建立時間比較耗時，RFC算法適用于規則庫變化不頻繁的應用環境中。
從以上典型算法的實驗可以看出，不同算法具有各自的優勢和缺陷，因此需要根據實際應用環境選擇合適的算法，或者根據不同的應用要求將大規模規則庫分塊，在不同的塊使用不同的算法以滿足對應的應用需求。表4是本文總結的各種算法的推薦應用環境。
表4算法的推薦應用環境
算法推薦應用環境算法推薦應用環境
TCAM中小規模的規則庫，查找速度要求高，對分類器的功耗限制小FIS中大規模規則庫，查找速度要求不高，規則庫更新較頻繁
BV中小規模數據庫，查找速度要求較高，規則庫更新不頻繁EGTPC適用于擁有相同源地址、目標地址對的規則很少的大規模規則庫，查找速度要求不高，規則庫更新不頻繁
ABV中等規模數據庫，查找速度要求較高，規則庫更新不頻繁TSS中大規模規則庫，查找速度要求不高，規則庫更新頻繁
Grid ofTries兩維大規模規則庫，查找速度要求較高，規則庫更新不頻繁HiCuts中小規模規則庫，查找速度要求不高，規則庫更新很少
CrossProducting小規模規則庫，查找速度要求高，有大容量用于存放前綴組合的緩存空間，規則庫更新較頻繁HyperCuts中小規模規則庫，查找速度要求較高，規則庫更新很少
RFC小規模規則庫，查找速度要求高，規則庫更新不頻繁DCFL中等規模規則庫，查找速度要求高，規則庫更新較頻繁，能適應規則維數增減的情況，該算法硬件實現才能具有較好的性能
Gfilter中大規模規則庫，查找速度要求不高，規則庫更新不頻繁
4總結和展望
報文分類在現代網絡中具有廣泛的應用，是許多網絡關鍵技術的基礎。已有的研究表明，實現高速多維報文分類是十分困難的，它已成為網絡QoS的新瓶頸。目前已有的分類算法各有自身的優勢和缺陷，尚未有一種分類算法可以很好地滿足所有應用場景。在文獻[17]中指出，核心路由器、邊緣路由器、防火墻等設備中的規則庫均具有各自不同的特征，因此應該根據分類規則庫的結構和統計特性（規則庫規模、維數、動態更新性等）選用合適的分類算法。
未來的報文分類技術研究和報文分類算法設計具有如下發展趨勢：
（1）分類算法設計將充分利用分類規則的結構和統計特性。大量研究表明，分類規則庫中過濾規則的各維數值并不是完全隨機分布的，是有一定規律可循的，充分分析并利用這些規律，可以使分類算法的空間和時間復雜度顯著降低。
（2）分類算法的設計將更多地關注已有算法的融合。目前已有算法各有自己的優勢和特點，特別是有些一維、二維分類算法已經具有很好的性能。因此在設計多維分類算法時，應該考慮如何將這些算法有效利用起來。例如DCFL算法在單維匹配時就充分利用了目前已有的各種單維匹配算法。
（3）將分類算法的可擴展性研究放到重要的地位加以考慮。算法的可擴展性包括規則庫規模的可擴展性以及分類規則維數的可擴展性。隨著互聯網業務量的激增，分類規則庫的規模在不斷擴大，好的分類算法應該滿足當規則數目增多時對報文分類處理的時間和空間性能不會下降很快。此外，目前的規則很少規定經典五元組（源地址、目的地址、源端口、目的端口、協議號）之外的域，但是新的服務和管理策略將越來越多地用到其他一些字段（如TCP Flag和ICMP Number）來分類報文。所以，好的算法應能很好地適應規則維數增多的情況。
（3）報文分類問題的一些分支問題也在成為新的研究熱點，如報文分類Benchmark[23]的設計。
注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
