封包過濾規則衝突之分群位元向量演算法

Abstract

隨著網路的發展與服務的多元化，網路中的路由器必須具備封包分類的功能。在進行封包分類的過程中，若封包符合多條規則且這些規則對應的處理方式不同時會發生衝突。封包衝突會導致錯誤的分類行為，使得網路服務出現問題。隨著網路型態的演進，封包規則欄位和規則數漸漸變多，因此提供一個多維度有效率的衝突偵測方法是相當重要的。 Bit vector 是一個拓展到多維度相當容易的衝突偵測演算法，但是記憶體的儲存與記憶體的存取次數是該演算法的瓶頸。過去文獻的改善多半著重在預先對bit vector的數值內容去做索引，透過讀取索引數值達到減少對bit vector的內容存取，但並沒有文獻針對封包規則的欄位特性去做改進。 本論文中，我們利用了封包規則設定的特性去對規則做分群，讓不同群的封包透過互斥關係去減少記憶體存取次數，藉以提升效能。我們所提出的group type bit vector衝突偵測演算法在執行30,000個分類規則資料庫與原本bit vector相比平均減少50.3%的偵測時間，最多減少了77.8%。而提出的group type aggregation bit vector與原本aggregation bit vector相比平均可減少23.1%的偵測時間，最多可減少34.7%。

With the development of network services, routers in the network must have the function of packet classification. In the process of packet classification, if a packet matches multiple rules with different actions, it will cause conflict. Rule conflict may lead to wrong behavior, resulting in the network service problems. As the network service evolves, the number of packet rules and rule field increase. Therefore, it is important to provide a multi-dimensional and efficient conflict detection method. Though the bit vector algorithm can be easily scaled to multi-dimensional rule conflict detection, the memory space and memory access time are important issues to be concerned. Some related works rely on bit vector value to create index and read the index to reduce the memory access times. However, these works did not make good usage of the packet rule’s features. In this thesis, we use the features of packet rule for grouping so that different groups of packets through disjoint relationship to reduce the number of memory access. Our proposed group type bit vector conflict detection algorithm can reduce the total detection time by a factor of 77.8% compared with the original bit vector in the 30,000 packet rules database and the average reduced percentage of detection time is 50.3%. The results show that the group type aggregation bit vector outperforms aggregation bit vector, with the total detection time being reduced by a factor up to 34.7% and the average reduced percentage of detection time is 23.1%.