流分類算法的分類及比較

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中T＝lbN，T<