JP4331733B2 - SEARCH PROCESSING DEVICE, SEARCH PROCESSING METHOD, AND SEARCH PROCESSING PROGRAM - Google Patents

Description

  The present invention relates to a search processing device, a search processing method, and a search processing program for searching for a resource record and a delegation destination for a domain name related to a DNS query request using a hash function.

  2. Description of the Related Art Conventionally, there is a DNS system (Domain Name System) that associates a host name (domain name) and an IP address (Internet Protocol Address) in Internet services that are generally used. In such a DNS system, a name space consisting of hierarchical domain names is managed by a plurality of authority servers. The authoritative server that manages the highest level of this namespace is called a root server, and other authoritative servers are delegated the namespace managed directly or indirectly from the root server.

  In such a configuration, when a name resolution query (DNS query) is received, the authoritative server performs a resource record search process (RR search process), and whether the domain name has been delegated to another authoritative server. Delegation destination search processing (NS-RR search processing) for confirmation is performed. If the authority server has been delegated, the authority server returns a resource record indicating NS-RR delegation as a query response.

  More specifically, as shown in FIG. 7, the cache server that has received the name resolution query (QNAME = ns2.sales.ntt.co.jp.) Sent from the DNS client is “ntt.co.jp”. The name resolution query received is sent to the authoritative server A that manages the zone. Upon receiving the name resolution query, the authoritative server A executes resource record search processing and delegation destination search processing, and the “sales.ntt.co.jp.” Zone is delegated to the authority server B in the delegation destination processing. If it is confirmed, NS-RR indicating the authoritative server B is transmitted as a query response to the cache server. After that, the cache server again sends a name resolution query (QNAME = ns2.sales.ntt.co.jp.) To the authoritative server B that manages the “sales.ntt.co.jp.” Zone. The resource record search process and the delegation destination process are executed, and the obtained resource record (Answer = A-RR; 192.168.1.1) is transmitted as a query response to the cache server. Then, the DNS server can perform name resolution of “ns2.sales.ntt.co.jp.” By transmitting the received query response to the DNS client that has transmitted the name resolution query. .

  As described above, when the name resolution query (DNS query) is received, the authoritative server performs the resource record search process and the delegation destination search process, and thus each process needs to be performed efficiently. Therefore, as a technique for efficiently performing processing, a technique that employs a tree as an index of the database in the authority server and a technique that employs a hash table (for example, Patent Document 1) are disclosed.

  For example, in the case of a technique that employs a tree for the index, as shown in FIG. 8, the authority server A that has received the name resolution query (QNAME = ns2.sales.ntt.co.jp.) Is a tree managed by itself. In order to find the delegated domain. Here, first, the ftp1 domain is searched, then the ns1 domain is searched, then the sales domain is searched, the delegation destination (authoritative server B) is found, and the found delegation destination is queried as an official answer. Send a response.

Also, in the case of a technology that uses a hash table for the index, as shown in FIG.
Upon receiving the name resolution query (QNAME = ns2.sales.ntt.co.jp.), The authoritative server A first calculates the hash value of “ns2.sales”, searches the hash table, and formalizes this search result. Candidate for answer (query answer). Next, the hash value of “sales” is calculated to search the hash table, and since the delegation destination (NS-RR) exists in the search result, a query response is transmitted with this NS-RR record as an official answer.

JP 2005-44125 A

  By the way, in the case of the above-described conventional technique that employs a tree for the index, there is a problem that the resource record search process and the delegation destination search process cannot always be efficiently performed and the search process cannot be performed at high speed. In addition, in the case of a technology that uses a hash table, it is necessary to calculate separate hash values for resource record search processing and delegation destination search processing, so the processing is not efficient and cannot be performed at high speed There is.

  This problem will be described in detail. When a tree is used, an NS-RR indicating a delegation destination can be found in the process of searching for a tree in the resource record search process. -RR) No processing is required. However, if the height of the tree is deep, it takes time to search, and it is not always possible to perform processing efficiently.

  Also, in the case of technology that uses a hash table, the hash value is calculated for each domain, and the number of labels (units in which the domain name is separated by “.”) Is shortened to check whether it is delegated or not. However, since it is necessary to search the hash table, it is necessary to calculate the hash value many times, and the processing is not efficient.

  Accordingly, the present invention has been made to solve the above-described problems of the prior art, and in the case of employing an index based on a hash table, search processing for a DNS query request (resource record search processing and delegation destination search processing). It is an object of the present invention to provide a search processing device, a search processing method, and a search processing program that can perform the search at high speed.

