JP2003224581A - Longest match search circuit and method, program and recording medium - Google Patents

Abstract

(57) [Summary] [PROBLEMS] To realize a high-speed and economical search method using a large-scale Patricia tree. SOLUTION: The address of a node constituting a Patricia tree, information on a bit position of interest of entry data corresponding to this address, and information on a destination node or a termination point with respect to a possible value of entry data corresponding to this bit position of interest Are recorded using an inexpensive memory such as a RAM, and the destination node or the end point of the entry data is sequentially searched for each node going downstream from the start point of the Patricia tree according to the value of the bit of interest.

Description

Detailed Description of the Invention

[0001]

TECHNICAL FIELD The present invention is used for data retrieval using a Patricia tree. In particular, it is suitable for use in a routing table search system.

[0002]

2. Description of the Related Art FIG. 9 shows the structure of a Patricia tree used in a conventional routing table search system or the like. In the longest match search using a Patricia tree, the longest possible bit match among the numbers of the entry data is searched, and the output port for the next router (NHR) and other priority control are performed under that condition. Those N
Information such as HR is stored in the memory of FIG.

In the example of FIG. 9, if the entry data is, for example, 0001, the contents of # a4 of the memory storing the address information of # a4 is read and output to the 4th port. On the other hand, when the entry data is 0010, the tree is searched in the same manner from the above, the first bit is 0, the second bit is 0, the third bit is 1, the end point is found, and the value # a2 is obtained. NHR is 2.

Conventionally, as an example of implementation of a search method using a Patricia tree, there is one using a CAM (associative memory). As shown in FIG. 11, in the CAM, the higher order (upper address) of the stored data is prioritized, the search is performed from the top, the stop is made at the coincident position, and the content is read.

[0005]

As described above, the search method using the Patricia tree can be realized by the CAM to perform the longest match search described above.
There is a limit to the capacity of, and it cannot be done on a large scale. In addition, since many addresses are searched at the same time in principle, very large power consumption is required and it is expensive, which is not economical.

The present invention has been made against such a background, and is a longest-match search circuit, method, program, and program capable of realizing a search method using a large-scale Patricia tree at high speed and economically. The purpose is to provide a recording medium.

[0007]

The first feature of the present invention is to replace the structure of the Patricia tree with a form that can be recorded in a table using a memory such as a RAM.

That is, the address of the node forming the Patricia tree, the information on the target bit position of the entry data corresponding to this address, and the destination node or terminal point for the possible value of the entry data corresponding to this target bit position. The information is recorded as a Patricia tree connection table. The bit position of interest shifts from the head bit to the lower bit one bit at a time from the start point of the Patricia tree to the downstream side. As a result, even a large-scale Patricia tree can be recorded using an inexpensive memory such as RAM, which is economical.

A second feature of the present invention is a configuration for performing the longest match search using the Patricia tree connection table using a memory such as a RAM. In the present invention,
Since the destination node or end point of the entry data is sequentially searched according to the value of the bit of interest for each node going downstream from the start point of the Patricia tree in the table, if the end point is hit before reaching the end of the tree structure, Since the search can be terminated at that point, the longest match search can be performed at high speed.

That is, a first aspect of the present invention is to obtain an address of a node forming a Patricia tree, information on a target bit position of entry data corresponding to this address, and an entry data corresponding to the target bit position. A Patricia tree connection table in which information about a destination node or an end point for the obtained value is recorded is provided, and the bit position of interest is sequentially shifted from the head bit to the lower bit by one bit for each stage from the start point to the downstream of the Patricia tree. However, the longest match search circuit is provided with means for sequentially searching the destination node or the end point of the entry data according to the value of the bit of interest for each node going downstream from the starting point of the Patricia tree in the table. .

Further, as a structure for increasing the speed, there is provided a plurality of means for retrieving the destination node or the end point of the entry data in parallel for each bit of interest of the node going downstream from the start point of the Patricia tree in the table. The means for searching outputs the search result as the longest match search result of the entry data when the self search result indicates the terminal point, and when the self search result indicates the address of the node of the next stage, the entry data It is also possible to provide a means for handing over to a searching means at a next stage whose position is one lower than itself.

According to this, since the parts corresponding to the respective stages of the Patricia tree are performing the parallel processing, the entry of the next entry data is not continuously waited until the search result of one entry data is obtained. Since a plurality of entry data can be entered, high speed processing can be performed.

As another configuration for increasing the speed, k from the starting point of the Patricia tree in the table to the downstream side
(K is a natural number) First search means for sequentially searching the destination node or terminal point of the entry data according to the value of the bit of interest for each node up to the (k + 1) th stage, and a plurality of subtrees after the (k + 1) th stage in the table. A plurality of second search means for sequentially searching destination nodes or end points of entry data in parallel according to the value of the bit of interest for each node going downstream from the start point of the subtree. And a means for selecting any one of the plurality of search results based on the search result of the first search means as a final longest match search result.

