论文部分内容阅读
本文研究NGI(Next Generation Internet)高性能路由器的转发处理关键技术——路由查找技术和流转发／交换技术。通过对已有路由查找算法的分析得出两点结论。结论一是已有路由查找算法不能适应NGI高性能路由器的线速率转发；二是适应NGI高性能路由器线速率转发的路由查找算法应基于分部搜索和TCAM技术。两点结论成为本文主要研究工作的基础。 综合基于前缀长度二分搜索的路由查找算法和基于Trie的路由查找算法的优点，提出了“基于Trie二分搜索的路由查找算法(BSTrie，Binary-search on Trie)”。不同于Radix Trie算法的逐一比特进行比较和对前缀长度进行二分搜索的路由查找，BSTrie采用二分法将IP目的地址与Trie进行匹配，并用部分IP目的地址做索引避免了使用Hash函数。对BSTrie IPv4实现方案和BSTrie IPv6实现方案进行了讨论。其路由查找速度和转发表表项更新速度可适应OC-48(2.5Gbps)端口的线速率转发。 提出了“基于前缀范围二分搜索的路由查找算法(BSPR，Binary-search on Prefix Range)”并给出了两组实现方案。第一组方案采用了比较器并在各步TCAM存储完整的转发表。包括BSPR IPv4路由查找流水线，BSPR IPv6路由查找流水线，和BSPR IPv4／IPv6双协议栈路由查找流水线。通过转发表的减半存储(Half-Stored)，第二组方案避免了比较器的使用并减少了TCAM的容量需求。由此产生了HS-BSPR IPv4路由查找流水线，HS-BSPR IPv6路由查找流水线，和HS-BSPR IPv4／IPv6双协议栈路由查找流水线。 提出了“基于前缀范围四分搜索的路由查找算法(QSPR，Quaternary-search on Prefix Range)”，实现了两组硬件路由查找流水线。将QSPR与前缀扩展技术相结合，实现了QSPE(Quaternary-search on Prefix-expansion)IPv4路由查找流水线，QSPE IPv6路由查找流水线，和BSPE IPv4／IPv6双协议栈路由查找流水线。混合采用QSPR和BSPR技术，构建了QBSPR(Quaternary-Binary-search on Prefix Range)IPv4路由查找流水线，QBSPR IPv6路由查找流水线，和QBSPR IPv4／IPv6双协议栈路由查找流水线。 与已有的对前缀长度进行二分搜索和采用单步TCAM的路由查找算法不同，本文提出的BSPR路由查找算法和QSPR路由查找算法对前缀范围分别进行二分搜索和四分搜索，并采用多步TCAM组建路由查找流水线。突出特点是转发表无需排序、表项更新快、查找速率高且连续性好。每2个时钟周期即可完成一次IPv6路由查找或一次转发表表项更新，每项表项更新只对流水线路由查找流程中断一次。满足IPv4、IPv6及IPv4／IPv6双协议栈核心路由器OC-768(40Gbps)端口的线速率转发。 提出了“虚分组”概念和“虚分组交换(VPS，Virtual-packet Switching)”机制。通摘要博士论文过对传统IP分组的改进，VPS在支持零散分组的逐一分组转发的基础上，特别适应对TCP流和UDP流(如实时视频数据流和实时音频数据流)的高速交换。