In order to solve the above-described problems and achieve the object, the present invention provides a search processing device that searches for a resource record and a delegation destination for a domain name related to a DNS query request using a hash function, and the domain names are sequentially searched from the end. A hash value calculation unit that inputs to the hash function and sequentially calculates a hash value from the end to each label using a hash value up to the label immediately before each label, and the domain calculated by the hash value calculation unit Of the hash values from the end of the name to each label, the resource record search means for searching for the resource record for the domain name using the hash value from the domain name to the beginning, and the hash value calculation means The domain name is hashed from the end of the domain name to each label. Characterized by comprising a transfer destination retrieval means for retrieving the name of the transfer destination, the. The present invention is also a search processing device for searching for a resource record and a delegation destination for a domain name related to a DNS query request by a hash function, wherein the domain name is input to the hash function in order from the end, and A hash value calculation means for sequentially calculating a hash value up to a label by remainder of an intermediate calculation value calculated based on the hash value up to the label immediately before the label and a character in the label; and the hash value calculation Resource record search means for searching for a resource record for the domain name using a hash value from the end of the domain name to each label calculated by means to the beginning of the domain name; and the hash value Hash from the end of the domain name to each label calculated by the calculation means Characterized in that and a transfer destination searching means for searching the delegate of the domain name by using the values.

Further, the present invention is the above invention, wherein the delegation destination search unit has a hash value from the end of the domain name to the label calculated by the hash value calculation unit to a label close to the end. The delegation destination of the domain name is searched in order from the value. Further, according to the present invention, the hash value calculation unit is configured to output the last character and the input label immediately before the last character of the character string constituting the hash value calculation target label. An intermediate calculation value is calculated based on the hash value calculated for the label, and for the character from the head of the last character, the calculation target character and the intermediate calculation value calculated immediately before the character are A new intermediate calculation value is sequentially calculated based on the length field indicating the number of characters of the character string constituting the input label and the first character string constituting the label from which the hash value is to be calculated. A new intermediate calculation value is calculated on the basis of the intermediate calculation value calculated for the character, and the calculated new intermediate calculation value is remaindered by a predetermined constant, thereby allocating the label to be calculated. And calculates the Interview value.

In the above invention, the present invention further includes delegation destination information storage means for preliminarily storing delegation destination information indicating a label including the delegation destination information, wherein the hash value calculation means includes the delegation destination information storage Only the hash value from the delegation destination information stored in the means to the determined label is calculated. In the above invention, the present invention further includes delegation destination information storage means for preliminarily storing delegation destination information indicating a label including the delegation destination information, wherein the hash value calculation means includes the delegation destination information storage If there is a means, refer to the delegation destination information storage means prior to executing the hash value calculation, and only the hash value from the delegation destination information stored in the delegation destination information storage means to the determined label Is calculated.

The present invention further includes, in the above invention, a delegation destination information storage unit that preliminarily stores delegation destination information indicating a label including information indicating the delegation destination, and the delegation destination search unit includes the delegation destination information The delegation destination of the domain name is searched using only the hash value from the delegation destination information stored in the storage means to the determined label. The present invention further includes, in the above invention, a delegation destination information storage unit that preliminarily stores delegation destination information indicating a label including information indicating the delegation destination, and the delegation destination search unit includes the delegation destination information If there is a storage unit, the hash value from the delegation destination information stored in the delegation destination information storage unit to the label determined by referring to the delegation destination information storage unit prior to executing the hash value calculation The delegation destination of the domain name is searched using only.

