CN1996952A

CN1996952A - Tcam路由表查找方法及tcam路由表查找装置

Info

Publication number: CN1996952A
Application number: CNA2006101653299A
Authority: CN
Inventors: 宋建明
Original assignee: Hangzhou Huawei 3Com Technology Co Ltd
Current assignee: New H3C Technologies Co Ltd
Priority date: 2006-12-18
Filing date: 2006-12-18
Publication date: 2007-07-11
Anticipated expiration: 2026-12-18
Also published as: CN100481820C

Abstract

本发明涉及一种TCAM路由表查找方法及TCAM路由表查找装置。其中，方法包括：预先在TCAM路由表地址单元中保存加长IP地址和加长掩码，检测到携带有掩码表示位的加长IP地址后，根据预先设定的指令信息判断是否要进行路由表维护，是则根据该加长IP地址在TCAM路由表中查找相应的地址单元。装置包括：地址检测模块，路由表模块和查找模块。由于增加了掩码表示位，因此不需要另设维护表也可以找到要维护的TCAM路由表的地址单元，从而节省了存储空间；并且整个查找过程可以通过硬件一次完成，不需要再通过软件对维护表进行查找，从而提高了查找速度，也降低了维护的难度。

Description

TCAM路由表查找方法及TCAM路由表查找装置

技术领域

本发明涉及一种TCAM路由表查找方法，尤其涉及一种以维护为目的对TCAM路由表中的预先保存路由地址进行查找的方法，及实现这种方法的TCAM路由表查找装置。

背景技术

三进制内容可寻址存储器(Ternary Content Addressable Memory，简称TCAM)技术是一种用于提高路由器查表效率的硬件查找技术，TCAM实际上是一种专用于进行查表操作的硬件芯片，它以硬件化的路由表查找和分组转发技术实现对各类数据包的快速分类和路由，性能卓越，可扩充性强，因此被许多高端路由器所采用。

TCAM路由表采用地址单元(entry)格式进行组织，每一个地址单元包括IP位(data)和掩码位(mask)。在建立TCAM路由表时，控制平面软件根据现有的路由表生成算法向地址单元中写入目的IP地址及与该IP地址相对应的掩码，并且每一个地址单元还会与下一跳IP地址相关联。其中，下一跳IP地址是指能够通往目的路由地址的下一个路由器的IP地址。当需要在数据平面对数据包进行路由转发时，根据数据包中携带的目的IP地址在TCAM路由表中查找相应的地址单元，进而得到与该地址单元相关联的下一跳IP地址，将数据包发往该下一跳IP地址，从而完成数据包的路由转发。

根据目的IP地址对TCAM路由表进行查找时，可能会有多个地址单元满足查找条件。例如，如图1所示，假设TCAM路由表中预先保存有四个目的路由地址分别为：1.1.0.0/16，1.1.0.0/18，1.1.0.0/24，1.1.0.0/27。其中，“/”前表示IP地址，“/”后表示相应掩码中1的位数。如果被查找的目的IP地址为1.1.0.0/16，则根据现有查找方法上述目的地址均满足查找条件。现有技术中是按照掩码中1的位数从大到小的顺序进行查找，因此查找到的目的路由地址为1.1.0.0/27，根据该路由地址完成路由转发。现有技术的缺陷在于：当需要在控制平面对TCAM中保存的地址单元进行添加、删除或修改等维护操作时，查找出的路由地址1.1.0.0/27与被查找的路由地址1.1.0.0/16不相同，因此实际上并没有查找到要进行维护路由地址1.1.0.0/16，因此也就无法对其进行维护。

