快速包分類(lèi)算法研究.pdf

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

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