Further, the present invention provides a search processing method for searching for a resource record and a delegation destination for a domain name related to a DNS query request by using a hash function in the above invention, wherein the domain name is input to the hash function in order from the end. A hash value calculation step of calculating a hash value from the tail to each label in order using a hash value up to the immediately preceding label of each label, and from the end of the domain name calculated by the hash value calculation step Among the hash values up to each label, a resource record search step of searching for a resource record for the domain name using a hash value up to the beginning of the domain name, and the domain name calculated by the hash value calculation step Domain name delegation using the hash value from the end of A transfer destination search step of searching earlier and that it contained characterized. Further, the present invention provides a search processing method for searching for a resource record and a delegation destination for a domain name related to a DNS query request by using a hash function in the above invention, wherein the domain name is input to the hash function in order from the end. Hash value calculation for calculating the hash value from the end to each label by sequentially calculating the intermediate calculation value calculated based on the hash value up to the label immediately before the label and the character in the label And a resource record for searching for a resource record for the domain name using a hash value from the end of the domain name to each label calculated by the hash value calculation step to the beginning of the domain name The domain name calculated by the search step and the hash value calculation step A transfer destination search step of searching the delegate of the domain name by using the hash value from the tail to the label, that it contained characterized.

In addition, the present invention provides a search processing program for causing a computer to execute a method for searching for a resource record and a delegation destination for a domain name related to a DNS query request by a hash function in the above-described invention, wherein the domain name is searched in order from the end. A hash value calculation procedure for inputting to the hash function and calculating a hash value from the tail to each label in order using a hash value up to the immediately preceding label of each label, and the hash value calculation procedure Among the hash values from the end of the domain name to each label, the resource record search procedure for searching for the resource record for the domain name using the hash value from the domain name to the beginning, and the hash value calculation procedure From the end of the calculated domain name to each label Characterized in that to execute a delegate search procedure for searching the delegate of the domain name, to the computer using a Mesh value. In addition, the present invention provides a search processing program for causing a computer to execute a method for searching for a resource record and a delegation destination for a domain name related to a DNS query request by a hash function in the above-described invention, wherein the domain name is searched in order from the end. Input to the hash function, and calculate the hash value from the end to each label in turn by calculating the remainder of the intermediate calculation value calculated based on the hash value up to the label immediately before the label and the character in the label Hash value calculation procedure to be calculated, and among the hash values from the end of the domain name to each label calculated by the hash value calculation procedure, a resource for the domain name using a hash value up to the beginning of the domain name Resource record search procedure for searching records, and the hash value calculator Characterized in that to execute a delegate search procedure for searching the delegate of the domain name from the end of the calculated the domain name with a hash value to each label, to the computer through.

According to the present invention, the domain name is input to the hash function in order from the end, and the hash value from the end to each label is calculated based on the hash value up to the label immediately before the label and the characters in the label The intermediate calculated values are calculated in order, and the resource record is searched for the domain name using the hash value up to the beginning of the domain name, and the domain using the hash value from the end of the domain name to each label Since the name delegation destination is searched, there is no need to calculate the hash value separately for the resource record search process and the delegation destination search process when using an index based on a hash table. Compared with the case where a tree index is used. Even so, search processing for DNS query requests (resource record search processing and delegation destination search) It is possible to carry out the management) to high speed.

Further, according to the present invention, since the domain name delegation destination is searched in order from the hash value from the end of the domain name to each label, from the hash value from the label close to the end, the delegation destination from the head direction of the domain name Compared to the method of searching for the URL, there is a high possibility that the delegation destination will be found earlier, and the search processing for the DNS query request can be performed at higher speed.

In addition, according to the present invention , prior to performing hash value calculation by preliminarily storing delegation destination information (for example, the second label and the fourth label from the end) indicating the label including the delegation destination information. Te, the hash value to the label determined from the transfer destination information (e.g., a hash value from the end to the second label first, a hash value of up to 4 label-th) is calculated. therefore only, until the label does not include the delegation destination information Therefore, it is possible to perform a search process for a DNS query request at a higher speed.

In addition, according to the present invention , prior to performing hash value calculation by preliminarily storing delegation destination information (for example, the second label and the fourth label from the end) indicating the label including the delegation destination information. Te, the hash value to the label determined from the transfer destination information (e.g., a hash value from the end to the second label first, a hash value of up to 4 label-th) so searching the domain name of the delegate using only delegate Therefore, it is not necessary to search for a delegation destination for a hash value up to a label that does not include the above information, and a search process for a DNS query request can be performed at higher speed.

  Exemplary embodiments of a search processing device, a search processing method, and a search processing program according to the present invention will be described below in detail with reference to the accompanying drawings.

  In the following, the outline and features of the search processing device according to the first embodiment, the configuration of the search processing device and the flow of processing will be described, and finally the effects of the first embodiment will be described. The “authority server” appearing in the first embodiment corresponds to the “search processing device” described in the claims.

