JP3570606B2 - Data retrieval apparatus and method - Google Patents

Description

[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to a data search technique, and in particular, to a data search system that handles a large amount of data that needs to delete old data in response to new data, such as address resolution in a communication network. The present invention relates to a data search apparatus and method suitable for efficiently performing a search.
[0002]
[Prior art]
In general, when resolving an IP address on the Internet, for example, a search is made of a table in the own apparatus for data (numerical value) such as a given IP address, and if desired data is registered in the table, The data to be extracted is retrieved, and if the data is not registered, it is executed by inquiring another device to acquire the data.
[0003]
The data obtained from the other device in this way is registered in a temporary table (cache table) and used for subsequent searches. The data registered in the temporary table is deleted after a certain time according to a predetermined standard.
On the other hand, such data may be held semi-permanently in a fixed table. In this case, the table may be realized by a mechanism called a CAM (Contents Association Memory or Content Addressable Memory) or a tree-like data structure. In particular, when the data is a numerical value and a binary integer, a data structure called a Patricia tree may be used.
[0004]
When a one-dimensional data structure is used when constructing a temporary table for such an IP address resolution, data (numerical value) is added or data (numerical value) having the oldest described time is added. Can be deleted at high speed. However, with a one-dimensional data structure, it is difficult to construct a large-scale search table due to poor search efficiency.
[0005]
On the other hand, in a CAM or a tree structure used for a fixed table, it is easy to add data (numerical value) and delete given data (numerical value), and search is efficient. However, it takes a very large amount of processing to perform processing such as searching for and deleting data (numerical value) that meets the condition that the registered time is the oldest. For this reason, it is not realistic to apply a CAM or a tree structure to a temporary table.
[0006]
[Problems to be solved by the invention]
The problem to be solved is that the conventional technology cannot achieve both the efficiency of data search and the efficiency of specific data to be deleted and added.
An object of the present invention is to solve these problems of the prior art, and to efficiently solve a case where a large-scale search table such as resolution of an IP address is required and deletion and addition of elements constituting the search table frequently occur. An object of the present invention is to provide a data search device and a data search method capable of performing data search.
[0007]
[Means for Solving the Problems]
In order to achieve the above object, the data search device and method of the present invention provide a history management table having a one-dimensional data structure in addition to a search table, and data is searched using the history management table. By managing the search history by registering and updating the order, efficient data search can be performed by a combination of both. As a result, a search for a numerical value having a large number of digits, such as resolution of an IP address, can be performed at high speed, and a numerical value or the like can be added to or deleted from a search table at high speed.
[0008]
BEST MODE FOR CARRYING OUT THE INVENTION
Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.
FIG. 1 is a block diagram showing one embodiment of the configuration of the data search device of the present invention according to the present invention, and FIG. 2 is a block diagram showing a configuration example of a network using the data search device in FIG. .
The network shown in FIG. 2 is connected to hosts 21a and 22a in user networks 21 and 22 connected via hubs 21b and 22b to an access network 23 including redirection mechanisms 23a and 24a and concentrators 23b and 24b, and a core network 25d. Of the shell node 25 for efficiently realizing the service, edge nodes (subscriber accommodating nodes) 25a, 25b and A representative forwarder 25c is provided.
[0009]
The packets at the beginning of communication are transferred to the representative forwarder 25c by the edge nodes 25a and 25b, and are transferred to the other party directly (shortcut transfer) using the redirection mechanisms 23a and 24a after the second time. At this time, the transfer management tables of the edge nodes 25a and 25b secure the reachability with a small number of fixed entries, and store cache entries (temporary registration information) for shortcut transfer by the redirection mechanisms 23a and 24a on the host 21a. , 22a.
[0010]
In order to obtain a high throughput in the entire network, it is necessary to enable high-speed transfer of the edge nodes 25a and 25b and to reduce the load on the representative forwarder 25c. For that purpose, the edge nodes 25a and 25b need to have an address table (cache table) of a considerable scale. Further, a dynamic operation is required in order to prevent address distribution to a large number of ENs in advance, change user entries, and delete addresses when not in use.
[0011]
To speed up the search of a large-scale cache table, use of a tree search or a CAM may be considered instead of a normal one-dimensional table search, but aging processing (data rewriting) required for dynamic operation is considered. , Tree search, and CAM alone cannot be performed efficiently.
Therefore, in this example, an efficient aging process is enabled by newly adding an aging process table to a data search device that performs a tree search.
[0012]
That is, a link to a table (history management table) of a one-dimensional data structure for aging processing is provided for each entry in a search table having a tree-like data structure or a CAM configuration, and the history is updated when a new entry is updated. By referring to the management table, efficient aging processing is enabled. Specifically, when a certain entry is hit, the contents of the history management table of the link destination are updated. When the entry needs to be updated, the contents of the history management table are referred to and the oldest one is deleted. At this time, the corresponding contents of the search table are also deleted.
[0013]
Hereinafter, the configuration and operation of the data search device for performing such data search will be described in detail.
The data search device 1 of this example shown in FIG. 1 searches for data corresponding to an IP address, and includes a transmission / reception unit 2, a search unit 3, a search table 4 having a Patricia tree structure, an inquiry unit 5, a table control unit. 6, a history management table 7 having a one-dimensional data structure.
[0014]
When the transmission / reception unit 2 receives the IP address, the retrieval unit 3 retrieves the corresponding data from the retrieval table 4 using the IP address as a key, extracts the data if there is one, and extracts the data via the transmission / reception unit 2 to a predetermined destination. To send to.
When the search based on the IP address is performed in this manner, the search history is registered in the history management table 7 by the table control unit 6. Each time a new search is performed, the table control unit 6 registers the latest search history in the history management table 7 and updates the registration ranking of the registered search histories.
[0015]
When a search based on the IP address does not include the corresponding data in the search table 4, the query unit 5 passes the IP address to another device to obtain the corresponding data. Then, the data acquired in this way from another device is additionally registered in the search table 4 by the table control unit 6 in association with the IP address. At the same time, the table control unit 6 registers the latest search history in the history management table 7 and updates the ordering of other search histories.
[0016]
At this time, if there is no free space in the search table 4 for additionally registering new data, the table control unit 6 searches the history management table 7 to detect the oldest search history, and the oldest search history. Elements constituting a table consisting of a set of history data and an IP address are deleted from the search table 4, and an element consisting of a set of data and an IP address obtained by inquiring of another device is added to the deleted free space. register.
[0017]
As described above, in the data search device 1 of this example, since the search table has a Patricia tree structure, it is easy to add or delete a set of data corresponding to an IP address, and it is possible to efficiently perform a search. Can build a large search table. Further, since the search history is managed using the history management table 7 having a one-dimensional data structure, registration and update of the search history are easy, and data to be deleted can be searched efficiently.
The configuration of the search table 4 and the history management table 7 will be described with reference to FIGS.
[0018]
FIG. 3 is an explanatory diagram showing a configuration example of the search table in FIG. 1, and FIG. 4 is an explanatory diagram showing a configuration example of the history management table in FIG.
In FIG. 3, each element constituting the search table 4 is a numerical value (IP address or the like) to be searched, a pointer indicating the position of the corresponding element on the history management table, data obtained as a search result (or its data). A pointer indicating a storage location), a pointer indicating an upper node adjacent on the tree, and pointers (1, 2) indicating lower nodes (here, two).
[0019]
4, each element constituting the history management table 7 has a numerical value (IP address or the like) to be searched, a pointer indicating the next element in the forward order, and a pointer indicating the next element in the reverse order. The management table 7 is provided with a pointer indicating the oldest element described on the history management table 7 and a pointer indicating the element newly described on the history management table 7.
[0020]
When a numerical value (IP address) to be searched is given to the data search device having the search table 4 and the history management table 7 having such a configuration, any one of the following three cases occurs.
The first case is when there is no corresponding element in the search table and the data capacity of the data search device has a margin. In the second case, there is no corresponding element in the search table and the data search device The third case is when there is a corresponding element in the search table.
[0021]
First, the operation of the first case will be described with reference to FIG.
FIG. 6 is an explanatory diagram showing an example of a search operation in the first case of the data search device in FIG.
As a result of searching the search table based on the received numerical value (IP address), if there is no corresponding element in the search table, an inquiry is made to another device or mechanism, and the corresponding data is received from another device or mechanism as an answer. , Add to search table.
[0022]
At this time, the inquired numerical value is newly registered in the empty area of the history management table as the latest element, and the setting of the forward pointer and the reverse pointer is updated, and the pointer indicating the latest element of the history management table is updated. I do.
The registration of the data obtained as a result of the inquiry and the position on the history management table in the search table is performed in the normal search table operation procedure. The specific operation depends on the means for realizing the search table, and will not be described here.
[0023]
Next, the operation of the second case will be described with reference to FIGS.
FIGS. 7 and 8 are explanatory diagrams showing an example of a search operation in the second case of the data search device in FIG.
As a result of searching the search table based on the received numerical value (IP address), if there is no corresponding element in the search table, first, the numerical value described in the oldest element on the history management table is read from the history management table. Erase, make room, and update the pointer to the oldest element to point to the next oldest element.
[0024]
Then, after deleting the oldest element on the search table corresponding to the oldest element deleted on the history management table, an inquiry is made to another device.
A new element is added to the search table based on a response from the other device to the inquiry, and the history management table is updated. That is, a new element is registered as the latest element in the vacant area, and the pointer indicating the latest element, and the forward pointer and the reverse pointer are updated to point to this element.
[0025]
Next, the operation of the third case will be described with reference to FIG.
FIG. 9 is an explanatory diagram showing a search operation example of the data search device in FIG. 1 in the third case.
Since the element corresponding to the received numerical value (IP address) exists in the search table, the element is searched, and then the history management table is updated. That is, the element on the history management table indicated by the pointer of the searched element is updated as the latest element, the pointer indicating the latest element is updated to point to this element, and the forward pointer and the reverse pointer are set. To update.
[0026]
FIG. 5 is a flowchart showing a processing operation procedure according to the present invention of the data search device in FIG.
If there is a data search request by IP address (step 501), the search table is searched (step 502). If the requested data is present in the search table (step 503), the data is extracted and transmitted according to the procedure described in FIG. 9 (step 504), and the history management table is updated (step 505).
[0027]
If the requested data does not exist in the search table in step 503, it is determined whether or not there is free space in this search table to additionally register new data (step 506). If there is, as in the procedure described with reference to FIG. 6, an inquiry is made to another device (step 507), the corresponding data is obtained (step 508), and additionally registered in the search table (step 509). Thereafter, the processing of steps 504 and 505 is performed.
[0028]
Further, if there is no free space in the search table in step 506, the oldest search history information (element) in the history management table is deleted (step 510) and the correspondence between the search tables is performed according to the procedure described in FIGS. The data (element) to be deleted is deleted (step 511). After that, the processing of steps 507 to 509, 504, and 505 is performed.
[0029]
As described above with reference to FIGS. 1 to 9, in the data search device and method of the present embodiment, a history management table having a one-dimensional data structure is provided in addition to a search table such as a Patricia tree structure. By using this history management table to register, update, and manage the history in which data has been searched, efficient data search can be performed by combining the two.
[0030]
This makes it possible to perform a high-speed search even for a set of numerical values having a large number of digits corresponding to some data, such as IP address resolution, and to add or delete numerical values to the search table. Can be done at high speed. Since a large-scale and high-speed data search device can be configured, the probability that it is necessary to query another device for an IP address when searching for an IP address of a communication network is reduced, and the efficiency of the communication network can be improved. it can.
[0031]
The present invention is not limited to the embodiment described with reference to FIGS. 1 to 9 and can be variously modified without departing from the gist thereof. For example, in this example, the data search based on a numerical value such as an IP address has been described as an example. However, the present invention is not limited to a numerical value such as a data search using characters and can be applied. Although the history management table has a one-dimensional data structure, the history management table may have a tree structure. Further, the search table is not limited to the Patricia tree structure.
[0032]
【The invention's effect】
According to the present invention, it is possible to achieve both efficiency of data search and specific efficiency of data to be deleted and added, and a large-scale search table such as resolution of an IP address is required. Even when elements constituting the table are frequently deleted and added, efficient data search can be performed.
[Brief description of the drawings]
FIG. 1 is a block diagram showing one embodiment of the configuration of the data search device of the present invention according to the present invention.
FIG. 2 is a block diagram illustrating a configuration example of a network using the data search device in FIG. 1;
FIG. 3 is an explanatory diagram illustrating a configuration example of a search table in FIG. 1;
FIG. 4 is an explanatory diagram showing a configuration example of a history management table in FIG. 1;
FIG. 5 is a flowchart illustrating a processing operation procedure according to the present invention of the data search device in FIG. 1;
FIG. 6 is an explanatory diagram showing a search operation example in the first case of the data search device in FIG. 1;
FIG. 7 is an explanatory diagram showing a half part of a search operation example in the second case of the data search device in FIG. 1;
FIG. 8 is an explanatory diagram showing a 2/2 portion of a search operation example in the second case of the data search device in FIG. 1;
FIG. 9 is an explanatory diagram showing a search operation example in a third case of the data search device in FIG. 1;
[Explanation of symbols]
1: data search device, 2: transmission / reception unit, 3: search unit, 4: search table, 5: inquiry unit, 6: table control unit, 7: history management table, 21, 22: user network, 21a, 22a: Host, 21b, 22b: hub, 23: access network, 23a, 24a: redirection mechanism, 23b, 24b: concentrator, 25: shell network, 25a, 25b: edge node (subscriber accommodating node), 25c: representative forwarder 25d: core network, 25e: core node.

