基于IXP2400的改進RFC算法的研究與設計.pdf

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

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

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