[Outline and Features of Search Processing Device (Authoritative Server)]
First, the outline and features of the search processing apparatus according to the first embodiment will be described with reference to FIG. FIG. 1 is a DNS system configuration diagram illustrating an overall configuration of a DNS system including a search processing apparatus (authoritative server) according to the first embodiment.

  As shown in the figure, in such a DNS system, a plurality of authoritative servers 30 and a plurality of cache servers 20 are connected via the Internet. A plurality of DNS clients 10 are connected to the cache server 20 via the Internet.

  Under such a configuration, the authoritative server 30 according to the first embodiment outlines searching for a resource record and a delegation destination for a domain name related to a DNS query request by using a hash function. The main feature is that search processing (resource record search processing and delegation destination search processing) can be performed at high speed.

  This main feature will be specifically described. The DNS client 10 transmits a DNS query request to the cache server 20 ((1) in FIG. 1). Then, the cache server 20 transmits the DNS query request to the authority server 30 that manages the domain corresponding to the received DNS query request ((2) in FIG. 1). The authority server 30 calculates a hash value based on the received DNS query request and executes a search process ((3) in FIG. 1). Then, the authority server 30 transmits the search result as a query response to the cache server 20 ((4) in FIG. 1). The cache server 20 transmits the received query response to the DNS client 10 that is the source of the DNS query request ((5) in FIG. 1).

  Here, the search processing by the authority server 30 will be described with an example. When the search request “www.lab.ntt.co.jp.” is received as the DNS query request, the authority server 30 uses the hash value calculation algorithm (hash function) shown in FIG. ntt.co.jp. "is input to the hash function in order from the end, and the hash value from the end to each label is calculated in order using the hash value up to the label immediately before each label. Specifically, as shown in FIG. 4, first, “.jp.” Is input to the hash function to calculate a hash value H (1) ((1) in FIG. 4). Next, the hash value H (2) of “.co.jp.” Is calculated using the calculated H (1) ((2) in FIG. 4). In this way, the hash values H (1) to H (5) of each label of “www.lab.ntt.co.jp.” are calculated using the hash value of the immediately preceding label.

  Further, the authority server 30 calculates “www.lab.ntt.co.jp” from among the hash values (H (1) to H (5)) of each label from the end of the calculated “www.lab.ntt.co.jp.”. The resource record of “www.lab.ntt.co.jp.” is searched using the hash value H (5) up to the head of “co.jp.”. Here, if the resource record is found, the authority server 30 sets the found resource record as a query response candidate.

  Subsequently, the authority server 30 uses the hash value (H (1) to H (5)) of each label from the end of the calculated “www.lab.ntt.co.jp.” to “www.lab.ntt Search for the delegation of ".co.jp." If the delegation destination is found, the authority server 30 transmits the delegation destination to the cache server 20 as a query response. On the other hand, if the delegation destination is not found, the authority server 30 transmits the resource record that has been a response candidate to the cache server 20 as a query response.

  As described above, the authority server 30 according to the first embodiment does not need to separately calculate the hash value in each of the resource record search process and the delegation destination search process when the index by the hash table is adopted. As described above, the search processing (resource record search processing and delegation destination search processing) for the DNS query request can be performed at a higher speed than when the tree index is employed.

