WO2011078108A1 - Pattern-matching method and device for a multiprocessor environment - Google Patents

Abstract

Disclosed is a pattern-matching device that operates in a multi-core processor environment that has a multi-core CPU provided with: a plurality of processor cores; and a shared memory shared among the processor cores, which exist within the same CPU. The shared memory contains a pattern table provided with search patterns. The pattern-matching device executes a pattern-matching process in parallel across the plurality of processor cores. Said pattern-matching process tries to match a search target, namely a search key.

Description

Pattern matching method and apparatus in multiprocessor environment

The present invention relates to a multiprocessor environment composed of a plurality of processors, and in particular, in a system in which a plurality of processors and a shared memory shared by these processors are regarded as one unit, and there are a plurality of units, sharing in each unit is performed. The present invention relates to a system for performing pattern matching by dividing a pattern management table into a memory and executing pattern matching in parallel using a plurality of processors in the system.

Pattern matching processing that identifies whether an input character string matches a character string (pattern) is an important elemental technology in the network field. For example, it is input in a network relay device such as a router or a switch. Using the header information of the packet to identify the flow to which the packet belongs (hereinafter referred to as flow search processing), not only the packet header information but also the data in the packet payload It is used in a technique called Deep Packet Inspection (DPI) for performing pattern matching processing, specifying flows more finely, providing QoS (Quality of Service) for each flow, performing load distribution control, and the like.

In the flow search process, TCP (Transmission Control Protocol) / UDP (User Datagram Protocol) in addition to the source IP address, destination IP address, and protocol number defined in the IP (Internet Protocol) header of generally input packets. ) A series of packet sequences specified using fields such as a transmission port number and a destination port number defined in the header is called a flow. For example, a flow is specified using a technique called hashing or hashing. . In the hash method, the search key is converted into a bit string of a specific length called a hash value by performing a calculation called a hash function on the search key using the set of fields as described above for identifying the flow. Then, a flow search process is performed using a table storing a search key and a pointer to the next entry at the entry position in the table corresponding to the obtained hash value. Such a table is called a hash table, and in particular, since a search key for specifying a flow is stored, it may be called a flow table. Since the hash method is described in, for example, Patent Document 1 and details thereof are omitted, FIG. 17 shows a configuration example of a hash table.

FIG. 18 shows a schematic configuration example of a normal server architecture including only one CPU (Central Processing Unit) having only one processor core, and describes an operation outline when performing flow search processing on this server. . In the example of the normal server architecture shown in FIG. 18, a CPU 11 having only one processor core, a main memory 6 such as a DRAM (Dynamic Random Access Memory), a MAC (Media Access Control) and a transmission / reception FIFO (First-In). A packet transmission / reception block 10 including First-Out) is connected through the bus 3. The CPU 11 includes a processor core 11-1 and a level 2 cache (L2 cache) 11-0. The CPU 11, the main memory 6, and the packet transmission / reception block 10 may be connected through a chip set called North Bridge or South Bridge, but here, these chipsets are also shown as the bus 3.

Usually, since the flow table has a large capacity, it is constructed on the main memory 6. When the packet is received by the packet transmission / reception block 10, it is written on the main memory 6 using, for example, a DMA (Direct Memory Access) function via the MAC or reception FIFO. When a packet is received by the packet transmission / reception block 10, the packet transmission / reception block 10 applies interrupt control to the processor core 11-1 of the CPU 11, or an event is issued to the event queue. As a result of polling, the processor core 11-1 determines the arrival of the packet and reads the header information of the packet from the main memory 6. Subsequently, the processor core 11-1 derives a hash value for a plurality of header field sets as search keys, reads an entry of the flow table corresponding to the hash value from the main memory 6, and Make a comparison. If these search keys match, it is determined that the packet belongs to the flow corresponding to the entry. If they do not match, follow the pointer stored in the entry, read the next entry, and repeat the process of comparing the search key with the search key in the entry, so that the packet is in the entry The process of confirming whether it belongs to the flow is performed. Note that processing when the search key of the packet does not match the entry in the flow table to the end, for example, registering a table entry as a new flow, is omitted here because it depends on the individual system specifications. To do.

Since such pattern matching processing in the network field, particularly flow search processing, is performed for each input packet, it is necessary to realize this with a high-speed search throughput corresponding to the bandwidth of the network. For this reason, as described above, when a flow table is constructed on the main memory and the flow search process is executed by software processing by the CPU, the flow table on the main memory having a low access performance per search process for one packet is stored multiple times. Therefore, the reduction in processing performance becomes a problem. By holding a part of the flow table of the main memory in the cache memory inside the CPU, for example, the L2 cache 11-0 in FIG. 18, it is possible to reduce the delay related to the access to the main memory. However, in a network, packets belonging to a large number of flows arrive almost randomly, so when it is necessary to refer to different data (table entries in the flow search process) for each process such as the flow search process. It is unlikely that it will not function effectively, resulting in a dramatic decrease in access to the main memory, and may not function effectively. Similarly, for example, as in Patent Document 2, there is a problem similar to the above even if a table in which a part of the hash table is cached is prepared separately from the data cache provided in the CPU. It is done.

On the other hand, in recent years, multi-core CPUs (multi-core processors) incorporating a plurality of processor cores have appeared, and servers equipped with a plurality of them have also been provided. For example, FIG. 19 shows a schematic configuration example of a normal server architecture composed of two CPUs having two processor cores. FIG. 19 shows a configuration in which the CPU 12 and the CPU 13 having two processor cores are provided instead of the CPU 11 in the configuration shown in FIG. Here, the CPU 12 includes two processor cores 12-1 and 12-2 and an L2 cache 12-0, and the CPU 13 includes two processor cores 13-1 and 13-2 and an L2 cache 13-0. In such a server, there are four processor cores, and by performing flow search processing in parallel between these processor cores, the flow search processing is performed in the server configured as shown in FIG. Also improves search performance. However, since the flow table is constructed in the main memory, access to the low-speed main memory is required, and arbitration of access contention for a plurality of processor cores to access the same main memory is required. For this reason, each processor core cannot be used effectively, and there remains a problem in terms of performance. More generally, a similar problem exists in a server including a plurality of CPUs having a plurality of processor cores. Similarly, although such a CPU has a cache memory, the problem in the case where it is necessary to refer to different data for each process as described above has not been solved.

Patent Document 3 discloses a replacement control for reducing the miss-miss rate of a shared cache in a multi-core processor environment as shown in FIG. 19, and Patent Document 4 discloses an exclusive control for a shared memory in a multi-processor environment. Patent Document 5 discloses a prefetch function for a shared cache in a multi-core processor environment, but solves the problem itself when it is necessary to refer to different data for each process such as a flow search process. Not what you want. Furthermore, in Non-Patent Document 1, the longest match search (LPM: Longest Prefix Match) is targeted, and a part of the data area in which data serving as a search key is stored is a memory area having a high-speed access performance such as a cache. A technique for storing and reducing the number of accesses to a low-speed memory is disclosed.

In Patent Document 6, as shown in FIG. 1, a configuration in which (a plurality of) processors, a cache memory, a memory, peripheral devices (peripherals), and a packet controller are connected via a system bus is disclosed (for example, the seventh See paragraph).

