成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	許凱銘 Hsu, Kai-Ming
論文名稱：	在IXP1200網路處理器上設計快取來增進路由查表及封包分類的效能 Cache Design for Improving IP Lookups and Packet Classification in IXP1200 Network Processor
指導教授：	張燕光 Chang, Yeim-Kuan
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 資訊工程學系 Department of Computer Science and Information Engineering
論文出版年：	2004
畢業學年度：	92
語文別：	英文
論文頁數：	71
中文關鍵詞：	快取、封包分類、網路處理器
外文關鍵詞：	IXP1200, network processor, packet classification, cache
相關次數：	點閱：62 下載：1
分享至:	分享至facebook 分享至twitter

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

　　網路處理器具有軟體可程式化、硬體運算效能、以及高頻寬介面的優點，因此高效能的下一代路由器可採用網路處理器來實作。在本篇論文中，我們採用RadiSys 公司的ENP-2505 評估模板做為我們的開發環境，它包含了一顆IXP1200網路處理器晶片以及四個快速乙太網路介面(4*100Mbps)。我們設計的路由器是根據RFC1812的規範。除此之外，此路由器還包含了封包分類(packet classification)的程序，所採用的演算法是我們所提出的二元搜尋為基礎的五維度封包分類演算法，此演算法比其它演算法具有較快速且所耗用少量記憶體的優點，因此我們可以將之放置於快速的靜態記憶體(SRAM)中。再者，經由骨幹路由器(backbone router)的流量分析，我們發現它具有很高的時間區域性(temporal locality)，因此我們針對IXP1200系統架構提出了一個快取機制，此快取不僅僅只有記錄封包分類的結果，它還記錄了路由查表的結果。當快取命中時，此快取機制只須一次靜態記憶體讀取就能完成路由查表及封包分類。有了這樣的快取機制，在合理快取命中率的前提下，我們系統的效能將非常接近理論的最高頻寬。值得一提的是，在系統具有8192個快取單位時，具有快取機制的系統效能將勝過無快取機制的系統達百分之五十。

　　The high performance next generation routers are mostly implemented with network processors because of their software programmability, hardware computation power, and high bandwidth interface design. In this thesis, we use the RadiSys ENP-2505 evaluation board that consists of one IXP1200 network processor chip and four Ethernet ports (4*100Mbps) as our development environment. Our router design is based on RFC1812. In addition, we proposed a 5-dimensional packet classification algorithm based on binary prefix search. Our proposed 5-dimensional classification algorithm is faster and smaller than other schemes and makes it possible to be put in fast SRAM. Moreover, we proposed a cache mechanism for IXP1200 because we observed that the traffic patterns of backbone routers have a strong temporal locality. Our proposed cache scheme not only caches the results from packet classification but also caches the results from IP lookups. Only one SRAM-read is needed to perform IP Lookup and packet classification procedure for a cache hit. With this cache mechanism, the throughput of our system is very close to the theoretical maximum bandwidth with a reasonable hit ratio. Specifically, with a cache of 8192 entries, the proposed cache mechanism has 50% improvement in throughput over the system with no cache.

Contents
Chinese Abstract	I
English Abstract	II
Acknowledgment	        III
Contents		IV
List of Tables	        VI
List of Figures	        VII


Chapter 1 Introduction	                                                1
Chapter 2 IXP1200 Hardware Architecture and Development Environment	6
2.1 IXP1200 Overview	                                                6
2.2 StrongARM Core	                                                7
2.3 Microengines	                                                8
2.4 Memory interfaces	                                               11
2.5 FBI Units	                                                       11
2.6 Development Environment	                                       12
Chapter 3 Design and Implementation of IXP NetBench: 
        A High Performance Network Performance Analysis System	                                          15
3.1 Why we need to develop IXP NetBench.	                       15
3.2 IXP NetBench software architecture	                               17
3.3 IXP NetBench Performance.	                                       20
Chapter 4 Implementation of Robust Router using IXP1200	               23
4.1 Router Software Architecture.	                               23
4.2 Receive and Transmit Packets	                               27
4.2.1 Receive Packet Process	                                       28
4.2.2 Transmit Packet Process	                                       28
4.3 IP Lookups Algorithm.	                                       30
4.3.1 Binary Tries	                                               31
4.3.2 Multibit Tries	                                               32
4.4 Packet Classification Algorithm	                               35
4.5 Performance Analysis and Bottlenecks Discussion	               38
4.5.1 IXP Router Configuration	                                       39
4.5.2 Experiment Results	                                       40
4.5.3 Bottleneck Discussions	                                       42
   4.5.3.1 Partition the Task of Receive MicroEngine 
           into five categories	                                       42
   4.5.3.2 Simulation Results and Bottlenecks Discussion	       43
