JPH0832613A - Route selection information retrieval device - Google Patents

Abstract

(57) [Summary] [Purpose] Even when a plurality of network numbers are assigned to one network, the corresponding route selection information is searched from all the network numbers by using the hash method. In a route selection information search device that searches for predetermined route selection information from the route selection information stored in the route selection information table 11 by a hash method,
In addition to the route selection information table 11 including the first network number of the assigned network numbers as the selection key information, the route including the network number other than the first network number and the first network number as the search key information. The search means 13 uses the selection information search table 12 to perform a two-step hash search.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a retrieval device for retrieving route selection information for data transfer between a plurality of connected networks.

[0002]

2. Description of the Related Art Conventionally, this type of search device has been provided in a router that connects a plurality of networks. The search device has route selection information including the address of the router to be transferred next, the number of hops, etc. for each routable network, and the destination network of the data is selected from all of this route selection information. Was looking for route information to and sending the data to the appropriate network. At this time, the search device uses the hash method,
The individual route selection information is linked to the hash value of the hash table using the network number of the network as a key. Then, when searching the route selection information for a certain network, only the information having the same hash value is searched, so that it is not necessary to search all the information, and the search can be performed in a short time. In the above search device, when one network number is assigned to one network, the route selection information can be easily managed and searched by the above method.

[0003]

In some of the above routers, the range of the number of nodes that can be connected to one network number is specified. In such a case, the connection to one network is possible. When connecting more than a certain number of nodes, it may be possible to allocate a plurality of network numbers to one network to increase the number of connectable nodes.

In such a case, however, if the search device is used to set the route selection information for each network number, if the range of assigned network numbers is wide, many corresponding numbers will be available. There is a problem that the storage capacity becomes large because it must have the route selection information. In addition, since the addition / deletion of information to / from a certain network must be performed for each network number assigned to that network, there is a problem in that efficiency is deteriorated. Furthermore, if each network has route selection information, only one network number can be used as a hash key. Therefore, in the hash method as described above, other network numbers that are not keys are used. There was a problem that the route selection information could not be found.

The present invention has been made in view of the above problems, and even when a plurality of network numbers are assigned to one network, the route selection information corresponding to all the network numbers is calculated by using the hash method. It is an object of the present invention to provide a search device capable of searching for. Another object of the present invention is to provide a search device capable of easily adding / deleting information to / from a network.

Still another object of the present invention is to provide a search device capable of easily creating route selection information.

[0007]

In order to achieve the above object, in the present invention, route selection information for searching predetermined route selection information from the route selection information stored in the route selection information table by the hash method. When a plurality of network numbers are assigned to one network in the search device, the route selection information table including one network number of the assigned network numbers as the selection key information, and the search key. A route selection information search table including a network number that is not the selection key information and a network number that is the selection key information as information, and a network number to perform route selection as the selection key information. If you search the information table and there is no corresponding route selection information, The work number, routing information search locate the selected key information is in the network number is in table search means a search device equipped with is provided as search key information.

In the third aspect, when the search means cannot search the route selection information corresponding to the network number for which the route is selected, all the route selection information tables can be searched for the corresponding route selection information. In that case, the route selection information search table corresponding to the network number is created, and the created route selection information search table is linked to the corresponding hash value.

[0009]

The above-mentioned search device has a route selection information table and a route selection information retrieval table, and when there is no route selection information corresponding to the network number for route selection in the route selection information table, the route selection information is displayed. Since the network number as the selection key information corresponding to the network number is searched from the search table, the corresponding route selection information can be easily searched. Since there is one route selection information table for one network, addition / deletion of route selection information can be performed easily.

In the third aspect, when the route selection information cannot be searched, the entire route selection information table is searched, and when the route selection information can be searched, the route selection information search table is created and linked to the corresponding hash value. Therefore, with respect to the network number that has been searched once, the network number serving as the selection key can be acquired by searching the route selection information table and the route selection information search table from the next time.

[0011]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the present invention will be described with reference to the drawings of FIGS. FIG. 1 is a configuration diagram showing a schematic configuration of a search device according to the present invention. In the figure, the search device is provided in each router that connects a plurality of networks, as in the conventional example. The search device has a hash structure and also has a route selection information table 11 having route selection information, a hash structure and a route selection information search table 12 having search information, and a network number to be input by a hash method. On the other hand, the search means 13 for searching the route selection information and the search information.

The route selection information table 11 is composed of a route selection information hash table 11a consisting of a plurality of arbitrarily set hash values, and route selection information provided corresponding to each of the hash values. . In this embodiment, the hash value of the route selection information hash table 11a is an arbitrary number from [0], and a plurality of route selection information is provided corresponding to the hash value. Here, for convenience of explanation, the route selection information A1 and A2 corresponding to the hash value [a] and the route selection information A3 and A4 corresponding to the hash value [b] are shown.

That is, in this embodiment, when a plurality of network numbers are assigned to one network, the first network number X1 to
X4, the final network numbers Y1 to Y4, and the routeable information A1 to A4 including the address of the router to be transferred next and the number of hops (not shown) for each routable network, for each network. I have one.