[Configuration of search processing device (authoritative server)]
Next, the configuration of the authority server shown in FIG. 1 will be described with reference to FIGS. FIG. 2 is a block diagram showing a configuration of the authority server 30, FIG. 3 is a diagram showing an example of a hash function showing a hash value calculation algorithm, and FIG. 4 is a diagram showing an example of hash value calculation. It is. As shown in FIG. 2, the authority server 30 includes a communication control I / F unit 31, a storage unit 32, and a control unit 33.

  Among these, the communication control I / F unit 31 is a means for controlling communication related to various information exchanged with the cache server 20 or the DNS client 10. Specifically, a DNS query request transmitted from the cache server 20 is received, and a query response is transmitted to the cache server 20 as a transmission source.

  The storage unit 32 is a storage unit (storage unit) that stores data and programs necessary for various processes performed by the control unit 33. Specifically, the storage unit 32 stores the hash value calculated by the control unit 33 in a temporary storage area. Or a resource record for responding to a query request to a zone managed by the authority server unit 30 is stored.

  The control unit 33 is a processing unit that has a control program such as an OS (Operating System), a program that defines various processing procedures, and an internal memory for storing necessary data, and executes various processes using these. Particularly, those closely related to the present invention include a hash value calculation unit 33a, a resource record search unit 33b, and a delegation destination search unit 33c. The hash value calculation unit 33a corresponds to the “hash value calculation unit” described in the claims, and the resource record search unit 33b similarly corresponds to the “resource record search unit” and the delegation destination search unit. 33c corresponds to “delegation destination search means”.

  Among these, the hash value calculation unit 33a uses the hash value calculation algorithm shown in FIG. 3 to input the domain name to the hash function in order from the end, and the hash value from the end to each label is immediately before each label. It is means for calculating in order using the hash value up to the label. Specifically, for example, when calculating the hash value of “www.lab.ntt.co.jp.” (number of labels 5), first, using the hash function H (i) shown in FIG. The hash value H (1) of “.jp.” at the end of “www.lab.ntt.co.jp.” is calculated. Then, the hash value H (2) of “.co.jp.” Is calculated using H (1). In this way, the hash values H (1) to H (5) are calculated in order using the hash values up to the label immediately before each label.

  Then, the resource record search unit 33b uses the hash value from the end of the domain name calculated by the hash value calculation unit 33a to each label to use the hash value from the domain name to the beginning of the domain name. It is a means to search. Specifically, when searching for a resource record of “www.lab.ntt.co.jp.” (number of labels: 5), the hash value H (5) calculated by the hash value calculation unit 33a is used to search the resource record. Search for records.

  The delegation destination search unit 33c is a means for searching for a delegation destination of a domain name using a hash value from the end of the domain name calculated by the hash value calculation unit 33a to each label. Specifically, when searching for the delegation destination of the domain name “www.lab.ntt.co.jp.” (number of labels 5), it was calculated based on “www.lab.ntt.co.jp.” The delegation destination is searched using the hash values H (1) to H (5).

