CN107528782A.PDF

《CN107528782A.PDF》由会员分享，可在线阅读，更多相关《CN107528782A.PDF（10页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号(43)申请公布日(21)申请号 201610442869.0(22)申请日 2016.06.20(71)申请人 中兴通讯股份有限公司地址 518057 广东省深圳市南山区高新技术产业园科技南路中兴通讯大厦(72)发明人 刘丛(74)专利代理机构 北京银龙知识产权代理有限公司 11243代理人 许静安利霞(51)Int.Cl.H04L 12/747(2013.01)H04L 12/743(2013.01)(54)发明名称一种TCAM表项的更新方法、装置及TCAM(57)摘要本发明提供了一种TCAM表项的更新方法、装置及T

2、CAM，其中，更新方法包括：获取TCAM表项中存储的全部存储信息；判断全部存储信息中是否存在与预处理信息相同的存储信息，得到判断结果；根据判断结果，更新TCAM表项。本发明解决了现有技术中TCAM存储有相同的存储信息时造成的资源浪费的问题，有效减少了TCAM的资源占用，在TCAM存储资源有限的情况下，增加了TCAM的处理容量。权利要求书2页 说明书6页 附图1页CN 107528782 A2017.12.29CN 107528782 A1.一种三态内容可寻址存储器TCAM表项的更新方法，其特征在于，包括：获取TCAM表项中存储的全部存储信息；判断所述全部存储信息中是否存在与预处理信息相同的存储

3、信息，得到判断结果；根据所述判断结果，更新所述TCAM表项。2.根据权利要求1所述的更新方法，其特征在于，根据所述判断结果，更新所述TCAM表项的步骤包括：根据所述判断结果，在所述TCAM表项中添加所述预处理信息；或者，根据所述判断结果，删除所述TCAM表项中与所述预处理信息相同的存储信息。3.根据权利要求2所述的更新方法，其特征在于，所述根据所述判断结果，在所述TCAM表项中添加所述预处理信息的步骤包括：当所述判断结果为是时，获取与所述预处理信息相同的存储信息的第一条数，并根据所述第一条数，将所述预处理信息添加至所述TCAM表项中；当所述判断结果为否时，直接将所述预处理信息添加至所述TCAM

4、表项中。4.根据权利要求3所述的更新方法，其特征在于，所述根据所述第一条数，将所述预处理信息添加至所述TCAM表项中的步骤包括：当所述第一条数大于1时，仅保留所述TCAM表项中与所述预处理信息相同的存储信息中的其中一条存储信息，并更新所述第一条数；当所述第一条数为1时，直接更新所述第一条数；其中，更新后的第一条数为更新前的第一条数与所述预处理信息的第二条数的和值。5.根据权利要求2所述的更新方法，其特征在于，所述根据所述判断结果，删除所述TCAM表项中与所述预处理信息相同的存储信息的步骤包括：当所述判断结果为是时，获取与所述预处理信息相同的存储信息的第一条数，并根据所述第一条数，删除所述TCA

5、M表项中与所述预处理信息相同的存储信息。6.根据权利要求5所述的更新方法，其特征在于，所述根据所述第一条数，删除所述TCAM表项中与所述预处理信息相同的存储信息的步骤包括：当所述第一条数大于1时，仅保留所述TCAM表项中与所述预处理信息相同的存储信息中的其中一条存储信息，并更新所述第一条数，其中，更新后的第一条数为更新前的第一条数与所述预处理信息的第二条数的差值；当所述第一条数等于1时，直接删除所述TCAM表项中与所述预处理信息相同的存储信息。7.一种三态内容可寻址存储器TCAM表项的更新装置，其特征在于，包括：获取模块，用于获取TCAM表项中存储的全部存储信息；判断模块，用于判断所述全部存储

