[go: up one dir, main page]

WO2016101439A1 - 三态内容寻址存储器tcam空间的处理方法及装置 - Google Patents

三态内容寻址存储器tcam空间的处理方法及装置 Download PDF

Info

Publication number
WO2016101439A1
WO2016101439A1 PCT/CN2015/076097 CN2015076097W WO2016101439A1 WO 2016101439 A1 WO2016101439 A1 WO 2016101439A1 CN 2015076097 W CN2015076097 W CN 2015076097W WO 2016101439 A1 WO2016101439 A1 WO 2016101439A1
Authority
WO
WIPO (PCT)
Prior art keywords
service
address
tcam
entry
write
Prior art date
Application number
PCT/CN2015/076097
Other languages
English (en)
French (fr)
Inventor
姜海明
朱延灵
Original Assignee
中兴通讯股份有限公司
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 中兴通讯股份有限公司 filed Critical 中兴通讯股份有限公司
Publication of WO2016101439A1 publication Critical patent/WO2016101439A1/zh

Links

Images

Definitions

  • the present invention relates to the field of communications, and in particular to a method and apparatus for processing a TCAM space of a three-state content addressed memory.
  • ASICs Application Specific Integrated Circuits
  • NPs Network Processors
  • SRAM Random Access Memory
  • TCAM ternary content addressable memory
  • Synchronous Dynamic Random Access Memory Synchronous Dynamic Random Access Memory
  • the three-state content-addressable memory TCAM is mainly used for quickly searching for an access control list (ACL), a route, and the like.
  • the main feature of TCAM is fast parallel search.
  • the application on the network processor is usually that the microcode composes a key value KEY from the message extraction information, and sends a search command to the TCAM through the NP TCAM controller, and processes the message according to the result. .
  • TCAM is characterized by high cost, high power consumption and limited capacity. The advantages are fast search, fixed delay, longest prefix matching and multi-region matching. In order to make full use of the valuable TCAM space, TCAM generally adopts multi-table distinguishing technology on hardware.
  • a TCAM is divided into blocks of several sizes. The KEY sent by the microcode is searched in parallel in multiple blocks at the same time, and the key value can be sent at one time, and more returns. Check the results of the table.
  • TCAM TCAM
  • IPV4 forwarding port ACL
  • QOS protocol protection
  • NAT port mirroring
  • IPSEC encryption IPSEC encryption
  • the TCAM is used to search for multiple services by using multiple TCAM cascades. This method sacrifices the forwarding performance of the TCAM and requires multiple lookups. Currently, no effective solution has been proposed.
  • the main purpose of the present invention is to provide a method and a device for processing a TCAM space of a three-state content-addressable memory, so as to at least solve the problem of using a multi-chip TCAM cascading method to implement TCAM searching for multiple services in the related art.
  • the forwarding performance requires multiple lookups.
  • a method for processing a TCAM space of a tri-state content-addressable memory comprising: setting a first service and a second service in a same storage block block of a TCAM, wherein the first service Having mutual exclusion or priority with the second service; according to the mutual exclusion or priority, the first service and the second service are written in the block according to different address directions Table processing.
  • Performing the table write process includes: performing a table processing on the first service from a low address to a high address direction, and performing a table processing on the second service from a high address to a low address direction, or performing the second service
  • the table processing is performed from the low address to the high address direction, and the first service is written into the table from the high address to the low address direction.
  • the first service and the second service are performed in the block according to different address directions.
  • the write table processing includes: when the service priority of the first service is higher than the service of the second service, performing the table processing on the first service from the low address to the high address direction, and performing the second process The service is sent from the high address to the low address direction; or when the service priority of the first service is lower than the service of the second service, the second service is performed from the high address to the low address.
  • Write table processing and write the first service from the low address to the high address direction.
  • the method further includes: determining, when the write table address of the first service is coincident with the write table address of the second service, the TCAM occupied by the first service or the second service Is there space in the space? a free space; when the determination result is YES, the entry of the first service or the second service is added according to the free space.
  • an entry of a service includes: writing an entry to be added by the first service to the first free space; adding an entry to the entry of the first service, and determining that the second service is occupied by the second service
  • adding the entry of the first service according to the free space includes: compressing a second free space in a TCAM space occupied by the second service, and transferring the second free space Between the boundary write table address of the first service and the boundary write table address of the second service; according to the direction of the first service write table, write an entry that needs to be added by the first service to the The next address of the boundary write table address.
  • the first space is added according to the free space.
  • the entry of the second service includes: writing an entry to be added by the second service to the third free space; adding the entry to the entry of the second service, and determining that the first service is occupied by the first service
  • adding the entry of the second service according to the free space includes: compressing a third free space in the TCAM space occupied by the second service, and transferring the third free space Between the boundary write table address of the first service and the boundary write table address of the second service; and in the second service write table direction, the entry to be added by the second service is written to the The next address of the boundary write table address.
  • a processing apparatus for a TCAM space of a tri-state content addressed memory comprising: a setting module configured to set a first service and a second service in a same block block of a TCAM, wherein a mutual exclusion or priority between the first service and the second service; the write table module is configured to: the first service and the second service according to the mutual exclusion or priority The table processing is performed in the block according to different address directions.
  • the write table module when there is mutual exclusion between the service of the first service and the second service, includes: a first write table unit, configured to set the first service from Writing a table to the high address direction, and writing the second service from the high address to the low address direction, or the second write table unit, setting the second service from the low address to the high address
  • the address direction performs a write table process, and the first service is written into the table from a high address to a low address direction.
  • the write table module when there is a priority between the service of the first service and the second service, the write table module further includes: a third write table unit, configured to be in the first service When the service priority is higher than the service of the second service, the first service is written from the low address to the high address direction, and the second The service performs a table write process from the high address to the low address direction; or the fourth write table unit is configured to set the second service when the service priority of the first service is lower than the service of the second service The table processing is performed from the high address to the low address direction, and the first service is written into the table from the low address to the high address direction.
  • a third write table unit configured to be in the first service When the service priority is higher than the service of the second service, the first service is written from the low address to the high address direction, and the second The service performs a table write process from the high address to the low address direction
  • the fourth write table unit is configured to set the second service when the service priority of the first service is lower than the service of the second service
  • the apparatus further includes: a determining module, configured to determine, when the write table address of the first service coincides with a write table address of the second service, the first service or the first Whether there is a free space in the TCAM space occupied by the second service; the adding module is configured to add the entry of the first service or the second service according to the free space when the determination result is yes.
  • the first service and the second service are set in the storage block block in the TCAM, wherein the service can be two services of the same type, or two types of services of different types, and the first service and the second service There is mutual exclusion or priority between services; according to the mutual exclusion or priority of the first service and the second service, the first service and the second service are written in different ways in the block,
  • the multi-chip TCAM cascading method is used in the related art to implement the TCAM to search for multiple services, there is a problem of sacrificing the forwarding performance of the TCAM, and the problem of multiple table lookups is required, thereby achieving the performance of the TCAM without sacrificing the forwarding performance.
  • FIG. 1 is a flow chart of a method for processing a TCAM space of a tri-state content addressed memory according to an embodiment of the present invention
  • FIG. 2 is a block diagram showing the structure of a processing apparatus for a TCAM space of a tri-state content address memory according to an embodiment of the present invention
  • FIG. 3 is a block diagram of an optional structure of a processing device for a TCAM space of a tri-state content addressable memory according to an embodiment of the present invention
  • FIG. 4 is a block diagram 2 of an optional structure of a processing device for a TCAM space of a tri-state content addressable memory according to an embodiment of the present invention
  • FIG. 5 is a block diagram 3 of an optional structure of a processing device for a TCAM space of a tri-state content-addressable memory according to an embodiment of the present invention
  • FIG. 6 is a schematic diagram of block parallel search and service addition according to the related art
  • FIG. 7 is a schematic diagram of service addition of a tri-state content addressed memory TCAM space in accordance with an alternative embodiment of the present invention.
  • FIG. 8 is a schematic diagram of a table management manner of a TCAM space of a tri-state content-addressable memory according to an alternative embodiment of the present invention.
  • FIG. 9 is a flow chart of a TCAM add entry method in accordance with an alternate embodiment of the present invention.
  • FIG. 1 is a flowchart of a method for processing a TCAM space of a tri-state content address memory according to an embodiment of the present invention. As shown in FIG. Includes the following steps:
  • Step S102 setting the first service and the second service in the same storage block block of the TCAM
  • Step S104 According to the mutual exclusion or priority, the first service and the second service are written in the block according to different address directions.
  • the first service and the second service are set in the storage block block in the TCAM, where the service can be two services of the same type, or two types of services of different types, and the first service and the first service
  • the second service has mutual exclusion or priority; according to the mutual exclusion or priority of the first service and the second service, the first service and the second service are written in different ways in the block.
  • the first service and the second service are written in the block according to different address directions.
  • the way can be achieved by:
  • Manner 1 Write the first service from the low address to the high address direction, and write the second service from the high address to the low address direction;
  • Manner 2 Write the second service from the low address to the high address direction, and write the first service from the high address to the low address direction.
  • the first service and the second service are written in the block according to different address directions.
  • the method can be implemented as follows:
  • Manner 1 When the service priority of the first service is higher than that of the second service, the first service is written from the low address to the high address, and the second service is written from the high address to the low address. Table processing; or,
  • a and B respectively represent the first service and the second service.
  • the service mutual exclusion means that the A and B services are not configured at the same time, or the same message cannot simultaneously hit the A and B TCAMs. entry.
  • protocol protection and IPSEC encryption protocol protection is to match the protocol packet for priority promotion or to the CPU, and IPSEC encryption is not required for protocol packets.
  • Such protocol protection and IPSEC services are mutually exclusive.
  • the service priority relationship means that the A and B services have different priority relationships.
  • a and B may be configured at the same time.
  • the priority of the A service is higher than that of the B service.
  • PORT ACL and QOS PORT ACL is generally used to filter certain packets
  • QOS is used to implement priority modification of packets
  • PORT ACL has higher priority than QOS.
  • the method in this embodiment may further include:
  • Step S106 determining whether there is a free space in the TCAM space occupied by the first service or the second service when the write table address of the first service overlaps with the write table address of the second service;
  • Step S108 When the determination result is YES, the entry of the first service or the second service is added according to the free space.
  • the value of the write table address of the first service and the write address of the second service in the optional embodiment of the embodiment are worth: the first service and the second service are written in different directions, such as the first service. According to the write table processing from the low address to the high address direction, the second service performs the write table processing from the high address to the low address direction, and the two write the table in the same block, and finally the highest address and the second address of the first service. The lowest address of the business coincides.
  • adding an entry of the first service or the second service according to the free space may be implemented by:
  • the entry of the first service according to the free space includes: an entry to be added by the first service Write to the first free space;
  • adding the entry of the first service according to the free space includes: compressing the TCAM space occupied by the second service The second free space transfers the second free space to the boundary write table address of the first service and the boundary write table address of the second service; according to the direction of the first service write table, the entry to be added by the first service is written Enter the next address of the boundary write table address.
  • the entry of the second service according to the free space includes: an entry to be added by the second service Write to the third free space;
  • adding the entry of the second service according to the free space includes: compressing the TCAM space occupied by the second service The third free space, the third free space is transferred between the boundary write table address of the first service and the boundary write table address of the second service; according to the direction of the second service write table, the entry to be added by the second service is written Enter the next address of the boundary write table address.
  • a processing device for the TCAM space of the three-state content-addressable memory is provided, and the device is used to implement the above-mentioned embodiments and optional embodiments, and details are not described herein.
  • the term “module” "unit” may implement a combination of software and/or hardware of a predetermined function.
  • the described apparatus is preferably implemented in software, but hardware, or a combination of software and hardware, is also possible and contemplated.
  • the apparatus includes: a setting module 22 configured to set a first service and a second service in a TCAM.
  • the write table module 24 is coupled with the setting module 22, and is configured to follow the first service and the second service in the block. Write table processing in different address directions.
  • the write table module 24 includes: a first write table unit 32 configured to perform a write table process on the first service from a low address to a high address direction, and write a second service from a high address to a low address direction,
  • the second write table unit 34 is configured to perform a write table process on the second service from the low address to the high address direction, and write the first service from the high address to the low address direction.
  • write The table module 24 further includes: a third write table unit 42 configured to write the first service from the low address to the high address direction when the service priority of the first service is higher than the service of the second service, and The second service performs a write table process from a high address to a low address direction; the fourth write table unit 44 is configured to set the second service from a high address to a low when the service priority of the first service is lower than the service of the second service.
  • the address direction performs table write processing, and the first service is written to the table from the low address to the high address direction.
  • the device further includes: a determining module 52 coupled to the write table module 24, configured to be When the write table address of the first service coincides with the write address of the second service, it is determined whether there is a free space in the TCAM space occupied by the first service or the second service; the adding module 54 is coupled with the determining module 52, and is set to determine When the result is YES, the entry of the first service or the second service is added according to the free space.
  • the adding module 54 is further configured to: when the added entry is an entry of the first service, and the first free space exists in the TCAM space occupied by the first service, the first service needs to be added.
  • the entry is written in the first free space; or, when the added entry is the entry of the first service, and the result of the determination is that the second free space exists in the TCAM space occupied by the second service, the TCAM of the second service is compressed.
  • a second free space in the space transferring the second free space to the boundary write table address of the first service and the edge of the second service Between the write table addresses; according to the direction of the first service write table, the entry that needs to be added by the first service is written to the next address of the boundary write table address.
  • the above-mentioned adding module 54 uses the first service item as an example to specifically add an entry as follows. Similarly, when the added item is the second service, the adding module 54 operates similarly to the operation of adding the first service item. Specifically, the The addition entry 54 can also be used to write the entry that the second service needs to be added when the added entry is the entry of the second service and the third free space exists in the TCAM space occupied by the second service.
  • the third free space is transferred between the boundary write table address of the first service and the boundary write table address of the second service; according to the direction of the second service write table, the entry to be added by the second service is written to the boundary write The next address of the table address.
  • the optional embodiment puts different services in one block; the two services A and B in the same block have service mutual exclusion or priority relationship; A and B in the same block are written in different directions. table.
  • the service mutual exclusion means that the A and B services are not configured at the same time, or the same message cannot simultaneously hit the A and B TCAM entries.
  • protocol protection and IPSEC encryption protocol protection is to match the protocol packet for priority promotion or to the CPU, and IPSEC encryption is not required for protocol packets.
  • IPSEC services are mutually exclusive.
  • the service priority relationship means that the A and B services have different priority relationships.
  • a and B may be configured at the same time.
  • the priority of the A service is higher than that of the B service.
  • PORT ACL and QOS PORT ACL is generally used to filter certain packets
  • QOS is used to implement priority modification of packets
  • PORT ACL has higher priority than QOS.
  • the A/B service in the same block, one of A and B writes the table from the low address to the high address direction; the other writes the table from the high address to the low address direction.
  • the A/B services in the same block have different priorities, for example, the A service priority is greater than the B service. Since the TCAM preferentially returns an entry with a low address match hit, the A service writes the table from the low address to the high address direction; the B service writes from the high address to the low address direction. In this way, even if the tcam entries of the A service and the B service are hit, the high priority service is returned preferentially.
  • the forwarding plane in the case of a limited number of table lookups, more service lookups are implemented as much as possible, and in the optimal case, the TCAM utilization rate is doubled.
  • NL11K has four block hardware search engines. In the related art, only four service search can be performed at a time. With this alternative embodiment, up to eight services can be searched in parallel.
  • the service A and the service B in the same block can share the TCAM space, which greatly improves the space utilization of the TCAM.
  • FIG. 6 is a schematic diagram of block parallel search and service addition according to the related art. As shown in FIG. 6 , each block stores a service, which is A1/A2/A3/A4, and each service writes according to a low address to a high address direction. table. For the forwarding plane, the results of the lookup of the four services A1/A2/A3/A4 are returned at one time.
  • A1/A2/A3/A4 the results of the lookup of the four services A1/A2/A3/A4 are returned at one time.
  • FIG. 7 is a schematic diagram of service addition of a TCAM space of a tri-state content-addressable memory according to an alternative embodiment of the present invention.
  • two services are stored in each block, and mutually exclusive or different priorities exist between services.
  • A1/B1 services are stored.
  • A1 writes the table to the high address direction according to the low address
  • B1 writes the table to the low address direction according to the high address.
  • the forwarding face lookup table returns the matching entries in A1 or B1 to achieve simultaneous lookup of the two services.
  • the optional embodiment can also enable the services A and B to share the block space and utilize the TCAM hardware resources to a great extent.
  • the port stores both the port ACL and the QoS ACL. If the total number of blocks is 64K, the port ACL and the QoS ACL can support up to 64K. In the user application, a very small number of QoS ACL entries may be configured, so that the space allocated by the port ACL can be close to 64K. According to the traditional practice, the space of Port ACL and Qos ACL must be statically allocated, and space sharing cannot be achieved. TCAM resources are very wasteful.
  • FIG. 8 is a schematic diagram of a table management manner of a TCAM space of a tri-state content-addressable memory according to an alternative embodiment of the present invention.
  • a hole exists in the TCAM that is, an idle entry, as shown in FIG. 8 .
  • the middle 1 is shown by the dotted line. Therefore, the addition of A/B services in the same block needs to consider the space management problem and solve the Block "false full" phenomenon, as shown in Figure 2 and Figure 2.
  • More general is the ordered list management algorithm, which is to create a linked list management tcam idle entry address.
  • the TCAM management algorithm is not within the scope of this patent and does not belong to the point of this patent.
  • the TCAM resource management method for two services in the same block based on the algorithm will be described later.
  • the resource management method for two services in the same block based on other algorithms is similar.
  • the A/B service is stored in the block, and the table is written in different directions.
  • the total Block size is MAX.
  • the corresponding ordered list resource management direction of the service A/B is different, that is, the corresponding ordered list of the service A returns the lowest address idle entry of the service A; the corresponding ordered list of the service B returns the highest address idle entry of the service B. In this way, when service A is added, it is added from the low address to the high address, and service B is added from the high address to the low address.
  • the free space (“hole”) is indicated by a dashed line in FIG.
  • the highest address of service A and the lowest address of service B are respectively recorded by a boundary address Ta and Tb, and Ta and Tb are two variables for solving the phenomenon of "false full" in the two service additions.
  • services A and B allocate address spaces from their respective resource pools.
  • the deleted entries are released to their respective resource pools.
  • the entry is the address in the first node of the ordered list of the service A.
  • the entry node is returned to the corresponding position of the ordered list of the service A.
  • FIG. 9 is a flowchart of a TCAM adding entry method according to an alternative embodiment of the present invention. As shown in FIG. 9, the method includes the following steps:
  • Step S902 start;
  • Step S904 Whether the A service has a hole
  • Step S906 determining whether Ta+Tb is less than MAX, if yes, the entry is added at the Ta+1 position, and updating the value of Ta, proceeds to step S908; otherwise, proceeds to step S912;
  • Step S908 determining whether the service B can be compressed
  • step S910 it is determined whether there is a "hole” in the B space, that is, whether the address in the free resource pool of B is greater than Tb, if yes, the proof can be compressed, and the process proceeds to step S910; otherwise, the entire TCAM is not "empty", and the process proceeds to step S916. ;
  • Step S910 B service space compression
  • the physical address of the valid TCAM entry in the B service is discontinuous, the B service space is compressed, the valid entries are moved, the physical addresses are consecutive, and the original order is stored in the high address part of the block.
  • Tb is updated.
  • Ta+Tb ⁇ MAX that is, service B has moved the "void" in the idle resource pool to between Ta and Tb, and service A has space to write the table, and the entry to be added to the A service. Stored in the Ta+1 position, proceeds to step S912;
  • Step S912 A service write table
  • Step S914 the writing table is successful and ends
  • Step S916 The table is full, the writing table fails, and the table ends.
  • the management of two services based on the general ordered list management algorithm is simply extended on the basis of the general algorithm, and the two service A/Bs create separate resource management instances for resource management, and add a boundary.
  • the variable of the address handles the problem of "fake full”. Therefore, the TCAM management algorithm based on the patented method only needs to be simply extended on the basis of the original general algorithm, and the TCAM space based on the patented method is easy to manage.
  • the logical relationship between the services is analyzed, and different services are put into the same hardware block space, and then TCAM management is performed by using a method similar to “up and down squeezing”; In terms of the number of times, it is possible to implement more types of service search within a limited number of table lookups.
  • TCAM management is performed by using a method similar to “up and down squeezing”; In terms of the number of times, it is possible to implement more types of service search within a limited number of table lookups.
  • multiple services share the same address space to avoid static allocation, which can greatly improve the space of TCAM resources. Utilization; in terms of table management, it only needs to be simply extended on the basis of existing algorithms, and management is convenient.
  • the first service and the second service are set in the storage block block in the TCAM, where the service can be two services of the same type or two types of services of different types.
  • the mutual exclusion or priority exists between the first service and the second service; according to the mutual exclusion or priority of the first service and the second service, the first service and the second service are in different places in the block.
  • the method of writing table processing solves the problem that multi-chip TCAM cascade is used in the related technology to realize TCAM to check various services. When looking for it, there is a problem of sacrificing TCAM forwarding performance, and it is necessary to perform multiple lookups, thereby achieving the effect of searching for multiple services without sacrificing the forwarding performance of the TCAM.

