王勝德臺灣大學：電機工程學研究所卓昇勳Cho, Sheng-HsunSheng-HsunCho2007-11-262018-07-062007-11-262018-07-062007http://ntur.lib.ntu.edu.tw//handle/246246/53470在防火牆 (Firewall) 與入侵偵測 (Intrusion Detection) 等網路安全機制中，封包分類 (Packet Classification) 是一個是很重要的部份，其作用在於使用封包檔頭 (packet header) 中傳輸層 (Transport Layer) 與網路層 (Network Layer) 這兩層的欄位，來決定封包是否符合規則資料庫 (rule database) 中的某條規則。目前這個領域已經許多的演算法被提出來，但我們發現，雖然這些演算法在某個條件下或是使用某種類型的規則資料庫時，所使用的記憶體空間非常小，但若是換了另一套規則資料庫，其記憶體使用量可能無法令人接受。由於硬體平台的記憶體容量通常很小，並且一定是事前就必須規劃好的，若要將這些記憶體需求無法固定的封包分類演算法實作為硬體，則可能會發生記憶體不足的情形。為了解決這個問題，這篇論文提出了一個封包分類的架構，稱為 PBV (Probable Bit Vector)，結合了 Bit Vector、Aggregate、Folding、規則重新排序 (rule rearrangement)、我們所提出的資料結構，以及硬體線路等。使用個架構，我們可以保證在任何情況下，記憶體的需求都不會超過一個很小的上限，而且實驗證明其平均的速度效能還是在可接受的範圍內。Packet classification is an important part of many Internet security applications, such as firewalls and intrusion detection. A packet classifier uses packet header information to decide if a packet matches any rule in a rule database. There exist many algorithms in this research area. However, many of them have the drawback of requiring a large amount of memory storage in general and consume small amount of memory only in some particular conditions, like using some kind of rule databases or with several restrictions. When the contents of the rule database changes, the memory requirement may become unaffordable, even the rule number remains the same. If those packet classifiers are going to be implemented on hardware, they may not be accepted due to the memory requirement and the limited amount of memory on hardware. To overcome this problem, we proposed a packet classification architecture called Probable Bit Vector (PBV), which combines the concepts of aggregated and folded bit vectors, the rule rearrangement, the Split IP Index Table data structure, and FPGA hardware circuits. With this architecture, we can guarantee that in any case the maximum amount of memory requirement will not exceed a relatively small number, and experiments with synthetically generated rule databases have showed that the average performance is still acceptable.論文口試委員審定書 i 致謝 ii 中文摘要 iii Abstract iv 第一章　序論 1 1.1 處理速度 1 1.1.1 預先處理速度 1 1.1.2 搜尋速度 2 1.1.3 更新速度 3 1.2 空間需求 4 第二章　相關研究 5 第三章　方法 8 3.1 問題描述 8 3.2 基礎演算法 9 3.2.1 位元向量 (Bit Vecotr，BV) 10 3.2.2 聚集 (Aggregation) 12 3.2.3 摺積 (Folding) 13 3.3 Probable Bit Vector 14 3.4 資料結構 16 3.4.1 分割 IP 索引表格 17 3.4.2 使用通訊協定欄位來重排規則 19 3.4.3 不考慮 BV (Don’t Care BV) 22 3.4 封包分類流程 23 3.5 記憶體需求 25 第四章　實做過程 28 4.1 演算法軟體實做與模擬 28 4.2 硬體描述語言模擬 30 4.3 FPGA 實做 31 第五章　實驗結果 33 5.1 實驗資料與單位 33 5.2 PBV參數與記憶體讀取次數 34 5.3.1 聚集單位與記憶體讀取次數 34 5.3.2 摺積常數與記憶體讀取次數 36 5.3.3 摺積群組單位與記憶體讀取次數 37 5.3.4 使用 port 欄位與記憶體讀取次數 38 5.3.5 使用 IP 索引表格數與記憶體讀取次數 40 5.3.6 不同 IP 分割、記憶體類型與記憶體讀取次數 41 5.3演算法比較 42 5.4 硬體實作結果 43 5.5 討論 45 第六章　結論 46 參考文獻 47863433 bytesapplication/pdfen-US封包分類位元向量聚集折積FPGAPacket ClassificationBit VectorAggregateFoldingthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53470/1/ntu-96-R94921092-1.pdf