摘要：面向路由器FIS（Forwarding In Switch， FIS）处理机制，提出了一种基于路由表分布式存储的多级流水并行查找架构，采用多个低速的具有独立转发和交换功能的转发交换结点FSN（Forwarding and Switching Node）构成多级流水线，针对IPv6最长匹配前缀的查找需求，设计了一种基于前缀范围的二分查找算法PSB-BS（Prefix Scope Based Binary Search）：将IPv6转发表组织为分层结构，每一层对应不同长度范围的前缀信息，采用二分查找策略对子树层进行搜索，通过构建非对称二分查找树实现了转发表在FSN结点的分布式存储并能有效降低存储开销及IP查找复杂度.仿真结果表明，与目前Cisco商业路由器广泛采用的树位图算法相比，PSB-BS算法显著降低了存储及访存开销.
关键词：路由器；网络路由；查找引擎
中图分类号：TP393 文献标识码：A
IP Lookup Architecture and Algorithm Based on Distributed
Storage and Forwarding of Routing Table
DAI Yi，WANG Ke-fei， ZHANG He-ying， WANG Shao-gang
（College of Computer， National Univ of Defense Technology， Changsha， Hunan 410073， China）
Abstract： 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.
Key words： routers； network routing； search engines
面向FIS处理特性，本文提出一种基于前缀范围的二分查找算法PSB-BS（Prefix Scope Based Binary Search）：将IPv6转发表组织为分层结构，每一层仅保存含前缀信息的子树，忽略子树的路径信息即孩子子树的分布信息，有效降低了存储开销；采用二分查找策略对子树层进行搜索，降低了访存开销.转发表在各级FSN节点的分布式存储，增强了路由器的FIB扩容能力；每一级FSN节点具有相同的转发表映像，提高了系统可靠性，易于实现负载均衡，避免流量集中现象.
1.1 FIS原型系统硬件平台结构
为实现对子树层序列的二分查找，需要在高层子树中加入指向包含更长前缀的低层子树的标记.查找hash表时，若匹配标记，则搜索低半层子树hash表；若匹配前缀则记录当前LMP，将报文转至下一级FSN节点处理；若未命中任何表项，则搜索高半层子树hash表.对子树层Sl，h的任何子树T，在访问层Sl，h的二分查找路径上比Sl，h高的子树层都需要加入标记，即根节点级数小于l的子树层中都需要加入查找Sl，h中每一棵子树的标记.实际上，尽管同一棵子树的最大标记开销为log2w，但标记引发的最坏情况下的回溯次数为O，因此必须消除标记造成的回溯.预计算每个标记M的最长匹配前缀，将标记LMP对应的下一跳信息保存在标记下一跳信息域中.匹配标记时，同时记录标记LMP的下一跳信息，在低半层子树查找失败时，不需要再回溯到高半层子树，标记LMP就是最终的查找结果.尽量将低层子树放在查找路径的前端有利于降低标记开销，在极端情况下，按照从低层子树到高层子树的顺序查找时，标记开销为零，但最坏情况下的查找次数为w.理想的具有低标记开销且存储空间分布均衡的二分查找结构难以获得，一方面，降低标记开销需要将低层子树放置在查找路径的前端；另一方面，存储空间的均衡分布需要在查找路径的每一级上放置数量相同的hash表.为了构造最优二分查找树，我们以递归方式划分二分查找树中当前节点搜索空间的高低部分，采用启发式加权函数选择高/低部分的子树层，而不是简单地选择高半层或低半层子树，称之为非对称二分法.运用两种不同的加权函数构造非对称二分查找树，一种加权函数优先选择低层子树以降低标记开销；另一种加权函数保证查找路径的每一级具有相同数目的hash表；最终得到非对称二分查找结构如图3所示.
2 性能评测
与经典的二分查找算法相比，PSB-BS算法基于范围的查找策略能够有效地压缩查找路径、减少访存开销，并通过调节步长而更具灵活性和可扩展性，适用于IPv6的查找需求.
3 结 论
本文基于FIS报文处理特性，针对IPv6更长位宽的转发需求，提出了基于前缀范围的二分查找算法PSB-BS（Prefix Scope Based Binary Search）：基于前缀范围的子树表示法消除了对路径信息的保存，降低了存储开销，实验结果表明，该策略可将存储开销降低为树位图算法的50%；二分查找策略能够有效压缩查找路径，减少访存开销，适用于IPv6更长位宽的查找并有利于转发表在FSN结点的均衡分布.通过构造PSB-BS算法非对称二分查找树，实现了IPv6转发表到FSN结点的分布式存储与转发.仿真结果表明，随着前缀数目的增加，每一级FSN结点的平均查找次数几乎没有变化，反映了PSB-BS算法良好的可扩展性. 参考文献
[1] BGP routing table analysis report [EB/OL]. http：//bgp.potaroo.net.
[2] Cisco Corporation. Next generation networks and the Cisco carrier routing system： white paper of Cisco Systems[R/OL]. San Jose， CA， USA： Cisco Corporation， 2007. http：//www.Cisco.com/warp/public/cc/pd/rt/ 12000/clc/prodlit/reqng_wp.pdf.
[3] DAI Yi， SUN Zhi-gang， SU Jin-shu. Analysis of an evolvable architecture of internet routers [C]//Proceedings of IEEE Workshop on High Performance Switching & Routing （HPSR）. New York： IEEE， 2007： 1-5.
[4] KESLASSY I. The load-balanced router [D]. Stanford， CA： Stanford University， 2004.
[5] LIN B， KESLASSY I. The concurrent matching switch architecture [J]. IEEE/ACM Transactions on Networking， 2010，18（4）： 1330-1343.
[7] EATHERTON W N. Hardware-based internet protocol prefix lookups [D]. Washington， DC： Electrical Engineering Department， Washington University， 1999.
[8] BABOESCU F， RAJGOPAL S， HUANG L B， et al. Hardware implementation of a tree based IP lookup algorithm for OC-768 and beyond [C]//Proceedings of Design Con’05. 2005： 1680-1687.
