JP2004187201A - Data string search node, data string search method using the same, and data string search processing device - Google Patents

Abstract

[PROBLEMS] To provide a data string search node that can handle discontinuous masks and that can be easily implemented as hardware, and that a data string including an unfixed partial data string can be handled as a search key. A data string search node, a data string search method using the same, and a data string search processing device.
The information storage device includes information for specifying a subsequence of a data string serving as a search key, such as a subsequence of a data string serving as a search key or positional information on the data string serving as a search key. A data string search node (in the search tree unit 11), wherein a branch destination is changed by a comparison result (input data / registered data comparison unit 13) between the data subsequence and a data string given as a search target. ), A data string search method and a data string search processing device using the same.
[Selection diagram] Fig. 1

Description

[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to a data string search node, a data string search method and a data string search processing device using the same, and more particularly, to a predetermined data string such as a specific address in an Ethernet frame, an IP packet, HTTP text header information or the like. The present invention relates to a data string search node enabling a high-speed search for whether or not the data string is included, a data string search method using the same, and a data string search processing device.
[0002]
[Prior art]
In searching for an address of an IP packet or the like, a method using a hash function, a method using a CAM, and a method using a search tree are generally used (see Non-Patent Document 1). The search tree method is often used from the viewpoints of flexibility for the search key length and the like, high speed, and economy. In a method using a search tree, a simple binary tree search method can perform a high-speed search, but requires a great deal of time to add / delete entries in the search tree. Non-Patent Document 2) or similar methods are often used.
[0003]
The PATRICIA tree is a tree in which each node of the tree has two child nodes and location information on a search key, and the node (leaf) closest to the descendant corresponds to the search result. For example, when used for routing an IP packet, a search key is an IP address, and a search result is a set of an IP address and a next route. The position information on the search key of each node in the tree is information on the bit of the IP address corresponding to the node. FIGS. 13 and 14 show an example in which the address is 16 bits for simplification.
[0004]
The search is performed as follows (FIG. 14).
(1) The node on the ancestor side (node 1) is set as a processing node.
(2) The bit corresponding to the position information of the processing node of the given address is read (the second bit in the node 1 and the fourth bit in the node 2).
(3) If the read bit is “0”, the child 1 is set as a processing node, and if the read bit is “1”, the child 2 is set as a processing node.
(4) If the leaf is reached, go to (5), otherwise go to (2).
(5) If the given address matches the address registered in the leaf, return the route information. If they do not match, there is no corresponding entry.
[0005]
For example, “1100110000111001” reaches the leaf of the registered data 2 from the above procedure because the second bit is 1 and the fourth bit is “0”, but is not applicable because all digits of the address do not match.
When a mask is used for an IP address or the like, it is not possible to cope with the above procedure alone, but it is possible to cope with a method of once arriving at the leaf and going back up the tree. If the masks are discontinuous, a procedure is taken to go back up the tree and repeat the search, and in this case, it is called a Radix tree (see Non-Patent Document 3).
[0006]
Various attempts have been made to speed up the above-mentioned PATRICIA tree. In Patent Literature 1, the search processing is speeded up by parallel processing. In Patent Documents 2 and 3, the speed is increased by improving the data structure of a search tree. These techniques are aimed at speeding up the search, and do not attempt to expand the search target, such as handling discontinuous masks.
[0007]
[Non-patent document 1]
"Thorough Explanation of LAN Switching," by Rich Seifert, translated by Akira Mamiya, Nikkei BP, published in 2001, p. 78-88)
[Non-patent document 2]
http: // www. csse. monash. edu. au / ^~ lloyd / tildeAlgDS / Tree / PATRICIA. html
[Non-Patent Document 3]
http: // www. wide. ad. jp / document / reports / pdf1996 / art5. htm
[0008]
[Patent Document 1]
Japanese Patent Application Laid-Open No. 2000-83054 [Patent Document 2]
JP 2000-83056 A [Patent Document 3]
JP 2000-196670 A
[Problems to be solved by the invention]
In address search, if only an IP address is intended, it is sufficient to be able to deal with continuous masks. However, in order to deal with layers 2 to 7 of the OSI reference model, it is essential to deal with discontinuous masks. is there. Therefore, a simple PATRICIA tree is not suitable, and a Radix tree is used. However, since the Radix tree includes the procedure of retracing the tree and re-searching as described above, there is a problem that the search is troublesome and it is difficult to implement hardware.
[0010]
In addition to the above, when applied to layer 7 (application layer), there is a problem that the position of a data string serving as a search key is undefined. For example, in the HTTP text, the format and name of each HTTP header are specified, but the presence / absence, order, and data length are not normally specified. It is difficult to handle such a partial search key whose position is unfixed by the conventional tree-type search.
[0011]
The present invention has been made in view of the above circumstances, and an object of the present invention is to solve the above-described problems in the conventional technology, to be able to cope with discontinuous masks, and to easily implement a hard mask. It is an object of the present invention to provide a data string search node that can be implemented as hardware, a data string search method using the same, and a data string search processing device.
[0012]
Further, another object of the present invention is to provide a data string search node capable of handling a data string including an indeterminate partial data string as a search key, a data string search method using the same, and a data string search processing device. It is in.
[0013]
[Means for Solving the Problems]
In order to achieve the above object, a data string search node according to the present invention includes a substring of a data string serving as a search key, or a substring of a data string serving as a search key, such as position information on the data string serving as a search key. And a branch destination is changed according to a result of comparison between the data subsequence and a data sequence given as a search target.
[0014]
Further, the other data string search node according to the present invention sets one of the branch destinations as an ancestor node on a search tree including its own node, and shifts a search position when branching to this ancestor node. A data string including a partial data string whose position is not fixed can be handled as a search key.
[0015]
Further, a data string search method according to the present invention is a data string search method using any one of the above-described data string search nodes, wherein the search tree or the tree is modified by combining the data string search nodes in multiple stages. By using the search key, it is possible to handle a search key having a discontinuous mask and a search key whose search position on the data string is not determined.
[0016]
Further, another data string search method according to the present invention has, in addition to any of the above-described data string search nodes, position information on a data string given as a search target and branches based on a bit value of the position. By using a node whose destination is changed and combining them in multiple stages, in handling a search key having a discontinuous mask and a search key whose search position on a data string is not fixed, a plurality of candidates are associated with a mask portion. It is characterized by being able to do.
[0017]
Further, a data string search processing device according to the present invention is a data string search processing device using any of the above-described data string search nodes, and uses a search tree or a modification of the tree having the data string search node. A search tree section, a registration data section that outputs registration data specified by the search tree section, and a data comparison section that compares input data with registration data output from the registration data section. And
[0018]
More specifically, the present invention has solved the problem by adopting, for example, a system configuration as shown in FIG. In FIG. 1, reference numeral 10 denotes a search engine. Reference numeral 11 denotes a search tree unit, which includes a node for deriving a feature of the present invention described later, and a conventionally used node (for example, a node of the PATRICIA tree). Is used.
[0019]
Reference numeral 12 denotes a registration data section, in which registration data for a search result by a search key is stored. Reference numeral 13 denotes an input data / registered data comparison unit, which compares the two and outputs a search result such as a next route.
Since the search tree in the present invention can have a complicated configuration, a search tree data generation unit 14 is provided to indicate a change in the search tree when adding / deleting registration data.
[0020]
As described above, in the present invention, the mask processing node shown in FIG. 2 is used in addition to the normal PATRICIA tree node shown in FIG.
The node of the normal PATRICIA tree shown in FIG. 13 has two child nodes and position information on a search key as information of each node. When the node becomes a processing target, the bit value at the position corresponding to the position information is read from the data string to be searched, and if "0", the child node 1; if "1", the child node 2 Branch.
[0021]
On the other hand, the mask processing node used in the present invention shown in FIG. 2 has two child nodes, information (for example, a start position and an end position) specifying a section on a search key, and is registered as a search key. A data string or information on its storage location is stored in each node. If the node is to be processed, the data string registered in the registered section is compared with the data string to be searched, and if they match, the child node 1 is used; if not, the child node is used. Branch to 2.
[0022]
FIG. 3 shows a configuration example of a search tree in the case of searching for a data string including a mask.
FIG. 4 shows a case where a mask processing node is used for processing a partial search key whose position is unfixed. If the data string does not match, the process returns to the ancestor node, and the search position is shifted to perform the search again.
FIG. 5 shows an example of the configuration of a search tree that handles an indeterminate partial search key. (When processing an indeterminate partial search key, it includes a branch to an ancestor node. It is no longer a "tree" structure).
[0023]
[Action]
When, for example, a data string of “0110111110111001” is added to the search tree of FIG. 3, the search is performed as follows.
Start the search from the node at the most ancestral side of the tree (node 1: this node is a node of a regular PATRICIA tree). Since the third bit of the data string to be searched is “1”, the process proceeds to the node 2 on the child node 2 side.
[0024]
Since node 2 is a mask processing node, “11111”, which is the fifth to ninth bits of the data string to be searched, is compared with “10010”, which is the fifth to ninth bits of the search key of the registered data 2 registered in the node. I do.
-As a result of the comparison, since they do not match, the procedure proceeds to the child node 2 side, and the registration data 3 is obtained.
Compare the search target data string with the unmasked portion of the search key of the registered data 3.
-As a result of the comparison, they match, so the route-C is obtained as a search result.
[0025]
The search key with the mask is searched by the above procedure. In the node 2, if the masked portion matches the search key of the registered data 2, the process branches to the registered data 2. Therefore, if there is a masked search key and a non-masked search key, the unmasked search key It can be seen that priority is given to
[0026]
When data of, for example, “01100000100101001” is added to the search tree of FIG. 5, the search is performed as follows.
Start the search from the node at the most ancestral side of the tree (node 1: this node is a node of a regular PATRICIA tree). Since the third bit of the data string to be searched is “1”, the process proceeds to the node 2 on the child node 2 side.
[0027]
Since node 2 is a mask processing node, “00010”, which is the fifth to ninth bits of the data string to be searched, and “10010”, which is the fifth to ninth bits of the search key of the registered data 2 registered in the node, Compare.
Since there is no match, the search position is shifted by a predetermined number of bits (in this example, 1 bit; in most cases, 1 byte), and the process proceeds to the ancestor node side (in this example, node 2 which is the own node).
[0028]
Compare "00100" which is the sixth to tenth bits of the search target data string with "10010" which is the fifth to ninth bits of the search key of the registered data 2 registered in the node. Since they do not match, the process proceeds to the own node with a further shift by one bit.
...
Compare “10010”, which is the 8th to 12th bits of the search target data string, and “10010”, which is the 5th to 9th bits of the search key of the registered data 2 registered in the node. Since they match, the process proceeds to the child node side, and registration data 2 is obtained.
[0029]
The data string to be searched is compared with the search key of the registered data 2 up to (between the first and fourth bits) up to the position-unfixed part search key. In addition, the position after the indeterminate position search key is compared in consideration of the position shift (13th bit and after and 10th bit and after).
-Since they match, route-B is obtained as a search result.
As described above, the search including the partial search key whose position is unfixed is performed. If the search position is shifted and the end of the data string is reached, the search is terminated as a search failure.
[0030]
BEST MODE FOR CARRYING OUT THE INVENTION
The configuration and operation example of the search tree when the present invention is used will be described below. In the following example, route data is returned as a search result. However, this is not limited to actual use, and data according to the application may be returned.
[0031]
[Example 1]: Example of a case where a plurality of search keys correspond to a mask portion A configuration of a search tree when a plurality of search keys correspond to a mask portion is shown in FIG.
Here, for example, when a data string of “0110111110111001” is added, the sixth bit is “1”, so that the process proceeds from node 1 to node 3. In the node 3, since the fifth to ninth bits do not match the search key of the registered data 3, the registered data 3 is the result of the processing by the search tree. When the given character string and the search tree of the registered data 3 are compared in consideration of the mask, they match, so that the route-C is returned as the search result.
This example corresponds to, for example, a case where a plurality of IP addresses and a default route when they do not match are set.
[0032]
[Second Embodiment]: Example of Having a Plurality of Unfixed Partial Search Keys FIG. 7 shows a configuration of a search tree having a plurality of unfixed partial search keys. Here, for example, when a data string of “011001101001111001” is added, first,
-After looking at the 6th bit at node 1, go to node 3 because it is "1".-Compare the 5th to 9th bits with the search key of registration data 2, and because they do not match, shift the search position by 1 bit (in this example) to node 1 Return ・ Because the 7th bit is '1', proceed to node 3
Since the 6th to 10th bits of the given data string match the 5th to 9th bits of the search key of the registered data 2, the registered data 2 is the result of processing by the search tree.
-The first to fifth bits of the given data are compared with the first to fifth bits of the search key of the registered data 2, and the 11th and 17th bits and the 10th to 16th bits, and since they match, the route-B is returned as the search result. .
It becomes.
This example corresponds to a case where a plurality of HTTP headers are searched, for example.
[0034]
[Embodiment 3]: Example of non-continuous mask FIG. 8 shows the configuration of a search tree in the case of non-continuous mask.
In the node 3, processing is performed when the fifth to ninth bits of the given data string do not match the search key of the registered data 1. When there is no other search key whose mask portion of the search key is not masked as in the node 3, the search key is not made to correspond to the mask processing node and the branch is always made to the child node 2 side. Further, since the node 3 has no meaning in the search processing, it can be omitted.
[0035]
For example, when a data string of “0110110100111101” is added to this tree,
-Looking at the fifth to ninth bits at the node 1 and matching, proceed to the node 2.
When the node 2 looks at the 12th to 14th bits and does not match, the registered data 2 is the result of processing by the search tree.
Compare the given data with the search key of the registered data 2 and return the route-B as the search result because they match.
This example corresponds to a case in which, for example, only the originating address and the destination port number are specified in the IP header, and the subsequent part is masked.
[0036]
[Embodiment 4]: Example when masks overlap FIG. 9 shows the configuration of a search tree when masks overlap. In the present embodiment, the masks of the fifth to ninth bits of the search keys of the registration data 2 and the registration data 3 overlap.
For example, when a data string of “0110110100111101” is added to this tree,
-Looking at the fifth to ninth bits at the node 1, they do not match and proceed to the node 3.
[0037]
Look at the 10th to 11th bits at the node 3 and match, so the registered data 2 is the result of processing by the search tree.
Compare the given data with the search key of the registered data 2 and return the route-B as the search result because they match.
This example corresponds to a case in which, for example, an IP address in which all digits are specified, an IP address in which some digits are specified, and a default value in a case where none of them match.
[0038]
[Embodiment 5]: Example in the case of having a discontinuous mask and an indeterminate partial search key The configuration of a search tree in the case of having a discontinuous mask and an indeterminate partial search key is shown in FIG.
This embodiment is a combination of the example of FIG. 9 and the example of FIG. 8, and corresponds to a case where a packet having an Authorization header added to an HTTP header is filtered in HTTP communication between specific IP addresses. The operation is a combination of the fourth and third embodiments. FIG. 10 shows a case where the nodes on the child node 2 side of the node 2 and the node 3 are shared to save memory. Another node having the same information as the node 5 is replaced by a child of the node 2. The node 2 operates similarly.
[0039]
[Embodiment 6]: Example when mask covers entire search key FIG. 11 shows a configuration of a search tree when a mask covers the entire search key. Since the mask of the registration data 3 covers the entire search key, if there is no other corresponding registration data, the route-C is always obtained as a search result.
For example, when a data string of “0110101111111111” is added to this tree,
The node 1 looks at the first to eighth bits and matches, so it proceeds to the node 2.
When looking at the 9th to 16th bits at the node 2, they do not match, so the registered data 3 is the result of processing by the search tree.
[0040]
The given data is compared with the search key of the registered data 3 and the route-B is returned as a search result because they match (in this case, the match is always made because the mask covers all digits).
It becomes.
This example corresponds to a case in which, for example, an IP address of a call originating and terminating, an IP address of only a terminating side, and a default value when both do not match.
In the case of this embodiment, since the data string comparison at the mask processing node extends over the entire length of the search key, the comparison of all digits after processing in the search tree can be omitted.
[0041]
[Embodiment 7]: Example in Consideration of Mask Priority In the figure, an example of a tree based on registered data 1 to 5 at the top is shown in FIGS. 12 (a) and 12 (b).
The search tree 1 illustrated in FIG. 12A determines whether the first to ninth bits of the search key match the search target data string, prioritizing the 10th to 16th bits. The search tree 2 shown in FIG.
[0042]
For example, the data string of “01101100101001001” matches both the registered data 1 and the registered data 3. When this data string is added to the tree of FIG. 12, in both of the trees (a) and (b), the operation is performed in the order of node 1 → node 2 → node 6 → node 7. The registered data 1 is the registered data 3 in the search tree 2. As described above, it is possible to set the priority of the mask depending on the arrangement of the nodes.
This example corresponds to a case where, for example, the calling side and called side IP addresses are registered, and one of them is given priority.
[0043]
It should be noted that each of the above embodiments is merely an example of the present invention, and the present invention should not be limited thereto, and may be arbitrarily changed and improved without departing from the gist of the present invention. Needless to say, it is good.
[0044]
【The invention's effect】
As described above in detail, according to the present invention, a remarkable effect that it is possible to perform a high-speed search for a data string including a search key having a non-continuous mask and an unfixed position can be achieved. Things.
[0045]
Further, according to the present invention, a remarkable effect that a data string including a partial data string whose position is unfixed can be handled as a search key is also exerted.
[Brief description of the drawings]
FIG. 1 is a diagram illustrating an outline of a data string search system according to the present invention.
FIG. 2 is a diagram illustrating a mask processing node;
FIG. 3 is a diagram illustrating a configuration example of a search tree when a search for a data string including a mask is performed.
FIG. 4 is a diagram illustrating a case where a mask processing mode is used for processing a partial search key whose position is unfixed.
FIG. 5 is a diagram illustrating a configuration example of a search tree that handles a partial search key whose position is unfixed.
FIG. 6 is a diagram illustrating an example (first embodiment) in which a plurality of search keys correspond to a mask portion.
FIG. 7 is a diagram illustrating an example (second embodiment) in which a plurality of types of partial search keys having undetermined positions are provided.
FIG. 8 is a diagram for explaining an example (Example 3) in the case of a discontinuous mask.
FIG. 9 is a diagram illustrating an example (Example 4) where masks overlap.
FIG. 10 is a diagram illustrating an example (embodiment 5) in which a discontinuous mask and an indeterminate position partial search key are provided.
FIG. 11 is a diagram illustrating an example (sixth embodiment) in which a mask covers the entire search key.
FIG. 12 is a diagram illustrating an example (Embodiment 7) in which the priority order of masks is taken into account.
FIG. 13 is a diagram illustrating nodes of a normal PATRICIA tree.
FIG. 14 is a diagram illustrating an example of a PATRICIA tree.
[Explanation of symbols]
Reference Signs List 10 search engine 11 search tree section 12 registration data section 13 input data / registration data comparison section 14 search tree data generation section