In this embodiment, each route selection information A1
..- A4 are the same as the hash-calculated values with the leading network numbers X1 to X4 as selection key information.
Although linked to the above hash value, the present invention is not limited to this, and for example, the hash value with the most frequently used network number among the network numbers assigned to the network as selection key information is used. It is also possible to link.

The route selection information search table 12 is composed of a route selection information search hash table 12a consisting of a plurality of arbitrarily set hash values, and search information provided corresponding to the hash values. There is.
In this embodiment, the hash value of the route selection information search hash table 12a is an arbitrary number from [0], and a plurality of search information is provided corresponding to the hash value. Here, for convenience of explanation, search information B1 and B2 corresponding to the hash value [aa] and search information B3 and B4 corresponding to the hash value [bb] are shown.

That is, in this embodiment, search information B1 to B4 respectively including network numbers Z1 to Z4 other than the head network numbers X1 to X4 in the range of the network numbers and the head network numbers X1 to X4. To
You have one for each network number that is not at the beginning.
In the present embodiment, the search information B1 to B4 are linked to the hash value that matches the hash-calculated value with the non-leading network numbers Z1 to Z4 as the search key information. The present invention is not limited to this. For example, when a frequently used network number is used as the selection key information, a network number other than the frequently used network number is linked to the hash value as the search key information. It is also possible.

The search means 13 searches for the route selection information linked by the hash value of the route selection information hash table 11a which is hash-calculated using the network number as a key, using the hash search algorithm. The search means 13 searches the route information for the destination network of the data out of the linked route selection information, whereby the router can transmit the data to the appropriate network.

When there is no corresponding route selection information, the search means 13 searches the search information linked by the hash value in the route selection information search hash table 12a. Here, the search means 13 searches the headed network number corresponding to the corresponding network number from the linked search information. And
Hash calculation is performed using the retrieved first network number as selection key information. Then, the search means 13
The route selection information linked with the calculated hash value of the route selection information hash table 11a is searched.

Further, the search means 13 searches the route selection information table when there is no corresponding search information, and when there is the corresponding search information, it becomes a target when searching the route selection information. The routing information search table of the network number that is set is generated. It should be noted that the route selection information search table is generated by the search means 13, and when searching for the same network number once searched, the route selection information search table and the route selection information search table will be used from the next time. It is possible to retrieve and obtain the leading network number that is the route selection key, and there is no need to search the entire route selection information table.

Next, the search operation for searching the route selection information for a certain network number will be described with reference to the drawings of FIGS. FIG. 2 is a diagram showing an example of a system in which a plurality of networks are connected using a router provided with the search device according to the present embodiment. In the figure, a router 20 is connected to each of the networks 1, 2 and 5. The router 21 is connected to the networks 3 and 5, respectively. The router 22 is connected to each of the networks 2 and 6. The router 23 is connected to each of the networks 4, 6 and 7. The router 24 is connected to each of the networks 1 and 8. The router 25 is connected to the networks 6 and 9, respectively. In addition, the router 26 is connected to the network 7, 1.
0 and 0 respectively.

Here, for example, the network 1 is "10".
Network numbers in the range of 01 to 2000, network 2 in the range of 101 to 180, network 3 in the range of 11 to 5.
It is assumed that the network number in the range of “0” and the network 4 in the range of “10001” to “10005”.

In such a state, each router has, for example, a route selection information table 11 having a hash structure as shown in FIG. 3 and a route selection information search table 12 as shown in FIG. That is, in the route selection information table 11, the route selection information A1 includes the first network number “1001” and the last network number “2000” of the network 1, and the route selection information A2 includes the network number 2 of the network 2. The first network number "101" and the last network number "180" are included. The route selection information A1 and A2 are linked to the hash value [a] of the hash-calculated route selection information hash table 11a using the leading network number as the selection key information.

The route selection information A3 includes the first network number "11" and the last network number "50" of the network 3, and the route selection information A4 includes
Network number “1000 at the beginning of network 4
1 ”and the final network number“ 10005 ”are included. The route selection information A3, A4 is linked to the hash value [b] of the hash-calculated route selection information hash table 11a using the leading network number as the selection key information.

In the route selection information search table 12, the search information B1 includes the network number "156" in the number range of the network 2 and the head network number "101", and the search information B2 is included in the search information B2. Is
For example, the network number “10005” in the number range of the network 1 and the leading network number “100”
1 ”is included. The search information B1 and B2 are network numbers "15" other than the network number at the beginning.
6 "and" 10005 "are used as search key information, and the hash value [aa] of the hash calculation route selection information search hash table 12a is linked.

The search information B3 includes, for example, the network number "30" in the number range of the network 3 and the head network number "11".
4 includes, for example, a network number “160” in the number range of the network 4 and a leading network number “1”.
01 ”is included. The search information B3 and B4 are network numbers “3
It is linked to the hash value [bb] of the route selection information search hash table 12a that has been hash-calculated with 0 "and" 160 "as search key information.

