网络处理器负载均衡和报文转发设计与实现
|
摘要
网络处理器是路由器中进行报文转发处理的关键部件。由于报文处理具有内在的并行性,网络处理器可采用多种并行技术来加速报文的处理。本文对网络处理器的并行体系结构进行了深入研究,将网络处理器的并行处理分三个层次,分别是PE(Processing Element,处理单元)内部并行,PE间并行和PE与协处理器间并行。
由于报文分配策略影响网络处理器并行性能,我们提出了HDW(Hash-based Dynamic Weight)负载分配算法,基于报文流标识与PE间建立映射关系,并将映射关系保存在哈希表中,映射关系基于HRW(Highest Random Weight)算法,增加了负载反馈回路监控PE负载状况,通过动态调整策略阻止PE间负载偏差。模拟结果显示,此算法可以明显的提高PE负载均衡性,减少报文流乱序概率。
最后本文在网络处理器原型验证平台上实现网络处理器芯片原型设计。网络处理器芯片原型采用Nios II软核处理器在FPGA上实现,提高了网络处理器的可编程能力。原型系统采用TCAM实现高速路由查找,利用软件实现IPv4报文转发功能。本文实现了Nios II启动微码、报文转发、数据包过滤软件模块设计。
Network processors are the key devices to forward packets in the routers. As there is inherent parallelism in the packets processing, network processors adopt many parallel technologies to accelerate the processing of the packets. The parallel architectures of the network processors are explored in this article and the parallel technologies adopted by the network processors are divided into three aspects. They are the parallelism inside the PEs(Processing Element), the parallelism between the PEs and the parallelism between PEs and coprocessors. The distribution schemes of packet influence the performance of parallelism.
As the scheme of packet distributed influence the performance of parallelism, in this paper, the HDW(Hash-based Dynamic Weight) scheme for allocation packets in network processors is presented. The scheme is building and keeping one mapping relationship between packets’identifier and PEs in a table of hash. The mapping formula is derived from the HRW( highest random weight ) scheme, it is complemented by a feedback control mechanism designed to monitor processor’s utilization. A dynamic extension to the HRW scheme is provided in order to cope with biased traffic patterns. Simulation results indicate that the scheme achieves significant improvements the load balance of processor and minimizes the probability of flow reordering.
On the validate platform of network processors, this paper implements the prototype of network processors chip. The prototype designs with soft-core processors of Nios II in FPGA, improves the programmability of network processors. It implements high-speed routing lookup based on TCAM and IPv4 packet forwarding function through software. We have designed and finished the software module development, including boot microcode of Nios II、packet forwarding and filtrating.
由于报文分配策略影响网络处理器并行性能,我们提出了HDW(Hash-based Dynamic Weight)负载分配算法,基于报文流标识与PE间建立映射关系,并将映射关系保存在哈希表中,映射关系基于HRW(Highest Random Weight)算法,增加了负载反馈回路监控PE负载状况,通过动态调整策略阻止PE间负载偏差。模拟结果显示,此算法可以明显的提高PE负载均衡性,减少报文流乱序概率。
最后本文在网络处理器原型验证平台上实现网络处理器芯片原型设计。网络处理器芯片原型采用Nios II软核处理器在FPGA上实现,提高了网络处理器的可编程能力。原型系统采用TCAM实现高速路由查找,利用软件实现IPv4报文转发功能。本文实现了Nios II启动微码、报文转发、数据包过滤软件模块设计。
Network processors are the key devices to forward packets in the routers. As there is inherent parallelism in the packets processing, network processors adopt many parallel technologies to accelerate the processing of the packets. The parallel architectures of the network processors are explored in this article and the parallel technologies adopted by the network processors are divided into three aspects. They are the parallelism inside the PEs(Processing Element), the parallelism between the PEs and the parallelism between PEs and coprocessors. The distribution schemes of packet influence the performance of parallelism.
As the scheme of packet distributed influence the performance of parallelism, in this paper, the HDW(Hash-based Dynamic Weight) scheme for allocation packets in network processors is presented. The scheme is building and keeping one mapping relationship between packets’identifier and PEs in a table of hash. The mapping formula is derived from the HRW( highest random weight ) scheme, it is complemented by a feedback control mechanism designed to monitor processor’s utilization. A dynamic extension to the HRW scheme is provided in order to cope with biased traffic patterns. Simulation results indicate that the scheme achieves significant improvements the load balance of processor and minimizes the probability of flow reordering.
On the validate platform of network processors, this paper implements the prototype of network processors chip. The prototype designs with soft-core processors of Nios II in FPGA, improves the programmability of network processors. It implements high-speed routing lookup based on TCAM and IPv4 packet forwarding function through software. We have designed and finished the software module development, including boot microcode of Nios II、packet forwarding and filtrating.
引文
[1] http:// www.idc.com
[2] Xu Ningyi, Liu Hong, Chen Xi. Zhou Zucheng. Implementation of DVB demultiplexer system with system-on-a-programmable-chip FPGA. Proceedings 5th International Conference, 2003:954-957
[3] F. Ghozzi, P. Nouel, P. Marchegay. Video acquisition and memorisation on Excalibur system. 2003:1275-1278
[4] M. Luthra, Sumit Gupta, Nikil Dutt, Rajesh Gupta, A. Nicolau. Interface synthesis using memory mapping for an FPGA platform. Computer Design. Proceedings. 21st International Conference, 2003:140-145
[5] Paul Metzgen. A High Performance 32-bit ALU for Programmable Logic. ACM FPGA, 2004: 61-70
[6] H.M.D.Ip, J.D.Low, P.Y.K. Cheung, G. Constantinides, W.Luk, S.P. Seng, P. Metzgen. Strassen's matrix multiplication for customisable processors. IEEE International Conference, 2002: 453-456
[7] M. Finc, A. Zemva. Rapid HW/SW co-design of softcore processor systems. IEEE, 2003: 104-108
[8] J. Kairus, J. Forsten, M. Tommiska, J. Skytta. Bridging the gap between future software and hardware engineers: a case study using the Nios softcore processor. IEEE, 2003: 1-5
[9] P.Crowley. Network Processor Design: Issues and Practices. Morgan Kaufmann Publishers, Volume 1, 2003
[10] Samuel J.Barnett, Mark R.Fauber. Network Processors: Uncovering Architectural Approaches for High-Speed Packet Processing. Vitesse Semiconductor, http://www.vitesse.com
[11] Mark Janoska. Co-Processors and the Role of Specialized Hardware. Networld InterOP2000, 2000
[12] 网络处理器章程,http:// www.npforum.org
[13] Niraj Shah. Understanding Network Processor. 2001
[14] IBM PowerNP NP4GS3 数 据 手 册 .IBM Networking Technology. http://www.chips.ibm.com/products/wired/communications/network_processors.html
[15] Intel IXP1200 数据手册. Intel Corporation, http://developer.intel.com/design/network/index.htm
[16] EZchip Technologies. Network Processor Designs for Next-Generation Networking Equipment. White Paper,http://www.ezchip.com/html/tech_r.html
[17] MMC Networks. Network Processing Platforms: Minimizing Total Time-to-Market. MMC Networks White Paper, http://www.mmcnetworks.com/Solutions
[18] Motorola Inc.http://www.motorola.com
[19] David G. Thaler, C.V.Ravishankar. Using name-based mappings to increase hit rates. IEEE/ACM Transactions on Networking, 1998: 1-14
[20] T.Brisco. DNS support for load balancing. RFC1794, 1995
[21] E. Katz, M. Butler, R. McGrath. A scalable HTTP server: TheNCSA prototype. Comput. Networks ISDN Systems, 1994:155–164
[22] Cisco Systems. Scaling the world wide web. http://cio.cisco.com/warp/public/751/advtg/swww_wp.htm, 2005
[23] M. Satyanarayanan. Scalable, secure, and highly available distributed file access. IEEE Comput. Mag., 1990:9-21
[24] D. Estrin, D. Farinacci, A. Helmy, D. Thaler, S. Deering, M. Handley,V. Jacobson, C.-G. Liu, P. Sharma, and L. Wei. Protocol independent multicast-sparse mode (PIM-SM): Specification. RFC2117, June 1997
[25] A.Ballardie. Core based trees (CBT version 2) multicast routing:Protocol specification. RFC2189, 1997
[26] D.L.Eager, E.D.Lazowska, J.Zahorjan. Adaptive load sharing in homogenous distributed systems. IEEE Transactions on Software Engineering, 1986:662-675
[27] B.A.Shirazi. Scheduling and Load Balancing in Parallel and Distributed Systems. IEEE CS Press, 1999
[28] G.Goldszmidt, G.Hunt. Scaling Internet services by dynamic allocation of connections. Proceedings of the Sixth IFIP/IEEE International Symposium on Integrated Network Management, 1999:171-184
[29] K.O.G.Barish. World Wide Web caching: trends and techniques. IEEE Communications Magazine, 2000:178-184
[30] T.L.Casavant, J.G.Kuhl. A taxonomy of scheduling in generalpurpose distributed computing systems. IEEE, 1998:141-154
[31] D. G. Thaler, C. V. Ravishankar. Using name-based mappings to increase hit rates. IEEE/ACM Transactions on Networking, 1998:1-14
[32] Altera. Nios II Custom Instruction User Guide. http://www.altera.com/literature/ug/ug_nios2_custom_instruction.pdf, 2005
[33] R.Braden, D.Borman, C.Partridge. Computing the Internet Checksum. RFC1071,1988
[34] A.Rijsinghani. Computation of the Internet Checksum via Incremental Update. RFC1624, 1994
[35] Y.Rekhter, T.Li. An Architecture for IP Address Allocation with CIDR. RFC1518, http://www. rfc.net/rfc1518.html. 1993
[36] W.Doeringer. Routing on Longest-Matching Prefixes.4 ed IEEE/ACM Trans. on Networking.1998:86-97
[37] Mikael Degermark, Andrej Brodnik, Svante Carlsson, Stephen Pink. Small forwarding tables for fast routing lookups. Proceedings of ACM SIGCOMM, 1997:3-13
[38] G. V. V Srinivasan . Faster IP Lookups using Controlled Prefix Expansion. ACM Sigmetrics, 1998:1-10
[39] P. M Waldvogel. Scalable high speed IP routing lookups. Proceedings of ACM SIGCOMM, 1997:25-36
[40] G. K. S.Nilsson. Fast Address Look-Up for Internet Routers. Proc. of IEEE Broadband Communications, 1998
[41] Nen-Fu Huang ,Shi-Ming Zhao.A fast IP routing lookup scheme for gigabit switching routers. IEEE INFOCOM, 1999:1429-1436
[42] Nen-Fu Huang ,Shi-Ming Zhao. A novel IP routing lookup scheme and hardware architecture for multigigabit switching routers. IEEE JSAC, 1999: 1093-1104
[43] Anthony J.McAuley, Paul Francis. Fast Routing Table Lookup Using CAMs. INFOCOM '93, IEEE, 1993:1382-1391
[44] T.B.Pei. Putting Routing Tables in Silicon. IEEE, 1992: 42-50
[45] P.Gupta. Routing Lookups in Hardware at Memory Access Speeds. Proc. IEEE Infocom'98, 1998
[2] Xu Ningyi, Liu Hong, Chen Xi. Zhou Zucheng. Implementation of DVB demultiplexer system with system-on-a-programmable-chip FPGA. Proceedings 5th International Conference, 2003:954-957
[3] F. Ghozzi, P. Nouel, P. Marchegay. Video acquisition and memorisation on Excalibur system. 2003:1275-1278
[4] M. Luthra, Sumit Gupta, Nikil Dutt, Rajesh Gupta, A. Nicolau. Interface synthesis using memory mapping for an FPGA platform. Computer Design. Proceedings. 21st International Conference, 2003:140-145
[5] Paul Metzgen. A High Performance 32-bit ALU for Programmable Logic. ACM FPGA, 2004: 61-70
[6] H.M.D.Ip, J.D.Low, P.Y.K. Cheung, G. Constantinides, W.Luk, S.P. Seng, P. Metzgen. Strassen's matrix multiplication for customisable processors. IEEE International Conference, 2002: 453-456
[7] M. Finc, A. Zemva. Rapid HW/SW co-design of softcore processor systems. IEEE, 2003: 104-108
[8] J. Kairus, J. Forsten, M. Tommiska, J. Skytta. Bridging the gap between future software and hardware engineers: a case study using the Nios softcore processor. IEEE, 2003: 1-5
[9] P.Crowley. Network Processor Design: Issues and Practices. Morgan Kaufmann Publishers, Volume 1, 2003
[10] Samuel J.Barnett, Mark R.Fauber. Network Processors: Uncovering Architectural Approaches for High-Speed Packet Processing. Vitesse Semiconductor, http://www.vitesse.com
[11] Mark Janoska. Co-Processors and the Role of Specialized Hardware. Networld InterOP2000, 2000
[12] 网络处理器章程,http:// www.npforum.org
[13] Niraj Shah. Understanding Network Processor. 2001
[14] IBM PowerNP NP4GS3 数 据 手 册 .IBM Networking Technology. http://www.chips.ibm.com/products/wired/communications/network_processors.html
[15] Intel IXP1200 数据手册. Intel Corporation, http://developer.intel.com/design/network/index.htm
[16] EZchip Technologies. Network Processor Designs for Next-Generation Networking Equipment. White Paper,http://www.ezchip.com/html/tech_r.html
[17] MMC Networks. Network Processing Platforms: Minimizing Total Time-to-Market. MMC Networks White Paper, http://www.mmcnetworks.com/Solutions
[18] Motorola Inc.http://www.motorola.com
[19] David G. Thaler, C.V.Ravishankar. Using name-based mappings to increase hit rates. IEEE/ACM Transactions on Networking, 1998: 1-14
[20] T.Brisco. DNS support for load balancing. RFC1794, 1995
[21] E. Katz, M. Butler, R. McGrath. A scalable HTTP server: TheNCSA prototype. Comput. Networks ISDN Systems, 1994:155–164
[22] Cisco Systems. Scaling the world wide web. http://cio.cisco.com/warp/public/751/advtg/swww_wp.htm, 2005
[23] M. Satyanarayanan. Scalable, secure, and highly available distributed file access. IEEE Comput. Mag., 1990:9-21
[24] D. Estrin, D. Farinacci, A. Helmy, D. Thaler, S. Deering, M. Handley,V. Jacobson, C.-G. Liu, P. Sharma, and L. Wei. Protocol independent multicast-sparse mode (PIM-SM): Specification. RFC2117, June 1997
[25] A.Ballardie. Core based trees (CBT version 2) multicast routing:Protocol specification. RFC2189, 1997
[26] D.L.Eager, E.D.Lazowska, J.Zahorjan. Adaptive load sharing in homogenous distributed systems. IEEE Transactions on Software Engineering, 1986:662-675
[27] B.A.Shirazi. Scheduling and Load Balancing in Parallel and Distributed Systems. IEEE CS Press, 1999
[28] G.Goldszmidt, G.Hunt. Scaling Internet services by dynamic allocation of connections. Proceedings of the Sixth IFIP/IEEE International Symposium on Integrated Network Management, 1999:171-184
[29] K.O.G.Barish. World Wide Web caching: trends and techniques. IEEE Communications Magazine, 2000:178-184
[30] T.L.Casavant, J.G.Kuhl. A taxonomy of scheduling in generalpurpose distributed computing systems. IEEE, 1998:141-154
[31] D. G. Thaler, C. V. Ravishankar. Using name-based mappings to increase hit rates. IEEE/ACM Transactions on Networking, 1998:1-14
[32] Altera. Nios II Custom Instruction User Guide. http://www.altera.com/literature/ug/ug_nios2_custom_instruction.pdf, 2005
[33] R.Braden, D.Borman, C.Partridge. Computing the Internet Checksum. RFC1071,1988
[34] A.Rijsinghani. Computation of the Internet Checksum via Incremental Update. RFC1624, 1994
[35] Y.Rekhter, T.Li. An Architecture for IP Address Allocation with CIDR. RFC1518, http://www. rfc.net/rfc1518.html. 1993
[36] W.Doeringer. Routing on Longest-Matching Prefixes.4 ed IEEE/ACM Trans. on Networking.1998:86-97
[37] Mikael Degermark, Andrej Brodnik, Svante Carlsson, Stephen Pink. Small forwarding tables for fast routing lookups. Proceedings of ACM SIGCOMM, 1997:3-13
[38] G. V. V Srinivasan . Faster IP Lookups using Controlled Prefix Expansion. ACM Sigmetrics, 1998:1-10
[39] P. M Waldvogel. Scalable high speed IP routing lookups. Proceedings of ACM SIGCOMM, 1997:25-36
[40] G. K. S.Nilsson. Fast Address Look-Up for Internet Routers. Proc. of IEEE Broadband Communications, 1998
[41] Nen-Fu Huang ,Shi-Ming Zhao.A fast IP routing lookup scheme for gigabit switching routers. IEEE INFOCOM, 1999:1429-1436
[42] Nen-Fu Huang ,Shi-Ming Zhao. A novel IP routing lookup scheme and hardware architecture for multigigabit switching routers. IEEE JSAC, 1999: 1093-1104
[43] Anthony J.McAuley, Paul Francis. Fast Routing Table Lookup Using CAMs. INFOCOM '93, IEEE, 1993:1382-1391
[44] T.B.Pei. Putting Routing Tables in Silicon. IEEE, 1992: 42-50
[45] P.Gupta. Routing Lookups in Hardware at Memory Access Speeds. Proc. IEEE Infocom'98, 1998