JP5848185B2 - Frame search processing apparatus and method - Google Patents

Description

  The present invention relates to a frame transfer technique, and more particularly to a frame search processing technique for performing a search process for determining frame processing according to an input frame.

In general, frame search processing devices such as routers, switches, and bridges perform search processing for determining frame processing according to input frames when performing frame transfer, filtering, priority control, and the like.
In this search process, information necessary for the search, for example, header information such as VLAN ID, MAC address and IP address, input port number, frame length, and the like is extracted from the input frame as frame information. A process for finding an entry having a search condition that matches the input frame is executed in comparison with the search condition specified in advance for each entry in the search table.

  When an input frame is input, the frame search processing device first executes the above search processing to find an entry having a search condition that matches the frame information extracted from the input frame, and responds to this entry. A search result, for example, a search result including a port number for outputting a frame, presence / absence of discard, priority when performing priority control, a value after rewriting when rewriting header information of a frame, and the like is obtained.

  Thereafter, the frame search processing device performs frame processing based on the obtained search result on the frame. As this frame processing, for example, a frame is output from the port corresponding to the port number of the search result, and when the search result indicates discard, the frame is discarded without outputting, and the frame is queued according to the priority of the search result. Are stored, and the frame header information is rewritten to the rewritten value of the search result.

In order to perform such search processing, the frame search processing device includes a search table that stores search conditions for each entry. In addition, a comparison circuit is provided that compares the frame information with each search condition stored in the search table and determines whether or not there is a match.
In the above search processing, entry information representing the search condition is read from the search table every clock cycle, and these search conditions are compared with the frame information. By performing the above comparison for all entries in the search table, an entry having a search condition that matches the input frame is searched from the search table.

Conventionally, in such a frame search processing device, when the time required for the search processing for one frame is longer than the frame input interval to the frame search processing device, that is, when the number of entries is large or the frame speed is high. Has been proposed (see, for example, Non-Patent Document 1).
In this technique, for example, eight comparison circuits are provided, and search processing for eight pieces of frame information is performed in parallel.

As a result, even if seven frames are input during the time from the start of search processing for one input frame to completion, the search processing can be completed for all of these frames.
In addition, when P paralleled parallel comparison circuits perform search processing simultaneously with the case where one comparison circuit performs search processing, the number of times of reading entry information from the search table is reduced to 1 / P. Therefore, it has the effect of reducing power consumption.

M. Urano, T. Kawamura, S. Ohteru, H. Suto, K. Kawai, R. Kusaba, N. Miura, J. Kato,. Miyazaki, T. Hatano, S. Yasuda, N. Tanaka, S. Shigematsu , M. Nakanishi, T. Shibata, "The 10G-EPON OLT and ONU LSIs for the coexistence of 10G-EPON and GE-PON toward the next FTTH era", 2011 Symposium on VLSI Circuits (VLSIC), pp.132-133 , 15-17 June 2011.

  However, in such a conventional technique, in the search processing for determining the frame processing according to the input frame, parallel processing is performed in units of frames, and therefore, it is consumed when reading entry information from the search table. There is a problem that power increases in proportion to the number of bits of entry information.

For example, when the search condition is simple, for example, only the condition for the VLAN ID, the number of bits of entry information representing the search condition is small, so that the power consumption when reading the entry information from the search table is small.
However, when performing advanced search processing, for example, when filtering is performed using search conditions that combine various header information from layer 2 to layer 4, the number of bits of entry information representing the search conditions increases.

For example, when the search condition is only the VLAN ID, the entry information is about 12 bits. However, when the destination IP address and the destination TCP port number are combined in addition to the VLAN ID as the search condition, the entry information is 60 bits. .
Therefore, according to the prior art, the power consumed when reading the entry information from the search table increases in proportion to the number of bits of the entry information. Will increase.

  An object of the present invention is to provide a frame search processing technique that can suppress an increase in power consumption even when the number of bits of entry information is increased.

In order to achieve such an object, a frame search processing device according to the present invention includes a frame information extraction unit that extracts frame information for specifying frame processing to be executed on an input frame from the input frame. The frame information extracted by the frame information extraction unit is sequentially compared with a search condition registered in advance for each entry, thereby searching for a matching entry that matches the input frame and corresponding to the obtained matching entry. A search processing unit that outputs the search result as processing information indicating the content of the frame processing to be executed on the input frame, and the search processing unit is configured to search the search corresponding to the entry for each entry. A first search table for storing first entry information comprising a part of a condition, and for each entry, the entry A second search table that stores second entry information that includes portions other than the first entry information in the corresponding search conditions, and the first entry information read from the first search table for each entry A comparison circuit for comparing the second entry information read from the second search table with the frame information to determine whether the entry is a matching entry that matches the input frame; A first read circuit that cyclically reads the first entry information from an entry and outputs the first read signal for output to the comparison circuit to the first search table; and the second read circuit cyclically from each entry. A second readout circuit for outputting a second readout signal for reading out entry information and outputting it to the comparison circuit to the second search table; The comparison circuit compares the first entry information with the frame information first when comparing the first entry information and the second entry information of the entry with the frame information. There wherein determining whether to comply with the frame information, and outputs a first adaptation determination result obtained by the determination to the second readout circuit as read judgment result indicating reading necessity of the second entry information, the When the first conformity determination result indicates conformity, the second entry information is compared with the frame information to determine whether or not the second entry information is compatible with the frame information. If the obtained second conformity determination result indicates conformity, the entry number of the entry, a part of the first entry information, or one of the second entry information Are output as the search result corresponding to the matching entry, and the second readout circuit reads from the second search table when the readout determination result output from the comparison circuit indicates that there is a readout. The second entry information is read, and when the reading determination result indicates no reading, the second entry information is not read from the second search table.
Another frame search processing device according to the present invention includes a frame information extraction unit that extracts frame information for specifying frame processing to be executed on an input frame from the input frame, and the frame information extraction unit. By sequentially comparing the frame information extracted in step 1 with search conditions registered in advance for each entry, a matching entry that matches the input frame is searched, and a search result corresponding to the obtained matching entry is obtained. A search processing unit that outputs processing information indicating the content of the frame processing to be performed on the input frame, and the search processing unit includes, for each entry, a part of the search condition corresponding to the entry. The first entry information is stored, and a second entry comprising a portion other than the first entry information in the search condition. A second search table for storing the second entry number related to the first entry information in addition to the first entry information, a second search table for storing the second entry information for each entry, and for each entry, Comparing the first entry information and the second entry information with the frame information to determine whether the entry is a conforming entry that matches the input frame; The first entry information of the entry is read cyclically, the second entry number added to the first entry information is separated, and the first entry information separated from the second entry number is output to the comparison circuit Based on the second entry number separated by the first readout circuit and the second entry number. A second read circuit that generates a second read signal instructing reading of the second entry information from the entry to be output, and outputs the second read signal to the second search table. When comparing the first entry information and the second entry information of an entry with the frame information, the first entry information is first compared with the first entry information output from the first readout circuit, whereby the first entry information is It is determined whether or not it is compatible with the frame information, and the first conformity determination result obtained by the determination is output to the second reading circuit as a read determination result indicating whether the second entry information needs to be read. When the conformity determination result indicates conformity, whether or not the second entry information conforms to the frame information by comparing the second entry information with the frame information. If the second conformity determination result obtained by the determination indicates conformity, the entry number of the entry, a part of the first entry information, or a part of the second entry information is The second entry from the second retrieval table is output as the retrieval result corresponding to the matching entry, and the second readout circuit, when the readout determination result output from the comparison circuit indicates that there is readout. When the information is read and the read determination result indicates no read, the second entry information is not read from the second search table.
Still another frame search processing device according to the present invention includes a frame information extraction unit that extracts frame information for specifying frame processing to be executed on an input frame from the input frame, and the frame information extraction The frame information extracted in the section is sequentially compared with a search condition registered in advance for each entry, thereby searching for a matching entry that matches the input frame, and a search result corresponding to the obtained matching entry is obtained. A search processing unit that outputs processing information indicating the content of frame processing to be performed on the input frame, and the search processing unit includes, for each entry, a part of the search condition corresponding to the entry. A first search table for storing first entry information, and for each entry, the search corresponding to the entry. A second search table that stores second entry information including a part other than the first entry information in the condition, and the first entry information and the second entry information are compared with the frame information for each entry. Thus, a comparison circuit that determines whether or not the entry is a matching entry that matches the input frame, and a plurality of the first entry information are read out in parallel from each entry in parallel to each comparison circuit. A first readout circuit for outputting a first readout signal for distribution to the first search table; and a second readout signal for cyclically reading out the second entry information from each entry and outputting it to the comparison circuit. And a second readout circuit that outputs the second entry to the second search table, wherein the comparison circuit includes the first entry information and the second entry of the entry. When comparing the frame information with the frame information, first, the first entry information distributed from the first search table is compared with the frame information to determine whether the first entry information matches the frame information. And the first conformity determination result obtained by the determination is output to the second reading circuit as a read determination result indicating whether the second entry information needs to be read, and the first conformity determination result indicates conformity. In this case, the second entry information is compared with the frame information to determine whether the second entry information is compatible with the frame information, and the second conformity determination result obtained by the determination is compatible. Indicates the entry number of the entry, a part of the first entry information, or a part of the second entry information. The second readout circuit outputs a retrieval result, and the second readout circuit corresponds to the first entry information that has obtained the readout judgment result for the readout judgment result indicating the presence of readout among the readout judgment results output from the comparison circuit. The second entry information indicating the second entry information is sequentially accumulated in a queue, and the second entry information from the entry corresponding to the second entry number is based on the second entry number sequentially read from the queue. The second read signal for instructing reading is generated, and the second read signal is output to the second search table. When the read determination result indicates no read, the second read signal is read from the second search table. The second entry information is not read out.

  In addition, a configuration example of the frame search processing device includes a plurality of the comparison circuits, and the frame information extraction is performed for any one of the comparison circuits other than the comparison circuit for which the matching entry is being searched. A frame information distribution circuit for distributing the frame information obtained by the unit.

Also, in one configuration example of the frame search processing device, when the first reading circuit reads the first entry information, a plurality of the first entry information is read in parallel from each entry in parallel. A first read signal for distribution to each of the comparison circuits is output to the first search table, and the comparison circuit compares the first entry information of the entry with the frame information when the first search table is compared. By comparing the first entry information distributed from the frame information with the frame information, it is determined whether or not the first entry information is compatible with the frame information, and the first conformity determination result obtained by the determination is A read determination result indicating whether or not the second entry information needs to be read is output to the second read circuit, and the second read circuit outputs the read determination result output from the comparison circuit. Among the read determination results indicating the presence of reading, the second entry number indicating the second entry information corresponding to the first entry information obtained from the read determination result is sequentially accumulated in a queue, and the read sequentially from the queue Based on the second entry number, the second read signal for instructing reading of the second entry information from the entry corresponding to the second entry number is generated, and the second read signal is generated in the second search table. Is output .

The frame search processing method according to the present invention includes a frame information extraction step in which a frame information extraction unit extracts frame information for specifying frame processing to be executed on an input frame from the input frame, and a search. The processing unit searches the matching entry that matches the input frame by sequentially comparing the frame information extracted in the frame information extraction step with a search condition registered in advance for each entry, and the obtained matching A search processing step for outputting a search result corresponding to the entry as processing information indicating the content of the frame processing to be executed on the input frame, wherein the search processing step includes a first search table for each entry. The first entry information consisting of a part of the search condition corresponding to the entry is stored in A step of storing, for each entry, second entry information comprising a portion other than the first entry information in the search condition corresponding to the entry; Each time the first entry information read from the first search table and the second entry information read from the second search table are compared with the frame information, the entry is A comparison step for determining whether the entry is compatible with the frame; and a first readout signal for the first readout circuit to cyclically read out the first entry information from each entry and output the first entry information to the comparison circuit. A first reading step for outputting to the first search table and a second reading circuit cyclically start the second entry from each entry. A second reading step for outputting to the second search table a second reading signal for reading out information to be output to the comparison circuit, and the comparing step includes the first entry information of the entry and the second entry table. when comparing the second entry information and the frame information, by first comparing the first entry information and the frame information, the first entry information is determined whether or not compatible with said frame information, by the determination the obtained first adaptation judgment result is outputted to the second readout circuit as read judgment result indicating reading necessity of the second entry information, when said first matching determination result indicates fit, the second By comparing the entry information with the frame information, it is determined whether the second entry information is compatible with the frame information, and the second appropriate information obtained by the determination is determined. If the match determination result indicates a match, the entry number of the entry, a part of the first entry information, or a part of the second entry information is output as the search result corresponding to the match entry, The second reading step reads the second entry information from the second search table when the read determination result output from the comparison circuit indicates that there is a read, and the read determination result is read In the case of “none”, the second entry information is not read from the second search table.
According to another frame search processing method of the present invention, the frame information extraction unit extracts frame information for specifying frame processing to be executed for the input frame from the input frame. The search processing unit searches for a matching entry that matches the input frame by sequentially comparing the frame information extracted by the frame information extraction unit with a search condition registered in advance for each entry. A search processing step for outputting a search result corresponding to the matching entry as processing information indicating the content of the frame processing to be executed on the input frame, wherein the search processing step includes the first search table, For each entry, first entry information including a part of the search condition corresponding to the entry is stored. Both the step of adding the second entry number related to the second entry information comprising the portion other than the first entry information in the search condition to the first entry information and storing the second entry number, and the second search table includes the entry Storing the second entry information for each entry and a comparison circuit comparing the first entry information and the second entry information with the frame information for each entry, so that the entry becomes the input frame. A comparison step for determining whether or not the matching entry matches, and a first reading circuit cyclically reads out the first entry information of each entry from the first search table and adds the first entry information to the first entry information. The second entry number is separated, and the first entry information separated from the second entry number is sent to the comparison circuit. A first reading step and a second reading circuit reading out the second entry information from the entry corresponding to the second entry number based on the second entry number separated by the first reading circuit. A second reading step for generating a second reading signal to instruct and outputting the second reading signal to the second search table, wherein the comparing step includes the first entry information of the entry and the second reading step. When comparing the entry information with the frame information, first, it is determined whether or not the first entry information matches the frame information by comparing with the first entry information output from the first readout circuit; The first conformity determination result obtained by the determination is output to the second readout circuit as a read determination result indicating whether the second entry information needs to be read, and the first conformity determination is performed. If the result indicates conformity, the second entry information is compared with the frame information to determine whether the second entry information is compatible with the frame information, and the second obtained by the determination When the conformity determination result indicates conformity, the entry number of the entry, a part of the first entry information, or a part of the second entry information is output as the search result corresponding to the conforming entry, The second reading step reads the second entry information from the second search table when the read determination result output from the comparison circuit indicates that there is a read, and the read determination result is read In the case of “none”, the second entry information is not read from the second search table.
According to still another frame search processing method of the present invention, a frame information extraction step in which a frame information extraction unit extracts, from the input frame, frame information for specifying frame processing to be executed on the input frame. The search processing unit sequentially searches the matching information that matches the input frame by comparing the frame information extracted by the frame information extraction unit with a search condition registered in advance for each entry. A search processing step for outputting a search result corresponding to the matched entry as processing information indicating the content of the frame processing to be executed on the input frame, the search processing step comprising: a first search table; For each entry, first entry information including a part of the search condition corresponding to the entry is recorded. A second search table storing, for each entry, second entry information consisting of portions other than the first entry information in the search condition corresponding to the entry, and a comparison circuit, For each entry, a comparison step for comparing the first entry information and the second entry information with the frame information to determine whether the entry is a conforming entry compatible with the input frame, and a first reading A first reading step in which a circuit cyclically reads a plurality of first entry information from each entry in parallel and outputs a first read signal for distribution to each comparison circuit to the first search table. And a second readout circuit cyclically reads out the second entry information from each entry and outputs the second entry information to the comparison circuit. A second read step for outputting a read signal to the second search table, and the comparing step first compares the first entry information and the second entry information of the entry with the frame information. By comparing the first entry information distributed from the first search table with the frame information, it is determined whether or not the first entry information is compatible with the frame information, and the first match obtained by the determination is determined. The determination result is output to the second reading circuit as a reading determination result indicating whether or not the second entry information needs to be read. When the first conformity determination result indicates conformity, the second entry information is converted into the frame information. To determine whether the second entry information is compatible with the frame information, and the second determination result obtained by the determination is compatible. The entry number of the entry, a part of the first entry information, or a part of the second entry information is output as the search result corresponding to the matching entry, and the second reading step Is a second entry number indicating the second entry information corresponding to the first entry information obtained from the read determination result for the read determination result indicating the presence of reading out of the read determination results output from the comparison circuit Are sequentially stored in the queue, and based on the second entry number sequentially read from the queue, the second read signal for instructing the reading of the second entry information from the entry corresponding to the second entry number Generating and outputting the second read signal to the second search table, and when the read determination result indicates no read, the second search signal is output. It is obtained so as not read the second entry information from Buru.

  According to the present invention, as a result of the comparison between the first entry information and the frame information, it is determined whether it is necessary to read the second entry information, which is the remaining entry information, and only when the reading is necessary, The second entry information is read out. For this reason, there are two cases: an entry that reads only a part of entry information (first entry information) and an entry that reads all entry information (first entry information + second entry information).

  Accordingly, since it is not necessary to read out all entry information for all entries, the number of bits of entry information to be read can be reduced. For this reason, the number of bits of entry information increases, for example, when the destination IP address and the destination TCP port number are combined in addition to the VLAN ID as a search condition used for the search processing for determining the frame processing according to the input frame. Even in this case, an increase in the number of bits of entry information to be read can be suppressed, and as a result, an increase in power consumption required for the frame search process can be suppressed.

It is a block diagram which shows the structure of the frame search processing apparatus concerning 1st Embodiment. It is a block diagram which shows the structure of the search process part of the frame search processing apparatus concerning 1st Embodiment. It is a block diagram which shows the principal part of the search process part concerning 1st Embodiment. It is a time chart which shows operation | movement of the search process part concerning 1st Embodiment. It is a block diagram which shows the principal part of the search process part concerning 2nd Embodiment. It is a time chart which shows operation | movement of the search process part concerning 2nd Embodiment. It is a block diagram which shows the structure of the search process part concerning 3rd Embodiment. It is a block diagram which shows the principal part of the search process part concerning 3rd Embodiment. It is a time chart which shows operation | movement of the search process part concerning 3rd Embodiment. It is a block diagram which shows the structure of the search process part concerning 4th Embodiment. It is a block diagram which shows the principal part of the search process part concerning 4th Embodiment. It is a time chart which shows operation | movement of the search process part concerning 4th Embodiment. It is a time chart (continuation) which shows operation | movement of the search process part concerning 4th Embodiment.

Next, embodiments of the present invention will be described with reference to the drawings.
[First Embodiment]
First, with reference to FIG. 1, a frame search processing apparatus 10 according to a first embodiment of the present invention will be described. FIG. 1 is a block diagram illustrating a configuration of a frame search processing apparatus according to the first embodiment.

  The frame search processing apparatus 10 includes a frame information extraction unit 11, a search processing unit 12, a frame buffer 13, and a frame synthesis unit 14 as main functional units.