According to this, the Patricia tree is vertically divided from an appropriate place, the upper part performs the longest match search in the upper part, and the lower part executes the longest match search in the lower part. At this time, the upper part starts the search from the starting point of the Patricia tree, so the search result for the entry data is set to one, but the lower part is divided into multiple subtrees and the search is started for each subtree. Therefore, there are a plurality of search results for the entry data. In this way, when the search results for the upper part and the lower part are determined, one of the plurality of search results for the lower part is selected as the final search result based on the search result for the upper part. In this way, one Patricia tree can be split up and down and parallel processing can be performed.
The search time can be shortened.

As another configuration for increasing the speed, k from the starting point of the Patricia tree in the table to the downstream side
A plurality of third search means are provided for searching destination nodes or termination points of a plurality of entry data in parallel according to the value of the bit of interest for each node up to the stage,
For each of a plurality of (k + 1) th and subsequent subtrees in the table, a destination node or an end point of entry data is sequentially searched in parallel for each node from the start point of the subtree to the downstream side according to the value of the bit of interest. A plurality of fourth search means are provided, and the entry data output from the third search means is distributed to the destination node based on the search results of the plurality of third search means or the terminal searched by the third search means. Means for allocating points to the longest match search result output is provided, and the fourth search means sequentially, for each node going downstream from the starting point of the subtree, for the entry data distributed by this allocating means, according to the value of the bit of interest. It is also possible to provide a means for searching the end point.

This is a structure based on the idea that a plurality of entry data are simultaneously processed in parallel by using a plurality of Patricia trees to increase the speed. However, in the present invention, the Patricia trees are moved up and down from an appropriate position. Although it is divided and the upper part prepares a plurality of replicas, the lower part is characterized by keeping the memory amount low by sharing one tree. That is, a plurality of entry data are processed in parallel in a plurality of upper parts, and when each search result is obtained, the entry data is distributed to each destination node in one lower part. At this time, assuming a case where a plurality of entry data are distributed to the same node in the lower part almost at the same time, means for temporarily storing the entry data distributed by the distribution means is provided, and this temporary storage means is When a plurality of entry data are stored in a node, it is desirable to provide a means for entering the stored entry data into the node one by one.

As a result, a plurality of entry data can be processed in parallel with a smaller amount of memory than in the case of preparing a plurality of Patricia trees as a whole, and the longest match search can be performed at high speed.

According to a second aspect of the present invention, when installed in an information processing device, the information processing device has, as a function corresponding to a longest match search circuit, an address of a node forming a Patricia tree and the address of this node. Information on the bit position of interest of the corresponding entry data,
The function corresponding to the Patricia tree connection table in which the information of the destination node or the terminal point for the possible value of the entry data corresponding to the bit position of interest is recorded is realized, and the bit position of interest is located downstream from the start point of the Patricia tree. For each stage going to the lower bit, one bit at a time from the first bit to the lower bit, and for each node going downstream from the start point of the Patricia tree in the table, the destination node or end point of the entry data is sequentially searched according to the value of the bit of interest. It is a program that realizes the function of performing.

Alternatively, a plurality of functions for searching the destination node or the terminal point of the entry data in parallel for each bit of interest of the node going downstream from the starting point of the Patricia tree in the table are realized, and this searching function is When the search result of indicates the end point, the search result is output as the longest match search result of the entry data, and when the search result of itself indicates the address of the node of the next stage, the entry data is set so that the bit position of interest is It is a program that realizes a function to be handed over to a search means in the next lower stage.

Alternatively, a first search function for sequentially searching the destination node or terminal point of the entry data according to the value of the bit of interest for each node from the starting point of the Patricia tree in the table to the k-th stage going downstream, For each of a plurality of (k + 1) th and subsequent subtrees in the table, a destination node or an end point of the entry data is sequentially searched in parallel according to the value of the bit of interest for each node from the starting point of the subtree to the downstream side. And the function of selecting any one of the plurality of search results of the second search function as the final longest-match search result based on the search result of the first search function. It is a program characterized by that.

Alternatively, a plurality of destination data nodes or terminal points of a plurality of entry data are sequentially searched in parallel for each node from the starting point of the Patricia tree in the table to the k-th stage going downstream, according to the value of the bit of interest. The third search function is realized, and for each of a plurality of subtrees from the (k + 1) th stage onward in the table, a destination node or a terminal of the entry data is sequentially added to each node from the start point of the subtree to the downstream side according to the value of the bit of interest. A plurality of fourth search functions for searching points in parallel are realized, and the entry data output from the third search function is distributed to the destination node based on the search results of the plurality of third search functions, or (3) The end points searched by the search function are distributed to the longest match search result output. A function is realized, and as the fourth search function, a function of sequentially searching the end point according to the value of the bit of interest for each node going downstream from the start point of the subtree for the entry data distributed by this distribution function is realized. It is a program characterized by that.

