范富明;李念军;雷升平;吉萌
【摘 要】网络带宽的急剧增加对处于网络节点的路由器设备数据转发速度提出了更高的要求.为此,将哈希表和多比特树相结合,提出一种新的路由查算法.根据路由前缀的长度将路由表项分层存储在固定的三层Tree中,采用哈希表存储路由下一跳的信息,根据目的IP地址在三层Tree结构中按最长前缀匹配的原则进行快速路由表项定位,并通过表项的信息在对应的哈希表中读取下一跳信息,进行数据转发.在多核平台上的测试结果表明,该算法在百万条路由环境下可达到双向10 GB/s的速度,平均查次数介于1～2次之间,平均延时小于30 μs.
【期刊名称】《计算机工程》
【年(卷),期】2015(041)009
【总页数】5页(P63-67)
【关键词】路由器;路由查;哈希表;多比特树;最长前缀匹配
【作 者】范富明;李念军;雷升平;吉萌
【作者单位】光纤通信技术和网络国家重点实验室,武汉430074;武汉烽火网络有限责任公司,武汉430074;光纤通信技术和网络国家重点实验室,武汉430074;武汉烽火网络有限责任公司,武汉430074;光纤通信技术和网络国家重点实验室,武汉430074;武汉烽火网络有限责任公司,武汉430074;光纤通信技术和网络国家重点实验室,武汉430074;武汉烽火网络有限责任公司,武汉430074
【正文语种】中 文
【中图分类】TP393.04
当前路由查主要有Trie树和哈希表等方法［1-3］。基于Trie树路由算法在路由表项增多情况下，树的深度变大，路由查过程中平均匹配次数变多，算法效率较低。为了提高算法的查效率，路由查过程中采用步长为8的查方式，在一定程度上提高了查的效率。基于哈希表的路由算法，依据前缀长度路由表划分为多张路由子表，在路由条目较少的情况下，取得了较好的性能，但在路由条目较多的情况下，哈希冲突迅速上升，查效率下降明
显［4-5］。当前高端路由设备中大多采用基于Trie树的方式存储路由表项，路由查过程依据表项的数目采用变步长的查方式。在算法实际设计的过程中，为了权衡查速率与消耗存储空间之间的矛盾，对插入的表项要进行再平衡，使得树的高度不至于太高和太低。
传统基于哈希表或Trie树的算法在表项较少的情况下能够取得满意的查效率，但是在表项达到百万以上时，查效率迅速下降，难以满足高端路由设备的需求［6-9］。TCAM（Ternary Content Addressable M em ory）专用芯片凭借其出的硬件查性能，能显著提高路由查性能，可应用与高端路由设备，但是TCAM价格昂贵，在一定程度上限制了其应用的广泛性［10］。当前随着存储设备容量的快速翻倍，内存价格进一步下降，高端路由设备迫于对性能的强烈要求，在算法中适当地采用内存空间置换时间也是可行的。
本文借鉴上述路由查算法的特点，综合考虑内存消耗和查效率的因素，提出一种基于哈希表和多比特树的路由最长前缀匹配查算法。路由表项根据前缀长度采用分段储的方式，表项查和放置过程均从顶层开始。从数据结构上来看，每一级都是相当一个完全多比特树。本文根据表项结构的存储特点，在算法的内存消耗方面采取了进一步优化，同时为解决因表项重复而导致的遍历困难问题，引入哈希表用于优化。
当前处理芯片大多具有用于动态随机存取存储器（dynamic Random Access M emory，DRAM）管理的专用接口，为数据在内存中的读写效率提供了较好的硬件条件，也为基于DRAM的大表项路由查算法的设计与实现提供了可能性。高效的路由查方法的设计在依赖硬件基础的同时，良好的算法数据结构的设计显得更加关键。
2.1 路由查机制
16-8-8路由查机制如图1所示。在路由条目存储是根据前缀长度分为第1部分1 bit～16 bit，第2部分17 bit～24 bit，第3部分25 bit～32 bit。
查是采用最长前缀匹配（LPM）查机制，首先取地址前16 bit的数值，在第1部分数组定位表项位置，并对表项的有效性进行测试。Valib为表项有效性的标志位，如果Valib=1，表明当前表项是有效的，如果Valib=0，则表明表项为空；Cont表示是否有更长路由可供查的标志位，表明可以进行下一部分的查，如果Valib=1，Cont=0，表明当前的路由是唯一最长的匹配的路由，则可以在表项结构Info指针的地址中直接获取下一跳的输出信息，表项数据结构如图2所示。
linian如果Valib=1，Cont=1，表明有比当前长度为16 bit的表项更长的路由表项存在下一部分中，并需要抽取目的IP地址的17 bit～24 bit的数值作为偏移量，在第2级的对应数组中查询表项。在第2级的表项判别过程同上一部分完全相同，主要对2个标志位进行判别。区分是查成功、失败或还是需要进入下一步中继续查，如图3所示。
第2级表的起始位置M in和结束位置Maχ，Maχ-M in+1表示第2级表中可供查的表项数，Maχ和M in的取值都不超过第2级表的最大有效表项数。Info路由信息指针，指向路由的下一跳信息。L1_Entry指向第2级表中相应表项的起始位置。
2.2 路由存储机制
如图2所示，当路由前缀长度小于16 bit时，将路由添加到路由表的第1级表Tbl_L1_Entry中。当路由前缀长度介于17 bit～24 bit之间时，将路由添加到路由表的第2级表Tbl_L2_Entry中。但需要根据路由前16位前缀在第一级表中到对应的表项位置，并将Valid和Cont位置为有效。当路由前缀长度介于25 bit～32 bit之间时，将路由添加到路由表的第3级表Tbl_L3_Entry中。但需要根据路由前16位前缀在第一级表中到对应的表项位置，并将Valid和Cont位置为有效；并且根据17 bit～24 bit为前缀在第2级表中到对应的表项位置，同样
将该表项的Valid和Cont位置为有效。
例如有3个路由表项先后需要插入到路由表中：
首先A=10.0.0.0/8，前缀长度小于16故而直接存储到表的第1部分，则根据表项IP的前16位，到table1［2560］的表项作为地址，前缀长度为8的表项A=10.0.0.0/8，在第一级表项中作用域10.0.X.X～10.255.X.X，第一级的下一跳指向A的表项都是其作用域。
第2条表项B=10.34.128.0/17，其前缀长度大于16，因此需要动用第1级和第2级进行表项的存储，首先在第一部分的Tbl_L1_Entry［2594］的表项中将Cont标志位置为1，表明有比10.34给长的表项供匹配。在第2部分中的Tbl_L2_Entry［128］个表项起始，开始插入表项，其作用域是从10.34.128.X到10.34.255.X，第2级的下一跳指向B的表项都是其作用域。
第3条表项C=10.34.192.0/18，同样长度大于16，并且同样在第1部分的Tbl_L1_Entry［2594］表项中，指向第二部分的列表，由于其前缀长度为18，故而其作用域为10.34.192.X～10.34.255.X，在第2部分表项插入过程中，需要进行判别已经存在表项的前缀长度Len是否小于当前需要插入的表项前缀18，如果小于，则需要对已存在表项进行替换。
由于第2条表项插入的前缀Len为17，小于当前的前缀长度18，因此如图3表项下一跳指向C的所示，其对原有的部分下一跳指向B的表项进行了替换。
由上述算法的原理可知，在设计上采用三级的表项设计，前缀1到16的第一级完全采用连续的内存空间存储表项，二三级以近似256个表项为单位的连续内存存储方式。这些连续的内存存储组织方式，使得路由在查或存储的过程中，根据目的IP或路由可以很简便的计算出地址偏移量，从而快速定位到表项的位置，相对于传统的动态树形结构的路由组织方式在路由查和路由添加效率上确实高很多。但算法是这种设计方式耗用了大量内存，并且有相当一部分的路由表项是空的，同时由于作用域的存在造成很多表项的键值是重复的，这些重复键值的存在导致路由遍历操作的困难，难以完成用户的Show或Dum p路由条目的操作，因此需要对算法进行进一步的优化。
3.1 内存空间的优化
根据网络研究机构的有效数据统计IPV4的路由前缀99.93%是小于等于24的［3］，也就是说大部分表项在树形结构中分布于第一级和第二级中。第一层的长度16的前缀路由表项的存储空间是在初始化的时候一次分配完成，大约为Tbl_L1_Entry［52000］（除去多播地址区间）
，但是对于第2级和第3级的空间是根据添加路由的前缀长度动态分配。
二三级前缀范围分别从17～24和25～32，前缀跨度为8，一般二三级存储的时标号是0～255，需要的存储块大小统一都是256个表项空间，这中内存分配方式在一定程度上造成空间的浪费。算法在设计的过程中，在第一级和第二级的表项中设置了2个参数：M in和Maχ域，其分别用来标示下一级中表项的起始和结束段地址，其值是0～255范围内的一个子区间，这个区间的大小取决与路由前缀的长度，该区间总是0～255范围的一个子区间，消耗的内存空间块大小总是不超过256个表项空间。
3.2 哈希表的引入
为了解决表项遍历的问题，算法在设计上增加了一张用于存储下一跳的信息的Hash表。Hash表根据前缀的长度建立32张子表，相同前缀的路由表项下一跳信息存储在同一张子表中。每次在树形结构中添加表项的时候，先把下一跳的信息结构Info添加到Hash表中，并把该地址指针传给树形表项的Info指针。
虽然树形结构中有多个重复的表项，但是每个重复的表项的Info域指向哈希表中的地址是相
同的Htbl_Entry，如图3所示。添加的路由表项根据前缀长度在Hash表中的信息是唯一的，因此，在进路由Dump或Show进行路由遍历的时候，从在Hash表中32张子表中依次遍历出路由信息。
哈希表在冲突域中采用单链表的组织方式，虽然由于表项条目巨大，路由信息的添加和删除的过程中，碰撞比较多。但是哈希表管理与维护是由控制平面来完成的，不会给数据平面的转发效率带来影响。
为了实现最长匹配，依次从顶层开始向下查。如果在第一层没有匹配到路由前缀项，则表明路由不存在，则对数据包进行丢弃或送默认路由。如果在尽可能深的层次中匹配到表项，表明是最长的路由匹配，并通过表项中Info指针在哈希表中获取下一跳的信息，并到相应的出接口。
步骤1 根据目的IP地址计算出高16位数值L1_Base_Idx，在第一级路由表结构中到对于的表项Tbl_L1_Entry［L1_Base_Idx］。判别表项中的Valid标志位，如果Valid=0进入步骤8；如果Valid=1，进一步判别Cont标志位，如果Cont=1，进入步骤3，否则进入步骤2。
步骤2 根据Tbl_L1_Entry［L1_Base_Idx］表项中的Info指针，到路由信息H tbl_Entry，即可获得出接口Index和下一跳网关等信息，进入步骤7。
步骤3 表明第二级中可能存在更长的路由表项，其中L2_Entry指向下一级结构内存的起始地址Table2［0］，根据目的IP地址的17～24位获得数值L2_Base_Idx，将L2_Base_Idx值与上级Tbl_L1_Entry［L1_Base_Idx］中的M in和Maχ值进行比较，如果L2_Base_Idx不在M in和Maχ组成的闭区间内，返回步骤2；如果L2_Base_Idx在M in和Maχ组成的闭区间中，表明第二级空间中存在该路由。进一步检查Tbl_L2_Entry［L2_Base_Idx］表项中Valid的有效性，如果Valid=0，表明该表项无效，返回步骤2；如果Valid=1，进一步判别Cont标志位，如果Cont=1，进入步骤5，否则进入步骤4。
发布评论