The frame information extraction unit 11 has a function of extracting frame information FD for specifying frame processing to be executed for the input frame FIN from the input frame FIN.
The search processing unit 12 searches the matching information matching the input frame FIN by sequentially comparing the frame information FD extracted by the frame information extracting unit 11 with the search conditions registered in advance for each entry. The search result SR corresponding to the matching entry is output as processing information indicating the content of the frame processing to be executed for the input frame FIN.

The frame buffer 13 has a function of storing data of the input frame FIN until a search result SR is obtained by a search process in the search processing unit 12 for the frame information FD of the input frame FIN.
The frame synthesis unit 14 has a function of rewriting the data of the input frame FIN output from the frame buffer 13 based on the search result SR obtained by the search processing unit 12 and outputting it as the output frame FOUT.

  In FIG. 1, the case where the input frame FIN is rewritten based on the search result SR obtained by the search processing unit 12 has been described as an example. However, the data of the input frame FIN need not be rewritten. When the frame search processing apparatus 10 performs frame processing such as search for the presence / absence of discard of the input frame FIN and search for the transmission destination, the frame synthesis unit 14 is not provided.

  For example, in the case where the presence / absence of frame discard is obtained as the search result SR, that is, in the case of a device that performs frame filtering, the frame search processing device 10 receives the input from the frame buffer 13 when the search result SR is no frame discard. Data of the frame FIN is output and output outside the apparatus. In addition, when the search result SR is frame discard, the data of the input frame FIN is idle-read from the frame buffer 13, and the data reading position from the frame buffer 13 is the input frame FIN accumulated after the input frame FIN. Preparation for outputting the input frame FIN stored next to the input frame FIN, such as moving to the data start position.

  When the transmission destination (output port number) is obtained as the search result SR, that is, when the frame transfer device has a plurality of ports, the frame search processing device 10 outputs the data of the input frame FIN from the frame buffer 13. From the port indicated by the output port number that is the search result SR, the information is output outside the apparatus. If the input frame FIN and the search result SR can be synchronized, the frame search processing device 10 does not necessarily have the frame buffer 13, and the function of the frame buffer 13 may be realized by the next external device. .

Next, a detailed configuration of the search processing unit 12 will be described with reference to FIG.
FIG. 2 is a block diagram illustrating a configuration of a search processing unit of the frame search processing apparatus according to the first embodiment.
The search processing unit 12 includes, as main circuit units, a frame information distribution circuit 21, a first search table 22A, a second search table 22B, a first readout circuit 23A, a second readout circuit 23B, and N comparison circuits. 3n (n = 1 to N; N is a natural number of 2 or more) and a search result merging circuit 24 are provided.

  The frame information distribution circuit 21 includes a dedicated signal processing circuit, and the frame information FD obtained by the frame information extraction unit 11 is converted into any one of the comparison circuits 3n other than the comparison circuit that is searching for a matching entry. The comparison circuit 3n has a function of distributing as frame information FDn. In this embodiment, a case where a plurality of comparison circuits 3n are provided in parallel will be described as an example. However, the present invention is not limited to this, and the present invention is similarly applied to a case where there is one comparison circuit 3n. In this case, the frame information distribution circuit 21 can be omitted.

The first search table 22A includes a storage device such as a semiconductor memory, and has a function of storing first entry information including a part of search conditions corresponding to the entry for each entry.
The second search table 22B includes a storage device such as a semiconductor memory, and has a function of storing, for each entry, second entry information including a portion other than the first entry information in the search condition corresponding to the entry. ing.

The first read circuit 23A is composed of a dedicated signal processing circuit. The first read signal RA for cyclically reading the first entry information EDA from each entry of the first search table 22A and outputting it to each comparison circuit 3n. Is output to the first search table 22A.
The second readout circuit 23B is composed of a dedicated signal processing circuit and cyclically reads out the second entry information EDB from each entry of the second search table 22B and outputs a second readout signal for output to each comparison circuit 3n. It has a function of outputting to the second search table 22B.
The search result merge circuit 24 receives the search results SRn from the respective comparison circuits 3n (n = 1 to N), and sequentially outputs them to the frame synthesis unit 14 as the search results SR.

  Each comparison circuit 3n includes a dedicated signal processing circuit. For each entry, the comparison circuit 3n receives the first entry information EDA read from the first search table 22A and the second entry information EDB read from the second search table 22B. By comparing with the frame information FDn from the frame information distribution circuit 21, it has a function of determining whether or not the entry is a conforming entry that matches the input frame FIN.

  In addition, when comparing the first entry information EDA and the second entry information EDB of the target entry with the frame information FDn, the comparison circuit 3n first compares the first entry information EDA with the frame information FDn. Thus, a function for determining whether or not the first entry information EDA matches the frame information FDn, a function for outputting to the second reading circuit 23B as a reading determination result RJ indicating whether or not the second entry information EDB is to be read, When the first conformity determination result obtained by the determination indicates conformity, the second entry information EDB is compared with the frame information FDn to determine whether the second entry information EDB conforms to the frame information FDn. When the function and the second conformity determination result obtained by the determination indicate conformity, the entry number of the entry, the second Some of the entry information EDA, or a portion of the second entry information EDB, and a function of outputting a search result SRn corresponding Relevant entries.

  Further, the second reading circuit 23B has a function of reading the second entry information EDB from the second search table 22B when the reading determination result RJ output from the comparison circuit 3n indicates that there is reading (requires reading). When the reading determination result RJ indicates no reading (no reading required), the second entry information EDB is not read from the second search table 22B.

  The number N of the comparison circuits 3n is not necessarily two or more. However, when N = 1, the frame information distribution circuit 21 is not provided. If the maximum number Nmax of input frame information FD is set within the time Ts from when the search processing unit 12 inputs the frame information FD until the search result SR corresponding to the frame information FD is obtained, N is set to Nmax By doing so, it can be guaranteed that the search result SR is obtained for the frame information FD.

  When N is smaller than Nmax, when the search processing unit 12 inputs the frame information FD at a high rate, that is, when the number of frame information FD input per unit time Tc is greater than N / Tc, There is a possibility that a situation occurs in which the comparison circuit 3n is performing a search process on the already input frame information FDn. In such a situation, since the search result SR for the frame information FD input by the search processing unit 12 cannot be obtained, the original search result SR cannot be applied to the input frame FIN from which the frame information FD is extracted.

  Each of the first search table 22A and the second search table 22B has Ne (N is a natural number of 1 or more) entries i (i = 1 to Ne). The first search table 22A stores first entry information EDA [i] in each entry i. The second search table 22B stores second entry information EDB [i] in each entry i.

  The first entry information EDA [i] stored in the entry i of the first search table 22A and the second entry stored in the entry i having the same entry number as the first entry information EDA [i] in the second search table 22B. The set with the entry information EDB [i] corresponds to the entry information in the prior art described above. That is, the first search condition [i] expressed by the first entry information EDA [i] matches the frame information FD, and the second search condition [i] expressed by the second entry information EDB [i]. When the frame information FD matches, the entry i having a search condition that matches the input frame FIN is found.

The first search table 22A receives the first read signal RA from the first read circuit 23A and stores it from the address indicated by the first read signal RA, that is, from the entry i at the timing indicated by the first read signal RA. The first entry information EDA [i] is read out.
The second search table 22B receives the second read signal RB from the second read circuit 23B and stores it from the address indicated by the second read signal RB, that is, the entry i at the timing indicated by the second read signal RB. The second entry information EDB [i] is read.

  The frame information distribution circuit 21 receives the frame information FD from the frame information extraction unit 11, determines a comparison circuit 3n that is an output destination of the frame information FD based on a predetermined comparison circuit selection method, and the comparison circuit 3n has a function of outputting the frame information FD as frame information FDn.

  An example of the comparison circuit selection method is to determine whether or not each comparison circuit 3n is performing a search process, and to select one of the comparison circuits 3n that is not performing the search process. As an example of realizing the comparison circuit selection method with a simple circuit, there is a method of selecting the comparison circuit 3 (n + 1) having a number obtained by adding 1 to the number n of the comparison circuit 3n selected at the previous input when frame information is input. In this comparison circuit selection method, when the number n of the comparison circuit 3n selected at the previous input is N, the comparison circuit 31 of number 1 is selected and the comparison circuit 3n is selected cyclically.

  Another example of the comparison circuit selection is a method in which the frame information distribution circuit 21 determines whether or not each of the comparison circuits 3n has been searched. That is, the frame information distribution circuit 21 measures the elapsed time from the time when the previous frame information FD was input to each comparison circuit 3n, and when the measurement time reaches a certain time required for completion of the search, the comparison circuit It is determined that 3n has completed the search, and one of the comparison circuits 3n that has completed the search is selected.

The comparison circuit 3n performs a search process for searching for an entry having a search condition matching the frame information FDn according to the input of the frame information FDn (n = 1 to N) from the frame information distribution circuit 21. Run.
In this search process, the comparison circuit 3n uses the input frame information FDn and the first entry information EDA [i] read from the entry i (i = 1 to Ne) of the first search table 22A by the first reading circuit 23A. The frame information FDn is subjected to a first conformity determination for determining whether or not the frame information FDn conforms to a search condition represented by the first entry information EDA [i]. A determination result CJAn [i] (not shown) is obtained.

  Further, the comparison circuit 3n obtains the second entry information EDB [i] from the entry i (i = 1 to Ne) of the second search table 22B based on the obtained first suitability determination result CJAn [i]. A second search table read determination for determining whether to read is performed, and the obtained read determination result RJn [i] is output to the second read circuit 23B.

In this example, when the first conformity determination result CJAn [i] indicates conformity, it is determined that the second entry information EDB [i] is read from the second search table 22B (the second search table is read), and the first When the one conformity determination result CJAn [i] indicates nonconformity, it is determined that the second entry information EDB [i] is not read from the second search table 22B (the second search table is not read).
That is, in this example, it is not necessary to perform the second search table read determination separately from the first suitability determination, and the read determination result RJn [i] can be obtained using the first match determination result CJAn [i]. it can.

  Here, when the comparison circuit 3n outputs the read determination result RJn [i] indicating that the second search table is read to the second read circuit 23B based on the frame information FDn and the first entry information EDA [i]. The second reading circuit 23B reads the second entry information EDB [i] from the second search table 22B and inputs the second entry information EDB [i] to the comparison circuit 3n.

  At this time, the comparison circuit 3n determines whether the frame information FDn conforms to the second entry information EDB [i] based on the frame information FDn and the second entry information EDB [i]. The second conformity determination is performed to obtain a second conformity determination result CJB [i] (not shown) as a circuit internal signal.

  Thereby, even when the first partial comparison circuit that compares the frame information FDn and the first entry information EDA [i] in the comparison circuit 3n is performing the search process, the second search table 22B is read. In the absence period, for example, the clock supply and the power supply are stopped, and the operation of the second partial comparison circuit that compares the frame information FDn and the second entry information EDB [i] in the comparison circuit 3n is stopped. Therefore, power consumption can be reduced.

  The comparison circuit 3n determines whether the search condition of the entry i matches the frame information FDn based on the first match determination result CJAn [i] and the second match determination result CJB [i]. Perform integrated conformity judgment.

  As an example of the integrated suitability determination, when the first suitability determination result CJAn [i] indicates that there is a conformity and the second conformance determination result CJB [i] indicates that there is a conformance, In other cases, that is, when the first conformity determination result CJAn [i] indicates no conformity, or when the first conformity determination result CJAn [i] indicates conformity, the second conformity determination result CJB [ When i] indicates that there is no conformity, it is determined as nonconformity in the integrated conformity determination. In this example, when the first conformity determination result CJAn [i] is nonconforming, the read determination result RJn [i] is not read, and the second conformity determination is unnecessary.

  As another example of the integrated suitability determination, when the first suitability determination result CJAn [i] indicates that there is a conformity, or when the second conformance determination result CJB [i] indicates that there is a conformance, the entry i In other cases, that is, when the first conformity determination result CJAn [i] is incompatible and the second conformity determination result CJB [i] is incompatible, the integrated conformity is determined. Judged as nonconforming. In this example, when the first conformity determination result CJAn [i] indicates conformity, the read determination result RJn [i] is not read, and the second conformity determination is not necessary.

  At this time, when the first conformity determination result CJA is nonconforming, the integrated determination result does not necessarily become nonconforming. However, generally, when the first conformity determination result CJA is nonconforming, the integrated determination result is regarded as nonconforming. That is, a search is generally performed using an AND of the first search condition represented by the first entry information EDA [i] and the second search condition represented by the second entry information EDB [i] as a condition of the integrated suitability determination. The reason is that the search of “first search condition OR second search condition” can be realized by dividing the search into two entries, that is, the entry of only the first search condition and the entry of only the second search condition. A plurality of entries having the same search result SR is equivalent to one entry using the OR of the search conditions of the entry as a search condition. However, the search for “first search condition AND second search condition” This is because it is difficult to realize the search by one search condition OR second search condition.

  Further, when the entry determined to be compatible by the integrated compatibility determination is found or when the frame information FDn has been determined for all the entries, the comparison circuit 3n ends the search and outputs the search result SRn. . That is, when there is a match in the integrated suitability determination for the entry i, the entry i is searched even if there is an entry that has not been subjected to the integrated suitability determination other than the entry i for the frame information FDn. It is possible to adopt the result SRn so that the processing for the remaining entries, for example, the reading of the first entry information EDA and the second entry information EDB, the conformity determination, the integrated conformity determination, and the like are not performed.

Further, when the integrated suitability determination for the entry i becomes nonconforming, processing for the entry for which the integrated suitability determination has not been performed, for example, reading of the first entry information EDA and the second entry information EDB, the conformity determination, the integrated conformance determination. Continue the process.
Further, when the integrated suitability determination is performed for all the entries in the search table by continuing the processing, the processing is ended even if the integrated suitability determination result for the last entry is nonconforming.

  At this time, when the integrated conformity determination result with respect to the last entry is nonconforming, the search result SRn in the case where all the preset entries are unconforming is adopted. During the search for the frame information FDn, even if the first suitability determination result CJA is non-conforming in a certain entry, it may be possible to find a conforming entry among the remaining entries. For this reason, the search is not terminated just because the first conformity determination result CJA is nonconforming.

  In the example in which the entry entry priority is included in the first entry information EDA or the second entry information EDB, and the entry having the highest entry priority is found among the entries determined to be compatible by the integrated suitability determination, The search is not terminated when one entry is found to be matched by the match determination, but the integrated match determination is completed for all entries, or the upper limit application priority, that is, a value within a range that can be set as the application priority. The search is terminated only when an entry having an application priority having the highest application priority is found.

The comparison circuit 3n is a result obtained by the integrated suitability determination, for example, information indicating a result included in the entry number i matched in the determination or the second entry information EDB [i] of the entry; The indicated information, the port number indicating the transmission destination, and the like are output to the search result merging circuit 24 as the search result SRn.
The application priority is used to determine which entry's search result SRn is to be adopted when there are a plurality of entries determined to be suitable in the search table. The value specified for the entry. For example, an entry having the smallest application priority value among entries determined to be suitable is adopted.

  At this time, instead of setting the application priority value for each entry, it is also possible to use the entry number as the application priority. In this case, the search table among the entries determined to be compatible. The entry located at the top of the is adopted. In addition, by setting an application priority value for each entry, the same search can be performed without being restricted by the entry number. Therefore, an entry moving process for creating an empty entry between entries for adding an entry is performed. It becomes unnecessary.

For the entry i, the comparison circuit 3n obtains the first match determination result CJAn [i] obtained after the first entry information EDA [i] is read from the first search table 22A, and the second entry information EDB [ i] is read from the second search table 22B, and the integrated suitability determination is performed based on the second suitability determination result CJB [i] obtained.
Before obtaining the second conformity determination result CJB [i], when the first conformity determination is performed for the next entry (i + 1) to obtain the first conformity determination result CJAn [i + 1], the first conformity determination for the entry i The first match determination result CJAn [i + 1] for the entry (i + 1) together with the result CJAn [i] is temporarily held until the integrated match determination is performed.

  That is, the first conformity determination result CJAn [i] needs to be retained until the second conformity determination result CJBn [i] is obtained and the integrated conformity determination is performed. 1 Conformity determination result CJAn is also held. As a result, it is not necessary to set the entry update interval longer than the time from when the first conformity determination result CJAn [i] is obtained until the second conformity determination result CJBn [i] is obtained, and the search processing speed can be improved.

  The comparison circuit 3n inputs the frame information FDn as an example of a determination end specifying method for knowing the time point when the determination of the frame information FDn (n = 1 to N) is completed for all the entries i (i = 1 to Ne). There is a method in which the comparison circuit 3n measures the elapsed time from the time point, and uses the timing when the elapsed time reaches a predetermined time Ts. This determination end specifying method is a method using the fact that the processing time of each entry is a fixed value and the number of entries is also a fixed value, so that the time taken to search all entries is also a fixed value. As another determination end specifying method, the number of times of integrated conformity determination from the time when the frame information FD is input to the comparison circuit 3n (n = 1 to N) is counted, and the number of times reaches N (total number of entries). Timing can also be used.

  The search result merging circuit 24 receives the search results SRn from each comparison circuit 3n (n = 1 to N), and outputs these as search results SR to the frame synthesis unit 14.

  The first read circuit 23A outputs a first read signal RA for reading the entry i to the first search table 22A while changing the entry i (i = 1 to Ne) with the passage of time based on the clock. As a result, the first entry information EDA [i] stored in the first search table 22A is read one after another. Thereby, the first entry information EDA [i] is distributed to each comparison circuit 3n (n = 1 to N).

  As an example of a method of reading the first entry information EDA, the first search table 22A is constituted by a first table memory, and the first entry information EDA is assigned to each address a1 (a1 = 0 to Ne-1) of the first table memory. There is a method of storing [a1 + 1] and sequentially changing the read address a1 from 0 to Ne-1 as time passes. In this method, when the address a1 reaches the address of the last entry Ne-1, the first entry information EDA is read cyclically by returning to 0.

  Here, the first readout circuit 23A inputs the search state SSn indicating whether or not the search process output from each comparison circuit 3n (n = 1 to N) is being performed, and all the comparison circuits 3n perform the search process. By not performing the reading during a period during which no reading is performed, it is possible to reduce power consumption during a period during which reading of the first search table 22A is unnecessary.

  The above method can also be applied to the case where a part of the table memory is used as the first search table 22A instead of the entire area of the table memory. In this case, the address a1 is not incremented by +1 in the range of 0 to Ne-1, but the entry i to be read is incremented by +1 (i = 1 next to i = Ne), and the address a1 is calculated by A0 + (i−1) * A1. In this case, A0 indicates the lower limit value of the memory area allocated to the first search table 22A, and A1 indicates an address increment corresponding to the memory amount necessary to store one piece of first entry information EDA. Note that the data stored in the area from the address a1 to immediately before the address a1 + A0 is referred to as first entry information EDA [i].

  Similarly to the first read circuit 23A, the second read circuit 23B changes the entry i (i = 1 to Ne) according to the passage of time based on the clock and outputs a second read signal RB for reading the entry. By outputting to the second search table 22B, the second entry information EDB [i] stored in the second search table 22B is read one after another. Thus, the second entry information EDB [i] is distributed to each comparison circuit 3n (n = 1 to N). However, the second entry information EDB [i] is read after a predetermined time difference Td from the reading of the first entry information EDA [i].

  The second entry information EDB [i] is read only when the read determination result RJn [i] indicating that the second search table is read is input from at least one comparison circuit 3n. Note that the comparison circuit 3n that has not performed the search process outputs the read determination result RJn [i] indicating that the second search table is not read, and thus does not distinguish whether the comparison circuit 3n is performing the search process. In addition, it is possible to determine whether or not the second entry information EDB [i] is read based only on each read determination result RJn [i] (n = 1 to N).

  The time difference Td is as follows. (A) The first read circuit 23A starts reading the first entry information EDA [i] (i = 1 to Ne), and then the comparison circuit 3n (n = 1 to N) Time until 1 entry information EDA [i] is input (= time required to read first search table 22A + time required to distribute first entry information EDA to each comparison circuit 3n), (b) comparison Time from when the circuit 3n (n = 1 to N) inputs the first entry information EDA [i] to when the read determination result RJn [i] is output to the second read circuit 23B (= second search table read determination) (C) The second read circuit 23B inputs the read determination result RJn [i] from all the comparison circuits 3n (n = 1 to N) and then reads the second entry information EDB [i]. Second entry information determined to be performed DB [i] (i = 1~Ne) reading time until you start (= the time required to determine the reading whether the second search table 22B) of the sum of.

  The second read circuit 23B determines the read from each comparison circuit 3n (n = 1 to N) after a delay of Td from the time when the first read circuit 23A reads the first entry information EDA [i] of the entry i. When the result RJn [i] includes that indicating that the second search table is read, the second entry information EDB [i] of the entry i is read.

  As an example of this reading method, the second search table 22B is constituted by a second table memory, and the second entry information EDB [a2 + 1] is stored in each address a2 (a2 = 0 to Ne-1) of the second table memory. The read address a2 is set as the read address a1 of the first read circuit 23A generated for reading from the first search table 22A before the time Td. Further, as a read control signal which is a signal indicating whether or not reading from the second table memory is performed, a logical operation on a signal indicating the read determination result RJn [i], that is, at least one read determination result RJ is the second. When the retrieval table is read, the result of the operation is used in which the reading control signal has a value indicating the reading.

  Next, the first readout circuit 23A and the second readout circuit 23B according to the present embodiment will be described with reference to FIG. FIG. 3 is a block diagram illustrating a main part of the search processing unit according to the first embodiment.