In such a state, for example, when searching the route selection information for the network number "1001", since the above "1001" is the head of the range of network numbers, the search means 13 causes the route selection information. By following the link of the hash value [a] in the hash table 11a, the corresponding route selection information A1 can be found.

Also, for example, the network number "160"
When the route selection information is searched for, first, the links of the hash values of the route selection information hash table 11a which are hash-calculated by the network number are traced. But,
Since the network number is not at the beginning of the range of network numbers, the search means 13 cannot find the corresponding route selection information. Therefore, next, the search means 1
3 is the hash value [b of the route selection information search hash table 12a calculated by hashing with the network number.
b], the corresponding search information B4
You can find out. Then, the first network number “10” stored in the search information B4 is stored.
1 ”, the corresponding route selection information A2 can be found by following the link of the hash value [a] of the hash-calculated route selection information hash table 11a.

When the route selection information corresponding to the new network number is searched, that is, when the route selection information table 11 and the route selection information search table 12 are not searched, the route selection information and the route selection information cannot be acquired. In the search means 13, the route selection information table 1
All route selection information stored in 1 is searched in order to find the corresponding one. Next, the search information is linked to the hash value of the route selection information search hash table 12a that is hash-calculated by the searched network number to create the route selection information search table.

As described above, in each router, at first,
Although it does not have the route selection information search table for any network number, once the route selection information is searched, the route selection information search table exists for that network number. Therefore, in this embodiment,
Even when a plurality of consecutive network numbers are assigned to one network, a two-step hash search is performed using the route selection information search table in addition to the route selection information table, so all routable You do not have to manage the route selection information for the network number of the network, you only have to search a part of the search information and route selection information linked to the corresponding hash value,
It is possible to find the corresponding route selection information in a short time.

Further, in this embodiment, since there is one route selection information table for one network, addition / deletion of information for the network can be easily performed. Further, in the present embodiment, the search means creates the route selection information search table corresponding to the network number and links the created route selection information search table to the corresponding hash value, which facilitates the creation of the route selection information. Can be done.

As a result, in the present embodiment, it becomes possible to accurately and easily find the route selection information for the destination network of the data from the route selection information and transmit the data to the appropriate network. Transfer reliability can be improved.

[0032]

As described above, according to the present invention, in the route selection information retrieval device for retrieving predetermined route selection information from the route selection information stored in the route selection information table by the hash method, When a plurality of network numbers are assigned to one network, a route selection information table including one network number of the assigned network numbers as selection key information, and the selection key as search key information. A route selection information search table including a network number that is not information and a network number that is the selection key information, and a network number for performing route selection,
The route selection information table is searched as the selection key information, and if there is no corresponding route selection information, the network number is used as the search key information and the network is the selection key information in the route selection information search table. Since a search means for finding a number is provided, even if a plurality of network numbers are assigned to one network, it is possible to find the corresponding route selection information from all the network numbers by using the hash method. Since there is one route selection information table for one network, it is possible to easily add / delete information for the network.

According to a third aspect of the present invention, the search means, when the route selection information corresponding to the network number for which the route is selected cannot be searched, searches the entire route selection information table and searches for the corresponding route selection information. In this case, the route selection information search table corresponding to the network number is created, and the created route selection information search table is linked to the corresponding hash value, so that the route selection information can be created easily. .

[Brief description of drawings]

FIG. 1 is a configuration diagram showing a schematic configuration of a search device according to the present invention.

FIG. 2 is a diagram showing an example of a system in which a plurality of networks are connected by using a router provided with the search device according to the present embodiment.

FIG. 3 is a diagram showing a specific example of the route selection information table shown in FIG.

FIG. 4 is a diagram showing a specific example of the route selection information search table shown in FIG.

[Explanation of symbols]

11 route selection information table 11a route selection information hash table 12 route selection information search table 12a route selection information search hash table 13 search means A1 to A4 route selection information B1 to B4 search information X1 to X4 first network number Y1 to Y4 final Network number Z1 to Z4 Network numbers other than the first network number

 ─────────────────────────────────────────────────── ─── Continuation of the front page (72) Inventor Shuichi Saito 2-6-1, Marunouchi, Chiyoda-ku, Tokyo Furukawa Electric Co., Ltd.

Claims (3)

[Claims] 1. In a route selection information search device that searches for predetermined route selection information from stored route selection information by a hash method, a plurality of network numbers are assigned to one network. , A route selection information table including one of the assigned network numbers as the selection key information, a network number that is not the selection key information as the search key information, and the selection key information. A search device comprising: a route selection information search table including a network number that is present; and a search unit that searches route selection information for the network from the route selection information table and the route selection information search table. 2. The search means searches the route selection information table by using the network number for route selection as the selection key information, and if there is no corresponding route selection information, searches the network number for the search key. 2. The search device according to claim 1, wherein a route selection information search table is searched as information, and a network number that is the selection key information in the route selection information search table is searched for. 3. If the search means cannot search the route selection information corresponding to the network number for which the route is selected, it searches all of the route selection information tables and can find the corresponding route selection information. 3. The search device according to claim 2, wherein the route selection information search table corresponding to the network number is created, and the created route selection information search table is linked to the corresponding hash value.