6、信息中是否存在与预处理信息相同的存储信息，得到判断结果；更新模块，用于根据所述判断结果，更新所述TCAM表项。8.根据权利要求7所述的更新装置，其特征在于，所述更新模块包括：第一更新单元，用于根据所述判断结果，在所述TCAM表项中添加所述预处理信息；或者，第二更新单元，用于根据所述判断结果，删除所述TCAM表项中与所述预处理信息相同的存储信息。9.根据权利要求8所述的更新装置，其特征在于，所述第一更新单元用于，当所述判断权利要求书1/2 页2CN 107528782 A2结果为是时，获取与所述预处理信息相同的存储信息的第一条数，并根据所述第一条数，将所述预处理信息添加至所述TCAM表项中；当所

7、述判断结果为否时，直接将所述预处理信息添加至所述TCAM表项中。10.根据权利要求9所述的更新装置，其特征在于，所述第一更新单元用于，当所述第一条数大于1时，仅保留所述TCAM表项中与所述预处理信息相同的存储信息中的其中一条存储信息，并更新所述第一条数；当所述第一条数为1时，直接更新所述第一条数；其中，更新后的第一条数为更新前的第一条数与所述预处理信息的第二条数的和值。11.根据权利要求8所述的更新装置，其特征在于，所述第二更新单元用于，当所述判断结果为是时，获取与所述预处理信息相同的存储信息的第一条数，并根据所述第一条数，删除所述TCAM表项中与所述预处理信息相同的存储信息。12.根据权利要

8、求11所述的更新装置，其特征在于，所述第二更新单元用于，当所述第一条数大于1时，仅保留所述TCAM表项中与所述预处理信息相同的存储信息中的其中一条存储信息，并更新所述第一条数，其中，更新后的第一条数为更新前的第一条数与所述预处理信息的第二条数的差值；当所述第一条数等于1时，直接删除所述TCAM表项中与所述预处理信息相同的存储信息。13.一种三态内容可寻址存储器TCAM，其特征在于，TCAM包括如权利要求7至12任一项所述的三态内容可寻址存储器TCAM表项的更新装置。权利要求书2/2 页3CN 107528782 A3一种TCAM表项的更新方法、装置及TCAM技术领域0001本发明涉及通信技术领

9、域，尤其是涉及一种TCAM表项的更新方法、装置及TCAM。背景技术0002在分组传输时网(PTN)以及数据产品设备中，三态内容可寻址存储器(TCAM)作为目前主流的快速查找存储器件，主要用于快速查找访问控制列表(ACL)以及路由等表项。但是由于TCAM成本较高，存储容量通常较小。此外，在对TCAM进行配置时，通常需要和随机存取存储器(RAM)配合进行配置。其中，通常在TCAM中存储根据关键字(Key)和掩码(Mask)计算得到的数据，而在RAM中存储与根据Key和Mask计算得到的数据相关联的值(Value)，然后中央处理器(CPU)根据具体需求，根据不同顺序规则配置TCAM和RAM。0003

10、而目前在配置TCAM时，通常是根据用户数据进行计算得到Key和Mask，然后再对Key和Mask进行计算，得到计算后的数据，最后存储计算后的数据。但是由于相应算法不能保证根据Key和Mask计算得到的数据的最少冗余，因此经常出现根据Key和Mask计算得到的数据重复配置的情况，这对TCAM资源占用产生了较大的浪费。例如：0004根据用户数据1得到的Key1为0 xf0f0，Mask1为0 x00f0，根据Key1和Mask1计算得到的数据1为0 x00f0；0005根据用户数据2得到的Key2为0 x00f0，Mask2为0 x00ff，根据Key2和Mask2计算得到的数据2为0 x00f0

11、；0006根据用户数据1和用户数据2可以看出，虽然根据用户数据得到的Key和Mask不同，但最后根据Key和Mask计算得到的数据是相同的，这就导致在TCAM中存储时，存在相同的数据重复存储的情况，这在TCAM的存储空间较小的情况下，极大的浪费了TCAM的存储空间。0007由上可以看出，现有技术中的TCAM存在资源浪费的问题。发明内容0008为了解决现有技术中TCAM存在的资源浪费的问题，本发明提供一种TCAM表项的更新方法、装置及TCAM。0009为了解决上述技术问题，第一方面，本发明提供了一种TCAM表项的更新方法，包括：0010获取TCAM表项中存储的全部存储信息；0011判断所述全部存

