TCAM-based Multimatch Packet Classification with Hybrid Algorithms

隨著入侵偵測系統、虛擬私有網路和服務品質保證等不同類型的網路應用程式快速地增加，封包分類在路由器上將扮演重要的角色，並且需要作多重的比對。然而，作多重比對分類是相當耗費搜尋時間的，所以將使用TCAM來作多重比對分類，但TCAM的特性只支援單一比對分類。為了讓TCAM可以支援多重比對分類，將新增規則到TCAM或是增加對TCAM的存取，因此將面臨TCAM空間的消耗和整體搜尋速度的下降。 本篇論文提出基於TCAM的多重比對混合式封包分類器，在資料庫裡的部分規則使用ABV來實作，而另一部分規則使用geometric intersection 或MUD來實作。經由實驗結果顯示TCAM在作多重比對分類可以更有效率，並減少TCAM空間的消耗和加快整體搜尋的速度。As network intrusion detection system, virtual private network and Quality of Service (QoS) of various types of network applications increased rapidly, packet classification plays an important role in routers, and also support to make multi-match classification. However, implementation of multi-match classification is quite time-consuming for search, so we use TCAM to achieve multi-match classification, but the characteristics of TCAM supports only a single-match classification. In order to TCAM supports multi-match classification, rules will be added to the TCAM or increase number of TCAM accesses, therefore we will face the TCAM space consumption and decline of overall search speed. This paper presents the TCAM-based multi-match packet classification with hybrid algorithms, the rule set in the database using ABV to implement, and the other of rule set using geometric intersection or MUD to implement. The simulation results show that the TCAM for multi-match classification could be more efficient, and reduce the TCAM space consumption and speed up the overall search.目次 摘要 i Abstract ii 目次 iii 表目錄 vi 圖目錄 vii 第一章 緒論 1 一、 研究背景 1 二、 問題定義與描述 2 (一) 問題定義 2 (二) 問題描述 - Multi-match Classification 3 三、 評估標準 5 (一) 搜尋速度 5 (二) 儲存空間 5 (三) 可擴充性 (Scalability) 5 四、 論文架構 6 第二章 相關研究 7 一、 Software solutions 7 (一) Linear search 7 (二) Hierarchical tries 7 (三) Grid-of-tries 8 (四) Cross-producting 8 (五) Recursive flow classification (RFC) 8 (六) Hierarchical intelligent cuttings (HiCuts) 9 二、 Hardware solutions based on bit vector 10 (一) Lucent Bit Vector (BV) 10 (二) Aggregated Bit Vector (ABV) 10 三、 Hardware solutions based on TCAM 12 (一) TCAM-based Solution 12 (二) Geometric Intersection-Based Solutions 13 (三) Database Independent Range Pre-Encoding (DIRPE) 14 (四) Multi-match Using Discriminators (MUD) 14 四、 封包分類演算法複雜度的歸納與比較 16 第三章 設計方法 17 一、 研究動機 17 二、 基於TCAM的多重比對混合式封包分類器-Geometric Intersection和ABV 19 (一) Geometric Intersection-based Solution 19 (二) Aggregated Bit Vector (ABV) 23 (三) Combining Geometric Intersection and ABV 26 三、 基於TCAM的多重比對混合式封包分類器-MUD和ABV 30 (一) Multi-match Using Discriminators (MUD) 30 (二) Combining MUD and ABV 33 第四章 模擬實驗與結果 37 一、 實驗環境與設定 37 二、 實驗數據與分析 38 (一) Combining Geometric Intersection and ABV的實驗分析 38 (二) Combining MUD and ABV的實驗分析 42 第五章 結論與未來展望 48 參考文獻 4