簡易檢索 / 詳目顯示

回結果列表
研究生： 郭芳辰
Kuo, Fang-Chen
論文名稱： 在網路處理器上設計使用特殊快取之快速封包分類法
Fast Packet Classification with Specific Cache Design over Network Processors
指導教授： 張燕光
Chang, Yeim-Kuan
學位類別： 碩士
Master
系所名稱： 電機資訊學院 - 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年： 2006
畢業學年度： 94
語文別： 英文
論文頁數： 57
中文關鍵詞： 二元搜尋 、IXP2400 、網路處理器 、快取 、封包分類
外文關鍵詞： binary prefix search, network processor, cache, packet classification
相關次數： 點閱：78  下載：1 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 因為可以達到不錯的效能，同時又能保持開發的彈性，網路處理器成為近年來製作路由器的一個實作方式。現在的網路環境在封包分類(Packet Classification)上，不只是網路層，還會用到傳輸層的標頭(Header)。在此篇論文中，我們在IXP2400實作了一個五維的封包分類法，所採用的演算法比其他方法更為快速。
    我們又提出了一個新的快取架構來加強我們實作的封包分類法。傳統針對封包分類的快取架構，在快取失敗時會折損效能。而我們所提出的版本，不只會快取住封包的標頭，而且會快取住那些在搜尋過程中，跳到下一維的點的索引值。利用這個資訊，我們實作的封包分類法可得到加速的效果。這樣快取在失敗時，仍能對效能有所貢獻。

    To achieve high performance and still keep the flexibility, network processor has became a major implementation of router design. Nowadays network environment demands not only classification the packet with Layer 3 fields but also Layer 4 fields. In this paper, we implement a 5-D packet classification on Intel IXP2400 which base on the hierarchal binary prefix search. We also propose a cache scheme for our implement because of we observe that network traffic has strong locality. Traditionally cache scheme decrease the performance when cache miss. Our propose cache scheme does not only cache the packet header but also the node index which switch to next dimension in the search process. We can use the information to accelerate the implemented packet classification scheme. Thus the cache still has contribution even when cache misses.

    Chapter 1 Introduction 1 Chapter 2 Related Work 3 2.1 IP Lookup: 3 2.1.1 Binary Trie 3 2.1.2 Binary Prefix Search 4 2.1.2.1 Space Complexity Analysis 6 2.1.2.2 Search Time Complexity Analysis 6 2.2 2-D Packet Classification: 7 2.2.1 Grid-of-Trie 7 2.3 5-D Packet Classification: 10 2.3.1 Extended Grid-of-Trie 11 2.3.2 Packet Classification on Network Processor 11 2.4 Cache Scheme 12 2.4.1 Accuracy Tradeoff based Cache Scheme 13 Chapter 3 The Intel IXP 2400 Network Processor 15 3.1 Intel Exchange Network Processor (IXP): 15 3.2 Intel IXP2400 Overview: 16 3.3 XScale Core: 17 3.4 Microengine (MEv2): 18 3.4.1 Threads and Thread Arbitration: 18 3.4.2 Registers: 19 3.4.2.1 General Purpose Registers 20 3.4.2.2 SRAM Transfer Register 20 3.4.2.3 DRAM Transfer Register 20 3.4.2.4 Next neighbor Register 21 3.4.3 Local Memory: 21 3.4.4 Content-addressable Memory: 21 3.5 Memory Interface: 21 3.5.1 Scratchpad 22 3.5.2 SRAM 22 3.5.3 DRAM 22 3.6 Media Switch Fabric Unit (MSF): 22 3.7 SHaC Unit: 23 Chapter 4 Implemented Packet Classification and proposed cache scheme 24 4.1 2-D Binary Prefix Search 24 4.1.1 Space Complexity Analysis 27 4.1.2 Search Time Complexity Analysis 28 4.2 5D Binary Prefix Search 29 4.2.1 Space Complexity Analysis 30 4.2.2 Search Time Complexity Analysis 30 4.3 Implement Packet Classification on IXP2400 31 4.4 Cache Scheme for Binary Prefix Search 39 Chapter 5 Performance Evaluation 42 5.1 Simulation Setting 42 5.2 IP Lookup Performance Evaluation 43 5.2.1 Routing Table 44 5.2.2 Performance Evaluation for Binary Prefix Search 44 5.3 5-D Packet Classification Performance Evaluation 46 Chapter 6 Conclusion 54 Reference 55

    [1] BGP Routing Table Analysis Reports, http://bgp.potaroo.net/
    [2] David E. Taylor, “Surveys and Taxonomy of Packet Classification Techniques”, ACM Computing Surveys, Vol. 37, No. 3, pp. 238-275, Sep. 2005.
    [3] David E. Taylor and Jonathan S. Turner, “ClassBench: a packet classification benchmark”, INFOCOM 2005, Volume 3, pp. 2068-2079, 13-17 March 2005
    [4] Deepa Srinivasan and Wu-chang Feng, “Performance Analysis of Multi-dimensional Packet Classification on Programmable Network Processors”, Computer Communications, Volume 28, Issue 15, pp. 1752-1760, 15 September 2005.
    [5] D. Meyer, University of Oregon Route Views Archive Project, at http://archive.routeviews.org/
    [6] Florin Baboescu, Sumeet Singh, and Geroge Varghese, “Packet Classification for Core Routers: Is there an alternative to CAMs?”, INFOCOM 2003, Volume 1, pp. 53-63, 30 March-3 April 2003.
    [7] Francis Chang, Wu-chang Feng, and, Kang Li, “Approximate Caches for Packet Classification”, INFOCOM 2004, Volume 4, 7-11 March 2004.
    [8] Francis Chang, Wu-chang Feng, Wu-chi Feng, Kang Li “Efficient Packet Classification with Digest Caches”, HPCA NP3 Workshop, February 2004
    [9] Gupta P., McKeown N., “Algorithms for packet classification”, Network, IEEE, Volume 15, Issue 2, pp. 24-32, Mar.-Apr. 2001.
    [10] Intel Corporation, “Intel IXP2400 Network Processor Hardware Reference Manual”, Nov. 2003.
    [11] Intel Corporation, “Intel IXP2400/IXP2800 Network Processor Programmer’s Reference Manual”, Nov. 2003.
    [12] Kartik Gopalan and Tzi-cker Chiueh, “Improving Route Lookup Performance Using Network Processor Cache”, Supercomputing, ACM/IEEE 2002 Conference, pp. 22-22, 16-22 Nov. 2002.
    [13] Liqin Tian, Chuang Lin, Zhangxi Tan, “A Fast Packet Classification Algorithm Based on Classifier’s Characteristic Applying to Multi-fields”, Communication Technology Proceedings, 2003. ICCT 2003. International Conference on, Volume 1, pp. 255-258, 9-11 April 2003.
    [14] RadiSys Corporation, “ENP-2611 Hardware Reference”, Aug. 2003.
    [15] Ruiz-Sanchez, M.A., Biersack, E.W., Dabbous, W., “Survey and taxonomy of IP address lookup algorithms”, Network, IEEE, Volume 15, Issue 2, pp. 8-23, Mar.-Apr. 2001.
    [16] T. V. Lakshman, D. Stiliadis, “High-speed policy-based packet forwarding using efficient multi-dimensional range matching”, SIGCOMM ’98, Volume 28 Issue 4, October 1998.
    [17] V. Srinivasan, Geroge Varghese, S. Suri, M. Waldvogel, “Fast and scalable layer four switching”, SIGCOMM ’98, Volume 28 Issue4, Oct. 1998.
    [18] Yeim-Kuan Chang, “Fast Binary and Multiway Prefix Searches for Packet Forwarding”, Computer Networks, Accepted to be published.
    [19] Yie-Tarng Chen and Shin-Shian Lee, “An Efficient Packet Classification Algorithm for Network Processors”, Communications, 2003. ICC ‘03. IEEE International Conference on, Volume 3, pp. 1596-1600, 11-15 May 2003.
    [20] Ying-Dar Lin, Yi-Neng Lin, Shun-Chin Yang, and Yu-Sheng Lin, “DiffServ edge routers over network processors: implementation and evaluation”, Network, IEEE Volume 17, Issue 4, pp. 28-34, July-Aug. 2003.
    [21] Yiyan Tang, Lie Qian, Bashar Bou-Diab, Anand Krishnamurthy, Gerard Damm, and Yuke Wang, “High-performance implementation for graph-based packet classification algorithm on network processor”, Communications, 2004 IEEE International Conference on, Volume 2, pp. 1268-1272, 20-24 June 2004.
    [22] Zhen Liu, Kai Zheng, and Bin Liu, “Hybrid Cache Architecture for High Speed Packet Processing”, High Performance Interconnects, 2005. Proceedings. 13th Symposium, pp. 67-72, 17-19 Aug. 2005.

    下載圖示 校內：2007-08-18公開
    校外：2008-08-18公開
    QR CODE