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

Packet Classification Using R*-Tree based Bitmap Intersection

黃鼎峰(Ding-Fong Huang)

指導教授 ： 陳健

國立交通大學/資訊學院/網路工程研究所/碩士(2010年)

https://doi.org/10.6842/NCTU.2010.00458

摘要

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

關鍵字

封包分類 ； R-Tree ； 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.

並列關鍵字

Packet Classification ； R-Tree ； R*-Tree ； Bitmap Intersection

參考文獻

[1] A. Cuttman, “R-Tree: A Dynamic Index Structure for Spatial Searching,” in proceedings of SIGMOD, pages 47-57, 1984.

[2] B. Seeger, H.-P. Kriegel, N. Beckmann, and R. Schneider, “The R*-tree: An Efficient and Robust Access Method for Points and Rectangles,” in proceedings of SIGMOD, pages 322-331, 1990.

[3] C. Maindorfer and T. Ottmann, “Is the Popular R*-Tree Suited for Packet Classification?,” in proceedings of IEEE NCA, pages 168-176, 2008.

[4] D. Taylor, “Survey & Taxonomy of Packet Classification Techniques,” ACM Comput. Surv., vol. 37, no. 3, pages 238–275, 2005.

[5] D.E. Taylor and J.S. Turner, “ClassBench: A Packet Classification Benchmark,” in proceedings of IEEE INFOCOM, 2005.