IP路由查找

主要内容 路由查找问题的产生背景 典型的IPv4路由查找算法 基于IXP2800的高速IPv6路由查找算法及实现

参考文献 Survey and Taxonomy of IP Address Lookup Algorithms. IEEE Network, 2001. High-performance IPv6 Forwarding Algorithm for Multi-core and Multithreaded Network Processors. In Proceedings of PPoPP’06, 2006.

地址前缀与地址聚合 IP编址方案最初使用一个简单的二层结构：上层为网络，下层为主机。 这个分层结构反映在IP地址上，就是IP地址由两个部分组成：网络地址部分（地址前缀）和主机地址部分。 地址前缀的两种表示方法： 不大于32比特的比特串跟上一个*，比如：1000001001010110* 带点十进制表示加上地址前缀长度，比如：130.86/16 地址聚合（address aggregation）：连接到同一个网络的所有主机，在转发表中对应一个入口，即允许使用前缀来表示一组地址。

转发表举例

基于类的编址方案

基于类的编址方案的缺点 地址空间利用率低，地址短缺问题日益突显。 核心路由器的转发表规模急剧扩大，导致查表时间及内存需求增加。

无类域间路由（CIDR）编址方案 摒弃传统的基于类的地址分配方式，允许使用任意长度的地址前缀，有效提高地址空间的利用率。 允许任意地、递归地进行地址聚合，减少转发表中的入口数目，有效解决路由表爆炸的问题。

地址聚合的例子（1）

地址聚合的例子（2） 路由器的地址查找问题就是要从转发表中查找匹配数据包目的地址的最长的地址前缀。

基于类的地址查找 转发表中的前缀被组织成三张表（分别对应A、B、C三类地址前缀），地址查找就是在对应的转发表中进行精确匹配查找。 查找过程如下： 根据IP地址的前几位得到该地址所属的地址类别 根据地址类别提取目的地址中的网络地址部分 查找相应的哈希表或进行二分查找

最长地址前缀匹配的困难 转发表中的目的前缀具有任意的长度，并且不再对应地址的网络部分，因而前缀长度无法从目的地址本身获得。 转发表查找要求采用最长前缀匹配查找而不是精确匹配查找。 地址查找在数值和长度两个维度上进行。

地址查找算法的评价标准 查找速度 存储容量 预处理和更新速度 算法实现的灵活性（同时具有硬件和软件实现方式） 算法的可扩展性（路由表规模，IPv6）

经典的IP地址查找算法 线性表查找 二进制Trie树（Binary Trie） 路径压缩Trie树（path-compressed Trie）

二进制Trie树 采用基于树的数据结构，通过前缀中每一位的值来决定树的分支。 处于第L层的节点代表了一个地址前L比特均相同的地址空间，这L个比特串就是由从根节点到这个节点路径上的L比特组成。 与地址前缀对应的节点包含了转发信息。

Trie树代表的地址空间结构

Trie树的查找 从根节点开始每次一位地查找： 以上查找方法为基于长度的顺序前缀查找，每搜索一步，搜索空间就缩减一半，当缩减为1时搜索结束。 当地址中的相应位为0时选择左分支，为1时选择右分支。 当遇到那些对应地址前缀的中间节点时，将此地址前缀记录为目前为止找到的最长地址前缀。 当不再有分支可以选择时搜索过程结束，此时被记录的最长地址前缀就是查找结果。 以上查找方法为基于长度的顺序前缀查找，每搜索一步，搜索空间就缩减一半，当缩减为1时搜索结束。

Trie树的更新 插入一个地址前缀 删除一个地址前缀 以该前缀项为关键字在Trie树中进行查找； 若查找过程在一个中间节点终止，将此节点标记为前缀节点，并在此中间节点中加入前缀转发信息； 若不再有分支可选取，需要插入必要的分支节点。 删除一个地址前缀 若查找过程在一个中间节点终止，将此节点标记为非前缀节点，删除此节点的转发信息； 若查找过程终止于叶子节点，除了删除该节点之外，还需要根据情况删除其它一些内部节点 。

路径压缩Trie树 路径压缩Trie树压缩单向分支 每个节点需要维护一个变量，指示下一个需要检查的比特位 前缀节点需要保存地址前缀的比特串

路径压缩Trie树（续） 当二进制Trie树中的前缀分布较稀疏时，路径压缩算法能够获得良好的压缩效果。 研究表明，对于一个具有47113个前缀表项的典型骨干网路由器，使用BSD Trie会创建93304个节点，树的最大高度为26，平均高度为20。而对于同样的前缀表，二进制Trie树的最大高度为30，平均高度为22。

