1 RFC算法
1.1 RFC算法介紹
RFC(Recursive Flow Classification)算法[1]是一種多元IP分類快速查找算法，通過對實際的過濾規則資料庫的考察，發現資料庫中的過濾規則都有内在的結構和備援度，這個特點可以為分類算法所利用。
RFC算法的主要思想是将IP分類問題看成一個将標頭中的S比特資料到T比特的classID的一個映射（T=logN且N<<S,N是過濾規則的總數）。如果預先計算出標頭中的這S位共2s種不同情況中每種情況所對應的classID值。那麼每一個包隻需要一次查表，即一次記憶體通路就可以得到相應的classID,但是這樣會消耗極大的空間。RFC的思想是映射不是通過一步來完成，而是通過多個階段（phase）完成，如圖1.1所示。每個階段的結果是将一個較大的集合映射成一個較小的集合，稱其為一次縮減（reduction）。RFC算法共分P個階段，每個階段由一些列的并行的查找組成。每個查找的結果值比用于查找的索引值要短（故稱為一次縮減）。
圖1 RFC的基本構思 圖2 一個四階段的RFC縮減樹
圖1.2中建立了一種4階段的縮減樹，對IP包查找過程如下：
1）在第一階段（Phase 0），標頭中的K個域被分成若幹個塊(chunks)，每個塊被用來作為并行查找的索引；
2）後面的幾個階段，每次查找記憶體的索引值都是由前幾個階段的查找結果合并而成的。一種簡單的合并辦法就是将查找結果按二進制串連接配接起來(concatenation)，
但還有更好的方法可以節省空間；
3）在最後一個階段，查找的結果得到一個值。由于我們進行了預先的計算，這個值就是該包對應的classID。
1.2 RFC算法性能分析
RFC算法受到兩個參數的影響：
1）選取的階段的數目P
2）在給定P的情況下,"縮減"樹的形狀.也就是後面的階段的索引值從前面哪幾個階段的查找結果進行合并。
在給定P的情況下,給出一種嚴格的判定方法來選擇最優的縮減樹很困難。[1]中給出了兩種啟發性原則：
1)盡可能合并具有一定“相關性”的塊。如我們盡可能早的将同一個IP位址的兩個塊進行合并。因為具有“相關性”的兩個塊往往在同一條規則或者在少數幾個規則中
集中出現。盡早對其進行合并，可以避免後續合并産生不必要的擴充；
2)在不引起記憶體激增的情況下.盡可能合并多的塊。
在P和縮減樹固定的情況下，随着過濾規則樹N的增加，消耗的記憶體量也增加。同時，對于同樣的過濾規則資料庫，P=3比P=4消耗更多的記憶體，但是查找速度前者比後者要快。
RFC算法的優點：(1)易于并行處理，處于同一階段的預處理表和交叉乘積表可被并行地索引，處于不同階段的表也可被并行的索引，這些表各自獨立，處于不同的存儲單元。(2)與其他算法相比，更适用于實際的網絡中。
RFC算法的缺點：缺乏一般性，因為它與分類器的結構有關，是以需要針對不同的分類器來進行微調(tuning)才能達到理想中的最佳工作狀态。一般的解決方法是在算法設計時便留有許多的參數供日後設定，像在RFC算法中所需要的階段數，每一階段中所做的化簡比例等都是可以在執行時期設定的。
2 Set-prunning trie
2.1 Hierarchical Tries
分層查找樹算法就是将分類字段的每一個維分成一層構造一個分層查找樹，實際上就是對一維查找樹的簡單擴充，使用遞歸方式來生成分層查找樹。基本思想是：設一個分類器C={Rj}有k個域，如果k>1，開始建構第一維的查找樹，将其稱之為F1-trie，它所對應的是分類器中每一條規則第一個域的字首集{Rjl}。F1-trie中的每個結點表示一個字首front，然後在front處進行遞歸建構一個(k—1)維的分層查找樹Tp。字首節點front使用“下一級查找樹的指針next"指向下一級分層樹Tp。由表2.1的規則庫得出的分層查找樹如圖2.1所示。
假設D是樹中一個結點，如果D’是D的字首，一般稱D’是D的祖先。如果D’是D的最長字首，則稱D’是D的最小祖先。
分類過程：進入分類算法的IP封包D(Dl，D2，⋯，Dd)，分層查找樹算法首先根據Dl在F1-trie樹上進行周遊，進而找到Dl的一條最佳比對字首，記下最後一個比對結點為Z，然後沿着“下一級查找樹的指針next”繼續周遊(Z—1)維的分層查找樹，記錄下這條路徑上所有比對的規則。接着要回溯到Z的最小祖先Z’，所謂的最小祖先就是指設Z是樹中一個結點，如果Z’是Z的最長字首，則稱Z’是Z的最小祖先。繼續沿着Z’的“下一個查找樹的指針next”進行周遊，直到Z節點的所有祖先都被周遊一次為止。最後，選擇比對規則中優先級最高的規則為進入分類封包的最佳比對規則。如圖給出了二進制組D(00l，110)的分層查找樹，其中虛線表示整個查找的過程。
表2.1 規則庫執行個體 圖2.1 2-D Hierarchical Tries執行個體
該算法的優點是直接、簡單、易于硬體實作，但是由于分類維數的增加整個算法的回溯查找時間就随之增長，是以不利于規則維數的擴充性，同時也不法直接支援範圍比對。
2.2 Set-pruning trie
由于分層查找樹算法的一些局限性，後來就提出了一種集合歸并查找樹算法，在分層查找樹的算法上進行了改進，該算法主要是解決了分成查找樹算法中多次回溯的問題，提出了通過對多元分層查找樹中的某些結點進行多次複制的解決方案。下面介紹一下在查找過程中比對l失敗情況下，如何進行節點規則的複制。首先假設T(Z)是表示節點Z所指向的查找樹，如果v對應字首s，查找樹T(D)中沒有以sl開頭的串，那麼節點v則表示T(Z)中比對位元組l失敗的結點。再假設Z’是Z的最小祖先節點，它所指向的下一層查找樹有以s1開頭的字首串，假定是在結點u上。如果結點u有左兒子，并且對應某條規則，那麼就把結點u的左兒子複制到結點v上，作為結點v的左兒子；否則對結點u重複以上操作。但是如果不存在這樣的結點u，就無需對結點進行複制。比對2失敗情況下的複制結點方法與上述方法一樣。最後在查找過程中，記錄下比對優先級最高的那條規則。
如圖2.2給出了二進制組P(001，110)的集合歸并查找樹，其中虛線表示查找的過程。
圖2.2 Set-pruning trie執行個體
通過對多元分層查找樹中某些結點進行多次複制，集合歸并查找樹算法的性能與分層查找樹算法相比，減少了多元分層的層次，提高了分類查找的效率。但是由于多次複制結點使得所需存儲空間增大，也不利于規則維數的擴充性。
3 Grid of trie
文獻[3]介紹了種子算法Grid of Tries和Crossproducting算法。這節主要介紹Grid of Tries算法，應用決策樹方法解決關于源位址和目的位址字首對的包分類問題。
如果将資料結構中的Trie of tries從一維擴充到二維,就形成Grid of Tries[3]。以表3.1中的資料庫為例來說明這個擴充過程。先不考慮過濾規則資料庫中源IP位址，根據過濾規則資料庫中目的位址字首構造一棵Trie of tries（稱為Dest-Trie樹)。這個目的字首Trie樹中每個節點，如果在資料庫中存在其對應的目的位址字首，則會指向一棵源位址Trie樹（稱為Src-trie樹)。否則相應的指針為空（如圖3.1中的空心圓圈所示)。
Grid of Tries算法在查找過程中是分成兩步的。第一步是通過對目的Ip位址做最長比對字首，然後再通過查找對應的源位址Trie樹得到代價最小的過濾規則。這意味着,任意一個Dest-Trie樹中的節點不但包含過濾規則資料庫中與該節點對應的源位址字首，還應當包含該目的字首的“字首”（即它在Dest-Trie樹中的祖先)所有的源位址字首，由此建立的Grid of Tries樹如圖3.1所示。
以上建立的Grid of tries樹是Trie樹的簡單擴充，其時間複雜度為O(W)。但是很明顯，在記憶體方面，它存在着極大的浪費，每個Dest-Trie節點不但存儲它自身的源位址字首，還存儲其祖先的源位址字首。在最壞情況下，其空間複雜度可達到O(N2)。
一種改進的辦法就是去掉這些多餘的拷貝，每個目的位址字首隻包含在過濾規則資料庫中與該目的位址配對的源位址字首，由此我們得到一種改進的Grid of tries樹。當去掉備援拷貝之後，查找一個目的—源位址對對應的最小代價的classID，不僅要從目的位址的最長比對字首所指向的Src-Trie樹中進行搜尋，還必須對該目的位址的最長比對字首的祖先所指向的Src-Trie樹中進行搜尋，從搜尋所經過的路徑中找出代價最小的過濾規則的classID，這使得時間複雜度上升到O(W2)。
一個巧妙的解決方法是引入轉向指針，即通過預處理将Src-Trie樹中的空指針指向其Dest-Trie樹的某個祖先對應的Src-Trie中的節點，使得在查找過程中沿着最長比對路徑能夠盡可能的前進。此外，為了確定算法的正确性，還必須保證目的-源IP字首對中字首長的節點，對應的代價也小（即IP字首比對越精确代價越小)，這些都是通過預處理完成的。經過第二次改進的Grid of tries樹見圖3.2所示。
根據該圖，對一個包，查找最小代價過濾規則的過程如
下：先對目的位址做最長字首比對，然後沿着目的位址最長比對字首所指向的Src-Trie根據標頭的源位址沿着0、1指針（或者轉向指針）盡可能的前進，直到無法繼續前進為止，沿途經過的結點中存儲的過濾規則代價最小的過濾規則所對應的classID即是其分類的classID。此時算法的時間複雜度為O(W)空間複雜度為O(NW)。
GOT算法還可改進。由于DT僅用于一維最長比對字首搜尋，是以可采用更高效搜尋方法。實際中可将總搜尋次數降低到logw ＋w。另一種改進是采用多比特樹替代單比特ST樹，使ST的深度從w減少到w/m(m為比特數)，故查找時間可降為O(logw＋w/m)。但所需空間将從2Nw增加到Nw2m/m，是以m需折衷選擇。此外，算法需要較多的預處理時間。通過擴充，GOT還可支援範圍比對，與CP算法結合也可實作多元的分類，但最壞情況下的性能無法保證。
表3.1 規則庫執行個體 圖3.1 根據表3.1建立的Grid of trie 圖3.2 改進過的Grid of trie
4 Cross-Producting算法
Cross-Producting算法可實作對多元的任意規則的快速比對，其基本思想是以犧牲空間為代價換取時間複雜度的降低。CP算法先在每一維上分别進行比對，把結果連接配接起來形成交叉乘積，在乘積空間中直接映射到最佳比對。CP算法查找時間很短，但最壞情況下乘積空間巨大(O(N k))，如50條規則需約1.5M空間。一種改進的On－Demand CP算法采用了緩存(Cache)技術降低空間的需求，使之能用于更大規模的規則庫，但其最壞情況下的搜尋時間得不到保證。
Cross-Producting的Cache政策是基于對過慮規則中各域值的交叉組合的“緩存”，每一個交叉組合對應一類IP包，是以用少量的Cross-Producting就可以代表相當數量的一類IP包。在Cross-Producting中表現出的局部性，也相應好得多，Cache的效率也高得多。
Cross-Producting算法是先根據標頭H不同的資料域分别做最長字首比對，可以證明将各個域的最長字首配的結果連接配接起來産生的Cross-Producting所對應的最佳過慮規則也是H的最佳比對過濾規則。如果預先計算出所有的Cross-Producting所對應的最佳比對規則，那麼就可以隻需要先分别對各個域分别做最長字首比對，然後通過一次查表(假定采用的Hash表不發生沖突)就可以得到最終結果。而且分别對不同的域查找其最長字首的比對，在硬體上非常容易進行并行處理。
但在極端情況下，Cross-Product可能會産生記憶體爆炸問題，解決辦法是采取和硬體Cache相類似的思想(并不将所有的Cross-product的最佳比對過濾規則都存起來(而是固定實際存儲的最佳比對過濾規則的數量（類似一個固定大小的硬體Cache，稱其為軟Cache，軟Catche的内容是動态更新的。當一個標頭H到達的時候，先對其按照各自的域得到最精确比對，然後将不同域的查找結果連接配接起來(進行Hash查找）。在絕大部分情況下，都能夠成功（稱為cache hit)。在不成功的情況下(說明相應的cross-product尚不在cache中(此時需要進行計算，得到最佳比對字首的cross-product，同時，根據某種置換政策将軟Cache中的一個不常用的cross-product換出(換入目前的cross-product)。
5 Bit Vector
5.1 Parallel BV
Parallel BV(Parallel Bit Vector or Bit Vector Scheme)算法[2]，由Lakshman和Stiliads提出。作者假設所有規則已經按優先級(Priority)排序。對于每維，N條規則最多能定義2N+1個基本間隔。每維每個基本間隔都為之定義一個N位的位向量，其每位對應一條規則。在構造每個位向量時，其所有位均被初始化為“0”，然後将該向量中所有與該基本間隔交疊的規則對應的位都置為“1”。一旦所有位向量和d個資料結構計算完畢，查找也變得的簡單。由于每維持有一個資料結構，各維查找可以獨立進行，各找到一個位向量，待各維查找均己完畢，共找到d個位向量。接着，d個位向量執行“與”(AND)操作，得到一個最終的位向量。此位向量中，所有“1"位對應之規則均為比對規則，而最高一個“1"位對應之規則具有最高優先級，為最佳比對。
該算法的查找時間為O(logN)，記憶體需求為O(n2)。該算法适于硬體實作。令W表示記憶體接口寬度，則通路一個N位向量需要
次通路。
5.2 ABV
ABV(Aggregated Bit-Vector)算法[5]，通過對規則集的統計觀察，對ParallelBV算法加以改進。ABV将所有規則轉化成字首，和TCAM一樣導緻規則集的膨脹。一開始，ABV向量的構造和Parallel BV向量方法相同。作者充分利用真實規則集與輸入包相比對的規則個數一般是5或更小這條性質，該性質導緻N位向量稀疏。為減少記憶體通路次數，ABV将N位向量分割成A大塊(Chunk)，每個大塊有
位。進行壓縮時，塊中全為“0”則值為“0”，否則值為“1”，值為“l”的塊在查找時需要恢複。
該算法查找過程如下。每個獨立查找傳回一個A位的ABV向量，然後将這些ABV向量相“與"，合并成一個ABV向量。ABV向量中每個“1”位，需要恢複成原向量，重新執行“與”操作。直到所有向量中所有位對應的是一條規則。用真實規則仿真，ABV算法的記憶體通路次數比Parallel BV算法小4倍。使用模拟規則仿真，ABV算法的記憶體通路次數比小20倍。
6 TCAM算法
CAM是Content Access Memory的縮寫，是一種專用存儲器件，可實作快速大批量的資料進行并行搜尋。原先的CAM是一種單純的二進制器件，每一個比特位隻能存儲0或1這兩個二進制數，而最近幾年出現一種可以存儲三種值的三态CAM，它的每個存儲位置可存儲O、1或X這三種值。TCAM算法就是将所有的規則使用TCAM(三态CAM)硬體來實作，進而實作并行比對，該算法的空間複雜度為O(N)，時間複雜度為O(1)。TCAM算法以變量／掩碼形式存儲一個w比特的項。其中，變量和掩碼都是w比特長，這種表示形式和IP位址表示方法相類似，這也使得TCAM算法在IP路由查找中得到了比較廣泛的應用。在IP封包分類問題，如果W=64，那麼對于二維IP封包分類規則(61.136.*)、(202.117.112.*)，在TCAM中存儲形式為(61.136.0.0、202.117.112.0、255.255.0.0、255.255.255.0)。在分類的時候，先提取相應參數域，然後在連接配接各個參數域所組成的TCAM輸入值，查找在掩碼位置值為l的二進制位與變量相比對則就找到比對位。
該算法分類速度極快，但是卻需要增加一個容量為dNw的CAM存儲器，由于這種存儲器價格較高，而且耗電量大，又不能直接支援範圍比對，因而對規則數、規則數量以及每維寬度的可擴充性都比較差，僅僅适用于規則量較小的的IP封包分類。
6 各種算法性能比較
| 算法名稱 | 時間複雜度 | 空間複雜度 | 應用場合說明 |
| RFC | P(階段數) | np | 分類速度快，存儲空間和維數相關,記憶體消耗多，可能引起記憶體爆炸，需要并行計算能力 |
| Hierarch trie | wd | ndw | 維數不超過二，規則較少 |
| Set-pruning tries | dw | nd | 維數不超過二，規則較多 |
| Grid of tries | wd-1 | nw | 空間效率高，适合數量大的規則資料庫，規則更新複雜度高，二維分類 |
| Cross-producting | dw | nd | 可并行實作，高吞吐率，記憶體需求過大，指數增長 |
| Bit Vector | logN | n2 | 适于硬體實作 |
| TCAM | 1 | n | 速率極高，成本高，支援維數較少 |
說明：本文主要參考了機械工業出版社《高等計算機網絡--體系結構，協定機制，算法設計與路由器技術》一書，在此特别聲明。