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

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

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

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

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

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