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

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

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

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

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