网络处理器包传输结构的研究
|
摘要
作为推动今后网络发展的一项核心技术，网络处理器越来越受到集成电路产业界的关注，国内外的许多公司和研究机构纷纷展开了网络处理器的相关研发。网络处理器是一种全新的基于网络协议处理的可编程RISC处理器，作为今后网络主干设备如交换机、路由器中的核心部件，它结合了通用处理器的高灵活性和专用包处理器芯片的高性能特征，针对网络协议处理进行专门的优化设计，达到网络IP包的线速处理以及越来越复杂的网络应用要求。
包传输(或包转换)单元(Packet Transfer Unit，PTE)是网络处理器中负责IP包协议处理的核心模块，完成IP包在转发过程中的分析处理。PTE上行通道(Ingress)完成数据包从MAC层接口向交换架构(Switch Fabric)的传输；下行通道完成数据包从交换架构向MAC层接口的传输。在PTE的处理流程中包括两个关键的过程：1、保证相关IP包的转发顺序：2、快速的完成路由查找。
路由查找决定IP包下一站转发的端口，路由查找过程是网络处理器处理流程的一个重要组成部分，快速有效的路由查找是网络处理器实现线速转发的一个重要条件。
本文对网络处理器体系结构以及PTE模块做了研究，主要研究工作主要包括三个方面：
1、对网络处理器体系结构做了较全面的研究，讨论了网络处理器的功能特征和网络处理器体系结构的编程性、并行处理、协处理单元、多线程以及深层数据处理等方面的特征。
2、以nP3400网络处理器为基本参考模型，对PTE模块进行了详细的设计和分析，在此基础上，讨论了IP数据包在并行处理过程中逆序的问题，在PTE的设计中加入了避免IP包逆序的机制，并做了设计模型的功能仿真和相关分析。
3、引入基于快速最长前缀匹配的路由查找机制，该机制以转发表的面积和查找速度为目标对路由查找方案进行优化。本文对该路由查找机制的原理做了深入的研究，在此基础上对该机制做了模型的设计、功能上的仿真以及性能的分析。
本课题属预研性课题，旨在为将来对网络处理器这个新兴领域的研究积累经验。面对网络处理器这个新兴的科研领域以及目前研究发展状况善不成熟的局面，对这个课题的研究存在很大的难度。在没有任何现成研究成果的情况下，本文作者从功能需求分析入手，通过收集和阅读大量的文献资料自行展开了本课题的研究工作。
As a core technology on promoting the future network, network processor (NP) is being given more and more attention in IC field, and there are many companies and institutions researching on NP. Based on network protocol processing, NP is a new type of RISC processor with special architectural features that are optimized to perform packet-processing functions. This type of processor has emerged to cope with the ever-changing networking applications that are becoming increasingly complex, and will be the core component of new types of backbone devices such as routers and switches.
Packet Transfer Unit (PTE) is one of the most important units of NP, which is responsible for packet analyzing and processing. There are two lanes in PTE, one is ingress lane, in which packets are transmitted from MAC to Switch Fabric, and the other is egress lane, in which packets are transmitted from Switch Fabric to MAC. In the process flow of PTE two important points are included:
1. Ensuring forwarding sequence of packets;
2. Finishing routing lookup with high rate.
The primary work of research and design in this paper includes:
1. Giving an entire research of NP's architecture, discussing some key features of NP including Programming, Parallel Processing, Coprocessors, Multithread and Intelligent Processing.
2. Designing PTE, with the architecture of AMCC nP3400 as a source reference. Adding a scheme to this design, which is in order to ensrue forwarding sequence of packets. Doing function simulation for the design of PTE, with emphasis on this scheme.
3. Introducing a fast IP routing lookup scheme, designing the modle of this lookup scheme, and analyzing performance for this design.
This thesis is for the purpose of accumulating experience on research of NP. In the case of having little achievement at hand, the author has undertaken research from function demand.
包传输(或包转换)单元(Packet Transfer Unit，PTE)是网络处理器中负责IP包协议处理的核心模块，完成IP包在转发过程中的分析处理。PTE上行通道(Ingress)完成数据包从MAC层接口向交换架构(Switch Fabric)的传输；下行通道完成数据包从交换架构向MAC层接口的传输。在PTE的处理流程中包括两个关键的过程：1、保证相关IP包的转发顺序：2、快速的完成路由查找。
路由查找决定IP包下一站转发的端口，路由查找过程是网络处理器处理流程的一个重要组成部分，快速有效的路由查找是网络处理器实现线速转发的一个重要条件。
本文对网络处理器体系结构以及PTE模块做了研究，主要研究工作主要包括三个方面：
1、对网络处理器体系结构做了较全面的研究，讨论了网络处理器的功能特征和网络处理器体系结构的编程性、并行处理、协处理单元、多线程以及深层数据处理等方面的特征。
2、以nP3400网络处理器为基本参考模型，对PTE模块进行了详细的设计和分析，在此基础上，讨论了IP数据包在并行处理过程中逆序的问题，在PTE的设计中加入了避免IP包逆序的机制，并做了设计模型的功能仿真和相关分析。
3、引入基于快速最长前缀匹配的路由查找机制，该机制以转发表的面积和查找速度为目标对路由查找方案进行优化。本文对该路由查找机制的原理做了深入的研究，在此基础上对该机制做了模型的设计、功能上的仿真以及性能的分析。
本课题属预研性课题，旨在为将来对网络处理器这个新兴领域的研究积累经验。面对网络处理器这个新兴的科研领域以及目前研究发展状况善不成熟的局面，对这个课题的研究存在很大的难度。在没有任何现成研究成果的情况下，本文作者从功能需求分析入手，通过收集和阅读大量的文献资料自行展开了本课题的研究工作。
As a core technology on promoting the future network, network processor (NP) is being given more and more attention in IC field, and there are many companies and institutions researching on NP. Based on network protocol processing, NP is a new type of RISC processor with special architectural features that are optimized to perform packet-processing functions. This type of processor has emerged to cope with the ever-changing networking applications that are becoming increasingly complex, and will be the core component of new types of backbone devices such as routers and switches.
Packet Transfer Unit (PTE) is one of the most important units of NP, which is responsible for packet analyzing and processing. There are two lanes in PTE, one is ingress lane, in which packets are transmitted from MAC to Switch Fabric, and the other is egress lane, in which packets are transmitted from Switch Fabric to MAC. In the process flow of PTE two important points are included:
1. Ensuring forwarding sequence of packets;
2. Finishing routing lookup with high rate.
The primary work of research and design in this paper includes:
1. Giving an entire research of NP's architecture, discussing some key features of NP including Programming, Parallel Processing, Coprocessors, Multithread and Intelligent Processing.
2. Designing PTE, with the architecture of AMCC nP3400 as a source reference. Adding a scheme to this design, which is in order to ensrue forwarding sequence of packets. Doing function simulation for the design of PTE, with emphasis on this scheme.
3. Introducing a fast IP routing lookup scheme, designing the modle of this lookup scheme, and analyzing performance for this design.
This thesis is for the purpose of accumulating experience on research of NP. In the case of having little achievement at hand, the author has undertaken research from function demand.
引文
[1] 《网络处理器的分析与研究》，谭章熹，任丰源，周文江 清华大学计算机科学与技术系。
[2] 《蓄势待发网络处理器》，周文江，http://sinbad.zhoubin.com 转载自微电脑世界。
[3] 《网络处理器概述》，http://sinbad.zhoubbin.com 转载自电子产品世界。
[4] 《网络处理器研发动态》，http://sinbad.zhoubbin.com 转载自电子产品世界。
[5] 《聚焦网络处理器，共塑“产业价值链”，打造NP新平台》，hnp://www.gkong.com。
[6] P.Gupta, S.Lin, and N.McKeown. "Routing Lookups in Hardware at Memory Access Speeds." IEEE INFOCOM'98, San Francisco, April 1998, Session 10B-1.
[7] A.McAuley, P.Francis. "Fast Routing Lookup Using CAMs." IEEE network Magazine,January 1992.
[8] B.Lampsonm, V.Srinivasan, and G. varghese, "IP Lookups using Multiway and Multicolumn Search," IEEE INFOCOM'98, San Francisco, April 1998, Session 10B-2.
[9] "Routing Lookups in Hardware at Memory Access Speeds", Pankaj Gupta, Steven Lin, and Nick McKeown, Computer Systems Laboratory, Standford University.
[10] "High-Speed Routing Table Lookups for Current and Next Generation Internet Routing", by Ernest Hampson Ⅲ.
[11] "Small Forwarding Tables for Fast Routing Lookups", Mikael Degermark, Andrej Brodnik Svante Carlsson, and Stephen Pink, Department of Computer Science and Electrical Engineering, Lulea University of Technology, Sweden.
[12] "Technologies and Building Blocks for Fast Packet Forwarding", Werner Bux, Wolfgang E. Denzel, Ton Engbersen, Andreas HerkerSdorf, and Ronald P. Luijten, IBM Research.
[13] "High-Performance IP Routing Table Lookup Using CPU Caching", Tzi-cker Chiueh, Prashant Pradhan, Computer Science Department, State University of New York at Stony Brook.
[14] "Scalable IP Lookup for Programmable Routers", David E. Taylor, John W. Lockwood, Todd S. Sproull, Jonathan S. Turner, David B. Parlour.
[15] "IXP2400/2800 Programming, the Complete Microengine Coding Guide", Erik J.Johnson, Aaron R.Kunze.
[16] MMC Network Processor Whitepaper, AMCC Inc, 2001.
[17] "A Flexible Accelerator for layer 7 Networking Applications", Gokhan Memik and William H.Mangione-Smith, Department of Electrical Engineering,University of California, Los Angeles.
[18] "High-Bandwidth Packet Switching on the Raw General-Purpose Archithcture", by Gleb Albertovich Chuvpilo.
[19] "Hardware Architecture for Protocol Processing", Tomas Henriksson.
[20] "Effects of a Hash-based Scheduler on Cache Performance in a Parallel Forwarding System", Weiguang shi, Mike H. MacGregor and pawel Gburzynski Department of Computing Science, University of Alberata, Edmonton, AB, T6G 2E8, Canada.
[21] "Fundamental architectural considerations for network processor". Mohammad Peyravian,
Jean Calvignac. IBM Corporation, P.O.Box 12195, Research Triangle Park, NC 27709, USA.
[22] "Handling of Packet Dependencies: A Critical Issue for Highly Parallel Network Processors", Stephen Melvin, FlowStorm, Inc. yale Patt, University of Texas, Austin.
[23] "Design Space Exploration of Network Processor Architectures", Lothar Thiele, Aamarjit Chakraborty, Matthias Gries, Simon Kunzli, Computer Engineering and Networks Laboratory, Swiss Federal Institute of Technology (ETH) Zurich, Switzerland.
[24] "On the Performance of Multithreaded Architectures for Network Processors", Patrick Crowley, Marc E.Fiuczynski, Jean-loup Baer, Technical Report 2000-10-01, Department of Computer Science & Engineering, University of Washington.
[25] "UnderStanding Network Processors", by Niraj Shah.
[26] "Design Tradeoffs for Embedded Network Processors", Tilman Wolf, Mark A.Franklin,Edward W. Spitznagel.
[27] "Network Processor Technologies", W. H. Mangione-Smith, G. Memik.
[28] "nP3400 Network Processor Reference Manual". AMCC Inc, 2001.
[29] 数据结构C语言版，严蔚敏 吴伟民编著，清华大学出版社，2003年
[30] "A Fast IP Routing Lookup Scheme for Gigabit Switching Routers". Nen-Fu Huang, Shi-Ming Zhao, Jen-Yi Pan, and Chi-An Su, Department of Computer Science, National Tsing Hua University, Taiwan.
[31] 《计算机网络技术》，蔡皖东编著，西安电子科技大学出版社，1999年。
[32] 《TCP／IP详解》，卷1：协议“TCP／IP Illustrated”Volume 1：The Protocols．(美) W．Richard Stevens 著，范建华，胥光辉 张涛等译，谢希仁 校，机械工业出版社，2000年4月。
[33] PowerNP NP4GS3, PowerNP NP2G, PowerNP Npe405 Embedded Processors, http://www.ibm.com.
[34] Network Processors, http://www.intel.com/design/network/products/npfamily.
[35] C-5 Product Summary Page, C-5E Procuct Summary Page, www.motorola.com.
[36] MMC, MMC Networks Debuts Third Generation Network Processor.
[37] 《VHDL程序设计》，曾繁泰，陈美金 著，清华大学出版社，2000年。
[38] 《硬件描述语言Verilog》(第四版)，刘明业，蒋敬旗，刁岚松 等译，清华大学出版社。
[39] 《计算机系统结构》，李学干，苏东庄，西安电子科技大学出版社，1991年。
[40] Shah N. Understanding network processors [MS.Thesis]. Berkeley: Department of Electrical Engineering and Computer Sciences, University of California, 2001.
[41] 专题——路由器包处理器芯片的设计，胡庆生，吴本春。
[42] M.Degermark, A.Brodnik, S.Carlsson, and S. Pink. "Small Forwarding Tables for Fast Routing Lookups." ACM SIGCOMM'97, Palais des Festivals, Cannes, France, pp.3-14.
[43] 《超大规模集成电路——系统和电路的设计原理》，高德远，康继吕，西北工业大学出版社，1989年12月。
[44] 《数字系统设计自动化》，薛宏熙，边计年，清华大学出版社，1996年。
[45] 《EDA技术与数字系统设计，包明，赵明富，陈渝光，北京航空航天大学出版社。
[2] 《蓄势待发网络处理器》，周文江，http://sinbad.zhoubin.com 转载自微电脑世界。
[3] 《网络处理器概述》，http://sinbad.zhoubbin.com 转载自电子产品世界。
[4] 《网络处理器研发动态》，http://sinbad.zhoubbin.com 转载自电子产品世界。
[5] 《聚焦网络处理器，共塑“产业价值链”，打造NP新平台》，hnp://www.gkong.com。
[6] P.Gupta, S.Lin, and N.McKeown. "Routing Lookups in Hardware at Memory Access Speeds." IEEE INFOCOM'98, San Francisco, April 1998, Session 10B-1.
[7] A.McAuley, P.Francis. "Fast Routing Lookup Using CAMs." IEEE network Magazine,January 1992.
[8] B.Lampsonm, V.Srinivasan, and G. varghese, "IP Lookups using Multiway and Multicolumn Search," IEEE INFOCOM'98, San Francisco, April 1998, Session 10B-2.
[9] "Routing Lookups in Hardware at Memory Access Speeds", Pankaj Gupta, Steven Lin, and Nick McKeown, Computer Systems Laboratory, Standford University.
[10] "High-Speed Routing Table Lookups for Current and Next Generation Internet Routing", by Ernest Hampson Ⅲ.
[11] "Small Forwarding Tables for Fast Routing Lookups", Mikael Degermark, Andrej Brodnik Svante Carlsson, and Stephen Pink, Department of Computer Science and Electrical Engineering, Lulea University of Technology, Sweden.
[12] "Technologies and Building Blocks for Fast Packet Forwarding", Werner Bux, Wolfgang E. Denzel, Ton Engbersen, Andreas HerkerSdorf, and Ronald P. Luijten, IBM Research.
[13] "High-Performance IP Routing Table Lookup Using CPU Caching", Tzi-cker Chiueh, Prashant Pradhan, Computer Science Department, State University of New York at Stony Brook.
[14] "Scalable IP Lookup for Programmable Routers", David E. Taylor, John W. Lockwood, Todd S. Sproull, Jonathan S. Turner, David B. Parlour.
[15] "IXP2400/2800 Programming, the Complete Microengine Coding Guide", Erik J.Johnson, Aaron R.Kunze.
[16] MMC Network Processor Whitepaper, AMCC Inc, 2001.
[17] "A Flexible Accelerator for layer 7 Networking Applications", Gokhan Memik and William H.Mangione-Smith, Department of Electrical Engineering,University of California, Los Angeles.
[18] "High-Bandwidth Packet Switching on the Raw General-Purpose Archithcture", by Gleb Albertovich Chuvpilo.
[19] "Hardware Architecture for Protocol Processing", Tomas Henriksson.
[20] "Effects of a Hash-based Scheduler on Cache Performance in a Parallel Forwarding System", Weiguang shi, Mike H. MacGregor and pawel Gburzynski Department of Computing Science, University of Alberata, Edmonton, AB, T6G 2E8, Canada.
[21] "Fundamental architectural considerations for network processor". Mohammad Peyravian,
Jean Calvignac. IBM Corporation, P.O.Box 12195, Research Triangle Park, NC 27709, USA.
[22] "Handling of Packet Dependencies: A Critical Issue for Highly Parallel Network Processors", Stephen Melvin, FlowStorm, Inc. yale Patt, University of Texas, Austin.
[23] "Design Space Exploration of Network Processor Architectures", Lothar Thiele, Aamarjit Chakraborty, Matthias Gries, Simon Kunzli, Computer Engineering and Networks Laboratory, Swiss Federal Institute of Technology (ETH) Zurich, Switzerland.
[24] "On the Performance of Multithreaded Architectures for Network Processors", Patrick Crowley, Marc E.Fiuczynski, Jean-loup Baer, Technical Report 2000-10-01, Department of Computer Science & Engineering, University of Washington.
[25] "UnderStanding Network Processors", by Niraj Shah.
[26] "Design Tradeoffs for Embedded Network Processors", Tilman Wolf, Mark A.Franklin,Edward W. Spitznagel.
[27] "Network Processor Technologies", W. H. Mangione-Smith, G. Memik.
[28] "nP3400 Network Processor Reference Manual". AMCC Inc, 2001.
[29] 数据结构C语言版，严蔚敏 吴伟民编著，清华大学出版社，2003年
[30] "A Fast IP Routing Lookup Scheme for Gigabit Switching Routers". Nen-Fu Huang, Shi-Ming Zhao, Jen-Yi Pan, and Chi-An Su, Department of Computer Science, National Tsing Hua University, Taiwan.
[31] 《计算机网络技术》，蔡皖东编著，西安电子科技大学出版社，1999年。
[32] 《TCP／IP详解》，卷1：协议“TCP／IP Illustrated”Volume 1：The Protocols．(美) W．Richard Stevens 著，范建华，胥光辉 张涛等译，谢希仁 校，机械工业出版社，2000年4月。
[33] PowerNP NP4GS3, PowerNP NP2G, PowerNP Npe405 Embedded Processors, http://www.ibm.com.
[34] Network Processors, http://www.intel.com/design/network/products/npfamily.
[35] C-5 Product Summary Page, C-5E Procuct Summary Page, www.motorola.com.
[36] MMC, MMC Networks Debuts Third Generation Network Processor.
[37] 《VHDL程序设计》，曾繁泰，陈美金 著，清华大学出版社，2000年。
[38] 《硬件描述语言Verilog》(第四版)，刘明业，蒋敬旗，刁岚松 等译，清华大学出版社。
[39] 《计算机系统结构》，李学干，苏东庄，西安电子科技大学出版社，1991年。
[40] Shah N. Understanding network processors [MS.Thesis]. Berkeley: Department of Electrical Engineering and Computer Sciences, University of California, 2001.
[41] 专题——路由器包处理器芯片的设计，胡庆生，吴本春。
[42] M.Degermark, A.Brodnik, S.Carlsson, and S. Pink. "Small Forwarding Tables for Fast Routing Lookups." ACM SIGCOMM'97, Palais des Festivals, Cannes, France, pp.3-14.
[43] 《超大规模集成电路——系统和电路的设计原理》，高德远，康继吕，西北工业大学出版社，1989年12月。
[44] 《数字系统设计自动化》，薛宏熙，边计年，清华大学出版社，1996年。
[45] 《EDA技术与数字系统设计，包明，赵明富，陈渝光，北京航空航天大学出版社。