流分類算法的分類及比較

流分類算法的分類及比較

流分類算法可以根據(jù)不同的原則進(jìn)行分類，本文根據(jù)對多個區(qū)域查找之間的關(guān)系把現(xiàn)有的流分類算法分成3類。

1) N表示規(guī)則數(shù)目，

2) d表示維數(shù)，

3) w表示每一維的寬度。

多維查找轉(zhuǎn)換為一維查找的算法

該類算法的特點就是把流分類查找的各個區(qū)域連接起來組成一個查找關(guān)鍵字，從而把多維查找的問題轉(zhuǎn)化為一維查找問題。在基于哈希表進(jìn)行查找的流分類器以及使用TCAM的流分類器中經(jīng)常使用到這種方法。缺點是得到的查找關(guān)鍵字很大，而且由于多維合成了一維，無法利用規(guī)則中各維內(nèi)部的共性進(jìn)行優(yōu)化設(shè)計。此類算法的代表是多元空間查找算法(Tuple-Space-Search)[1]，基本思想是把流分類查找問題分解為多個精確匹配問題。

首先把d維的規(guī)則映射到一個具有d個分量的空間中，空間的第i個分量表明規(guī)則第i維的前綴長度，這樣各維前綴長度都相同的規(guī)則就對應(yīng)同一個空間，把它們存儲在同一個哈希表中。查找時對所有哈希表進(jìn)行精確匹配查找。這種算法的空間復(fù)雜度為O(N)，時間復(fù)雜度由需要訪問的哈希表數(shù)目決定，使得查找的時間復(fù)雜度不能確定。在最糟的情況下，空間數(shù)目可能達(dá)到O(wd)，使得查找時間不能接受。更新速度很快，只需要一次哈希訪問的時間。實際上許多知名硬件廠商在設(shè)計自己的流分類實現(xiàn)方案時都采用了哈希技術(shù)。

相關(guān)區(qū)域查找算法
這種算法的特點是前一個區(qū)域的查找結(jié)果會影響到隨后要查找的區(qū)域的路徑，主要優(yōu)點是可以使用相對簡單的生成樹結(jié)構(gòu)，缺點是要想達(dá)到較快的查找速度就需要對樹的結(jié)構(gòu)進(jìn)行復(fù)制或者在數(shù)據(jù)中加入鏈路信息，這樣就會增加存儲器容量，也會使更新更慢。另外大量對存儲器的訪問都是互相依賴的，導(dǎo)致了不可預(yù)測的延遲。此類算法的代表是分層查找樹(Hierarchical Tries)，集合歸并查找樹(Set-Pruning tries)[2]，查找樹網(wǎng)格(Grid-of-tries)和智能分層查找樹(Hierarchical Intelligent Cuttings，HiCuts)[3]。分層查找樹從d維中任取一維生成第一級二叉樹，再從剩下的d?1維中任取一維作為第二維，對該二叉樹中每一個與規(guī)則表中第一維匹配的結(jié)點，按照它的第二維建立第二級二叉樹，重復(fù)上述過程，直到完成每一維的處理。分層查找樹的空間復(fù)雜度為O(Ndw)，時間復(fù)雜度為O(wd)。它簡單，容易實現(xiàn)，但是查找較慢，并且更新也不快。集合歸并查找樹是對分層查找樹的改進(jìn)，通過把前綴長度小的結(jié)點對應(yīng)的子樹復(fù)制到所有前綴長度大于它的結(jié)點的子樹上，如果某個結(jié)點出現(xiàn)規(guī)則重復(fù)，則取優(yōu)先級高的規(guī)則。這個過程是在所有子樹上遞推進(jìn)行的。查找時只需要依次找到所有樹上的最長匹配，就能找到相應(yīng)的規(guī)則。時間復(fù)雜度為O(dw)，空間復(fù)雜度為O(Nddw)，可見是以增大存儲空間來減少查找時間，擴展性也較差。查找樹網(wǎng)格是在分層查找樹的基礎(chǔ)上，給某些結(jié)點增加一個轉(zhuǎn)移指針b(0或1)，它指向另一個子樹的一個結(jié)點。

存在從子樹Ty的Y結(jié)點到子樹Tx的x結(jié)點的轉(zhuǎn)移指針的條件是：

1) Tx和Ty是同一層上的不同子樹，并且指向它們的根結(jié)點的指針是同一棵樹T上的兩個不同的結(jié)點(r和s)的下一棵指針。

