跳到主要內容

臺灣博碩士論文加值系統

(3.235.174.99) 您好!臺灣時間:2021/07/24 20:15
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:王煜翔
研究生(外文):Yu-HsiangWang
論文名稱:用於封包分類之無規則重複決策樹
論文名稱(外文):A Non-Redundancy Decision Tree for Packet Classification
指導教授:張燕光
指導教授(外文):Yeim-Kuan Chang
學位類別:碩士
校院名稱:國立成功大學
系所名稱:資訊工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:英文
論文頁數:67
中文關鍵詞:FPGA封包分類決策樹管線化設計
外文關鍵詞:FPGApacket classificationdecision tree based algorithmspipeline
相關次數:
  • 被引用被引用:0
  • 點閱點閱:316
  • 評分評分:
  • 下載下載:95
  • 收藏至我的研究室書目清單書目收藏:0
封包分類在現今高速路由器中是一個重要的功能,它提供了許多服務例如VPN, QoS以及 防火牆。為了到達連線速率超過40Gbps的效能(OC-768),我們需要硬體架構來支援。因為在硬體環境如FPGA上的on-chip記憶體是有限的,如果不能把所有資料結構存進FPGA的on-chip記憶體,那我們效能就會被額外記憶體裝置的讀取速度拖慢。決策樹演算法如 HiCuts, HpyerCuts以及 HpyerSplit都有規則複製的問題,這會使得我們花費的儲存空間太龐大。在這個論文中,我們提出一個不會產生任何規則複製的切點演算法叫做CubeCuts,它是一個二元切割演算法並且建造多棵決策樹。CubeCuts先依照互斥的關係對rule table作分組再對搜尋空間使用hypercube的觀念來切割。在CubeCuts中,一個節點的位址空間被分為兩塊,一個在切下的hypercube裡面另一個在切下的hypercube外面。我們並提出如何計算所需hypercube的heuristic。然而在超過15K的Firewall及IPC中會發生歪斜樹的情形,所以我們提出修改的heuristic去解決它。在提出的CubeCuts之下,我們可以產生一個有效率運用儲存空間的資料結構,我們可以讓高達到五萬筆規則的ACL table,兩萬筆規則的Firewall table及一萬五千筆規則的IPC table 存進FPGA的on-chip記憶體之中。我們的演算法在硬體設計上非常適合管線化設計跟平行運算設計。在硬體實作的模擬中,每個封包大小假設為40bytes,我們的硬體設計可以達到每秒184 Gbits的高速效能,這足夠來處理現今路由器的大量流量附載。
Packet Classification is one of the most important services provided by high speed Internet routers nowadays. To obtain the throughput of higher than 40Gbps (OC-768) , we need the hardware architecture support. If the entire data structure cannot be stored in on-chip memory of FPGA devices, the packet classification performance will be slowed down by external storage device. Decision tree based algorithms, such as HiCuts, HyperCuts and HyperSplit, have rule replication problem which might cause memory storage explosion. In this thesis, we propose a new scheme called CubeCuts that does not generate any rule replication. CubeCuts is a binary cutting scheme that constructs multiple decision trees. CubeCuts partitions the rule table by disjoint relationship and separates the search space by using the concept of hypercube. The address space of a node in CubeCuts decision tree is separated into the one inside the cut hypercube and the other one outside the cut hypercube. A heuristic to compute how to cut the hypercube is proposed. However, the skewed tree problem occurs in the Firewall and IPC tables of more than 15K rules. Therefore, a modified heuristic is also proposed to solve the skewed tree problem. Based on the proposed CubeCuts, we can have a memory-efficient data structure such that ACL table of 50K rules, Firewall table of 20K rules, and IPC table of 15K rules can be fit into the on-chip memory of FPGA. Our design is suitable to be implemented with parallel and pipeline architecture. The hardware implementation can achieve a throughput of 184 Gbps, which is enough to accommodate the Internet traffic that is growing rapidly in recent years.
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Organization of The Thesis 2
Chapter 2 Background 3
2.1 Packet Classification Problem 3
Chapter 3 Related Work 7
3.1 Introduction 7
3.2 Binary Trie and Multi-bits Trie 7
3.3 Trie Based Solution in Packet Classification 10
3.4 Decision Tree Based Algorithm 14
3.5 HiCuts and HyperCuts 15
3.6 HyperSplit 18
3.7 Multiple Decision Tree Algorithm 20
Chapter 4 Proposed Scheme 22
4.1 Introduction 22
4.2 Grouping Phase 22
4.3 Space Decomposition Phase 25
4.4 Search Process 31
4.5 Optimization 32
4.6 Balance Tree Problem 37
Chapter 5 Hardware Architecture 38
5.1 Introduction 38
5.2 Architecture Overview 38
5.3 Memory Mapping 40
5.4 Architecture of Search Engine 45
Chapter 6 Performance Evaluation 50
6.1 Introduction 50
6.2 Dataset and Environment Setup 50
6.3 Software Evaluation 51
6.4 Hardware Performance 59
Chapter 7 Conclusions 64
References 65