Also, when the packet is received by the packet controller, the pattern matching logic configured in the packet receiver and the hash mechanism define in advance the pattern stored in the register in the pattern matching logic and the received packet Addresses and the like are compared to determine whether or not the packet can be received (for example, see the ninth paragraph).

Further, a part of the packet permitted to be received is written in the cache memory in the system and is held for subsequent packet processing performed by the processor (see, for example, the 11th paragraph).

However, as described above, Patent Document 6 has a function of performing pattern matching inside the packet controller, and performs pattern matching there. Pattern matching is not performed in each processor.

Also, as described above, a part of the packet data permitted to be received by pattern matching is written into the cache memory of Patent Document 6 and used for packet processing by the processor. A pattern (flow information) to be subjected to pattern matching is written in the cache memory and is not used as a flow management table.

FIG. 7 of Patent Document 7 shows a configuration in which a plurality of micro engines (processors), a memory (SRAM, DRAM) shared by them, a packet receiving unit, and the like are connected by a bus (for example, see paragraph 50). It is disclosed. Each micro engine includes a local memory and a computing core (processor core).

In addition, the flow state information (pattern, state transition information used in pattern matching) held in the shared memory (SRAM) is read to the local memory in the micro engine, and pattern matching processing is performed by the processor core in the micro engine. (See, for example, paragraph 55).

However, as described above, in Patent Document 7, there are main memories such as SRAM and DRAM which are shared and used by a plurality of processors. There is only local memory corresponding to the processor, and there is no cache memory that can be shared by a plurality of processors. In addition to the main memory (SRAM, DRAM, etc.) shared by a plurality of processors, there is no cache memory shared by a specific number of processors.

As described above, in the pattern matching process of Patent Document 7, information such as a pattern is held on a main memory shared and used by a plurality of processors, and the cache memory (local memory in the micro engine) Information is read from the main memory and used only during the pattern matching process of the target packet. A pattern (flow information) to be subjected to pattern matching is written in the cache memory, and the cache memory is not directly used as a flow management table.

Japanese Patent Laid-Open No. 11-53199 Special table 2002-511703 gazette JP 2002-373115 A JP 2008-293368 A JP 2007-207240 A Special Table 2007-525037 Special table 2008-544728

Butler Lampson, Venkatachari Srinivasan, George Vargese, “IP Lookups Multiway and Multicolumn Search”, IEEE / ACM Transactions. 7, no. 3, 1999, pages 324-334

In pattern matching processing using the multiprocessor environment in the network field as described above, it is necessary to achieve this with high-speed search throughput that matches the network bandwidth, but it is not possible to provide high processing performance that satisfies it. There is a problem.

The reason is that the flow table is built on the main memory with low access performance, and the flow table on the main memory needs to be accessed multiple times. In addition, if a part of the flow table is cached in a memory such as a cache memory that can be accessed faster than the main memory, and the number of accesses to the main memory is reduced, the flow to which the arriving packet belongs is random. This is because there is less dependency between arriving packets and there is less possibility of matching some entries in the cached flow table, so that the effect of reducing the number of accesses to the main memory is small.

An object of the present invention is to provide a pattern matching system capable of realizing a pattern matching process having a high-speed search performance corresponding to a network band.

The first and second pattern matching apparatuses according to the present invention include one or a plurality of multi-core CPUs (1 and 6 in FIG. 1) having a plurality of processor cores and a shared memory shared between the processor cores. 1, 2,..., M), a packet transmission / reception block (5 in FIG. 1, 5 in FIG. 6), and header information serving as a search key in the flow search process is extracted from the received packet. In addition, a search key extraction block (4 in FIG. 1 and 4 in FIG. 6) for generating and issuing a packet reception event and writing the packet to the main memory, a DRAM in which the packet reception event and the packet itself are written if necessary, etc. 1 main memory (6 in FIG. 1, 6 in FIG. 6), a bus (FIG. 1) for connecting the multi-core CPU, the search key extraction block, and the main memory 3, and a 3 in Figure 6). A pattern table based on a hash table is configured in a shared memory in the multi-core CPU. Adopting such a configuration, the search key extraction block extracts a set of fields as a search key from the packet header information in advance, notifies the processor core of the set, and allows faster access than the main memory. By performing the pattern matching process using the pattern table in the shared memory, the object of the present invention can be achieved.

In addition to the second pattern matching device, the third pattern matching device of the present invention has a final result determination block (7 in FIG. 9). Each multi-core CPU has a sub pattern table obtained by dividing one original pattern table on the shared memory. Adopting such a configuration, the search key extraction block extracts in advance the set of fields that will be the search key from the packet header information, notifies it to one processor core of each multi-core CPU, and distributes the pattern matching The object of the present invention can be achieved by performing the pattern matching process using the pattern table in the shared memory that can be accessed at a higher speed than the main memory.

Furthermore, the fourth pattern matching device of the present invention has a configuration in which a hash value calculation block (9 in FIG. 13) is added except for the final result determination block (7 in FIG. 9) in the third pattern matching device. Employing such a configuration, a search key extraction block (8 in FIG. 13) previously extracts a set of fields serving as a search key from the header information of the packet, and further in a hash value calculation block (9 in FIG. 13). By calculating a hash value for the search key, a multi-core CPU having a pattern table holding a pattern entry group corresponding to the hash value can be specified, and pattern matching is performed in one processor core of the multi-core CPU. The object of the present invention can be achieved by performing the pattern matching process using the pattern table in the shared memory that can be accessed at a higher speed than the main memory.

According to the present invention, it is possible to realize a pattern matching process having a high-speed search performance corresponding to the network bandwidth.

It is a block diagram which shows the structure of the apparatus by the 1st Embodiment of this invention. 2 is a flowchart showing the operation of the apparatus according to the first embodiment of the present invention; It is a flowchart which shows step A4 in FIG. It is a figure which shows an example of a flow table. It is a figure which shows the operation | movement outline | summary of the apparatus by the 1st implementation of this invention. It is a block diagram which shows the structure of the apparatus by the 2nd Embodiment of this invention. 6 is a flowchart showing the operation of the apparatus according to the second embodiment of the present invention. It is a figure which shows the operation | movement outline | summary of the apparatus by the 2nd implementation of this invention. It is a block diagram which shows the structure of the apparatus by the 3rd Embodiment of this invention. It is a figure which shows an example of the division | segmentation of the flow table in the 3rd Embodiment of this invention. 6 is a flowchart showing the operation of the apparatus according to the third embodiment of the present invention; It is a figure which shows the operation | movement outline | summary of the apparatus by the 3rd implementation of this invention. It is a block diagram which shows the structure of the apparatus by the 4th Embodiment of this invention. 6 is a flowchart showing the operation of the apparatus according to the fourth embodiment of the present invention; It is a flowchart which shows step A13 in FIG. It is a figure which shows the operation | movement outline | summary of the apparatus by the 4th implementation of this invention. It is a structural example of a hash table. It is an example of an architecture of flow search processing by software in a server having a normal single CPU (single core). It is an example of an architecture of flow search processing by software in a server having two normal CPUs (dual core).

