高速分組查找規(guī)則匹配算法研究.pdf

1、互聯(lián)網(wǎng)流量增長(zhǎng)和通信線路速率的提高，對(duì)路由交換網(wǎng)絡(luò)設(shè)備數(shù)據(jù)平面的報(bào)文處理提出了更高的要求，以100Gbps以太網(wǎng)接口為例，要實(shí)現(xiàn)最小包長(zhǎng)線速轉(zhuǎn)發(fā)，每報(bào)文處理時(shí)間要小于6.72ns,其中二到七層的分組查找規(guī)則匹配是分組轉(zhuǎn)發(fā)、QoS調(diào)度、流量控制等處理的關(guān)鍵。本文在三層IP路由最長(zhǎng)匹配（LPM：Longest Prefix matching）、三到四層的報(bào)文分類(lèi)（PC：Packet Classification）和七層的深度報(bào)文檢測(cè)（DPI

2、：Deep Packet Inspection）等方面開(kāi)展研究，基于硬件三態(tài)內(nèi)容尋址存儲(chǔ)器（TCAM：Ternary Content Addressable Memory）提出了相關(guān)的分組查找規(guī)則匹配算法，并對(duì)算法進(jìn)行分析、仿真和實(shí)驗(yàn)驗(yàn)證。
　　 傳統(tǒng)IP路由查找算法在前綴值或者前綴長(zhǎng)度維度采用線性或者二分搜索，存在查找速率慢、預(yù)計(jì)算復(fù)雜和功耗高的缺點(diǎn)。為提高查找速率和降低功耗，提出了一種采用TCAM實(shí)現(xiàn)前綴覆蓋級(jí)別的二分路由查

3、找算法BSPCL（Binary Search on Prefix Covered Level），其特點(diǎn)是：前綴按照所在覆蓋級(jí)別劃分到不同的集合并放置在TCAM中，通過(guò)二分算法來(lái)實(shí)現(xiàn)路由查找。查找性能方面：路由查找可以在O(log2max_level+1)個(gè)TCAM時(shí)鐘周期內(nèi)完成，max_level為最大的前綴覆蓋級(jí)別，目前對(duì)于IPv4和IPv6來(lái)說(shuō)max_level分別為7和2；功耗方面：二分查找特性可以降低功耗約50％；路由更新方面：

4、前綴在TCAM中的存放無(wú)需排序，支持隨機(jī)更新。
　　 為加速I(mǎi)P路由查找，提出了一種并行IP路由查找方法LEAF-TCAM。路由表分區(qū)方面：LEAF-TCAM方法基于葉子節(jié)點(diǎn)（Leaf Node）進(jìn)行路由表分區(qū)，分區(qū)算法實(shí)現(xiàn)簡(jiǎn)單且分區(qū)均勻；負(fù)載均衡方面：分區(qū)子表按照流量特征，基于貪心方法在K個(gè)TCAM芯片中進(jìn)行均衡分布；查找性能方面：和其他并行方法一樣具有K-1倍加速因子；路由更新方面：該方法無(wú)需進(jìn)行前綴擴(kuò)展，可以采用隨機(jī)更新。

5、針對(duì)骨干網(wǎng)路由表的分析表明在引入0.1*(K-1)冗余，90％以上的路由無(wú)需排序，功耗只有傳統(tǒng)單片方案的12％。
　　 緩存技術(shù)也應(yīng)用于IP路由查找，目前用于IP路由查找的地址緩存時(shí)間局部性和空間局部性有限，前綴緩存技術(shù)的存在不公平性以及不支持增量更新的問(wèn)題。本文提出了一種基于閾值的IP路由緩存方法（TRC：Threshold-based Route Caching），該方法結(jié)合了地址緩存和前綴緩存技術(shù)，克服了地址緩存技術(shù)緩存空

6、間要求過(guò)大，前綴緩存技術(shù)無(wú)法緩存內(nèi)部前綴節(jié)點(diǎn)的問(wèn)題，在緩存空間、緩存命中率、緩存公平性以及路由增量更新方面具有優(yōu)勢(shì)。仿真實(shí)驗(yàn)表明對(duì)于路由條目超過(guò)260K的路由表，緩存空間大小為30K，選擇閾值K=4時(shí)，緩存失效率為0.02，可以用小的緩存空間實(shí)現(xiàn)高速接口的線速轉(zhuǎn)發(fā)。
　　 基于TCAM的報(bào)文分類(lèi)在實(shí)現(xiàn)范圍匹配時(shí)存在范圍擴(kuò)張問(wèn)題，最壞情況下，基于前綴擴(kuò)展方法（PE：Prefix Expansion）的范圍擴(kuò)張因子為2（W-1），基

7、于格雷碼表示方法（SRGE：Short Range Gray Encoding）的范圍擴(kuò)張因子為2（W-2），其中W為范圍字段的長(zhǎng)度。范圍擴(kuò)張一方面會(huì)導(dǎo)致TCAM空間利用率的降低，另一方面會(huì)導(dǎo)致查找匹配時(shí)功耗的升高。本文提出了一種基于TCAM的范圍匹配方法：C-TCAM（Compressed TCAM）?？臻g方面，通過(guò)二級(jí)壓縮存儲(chǔ)，C-TCAM可以將2個(gè)擴(kuò)展后的TCAM表項(xiàng)壓縮成1個(gè)，最壞情況下范圍擴(kuò)張因子為W-1或者W-2，提高了空間

8、利用率；功耗方面，通過(guò)一種新的TCAM查找算法來(lái)避免無(wú)效表項(xiàng)參與比較從而降低了功耗；擴(kuò)展性方面，在性能允許的條件下，C-TCAM可以向多級(jí)擴(kuò)展，從而進(jìn)一步減少空間和降低功耗。分析和仿真顯示C-TCAM方法在實(shí)現(xiàn)性能報(bào)文分類(lèi)的同時(shí)在空間利用率、功耗等方面具有優(yōu)勢(shì)。
　　 基于報(bào)文內(nèi)容掃描的深度報(bào)文檢測(cè)技術(shù)廣泛應(yīng)用于網(wǎng)絡(luò)入侵檢測(cè)、業(yè)務(wù)識(shí)別和控制系統(tǒng)，傳統(tǒng)基于三層、四層報(bào)文頭部的安全訪問(wèn)控制需要掃描的三層、四層報(bào)頭內(nèi)容在報(bào)文中的位置固

9、定，而DPI需要檢測(cè)的特征字在報(bào)文中出現(xiàn)的位置不固定，因此需要對(duì)報(bào)文內(nèi)容進(jìn)行逐字節(jié)掃描。為實(shí)現(xiàn)低功耗高速DPI，提出一種基于布魯姆過(guò)濾器（BF：Bloom Fliter）和TCAM的分級(jí)DPI方法BF-TCAM。第一級(jí)采用低功耗的并行布魯姆過(guò)濾器排除無(wú)需檢測(cè)的正常報(bào)文；第二級(jí)采用TCAM對(duì)真正需要檢測(cè)的攻擊報(bào)文和第一級(jí)的假陽(yáng)性誤判報(bào)文做進(jìn)一步的檢測(cè)。由于網(wǎng)絡(luò)流量中大部分報(bào)文是正常報(bào)文，攻擊報(bào)文在其中只占很少的部分，布魯姆過(guò)濾器的假陰性（