As shown in FIG. 3, the first read circuit 23A includes a first read address generation unit 41A and a first read effective generation unit 42A.
The first read address generation unit 41A sets a value obtained by adding 1 to the first read address RAA [i−1], which is the first read address RAA value output one cycle before the first read address RAA [ i]. As a result, the value of the first read address RAA [i] of entry i is i−1. However, when the operation of the frame search processing device 10 starts and when the first read address RAA value becomes Ne, 0 is output.

The first read valid generation unit 42A has a function of outputting a first read valid signal REA [i] indicating validity when one or more search states SSn indicate that the search process is being performed. Note that if all search is stopped, the first read valid signal REA [i] indicating invalidity is output.
The first read signal RA [i] output from the first read circuit 23A has a first read valid signal REA [i] and a first read address RAA [i].

By inputting the first read signal RA [i], the first search table 22A receives the first read address RAA [when the first read valid signal REA [i] indicates valid after a predetermined time from the input. The first entry information EDA [i] stored at the address of the first table memory M1 (memory for the first search table 22A) indicated by i] is output to each comparison circuit 3n.
The first read address RAA [i] is output to the second read circuit 23B in addition to the first search table 22A, and the second entry information from the second table memory M2 (memory for the second search table 22B). Used to read EDB [i].

The second read circuit 23B includes a second read address generation unit 41B and a second read effective generation unit 42B.
The second read effective generation unit 42B receives the read determination result RJn [i] from each comparison circuit 3n (n = 1 to N), and when one or more read determination results RJn [i] indicate that there is a read, It has a function of outputting a second read valid signal REB [i] indicating validity. Note that when all indicate no reading, the second reading valid signal REB [i] indicating invalidity is output. That is, for n = 1 to N, the logical sum of the read determination results RJn [i] becomes the second read valid signal REB [i].

  The second read address generator 41B receives the first read address RAA [i], delays the first read address RAA [i] by time Td, and outputs the value as the second read address RAB [i]. It has a function to do. Since the first read address RAA [i] is a signal that increases by +1 for each clock, the first read address RAA [i] does not have to be delayed by Td by the shift register to generate the second read address RAB [i]. It is also possible to generate using a counter.

  Note that the first table memory and the second table memory each store entry information of the same entry at the same address. That is, when the first entry information EDA [i] of the entry i is stored at the address a of the first table memory, the second entry information EDB [i] of the entry i is stored at the address a of the second table memory. Has been. The second read valid signal REB [i] indicating the validity / invalidity of reading the second entry information EDB [i] of the entry i by delaying the time Td from the input of the first read address RAA [i] and outputting it. The second read address RAB [i], which is the address stored in the second table memory, can be output at the same timing as when the second entry information EDB [i] of the entry i is output.

[Operation of First Embodiment]
Next, the operation of the search processing unit 12 according to the present embodiment will be described with reference to FIG. FIG. 4 is a time chart showing the operation of the search processing unit according to the first embodiment, and the passage of time for each signal in the search processing unit 12 taking the case where the number N of comparison circuits 3n is 2 as an example. Changes with (from left to right) are shown.

  Each signal in the search state SSn (n = 1, 2) is a signal indicating H level: search processing being in progress / L level: search is being stopped, and frame information FDn (n = 1, 2) is input to the comparison circuit 3n. At this time, the H level: search processing is in progress, and after reading all entries (16) for one frame information FD from the table (after 16 cycles have elapsed from the start of processing), the L level: search processing is stopped. Become.

  The signal of the first read valid signal REA [i] is a signal representing H level: valid / L level: invalid, and is the logical sum of the signals in the search state SS1 and the search state SS2. That is, the first read valid signal REA [i] is valid during a period when one or more of the comparison circuits 3n are in the search process, so that the first read address RAA [i] in the first table memory is positioned. The stored first entry information EDA [i] is read out.

  The signal of the first read address RAA [i] repeatedly increases by +1 for each clock in the range of 0-15. However, the value after 15 is 0. The number in each box representing the first read address RAA [i] in FIG. 4 represents the entry number i (1 to 16), and the signal value of the entry number i is i-1. That is, the first entry information EDA [i] is stored in the address i-1 of the first table memory, the entry number is incremented every clock cycle, and the first entry information EDA corresponding to the entry number is stored. Read from the first table memory.

  The first read valid signal REA [i] and the first read address RAA [i], which are signals for reading the first entry information EDA [i], are input to the first table memory at the same time. However, a memory that is not simultaneously input (for example, a memory in which the first read enable signal REA [i] needs to be input a predetermined cycle before the first read address RAA [i]) is used as the first table memory. In this case, the first read circuit 23A generates the first read valid signal REA [i] and the first read address RAA [i] according to the signal input method defined by the memory. become.

  In the case of a memory that is accessed by using a command instead of reading by the first read valid signal REA [i] and the first read address RAA [i], the first read circuit 23A has the first read valid signal REA [ When i] is valid, the first read command [i] for reading the data stored at the position of the first read address RAA [i] is generated.

  The first entry information EDA [i] is data read from the first search table 22A two cycles after the input of the first read address RAA [i] when the first read valid signal REA [i] is valid. . The two-cycle delay is latched before outputting the data stored in the cells in the memory and the one-clock delay generated by latching the signal such as the address input to the first table memory. Therefore, it is a value obtained by adding a delay of 1 clock generated for the purpose.

  In the case of a device in which the type of the first table memory, the memory, and the first reading circuit 23A, etc. are configured as separate components, there is a possibility that the delay is larger than the above. Further, a configuration in which the amount of delay varies depending on the state of the memory, for example, whether or not the memory is accessed from the outside, instead of a fixed delay. The numbers in each box representing the first entry information EDA [i] in FIG. 4 represent the entry numbers i (1 to 16).

Each signal of the read determination result RJn [i] (n = 1, 2) is a signal indicating H level: read / L level: no read.
Each comparison circuit 3n (n = 1, 2) outputs the read determination result RJn [i] after one cycle from the input of the first entry information EDA [i]. This one-cycle delay is caused by the comparison circuit 3n latching and outputting the read determination result RJn [i]. Note that when the read determination result RJn requires a complicated calculation of the first entry information EDA [i] and the frame information FDn, there may be a delay greater than one cycle.

  FIG. 4 shows a case where the read determination result RJ1 [i] indicates that there is a read at the timing corresponding to the entry numbers 5 and 12. That is, the comparison circuit 31 obtains the read determination result RJ1 for reading the second entry information EDB [5] and the second entry information EDB [12]. In this example, the first suitability determination result CJAn [i] and the read determination result RJn [i] have the same value, and the frame information FD1 is changed to the first entry information EDA [5] and the first entry information EDA [12]. It will also fit.

  Similarly, FIG. 4 shows a case where the reading determination result RJ2 [i] indicates reading at the timing corresponding to the entry numbers 7 and 10. That is, the comparison circuit 32 obtains the read determination result RJ2 for reading the second entry information EDB [7] and the second entry information EDB [10].

  The signal of the second read valid signal REB [i] is a signal representing H level: valid / L level: invalid, and the logical sum of the read determination results RJn [i] becomes the second read valid signal REB [i]. ing. In this example, validity is shown for the entries 5, 7, 10, and 12 of the second search table 22B, the second entry information EDB [5], the second entry information EDB [7], and the second entry of the entry number. Information EDB [10] and second entry information EDB [12] are read out.

  The second read valid signal REB [i] has a value obtained by delaying the first read valid signal REA [i] for the entry i by a time difference Td, here, by three clock cycles. The Td corresponds to two cycles from when the first search table 22A inputs the first read address RAA [i] and the first read valid signal REA [i] until the first entry information EDA [i] is output. A delay, a delay of one cycle from the input of the first entry information EDA [i] by the comparison circuit 3n to the output of the read determination result RJn [i] based on the input, and a second read effective generation Delay from the time the unit 42B inputs the read determination result RJn [i] from each comparison circuit 3n to the output of the second read valid signal REB [i] based on the above (however, in this example, a simple logical sum) Since this is an operation, there is no delay).

  The Td is a fixed value for three clock cycles, but the first entry information EDA after the first search table 22A inputs the first read address RAA [i] and the first read valid signal REA [i]. The delay amount until [i] is output may be larger than two cycles or the delay amount may vary. In addition, a delay from when the comparison circuit 3n inputs the first entry information EDA [i] to when it outputs the read determination result RJn [i] based on the input may be greater than one cycle.

  The second read address RAB [i] is a signal obtained by delaying the first read address [i] by Td = 3 cycles. At the same time as the second read address RAB [i], the second read valid signal REB [i] 2 is input to the search table 22B. The numbers in the boxes representing the second read address RAB [i] in FIG. 4 represent the entry number i (1 to 16), and the entry number i is the same as the first read address RAA [i]. The signal value is i-1.

If Td is not equal to three clock cycles, the second read address RAB [i] is input to the second search table 22B simultaneously with the second read valid signal REB [i], so that the first read address [i ] Is a signal delayed by Td.
Further, if Td varies and the second read address generation unit 41B cannot be delayed in accordance with the variation, the first read address RAA [i] that the first read address generation unit 41A outputs to the second read address generation unit 41B ] Is delayed from the first readout circuit 23A via the comparison circuit 3n, as in the configuration in which the delay time is delayed in accordance with the variation in Td and the configuration in another embodiment shown in FIG. A configuration of passing to the second readout circuit 23B is also possible.

  In FIG. 4, the second read valid signal REB [i] and the second read address RAB [i], which are signals for reading the second entry information EDB [i], are simultaneously input to the second table memory. In this example, a memory that is not simultaneously input, for example, a memory that needs to input the second read enable signal REB [i] a predetermined cycle before the second read address RAB [i]. It can also be used as a second table memory. In this case, the second read circuit 23B generates the second read valid signal REB [i] and the second read address RAB [i] according to the signal input method defined by the memory.

  Further, the second entry information EDB [i] is not read by the second read enable signal REB [i] and the second read address RAB [i], but in the case of a memory that is accessed using a command, the second entry information EDB [i] The read circuit 23B generates a second read command [i] for reading the data stored at the position of the second read address RAB [i] when the second read valid signal REB [i] indicates valid. It will be.

In FIG. 4, the second entry information EDB [i] is read from the second search table 22B after two cycles from the input of the second read address RAB [i] when the second read valid signal REB [i] is valid. ing.
This two-cycle delay is caused by a one-clock delay caused by latching a signal such as an address input to the second table memory, and a latch before outputting data stored in a cell in the memory. It is a value that combines the delay of one clock that occurs. In the case of a device in which the type of the second table memory, the memory, and the second reading circuit 23B and the like are configured as separate components, there is a possibility that the delay is larger than the above.

  The numbers in each box representing the second entry information EDB [i] in FIG. 4 represent the entry numbers i (1 to 16), and the entry 5 in which the second read valid signal REB [i] indicates validity. , 7, 10, 12 are output.

[Effect of the first embodiment]
Thus, in the present embodiment, when the comparison circuit 3n compares the first entry information EDA [i] and the second entry information EDB [i] of the entry i with the frame information FDn, first, the first entry information By comparing EDA [i] with the frame information FDn, it is determined whether the first entry information EDA [i] matches the frame information FDn, and the second entry information EDB [i] is read. The read determination result RJn indicating necessity is output to the second read circuit 23B, and when the first conformity determination result CJAn [i] obtained by the determination indicates conformity, the second entry information EDB [i ] Is compared with the frame information FDn to determine whether the second entry information EDB [i] matches the frame information FDn. When the obtained second conformity determination result CJB [i] indicates conformity, the entry number of the entry i, a part of the first entry information EDA [i], or the second entry information EDB [i] Is a search result SRn corresponding to the matching entry.

  Further, when the second read circuit 23B indicates that the read determination result RJn output from the comparison circuit 3n is read, the second entry information EDB [i] is read from the second search table 22B. When the read determination result RJn indicates no read, the second entry information EDB [i] is not read from the second search table 22B.

  Thereby, as a result of the comparison between the first entry information EDA [i] and the frame information FDn, it is determined whether or not the second entry information EDB [i], which is the remaining entry information, needs to be read. Only when necessary, the second entry information EDB is read out. For this reason, there are two cases: an entry that reads only a part of entry information (first entry information EDA) and an entry that reads all entry information (first entry information EDA + second entry information EDB).

  Therefore, in the conventional configuration, all entry information is read for all entries, whereas in this embodiment, the number of bits of entry information to be read can be reduced. For this reason, as a search condition used for search processing for determining frame processing according to the input frame FIN, for example, when the destination IP address and the destination TCP port number are combined in addition to the VLAN ID, the number of bits of the entry information is Even if it increases, it is possible to suppress an increase in the number of bits of entry information to be read, and as a result, it is possible to suppress an increase in power consumption required for frame search processing.

[Operation Example of First Embodiment]
Next, an operation example of the frame search processing apparatus 10 according to the present embodiment will be described.
Here, as an example, the frame information FD input from the frame information extraction unit 11 includes the source IP address and the destination IP address stored in the IP header of the input frame FIN input by the frame search processing device 10. It will be taken up and explained as.

The frame information FD does not necessarily include the source IP address and the destination IP address. Other header information such as MAC address, VLAN ID, VLAN priority, frame type, IP upper layer protocol number, frame length or packet length, TCP or UDP port number, ToS (Type of Service in IP header) ) A part of information such as a value may be included. Further, the frame information FD may include information other than the header information such as the port number to which the frame is input and another search result for the frame.
An example of the first entry information EDA and the second entry information EDB when searching for the frame information FD will be described below.

[Case 1]
First entry information EDA = entry valid flag / frame type; flag indicating IPv4 or IPv6 second entry information EDB = source IP address and destination IP address for conforming to entry

  Normally, not all entries in the search table are used, but the number of entries used increases or decreases depending on the communication state of the apparatus. In such a case, each entry number of the entry in use and the entry that is not used becomes irregular. Therefore, instead of judging whether the entry is in use or not in use, the entry condition is added to the search condition, and the entry is matched. This determination is made only when the entry is valid (= entry in use).

  In some cases, the device is required to support both IPv4 and IPv6. In such a case, each entry of the search table describes a search condition for either IPv4 or IPv6. Become. Since the frame (IP packet) to be searched is either IPv4 or IPv6, the IPv4 entry does not match in the IPv6 frame. Conversely, in the IPv4 frame, the IPv6 entry Will not fit.

  In the present embodiment, the first entry information EDA includes the entry validity flag indicating whether or not the entry is valid, so that the second entry information EDB is read only when the entry is valid. That is, in the second search table read determination, when the entry valid flag indicates valid, it is determined that the second search table is read. Thereby, the second entry information EDB of the invalid entry (= unused entry) is not read from the second search table 22B. Therefore, the more invalid entries, the smaller the number of bits of the read entry information. Can do.

  Furthermore, the first entry information EDA includes a frame type indicating whether the entry is for an IPv4 frame or an entry for an IPv6 frame. Only when the frame types of the target frames match, it is determined that the second search table has been read, and the second entry information EDB is read. Accordingly, when searching for an IPv4 frame, the second entry information EDB for IPv6 is not read from the search table. Similarly, when searching for an IPv6 frame, the IPv4 second entry information EDB is not read from the search table.

  For example, when 1/2 entry is an unused entry, 1/4 is an entry for IPv4, the remaining 1/4 is an entry for IPv6, and the ratio of the IPv4 frame to the IPv6 frame is the same. In the conventional configuration, the number of read bits per entry is 260 bits (= entry valid flag 1 bit + frame type 1 bit + source IP address 128 bits + destination IP address 128 bits). , 82 bits (= entry valid flag 1 bit + frame type 1 bit + (source IP address 32 bits + destination IP address 32 bits) / 4 + (source IP address 128 bits + destination IP address 128 bits) / 4) Can be reduced.

[Case 2]
First entry information EDA = entry application priority second entry information EDB = source IP address, destination IP address and mask length of each address for conforming to entry

When there is a plurality of entries for which the search conditions are determined to be appropriate, specifying an application priority for each entry, a search process is performed in which the entry with the highest application priority is adopted among those entries. There is a device.
For example, a frame in which a destination IP address is in a certain range (IPx to IPy) is discarded, but exceptionally, a frame having a specific destination IP address (IPz) in the range is desired to pass. is there. In this case, the above can be achieved by making the entry application priority for the latter higher than the entry application priority for the former.

  In order to obtain the same search result SR with an apparatus for which the application priority cannot be specified, an entry for discarding a frame whose destination IP address is in the range of IPx to (IPz-1), and the destination IP address from (IPz + 1) At least three entries are required among an entry for discarding a frame in the IPy range and an entry for allowing a frame having a destination IP address of IPz to pass.

  In the method of performing a search with respect to a search condition to which application priority is added, the application priority and entry number of the entry determined to be compatible first are temporarily stored in the comparison circuit 3n, and then the entry determined to be compatible is found. In this case, the application priority of the entry is compared with the temporarily stored application priority. If the former is higher, the temporarily stored entry number and the application priority are compared with the former entry number. The application priority is updated, and this is repeated until conformity determination is completed for all entries or an entry having an upper limit application priority is found.

  Here, the first entry information EDA is set as the application priority of the entry, and when the entry determined to be suitable from the start of search is not found, or the first entry information EDA exceeds the temporarily stored application priority. The second entry information EDB is read only when the application priority shown is higher. That is, in the second search table read determination, the application priority indicated by the first entry information EDA is higher than the application priority that is temporarily stored as to whether an entry determined to be suitable from the start of search is found as described above. When it is higher, it is determined that the second search table is read. As a result, the second entry information EDB is not read from the second search table 22B for entries whose application priority is lower than the already found entry.

  For example, when the application priority of each entry is random and the number of entries that are determined to be suitable is one, an entry that is determined to be compatible is found on average when 1/2 of the number of entries is searched, Since 1/2 of the retrieved entries are entries having higher application priority than the entry determined to be compatible, the second entry information EDB is not read for 25% of all entries.