现有技术的解决方案是：除了在TCAM路由表中保存地址单元以外，还需要另设一个维护表用于记录地址单元在TCAM路由表中的存储位置。在进行路由维护时，首先在维护表中查找地址单元在TCAM路由表中的存储位置，进而在TCAM路由表中查找到准确的地址单元，以便对其进行维护。如图2所示，1.1.0.0/16的存储位置为65734，1.1.0.0/18的存储位置为10035，1.1.0.0/24的存储位置为5347，1.1.0.0/27的存储位置为1002。当要查找的路由地址为1.1.0.0/16时，首先在维护表中找到相应地址单元的存储位置为65734，进而在TCAM路由表中找到该地址单元。维护表的组织形式有很多，如哈希表结构或树形结构等。但是，这种维护表需要占用额外的存储空间，并且目的路由地址条数越多占用的存储空间就越大，造成了系统资源的浪费，并且也增加了对TCAM路由表维护的难度。

发明内容

本发明的目的是一种TCAM路由表查找方法，使得不需要另设维护表也可以实现对TCAM路由表中预存的路由地址进行查找进而进行维护的方法，及能够实现这中方法的TCAM路由表查找装置。

为实现上述目的，本发明提供了一种TCAM路由表查找方法，包括：

预先在TCAM路由表地址单元中保存加长IP地址和加长掩码，其中，加长IP地址包括目的IP地址和掩码表示位，加长掩码包括与目的IP地址相应的掩码和与掩码表示位长度相等个数的1；

检测到携带有掩码表示位的加长IP地址后，根据预先设定的指令信息判断是否要进行路由表维护，若是，则根据该加长IP地址在TCAM路由表中查找相应的地址单元。

为实现上述目的，本发明还提供了一种TCAM路由表查找装置，包括：

地址检测模块，用于检测携带有掩码表示位的加长IP地址，根据预先设定的指令信息判断是否要进行路由表维护，并将判断结果发送给查找模块；

路由表模块，用于预存加长IP地址和加长掩码；

查找模块，用于根据来自于地址检测模块的判断结果，对路由表模块进行查找。

通过本发明，由于增加了掩码表示位，因此不需要另设维护表也可以找到要维护的TCAM路由表的地址单元，从而节省了存储空间；并且整个查找过程可以通过硬件一次完成，不需要再通过软件对维护表进行查找，从而提高了查找速度，也降低了维护的难度。

下面通过附图和实施例，对本发明的技术方案做进一步的详细描述。

附图说明

图1为现有技术的TCAM路由表中预存的路由地址数据结构举例示意图；

图2为现有技术的TCAM路由表中预存的路由地址存储位置举例示意图；

图3为本发明TCAM路由表中预存的路由地址数据结构举例示意图；

图4为本发明实施例1所述TCAM路由表查找方法流程图；

图5为本发明实施例2所述TCAM路由表查找方法流程图；

图6为本发明实施例3所述TCAM路由表查找装置的内部结构示意图。

具体实施方式

预先在TCAM路由表中的地址单元中保存加长IP地址和加长掩码，其中，加长IP地址包括目的IP地址和掩码表示位，加长掩码包括与目的地址相应的掩码和与掩码表示位长度相同个数的1。例如，如图3所示，为在TCAM路由表中预先保存的4个路由地址，每个地址单元保存一个路由地址，上一列为地址单元的IP位，包括32位IP地址和6位掩码表示位；下一列为地址单元的掩码位，包括32位掩码和6位掩码表示位长度相应的1。

此处需要说明的是，IP地址不仅限于32位，可以根据现有技术为128位或其他位数。掩码表示位也不仅限于6位，只要与所采用的掩码中1的位数相对应即可。即，如果掩码为128位，则掩码表示位可以为8位，这样，即使该掩码的128位全为1，那么8位的掩码表示位也能够满足需要。另外，如果预先设定本系统中所采用的掩码中1的位数不超过16位，则设置4位的掩码表示位也是可以满足需要的，这样做的好处是可以尽量减少数据处理量，提高系统效率；并且，掩码表示位所能表示的个数也可以比掩码中1的位数多，如针对32位掩码，也可以设置8位掩码表示位，只要将掩码表示位中不需要的位数置0即可，这样做的好处是可以使该掩码表示位的适用范围更广，既可以表示32位掩码中的1位数，又可以表示128位掩码中1的位数。总之掩码表示位的位数可以根据需要进行设置，并不仅限于以上几种可能。以下实施例中，仅以IP地址为32位的情况予以说明，其他位数的IP地址的工作原理相同。