Further, a function of temporarily storing the entry data distributed by the distribution function is realized, and as a function of temporarily storing the plurality of entry data for one node, the accumulated entries are stored. It is desirable to realize the function of entering data one by one into the relevant node.

A third aspect of the present invention is a recording medium readable by the information processing device, in which the program of the present invention is recorded. By recording the program of the present invention on the recording medium of the present invention, the information processing apparatus can install the program of the present invention using this recording medium. Alternatively, the program of the present invention can be installed in the information processing apparatus directly from a server holding the program of the present invention via a network.

As a result, an information processing device such as a computer can realize a longest-match search circuit capable of realizing a search method using a large-scale Patricia tree at high speed and economically.

According to a fourth aspect of the present invention, an address of a node forming a Patricia tree and information on a bit position of interest of entry data corresponding to this address,
The information of the destination node or the terminal point for the possible values of the entry data corresponding to the bit position of interest is recorded as a Patricia tree connection table, and the bit position of interest is sequentially headed for each stage from the start point of the Patricia tree to the downstream side. The longest feature is that the destination node or the end point of the entry data is sequentially searched according to the value of the bit of interest for each node moving from the start point of the Patricia tree in the table to the lower bit one by one to the lower bit. It is a match search method.

Alternatively, the destination node or the terminal point of the entry data is searched in parallel for each bit of interest of the node that goes downstream from the starting point of the Patricia tree in the table, and when the search result indicates the terminal point, The search result is output as the longest match search result of the entry data, and when the search result indicates the address of the node at the next stage, the entry data is subjected to the search one bit lower in the bit position of interest. Is the longest match search method.

Alternatively, the destination node or the terminal point of the entry data is sequentially searched as a first search according to the value of the bit of interest for each node from the starting point of the Patricia tree in the table to the k-th stage downstream. For each of a plurality of subtrees after the (k + 1) th stage in, the destination node or the end point of the entry data is sequentially paralleled as a second search according to the value of the bit of interest for each node from the start point of the subtree to the downstream side. The longest match search method is characterized by searching and selecting one of the plurality of search results of the second search as a final longest match search result based on the search result of the first search. .

Alternatively, for each node from the starting point of the Patricia tree in the table to the k-th stage going downstream, the third search for sequentially searching the destination node or terminal point of the entry data in accordance with the value of the bit of interest is made into a plurality of entries. The data is performed in parallel, and for each of a plurality of subtrees from the (k + 1) th stage in the table, the destination node or the end point of the entry data is sequentially determined according to the value of the bit of interest for each node going downstream from the start point of the subtree. Each of them is searched in parallel as a fourth search, and the entry data output by the third search is distributed to the destination node based on the search result by the third search or the end point searched by the third search is the longest match. Allocate to search result output,
The fourth search is a longest match search method characterized in that, for the entry data sorted by this sorting, the end point is sequentially searched for each node going downstream from the start point of the subtree according to the value of the bit of interest. .

At this time, the entry data sorted by the sorting is temporarily stored, and when a plurality of entry data is stored for one node, the stored entry data is entered into the node one by one. Is desirable.

[0030]

BEST MODE FOR CARRYING OUT THE INVENTION (First Embodiment) A first embodiment of the present invention will be described with reference to FIGS. FIG. 1 is a block diagram of the first embodiment. FIG. 2 is a diagram showing a Patricia tree used in this embodiment. FIG. 3 is a diagram showing a Patricia tree connection table used in this embodiment. FIG. 4 is a flow chart showing the operation of the longest match search circuit of the first embodiment.

In the first embodiment, as shown in FIG. 3, the address (node address) of the node forming the Patricia tree, the information (mask) about the bit position of the entry data corresponding to this address, and this attention. Patricia tree connection table T in which information of destination nodes or termination points for possible values (“0”, “1”) of entry data corresponding to bit positions is recorded
1 is provided in the table unit M shown in FIG. 1, the bit position of interest is sequentially shifted from the start bit of the Patricia tree to the lower bit one bit at a time from the start point to the lower bit of the Patricia tree. The longest match search circuit is provided with a processing unit P that sequentially searches the destination node or the end point of the entry data according to the value of the bit of interest for each node going from the start point to the downstream side.

That is, the longest match search circuit of the first embodiment is composed of a table section M composed of a RAM and a processing section P. Fig. 2 for easier understanding
Enter the node address in the same Patricia tree as the conventional example with a number. The address information table is shown in FIG.
It is common with 0. FIG. 3 shows the contents of the Patricia tree connection table T showing the search data of the Patricia tree of FIG. Further, FIG. 4 is a flowchart showing the operation of the processing unit P.

The operation of the longest match search circuit of the first embodiment will be described with reference to FIGS. The entry data to be searched is masked from the upper bits by the processing unit P,
One data is taken out from the Patricia tree connection table T which is a table of data (connections and results) of the Patricia tree, and when the remaining masked data is "0" or "1", the next tree connection is made. jump. At the end point, the address of the memory storing the address information is called, and the Patricia tree connection table T is further read to read the NHR port. Of course, it is also possible to store this NHR itself at the end point. For example, instead of # a1 in Figure 3, NHR
7 may be stored.

