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

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

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

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

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

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