成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	林呈俞 Lin, Chen-yu
論文名稱：	用於封包分類之網格化區段樹演算法 Grid of Segment Trees for Packet Classification
指導教授：	張燕光 Chang, Yeim-kuan
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 資訊工程學系 Department of Computer Science and Information Engineering
論文出版年：	2009
畢業學年度：	97
語文別：	英文
論文頁數：	94
中文關鍵詞：	紅黑樹、B 樹、區段樹、網格化的數位搜尋樹、封包分類
外文關鍵詞：	Packet classification, B-trees, segment trees, red-black trees, Grid-of-tries
相關次數：	點閱：90 下載：1
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

在最近幾年裡，封包分類一直是個重要的議題並且已經受到廣泛的注意。每個封包都必須決定應該送往那個輸出阜以及應該採取的措施。許多高效能的封包分類方法相繼被提出。一般來說，這些方法大致可以被分為兩類：軟體演算法式與硬體架構式。網格化的數位搜尋樹是其中一個用來解決兩維封包分類的方法，但是因為網格化的數位搜尋樹的資料結構是二元數位搜尋樹且不適用於連接阜。透過轉換指標與延伸指標的觀念，網格化的數位搜尋樹可以不需要原路返回的搜尋而找到最佳或是多個相配的項目以減少搜尋的成本。
在本論文中，我們以一個較為有效率的資料結構，即區段樹來替換與改善原本使用二元數位搜尋樹為基礎的網格化的數位搜尋樹，並且以區段樹為基礎提出兩個資料結構，第一個稱為DGST (Dynamic Grid of Segment Trees) 另一個則是 DGST(Dynamic Grid of Multiway Segment Trees)。DGST 是一棵以多層次平衡二元搜尋樹為架構的區段樹而DGMST 則是一棵以多層次B 樹為架構的區段樹。我們所提出的方法可以兼具網格化的數位搜尋樹與區段樹的優點並且可以支援動態更新。對一個有n個元素的階層而言，搜尋可以在O(logn)時間內完成。實驗數據是使用三種由ClassBench 產生的規則表來測量。

Packet classification has received much attention and continued to be an important topic in recent years. Each incoming packet needs to determine both the output port it
should be sent to and what action should be taken. Several high performance approaches for solving packet classification has been proposed. In general, these approaches can be roughly divided into two categories: algorithmic and architectural. Grid-of-tries is one of
the traditional algorithmic schemes for solving 2-dimensional packet classification problem, however, the data structure of gird-of-tries is based on binary tries which is not suitable for the port range fields. By using the concepts of switch pointers and extended pointers, grid-of-tries can find best matching filter or multiple matching filters without backtracking during search and save lots of search cost.
In this thesis, we replace the binary tries by an efficient data structure, called segment trees to modify and improve the original grid-of-tries and we proposed two data structures, which are called the DGST (Dynamic Grid of Segment Trees) and DGMST (Dynamic Grid of Multiway Segment Trees) respectively. The DGST is a multidimensional balanced binary search tree structure while the DGMST is a multidimensional B-tree structure. Our
proposed schemes combine the advantage of grid-of-tries and segment trees and support incremental updates. For each dimension contains N elements, the search procedure can be accomplished in O(logN) time. Experiments using three kinds of rule tables which are generate from ClassBench [12], our proposed schemes can have a better performance than traditional schemes, such as hierarchical trie, grid-of-tries and Hypercut.

