一种改进的TCAM路由表项管理算法及实现

张宏亮，陈 明，贾永兴，陈沛然

（中国电子科技集团公司第三十研究所，四川 成都 610041）

0 引言

近年来移动互联网、物联网、大数据等技术日新月异，深刻地影响着人们的生产和生活。网络中高带宽、低延迟的数据业务对路由器转发速率的要求也越来越高，然而使用软件通过如Patricia树[1]、路径压缩树[1]（Path compressed tree）等结构来组织路由表数据，并配合相应的算法来实现路由查表的方案，已无法满足高速转发的要求。正是在这种背景下，业界提出了基于硬件三态内容寻址存储器（Ternary Content-Addressable Memory，TCAM）的路由查表方案。该方案解决了（Classless Inter-Domain Routing，CIDR）[2,3]最长前缀匹配问题，因此在行业内得到大规模应用。TCAM硬件查表的时长恒定为一个时钟周期，时间复杂度仅为O(1)，但由于TCAM对路由表项存放有严格的顺序要求，使得表项管理趋于复杂，例如，当表项更新时，无法进行查表，此时数据包需要先缓存，等表项更新完毕后才能查表。此外，若表项更新时间过长，会引起缓存溢出，进而产生严重丢包，影响路由器的正常转发性能。因此，表项管理算法的性能是影响TCAM路由查表性能的关键因素之一。

本文首先分析现有表项管理算法的优缺点；其次利用前缀块概率分布、动态平衡的特点，对表项预留模型进行了优化，合理利用回收缓存；最后提出并实现一种改进的基于缓存的双链表管理算法。

1 TCAM原理及特性分析

TCAM每个存储比特可以有3种状态：0,1,X。X态表示“Don’t care”，正是这第三态的特征使得其能进行模糊匹配查表。在模糊匹配查表时，可能存在多个表项都匹配的情况，此时TCAM会在匹配表项中选择地址最低的表项作为最终匹配项，如图1所示。

图1 TCAM最长匹配规则

TCAM存放路由表时，需要按地址由低到高，依次存放前缀长度由长到短的表项[4]，才能实现最长前缀匹配。这种硬性规定，让表项管理变得复杂，有时会附带无法避免的现有表项的挪动。

假设TCAM的容量为M，现存表项总数为N。用原始的方法添加一条表项，且要保证顺序要求，就要在TCAM的特定位置增加才行，不然表项的前缀长度会乱序。最糟糕的情况下，需要挪动N次为其挪出空间，时间复杂度为O(N)。因此，实现表项高效管理、减少挪动次数、节省更新时间，是提高查表速度的几个关键因素。

2 TCAM表项管理算法介绍

本文以IPv4路由表为例进行说明，其中的方法也可以扩展到IPv6上，同时假定其前缀块长度范围在3～32之间。

2.1 顺序移动法

顺序移动法如图2所示，图中相同长度表项组成前缀块。从TCAM低地址空间开始，按前缀块由长到短的顺序存放表项，高地址处存放空闲表。当新增加一个表项时，假设其前缀长度为i(3≤i≤32)，表项中长度小于i的表项都需要挪动位置，然后插入新表项。显然，这种管理方式造成现有表项关联移动次数过多，效率极低。最糟糕的情况下，时间复杂度为O(N)，其中N是TCAM中现存的表项条数。

图2 顺序移动法

2.2 带预留表项的顺序移动法

与顺序移动法相比，带预留表项的顺序移动算法[5]的改进之处在于，把空闲表分散到各个前缀块内部。如图3所示，带预留表项的顺序移动算法中3～32前缀长度预留相同大小的存储空间。当添加表项时，假设其前缀长度为i(3≤i≤32)，如果i对应的前缀块内部未占满，则直接写入，现存表项不需要挪动；若i前缀块内部占满，则借占i+1前缀块的预留空间尾部位置添加表项。当删除表项时，为保证空闲表的连续性，i前缀块内部在其后面的表项都往上挪动一位。该算法仅减少了表项移动的平均次数，但若是前缀块及相邻前缀块预留空间均占满的情况下，时间复杂度仍然是O(N)。