Therefore, in the conventional configuration, the number of read bits per entry is 82 bits (= application priority 8 bits + source IP address 32 bits + destination IP address 32 bits + source IP address mask length 5 bits + destination The mask length of the IP address is 5 bits).
On the other hand, according to this example, the average number of read bits from the search table per entry when searching for one frame is 63.5 bits (= application priority 8 bits + (source IP Address 32 bits + destination IP address 32 bits + source IP address mask length 5 bits + destination IP address mask length 5 bits) * 0.75). That is, the average value of the number of bits read from the search table when searching for one frame is 63.5 bits * Ne (Ne is the number of entries).

[Case 3]
First entry information EDA = Hash value calculated from second entry information EDB Second entry information EDB = Source IP address and destination IP address for conforming to entry

  There is a search method using a hash method, but in a general implementation of this search method, a predetermined hash operation is performed on the entry information to obtain a hash value of the entry information, which is determined according to the hash value. The entry information is stored in the search table entry. At the time of inputting the frame information FD, the hash value of the frame information FD obtained by performing the hash operation on the frame information FD is used to limit the search table entries that can be matched, and the limited entry Only for, conformity determination is performed using the frame information FD and entry information.

  However, in such a search method, the entries that can store the hash value of the entry information are limited. Therefore, if the hash values collide (they have different entry information with the same hash value), there is a possibility that there are no entries that can be stored. There was a problem.

  According to the present embodiment, the second entry information EDB is used as a transmission source IP address and a destination IP address for matching the entry, and the first entry information EDA is subjected to a predetermined hash operation on the second entry information EDB. The hash value of the obtained second entry information EDB is used. When the frame information FD is input, the frame information FD is subjected to the predetermined hash calculation to obtain a hash value of the frame information FD, and then the search is started.

  The comparison circuit 3n determines whether or not the hash value of the second entry information EDB, which is the first entry information EDA read from the first search table 22A, matches the hash value of the frame information FD. . Further, the second entry information EDB is read only when the result of the match determination is match (hash value matches). That is, in the second search table read determination, if the hash value of the frame information FD and the hash value of the second entry information EDB match, it is determined that the second search table is read. Thereby, generally, the reading from the search table can be limited based on the hash value, as in the implementation of the hash method. Furthermore, in general, the problem of implementing the hash method is solved, and the entries that can be stored are not limited by the hash value of the entry information.

  For example, when the number of entries is 256 and the number of bits of the hash value is 8, the probability that the hash value (random) of each entry matches the hash value (random) of the frame information FD is 1/2 ^ 8. Since the occurrence of each entry is an independent event, reading of the second search table 22B occurs once on average. Therefore, the number of read bits per entry is 8.25 bits (= hash value 8 bits + (source IP address 32 bits + destination IP address 32 bits) * 1/256). This can be reduced from 64 bits, which is the number of read bits per entry when the destination IP address is read.

  Of the bit strings representing the source IP address and destination IP address that are entry information, a predetermined partial bit string, for example, the lower 8 bits of the source IP address, is often different between entries. The partial bit string is the first entry information EDA, and the remaining bit string, in the example, the upper 24 bits of the source IP address and the destination IP address are the second entry information EDB.

  As a result, as in the case where a hash value is used as the first entry information EDA, an effect that reading from the search table can be limited is obtained. Furthermore, since this method does not require a hash value calculation and does not require a memory for storing the hash value, in addition to reducing the number of read bits per entry, the hash value calculation and hash The circuit scale of the memory for storing values can be reduced.

  In the above example, the number of read bits per entry is 8.22 bits (= the lower 8 bits of the source IP address + (the upper 24 bits of the source IP address + the 32 bits of the destination IP address) * 1/256 The total memory amount of the first search table 22A and the memory amount of the second search table 22B is 16384 bits (= (the lower 8 bits of the source IP address + the upper 24 bits of the source IP address + the destination IP) Address is 32 bits) * 256), but in the case of using a hash value, in addition to the above, the memory needs to store the hash value, that is, 2048 bits (hash value 8 bits * 256). Therefore, there is an effect that the memory amount can be reduced by about 11%.

  In the above example, the source IP address and the destination IP address are taken up as an example of the second entry information EDB, but other applications are possible. The second entry information EDB may be a combination of an IP address with a MAC address or VLAN ID, or a TCP / UDP port number. In addition, the hash value is not obtained by the hash operation on the entire bit string of the second entry information EDB, but may be the result of the hash operation on the partial bit string to be matched among all the bit strings representing the second entry information EDB. Good.

  If all bits can be masked, a valid flag is added to the first entry information EDA, and if the hash value of the first entry information EDA indicates invalidity, the second entry information is always included. The EDB is read from the second search table 22B. As a result, a search condition in which reading from the search table cannot be limited by the hash value (a search condition in which at least a part of the bit values of the bit string of the second entry information EDB to be hashed is masked) is specified. For the entry, the read limitation based on the hash value can be released.

Therefore, the number of read bits per entry can be reduced with respect to the former entry, even for a search table in which entries that can be read from the search table are limited by hash values and entries that cannot be limited.
For example, the search processing includes a part of entries that are determined to be compatible based only on the destination IP address in addition to the entries that are determined to be compatible based on both the destination IP address and the source IP address.

  In this case, the hash value is adopted as the first entry information EDA with the hash calculation target as a bit string combining the destination IP address and the source IP address. Furthermore, the value of the validity flag indicating invalidity is specified only for the entry that is determined to be compatible based only on the destination IP address, that is, the entry whose source IP address is masked. The hash value included in the first entry information EDA at this time may be an arbitrary value. Further, a destination IP address and a source IP address for determining conformity are designated in the second entry information EDB. That is, only the destination IP address is specified in the entry for determining the conformity based only on the destination IP address.

As a result, for entries for which conformity is determined based on both the destination IP address and the source IP address, the hash value obtained from the destination IP address and source IP address of the frame information FD and the first entry information EDA Only when the hash values match, the second entry information EDB is read from the search table, and the second entry information EDB is determined for the entry whose conformity is determined based only on the destination IP address, regardless of whether the hash values match or not. Entry information EDB is read from the search table.
Therefore, even when an entry having a search condition capable of calculating a hash value and an entry incapable of the above are mixed, the number of read bits per entry can be reduced with respect to the former entry.

[Case 4]
First entry information EDA = destination IP address for conforming to the entry, its mask length, read flag of the second entry information EDB,
Second entry information EDB = source IP address and mask length for conforming to entry

There is a device that performs a search that includes both an entry that is determined to be suitable based on a condition for only the destination IP address and an entry that is determined to be compatible based on a condition for both the destination IP address and the source IP address. For example, the route table of the router device is normally occupied by entries that are determined to be compatible only with the destination IP address as a condition. However, when performing source routing, both the destination IP address and the source IP address are specified as conditions. As a result, an entry for determining conformity is added.
In such a case, in an apparatus that reads both the destination IP address and the source IP address from the search table for all entries, if there are a large number of entries conditioned only on the destination IP address, the source IP address is wasted Reading becomes a problem.

  According to the present embodiment, the first entry information EDA is not a match determination target among the destination IP address for matching the entry and its mask length, that is, the bit string representing the IP address; The number of bits from the lower bits and a read flag of the second entry information EDB, that is, a flag indicating whether or not to read the second entry information EDB, and the source IP for adapting the second entry information EDB to the entry Address and its mask length.

That is, in the second search table read determination, only when the condition for the destination IP address represented by the frame information FD and the first entry information EDA is satisfied, and the read flag of the second entry information EDB indicates that there is a read. Then, the second entry information EDB is read.
As a result, only the entry for which both the destination IP address and the source IP address need to be read from the search table is read from the second search table 22B, so that the useless source IP address is read. Does not occur.

  For example, if half of all entries are entries that require only the destination IP address and the remaining entries are conditions that also include the source IP address in addition to the destination IP address, The number of read bits per entry is 74 bits (= source IP address 32 bits + destination IP address 32 bits + source IP address mask length 5 bits + destination IP address mask length 5 bits, search for source IP address) Otherwise, the mask length of the source IP address is 32).

  According to this example, 56.5 bits (= destination IP address 32 bits + destination IP address mask length 5 bits + second entry information EDB read flag 1 bit + (source IP address 32 bits + source IP address) Mask length of 5 bits) / 2).

In the above example, the destination IP address and the source IP address are taken up as examples of the first entry information EDA and the second entry information EDB, but application to other than the above is also possible.
For example, in the case of a search table in which an entry having only a VLAN ID as a search condition and an entry having a search source MAC address in addition to the VLAN ID as a search condition are mixed, the VLAN ID is designated as the first entry information EDA and the second entry information The source MAC address is designated as EDB.

  In this way, entry information representing search conditions common to all entries (VLAN ID in the above example) is the first entry information EDA, and entry information representing search conditions added to some entries (sent in the above example) By setting the original MAC address) as the second entry information EDB, the second entry information EDB is not read from the search table for entries that do not require the second entry information EDB for the search process, so the number of read bits per entry Can be reduced.

[Case 5]
1st entry information EDA = IP address and entry information type for conforming to entry; flag for identifying destination / source 2nd entry information EDB = IP address for conforming to entry (specified in first entry information EDA IP address of the one that did not exist; if the destination, the source, if the source, the destination

  If a plurality of entries for specifying frames from a large number of terminals to a small number of servers are included in the search table, the destination IP address representing the IP address of the server is the same between the entries. The source IP address representing the IP address differs between entries. On the other hand, in the case of an entry specifying a frame in the reverse direction, the destination IP address is different between entries, while the source IP address is the same.

  Thus, in the search table that stores entry information including conditions for a plurality of header information, it is easy to limit the entry, that is, includes both header information that is different from other entries and header information that is not, and Depending on the entry, header information that makes it easy to limit the entry changes. In the above example, the entry IP address is different from the entry IP address or the destination IP address.

  According to the present embodiment, the first entry information EDA is designated with a value related to header information that is easy to limit the entry (different from other entries), thereby reducing the chance of reading the second entry information EDB. be able to. Since the header information differs depending on the entry, an entry information type indicating the type of header information specified in the first entry information EDA is added.

  As an example, there are 4 servers and 32 terminals, 128 (= 4 * 32) entries that specify frames from each server to each terminal, and 128 that specify frames from each terminal to each server. When a total of 256 entries (= 32 * 4) are stored in the search table, the number of read bits per entry is 64 bits (= source IP address 32 bits + destination IP) in the conventional configuration. Address 32 bits).

  According to this example, the first entry information EDA read for each entry, that is, the terminal-side IP address 32 bits + entry information type 1 bit matches the probability of matching the first entry information EDA, that is, the terminal-side IP address. 33.5 bits (= first entry information EDA 33 bits + second) added with the second entry information EDB (server side IP address 32 bits) read at 4 (the number of servers) / 256 entries. Entry information EDB 32 bits * 4/256).

  In the above description, a value related to header information that is easy to limit the entry (different from other entries) is specified as the first entry information EDA, but in order to reduce the number of bits of the first entry information EDA, It is also possible to use a hash value obtained by performing a predetermined hash operation on a value related to header information.

[Second Embodiment]
Next, with reference to FIG. 5, a frame search processing device 10 according to a second exemplary embodiment of the present invention will be described. FIG. 5 is a block diagram illustrating a main part of the search processing unit according to the second embodiment.
In the first embodiment, as shown in FIG. 3, two table memories M1 and M2 of the first table memory for the first search table 22A and the second table memory for the second search table 22B are used. The case where it does is demonstrated as an example. In the present embodiment, a case where both the first search table 22A and the second search table 22B are realized in one common table memory M0 will be described.

  In the present embodiment, the first reading circuit 23A changes the first entry information EDA [i [i] stored in the first search table 22A while changing the entry i (i = 1 to Ne) with the passage of time based on the clock. ] Are read one after another and distributed to each comparison circuit 3n (n = 1 to N). Specifically, the first entry information EDA [a + 1] is stored in each address a (a = 0 to Ne−1) of the common table memory. Further, the address a to be read is changed in order from 0 to Ne-1 as time passes. In the above method, when the address a reaches the last entry Ne-1, it is assumed to return to 0.

  Here, if the number of entries to be read is Cd within the time difference Td from the reading of the first entry information EDA [i] to the reading of the second entry information EDB [i], each address a of the common table memory Stores the first entry information EDA [a + 1] and the second entry information EDB [a + 1−Cd]. When the value of a + 1−Cd is negative, the second entry information EDB [Ne + a + 1−Cd] is stored.

Further, the first entry information EDA [a + 1] stored in the address a is read by the first reading circuit 23A, and at the same time, the second entry information EDB [a + 1−Cd] is read from the common table memory.
That is, the second entry information EDB [a + 1−Cd] read from the second search table 22B with the same entry as the first entry information EDA [a + 1−Cd] read from the first search table 22A before the time Td. Are read together with the first entry information EDA [a + 1] of the entry (a + 1).

  However, as the common table memory, a memory capable of inputting a read control signal that is a signal indicating whether or not the second entry information EDB [i] (i = 1 to Ne) is read is used. Further, as the read control signal, the result of the logical operation on the signals indicating the read determination results RJn [i] from all the comparison circuits 3n (n = 1 to N), that is, at least one read determination result RJ is the first. When the two-search table reading is indicated, the result of the operation in which the reading control signal has a value indicating the reading is used.

  That is, in order to read the first entry information EDA [a + 1] of the entry (a + 1) and the second entry information EDB [a + 1−Cd] of the entry (a + 1−Cd) from the common table memory, the read address a In addition to this, when the second search table read is indicated in the read determination result RJn [a + 1-Cd] for the entry (a + 1-Cd), the second entry of the entry (a + 1-Cd) A read control signal for reading the information EDB [a + 1−Cd] is input to the common table memory.

  The main difference between the configuration example of FIG. 5 and the configuration example of FIG. 3 described above is that the first search table 22A and the second search table 22B are accommodated in a common table memory M0 for one search table. It is. As a result, the second read address RAB [i] and the second read address generation unit 41B for generating the signal described in FIG. 3 are unnecessary and deleted.

  In the configuration example of FIG. 3, the first read address RAA [i] is delayed to generate the second read address RAB [i]. However, in the configuration example of FIG. 5, the second read address RAB [i] is generated. As [i] becomes unnecessary, the first read address RAA [i], which is a signal from the first read circuit 23A to the second read circuit 23B, is deleted.

  The word indicated by the read address [i] of the common table memory includes the first entry information EDA [i] with the entry number i and the entry number I ′ = i−Cd (I ′ = Ne when i ≦ Cd). -Cd + i) second entry information EDB [I '] is stored. Cd is the number of entries read from the common table memory within time Td. Cd is a fixed value, Td is a time corresponding to three clock cycles, and Cd = 3 when one entry is read from the common table memory every cycle.

The first entry information EDA [i] is input after the first search table 22A inputs the first read address RAA [i] and the first read enable signal REA [i] shown in the description of FIG. When the delay amount required for reading the search table varies until the output, the first delay time is absorbed in each comparison circuit 3n or the second read circuit 23B by absorbing the change in the delay amount required for reading the search table. The time difference from the time when the read signal RA [i] is input to the common table memory to the time when the second read signal RB is input to the common table memory needs to be a fixed value.
In the present embodiment, configurations other than those described above are the same as those in the first embodiment, and a description thereof is omitted here.

[Operation of Second Embodiment]
Next, the operation of the search processing unit 12 according to the present embodiment will be described with reference to FIG. FIG. 6 is a time chart showing the operation of the search processing unit according to the second embodiment, and the passage of time for each signal in the search processing unit 12 taking the case where the number N of comparison circuits 3n is 2 as an example. Changes with (from left to right) are shown.

  6 does not have the first read address RAA [i] and the second read address RAB [i] in FIG. 4, and the first read address RAA [i] in FIG. 4 is replaced with the read address RAD [i]. .

In FIG. 6, when the first read valid signal REA [i] is valid, the first entry information EDA [i] is obtained from the first search table 22A after two cycles from the input of the first read address RAA [i] = i-1. Read out. When the second read valid signal REB [i] is valid, the second entry information EDB [i] is output two cycles after that point.
Since the first entry information EDA [i] and the second entry information EDB [i-Cd] (Cd = 3) are stored in the word of the read address RAD [i] = i−1, the read address a Second entry information EDB [a-2] is read from the word.

The two-cycle delay is caused by a one-clock delay caused by latching a signal such as an address input to the common table memory and a latch before outputting data stored in a cell in the memory. This value is a sum of delays of one clock.
In this embodiment, operations other than those described above are the same as those in the first embodiment, and a description thereof is omitted here.

[Effect of the second embodiment]
Thus, the present embodiment includes the first search table 22A and the second search table 22B, and the first entry information corresponding to the entry i and the second entry information of the second search table 22B are If EDA [i] and EDB [i] are respectively set, and the number of entries read during the period from reading EDA [i] to reading EDB [i] is Cd, EDA [i ] And EDB [i-Cd] are stored in the common table memory M0, and the first read circuit 23A cyclically EDA [i] and EDB [] from each entry in the common table memory M0. i-Cd] and output to the comparison circuit 3n, the common read signal RA is output to the common table memory M0, and the second read When the read determination result RJ output from the comparison circuit 3n indicates that there is a read, the circuit 23B sends the second read signal RB indicating the read valid from the second search table 22B to the common table memory M0. In response to the common read signal RA from the first read circuit 23A, the common table memory M0 reads and outputs EDA [i] from the address corresponding to the common read signal RA, and outputs the first data. The EDB [i-Cd] is read from the address and output only when the two read signal RB indicates that the reading from the second search table 22B is valid.

  Thereby, each of the first search table 22A and the second search table 22B is compared with the case where the first table memory M1 and the second table memory M2 are used, and the address decoder circuit provided in each of these table memories. That is, when an address is input, instead of a circuit that generates a signal for selecting a memory cell corresponding to the address, the address decoder circuit of one common table memory M0 can be used. Can be reduced.

[Third Embodiment]
Next, a frame search processing device 10 according to the third exemplary embodiment of the present invention will be described with reference to FIG. FIG. 7 is a block diagram illustrating a configuration of a search processing unit according to the third embodiment.
In the first embodiment, the case where the second read address RAB is generated by the second read circuit 23B based on the first read address RAA from the first read circuit 23A has been described as an example. In the present embodiment, based on the second entry number on the second search table 22B indicating the second entry information EDB corresponding to the first entry information EDA stored in the first entry information EDA, A case where the second read circuit 23B generates the second read address RAB will be described.

  In the present embodiment, the search processing unit 12 includes, as main circuit units, a frame information distribution circuit 21, a first search table 22A, a second search table 22B, a first readout circuit 23A, a second readout circuit 23B, N comparison circuits 3n (n = 1 to N; N is a natural number of 2 or more) and a search result merging circuit 24 are provided.