[Search Processing by Search Processing Device (Authoritative Server) (Example 1)]
Next, search processing by the search processing device (authoritative server) will be described with reference to FIG. FIG. 5 is a flowchart showing the flow of search processing.

  As shown in FIG. 5, when the DNS query is received (Yes at Step S501), the authority server 30 sets the number of labels of the search target domain name to X (Step S502) and sets the number of labels of the zone name of the search target domain name to Y. Substitution is performed (step S503). For example, if the search target is “www.lab.ntt.co.jp.” in the “.co.jp.” Zone, the number of labels of the search target domain name is 5, and the number of labels of the zone name. Is 2, so X is 5 and Y is 2.

  Then, the authority server 30 assigns 1 to “i” as a variable for executing the search process (step S504). Subsequently, the authority server 30 calculates the hash value H (i) of the i-th label from the right (end) of the search target domain name and stores it in the temporary storage area (step S505). Then, it is determined whether i and X are equal (step S506). If they are not equal (No in step S506), i is increased by 1 (step S507), and the process returns to step S506.

  For example, first, the hash value H (1) of the first label “.jp.” From the right of “www.lab.ntt.co.jp.” is calculated and stored in the temporary storage area. Since i (1) and X (5) are not equal, i is increased by 1 (where i is 2), and then from the right of “www.lab.ntt.co.jp.” The hash value H (2) of the second label “.co” is calculated and stored in the temporary storage area. In this way, until i becomes equal to i, that is, until i becomes 5, i is incremented by 1 to calculate the hash value H (i) and store it in the temporary storage area. Eventually, hash values from H (1) to H5) are calculated.

  On the other hand, if i and X are equal values (Yes at step S506), the authority server 30 searches the hash table for data corresponding to the hash value H (X) (step S508), and the resource record (RR) is It is determined whether or not it exists (step S509). Specifically, the authority server 30 has the hash values from the end of “www.lab.ntt.co.jp.” to each label, up to the beginning of “www.lab.ntt.co.jp.” Data corresponding to the hash value H (5) is searched from the hash table, and it is determined whether or not a resource record (RR) exists.

  If an RR exists (Yes at step S509), the authority server 30 sets the searched RR as a query answer candidate (step S510). On the other hand, when the RR does not exist, the authority server 30 sets a nonexistent error (NXDOMAIN) as a query answer candidate (step S511).

  Subsequently, the authority server 30 substitutes the value “Y + 1” for the variable “i” (step S512). Then, the authority server 30 searches the hash table for data corresponding to the hash value H (i) (step S513), and determines whether NS-RR (delegation destination) exists (step S514). Subsequently, when NS-RR does not exist (No at Step S514), the authority server 30 determines whether or not the values of i and X are equal (Step S515). On the other hand, when NS-RR exists (Yes at Step S514), the authority server 30 sets the searched NS-RR as a candidate answer (Step S517), and responds with this answer candidate as a query response (Step S518).

  If the values of i and X are not equal (No at Step S515), the authority server 30 increases i by 1 (Step S516) and returns to Step S514 and Step S514. On the other hand, if the values of i and X are equal (Yes at Step S515), the authority server 30 responds with the stored answer candidate (Step S517).

  For example, the authority server 30 sequentially calculates the hash value from the end of the calculated “www.lab.ntt.co.jp.” to each label, starting from the hash value up to the label near the end. Since the delegation destination of “www.lab.ntt.co.jp.” is searched, the authority server 30 substitutes “3” as “Y (2) +1” for the variable “i”. Then, the authority server 30 first searches the hash table for data corresponding to the hash value H (3), and determines whether or not NR-RR exists. Subsequently, when NS-RR does not exist, the authority server 30 determines whether or not the values of i (3) and (5) are equal. On the other hand, when the NS-RR exists, the authority server 30 sets the searched NS-RR as an answer candidate and responds with the answer candidate as a query response.

  If the values of i (3) and X (5) are not equal, the authority server 30 increments i by 1, searches the hash table for data corresponding to the hash value H (4), and NS-RR. It is determined whether (delegation destination) exists. Here, when NS-RR does not exist, i is incremented by 1 again, data corresponding to the hash value H (5) is searched from the hash table, and whether or not NS-RR (delegation destination) exists is determined. judge. Again, if there is no NS-RR, the values of i and X are equal, so the previously stored answer candidate is returned as a query response. However, when NS-RR exists in the hash value H (4) or (5), the authority server 30 replies NS-RR as a query response.

[Effects of Example 1]
As described above, according to the first embodiment, domain names are input to the hash function in order from the end, and hash values from the end to each label are sequentially calculated using the hash values from the label to the immediately preceding label. The domain name resource record is searched using the hash value up to the beginning of the domain name, and the delegation destination of the domain name is searched using the hash value from the end of the domain name to each label. In the resource record search process and the delegation destination search process, it is not necessary to calculate the hash value separately, and the search process (resource record) for the DNS query request can be compared with the case where a tree index is used. Search processing and delegation destination search processing) can be performed at high speed.

  Also, according to the first embodiment, the domain name delegation destination is searched in order from the hash value from the end of the domain name to each label, starting from the hash value from the label close to the end. Compared to a method of searching for a destination, there is a high possibility that a delegation destination will be found earlier, and a search process for a DNS query request can be performed at a higher speed.

  Although the embodiments of the present invention have been described so far, the present invention may be implemented in various different forms other than the embodiments described above. Therefore, another embodiment included in the present invention will be described below as a second embodiment.

  In the first embodiment, the case where the DNS server request is received from the cache server 20 and the authority server 30 executes the search process has been described. However, the present invention is not limited to this, and the DNS client 10 A DNS query request may be received.

  In the first embodiment, the case where the hash value calculation process, the resource record (RR) search process, and the delegation destination (NS-RR) search process are sequentially performed has been described. However, the present invention is not limited to this. Each process may be performed in parallel. For example, after performing the hash value calculation process, the resource record search process and the delegation destination search process may be performed in parallel.

  Also, in the first embodiment, as shown in FIG. 4, the domain name is input to the hash function in order from the end, and the hash value from the end to each label is used as the hash value up to the label immediately before each label. The case of calculating in order has been described, but the present invention is not limited to this, and further includes a delegation destination information storage unit that preliminarily stores delegation destination information indicating a label including information on the delegation destination, and the delegation destination information Only the hash value from the delegation destination information stored in the storage unit to the determined label may be calculated.

