Study and Design of Efficient Packet Classification Algorithms

在過去的十年以來，網際網路服務不論在種類或使用人數上都有極快速的成長。為了支援進階的網際網路服務，如防火牆、虛擬頻寬配置、差異化服務、以及虛擬私有網路，路由器必須將進入的封包分成許多不同的類別，接著再根據其類別執行先前定義好的動作。對於每一個進入的封包，路由器利用過濾器(或分類規則)資料器和儲存在封包表頭的資訊來執行分類的工作，可能被用來當分類條件的欄位有來源IP 位址、目的地IP 位址、來源通訊埠號碼、目的地通訊埠號碼、以及通訊協定。由於傳輸線路速度的快速提升，路由器必須以足夠快速的速度執行封包分類以跟上傳輸線路的速度。除此之外，資料庫中所儲存的分類規則數目也不斷增加。因為電源消耗和成本的考量，路由器必須能在其有限的記憶體中盡可能儲存更多的分類規則。雖然已經有許多封包分類演算法被提出，但是當資料庫的分類規則數目變大時，現有文獻中的演算法不是在空間方面，否則就是在時間方面無法達到令人滿意的結果。在本計畫中，我們將設計一個能用於大型的分類規則資料庫，並且同時滿足空間與時間要求的封包分類演算法，最後再利用真實與合成的分類規則資料庫來評估所設計之演算法的效能。

Project ID:PB9508-4042
External Project ID:NSC95-2221-E182-073