JP5920698B2 - Data judgment device and data judgment program - Google Patents

Description

  The present invention relates to a data determination device and a data determination program for determining whether or not input collation data matches registration data in a registered data group registered in advance.

  Communication terminals connected to the network include terminals equipped with a packet filter circuit for filtering received packets. This packet filter circuit compares collation data such as an IP address included in the received packet with registration data in a registered data group registered in advance as a matching condition, and matches / matches the collation data with the registration data. A mismatch is determined, and processing such as packet discard or transmission is performed based on the determination result. As the capacity of a network increases, the number of packets transmitted and received by a communication terminal increases, and the packet filter circuit is required to perform determination on a large number of packets, that is, to increase the throughput.

  In the packet filter circuit, there is a linear search method (see, for example, Non-Patent Document 1) as one of methods for determining matching / mismatching between verification data and registered data. In this linear search method, collation data and registration data are collated one by one, and if the collation data and registration data match, it is determined to match, and if the collation data does not match any registration data, it is determined to be disagreement. To do. That is, the linear search method is a method in which a mismatch is determined after collation data is collated with all registered data.

[Conventional example 1]
FIG. 22 shows a typical configuration of a packet filter circuit that implements the linear search method. The packet filter circuit 200 includes a buffer circuit 201 and a coincidence determination circuit 202.

  The buffer circuit 201 sends a determination start signal and collation data (data consisting of part or all of the packet) to the coincidence determination circuit 202 based on the input determination request signal and packet. The coincidence determination circuit 202 compares the collation data from the buffer circuit 201 with registered data in a registered data group registered in advance as a coincidence condition, and performs a coincidence determination.

  The coincidence determination circuit 202 outputs a coincidence determination signal to the buffer circuit 201 when detecting registration data that matches the collation data. If matching registration data cannot be detected even after collation with all registration data, a mismatch judgment signal is output to the buffer circuit 201.

  The match determination signal / mismatch determination signal from the match determination circuit 202 is sent to the buffer circuit 201. The buffer circuit 201 transmits the received packet when the coincidence determination signal is transmitted, and discards the received packet when the mismatch determination signal is transmitted.

  As can be seen from these operations, the packet filter circuit that implements the linear search method can not be determined to be inconsistent unless collation data and all registered data are collated. Judgment takes time. In filtering processing at a communication terminal, received packets are often determined to be inconsistent, and the time required for inconsistency determination is a cause of lowering throughput.

  In the packet filter circuit, there is a binary search method (for example, refer to Non-Patent Document 2) as another method for determining the match / mismatch between the verification data and the registered data. This binary search method is a method of narrowing the registration data to be collated to half. Since this method narrows down the registration data to be collated to half, the registration data to be collated is reduced as compared to the linear search method, and the time required to determine a match is shortened.

  However, in this method, it is not possible to determine the mismatch unless the verification with all registered data to be verified is completed, and it takes time to determine the mismatch. There are other methods using a hash function (for example, see Non-Patent Document 3). However, all of these methods are judged to be inconsistent after completing collation with all registered data to be collated. Therefore, it takes time to determine the mismatch.

  In view of this, for example, Patent Document 1 and Non-Patent Document 4 propose packet filter circuits in which a mismatch is determined before collation between collation data and all registered data is completed. In this packet filter circuit, a mismatch determination circuit is used in addition to the match determination circuit.

[Conventional example 2]
FIG. 23 shows a packet filter circuit disclosed in Non-Patent Document 4. The packet filter circuit 300 includes a buffer circuit 201, a match determination circuit 202, a mismatch determination circuit 203, and an OR gate 204.

  The buffer circuit 201 sends a determination start signal and verification data (data consisting of part or all of the packet) to the match determination circuit 202 and the mismatch determination circuit 203 based on the input determination request signal and packet. The coincidence determination circuit 202 compares the collation data from the buffer circuit 201 with registered data in a registered data group registered in advance as a coincidence condition, and performs a coincidence determination. On the other hand, the mismatch determination circuit 203 compares the input verification data with presence / absence information (described later) of registered data registered in advance, and determines mismatch.

  When the coincidence determination circuit 202 detects registered data that matches the collation data, it outputs a coincidence determination signal at that time. If matching registration data cannot be detected even after collation with all registration data, a mismatch judgment signal is output. The mismatch determination circuit 203 compares the verification data with the presence / absence information of the registration data, and outputs a mismatch determination signal when determining that there is no registration data that matches the verification data. A match determination signal from the match determination circuit 202 is sent to the buffer circuit 201. The mismatch determination signal from the match determination circuit 202 and the mismatch determination signal from the mismatch determination circuit 203 are sent to the buffer circuit 201 via the OR gate 204.

  The buffer circuit 201 transmits the received packet when the coincidence determination signal is transmitted, and discards the received packet when the mismatch determination signal is transmitted. Then, after processing this packet, the buffer circuit 201 outputs collation data for the next packet and a determination start signal, and the match determination circuit 202 and the mismatch determination circuit 203 shift to the determination process for that packet.

  The operation of the packet filter circuit 300 will be described with reference to FIG. FIG. 24 shows a timing chart in the case where “packet 1” determined to be inconsistent and “packet 2” determined to match are successively input.

  First, the buffer circuit 201 outputs the collation data of “packet 1” and the determination start signal to the match determination circuit 202 and the mismatch determination circuit 203. The match determination circuit 202 and the mismatch determination circuit 203 receive the determination start signal and simultaneously start the determination process for “packet 1”. If the mismatch determination circuit 203 determines that there is no registered data that matches the verification data of “packet 1”, it outputs a mismatch determination signal at that time. This mismatch determination signal is given to the buffer circuit 201 via the OR gate 204. The determination that there is no matching registration data in the mismatch determination circuit 203 is made in a short time.

  When the mismatch determination signal is sent, the buffer circuit 201 discards the received “packet 1” even if the match determination circuit 202 is in the middle of determination. When the processing of “packet 1” is completed, the buffer circuit 201 outputs the collation data of “packet 2” and the determination start signal. As a result, the determination process for “packet 2” is started simultaneously by the match determination circuit 202 and the mismatch determination circuit 203. When coincidence determination circuit 202 detects registration data that matches the collation data of “packet 2”, it outputs a coincidence signal at that time. This coincidence signal is supplied to the buffer circuit 201. When the coincidence signal is sent, the buffer circuit 201 transmits the received “packet 2”.

  As can be seen from the above operation, in the packet filter circuit 300, the mismatch determination circuit 203 determines the mismatch before the match determination circuit 202, whereby the determination processing time is shortened and the effective throughput is improved.

[Disagreement judgment circuit]
In the packet filter circuit 300, the mismatch determination circuit 203 compares the verification data with the presence / absence information of registered data registered in advance using a memory in order to determine a mismatch in a short time, thereby determining a mismatch. I do.

  The configuration of the memory used for the mismatch determination circuit 203 is shown in FIG. The memory M stores a determination of “match (registered data exists)” using the value of the registered data as an address, and stores a determination of “mismatch (no registered data)” at other addresses. FIG. 25 shows a case where the registration data has five values “1”, “6”, “10”, “14”, and “18”. In this case, “match” determination is stored in “1”, “6”, “10”, “14”, and “18” of the addresses of the memory M, and “mismatch” is determined for other addresses. Store.

  By using such a memory M, at the time of collation, the value of the collation data that is input is accessed as a read address to the memory M, and a determination of “match” or “mismatch” is output from the memory M. The mismatch determination circuit 203 determines a mismatch based on the output from the memory M.

