一個有效率的封包過濾衝突偵測之平行演算法

Abstract

隨著網際網路迅速發展，網路服務愈趨多元，為滿足進階網路服務的需求，網路中的路由器必須具備封包分類的功能。而在對封包進行分類的過程中，若封包同時符合多個分類規則便會產生衝突，衝突會導致錯誤的封包分類行為，使得網路服務出現問題，例如：網路漏洞、使用者經驗、網路可靠性。現有的衝突偵測演算法皆是執行在中央處理器，而圖形處理器擁有優異的平行計算能力，適合用以處理偵測過程中的比對行為。 本論文中，我們提出在圖形處理器上執行適用多維度分類規則的衝突偵測演算法，透過分析偵測比對的過程，減少衝突偵測時分類規則需要比對的次數，並設計一平均分配工作量的方法使圖形處理器上的執行緒達到平衡的工作量，藉以提升效能。我們所提出的衝突偵測演算法在圖形處理器上執行3,0000個分類規則比對與中央處理器相比，可達2.8至11.6倍的加速，而在經過最佳化後設計的演算法則可增加4.2至21.8倍的效能。

Packet classification plays an important role in network security. Routers, firewalls and intrusion detection systems classify incoming packets into different flows according to predefined rules, which are also called packet filters, to implement security functions. If two or more filters overlap, a conflict may occur and lead to ambiguity in packet classification. Packet classification has attracted a lot of attention due to its importance. However, few studies have been done on conflict detection. In the literature, most conflict detection algorithms were designed based on central processing unit (CPU). Graphical processing unit (GPU), which has parallel processing power superior to that of CPU, is a considerable candidate to provide high detection speed. In this paper, we propose a parallel conflict detection algorithm using GPU. By analyzing the critical steps in conflict detection and the workload of each step, our proposed algorithm can reduce the number of comparisons for each filter and balance workload between GPU threads, resulting in significant performance improvement. Experimental results show that for a filter database with 30,000 filters, the detection speed of our proposed algorithm is 4 to 9.8 times higher than that of the algorithm using CPU.