支持多nexthop的TCAM高速查找方法及其系统

摘要

支持多nexthop的TCAM的高速查找方法及其系统属于互联网中IP地址高速查找技术领域，其特征在于：它是一种基于三态内容可寻址存储器TCAM的采用索引方式对路由表项中的多个下一跳(nexthop)以块的形式进行存储，同时再把下一跳地址、端口组成nexthop映射表来进行高速查找的方法，它针对几乎所用的路由表项的下一跳个数都低于4这一规律同时以下一跳的个数为8个作为上限建立了一、二两级下一跳索引表。它具有高速查找、存储空间少、支持IPv6的扩展以及可支持多个下一跳等优点。

主权项

1.支持多nexthop的TCAM高速查找方法，其特征在于它是一种采用索引方式对路由表 项中的多个下一跳(Nexthop)组成以块(Block)的形式进行存储，同时再把下一跳地址、 端口和相应的下一跳组成Nexthop映射表索引来进行高速查找的方法，它针对几乎所用的路 由表项的下一跳个数都低于4个这一个规律同时以下一跳的个数为8个作为上限，建立了一、 二两级下一跳索引表；它是在具有高速路由查找性能的三态内容可寻址的存储器(TCAM) 的基础上实现的，依次含用如下的步骤： (1)初始化： 在TCAM单元k存储路由前缀信息； 在SRAM1中，与TCAM的存储单元k一一对应，按下述三类数据结构存储一级下一 跳索引信息，组成一级索引表； a类：共16位，第1位是0，表示只有一个下一跳；其余15位是该下一跳的映射表索 引； b类：共16位，第1位是1，表示下一跳个数大于1；第2～3位是块号(Blocknumber)， 表示块内的路由表项存在2、3或4个下一跳；第4～16位表示二级下一跳索引表的块内 偏移(Blockoffset)；用BN表示二级下一跳索引表内的块编号，BN＝0、1、2分别表示 相应的块内依次存在着2、3或4个下一跳； c类：共16位，第1位是1，表示下一跳多于一个；第2～3位表示块号BN＝3，意义 同上；第4～6位表示该块号3内的下一跳数(Nexthopnumber)，它的取值在2～8之间； 第7～16位表示块内偏移，意义同上，用BO来表示； 在SRAM2中存储下一跳映射表的索引，组成二级下一跳索引表；该索引表分成4块， 前三块分别存储下一跳个数为2、3或4的路由表项的映射表索引，第4块存储下一跳个 数为2～8之间的路由表项的映射表索引；其中，路由表项的多个下一跳的映射表索引在 二级索引表中连续存储； 在SRAM3中存储转发信息，内容为下一跳的IP地址和出端口号，组成下一跳映射表， 设定下一跳映射表的深度为256； 在现场可编程门阵列(FPGA)中存储二级下一跳索引表中4个块的基地址(BA，base address)，即每一块内第一个下一跳的首地址； (2)输入分组的源地址和分组的目的地址； (3)根据目的IP地址查找TCAM芯片，得到最长匹配前缀所在单元k； (4)访问一级下一跳索引表的单元k； (5)判断单元k的第1位： 若第1位为0，则从单元k中获得下一跳映射表索引，跳到步骤(9)； 若第1位为1，则执行步骤(6)； (6)把一级索引表单元k中的BN、BO和NN传送到FPGA存储和控制电路； (7)FPGA根据BN、BO和NN计算出要访问的二级下一跳索引表的单元位置，它依次含 有以下的步骤： 7.1通过BN，得到相应块的基地址BA； 7.2判断BN的值： 若BN＜3，则得到相应的NN，即BN＝0，1，2分别对应NN＝2，3，4； 若BN＝3，则从一级下一跳索引表中的c类数据结构中得到NN，即下一跳数目； 7.3根据下述策略选择转发的下一跳映射表索引： 7.3.1根据下式得到选择的下一跳的索引(index)： (分组的源地址+分组的目的地址)/NN； 7.3.2通过计算(BA+BO+index)得到要访问的二级索引表的单元位置； (8)根据FPGA计算的结果访问二级索引表，得到下一跳映射表索引； (9)根据下一跳映射表索引，访问映射表，得到转发信息。