DESCRIPTION OF EMBODIMENTS Hereinafter, embodiments for carrying out the present invention will be described in detail with reference to the drawings.
<Embodiment 1>
FIG. 1 is a block diagram showing the configuration of the first exemplary embodiment of the present invention. Referring to FIG. 1, in the first embodiment of the present invention, a multi-core CPU 1, a packet transmission / reception block 5 for transmitting / receiving packets, and header information serving as a search key in flow search processing are extracted from received packets. Search key extraction block 4 for generating and issuing packet reception events and writing packets to the main memory; main memory 6 such as a DRAM in which packet reception events and packets themselves are written; multi-core CPU 1; search key extraction Block 4 and bus 3 interconnecting main memory 6 are included.

The multi-core CPU 1 includes N processor cores 1-1, 1-2,..., 1-N, and a shared memory 1-0 shared by the N processor cores. The shared memory 1-0 holds all the flow tables configured as hash tables. When the shared memory is used as a data cache, the flow table is held in an area logically separated from the data cache.

When the network is Ethernet (registered trademark), the packet transmission / reception block 5 has a MAC function, and after shaping the input bit stream as an Ethernet (registered trademark) frame, outputs it to the search key extraction block 4 . Since such a packet transmission / reception block 5 is well known to those skilled in the art, its detailed configuration is omitted.

The search key extraction block 4 receives the packet received from the packet transmission / reception block 5 and extracts header information serving as a search key in the flow search process. A packet reception event including the extracted search key information is generated and written to the event queue for the multi-core CPU 1, and the packet after the search key is extracted is written to the main memory. In general, the DMA function is used for the writing process. At the time of packet transmission, this block reads packet data from the main memory and outputs it to the packet transmission / reception block 5 as it is.

In FIG. 1, the multi-core CPU 1, the search key extraction block 4, and the main memory 6 are connected by a bus 3, but this connection form is a chip called North Bridge or South Bridge provided in a server or the like. A form connected through a set, a crossbar, or a ring bus may be used. In addition, the present embodiment may be configured on a motherboard such as a server, or all except the main memory 6 is configured as one SoC (System-on-a-Chip) on one chip. May be.

Next, the operation of the first exemplary embodiment of the present invention will be described in detail with reference to the flowcharts of FIGS.

Packets input from the network are received by the packet transmission / reception block 5. For example, when the network is the Ethernet (registered trademark), the packet received by the packet transmission / reception block 5 is shaped as an Ethernet (registered trademark) frame (in the present specification, these are collectively referred to as a packet), and then a search key. It outputs to the extraction block 4 (step A1).

When receiving a packet from the packet transmission / reception block 5, the search key extraction block 4 extracts a predetermined field as a search key in the flow search process from the packet header information, and uniquely identifies the packet within the apparatus. A possible identifier is assigned and written in the FIFO included in the search key extraction block 4 (step A2). Here, as a field of the packet header used as a search key, for example, a source IP address (32 bits), a destination IP address (32 bits), a protocol number (8 bits), and a TCP / UDP header defined in the IP header are defined. A set of five fields of a transmission port number (16 bits) and a destination port number (16 bits) are used, and the length of the search key in this case is 104 bits (= 13 bytes).

Next, the search key extraction block 4 generates and issues an event for notifying the multi-core CPU 1 of packet reception, writes it in the event queue, and writes the corresponding packet in the main memory 6 (step A3). The event generated here only needs to include the extracted search key information and the identifier of the corresponding packet. When the event queue is configured in the main memory 6, for example, the event is written in the event queue in the main memory 6. . When the event queue is configured in the main memory 6, the event queue area for the multi-core CPU 1 and the area for writing packet data are logically separated, and the base address is known to the multi-core CPU 1. Shall.

On the other hand, the multi-core CPU 1 monitors whether there is an event in the event queue by polling. If there is an event in the event queue, the multi-core CPU 1 reads the leading event and performs flow search processing by a specific processor core. Perform (Step A4).

FIG. 3 is a flowchart for explaining the detailed operation of step A4.

When there is an event in the event queue, the multi-core CPU 1 reads the top event and assigns it to a specific processor core (step B1). Here, in a CPU having a plurality of processor cores such as the multi-core CPU 1, a specific processor core, for example, the processor core 1-1 performs processing specialized for polling, and after reading an event from the event queue, the processing A method of assigning to another free processor core that has not been performed is conceivable. In addition, there is a method in which each processor core collects an event by polling the event queue. In the latter case, since each processor core accesses a memory area where the same event queue exists, arbitration between these processor cores is necessary. In this embodiment, an existing method is used for such event reading processing, and each processor core (a processor core other than this when a specific processor core performs processing specialized for polling) It suffices if events are assigned on average. Hereinafter, for simplification, the processor core 1-k (k = 1,..., N) is assumed as the processor core to which the event is assigned, and the processing of the processor core 1-k will be described.

The processor core 1-k to which the event is assigned calculates a hash value using a preset hash function for the search key stored in the event (step B2). Here, since the hash function and the hash value are well known to those skilled in the art, a detailed description thereof will be omitted.

Subsequently, the processor core 1-k reads the entry from the flow table (step B4) using the calculated hash value as an address value (step B3). FIG. 4 shows an example of a flow table configured in the shared memory 1-0. The flow table is configured based on a hash table, and a plurality of entries having the same hash value are connected in a bidirectional list. One entry holds a search key, a flow ID for specifying a flow, an address value serving as a pointer to the next entry in the list, and a pointer to the previous entry in the list. However, if the sum of the search key of the entry shown in FIG. 4, the flow ID, the pointer to the next entry, and the data length of the pointer to the previous entry is longer than the word length of the shared memory 1-0, it is continuous. An entry is composed of a plurality of words. For example, the address value means a logical address value indicating the first word of each entry, such as ignoring the lower bits of the bit length of the physical address. And Entries are basically added to the free space and managed by a bidirectional list. On the other hand, when an entry is added to an address value for which an entry is already managed, that is, a hash value, the priority of the entry having the address value of the entry as a hash value is higher, and the already managed entry is Assume that it is moved to another free area. Note that FIG. 4 is merely an example, and in consideration of the occurrence of a collision, the hash value may be calculated in a range smaller than the logical address space indicating the first word of the entry. The flow table may be configured according to the configuration of the hash table. In addition, when a flow table is configured such that the entry storage location does not move, an address value can be used for the flow ID that identifies the flow, so there is no need to hold the flow ID in the entry.

The processor core 1-k that has read the entry from the flow table determines whether the search key of the read entry matches the search key of the event (step B5). The ID is acquired (step B6), and the flow search process (step A4) is terminated. If they do not match, it is confirmed whether there is a next entry connected by a link (step B7). If there is a next entry, the next pointer of the entry is used as an address value (step B8), and the next The flow search process is performed by repeating the process of reading the entry (step B4). If the next entry does not exist, the corresponding flow is not registered. As a result, it is determined that the flow is not registered (step B9), and the flow search process (step A4) is terminated.

Finally, the corresponding processor core 1-k outputs the result obtained in the flow search process (step A4) (step A5). Here, since the flow search processing is generally performed to identify a flow to which a packet belongs, such as QoS processing, and to perform individual processing on the flow, a processing block for performing these processing, a CPU Or the like is provided via the bus 3 or by some communication means. Since this embodiment focuses on the flow search processing, these processing blocks are omitted, but as a result output destination in step A5, individual processing is performed for each such flow. Assume output to processing block. In the above description, if there is no entry having a matching search key, it is determined that the flow has not been registered, and the process ends. However, a process for registering the flow as a new flow may be performed. Similarly, it is possible to delete a flow that has already been registered as an entry. However, since these processes largely depend on the configuration of a hash table that is a flow table, the details thereof are omitted.

