基于三態(tài)內(nèi)容可尋址存儲器的包分類算法研究.pdf

1、計算機網(wǎng)絡(luò)的迅速發(fā)展衍生出了很多新型的網(wǎng)絡(luò)服務(wù)，包分類是所有這類應(yīng)用的核心技術(shù)。包分類根據(jù)包頭中的相關(guān)域?qū)?shù)據(jù)包劃分到不同的類中進行區(qū)分處理。隨著網(wǎng)絡(luò)流量的激增，包分類已成為影響網(wǎng)絡(luò)傳輸速率的瓶頸。
　　 目前，數(shù)據(jù)包分類的方法主要有軟件方法和硬件方法兩類。軟件方法具有較好的靈活性，但分類速度慢；硬件方法可以滿足高速處理要求，但靈活性較差。由于三態(tài)內(nèi)容可尋址存儲器(TCAM)的高速并行查找特性，已被越來越多地應(yīng)用到包分類領(lǐng)域。但

2、是基于TCAM實現(xiàn)數(shù)據(jù)包分類面臨區(qū)間膨脹的問題，已有算法無法解決編碼區(qū)間所需的比特數(shù)隨區(qū)間數(shù)目線性增長的問題。
　　 本文提出兩種基于TCAM硬件的有效包分類算法：區(qū)間分組算法RG(RangeGroupingAlgorithm)和擴展的區(qū)間分組算法E-RG(ExtendedRangeGroupingAlgorithm)，通過將多個滿足一定條件的區(qū)間劃分到同一組并共用同一個編碼段進行編碼，來達(dá)到減少編碼位數(shù)的目的。RG算法將彼此獨

3、立的區(qū)間分到同一組中，并共用同一個編碼段進行編碼表示，減少了編碼所需的位數(shù)。E-RG算法大幅放寬了分組的條件，將彼此獨立或者相互包含的區(qū)間分到同一組，并利用ShadowEncoding編碼方法對同組內(nèi)的區(qū)間進行有效編碼。通過使更多的區(qū)間共用同一碼段，E-RG算法使得編碼所需的位數(shù)大幅降低。通過合理分組和有效編碼，RG算法和E-RG算法不僅完全解決了TCAM中普遍存在的“區(qū)間膨脹”問題，還對包分類規(guī)則的比特寬度進行了高效壓縮，大大減少了T

4、CAM的空間開銷。
　　 針對預(yù)處理操作會降低RG算法和E-RG算法的匹配速度，本文提出了一種并行流水線匹配機制。采用此匹配機制，可以保證在一個TCAM的時鐘周期內(nèi)完成一個數(shù)據(jù)包的分類操作。
　　 本文在Windows平臺上將RG算法、E-RG算法和幾個典型的基于TCAM的包分類算法進行了比較。實驗結(jié)果表明，E-RG算法可以保證在不損失匹配速度（即在一個TCAM時鐘周期內(nèi)分類一個數(shù)據(jù)包）的前提下，極大地降低TCAM的空間