Study and Design of Conflict Detection Algorithms for Packet Classifiers

網際網路在近年來的發展十分快速，傳統的盡力式服務已經無法滿足網際網路的使用者，越來越多進階的網際網路服務被推出，如防火牆、虛擬頻寬配置、差異化服務、以及虛擬私有網路。為了支援這些服務，路由器必須將進入的封包分成不同的類別，接著再根據其類別執行先前定義好的動作。對於每一個進入的封包而言，路由器會檢視其封包表頭，再尋找過濾器(或分類規則)資料庫以決定該封包屬於那一個類別。為了提供線路速度(line speed)的傳送，路由器必須盡快完成封包分類的動作。由於封包分類是路由器中一個重要的單元，因此成為極受重視的研究課題。雖然封包分類受到廣泛的討論與研究，但是與其相關的分類規則衝突問題卻沒有受到相同的重視，這個問題可能會在封包分類時造成無法分類(ambiguity)的結果。當一個封包同時符合資料庫中的多個分類規則時，路由器會無法決定該選擇那一個分類規則，我們稱這些符合的分類規則處於衝突的狀態。這個問題可以被切分為兩個子問題：第一個子問題是如何偵測出分類規則資料庫中的所有衝突；第二個子問題是如何解決(或是分解)這些衝突。針對一種分類策略，找出所需要加入最小數目的分解分類規則(resolve filters)已經被證明是NP-hard的問題。除此之外，由於路由器所擁有的分類規則數目持續增加，路由器上所使用的衝突偵測演算法的擴充性與效能變得越來越重要。在這個為期兩年的計畫中，我們預計進行衝突偵測演算法的研究與設計。在第一年裡，我們將焦點放在二維度分類規則。雖然多維度分類規則較為一般化，但是仍有部份的服務只需要使用二維度分類規則，例如IP群播(multicast)與IPsec。一般而言，在考慮二維度分類規則的情況下，專為二維度分類規則所設計的衝突偵測演算法能提供比為多維度分類規則所設計的演算法更好的效能。在第二年裡，我們將提出一個針對多維度分類規則的衝突偵測演算法。我們所提出的兩個衝突偵測演算法都是針對大型的分類規則資料庫所設計，並且同時滿足空間與時間的需求。最後，我們將使用真實與合成的分類規則來評估所提出之演算法的效能。

Project ID:PB9609-4093
External Project ID:NSC96-2221-E182-013