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

高速IP查表算法,国防科大计算机学院孙志刚,2010年路由器原理与设计,主要内容,RoutingLookupsinHardwareatMemoryAccessSpeedsTreeBitmap:Hardware/SoftwareIPLookupswithIncrementalUpdates,RoutingLookupsinHardwareatMemoryAccessSpeeds,PankajGupta,StevenLin,andNickMcKeownComputerSystemsLaboratory,StanfordUniversityInfocom1998,算法研究目标,算法必须硬件实现简单查表只需要一次访存操作如果需要多次访存操作只有很少概率需要多次访存访存次数有很小的上限，如2次、3次等数据在不同的物理存储器中保存，有利于流水实现控制表格的更新开销小,算法研究基于的假设,存储器的价格便宜路由前缀长度分布特征,核心路由器上路由前缀长度超过24的十分少例如：MAE-EAST骨干路由器中99.93%的路由前缀小于等于24,DIR-24-8-BASIC结构,TBL24：保存前缀长度小于等于24的所有前缀的信息0.0.0-255.255.255TBLlong：保存前缀长度大于24的前缀信息,TBL24的表项,前缀长度小于24的将被扩展例如128.23/16前缀将被扩展为224-16256项，对应地址为：128.23.0128.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算法的优缺点,优点,绝大部分需要一次访存，即时需要2次访存，也可以流水实现主要前缀长度小于25，支持数目不限只需要33MB的存储空间若访存为50ns，则每秒查表20M次,缺点,存储器利用率低表项更新复杂。增加或删除前缀需要大量的存储访问支持长度超过24的前缀数目受限,DIR-24-8-BASIC算法的改进（1）,DIR-24-8-INT算法,将2级表变成3级表，TBLint表用来指示扩展表的大小，而不是默认的256项用多一次访存换取TLBlong表利用率的提高,TLBlong中表项为26项,DIR-24-8-BASIC算法的改进（2）,多级表结构,通过增加访存次数，降低存储开销,先用前n比特查表，若有扩展表项，则用i位索引拼上后续m位地址继续查找第二级表，以此类推,算法的更新问题,转发表中的“洞”结构，存在多个嵌套的洞时，更新变得复杂,Rowupdate：软件计算，为更新每个地址发出一条指令，硬件简单，软件开销太大Subrangeupdata：软件计算可以连续更新的区域，发出一条指令，触发硬件更新多个连续的地址OneInstructionupdate：每个表项中包含对应的前缀长度（6位），硬件自动识别是否要更新相应的表项,TreeBitmap:Hardware/SoftwareIPLookupswithIncrementalUpdates,ACMSIGCOMMComputerCommunicationsReview,Volume34,Number2:April2004,前言（1）,目前IP查找算法研究得到广泛关注，但目前各种算法有以下不足FIB更改时开销过大，导致正常数据路径的查找中断算法假设查表的输出结果仅为出口id（用8-10比特标识查表结果）实际情况需包括前缀访问统计、负载均衡控制和L2信息，这些信息都存储在表的叶节点中，大约需要16B只考虑一般情况，采用网络上现有的FIB进行模拟，可能不会适应未来情况或极端情况下性能较差,前言（2）,最长前缀匹配回顾前缀由数字串（如01）以及后续的*组成FIB由路由协议生成，包括前缀和输出端口组成例如FIB中仅包括：01*-P1和0100*-P2如果到达报文的目的IP地址以01000开始，选择最长匹配，从端口P2输出如果到达报文的目的IP地址以01010开始，匹配01*，从端口P1输出,需求和模型（1）,不同应用场合对路由器查表能力的不同要求,注：一个物理接口可能包含大量的逻辑接口，如ATM的VC，以太网的VLAN等,需求和模型（2）,路由器的查表模型,需求和模型（3）,转发需要的数据,需求和模型（4）,路由器需要支持多种控制表的查找不同的表具有不同的查找key和不同的深度使用4比特表示控制表的类型,需求和模型（5）,需求和模型（6）,同一台路由器在不同场合应用需要处理的表格类型和支持的表项不同需要各种控制表能够共享存储器空间，采用统一的查表方法降低成本一些算法不支持这一特性，如基于24/8扩展的硬件查表方法,存储器技术（1）,存储器是影响查表算法设计的主要因素之一存储器的指标有：容量、随机访问延时、带宽、PCB空间占用（引脚个数）以及价格等可选的存储器类型有片上RAM、SRAM、DRAM和TCAM,存储器技术（2）,片上RAM优点访存速度快目前90nmASIC上可实现50Mb的容量可用于部分表项的存储片上SRAM价格昂贵是每bit是网络DRAM（RLDRAM）的25倍是普通DRAM的50倍,存储器技术（3）,SRAMDDRII/QDRIISRAM目前主要为网络应用使用相同访问带宽，每bit价格约为网络DRAM的36倍,存储器技术（4）,DRAM（1）可采用多个通道，利用dram多bank的特点加速查找的访问例如表项有4级，可采用如下方式存储：,bank1第一级,bank2第二级,bank1第三级,bank2第四级,DRAM1,DRAM2,转发引擎,通道1,通道2,假设每个bank每20ns可以访问一次，存储访问延时10ns如果同时对2个目的IP（d1、d2）进行查找，每个需要访问4次，延时为40ns。但d1在查找第34级时，d2可以查找12级，因此平均20ns出一个结果,存储器技术（5）,DRAM（2）对于RLDRAM2随机访问时间为20ns，工作在400MHzDDR方式，burstlength为4，每次burst时间为1/800MHz*4=5ns在20ns内可进行4个bank的交叉访问若将存储器的4个bank存放相同的FIB，那么20ns内相当于访存4次，基本与SRAM相当，但价格仍是SRAM的1/9因此，目前实现查表可以不考虑SRAM,存储器技术（6）,SRAM和DRAM存储器的比较,存储器技术（7）,TCAM（1）优点接口简单性能高，满足高性能路由器的性能需求可以与报文分类集成容量问题目前容量最大为18Mb，需要用多片级联来支持较多表项例如支持10MIPv4VPN（表项宽度为52），需要20片，功耗超过200W，价格超过$4000,存储器技术（8）,TCAM（2）缺点表项配置不灵活，只能配置成288/144/72/36长度，可能造成浪费不适合其它路由查表，没有DRAM灵活板面积比DRAM大功耗较大,存储器技术（9）,小结网络DRAM是实现路由器统一查表的最佳选择,路由器查找引擎的设计要求,面向低成本的优化技术十分重要各种转发表的查找能够共享存储器，对可变长度查找支持灵活，可与其他应用（统计计数器、报文深度检查等）共享存储器对查找各种不同的表项可以有不同的性能要求，每个表的大小可灵活伸缩增量修改和in-place修改（不能采用standby修改）RIB表和FIB表采用相同的组织方式和查表方法具有确定的最坏情况的性能,相关研究（1）,UnibitTries扩展TriesLulea方法,相关研究（2）,UnibitTrie每次查找1bit具有最好的存储和更新性能,相关研究（3）,扩展Tries每次使用nbit进行查找，n为步长前缀扩展以n=3为例，1*可扩展为100、101、110和111,相关研究（4）,扩展Tries示意图,每一项都包含前缀和指针,相关研究（5）,Leafpushing示意图,每一项包含前缀或指针,相关研究（6）,Lulea方法（1）节点采用位向量（bitmap）压缩存储开销,0代表本项与前一项相同,Leafpushing方法,相关研究（7）,Lulea方法（2）缺点是前缀的插入速度慢，主要由于leafpushing造成在根部插入前缀P0，该前缀信息可能需要推到数千个叶结点，需要上千次更新,TreeBitmap算法基于的观察（1）,Multibit节点(代表多层unibit节点)有2个功能：指向其孩子multibit节点以及保存下一跳指针（对于最长前缀匹配落在本节点内部的情况），而这两个功能是相对独立的。,存储器采用burst的访问技术，每次访问存储器的数据大小，例如SDRAM每次可burst32字节，因此multibit节点的大小可针对存储器的burst大小进行优化,TreeBitmap算法基于的观察（2）,硬件可在一个时钟周期内处理复杂的bitmap。由于处理器处理速度与访存速度相差很大，软件处理复杂bitmap的时间相对访存来说也不算大要提高更新的性能，trie节点的大小不能太大，最好处理每个trie节点只使用一次访存节点的大小最好是2的次幂，最好是8字节的整数倍,TreeBitmap算法思想（1）,节点所有子节点连续存储（节约指针数目）,TreeBitmap算法思想（2）,节点采用2个bitmap分别保存前缀信息和子节点信息,TreeBitmap算法思想（3）,减小节点大小，一次burst访问即得到节点信息外部子节点信息bitmap子节点指针内部前缀信息bitmap指向前缀信息块（resultblock）的指针Resultblock使查找每级节点的访存次数增加到2次（读节点信息和读相应的resultblock信息）采用lazy的resultblock访问方式，查找过程保存当前resultblock，只有全部查找结束才访问resultblock,TreeBitmap算法思想（4）,Resultblock的组织resultblock大小是节点大小的偶数倍每个节点可能使用多个resultblock多个resultblock连续存放根据result指针和前缀bitmap可迅速定位到相应的resultblock,TreeBitmap算法工作过程（1）,第一步：查找内部bitmap以下过程可由硬件并行执行，最后选择最长匹配用111查找内部bitmap，命中0，说明FIB中无111*前缀用11*查找内部bitmap，命中1，说明FIB中有11*前缀根据命中1的位置，计算resultblock中下一跳指针的位置（前面有多少个1），并记录,输入地址1110111,TreeBitmap算法工作过程（2）,第二步：查找外部bitmap用111查找命中1，表示有子节点bitmap中在其之前有2个1，因此子节点地址为子节点基地址+2根据计算出的子节点地址读出子节点数据,输入地址1110111,TreeBitmap算法工作过程（3）,重复叠代前两步，直到处理的节点不再有子节点处理中若有新的result指针记录，覆盖前面记录本例中P7的结果记录会覆盖P2的结果记录最后从记录的resultblock中读出下一跳信息的指针,输入地址1110111,TreeBitmap算法的优化（1）,主要优化技术初始阵列优化端节点优化Bitmap分离节点分割CAM节点,TreeBitmap算法的优化（2）,初始阵列优化用索引的前8项直接查表，找到后续节点的入口减小树搜索的级数初始阵列可存放在片内RAM中初始阵列过大虽然可提高性能，但会增加更新复杂度,01255,TreeBitmap算法的优化（3）,端节点优化只含一个前缀信息的节点为空节点（P8）如果节点唯一的子节点为空节点。那么该节点可设置成端节点（endnode），并合并其子节点信息端节点只包含内部bitmap，但大小不变,TreeBitmap算法的优化（4）,Bitmap分离内部前缀bitmap放到internalnode中分开存储真实表项中大概有一半节点的内部前缀bitmap为空Internalnode紧靠trienode存储若trienode包含前缀P，那么该节点所有匹配P的子节点中均有一个标志位标明其父节点已经有匹配，查找过程中记录internalnode的地址Internalnode采用lazy的访问策略查找过程中只访问一次内部前缀bitmap,每个节点只保存外部bitmap和指向子节点的指针,TreeBitmap算法的优化（5）,节点分割用来保证节点大小满足存储器的burstsize在步长和复杂度之间寻求平衡分割的节点连续存储,TreeBitmap算法的优化（6）,CAM节点有些trie节点的子节点Bitmap为空，而且只有一个内部前缀将resultnode的内容直接合并到trie节点中存放在外部bitmap域中用少量bit标示这时一个CAM节点,软件参考实现（1）,软件实现适合低端路由器以及高端路由器RIB管理采用13,4,4,4,4,3的步长分配13决定初始