The memory M shown in FIG. 25 requires a capacity equal to the maximum value that the collation data can take. That is, if the bit length of the verification data and the registration data is n bits, the memory M needs to store 2 ⁿ determinations. Therefore, in order to reduce the memory capacity, the above-mentioned Non-Patent Document 4 discloses that the memory is obtained by dividing the n-bit verification data and the registration data into a plurality of memories by m bits and performing the verification processing in parallel. A method for reducing the capacity of the disk is disclosed.

  FIG. 26 shows an example where n = 16 and m = 4. In FIG. 26, the upper 4 bits of each registered data are assigned to the memory M1, the next 4 bits are assigned to the memory M2, the next 4 bits are assigned to the memory M3, and the lower 4 bits are assigned to the memory M4. For example, when two registration data of 16 bits “0x1234” and “0x4567” are divided and stored in four memories, each registration data divided into four bits is stored in each memory in the same manner as in FIG. To remember. Here, “0x” means hexadecimal display.

  In the case of registration data “0x1234”, the memory M1 stores “0x1”, which is the value of the upper 4 bits, as an address, and stores “match” determination. The memory M2 has the next 4-bit value “0x2”, the memory M3 has the next 4-bit value “0x3”, and the memory M4 has the lower 4-bit value. The determination of “match” is stored at a certain “0x4” address.

  Similarly, in the case of registration data “0x4567”, the memory M1 has an address “0x4”, the memory M2 has an address “0x5”, the memory M3 has an address “0x6”, and the memory M4 has “ The determination of “match” is stored at the address “0x7”. All other addresses are stored with a “mismatch” determination.

In this way, the n-bit registration data is divided into a plurality of memories in units of m bits and the determination of “match” / “mismatch” is stored, thereby reducing the memory capacity to (n / m) 2 ^m . it can.

  When the memory of the mismatch determination circuit 203 is divided, at the time of mismatch determination, collation is performed independently in parallel with a plurality of memories, and if mismatch is output from one of the memories, the verification data is determined to be mismatched. The For example, as shown in FIG. 27, when the collation data “0x1235” is input, the determination of “match” is output from the memory M1, the memory M2, and the memory M3, and the determination of “mismatch” is output from the memory M4. The collation data is determined to be inconsistent.

  However, there are cases where it cannot be determined that there is a mismatch even though the collation data does not match. For example, as shown in FIG. 28, when collation data “0x1237” is input, since this data is not registered data, it should be determined that there is a mismatch, but all the memories M1 to M4 (hereinafter referred to as this data) The memory is referred to as a mismatch table), so that a “match” determination is output, so it is determined as a match. In this case, since the coincidence determination circuit 202 collates with all the registered data and finally determines that there is a mismatch, no erroneous determination is made.

[Match determination circuit]
As described above, the coincidence determination circuit 202 is implemented by using a linear search method that sequentially collates collation data with registered data, a binary search method that narrows down to half, a hash search method, and the like. Can do. Regardless of which method is used, the coincidence determination circuit 202 requires a memory for storing registration data (hereinafter, this memory is referred to as a condition table), and the registration data is efficiently read from the condition table. The match / mismatch of the collation data is determined by.

JP 2010-165102 A

David E. Taylor "Survey and Taxonomy of Packet Classification Techniques" ACM Computing Surveys, Vo1.37, No.3, September 2005, pp.238-275. Yumiba, Hoshi "Headline search technique using tree structure" Information Processing, Vol.21, No1, January 1980, pp.28-49. Yeim-Kuan Chang and Wen-Hsin Cheng "A Small IP Forwarding Table Using Hashing" Proceeding of The l8th International Conference on AINA, 2004. Naura Miura et al., “High-speed packet filter circuit using mismatch circuit”, IEICE Technical Report VLD2008-143, pp. 101-106, March 2009.

  However, in the above-described conventional packet filter circuit 200 (FIG. 22) or 300 (FIG. 23), in order to create the condition table in the coincidence determination circuit 202, a list of registered data to be written to each address is created in advance. In general, it is written in a memory. Usually, this data creation is executed separately by software, and after the data is created, it is written to the memory.

  In particular, in the packet filter circuit 300 provided with the mismatch determination circuit 203 in addition to the match determination circuit 202, the creation of the mismatch table in the mismatch determination circuit 203 is written in advance to each address in the same manner as the match determination circuit 202. It is necessary to create a list of data to be written and write it to the memory. Furthermore, if the registered data is changed, all the judgment data for “match” / “mismatch” in the mismatch table and all the registered data in the condition table You need to recreate it and write it back into memory.

  As described above, in the conventional packet filter circuit, it is necessary to create a separate table, and there is a problem that software for creating the table and labor for creating the table in advance are required.

  The present invention has been made to solve such a problem, and an object of the present invention is to determine a match / mismatch by using a match / mismatch determination function between matching data and registered data. It is an object of the present invention to provide a data determination apparatus and a data determination program that can eliminate the need to create software for creating a table and the trouble of creating a table in advance.