实施例1

本实施例提供了一种对TCAM路由表进行维护时的TCAM路由表查找方法，如图4所示，

步骤101，当需要对TCAM路由表进行维护时，向TCAM芯片中输入要进行查找的加长IP地址，该地址包括IP地址和掩码表示位。加长IP地址的结构与TCAM路由表中预存的加长IP地址的结构相同。并且还要预先设定指令信息，以通知TCAM芯片，以下输入的加长IP地址是为了对路由表进行维护。

步骤102，TCAM检测到加长IP地址后，根据预先设定的指令信息判断是否要进行路由表维护，若是，说明查找的目的是为了对TCAM路由表进行维护，则执行步骤103。

步骤103，根据该加长IP地址在TCAM路由表中查找相应的地址单元，如果查找成功则执行步骤111，否则执行步骤112。具体地，可以先用每一个地址单元中预存的加长掩码对要查找的加长IP地址进行与运算，以屏蔽掉该加长IP地址中的主机地址；然后将与运算后的加长IP地址与该地址单元中预存的加长IP地址进行比较，若相同则说明查找成功；否则对下一地址单元用同样方法进行查找。此处需要说明的是，如果事先规定输入到TCAM芯片中进行查找的加长IP地址中不得包括主机地址，则上述与运算的的步骤可以省略。

步骤111，如果查找到相应的地址单元，则对该地址单元进行编辑。步骤112，如果没有查找到相应的地址单元，则将该加长IP地址保存于空闲地址单元中。具体地，将该加长IP地址保存于空闲地址单元的IP位，将该加长IP地址中携带的掩码表示位所对应的加长掩码保存于空闲地址单元的掩码位。为了保证具有较长的1的位数的掩码保存在TCAM路由表中地址较低的区域内，在保存之前，可以预先根据掩码中1的位数对TCAM路由表进行分区，根据加长掩码中的掩码的1的个数将加长IP地址和加长掩码保存于相应分区的地址单元中。

根据本实施例所述方法，由于增加了掩码表示位，因此不需要另设维护表也可以找到要维护的TCAM路由表的地址单元，从而节省了存储空间；并且整个查找过程可以通过硬件一次完成，不需要再通过软件对维护表进行查找，从而提高了查找速度，也降低了维护的难度。

实施例2

本实施例提供了一种在数据平面对数据包进行路由转发的TCAM路由表查找方法。如图5所示，

预先设定指令信息，以通知TCAM芯片，以下输入的加长IP地址是为了对数据包进行转发。

步骤201，转发设备接收到数据包后，对该数据包中的IP地址进行检测，将检测到的IP地址与全0的掩码表示位组成加长IP地址，发送给TCAM芯片。

步骤202，TCAM检测到加长IP地址后，根据预先设定的指令信息判断是否要进行路由表维护，若不是，说明查找的目的是为了对数据包进行转发，则执行步骤203。

步骤203，设置全局掩码，由全局掩码对TCAM路由表中预存的加长IP地址进行与运算，以屏蔽掉掩码表示位的内容。该全局掩码由与IP地址长度相对应的1和与掩码表示位长度相对应的0组成。具体地，该全局掩码可以由全局掩码寄存器生成。全局掩码寄存器是在现有TCAM中存在的硬件寄存器，用于生成全局掩码，不需要占用其他存储空间，并且读写速度快。

步骤204，根据接收到的加长IP地址在TCAM路由表中查找相应的地址单元，如果查找成功则执行步骤211，否则执行步骤212。具体查找过程中，由预存的加长掩码对接收到的加长IP地址进行与运算，以屏蔽掉该加长IP地址中的主机地址，并根据进行与运算后的加长IP地址查找相应的地址单元。

步骤211，根据查找到的地址单元所对应的下一跳IP地址，对数据包进行转发。

步骤212，路由转发失败，返回错误信息。