Claims (2)

Based on the first data, a search is made for the second data previously assigned to the first data, and the set of the first data and the second data to be searched is not registered in a search table. In this case, in the data search device that obtains by inquiring of another device and additionally registers in the search table,
First means for registering and updating a search history based on the first data using a history management table newly added separately from the search table;
If there is no free area in the search table for additionally registering the first and second data to be searched by inquiring of the other device, the oldest search history is detected by referring to the search history in the history management table. The first and second data sets corresponding to the oldest search history that has been deleted are deleted from the search table, and the first and second data sets searched by inquiring of the other device in the empty area after the deletion are deleted. And second means for additionally registering
Further, the history management table has, in a one-dimensional data structure, an element consisting of the first data and a forward pointer pointing to the next element in the normal order and a reverse pointer pointing to the next element in the reverse order . The table has, in a CAM or tree-like data structure, an element including the first and second data sets and a pointer to an element of the history management table,
The history management table is provided with a first pointer that points to the latest element in the history management table and a second pointer that points to the oldest element.
Said second means, on the basis of the second pointer, the first on the search table corresponding to the oldest element of the history management table, to identify and eliminate a component of a second data,
The first means deletes the oldest element deleted from the search table by the second means from the history management table and the second pointer so as to point to the next oldest element after the oldest element. Is updated, and an element including the first data searched for in the search table or additionally registered in the search table is registered as a new latest element in the history management table, and the second element is referred to as the element. A data search device for updating a first pointer, a forward pointer and a reverse pointer . Based on the first data, a search is made for second data previously associated with the first data, and a set of the first data and the second data to be searched is registered in a search table. If not, a data search method of a data search device that obtains by inquiring of another device and additionally registers in the search table,
The search table has a CAM or tree-like data structure,
Registering and updating a search history based on the first data by using a newly added one-dimensional data structure history management table separately from the search table;
Determining whether there is a free area in the search table for additionally registering the first and second data to be searched by inquiring of the other device;
If there is, the other device is inquired to acquire the second data, perform additional registration in the search table, register the latest search history in the history management table, and sequentially rank the other search histories. Deferring and updating;
If not, the oldest search history in the history management table is detected, the first and second data sets corresponding to the detected oldest search history are deleted from the search table, and then the other device is inquired. Performing
The first and second data obtained by inquiring of the other device are additionally registered in the empty area after the deletion, registered as the latest search history in the history management table, and the order of other search histories is sequentially determined. Deferring and updating the data.

Images