2) 從Ty的根結(jié)點到Y(jié)再串連上轉(zhuǎn)移指針b的比特串等于從Tx的根結(jié)點到x的比特串。

3) Y沒有等于轉(zhuǎn)移指針b的子結(jié)點。

4) s是T中離r最近的滿足上述條件的父結(jié)點。查找樹網(wǎng)格避免了由于復(fù)制規(guī)則導(dǎo)致存儲空間擴大和分層查找樹的回溯問題。在處理兩維流分類問題時，時間復(fù)雜度為O(w)，空間復(fù)雜度為O(Nw)，應(yīng)此它是一種很好的處理兩維流分類問題的算法。在處理多維問題時，它也可以用來優(yōu)化分層查找樹的最后兩層子樹。HiCuts的實現(xiàn)需要建立一種決策樹的數(shù)據(jù)結(jié)構(gòu)，每個葉結(jié)點都存儲著一些規(guī)則，查找時經(jīng)過決策樹找到一個葉結(jié)點，再對這個葉結(jié)點中的規(guī)則進(jìn)行線性查找找到匹配的規(guī)則。決策樹的根節(jié)點包含了整個d維空間，具體結(jié)構(gòu)可以通過參數(shù)來決定。

參數(shù)binth規(guī)定了每個葉結(jié)點包含的規(guī)則的最大數(shù)，當(dāng)一個結(jié)點的規(guī)則數(shù)大于binth時，就把d維中的某一維平均劃分成NP(C)份，形成NP(C)個子結(jié)點。如果結(jié)點包含的規(guī)則數(shù)小于binth，那么該結(jié)點就是一個葉結(jié)點。HiCuts的時間復(fù)雜度為O(d)，空間復(fù)雜度為O(Nd)。可以根據(jù)規(guī)則的特征調(diào)整參數(shù)來優(yōu)化數(shù)據(jù)結(jié)構(gòu)，降低所需的存儲空間，提高查找速度，規(guī)則的更新容易實現(xiàn)。缺點是預(yù)處理的時間較長，適用于規(guī)則較少的情況。

獨立區(qū)域查找算法
這類算法首先通過一維查找算法對每個區(qū)域單獨進(jìn)行查找，產(chǎn)生中間查找結(jié)果，再根據(jù)中間結(jié)果決定最后多維的查找結(jié)果。這樣就可以利用各個區(qū)域的特點使得查找更加有效,另外存儲器的訪問是獨立的，因此可以并發(fā)進(jìn)行。它的性能很大程度上決定于中間查找結(jié)果的編碼。

代表算法有crossproducting，位向量交集(Bitmap-Intersection)和重復(fù)流分類(Recursive Flow Classification，RFC)[4]。Crossproducting先找出各維上不同情況的組合(每種組合都對應(yīng)于一條規(guī)則)，把它們存儲在一個Crossproduct表中，查找是在每個維上單獨進(jìn)行的，最后根據(jù)各個維的查找結(jié)果對Crossproduct表進(jìn)行查找，找到相應(yīng)的規(guī)則。時間復(fù)雜度為O(dw)，空間復(fù)雜度為O(Nd)。它的缺點在于存儲空間要求很大，成級數(shù)變化。另外它的更新不方便，每次增加規(guī)則都需要重新計算Crossproduct表。

位向量交集把所有規(guī)則的同一維映射到同一條數(shù)軸上，那么每條規(guī)則在該數(shù)軸上都是一個范圍或一個點，給它們都定義一個中間向量，它的位寬為N，對應(yīng)于N條規(guī)則，規(guī)則按照優(yōu)先級排列，根據(jù)每條規(guī)則在該范圍的上的匹配情況給它取值，規(guī)則匹配時，向量的對應(yīng)位取1，否則取0。查找時分別先找到每一維上匹配的中間向量，再把它們進(jìn)行與運算，找到向量中優(yōu)先級最高的1位，對應(yīng)的規(guī)則就是匹配的規(guī)則。時間復(fù)雜度為O(dw+N/memwidth)，空間復(fù)雜度為O(dN2)。這種算法試圖通過增加存儲器訪問次數(shù)來減少所需存儲空間，但是效果不明顯，而且它并沒有解決更新困難的問題。RFC算法在對數(shù)據(jù)包進(jìn)行處理時，可以看作是將數(shù)據(jù)包頭部的S比特映射到T比特的類符號的過程。

其中T＝lbN，T<