通过本实施例所述方法，可以即可以在控制平面实现对TCAM路由表的维护，又可以实现在数据面对数据包进行路由转发，并且不需要另设维护表，节省了存储空间；并且整个查找过程可以通过硬件一次完成，不需要再通过软件对维护表进行查找，从而提高了查找速度，也降低了维护的难度。

实施例3

本实施例提供了一种路由表查找装置40，如图6所示，包括，地址检测模块41，查找模块42，路由表模块43，全局掩码模44，与运算模块45和转发模块46。该装置能够与外部进行通信，各模块之间通信连接，具体连接方式根据现有技术可以有很多，本实施例仅以总线连接方式加以说明。

预先在路由表模块43中的地址单元中保存加长IP地址和加长掩码，其中，加长IP地址包括目的IP地址和掩码表示位，加长掩码包括目的地址相应的掩码和与掩码表示位长度相应的1。

当需要对TCAM路由表进行维护时，路由表查找装置40的工作过程如下：

向路由表查找装置40中输入要进行查找的加长IP地址，该地址包括IP地址和掩码表示位。加长IP地址的结构与TCAM路由表中预存的加长IP地址的结构相同。

地址检测模块41检测到加长IP地址后，根据预先设定的指令信息判断是否要进行路由表维护，若是，说明查找的目的是为了对TCAM路由表进行维护，则将判断结果发送给查找模块42。

查找模块42根据加长IP地址在路由表模块43中查找相应的地址单元，具体地，可以先将每一个地址单元中预存的加长掩码和要查找的加长IP地址发送给与运算模块45进行与运算，以屏蔽掉该加长IP地址中的主机地址；然后将与运算后的加长IP地址与该地址单元中预存的加长IP地址进行比较，若相同则说明查找成功；否则对下一地址单元用同样方法进行查找。此处需要说明的是，如果事先规定输入到路由表查找装置40中进行查找的加长IP地址中不得包括主机地址，则上述与运算的步骤可以省略。

如果查找成功则对该地址单元进行编辑，否则将该加长IP地址保存于路由表模块43的空闲地址单元中。具体地，将该加长IP地址保存于空闲地址单元的IP位，将该加长IP地址中携带的掩码表示位所对应的加长掩码保存于空闲地址单元的掩码位。为了保证具有较长的1的位数的掩码保存在路由表模块43中地址较低的区域内，在保存之前，可以预先根据掩码中1的位数对TCAM路由表进行分区，根据加长掩码中的掩码的1的个数将加长IP地址及加长掩码保存于相应分区的地址单元中。从而完成对路由表的编辑或添加。

当需要通过TCAM路由表对接收到的数据包进行路由转发时，路由表查找装置40的工作过程如下：

路由表查找装置40中的转发模块46接收到数据包后，对该数据包中的IP地址进行检测，将检测到的IP地址与全0的掩码表示位组成加长IP地址，发送给地址检测模块41。地址检测模块41检测到加长IP地址后，根据预先设定的指令信息判断是否要进行路由表维护，若不是，说明查找的目的是为了对数据包进行转发，则将判断结果发送给全局掩码模块44。

全局掩码模块44设置全局掩码，该全局掩码由与IP地址长度相对应的1和与掩码表示位长度相对应的0组成，并将全局掩码发送给与运算模块45。具体地，该全局掩码模块44可以是全局掩码寄存器。全局掩码寄存器是在现有TCAM中存在的硬件寄存器，用于生成全局掩码，不需要占用其他存储空间，并且读写速度快。

与运算模块45通过全局掩码对路由表模块43中预存的加长IP地址进行与运算，以屏蔽掉加长IP地址中的掩码表示位的内容。并将与运算结果发送给查找模块42。

查找模块42接收到与运算结果后，根据转发模块46接收到的加长IP地址在路由表模块43中查找相应的地址单元，具体查找过程中，由预存的加长掩码对接收到的加长IP地址进行与运算，以屏蔽掉该加长IP地址中的主机地址，并根据进行与运算后的加长IP地址查找相应的地址单元。如果查找成功则将查找到的地址单元所对应的下一跳IP地址发送给转发模块46；否则向转发模块46发送错误信息，说明查找失败。