The flowchart of FIG. 4 will be described. The start is node address # 0, which is the branch of the top tree of the Patricia tree (FIG. 2). Since the mask processing is _ ***, it judges "0" or "1" by the first bit data of the entry data, and if it is "0", it is the node address 1, and if it is "1", it is the node address. 2 is the next node address, and it jumps to that address (corresponding to ni).
Alternatively, the data of the address of the node address 2 is read.

The read data is masked again, and based on the data of the second bit, “0”,
If it is "1", jump to the connection data of the next tree.
If the data of "0" or "1" is the end point, #ai, that is, the address of the memory in which NHR is stored is output.

With such a configuration, the stored data of the Patricia tree constituted by the RAM is extremely large in scale and highly expandable. Further, since no CAM is required, it has low power consumption and is economical.

(Second Embodiment) A second embodiment of the present invention will be described with reference to FIG. In the second embodiment, as shown in FIG.
The Patricia tree connection table T is provided with a plurality of processing units P1 to P4 which respectively search in parallel the destination node or the terminal point of the entry data for each bit of interest of the node going downstream from the starting point of the Patricia tree. Is any one of 1 to 4), when its own search result indicates the end point, the search result is output as the longest match search result of the entry data, and when its own search result indicates the address of the node at the next stage, The longest match search circuit is characterized in that the entry data is transferred to the processing unit P (i + 1) at the next stage, which is one bit lower than the self in the bit position of interest. Although illustration of the table unit M is omitted in FIG. 5, the processing units P1 to P4 execute processing by referring to the table unit M.

In the first embodiment, four clocks are required to match one entry data at the longest. On the other hand, in the second embodiment, pipeline processing is performed for each mask bit, 1-bit processing is performed, and if it is necessary to search the result portion R when the end point is hit, further lower bits are searched together with the next node address. Pass the data to the next pipeline. When the data is delivered to the next stage, the next entry data is inserted from the higher order and the pump line processing is performed.

That is, since the parts corresponding to the respective stages of the Patricia tree are performing parallel processing, a plurality of entries are continuously input without waiting for the entry of the next entry data until a search result for one entry data is obtained. Since data can be entered, high speed processing can be performed.

(Third Embodiment) A third embodiment of the present invention will be described with reference to FIGS. 6 and 7. In the third embodiment, as shown in FIGS. 6 and 7, the Patricia tree connection table T
Processing unit P11 that sequentially searches the destination node or terminal point of the entry data according to the value of the bit of interest for each node from the start point of the Patricia tree to the second stage downstream, and the Patricia tree connection table T.
In each of the plurality of subtrees # 1 to # 3 in the third and subsequent stages in the above, the destination node or the end point of the entry data is sequentially determined according to the value of the bit of interest for each node going downstream from the start point of the subtree # 1 to # 3. A plurality of processing units P21, P22, P23 which are searched in parallel,
The result sections R1 to R3 and the result processing section RC are provided for selecting any one of the plurality of search results of P21, P22 and P23 as the final longest match search result based on the search result of the processing section P11. The longest match search circuit is characterized by the fact that Although the table portion M is not shown in FIG. 6, the processing portions P11 and P21 to P23 are not included in the table portion M.
Refer to to execute the process.

In the configuration of FIG. 6, the entry data of the 3rd to 4th bits is searched in advance, and one of the answers of the 3rd to 4th bits is selected from the search results of the 1st to 2nd bits. Alternatively, the processing is terminated with 1 to 2 bits.
The operation will be described with reference to this figure.

For the entry data, the search processing for the first and second bits and the search processing for the third and fourth bits are performed in parallel. At the 3rd to 4th bits, the value of the upper 2 bits is unknown, but the lower 2 bits are used, and in the example, the search is performed in parallel with 3 bits. The result comes out at each of the node addresses 3, 4, and 5, but as the result of the upper 2 bits, the node address 3, 4, or 5 of the node is jumped to, or 2 bits
As a result, the result processing section RC selects an appropriate one. As a result, the pipeline takes only the number of bits and high-speed processing is possible, but higher-speed processing can be performed as compared with the second embodiment.

That is, the Patricia tree is vertically divided from an appropriate position, the upper part performs the longest match search in the upper part, and the lower part executes the longest match search in the lower part. At this time, the upper part starts the search from the starting point of the Patricia tree, so the search result for the entry data is set to one, but the lower part is the plurality of subtrees # 1 to # 3.
Since the search is started for each of the subtrees # 1 to # 3, there are a plurality of search results for the entry data. In this way, when the search results for the upper part and the lower part are determined, one of the plurality of search results for the lower part is selected as the final search result based on the search result for the upper part. In this way, one Patricia tree can be divided into upper and lower parts and parallel processing can be performed, so that the search time can be shortened.