12、储信息中是否存在与预处理信息相同的存储信息，得到判断结果；0012根据所述判断结果，更新所述TCAM表项。0013可选地，根据所述判断结果，更新所述TCAM表项的步骤包括：根据所述判断结果，在所述TCAM表项中添加所述预处理信息；或者，根据所述判断结果，删除所述TCAM表项中与所述预处理信息相同的存储信息。0014可选地，所述根据所述判断结果，在所述TCAM表项中添加所述预处理信息的步骤说明书1/6 页4CN 107528782 A4包括：当所述判断结果为是时，获取与所述预处理信息相同的存储信息的第一条数，并根据所述第一条数，将所述预处理信息添加至所述TCAM表项中；当所述判断结果为否时，直接

13、将所述预处理信息添加至所述TCAM表项中。0015可选地，所述根据所述第一条数，将所述预处理信息添加至所述TCAM表项中的步骤包括：当所述第一条数大于1时，仅保留所述TCAM表项中与所述预处理信息相同的存储信息中的其中一条存储信息，并更新所述第一条数；当所述第一条数为1时，直接更新所述第一条数；其中，更新后的第一条数为更新前的第一条数与所述预处理信息的第二条数的和值。0016可选地，所述根据所述判断结果，删除所述TCAM表项中与所述预处理信息相同的存储信息的步骤包括：当所述判断结果为是时，获取与所述预处理信息相同的存储信息的第一条数，并根据所述第一条数，删除所述TCAM表项中与所述预处理信息相

14、同的存储信息。0017可选地，所述根据所述第一条数，删除所述TCAM表项中与所述预处理信息相同的存储信息的步骤包括：当所述第一条数大于1时，仅保留所述TCAM表项中与所述预处理信息相同的存储信息中的其中一条存储信息，并更新所述第一条数，其中，更新后的第一条数为更新前的第一条数与所述预处理信息的第二条数的差值；当所述第一条数等于1时，直接删除所述TCAM表项中与所述预处理信息相同的存储信息。0018第二方面，本发明还提供了一种三态内容可寻址存储器TCAM表项的更新装置，包括：0019获取模块，用于获取TCAM表项中存储的全部存储信息；0020判断模块，用于判断所述全部存储信息中是否存在与预处理信

15、息相同的存储信息，得到判断结果；0021更新模块，用于根据所述判断结果，更新所述TCAM表项。0022可选地，所述更新模块包括：第一更新单元，用于根据所述判断结果，在所述TCAM表项中添加所述预处理信息；或者，第二更新单元，用于根据所述判断结果，删除所述TCAM表项中与所述预处理信息相同的存储信息。0023可选地，所述第一更新单元用于，当所述判断结果为是时，获取与所述预处理信息相同的存储信息的第一条数，并根据所述第一条数，将所述预处理信息添加至所述TCAM表项中；当所述判断结果为否时，直接将所述预处理信息添加至所述TCAM表项中。0024可选地，所述第一更新单元用于，当所述第一条数大于1时，仅

16、保留所述TCAM表项中与所述预处理信息相同的存储信息中的其中一条存储信息，并更新所述第一条数；当所述第一条数为1时，直接更新所述第一条数；其中，更新后的第一条数为更新前的第一条数与所述预处理信息的第二条数的和值。0025可选地，所述第二更新单元用于，当所述判断结果为是时，获取与所述预处理信息相同的存储信息的第一条数，并根据所述第一条数，删除所述TCAM表项中与所述预处理信息相同的存储信息。0026可选地，所述第二更新单元用于，当所述第一条数大于1时，仅保留所述TCAM表项中与所述预处理信息相同的存储信息中的其中一条存储信息，并更新所述第一条数，其中，更新后的第一条数为更新前的第一条数与所述预处

