论文部分内容阅读
高速增长的网络链路速率(OC768,40Gbps)给IP查找的吞吐量带来了巨大的挑战。另外,路由表规模急剧增加,而虚拟路由器导致路由表规模进一步扩大,这给IP查找的存储资源带来了严峻的挑战。
针对IP查找存在的问题,本文深入研究了IP查找方法,提出一种支持虚拟路由器可扩展的内存均衡的IP查找流水线架构DLP(Dual Linear Pipeline)。DLP具有内存均衡,高吞吐量,支持虚拟路由器等特点。论文的研究工作已取得了以下成果:
1.提出了基于节点高度的流水级分割方法。本文针对片内SRAM容量有限的问题,使用按节点高度划分trie树的方法,把大量的节点分割到片外SRAM,很好地解决了片内SRAM容量有限的问题;实验结果表明,采用3级以上的片外SRAM,按节点高度划分的方法就可以把大量的节点(80%以上)映射到片外SRAM。
2.提出了支持增量更新的均衡映射算法。通过把大量的节点存储在片外SRAM,根据流水级数和树高选取合适的初始步长,对trie树进行前缀扩展分成多棵子树,然后把子树转化成分组队列,在对分组队列排序之后,把trie树均衡地映射到对应的SRAM流水级。这个方法可以使得各级流水线存储均衡,很好地支持增量更新,同时可以在一个时钟周期完成一次IP查找。
3.设计并实现了支持虚拟路由器的并行流水线架构DLP。针对虚拟路由器多个路由表和路由引擎的新问题,该架构利用前面提出的两种方法,实现了只需要一个查找引擎就可以实现多个路由器实例的IP查找。DLP的流水线内存分布均衡,内存利用率可以达到98%以上,在FPGA上布局布线之后的IP查找速度可达到85Gbps。在PEARL原型系统上实现DLP,其中原型系统是4个GE端口的设备,测试转发性能可以达到系统的最大吞吐量4Gbps。DLP也具有很好的扩展性,吞吐量随着路由器实例的增加保持不变。