跳到主要內容

臺灣博碩士論文加值系統

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

詳目顯示

我願授權國圖
: 
twitterline
研究生:林意勝
研究生(外文):I-sheng Lin
論文名稱:有效使用記憶體的管線化封包分類架構
論文名稱(外文):A Memory-Efficient Pipelined Architecture for Packet Classification
指導教授:張燕光
指導教授(外文):Yeim-kuan Chang
學位類別:碩士
校院名稱:國立成功大學
系所名稱:資訊工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:英文
論文頁數:70
中文關鍵詞:管線化設計封包分類
外文關鍵詞:Packet ClassificationFPGAPipelined ArchitectureSet Pruning Trie
相關次數:
  • 被引用被引用:0
  • 點閱點閱:105
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在一個高速的路由器中,為了能夠支援Quality of Service (QoS)、流量計費、網路安全和一些有附加價值的服務,多維度的封包分類是很重要的一個功能。現今的路由器設計的主要目標是想要達到40Gbps的產能,同時也能支援更大rule sets,但這是很難在軟體方法上被同時滿足,因此,在硬體上尋求解答是目前的趨勢。在此論文中,我們提出一個基於set pruning trie的管線化架構來解決多維度的封包分類,叫作Set Pruning Multi-Bit Trie (SPMT)。如同set pruning trie,不用backtracks的優點是很適合實作在管線化的架構設計中。然而,rule的複製是造成記憶體過度使用的主要問題,為了能夠實作SPMT並且能放入FPGA裝置中的晶載記憶體,這問題是一定要被解決的,我們將會提出兩個rule分組的方法來大量減少rule複製。在第一個方法中,rule會依照在相同維度中同時是一個或多個萬用字元來分組。第二個方法則是根據某一維的prefix長度來進行分組,動態規劃的技術則被用來挑選出最適合的一組prefix長度來將rule分組。我們使用Xilinx Virtex-5的FPGA裝置的實驗結果顯示我們所提出的管線化架構在使用雙端口記憶體下,可以達到超過100Gbps的產能,同時也可以支援10k的rule set,將之放入我們所使用的FPGA裝置中的晶載記憶體。
Multi-field Packet classification is a very important functionality in high-performance routers for supporting Quality of Service (QoS) differentiation, traffic billing, network security and other value-added services. The current router design goal of achieving a throughput of 40 Gbps and supporting large rule sets simultaneously is difficult to be fulfilled by software approaches. Thus, the current trend is towards the hardware implementation. In this thesis, a set pruning trie based pipelined architecture called Set Pruning Multi-Bit Trie (SPMT) is proposed for multi-field packet classification. As in the set pruning trie, SPMT needs no backtracks and thus is very suitable for a pipeline design. However, the problem of rule duplications in SPMT that may cause a memory blowup must be solved in order to implement SPMT with large rule sets in FPGA devices consisting of limited on-chip memory. We will propose two rule grouping schemes to reduce rule duplications in SPMT. In the first scheme, rules with one or more wildcards in the same fields are grouped into the same subgroup. In the second scheme, rules are grouped according to their prefix lengths. The dynamic programming technique is used for the second scheme to choose the best lengths to divide rules into subgroups. Based on our performance experiments on Xilinx Virtex-5 FPGA device, the proposed pipeline architecture can achieve a throughput of over 100 Gbps with dual port memory. Also, the rule sets of up to 10k rules can be fit into the on-chip memory of Xilinx Virtex-5 FPGA device.
Chapter 1 Introduction....................................1
1.1 Motivation............................................1
1.2 Organization of The Thesis............................2
Chapter 2 Background......................................4
2.1 Main Concern of Packet Classification.................4
2.2 Brief View of Packet Classification Scheme............6
Chapter 3 Related Works...................................8
3.1 Binary Trie...........................................8
3.2 Multi-Bit Trie........................................9
3.3 Converting Ranges to Prefixes........................10
3.4 Set Pruning Trie.....................................12
3.5 FPGA-Based Packet Classification Schemes.............15
3.5.1 Trie-Based Pipeline................................16
3.5.2 Decision Tree-Based Pipeline Scheme................17
3.5.3 TCAM-Based Packet Classification Engine............18
3.5.4 Packet Classification Engine Using Bloom Filter....20
3.6 The Main Idea of Simple k_set........................22
Chapter 4 Proposed Data Structure........................24
4.1 Motivation...........................................24
4.2 Set Pruning Multi-Bit Trie...........................25
4.3 Observation on The Rule Tables.......................28
4.4 Partitioned by Possible Positions with Wildcards.....32
4.5 Partition by Using Main Idea of Simple K_Set.........34
4.6 Partition and Using K_Set Simultaneously.............39
Chapter 5 Proposed Pipeline Architecture.................41
5.1 Architecture Overview................................41
5.2 Mapping Trie Nodes to Pipeline Stage.................43
5.3 Pipeline for Set Pruning Multi-Bit Trie..............44
5.3.1 Protocol Field Segmentation........................44
5.3.2 Memory Design......................................45
5.3.3 Pipeline Architecture and Match Process............48
Chapter 6 Performance....................................54
6.1 Simulation Environment...............................54
6.2 Software Evaluation..................................55
6.3 FPGA Implementation Results..........................62
Chapter 7 Conclusion and Future Works....................67
References...............................................68
[1]
Adam L. Buchsbaum, Glenn S. Fowler, Balachander Krishnamurthy, Kiem-Phong Vo, and Jia Wang, “Fast Prefix Matching of Bounded Strings,” ALENEX’03, pp. 128-139 2003.
[2]
Yeim-Kuan Chang, “Efficient Multidimensional Packet Classification with Fast Updates,” IEEE Transactions on Computers, Vol. 58, No. 4, pp. 463-479, Apr. 2009.
[3]
Y.-K. Chang, Y.-C. Lin, and K.-Y. Ho, “Update-aware Controlled Prefix Expansion for Fast IP Lookups,” In IEEE HPSR, 2009
[4]
Yeim-Kuan Chang, Yen-Cheng Liu, and Fang-Chen Kuo, “A pipeline IP Forwarding Engine with Fast Update,” IEEE International Conference on Advanced Information Networking and Applications, 2009.
[5]
S. Dharmapurikar, H. Song, J. Turner, and J. Lockwood, “Fast Packet Classification Using Bloom Filters,” In ACM/IEEE ANCS, 2006.
[6]
Pankaj Gupta, and Nick McKeown, “Packet Classification on Multiple Fields,” ACM SIGCOMM, pp. 147-160, Aug. 1999.
[7]
Pankaj Gupta, and Nick McKeown, “Packet Classification Using Hierarchical Intelligent Cutting,” Hot Interconnects VII, Aug. 1999.
[8]
Hypercut, http://www.arl.wustl.edu/~hs1/project/hypercuts.htm.
[9]
Gajanan S. Jedhe, Arun Ramamoorthy, and Kuruvilla Varghese, “A Scalable High Throughput Firewall in FPGA,” IEEE FCCM, 2008.
[10]
Weirong Jiang, and V. K. Prasanna, “Large-Scale Wire-Speed Packet Classification on FPGAs,” ACM FPGA’09, Feb. 2009.
[11]
Weirong Jiang and V. K. Prasanna, “Parallel IP Lookup using Multiple SRAM-based Pipelines,” In IEEE IPDPS, 2008.
69
[12]
W. Jiang and V. K. Prasanna, “A Memory-Balanced Linear Pipeline Architecture for Trie-Based IP Lookup,” In IEEE HOTI, 2007.
[13]
A. Kennedy, X. Wang, Z. Liu, and B. Liu. ”Low power architecture for high speed packet classification,” In Proc. ANCS, 2008.
[14]
Sailesh Kumar, Michela Becchi, Patrick Crowley, and Jonathan Turner, “CAMP: Fast and Efficient IP Lookup Architecture,” ACM ANCS’06, Dec. 2006.
[15]
Wencheng Lu, and Sartaj Sahni, “Packet Forwarding Using Pipeline Multibit Tries”, IEEE Symposium on Computers and Communications, 2006.
[16]
D. R. Morrison, “PATRICIA–Practical Algorithm to Retrieve Information Coded in Alpha Numeric,” Journal of the ACM, 1968.
[17]
Antonis Nikitakis, and Ioannis Papaefstathiou, “A Memory-Efficient FPGA-Based Classification Engine,” IEEE FCCM, 2008.
[18]
I. Papaefstathiou and V. Papaefstathiou, “Memory-Efficient 5D Packet Classification at 40 Gbps,” In IEEE INFOCOM, 2007.
[19]
Haoyu Song, and John W. Lockwood, “Efficient Packet Classification for Network Intrusion Detection Using FPGA,” ACM FPGA’05, Feb. 2005.
[20]
Summed Singh, Florin Baboescu, George Varghese and Jia Wang, “Packet Classification Using Multidimensional Cutting,” ACM SIGCOMM, Aug. 2003.
[21]
V. Srinivasan, and G. Varghese, “Fast Address Lookups Using Controlled Prefix Expansion,” ACM Transactions on Computer System, Vol. 17, No. 1, pp. 1-40, Feb. 1999.
[22]
V. Srinivasan, G. Varghese, S. Suri, and M. Waldvogel, “Fast and Scalable Layer Four Switching,” ACM SIGCOMM, pp.191-202, Aug. 1998.
[23]
David E. Taylor, “Survey and Taxonomy of Packet Classification Techniques,” ACM Computing Surveys, vol. 37, no.3, pp.238-275, Sep. 2005.
70
[24]
David E. Taylor, and J. S. Turner, “ClassBench: A Packet Classification Benchmark,” IEEE INFOCOM, May 2005.
[25]
Xilinx, "Virtex-5 Family Overview", Product Specification, DS100 (v5.0), Feb. 6, 2009, at http://www.xilinx.com.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