Landscapes

  • Memory System Of A Hierarchy Structure (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Memory System (AREA)

Abstract

一种三态内容寻址存储器TCAM空间的处理方法及装置，其中该方法包括：将第一业务和第二业务设置在TCAM的同一存储块block（S102），其中，第一业务和第二业务之间存在互斥性或优先级；依据互斥性或优先级，将第一业务和第二业务在block中按照不同的地址方向进行写表处理（S104）。通过该方法及装置，解决了相关技术中采用多片TCAM级联的方式实现TCAM对多种业务的查找时，存在牺牲TCAM的转发性能，需要进行多次查表的问题，进而达到了不用牺牲TCAM的转发性能，就能对多种业务查找的效果。

Description

三态内容寻址存储器TCAM空间的处理方法及装置 技术领域
本发明涉及通信领域，具体而言，涉及一种三态内容寻址存储器TCAM空间的处理方法及装置。
背景技术
现今网络发展速度惊人，网络流量的增长及新业务的出现，需要网络设备具有线速和灵活的处理能力。目前网络芯片包括专用集成电路(Application Specific Integrated Circuits简称为ASIC)和网络处理器(Network Processor简称为NP)两大类。网络处理器凭借其高速处理及灵活的可编程性，已成为当今网络中数据处理的有效解决方案。
网络处理器中有多种不同的存储器，如讲台随机存储器(Random Access Memory简称为SRAM)、三态内容寻址存储器(ternary content addressable memory简称为TCAM)、同步动态随机存储器(Synchronous Dynamic Random Access Memory简称为SDRAM)等，这些存储器存放着各种业务表项，如端口表、硬件地址(Media Access Control简称为MAC)表、路由表等。
三态内容寻址存储器TCAM主要用于快速查找访问控制列表(Access Control List简称为ACL)、路由等表项。TCAM的主要特点是快速并行查找，在网络处理器上的应用通常是，微码从报文抽取相关信息组成一个键值KEY，通过NP的TCAM控制器向TCAM发送查找命令，根据结果处理报文。
TCAM的特点是成本高、功耗大、容量有限；优点是快速查找，固定时延，支持最长前缀匹配及多区域匹配。为了充分利用宝贵的TCAM空间，TCAM一般采用硬件上的多表区分技术，一个TCAM划分成若干大小的block，微码发送的KEY同时在多个block内并行查找，可以一次发送键值，返回多个查表结果。
目前网络设备转发要求高的转发带宽，在有限的TCAM查表带宽情况下，查表次数是有限制的。比如要求100Gbps、64字节线速转发，相应包速率为148Mpps，如果选用业界应用广泛的NETLOGIC的NL11K芯片，该芯片的主频400M，这样要完成线速转发，单个报文查表次数只有两次。如果要实现入向、出向ACL，入出方向各一次查找。
目前依赖TCAM实现的业务非常之多，比如IPV4转发、端口ACL、QOS、协议保护、NAT、端口镜像、IPSEC加密等。如果要实现上述这么多业务，相关技术中利用TCAM的转发性能，进行多次查表，采用多片TCAM级联的方式，实现多种业务的查找。
针对相关技术中采用多片TCAM级联的方式实现TCAM对多种业务的查找，该方式存在牺牲了TCAM的转发性能，需要进行多次查表的问题，目前尚未提出有效的解决方案。
发明内容
本发明的主要目的在于提供一种三态内容寻址存储器TCAM空间的处理方法及装置，以至少解决相关技术中采用多片TCAM级联的方式实现TCAM对多种业务的查找时，存在牺牲TCAM的转发性能，需要进行多次查表的问题。
根据本发明的一个实施例，提供了一种三态内容寻址存储器TCAM空间的处理方法，包括：将第一业务和第二业务设置在TCAM的同一存储块block，其中，所述第一业务和所述第二业务之间存在互斥性或优先级；依据所述互斥性或优先级，将所述第一业务和所述第二业务在所述block中按照不同的地址方向进行写表处理。
在本实施例中，在所述第一业务和所述第二业务的业务之间存在互斥性时，将所述第一业务和所述第二业务在所述block中按照不同的地址方向进行写表处理包括：将所述第一业务从低地址向高地址方向进行写表处理，并将所述第二业务从高地址向低地址方向进行写表处理，或将所述第二业务从低地址向高地址方向进行写表处理，并将所述第一业务从高地址向低地址方向进行写表处理。
在本实施例中，在所述第一业务和所述第二业务的业务之间存在优先级时，将所述第一业务和所述第二业务在所述block中按照不同的地址方向进行写表处理包括：在所述第一业务的业务优先级高于所述第二业务的业务时，将所述第一业务从低地址向高地址方向进行写表处理，并将所述第二业务从高地址向低地址方向进行写表处理；或，在所述第一业务的业务优先级低于所述第二业务的业务时，将所述第二业务从高地址向低地址方向进行写表处理，并将所述第一业务从低地址向高地址方向进行写表处理。
在本实施例中，所述方法还包括：在所述第一业务的写表地址与所述第二业务的写表地址重合时，判断所述第一业务或所述第二业务占有的TCAM空间中是否存在空 闲空间；在判断结果为是时，依据所述空闲空间添加所述第一业务或所述第二业务的条目。
在本实施例中，在添加的条目为所述第一业务的条目，且在判断结果为所述第一业务占有的TCAM空间中存在第一空闲空间时，依据所述空闲空间添加所述第一业务的条目包括：将所述第一业务需要添加的条目写入所述第一空闲空间中；在添加的条目为所述第一业务的条目，且判断结果为所述第二业务占有的TCAM空间中存在第二空闲空间时，依据所述空闲空间添加所述第一业务的条目包括：压缩所述第二业务占有的TCAM空间中的第二空闲空间，将所述第二空闲空间转移到所述第一业务的边界写表地址与所述第二业务的边界写表地址之间；按照所述第一业务写表方向，将所述第一业务需要添加的条目写入到所述边界写表地址的下一地址。
在本实施例中，在添加的条目为所述第二业务的条目，且在判断结果为所述第二业务占有的TCAM空间中存在第三空闲空间时，依据所述空闲空间添加所述第二业务的条目包括：将所述第二业务需要添加的条目写入所述第三空闲空间中；在添加的条目为所述第二业务的条目，且判断结果为所述第一业务占有的TCAM空间中存在第四空闲空间时，依据所述空闲空间添加所述第二业务的条目包括：压缩所述第二业务占有的TCAM空间中的第三空闲空间，将所述第三空闲空间转移到所述第一业务的边界写表地址与所述第二业务的边界写表地址之间；照所述第二业务写表方向，将所述第二业务需要添加的条目写入到所述边界写表地址的下一地址。
根据本发明的另一个实施例，提供了一种三态内容寻址存储器TCAM空间的处理装置，包括：设置模块，设置为将第一业务和第二业务设置在TCAM的同一存储块block，其中，所述第一业务和所述第二业务之间存在互斥性或优先级；写表模块，设置为依据所述互斥性或优先级，将所述第一业务和所述第二业务在所述block中按照不同的地址方向进行写表处理。
在本实施例中，在所述第一业务和所述第二业务的业务之间存在互斥性时，所述写表模块包括：第一写表单元，设置为将所述第一业务从低地址向高地址方向进行写表处理，并将所述第二业务从高地址向低地址方向进行写表处理，或第二写表单元，设置为将所述第二业务从低地址向高地址方向进行写表处理，并将所述第一业务从高地址向低地址方向进行写表处理。
在本实施例中，在所述第一业务和所述第二业务的业务之间存在优先级时，所述写表模块还包括：第三写表单元，设置为在所述第一业务的业务优先级高于所述第二业务的业务时，将所述第一业务从低地址向高地址方向进行写表处理，并将所述第二 业务从高地址向低地址方向进行写表处理；或，第四写表单元，设置为在所述第一业务的业务优先级低于所述第二业务的业务时，将所述第二业务从高地址向低地址方向进行写表处理，并将所述第一业务从低地址向高地址方向进行写表处理。
在本实施例中，所述装置还包括：判断模块，设置为在所述第一业务的写表地址与所述第二业务的写表地址重合时，判断所述第一业务或所述第二业务占有的TCAM空间中是否存在空闲空间；添加模块，设置为在判断结果为是时，依据所述空闲空间添加所述第一业务或所述第二业务的条目。
通过本发明，采用在TCAM中的存储块block中设置第一业务和第二业务，其中，该业务可以同类型的两个业务，或是不同类型的两种业务，并且第一业务和第二业务之间存在互斥性或优先级；依据第一业务和第二业务的互斥性或优先级，将第一业务和第二业务在该block中按照不同的地方进行写表处理的方式，解决了相关技术中采用多片TCAM级联的方式实现TCAM对多种业务的查找时，存在牺牲TCAM的转发性能，需要进行多次查表的问题，进而达到了不用牺牲TCAM的转发性能，就能对多种业务查找的效果。
附图说明
此处所说明的附图用来提供对本发明的进一步理解，构成本申请的一部分，本发明的示意性实施例及其说明用于解释本发明，并不构成对本发明的不当限定。在附图中：
图1是根据本发明实施例的三态内容寻址存储器TCAM空间的处理方法流程图；
图2是根据本发明实施例的三态内容寻址存储器TCAM空间的处理装置结构框图；
图3是根据本发明实施例的三态内容寻址存储器TCAM空间的处理装置可选结构框图一；
图4是根据本发明实施例的三态内容寻址存储器TCAM空间的处理装置可选结构框图二；
图5是根据本发明实施例的三态内容寻址存储器TCAM空间的处理装置可选结构框图三；
图6是根据相关技术中Block并行查找及业务添加示意图；
图7是根据本发明可选实施例的三态内容寻址存储器TCAM空间的业务添加示意图；
图8是根据本发明可选实施例的三态内容寻址存储器TCAM空间的表管理方式示意图；
图9是根据本发明可选实施例的TCAM添加条目方法流程图。
具体实施方式
需要说明的是，在不冲突的情况下，本申请中的实施例及实施例中的特征可以相互组合。下面将参考附图并结合实施例来详细说明本发明。
在附图的流程图示出的步骤可以在诸如一组计算机可执行指令的计算机系统中执行，并且，虽然在流程图中示出了逻辑顺序，但是在某些情况下，可以以不同于此处的顺序执行所示出或描述的步骤。
本实施例提供了一种三态内容寻址存储器TCAM空间的处理方法，图1是根据本发明实施例的三态内容寻址存储器TCAM空间的处理方法流程图，如图1所示，该流程包括以下步骤：
步骤S102：将第一业务和第二业务设置在TCAM的同一存储块block；
其中，第一业务和第二业务之间存在互斥性或优先级；
步骤S104：依据互斥性或优先级，将第一业务和第二业务在block中按照不同的地址方向进行写表处理。
通过本实施例，采用在TCAM中的存储块block中设置第一业务和第二业务，其中，该业务可以同类型的两个业务，或是不同类型的两种业务，并且第一业务和第二业务之间存在互斥性或优先级；依据第一业务和第二业务的互斥性或优先级，将第一业务和第二业务在该block中按照不同的地方进行写表处理的方式，解决了相关技术中采用多片TCAM级联的方式实现TCAM对多种业务的查找时，存在牺牲TCAM的转发性能，需要进行多次查表的问题，进而达到了不用牺牲TCAM的转发性能，就能对多种业务查找的效果。
在本实施例中在涉及到第一业务和第二业务的业务之间存在互斥性时，上述步骤S104中将第一业务和第二业务在block中按照不同的地址方向进行写表处理的方式可以通过如下方式来实现：
方式一：将第一业务从低地址向高地址方向进行写表处理，并将第二业务从高地址向低地址方向进行写表处理；
方式二：将第二业务从低地址向高地址方向进行写表处理，并将第一业务从高地址向低地址方向进行写表处理。
在本实施例中还涉及到在第一业务和第二业务的业务之间存在优先级时，上述步骤S104中将第一业务和第二业务在block中按照不同的地址方向进行写表处理的方式则可以通过如下方式来实现：
方式一：在第一业务的业务优先级高于第二业务的业务时，将第一业务从低地址向高地址方向进行写表处理，并将第二业务从高地址向低地址方向进行写表处理；或，
方式二：在第一业务的业务优先级低于第二业务的业务时，将第二业务从高地址向低地址方向进行写表处理，并将第一业务从低地址向高地址方向进行写表处理。
针对上述第一业务和第二业务存在互斥性和优先级，下面通过本实施例的一个应用场景进行相应的说明；
在本应用场景中通过A和B分别表示第一业务和第二业务，业务互斥性指A和B两种业务不会同时配置，或者说同一个报文不可能同时命中A和B的TCAM条目。例如协议保护和IPSEC加密，协议保护是匹配协议包进行优先级提升或者上送CPU，对于协议报文不要求进行IPSEC加密。这样协议保护和IPSEC两种业务就是互斥的。
业务优先级关系是指A和B两种业务有不同的优先级关系，A和B可能同时配置，当时同时配置情况下，A业务的优先级高于B业务。例如PORT ACL和QOS，PORT ACL一般是先某种报文的过滤，QOS用来实现报文的优先级修改等，PORT ACL优先级高于QOS。
此外，在本实施例的一个可选实施方式中，本实施例的方法还可以包括：
步骤S106：在第一业务的写表地址与第二业务的写表地址重合时，判断第一业务或第二业务占有的TCAM空间中是否存在空闲空间；
步骤S108：在判断结果为是时，依据空闲空间添加第一业务或第二业务的条目。
在本实施例可选实施方式中涉及到的第一业务的写表地址与第二业务的写表地址重合值得是：第一业务和第二业务按照不同的方向进行写表，如第一业务按照从低地址向高地址方向进行写表处理，第二业务按照从高地址向低地址方向进行写表处理，两者在同一个block中进行写表，最终第一业务的最高地址与第二业务的最低地址重合。
在本实施例中的可选实施方式中，依据空闲空间添加第一业务或第二业务的条目可以通过如下方式来实现：
方式一：
在添加的条目为第一业务的条目，且在判断结果为第一业务占有的TCAM空间中存在第一空闲空间时，依据空闲空间添加第一业务的条目包括：将第一业务需要添加的条目写入第一空闲空间中；
在添加的条目为第一业务的条目，且判断结果为第二业务占有的TCAM空间中存在第二空闲空间时，依据空闲空间添加第一业务的条目包括：压缩第二业务占有的TCAM空间中的第二空闲空间，将第二空闲空间转移到第一业务的边界写表地址与第二业务的边界写表地址之间；按照第一业务写表方向，将第一业务需要添加的条目写入到边界写表地址的下一地址。
方式二：
在添加的条目为第二业务的条目，且在判断结果为第二业务占有的TCAM空间中存在第三空闲空间时，依据空闲空间添加第二业务的条目包括：将第二业务需要添加的条目写入第三空闲空间中；
在添加的条目为第二业务的条目，且判断结果为第一业务占有的TCAM空间中存在第四空闲空间时，依据空闲空间添加第二业务的条目包括：压缩第二业务占有的TCAM空间中的第三空闲空间，将第三空闲空间转移到第一业务的边界写表地址与第二业务的边界写表地址之间；照第二业务写表方向，将第二业务需要添加的条目写入到边界写表地址的下一地址。
在本实施例中还提供了一种三态内容寻址存储器TCAM空间的处理装置，该装置用于实现上述实施例及可选实施方式，已经进行过说明的不再赘述。如以下所使用的，术语“模块”“单元”可以实现预定功能的软件和/或硬件的组合。尽管以下实施例所 描述的装置较佳地以软件来实现，但是硬件，或者软件和硬件的组合的实现也是可能并被构想的。
图2是根据本发明实施例的三态内容寻址存储器TCAM空间的处理装置结构框图，如图2所示，该装置包括：设置模块22，设置为将第一业务和第二业务设置在TCAM的同一存储块block，其中，第一业务和第二业务之间存在互斥性或优先级；写表模块24与设置模块22耦合连接，设置为将第一业务和第二业务在block中按照不同的地址方向进行写表处理。
图3是根据本发明实施例的三态内容寻址存储器TCAM空间的处理装置可选结构框图一，在第一业务和第二业务的业务之间存在互斥性时，如图3所示，该写表模块24包括：第一写表单元32，设置为将第一业务从低地址向高地址方向进行写表处理，并将第二业务从高地址向低地址方向进行写表处理，第二写表单元34，设置为将第二业务从低地址向高地址方向进行写表处理，并将第一业务从高地址向低地址方向进行写表处理。
图4是根据本发明实施例的三态内容寻址存储器TCAM空间的处理装置可选结构框图二，在第一业务和第二业务的业务之间存在优先级时，如图4所示，写表模块24还包括：第三写表单元42，设置为在第一业务的业务优先级高于第二业务的业务时，将第一业务从低地址向高地址方向进行写表处理，并将第二业务从高地址向低地址方向进行写表处理；第四写表单元44，设置为在第一业务的业务优先级低于第二业务的业务时，将第二业务从高地址向低地址方向进行写表处理，并将第一业务从低地址向高地址方向进行写表处理。
图5是根据本发明实施例的三态内容寻址存储器TCAM空间的处理装置可选结构框图三，如图5所示，装置还包括：判断模块52与写表模块24耦合连接，设置为在第一业务的写表地址与第二业务的写表地址重合时，判断第一业务或第二业务占有的TCAM空间中是否存在空闲空间；添加模块54与判断模块52耦合连接，设置为在判断结果为是时，依据空闲空间添加第一业务或第二业务的条目。
可选地，该添加模块54，还设置为在添加的条目为第一业务的条目，且在判断结果为第一业务占有的TCAM空间中存在第一空闲空间时，将第一业务需要添加的条目写入第一空闲空间中；或，设置为在添加的条目为第一业务的条目，且判断结果为第二业务占有的TCAM空间中存在第二空闲空间时，压缩第二业务占有的TCAM空间中的第二空闲空间，将第二空闲空间转移到第一业务的边界写表地址与第二业务的边 界写表地址之间；按照第一业务写表方向，将第一业务需要添加的条目写入到边界写表地址的下一地址。
上述添加模块54是以第一业务条目为例进行具体如下添加条目的说明，同样的在添加的条目为第二业务时，添加模块54操作与添加第一业务条目的操作类似，具体地，该添加条目54还可以用于，在添加的条目为第二业务的条目，且在判断结果为第二业务占有的TCAM空间中存在第三空闲空间时，将第二业务需要添加的条目写入第三空闲空间中；或，在添加的条目为第二业务的条目，且判断结果为第一业务占有的TCAM空间中存在第四空闲空间时，压缩第二业务占有的TCAM空间中的第三空闲空间，将第三空闲空间转移到第一业务的边界写表地址与第二业务的边界写表地址之间；照第二业务写表方向，将第二业务需要添加的条目写入到边界写表地址的下一地址。
下面结合附图以及可选实施例对本发明进行举例说明。
本可选实施例将不同的业务放在一个block内；放在同一block内的A和B两个业务间具有业务互斥性或者优先级关系；同一个block内的A和B按照不同方向写表。
其中，业务互斥性指A和B两种业务不会同时配置，或者说同一个报文不可能同时命中A和B的TCAM条目。例如协议保护和IPSEC加密，协议保护是匹配协议包进行优先级提升或者上送CPU，对于协议报文不要求进行IPSEC加密。这样协议保护和IPSEC两种业务就是互斥的。
业务优先级关系是指A和B两种业务有不同的优先级关系，A和B可能同时配置，当时同时配置情况下，A业务的优先级高于B业务。例如PORT ACL和QOS，PORT ACL一般是先某种报文的过滤，QOS用来实现报文的优先级修改等，PORT ACL优先级高于QOS。
需要说明的是，上述只是本可选实施例的一个可选实施方式，在具体的实际应用不完全相同，只需要满足上述的业务互斥性或者优先级关系。
也就是说，同一个block内的A/B业务如果有业务互斥性，则A和B其中一个从低地址向高地址方向写表；另外一个从高地址向低地址方向写表。同一个block内的A/B业务如果具有不同优先级，如A业务优先级大于B业务。由于TCAM优先返回低地址匹配命中的条目，因此A业务从低地址向高地址方向写表；B业务从高地址向低地址方向写。这样，即便A业务和B业务的tcam条目都命中的情况下，优先返回高优先级的业务。
通过本可选实施例对转发面而言，在有限的查表次数情况下，尽可能地实现更多业务查找，最优情况下TCAM利用率达到两倍。比如NL11K有4个Block硬件查找引擎，相关技术中查找一次只能实现四种业务查找；采用本可选实施例一次查找最多可以实现八种业务并行查找。对控制面而言，同一个Block内的业务A和业务B可以共享TCAM空间，极大提高了TCAM的空间利用率。
图6是根据相关技术中Block并行查找及业务添加示意图，如图6所示，每个Block内存放一种业务，分别为A1/A2/A3/A4，各业务按照低地址向高地址方向写表。对转发面而言，一次分别返回A1/A2/A3/A4四种业务的查表结果。
图7是根据本发明可选实施例的三态内容寻址存储器TCAM空间的业务添加示意图，如图7所示，每一个block内存放两种业务，业务间存在互斥性或者不同优先级。例如：Block1内存放A1/B1两种业务，A1按照低地址向高地址方向写表，B1按照高地址向低地址方向写表。转发面查表返回A1或者B1中的匹配条目，实现两种业务的同时查找。
通过本可选实施例还可以使得业务A和B可以共享Block空间，极大限度的利用TCAM硬件资源。例如，Block内存放Port ACL和Qos ACL两种业务，如果Block总条目数为64K，则Port ACL和Qos ACL都可以最大支持64K。在用户应用中，可能配置极少量的Qos ACL条目，这样Port ACL可以分配的空间可以接近64K。而按照传统做法，Port ACL和Qos ACL的空间必须静态分配好，做不到空间共享，TCAM资源有很大浪费。
图8是根据本发明可选实施例的三态内容寻址存储器TCAM空间的表管理方式示意图，如图8所示，由于表项添加删除，TCAM中会存在空洞，即空闲条目，如图8中①图虚线所示。因此，同一Block内A/B两个业务的添加需要考虑空间管理的问题，解决Block“假满”现象，如图8中②图所示。
目前有很多TCAM管理算法，但基本思想都是记录和维护TCAM的空闲条目，表项删除时将删除的条目地址加到空闲资源池，表项添加时从空闲资源池分配一个空闲条目。
比较通用的是有序链表管理算法，即创建一个链表管理tcam空闲条目地址。TCAM管理算法不在本专利范围之内，不属于本专利发明点。后面介绍基于该算法的同一Block内两个业务的TCAM资源管理方法。基于其他算法的同一Block内两个业务的资源管理方法与此类似。
如图8中①图所示，Block内存放A/B两种业务，分别按照不同方向写表，Block总大小为MAX。基于通用有序链表管理算法的Block内资源管理，需要分别为A/B两种业务建立两个资源池，即两个链表，分别管理各自的空闲空间。业务A/B相应的有序链表资源管理的方向不同，即业务A相应的有序链表返回业务A的最低地址空闲条目；业务B相应的有序链表返回业务B的最高地址空闲条目。这样业务A添加时从低地址向高地址方向添加，业务B添加从高地址向低地址方向添加。空闲空间(“空洞”)在图8中用虚线表示。此外通过一个边界地址Ta和Tb分别记录业务A的最高地址和业务B的最低地址，Ta和Tb是用来解决两个业务添加出现“假满”现象的两个变量。
表项添加时，业务A和B分别从各自资源池分配地址空间，表项删除时，删除条目释放到各自的资源池。以有序链表为例，业务A添加时分配条目为业务A的有序链表第一个节点内的地址，删除条目时，将该条目节点返回到业务A的有序链表相应位置中。
图8中②图所示为Block出现“假满”的情况，即业务A最高地址和业务B最低地址重合，即Ta+Tb＝MAX，此时如果添加业务A或者业务B，已经没有空间，但实际上TCAM空间存在很多“空洞”，如果压缩的话，可以有空间进行条目添加。以添加业务A为例，图9是根据本发明可选实施例的TCAM添加条目方法流程图，如图9所示，该方法的步骤包括如下步骤：
步骤S902：开始；
步骤S904：A业务是否有空洞；
其中，A的空闲资源池中是否有条目地址小于Ta，如果是则填补“空洞”，使用空闲链表中第一个节点内的地址，条目添加在第一个“空洞”，否则进入步骤S906；
步骤S906：判断Ta+Tb是否小于MAX，如果是，条目添加在Ta+1位置，并更新Ta的值，进入步骤S908；否则进入步骤S912；
步骤S908：判断业务B是否可以压缩；
其中，也就是判断B空间内是否有“空洞”，即是否B的空闲资源池内有地址大于Tb，如果有，证明可以压缩，进入步骤S910；否则证明整个TCAM都没有“空洞”，进入步骤S916；
步骤S910：B业务空间压缩；
B业务内有效TCAM条目物理地址不连续，压缩B业务空间，搬移有效条目，使之物理地址连续，保持原有先后次序存放到该Block内高地址部分。压缩后，更新Tb，此时Ta+Tb<MAX,即业务B已经把空闲资源池中的“空隙”搬移到Ta和Tb之间，业务A有空间可以进行写表，A业务要添加的条目存放到Ta+1位置，进入步骤S912；
步骤S912：A业务写表；
其中，将新加的TCAM条目写到硬件中；
步骤S914：写表成功，结束；
步骤S916：表满，写表失败，结束。
由上可见，基于通用有序链表管理算法的两个业务的管理，只是在通用算法基础上进行简单扩展，两个业务A/B创建各自独立的资源管理实例分别进行资源管理，另外添加一个边界地址的变量处理空间“假满”的问题。因此基于本专利方法的TCAM管理算法只需在原有通用算法基础上进行简单扩展，基于本专利方法的TCAM空间易于管理。
通过本可选实施例提供的一种TCAM管理方法，采用分析业务之间的逻辑关系，将不同业务放到同一个硬件Block空间，进而采用类似“上下对挤”的方法进行TCAM管理；对于转发面而言，可以在有限的查表次数内，尽可能的实现更多种类的业务查找；对于控制面而言，多种业务共享同一地址空间，避免静态分配，可以极大提高TCAM资源的空间利用率；而在表管理方面，只需要在已有算法基础上，进行简单扩展，管理方便。
以上仅为本发明的可选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。
工业实用性
基于本发明实施例提供的上述技术方案，通过在TCAM中的存储块block中设置第一业务和第二业务，其中，该业务可以同类型的两个业务，或是不同类型的两种业务，并且第一业务和第二业务之间存在互斥性或优先级；依据第一业务和第二业务的互斥性或优先级，将第一业务和第二业务在该block中按照不同的地方进行写表处理的方式，解决了相关技术中采用多片TCAM级联的方式实现TCAM对多种业务的查 找时，存在牺牲TCAM的转发性能，需要进行多次查表的问题，进而达到了不用牺牲TCAM的转发性能，就能对多种业务查找的效果。

Claims (10)

  1. 一种三态内容寻址存储器TCAM空间的处理方法，包括：
    将第一业务和第二业务设置在TCAM的同一存储块block，其中，所述第一业务和所述第二业务之间存在互斥性或优先级；
    依据所述互斥性或优先级，将所述第一业务和所述第二业务在所述block中按照不同的地址方向进行写表处理。
  2. 根据权利要求1所述的方法，其中，在所述第一业务和所述第二业务的业务之间存在互斥性时，将所述第一业务和所述第二业务在所述block中按照不同的地址方向进行写表处理包括：
    将所述第一业务从低地址向高地址方向进行写表处理，并将所述第二业务从高地址向低地址方向进行写表处理，或
    将所述第二业务从低地址向高地址方向进行写表处理，并将所述第一业务从高地址向低地址方向进行写表处理。
  3. 根据权利要求1所述的方法，其中，在所述第一业务和所述第二业务的业务之间存在优先级时，将所述第一业务和所述第二业务在所述block中按照不同的地址方向进行写表处理包括：
    在所述第一业务的业务优先级高于所述第二业务的业务时，将所述第一业务从低地址向高地址方向进行写表处理，并将所述第二业务从高地址向低地址方向进行写表处理；或，
    在所述第一业务的业务优先级低于所述第二业务的业务时，将所述第二业务从高地址向低地址方向进行写表处理，并将所述第一业务从低地址向高地址方向进行写表处理。
  4. 根据权利要求1所述的方法，其中，所述方法还包括：
    在所述第一业务的写表地址与所述第二业务的写表地址重合时，判断所述第一业务或所述第二业务占有的TCAM空间中是否存在空闲空间；
    在判断结果为是时，依据所述空闲空间添加所述第一业务或所述第二业务的条目。
  5. 根据权利要求4所述的方法，其中，
    在添加的条目为所述第一业务的条目，且在判断结果为所述第一业务占有的TCAM空间中存在第一空闲空间时，依据所述空闲空间添加所述第一业务的条目包括：将所述第一业务需要添加的条目写入所述第一空闲空间中；
    在添加的条目为所述第一业务的条目，且判断结果为所述第二业务占有的TCAM空间中存在第二空闲空间时，依据所述空闲空间添加所述第一业务的条目包括：压缩所述第二业务占有的TCAM空间中的第二空闲空间，将所述第二空闲空间转移到所述第一业务的边界写表地址与所述第二业务的边界写表地址之间；按照所述第一业务写表方向，将所述第一业务需要添加的条目写入到所述边界写表地址的下一地址。
  6. 根据权利要求4所述的方法，其中，
    在添加的条目为所述第二业务的条目，且在判断结果为所述第二业务占有的TCAM空间中存在第三空闲空间时，依据所述空闲空间添加所述第二业务的条目包括：将所述第二业务需要添加的条目写入所述第三空闲空间中；
    在添加的条目为所述第二业务的条目，且判断结果为所述第一业务占有的TCAM空间中存在第四空闲空间时，依据所述空闲空间添加所述第二业务的条目包括：压缩所述第二业务占有的TCAM空间中的第三空闲空间，将所述第三空闲空间转移到所述第一业务的边界写表地址与所述第二业务的边界写表地址之间；照所述第二业务写表方向，将所述第二业务需要添加的条目写入到所述边界写表地址的下一地址。
  7. 一种三态内容寻址存储器TCAM空间的处理装置，包括：
    设置模块，设置为将第一业务和第二业务设置在TCAM的同一存储块block，其中，所述第一业务和所述第二业务之间存在互斥性或优先级；
    写表模块，设置为依据所述互斥性或优先级，将所述第一业务和所述第二业务在所述block中按照不同的地址方向进行写表处理。
  8. 根据权利要求7所述的装置，其中，在所述第一业务和所述第二业务的业务之间存在互斥性时，所述写表模块包括：
    第一写表单元，设置为将所述第一业务从低地址向高地址方向进行写表处理，并将所述第二业务从高地址向低地址方向进行写表处理，或
    第二写表单元，设置为将所述第二业务从低地址向高地址方向进行写表处理，并将所述第一业务从高地址向低地址方向进行写表处理。
  9. 根据权利要求7所述的装置，其中，在所述第一业务和所述第二业务的业务之间存在优先级时，所述写表模块还包括：
    第三写表单元，设置为在所述第一业务的业务优先级高于所述第二业务的业务时，将所述第一业务从低地址向高地址方向进行写表处理，并将所述第二业务从高地址向低地址方向进行写表处理；或，
    第四写表单元，设置为在所述第一业务的业务优先级低于所述第二业务的业务时，将所述第二业务从高地址向低地址方向进行写表处理，并将所述第一业务从低地址向高地址方向进行写表处理。
  10. 根据权利要求7所述的装置，其中，所述装置还包括：
    判断模块，设置为在所述第一业务的写表地址与所述第二业务的写表地址重合时，判断所述第一业务或所述第二业务占有的TCAM空间中是否存在空闲空间；
    添加模块，设置为在判断结果为是时，依据所述空闲空间添加所述第一业务或所述第二业务的条目。
PCT/CN2015/076097 2014-12-26 2015-04-08 三态内容寻址存储器tcam空间的处理方法及装置 WO2016101439A1 (zh)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
CN201410829630.X 2014-12-26
CN201410829630.XA CN105791455B (zh) 2014-12-26 2014-12-26 三态内容寻址存储器tcam空间的处理方法及装置

Publications (1)

Publication Number Publication Date
WO2016101439A1 true WO2016101439A1 (zh) 2016-06-30

Family

ID=56149055

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/CN2015/076097 WO2016101439A1 (zh) 2014-12-26 2015-04-08 三态内容寻址存储器tcam空间的处理方法及装置

Country Status (2)

Country Link
CN (1) CN105791455B (zh)
WO (1) WO2016101439A1 (zh)

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
TWI730714B (zh) * 2020-04-10 2021-06-11 啓碁科技股份有限公司 記憶體設備和設備信息維護方法
CN113328948A (zh) * 2021-06-02 2021-08-31 杭州迪普信息技术有限公司 资源管理方法、装置、网络设备及计算机可读存储介质
WO2024078011A1 (zh) * 2022-10-11 2024-04-18 深圳市中兴微电子技术有限公司 并行查表装置、方法及设备、计算机可读存储介质

Families Citing this family (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN106789706B (zh) * 2016-11-11 2020-08-07 天津光电通信技术有限公司 一种基于tcam的网络分流系统
CN108595731B (zh) * 2018-01-23 2022-02-08 苏州盛科通信股份有限公司 一种以太网芯片中动态表项的设计方法及装置
CN113519144B (zh) * 2019-01-10 2023-06-27 马维尔以色列(M.I.S.L.)有限公司 用于网络设备的精确匹配和三元内容可寻址存储器(tcam)混合查找

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN1465014A (zh) * 2001-07-20 2003-12-31 诺基亚有限公司 使用tcam实现数据流的选择性路由
CN102957617A (zh) * 2011-08-18 2013-03-06 盛科网络（苏州）有限公司 实现多业务叠加的方法及装置
CN104035928A (zh) * 2013-03-04 2014-09-10 杭州华三通信技术有限公司 一种tcam表空间回收的方法及装置
US20140321467A1 (en) * 2013-04-30 2014-10-30 Xpliant, Inc. Apparatus and Method for Table Search with Centralized Memory Pool in a Network Switch

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN1279729C (zh) * 2004-02-20 2006-10-11 清华大学 基于tcam的分布式并行ip路由查找方法
CN102289453B (zh) * 2011-06-20 2013-09-18 北京星网锐捷网络技术有限公司 三态内容寻址存储器规则存储方法、装置及网络设备

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN1465014A (zh) * 2001-07-20 2003-12-31 诺基亚有限公司 使用tcam实现数据流的选择性路由
CN102957617A (zh) * 2011-08-18 2013-03-06 盛科网络（苏州）有限公司 实现多业务叠加的方法及装置
CN104035928A (zh) * 2013-03-04 2014-09-10 杭州华三通信技术有限公司 一种tcam表空间回收的方法及装置
US20140321467A1 (en) * 2013-04-30 2014-10-30 Xpliant, Inc. Apparatus and Method for Table Search with Centralized Memory Pool in a Network Switch

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
TWI730714B (zh) * 2020-04-10 2021-06-11 啓碁科技股份有限公司 記憶體設備和設備信息維護方法
CN113328948A (zh) * 2021-06-02 2021-08-31 杭州迪普信息技术有限公司 资源管理方法、装置、网络设备及计算机可读存储介质
WO2024078011A1 (zh) * 2022-10-11 2024-04-18 深圳市中兴微电子技术有限公司 并行查表装置、方法及设备、计算机可读存储介质

Also Published As

Publication number Publication date
CN105791455A (zh) 2016-07-20
CN105791455B (zh) 2020-04-07

Similar Documents

Publication Publication Date Title
WO2016101439A1 (zh) 三态内容寻址存储器tcam空间的处理方法及装置
CN101247337B (zh) 一种报文转发的方法和设备
US7392241B2 (en) Searching method for a security policy database
US9367645B1 (en) Network device architecture to support algorithmic content addressable memory (CAM) processing
US9571300B2 (en) Reducing encapsulation overhead in overlay-based networks
KR100705593B1 (ko) 라우팅 시스템 및 라우팅 시스템의 룰 엔트리 관리 방법
JP6190754B2 (ja) ネットワークスイッチにおける集中型メモリプールを用いるテーブル検索のための装置および方法
US11310158B2 (en) Packet classification using fingerprint hash table
WO2014101777A1 (zh) 流表匹配方法和装置以及交换机
US10805216B2 (en) Shared service access for multi-tenancy in a data center fabric
US8341187B2 (en) Method and device for storage
US9306851B1 (en) Apparatus and methods to store data in a network device and perform longest prefix match (LPM) processing
WO2014127605A1 (zh) 基于哈希表和tcam表的mac地址硬件学习方法及系统
WO2007019755A1 (en) Method for providing the different quality of service for data stream
US9906443B1 (en) Forwarding table updates during live packet stream processing
CN102291472A (zh) 一种网络地址查找方法及装置
CN108234422B (zh) 资源调度方法及装置
US8472350B2 (en) Bank aware multi-bit trie
CN109981464A (zh) 一种在fpga中实现的tcam电路结构及其匹配方法
WO2020248690A1 (zh) 报文匹配查表方法、系统、存储介质和终端
US20140095785A1 (en) Content Aware Block Power Savings
WO2016091027A1 (zh) 一种网络地址转换与访问控制列表规则聚合方法和装置
CN105743678A (zh) 管理三态内容寻址存储器tcam表空间的方法及装置
CN106294191A (zh) 处理表的方法、访问表的方法和装置
CN104601645A (zh) 一种数据包处理方法及装置

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 15871517

Country of ref document: EP

Kind code of ref document: A1

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 15871517

Country of ref document: EP

Kind code of ref document: A1