The first search table 22A has Ne (N is a natural number of 1 or more) entries i (i = 1 to Ne), and the first entry information EDA [i] is stored in each entry i.
The second search table 22B has Ne ′ (Ne ′ is a natural number of 1 or more) entries j (j = 1 to Ne ′), and stores second entry information EDB [j] in each entry j.

The first search table 22A receives the first read signal RA from the first read circuit 23A, and reads the stored first entry information EDA [i] from the address indicated by the signal at the timing indicated by the signal.
Similarly, the second search table 22B receives the second read signal RB from the second read circuit 23B, and stores the second entry information EDB [i] stored at the timing indicated by the signal from the address indicated by the signal. Is read.

  In the first embodiment, the second entry stored in the entry i of the second search table 22B having the same entry number i as the first entry information EDA [i] stored in the entry i of the first search table 22A. Although the set with the information EDB [i] corresponds to the entry information in the prior art, in the present embodiment, the set is included in the first entry information EDA [i] stored in the first search table 22A. The entry number of the second search table 22B to be included is included.

That is, the first search condition expressed by the first entry information EDA [i] matches the frame information FD, and the first entry information EDA [i] is the entry number of the second search table 22B. When the second entry number ENB [i] is included, and the second search condition expressed by the second entry information EDB [second entry number ENB [i]] matches the frame information FD, the frame conforms to the frame. An entry having a search condition to be found is found.
Therefore, the entry information of entry i in the conventional search table is the first entry information EDA [i] (excluding the second entry number ENB [i]) in the first search table 22A and the second entry in the second search table 22B. This is divided into 2-entry information EDB [second entry number ENB [i]].

  The comparison circuit 3n that receives the frame information FDn (n = 1 to N) from the frame information distribution circuit 21 starts the search when the frame information FDn is input, and the frame information FDn and the first readout circuit 23A. Is based on the first entry information EDA [i] of the entry i (i = 1 to Ne) read from the first search table 22A, and the search condition that the frame information FDn represents by the first entry information EDA [i] The first conformity determination as to whether or not conforms to is performed to obtain a first conformity determination result CJAn [i]. It is assumed that the second entry number ENB [i] is specified in the first entry information EDA [i].

  Further, the comparison circuit 3n performs a second search as to whether or not to read the second entry information EDB [second entry number ENB [i]] of the second entry number ENB [i] from the second search table 22B. The table read determination is performed based on the first suitability determination result CJA, and the read determination result RJn [i] is output to the second read circuit 23B.

  In the present embodiment, when the first conformity determination result CJAn [i] indicates conformity, the second entry information EDB [second entry number ENB [i]] is read from the second retrieval table 22B (second retrieval If the first conformity determination result CJAn [i] indicates nonconformity, the second entry information EDB [second entry number ENB [i]] is not read from the second search table 22B. It is determined that the second search table is not read. That is, in this example, it is not necessary to perform the second search table read determination separately from the first suitability determination, and the read determination result RJn [i] can be obtained using the first suitability determination result CJAn [i].

  Here, when the comparison circuit 3n outputs the read determination result RJn [i] indicating that the second search table is read to the second read circuit 23B based on the frame information FDn and the first entry information EDA [i]. The second reading circuit 23B reads the second entry information EDB [second entry number ENB [i]] from the second search table 22B and inputs it to the comparison circuit 3n. At this time, the comparison circuit 3n determines that the frame information FDn is based on the frame information FD and the second entry information EDB [second entry number ENB [i]]. The second conformity determination is performed as to whether or not it conforms to the entry number ENB [i]] of 2 to obtain a second conformity determination result CJB [i].

  The comparison circuit 3n determines whether the search condition of the entry i matches the frame information FDn based on the first match determination result CJAn [i] and the second match determination result CJB [i]. Perform integrated conformity judgment. Further, when the entry determined to be compatible by the integrated compatibility determination is found, or when the determination of the frame information FDn is completed for all the entries, the comparison circuit 3n finishes the search and obtains the search result SRn. Output.

  In the example in which the entry entry priority is included in the first entry information EDA or the second entry information EDB, and the entry having the highest entry priority is found among the entries determined to be compatible by the integrated suitability determination, The search is not terminated when one entry that is determined to be conforming by the conformity determination is found, but only when the integrated conformance determination is completed for all entries or when an entry having an upper limit application priority is found. finish.

  The comparison circuit 3n obtains the result obtained by the integrated suitability determination (for example, information indicating the result included in the entry number i matched in the determination or the second entry information EDB [i] of the entry; passing / discarding). Information or a port number indicating a transmission destination) is output to the search result merging circuit 24 as a search result SRn.

The comparison circuit 3n, for the entry i, the first match determination result CJAn [i] obtained after the first entry information EDA [i] is read from the first search table 22A and the subsequent second entry information EDB. The integrated suitability determination is performed based on the second suitability determination result CJB [i] obtained after [i] is read from the second search table 22B.
Before obtaining the second conformity determination result CJB [i], when the first conformity determination is performed for the next entry (i + 1) to obtain the first conformity determination result CJAn [i + 1], the first conformity determination for the entry i The first match determination result CJAn [i + 1] for the entry (i + 1) together with the result CJAn [i] is temporarily held until the integrated match determination is performed.

That is, the first conformity determination result CJAn [i] needs to be retained until the second conformity determination result CJB [i] is obtained and the integrated conformity determination is performed, but the first entry after the next entry obtained during the retention period is required. 1 Conformity determination result CJA is also held.
As a result, it is not necessary to set the entry update interval longer than the time from when the first conformity determination result CJAn [i] is obtained until the second conformity determination result CJB [i] is obtained, and the search processing speed can be improved.

  As an example of the determination end specifying method for knowing the time point when the determination with the frame information for all the above entries is completed, the time elapsed since the comparison circuit 3n input the frame information FDn (n = 1 to N) is compared with the comparison result. There is a method in which the circuit 3n measures and uses a timing at which the elapsed time reaches a predetermined time Ts. This determination end specifying method is a method using the fact that the processing time of each entry is a fixed value and the number of entries is also a fixed value, so that the time taken to search all entries is also a fixed value. As another method, the number of times of integrated conformity determination from the time when the frame information FDn (n = 1 to N) is input by the comparison circuit 3n is counted, and the timing at which the number reaches N (the total number of entries) is used. You can also.

  The first reading circuit 23A sequentially reads the first entry information EDA [i] stored in the first search table 22A while changing the entry i (i = 1 to Ne) with the passage of time. The first entry information EDA [i] excluding the entry number ENB [i] is distributed to each comparison circuit 3n (n = 1 to N). The second entry number ENB [i] is output to the second readout circuit 23B.

  As an example of a method of reading the first entry information EDA, the first search table 22A is constituted by a first table memory, and the first entry information EDA is assigned to each address a1 (a1 = 0 to Ne-1) of the first table memory. There is a method of storing [a1 + 1] and sequentially changing the read address a1 from 0 to Ne-1 as time passes. In this method, it is assumed that the address a1 returns to 0 when it reaches the last entry Ne-1. Here, the first readout circuit 23A inputs the search state SSn indicating whether or not the search process output from each comparison circuit 3n (n = 1 to N) is being performed, and all the comparison circuits 3n perform the search process. By not performing the reading during a period during which no reading is performed, it is possible to reduce power consumption during a period during which reading of the first search table 22A is unnecessary.

  Each time the second reading circuit 23B inputs the second entry number ENB [i] (i = 1 to Ne) from the first reading circuit 23A, the second entry information EDB [second] stored in the second search table 22B is stored. 2 entry number ENB [i]] is read out and distributed to each comparison circuit 3n (n = 1 to N). However, the second entry information EDB [[second entry number ENB [i]] is read after a predetermined time difference Td from the reading of the first entry information EDA [i].

  The second entry information EDB [second entry number ENB [i]] is read from the read determination result RJn [i] indicating that the second search table is read from at least one comparison circuit 3n. Only when entered. The comparison circuit 3n that has not performed the search process needs to distinguish whether or not the comparison circuit 3n is performing the search process by outputting the read determination result RJn [i] indicating that the second search table is not read. Rather, it is possible to determine whether or not the second entry information EDB [second entry number ENB [i]] has been read based on each read determination result RJn [i] (n = 1 to N).

  The time difference Td is as follows. (A) The first read circuit 23A starts reading the first entry information EDA [i] (i = 1 to Ne), and then the comparison circuit 3n (n = 1 to N) Time until 1 entry information EDA [i] is input (= time required to read first search table 22A + time required to distribute first entry information EDA to each comparison circuit 3n), (b) comparison Time from when the circuit 3n (n = 1 to N) inputs the first entry information EDA [i] to when the read determination result RJn [i] is output to the second read circuit 23B (= second search table read determination) (C) The second entry information EDB [second entry number] after the second readout circuit 23B inputs the readout determination result RJn [i] from all the comparison circuits 3n (n = 1 to N). Read ENB [i]] And the time until the start of reading of the second entry information EDB [second entry number ENB [i]] (= time required to determine whether or not the second search table 22B is read) Become.

  The second read circuit 23B determines the read from each comparison circuit 3n (n = 1 to N) after a delay of Td from the time when the first read circuit 23A reads the first entry information EDA [i] of the entry i. When the result RJn [i] includes that indicating that the second search table is read, the second entry information EDB [second entry number ENB [i]] of the entry i is read.

  As an example of this reading method, the second search table 22B is constituted by a second table memory, and the second entry information EDB [a2 + 1] is stored in each address a2 (a2 = 0 to Ne′−1) of the second table memory. The address a2 that is stored and read out is the second entry number ENB [i]. Further, as a read control signal that indicates whether or not reading from the second table memory is performed, a logical operation (at least one read determination result RJ is a second search table) for a signal indicating the read determination result RJn [i]. The result of an operation in which the read control signal is set to a value indicating read when the read is indicated is used.

  Next, the first readout circuit 23A and the second readout circuit 23B according to the present embodiment will be described with reference to FIG. FIG. 8 is a block diagram illustrating a main part of a search processing unit according to the third embodiment.

As shown in FIG. 8, the first read circuit 23A includes a first read address generation unit 41A, a first read effective generation unit 42A, and a second entry number separation unit 43A.
Among these, the first read address generation unit 41A and the first read effective generation unit 42A are the same as those in FIG. 3 described above, and the first read address RAA [i] and the first read effective signal are synchronized with the clock, respectively. It has a function of generating REA [i], outputting it to the first search table 22A, and reading the first entry information EDA [i].

  Further, the second entry number separation unit 43A receives the first entry information EDA [i] read from the first search table 22A, and the second entry RNB included in the first entry information EDA [i]. The function of separating the number [i] and outputting it to the second reading circuit 23B, and the remaining part of separating the second entry number ENB [i] from the first entry information EDA [i] The information EDA [i] is distributed to each comparison circuit 3n (n = 1 to N). A simple configuration may be used in which the first entry information EDA [i] output from the first search table 22A is distributed to the first readout circuit 23A and each comparison circuit 3n.

The second read circuit 23B includes a second read address generation unit 41B and a second read effective generation unit 42B.
Among these, the second read effective generation unit 42B is the same as in FIG. 3, and receives the read determination result RJn [i] from each comparison circuit 3n (n = 1 to N), and receives one or more read determination results RJn. When [i] indicates the presence of reading, it has a function of outputting a second reading valid signal REB [i] indicating validity.
The second read address generation unit 41B has a function of inputting the second entry number ENB [i], generating and outputting the second read address RAB [i] based on the number.

The second search table 22B stores the second entry information EDB [j] in each entry j. The second search table 22B stores the second entry information EDB [j] from the entry number j. The actual address of the second table memory M2 can be generated by a simple calculation.
The example of the calculation is the address of the second table memory = j−1. In the example, the second entry information EDB [j] of the entry number j is the word at the address of the second table memory = j−1. Is remembered. A method of generating an address from the entry number by another calculation method may be used. In the above example, when entry number = second entry number ENB [i], second read address RAB [i] = second entry number ENB output by second read address generation unit 41B to second search table 22B. [I] -1.

  After the first search table 22A inputs the first read valid signal REA [i] and the first read address RAA [i], the second read valid signal REB [i] is changed to the second search table 22B after the time Td has elapsed. Is input. The Td includes a delay from when the first search table 22A inputs the first read address RAA [i] and the first read valid signal REA [i] until the first entry information EDA [i] is output, Until the second entry number separator 43A inputs the first entry information EDA [i] and distributes the first entry information EDA [i] excluding the second entry number ENB [i] to each comparison circuit 3n. And a delay from the input of the first entry information EDA [i] by the comparison circuit 3n to the output of the read determination result RJn [i] based on the input. This is the sum of the delay from the input of the read determination result RJn [i] from the comparison circuit 3n to the output of the second read enable signal REB [i] based on the above.

  On the other hand, in the case of the second table memory in which the second read address RAB [i] is required to be input simultaneously with the second read valid signal REB [i], the first read valid signal REA [i] and the first read address RAA. The time from when [i] is input to the first search table 22A to when the second read address RAB [i] is input to the second search table 22B needs to be Td. The Td includes a delay from when the first search table 22A inputs the first read address RAA [i] and the first read valid signal REA [i] to when the first entry information EDA [i] is output, The second entry number separation unit 43A inputs the first entry information EDA [i] until the second entry number ENB [i] is extracted and output, and the second read address generation unit 41B This is the sum of the delay from the input of the second entry number ENB [i] to the output of the second read address RAB [i].

[Operation of Third Embodiment]
Next, the operation of the search processing unit 12 according to the present embodiment will be described with reference to FIG. FIG. 9 is a time chart illustrating the operation of the search processing unit according to the third embodiment. For example, when the number N of comparison circuits 3n is 2, the time elapses for each signal in the search processing unit 12. Changes with (from left to right) are shown.

  In FIG. 9, the search state SSn (n = 1, 2), the first read valid signal REA [i], the first read address RAA [i], the first entry information EDA [i], the read determination result RJn [i] Each signal of (n = 1, 2) and each signal of the second read valid signal REB [i] are the same as those in FIG. 4 described above, and a description thereof is omitted here.

  The second entry number ENB [i] is obtained by replacing the second entry number ENB [i] included in the first entry information EDA [i] read from the first search table 22A with the second entry number separation unit 43A. Is output after two cycles from the input of the first read address RAA [i] when the first read valid signal REA [i] to the first search table 22A is valid. In the example of FIG. 9, the first entry information EDA [i] includes the value of the second entry number ENB [i-1].

  The two-cycle delay is caused by a one-clock delay caused by latching a signal such as an address input to the first table memory and a latch before outputting data stored in a cell in the memory. This value is a combination of the generated delay of one clock, and in the case of a device in which the type of the first table memory and the memory and the first reading circuit 23A and the like are constituted by separate parts, there is a possibility that the delay is larger than the above. There is. Further, it is possible to adopt a configuration in which the amount of delay varies depending on the state of the memory (for example, whether or not the memory is accessed from the outside) instead of a fixed delay.

The delay from the input of the first entry information EDA [i] by the second entry number separation unit 43A to the extraction and output of the second entry number ENB [i] is equal to 0 clock cycles in this example. It is said. This is a simple process of extracting a predetermined bit string of the first entry information EDA [i] as the second entry number ENB [i], and can be regarded as no delay.
9 represents the second entry number ENBi (1 to 8; the number of entries in the second search table 22B = 8) which is a signal value, and the symbol “−” in the box represents the signal in FIG. Means that there is no second entry information EDB, that is, the entry can be determined only by the first entry information EDA.

  Further, the first search table 22A is such that the values of the second entry numbers ENB [4] and [9] included in the first entry information EDA [4] and [9] in FIG. The values of the second entry numbers ENB included in the first entry information EDA read from the different entries can be the same, and the entries of the first search table 22A are different. Even in this case, the same entry in the second search table 22B can be referred to. In other words, when there are a plurality of entries in which a part of the search conditions match, the search conditions can be reduced by storing the entry information in the second search table 22B.

  Thus, the number of entries in the second search table 22B can be made smaller than the number of entries in the first search table 22A. In this example, the number of entries in the second search table 22B = 8 with respect to the number of entries = 16 in the first search table 22A. Therefore, the memory amount of the second table memory for the second search table 22B can be reduced.

  The second read address RAB [i] is an address of the second table memory corresponding to the second entry number ENB [i], and the second read valid signal REB [i] is input to the second search table 22B. At the same time, it is output to the second search table 22B. In order to input the second read address RAB [i] to the second search table 22B simultaneously with the second read valid signal REB [i], the second read address generation unit 41B uses the second entry number ENB [i]. The delay from the input to the output of the second read address RAB [i] is one clock cycle.

  In other words, the first read address RAA [i] and the first read valid signal REA [i] are input by the first search table 22A until the first entry information EDA [i] is output, the second cycle. 2 entry number separation unit 43A inputs the first entry information EDA [i] until the second entry number ENB [i] is extracted and output, second read address generation unit 41B The total of one cycle from the input of the second entry number ENB [i] to the output of the second read address RAB [i] is 3 cycles of the Td value in this example.

  In FIG. 9, the second read valid signal REB [i] and the second read address RAB [i], which are signals for reading the second entry information EDB [i], are simultaneously input to the second table memory. An example is shown. However, a memory that is not simultaneously input, for example, a memory in which the second read enable signal REB [i] needs to be input a predetermined cycle before the second read address RAB [i] is used as the second table memory. In this case, the second read circuit 23B generates the second read valid signal REB [i] and the second read address RAB [i] according to the signal input method defined by the memory. .

In the case of a memory that is accessed by using a command instead of reading by the second read valid signal REB [i] and the second read address RAB [i], the second read circuit 23B includes the second read valid signal. When REB [i] indicates validity, a second read command [i] for reading data stored at the position of the second read address RAB [i] is generated.
The second entry information EDB [second entry number ENB [i]] is stored in the second search table 22B after two cycles from the input of the second read address RAB [i] when the second read valid signal REB [i] is valid. The second entry information EDB [i], which is the data read from, is output.

  The two-cycle delay is latched before outputting the data stored in the cells in the memory and the one-clock delay generated by latching the signal such as the address input to the second table memory. Therefore, it is a value obtained by adding a delay of 1 clock generated for the purpose. In the case of a device in which the type of the second table memory, the memory, and the second reading circuit 23B and the like are configured as separate components, there is a possibility that the delay is larger than the above. The numbers in the boxes representing the signals in FIG. 9 represent the entry numbers i (1 to 16), and the entries 1 = 5, 7, 10 and 2 indicating that the second read valid signal REB [i] is valid. 12 is output.

