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

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

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

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

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

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