低記憶體容量需求的封包分類架構

Abstract

在防火牆 (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.