基於R*-Tree 的位元圖交集封包分類演算法

Abstract

隨著網際網路的蓬勃發展，網際網路服務如網路安全防護、虛擬私 有網路、品質保證等的需求也越來越高。為了達到這些服務，網際網 路路由器必須針對收到的封包做出快速的分類，而此過程我們把它稱 之為封包分類。封包分類是利用封包標頭中所包含的資訊與路由器中 事先定義好的規則做比對，依據比對出來的結果，執行不同的動作； 多重欄位的封包分類是一個相當困難的問題，已經有許多的演算法被 提出來解決這個問題。在這篇論文中，我們提出了一個透過結合位元 圖交集(Bitmap Intersection)演算法與R*-Tree 封包分類演算法來達到快速封包分類的演算法。透過效能分析以及實驗模擬，我們證明我們所提出的方法無論是在封包分類速度或是所需要的記憶體上，比起這兩種方法都有著顯著的進步。

With the vigorous development of the Internet, there is a stringent speed requirement for processing Internet services such as network security, virtual private network, and quality of service. To accomplish these Internet services, Internet routers must have a fast packet classification capability for incoming packets. Packet classification is the process of identifying a set of pre-defined rules to which a packet matches. Then according to the matched rules, different actions can be performed. Multi-field packet classification generally is a difficult problem, and many different solutions have been proposed to solve this problem. In this thesis,we propose a fast packet classification algorithm that combines bitmap intersection algorithm and R*-Tree algorithm. Through analysis and simulation, we prove that our solution has a significant improvement over both original algorithms in classification speed and memory usage.