(Fourth Embodiment) A fourth embodiment of the present invention will be described with reference to FIG. The fourth embodiment, as shown in FIG.
A plurality of processing units that sequentially search for destination nodes or end points of a plurality of entry data in parallel according to the value of the bit of interest for each node from the start point of the Patricia tree connection table T to the second stage downstream from the Patricia tree. P31 to P33 are provided, and for each of a plurality of subtrees in the Patricia tree connection table T on the third and subsequent stages, each node going downstream from the starting point of the subtree sequentially has a destination node or terminal of the entry data according to the value of the bit of interest. A plurality of processing units P41 to P43 for respectively searching points in parallel are provided, and the processing unit P31 is based on the search results of the plurality of processing units P31 to P33.
A distribution unit D that distributes the entry data output from P33 to the destination node or distributes the end point searched by the processing units P31 to P33 to the longest match search result output is provided, and the processing units P41 to P43
The longest match search circuit is characterized in that, with respect to the entry data distributed by the distribution unit D, the end point is sequentially searched for each node downstream from the start point of the subtree according to the value of the bit of interest.

Further, waiting sections B1 to B for temporarily storing the entry data sorted by the sorting section D
3 is provided, and when a plurality of entry data is accumulated for one node, the waiting units B1 to B3 enter the accumulated entry data into the node one by one.

In the fourth embodiment, the upper 1 to 2 bits are 3
Process one entry data in parallel at almost the same time. If the result is a 3-4 bit node, the node address is 3,
It is the same as in the third embodiment that there is a case where it becomes either 4, 5 or it ends. Since a plurality of pieces of data compete for the node address 3 and the like, waiting sections B1 to B3 are provided. With such a configuration, three entry data can be processed at the same time, and high speed performance is improved.

In other words, the fourth embodiment is based on the idea that a plurality of entry data are simultaneously processed in parallel by using a plurality of Patricia trees to increase the speed, but in the fourth embodiment, the Patricia tree is used. Is divided into upper and lower parts from an appropriate place, and the upper part prepares a plurality of replicas, but the lower part is characterized by sharing a single tree to keep the memory amount low. That is, a plurality of entry data are processed in parallel in a plurality of upper parts, and when each search result is obtained, the entry data is distributed to each destination node in one lower part. At this time, assuming that a plurality of entry data are distributed to the same node in the lower part almost at the same time, the distribution unit D
Waiting units B1 to B3 for temporarily storing the entry data sorted by the above are provided, and when the plurality of entry data are stored for one node, the waiting units B1 to B3 store the stored entry data Entry to the relevant node one by one.

As a result, a plurality of entry data can be processed in parallel with a smaller amount of memory as compared with the case of preparing the whole of a plurality of Patricia trees, and the longest match search can be performed at high speed.

(Fifth Embodiment) The longest match search circuit of this embodiment can be realized by a computer device as an information processing device. That is, by installing in a computer device,
As a function corresponding to the longest match search circuit of the first embodiment shown in FIG. 1, the address of the node forming the Patricia tree, the information on the bit position of interest of the entry data corresponding to this address, and the bit position of interest A corresponding function of the Patricia tree connection table T in which the information of the destination node or the end point for the possible value of the entry data is recorded is realized, and the bit position of interest is at each stage from the starting point of the Patricia tree to the downstream side. Processing for sequentially shifting from the first bit to lower bits one by one, and sequentially searching for the destination node or terminal point of the entry data according to the value of the bit of interest for each node that goes downstream from the starting point of the Patricia tree in the Patricia tree connection table T A professional who realizes the function corresponding to department P By installing a ram in the computer apparatus may be a circuit corresponding to the computer device to the longest match search circuit of the first embodiment.

Alternatively, when installed in a computer device, the computer device has a function corresponding to the longest match search circuit of the second embodiment shown in FIG. 5 from the starting point of the Patricia tree in the Patricia tree connection table T to the downstream side. A plurality of functions corresponding to the processing units P1 to P4 that respectively search the destination node or the end point of the entry data in parallel for each bit of interest of the node to be realized are realized, and as a function of this search, the own search result determines the end point. When it shows, the search result is output as the longest match search result of the entry data, and when its own search result shows the address of the node of the next stage, the entry data is searched for the next stage whose bit position is one lower than the self. Computer program that realizes the function of delivering to the means By installing, it can be a circuit corresponding to the computer device to the longest match search circuit of a second embodiment.

Alternatively, when installed in a computer device, the computer device has a function corresponding to the longest match search circuit of the third embodiment shown in FIG. 6 from the starting point of the Patricia tree in the Patricia tree connection table T to the downstream side. The processing unit P11 that sequentially searches the destination node or the terminal point of the entry data according to the value of the bit of interest for each node up to the kth stage
And a plurality of subtrees in the Patricia tree connection table T on and after the (k + 1) th stage in the Patricia tree connection table T. A second search function corresponding to the plurality of processing units P21 to P23 for respectively searching the destination node or the termination point in parallel, and a search result of the first search function from the plurality of search results of the second search function. By installing a program for realizing a function corresponding to the result processing section RC that selects any one of them as a final longest-match search result on the computer, the computer can be searched for the longest-match search of the third embodiment. It can be a circuit corresponding to the circuit.