图3 带预留表项的顺序移动法

2.3 选择移动法

由第1节可知：路由最长前缀匹配只要求不同长度表项的存放有顺序关系，相同长度的表项不要求顺序。选择移动法则充分利用此特性，其表项存放结构与顺序移动法相同。如图4所示，假设新添加的表项前缀长度为i(3≤i≤32)，那么需要按前缀块长度由短到长的顺序，依次将前缀长度为3,4,…,i-1的前缀块的第一条表项挪至该前缀块尾部。其时间复杂度为O(P)(0

图4 选择移动法

2.4 带预留表项的选择移动法

通过将预留空间、选择移动两种方法结合起来，减少关联移动次数，这就是带预留表项的选择移动法的思路。如图5所示，3～32前缀长度预留相同大小的存储空间。当新增加一个表项时，假设其前缀长度为i(3≤i≤32)，若i对应前缀块有空闲，则直接写入。若i预留空间占满，则考虑i+1前缀块是否未满。如果未满，则借i+1预留空间尾部地址写入表项；否则，按选择移动法的方式处理，直到为i前缀块挪出空间写入新表项。删除表项时，也要求在挪动i前缀块内部被删除表项以后的表项，以保持空闲表连续，并且仅在i前缀块及相邻i+1前缀块均占满的情况下，才挪动表项，关联移动概率大幅降低，算法时间复杂度比选择移动法更小。

图5 带预留表项的选择移动法

3 一种改进的带预留表项的选择移动法及实现

综合分析顺序移动法、带预留表项的顺序移动法、选择移动法、带预留表项的选择移动法[6,7]这几种现存的TCAM管理算法，可以看出TCAM表项管理算法优化主要有以下几个方向：

（1）选择与实际路由前缀分布最符合的预留模型；

（2）当出现特定长度前缀块预留空间满时，尽最大可能减少现存表项的移动次数；

（3）系统趋稳后，特定长度前缀块内部表项新增和删除的次数会趋于相同，可以充分利用动态平衡的特性进行缓存优化。

3.1 选择最符合的预留模型

现实中各种网络设备侧重不一样，IP前缀长度为3～32的路由表项分布也不一样，比如，核心骨干网与边缘接入网对IP地址段的使用侧重就不一样。核心骨干网和边缘接入网节点IP前缀按长度分布情况分别如图6、图7所示。边缘接入网一般24～32之间网段需求最多，核心骨干网则对长度8～24之间的IP前缀需求最多[8]，尤其是8，16，24位长度的IP前缀需求较多。如图6所示，在设备规划设计阶段，通过对核心骨干网节点的统计分析发现，8～24位长度掩码的占了98%，其他长度掩码的IP路由地址，总共才占2%。如图7所示，在边缘接入网节点对24～32位IP前缀需求最多，总计占了约80%的比例，其他长度IP前缀仅占20%左右。

图6 核心骨干节点IP前缀按长度分布的情况

图7 边缘接入节点IP前缀按长度分布的情况

结合设计，本文可以得出按掩码长度i(3≤i≤32)统计分布概率的模型a[i]，其中。假设TCAM容量为N，根据概率统计分布，可以得出掩码长度为i的预留表项大小为r[i]=N×a[i]。如果网络无法通过设计方案得出概率分布，则可以根据分类原则，首先确定路由节点在网络中承担的是核心骨干、边缘接入或者混合接入的角色，其次对相应范围的前缀增大权重比。此外，也可以通过抽样分析的方法，确定最终合适的统计分布模型。

根据以上分析，本文可以定义出如下的数据结构：struct route_queue[32]数组。对于任一掩码长度i对应的预留描述结构route_queue[i]，如图8所示，其中total字段表示为该前缀块预留表项总条数，length为当前该前缀块已经使用的表项大小。head、tail、empty_head、empty_tail为前缀块内部TCAM分配管理使用的字段（下一小节予以说明），这样即可生成与实际情况相匹配的前缀块预留模型。

图8 route_queue结构

3.2 减少现存表项移动次数

带预留表项的选择移动法保证IP前缀块之间相对顺序一致，但其实前缀块内部不需要绝对的先后存放顺序。该方法还要求前缀块内部已使用表项和空闲表之间保持连续，这就会增加额外的前缀块内部路由集合的移动次数。在相同长度前缀块内部，也并非一定要让已使用表项和空闲表严格分开，可以通过在前缀块内部，增加已分配链表（已占用表和空闲链表）和空闲链表这两个链表，将它们分别组织起来。需要说明的是，空闲链表是已分配链表的子集。如图9所示，index为分配的TCAM地址，use_flag表示是否占用，next、prev指针用于构建已分配链表，empty_next、empty_prev用于构建空闲链表，entry则是对应具体的路由信息。按照掩码长度形成的已分配链表、空闲链表如图10 所示。

图9 route_node结构

图10 基于前缀块长度的TCAM管理双链表

该管理算法添加路由表项的步骤如下文所述。

（1）对于掩码长度为i的新增路由，首先通过route_queue的total和length比较，判断相对应前缀块是否占满。如果未占满，按照链表顺序搜索空闲表项，即首先通过route_queue[i]的empty_head指针搜索。如果能寻找到，那么直接添加表项，同时将该节点use_flag标示为已占用，并将该节点移出空闲链表。

（2）如果在空闲表内未找到可使用节点但预留还未填满，则在当前掩码长度块的预留范围内，创建新的route_node。将该节点关联的TCAM地址置为tail节点的index+1，并加入已分配链表表尾，形成新的tail。

（3）如果当前掩码长度预留范围已占满，则优先向掩码长度i+1的预留地址范围，检查其是否存在未分配地址空间（向上扩展）。如果存在，则直接添加表项，不用挪动现有表项，仅需修正相邻前缀块的预留范围和大小。

（4）如果无法向上扩展，则开始尝试向下扩展。这个时候使用带预留表项的选择移动法挪动表项，直到存在可用空闲表为止。

删除路由时，首先直接删除TCAM表内容或置该项无效，其次通过软件将需要删除的路由节点use_flag置为空闲，同时将该路由节点加入空闲链表尾部，以备添加路由时使用。

通过分析可以得到以下几点结论。

（1）前缀块内部空闲链表有已分配的空闲节点可以使用时，不需要系统分配新的route_node，更不需要挪动现有表项，可以直接添加表项，能加快表项更新速度。

（2）当空闲链表为空但前缀块预留空间未满时，仅需分配新的route_node即可添加表项，也不需要挪动现有表项。

（3）当长度i前缀块预留空间占满时，可以优先向i+1长度前缀块预留空间扩充（向上扩展）。由于前缀块内部优先从地址小的空间分配route_node，所以向i+1前缀块空间扩展大概率仅需调整相邻前缀块的预留参数，然后分配、添加新route_node表项即可，也不需要挪动现有表项。

（4）当i+1长度的前缀块已分配完毕（无论是否占用完），表明i+1长度前缀块存储表项的突发峰值已经达到预留空间大小，此时不应当向i+1长度前缀块借占空间。此时，考虑向i-1长度前缀块借占空间，有一定概率i-1长度块并未分配空间，此时也不用挪动现有表项，可以直接添加route_node，并加入分配表的链表尾部。更多的情况是，i-1长度前缀块开始处的空间已经被分配，这个时候就需要考虑传统的带预留表项的选择移动法，挪动未占用的TCAM空间，为i长度前缀块分配空间。此时，是向i长度前缀块的上方，还是下方寻找可以挪动的空间，可以作为一个新的研究方向。

4 结语

本文根据具体实现，有针对性地优化路由表项的预留模型，充分利用前缀块内部动态平衡的特点，减少表项移动的次数、降低表项移动的复杂度，进而提高表项更新的速度。本文研究是提高TCAM查表速度的一个研究方向。本文在分析现有方案的优缺点之后，结合前缀块静态概率分布、动态路由平衡等特点，提出并实现了基于缓存优化的双链表管理算法，对带预留表项的选择移动法进行了深入的优化，并在实践中取得了较好的效果。