论文部分内容阅读
目前,随着应用的快速发展和图像、音频、视频等多媒体信息传输的大量增加,Internet流量呈指数方式增长,对骨干路由器提出了越来越高的性能需求。在Internet发展初期,路由器大多基于CPU+内存结构,其路由查找过程大多由软件采用二进制树的方法实现。在高性能路由器中,多种基于硬件方法实现的IP路由查找技术被广泛使用,如直接存储器访问、基于三态CAM和Cache的查找技术等。随着第三代网络处理核心——网络处理器的出现,IP路由查找过程大多被集成在网络协处理器中。
路由器的转发速率通常受限于选择路由的速度,因此,路由查找和更新的方法是路由器进行包转发的基础和提高其性能的关键性技术,在路由器设计中至关重要。本文在详细分析多种现有IP路由查找技术的基础上,提出了一种可硬件实现的快速IP路由查找方法,将IP前缀匹配等价为地址范围搜索,采用B-树结构存储路由表。这种方案对存储要求较低,仅由小容量的片上SRAM和片外DRAM构成即可。实验结果表明,对于一个具有32K个路由表项的IPv4路由表,在160位存储带宽下,只需要2Mb的片上SRAM,平均访存7次,路由更新的速度为微秒量级;对于一个具有20K个路由表项的IPv6路由表,在552位存储带宽下,只需要3Mb的片上SRAM,平均访存6次。本文描述的快速IP路由查找技术在简单硬件支持下就能够达到OC-48的转发要求,并能支持IPv4和IPv6下的路由查找。如果采用硬件流水线来组织B-树的查找过程,那么可以达到一次存储器访问时间的查找速率。
此外,由于在设计中采用了B-树结构存储路由表数据,并利用“空间换取时问”的思想在片外DRAM中存储了路由表更新所需要的信息,本文的设计方案在具有快速路由查找能力的同时能达到较高的路由表更新速度。