基于搜索空間分解的IP報文分類技術研究.pdf

1、報文分類是指網絡設備根據預先定義的某些規(guī)則將流經的IP報文分成不同的類并對每類進行相應處理的過程，廣泛地應用于防火墻、區(qū)分服務、虛擬專用網、入侵檢測、流量計費等領域。近年來隨著網絡鏈路速率的增長和網絡中一些新增加應用的出現，網絡設備的處理能力逐漸落后于網絡流量的增長速度，現有的基于軟件或網絡處理器的報文分類算法很難滿足性能需要。研究人員開始從硬件上尋求問題的解決方案，如專用集成電路（ASIC）和現場可編程門陣列（FPGA）等。
　

2、　本文針對搜索空間分解的分類算法進行了研究，主要工作如下：
　　1.對現有經典分類算法特別是對基于Trie結構的分類算法進行分析總結，從理論上分析了各類算法在最壞情況下的時間復雜度、空間復雜度、及其應用環(huán)境。為了能夠有效評測報文分類算法的各種性能指標，采用了兩種分類算法性能評價工具，一種是華盛頓大學開發(fā)的ClassBench，另一種是斯坦福大學開發(fā)的PALAC（Packet Lookup And Classification Si

3、mulator）。ClassBench能夠根據真實的規(guī)則集特征來產生不同數量的實驗規(guī)則集用來對算法進行測試，因此它能有效地解決規(guī)則集來源的問題；PALAC在它的COLAR模塊中有一個算法類，用戶只需要把自己的算法添加為該類的子類，因此PALAC使用起來更方便。
　　2.提出了一種基于搜索空間分解優(yōu)化的i-HyperCuts算法。研究分析了搜索空間分解的分類算法HiCuts及其改進算法HyperCuts的機制機理，由于HiCuts算

4、法和HyperCuts算法對搜索空間進行了均勻切割,造成了規(guī)則的復制，增加了算法的存儲空間需求，因此本文根據HyperCuts算法中規(guī)則復制的兩個來源做了相應的改進，提出了i-HyperCuts算法。該算法主要思想為：一、減少規(guī)則重疊，把需要復制到各個子空間中的規(guī)則挑選出來另行處理，不再復制到各個子空間去；二、對端口域的搜索區(qū)間進行切割時尋找導致規(guī)則復制最小點，而不是平均切割。實驗結果表明，基于核心路由器規(guī)則集（CR2，該規(guī)則集包含12

5、5條過濾規(guī)則）測試樣例，改進后的i-HyperCuts算法所需存儲空間從2,440字節(jié)降低至2,135字節(jié)；建立的決策樹深度（也即訪存次數）從11次降低到8次。
　　3.在Xilinx FPGAVirtex-6平臺上對i-HyperCuts算法進行了驗證。布局布線的結果表明，在單個FPGA芯片中存儲10K個規(guī)則的情況下，與HyperCuts算法相比，i-HyperCuts算法的吞吐量從90Gbps提高到100Gbps，FPGA芯片