17、理信息的第二条数的差值；当所述第一条数等于1时，直接删除所述TCAM表项中与所述预处理信息相同的存储信息。说明书2/6 页5CN 107528782 A50027第三方面，本发明还提供了一种三态内容可寻址存储器TCAM，包括上述提供的三态内容可寻址存储器TCAM表项的更新装置。0028本发明的有益效果是：0029本发明提供的TCAM表项的更新方法，通过获取TCAM表项中存储的全部存储信息，然后判断全部存储信息中是否存在与预处理信息相同的存储信息，得到判断结果，最后根据判断结果，更新TCAM表项，解决了现有技术中TCAM存储有相同的存储信息时造成的资源浪费的问题，有效减少了TCAM的资源占用，在

18、TCAM存储资源有限的情况下，增加了TCAM的处理容量。附图说明0030图1表示本发明的第一实施例中TCAM表项的更新方法的步骤流程图；0031图2表示本发明的第四实施例中TCAM表项的更新装置的结构框图。具体实施方式0032下面将参照附图更详细地描述本公开的示例性实施例。虽然附图中显示了本公开的示例性实施例，然而应当理解，可以以各种形式实现本公开而不应被这里阐述的实施例所限制。相反，提供这些实施例是为了能够更透彻地理解本公开，并且能够将本公开的范围完整的传达给本领域的技术人员。0033第一实施例：0034如图1所示，为本发明的第一实施例中TCAM表项的更新方法的步骤流程图，包括如下步骤：00

19、35步骤101，获取TCAM表项中存储的全部存储信息。0036在本步骤中，具体的，TCAM表项中存储的存储信息可以为根据Key和Mask计算得到的数据。0037步骤102，判断全部存储信息中是否存在与预处理信息相同的存储信息，得到判断结果。0038在本步骤中，具体的，在需要更新TCAM表项时，即需要在TCAM表项中添加存储信息或者是删除存储信息时，可以在获取到TCAM表项中存储的全部存储信息之后，判断全部存储信息中是否存在与预处理信息相同的存储信息，然后得到判断结果。0039步骤103，根据判断结果，更新TCAM表项。0040在本步骤中，具体的，在得到TCAM表项中的全部存储信息中是否存在与预

20、处理信息相同的存储信息的判断结果之后，可以根据判断结果更新TCAM表项。此外，更新TCAM表项可以包括根据判断结果，在TCAM表项中添加预处理信息，或者是根据判断结果，删除TCAM表项中与预处理信息相同的存储信息。0041这样，本实施例通过先获取TCAM表项中存储的全部存储信息，然后判断全部存储信息中是否存在与预处理信息相同的存储信息，得到判断结果，最后根据判断结果，更新TCAM表项，解决了现有技术中TCAM存储有相同的存储信息时造成的资源浪费的问题，有效减少了TCAM的资源占用，在TCAM存储资源有限的情况下，增加了TCAM的处理容量。0042此外，可选的，在根据判断结果，更新TCAM表项时

21、，可以参见下述第二实施例和第说明书3/6 页6CN 107528782 A6三实施例。具体的，第二实施例为根据判断结果，在TCAM表项中添加预处理信息的实施例，第三实施例为根据判断结果，删除TCAM表项中与预处理信息相同的存储信息的实施例。0043第二实施例：0044在本实施例中，在根据判断结果，在TCAM表项中添加预处理信息时，当判断结果为是时，即当判断结果指示全部存储信息中存在与预处理信息相同的存储信息时，可以获取与预处理信息相同的存储信息的第一条数，然后根据第一条数，将预处理信息添加至TCAM表项中。具体实施方式可以如下：0045具体的，当获取到的与预处理信息相同的存储信息的第一条数大于

22、1时，为了减少TCAM表项中相同的存储信息占用不同的存储资源，可以将多余1条与预处理信息相同的存储信息删除，即仅保留TCAM表项中与预处理信息相同的存储信息中的其中一条存储信息，然后更新第一条数，此时更新后的第一条数为更新前的第一条数与预处理信息的第二条数的和值。在此对此举例进行说明。0046例如，TCAM表项中存储的为根据Key和Mask计算得到的数据。原始数据Key1为0 xf0f0，Mask1为0 x00f0，根据Key1和Mask1计算得到的数据1为0 x00f0；原始数据Key2为0 x00f0，Mask2为0 x00ff，根据Key2和Mask2计算得到的数据2为0 x00f0。数