查找算法使用的辅助策略（1） 前缀扩展（prefix expansion） 将一条长度较短的地址前缀展开成多条长度较长的地址前缀集合，这个前缀集的转发信息就是原来地址前缀所对应的转发信息。 例如：前缀1*的地址范围可以用前缀10*和11*来涵盖，也可以用前缀100*、101*、110*和111*来涵盖。 前缀扩展的目的是为了获得一组长度差异较小的前缀集合，以利于快速查找。

查找算法使用的辅助策略（2） 独立前缀转化 将地址前缀集转化为一组不相交的前缀集 所有的前缀节点都出现在叶子节点

查找算法使用的辅助策略（3） 压缩技术 优化技术的应用 存储层次设计 压缩前缀扩展造成的信息冗余 从压缩数据中恢复原有信息不应过于复杂 在满足一定约束条件的前提下找到最佳的前缀集，比如在满足查找速度的前提下减少算法的存储空间。 存储层次设计 尽量减小查找算法的数据结构所占据的存储空间，从而可以将数据结构放入较高的存储层次中。 应最小化访存次数

多分支Trie树的基本算法 查找的每一步检查地址中的多个比特。 查找步宽为k的多分支Trie树，每个节点的最大分支数为2k 。 同一层中不同子树的步宽可以相同（固定步宽多分支Trie），也可以不同（可变步宽多分支Trie）。图 固定步宽的多分支Trie实现简单，但会浪费较多的存储空间，可变步宽的多分支Trie则相反。 前缀表中的地址前缀必须转换成多分支Trie查找能够允许的地址前缀。图 多分支Trie树的深度有很大缩减，因而提高了查找效率。 多分支Trie的查找过程类似于二进制Trie。 多分支Trie的更新过程比二进制Trie复杂： 插入一个前缀时，需要找到相应的subtrie，对前缀进行扩展，然后插入。 删除一个前缀时，需要删除所有扩展的前缀。 需要额外的数据结构保存原始前缀。

可变步宽与固定步宽的多分支Trie树

多分支Trie例1

多分支Trie例2 在地址扩展过程中，如果扩展的地址前缀与原来的地址前缀冲突，应保留原来的地址前缀。

多分支Trie的优化（1） 步宽的选择 步宽的选择是在算法查找速度、存储空间和更新复杂度之间的折衷。 一种较自然的做法是根据实际地址前缀的分布来选择合适的步宽。 使用某种优化策略，使在搜索深度固定的情况下整个树的存储空间最小。

多分支Trie的优化（2） 24-8多分支trie快速查找算法的硬件实现 TBL24 TBLlong 24-8多分支trie快速查找算法的硬件实现 查找最多只需要两次访存；采用硬件流水线技术，实际上只需要一次访存的时间。 算法要求的内存空间比较大。

多分支Trie的优化（3） 压缩 在前缀扩展的过程中，前缀的转发信息被扩展到了trie树的多个连续节点中，造成大量的信息冗余。 压缩因前缀扩展造成的大量冗余信息，减少算法占用的内存空间。

基于前缀长度的二分查找

前缀范围查找 任何地址区域所对应的最长前缀应该是包含此区域的前缀中范围最窄的那一项。

地址区间的二分查找树 最长前缀匹配查找变成在左端点集合中寻找离目的地址最近的左端点。 路由表规模很大时，查找效果不好。 更新性能较差。

基于TCAM的硬件查找 TCAM中每一个表项以<地址，掩码>序偶的形式保存。 查找速度快，实现简单。完成一次查找只需三步操作，采用流水线技术可以进一步提高查找速度。 容量小，代价高，功耗大，更新复杂（关键字需要排序）。

IPv6地址查找的困难 前缀更长： 规模更大： IPv4路由查找算法不能直接应用于IPv6： IPv6地址长度为128比特，路由器只转发Aggregatable Global Unicast Address，这类地址的前3个比特总为001，且最后64比特用于标识网络接口。 规模更大： 目前IPv6尚未广泛使用，IPv6路由表都很小（基本不超过1000个前缀项），但估计的前缀项应在50万条左右。 IPv4路由查找算法不能直接应用于IPv6： 基于trie的算法内存需求很大，访存次数很多。 Stanford算法直接应用于IPv6查找会造成高达几百兆的内存需求。 基于TCAM的方法不适用于规模巨大的表。 基于地址前缀长度的二分查找的更新复杂度很大，无法接受。

TrieC算法设计思想 采用改进的Stanford算法 已有IPv6路由表的统计结果和地址分配策略表明，长度大于48比特的前缀比例很低，仅为5%左右，因此可对IPv6地址的高48位采用多分支trie进行查找，剩余的16比特直接采用hash查找。 根据IPv6地址前缀的分布特点，构造查找步宽为24-8-8-8-16的五层多分支TrieC树，限制最坏情况下路由查找的访存次数。