[Effect of the third embodiment]
Thus, in the present embodiment, the first entry information EDA includes the second entry number ENB indicating the entry number of the second entry information EDB corresponding to the first entry information EDA, and the first read information The circuit 23A separates the second entry number ENB from the first entry information EDA read from the first search table 22A, and compares the first entry information EDA excluding the second entry number ENB. In addition to outputting to the circuit 3n, the separated second entry number ENB is output to the second readout circuit 23B, and the comparison circuit 3n replaces the first search table 22A with the first readout circuit 23A. The first entry information EDA excluding the second entry number ENB is input, and the second read circuit 23B is connected to the first read circuit 2 Based on the second entry number ENB from A, and generates the second read signal RB is obtained so as to output to the second search table 22B.

  Thereby, when the second entry information EDB is not necessary and there is an entry that can be determined to be compatible only with the first entry information EDA, it is not necessary to prepare an entry in the second search table 22B for the entry. Accordingly, since the number of entries in the second search table 22B can be realized with a smaller number of entries than the number of entries in the first search table 22A, the circuit scale (memory amount) of the second search table 22B can be reduced.

[Operation Example of Third Embodiment]
Next, an operation example of the frame search processing apparatus 10 according to the present embodiment will be described.
Here, as an example, the frame information FD input from the frame information extraction unit 11 includes the source IP address and the destination IP address stored in the IP header of the input frame FIN input by the frame search processing device 10. It will be taken up and explained as.
An example of the first entry information EDA and the second entry information EDB when searching for the frame information FD will be described below.

[Case 1]
First entry information EDA = Destination IP address for conforming to entry, its mask length, read flag of second entry information EDB, and second entry number ENB
Second entry information EDB = source IP address and mask length for conforming to entry

  As shown in [Case 4] of the first embodiment, an entry that is determined to be compatible based on a condition for only the destination IP address and an entry that is determined to be compatible based on a condition for both the destination IP address and the source IP address , There are devices that do both searches. For example, in the case of a search table in which entries that are discarded only by looking at the destination IP address and entries that are discarded by looking at both the destination IP address and the source IP address are mixed.

  Thus, entry information indicating search conditions common to all entries (destination IP address and its mask length in the above example) and entry information indicating search conditions added to only a part of the entries (transmitted in the above example) If the former entry information is the first entry information EDA and the latter entry information is the second entry information EDB, the entry information that does not require the latter entry information. Since the latter entry information is not read from the search table when the conformity determination is performed for, the number of read bits of the search table can be reduced, and the same effect as [Case 4] of the first embodiment can be obtained. .

  Further, since the number of entries in the second search table 22B storing the second entry information EDB can be expected to be smaller than the number of entries in the first search table 22A storing the first entry information EDA, the second search table 22B The amount of memory necessary for the first search table 22A and the second search table 22B is reduced as compared to the case where the number of entries is the same as in [Case 4] of the first embodiment. Can do.

  For example, if half of all entries (256 entries) are entries that require only the destination IP address and the remaining entries are entries that also use the source IP address as a condition, the first entry In the search processing unit 12 of the embodiment, the average number of read bits per entry is 56.5 bits (= destination IP address 32 bits + destination IP address mask length 5 bits + second entry information EDB Read flag 1 bit + (source IP address 32 bits + source IP address mask length 5 bits) / 2), and the amount of memory is 19200 bits (= (source IP address 32 bits + destination IP address 32 bits +) Source IP address mask length 5 bits + destination IP address mask length 5 bits + second entry information E A read flag 1 bit) * 256) of B.

  On the other hand, in this example, the average number of read bits per entry is 64.5 bits (= destination IP address 32 bits + destination IP address mask length 5 bits + second entry information EDB read flag 1 bit + second Entry number 7 bits + (source IP address 32 bits + source IP address mask length 5 bits) / 2), and the amount of memory is 16256 bits (= (source IP address 32 bits + source IP address) (Mask length 5 bits + second entry information EDB read flag 1 bit + second entry number 7 bits) * 256 + (source IP address 32 bits + source IP address mask length 5 bits) * 256/2) Become.

  Thus, the average number of read bits per entry in this example is larger by the number of bits of the second entry number ENB than in [Case 4] of the first embodiment, but the second search is performed. By reducing the number of entries in the table 22B, the memory amount of the search table can be reduced. The effect becomes more prominent as the ratio of the number of entries that do not require the second entry information EDB is larger.

[Case 2]
First entry information EDA = Hash value calculated from second entry information EDB, entry information type, second entry number ENB,
2-1 entry information = source IPv4 address and destination IPv4 address to match the entry,
2-2 entry information = source IPv6 address and destination IPv6 address to match the entry

  As shown in [Case 3] of the first embodiment, the number of bits read from the search table can be reduced by using the hash value of the bit string representing the search condition as the first entry information EDA. For example, a bit string shortened by hashing by performing a hash operation on frame information FD having a large number of bits and a search condition such as a destination IP address (128 bits) and a source IP address (128 bits) of IPv6 A match comparison is performed, and a bit string before hashing is read from the search table only when a match is found in the comparison, and conformance is determined.

  The hashed bit string of the search condition is stored in the first search table 22A as the first entry information EDA, and the bit string before hashing is stored in the second search table 22B as the second entry information EDB. In an apparatus that performs a search process for both an IPv4 frame and an IPv6 frame, either an IPv4 IP address or an IPv6 IP address, which is a search condition, is stored in an entry of the second search table 22B.

At this time, since the IPv6 IP address is 128 bits, the IPv4 IP address is 32 bits, so that each entry of the second search table 22B can store an IPv6 IP address having a large number of bits. When storing the IPv4 IP address, a part of the area for storing the IPv6 IP address is used, and the remaining area is reserved.
As described above, when one of the search conditions having different bit numbers is stored in the entry, a storage area that is not used for the entry storing the search condition having the shorter bit number is generated. The storage area not used increases the size of the search table memory more than necessary.

Therefore, in this example, together with the use of the hash value, as shown in [Case 5] of the first embodiment, the entry information type (IPv4 or IPv6 in this example) is added to the first entry information EDA. And a 2-1 search table for IPv4 and a 2-2 search table for IPv6.
Since the search condition of each entry is either IPv4 or IPv6, the number of entries used in the 2-1 search table and the number of entries used in the 2-2 search table Is the number of entries used in the first search table 22A.

  Further, when the second entry number ENB is added to the first entry information EDA and the entry information type indicates IPv4, the IP address of IPv4 which is the search condition for the entry is stored in the second entry number ENB. This is used as the entry number of the 2-1 search table. Similarly, when the entry information type indicates IPv6, the second entry number ENB is used as the entry number of the 2-2 search table that stores the IPv6 IP address that is the search condition for the entry. use.

In the above, each comparison circuit 3n determines whether or not to read the second entry information EDB [second entry number ENB [i]] from the 2-1 search table or the 2-2 search table. 2 The retrieval table reading determination is obtained based on the first conformity determination result CJA.
In the first conformity determination, the frame information FD conforms to the entry information type [i] included in the first entry information EDA [i] (in the above example, when the frame is IPv4, the entry information type is IPv4). Or the entry information type indicates IPv6 when the frame is IPv6), and the hash value calculated from the second entry information EDB matches the hash value calculated from the frame information FD (the above example) Is included in the hash value of the frame information FD obtained by performing a predetermined hash operation (for example, SRC8) on the bit string of the source IP address and the destination IP address included in the frame information FD and the first entry information EDA [i]. If the hash values match), it is determined as conforming.

Further, in the second search table read determination, when it is determined that the first match determination is appropriate, it is determined that the second entry information EDB is read from the second search table 22B. Further, the comparison circuit 3n outputs the read determination result RJn [i] to the second read circuit 23B.
The first reading circuit 23A outputs the second entry number ENB [i] and the entry information type [i] included in the first entry information EDA [i] to the second reading circuit 23B. To do.

  When the read determination result RJn [i] from at least one comparison circuit 3n indicates that the second entry information EDB is being read, the second read circuit 23B determines the second read circuit 23B according to the entry information type [i]. The search table for reading the 2-entry information EDB is selected from the 2-1 search table and the 2-2 search table, and from the entry indicated by the second entry number ENB [i] in the selected search table. Then, the second entry information EDB [second entry number ENB [i]] is read out and input to the comparison circuit 3n.

  In this way, in this example, when one of the search conditions (IPv4 and IPv6 IP addresses) having different numbers of bits is stored in the entry, each of the different search tables (2-1 search table and 2-2) is stored. Storage table), the storage area which is not used when storing in one search table entry does not occur, and the scale of the search table memory can be suppressed.

  For example, if 1/2 of all entries (256 entries) are entries that require IPv4 and the remaining entries are entries that require IPv6, the search processing unit 12 of the first embodiment may be used. For example, the memory amount is 67840 bits (= (source IP address 128 bits + destination IP address 128 bits + hash value 8 bits + entry information type 1 bit) * 256). On the other hand, in this example, the memory amount is 45056 bits (= (source IPv6 address 128 bits + destination IPv6 address 128 bits + hash value 8 bits + entry information type 1 bit + second entry number 7 bits)) * 128+ ( (Source IPv4 address 32 bits + destination IPv4 address 32 bits + hash value 8 bits + entry information type 1 bit + second entry number 7 bits) * 128).

  In addition to the above search table configuration, the 2-1 search table is an entry having a capacity capable of storing an IPv4 destination / source IP address. It is also possible to store the bits (the same number of bits as the IPv4 IP address length) in the 2-1 search table and store the upper 96 bits of the IPv6 IP address in the 2-2 search table. is there.

In this case, as in the first embodiment, the entry of the 2-1 search table is read using the entry number of the first search table 22A, and only when the entry information type is IPv6. The entry in the 2-2 search table indicated by the second entry number ENB included in the one entry information EDA is read.
As a result, the number of bits in the search table can be reduced, and all entries can be used for IPv4. Therefore, half of all entries (256 entries) are IPv4-only entries with IPv4 as the remaining entries. Compared to the case where the entry is an IPv6-only entry with IPv6 as a condition, the restriction on the number of entries for the entry for IPv4 is relaxed, and the entry number can be set up to twice the maximum.

[Fourth Embodiment]
Next, a frame search processing device 10 according to the fourth exemplary embodiment of the present invention will be described with reference to FIG. FIG. 10 is a block diagram illustrating a configuration of a search processing unit according to the fourth embodiment.
In the first embodiment, the case where the first entry information EDA is output from the first search table 22A to the comparison circuit 3n has been described as an example. In the present embodiment, a case where the first entry number ENA is output from the first readout circuit 23A to the comparison circuit 3n will be described.

  In the present embodiment, the search processing unit 12 includes, as main circuit units, a frame information distribution circuit 21, a first search table 22A, a second search table 22B, a first readout circuit 23A, a second readout circuit 23B, N comparison circuits 3n (n = 1 to N; N is a natural number of 2 or more) and a search result merging circuit 24 are provided.

The first search table 22A has Ne (N is a natural number of 1 or more) entries i (i = 1 to Ne), and the first entry information EDA [i] is stored in each entry i.
The second search table 22B has Ne entries j (j = 1 to Ne), and stores second entry information EDB [j] in each entry j.

The first search table 22A receives the first read signal RA from the first read circuit 23A, and reads the stored first entry information EDA [i] from the address indicated by the signal at the timing indicated by the signal.
Similarly, the second search table 22B receives the second read signal RB from the second read circuit 23B, and stores the second entry information EDB [i] stored at the timing indicated by the signal from the address indicated by the signal. Is read.

  In the first embodiment, the first entry information EDA is read from the first search table 22A one by one in the order according to the entry number. Therefore, the time required for the search processing for one frame depends on the time required to read all entries from the first search table 22A.

  For example, in a device in which the first search table 22A has 256 entries and reads out the one entry for each cycle of the clock used to drive the search processing unit 12, the time required for the search process is as follows: Time required to read all entries from the first search table 22A = 256 cycles, a predetermined constant required from reading the first entry information EDA [i] to reading the second entry information EDB [i] in 256 cycles The time difference Td (for example: 3 cycles) and the time for integration suitability determination (for example: 1 cycle) are combined to add a time of about 4 cycles (for example: 260 cycles).

  That is, the search for each frame can be processed in one cycle per entry by pipeline processing in units of entries, and requires the same number of cycles as the number of entries. However, in order to start the search for the next frame, the time until the pipeline is emptied, that is, the time until the last entry exits the pipeline (= time Td + time required for integrated conformity determination) It is necessary to add. This addition time is about 4 cycles. Thus, the time required to read all entries from the first search table 22A accounts for most of the time required for the search process.

  The Td is two cycles from when the first search table 22A inputs the first read address RAA [i] and the first read valid signal REA [i] to when the first entry information EDA [i] is output. A delay for one cycle, a delay for one cycle from when the comparison circuit 3n inputs the first entry information EDA [i] to the output of the read determination result RJn [i] based on the input, and the second read A delay from when the valid generation unit 42B inputs the read determination result RJn [i] from each comparison circuit 3n to when the second read valid signal REB [i] is output based on the above (in this example, a simple logical sum) Since this is an operation, there is no delay).

  What is output two cycles after the input of the first read address RAA [i] when the first read valid signal REA [i] to the first search table 22A is valid is the memory for the first search table 22A. This is because there is a one-clock delay caused by latching a signal such as an input address and a one-clock delay caused by latching before data stored in a cell in the memory is output.

  Therefore, according to the first embodiment, the search processing time increases as the number of entries in the search table increases. However, in order to maintain performance (= the number of frames that can be searched per unit time), comparison is required. It is necessary to increase the parallelism of the circuit 3n (n is increased). That is, the increase in the number of entries in the search table not only increases the size of the memory used as the search table, but also increases the circuit size of the comparison circuit 3n.

  Therefore, in the present embodiment, the first read circuit 23A includes Nr pieces of first entry information EDA [i] (Nr is a natural number of 1 or more, Ne = Nr * Nl and Nl is a natural number of 1 or more). (I = Nr * k + 1, Nr * k + 2,..., Nr * k + Nr, the first entry number k is an integer greater than or equal to 0 and less than Nl) is simultaneously read out in parallel from the first search table 22A, and the Nr first One entry information EDA is distributed to each comparison circuit 3n. Further, each time the reading is performed, the value of the first search table reading control variable is incremented by 1, and the value is returned to 0 when the maximum value (Nl-1) is reached.

  As a result, the reading from the first search table 22A is performed in order according to the entry number of the first entry information EDA for each Nr, so the time required to read all the entries from the first search table 22A Is 1 / Nr of the time required in the first embodiment. However, the above does not include a period during which a signal indicating a read stop of the first search table 22A described later is input.

Note that the first readout circuit 23A receives a search state SSn indicating whether or not the search is output from each comparison circuit 3n (n = 1 to N), and the search state of any one comparison circuit 3n. When the SSn is being searched, the first search table 22A is read.
Further, for all the comparison circuits 3n, when the search state SSn indicates that the search is stopped, the first search table 22A is not read. As a result, power consumption during a period when reading of the first search table 22A is unnecessary can be reduced.

  The frame information distribution circuit 21 receives the frame information FD from the frame information extraction unit 11, determines a comparison circuit 3n that is an output destination of the frame information FD based on a predetermined comparison circuit selection method, and the comparison circuit 3n has a function of outputting the frame information FD as frame information FDn.

  An example of the comparison circuit selection method is to determine whether or not each comparison circuit 3n is performing a search process, and to select one of the comparison circuits 3n that is not performing the search process. As an example of realizing the comparison circuit selection method with a simple circuit, there is a method of selecting the comparison circuit 3 (n + 1) having a number obtained by adding 1 to the number n of the comparison circuit 3n selected at the previous input when the frame information FD is input. . In this comparison circuit selection method, when the number n of the comparison circuit 3n selected at the previous input is N, the comparison circuit 31 of number 1 is selected and the comparison circuit 3n is selected cyclically.

The comparison circuit 3n performs a search process for searching for an entry having a search condition matching the frame information FDn according to the input of the frame information FDn (n = 1 to N) from the frame information distribution circuit 21. Run.
In this search process, the comparison circuit 3n uses the input frame information FDn and the first entry information EDA [i] read from the entry i (i = 1 to Nr) of the first search table 22A by the first reading circuit 23A. Based on the above, the frame information FDn is subjected to a first conformity determination for determining whether or not the search condition represented by the first entry information EDA [i] is satisfied, and a first signal as a circuit internal signal is obtained. A conformity determination result CJAn [i] (not shown) is obtained.

  Further, the comparison circuit 3n obtains the second entry information EDB [i] from the entry i (i = 1 to Nr) of the second search table 22B based on the obtained first suitability determination result CJAn [i]. A second search table read determination for determining whether to read is performed, and the obtained read determination result RJn [i] is output to the second read circuit 23B.

Further, after obtaining the first conformity determination result CJAn [i], the comparison circuit 3n obtains the second conformity determination result CJB [i] based on the second entry information EDB [i] and the frame information FDn, and Based on the first conformity determination result CJAn [i] and the second conformity determination result CJB [i], an integrated conformity determination indicating whether the entry i conforms to the frame information FDn is performed.
For this reason, the comparison circuit 3n needs to temporarily hold the first suitability determination result CJAn [i] until the integrated suitability determination is performed. It should be noted that the first conformity determination result CJA of another entry obtained during the period needs to be held in the same manner.

  The second read circuit 23B inputs Nr read determination results RJn [i] (i = Nr * k + 1, Nr * k + 2,..., Nr * k + Nr) from each comparison circuit 3n. Here, for each of Nr entry numbers i = Nr * k + 1, Nr * k + 2,..., Nr * k + Nr, read determination result RJn [i] indicating that the second search table is read from at least one comparison circuit 3n. Is stored in a second read waiting queue 44B, which will be described later, that the second read circuit 23B has. Therefore, the numbers of entries that need to be read from the second search table 22B are stored in the second read waiting queue 44B in the order of the numbers.

  When the queue stores the entry numbers of the predetermined number Ns or more by accumulating the entry numbers in the second read waiting queue 44B, it can be accumulated by taking out the entry numbers from the queue as described below. The accumulation in the queue is temporarily stopped until a state is reached. Further, the first read circuit 23A outputs a first read stop signal RSA for stopping the reading of the first entry information EDA from the first search table 22A, receives the signal, and receives the signal. 23A does not read the first entry information EDA.

This prevents overflow of the second search table read waiting entry queue. At this time, the determination speed for the first search table 22A (number of entries determined per clock = Nr) is higher than the determination speed for the second search table 22B (number of entries that can be determined per clock = 1).
For this reason, if the second read waiting queue 44B does not perform processing for preventing the overflow, the number of entries to be read in the second search table in the determination for the first search table 22A exceeds the determination speed for the second search table 22B. When a situation occurs, when the accumulation in the second read queue 44B increases and exceeds the maximum number that can be accumulated in the queue (overflow occurs), an entry that cannot be determined for the second search table 22B is generated. Problems occur.

Since the time for reading all the entries from the first search table 22A increases due to the suspension of the reading of the first search table, each comparison circuit 3n is only used for the time when the reading from the first search table 22A is paused. This increases the time from the start to the end of the search process.
For example, when Ne = 256 and Nr = 8, if there is no temporary stop, the time required to read all entries in the first search table 22A is 32 cycles (== Ne / Nr), but when all the entries, which are the cases where the pause is maximum, are read out of the second search table 22B, one entry is generated per clock. Become.

  Accordingly, the time required for the search processing of each comparison circuit 3n is not a constant value, and changes according to the settings of the frame information FD, the first entry information EDA, and the second entry information EDB input to the comparison circuit 3n. For this reason, if the time required for the search process of the comparison circuit 3n increases, and there is a possibility that the frame information FD is input to the apparatus when all the comparison circuits 3n are in the search process, the search of the frame information FD is performed. The input to the processing unit 12 is temporarily stopped until the input becomes possible, that is, until the search process is completed by one or more comparison circuits 3n.

  The second reading circuit 23B takes out the entry number j stored in the second reading waiting queue 44B one by one, reads the second entry information EDB [j] from the second search table 22B, and The 2-entry information EDB [j] is distributed to each comparison circuit 3n (n = 1 to N) together with the entry number j.

  Since the entry numbers taken out from the queue are taken out from the most recently stored according to the FIFO function, the entries in order of storage, that is, the entries that need to be read from the second search table 22B are arranged in the order of the entry numbers. It will be taken out in order. When the second read waiting queue 44B is empty, that is, when the entry number is not accumulated, the second read circuit 23B does not read from the second search table 22B.