Further, after performing some processing in the processing block that performs individual processing for each flow, the search key extraction block 4 reads and reads the packet from the main memory 6 for processing when the packet is transmitted. It is assumed that the packet data is output to the packet transmission / reception block 5 and the packet transmission / reception block 5 that has received the packet data transmits the packet. However, in this embodiment, attention is paid to the flow search process, and the details are omitted.

Alternatively, in the present embodiment, the packet itself is received from the network by the packet transmission / reception block 5, but only the packet header is input to the flow search device shown in the present embodiment. Is also envisaged. In this case, the packet transmission / reception block 5 receives a packet header input from the outside and outputs it to the search key extraction block 4. Upon receiving the packet header, the search key extraction block 4 extracts a set of fields serving as a search key from the packet header, and generates and issues an event. In this case, since the payload data of the packet is not received, it is not necessary to write the packet data to the main memory 6.

Furthermore, in the present embodiment, it is assumed that the event queue for the multi-core CPU 1 is configured in the main memory 6, but this event queue is logically different from the flow table in the shared memory 1-0 in the multi-core CPU 1. The event may be written directly to the event queue in the shared memory 1-0 from the search key extraction block 4 or may be configured using a specific memory or register in the search key extraction block. It doesn't matter. In any case, there is no problem as long as it is an area that can be specified on the address space that can be viewed from the multi-core CPU 1.

Finally, an outline of the processing in the present embodiment described above will be described with reference to FIG. As shown in FIG. 5, when the packets pkt1, pkt2,... Arrive, the search keys Key # 1, Key # 2,. A search key is assigned to a plurality of processor cores in the multi-core CPU, and a flow search process is performed. Here, as a method of assigning to a plurality of processor cores in the multi-core CPU, a method of sequentially assigning by a technique such as round-robin is conceivable, but is not limited thereto.

Next, the function and effect of the first embodiment of the present invention will be described.

As described above, in the present embodiment, the search key extraction block extracts a set of fields as a search key from the header information of the packet in advance, and notifies the processor core of the set to store in the main memory. Since there is no need to read the packet header, the processing performance of the flow search can be improved.

Also, in this embodiment, the flow table is configured on a shared memory shared by a plurality of processor cores in the multi-core CPU, so that reading of entries is performed more than when the flow table is configured on a main memory such as a DRAM. As a result, the processing latency related to the flow search process can be improved.

From the above, it is possible to provide a pattern matching system capable of realizing a pattern matching process having a high-speed search performance corresponding to the network bandwidth.

Next, a second embodiment of the present invention will be described in detail with reference to the drawings.
<Embodiment 2>
FIG. 6 is a block diagram showing the configuration of the second exemplary embodiment of the present invention. Referring to FIG. 6, the second embodiment of the present invention relates to a multi-core CPU 1, multi-core CPU 2,..., Multi-core CPU M, a packet transmission / reception block 5 for transmitting / receiving packets, and a flow search process from received packets. The search key extraction block 4 that extracts header information as a search key, generates and issues a packet reception event, and writes the packet to the main memory, and a main body such as a DRAM in which the packet reception event and the packet itself are written if necessary. The memory 6 includes a multi-core CPU 1, a multi-core CPU 2,..., A multi-core CPU M, a search key extraction block 4, and a bus 3 to which the main memory 6 is connected. This embodiment is the same as the first embodiment except that multi-core CPUs 2,..., Multi-core CPUM are added to the first embodiment shown in FIG.

The multi-core CPU 2 has the same form as the multi-core CPU 1, and the N processor cores 2-1, 2-2,..., 2-N and the shared memory 2-0 shared by the N processor cores The shared memory 2-0 holds a flow table configured as a hash table. Such a configuration is the same for other multi-core CPUs, and all the flow tables configured in the shared memory in each multi-core CPU have the same flow table. When the shared memory is used as a data cache, the flow table is held in an area logically separated from the data cache.

As shown in FIG. 6, in the present embodiment, as in the first embodiment, the multi-core CPU 1, the multi-core CPU 2,..., The multi-core CPU M, the search key extraction block 4, and the main memory 6 are connected via the bus 3. Although this is a form of bus connection, this connection form may be a form connected through a chip set called North Bridge or South Bridge provided in a server or the like, a form of a crossbar, or a ring bus. Further, the present embodiment may be configured on a motherboard such as a server, or may be configured on one chip as a single SoC except for the main memory 6.

Next, the operation of the second exemplary embodiment of the present invention will be described in detail with reference to the flowcharts of FIGS.

The flowchart of FIG. 7 is a modification of the flowchart of the first embodiment, in which step A3 is replaced with step A6 and step A5 is replaced with step A7. Since other steps are the same as those in the first embodiment, detailed description thereof is omitted.

The search key extraction block 4 receives a packet input from the network via the packet transmission / reception block 5 (step A1), and performs processing for step A2 such as search key extraction.

Next, the search key extraction block 4 generates and issues an event for notifying one of a plurality of multi-core CPUs of packet reception, writes it in the event queue, and writes the corresponding packet in the main memory 6 ( Step A6). Here, the generated event only needs to include the extracted search key information and the identifier of the packet, as in the first embodiment. For example, when the event queue is configured in the main memory 6, the event queue is written in the event queue of the main memory 6, but the event queue for each multi-core CPU writes the event queue area of each multi-core CPU and packet data. It is assumed that the areas are logically separated, and the base address of the event queue area for each multi-core CPU is known to each multi-core CPU. The event is issued only to one of the plurality of multi-core CPUs, and the selection of the multi-core CPU that issues the event is performed in order to smooth the flow search process for each multi-core CPU, for example. A method using the Round-Robin method such as the multi-core CPU 1, the multi-core CPU 2,..., The multi-core CPU M, the multi-core CPU 1, and so on is conceivable, but is not limited thereto.

On the other hand, each of the M multi-core CPUs monitors whether there is an event in its own event queue by polling. If there is an event in the event queue, the M multi-core CPU reads the first event and has its own A flow search process is performed by a specific processor core (step A4). Here, step A4 is a process performed independently by each multi-core CPU, and the contents of each process are the same as those in the first embodiment, and thus detailed description thereof is omitted here.

Finally, the processor core in each multi-core CPU that has performed the actual flow search process outputs the result obtained there (step A7). In the first embodiment, a plurality of processor cores in one multi-core CPU perform this processing, but here, among the plurality of processor cores in the plurality of multi-core CPUs, the flow search processing is actually performed. This is different from step A5 in the first embodiment in that the processor core outputs the result. The other processing contents of step A7 are the same as those of step A5, so the details are omitted.

In this embodiment, the flow table configured in the shared memory in each multi-core CPU has the same contents in all multi-core CPUs. For this reason, if the process of registering an unregistered flow as a new flow is performed, the contents of the flow table updated in the processor core in a certain multi-core CPU are updated to the flow tables in other multi-core CPUs. There is a need to do.

In the present embodiment, the packet itself is received from the network by the packet transmission / reception block 5, but the processing when only the packet header is input is the same as in the first embodiment. The event queue components (main memory 6, shared memory in each multi-core CPU, specific memory in the search key extraction block 4, registers, etc.) are also the same as those in the first embodiment. Is omitted.