转发模块46根据接收到的下一跳IP地址对数据包进行转发。

根据本实施例所述装置，即可以在数据平面对数据包进行转发，又可以在控制平面对TCAM路由表进行维护。并且由于增加了掩码表示位，因此不需要另设维护表也可以找到要维护的TCAM路由表的地址单元，从而节省了存储空间；并且整个查找过程可以通过硬件一次完成，不需要再通过软件对维护表进行查找，从而提高了查找速度，也降低了维护的难度。

最后所应说明的是，以上实施例仅用以说明本发明的技术方案而非限制，尽管参照较佳实施例对本发明进行了详细说明，本领域的普通技术人员应当理解，可以对本发明的技术方案进行修改或者等同替换，而不脱离本发明技术方案的精神和范围。

Claims

1、一种TCAM路由表查找方法，包括：

2、根据权利要求1所述的TCAM路由表查找方法，其特征在于，查找相应的地址单元还包括：如果没有查找到该地址单元，则将该加长IP地址保存于空闲地址单元中。

3、根据权利要求2所述的TCAM路由表查找方法，其特征在于，所述将该加长IP地址保存于空闲地址单元中包括：将该加长IP地址保存于空闲地址单元的IP位，将该加长IP地址中携带的掩码表示位所对应的加长掩码保存于空闲地址单元的掩码位。

4、根据权利要求3所述的TCAM路由表查找方法，其特征在于，保存于空闲地址单元的掩码位包括：

预先根据加长掩码的掩码中1的个数对TCAM路由表进行分区，根据接收到的加长IP地址所对应的掩码的1的个数将加长IP地址和加长掩码保存于相应分区的地址单元中。

5、根据权利要求1所述的TCAM路由表查找方法，其特征在于，查找相应的地址单元还包括：如果查找到该地址单元，则对该地址单元进行编辑。

6、根据权利要求1所述的TCAM路由表查找方法，其特征在于，所述检测到携带有掩码表示位的加长IP地址之前包括：检测到数据包中的IP地址后，将该IP地址与全0的掩码表示位组成加长IP地址。

7、根据权利要求6所述的TCAM路由表查找方法，其特征在于，所述判断是否要进行路由表维护还包括：如果不是，则，

设置全局掩码，该全局掩码由与IP地址长度相对应的1和与掩码表示位长度相对应的0组成；

由全局掩码对TCAM路由表中预存的加长IP地址进行与运算，以屏蔽掉加长IP地址中的掩码表示位的内容；

根据接收到的加长IP地址查找相应的地址单元。

8、根据权利要求1或7所述的TCAM路由表查找方法，其特征在于，所述查找相应的地址单元包括：

由预存的加长掩码对接收到的加长IP地址进行与运算，以屏蔽掉加长IP地址中的主机地址，根据进行与运算后的加长IP地址查找相应的地址单元。

9、根据权利要求8所述的TCAM路由表查找方法，其特征在于：所述查找相应的地址单元后还包括：根据查找到的地址单元所对应的下一跳IP地址，对数据包进行转发。

10、根据权利要求7所述的TCAM路由表查找方法，其特征在于，所述全局掩码由全局掩码寄存器生成。

11、一种TCAM路由表查找装置，包括：

路由表模块，用于预存加长IP地址和加长掩码；

12、根据权利要求11所述的TCAM路由表查找装置，其特征在于，还包括：

全局掩码模块，用于根据来自于地址检测模块的判断结果设置全局掩码，并将全局掩码发送给与运算模块；

与运算模块，用于根据来自于全局掩码模块的全局掩码对路由表模块中预存的加长IP地址进行与运算，并将与运算结果发送给查找模块；所述查找模块还用于根据来自于与运算模块的与运算结果，对路由表模块进行查找；

转发模块，用于根据查找模块的查找结果对接收到的数据包进行转发。