Claims (5)

It has information for specifying a subsequence of a data string serving as a search key, such as a subsequence of a data string serving as a search key or position information on the data string serving as a search key, and is provided as the data subsequence and a search target. A data string search node wherein a branch destination is changed according to a result of comparison with a given data string. One of the branch destinations is an ancestor node on the search tree including its own node, and when branching to this ancestor node, the search position is shifted so that a data string including an unfixed partial data string is used as a search key. A data string search node characterized by being made possible. A data string search method using the data string search node according to claim 1 or 2,
By using a search tree or a modification of the tree in which the data string search nodes are combined in multiple stages, it is possible to handle a search key having a discontinuous mask and a search key whose search position on the data string is not fixed. A data string search method characterized in that: In addition to the data string search node according to claim 1 or 2, a node having position information on a data string given as a search target and changing a branch destination according to a bit value of the position is used.
By combining these in multiple stages, it is possible to associate a plurality of candidates with a mask portion when handling a search key having a discontinuous mask and a search key whose search position on the data string is not fixed. Data string search method. A data string search processing device using the data string search node according to claim 1 or 2,
A search tree having the data string search node or a search tree part using a modification of the tree;
A registration data section for outputting registration data specified by the search tree section;
A data string search processing device comprising: a data comparison unit that compares input data with registration data output from the registration data unit.

Images