跳到主要內容

臺灣博碩士論文加值系統

(3.90.139.113) 您好!臺灣時間:2022/01/16 18:34
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:林雅雯
研究生(外文):ya-wen lin
論文名稱:應用Kd-Tree架構於TupleSpace的封包分類機制
論文名稱(外文):Adaptive Packet Classification Using Kd-Tree Based Tuple Space Search
指導教授:謝續平謝續平引用關係
指導教授(外文):Shiuh-Pyng Shieh
學位類別:碩士
校院名稱:國立交通大學
系所名稱:資訊工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:42
中文關鍵詞:封包分類
外文關鍵詞:packet classificationtuple spacekd-tree
相關次數:
  • 被引用被引用:0
  • 點閱點閱:297
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
為了提供封包不等同的服務,路由器(router)、防火牆(firewall)和端點路由器(edge router)必須能夠辨識網路封包,並根據管理者所訂定的規則(rule)分類封包,這樣的動作稱之為封包分類(packet classification)。封包分類的應用廣泛,除了可應用在提供服務品質(QoS)的路由器、提供安全保護的防火牆之外,尚可使用於網際網路服務提供者(ISP,Internet Service Provider)的端點路由器,以幫助企業建立虛擬私有網路(VPN,Virtual Private Network)。因此在過去幾年當中,許多研究者致力於設計適合高維應用的封包分類方法,希望能夠提供快速、低儲存量的分類機制。
在本篇論文當中,我們提出以Tuple space為基礎的封包分類機制,並使用多維的二元樹(multidimensional binary search tree)來改善搜尋的時間,可達到 的效能。除了滿足具彈性、可擴充的特性,同時還考慮到更新分類器(classifier)的需求及IDS的應用,提出低成本的擴充方式,使得我們的封包分類機制相對於其他方法具有較高的適應性。

Packet classification is to categorize network traffic in order to provide differential services to particular packet(s). It can be used within integrated or differentiated services in routers, security assurance in firewall and VPN tunnel, or payment in ISP edge routers. In last few years, many researchers were devoted to provide fast packet classification methods for high dimensional classifier. However, these methods either have undesirable performance and storage cost, or lack scalability of dimensions.
In this paper, we propose a packet classification method based on tuple space search, and use the multidimensional binary search tree (Kd-tree) to improve search performance in search time with controlled storage (where d is the number of dimensions, W is the number of bit length of fields). Moreover, it can be extended with little cost to support both incremental update for future use and IDS applications, which makes our method more adaptive than others.

Chapter 1 Introduction 1
1.1. Background 1
1.2. Contributions 3
1.3. Synopsis 4
Chapter 2 Related work 5
2.1. Data structure-based 5
2.2. Geometric-based 6
2.3. Heuristic-based 7
2.4. Comparison 9
2.5. Summary 10
Chapter 3 Kd-tree based Tuple space search 12
3.1. Definition 12
3.1.1. Conflict-free classifier 12
3.1.2. Tuple space 13
3.1.3. Tuple relationship 14
3.2. Kd-tree structure 15
3.3. Search 16
3.3.1. Resolution of Error-judged problem 17
3.3.2. Search procedure 18
3.3.3. Proof of binary search on tuple space 19
3.4. Summary 20
Chapter 4 Adaptation of Dynamic classifier 21
4.1. Problems of Kd-tree based Tuple space search 21
4.2. Randomized Kd-tree of tuples 22
4.3. Update 23
4.3.1. Insertion 23
4.3.2. Deletion 25
4.4. Summary 26
Chapter 5 Adaptation of IDS classifier 27
5.1. IDS classifier 27
5.1.1. IDS packet classification problem statement 28
5.2. Modifications 29
5.2.1. Data structure 30
5.2.2. Conflict detection and resolution algorithm 30
5.3. Summary 31
Chapter 6 Analysis 32
6.1. Complexity evaluation 32
6.2. Measurements 33
6.3. Comparison 34
Chapter 7 Conclusion 36
Reference 37

