路由器原理与设计-2010-lesson4-高速IP查表算法.ppt

高速IP查表算法 国防科大计算机学院 孙志刚 2010年路由器原理与设计 主要内容 o Routing Lookups in Hardware at Memory Access Speeds o Tree Bitmap : Hardware/Software IP Lookups with Incremental Updates Routing Lookups in Hardware at Memory Access Speeds Pankaj Gupta, Steven Lin, and Nick McKeown Computer Systems Laboratory, Stanford University Infocom 1998 算法研究目标 o 算法必须硬件实现简单 o 查表只需要一次访存操作 o 如果需要多次访存操作 n 只有很少概率需要多次访存 n 访存次数有很小的上限，如2次、3次等 n 数据在不同的物理存储器中保存，有利于流水 实现 o 控制表格的更新开销小 算法研究基于的假设 o 存储器的价格便宜 o 路由前缀长度分布特征 核心路由器上路由前缀长度超 过24的十分少 例如：MAE-EAST骨干路由 器中99.93%的路由前缀小于 等于24 DIR-24-8-BASIC结构 o TBL24：保存前缀长度小于等于24的所有前缀 的信息 n 0.0.0-255.255.255 o TBLlong：保存前缀长度大于24的前缀信息 TBL24的表项 前缀长度小于24的将被扩展 例如128.23/16前缀将被扩展为224-16 256项，对应地址为：128.23.0 128.23.255，而这256项将保存相同 的内容，即指向前缀128.23/16转发 信息的指针 查表流程： （1）使用高24位IP地址查找TBL24，读出2个字节数据 若第1位为0，后15位为下一跳信息 否则，把后15位乘以256，加上IP地址低8位，计算新的地址 （2）使用新的地址查找TLBlong表，获得下一跳信息 表项组织的例子 假设到达报文为： （1）10.54.22.147 （2）10.54.34.23 （3）10.54.34.194 232-26=64 每个前缀长度大于24的占用 2562512字节 1M字节保存2K个前缀，满足核 心路由器上前缀分布的要求 DIR-24-8-BASIC算法的优缺点 优点 o 绝大部分需要一次访存， 即时需要2次访存，也可 以流水实现 o 主要前缀长度小于25， 支持数目不限 o 只需要33MB的存储空间 o 若访存为50ns，则每秒 查表20M次 缺点 o 存储器利用率低 o 表项更新复杂。增加或删 除前缀需要大量的存储访 问 o 支持长度超过24的前缀 数目受限 DIR-24-8-BASIC算法的改进（1） o DIR-24-8-INT算法 将2级表 变成3级表，TBLint 表用来指示扩展表的大小， 而不是默认的256项 用多一次访存换取TLBlong 表利用率的提高 TLBlong中表 项为26项 DIR-24-8-BASIC算法的改进（2） o 多级表结构 通过增加访 存次数，降 低存储开销 先用前n比特查表，若有扩 展表项，则用i位索引拼上 后续m位地址继续查找第 二级表，以此类推 算法的更新问题 o 转发表中的“洞”结构，存在多个嵌套的洞时，更新变得 复杂 Row update：软件计算，为更新每个地 址发出一条指令，硬件简单，软件开销太 大 Subrange updata：软件计算可以连续更 新的区域，发出一条指令，触发硬件更新 多个连续的地址 One Instruction update：每个表项中包 含对应的前缀长度（6位），硬件自动识别 是否要更新相应的表项 Tree Bitmap : Hardware/Software IP Lookups with Incremental Updates ACM SIGCOMM Computer Communications Review, Volume 34, Number 2: April 2004 前言（1） o 目前IP查找算法研究得到广泛关注，但目前各种算 法有以下不足 nFIB更改时开销过大，导致正常数据路径的查找中断 n算法假设查表的输出结果仅为出口id（用8-10比特标识 查表结果） o 实际情况需包括前缀访问统计、负载均衡控制和L2信息 ，这些信息都存储在表的叶节点中，大约需要16B n只考虑一般情况，采用网络上现有的FIB进行模拟，可能 不会适应未来情况或极端情况下性能较差 前言（2） o 最长前缀匹配回顾 n 前缀由数字串（如01）以及后续的*组成 n FIB由路由协议生成，包括前缀和输出端口组成 n 例如FIB中仅包括： o 01* P1和0100* P2 o 如果到达报文的目的IP地址以01000开始，选择最 长匹配，从端口P2输出 o 如果到达报文的目的IP地址以01010开始，匹配01* ，从端口P1输出 需求和模型（1） 宽带（如 DSL） 100k个会话，基于会话的队列管理，QoS调度 租用线几K个会话（如T1），帧/语音和VPN的支持 大的企业网QoS支持，加解密，几百个网络接口，对支持的前缀数目 要求不高，但对性能要求较高 边缘ISP成百上千个接口，v4/v6/mpls支持，每个接口可能会有 大量VPN表，对支持的前缀数目和性能要求较高 核心ISP成百上千个接口，v4/v6/mpls支持，对性能要求很高 不同应用场合对路由器查表能力的不同要求 注：一个物理接口可能包含大量的逻辑接口，如ATM的VC，以太 网的VLAN等 需求和模型（2） 路由器的查表模型 需求和模型（3） 转发需要的数据 需求和模型（4） o 路由器需要支持多种控制表的查找 n 不同的表具有不同的查找key和不同的深度 n 使用4比特表示控制表的类型 需求和模型（5） 需求和模型（6） o 同一台路由器在不同场合应用需要处理的表 格类型和支持的表项不同 o 需要各种控制表能够共享存储器空间，采用 统一的查表方法 n 降低成本 n 一些算法不支持这一特性，如基于24/8扩展的 硬件查表方法 存储器技术（1） o 存储器是影响查表算法设计的主要因素之一 o 存储器的指标有： n 容量、随机访问延时、带宽、PCB空间占用（引 脚个数）以及价格等 n 可选的存储器类型有 o 片上RAM、SRAM、DRAM和TCAM 存储器技术（2） o 片上RAM n 优点 o 访存速度快 o 目前90nm ASIC上可实现50Mb的容量 o 可用于部分表项的存储 n 片上SRAM价格昂贵 o 是每bit是网络DRAM（RLDRAM）的25倍 o 是普通DRAM的50倍 存储器技术（3） o SRAM n DDRII/QDRII SRAM n 目前主要为网络应用使用 n 相同访问带宽，每bit价格约为网络DRAM的36倍 存储器技术（4） o DRAM（1） n可采用多个通道，利用dram多bank的特点加速查找的访 问 n例如表项有4级，可采用如下方式存储： bank1 第一级 bank2 第二级 bank1 第三级 bank2 第四级 DRAM1DRAM2 转发引擎 通道1通道2 1. 假设每个bank每20ns可以访问 一次，存储访问延时10ns 2. 如果同时对2个目的IP（d1、 d2）进行查找，每个需要访问4 次，延时为40ns。 3. 但d1在查找第34级时，d2可以 查找12级，因此平均20ns出一 个结果 存储器技术（5） o DRAM（2） n 对于RLDRAM2随机访问时间为20ns，工作在 400MHz DDR方式，burst length为4， o 每次burst时间为1/800MHz * 4=5ns o 在20ns内可进行4个bank的交叉访问 n 若将存储器的4个bank存放相同的FIB，那么 20ns内相当于访存4次，基本与SRAM相当，但价 格仍是SRAM的1/9 n 因此，目前实现查表可以不考虑SRAM 存储器技术（6） SRAM和DRAM存储器的比较 存储器技术（7） o TCAM（1） n优点 o 接口简单 o 性能高，满足高性能路由器的性能需求 o 可以与报文分类集成 n容量问题 o 目前容量最大为18Mb，需要用多片级联来支持较多表项 o 例如支持10M IPv4 VPN（表项宽度为52），需要20片， 功耗超过200W，价格超过$4000 存储器技术（8） o TCAM（2） n 缺点 o 表项配置不灵活，只能配置成288/144/72/36长度 ，可能造成浪费 o 不适合其它路由查表，没有DRAM灵活 o 板面积比DRAM大 o 功耗较大 存储器技术（9） o 小结 n 网络DRAM是实现路由器统一查表的最佳选择 路由器查找引擎的设计要求 o 面向低成本的优化技术十分重要 o 各种转发表的查找能够共享存储器，对可变长度查 找支持灵活，可与其他应用（统计计数器、报文深 度检查等）共享存储器 o 对查找各种不同的表项可以有不同的性能要求，每 个表的大小可灵活伸缩 o 增量修改和in-place修改（不能采用standby修改 ） o RIB表和FIB表采用相同的组织方式和查表方法 o 具有确定的最坏情况的性能 相关研究（1） o Unibit Tries o 扩展Tries o Lulea方法 相关研究（2） o Unibit Trie n 每次查找1bit n 具有最好的存储和更新性能 相关研究（3） o 扩展Tries n 每次使用n bit进行查找，n为步长 n 前缀扩展 o 以n=3为例，1*可扩展为100、101、110和111 相关研究（4） 扩展Tries示意图 每一项都包含前缀和指针 相关研究（5） Leaf pushing 示意图 每一项包含前缀或指针 相关研究（6） o Lulea方法（1） n 节点采用位向量（bitmap）压缩存储开销 0代表本项与前一 项相同 Leaf pushing方法 相关研究（7） o Lulea方法（2） n 缺点是前缀的插入速度慢，主要由于leaf pushing造成 n 在根部插入前缀P0，该前缀信息可能需要推到 数千个叶结点，需要上千次更新 Tree Bitmap算法基于的观察（1） o Multibit节点(代表多层unibit节点)有2 个功能：指向其孩子multibit节点以及 保存下一跳指针（对于最长前缀匹配落 在本节点内部的情况），而这两个功能 是相对独立的。 o 存储器采用burst的访问技术，每次访问存储器的数据 大小，例如SDRAM每次可burst32字节，因此 multibit节点的大小可针对存储器的burst大小进行优 化 Tree Bitmap算法基于的观察（2） o 硬件可在一个时钟周期内处理复杂的bitmap。由 于处理器处理速度与访存速度相差很大，软件处理 复杂bitmap的时间相对访存来说也不算大 o 要提高更新的性能，trie节点的大小不能太大，最 好处理每个trie节点只使用一次访存 o 节点的大小最好是2的次幂，最好是8字节的整数 倍 Tree Bitmap算法思想（1） o 节点所有子节点连续存储（节约指针数目） Tree Bitmap算法思想（2） o 节点采用2个bitmap分别保存前缀信息和子 节点信息 Tree Bitmap算法思想（3） o 减小节点大小，一次burst访问即得到节点信息 n外部子节点信息bitmap n子节点指针 n内部前缀信息bitmap n指向前缀信息块（result block）的指针 o Result block使查找每级节点的访存次数增加到2 次（读节点信息和读相应的result block信息） n采用lazy的result block访问方式，查找过程保存当前 result block，只有全部查找结束才访问result block Tree Bitmap算法思想（4） o Result block的组织 nresult block大小是节点大小的 偶数倍 n每个节点可能使用多个result block n多个result block连续存放 n根据result指针和前缀bitmap 可迅速定位到相应的result block Tree Bitmap算法工作过程（1） o第一步：查找内部bitmap n以下过程可由硬件并行执行，最后选择最长匹配 o用111查找内部bitmap，命中0，说明FIB中无111*前缀 o用11*查找内部bitmap，命中1，说明FIB中有11*前缀 n根据命中1的位置，计算result block中下一跳指针的位置（ 前面有多少个1），并记录 输入地址1110111 Tree Bitmap算法工作过程（2） o 第二步：查找外部bitmap n用111查找命中1，表示有子节点 o bitmap中在其之前有2个1，因此子节点地址为子节点 基地址+2 n根据计算出的子节点地址读出子节点数据 输入地址1110111 Tree Bitmap算法工作过程（3） o 重复叠代前两步，直到处理的节点不再有子节点 n处理中若有新的result指针记录，覆盖前面记录 o 本例中P7的结果记录会覆盖P2的结果记录 n最后从记录的result block中读出下一跳信息的指针 输入地址1110111 Tree Bitmap算法的优化（1） o 主要优化技术 n 初始阵列优化 n 端节点优化 n Bitmap分离 n 节点分割 n CAM节点 Tree Bitmap算法的优化（2） o 初始阵列优化 n用索引的前8项直接查表，找到后续节点的入口 o 减小树搜索的级数 o 初始阵列可存放在片内RAM中 n初始阵列过大虽然可提高性能，但会增加更新复杂度 0 1 255 Tree Bitmap算法的优化（3） o 端节点优化 n只含一个前缀信息的节点为空节点（P8） n如果节点唯一的子节点为空节点。那么该节点可设置成 端节点（end node），并合并其子节点信息 n端节点只包含内部bitmap，但大小不变 Tree Bitmap算法的优化（4） oBitmap分离 n内部前缀bitmap放到internal node中分开存储 o真实表项中大概有一半节点的内部前缀bitmap为空 oInternal node紧靠trie node存储 n若trie node包含前缀P，那么该节点所有匹配P的子节点中均 有一个标志位标明其父节点已经有匹配，查找过程中记录 internal node的地址 oInternal node采用lazy的访问策略 o查找过程中只访问一次内部前缀bitmap 每个节点只保存外部bitmap和指向子 节点的指针 Tree Bitmap算法的优化（5） o 节点分割 n 用来保证节点大小满足存储器的burst size n 在步长和复杂度之间寻求平衡 n 分割的节点连续存储 Tree Bitmap算法的优化（6） o CAM节点 n 有些trie节点的子节点Bitmap为空，而且只有 一个内部前缀 n 将result node的内容直接合并到trie节点中 o 存放在外部bitmap域中 o 用少量bit标示这时一个CAM节点 软件参考实现（1） o 软件实现适合低端路由器以及高端路由器RIB管理 o 采用13,4,4,4,4,3的步长分