Alternatively, when installed in a computer device, the computer device has a function corresponding to the longest match search circuit of the fourth embodiment shown in FIG. 8 from the start point of the Patricia tree in the Patricia tree connection table T to the downstream side. The first search function corresponding to the plurality of processing units P31 to P33 that sequentially searches the destination node or the end point of the plurality of entry data in parallel according to the value of the bit of interest for each node up to the k-th stage to be realized is realized. , For each of a plurality of (k + 1) th and subsequent subtrees in the Patricia tree connection table T, the destination node or end point of the entry data is sequentially paralleled according to the value of the bit of interest for each node going downstream from the start point of the subtree. To a plurality of processing units P41 to P43 to be searched for To realize a second search function of response,
Based on the search results of the plurality of first search functions, the entry data output from the first search function is distributed to its destination nodes, or the terminal point searched by the first search function is distributed to the longest match search result output. A function corresponding to part D is realized, and as the second search function, for the entry data sorted by this sort function, the end point is sequentially searched for each node going downstream from the start point of the subtree according to the value of the bit of interest. By installing a program for realizing the function described above in a computer device, the computer device can be made a circuit corresponding to the longest match search circuit of the fourth embodiment.

Furthermore, in the fourth embodiment, by installing in the computer device, the waiting unit B1 to temporarily store the entry data sorted by the function corresponding to the sorting unit D in the computer device.
A function corresponding to B3 is realized, and as a function of temporarily storing this, when a plurality of entry data is stored in one node, a function of entering the stored entry data one by one into the node is realized. .

By recording the program of this embodiment on the recording medium of this embodiment, the computer device can install the program of this embodiment using this recording medium. Alternatively, the program of this embodiment can be directly installed in a computer device from a server holding the program of this embodiment via a network.

As a result, the computer apparatus can realize the longest match search circuit that can realize the search method using a large-scale Patricia tree quickly and economically.

[0056]

As described above, according to the present invention,
A search method using a large-scale Patricia tree can be realized at high speed and economically.

[Brief description of drawings]

FIG. 1 is a configuration diagram of a longest match search circuit according to a first embodiment.

FIG. 2 is a diagram showing a Patricia tree used in this embodiment.

FIG. 3 is a diagram showing a Patricia tree connection table used in this embodiment.

FIG. 4 is a flowchart showing the operation of the longest match search circuit of the first embodiment.

FIG. 5 is a configuration diagram of a longest match search circuit according to a second embodiment.

FIG. 6 is a configuration diagram of a longest match search circuit according to a third embodiment.

FIG. 7 is a diagram showing a state in which a Patricia tree is vertically divided.

FIG. 8 is a configuration diagram of a longest match search circuit according to a fourth embodiment.

FIG. 9 is a diagram showing an example of a Patricia tree.

FIG. 10 is a diagram showing an example of an address table.

FIG. 11 is a diagram showing a configuration of a CAM.

[Explanation of symbols]

B1 to B3 Waiting unit D Sorting unit M Table unit T Patricia tree connection table P, P1 to P4, P11, P21 to P23, P31 to P
33, P41 to P43 processing unit R, R1 to R3 result unit RC result processing unit # 1 to # 3 subtree

   ─────────────────────────────────────────────────── ─── Continued front page    (72) Inventor Masaru Katayama             2-3-1, Otemachi, Chiyoda-ku, Tokyo             Inside Telegraph and Telephone Corporation (72) Inventor Masanori Uga             2-3-1, Otemachi, Chiyoda-ku, Tokyo             Inside Telegraph and Telephone Corporation F-term (reference) 5B075 ND02 QM01 QS06 UU01                 5K030 KA05 LB05 LD17

Claims (16)