Finally, an outline of the processing in the present embodiment described above will be described with reference to FIG. As shown in FIG. 8, in the flow search process using this embodiment, when packets pkt1, pkt2,... Arrive, search keys Key # 1, Key # 2,. A search key is sent to one of a plurality of multi-core CPUs. Each transmitted search key is assigned to one of a plurality of processor cores in each multi-core CPU, and a flow search process is performed by the processor core in each multi-core CPU. Here, as a method for assigning to a plurality of processor cores in each multi-core CPU, for example, a method such as Round-Robin may be used, but the method is not limited to this.

Next, the function and effect of the second embodiment of the present invention will be described.

As described above, in this embodiment, in addition to the operation and effect in the first embodiment, there are a plurality of multi-core CPUs, and the flow search process is distributed to each multi-core CPU. The processing performance of the flow search can be further improved according to the increased number of multi-core CPUs. In addition, since distributed processing can be performed for a plurality of multi-core CPUs, the frequency of contention for access to the shared memory among the plurality of processor cores in one multi-core CPU is reduced, and more efficient flow search processing is performed. Is possible.

Next, a third embodiment of the present invention will be described in detail with reference to the drawings.
<Embodiment 3>
FIG. 9 is a block diagram showing the configuration of the third exemplary embodiment of the present invention. Referring to FIG. 9, the third embodiment of the present invention relates to a multi-core CPU 1, a multi-core CPU 2,..., A multi-core CPU M, a packet transmission / reception block 5 for transmitting / receiving packets, and a flow search process from received packets. The header information as a search key is extracted, the packet reception event is generated and issued, the search key extraction block 4 for writing the packet to the main memory, and the results of the individual flow search processes in a plurality of multi-core CPUs are collected. Final result determination block 7 for selecting a typical flow search processing result, a main memory 6 such as a DRAM in which a packet reception event or a packet itself is written if necessary, a multicore CPU1, a multicore CPU2,..., A multicore CPUM, Search key extraction block 4, main Mori 6, including the final result decision block 7 and the bus 3 connected respectively. This embodiment is the same as the second embodiment except that a final result determination block 7 is added to the second embodiment shown in FIG.

In the second embodiment, the same flow table is configured for all the shared memories in each multi-core CPU, but in this embodiment, one of the original flow tables divided into M pieces is used. A flow table is configured. When the shared memory is used as a data cache, the flow table is held in an area logically separated from the data cache. FIG. 10 is a diagram illustrating an example of the division of the flow table in the present embodiment. As shown in FIG. 10, in the present embodiment, one original flow table is divided into M pieces, and each sub-flow table k (k = 1,..., M) is divided into multi-core CPUk (k = 1). ,..., M). Each subflow table is basically a flow table based on a hash table, as in the first and second embodiments, so description of the contents of each entry is omitted, but each subflow table is The table is completely independent. That is, a flow for a hash value assigned to one subflow table is stored in an empty entry area in the same subflow table. For this reason, when the hash value is calculated in a range smaller than the logical address space indicating the first word of the entry in consideration of the occurrence of the collision, the above holds in each subflow table. Must be configured. Supplementary information is as follows.

For example, considering the occurrence of a collision in the original flow table, the hash value is calculated in a range smaller than the logical address space indicating the first word of the entry, and the entry in the area that cannot be specified by the hash value is the address value. If this table is divided into subflow tables when located in a large area, the entry area that cannot be specified by the hash value is biased to the Mth subflow table or the like. In this case, in the subflow table having only the entry area that can be specified by the hash value, collisions frequently occur, and conversely, the subflow table having many entry areas that cannot be specified by the hash value or only the entry area that cannot be specified. Thus, the entry area cannot be used up effectively, and an efficient flow table cannot be constructed. For this reason, it is necessary to secure an entry area in consideration of collision for each subflow table.

As shown in FIG. 9, the present embodiment is similar to the first and second embodiments in that the multi-core CPU 1, the multi-core CPU 2,..., The multi-core CPU M, the search key extraction block 4, the main memory 6, and the final The result determination block 7 is connected to the bus 3 by a bus 3, but this connection form is connected through a chip set called North Bridge or South Bridge provided in a server or the like, a crossbar, or a ring bus. It does not matter in the form. Further, the present embodiment may be configured on a motherboard such as a server, or may be configured on one chip as a single SoC except for the main memory 6.

Next, the operation of the third exemplary embodiment of the present invention will be described in detail with reference to the flowcharts of FIG. 9 and FIG.

The flowchart of FIG. 11 is a modification of the flowchart of the second embodiment shown in FIG. 7, in which step A6 is replaced with step A8, and step A7 is replaced with step A10, and flow search processing (step A4) and result output are performed. A final result determination step (step A9) is added between the steps (step A10). Since other steps are the same as those in the first and second embodiments, detailed description thereof is omitted.

The search key extraction block 4 receives a packet input from the network via the packet transmission / reception block 5 (step A1), and performs processing for step A2 such as search key extraction.

Next, the search key extraction block 4 generates and issues an event for notifying all of the plurality of multi-core CPUs of packet reception, writes the event in the event queue, and writes the corresponding packet in the main memory 6 (step A8). . Here, the information on the event to be generated and the event queue for each multi-core CPU are the same as those in the second embodiment, and thus the details are omitted.

On the other hand, each of the M multi-core CPUs monitors whether there is an event in its own event queue by polling. If there is an event in the event queue, the M multi-core CPU reads the first event and has its own A flow search process is performed by a specific processor core (step A4). Here, step A4 is a process performed independently by each multi-core CPU, and the contents of each process are the same as those in the first and second embodiments, and thus detailed description thereof is omitted here.

Among the plurality of processor cores in each multi-core CPU, the processor core that has performed the flow search process outputs the result obtained there and the identifier for identifying the processed packet to the final result determination block 7. When all (M) search results for the same packet for which the M multi-core CPUs have performed the flow search processing are prepared, the final result determination block 7 checks whether there is a result of which the flow ID can be specified. If it can be specified, the result is output as the final result. On the other hand, if all the search results cannot identify the flow ID, the final result is output as an unregistered flow (step A9, step A10). Note that the output destination of this final result is the same as in the first and second embodiments, and details thereof are omitted. Furthermore, in the above, the final result is confirmed and determined when all the search results from the M multi-core CPUs are prepared. However, a variable, a register, or the like that can specify the final result for the packet to be processed is prepared. A method of sequentially checking the results every time search results from the multi-core CPU are returned may be used.

In the present embodiment, all the subflow tables configured in the shared memory in each multi-core CPU have independent contents. For this reason, if the final result determination block 7 performs processing for registering an unregistered flow for which a flow ID could not be specified as a new flow, an appropriate subflow table among the subflow tables in each multi-core CPU is used. Processing to perform flow registration is required.

In the present embodiment, the packet itself is received from the network by the packet transmission / reception block 5, but the processing when only the packet header is input is the same as in the first embodiment. The event queue components (main memory 6, shared memory in each multi-core CPU, specific memory in the search key extraction block 4, registers, etc.) are also the same as in the first and second embodiments. Therefore, details are omitted.

