多維包分類算法的研究與仿真.pdf

1、包分類是根據(jù)數(shù)據(jù)包的頭部字段將數(shù)據(jù)包按一定規(guī)則進行分類的過程，在路由器、防火墻和入侵檢測等網(wǎng)絡關鍵設備中均有廣泛的應用。包分類技術是因特網(wǎng)提供一切有差別服務和其他新業(yè)務的基礎。隨著網(wǎng)絡規(guī)模的日益擴大，各種應用以及網(wǎng)絡流量迅猛增長，需要網(wǎng)絡設備提供更高的帶寬和數(shù)據(jù)分類處理能力。因此，研究高速包分類問題具有重要的現(xiàn)實意義和理論價值。
　　 本文首先給出了包分類問題的形式化描述，分析了現(xiàn)實規(guī)則庫的特點以及包分類算法的衡量標準，最后對多

2、維包分類算法進行了分類總結。在此基礎上，分別從軟件和硬件兩個方面對現(xiàn)有的高速包分類算法進行了研究和改進。
　　 RFC算法是軟件實現(xiàn)的包分類算法中分類速度較快的一種算法，適合快速多維包分類，但其預處理階段需要大量的時間。對RFC預處理階段算法進行了改進，重新設計了等價類的存儲方式，采用棧存儲等價類，并加入啟發(fā)式信息提前確定等價類的編號。實驗結果表明總的初始化時間比原來減少了90％以上，并且改進后的算法在包分類階段與RFC算法保持

3、相同的時間復雜度。
　　 在改進RFC算法的基礎上，提出了一種兩階段索引RFC算法，為每個等價類生成一個索引表。包分類過程分兩步完成，先根據(jù)預處理表查找與數(shù)據(jù)包的源IP地址和目的IP地址字段匹配的規(guī)則，然后再判斷數(shù)據(jù)包的其他分類字段是否匹配。實驗結果表明兩階段索引RFC算法極大地減少了初始化時間，但仍保持了較高的分類速度。
　　 TCAM是一種廣泛應用于工業(yè)領域的硬件包分類設備，在一個時鐘周期內(nèi)就可以完成一次數(shù)據(jù)包的匹配