Based on the frame information FDn and the second entry information EDB [j], the comparison circuit 3n determines whether the frame information FDn matches the second entry information EDB [j]. A determination is made to obtain a second conformity determination result CJB [j].
Further, the comparison circuit 3n, for the entry j, the first conformity determination result CJAn [j] obtained after the first entry information EDA [j] is read from the first search table 22A, and the subsequent second entry Based on the second suitability determination result CJB [j] obtained after the information EDB [j] is read from the second search table 22B, the integrated suitability determination is performed. The comparison circuit 3n ends the search and outputs the search result SRn when the entry determined to be compatible by the integrated match determination is found or when the determination of the frame information FDn is completed for all entries. .

In the example in which the entry entry priority is included in the first entry information EDA or the second entry information EDB, and the entry having the highest entry priority is found among the entries determined to be compatible by the integrated suitability determination, The search is not terminated when one entry that is determined to be conforming by the conformity determination is found, but only when the integrated conformance determination is completed for all entries or when an entry having an upper limit application priority is found. finish.
The comparison circuit 3n obtains the result obtained by the integrated suitability determination (for example, information indicating the result included in the entry number i matched in the determination or the second entry information EDB [i] of the entry; passing / discarding). Information or a port number indicating a transmission destination) is output to the search result merging circuit 24 as a search result SRn.

In addition, the first embodiment and the second embodiment in which the time from when each comparison circuit 3n obtains the first entry information EDA [i] until the second entry information EDB [i] is obtained is a fixed time Td. Unlike the form, in this example, the time varies depending on the state of the second read waiting queue 44B in the second read circuit 23B.
In the first embodiment and the second embodiment, the second entry information EDB input from the second search table 22B when the time Td has elapsed since the comparison circuit 3n obtained the first entry information EDA is: Since it is guaranteed to correspond to the same entry number, it is not necessary to input the entry number when the second entry information EDB is input.

However, in this example, since it is not guaranteed that the second entry information EDB input when a certain time has passed since the first entry information EDA has been obtained corresponds to the same entry number, the second entry information EDB is combined with the second entry information EDB. Enter the entry number.
Each comparison circuit 3n obtains the first conformity determination result CJAn [i] indicating conformity and the entry number i (waiting for the second conformity determination) when the read determination result RJn [i] indicating that the second search table is read is obtained. Entry number) is temporarily stored.

Then, when the entry number j input together with the second entry information EDB [j] matches the stored entry number i, the frame information FDn matches the second entry information EDB [j]. The second suitability determination as to whether or not to perform is performed to obtain a second suitability determination result CJB [j].
In addition, before obtaining the second match determination result CJB [j], the first match determination is also performed for the entry i ′ subsequent to the entry j, and the entry number i ′ is temporarily held to thereby store the search processing speed. Therefore, the second matching determination waiting entry number is held in the queue.

  As an example of a determination completion specifying method for knowing when each comparison circuit 3n finishes determining the frame information FDn for all entries, the first entry number ENA when the comparison circuit 3n inputs the frame information FDn and starts the search. There is a method of using the timing when the reading of each entry in the first search table 22A is completed and the first entry number ENA reaches the held value.

  Next, the first readout circuit 23A and the second readout circuit 23B according to the present embodiment will be described with reference to FIG. FIG. 11 is a block diagram illustrating a main part of a search processing unit according to the fourth embodiment.

  The first read circuit 23A has a function of updating the first entry number k that was output one cycle earlier by one in synchronization with the clock and outputting the result as the first read address RAA [k]. However, 0 is output when the operation of the apparatus starts and when the first entry number k becomes Nl. When the first read stop signal RSA indicates stop, the first entry number k is not updated.

  Further, the first reading circuit 23A uses the first entry number k (however, when the first reading stop signal RSA indicates stop, a predetermined invalid value that is a value outside the range of the entry number of the first search table 22A). ) For a predetermined time (the time until the first search table 22A outputs the first entry information EDA [i] (i = Nr * k + 1, Nr * k + 2,..., Nr * k + Nr)). Output. Thus, the first entry number k is input to each comparison circuit 3n simultaneously with the first entry information EDA [i] (i = Nr * k + 1, Nr * k + 2,..., Nr * k + Nr). Further, the first reading stop signal RSA notifies each comparison circuit 3n that reading from the first search table 22A is stopped by the first entry number k indicating a predetermined invalid value.

Further, the first readout circuit 23A receives from one of the comparison circuits 3n (n = 1 to N) a search state SSn that indicates whether the comparison circuit 3n is searching or is stopped. The first read valid signal REA [k] indicating validity is output during a period when the search state SSn corresponding to the comparison circuit 3n indicates that the search is being performed and the first read stop signal RSA does not indicate a stop. To do. In addition, the first read valid signal REA [k] indicating invalidity is output during a period other than the above.
It should be noted that during the period when the search state SSn indicating the search stop is input from all the comparison circuits 3n (n = 1 to N) or during the period when the first read stop signal RSA indicates the stop, the first read valid indicating invalid The signal REA [k] is output.

The first search table 22A is realized by the first table memory M1, and Nr pieces of first entry information EDA [i] are included in each word located at each address k (k = 0 to Nl) of the memory. (I = Nr * k + 1, Nr * k + 2,..., Nr * k + Nr) is stored.
The first search table 22A receives the first read address RAA [k] and the first read valid signal REA [k] from the first read circuit 23A, and the first read valid signal REA [k] indicates valid. , Nr pieces of first entry information EDA [i] (i = Nr * k + 1, Nr * k + 2,..., Nr *) stored at the position indicated by the first read address RAA [k] from the first table memory. k + Nr) is read out and distributed to each comparison circuit 3n (n = 1 to N). Further, when the first read valid signal REA [k] indicates invalid, the reading and distribution are not performed.

  The comparison circuit 3n holds the frame information FDn input from the frame information distribution circuit 21, and holds the frame information FDn and the Nr pieces of first entry information EDA [i] input every clock cycle. The first suitability determination is performed as to whether or not the search conditions represented by each match, and Nr first suitability determination results CJAn [i] are obtained every clock cycle. Further, a second search table read decision is made as to whether or not to read each of the Nr pieces of second entry information EDB [i] from the second search table 22B, and the Nr pieces are read into the second read circuit 23B every clock cycle. The read determination result RJn [i] is output.

Further, the comparison circuit 3n receives the first entry number k from the first reading circuit 23A, and the reading determination result RJn [i] (i = Nr * k + 1, Nr * k + 2, 2) for a predetermined time from the input time point. .., Nr * k + Nr) is delayed by the time until it is output, and the value is output to the second readout circuit 23B. Thus, the first entry number k corresponding to the read determination result RJn [i] is output at the same time.
When the first entry number k indicates a predetermined invalid value, the first suitability determination and the second search table read determination using the first entry information EDA [i] input at the same time are not performed. This is because the first entry information EDA [i] is not a value read from the first search table 22A but is invalid.

The second read circuit 23B includes a second read effective generation unit 42B, a second read wait queue 44B, and a second read signal generation unit.
The second read effective generation unit 42B generates Nr read determination results RJn [i] (i = Nr * k + 1, Nr * k + 2,...) From each of the comparison circuits 3n (n = 1 to N) every clock cycle. , Nr * k + Nr). When the read determination result RJn [i] of each entry i input from each comparison circuit 3n includes a result indicating that one or more readings are present, a second read valid signal REB [i] indicating validity is output. If all the data indicates no reading, the second reading valid signal REB [i] indicating invalidity is output. Accordingly, the second read enable signal REB [i] is output for Nr entries i (i = Nr * k + 1, Nr * k + 2,..., Nr * k + Nr) every clock cycle.

  The second read waiting queue 44B receives the first entry number k output from any one comparison circuit 3n every clock cycle. Since all the comparison circuits 3n simultaneously input the first entry number k having the same value and output it after being delayed by the same time, the first entry number k having the same value is output at the same time. The output first entry number k may be adopted.

  Furthermore, the second read waiting queue 44B receives the second read from the second read effective generation unit 42B for Nr entries i (i = Nr * k + 1, Nr * k + 2,..., Nr * k + Nr) every clock cycle. The valid signal REB [i] is input. At this time, when the second read valid signal REB [i] indicating validity is received, the entry number i is generated based on the input first entry number k, and the generated number is queued (FIFO). ). The entry number i can be generated by an operation of Nr * k + 3 when, for example, the third of the inputted Nr second read valid signals REB [i] indicates validity. Note that the entry number i 'of the second read valid signal REB [i'] indicating invalidity is not accumulated.

In addition, the second read waiting queue 44B outputs a first read stop signal RSA indicating a stop during a period in which an entry number of a predetermined number Ns or more is accumulated in the queue. Also, the entry number stored in the queue is extracted in synchronization with the clock and output as the second entry number j. At this time, when the queue is empty (no accumulation), an invalid value of the entry number (a predetermined invalid value that is a value outside the range of the entry number; for example, 0) is output.
The entry number i of the second read valid signal REB [i] indicating validity is not input to the queue, but Nr second read valid signals REB [i] (i = Nr * k + 1, Nr * k + 2). ,..., Nr * k + Nr) indicates that the first entry number k and the bit string representing the Nr second read valid signals REB [i] are input to the queue when one or more of them are valid. Also, the same function as described above can be realized.

  The second read signal generation unit inputs the second entry number j from the second read waiting queue 44B, and when the value of the entry number is in a valid range, based on the second entry number j, A second read address RAB [j] is generated and output. Further, a second read valid signal REB [j] is generated and outputted, indicating invalidity when the value of the second entry number ENBj is a predetermined invalid value, and valid in other cases. Further, the second entry number j is delayed by a predetermined time from the input time point (time until the second search table 22B outputs the second entry information EDB [j]), and the value is output. As a result, the second entry number j corresponding to the second entry information EDB [j] is simultaneously input to each comparison circuit 3n.

The second search table 22B stores the second entry information EDB [j] in each entry j. The second search table 22B stores the second entry information EDB [j] from the entry number j. The actual address of the second table memory can be generated by a simple calculation. The example of the calculation is the address of the second table memory = j−1. In the example, the second entry information EDB [j] of the entry number j is the word at the address of the second table memory = j−1. Is remembered.
A method of generating an address from the entry number by another calculation method may be used. In the above example, when entry number = second entry number ENB [i], second read address RAB [i] = second entry number ENB output by second read address generation unit 41B to second search table 22B. [I] -1.

The reason why the first entry number k and Nr pieces of first entry information EDA [i] (i = Nr * k + 1, Nr * k + 2,..., Nr * k + Nr) are simultaneously input to each comparison circuit 3n is input simultaneously. The entry number k and the entry information [i] correspond to each other, that is, the entry number input at the same time as the entry information is used to know which entry the input Nr entry information belongs to. be able to.
Therefore, in addition to the method in which the first entry number k and Nr pieces of first entry information EDA [i] (i = Nr * k + 1, Nr * k + 2,..., Nr * k + Nr) are input simultaneously, the first entry number k The entry number can be associated with the entry information by a method in which the input of Nr and the input of the Nr pieces of first entry information EDA [i] are set to a fixed time difference.

Further, the first entry number k and Nr read determination results RJn [i] (i = Nr * k + 1, Nr * k + 2,..., Nr * k + Nr) are simultaneously input to the second read circuit 23B from each comparison circuit 3n. The reason why the second entry number j and the second entry information EDB [j] are simultaneously input to each comparison circuit 3n is the same as described above. The result is associated with the method of simultaneous input.
In the present embodiment, configurations other than those described above are the same as those in the first embodiment, and a description thereof is omitted here.

[Operation of Fourth Embodiment]
Next, the operation of the search processing unit 12 according to the present embodiment will be described with reference to FIGS. FIG. 12 is a time chart illustrating the operation of the search processing unit according to the fourth embodiment. FIG. 13 is a time chart (continued) showing the operation of the search processing unit according to the fourth embodiment. In FIGS. 12 and 13, the case where the number of comparison circuits 3n is 2 and the number of entries Nr is 2 is taken as an example, and each signal in the search processing unit 12 passes over time (from left to right). The accompanying changes are shown.

  In FIG. 12 and FIG. 13, each signal in the search state SSn (n = 1, 2) is a signal indicating H level: search processing in progress / L level: search stop in progress, and frame information FDn (n = 1, 2) is input at the H level: search processing is in progress, and all entries (Ne = 16) are read from the table for one frame information FDn (Nr = 2 because it is the shortest). L level: after the clock of Ne / Nr = 8): The search process is stopped.

  The signal of the first read valid signal REA [k] is a signal representing H level: valid / L level: invalid, and the logical sum of the signals of the search state SS1 and the search state SS2 includes the first read stop signal RSA. This is a signal obtained by performing a logical product. That is, when the search state SS1 or the search state SS2 is being searched (one or more comparison circuits 3n are being searched) and the first read stop signal RSA is read, the first table memory that is enabled for reading is stored. Two (Nr = 2) pieces of first entry information EDA [i] (i = 2 * k + 1, 2 * k + 2) stored at the position of the first read address RAA [k] are simultaneously read in parallel. become.

The signal of the first read address RAA [k] increases by +1 for each repeated clock within a range of 0 to 7 (Nl = Ne / Nr = 16/2 = 8, k = 0 to Nl−1). However, the value after 7 is 0. The numbers in each box representing the first read address RAA [k] in FIGS. 12 and 13 represent the entry number k (0 to 7), the signal value of the entry number k is k, and the entry number k. And the first read address RAA [k] have the same value.
That is, the first entry information EDA [2 * k + 1] and the first entry information EDA [2 * k + 2] are stored at the address k of the first table memory, and the entry number is incremented every clock cycle. Two pieces of first entry information EDA corresponding to the entry k are simultaneously read in parallel from the first table memory.

  It should be noted that the first read valid signal REA [k] and the first read address RAA [k], which are signals for reading the first entry information EDA [i], are input to the first table memory at the same time. However, a memory that is not simultaneously input, for example, a memory that needs to input the first read enable signal REA [k] for a predetermined cycle before the first read address RAA [k] is used as the first table memory. It is also possible to do. In this case, the first read circuit 23A generates the first read valid signal REA [k] and the first read address RAA [k] according to the signal input method defined by the memory.

  In the case of a memory that is accessed by using a command instead of reading by the first read valid signal REA [k] and the first read address RAA [k], the first read circuit 23A has the first read valid signal REA. When [k] indicates validity, the first read command [k] for reading the data stored at the position of the first read address RAA [k] is generated.

  The first entry information EDA [i] is data read from the first search table 22A two cycles after the input of the first read address RAA [k] when the first read valid signal REA [k] is valid. Two pieces of first entry information EDA [i] (i = 2 * k + 1, 2 * k + 2) are output. The numbers in each box representing the first entry information EDA [i] in FIGS. 12 and 13 represent the entry numbers i (1 to 16).

  The two-cycle delay is latched before outputting the data stored in the cells in the memory and the one-clock delay generated by latching the signal such as the address input to the first table memory. Therefore, it is a value obtained by adding a delay of 1 clock generated for the purpose. In the case of a device in which the type of the first table memory, the memory, and the first reading circuit 23A, etc. are configured as separate components, there is a possibility that the delay is larger than the above.

  In addition, a configuration in which the delay amount varies depending on the state of the memory instead of a fixed delay, for example, whether or not the memory is accessed from the outside. In this case, in the above configuration, since the first entry number k needs to be input to each comparison circuit 3n in accordance with the variation in the delay, the first entry from the first reading circuit 23A that cannot know the variation in the delay. Instead of inputting the number k, the first entry number k is input from the first search table 22A.

Each signal of the read determination result RJn [i] (n = 1, 2) is a signal indicating the presence / absence of reading, and the period in which the boxes in FIGS. 12 and 13 are shown indicates that there is reading. The numbers in the boxes represent entry numbers i (1 to 16).
Each comparison circuit 3n (n = 1, 2) outputs the read determination result RJn [i] after one cycle from the input of the first entry information EDA [i]. The one-cycle delay is caused by latching and outputting the read determination result RJn [i] by the comparison circuit 3n. When the second search table read determination n requires a complicated calculation of the first entry information EDA [i] and the frame information FDn, the delay may be longer than one cycle.

Here, in FIG. 12 and FIG. 13, the read determination result RJ1 [i] illustrates the case where the read number is indicated for the entry numbers i of 7, 10, 11, and 13. That is, the comparison circuit 31 has obtained the second search table read determination of reading the second entry information EDB [7], [10], [11], [13].
Similarly, the read determination result RJ2 [i] shows the case where the entry number i indicates that there is a read for 8, 9, 12, and 4. That is, the comparison circuit 32 has obtained the second search table read determination of reading the second entry information EDB [8], [9], [12], [4].

  The second read waiting queue 44B inputs and accumulates 7, 8, 9, 10, 11, 12, 13, and 4, which are entry numbers for which the read determination result RJn [i] is valid, into the queue. , One entry number is extracted and output per clock cycle. Note that a maximum of two (Nl = 2) entry numbers may be input to the queue per clock cycle. Therefore, when the number of entry numbers accumulated in the queue is 3 or more, that is, when the threshold value of the queue for outputting the first read stop signal RSA is set to 3 so that the queue does not overflow, The reading of the first entry information EDA from the first search table 22A is stopped by the 1 reading stop signal RSA.

  Since the first entry information EDA is not input to each comparison circuit 3n during the stop, as a result, the entry of the entry number to the queue is stopped. Even if the first read stop signal RSA indicating the stop is output, there is a certain delay until the entry number entry to the queue is stopped. It is necessary to provide a maximum accumulation amount in the queue that does not cause an overflow even when there is an input.

  As shown in FIG. 13, at the time T1, the entry number 7 and the entry number 8 are first input to the second read waiting queue 44B at the same time. However, since the queue is empty, the entry number 7 Is output to the second read signal generator without being stored in the queue, and is output from the second read signal generator to the second search table 22B as the second read address RAB [7]. The entry number 8 is stored in the queue. In the next clock cycle, the entry number 9 and the entry number 10 are simultaneously input to the queue. However, since the entry number 8 is being accumulated in the queue, the entry numbers 9 and 10 are accumulated in the queue. The entry number 8 being stored in the queue is output from the queue, and is output from the second read signal generator to the second search table 22B as the second read address RAB [8].

  In the clock cycle at time T2, entry number 11 and entry number 12 are simultaneously input to the queue. However, since entry numbers 9 and 10 are being accumulated in the queue, the entry numbers 11 and 12 are accumulated in the queue. Is done. The entry number 9 that has been stored in the queue is output from the queue, and is output from the second read signal generator to the second search table 22B as the second read address RAB [9]. Here, since the entry numbers accumulated in the queue are three, 10, 11, and 12, and reach the threshold value for outputting the first read stop signal RSA, the first read stop signal RSA has a value (L ).

  In the clock cycle at time T3, the entry number 13 is input to the queue. Since the entry numbers 10, 11, and 12 are being accumulated in the queue, the entry number 13 is accumulated in the queue. The entry number 10 that has been stored in the queue is output from the queue, and is output from the second read signal generator to the second search table 22B as the second read address RAB [10]. Here, since there are three entry numbers 11, 12, and 13 accumulated in the queue, the threshold value for outputting the first read stop signal RSA has been reached, so the first read stop signal continues from the previous clock cycle. RSA maintains a value (L) indicating stop of reading.

  In the clock cycle at time T4, there is no input, and the entry number 11 that has been stored in the queue is output from the queue, and the second search table is used as the second read address RAB [11] from the second read signal generator. To 22B. Here, since the entry numbers accumulated in the queue are 11, 12 and are less than the threshold for outputting the first read stop signal RSA, the first read stop signal RSA is a value (H) indicating that there is reading. Has changed.

