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

摘要：面向路由器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

Internet网络流量、网络规模和上层应用的快速发展，对Internet互联的核心设备――路由器提出了越来越高的要求.目前核心路由器FIB（Forwarding Information Base）表前缀数目已经达到45万条，并呈现出指数级增长[1]， 导致了DFZ（Default Free Zone）路由器FIB极限问题，下一代互联网 IPv6协议的应用无疑对路由器转发性能提出了更大的挑战.为实现高速接口对报文的线速转发，路由器采用了越来越复杂的并行处理技术.例如Cisco公司的CRS-1路由器在40 Gbps接口的SPP网络处理器内部集成了多达188个32位的CPU[2].硬件的复杂性不但提升了成本，更抑制了性能的进一步提高.文献[3]提出了一种新型的报文并行处理机制FIS （Forwarding in Switching），其基本思想是将报文转发操作融入到交换网络中分布执行，采用边转发边交换的方式，实现FIB表的分布式存储及报文转发操作的流水执行.而现有路由器采用的是FBS （Forwarding before Switching）机制，即报文在进入交换网络交换之前必须完成精确转发以确定其输出端口.在FBS处理机制中，转发阶段与交换阶段在逻辑上是分离的，报文转发操作由线卡中的网络处理器或专用ASIC芯片集中处理，然后由多级交换网络将报文发送到目的端口，转发引擎芯片按照特定的FIB容量及FIB处理能力进行设计，导致路由器FIB处理极限问题.FIS处理机制将IP查找功能分解并映射到多个硬件同构的具有独立转发交换功能的FSN（Forwarding and Switching Node）结点分布执行，通过分解FIB表，构建FIB表到FSN结点的映射，每个FSN结点仅保存转发控制信息一部分执行部分转发操作，降低了IP查找复杂度；FIB信息在FSN结点的分布式存储，解决了并行查找机制访存瓶颈问题.FSN结点通过多级互连网络构成FSN处理阵列，以流水的方式执行报文转发和交换，FIS同时开发转发和交换操作的并行度，降低对单个转发交换部件的要求，提高路由器的整体转发和交换能力.

1 基于前缀范围的二分查找算法

面向FIS处理特性，本文提出一种基于前缀范围的二分查找算法PSB-BS（Prefix Scope Based Binary Search）：将IPv6转发表组织为分层结构，每一层仅保存含前缀信息的子树，忽略子树的路径信息即孩子子树的分布信息，有效降低了存储开销；采用二分查找策略对子树层进行搜索，降低了访存开销.转发表在各级FSN节点的分布式存储，增强了路由器的FIB扩容能力；每一级FSN节点具有相同的转发表映像，提高了系统可靠性，易于实现负载均衡，避免流量集中现象.

1.1 FIS原型系统硬件平台结构

由于三级交换结构，例如负载均衡（load-balanced switch）交换结构[4-5]及并行报文交换结构PPS[6] （Parallel Packet Switch）等，在负载均衡、避免报文乱序、调度简单且易于提供延迟和吞吐率保证等方面的优势，我们采用Mesh结构的总线实现三级FSN结点间的全互连，构成3×3的交换转发阵列.如图1所示，FIS原型验证系统包含9片Xilinx公司的XC4VLX25 FPGA，每片外接1片2 MB SRAM，用于保存IPv6转发表，系统工作频率100 M，采用外部时钟电路进行强同步.每个FPGA芯片通过以太网接口连接外部的控制网络（图1中未显示），控制平面通过以太网接口对每个FSN的SRAM芯片进行配置.

为实现对子树层序列的二分查找，需要在高层子树中加入指向包含更长前缀的低层子树的标记.查找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的查找需求.

PSB-BS算法优化策略与前缀分布特性密切相关：1）为降低标记开销，应尽量将低层子树放置在查找路径的前端，并采用“避重就轻”的方式消除对子树密集层的标记开销；2）为降低访存开销，应尽量将前缀覆盖率高的层放在查找路径的前端.

目前IPv6转发表实验数据较少，不足以评估查找算法的性能，仅具备参考价值，另一方面学术界对IPv6前缀分布特性尚未达成一致.我们采用随机生成的IPv6转发表评估了PSB-BS算法应用于FIS处理机制时，每一级FSN节点的存储开销、平均访存开销，并独立评估了PSB-BS算法和树位图算法的存储开销.PSB-BS查找算法采用CAM节点[7]的存储方式来保存子树的前缀信息：每个前缀表项包含匹配位（match bits）、匹配长度（match length）、下一跳（next hop）3个信息域.子树最大高度h=5，那么每个前缀项包含h bits的匹配位，「log2（h+1）=3 bits的匹配长度和10 bits的下一跳信息（支持1 024个端口），每个子树块存储2个前缀，溢出前缀指针为8 bits，因此每个子树条目长度为48 bits.溢出前缀块和子树块具有相同尺寸，每个溢出前缀块至多保存2个前缀，每个FSN节点可支持29个溢出前缀.参与比较的树位图算法[8]，步长为4；采用位向量分离、CAM存储和路径压缩3种存储优化方法；节点长度为38 bits；只有CAM节点保存了前缀的下一跳信息，其他前缀的下一跳信息保存在结果节点（result node，一个结果节点可保存3个前缀的下一跳信息）.

图4统计了FIS中采用非对称二分查找结构的PSB-BS算法随着前缀数量的增加，每一级FSN节点及溢出前缀的存储开销.第一级FSN节点存储开销明显大于二、三级FSN节点，这是因为映射到第一级FSN节点的S47，5需要为低层子树S53，5及第二级的S59，5加入查找标记，S35，5则需要为第二级的S41，5加入查找标记.有时甚至需要为这些标记生成新的子树，这将耗费大量存储开销.第二级和第三级FSN节点存储开销相当，溢出前缀所耗费的存储开销很小，仅占总存储开销的0.02%（4 k）～0.9%（100 k）.

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：//.

[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：///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.

[6] IYER S， MCKEOWN N. Analysis of the parallel packet switch architecture [J]. IEEE/ACM Transactions on Networking， 2003， 11（2）： 314324.

[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.