Finally, an outline of the processing in the present embodiment described above will be described with reference to FIG. As shown in FIG. 12, in the flow search process according to the present embodiment, when packets pkt1, pkt2,... Arrive, search keys Key # 1, Key # 2,. Is sent to all multi-core CPUs. Each sent search key is assigned to one of a plurality of processor cores in each multi-core CPU, a flow search process is performed by the processor core in each multi-core CPU, and finally a final result is determined by a final result determination block. Will be determined. Here, for example, a technique such as Round-Robin may be used for allocation to a plurality of processor cores in each multi-core CPU, but the present invention is not limited to this.

Next, the function and effect of the third embodiment of the present invention will be described.

As described above, in the present embodiment, unlike the second embodiment, the flow tables existing in a plurality of multi-core CPUs all have independent contents. For this reason, distributed processing cannot be performed for a plurality of multi-core CPUs, but in addition to the effects of the first embodiment, the number of flow entries in the second embodiment is M times, and more flows are registered. It becomes possible to manage and search.

Next, a fourth embodiment of the present invention will be described in detail with reference to the drawings.
<Embodiment 4>
FIG. 13 is a block diagram showing the configuration of the fourth exemplary embodiment of the present invention. Referring to FIG. 13, the fourth embodiment of the present invention relates to a multi-core CPU 1, a multi-core CPU 2,..., A multi-core CPU M, a packet transmission / reception block 5 for transmitting / receiving packets, and a flow search process from received packets. A search key extraction block 8 for extracting header information serving as a search key; a hash value calculation block 9 for calculating a hash value for the extracted search key, generating and issuing a packet reception event, and writing the packet to the main memory; A main memory 6 such as a DRAM in which a packet reception event or a packet itself is written as necessary, a multi-core CPU 1, a multi-core CPU 2,..., A multi-core CPU M, a search key extraction block 8, a hash value calculation block 9, and a main memory 6 Each connected bus Including a 3 and. This embodiment is different from the third embodiment shown in FIG. 9 except that the final result determination block 7 is changed, the search key extraction block 4 is changed to a search key extraction block 8, and a hash value calculation block 9 is added. The others are the same as those of the second embodiment.

Also, in the shared memory in each multi-core CPU in the present embodiment, one flow table of the original flow table divided into M pieces is configured as in the third embodiment. Since this flow table is the same as that of the third embodiment, detailed description thereof is omitted.

In FIG. 13, as in the first, second, and third embodiments, the multi-core CPU 1, the multi-core CPU 2,..., The multi-core CPU M, the hash value calculation block 9, and the main memory 6 are connected by the bus 3. However, this connection form may be a form connected through a chip set called North Bridge or South Bridge provided in a server or the like, a form of a crossbar, or a ring bus. Further, the present embodiment may be configured on a motherboard such as a server, or may be configured on one chip as a single SoC except for the main memory 6.

Next, the operation of the third exemplary embodiment of the present invention will be described in detail with reference to the flowcharts of FIGS.

Step A1 and step A2 in the flowchart of FIG. 13 are the same as step A1 and step A2 in the first, second, and third embodiments, and thus detailed description is omitted, but the packet transmission / reception block 5 (step Via A1), the search key extraction block 8 receives a packet input from the network and performs processing for step A2 such as search key extraction.

Next, the search key extraction block 8 outputs the extracted search key and the packet received from the packet transmission / reception block 5 to the hash value calculation block 9, and the hash value calculation block 9 calculates a hash value for the received search key. (Step A11). Here, the hash value calculated in the hash value calculation block 9 is the same as the hash value calculation (step B2) in the flow search process (step A4) in the first, second, and third embodiments. Detailed description is omitted.

When the hash value calculation block 9 calculates the hash value, the hash value calculation block 9 generates and issues an event for notifying one of the multi-core CPUs of packet reception, writes the event to the event queue, and stores the corresponding packet in the main Write to the memory 6 (step A12). Here, the event to be generated only needs to include the value of the calculated hash value in addition to the extracted search key information and the corresponding packet identifier. For the configuration of the event queue for each multi-core CPU, This is the same as in the third embodiment.

The event generated and issued by the hash value calculation block 9 is one of M multi-core CPUs. A method of selecting a multi-core CPU that issues this event will be described below. As described above, the multi-core CPU according to the present embodiment configures one of the original flow tables into M sub-flow tables on the shared memory as in the third embodiment. Yes. In the hash value calculation block 9, a base address included in each subflow table is set in advance. Therefore, when the hash value calculation block 9 calculates the hash value, the hash value calculation block 9 may determine in which subflow table of the M multi-core CPUs the entry group corresponding to the hash value is registered. It becomes possible. The hash value calculation block 9 issues a packet reception event to the multi-core CPU in which the entry group corresponding to the hash value is registered according to the calculated hash value.

On the other hand, each of the M multi-core CPUs monitors whether there is an event in its own event queue by polling. If there is an event in the event queue, the M multi-core CPU reads the first event and has its own A flow search process is performed by a specific processor core (step A13).

FIG. 15 is a flowchart for explaining more detailed operation of step A13. This flow search process is a process common to the processor cores that perform the flow search process in the M multi-core CPUs, and will be described below as a process for any processor core in any multi-core CPU.

Referring to FIG. 15, the flow search process (step A13) in the present embodiment is a hash value calculation process (step A4) of the flow search processes (step A4) in the first, second, and third embodiments. This is a processing flow excluding B2). As described above, the received event includes the hash value calculated in the hash value calculation block 9. In the flow search process in the present embodiment, processing is performed using the hash value included in the received event as the hash value that should be calculated in step B2 in the first, second, and third embodiments. The other detailed processing in the flow search processing (step A13) in the present embodiment is the same as the flow search processing (step A4) in the first, second, and third embodiments, and thus detailed description thereof. Is omitted.

When the flow search process (step A13) ends, the processor core outputs the result (step A7). Since this result output step A7 is the same as that of the second embodiment, detailed description thereof is omitted. In the present embodiment, the subflow tables configured in the shared memory in each multi-core CPU all have independent contents. For this reason, if processing for registering an unregistered flow for which a flow ID could not be specified as a new flow is performed, it is necessary to perform flow registration processing. Unlike the third embodiment, one packet Since the flow search process is performed only on one processor core of one multi-core CPU, it is a registration process independent of each multi-core CPU.

In the present embodiment, the packet itself is received from the network by the packet transmission / reception block 5, but the processing when only the packet header is input is the same as in the first embodiment. . Further, the event queue for each multi-core CPU is configured in an area logically separated from the flow table in the shared memory in each multi-core CPU, and events are directly sent from the hash value calculation block 9 to the event queue in the shared memory. You may write in and you may comprise using the memory in the specific in the hash value calculation block 9, and a register | resistor. In any case, there is no problem as long as it is an area that can be specified as an event queue for its own multi-core CPU in an address space that can be viewed from each multi-core CPU.

Finally, an outline of processing in the present embodiment described above will be described with reference to FIG. Flow search processing using this embodiment, as shown in FIG. 16, when packets pkt1, pkt2,... Arrive, search keys Key # 1, Key # 2,. Calculate a hash value for the key. Subsequently, according to the calculated hash value, the search key and the hash value are sent to the multi-core CPU in which the entry group for the hash value is registered. The transmitted search key and hash value are assigned to one of a plurality of processor cores in each multi-core CPU, and flow search processing is performed by the processor core in each multi-core CPU. Here, for example, a technique such as Round-Robin may be used for allocation to a plurality of processor cores in each multi-core CPU, but the present invention is not limited to this.

