Scalable Packet Classification with A Hybrid Algorithm

網路服務提供者提供許多網路服務，如防火牆、VPN與QoS等服務。為了提供這些服務，路由器必須對接收到的封包進行分類的動作，這個功能在路由器上稱為封包分類。封包分類是由一個封包分類器從一群規則中尋找最佳符合的規則，並採取其相對應的動作，為了減少封包停留在路由器上的時間，需要有一套較為快速的封包分類演算法來尋找最佳符合的規則。本論文主要提出先以兩種不同方式將規則分為兩群的分群方法，再結合HyperCuts方法與ABV方法的演算法，最後在我們的實驗測試中，達到較少較穩定的記憶體空間需求與記憶體存取次數。Internet service providers provide Internet services such as firewall, VPN and QoS. In order to provide these services, the received packet must be classified by the router. This function of the routers is called packet classification. Packet classification find the best match rule in the rules set , and take the corresponding action to reduce the packet stay time on the router .We need a relatively fast packet classification algorithm to find the best match rule. In this thesis, firstly we proposed two different clustering methods to divide the rules into two groups, and secondly we combined HyperCuts algorithm and ABV algorithm. At the last, the experimental results show that our scheme is more stable then the others, and our scheme requires less memory and memory access times.摘要 i Abstract ii 圖目錄 v 表目錄 vi 第一章 導論 1 1.1 導論 1 1.2 問題描述 1 1.2.1 名詞解釋 1 1.2.2 問題描述 2 1.3 研究動機: 3 1.4 研究目的 6 1.5 研究方法 7 1.6 論文架構 8 第二章 相關研究 9 2.1 線性搜尋 9 2.2 啟發式特徵分類(Heuristic characteristics of classifiers) 9 2.2.1 Hierarchical intelligent Cutting (HiCuts): 10 2.2.2 Hyper-Cutting (HyperCuts): 10 2.3 獨立一維搜尋: 11 2.3.1 Bit-Vector (BV) 11 2.3.2 Aggregate Bit Vector (ABV) 12 2.3.3 Recursive Flow Classification (RFC) 13 2.4 以Trie為基礎(Trie-based): 14 2.4.1 Hierarchical Trie (H-trie) 14 2.4.2 Set-Pruning Trie 15 2.4.3 Grid-of-Trie 16 2.5 雜湊(Hash-based) 17 2.6 Hardware-based 17 第三章 我們的方法 19 3.1 建立結構: 19 3.1.1 規則分群方法 21 3.1.2 結合方法 34 3.2 搜尋方法與更新 36 第四章 實驗模擬與效能評估 38 4.1 模擬環境與參數設定 38 4.2 實驗結果與數據分析 40 第五章 結論與未來研究方向 56 參考文獻 5