針對多維度封包過濾規則的快速且具擴充性的衝突偵測

封包分類在支援如防火牆、策略路由、網路安全與服務品質等進階網路服務上扮演重要的角色。路由器必須將進入的封包根據預先定義好的規則分成不同的資料流，而這些規則又稱為封包過濾規則(packet filter)。如果有兩個以上的過濾規則重疊，便可能發生衝突的問題，進而導致在封包分類時產生模擬兩可的情形。由於封包分類的重要性，此領域過去已吸引許多研究者的注意，然而同樣重要的衝突偵測卻僅有少數的研究成果。在本計畫中，我們將目標放在設計一個針對多維封包分類規則的快速且具可擴充性的演算性。我們所提出的演算法的關鍵想法是將偵測過程分成兩個階段。第一個階段使用分類規則中的網路位址欄位，並透過值組空間來大幅減少必須偵測可能產生衝突的分類規則數量。透過發掘由著名封包分類演算法－矩形搜尋(rectangle search)，所產生的資料結構所具有的特性，我們所提出的演算法能比其他既有演算法更快速，且使用更少的記憶體空間。第二個階段利用一個預先建立的交叉乘積(cross-producting)表格處理其他的欄位，此做法能有效地偵測兩個過濾規則是否有衝突。最後，我們預計使用由封包分類效能評估工具ClassBench所產生的合成過濾規則資料庫來評估本計畫所提出之演算法的效能。

系統編號:PB10108-2288
原計畫編號:NSC101-2221-E182-074