Similarly, the clock cycle at time T5 has no input, and the entry number 12 that has been stored in the queue is output from the queue, and the second retrieval signal RAB [12] is used as the second retrieval address RAB [12]. It is output to the table 22B.
Similarly, the clock cycle at time T6 is not input, and the entry number 13 that has been stored in the queue is output from the queue, and the second read signal generation unit performs the second search as the second read address RAB [13]. It is output to the table 22B. If the reading is not stopped by the first reading stop signal RSA, the entry number 4 is input, but the first reading stop signal RSA outputs the reading stop three cycles before, Reading after one entry information EDA [3], [4] is delayed by two cycles.

Similarly, there is no input at the clock cycle at time T7, and the queue is also emptied, so the second read valid signal REB is invalidated.
Entry number 4 at time T8 is input with a delay of two cycles due to the stop of reading the first search table. Since the queue is empty, the entry number 4 is not accumulated in the queue but is output to the second read signal generator, and the second read signal generator outputs the second read address RAB [4] as the second read address RAB [4]. 2 is output to the search table 22B.

  The second entry information EDB [i] is data read from the second search table 22B after two cycles from the input of the second read address RAB [i] when the second read valid signal REB [i] is valid. Second entry information EDB [i] is output. The two-cycle delay is latched before outputting the data stored in the cells in the memory and the one-clock delay generated by latching the signal such as the address input to the second table memory. This is a value that combines the delay of one clock generated for this purpose, and in the case of a device in which the type of the second table memory and the memory and the second reading circuit 23B, etc. are composed of separate parts, the delay may be larger than the above. There is sex. The numbers in the boxes representing the second entry information EDB [i] in FIGS. 12 and 13 represent the entry numbers i (1 to 16), and the second read valid signal REB [i] indicates that it is valid. The entries 7, 8, 9, 10, 11, 12, 13, and 4 are output.

[Effect of the fourth embodiment]
Thus, in the present embodiment, the first search table 22A stores Nr pieces of first entry information EDA corresponding to a plurality of entries for each address, and the comparison circuit 3m uses the first search table. The Nr pieces of first entry information EDA read simultaneously in parallel from the table 22A are compared with the frame information FD, and the Nr pieces of read determination results RJn obtained for each of the first entry information EDA are compared with the first information. 2 When the second read circuit 23B indicates that any of the Nr read determination results RJn output from the comparison circuit 3m indicates that there is a read, the read determination result RJn is output to the second read circuit 23B. The second entry number ENB indicating the second entry information EDB corresponding to the obtained first entry information EDA is sequentially stored in the second read waiting queue 44B, The second entry number ENB stored in the second read waiting queue 44B is sequentially read out, and the second entry information EDB is read out from the entry of the second entry number in the second search table 22B. The second read signal RB for output to 3n is output to the second search table 22B.

  Thereby, in the first embodiment, the first entry information EDA is read one by one from the first search table 22A, whereas in this example, Nr pieces of first entry information EDA are read at a time. The time required to read all entries from the first search table 22A can be shortened to 1 / Nr as compared with the configuration in the first embodiment.

  If the second search table 22B is read many times, the second search table read waiting entry queue becomes full, and reading of the first search table 22A is interrupted by the first read stop signal RSA. The time required to read all the entries from the first search table 22A at 1 is increased. However, by suppressing the possibility that the frame information FD matches the search condition indicated by the first entry information EDA, for example, as in the case 3 described in the first embodiment, a hash is added to the first entry information EDA. By increasing the number of bits of the hash value by using it, the number of readings of the second search table 22B can be reduced, so that the increase in time can be suppressed.

[Extended embodiment]
The present invention has been described above with reference to the embodiments, but the present invention is not limited to the above embodiments. Various changes that can be understood by those skilled in the art can be made to the configuration and details of the present invention within the scope of the present invention. In addition, each embodiment can be implemented in any combination within a consistent range.

  DESCRIPTION OF SYMBOLS 10 ... Frame search processing apparatus, 11 ... Frame information extraction part, 12 ... Search processing part, 13 ... Frame buffer, 14 ... Frame composition part, 21 ... Frame information distribution circuit, 22A ... First search table, 22B ... Second Search table, 23A ... first readout circuit, 23B ... second readout circuit, 24 ... search result merge circuit, 31, 32, 3n, 3N ... comparison circuit, 41A ... first readout valid generator, 41B ... second readout valid Generation unit, 42A ... first read address generation unit, 42B ... second read address generation unit, 43A ... second entry number separation unit, 44B ... second read waiting queue, M1 ... first table memory, M2 ... second table Memory, M0 ... Common table memory, FIN ... Input frame, FD, FD1, FD2, FDn, FDN ... Frame information, SS, SS1, SS2, SSn, SS ... Search state, SR, SR1, SR2, SRn, SRN ... Search result, FOUT ... Output frame, RA ... First read signal, RAA ... First read address, REA ... First read valid signal, RB ... Second read signal , RAB ... second read address, REB ... second read valid signal, RAD ... read address, EDA ... first entry information, EDB ... second entry information, ENA ... first entry number, ENB ... second entry number, RJ , RJn: Read determination result, RSA: First read stop signal.

Claims (8)

A frame information extraction unit for extracting frame information for specifying frame processing to be performed on the input frame from the input frame;
The frame information extracted by the frame information extraction unit is sequentially compared with search conditions registered in advance for each entry to search for a matching entry that matches the input frame, and corresponds to the obtained matching entry. A search processing unit that outputs search results as processing information indicating the contents of frame processing to be performed on the input frame,
The search processing unit
For each entry, a first search table that stores first entry information comprising a part of the search condition corresponding to the entry;
A second search table that stores, for each entry, second entry information consisting of portions other than the first entry information in the search conditions corresponding to the entry;
For each entry, by comparing the first entry information read from the first search table and the second entry information read from the second search table with the frame information, the entry becomes A comparison circuit for determining whether or not the matching entry matches the input frame;
A first reading circuit that cyclically reads the first entry information from each entry and outputs the first reading signal to the comparison circuit for output to the comparison circuit;
A second read circuit for outputting a second read signal for cyclically reading the second entry information from each entry and outputting it to the comparison circuit to the second search table;
When the comparison circuit compares the first entry information and the second entry information of the entry with the frame information, the comparison circuit first compares the first entry information with the frame information, so that the first entry information is wherein determining whether to comply with the frame information, and outputs to the second readout circuit a first adaptation determination result obtained by the determination as read judgment result indicating reading necessity of the second entry information, the first If the result of the conformity determination indicates conformity, the second entry information is compared with the frame information to determine whether the second entry information is compatible with the frame information, and is obtained by the determination. When the second conformity determination result indicates conformity, the entry number of the entry, a part of the first entry information, or a part of the second entry information It is output as the search result corresponding to the fit entry,
The second read circuit reads the second entry information from the second search table when the read determination result output from the comparison circuit indicates that there is a read, and the read determination result is read. The frame search processing device characterized by not reading the second entry information from the second search table when indicating no.   A frame information extraction unit for extracting frame information for specifying frame processing to be performed on the input frame from the input frame;
  The frame information extracted by the frame information extraction unit is sequentially compared with search conditions registered in advance for each entry to search for a matching entry that matches the input frame, and corresponds to the obtained matching entry. A search processing unit that outputs search results as processing information indicating the contents of frame processing to be performed on the input frame,
  The search processing unit
  For each entry, first entry information including a part of the search condition corresponding to the entry is stored, and a second entry relating to second entry information including a part other than the first entry information in the search condition A first search table for storing a number in addition to the first entry information;
  A second search table for storing the second entry information for each entry;
  A comparison circuit that determines, for each entry, whether the entry is a matching entry that matches the input frame by comparing the first entry information and the second entry information with the frame information;
  The first entry information of each entry is read cyclically from the first search table, the second entry number added to the first entry information is separated, and the second entry number is separated. A first readout circuit for outputting entry information to the comparison circuit;
  Based on the second entry number separated by the first read circuit, a second read signal is generated to instruct reading of second entry information from an entry corresponding to the second entry number, and the second read number is generated. A second readout circuit for outputting a signal to the second search table;
  When comparing the first entry information and the second entry information of the entry with the frame information, the comparison circuit first compares the first entry information output from the first readout circuit with the first entry information and the second entry information. It is determined whether or not the first entry information is compatible with the frame information, and the first determination result obtained by the determination is used as a read determination result indicating whether or not the second entry information needs to be read to the second reading circuit. If the first conformity determination result indicates conformity, the second entry information is compared with the frame information to determine whether the second entry information conforms to the frame information; When the second conformity determination result obtained by the determination indicates conformity, the entry number of the entry, a part of the first entry information, or the second entry Some information is output as the search result corresponding to the fit entry,
  The second read circuit reads the second entry information from the second search table when the read determination result output from the comparison circuit indicates that there is a read, and the read determination result is read. When indicating none, the second entry information is not read from the second search table.
  A frame search processing device characterized by that.   A frame information extraction unit for extracting frame information for specifying frame processing to be performed on the input frame from the input frame;
  The frame information extracted by the frame information extraction unit is sequentially compared with search conditions registered in advance for each entry to search for a matching entry that matches the input frame, and corresponds to the obtained matching entry. A search processing unit that outputs search results as processing information indicating the contents of frame processing to be performed on the input frame,
  The search processing unit
  For each entry, a first search table that stores first entry information comprising a part of the search condition corresponding to the entry;
  A second search table that stores, for each entry, second entry information consisting of portions other than the first entry information in the search conditions corresponding to the entry;
  A comparison circuit that determines, for each entry, whether the entry is a matching entry that matches the input frame by comparing the first entry information and the second entry information with the frame information;
  A first read circuit that cyclically reads a plurality of the first entry information from each entry and outputs a first read signal for distributing the first entry information to the comparison circuits to the first search table;
  A second read circuit for outputting a second read signal for cyclically reading the second entry information from each entry and outputting it to the comparison circuit to the second search table;
  When comparing the first entry information and the second entry information of the entry with the frame information, the comparison circuit first compares the first entry information distributed from the first search table with the frame information. Thus, it is determined whether or not the first entry information is compatible with the frame information, and the first conformity determination result obtained by the determination is used as a read determination result indicating whether or not the second entry information needs to be read. 2 When output to the reading circuit and the first conformity determination result indicates conformity, whether the second entry information conforms to the frame information by comparing the second entry information with the frame information. If the second conformity determination result obtained by the determination indicates conformity, the entry number of the entry, a part of the first entry information Or outputs a portion of the second entry information, as the search result corresponding to the fit entry,
  The second read circuit outputs the second entry information corresponding to the first entry information obtained from the read determination result for the read determination result indicating that there is a read out of the read determination results output from the comparison circuit. The second entry number shown is sequentially accumulated in a queue, and the second entry information is instructed to be read from the entry corresponding to the second entry number based on the second entry number read sequentially from the queue A second read signal is generated, and the second read signal is output to the second search table. When the read determination result indicates no read, the second entry information is read from the second search table. Do not
  A frame search processing device characterized by that. In the frame search processing device according to any one of claims 1 to 3 ,
A plurality of the comparison circuits are provided, and frame information distribution for distributing the frame information obtained by the frame information extraction unit to any one of the comparison circuits other than the comparison circuit for which the matching entry is being searched for. A frame search processing device further comprising a branch circuit.   The frame search processing device according to claim 2,
  When reading the first entry information, the first reading circuit cyclically reads the first entry information from each entry in parallel and distributes the first entry information to the comparison circuits. To the first search table,
  The comparison circuit compares the first entry information distributed from the first search table with the frame information when comparing the first entry information of the entry with the frame information. It is determined whether or not the information is compatible with the frame information, and a first conformity determination result obtained by the determination is output to the second reading circuit as a read determination result indicating whether the second entry information is to be read,
  The second read circuit outputs the second entry information corresponding to the first entry information obtained from the read determination result for the read determination result indicating that there is a read out of the read determination results output from the comparison circuit. The second entry number shown is sequentially accumulated in a queue, and the second entry information is instructed to be read from the entry corresponding to the second entry number based on the second entry number read sequentially from the queue Generate a second read signal and output the second read signal to the second search table
  A frame search processing device characterized by that. A frame information extraction step for extracting, from the input frame, frame information for identifying frame processing to be executed by the frame information extraction unit for the input frame;
A search processing unit searches the matching entry that matches the input frame by sequentially comparing the frame information extracted in the frame information extraction step with a search condition registered in advance for each entry. A search processing step for outputting a search result corresponding to the matching entry as processing information indicating the content of the frame processing to be performed on the input frame,
The search processing step includes:
A first search table storing, for each entry, first entry information including a part of the search condition corresponding to the entry;
A second search table storing, for each entry, second entry information including a portion other than the first entry information in the search condition corresponding to the entry;
A comparison circuit compares, for each entry, the first entry information read from the first search table and the second entry information read from the second search table with the frame information. A comparison step for determining whether the entry is a matching entry that matches the input frame;
A first reading step in which a first reading circuit outputs, to the first search table, a first reading signal for cyclically reading the first entry information from each entry and outputting it to the comparison circuit;
A second reading step in which the second reading circuit outputs a second reading signal for cyclically reading the second entry information from each entry and outputting the information to the comparison circuit to the second search table; ,
In the comparing step, when the first entry information and the second entry information of the entry are compared with the frame information, the first entry information is first compared with the frame information so that the first entry information is wherein determining whether to comply with the frame information, and outputs to the second readout circuit a first adaptation determination result obtained by the determination as read judgment result indicating reading necessity of the second entry information, the first If the result of the conformity determination indicates conformity, the second entry information is compared with the frame information to determine whether the second entry information is compatible with the frame information, and is obtained by the determination. If the second conformity determination result indicates conformity, the entry number of the entry, a part of the first entry information, or the second entry information The section is output as the search result corresponding to the fit entry,
The second reading step reads the second entry information from the second search table when the read determination result output from the comparison circuit indicates that there is a read, and the read determination result is read A frame search processing method characterized by not reading the second entry information from the second search table when indicating no.   A frame information extraction step for extracting, from the input frame, frame information for identifying frame processing to be executed by the frame information extraction unit for the input frame;
  The search processing unit searches for a matching entry that matches the input frame by sequentially comparing the frame information extracted by the frame information extraction unit with a search condition registered in advance for each entry. A search processing step for outputting a search result corresponding to the matching entry as processing information indicating the content of the frame processing to be performed on the input frame,
  The search processing step includes:
  The first search table stores, for each entry, first entry information including a part of the search condition corresponding to the entry, and a second search element including a part other than the first entry information. Adding a second entry number related to the entry information to the first entry information and storing the second entry number;
  A second search table storing the second entry information for each entry;
  A comparison step in which a comparison circuit determines, for each entry, whether the entry is a matching entry that matches the input frame by comparing the first entry information and the second entry information with the frame information. When,
  The first reading circuit cyclically reads the first entry information of each entry from the first search table, separates the second entry number added to the first entry information, and the second entry A first reading step of outputting first entry information with separated numbers to the comparison circuit;
  Based on the second entry number separated by the first read circuit, the second read circuit generates a second read signal instructing reading of the second entry information from the entry corresponding to the second entry number And a second reading step for outputting the second reading signal to the second search table,
  In the comparison step, when comparing the first entry information and the second entry information of the entry with the frame information, the comparison step first compares the first entry information output from the first readout circuit with the first entry information. It is determined whether or not the first entry information is compatible with the frame information, and the first determination result obtained by the determination is used as a read determination result indicating whether or not the second entry information needs to be read to the second reading circuit. If the first conformity determination result indicates conformity, the second entry information is compared with the frame information to determine whether the second entry information conforms to the frame information; When the second conformity determination result obtained by the determination indicates conformity, the entry number of the entry, a part of the first entry information, or the second entry Some birds information, and output as the search result corresponding to the fit entry,
  The second reading step reads the second entry information from the second search table when the read determination result output from the comparison circuit indicates that there is a read, and the read determination result is read When indicating none, the second entry information is not read from the second search table.
  A frame search processing method characterized by the above.   A frame information extraction step for extracting, from the input frame, frame information for identifying frame processing to be executed by the frame information extraction unit for the input frame;
  The search processing unit searches for a matching entry that matches the input frame by sequentially comparing the frame information extracted by the frame information extraction unit with a search condition registered in advance for each entry. A search processing step for outputting a search result corresponding to the matching entry as processing information indicating the content of the frame processing to be performed on the input frame,
  The search processing step includes:
  A first search table storing, for each entry, first entry information including a part of the search condition corresponding to the entry;
  A second search table storing, for each entry, second entry information including a portion other than the first entry information in the search condition corresponding to the entry;
  A comparison step in which a comparison circuit determines, for each entry, whether the entry is a matching entry that matches the input frame by comparing the first entry information and the second entry information with the frame information. When,
  A first read circuit cyclically reads a plurality of the first entry information from each entry in parallel and outputs a first read signal for distribution to each comparison circuit to the first search table. One reading step;
  A second reading step in which the second reading circuit outputs a second reading signal for cyclically reading the second entry information from each entry and outputting the information to the comparison circuit to the second search table; ,
  The comparing step compares the first entry information distributed from the first search table with the frame information when comparing the first entry information and the second entry information of the entry with the frame information. Thus, it is determined whether or not the first entry information is compatible with the frame information, and the first conformity determination result obtained by the determination is used as a read determination result indicating whether or not the second entry information needs to be read. 2 When output to the reading circuit and the first conformity determination result indicates conformity, whether the second entry information conforms to the frame information by comparing the second entry information with the frame information. If the second conformity determination result obtained by the determination indicates conformity, the entry number of the entry, the first entry information Part or a portion of the second entry information, and output as the search result corresponding to the fit entry,
  In the second reading step, the second entry information corresponding to the first entry information from which the read determination result is obtained for the read determination result indicating that there is a read out of the read determination results output from the comparison circuit. The second entry number shown is sequentially accumulated in a queue, and the second entry information is instructed to be read from the entry corresponding to the second entry number based on the second entry number read sequentially from the queue A second read signal is generated, and the second read signal is output to the second search table. When the read determination result indicates no read, the second entry information is read from the second search table. Do not
  A frame search processing method characterized by the above.

Images