TrieC算法设计思想（续） 使用压缩前缀扩展技术消除冗余信息： 采用一个位向量记录每个数据块的起始位置，数据块中的下一跳信息只在表是存储一次。 64条前缀压缩成一个表项，用高18比特作为新表项的索引，低6比特用作另一个索引查找位向量。

TrieC树结构 构造查找步宽为24-8-8-8-16的五层多分支TrieC树： 第五层采用hash16数据结构，存储长度为[49, 64]比特的地址前缀。 每一层节点的数据结构中都有一个标志位用于指示是否需要继续查找下一层节点。

网络处理算法在IXP2800上高效实现的关键 减少访存次数（TrieC限制了最大访存次数） 选择合适的指令 合理分配数据 合理划分任务 使用各种延迟隐藏技术

指令选择 以下指令对TrieC的高速实现非常重要： POP_COUNT指令：可在3个时钟周期内计算32位寄存器中1的个数，在RISC结构上通常需要100多条指令。 分支跳转指令：可以在1条指令中完成分支跳转操作，而在RISC体系结构上通常至少需要3条指令。 硬件CRC：使用微引擎内部的CRC单元提供对TrieC树最后一层的哈希计算（5个时钟周期）。

数据分配 IXP2800具有4个可并行访问的SRAM控制器和3个DRAM控制器，每个DRAM控制器支持4个可交错访问的存储器bank。 采用以下四种数据分配模式进行实验，只有前三种能够在最坏情况下支持OC-192线速： 所有TrieC表存储在一个SRAM控制器中 TrieC表按照TrieC树的层次存储在四个SRAM控制器中 TrieC表按照TrieC树的层次混合存储在SRAM和DRAM控制器中 所有的TrieC表存储在DRAM控制器中，此时TrieC数据结构被重新设计以适应DRAM存储器的访问特性。

任务切分 IXP2800支持两种任务切分模式： Multi-processing：包括微引擎内的多线程技术和基于多个微引擎的多线程技术，易于实现，易于平衡负载，但每个任务所用的资源不宜过多。 Context-pipelining：将一个任务切分成若干个子任务分配到多个微引擎上执行，子任务之间通过邻居环或Scratch ring连接形成流水线。每个任务可用的资源较多，但子任务间通信负载较高，且子任务间不易平衡负载。 实验了multi-processing、 Context-pipelining和混合三种模式，发现multi-processing模式更适合TrieC算法的实现。

长延迟隐藏 TrieC算法是实现需要频繁进行I/O操作，I/O操作是典型的长延迟操作，隐藏访存延迟的手段包括： 多线程技术是隐藏长延迟的主要手段。 I/O向量化：访问存储器中连续存储的内容可以通过一条I/O指令来完成。IXP2800使用一条I/O指令最多可以访问64个字节（SRAM），所以TrieC结构的大小都限制在64个字节内。 I/O交错（延迟槽填充）：在IXP2800上，分支指令和线程切换指令都会导致1个或者多个延迟槽。将无依赖关系的指令安排在分支指令或线程切换指令附近，以便让IXP编译器用它们填充到这些指令产生的延迟槽中。

TrieC算法对表空间的压缩性能 Group A：参考CERNET、6Bone、6Net和Telstra的IPv6路由表前缀长度分布而生成，代表了目前为止实际的IPv6路由表。 Group B：采用M.Wang等人提出的非随机IPv6路由表生成算法产生，代表理想状态的IPv6路由表。 Group C：由Group A和Group B的算法平均生成。

TrieC算法的平均访存次数 TrieC算法的平均访存次数与路由表前缀长度分布有关，而与规模无关。 Group B中超过70%的前缀的长度位于41-48比特之间，匹配这部分前缀的IPv6地址必须搜索到TrieC的第四级。

并行查找时的相对加速比 使用69字节的最小IPv6分组进行实验。 OC-192线速意味着转发速度至少要达到18.12Mpps。

支持OC-192线速需要的最少线程数

数据分配实验 单SRAM通道：3个微引擎就可以支持OC-192线速，但SRAM通道利用率较高。 DRAM：TrieC无法在最坏情况下支持OC-192线速。 混合SRAM/DRAM：第一级节点存储在SRAM中，其它节点存储在DRAM中，最坏情况下4个微引擎可以达到OC-192线速，但DRAM 通道利用率非常高，实际情况下无法使用。

任务切分 Context-pipelining的任务切分： ME1和ME2负责第一、第二层表的查找 ME3和ME4负责第三、四、五层表的查找

延迟槽填充带来的性能改善

线程同步（维持包序）带来的性能损失

总结 尽量压缩算法所需的内存空间 合理分配任务和分布数据 根据算法特性选择合适的位操作指令 充分利用各种延迟隐藏技术 在难以平衡各个子任务的工作负载时使用multi-processing编程模式