基本信息
- 项目名称：
- 基于NoC的分布式路由器
- 来源：
- 第十二届“挑战杯”作品
- 小类：
- 信息技术
- 大类：
- 科技发明制作A类
- 简介：
- 本项目采用2D Mesh片上网络NoC（Network on Chip）体系结构，提出了一种分布式查找的路由器的结构，制定了NoC节点之间的通信协议，构造了通用可配置路由器的验证环境，在NetFPGA平台上设计并实现了一个路由器软硬件系统。通过PCI接口，SCONE软件可完成路由器转发表和控制寄存器的配置并读取查找信息，Linux GUI界面实时的显示路由器当前的工作状态和分布式转发表的性能信息。
- 详细介绍：
- 设计目的： 在短线互连Mesh结构上提出分布式并行地址查找算法，提高核心路由器SoC系统的性能，并为解决深亚微米工艺下，集成电路设计中出现的“红砖墙（Red Brick Wall）”问题提供一种方案。 基本思路： 1．利用片上网络NoC思想，在Mesh网络上，实现分布式IP地址并行查找； 2．单节点的查找采用Tree Bitmap算法，硬件实现采用流水线设计方法； 3．构建通用可配置IP路由器验证平台，并利用该平台对路由器设计进行验证； 4．用FPGA实现路由器原型系统，开发路由器软件系统，组网测试。 创新点： 1．采用规则的Mesh结构连接IP地址查找节点，实现各个节点之间的并行计算。该结构具有良好的扩展性，系统处理能力随着节点的增多而提高。同时节点之间采用短线连接，可以避免深亚微米工艺下集成电路设计的“红砖墙”问题，为未来工艺下查找和交换融合的路由器设计提供了一种解决思路； 2．采用分布式存储原理，将路由表按照一定策略划分并存储在各个查找节点上，路由表存储开销不随Mesh结构的节点的增多而增加； 3．开发了通用可配置IP路由器验证平台，通过配置该平台可以对查找引擎、交换结构及硬件数据平面进行仿真验证，也可进行FPGA测试； 4．采用流水线的方法设计并实现了基于Tree Bitmap的IP地址查找引擎，该引擎平均每2个时钟周期完成1个IP地址查找。 技术关键： 1．用片上网络NoC的思想实现分布式IP地址并行查找需要制定片上网络通信协议，该协议的优劣直接影响到片上通信的性能； 2．为了增加IP地址查找的吞吐量，采用硬件流水线的设计方法实现Tree Bitmap查找算法； 3．为了实现分布式查找，将整个路由表划分为N份，存储在N个查找节点上，该表项的划分策略直接影响到片上通信与各查找节点的负载均衡； 4．在分布式系统中，各节点处理时间不同，任务在片上网络传输时间也不同。这便会造成任务顺序输入，乱序输出。因此任务的保序处理是分布式并行系统的关键问题； 5．片上网络NoC和路由器的功能验证与性能统计是保证系统正确，稳定工作的关键。 主要技术指标： 基于2×2 Mesh结构实现分布式IP转发引擎，在Xilinx V2芯片上处理速度可以达到62.5Mpps(系统时钟125MHz)。该转发结构具有非常好的扩展性，在更高端的FPGA上或者ASIC设计中，其性能随着系统时钟频率的提高和Mesh的节点增多而提高。 科学性与先进性： 1．基于Mesh结构的NoC实现分布式IP地址查找，实现各个节点之间的并行计算，各节点之间采用短线连接。 (1)清华大学提出的分布式并行路由查找框架（Distributed Parallel Router Lookup Framework，DPRLF）[1]是分布式并行计算在地址查找中的典型应用。本设计的结构与DPRLF相比的优势在于采用NoC的思想，具有大规模集成、扩展性强、可复用性强等优点。 (2)Venkatesh等提出的基于分布式存储的高性能并行IP地址查找技术[2]，该技术采用与DPRLF类似的体系结构。该系统实现分布式路由表存储，各子查找单元完成独立无关IP查找。该结构具有16个子查找单元，采用集中式任务分配。与该结构相比本作品具有NoC中短线互联的优势，片上通信效率高、扩展性强、可复用性强和分布式任务分配等优点。 (3)Baboescu等在基于Trie树的IP地址查找引擎体系结构[3]中，提出了利用单端口存储器构建一种环形的IP地址查找流水线——Ring Pipeline，提高了路由信息表到流水线结点映射的灵活性。与该结构相比本设计的优势在于，基于NoC的结构，任务可以按照片上路由算法到相应的节点进行查找计算而不必按流水线经过每一级，这样的优势在于缩短任务传输延迟。与该结构相比本作品所采用的结构同样具有大规模集成，扩展性强等优点。 2．对树位图(Tree bitmap)[4]传统的设计方法进行了改进，采用流水线的方法设计并实现了基于Tree Bitmap的IP地址查找引擎，在延时不变的基础上使吞吐量增加了3倍 参考文献： [1].郑凯, 高性能IP路由查找和分组分类技术的研究, 2006, 清华大学: 北京 [2].Venkatesh, K., et al. A high performance parallel IP lookup technique using distributed memory organization. 2004. Las Vegas, Nevada: IEEE Computer Society. [3].Baboescu, F., et al. A tree based router search engine architecture with single port memories. 2005: IEEE Computer Society. [4].Eatherton, W., G. Varghese and Z. Dittia, Tree bitmap: hardware/software IP lookups with incremental updates. ACM SIGCOMM Computer Communication Review, 2004. 34(2): p. 97-122. 本作品满足OC-192标准的核心路由器标准，可直接用于OC-192标准的核心网络。 本作品采用Xilinx-Virtex2实现。由于受FPGA资源限制，硬件的工作频率为125MHz时钟频率，处理速度为62.5Mpps（可处理32Gbps线速的数据），满足OC-192标准（10Gbps）。如果采用性能更高的FPGA或者采用最新工艺的ASIC设计，节点的规模与工作频率都可以得到大幅度的提高，可满足OC-768标准（40Gbps），同时也可扩展更多接口。对协议管理软件及外围电路进一步完善优化会更有市场价值与市场竞争力。
作品图片
作品专业信息
设计、发明的目的和基本思路、创新点、技术关键和主要技术指标
- 设计目的：在短线互连Mesh结构上提出分布式并行地址查找算法，提高核心路由器SoC系统的性能。 基本思路：1．利用片上网络NoC思想，在Mesh网络上，实现分布式IP地址并行查找；2．单节点采用Tree Bitmap算法，硬件实现采用流水线；3．构建通用可配置IP路由器验证平台对路由器设计进行验证；4．用FPGA实现路由器原型系统，组网测试。 创新点：1．采用Mesh结构连接IP查找节点，实现各个节点间的并行计算。该结构扩展性好，系统处理能力随着节点的增多而提高；2．采用分布式存储原理，将路由表按照负载均衡策略划分并存储在各个查找节点上，路由表存储开销不随Mesh结构的节点的增多而增加；3．开发通用可配置IP路由器VMM验证平台，通过配置该平台可以对查找引擎、交换结构及硬件数据平面进行验证与FPGA测试；4．采用流水线的方法实现了Tree Bitmap的IP查找引擎。 技术关键：1．制定片上网络NoC的片上网络通信协议，该协议的优劣直接影响到片上通信的性能；2．采用硬件流水线的设计并实现Tree Bitmap查找算法；3．将整个路由表划分并存储在N个查找节点上，且制定负载均衡策略；4．实现任务的保序处理，解决分布式系统中的乱序问题。 主要技术指标：2×2 Mesh结构的分布式IP转发引擎，在Xilinx V2芯片上处理速度可达到62.5Mpps(时钟125MHz)。该转发结构具有很好的扩展性，在高端FPGA上或者ASIC实现，其性能随着时钟频率的提高和节点的增多而提高。
科学性、先进性
- 1．基于Mesh结构的NoC实现分布式IP地址查找，实现各个节点之间的并行计算，各节点之间采用短线连接。(1)清华大学提出了分布式并行路由查找框架[1]。本作品的优势在于采用NoC的思想，具有大规模集成、扩展性强、可复用性强等优点。(2)文献[2]提出的基于分布式存储的高性能并行IP地址查找技术。与该结构相比本作品具有NoC中短线互联的优势，片上通信效率高、扩展性强、可复用性强和分布式任务分配等优点。(3)文献[3]在基于Trie树的IP地址查找引擎体系结构中，提出了利用单端口存储器构建一种环形的IP地址查找流水线。与该结构相比本设计的优势在于，任务可以按照片上路由算法到相应的节点进行查找计算而不必按流水线经过每一级，缩短任务传输延迟，且同样具有大规模集成，扩展性强等优点。 2．对树位图[4]传统的设计方法进行了改进，采用流水线的方法设计并实现了基于Tree Bitmap的IP地址查找引擎，在延时不变的基础上使吞吐量增加了3倍。 （参考文献见表C：国内外同类课题研究水平概述）
获奖情况及鉴定结果
- 无
作品所处阶段
- 实验室阶段
技术转让方式
- IP授权
作品可展示的形式
- 实物、现场演示、录像
使用说明,技术特点和优势,适应范围,推广前景的技术性说明,市场分析,经济效益预测
- 本作品满足OC-192标准的核心路由器标准，可直接用于OC-192标准的核心网络。 本作品采用Xilinx-Virtex2实现。由于受FPGA资源限制，硬件的工作频率为125MHz时钟频率，处理速度为62.5Mpps（可处理32Gbps线速的数据），满足OC-192标准（10Gbps）。如果采用性能更高的FPGA或者采用最新工艺的ASIC设计，节点的规模与工作频率都可以得到大幅度的提高，可满足OC-768标准（40Gbps），同时也可扩展更多接口。对协议管理软件及外围电路进一步完善优化会更有市场价值与市场竞争力。
同类课题研究水平概述
- 一.基本查找算法 1．线性查找算法：线性查找算法按照线性表的方式来组织路由前缀信息。2．基于树的查找算法：基于Trie树的算法是IP地址查找的经典算法之一。根据前缀的二进制比特值，将路由前缀映射到Trie树的结点上。3．二分查找算法：二分查找的算法是将最长前缀匹配分解成一系列的精确匹配。该算法具有良好的可扩展性，但有较大的存储的复杂度。4．基于范围的查找算法：基于范围的IP地址查找技术将前缀看作是整个IP地址空间内的一个“区间”，不同的前缀将整个地址空间分成多个子区间。5．基于Hash的查找算法：基于Hash的算法根据路由前缀某个特定的Hash函数值，构造Hash表对前缀进行组织和存储。但是Hash冲突的存在，使得该查找算法的最好和最坏情况下的性能差异较大。6．基于TCAM的查找算法：TCAM是一种基于内容寻址的存储器件，在IP地址查找中用来存储路由信息表项。TCAM由于其高速的查找性能和确定的查找延迟， 广泛地用于商用路由器中。然而，TCAM芯片价格昂贵，功耗大，难以大规模集成。 二.并行IP查找结构 （参见作品先进性与科学性） 参考文献： [1].郑凯, 高性能IP路由查找和分组分类技术的研究, 2006, 清华大学: 北京 [2].Venkatesh, K., et al. A high performance parallel IP lookup technique using distributed memory organization. 2004. Las Vegas, Nevada: IEEE Computer Society. [3].Baboescu, F., et al. A tree based router search engine architecture with single port memories. 2005: IEEE Computer Society. [4].Eatherton, W., G. Varghese and Z. Dittia, Tree bitmap: hardware/software IP lookups with incremental updates. ACM SIGCOMM Computer Communication Review, 2004. 34(2): p. 97-122.