Chapter 1 Introduction .......................................................................................................... 1
1 Motivation ................................................................................................................... 1
2 Overview of our thesis ................................................................................................ 2
Chapter 2 Background ........................................................................................................... 3
1 Problem Statement ...................................................................................................... 3
2 Performance Metrics for Classification Algorithms .................................................... 4
Chapter 3 Related Works ....................................................................................................... 5
1 Binary Trie ................................................................................................................... 5
2 Traditional algorithms for Packet Classification ......................................................... 7
2.1 Hierarchical Tries ................................................................................................. 7
2.2 Set-Pruning Tries .................................................................................................. 9
2.3 Grid-of-Tries ....................................................................................................... 11
3 Prefixes and Ranges .................................................................................................. 14
3.1 Prefixes ............................................................................................................... 14
3.2 Ranges ................................................................................................................ 16
4 Elementary intervals .................................................................................................. 17
5 Segment Trees ........................................................................................................... 19
5.1 How to construct the segment tree ..................................................................... 19
Chapter 4 Our proposed Dynamic Grid of Segment Trees (DGST) ................................... 21
1 The framework of our Dynamic Grid of Segment Tree (DGST) .............................. 22
2 Node structure of DGST ........................................................................................... 24
3 Inserting a filter ......................................................................................................... 25
3.1 Inserting a node into the DGST .......................................................................... 26
3.2 The DGST filter location rule ............................................................................ 31
3.3 The DGST filter allocation rule .......................................................................... 32
3.4 Constructing the switch pointers and extended pointers .................................... 33
3.5 Rotations of the DGST ....................................................................................... 42
4 Deleting a filter .......................................................................................................... 47
5 The demonstration of a complete insert example ...................................................... 48
6 Querying the DGST .................................................................................................. 62
Chapter 5 Our proposed Dynamic Grid of Multiway Segment Tree (DGMST) ................. 66
1 The framework of our DGMST................................................................................. 66
2 Inserting a filter ......................................................................................................... 68
3 The DGMST filter location rule ................................................................................ 74
4 The DGMST filter allocation rule ............................................................................. 75
5 Querying the DGMST ............................................................................................... 76
Chapter 6 Experimental Results .......................................................................................... 79
1 Simulation environment ............................................................................................ 79
2 Test data ..................................................................................................................... 79
3 Search time ................................................................................................................ 81
4 Memory requirement ................................................................................................. 88
5 Conclusion ................................................................................................................. 92
Chapter 7 Summary ............................................................................................................. 93
References ........................................................................................................................... 94
                                    

[1] M.D. Berg, M.V. Kreveld, M. Overmars, and O. Schwarzkopf, Computational
Geometry: Algorithms and Applications. Springer Verlag, 1997.
[2] T. Cormen, C. Lieserson, R. Rivest, and C. Stein, Introduction to Algorithms, 2nd
edition MIT Press, 2001.
[3] H. Chao, "Next Generation Routers", Proceeding of the IEEE, vol. 90, no.9, pages.
1518-1558, September 2002.
[4] Yeim-Kuan Chang and Yung-Chieh Lin, "Dynamic Segment Trees for Ranges and
Prefixes", IEEE Transactions on Computers, vol. 56, no. 6, pages. 769-784, June
2007.
[5] Yeim-Kuan Chang, "Efficient Multidimensional Packet Classification with Fast
Updates", IEEE Transactions on Computers, vol. 58, no. 4, pages. 463-479, April
2009.
[6] A. Feldman and S. Muthukrishnan, "Tradeoffs for Packet Classification",
Proceeding of IEEE INFOCOM, vol. 3, pages. 1193-1202, March 2000.
[7] P. Gupta and N. McKeown, "Packet Classification on Multiple Fields", ACM
SIGCOMM, pages. 147-160, August 1999.
[8] P. Gupta and N. McKeown, "Algorithms for Packet Classification", IEEE Network
Special Issue, vol. 15, no. 2, pages. 24-32. March/April 2001.
[9] E. Horowitz, S. Sahni, and D. Mehta, Fundamentals of data structures in C++, New
York: W.H Freeman, 1995.
[10] H. Lu and S. Sahni, "Enhanced Interval Trees for Dynamic IP router-tables", IEEE
Transactions on Computers, vol. 53, no. 12, pages. 1615-1628, December 2004.
[11] V. Srinivasan, G. Varghese, S. Suri, and M. Waldvogel, " Fast and Scalable Layer
Four Switching", ACM SIGCOMM Computer Communication Review, vol. 28,
pages.191-202, October 1998.
[12] David E. Taylor and Jonathan S. Turner, "ClassBench: A Packet Classification
Benchmark", IEEE/ACM Transactions on Networking, vol.15, no. 3, pages. 499-511,
June 2007.
[13] David E. Taylor, "Survey and Taxonomy of Packet Classification Techniques", ACM
Computing Surveys, vol. 37, no. 3, pages. 238-275, September 2005.

校內：2010-08-26公開
校外：2010-08-26公開

簡易檢索 / 詳目顯示

相關論文