Fast Packet Classification with a Two-Stage Architecture

封包分類為路由器、防火牆等網路安全設備核心工作之一，其作用在於使用封包標頭部（packet header) 中傳輸層（Transport Layer) 與網路層（Network Layer) 這兩層的欄位，來決定封包是否符合規則資料庫（rule database) 中的某條規則。而隨著網路軟、硬體設備的普及與進步，傳統適用於小維度、且僅能處理少量封包的分類法則已經漸漸無法負荷，諸如虛擬私人網路(Virtual Private Network)、服務品質保證(Quality of Service) 。如何提供一個有效率且具備實用價值的方法，是一項極為重要的議題。 我們提出一個多維度封包分類的架構，主要分為兩個階段：第一個階段為利用決策樹(Decision Tree)進行初步的搜尋分類，我們將規則資料庫依據規則編號分群，決策樹的葉節點儲存著以位元向量(Bit Vector)表示的群編號，由根節點搜尋至葉節點可以知道封包可能符合哪幾群。第二階段則針對各群中的特定位元組建立位元向量表，透過決策樹葉節點所提供的資訊，我們讀取特定群數中的位元向量表來進行更細部的分類。透過此架構，我們期望能夠在合理的記憶體空間內，有極佳的搜尋效率，由實驗結果得知，我們在記憶體用量以及存取次數上的表現均優於以往傳統的封包分類演算法。Packet classification is one of the most critical functions for network security devices such as routers and firewalls. A packet classifier uses the packet header information to decide if a packet matches a rule in the rule database. As the network wired speed increases, a fast packet classification architecture is required to process the incoming packets. In this paper, we propose a two-stage packet classification approach. The first stage uses the decision tree to conduct an initial coarse search, which partitions the rule database into groups according to their rule numbers; the leaf of the decision tree stores the group number that is expressed with bit vectors. By searching from root to leaf, we classify the incoming packets into groups. The second stage focuses on building bit vector tables for the specific groups for performing a fine search, which conducts detailed classifications to find out the exact matched rule. Through this structure, we can produce an excellent search engine within reasonable memory storage requirements. From the experiment results, we show that the performance of our method is better than existing packet classification algorithms in the average case.目錄 致謝 i 摘要 iv Abstract v 第一章 序論 1 1.1 背景 1 1.2 封包分類演算法的五項基本要求 2 1.3 貢獻 4 1.4論文架構 4 第二章 有關之演算法介紹 5 2.1 前言 5 2.2 演算法之簡介 6 2.2.1 線性搜尋(Linear Search) 6 2.2.2 三相可定址內容記憶體(Ternary Content Addressable Memory) 6 2.2.3 查找樹格演算法(Grid-of-Tries) 7 2.2.4 胖逆區段樹演算法(Fat inverted segment tree) 8 2.2.5 平行封包分類法(Parallel Packet Classification) 8 2.2.6 值組空間搜尋(Tuple Space Search) 9 第三章 相關研究 10 3.1 投影以及切割 10 3.2 階層式智慧切割(Hierarchical Intelligent Cuttings) 12 3.3.聚集位元向量(Aggregated Bit Vector) 18 第四章 兩階段式分類架構 20 4.1動機以及想法 20 4.2 兩階段式分類架構 - 方法一 26 4.2.1方法一第一階段建構演算法 27 4.2.2方法一第二階段建構演算法 31 4.2.3方法一搜尋演算法 33 4.3 兩階段式分類架構 - 方法二 37 4.3.1 方法二第二階段建構演算法 40 4.3.3方法二搜尋演算法 42 第五章 實作 46 5.1 演算法軟體實作以及模擬 46 5.2 硬體描述語言模擬 49 5.3 FPGA 實做 50 第六章 效能評估 54 6.1 評估平台 54 6.2 實驗資料以及單位 56 6.3 實驗結果 57 6.3.1 SPFAC對於記憶體用量以及存取次數之影響 57 6.3.2 Bucket對於記憶體用量以及存取次數之影響 60 6.3.3 演算法各部分所佔的記憶體空間以及存取次數 63 6.4與其他封包分類演算法之比較 66 6.5 討論 71 第七章 結論 74 參考文獻 7