[Ahn01] H. K. Ahn, N. Mamoulis, and H. M. Wong, “A Survey on Multidimensional Access Methods,” technical report of UU-CS-2001-14, May 2001
[Beckmann90] N. Beckmann, H. P. Kriegel, R. Schneider, and B. Seeger, “The R*-tree: An efficient and robust access method for points and rectangles,” Proceedings of ACM SIGMOD, pages 322-331, 1990
[Bentley75] J. L. Bentley, “Multidimensional binary search trees used for associative searching,” Communications of the ACM, pages 509-517, 1975
[Berg97] M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Computational Geometry: Algorithms and Applications, Springer-Verlag, Heidelberg, 1997
[Böhm01] C. Böhm, S. Berchtold, and D. Keim, “Searching in High-dimensional Spaces: Index Structures for Improving the Performance of Multimedia Databases,” ACM Computing Surveys, 2001
[Brown98] L. Brown and L. Gruenwald, “Tree-Based Indexes for Image Data,” Journal of Visual Communication and Image Representation, volume 9, number 4, pages 300-313, December 1998
[Buddhikot99] M. M. Buddhikot, S. Suri, and M. Waldvogel, “Space Decomposition Techniques for Fast Layer-4 Switching,” Proceedings of Protocols for High Speed Networks, August 1999
[Decasper98] D. Decasper, Z. Dittia, G. Parulkar, and B. Plattner, “Router Plugins: A Software Architecture for Next Generation Routers,” Proceedings of ACM SIGCOMM, volume 28, number 4, October 1998
[Duch98] A. Duch, V. Estivill-Castro, and C. Martinez, “Randomized k-dimensional binary search trees,” Lecture Notes in Computer Science, volume 1533, pages 199-208, Taejon, Korea, December 1998
[Feldmann00] A. Feldmann and S. Muthukrishnan, “Tradeoffs for packet classification,” Proceedings of IEEE INFOCOM, volume 3, pages 1193-1202, March 2000
[Freeston95] M. Freeston, “A general solution to the n-dimensional B-tree problem,” Proceedings of ACM SIGMOD, San Jose, California, 1995
[Gaede98] V. Gaede, and O. Gunther, "Multidimensional access methods," ACM Computing Surveys, volume 30, number 2, June 1998
[Gupta99a] P. Gupta and N. McKeown, “Packet Classification on Multiple Fields,” Proceedings of ACM SIGCOMM, volume 29, number 4, Harvard University, October 1999
[Gupta99b] P. Gupta and N. McKeown, “Packet Classification using Hierarchical Intelligent Cuttings,” Proceedings of Hot Interconnects VII, Stanford, August 1999 (Also available in IEEE Micro, volume 20, number 1, January/February 2000)
[Gupta01] P. Gupta and N. McKeown, “Algorithms for Packet Classification,” IEEE Network Special Issue, volume 15, number 2, pages 24-32, March/April 2001
[Guttman84] A. Guttman, “R-tree: A Dynamic Index Structure for Spatial Search,” Proceedings of ACM SIGMOD, pages 47-57, June 1984
[Hari00] A. Hari, S. Suri, and G. Parulkar, “Detecting and Resolving Packet Filter Conflicts,” Proceedings of IEEE INFORCOM, pages 1203-1212, 2000
[Innella01] P. Innella and O. McMillan, “An Introduction to Intrusion Detection Systems,” SecurityFocus corporate site, December 2001 http://online.securityfocus.com/infocus/1520
[IPMA] http://www.merit.edu/~ipma/routing_table/
[Lakshman98] T.V. Lakshman, and D. Stiliadis, “High-Speed Policy-based Packet Forwarding Using Efficient Multi-dimensional Range Matching,” Proceedings of ACM SIGCOMM, volume 28, number 4, October 1998
[Lomet89] D. B. Lomet and B. Salzberg, “hB-tree: A Robust Multi-Attribute Search Structure,” Conference on Data Engineering, Los Angeles, California, February 1989
[Lomet90] D. B. Lomet and B. Salzberg, “The hb-tree: a multiattribute indexing method with good guaranteed performance,” ACM Transactions on Database Systems, volume 15, number 4, pages 625-658, 1990
[Mahmoud92] H. M. Mahmoud, Evolution of random search trees, A Wiley-Interscience, New York, 1992
[Martínez98] C. Martínez, and S. Roura, “Randomized Binary Search Trees,” Journal of the ACM, volume 45, number 2, pages 288-323, 1998
[Martínez01] C. Martínez, A. Panholzer, and H. Prodinger, “Partial match queries in relaxed multidimensional search trees,” Algorithmica, pages 181-204, 2001
[Motwani95] R. Motwani, and P. Raghavan, Randomized algorithms, Cambridge University Press, Cambridge, 1995
[Robinson81] J.T. Robinson, “The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes,” Proceedings of ACM SIGMOD, pages 10-18, 1981
[Roesch99] Martin Roesch, “Snort - Lightweight Intrusion Detection for Networks,” Proceedings of LISA '99, 13th Systems Administration Conference, Seattle, Washington, USA, November 1999
[Sellis87] T. Sellis, N. Roussopoulos, and C. Faloutsos, "The R+-tree: A dynamic index for multidimensional objects," Proceedings of Very Large Data Bases, pages 3-11, Brighton, England, 1987
[Srinivasan98] V. Srinivasan, G. Varghese, S. Suri, and M. Waldvogel, “Fast and Scalable Layer Four Switching,” Proceedings of ACM SIGCOMM, volume 28, number 4, October 1998
[Srinivasan99] V. Srinivasan, S. Suri, and G. Varghese, “Packet Classification using Tuple Space Search,” Proceedings of ACM SIGCOMM, volume 29, number 4, October 1999
[Srinivasan01] V. Srinivasan, “A Packet Classification and Filter Management System,” Proceedings of IEEE INFORCOM, Anchorage, Alaska USA, April 2001,
[Su00] C. F. Su, “High-speed packet classification using segment tree,” IEEE Conference of Global Telecommunications, volume 1, pages 582-586, November/December 2000
[Tsuchiya92] P. Tsuchiya, "A Search Algorithm for Table Entries with Non-contiguous Wildcarding," unpublished paper, 1992
[Warkhede97] P. Warkhede, G. Varghese, J. Turner, and B. Plattner, “Scalable High Speed IP Routing Lookups,” Proceedings of ACM SIGCOMM, volume 27, number 4, October 1997
[Warkhede01] P. Warkhede, S. Suri, and G. Varghese, “Fast Packet Classification for Two-Dimensional Conflict-Free Filters,” Proceedings of the IEEE INFORCOM, Anchorage, Alaska USA, April 2001

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top