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

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

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

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

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

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

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

7、于格雷碼表示方法（SRGE：Short Range Gray Encoding）的范圍擴張因子為2（W-2），其中W為范圍字段的長度。范圍擴張一方面會導致TCAM空間利用率的降低，另一方面會導致查找匹配時功耗的升高。本文提出了一種基于TCAM的范圍匹配方法：C-TCAM（Compressed TCAM）。空間方面，通過二級壓縮存儲，C-TCAM可以將2個擴展后的TCAM表項壓縮成1個，最壞情況下范圍擴張因子為W-1或者W-2，提高了空間

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

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