Next, the function and effect of the fourth embodiment of the present invention will be described.

As described above, in the present embodiment, as in the third embodiment, all the flow tables in each multi-core CPU have independent contents. For this reason, it is possible to register, manage, and search more flows. In this embodiment, the hash value is calculated not in each processor core but in the hash value calculation block, and a multi-core CPU having a flow table to be subjected to a flow search process according to the calculated hash value is specified. Is possible. Therefore, unlike the third embodiment, there is no need to perform flow search processing with one processor core in all multi-core CPUs, and the flow search processing is efficiently distributed to a plurality of processor cores. Therefore, the performance of the flow search process is improved.

A part or all of the above embodiment can be described as in the following supplementary notes, but is not limited to the following.
(Supplementary Note 1) In a multi-core processor environment having a multi-core CPU composed of a plurality of processor cores and a shared memory shared among those processor cores existing in the same CPU,
Configure a pattern table with search patterns on shared memory,
A pattern matching method, wherein a pattern matching process for a search key to be searched is executed in parallel by a plurality of processor cores.

(Supplementary note 2) The pattern matching method according to supplementary note 1, wherein the pattern table is configured as a hash table.

(Appendix 3) Send and receive packets,
Extract a set of arbitrary fields that are search keys from the header information of the received packet, generate and issue a packet reception event, and store the packet data in the main memory,
The pattern matching method according to appendix 1 or appendix 2, wherein pattern matching processing is performed by one multi-core CPU.

(Appendix 4) Generate and issue a packet reception event including the extracted search key,
Sequentially assigns received packet reception events to one of a plurality of processor cores of the multi-core CPU;
4. The pattern matching method according to appendix 3, wherein pattern matching processing is performed by a processor core to which a packet reception event is assigned.

(Appendix 5) Sending and receiving packets
Extract a set of arbitrary fields that are search keys from the header information of the received packet, generate and issue a packet reception event, and store the packet data in the main memory,
Configure the same pattern table on the shared memory of multiple multi-core CPUs,
The pattern matching method according to appendix 1 or appendix 2, wherein pattern matching processing is performed by one of a plurality of multi-core CPUs.

(Appendix 6) Generate a packet reception event including the extracted search key,
The pattern matching method according to appendix 5, wherein the generated packet reception event is sequentially issued to one of a plurality of multi-core CPUs.

(Supplementary Note 7) In the multi-core CPU that has received the packet reception event,
The pattern matching method according to claim 6, wherein the received packet reception event is sequentially assigned to one of a plurality of processor cores of the multi-core CPU.

(Appendix 8) Send and receive packets
Extract a set of arbitrary fields that are search keys from the header information of the received packet, generate and issue a packet reception event, and store the packet data in the main memory,
On one shared memory of a plurality of multi-core CPUs, one of the sub-pattern tables obtained by dividing the pattern table into the same number as the multi-core CPUs is configured.
Perform pattern matching on all of the multi-core CPUs.
The pattern matching method according to Supplementary Note 1 or Supplementary Note 2, wherein results of pattern matching performed in a plurality of processor cores in each multi-core CPU are collected and a final pattern matching result is determined.

(Appendix 9) Generate a packet reception event including the extracted search key,
The pattern matching method according to appendix 8, wherein the generated packet reception event is issued to all of the plurality of multi-core CPUs.

(Supplementary Note 10) In the plurality of multi-core CPUs,
The pattern matching method according to appendix 9, wherein the received packet reception event is sequentially assigned to one of a plurality of processor cores of the multi-core CPU.

(Appendix 11) Sending and receiving packets,
Extract any set of fields that will be the search key from the header information of the received packet,
The hash value for the extracted search key is calculated, a packet reception event is generated and issued, and the packet data is stored in the main memory.
On one shared memory of a plurality of multi-core CPUs, one of the sub-pattern tables obtained by dividing the pattern table into the same number as the multi-core CPUs is configured.
The pattern matching method according to appendix 1 or appendix 2, wherein pattern matching processing is performed by one of a plurality of multi-core CPUs.

(Supplementary Note 12) Generate a packet reception event including the extracted search key and the calculated hash value,
12. The pattern matching method according to appendix 11, wherein the generated packet reception event is issued to a multi-core CPU having a sub-pattern table that holds an entry group corresponding to the calculated hash value.

(Additional remark 13) In multi-core CPU which received the said packet reception event,
The pattern matching method according to appendix 12, wherein the received packet reception event is sequentially assigned to one of a plurality of processor cores of the multi-core CPU.

(Supplementary Note 14) In a multi-core processor environment having a multi-core CPU including a plurality of processor cores and a shared memory shared between the processor cores existing in the same CPU,
The shared memory includes a pattern table including a search pattern,
A pattern matching apparatus that performs a pattern matching process on a search key to be searched by the plurality of processor cores in parallel.

(Supplementary note 15) The pattern matching device according to Supplementary note 14, wherein the pattern table is configured as a hash table.

(Supplementary Note 16) One multi-core CPU;
A packet transmission / reception block for transmitting and receiving packets;
A search key extraction block for extracting a set of arbitrary fields to be a search key from the header information of the received packet, generating and issuing a packet reception event, and storing the packet data in the main memory;
Main memory for storing packet data;
The pattern matching device according to appendix 14 or appendix 15, further comprising: a bus connecting the multi-core CPU, a search key extraction block, and a main memory.

(Supplementary Note 17) Generate and issue a packet reception event including the extracted search key,
The pattern matching apparatus according to appendix 16, wherein packet reception events are sequentially assigned to one of a plurality of processor cores included in the multi-core CPU.

(Supplementary Note 18) a plurality of multi-core CPUs;
A packet transmission / reception block for transmitting and receiving packets;
A search key extraction block for extracting a set of arbitrary fields to be a search key from the header information of the received packet, generating and issuing a packet reception event, and storing the packet data in the main memory;
Main memory for storing packet data;
A plurality of multi-core CPUs, a search key extraction block, and a bus connecting the main memory;
The pattern matching apparatus according to appendix 14 or appendix 15, wherein the same pattern table is configured on a shared memory of a plurality of multi-core CPUs.

(Supplementary note 19) Generate a packet reception event including the extracted search key,
The pattern matching apparatus according to appendix 18, wherein the packet reception event is issued to one of a plurality of multi-core CPUs.

(Supplementary Note 20) The multi-core CPU that has received the packet reception event
The pattern matching apparatus according to appendix 19, wherein the received packet reception event is sequentially assigned to one of a plurality of processor cores of the multi-core CPU.

(Supplementary note 21) a plurality of multi-core CPUs;
A packet transmission / reception block for transmitting and receiving packets;
A search key extraction block for extracting a set of arbitrary fields to be a search key from the header information of the received packet, generating and issuing a packet reception event, and storing the packet data in the main memory;
Main memory for storing packet data;
A final result determination block for collecting pattern matching results in a plurality of processor cores in each multi-core CPU and determining a final pattern matching result;
A plurality of multi-core CPUs, a search key extraction block, a main memory, and a bus connecting the final result determination block;
The pattern matching apparatus according to appendix 14 or appendix 15, wherein one of the sub-pattern tables obtained by dividing the pattern table into the same number as the multi-core CPU is configured on the shared memory of the plurality of multi-core CPUs. .