In order to achieve such an object, the invention according to claim 1 of the present application provides a data determination device that determines whether or not input collation data matches registration data in a registered data group registered in advance. The registration data storage means for storing the registration data, the address information storage means for storing the address information including the address where the registration data is not stored in the registration data storage means, and the registration stored in the registration data storage means The comparison means for comparing the data with the collation data to obtain a match / mismatch determination result, and the registration candidate data to be registered in the registration data storage means when updating the registration data stored in the registration data storage means In response to the input, the comparison means compares the registration candidate data with the registration data stored in the registration data storage means. If the determination result is obtained, based on the address information stored in the address storage means, means for writing the registration data storage means data of the input registration candidate as the registration data, stored in the registration data storage means When the registered data is updated, the input of the deletion candidate data to be deleted is received from the registration data storage means, and the comparison between the deletion candidate data and the registration data stored in the registration data storage means is compared. Means for deleting registration data that matches the inputted deletion candidate data from the registration data storage means based on the address information stored in the address storage means when the matching determination result is obtained. characterized in that it comprises and.

  According to this invention, when registration data stored in the registration data storage means (condition table) is updated, if registration candidate data to be registered in the registration data storage means is input, the registration candidate data And the registration data stored in the registration data storage means are compared by a comparison means (comparator), and when a determination result of mismatch is obtained, address information stored in the address storage means (register) (in this case, The input registration candidate data is written into the registration data storage means as registration data based on the empty address where no registration data is stored. In this way, according to the present invention, every time registration candidate data is input, if the registration candidate data is not stored in the registration data storage means, the registration data is successively stored as free data in the registration data storage means. Go written.

According to the present invention, when the registration data stored in the registration data storage means (condition table) is updated, if the deletion candidate data to be deleted is input from the registration data storage means, the registration candidate And the registered data stored in the registered data storage means are compared by the comparing means (comparator), and when a coincidence determination result is obtained, the address information stored in the address storing means (register) In this case, the registered data that matches the input deletion candidate data is deleted from the registered data storage means on the basis of the address at which the matching registered data is stored. In this way, in the present invention, every time deletion candidate data is input, if the deletion candidate data is stored in the registered data storage means, registered data that matches the deletion candidate data one after another is stored. It is deleted from the registered data storage means.

The invention according to claim 2 of the present application is the invention according to claim 1 , wherein registration data including a part of information of collation data as an address and a value of the address as part of information is stored in the registration data storage means. Registration data presence / absence information storage means storing information indicating whether or not the data is registered, and the registration data stored in the registration data storage means based on the information stored in the registration data presence / absence information storage means. When updating the information stored in the mismatch data determination unit and the registration data presence / absence information storage unit, the registration data is deleted after deleting all the information stored in the registration data presence / absence information storage unit. The registered data stored in the storage means is read out, and the registered data presence / absence information storage means is accessed by using a part of the read registration data as an address. And means for writing information indicating that the registered data containing the value of the address as part of the information is stored in the registered data storage means at the address of the accessed registration data presence / absence information storage means. It is characterized by that.

  According to the present invention, when updating the information stored in the registration data presence / absence information storage means (mismatch table), after all the information stored in the registration data presence / absence information storage means is deleted, the registration data storage means The registered data stored in the (condition table) is read. Then, the registered data presence / absence information storage means is accessed using a part of the information of the read registration data as an address, and the value of the address is used as a part of the information of the accessed registration data presence / absence information storage means. Information indicating that the registration data included is stored in the registration data storage means (“match (with registration data)”) is written. Information indicating that the registration data is not stored in the registration data storage means (“mismatch (no registration data)”) remains at the address that has not been accessed. Thus, according to the present invention, whether or not registration data that includes the value of the address as a part of information is automatically stored in the registration data storage means in the address of the registration data presence / absence information storage means. The information indicating is going to be written.

  The data determination apparatus according to the present invention can be realized as a program executed by a computer, and can be stored in a recording medium or provided through a network.

According to the present invention, when the registration data stored in the registration data storage means is updated, the registration candidate data to be registered in the registration data storage means is received, and the registration candidate data and the registration data storage are received. When the comparison result is compared with the registration data stored in the means and a determination result of inconsistency is obtained, the input registration candidate data is obtained based on the address information stored in the address storage means. Since the registration data is written in the registration data storage means, when the registration data stored in the registration data storage means is updated, the deletion data to be deleted is received from the registration data storage means. The comparison unit compares the deletion candidate data with the registration data stored in the registration data storage unit, and a match determination result is obtained. If, based on the address information stored in the address storage unit. Thus deletes the registration data matching the input data deletion candidate from the registered data storage means, every time the data of the registration candidate is input In addition, by using the matching / mismatching determination function between the collation data and the registered data, the data is sequentially written as registration data to the empty address of the registered data storage means , and deletion candidate data is input. Each time, using the matching / mismatching function between the matching data and the registered data, the registered data that matches the deletion candidate data is sequentially deleted from the registered data storage means, and the matching / mismatching is determined. Therefore, it is possible to eliminate the need for software for creating a table for creating a table and for creating a table in advance.

It is a figure which shows one Embodiment of the packet filter circuit containing the data determination apparatus which concerns on this invention. It is a figure which shows the structure of the mismatch determination circuit in this packet filter circuit. It is a figure which shows the structure of the mismatch table in this mismatch determination circuit. It is a figure which shows the structure of the coincidence determination circuit in this packet filter circuit. It is a figure which shows the structure of the condition table in this coincidence determination circuit. It is a figure which shows the structure of the index table in this coincidence determination circuit. It is a figure which shows the structure of the register group in this coincidence determination circuit. It is a figure which shows the state of the initialized mismatch table. It is a figure which shows the state of the initialized index table, condition table, and register group. It is a figure explaining the update procedure of each table in the case of registering "condition a0". It is a figure explaining the update procedure of each table in the case of registering "condition b0". It is a figure explaining the update procedure of each table in the case of registering "condition a1". It is a figure which shows the state of the index table at the time of completion of registration of "condition a0", "condition b0", and "condition a1", and a register group. It is a figure explaining the update procedure of each table in the case of deleting "condition a1". It is a figure explaining the update procedure of each table in the case of deleting "condition a0". It is a flowchart which shows the flow of the process sequence at the time of a registration request | requirement. It is a flowchart which shows the flow of a process in the branch (I) in the process sequence at the time of a registration request | requirement. It is a flowchart which shows the flow of a process in branch (II) in the process sequence at the time of a registration request | requirement. It is a flowchart which shows the flow of the process sequence at the time of a deletion request | requirement. It is a flowchart which shows the flow of a process in branch (III) in the process sequence at the time of a deletion request | requirement. It is a flowchart which shows the flow of a process in branch (IV) in the process sequence at the time of a deletion request | requirement. It is a figure which shows the typical structure of the conventional packet filter circuit (conventional example 1) which mounted the linear search system. It is a figure which shows the conventional packet filter circuit (conventional example 2) shown by the nonpatent literature 4. 10 is a time chart for explaining the operation of the packet filter circuit of Conventional Example 2. It is a figure which shows the structure of the memory used for the mismatch determination circuit in the packet filter circuit of the prior art example 2. It is a figure which shows the example which divided | segmented and memorize | stored registration data in four memories in the mismatch determination circuit in the packet filter circuit of the prior art example 2. FIG. It is a figure which shows the output condition of the determination result of the coincidence / non-coincidence from four memories when the collation data “0x1235” is input. It is a figure which shows the output condition of the determination result of the coincidence / non-coincidence from four memories when the collation data “0x1237” is input.

  Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings. FIG. 1 is a diagram showing an embodiment of a packet filter circuit including a data determination device according to the present invention.

  The packet filter circuit 100 includes a buffer circuit 101, a match determination circuit 102, a mismatch determination circuit 103, and an OR gate 104. The buffer circuit 101 receives a determination request signal and a packet. In addition to the determination start signal and collation data from the buffer circuit 101, the mode selection signal is input to the match determination circuit 102 and the mismatch determination circuit 103.

  In the embodiment, depending on the setting of the mode selection signal, the collation data to be input is determined as a condition [registration condition (registration candidate data) / deletion condition (deletion candidate data)]. This point will be described in detail later. In the packet filter circuit 100, the match determination circuit 102 and the mismatch determination circuit 103 constitute main components of the data determination apparatus according to the present invention.

  In this packet filter circuit 100, the buffer circuit 101 uses a determination start signal and collation data (data consisting of a part or all of a packet) based on the input determination request signal and packet as a match determination circuit 102 and a mismatch. This is sent to the determination circuit 103. The coincidence determination circuit 102 determines the coincidence by comparing the collation data from the buffer circuit 101 with the registered data in the registered data group registered in advance as a coincidence condition. On the other hand, the mismatch determination circuit 103 compares the input verification data with the presence / absence information of registered data registered in advance, and determines mismatch.

  When the coincidence determination circuit 102 detects registration data that matches the collation data, the coincidence determination circuit 102 outputs a coincidence determination signal at that time. If matching registration data cannot be detected even after collation with all registration data, a mismatch judgment signal is output. The mismatch determination circuit 103 compares the verification data with the presence / absence information of the registration data, and outputs a mismatch determination signal when determining that there is no registration data that matches the verification data. A match determination signal from the match determination circuit 102 is sent to the buffer circuit 101. The mismatch determination signal from the match determination circuit 102 and the mismatch determination signal from the mismatch determination circuit 103 are sent to the buffer circuit 101 via the OR gate 104.

  The buffer circuit 101 transmits the received packet when the coincidence determination signal is transmitted, and discards the received packet when the mismatch determination signal is transmitted. Then, after processing this packet, the buffer circuit 101 outputs collation data for the next packet and a determination start signal, and the match determination circuit 102 and the mismatch determination circuit 103 shift to the determination process for that packet.

[Configuration of mismatch judgment circuit]
The configuration of the mismatch determination circuit 103 is shown in FIG. The mismatch determination circuit 103 includes a bit division / selection circuit 103A, mismatch tables 103B1 to 103B4, an AND gate 103C, a processing unit 103D, and an inverter 103E. FIG. 2 shows an example in which the length of the collation data is 32 bits and is divided into four 8 bits.

  In this embodiment, the mismatch table 103B (103B1 to 103B4) is configured by a memory. The upper 8 bits of each registered data are assigned to the mismatch table 103B1, the next 8 bits are assigned to the mismatch table 103B2, the next 8 bits are assigned to the mismatch table 103B3, and the lower 8 bits are assigned to the mismatch table 103B4. In this example, since it is divided into 8 bits, the mismatch table 103B has a configuration of 256 words × 1 bit.

  The address of the mismatch table 103B1 corresponds to the upper 8-bit value of the registration data, and when the address value is included as the corresponding 8-bit value of the registration data, “match” to the corresponding address of the mismatch table 103B1. Write the decision. In this example, “1” is assigned. If it is not included in the registered data, the determination of “mismatch” is written. In this example, “0” is assigned. The same applies to the mismatch tables 103B2 to 103B4.

  A configuration example of the mismatch table 103B1 is shown in FIG. In FIG. 3, since the value of the upper 8 bits of “registration condition 1 (registration data 1)” is “1”, “1” (match) is stored at address “1” of the mismatch table 103B1. In “registration condition 2 (registered data 2)”, since the value of the upper 8 bits is “10”, “1” (match) is stored at address “10” of the mismatch table 103B1. The numbers in “Registration condition 1 (registration data 1)” and “registration condition 2 (registration data 2)” are values of 8-bit strings expressed in decimal numbers.

[Basic operation of the mismatch judgment circuit]
Next, the basic operation of the mismatch circuit 103 will be described. The collation data from the buffer circuit 101 is sent to the bit division / selection circuit 103A. A determination start signal from the buffer circuit 101 is sent to the processing unit 103D.

  When collation data is input, the bit division / selection circuit 103A selects 8 bits from the input collation data, and the upper 8 bits are in the mismatch table 103B1, and the next 8 bits are in the mismatch table 103B2. Are output to each mismatch table 103B.

  In each mismatch table 103B, each 8-bit value sent from the bit division / selection circuit 103A is input as an address, and data stored in the address is read out. Reading from each of the mismatch tables 103B is performed in accordance with an instruction from the processing unit 103D that has received the determination start signal.

  At this time, if any of the data read from the four mismatch tables 103B has a determination of “0”, that is, “mismatch”, the AND gate 103C outputs “0”, which is a determination of mismatch. If all the read data is “1”, that is, if all are “match”, the AND gate 103C outputs “1”, which is a match determination. The judgment of coincidence / non-coincidence from the AND gate 103C is inverted by the inverter 103E, passes through the OR gate 104 (FIG. 1), and is sent to the buffer circuit 101.

  In this example, the upper 8 bits and the next 8 bits are selected and divided sequentially, but the order of bits and the selection of each bit are not limited to this. It is easy to configure so that arbitrary 8 bits are selectively extracted and output to each mismatch table 103B as necessary. There is no need for 8 bits.

[Configuration of coincidence determination circuit]
Next, the configuration of the coincidence determination circuit 102 is shown in FIG. The coincidence determination circuit 102 includes an index table 102A, a condition table 102B, a register group 102C, a comparator 102D, selectors 102E1 to 102E3, a processing unit 102F, and the like. In the present embodiment, the index table 102A and the condition table 102B are configured by a memory. In this example, the collation data is 32 bits long, and up to 512 pieces of registration data can be registered in the condition table 102B.

  The configuration of the condition table 102B is shown in FIG. The condition table 102B is a table for storing matching conditions for determination as registration data (registration conditions). In this embodiment, a maximum of 512 pieces of registration data can be registered. Accordingly, the number of words in the condition table 102B is 512, and the address of the memory that designates this word is 9 bits long.

  First, 512 pieces of registration data are classified by the upper 8 bits of all 32 bits. Registration data having the same value of the upper 8 bits is regarded as one group. For example, if there are two pieces of registered data whose upper 8 bits are “a”, these are represented by “condition a0” and “condition a1”. Hereinafter, these may be simply expressed as “a0” and “a1”. The same applies to “condition b0”, “condition c0”, and the like.

  The data in the condition table 102B is divided into four fields. The first field is 1 bit wide and indicates whether or not the word stores registration data. This is called VB (Valid Bit), and “1” is assigned when registration data is stored, and “0” is assigned when it is not stored.

  The second field is called an FLT (condition) field and stores registration data. In this embodiment, since the verification data is 32 bits, 32 bits are assigned to this field. One bit is assigned to the third field to indicate whether registered data belonging to the same group is stored in the subsequent addresses. This bit is called an NF (Next Flag) field. If it is stored, “1” is stored in the NF field, and the next registration data is stored in the NA (Next Address) field, which is the fourth field. Stores an address. If registration data belonging to the same group is not stored in another address, “0” is stored in the NF field, and “0” is stored in the NA field. Therefore, the NA field is 1 bit wide and the NA field is 9 bits wide.

  The contents of the condition table 102B shown in FIG. 5 will be specifically described. First, the first row (address 0 of the condition table 102B) is VB = 1, indicating that registration data is stored at this address. In this case, the registration data is stored in the FLT field, and it can be seen that “condition a0”. Since the next NF field is “1”, it indicates that registration data whose upper 8 bits are “a” is still stored in the condition table 102B. Since the NA field is “2”, the next registration data is stored at address 2 of the condition table 102B. Thus, looking at address 2, VB = 1 and it can be seen that “condition a1” is stored in the FLT field. The NF field, which is the third field, is “0”, indicating that there is no more registration data belonging to this group. In this case, “0” is assigned to the NA field. The same applies to “condition b” and “condition c”.

  Next, address 510 will be described. Since VB = 0, this indicates that no registration data is stored at this address. In this case, “1” is set in the NF field, and the first empty address where no registered data is stored in the subsequent word is stored in the NA field. Here, since “511” is stored, it indicates that the next empty address is address 511. The value of the FLT field is arbitrary.

  Next, the configuration of the index table 102A will be described. FIG. 6 shows the configuration. The index table 102A is a memory whose address is the value of the upper 8 bits of the collation data. Therefore, it consists of 256 words. Each word includes a 1-bit wide MF (Match Flag) field and a 9-bit wide IA (Index Address) field. In the index table 102A, for example, the address “a” stores information indicating whether or not the registration data whose upper 8 bits are “a” is stored in the condition table 102B, and information associated therewith. .

  In the index table 102A, the value of the field MF at the address “a” indicates whether or not the registration data whose upper 8 bits are “a” exists in the condition table 102B. That is, if the value of the field MF of the address “a” is “1”, it means that registered data whose upper 8 bits are “a” exists in the condition table 102B. In the IA field of the address “a”, the address of the condition table 102B in which the registration data to be compared first among the registration data whose upper 8 bits are “a” is stored. If registration data whose upper 8 bits are “a” does not exist in the condition table 102B, MF = 0 and IA = 0 are set in the “a” address of the index table 102A.

  For example, when the address “0” in the index table 102A is viewed, MF = 1, indicating that registered data whose upper 8 bits are “0” exists in the condition table 102B. Since the value of the IA field is “1”, the first registered data to be compared is stored at address 1 of the condition table 102B.

  Note that the MF field of the index table 102A is the same as the mismatch table 103B1 of the mismatch determination circuit 103. Therefore, the mismatch table 103B1 of the mismatch determination circuit 103 can be omitted. Or, conversely, the MF field of the index table 102 </ b> A can be deleted and replaced with the mismatch table 103 </ b> B <b> 1 of the mismatch determination circuit 103.

[Basic operation of coincidence determination circuit]
Next, the basic operation of the coincidence determination circuit 102 will be described. As for the collation data from the buffer circuit 101, all the bits are sent to the comparator 102D and the upper 8 bits are sent to the index table 102A. The determination start signal from the buffer circuit 101 is sent to the processing unit 102F. The following processing operation is performed according to the instruction of the processing unit 102F that has received the determination start signal.

  Now, it is assumed that the value of the upper 8 bits of the collation data is “a”. In this case, first, the address “a” in the index table 102A shown in FIG. 6 is accessed, and the data is read out. In this example, since the value of the MF field is “1” in the read data, it can be seen that registered data whose upper 8 bits are “a” exists in the condition table 102B. Of the output data, the value “0” of the IA field is output to the condition table 102B.

  In the condition table 102B of FIG. 5, the value “0” of the IA field output from the index table 102A is used as the address “0” of the condition table 102A, and data at address 0 is read. At this time, since VB = 1, this registration data is valid, and data in the FLT field, that is, “condition a0” stored as registration data is sent to the comparator 102D. As a result, the comparator 102D compares the collation data from the buffer circuit 101 with the “condition a0” to determine a match / mismatch. If it is determined that they match, the determination process ends.

  When it is determined that they do not match, the value of the NF field at address 0 read in the condition table 102B is referred to. In FIG. 5, since NF = 1, it can be seen that there is still registered data whose upper 8 bits are “a”, and the address “2 (= NA) of the condition table 102B in which the registered data is stored. ”” Is output as the address of the condition table 102B that is itself. As a result, “condition a1” is read from the FLT field at address 2 in the condition table 102B and sent to the comparator 102D. The comparator 102D compares the collation data from the buffer circuit 101 with the “condition a1” and determines whether or not they match. If it is determined that they match, the determination process ends.

  If it is determined that they do not match, the data in the NF field at address 2 in the condition table 102B is referred to. In FIG. 5, NF = 0, and it is determined that there is no other registered data whose upper 8 bits are “a”, and the determination process ends. When the determination process ends, the process proceeds to the next packet process.

[Automatic update of various tables]
Next, the automatic update function of the mismatch table 103B, the index table 102A, and the condition table 102B, which is a characteristic function of the present embodiment, in the packet filter circuit 100 having the match determination circuit 102 and the mismatch determination circuit 103 will be described. To do.

  This automatic update function automatically generates or deletes the mismatch table 103B, the index table 102A, and the condition table 102B using the matching / mismatch determination function between the matching data and the registration data of the packet filter circuit 100. It is a function. The mode selection signal in FIG. 1 and the register group 102C in FIG. 4 are provided to realize this automatic update function.

  FIG. 7 shows the configuration of the register group 102C. The register group 102C includes a WADR register 102C1, a tmp register 102C2, an MCD register 102C3, a CADR register 102C4, and a BADR register 102C5. The WADR register 102C1, the tmp register 102C2, and the MCD register 102C3 are composed of an NF field having a 1-bit width and an NA field having a 9-bit width. The CADR register 102C4 and the BADR register 102C5 are composed only of a 9-bit wide NA field.

(Initialization mode)
First, the initialization mode will be described. In this mode, the mismatch table 103B, the index table 102A, the condition table 102B , and the register group 102C are initialized. The initialization is automatically performed only by setting the mode selection signal to the initialization mode and inputting the clock. This initialization can be realized with small-scale hardware such as a counter.

  In the mismatch determination circuit 103 shown in FIG. 2, the processing unit 103D has a hardware configuration for performing a processing operation according to the mode selection signal. Further, in the coincidence determination circuit 102 shown in FIG. 4, the processing unit 102F is provided with a hardware configuration for performing a processing operation in accordance with the mode selection signal.

  FIG. 8 shows the states of the mismatch tables 103B1 to 103B4 that have been initialized. When the mode selection signal is input as the initialization mode, the processing unit 103D sets the stored data to “0”, that is, “mismatch” for all addresses in the mismatch tables 103B1 to 103B4.

  FIGS. 9A, 9B, and 9C show the states of the index table 102A, the condition table 102B, and the register group 102C that are initialized. When the mode selection signal is input as the initialization mode, the processing unit 102F initializes the index table 102A, the condition table 102B, and the register group 102C.

  By this initialization, “0” is stored for all addresses in the index table 102A. In the condition table 102B, “0” is set in the VB field and the FLT field for all addresses. In the NF field, “0” is set only for the address “511”, and “1” is set for other addresses. In the NA field, “0” is set only for the address “511”, and a value 1 larger than that address is set for the other addresses. In the register group 102C, “1” is set in the NF field of the WADR register 102C1, and “0” is set in all other cases.

[Registration mode]
Next, a registration mode that is an operation mode for registering conditions will be described. The mode selection signal is set to the registration mode, and packets including conditions (registration candidate data) to be registered are sequentially input to the packet filter circuit 100. Thus, according to the operation of the match / mismatch determination process in the match determination circuit 102 described above, the input registration candidate data is automatically stored in the condition table 102B sequentially, and the accompanying address and the like are simultaneously selected as necessary. Stored in each table. The mismatch determination circuit 103 also stores information indicating the presence or absence of registration data for the input registration candidate data in the mismatch tables 103B1 to 103B4. Hereinafter, a specific operation when the registration mode is set will be described.

  First, a case where the first “condition a0” is registered in a state where each table is initialized as shown in FIGS. 8 and 9 will be described. When a packet including “condition a0” that is registration candidate data is input to the packet filter circuit 100, the “condition a0” is input to the mismatch determination circuit 103 and the match determination circuit 102 via the buffer circuit 101. . Since the data is the first registration candidate data, the mismatch determination circuit 103 and the match determination circuit 102 both determine a mismatch according to the determination operation. When the match determination circuit 102 determines that there is a mismatch, that is, when the comparator 102D determines that there is a mismatch, the updating of the various tables is started. In this registration mode, the determination result of the mismatch determination circuit 103 is ignored.

  Hereinafter, the operation of the coincidence determination circuit 102 and the update procedure of each table will be described in detail with reference to FIG. The following order (1), (2), etc. corresponds to that in FIG. This operation is performed in accordance with an instruction from the processing unit 102F that has received the mode selection signal (registration mode).

  (1) Since the value of the upper 8 bits of “condition a0” is “a”, the address “a” in the index table 102A is accessed (FIG. 16: step S101). In this case, since the MF field at address “a” is “0”, it is determined that there is a mismatch (YES in step S102). Thereby, the processing moves to branch (I) (step S103). A flowchart of branch (I) is shown in FIG. In the branch (I) process, the value “0” of the NA field of the WADR register 102C1 of the register group 102C is sent to the condition table 102B, and data at address 0 in the condition table 102B is read (step S101).

  (2) Of the data read from the condition table 102B, the values of the NF and NA fields are stored in the tmp register 102C2 of the register group 102C (step S102). Accordingly, the value (NF, NA) of the tmp register 102C2 is updated from (0, 0) to (1, 1).

  (3) Next, the values of the NF and NA fields of the WADR register 102C1 of the register group 102C are copied to the MF field and IA field of the address “a” in the index table 102A, respectively (step S203). As a result, the value (MF, IA) of the address “a” in the index table 102A is updated as (0, 0) → (1, 0).

  (4) Since “0”, that is, address 0 is stored in the NA field of the WADR register 102C1 of the register group 102C, the address 0 of the condition table 102B is accessed based on this value, and each field (VB, FLT , NF, NA) is updated from (0, 0, 1, 1) to (1, condition a0, 0, 0) (step S204). This indicates that address 0 in the condition table 102B is valid and “condition a0” is stored as registration data. Since the condition that the value of the upper 8 bits is “a” does not exist yet, NF = 0 and NA = 0 are set.

  (5) Finally, the values of the NF and NA fields of the tmp register 102C2 are copied to the NF and NA fields of the WADR register 102C1 (step S205). As a result, the value of the WADR register 102C1 becomes (NF, NA) = (1, 1), and is prepared for the next registration. In this case, at the time of the next registration, the value of the NA field of the WADR register 102C1 is used as an address, and the registration data is written to address 1 of the condition table 102B indicated by this address.

  From the above procedure, it can be seen that the data in the WADR register 102C1 means the smallest address in the condition table 102B to which the registered data has not yet been written, that is, the smallest address among the free addresses. When registering registration candidate data, it is written to this address. Since the NA field of the WADR register 102C1 is set to “0” by initialization, the first registration data is set to be stored at address 0. Therefore, in this example, the first “condition a0” is stored at address 0 of the condition table 102B. Further, the value of the NA field of the WADR register 102C1 may be copied to the IA field at the address “a” in the index table 102A.

  On the other hand, in the mismatch determination circuit 103, the bit division / selection circuit 103A writes the data “1” to the addresses of the mismatch tables 103B1 to 103B4 using the 8-bit value of “condition a0” as an address. This completes the update of the mismatch tables 103B1 to 103B4. This operation is performed in accordance with an instruction from the processing unit 103D that has received the mode selection signal (registration mode). The same operation is performed when a new condition is registered. Even if “1” is already written, “1” is written, but it is natural that there is no problem. Therefore, the description of the update of the mismatch table 103B is omitted below.

  Next, a case where “condition b0” is registered will be described with reference to FIG. In this example, b = 1 for convenience of explanation. This is basically the same as the registration of “condition a0”. Therefore, in response to YES in step S102 shown in FIG. 16, the process proceeds to branch (I) (step S103), and the process of branch (I) shown in FIG. 17 is performed.

  (1) Since the value of the upper 8 bits of “condition b0” is “1”, address 1 of the index table 102A is accessed (FIG. 16: step S101). In this case, since the MF field at address 1 is MF = 0, it is determined that there is a mismatch (YES in step S102). Thereby, the processing moves to branch (I) (step S103). In the branch (I) process (FIG. 17), the value “1” of the NA field of the WADR register 102C1 of the register group 102C is sent to the condition table 102B, and the data at address 1 in the condition table 102B is read (step S101). .

  (2) Of the data read from the condition table 102B, the values of the NF and NA fields are stored in the tmp register 102C2 of the register group 102C. Accordingly, the value (NF, NA) of the tmp register 102C2 is updated from (1, 1) to (1, 2).

  (3) Next, the values of the NF and NA fields of the WADR register 102C1 are copied to the MF and IA fields at address 1 of the index table 102A, respectively (step S203). As a result, the value (MF, IA) at address 1 in the index table 102A is updated as (0, 0) → (1, 1).

  (4) Since the NA field of the WADR register 102C1 stores “1”, that is, address 1, the address 1 of the condition table 102B is accessed based on this value, and each field (VB, FLT, NF, NA ) Is updated from (0, 0, 1, 2) to (1, condition b0, 0, 0) (step S204).

  (5) Finally, the values of the NF and NA fields of the tmp register 102C2 are copied to the NF and NA fields of the WADR register 102C1 (step S205). As a result, the value of the WADR register 102C1 becomes (NF, NA) = (1, 2), and is prepared for the next registration. In this case, at the time of the next registration, the value of the NA field of the WADR register 102C1 is used as an address, and the registration data is written in the second address of the condition table 102B indicated by this address.

  Next, as the last of the registration mode, a case will be described in which “condition a1” in which the value of the upper 8 bits is “a” and other bits are different.

  In this case, since the value of the upper 8 bits is “a”, the address “a” in the index table 102A is accessed. Since the value of the MF field at address “a” in the index table 102A is “1”, it is determined that they match. Thereby, based on the value “0” of the IA field of the index table 102A, the 0 address of the condition table 102B is accessed, and the “condition a0” read from the 0 address is sent to the comparator 102D.

  “Condition a1” is input to the comparator 102D. Since “condition a0” and “condition a1” are different, the comparator 102D determines that they do not match. In this case, since NF = 0, the registered data whose upper 8 bits are “a” indicates that this is the last. At this point, “condition a1” is determined to be data to be registered, and updating of each table is started. If the “condition a1” is the same as the “condition a0”, the comparator 102D determines that they match, and the process ends at this point.

  Hereinafter, the procedure for registering “condition a1” will be described in detail with reference to FIG. 12, starting from a table at the time when “condition a0” and “condition b0” are registered.

  (1) Since the value of the upper 8 bits of “condition a1” is “a”, the address “a” in the index table 102A is accessed (FIG. 16: step S101). In this case, since the MF field of the address “a” is MF = 1 (NO in step S103), it is determined that they match. As a result, the value “0” in the IA field at address “a” is used as an address (step S104), and data at address 0 in the condition table 102B is read (step S105). Then, among the read data, “condition a0” which is data in the FLT field is sent to the comparator 102D and compared with the inputted “condition a1” (step S106). In this case, the comparator 102D determines that there is a mismatch (NO in step S106).

  (2) At this time, since the value of the NF field at address “a” in the read condition table 102B is “0” (YES in step S107), this is the registered data whose upper 8 bits are “a”. It turns out that it is the last. At this point, the determination is completed, and it is determined that “condition a1” is data to be registered. Thereby, the processing moves to branch (II) (step S108). A flowchart of the branch (II) is shown in FIG. In the branch (II) process, the last registered data determined to be inconsistent, in this case, the address “0” of the condition table 102B storing “condition a0” is stored in the CADR register 102C4 (step S301).

  (3) Since the empty address for storing “condition a1” is stored in the NA field of WADR register 102C1, the data at address 2 in condition table 102B is read based on this value “2” (step S302), the values of the NF and NA fields in the data are stored in the tmp register 102C2 (step S303).

  (4) Similarly, based on the value of the NA field of the WADR register 102C1, the second address of the condition table 102B is accessed, and the value of each field (VB, FLT, NF, NA) is set to (0, 0, 1, 3). To (1, condition a1, 0, 0) (step S304). In this case, it is not necessary to rewrite the index table 102A.

  (5) Subsequently, the value of the NA field where “condition a0” is stored in the condition table 102B is changed to the address where “condition a1” is stored. In this case, since the address storing “condition a0” is stored in the CADR register 102C4, the address “0” in the condition table 102B is accessed based on this value “0”, and the NF, The value of the NA field is copied to the NF field and NA field of the condition table 102B (step S305).

  (6) Finally, the values of the NF field and NA field of the tmp register 102C2 are copied to the NF field and NA field of the WADR register 102C1, and set as the next empty address (step S306). This completes the registration of “condition a1”.

  FIGS. 13A, 13B, and 13C show states of the index table 102A, the condition table 102B, and the register group 102C at the time when registration of “condition a0”, “condition b0”, and “condition a1” is completed. .

[Delete Mode]
Next, a deletion mode that is an operation mode for deleting registered conditions will be described. The mode selection signal is set to the deletion mode, and a packet including a condition to be deleted (deletion candidate data) is input to the packet filter circuit 100. Since the input deletion candidate data should already be registered, the packet filter circuit 100 determines that they match. Various tables are updated based on the determination result.

  For example, it is assumed that “condition a1” is deleted in the state of FIG. The “condition a1” is sent to the mismatch determination circuit 103 and the match determination circuit 102 via the buffer circuit 101. Even in this mode, the determination result of the mismatch determination circuit 103 is not considered. In this case, the address “a” in the index table 102A of the coincidence determination circuit 102 is accessed. Since the value of the MF field at the address “a” in the index table 102A is “1”, it is determined to match, and the address 0 in the condition table 102B is accessed using the value “0” in the IA field. “Condition a0” stored at address 0 is read out and compared with the inputted “condition a1” by the comparator 102D, and it is determined that there is a mismatch.

  At this time, since the value of the NF field at address 0 is “1”, there is still registered data whose upper 8 bits are “a”. Referring to the value of the NA field at address 0 in the condition table 102B, since NA = 2, the address 2 in the condition table 102B is accessed next. As a result, the “condition a1” stored in the second address is read out and compared with the input “condition a1”, and it is determined that they match. When it is determined that they match, it is decided to delete this condition. Based on this match determination result, the index table 102A and the condition table 102B are updated.

  In this case, since the “condition a0” whose upper 8 bits are “a” remains, the index table 102A need not be rewritten. In the condition table 102B, the address where “condition a1” is stored is finally stored in the WADR register 102C1 as an empty address, and the NF and NA field values of the address where “condition a1” is stored are “ What is necessary is just to copy to the NF and NA field of the address where "condition a0" is stored. Along with this, data in other fields is rewritten as appropriate. Hereinafter, a specific operation when the deletion mode is set will be described.

[Delete condition a1]
Hereinafter, the procedure for deleting “condition a1” will be described in detail with reference to FIG. 14 starting from the state of FIG. Again, the determination result of the mismatch determination circuit 103 is ignored. In this embodiment, the mismatch table 103B of the mismatch determination circuit 103 is not updated. Therefore, the description of the operation of the mismatch determination circuit 103 is omitted, and the operation of the match determination circuit 102 and the update procedure of each table will be described. This operation is performed in accordance with an instruction from the processing unit 102F that has received the mode selection signal (deletion mode).

  (1) “Condition a 1” is sent to the match determination circuit 102 via the buffer circuit 101. The data at address “a” in the index table 102A of the coincidence determination circuit 102 is read (FIG. 19: step S401). In this case, since the value of the MF field at address “a” is “1”, it is determined that they match (NO in step S402). As a result, the value of the IA field at address “a” is used as an address (step S403), and the data at address 0 in the condition table 102B is read (step S404). The address “0” at this time is stored in the CADR register 102C4 (step S403). Then, among the read data, “condition a0” which is data in the FLT field is sent to the comparator 102D and compared with the inputted “condition a1” (step S405). In this case, the comparator 102D determines that there is a mismatch (NO in step S405).

  (2) At this time, since the value of the NF field at address 0 in the condition table 102B is “1” (NO in step S406), there is still other registered data whose upper 8 bits are “a”. Therefore, referring to the value “2” in the NA field at address 0, the data at address 2 in the condition table 102B is read (step S407). Then, among the read data, “condition a1” that is data in the FLT field is sent to the comparator 102D and compared with the inputted “condition a1” (step S408). In this case, the comparator 102D determines that they match (YES in step S408).

  (3) “2”, which is the address determined to match, is stored in the NA field of the CADR register 102C4 (step S412). At the same time, the value immediately before the NA field of the CADR register 102C4, that is, the address “0” of the condition table 102B in which the registration data determined immediately before is stored is moved to the BADR register 102C5 (step S413).

  (4) Further, the values of the NF and NA fields at address 2 of the condition table 102B in which the “condition a1” determined to match are stored in the MCD register 102C3 (step S414). Then, the process proceeds to branch (IV) processing (step S415). FIG. 21 shows a flowchart of the branch (IV) process.

  (5) In the branch (IV) processing, next, the second address of the condition table 102B is used by using the address “2” stored in the CADR register 102C4 and stored as the “condition a1”. And the values of the NF and NA fields of the WADR register 102C1 are copied to the NF and NA fields of the second address. At the same time, the value of the VB field is rewritten as “1” → “0”, and the value of the FLT field is rewritten as “condition a1” → “0” (step S601). As a result, the second address in the condition table 102B becomes a free address, and the third free address next to the second address is set.

  (6) Next, based on the data “0” stored in the BADR register 102C5, that is, the address of the condition table 102B that has been determined last time, the address 0 of the condition table 102B is accessed, and the address 0 The values of the NF and NA fields stored in the MCD register 102C3 are copied to the NF and NA fields (step S602).

  Subsequently, the value of the NF field of the tmp register 102C2 is updated to “1”, and the value of the NA field of the CADR register 102C4 is copied to the NA field (step S603). As a result, the value of the NF / NA field at the address where the deleted “condition a1” is stored is moved to the NF / NA field at the address where “condition a0” is stored.

  (7) Finally, the values of the NF and NA fields of the tmp register 102C2 are copied to the NF and NA fields of the WADR register 102C1 (step S604), and the deletion is completed. In the WADR register 102C1, the address of the condition table 102B in which the deleted registration data is stored is stored and used as the next empty address.

[Delete condition a0]
When deleting “condition a1”, there was no need to change the index table 102A. However, when the “condition a0” to be compared first in the state of FIG. 13 is deleted, the index table 102A must also be changed. Also in this case, each table can be updated based on the determination result of the coincidence determination circuit 102.

  When deleting the “condition a0”, the NF and NA field values of the address of the condition table 102B storing the “condition a0” are set in the MF and IA fields of the index table 102A, and the “condition a0” is stored. If the current empty address (address stored in the WADR register 102C1) is moved to the NF and NA fields of the address in the condition table 102B that has been stored, and the address storing “condition a0” is stored in the WADR register 102C1 Good.

  Hereinafter, a specific procedure for deleting “condition a0” will be described with reference to FIG. Here again, the state (FIG. 13) in which “condition a0”, “condition a1”, and “condition b0” are registered is used as a starting point.

  (1) “Condition a 0” is sent to the match determination circuit 102 via the buffer circuit 101. The data at address “a” in the index table 102A of the coincidence determination circuit 102 is read (FIG. 19: step S401). In this case, since the value of the MF field at address “a” is “1”, it is determined that they match (NO in step S402). As a result, the value of the IA field at address “a” is used as an address (step S403), and the data at address 0 in the condition table 102B is read (step S404). The address “0” at this time is stored in the CADR register 102C4 (step S403).

  Then, among the read data, “condition a0” which is data in the FLT field is sent to the comparator 102D and compared with the inputted “condition a0” (step S405). In this case, the comparator 102D determines that they match (YES in step S405). Then, the values of the NF and NA fields at address 0 of the condition table 102B determined to match are stored in the NF and NA fields of the MCD register 102C3 (step S410), and the process proceeds to branch (III) processing (step S411). . FIG. 20 shows a flowchart of the branch (III) process.

  (2) In the branch (III) process, the address 0 of the condition table 102B is accessed using the address “0” of the condition determined to be a match stored in the NA field of the CADR register 102C4, and the WADR register 102C1 The NF and NA field values (current free addresses) are copied to the NF and NA fields at address 0. Further, the value of the VB field is rewritten as “1” → “0”, and the value of the FLT field is rewritten as “condition a0” → “0” (step S501). With this operation, the address 0 in the condition table 102B is set as an empty address, and the next empty address after the address 0 is set as an address 3.

  (3) At the same time, the address “0” of the condition table 102B stored in the NA field of the CADR register 102C4 and storing the registered data determined to match is copied to the NA field of the tmp register 102C2. At the same time, the value of the NF field of the tmp register 102C2 is set to 1 (step S502).

  (4) Next, “a”, which is the upper 8 bits of the input registration data, is used to access the “a” address in the index table 102A and is stored in the NF and NA fields of the MCD register 102C3. The data, that is, the address of the condition table 102B storing the “condition a1” next to the deleted “condition a0” is copied to the MF and IA fields of the index table 102A (step S503).

  (5) Finally, the NF and NA field values of the tmp register 102C2 are copied to the NF and NA fields of the WADR register 102C1 (step S504), and the deletion of the “condition a0” is completed. In the WADR register 102C1, the address 0, which is the address of the condition table 102B, in which the currently deleted “condition a0” is stored is stored. Next, when registering registration candidate data, the data is stored as registration data at address 0 in the condition table 102B.

[Refresh mode]
Next, the refresh mode will be described. In the above-described deletion mode, the mismatch table 103B of the mismatch determination circuit 103 is not updated. For this reason, there is a possibility that “match” remains set at an address that should originally be a mismatch. If a normal operation is performed with the mismatch table 103B in this state, a packet that originally does not match is determined to match. If the mismatch determination circuit 103 determines that there is a match, the match determination circuit 102 finally determines, so that no error occurs in the determination result. However, if the deletion of registered data is piled up, there is a possibility that the number of packets finally determined by the coincidence determination circuit 102 increases and the throughput decreases. In order to prevent this, the mismatch table 103B is updated based on the data in the condition table 102B.

  This operation is performed in accordance with instructions from the processing units 102F and 103D that have received the mode selection signal (refresh mode) by setting the mode selection signal to the refresh mode. When the refresh mode is set, the mismatch table 103B is initialized as shown in FIG. Other tables are not changed. Next, the data at each address in the condition table 102B is sequentially read, and the data in the FLT field is sent to the mismatch table 103B by the bit division selection circuit 103A.

  With reference to the value of the VB field at this address, if VB = 1, that is, if it is determined that the registered condition is satisfied, data “1” is stored in the corresponding address of each mismatch table 103B. This operation is executed for all addresses in the condition table 102B, and a mismatch table 103B that correctly corresponds to the condition table 102B is configured. This address can be automatically generated by preparing an 8-bit ring counter or the like.

  Up to now, the generation of the mode selection signal is not essential in the present invention, and the details have been touched on, but a plurality of bits may be appropriately provided according to the number of modes. For example, two bits are prepared, and (00) is a normal mode, (01) is a registration mode, (10) is a deletion mode, and (11) is a refresh mode.

  As can be seen from the above description, according to the present embodiment, the packet filter circuit 100 is utilized by using the matching / mismatch determination operation between the collation data and the registration data of the packet filter circuit 100 and the hardware for realizing it. The various tables included in can be automatically created and updated, so software for creating tables and the effort to create tables in advance are no longer required.

  In the above-described embodiment, each functional unit of the packet filter circuit installs a computer program (software) in a computer (hardware) including a CPU (Central Processing Unit), a storage device such as a memory, and an interface. The functional units described above are realized by the various hardware resources of the computer and the computer program cooperating with each other.

  The computer program may be provided in a state stored in a computer-readable recording medium or storage device, or may be provided via an electric communication line.

[Extension of the embodiment]
Although automatic update (registration / deletion, etc.) of various tables has been described for the packet filter circuit 100 having the match determination circuit 102 and the mismatch determination circuit 103 as an embodiment of the present invention, the present invention is not limited to this configuration. Needless to say.

  The gist of the present invention is that the packet filter circuit 100 implements a function of automatically updating various tables using a normal packet determination operation and a circuit that implements it.

  For example, the packet filter circuit 200 that does not have the mismatch determination circuit shown in FIG. 22 also adopts the configuration shown in FIG. 4 to register or delete the match condition in the condition table in the match determination circuit 202. It can be done.

  DESCRIPTION OF SYMBOLS 100 ... Packet filter circuit, 101 ... Buffer circuit, 102 ... Mismatch judgment circuit, 102A ... Index table, 102B ... Condition table, 102C ... Register group, 102C1 ... WADR register, 102C2 ... tmP register, 102C3 ... MCD register, 102C4 ... CADR Register, 102C5 ... BADR register, 102D ... Comparator, 102E1-102E3 ... Selector, 102F ... Processing unit, 103 ... Disagreement determination circuit, 103A ... Bit division / selection circuit, 103 (103B1-103B4) ... Disagreement table, 103C ... AND Gate, 103D, processing unit, 103E, inverter.

Claims (3)

In the data determination device that determines whether or not the input verification data matches the registered data in the registered data group registered in advance,
Registration data storage means for storing the registration data;
Address information storage means for storing address information including an address where the registration data is not stored in the registration data storage means;
A comparison unit that compares the registration data stored in the registration data storage unit with the verification data to obtain a match / mismatch determination result;
When updating the registration data stored in the registration data storage means, the registration candidate data to be registered in the registration data storage means is input, and the registration candidate data and the registration data storage means are stored. If the comparison means performs comparison with the registered data and a determination result of inconsistency is obtained, the inputted registration candidate data is converted based on the address information stored in the address storage means. Means for writing in the registration data storage means as registration data ;
When updating the registration data stored in the registration data storage means, the deletion candidate data to be deleted is received from the registration data storage means, and the deletion candidate data and the registration data storage means are stored. If the comparison result is obtained by the comparison means and a coincidence determination result is obtained, based on the address information stored in the address storage means, the input deletion candidate data and And a means for deleting matching registration data from the registration data storage means . In the data determination device according to claim 1,
Registered data presence / absence information storage storing information indicating whether or not registration data containing a part of information of the verification data as an address and the value of the address as part of information is stored in the registration data storage means Means,
A mismatch determination unit that determines that the verification data does not match the registration data stored in the registration data storage unit based on information stored in the registration data presence / absence information storage unit;
When updating the information stored in the registration data presence / absence information storage means, after deleting all the information stored in the registration data presence / absence information storage means, the registration data stored in the registration data storage means The registered data presence / absence information storage unit is accessed using a part of the read registration data as an address, and the value of the address is used as a part of the address of the accessed registration data presence / absence information storage unit. A data determination apparatus comprising: means for writing information indicating that registration data included is stored in the registration data storage means . A data determination program for causing a computer to execute processing in each unit of the data determination device according to claim 1 .

Images