23、据1和数据2存储在TCAM表项中，且此时预处理信息同样为0 x00f0。0047此时由于数据1和数据2为相同的存储信息，且预处理信息同样与数据1和数据2相同，此时若直接将预处理信息添加至TCAM表项中，则TCAM中相同的存储信息会占用3份存储资源，这在TCAM存储空间较小时，严重浪费了TCAM的存储资源。此时为了提高TCAM存储资源的利用率，可以统计数据1和数据2的条数，即记录条数为2，然后将相同的数据删除，即可以删除数据1或者数据2，仅保留数据1和数据2中的其中1条数据，这样，可以释放TCAM中被重复占用的存储资源。此外，由于预处理信息与数据1和数据2相同，则可以不将预处理信息直接添加至TC

24、AM表项中，而是在统计的条数上增加预处理信息的条数，即最后统计的条数为与预处理信息相同的存储信息的条数与预处理信息的条数的和值，即最后统计的条数为3。这样即在TCAM表项中添加了预处理信息，又进一步避免了TCAM中相同存储信息重复占用存储资源的情况的发生。0048此外，当判断结果为否时，即当判断结果指示全部存储信息中不存在与预处理信息相同的存储信息时，可以直接将预处理信息添加至TCAM表项中。0049另外，具体的，在存储预处理信息时，可以采用红黑树进行存储。并且，在更新完TCAM表项时，还可以根据LPM路由查找算法，调整存储信息在TCAM表项中的位置。0050这样，本实施例在TCAM表项中添加

25、存储信息时，可以获取与预处理信息相同的存储信息的第一条数，且当TCAM表项中与预处理信息相同的存储信息的第一条数大于1时，仅保留与预处理信息相同的存储信息中的其中一条存储信息，然后记录更新后的第一条数为与预处理信息相同的存储信息的第一条数与预处理信息的条数的和值，当TCAM表项中与预处理信息相同的存储信息的第一条数等于1时，则直接将预处理信息添加至TCAM表项中。这样，最大限度了保证了TCAM表项中存储的存储信息的相异性，即最大程度的利用了TCAM表项的存储资源，有效减少了TCAM存储资源的占用。0051第三实施例：0052在本实施例中，在根据判断结果，删除TCAM表项中与处理信息相同的存储信

26、息时，说明书4/6 页7CN 107528782 A7在判断全部存储信息中是否存在与预处理信息相同的存储信息，得到的判断结果中，当得到的判断结果指示全部存储信息中存在与预处理信息相同的存储信息时，可以获取与预处理信息相同的存储信息的第一条数，然后根据第一条数，删除TCAM表项中与处理信息相同的存储信息。0053具体的，当与预处理信息相同的存储信息的第一条数大于1时，为了减少TCAM表项中相同的存储信息占用不同的存储资源，可以将多余1条与预处理信息相同的存储信息删除，即仅保留TCAM表项中与预处理信息相同的存储信息中的其中一条存储信息，然后更新第一条数，此时，更新后的第一条数为更新前的第一条数与

27、预处理信息的第二条数的差值。在此对此举例进行说明。0054例如，TCAM表项中存储的为根据Key和Mask计算得到的数据。数据1、数据2和数据3均为0 x00ff，且数据1、数据2和数据3存储在TCAM表项中，预处理信息与数据1相同。0055在删除预处理信息时，由于数据1、数据2和数据3为相同的存储信息，若此时直接将与预处理信息相同的数据1删除，则TCAM中同样存在相同的数据2和数据3，即同样存在相同的存储信息占用不同的存储资源的问题，这在TCAM存储空间较小时，严重浪费了TCAM的存储资源。此时为了提高TCAM存储资源的利用率，可以统计数据1、数据2和数据3的条数，即记录条数为3，然后将相同

