基于IXP2400的改進(jìn)RFC算法的研究與設(shè)計.pdf

1、計算機網(wǎng)絡(luò)應(yīng)用的多樣化和寬帶化已經(jīng)成為當(dāng)今網(wǎng)絡(luò)的發(fā)展趨勢。在應(yīng)用多樣化的趨勢下網(wǎng)絡(luò)設(shè)備不再僅是簡單地對數(shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā)，還需要為不同用戶提供有差別的服務(wù)，而流分類技術(shù)是差別類服務(wù)的技術(shù)基礎(chǔ)。多維流分類問題在實現(xiàn)上是比較困難的，在網(wǎng)絡(luò)寬帶化的趨勢下，網(wǎng)絡(luò)設(shè)備漸漸成為網(wǎng)絡(luò)的瓶頸，因此需要有高速的流分類方案，才能實現(xiàn)對數(shù)據(jù)包的線速分類轉(zhuǎn)發(fā)。 本文通過對常用算法的性能分析，選取了流分類算法中可以軟件實現(xiàn)的最快算法之一RFC(Recursi

2、ve Flow Classification，遞歸流分類)算法。RFC流分類算法的優(yōu)點是查詢速度快，而且算法在實現(xiàn)過程中存在分布式思想，各個表項可以獨立并行地進(jìn)行查詢，為此，本文采用了多核多硬件線程的網(wǎng)絡(luò)處理器IXP2400來實現(xiàn)算法。 RFC算法的缺點是隨著規(guī)則庫規(guī)模增加，算法的占用空間會驟增。因此，本文采取壓縮規(guī)則庫和壓縮交叉乘積表兩項措施對算法進(jìn)行改進(jìn)。規(guī)則庫壓縮算法是將原來以每條規(guī)則為劃分單位的規(guī)則庫重新組合為以處理結(jié)果

3、為劃分單位，在有相同的處理結(jié)果的規(guī)則組內(nèi)查找鄰接規(guī)則并將其進(jìn)行合并，RFC算法在每個階段都要合并一些域，所以規(guī)則庫壓縮在RFC算法預(yù)處理的每個階段開始之前都會產(chǎn)生壓縮效果。交叉乘積表壓縮主要采用比特向量壓縮算法，將原表中連續(xù)重復(fù)出現(xiàn)元素占用的空間壓縮掉。本文針對以上兩種措施對RFC算法的綜合改進(jìn)方案作了數(shù)據(jù)結(jié)構(gòu)設(shè)計、流程設(shè)計、代碼實現(xiàn)。 硬件資源的分配方案是改進(jìn)算法能否在多核多硬件線程的網(wǎng)絡(luò)處理器上充分利用多核多線程硬件資源，實