使用圖形處理器於封包分類器的平行衝突偵測之研究

諸如防火牆、策略式路由與虛擬私人網路(virtual private network，簡稱VPN)等進階網路服務，必須仰賴路由器根據封包的表頭欄位與預先定義的封包分類器(packet filters)將封包分成不同的資料流(flows)。當兩個以上的分類規則產生重疊時，可能會發生衝突，進而導致封包分類上的不確定性。於之前的科技部研究計畫(MOST 104-2221-E-182-005)中，我們透過分析衝突的成立條件，將來源端IP位址與目的端IP位址先以值組空間的方式進行處理。接著，再將規則中剩下的欄位加以編碼，以加快處理速度。利用預先建立的查詢表格，存取記憶體的時間與運算都可以大量減少。在這個為期一年的計畫中，我們預計延續目前的研究方向，但是將專注於利用圖形處理器(graphics processing unit，簡稱GPU)加速衝突偵測，因為GPU具有遠較中央處理器(central processing unit，簡稱CPU)更高的平行處理能力。為了設計有效率的平行衝突偵測演算法，我們首先分析衝突偵測如何能透過平行化的方式有效地執行，接著我們提出一個過濾機制以減少每一個規則於衝突偵測的過程中必須進行比對的次數。由於使用所提出的過濾機制可能使得每一個規則必須比對的次數有所不同，導致在平行處理時的工作負載不平衡，進而影響效能。因此，我們提出一個能平衡GPU執行緒工作負載的策略，藉以達成明顯的效能改進。

系統編號:PB10708-1624
原計畫編號:MOST107-2221-E182-029