For example, as shown in FIG. 6, 2 label counted from the end showing the labels in the transfer destination information, stored in advance 4 labels eyes, from the end as a hash value to the label determined from the transfer destination information 2 Only the hash value up to the fourth label and the hash value up to the fourth label may be calculated. As a result, the hash values from the tail to each label are calculated in sequence using the hash values up to the immediately preceding label of each label (see FIG. 4). It is no longer necessary to calculate a hash value, and as can be seen by comparing FIG. 4 and FIG. 6, the calculation of the hash value can be reduced from 5 times to 4 times, and the search processing for the DNS query request is performed at a higher speed. It is possible.

  Further, in the first embodiment, the case where the domain name delegation destination is searched using the hash value from the end of the calculated domain name to each label has been described, but the present invention is not limited to this, It further includes a delegation destination information storage unit that preliminarily stores delegation destination information indicating a label including information indicating the delegation destination, and uses only the hash value from the delegation destination information stored in the delegation destination information storage unit to the determined label. You may make it search for the transfer destination of a domain name.

  For example, the second label and the fourth label from the end indicating the label including the delegation destination information are stored in advance in the authority server unit or the zone unit, and the hash value from the delegation destination information to the label determined is 2 from the end. The delegation destination of the domain name may be searched using only the hash value up to the fourth label and the hash value up to the fourth label. This eliminates the need to search for a delegation destination for a hash value up to a label that does not include delegation destination information, and makes it possible to perform a search process for a DNS query request at a higher speed.

  In addition, among the processes described in this embodiment, all or part of the processes described as being performed automatically can be performed manually, or the processes described as being performed manually can be performed. All or a part can be automatically performed by a known method. In addition, the processing procedure, control procedure, specific name, and information including various data and parameters shown in the above-described document and drawings can be arbitrarily changed unless otherwise specified.

  Each component of the search processing device (authoritative server device) shown in FIG. 2 is functionally conceptual and does not necessarily need to be physically configured as illustrated. In other words, the specific form of distribution / integration of each device is not limited to that shown in the figure, and all or a part thereof may be functionally or physically distributed or arbitrarily distributed in arbitrary units according to various loads or usage conditions. Can be integrated and configured. Furthermore, each processing function (for example, hash value calculation processing) performed in the search processing device is realized by a CPU and a program that is analyzed and executed by the CPU, or a part thereof, or It can be realized as hardware by wired logic.

  In the above-described embodiments, the search processing apparatus that implements the present invention has been described in terms of functions. However, each function of the search processing apparatus may be realized by causing a computer such as a personal computer or a workstation to execute a program. it can. That is, the various processing procedures described in the above embodiments can be realized by executing a program prepared in advance on a computer. These programs can be distributed via a network such as the Internet. Further, these programs can be recorded on a computer-readable recording medium such as a hard disk, a flexible disk (FD), a CD-ROM, an MO, and a DVD, and can be executed by being read from the recording medium by the computer. That is, for example, a CD-ROM storing a search processing program as shown in the embodiment (may be a separate CD-ROM for each apparatus) is distributed and stored in this CD-ROM. The program may be read and executed by each computer.

  As described above, the search processing device, the search processing method, and the search processing program according to the present invention are useful for searching for a resource record and a delegation destination for a domain name related to a DNS query request using a hash function. It is suitable for performing search processing (resource record search processing and delegation destination search processing) for query requests at high speed.

1 is a system configuration diagram showing the overall configuration of a DNS system including a search processing device (authoritative server). It is a block diagram which shows the structure of the search processing apparatus (authoritative server) which concerns on Example 1. FIG. It is a figure which shows the example of the hash function which shows the hash value calculation algorithm which concerns on Example 1. FIG. It is a figure which shows the example of the hash value calculation which concerns on Example 1. FIG. 6 is a flowchart illustrating a flow of search processing by a search processing apparatus (authoritative server) according to the first embodiment. It is a figure which shows the example of the hash value calculation which concerns on Example 2. FIG. It is a figure for demonstrating the flow of a process of the DNS system which concerns on a prior art. It is a figure for demonstrating the flow of a search process at the time of employ | adopting a tree as the index of the database in the authoritative server which concerns on a prior art. It is a figure for demonstrating the flow of a search process at the time of employ | adopting a hash table as an index of the database in the authoritative server which concerns on a prior art.

