一种路由表分布式存储转发架构及其查找算法

面向路由器FIS(Forwarding In Switch, FIS)处理机制，提出了一种基于路由表分布式存储的多级流水并行查找架构，采用多个低速的具有独立转发和交换功能的转发交换结点FSN(Forwarding and Switching Node)构成多级流水线，针对IPv6最长匹配前缀的查找需求，设计了一种基于前缀范围的二分查找算法PSB-BS(Prefix Scope Based Binary Search)：将IPv6转发表组织为分层结构，每一层对应不同长度范围的前缀信息，采用二分查找策略对子树层进行搜索，通过构建非对称二分查找树实现了转发表在FSN结点的分布式存储并能有效降低存储开销及IP查找复杂度.仿真结果表明，与目前Cisco商业路由器广泛采用的树位图算法相比，PSB-BS算法显著降低了存储及访存开销.

IP Lookup Architecture and Algorithm Based on Distributed Storage and Forwarding of Routing Table

This paper proposed a parallel multi-level pipeline IP lookup architecture based on distributed storage of routing table that consists of multi-stage lower speed nodes called FSN performing IP-lookups and switching independently. An IPv6 binary lookup algorithm was proposed based on prefix scope called PSB-BS (prefix scope based binary search) for putting IPv6 longest prefix match in practice. The IPv6 route table was partitioned into multiple levels, each representing a specified range of prefixes. By doing binary search over these subtrie levels and especially by constructing asymmetric binary tree, our solution implemented distributed storage of forwarding table, thus reducing the storage overhead as well as the complexity of IP lookup. The experiment results demonstrate the PSB-BS algorithm reduces the storage and memory access overhead considerably, compared with the tree bitmap algorithm widely used in Cisco commercial routers.