(Appendix 22) Generate a packet reception event including the extracted search key,
The pattern matching apparatus according to appendix 21, wherein the generated packet reception event is issued to all of the plurality of multi-core CPUs.

(Supplementary Note 23) The plurality of multi-core CPUs are:
The pattern matching apparatus according to appendix 22, wherein the received packet reception event is sequentially assigned to one of a plurality of processor cores of the multi-core CPU.

(Supplementary Note 24) a plurality of multi-core CPUs;
A packet transmission / reception block for transmitting and receiving packets;
A search key extraction block that extracts a set of arbitrary fields as search keys from the header information of the received packet;
A hash value calculation block for calculating a hash value for the extracted search key, generating and issuing a packet reception event, and storing packet data in the main memory;
Main memory for storing packet data;
A plurality of multi-core CPUs, a search key extraction block, a hash value calculation block, and a bus connecting the main memory;
The pattern matching apparatus according to appendix 14 or appendix 15, wherein one of the sub-pattern tables obtained by dividing the pattern table into the same number as the multi-core CPU is configured on the shared memory of the plurality of multi-core CPUs. .

(Supplementary Note 25) Generate a packet reception event including the extracted search key and the calculated hash value,
25. The pattern matching apparatus according to appendix 24, wherein the generated packet reception event is issued to a multi-core CPU having a sub-pattern table that holds an entry group corresponding to the calculated hash value.

(Supplementary Note 26) The multi-core CPU that has received the packet reception event
26. The pattern matching apparatus according to appendix 25, wherein received packet reception events are sequentially assigned to one of a plurality of processor cores of the multi-core CPU.

Although representative embodiments of the present invention have been described in detail, various changes, substitutions and alternatives may be made without departing from the spirit and scope of the invention as defined in the claims. It should be understood. In addition, the inventors intend that the equivalent scope of the claimed invention will be maintained even if it is amended in the claim place application procedure.

This application claims priority based on Japanese Patent Application No. 2009-289011 filed on Dec. 21, 2009, the entire disclosure of which is incorporated herein.

As an application example of the present invention, a network device such as a switch or a router that identifies a flow to which a packet belongs from a header set of the packet by a specific field set and performs a specific process for each flow such as QoS processing or load distribution And an appliance device such as a load balancer.

1 Multi-core CPU
2 Multi-core CPU
3 Bus 4 Search key extraction block 5 Packet transmission / reception block 6 Main memory 7 Final result determination block 8 Search key extraction block 9 Hash value calculation block 10 Packet transmission / reception block 11 CPU
12 Multi-core CPU
13 Multi-core CPU
M multi-core CPU
1-0 shared memory 1-1, 1-2, 1-N processor core 2-0 shared memory 2-1, 2-2, 1-N processor core 11-0 L2 cache 11-1 processor core 12-0 L2 Cache 12-1, 12-2 Processor core 13-0 L2 cache 13-1, 13-2 Processor core M-0 Shared memory M-1, M-2, MN Processor core

Claims (14)

In a multi-core processor environment having a multi-core CPU having a plurality of processor cores and a shared memory shared among those processor cores existing in the same CPU,
The shared memory includes a pattern table including a search pattern,
A pattern matching apparatus that performs a pattern matching process on a search key to be searched by the plurality of processor cores in parallel. The pattern matching apparatus according to claim 1, wherein the pattern table is configured as a hash table. One multi-core CPU;
A packet transmission / reception block for transmitting and receiving packets;
A search key extraction block for extracting a set of arbitrary fields to be a search key from the header information of the received packet, generating and issuing a packet reception event, and storing the packet data in the main memory;
Main memory for storing packet data;
The pattern matching apparatus according to claim 1, further comprising: a bus that connects the multi-core CPU, a search key extraction block, and a main memory. Generate and issue a packet reception event that includes the extracted search key,
The pattern matching apparatus according to claim 3, wherein the packet reception event is sequentially assigned to one of a plurality of processor cores included in the multi-core CPU. A plurality of multi-core CPUs;
A packet transmission / reception block for transmitting and receiving packets;
A search key extraction block for extracting a set of arbitrary fields to be a search key from the header information of the received packet, generating and issuing a packet reception event, and storing the packet data in the main memory;
Main memory for storing packet data;
A plurality of multi-core CPUs, a search key extraction block, and a bus connecting the main memory;
The pattern matching apparatus according to claim 1, wherein the same pattern table is configured on a shared memory included in a plurality of multi-core CPUs. Generate a packet reception event that includes the extracted search key,
The pattern matching apparatus according to claim 5, wherein the packet reception event is issued to one of a plurality of multi-core CPUs. The multi-core CPU that has received the packet reception event,
The pattern matching apparatus according to claim 6, wherein the received packet reception event is sequentially allocated to one of a plurality of processor cores included in the multi-core CPU. A plurality of multi-core CPUs;
A packet transmission / reception block for transmitting and receiving packets;
A search key extraction block for extracting a set of arbitrary fields to be a search key from the header information of the received packet, generating and issuing a packet reception event, and storing the packet data in the main memory;
Main memory for storing packet data;
A final result determination block for collecting pattern matching results in a plurality of processor cores in each multi-core CPU and determining a final pattern matching result;
A plurality of multi-core CPUs, a search key extraction block, a main memory, and a bus connecting the final result determination block;
3. The pattern according to claim 1, wherein one of the sub-pattern tables obtained by dividing the pattern table into the same number as the multi-core CPU is configured on the shared memory of the plurality of multi-core CPUs. Matching device. Generate a packet reception event that includes the extracted search key,
The pattern matching apparatus according to claim 8, wherein the generated packet reception event is issued to all of the plurality of multi-core CPUs. The plurality of multi-core CPUs are:
The pattern matching apparatus according to claim 9, wherein the received packet reception event is sequentially assigned to one of a plurality of processor cores of the multi-core CPU. A plurality of multi-core CPUs;
A packet transmission / reception block for transmitting and receiving packets;
A search key extraction block that extracts a set of arbitrary fields as search keys from the header information of the received packet;
A hash value calculation block for calculating a hash value for the extracted search key, generating and issuing a packet reception event, and storing packet data in the main memory;
Main memory for storing packet data;
A plurality of multi-core CPUs, a search key extraction block, a hash value calculation block, and a bus connecting the main memory;
3. The pattern according to claim 1, wherein one of the sub-pattern tables obtained by dividing the pattern table into the same number as the multi-core CPU is configured on the shared memory of the plurality of multi-core CPUs. Matching device. Generate a packet reception event that includes the extracted search key and the calculated hash value,
The pattern matching apparatus according to claim 11, wherein the generated packet reception event is issued to a multi-core CPU having a sub-pattern table that holds an entry group corresponding to the calculated hash value. The multi-core CPU that has received the packet reception event,
The pattern matching apparatus according to claim 12, wherein the received packet reception event is sequentially assigned to one of a plurality of processor cores of the multi-core CPU. In a multi-core processor environment having a multi-core CPU composed of a plurality of processor cores and a shared memory shared among those processor cores existing in the same CPU,
Configure a pattern table with search patterns on shared memory,
A pattern matching method, wherein pattern matching processing for search keys to be searched is executed in parallel by a plurality of processor cores.

Images