Chapter 5 Proposed Packet Classification Algorithm for IXP1200	       46
5.1 Binary Prefix Search	                                       46
5.2 Multi-Dimensional Packet Classification	                       49
5.3 Performance Evaluation	                                       53
5.3.1 Scalability Test	                                               54
5.3.2 Multi-Threads Test	                                       55
5.3.3 Multi-Microengine Test	                                       56
Chapter 6 Cache Design for IXP1200	                               58
6.1 Cache Structure	                                               58
6.2 Hit Ratio Analysis	                                               60
6.2.1 Component Analysis	                                       60
6.2.2 Trace Simulation	                                               63
6.3 Experiment Results on IXP1200 Enp-2505 board	               65
Chapter 7 Conclusion	                                               67
References 	                                                       69
                                    

[1] V. Fuller, T. Li, J. Yu and K. Varadhan. “Classless inter-domain routing (CIDR): an address assignment and aggregation strategy,” RFC 1519, September 1993.
[2] Intel Corporation, “IXP1200 Network Processor Datasheet”, 2000.
[3] RadiSys Corporation, “ENP2505 Hardware Reference”, 2002.
[4] Intel Corporation, “Development Tools User’s Guide”, March 2002.
[5] Intel Corporation, “IXA SDK 2.01 Developer’s Guide: Intel IXA SDK ACE Programming Framework,” December 2001.
[6] Intel Corporation, “SDK 2.01 Reference: IXA SDK 2.01 Developer’s Guide: Intel IXA SDK ACE Programming Framework,” December 2001.
[7] Intel Corporation, “Reference Manual: Intel® Microengine C Compiler Language Support,” August 2001.
[8] Intel Corporation, “Reference Guide: Intel® Microengine C Networking Library for the IXP1200 Network Processor,” December 2001.
[9] Erik J. Johnson and Asron R. Kunze, “IXP1200 Programming book,” 2002.
[10] M. A. Ruiz-Sanchez, E.W. Biersack, and W. Dabbous, “Survey and taxonomy of IP address lookup algorithms,” IEEE/ACM Trans. Networking, vol. 15, pp. 8–23, 2001.
[11] S. Nilsson and G. Karlsson "IP-Address Lookup Using LC-Tries," IEEE Journal on selected Areas in Communications, 17(6):1083-1092, June 1999.
[12] D. Meyer, "University of Oregon Route Views Archive Project”, http://archive.routeviews.org/.
[13] P. Gupta and N. McKeown, “Algorithms for Packet Classification,” IEEE/ACM Trans. Networking, vol.15, pp.24-32, 2001.
[14] V. Srinivasan, G. Varghese, S. Suri, and M. Waldvagel, “Fast and scalable layer four switching,” In Proc. ACM SIGCOMM’98, pp. 191–202, 1998.
[15] P. Tsuchiya. “A search algorithm for table entries with non-contiguous wildcarding,” unpublished report, Bellcore.
[16] F. Baboescu, S. Singh, and G. Varghese, “Packet Classification for Core Routers: Is there an alternativeto CAMs?,” In IEEE Infocom, 2003.
[17] A. Tirumala, M. Gates, F. Qin, J. Dugan and J. Ferguson. “Iperf - The TCP/UDP band-width measurement tool,” http://dast.nlanr.net/Projects/Iperf.
[18] Quinn O. Sell, Armin. R. Mikler and John L. Gustafson, “NetPIPE-A Network Protocol Independent Performance Evaluator,” http://www.scl.ameslab.gov/netpipe/, 2004.
[19] Hewlett Packard, “Netperf: A Network Performance Benchmark,” http:// www.netperf.org/netperf/NetperfPage.html, 1995.
[20] IEEE. Standard 802.3, October 2000.
[21] Ethereal, “The Ethereal User's Guide”, http:// www.ethereal.com.
[22] D. E. Taylor and J. S. Turner, “ClassBench: A Packet Classification Benchmark,” Tech. Rep. WUCSE-2004-28, Department of Computer Science & Engineering,Washington University in Saint Louis, May 2004.
[23] Yeim-Kuan Chang, “Fast Binary and Multiway Prefix Searches for Software-Based Routers”.
[24] Passive Measurement and Analysis project, National Laboratory for Applied Network Research, http://pma.nlanr.net/Traces/long/ipls1.html.
[25] Ying-Dar Lin, Yi-Neng Lin, Shun-Chin Yang and Yu-Sheng Lin, “DiffServ Edge Routers over Network Processor: Implementation and Evaluation,” IEEE Network, August 2003.

[26] T. Spalink, S. Karlin, L. Peterson and Y. Gottlieb, “Building a Robust Software-Based Router Using Network Processors, ” In Proc. of the 18th ACM Symposium on Operating Systems Principles (SOSP'01), October 2001.
[27] F. Baker, “Requirements for IP Version 4 Routers,” Request for Comments - 1812, Network Working Group, June 1995.

校內：2006-08-16公開
校外：2006-08-16公開

簡易檢索 / 詳目顯示

相關論文