[Claims] 1. An address of a node forming a Patricia tree, information on a target bit position of entry data corresponding to this address, and a destination node or termination point for a possible value of the entry data corresponding to this target bit position. And a Patricia tree connection table in which information is recorded, and the bit position of interest is sequentially shifted from the start point of the Patricia tree to the lower bit by one bit from the start point to the lower bit, and the start point of the Patricia tree in the table is changed. A longest match search circuit comprising means for sequentially searching a destination node or a terminal point of entry data in accordance with the value of the bit of interest for each node going downstream from. 2. An address of a node forming a Patricia tree, information on a target bit position of entry data corresponding to this address, and a destination node or termination point for a possible value of the entry data corresponding to this target bit position. And a Patricia tree connection table in which information is recorded, and the bit position of interest is sequentially shifted from the start point of the Patricia tree to the lower bit by one bit from the start point to the lower bit, and the start point of the Patricia tree in the table is changed. It is equipped with a plurality of means for searching the destination node or the terminal point of the entry data in parallel for each bit of interest from the node going downstream from the node. When the own search result indicates the terminal point, the search result It is output as the longest match search result of the entry data. When the result of its own search indicates the address of the node of the next stage, the longest feature is that it has means for delivering the entry data to the means for searching the next stage whose bit position of interest is one lower than itself. Match search circuit. 3. An address of a node forming a Patricia tree, information on a target bit position of entry data corresponding to this address, and a destination node or terminal point for a possible value of the entry data corresponding to this target bit position. And a Patricia tree connection table in which information is recorded, and the bit position of interest is sequentially shifted from the start point of the Patricia tree to the lower bit by one bit from the start point to the lower bit, and the start point of the Patricia tree in the table is changed. First search means for sequentially searching the destination node or the end point of the entry data according to the value of the bit of interest for each of the nodes from k to downstream (k is a natural number), and (k + 1) th stage in the table. For each of the following subtrees, start of that subtree A plurality of second search means for sequentially searching destination nodes or terminal points of the entry data in parallel according to the value of the bit of interest for each node going downstream from the point, and a plurality of search results of the second search means. And a means for selecting any one of them as a final longest-match search result based on the search result of the first search means. 4. An address of a node forming a Patricia tree, information on a target bit position of entry data corresponding to this address, and a destination node or terminal point for a possible value of the entry data corresponding to this target bit position. And a Patricia tree connection table in which information is recorded, and the bit position of interest is sequentially shifted from the start point of the Patricia tree to the lower bit by one bit from the start point to the lower bit, and the start point of the Patricia tree in the table is changed. A plurality of third search means for searching the destination node or the terminal point of the plurality of entry data in parallel according to the value of the bit of interest is provided for each of the nodes from the to the downstream to the k-th stage. For each of a plurality of (k + 1) th and subsequent subtrees, A plurality of fourth search means for sequentially searching destination nodes or end points of the entry data in parallel according to the value of the bit of interest is provided for each node from the start point of the subtree to the downstream side, and the plurality of third search means are provided. Means for allocating the entry data output from the third search means to the destination node based on the search result of (3) or allocating the end point searched by the third search means to the longest match search result output, The longest match search is characterized in that the searching means includes means for sequentially searching the end points of the entry data sorted by the sorting means according to the value of the bit of interest for each node going downstream from the starting point of the subtree. circuit. 5. A means for temporarily storing the entry data sorted by the sorting means is provided, and when the plurality of entry data are stored for one node, the stored entries are temporarily stored. The longest match search circuit according to claim 4, further comprising means for entering data into the node one by one. 6. An address of a node forming a Patricia tree and a bit of interest of entry data corresponding to this address, which is installed in the information processing device, has a function corresponding to the longest match search circuit in the information processing device. A function corresponding to a Patricia tree connection table in which information on a position and information on a destination node or a terminal point for a possible value of entry data corresponding to the focused bit position is recorded is realized, and the focused bit position is a Patricia For each stage from the start point of the tree to the downstream, one bit is sequentially shifted to the lower bit from the start bit, and for each node from the start point of the Patricia tree in the table to the downstream side, the destination node of the entry data is sequentially according to the value of the bit of interest. Or the function to search the end point A program characterized by realizing. 7. When installed in an information processing device, the information processing device has, as a function corresponding to a longest match search circuit, an address of a node forming a Patricia tree and a bit of interest of entry data corresponding to this address. A function corresponding to a Patricia tree connection table in which information on a position and information on a destination node or a terminal point for a possible value of entry data corresponding to the focused bit position is recorded is realized, and the focused bit position is a Patricia For each stage from the start point of the tree to the downstream, the first bit is sequentially shifted to the lower bit by one bit, and the destination node or the end point of the entry data is set for each bit of interest of the node from the start point of the Patricia tree to the downstream side in the table. Multiple functions to search in parallel As a function to perform this search, when the self search result indicates the end point, the search result is output as the longest match search result of the entry data, and when the self search result indicates the address of the next node, the A program that realizes a function of delivering data to a search unit at a next stage whose bit position of interest is one lower than itself. 8. When installed in an information processing device, the information processing device has, as a function corresponding to the longest match search circuit, an address of a node forming a Patricia tree and a bit of interest of entry data corresponding to this address. A function corresponding to a Patricia tree connection table in which information on a position and information on a destination node or a terminal point for a possible value of entry data corresponding to the focused bit position is recorded is realized, and the focused bit position is a Patricia For each stage from the start point of the tree to the downstream, one bit is sequentially shifted from the first bit to the lower bit, and for each node from the start point of the Patricia tree in the table to the k-th stage downstream, according to the value of the bit of interest. The destination node or termination point of the entry data A first search function for searching, and for each of a plurality of subtrees from the (k + 1) th stage onward in the table, a destination node or an end of the entry data is sequentially added to each node going downstream from the start point of the subtree according to the value of the bit of interest. A plurality of second search functions for searching points in parallel, and one of the plurality of search results of the second search function based on the search result of the first search function as a final longest match search. A program that realizes the function of selecting as a result. 9. When installed in an information processing device, the information processing device has, as a function corresponding to a longest match search circuit, an address of a node forming a Patricia tree and a bit of interest of entry data corresponding to this address. A function corresponding to a Patricia tree connection table in which information on a position and information on a destination node or a terminal point for a possible value of entry data corresponding to the focused bit position is recorded is realized, and the focused bit position is a Patricia For each stage from the start point of the tree to the downstream, one bit is sequentially shifted from the first bit to the lower bit, and for each node from the start point of the Patricia tree in the table to the k-th stage downstream, according to the value of the bit of interest. Destination node or end of multiple entry data A plurality of third search functions for searching end points in parallel are realized, and for each of a plurality of subtrees from the (k + 1) th stage onward in the table, the value of the bit of interest is sequentially calculated for each node going downstream from the start point of the subtree. According to the above, a plurality of fourth search functions for respectively searching the destination nodes or terminal points of the entry data are realized in parallel, and the entry data output from the third search function based on the search results of the plurality of third search functions. To the destination node or to realize the function of allocating the end point searched by the third search function to the output of the longest match search result, and as the fourth search function, the subtree of the entry data distributed by this distribution function. The value of the bit of interest was set sequentially for each node going downstream from the start point of A program characterized by realizing a function to search termination point I. 10. The function of temporarily storing the entry data distributed by the distribution function is implemented, and when the plurality of entry data is stored for one node as the function of temporarily storing, the stored entries are stored. The program according to claim 9, which realizes a function of entering data one by one into the node. 11. A recording medium readable by the information processing device, in which the program according to claim 6 is recorded. 12. An address of a node forming a Patricia tree, information on a target bit position of entry data corresponding to this address, and a destination node or terminal point for a possible value of the entry data corresponding to this target bit position. Information is recorded as a Patricia tree connection table, and the bit position of interest is shifted from the starting point of the Patricia tree to the lower bit one bit at a time from the starting point of the Patricia tree to the lower bit. A longest-match search method characterized in that the destination node or terminal point of the entry data is sequentially searched according to the value of the bit of interest for each node heading for. 13. An address of a node forming a Patricia tree, information on a target bit position of entry data corresponding to this address, and a destination node or terminal point for a possible value of the entry data corresponding to this target bit position. Information is recorded as a Patricia tree connection table, and the bit position of interest is shifted from the starting point of the Patricia tree to the lower bit one bit at a time from the starting point of the Patricia tree to the lower bit. The destination node or the end point of the entry data is searched in parallel for each bit of interest of the node heading toward the node, and when the search result indicates the end point, the search result is output as the longest match search result for the entry data. , The search result is A longest match search method characterized in that, when indicating a dress, the entry data is subjected to a search whose bit position of interest is one level lower than the search. 14. An address of a node forming a Patricia tree, information on a target bit position of entry data corresponding to this address, and a destination node or terminal point of a possible value of the entry data corresponding to this target bit position. Information is recorded as a Patricia tree connection table, and the bit position of interest is shifted from the starting point of the Patricia tree to the lower bit one bit at a time from the starting point of the Patricia tree to the lower bit. For each node up to the k-th stage toward, the destination node or terminal point of the entry data is sequentially searched as the first search according to the value of the bit of interest, and for each of the plurality of subtrees after the (k + 1) -th stage in the table, From the start of the subtree to the downstream The destination node or terminal point of the entry data is sequentially searched in parallel as a second search for each node according to the value of the bit of interest, and the search result of the first search is selected from the plurality of search results of the second search. A longest-match search method characterized by selecting any one of them as a final longest-match search result based on. 15. An address of a node forming a Patricia tree, information on a target bit position of entry data corresponding to this address, and a destination node or terminal point of a possible value of the entry data corresponding to this target bit position. Information is recorded as a Patricia tree connection table, and the bit position of interest is shifted from the starting point of the Patricia tree to the lower bit one bit at a time from the starting point of the Patricia tree to the lower bit. For each node up to the k-th stage toward the destination, the third search for searching the destination node or terminal point of the entry data is performed in parallel for a plurality of entry data according to the value of the bit of interest, and the (k + 1) -th stage in the table. For each subsequent subtree , A destination node or an end point of the entry data is sequentially searched in parallel as a fourth search according to the value of the bit of interest sequentially for each node from the start point of the subtree to the downstream side, and based on the search result by the third search, The entry data output by the third search is distributed to the destination node, or the terminal point searched by the third search is distributed to the longest match search result output, and in the fourth search, the entry data distributed by this distribution A longest match search method characterized in that the end point is sequentially searched according to the value of the bit of interest for each node going downstream from the start point of the subtree. 16. The entry data sorted by the sorting is temporarily stored, and when a plurality of entry data is stored for one node, the stored entry data is entered into the node one by one. 15. The longest match search method described in 15.