28、的数据删除，即可以删除数据1和数据2，仅保留数据3，这样，可以释放TCAM中被重复占用的存储资源。此外，由于预处理信息与数据1相同，则可以更新与预处理信息相同的存储信息的条数，即最后统计的条数为与预处理信息相同的存储信息的条数与预处理信息的条数的差值，即最后统计的条数为2，从而实现删除与预处理信息相同的存储信息的目的。0056此外，当与预处理信息相同的存储信息的第一条数等于1时，可以直接删除TCAM表项中与预处理信息相同的存储信息。0057在本实施例中，在删除TCAM中与预处理信息相同的存储信息时，可以获取与预处理信息相同的存储信息的第一条数，然后当TCAM表项中与预处理信息相同的存储信息的第

29、一条数大于1时，仅保留与预处理信息相同的存储信息中的其中一条存储信息，然后记录更新后的第一条数为与预处理信息相同的存储信息的第一条数与预处理信息的条数的差值，当TCAM表项中与预处理信息相同的存储信息的第一条数等于1时，则直接删除TCAM表项中与预处理信息相同的存储信息。这样，在删除TCAM表项中的存储信息时，也能够保证TCAM表项中存储的存储信息的相异性，解决了现有技术中TCAM表项中存在相同的存储信息时出现的存储资源浪费的问题，有效减少了TCAM存储资源的占用。0058第四实施例：0059如图2所示，为本发明的第四实施例中TCAM表项的更新装置的结构框图。该更新装置包括：0060获取模块2

30、01，用于获取TCAM表项中存储的全部存储信息；0061判断模块202，用于判断全部存储信息中是否存在与预处理信息相同的存储信息，得到判断结果；0062更新模块203，用于根据判断结果，更新TCAM表项。0063可选地，更新模块203包括：第一更新单元，用于根据判断结果，在TCAM表项中添加预处理信息；或者，第二更新单元，用于根据判断结果，删除TCAM表项中与预处理信息相同说明书5/6 页8CN 107528782 A8的存储信息。0064可选地，第一更新单元用于，当判断结果为是时，获取与预处理信息相同的存储信息的第一条数，并根据第一条数，将预处理信息添加至TCAM表项中；当判断结果为否时，直

31、接将预处理信息添加至TCAM表项中。0065可选地，第一更新单元用于，当第一条数大于1时，仅保留TCAM表项中与预处理信息相同的存储信息中的其中一条存储信息，并更新第一条数；当第一条数为1时，直接更新第一条数；其中，更新后的第一条数为更新前的第一条数与预处理信息的第二条数的和值。0066可选地，第二更新单元用于，当判断结果为是时，获取与预处理信息相同的存储信息的第一条数，并根据第一条数，删除TCAM表项中与预处理信息相同的存储信息。0067可选地，第二更新单元用于，当第一条数大于1时，仅保留TCAM表项中与预处理信息相同的存储信息中的其中一条存储信息，并更新第一条数，其中，更新后的第一条数为更

32、新前的第一条数与预处理信息的第二条数的差值；当第一条数等于1时，直接删除TCAM表项中与预处理信息相同的存储信息。0068这样，本实施例通过获取TCAM表项中存储的全部存储信息，然后判断全部存储信息中是否存在与预处理信息相同的存储信息，得到判断结果，最后根据判断结果，更新TCAM表项，解决了现有技术中TCAM存储有相同的存储信息时造成的资源浪费的问题，有效减少了TCAM的资源占用，在TCAM存储资源有限的情况下，增加了TCAM的处理容量。0069第五实施例：0070在本实施例中，还提供了一种TCAM，该TCAM包括第四实施例中提供的TCAM的更新装置。0071在此需要说明的是，TCAM能够实现前述实施例中TCAM的更新装置能够实现的各个过程，为避免重复，这里不再赘述。0072以上所述的是本发明的优选实施方式，应当指出对于本技术领域的普通人员来说，在不脱离本发明所述的原理前提下还可以作出若干改进和润饰，这些改进和润饰也在本发明的保护范围内。说明书6/6 页9CN 107528782 A9图1图2说明书附图1/1 页10CN 107528782 A10