Explanation of symbols

DESCRIPTION OF SYMBOLS 10 DNS client 20 Cache server 30 Authority server 31 Communication control I / F part 32 Storage part 33 Control part 33a Hash value calculation part 33b Resource record search part 33c Delegation destination search part

Claims (7)

A search processing device for searching for a resource record and a delegation destination for a domain name related to a DNS query request by a hash function,
An intermediate calculation in which the domain name is input to the hash function in order from the end, and the hash value from the end to each label is calculated based on the hash value up to the label immediately before the label and the characters in the label Hash value calculation means for calculating values in order by remainder ,
Resource record search means for searching for a resource record for the domain name using a hash value from the end of the domain name to each label calculated by the hash value calculation means to the beginning of the domain name; ,
Delegation destination search means for searching for a delegation destination of the domain name using a hash value from the end of the domain name to each label calculated by the hash value calculation means;
A search processing apparatus comprising: The hash value calculation means calculates the hash calculated for the last character of the character string constituting the label for which the hash value is to be calculated for the last character and the label immediately before the input label. An intermediate calculation value is calculated based on the value, and for the first character from the last character, a new intermediate calculation is performed based on the character to be calculated and the intermediate calculation value calculated immediately before the character. After the values are calculated in order, the length field indicating the number of characters of the character string constituting the input label and the intermediate value calculated for the first character of the character string constituting the label for which the hash value is calculated Based on the calculated value, a new intermediate calculated value is calculated, and the calculated new intermediate calculated value is remaindered by a predetermined constant to calculate the hash value of the label to be calculated. Search processing apparatus according to claim 1, wherein the door. The delegation destination search unit searches for the delegation destination of the domain name in order from the hash value from the end of the domain name to each label calculated by the hash value calculation unit from the hash value to the label close to the end. Search processing apparatus according to claim 1 or 2, characterized in that. Delegation destination information storage means for preliminarily storing delegation destination information indicating a label including the information of the delegation destination,
When the delegation destination information storage means exists , the hash value calculation means refers to the delegation destination information storage means prior to executing the hash value calculation, and is stored in the delegation destination information storage means. search processing apparatus according to any one of claims 1-3, characterized in that to calculate only the hash value to the label determined from transfer destination information. Delegation destination information storage means for preliminarily storing delegation destination information indicating a label including information indicating the delegation destination,
When the delegation destination information storage unit exists , the delegation destination search unit refers to the delegation destination information storage unit prior to executing the hash value calculation, and is stored in the delegation destination information storage unit. search processing apparatus according to any one of claims 1 to 3 by using only the hash value to the label determined from transfer destination information, wherein the searching for delegate of the domain name. A search processing method for searching a resource record and a delegation destination for a domain name related to a DNS query request by a hash function,
An intermediate calculation in which the domain name is input to the hash function in order from the end, and the hash value from the end to each label is calculated based on the hash value up to the label immediately before the label and the characters in the label the hash value calculation step of calculating calculates the order by the remainder value,
A resource record search step of searching for a resource record for the domain name using a hash value from the end of the domain name to each label calculated by the hash value calculation step to the beginning of the domain name; ,
A delegation destination search step of searching a delegation destination of the domain name using a hash value from the end of the domain name to each label calculated by the hash value calculation step;
The search processing method characterized by including. A search processing program for causing a computer to execute a method of searching for a resource record and a delegation destination for a domain name related to a DNS query request using a hash function,
An intermediate calculation in which the domain name is input to the hash function in order from the end, and the hash value from the end to each label is calculated based on the hash value up to the label immediately before the label and the characters in the label the hash value calculation step of calculating calculates the order by the remainder value,
A resource record search procedure for searching for a resource record for the domain name using a hash value from the end of the domain name to each label calculated by the hash value calculation procedure to the beginning of the domain name; ,
A delegation destination search procedure for searching for a delegation destination of the domain name using a hash value from the end of the domain name to each label calculated by the hash value calculation procedure;
A search processing program characterized by causing a computer to execute.

Images