快速包分類算法研究.pdf

1、包分類是下一代路由器、防火墻等設(shè)備的關(guān)鍵技術(shù)。包分類算法研究具有十分重要的意義，是目前的熱點之一。 本文介紹了常用的包分類算法，分析了它們的優(yōu)缺點。從算法和體系兩條主線出發(fā)，對包分類問題進行研究。首先，針對多維包分類問題提出一種新的相聯(lián)存儲器結(jié)構(gòu)——MDR—CAM，支持多維范圍匹配，其維數(shù)的設(shè)定具有靈活性。理論分析表明，在該結(jié)構(gòu)上實現(xiàn)包分類，算法時間復雜度為O（1），空間復雜度為O（n）。然后，針對一個具體應用，提出一種動態(tài)多維

2、硬件高速包分類算法。該算法采用決策樹作為快速查找的數(shù)據(jù)結(jié)構(gòu)，每個葉結(jié)點存儲一組規(guī)則，根據(jù)葉結(jié)點所處決策樹層次和最大查找時間要求來確定葉結(jié)點最大規(guī)則數(shù)，從而可界定最壞情況下的分類時間；支持快速更新，借用一個限定長度的雙向鏈表來更新決策樹，可減少臨時空間；優(yōu)化決策樹并提出存儲動態(tài)管理策略，適于在FPGA上實現(xiàn)。仿真結(jié)果表明，在50MHz的搜索頻率下，該算法能夠達到每秒處理2．5M個包頭的速度，最壞情況下的分類時間Csum=34個時鐘，空間復