[1]F. Baboescu and G. Varghese. “Scalable Packet Classification, Proc. ACM SIGCOMM, vol. 31, pp. 199–210, Oct. 2001.
[2]Y.-K. Chang, Efficient Multidimensional Packet Classification with Fast Updates, Proc. IEEE Trans. Computers, vol. 58, no. 4, pp. 463-479, Apr. 2009.
[3]Y.-K. Chang, H.-C. Chen, Layered Cutting Scheme for Packet Classification, Proc. Advanced Information Networking and Applications, pp. 675-681, 2011.
[4]Y.-K. Chang and H.-M. Chen, Set Pruning Segment Trees for Packet Classification, Proc. Advanced Information Networking and Applications, pp. 688-694, 2011.
[5]Y.-K. Chang, Y.-S. Lin and C.-C. Su, “A High-Speed and Memory Efficient Pipeline Architecture for Packet Classification, Proc. IEEE FCCM, pp. 215-218, 2010.
[6]S. Dharmappurikar, H. Song, J. Turner, and J. Lockwood, “Fast Packet Classification Using Bloom Filters, Proc. ACM/IEEE ANCS, 2006.
[7]P. Gupta and N. McKeown, “Packet Classification Using Hierarchical Intelligent Cuttings, Proc. Hot Interconnects VII, 1999.
[8]P. Gupta and N. McKeown. “Packet Classification on Multiple Fields, Proc. ACM SIGCOMM, vol. 29, pp. 147–160, Oct. 1999.
[9]W. Jiang and V. K. Prasanna. “Energy-Efficient Multi-Pipeline Architecture for Terabit Packet Classification, Proc. GLOBECOM, pp. 1-6, 2009.
[10]W. Jiang and V. K. Prasanna. “Large-Scale Wire-Speed Packet Classification on FPGAs, Proc. FPGA, pp. 219-228, 2009.
[11]W. Jiang, V. K. Prasanna and N. Yamagaki “Decision Forest: A Scalable Architecture for Flexible Flow Matching on FPGA, Proc. FPL, pp. 394- 399, 2010
[12]A. Kennedy, X. Wang, Z. Liu, and B. Liu, “Low Power Architecture for High Speed Packet Classification, Proc. ACM/IEEE ANCS, pp. 131-140, 2008.
[13]A. Nikitakis and I. Papaefstathiou, “A Memory-Efficient FPGA Based Classification Engine, Proc. IEEE FCCM, pp. 53-62, Apr. 2008.
[14]I. Papaefstathiou and V. Papaefstathiou, “Memory-Efficient 5D Packet Classification at 40 Gbps, Proc. IEEE INFOCOM, pp. 1370-1378, 2007.
[15]Y. Qi, L. Xu, B. Yang, Y. Xue, and J. Li. “Packet Classification Algorithms: From Theory to Practice, Proc. IEEE INFOCOM, pp. 648– 656, 2009.
[16]Y. Qi, J. Fong, W. Jiang, B. Xu, J. Li and V. K. Prasanna, “Multi-dimensional Packet Classification on FPGA: 100 Gbps and Beyond, Proc. Field-Programmable Technology, pp. 241-248, Dec. 2010.
[17]S. Singh, F. Baboescu, G. Varghese, and J. Wang, “Packet Classification using Multidimensional Cutting, Proc. ACM SIGCOMM, pp. 213-224, 2003.
[18]H. Song and J. W. Lockwood, “Efficient Packet Classification for Network Intrusion Detection Using FPGA, Proc. ACM FPGA, pp. 238-245, 2005.
[19]D. E. Taylor and J.S. Turner, “ClassBench: a packet classification benchmark, Proc. INFOCOM, vol.3, pp. 2068-2079, Mar. 2005.
[20]D. E. Taylor, “Survey and Taxonomy of Packet Classification Techniques, ACM Computing Surveys, vol. 37, no.3, pp.238-275, Sep. 2005.
[21]B. Vamanan, G. Voskuilen and T.N. Vijaykumar. “EffiCuts: Optimizing Packet Classification for Memory and Throughput, Proc. ACM SIGCOMM, pp. 207-218, 2010.
[22]Xilinx, Virtex-5 Family Overview, Product Specification, DS100 (v5.0), Feb. 6, 2009, at http://www.xilinx.com.
[23]H. C. Chen, “Recursive Endpoint Based Hyper-Cutting Scheme For Packet Classification, Unpublished thesis for degree of master of computer science and information engineering, National Cheng-Kung University, Tainan, Taiwan, R.O.C, 2011.

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