JP2008234563A - Overlay management device, overlay management system, overlay management method, and program for managing overlay - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To efficiently retrieve data having multidimensional attributes at high speed. <P>SOLUTION: A plurality of peers 110, 120, ... are connected in a network 100. Each of peers 110, 120, ... has the data in common in an overlay network (P2P network) at a high level layer of the existing network 100. Each peer 110, 120, ... converts the data having a plurality of attributes into a one-dimensional value, generates a logical identifier by applying a distribution function on the one-dimensional value, specifies the other peer for managing the logical identifier generated based on assignment of logical identifiers for each of peers 110, 120, ... in the overlay network, and registers the data in the other specified peer. <P>COPYRIGHT: (C)2009,JPO&INPIT

Description

  The present invention relates to an overlay management apparatus, an overlay management system, an overlay management method, and an overlay management program for managing data shared by terminals arranged in an overlay network, and in particular, maintains multi-dimensional information uniformly and continuously. The present invention relates to an overlay management apparatus, an overlay management system, an overlay management method, and an overlay management program that can calculate a logical identifier.

  An overlay network is a network that uses an existing link to form and configure a virtual link according to the purpose in the upper layer. That is, an upper layer network constructed regardless of the lower layer topology of the computer network is called an overlay network. For example, it refers to a P2P (Peer to Peer) network constructed irrespective of the topology of the IP network.

  By using overlay network technology, a database that shares data over a wide area can be realized by distributing data to a plurality of peers (also referred to as nodes) without using a center server (central server). it can. In particular, as a technique for realizing an associative array (hash table), there is a distributed hash table (DHT). By constructing a distributed hash table on the overlay network, it becomes possible to search a huge amount of data at high speed.

  An overview of the distributed hash table will be described. First, it is assumed that a plurality of peers exist on the overlay network. The name (keyword) of the content held by the peer is converted into a hash value (digitized) using a hash function. For example, if the peer has content named A, A is converted to a hash value hash (A).

  When a peer joins an overlay network, the peer determines and maintains a random node ID (Node_ID). If the peer has the content named A, the peer sends a hash value {hash (A)} of A and its own IP address {IP_Address} to a peer (node) whose Node_ID = hash (A). A set {hash (A), IP_Address} is notified and registered. If there is no peer with Node_ID = hash (A), the peer with Node_ID closest to hash (A) registers {hash (A), IP_Address}. If a user (searcher) wants content such as C, for example, if the user makes an inquiry to a peer having Node_ID = hash (C), the IP address of the peer that owns the content can be known.

  In the distributed hash table, there are methods such as Chord (circle), CAN (N-dimensional torus), Kademlia, P-Grid (binary tree), Tapestry, Pastry (Platton algorithm). The most common Chord among the distributed hash tables will be described later.

  According to such a configuration, the content can be searched at high speed without a center server, and the IP address of the peer that owns the content can be found.

  Conventional techniques using an overlay network are disclosed in the following patent documents.

  In the system described in Patent Document 1, the terminal collects and discloses the physical information of its own terminal, collects the physical information of other terminals, and calculates the reliability for each peer based on the collected physical information. A technique is disclosed in which connection management is performed according to reliability, a network topology is determined, a traffic change is detected, and a connection is changed.

  Patent Document 2 discloses information relating to a communication load on a communication path between a participating node that has returned a reply packet based on reply packets from a plurality of participating nodes that participate in the overlay network. A configuration is disclosed in which a node that is close to the network is selected based on the acquired information, and a participation request is made to the participating node to participate in the overlay network.

  Further, in Patent Document 3, when an overlay network is formed to have a plurality of zones and the communication load on a communication path between one node and another node is within a predetermined range, one node and another Are arranged so as to belong to the same zone in the overlay network.

JP 2005-252596 A JP 2006-191489 A JP 2006-217538 A Proceedings of the forth International Workshop on Grid Computing, “MAAN: A Multi-Attribute Addressable Grid Information Services” Http: // andy. usc. edu / ~ mcai / papers / maan. pdf, “MAAN: A Multi-Attribute Addressable Network for Grid Information Services” Proceedings of the 2001 SIGCOMM Conference, “Cord: A Scalable Peer-to-Peer Lookup Service For Internet Applications” IEEE Internet Computing, “Enabling Flexible Queries with Guarantees in P2P Systems” High Performance Distributed Computing, “Flexible Information Discovery in Decentralized Distributed Systems”

  By the way, it is conceivable that the user performs a data search based on a search condition of a multidimensional attribute. For example, a data search is executed based on a search condition of an attribute called a CPU speed of a computer and an attribute called a memory size. However, the above Patent Documents 1 to 3 disclose a technique for reducing the communication load on the overlay network, but do not disclose a technique for realizing multidimensional attribute (multiple attribute) data search.

  An object of the present invention has been made to solve the above-described problems, and is an overlay management apparatus, an overlay management system, an overlay management method, and an overlay management apparatus capable of efficiently and rapidly performing multidimensional attribute data retrieval. The purpose is to obtain an overlay management program.

  In order to achieve the above object, an overlay management apparatus according to the present invention is an overlay management apparatus that is arranged on an overlay network and manages data shared with other apparatuses. One-dimensional means for conversion, identifier generating means for generating a logical identifier by applying a function including value distribution information to the value one-dimensionalized by the one-dimensional means, and each device on the overlay network Based on the assignment of the logical identifier to the management device specifying means for specifying another device that manages the logical identifier generated by the identifier generating means, and for registering data in the other device specified by the management device specifying means Data registration means for executing processing is provided.

  A search condition one-dimensionalization means for converting a search condition of multiple attributes into a one-dimensional value set, and value distribution information for elements in the set of values one-dimensionalized by the search condition one-dimensionalization means An identifier range generation unit that generates a set of logical identifier ranges by applying a function including the data identifier by transferring the set of logical identifier ranges generated by the identifier range generation unit to another apparatus as a search request. Search request transfer means for performing a search may be provided. According to this configuration, when one piece of data having a plurality of attributes is registered in one device, it is possible to prevent the transfer load of search requests from being concentrated on a specific device.

  Logical identifier range dividing means for dividing a set of logical identifier ranges based on logical identifier assignment to each device on the overlay network, and the search request transfer means includes logical identifier range dividing means for dividing the logical identifier range divided by the logical identifier range dividing means. Data may be searched by transferring a set of ranges to another device as a search request. According to this configuration, even when the search range is wide, the number of search request hops can be prevented from increasing, and as a result, high-speed search and reduction of communication load can be achieved.

  The one-dimensionalization means or the search condition one-dimensionalization means converts the data of a plurality of attributes into a one-dimensional value or a set of values using a space filling curve, and the identifier generation means or the identifier range generation means converts the data into a space filling curve. Applying a space-filling curve distribution function that equalizes the one-dimensionalized value or set of values to generate a logical identifier or a set of ranges from the one-dimensionalized value or set of values. May be. According to this configuration, the range of the logical identifier for transferring the search request (search message) can be narrowed (for example, the search message is propagated to the number of elements satisfying both the x attribute and the y attribute as shown in FIG. 18). It is possible to prevent the data management load from being concentrated on each device on the overlay network.

  The logical identifier range dividing means may be configured to divide a set of logical identifier ranges based on logical identifiers stored in the routing table. According to this configuration, a set of logical identifier ranges can be divided into appropriate ranges, and as a result, a much faster search can be realized. Note that the routing table includes, for example, a finger table and successor list used in Chord.

  An overlay management system according to the present invention is an overlay management system that includes a plurality of terminals arranged on an overlay network and manages data shared among the terminals. A one-dimensional means for converting into a value, an identifier generating means for generating a logical identifier by applying a function including value distribution information to the value one-dimensionalized by the one-dimensional means, and a logic for each terminal Based on the assignment of the identifier, a management terminal specifying means for specifying another terminal that manages the logical identifier generated by the identifier generating means, and a process for registering data in the other terminal specified by the management terminal specifying means And a data registration means to execute.

  Each terminal uses a search condition one-dimensionalization means for converting a search condition with multiple attributes into a one-dimensional value set, and values for elements in the set of values one-dimensionalized by the search condition one-dimensionalization means. An identifier range generation unit that generates a set of logical identifier ranges by applying a function including distribution information of the ID, and forwards the set of logical identifier ranges generated by the identifier range generation unit to another terminal as a search request Thus, a search request transfer means for searching for data may be provided. According to this configuration, when one piece of data having a plurality of attributes is registered in one device, it is possible to prevent the transfer load of search requests from being concentrated on a specific device.

  Logical identifier range dividing means for dividing a set of logical identifier ranges based on the assignment of logical identifiers to each terminal, and the search request transfer means comprises a set of logical identifier ranges divided by the logical identifier range dividing means. Data may be searched by transferring it as a search request to another terminal. According to this configuration, even when the search range is wide, the number of search request hops can be prevented from increasing, and as a result, high-speed search and reduction of communication load can be achieved.

  The one-dimensionalization means or the search condition one-dimensionalization means converts the data of a plurality of attributes into a one-dimensional value or a set of values using a space filling curve, and the identifier generation means or the identifier range generation means converts the data into a space filling curve. Applying a space-filling curve distribution function that equalizes the one-dimensionalized value or set of values to generate a logical identifier or a set of ranges from the one-dimensionalized value or set of values. May be. According to this configuration, the range of the logical identifier for transferring the search request (search message) can be narrowed (for example, the search message is propagated to the number of elements satisfying both the x attribute and the y attribute as shown in FIG. 18). It is possible to prevent the data management load from being concentrated on each device on the overlay network.

  The logical identifier range dividing means may be configured to divide a set of logical identifier ranges based on logical identifiers stored in the routing table. According to this configuration, a set of logical identifier ranges can be divided into appropriate ranges, and as a result, a much faster search can be realized.

  According to the overlay management method of the present invention, the control unit of the management apparatus arranged on the overlay network converts the data of a plurality of attributes into a one-dimensional value according to the control program, and distributes the value to the one-dimensional value. A logical identifier is generated by applying a function including information, and another device that manages the generated logical identifier is identified based on assignment of the logical identifier to each device on the overlay network, and data is transmitted to the identified other device. It is characterized in that a process for registering is executed.

The control unit of the management device arranged on the overlay network follows the control program,
Convert multiple attribute search conditions into a one-dimensional set of values, and apply a function containing value distribution information to the elements in the one-dimensional set of values to generate a set of logical identifier ranges. The data may be searched by transferring the set of generated logical identifier ranges to other devices as a search request. According to this configuration, when one piece of data having a plurality of attributes is registered in one device, it is possible to prevent the transfer load of search requests from being concentrated on a specific device.

  Based on the assignment of logical identifiers to each device on the overlay network, a set of logical identifier ranges is divided, and data is searched by transferring the divided set of logical identifier ranges to other devices as a search request. It may be configured as follows. According to this configuration, even when the search range is wide, the number of search request hops can be prevented from increasing, and as a result, high-speed search and reduction of communication load can be achieved.

  Apply a space-filling curve distribution function that transforms multi-attribute data into a one-dimensional value or set of values using a space-filling curve, and uniformizes the one-dimensional value or set of values in the space-filling curve. It is also possible to generate a logical identifier or a set of ranges thereof from a one-dimensionalized value or set of values. According to this configuration, the range of the logical identifier for transferring the search request (search message) can be narrowed (for example, the search message is propagated to the number of elements satisfying both the x attribute and the y attribute as shown in FIG. 18). It is possible to prevent the data management load from being concentrated on each device on the overlay network.

  The set of logical identifier ranges may be divided based on the logical identifier stored in the routing table. According to this configuration, a set of logical identifier ranges can be divided into appropriate ranges, and as a result, a much faster search can be realized.

  An overlay management program according to the present invention is an overlay management program for managing data shared with other devices by a management device arranged on the overlay network, and converts multi-attribute data into one-dimensional values. Based on one-dimensional processing, identifier generation processing for generating a logical identifier by applying a function including value distribution information to the one-dimensional value, and assignment of a logical identifier to each device on the overlay network A management device specifying process for specifying another device that manages the generated logical identifier and a data registration process for executing a process for registering data in the specified other device. .

  Logical identifier by applying a function that contains value distribution information to the elements in the set of one-dimensional values and the search condition one-dimensionalization processing that converts the search conditions of multiple attributes into a one-dimensional value set To cause the management apparatus to execute an identifier range generation process for generating a set of ranges and a search request transfer process for searching for data by transferring the generated set of logical identifier ranges to another apparatus as a search request It may be. According to this configuration, when one piece of data having a plurality of attributes is registered in one device, it is possible to prevent the transfer load of search requests from being concentrated on a specific device.

  Based on the assignment of logical identifiers to each device on the overlay network, the management device is caused to execute logical identifier range division processing for dividing the set of logical identifier ranges, and in the search request transfer processing, the set of divided logical identifier ranges May be made to search for data by transferring it as a search request to another device. According to this configuration, even when the search range is wide, the number of search request hops can be prevented from increasing, and as a result, high-speed search and reduction of communication load can be achieved.

  In one-dimensionalization processing or search condition one-dimensionalization processing, data of multiple attributes is converted into a one-dimensional value or set of values using a space-filling curve, and a space-filling curve is generated in the identifier generation processing or identifier range generation processing. A space-filling curve distribution function that equalizes the one-dimensionalized value or set of values may be applied to generate a logical identifier or a set of ranges from the one-dimensionalized value or set of values. . According to this configuration, the range of the logical identifier for transferring the search request (search message) can be narrowed (for example, the search message is propagated to the number of elements satisfying both the x attribute and the y attribute as shown in FIG. 18). It is possible to prevent the data management load from being concentrated on each device on the overlay network.

  In the logical identifier range dividing process, a set of logical identifier ranges may be divided based on the logical identifier stored in the routing table. According to this configuration, a set of logical identifier ranges can be divided into appropriate ranges, and as a result, a much faster search can be realized.

  According to the present invention, the control unit of the management device arranged on the overlay network converts the data of a plurality of attributes into a one-dimensional value according to the control program, and applies a function to the one-dimensional value to perform logic. Generate an identifier, specify another device that manages the generated logical identifier based on the assignment of the logical identifier to each device on the overlay network, and execute processing for registering data in the identified other device Since it is configured, data retrieval of multidimensional attributes (multiple attributes) can be executed efficiently and at high speed.

  Hereinafter, an embodiment of the present invention will be described with reference to the drawings.

Embodiment 1 FIG.
FIG. 1 is a block diagram showing a configuration of an overlay management system in the first embodiment. As shown in FIG. 1, this overlay management system is composed of a plurality of peers 110, 120, 130 (which are also referred to as nodes) having addresses on a network 100 such as the Internet. . In FIG. 1, only the peers 110, 120, and 130 are shown as peers, but a plurality of other peers are connected to the plurality of networks 100.

  As shown in FIG. 1, each peer 110, 120, 130... Has a local data storage unit 111, a routing table 112, a message transfer unit 113, a communication unit 114, a peer logical identifier storage unit 115, An individual attribute distribution function storage unit 117 and registration / search execution means 118 are provided.

  The peer logical identifier storage unit 115 stores a logical identifier (also referred to as a node ID) of the peer (for example, the peer 110) in the overlay network. In this embodiment, the logical identifier is an identifier for identifying each peer on the overlay network. In this embodiment, as will be described later, data retrieval is performed using the Chord algorithm. In Chord, each peer assigns its logical identifier by a hash function such as SHA-1 when participating in the overlay network. The generated logical identifier (node ID) is stored in the peer logical identifier storage unit 115. This logical identifier is a unique value for each peer.

  The local data storage unit 111 stores data handled by the peer (for example, the peer 110) among data (contents) shared by all the peers 110, 120, 130. Which portion of data each peer is responsible for (manages) depends on the logical identifier of each peer.

  A routing table (also referred to as a finger table) 112 is a table referred to when each peer performs routing. The routing table 112 stores a plurality of sets of logical identifiers of other peers and addresses (for example, IP addresses; Internet Protocol addresses) on the network 100. The management method by the routing table 112 is the same management method as Chord. The detailed contents of Chord will be described later.

  The individual attribute distribution function storage unit 117 stores the individual attribute distribution function storage table 200 shown in FIG. The individual attribute distribution function storage table 200 stores attribute names 201 and corresponding distribution functions 202. In the individual attribute distribution function storage table 200 shown in FIG. 2, the attribute names are “CPU-Speed” and “Memory-Size”, and “63x / 5” is stored as the distribution function H (x) of “CPU-Speed”. Then, “63x / 1024” is stored as the distribution function H (x) of “Memory-Size”. Here, “/ 5” in “CPU-Speed” indicates that the CPU speed is 5 GHz, and “/ 1024” in “Memory-Size” indicates that the memory size is 1024 Mbytes.

As shown in Equation 1 below, this distribution function H (v) includes a cumulative distribution function D (v) having an attribute value v as one variable, and a maximum logical identifier (2 ^ m− 1) (ie, if the hash space is 2 ⁶ (2 to the 6th power), it is obtained from the product 2 ⁶ −1 = 64−1 = 63).

  H (v) = D (v) × (2 ^ m−1) (Equation 1)

  A detailed description of the cumulative distribution function and the distribution function will be described later.

  The registration / search execution means 118 executes data registration and search processing. Specifically, when data is input from the external interface, the registration / search execution unit 118 generates a logical identifier corresponding to the input data, and outputs the generated logical identifier to the message transfer unit 113. Request to register data with the peer corresponding to. When the registration / search execution means 118 receives the search request from the external interface, the registration / search execution means 118 reads out the distribution function of the attribute corresponding to the search condition included in the search request from the individual attribute distribution function storage unit 117, A search message (search request) is generated based on the search condition. Further, the registration / search execution means 118 executes a search process for data stored in the local data storage unit 111 based on a search message from another peer.

  The message transfer means 113 executes a data registration request and search message (search request) transfer processing. Specifically, when the message transfer unit 113 receives a data registration request from the registration / search execution unit 118, the message transfer unit 113 performs a process of transmitting data to the peer of the logical identifier generated by the registration / search execution unit 118. Execute. Also, the message transfer unit 113 refers to the routing table 112 and executes a process of transferring the search message generated by the registration / search execution unit 118 to a predetermined transfer destination peer. When the message transfer unit 113 receives a search message from another peer, the message transfer unit 113 refers to the routing table 112 and transfers the search message to a predetermined transfer destination peer or outputs it to the registration / search execution unit 118. Execute the process.

  The communication unit 114 executes processing for transmitting and receiving a search message and the like with other peers via the network 100.

(1) About Chord;
First, Chord which is one of the distributed hash tables will be described. In Chord, a circular hash space (one-dimensional hash space) is 2 ¹⁶⁰ (2 to the power of 160), and SHA-1 is assumed as a hash function. Here, in order to facilitate the explanation of the hash space, it is assumed that 2 ⁶ (= 64; the sixth power of 2) as shown in FIG. In this case, logical identifiers (node IDs) 0 to 63 are arranged in a circular hash space. Among them, the actual peers are “4” “15” “30” “48” “56” “60” in the example shown in FIG.

In Chord, peer information (peer) of logical identifiers of the number obtained by adding 2 ⁱ (2 to the power of i: i = 0, 1, 2, 4, 8,..., N) to the logical identifier of its peer. (Information on a set of logical identifier and IP address) is registered in the routing table 112 as a finger table. That is, the peer's logical identifiers 1, 2, 4, 8,... When there is no peer with its own logical identifier, information on the nearest peer larger than the number of logical identifiers (information on a pair of peer logical identifier and IP address) Is registered. In addition, information on a peer that is first present in the clockwise direction as viewed from its own logical identifier (an adjacent peer larger than its own logical identifier) (peer logical identifier and IP address pair information) is also stored in the routing table 112. be registered.

  Note that the first peer that exists in the clockwise direction when viewed from a predetermined logical identifier is referred to as “successor”. A peer that exists first in a counterclockwise direction as viewed from a predetermined logical identifier (an adjacent peer smaller than its own logical identifier) is referred to as a “predecessor”. Data management is performed using a hash space between the predecessor and itself as a responsibility area.

For example, in the example shown in FIG. 3, the hash space of the logical identifier is 2 ⁶ (2 to the sixth power), and peers with the logical identifiers 4, 15, 30, 48, 56, and 60 exist on the overlay network. . At this time, if the logical identifier of its own peer is “56”, its own logical identifier of 1, 2, 4, 8,... (Ie, logical identifiers 57, 58, 60, 0, 8, 24). ) Peers, or peers with logical identifiers that are larger and closest to those logical identifiers. Therefore, the information on the peers of the logical identifiers 60, 15, and 30 is held in the routing table 112. In addition, information on the successor of the logical identifier 60 that is a neighboring peer larger than its own logical identifier is also held in the routing table 112.

  In the above case, when the user transmits the hash value (transfer destination logical identifier 20) of the search keyword from the peer 305 of the logical identifier 56 to the overlay network, the peer 305 of the logical identifier 56 refers to the routing table 112 and performs logical processing. The search request (search message) is transferred to the peer 302 with the logical identifier 15 closest to the identifier 20, and the peer 302 with the logical identifier 15 transfers the search request to the peer 303 with the logical identifier 30 that is the successor of the transfer destination logical identifier 20. To do.

  In this way, in Chord, the routing table 112 is used to narrow down the hash space to be searched every time a peer to be searched is passed to the next peer, so that the number of hops required for the search (from peer to other The number of times the search message is transferred to the peer) can be suppressed to O (logN), and as a result, high-speed data search can be realized.

  Next, peer participation in Chord will be described. In the example shown in FIG. 3, it is assumed that a peer having a logical identifier 10 newly joins the overlay network. In this case, the peer with the logical identifier 10 has an appropriate peer currently participating in the overlay network search for a peer with the next logical identifier (the logical identifier 15 in the example shown in FIG. 3) larger than the logical identifier 10. . In addition, the peer with the logical identifier 10 is informed of the peer with the logical identifier immediately preceding the logical identifier 15 (4 in the example shown in FIG. 3). Then, the peer with the logical identifier 10 notifies the peer with the logical identifier 15 and the peer with the logical identifier 4 of their existence, and causes the routing table 112 to be changed. Further, the peer with the logical identifier 10 receives the data corresponding to the hash values 10 to 14 from the peer with the logical identifier 15 and stores it. By such processing, the peer with the logical identifier 10 can participate in the Chord (overlay network).

  Next, the detachment of the peer in Chord will be described. Each peer on the overlay network periodically checks the peer's life and death against the routing peer. When it is confirmed that the peer has left, the routing table is changed. However, in this case, there is a possibility that data stored in a peer leaving the network is lost. For this reason, the data held by the peer is replicated to a predetermined number of peers in an order that is close to the clockwise direction when viewed from the peer. As a result, even if a certain peer leaves the network, data is not lost.

(2) Cumulative distribution function and distribution function;
The cumulative distribution function D (v) is a monotonically increasing function that is not less than 0 and not more than 1. For example, consider the Japanese age density function. In this case, the total number of people who are 60 years old is 0.05. The cumulative distribution function D (v) is obtained by integrating this density function. That is, the ratio of people under 60 years old is 0.7, and becomes 1 at about 120 years old. This D (v) is characterized in that data samples according to the same distribution are made uniform between 0 and 1. For example, if you select an arbitrary Japanese and listen to their age v, there are relatively few people up to about 20s, and the number of people in their 30s and 40s gradually increases. ) Is the most common, and in the subsequent years, the percentage decreases. However, when the cumulative distribution function D (v) is obtained, it is uniformly distributed in ˜1.

  As described above, 2 ^ m−1 is a maximum value of an ID (logical identifier) in the overlay network and represents a maximum value of m bits. For example, a 6-bit numerical value ranges from 000000 to 111111. In this case, the maximum value is 2 ^ 6-1 = 63 (111111 in binary notation).

By taking the product of the cumulative distribution function D (v) and 2 ^m −1, the distribution function H (v) is uniformly distributed between 0 and 2 ^m −1. If there is a server (terminal) for each ID, this age data is arranged in each server with the same probability, so there is an advantage that there is no load bias.

  Next, the operation of the overlay management system in the first embodiment will be described.

  FIG. 4 is a sequence diagram showing the operation of the overlay management system in the first embodiment. For example, in the peer 301 having the logical identifier 4 shown in FIG. 3, the attribute name “CPU-Speed” shown in FIG. 2 has the value (4.0, 5.0) and the attribute name “Memory-Size” is [768]. , 1024] is assumed. Here, (4.0, 5.0) indicates the search range where the lower limit value is 4.0 GHz and the upper limit value is 5.0 GHz, and [768,1024] is the lower limit value is 768 MB and the upper limit value is 1024 M. Indicates that this is a byte search range.

  As shown in FIG. 4, in the peer 301, the registration / search execution means 118 uses (4.0, 5.0) in the attribute name “CPU-Speed” and the attribute name “Memory-Size” as search conditions. [768, 1024] is input (acquired) from the external interface (step S100). Then, the registration / search execution means 118 reads out and obtains a calculation formula for obtaining the distribution function H (v) corresponding to the attribute name “CPU-Speed” and the attribute name “Memory-Size” from the individual attribute distribution function storage unit 117. To do.

  Then, the registration / search execution means 118 generates a search message (search request) based on the search condition and the calculation formula for obtaining the distribution function H (v) (step S101). Specifically, first, the distribution of each attribute is calculated by substituting the lower limit value and the upper limit value of each specified attribute into the calculation formula (the above formula 1) for obtaining the distribution function H (v) corresponding to each attribute. The lower limit value and upper limit value of the function H (v) are acquired. For example, in the case of the attribute name “CPU-Speed”, the value of the distribution function obtained from the lower limit value 4.0 is 50.4, and the value of the distribution function obtained from the upper limit value 5.0 is 63. . In the case of the attribute name “Memory-Size”, the value of the distribution function obtained from the lower limit value 768 is 47.23, and the value of the distribution function obtained from the upper limit value 1024 is 63. Accordingly, the distribution function range (50.4, 63) is obtained for the attribute name “CPU-Speed”, and the distribution function range [47.23, 63] is obtained for the attribute name “Memory-Size”. Become.

  Next, the registration / search execution means 118 selects, as a dominant attribute, an attribute having a narrow range of the distribution function range of each attribute. Here, the CPU-Speed attribute is selected. Then, the registration / search execution means 118 uses the lower limit value of the attribute range selected as the dominant attribute as the transfer destination logical identifier. Here, 50.4 is regarded as a transfer destination logical identifier. Then, the registration / search execution means 118 generates a search message (transfer request) 310 from these pieces of information. As shown in FIG. 3, the search message includes [transfer destination logical identifier, dominant attribute, range corresponding to the dominant attribute, sub search expression, result list] used in the Chord algorithm transfer. Here, the sub-search formula is a search formula obtained by removing the dominant attribute search formula from the original search formula (search condition) of each attribute, that is, the attribute name CPU-Speed is selected as the dominant attribute. Memory-Size search formula [768, 1024]. In the above example, a specific example of the search message 310 is the search message 311 [50.4, CPU-Speed, (4.0, 5.0), Memory-Sizeε [768, 1024], Null]. . The result list is initially set to “Null” (initial state).

  The registration / search execution means 118 outputs the generated search message to the message transfer means 113. The message transfer unit 113 refers to the routing table 112, determines the transfer destination peer of the search message, and transmits the search message via the communication unit 114 (step S102). In this case, since the “transfer destination logical identifier” included in the search message is 50.4, the peer 304 having the logical identifier 48 smaller than the transfer destination logical identifier 50.4 is determined as the transfer destination peer of the search message. The

  Upon receiving the search message from the peer 301, the peer 304 with the logical identifier 48 determines whether it is a successor with the transfer destination logical identifier 50.4 (step S103). If it is not a successor (N in step S103), the search message is transferred to another peer based on the routing table (step S104). Finally, it is transferred to the peer that is the successor of the transfer destination logical identifier 50.4. If it is a successor (Y in step S103), the processes in steps S105 to S108 are executed. In the example shown in FIG. 3, since the peer 304 is not a successor (N in step S103), the search message is transferred to the peer 305 of the logical identifier 56 without executing the processing in steps S105 to S108 (step S104). ).

  The peer 305 also performs the same process as the peer 304. That is, it is determined whether or not the transfer destination logical identifier 50.4 is a successor (step S103). In the example shown in FIG. 3, since the peer 305 with the logical identifier 56 is a successor with the transfer destination logical identifier 50.4 (Y in step S103), a search process is executed (step S105). That is, it is searched whether or not data matching the sub search expression included in the search message exists in the local data storage unit 111 (the local data storage unit 321 in FIG. 3). In the example illustrated in FIG. 3, it is assumed that [Memory-Size] 768 MB is retrieved as data that matches the sub retrieval formula (Memory-Sizeε [768, 1024]). In this case, since the name (search keyword) “peer 15” (that is, the peer 302 of the logical identifier 15) is found as a peer of [Memory-Size] 768MB, “peer 15” is stored in the result list of the search message 312. Is done.

  Next, the peer 305 determines whether or not it is a successor of the logical identifier with the upper limit of the range corresponding to the dominant attribute included in the search message (step S106). If it is the successor of the logical identifier at the upper limit of the range (Y in step S106), the search result is returned to the peer 301 (step S108), and the process is terminated. On the other hand, if it is not the successor of the logical identifier at the upper limit of the range (N in step S106), the search message is transferred to another peer (the peer of the peer's successor) (step S107). In the example shown in FIG. 3, since the upper limit value of the search range corresponding to the dominant attribute is 63 and the logical identifier of the peer 305 is 56, it is determined that the peer 305 is not a successor of the upper limit logical identifier ( In step S106, N), the search message is transferred to the peer 306 having the logical identifier 60, which is the successor of the peer 305 (step S107).

  Similarly to the peer 305, the peer 306 also executes the process of step S106. That is, it is determined whether it is a successor of the logical identifier at the upper limit of the range. In the example shown in FIG. 3, since the peer 306 is not the successor of the logical identifier at the upper limit of the range (N in step S106), the search message is further transferred to the peer 301 of the logical identifier 4 that is the successor of the peer 306 (step S107). .

  The peer 301 is a successor of the logical identifier at the upper limit of the range, but in the example shown in FIG. 3, since the peer 301 has no data to be searched, the search ends here. Then, a search result 313 of “peer 15” is returned to the peer 301 that issued the search message (sender) (step S108). In this case, the peer 301 replies to itself.

  FIG. 5 is an explanatory diagram showing the relationship between attribute values and distribution functions. As shown in the graph 400 of the xy coordinates in FIG. 5, when the x attribute data is taken on the x axis and the y attribute data is taken on the y axis, the data values (data plots) are concentrated in a predetermined range. It shall be. In the example shown in FIG. 5, it is concentrated in three places. Here, when the data of the x attribute is converted into a distribution function using the above equation 1, a uniform distribution as shown in a graph 421 at the bottom of FIG. 5 is obtained. Further, when the y attribute data is converted into a distribution function using the above equation 1, a uniform distribution as shown in the graph 422 on the right side of FIG. 5 is obtained.

  As shown in FIG. 5, it is assumed that a substantially central range 431 is designated as the x attribute search condition 411 and an upper half range 432 is designated as the y attribute search condition 412. In this case, since the x attribute has a narrow range, the x attribute is selected as the dominant attribute. Then, as described above, the lower limit value of the search range of the dominant attribute is determined as the transfer destination logical identifier, and a search message for the transfer destination logical identifier is transmitted. When the search message reaches the successor peer of the transfer destination logical identifier, data search is executed locally within the peer. Thereafter, the search message is forwarded to the successor peer for the logical identifier of the upper limit value of the search range of the dominant attribute. A data search is then performed locally at that peer. Thereafter, the search result is returned to the peer that sent the search message.

  As described above, according to the first embodiment, a data search can be executed based on a search condition for multidimensional attributes. In this case, since the search is performed using the Chord algorithm, the number of hops can be reduced, and the communication load on the network can be reduced and high-speed search can be realized. In addition, since multi-dimensional attribute data is converted into a distribution function and uniformized, it is possible to prevent a load from being concentrated on a specific peer.

  In the first embodiment, the data search based on the search condition of the two-dimensional attribute has been described. However, the data search can be applied to the data search based on the search condition of the multidimensional attribute. Also in this case, the attribute having the narrowest search range is selected as the dominant attribute, and a search message (search request) is transmitted using the lower limit value of the dominant attribute as the transfer destination logical identifier.

Embodiment 2. FIG.
In the first embodiment, the method using the distribution function of each attribute is described. In the second embodiment, a method using a space filling curve will be described.

  FIG. 6 is a block diagram showing the configuration of the overlay management system in the second embodiment. As shown in FIG. 6, the overlay management system according to the second embodiment also has a plurality of peers 510, 520, 530,... Having addresses on a network 500 such as the Internet (the peers are also referred to as nodes). It is composed of FIG. 6 shows only peers 510, 520, and 530 as peers, but a plurality of other peers are connected to a plurality of networks 500.

  As shown in FIG. 6, each of the peers 510, 520, 530... Has a local data storage unit 511, a routing table 512, a message transfer unit 513, a communication unit 514, a peer logical identifier storage unit 515, Space filling curve conversion means 517 and registration / search execution means 518 are provided.

  The peer logical identifier storage unit 515 stores a logical identifier (also referred to as a node ID) of the peer (for example, the peer 110) in the overlay network.

  In the local data storage unit 511, among data (contents) shared by all the peers 510, 520, 530,..., Data handled by the peer (for example, the peer 110) is stored.

  The routing table 512 is a table referred to when each peer performs routing. In the routing table 512, a plurality of sets of logical identifiers of other peers and addresses (for example, IP addresses) on the network 500 are stored.

  The space filling curve conversion means 517 executes processing for converting the search condition value of the multidimensional attribute into the value of the one-dimensional search condition using the space filling curve.

  The registration / search execution means 518 executes data registration and search processing. The message transfer unit 513 refers to the routing table 512 and executes search message (search request) transfer processing.

  The communication unit 514 executes processing for transmitting and receiving a search message and the like with other peers through the network 500.

  Note that the second embodiment is not a method using the Chord algorithm, unlike the first embodiment. However, almost the same processing is executed except for the configuration of the registration / search execution means 518 and the space filling curve conversion means 517.

  Next, the operation of the overlay management system in the second embodiment will be described.

  FIG. 7 is an explanatory diagram illustrating a specific example of dividing a cluster using a space filling curve. Assume that a search expression Query (a processing request (inquiry) to the database management system expressed as a character string) is a search expression for a two-dimensional attribute. For example, if the value of the x attribute is 011 and the value of the y attribute is 1 **, it can be expressed as (011, 1 **). At this time, the set of the first bit of each attribute is (0, 1). Here, the upper left area 602 in the upper left table 600 of FIG. 7 is the area (range) designated by (0, 1), and Cluster is “01” (the number shown at the center position of the upper left area 602). It is. This “01” indicates the distance from the origin “00” that traces the route of a space filling curve (a space filling curve is a curve that fills a certain space with a curve). In FIG. 7, the Hilbert space filling curve is used as the space filling curve.

  Next, the set of the second bits of (011, 1 **) is (1, *). Here, “*” is a value of 0 or 1. Therefore, there are combinations of (1, 0) and (1, 1). An area 611 having an x attribute “01” and y attributes “10” and “11” in the table 610 in the upper right of FIG. 7 is an area (range) designated by (01, 1 *). "0110" and "0111". These “0110” and “0111” indicate the distance from the origin “0000” traced to the route of the space filling curve.

  The third bit set of (011, 1 **) is also (1, *). Also in this case, there are combinations of (1, 0) and (1, 1). An area 621 in which the x attribute is “011” and the y attributes are “100”, “101”, “110”, and “111” in the table 620 in the lower left of FIG. 7 is an area designated by (011, 1 **) (Range), and Cluster is “011010”, “011011”, “011100”, “011111”. These “011010”, “011011”, “011100”, and “011111” indicate distances from the origin “000000” traced to the route of the space filling curve.

  In this way, a list having a plurality of Clusters can be generated from the search formula (011, 1 **) using the space filling curve. A list having a plurality of Clusters is called a ClusterList. According to the method of the second embodiment, the peer that transfers the search message is routed by associating the cluster with the logical identifier in the hash space.

  FIG. 8 is an explanatory diagram showing a specific example of a message flow between peers in the second embodiment. FIG. 9 is a sequence diagram showing the operation of the overlay management system in the second embodiment. As shown in FIG. 8, in the peer 705 with the logical identifier 56, when the registration / search execution means 518 obtains the search expression Query input from the external interface, a search message including the search expression is sent to the peer 706 with the logical identifier 0. Send. At this time, it is assumed that the retrieval formula is (011, 1 **). This search expression (011, 1 **) is a search expression for two attributes, and is an exact match search with an x attribute of 011 and a forward match search with a y attribute of 1 **. Note that the search message in the second embodiment has a format different from that of the search message shown in the first embodiment.

  When the peer 706 issues a search message (search formula) (step S500), the registration / search execution means 518 of the peer 706 outputs the search formula to the space filling curve conversion means 517 to generate ClusterList (step S501). The space filling curve conversion means 517 generates Cluster “01” and outputs it to the registration / search execution means 518 according to the procedure described in FIG. The registration / search execution means 518 transmits a search message to the peer 702 having the logical identifier 010000 (= 16) corresponding to the cluster “01” (step S502).

  When the peer 702 having the logical identifier 16 receives and acquires the search message (search formula) from the peer 706, the registration / search execution means 518 of the peer 702 uses the logical identifier specified by the search formula included in the search message. Is a logical identifier managed by itself (step S503). If it is a logical identifier managed by itself (Y in Step S503), the registration / search execution means 518 executes a search process (Step S506). That is, it is searched whether or not data matching the search formula included in the search message exists in the local data storage unit 511. Then, the peer 702 returns the search result to the peer 705 of the message transmission source (transmission source) (step S507). In the example illustrated in FIG. 8, the logical identifier specified in the search expression is not a logical identifier managed by the peer 702 of the logical identifier 16.

  If it is not a logical identifier managed by itself (N in step S503), the registration / search execution means 518 outputs the search formula to the space filling curve conversion means 517 to generate a ClusterList (step S504). The space filling curve conversion unit 517 generates the cluster “011” including “0110” and “0111” and outputs it to the registration / search execution unit 518 in the procedure described with reference to FIG. Note that the Cluster identifier is the common first bit of the elements included in it. The registration / search execution means 518 searches for a peer managing Cluster “011”, and transmits a search message to the peer with the logical identifier 011110 (= 30) (step S505).

  When the peer 703 with the logical identifier 30 receives and acquires the search message (search formula) from the peer 702, the registration / search execution means 518 of the peer 703 specifies the logical identifier specified by the search formula included in the search message. Is a logical identifier managed by itself (step S503). In the example illustrated in FIG. 8, a logical identifier that starts with “0110” in the Cluster is a logical identifier managed by the peer 703 of the logical identifier 30. Accordingly, the registration / search execution means 518 of the peer 703 executes a search process (step S506). That is, it is searched whether or not data matching the search formula included in the search message exists in the local data storage unit 511. Then, the peer 703 returns the search result to the peer 705 of the message transmission source (transmission source) (step S507).

  Further, the peer 703 of the logical identifier 30 outputs “011100” as an output obtained by using the space filling curve conversion means 517 from the logical identifier beginning with “0111” and the search expression (011, 1 **) included in the cluster. Cluster “011100” including “and Cluster“ 011111 ”including“ 011111 ”are obtained. These are transferred to the peer 703 having the logical identifier 011110 (= 30) as the next destination and the peer 704 having the logical identifier 110000 (= 48), respectively, and each logical identifier is determined to be managed by the peer. Therefore, a search is made as to whether data exists in the local data storage unit 511, and if it exists, the search result is returned to the peer 705 that is the message transmission source (step S507).

  As described above, according to the second embodiment, data search is performed based on a search expression (search condition) of multidimensional attributes by converting multidimensional data into one-dimensional data using space filling curve conversion. It can be performed. Further, by dividing the cluster in stages each time a search message is transferred, the transfer destination of the search message can be distributed and the number of hops can be reduced. As a result, communication load on the network can be reduced and high-speed search can be realized.

  In the first embodiment, data search based on a two-dimensional attribute search formula has been described. However, the present invention can also be applied to data search based on a multi-dimensional attribute search formula. Moreover, although the Hilbert space filling curve was used as the space filling curve, it is not limited to the Hilbert space filling curve, but is a Z-curve space filling curve, a Peano space filling curve, a Sherpinski space filling curve, a Lebesgue space filling curve. It may be.

Embodiment 3 FIG.
FIG. 10 is a block diagram showing the configuration of the overlay management system in the third embodiment. As shown in FIG. 10, this overlay management system is composed of a plurality of peers 1010, 1020, 1030 (having peers also referred to as nodes) having addresses on a network 1000 such as the Internet. . FIG. 10 shows only peers 1010, 1020, and 1030 as peers, but a plurality of other peers are connected to a plurality of networks 1000.

  As shown in FIG. 10, each of the peers 1010, 1020, 1030... Has a local data storage unit 1011, a routing table 1012, a message transfer unit 1013, a communication unit 1014, a logical identifier range dividing unit 1015, A space filling curve distribution storage unit 1016, a space filling curve conversion unit 1017, a registration / search execution unit 1018, and a peer logical identifier storage unit 1019 are provided.

  The peer logical identifier storage unit 1019 stores a logical identifier (also referred to as a node ID) of the peer (for example, peer 110) in the overlay network. In this embodiment, the logical identifier is an identifier for identifying each peer on the overlay network. In this embodiment, as in the first embodiment, data retrieval is performed using the Chord algorithm. In Chord, each peer has its own hash function such as SHA-1 when joining the overlay network. A logical identifier is generated, and the generated logical identifier (node ID) is stored in the peer logical identifier storage unit 1019. This logical identifier is a unique value for each peer.

  The local data storage unit 1011 stores data handled by the peer (for example, the peer 1010) among data (contents) shared by all the peers 1010, 1020, 1030. Which portion of data each peer is responsible for (manages) depends on the logical identifier of each peer.

  The routing table 1012 is a table that is referred to when each peer performs routing. The routing table 1012 stores a plurality of pairs of logical identifiers of other peers and addresses (for example, IP addresses) on the network 1000. The management method by this routing table 1012 is the same management method as Chord.

  In the space filling curve distribution storage unit 1016, as shown in FIG. 11, a space filling curve distribution function D (k) is stored for each group index of a plurality of attributes.

  The space filling curve conversion unit 1017 generates a logical identifier Id corresponding to data registered using the space filling curve distribution function D (k) stored in the space filling curve distribution storage unit 1016. The space filling curve conversion unit 1017 generates a logical identifier range list corresponding to the search expression included in the search request using the space filling curve distribution function D (k) stored in the space filling curve distribution storage unit 1016. To do.

  The registration / search execution means 1018 executes processing related to predetermined data registration in response to a data registration request from the external interface. Also, the registration / search execution means 1018 executes processing related to a predetermined data search in response to a data search request from the external interface. Also, the registration / search execution means 1018 executes processing such as data search in the local data storage unit 1011 and transfer of the search request to another peer in response to reception of the search request from another peer.

  The message transfer means 1013 executes search request (search message) transfer processing. The communication unit 1014 executes processing for transmitting and receiving a search message and the like with other peers through the network 1000. Thereby, the message transfer unit 1013 of a certain peer can call the message transfer unit 1013 of another peer.

  The logical identifier range dividing unit 1015 divides the range of the logical identifier given as the search target into two logical identifier ranges based on the information of the logical identifier of the peer stored in the routing table 1012.

  Next, processing for converting two-dimensional data into one-dimensional data using a space filling curve will be described with reference to FIG.

  FIG. 12 is an explanatory diagram showing a data structure that visually represents an algorithm of processing for converting two-dimensional data into one-dimensional data using a space filling curve. FIG. 12 shows a case where a Hilbert space filling curve is used as the space filling curve.

  The data structure shown in FIG. 12 manages the state 1211 (“0” in FIG. 12) and the bit pattern conversion rule uniquely determined by the state. The conversion rule is a bit string 1213 generated from the first bit of the two-dimensional attribute of (001, 011), for example, a bit string 00 generated from the i-th bit of the multidimensional attribute, a bit string 01 generated from the second bit, Based on the bit sequence 11 generated from the third bit), it is a rule for converting the i-th layer (for example, the first layer 1210 in FIG. 12) into a one-dimensional additional bit sequence 1212 (for example, the first layer). Assuming that 1210 is the i-th layer, when the lower bit string is 00, the upper 00 is an additional bit string, and when the lower bit string is 01, the upper 01 is an additional bit string. When the stage bit string is 11, the upper stage 10 is an additional bit string, and when the lower stage bit string is 10, the upper stage additional bit string is 11.

  A state 1421 (“1”, “0”, “0”, “2” in FIG. 12) defining the conversion rule of the (i + 1) th bit is treated as a state transition from the state 1211 of the i-th bit. The conversion rule is applied up to the number of bits to be converted from multidimensional to one-dimensional, and the bit string obtained by connecting the additional bit strings corresponding to the bit string in each layer becomes the key after converting the value of the multidimensional attribute.

  The algorithm (method) for converting multidimensional data into one-dimensional data using the data structure shown in FIG. 12 is the same as the algorithm (method) for converting multidimensional data into one-dimensional data described in FIG. Specifically, when the value of the x attribute is 011 and the value of the y attribute is 111, it can be expressed as (011, 111). At this time, the set of the first bit (first bit) of the two attributes is (0, 1). In this case, the bit string of the first bit set is “01”. In the first hierarchy 1210 shown in FIG. 12, the upper bit string corresponding to the lower bit string “01” is “01”. The set of the second bits of the two attributes is (1, 1). In this case, the bit string of the second bit set is “11”. In the second hierarchy 1220 shown in FIG. 12, the upper bit string corresponding to the lower bit string “11” in the state “0” is “10”. A set of third bits of two attributes is (1, 1). In this case, the bit string of the third bit set is “11”. In the third hierarchy 1230 shown in FIG. 12, the upper bit string corresponding to the lower bit string “11” in the state “0” is “10”. Thus, the bit string “011010” obtained by connecting the additional bit strings corresponding to the bit strings in each layer becomes the key after the two-dimensional attribute values (011, 111) are converted.

  Next, the operation of the overlay management system in the third embodiment will be described.

(1) Registering data to be shared on the overlay network;
FIG. 13 is a flowchart illustrating processing for registering data shared in the overlay network according to the third embodiment. First, when registering data to be shared in an overlay network, a registration / search execution unit 1018 of a certain peer (for example, peer 1010) accepts a data registration request from an external interface, and sends it to the space filling curve conversion unit 1017. Data is output and a logical identifier corresponding to this data (multi-attribute value Atts) is requested. Then, the registration / search execution unit 1018 acquires a logical identifier corresponding to the data generated by the space filling curve conversion unit 1017 (step S1301). Then, the registration / search execution means 1018 outputs the logical identifier acquired from the space filling curve conversion means 1017 to the message transfer means 1013 and registers data in the peer corresponding to this logical identifier (the peer of the successor of this logical identifier). It is requested to do so (step S1302).

  When the message transfer unit 1013 receives a data registration request from the registration / search execution unit 1018, the message transfer unit 1013 transmits data to the peer corresponding to the logical identifier output from the registration / search execution unit 1018 to request data registration. To do.

  When the registration is successful (when a registration completion notification is received from the peer corresponding to the logical identifier) (Y in step S1303), the registration / search executing means 1018 returns a registration success to the external interface (step S1303). If registration fails (N in step S1303), the registration / search execution means 1018 returns a registration failure to the external interface (step S1304). If registration fails, registration may be performed simultaneously with retry processing or other logical identifiers that are uniquely calculated from the logical identifiers to make data redundant.

  FIG. 14 is a flowchart showing the subroutine processing of step S1301. As shown in FIG. 14, when registering data to be shared with other peers, the space filling curve conversion means 1017 of a certain peer receives the logical identifier shown below when requested by the registration / search execution means 1018. A process for calculating the identifier Id is executed. First, the space filling curve conversion unit 1017 calculates a combination of attribute names and attribute names shown in FIG. 11 from a set of attribute names corresponding to the value Atts of multiple attributes included in the data from the registration / search execution unit 1018. The space filling curve distribution function D (k) corresponding to is acquired from the space filling curve distribution storage unit 1016 (step S1401).

  Then, the space filling curve conversion unit 1017 calculates and acquires a one-dimensional value Key obtained by adapting a set of values of multiple attributes included in the data to the space filling curve (step S1402). Here, the process of converting a set of values of a plurality of attributes into a one-dimensional value Key using a space filling curve is performed using the data conversion method based on the data structure shown in FIG. The calculation formula for obtaining the key is the following formula 2. Note that “SFC” in Equation 2 represents a space filling curve line.

  Key = SFC (v1,..., Vi,..., Vn) (Expression 2)

  Next, the space filling curve conversion unit 1017 calculates the logical identifier Id by substituting the value Key obtained from Equation 2 into the space filling curve distribution function D (k) acquired from the space filling curve distribution storage unit 1016 ( Step S1403). The calculation formula for obtaining the logical identifier Id is the following formula 3.

  Id = D (Key) (Formula 3)

(2) An operation for searching for shared data in the overlay network;
FIG. 15 is a flowchart showing processing for searching for data shared in the overlay network in the third embodiment. First, when searching for data to be shared in the overlay network, a registration / search executing means 1018 of a certain peer (for example, peer 1010) receives a search request including a search expression Query from an external interface, and space filling curve converting means. A search expression is output to 1017, and a logical identifier range list IdRanges corresponding to the search expression is requested. Then, the registration / search execution unit 1018 obtains a logical identifier range list corresponding to the search formula generated by the space filling curve conversion unit 1017 (step S1501). Next, the registration / search execution means 1018 initializes a list for storing search results (result list Results), and starts a process for storing search result messages (reception results) from other peers in the result list ( Step S1502).

  Next, the registration / search execution means 1018 sets the maximum time to wait for the search result as a timeout (Timeout) (step S1503), and the message transfer means 1013 using the logical identifier range list acquired from the space filling curve conversion means 1017 as an argument. Is called asynchronously (step S1504). That is, the registration / search execution means 1018 asynchronously requests the message transfer means 1013 to transfer a search message (search request) to the peer of the logical identifier in the logical identifier range list.

  The registration / search execution means 1018 waits for the search results until search results for all the logical identifier peers in the logical identifier range list are obtained or the timeout (Timeout) becomes 0 or less (steps S1505 and S1506). . That is, as long as the search results for all the logical identifier peers in the logical identifier range list have not been acquired and the timeout is 0 or more, an interbell is set for a certain time and the timeout value is subtracted. .

  When the search results for the peers of all the logical identifiers in the logical identifier range list are acquired, or when the timeout becomes 0 or less, the registration / search execution means 1018 displays the search results transmitted from other peers. The stored result list is returned to the search requester (the user who made the search request from the external interface) and presented.

  FIG. 16 is a flowchart showing the subroutine processing of step S1501. As shown in FIG. 16, when searching for data to be shared with other peers, a space filling curve conversion unit 1017 of a certain peer sets a set of attribute names included in the search expression output from the registration / search execution unit 1018. Based on this, the space filling curve distribution function D (k) corresponding to the set of attribute names is acquired (step S1601).

  Then, the space filling curve conversion unit 1017 uses the space filling curve to obtain a plurality of key ranges KeyRanges satisfying the search formula (upper limit value and lower limit value of a plurality of attributes) (step S1602). Here, the process of converting the search expression into a plurality of one-dimensional values Key using the space filling curve is performed using the data conversion method based on the data structure shown in FIG. The calculation formula for obtaining KeyRanges is the following formula 4.

  KeyRanges = SFC (q1,..., Qi,..., Qn) (Expression 4)

  Next, the space filling curve conversion unit 1017 initializes the logical identifier range list IdRanges (step S1603). Then, the space filling curve conversion means 1017 provides a space filling curve distribution with respect to the range of the element Key (each Key) included in the KeyRanges, with the start end (KeyStart; lower limit value) and the end (KeyEnd; upper limit value) of the range. The function D (k) is applied (assigned) to determine the start and end of the logical identifier range IdRange (step S1604). Then, the space filling curve conversion unit 1017 adds the logical identifier range (start end and end) obtained in step S1604 to the logical identifier range list IdRanges (step S1605). The calculation formula for obtaining the logical identifier range list IdRanges is the following formula 5.

  IdRanges = {Id | Id = H (Key), Key ∈ KeyRanges)} (Formula 5)

  The space filling curve conversion unit 1017 returns the logical identifier range list IdRanges obtained in step S1605 to the registration / search execution unit 1018 as the logical identifier range list IdRanges corresponding to the search expression (step S1606).

  FIG. 17 is a flowchart showing the subroutine processing of step S1504. Upon receiving a search message transfer request from the registration / search execution unit 1018, the message transfer unit 1013 executes a message transfer process for searching for a peer in charge (management) of the logical identifier of the data storage destination. Further, the logical identifier range dividing unit 1015 executes processing related to division of the logical identifier range when the message transfer unit 1013 executes message transfer processing.

  In addition, when registering data shared by all peers, it is a method for finding (searching) a peer corresponding to one logical identifier, which is the same method as the Chord algorithm. However, the process of searching for data shared by all peers is a process of finding (searching) a peer corresponding to the logical identifier range, which is a system different from the Chord system.

  First, the logical identifier range dividing unit 1015 divides the logical identifier range IdRanges given from the registration / search executing unit 1018 into two logical identifier ranges (LowRanges and HighRanges) with the logical identifier s of the successor, and the peer (this example) Then, the logical identifier range LowRanges close to the peer m) and the logical identifier range HighRanges far from the peer m are acquired (step S1701). Here, “far” means that the logical identifier m_Id of the peer m uses the congruence equation mod, and the following equation 6 is established between any logical identifier L_Id in LowRanges and any logical identifier H_Id in HighRanges. To do. For example, when m_Id is 56 and m = 6, 4 is closer than 40.

  (L_Id−m_Id) mod (2 ^ m−1) <(H_Id−m_Id) mod (2 ^ m−1) (Expression 6)

  Here, the congruence equation mod is a kind of equation defined by classifying integers using the divisor relation. Judges whether the remainder when divided by a certain natural number is equal.

  In step S1701, if the logical identifier range IdRanges does not include the successor logical identifier s, the processing proceeds to step S1705 without executing the processing in steps S1701 to S1704.

  Next, the logical identifier range dividing unit 1015 determines whether the logical identifier range LowRanges close to the peer m is Null (0) (step S1702). When the logical identifier range LowRanges close to the peer m is not Null (0) (N in Step S1702), the logical identifier range dividing unit 1015 searches the local data storage unit 1011 for data that matches the search formula (Step S1702). S1703). This is because when the logical identifier range LowRanges close to the peer m is not Null (0), the range between the peer m and the successor is a range managed by the peer m. On the other hand, when the logical identifier range LowRanges close to the peer m is Null (0) (Y in step S1702), the process proceeds to step S1704 without executing the process in step S1703.

  In step S1704, the logical identifier range dividing unit 1015 substitutes HighRanges for the remaining logical identifier range Residual (remaining logical identifier range that has not yet been searched) (step S1704). When the process of step S1703 is executed, a logical identifier range (HighRages) obtained by excluding the ranges of the peer m and the successor from the logical identifier range IdRanges is substituted into the remaining logical identifier range Residual.

  Next, the logical identifier range dividing means 1015 includes the Finger (the logical identifier 1, 2, 4,..., The previous logical identifier, or the logical identifier 1, 2, 2, etc. stored in the routing table (FingerTable) 1012. 4,... If there is no previous logical identifier, the closest logical identifier larger than those logical identifiers) is read in the order away from the peer m (step S1705).

  Then, the logical identifier range dividing unit 1015 divides the remaining logical identifier range Residual into two logical identifier ranges LowRanges and HighRanges according to the logical identifier of the finger searched in step S1705 (step S1706).

  Then, the logical identifier range dividing unit 1015 determines whether or not the logical identifier range HighRanges far from the peer m is Null (0) (step S1707). When the logical identifier range HighRanges far from the peer m is not Null (0) (N in step S1707), a process for searching for multiple logical identifier ranges IdRanges is executed in the peer Finger (step S1708). That is, the processing of steps S1701 to S1709 shown in FIG.

  On the other hand, when the logical identifier range HighRanges far from the peer m is Null (0) (Y in step S1707), the process proceeds to step S1709 without executing the process in step S1708.

  In step S1709, the logical identifier range dividing unit 1015 substitutes LowRanges for the remaining logical identifier range Residual (step S1709). Then, the process ends.

  As described above, according to the third embodiment, since the distribution information (distribution function) of a plurality of dimensions is managed and the logical identifier is calculated based on this distribution, the logical identifier for transferring the search request (search message) Can be narrowed.

  Further, according to the third embodiment, the process of converting a plurality of attributes into one dimension is performed in the message transfer process, not via a specific peer (for example, a peer in charge of logical identifier 0 or 1). Since the conversion process is completed in the search request peer and the message is transferred to the set of calculated logical identifiers, the search request transfer load is not concentrated on a specific peer.

  In addition, according to the third embodiment, when calculating the logical identifier of a plurality of attributes, the uniformity of the value is ensured. This also prevents the data management load from being concentrated on a specific peer. is doing.

  Furthermore, according to the third embodiment, the range of logical identifiers to be searched is divided in the middle of transfer and parallelized, so that the number of search request hops does not increase even when the search range is wide. Can do.

  Next, a specific example of the configuration in the third embodiment will be described with reference to FIGS. FIG. 18 is a diagram showing a data structure for deriving a logical identifier range list from a search expression. FIG. 19 is a diagram illustrating an example in which a search message is transferred to a peer corresponding to a logical identifier range list derived by a search expression.

  In the overlay management system according to the third embodiment, it is assumed that data having two attributes x and y are shared and each data is distributed in the value indicated by the coordinate 1860 in FIG. The peer shown in FIG. 19 (the peers of logical identifiers 0, 4, 15, 20, 27, 30, 32, 40, and 56) participates in the overlay management system, and the size of the logical identifier space (the hash space Size) is 64. Further, data registration and search are performed by a peer 1909 having a logical identifier 0 in FIG. The peer routing table 1012 stores the IP address of the peer 1901 having the logical identifier 4 as the successor 1921. Further, as the Finger 1922, the peer having the logical identifier for the first time in the clockwise direction of the logical identifier obtained by adding the i-th power of 2 (i = 0, 1, 2, 3, 4, 5) to the logical identifier 0 of the peer 1909. Information is stored. In this case, the IP address of the peer 1901 is stored for i = 0, 1, 2 and the IP address of the peer 1902 is stored for i = 3. Similarly, the information of the peers 1903 and 1906 is stored for i = 4 and 5.

(1) Data registration;
First, as an example at the time of data registration execution, it is assumed that the registration search receiving unit 1018 registers data (011, 111) having an x attribute value of 011 and a y attribute value of 111. This data registration request is converted into a logical identifier corresponding to this data by the space filling curve conversion means 1017. The space filling curve means 1017 acquires a space filling curve distribution function corresponding to the attribute x and the attribute y from the space filling curve distribution storage unit 1016. Here, it is assumed that functions 1840 in FIG. 18 and 1113 in FIG. 11 are acquired.

  Next, assuming that the space filling curve is a Hilbert space filling curve, a logical identifier corresponding to the data (011, 111) is acquired using this conversion rule. First, the first bit is acquired and becomes a bit pattern 01 generated from x attribute 0 and y attribute 1 and stored. Next, since the state next to the bit pattern 01 of the state 0 (1811 in FIG. 18) is 0 (1821 in FIG. 18), the conversion rule corresponding to this state is applied to the second bit. The second bit is the bit pattern 11 generated from the x attribute 1 and the y attribute 1, and the conversion rule 1822 is applied to the bit pattern 11 to obtain “10”. By combining this with the bit string of the first layer, “0110” becomes the key. Similarly, when applied up to the third bit, “011010” (26 in decimal notation) becomes Key. When this is applied to the space filling curve distribution function D (k), it becomes 0.4, and from this and the size 64 of the logical identifier space, the logical identifier becomes 25.

  Next, a registration message is transferred to this logical identifier. The transfer method here is the Chord method, but since Finger 1922 is the peer 1903 having the logical identifier 20 in the counterclockwise direction closest to the target logical identifier 25, the logical identifier of the successor is assigned to this peer 1903. Inquire. Since the peer 1903 returns 27 as the logical identifier, and the target logical identifier 25 is a number existing between the logical identifier 20 of this Finger and the successor 27, the peer 1904 having this logical identifier 27 is assigned to the logical identifier 25. It is determined that the peer manages the data (011, 111), and the data is stored in the local data storage unit 1011 of the peer.

(2) Data search;
Next, as an example at the time of data search execution, it is assumed that the registration search reception means 1018 has executed 011 complete match search for the x attribute and 1 ** forward match search for the y attribute. This search request is converted into a corresponding logical identifier list by the space filling curve conversion means 1017. The space filling curve conversion unit 1017 acquires a space filling curve distribution function corresponding to the attribute x and the attribute y from the space filling curve distribution storage unit 1016. Here, it is assumed that functions 1840 in FIG. 18 and 1113 in FIG. 11 are acquired.

  Next, assuming that the space filling curve is a Hilbert space filling curve, a logical identifier range list corresponding to the search expression (011, 1 **) is acquired using this conversion rule. First, the first bit is acquired, and the conversion rule is applied to the bit pattern 01 generated from the x attribute 0 and the y attribute 1 so that “01” (1813 in FIG. 18) becomes “01” (in FIG. 18). From the rule converted to 1812), the bit pattern after the one-dimensional conversion is 01, which is stored.

  Next, since the state next to the bit pattern 01 of the state 0 (1811 in FIG. 18) is 0 (1821 in FIG. 18), the conversion rule corresponding to this state is applied to the second bit. The second bits are bit patterns 00 and 01 generated from * (arbitrary bit) of 0 and y attributes of the x attribute. Conversion rules are applied to each of the bit patterns, and “10” and “11”. Is obtained. This is combined with the bit string of the first layer, and “0110” and “0111” are the keys after one-dimensional conversion up to the second layer. Similarly, when applying up to the third bit, “011010”, “011011”, “011100”, “011111” is a set of keys, and the range is that the starting point of the first KeyRange is “011010” and the end point is “011100”. ", And the start and end points of the second KeyRange are" 011011 ". By applying these to the space filling curve distribution function D (k), a logical identifier range list 1843 is obtained. Here, [0.40, 0.45] and [0.525, 0.525] are obtained as the application result of D. From this and the size 64 of the logical identifier space, the logical identifier range list is {[ 25, 28], [33, 33]}.

  Next, the search message is transferred to the logical identifiers included in these ranges, and the search result is acquired. First, after initializing a list for storing search results and starting a process for receiving results from other peers, the message transfer means 1013 in the peer 1909 is called to search for this logical identifier range list.

  First, these range lists are divided with the logical identifier 4 of the successor of the peer 1909 as a boundary, but the destination range list {[25, 28], [33, 33]} is in (0, 4). Since it does not exist, the destination range is not found here.

  Next, when the logical identifier 32 of the farthest Finger peer 1906 is divided as a boundary, the range list is divided into {[25, 28]} and {[33, 33]}, and the range list {[33, 33]}. Is forwarded to peer 1906 and the range list {[25, 28]} is forwarded to peer 1903. The range list {[33, 33]} transferred to the peer 1906 is divided on the boundary of the logical identifier 40 of the peer 1907 that is the successor of the peer 1906, but all {[33, 33]} are (32, 40). The peer 1907 is determined to be a peer managing the range [33, 33], and the local data storage unit 1011 of the peer is searched, and the range list transferred to the peer 1903 {[ 25, 28]} is divided by the logical identifier 27 of the peer 1904, which is the successor of the peer 1903, and the logical identifier range {[25, 27]} included in (20, 27] is stored in the peer 27 as local data. The part 1011 is requested to be searched, and the range {(27, 28]} not included is transferred to the finger.

  Here, because the range {(27, 28]} transferred to the peer 1904 that is also a finger exists between the logical identifier 27 of the peer 1904 and the logical identifier 30 of the peer 1905 that is the successor. , The peer 1905 is requested to search the local data storage unit 1011.

  The search results for the local data storage unit 1011 executed by the peers 1904, 1905, and 1907 are transmitted to the search request source 1909, and the search result reception process of the search request source 1909 receives this result and makes all the requests. When a search result is obtained from the logical identifier range list {[25, 28], [33, 33]}, or when the Timeout period elapses, the search process ends.

  In the first and third embodiments, the method of performing range search by making the distribution of multi-dimensional attribute values uniform in one dimension in the overlay network based on Chord has been disclosed. In other methods called Structured Peer-to-Peer where the peer has a logical identifier, the same effect can be obtained by the same method. This is not limited to overlay networks with a one-dimensional logical identifier space, but for overlay networks with a multi-dimensional logical identifier, it is converted from one dimension to multidimensional again using a space-filling curve after uniformizing to one dimension. By doing so, the same effect can be obtained.

  In each of the above first to third embodiments, the peer is realized by a computer (terminal) such as a server or a personal computer. Further, in each peer, a control unit such as a CPU executes each process described in the first to third embodiments in accordance with a program (overlay management program) stored in a storage unit such as a hard disk. ) Is realized. In each peer, a storage unit, a table, and the like are realized by storage means such as a hard disk.

  The present invention can be applied to a relational database that shares data over a wide area. In particular, the present invention can be applied to uses such as storage of radio frequency identifier (RFID) data, storage of logs in system operation management, storage of e-mails and Web pages, storage of social network service (SNS) data, and the like.

1 is a block diagram showing a configuration of an overlay management system in Embodiment 1. FIG. It is a table figure which shows the example of the attribute name and distribution function of each attribute. 6 is an explanatory diagram illustrating a specific example of a message flow between peers in Embodiment 1. FIG. FIG. 6 is a sequence diagram showing an operation of the overlay management system in the first embodiment. It is explanatory drawing which shows the relationship between an attribute value and a distribution function. FIG. 10 is a block diagram showing a configuration of an overlay management system in a second embodiment. It is a figure which shows the specific example which divides | segments Cluster using a space filling curve. 10 is an explanatory diagram showing a specific example of a message flow between peers in Embodiment 2. FIG. FIG. 10 is a sequence diagram showing an operation of the overlay management system in the second embodiment. FIG. 10 is a block diagram showing a configuration of an overlay management system in a third embodiment. It is a table figure which stores space filling curve distribution for every set index of a plurality of attributes. It is explanatory drawing which shows the data structure which represents the algorithm of the process which converts 2-dimensional data into 1-dimensional data using a space filling curve. 10 is a flowchart illustrating a process of registering data shared in the overlay network according to the third embodiment. It is a flowchart which shows the process of the subroutine of step S1301. 10 is a flowchart showing processing for searching for data to be shared in the overlay network in the third embodiment. It is a flowchart which shows the process of the subroutine of step S1501. It is a flowchart which shows the process of the subroutine of step S1504. It is a figure which shows the data structure which derives | leads-out a logical identifier range list | wrist from a search formula. It is a figure which shows the example which transfers a search message to the peer corresponding to the logical identifier range list induced | guided | derived with the search expression.

Explanation of symbols

110, 120, 130 Peer 111 Local data storage unit 112 Routing table 113 Message transfer unit 117 Individual attribute distribution function storage unit 118 Registration / search execution unit 510, 520, 530 Peer 511 Local data storage unit 512 Routing table 513 Message transfer unit 517 Space filling curve conversion means 518 Registration / search execution means 1010, 1020, 1030 Peer 1011 Local data storage unit 1012 Routing table 1013 Message transfer means 1015 Logical identifier range division means 1016 Space filling curve distribution storage part 1017 Space filling curve conversion means 1018 registration・ Search execution means

Claims (20)

An overlay management device arranged on an overlay network and managing data shared with other devices,
One-dimensionalization means for converting multi-attribute data into one-dimensional values;
Identifier generating means for generating a logical identifier by applying a function including value distribution information to the value one-dimensionalized by the one-dimensionalizing means;
A management device specifying means for specifying another device that manages the logical identifier generated by the identifier generating means based on the assignment of the logical identifier to each device on the overlay network;
An overlay management apparatus comprising: a data registration unit that executes a process of registering data in the other apparatus identified by the management apparatus identification unit. A search condition one-dimensionalization means for converting a search condition of multiple attributes into a set of one-dimensional values;
Identifier range generation means for generating a set of logical identifier ranges by applying a function including value distribution information to the elements in the set of values one-dimensionalized by the search condition one-dimensionalization means;
The overlay management apparatus according to claim 1, further comprising search request transfer means for searching for data by transferring a set of logical identifier ranges generated by the identifier range generation means as a search request to another apparatus. Logical identifier range dividing means for dividing a set of logical identifier ranges based on logical identifier assignment to each device on the overlay network;
The overlay management apparatus according to claim 2, wherein the search request transfer unit searches for data by transferring a set of logical identifier ranges divided by the logical identifier range dividing unit to another apparatus as a search request. The one-dimensionalization means or the search condition one-dimensionalization means converts the data of multiple attributes into a one-dimensional value or a set of values using a space filling curve,
The identifier generating means or the identifier range generating means applies a space filling curve distribution function that equalizes a one-dimensional value or a set of values in the space filling curve from a one-dimensional value or a set of values. The overlay management apparatus according to claim 1, wherein a set of logical identifiers or ranges thereof is generated. The overlay management apparatus according to claim 3 or 4, wherein the logical identifier range dividing means divides the set of logical identifier ranges based on the logical identifier stored in the routing table. An overlay management system comprising a plurality of terminals arranged on an overlay network and managing data shared between the terminals,
Each terminal is
One-dimensionalization means for converting multi-attribute data into one-dimensional values;
Identifier generating means for generating a logical identifier by applying a function including value distribution information to the value one-dimensionalized by the one-dimensionalizing means;
Management terminal specifying means for specifying other terminals that manage the logical identifier generated by the identifier generating means based on the assignment of the logical identifier to each terminal;
An overlay management system comprising: a data registration unit that executes a process of registering data in the other terminal identified by the management terminal identification unit. Each terminal
A search condition one-dimensionalization means for converting a search condition of multiple attributes into a set of one-dimensional values;
Identifier range generation means for generating a set of logical identifier ranges by applying a function including value distribution information to the elements in the set of values one-dimensionalized by the search condition one-dimensionalization means;
7. The overlay management system according to claim 6, further comprising search request transfer means for searching for data by transferring a set of logical identifier ranges generated by the identifier range generation means as a search request to another terminal. Logical identifier range dividing means for dividing a set of logical identifier ranges based on assignment of logical identifiers to each terminal;
8. The overlay management system according to claim 7, wherein the search request transfer unit searches for data by transferring a set of logical identifier ranges divided by the logical identifier range dividing unit to another terminal as a search request. The one-dimensionalization means or the search condition one-dimensionalization means converts the data of multiple attributes into a one-dimensional value or a set of values using a space filling curve,
The identifier generating means or the identifier range generating means applies a space filling curve distribution function that equalizes a one-dimensional value or a set of values in the space filling curve from a one-dimensional value or a set of values. The overlay management system according to claim 6, wherein a set of logical identifiers or ranges thereof is generated. The overlay management system according to claim 8 or 9, wherein the logical identifier range dividing means divides a set of logical identifier ranges based on the logical identifier stored in the routing table. The control unit of the management device arranged on the overlay network follows the control program,
Convert multi-attribute data into one-dimensional values,
A logical identifier is generated by applying a function including value distribution information to a one-dimensional value,
Based on the logical identifier assignment for each device on the overlay network, identify other devices that manage the generated logical identifier,
An overlay management method, comprising: performing a process of registering data in the specified other device. The control unit of the management device arranged on the overlay network follows the control program,
Convert multi-attribute search conditions into a one-dimensional set of values,
Apply a function containing value distribution information to the elements in the one-dimensional value set to generate a set of logical identifier ranges,
The overlay management method according to claim 11, wherein data search is performed by transferring the generated set of logical identifier ranges to another apparatus as a search request. Based on the logical identifier assignment for each device on the overlay network, the set of logical identifier ranges is divided,
13. The overlay management method according to claim 12, wherein data is searched by transferring a set of divided logical identifier ranges as a search request to another device. Transform multi-attribute data into a one-dimensional value or set of values using a space-filling curve,
Applying a space-filling curve distribution function that equalizes a one-dimensional value or set of values in the space-filling curve to generate a logical identifier or a set of ranges thereof from the one-dimensional value or set of values The overlay management method according to any one of claims 11 to 13. The overlay management method according to claim 13 or 14, wherein a set of ranges of logical identifiers is divided based on logical identifiers stored in a routing table. An overlay management program for managing data shared by a management device arranged on an overlay network with other devices,
One-dimensional processing that converts multi-attribute data into one-dimensional values;
An identifier generation process for generating a logical identifier by applying a function including value distribution information to a one-dimensional value;
A management device specifying process for specifying another device that manages the generated logical identifier based on the assignment of the logical identifier to each device on the overlay network;
An overlay management program for causing the management device to execute data registration processing for executing processing for registering data in the specified other device. A search condition one-dimensionalization process that converts a search condition of multiple attributes into a set of one-dimensional values,
An identifier range generation process for generating a set of logical identifier ranges by applying a function including value distribution information to elements in the one-dimensional value set;
The overlay management program according to claim 16, wherein the management device executes search request transfer processing for searching for data by transferring a set of generated logical identifier ranges to another device as a search request. Based on the assignment of the logical identifier to each device on the overlay network, causes the management device to execute a logical identifier range dividing process for dividing a set of logical identifier ranges,
18. The overlay management program according to claim 17, wherein, in the search request transfer process, data is searched by transferring a set of divided logical identifier ranges as a search request to another device. In one-dimensional processing or search condition one-dimensional processing, data of multiple attributes is converted into a one-dimensional value or set of values using a space filling curve,
In the identifier generation process or the identifier range generation process, from a value or value set that has been made one-dimensional by applying a space-filling curve distribution function that equalizes the one-dimensional value or value set in the space-filling curve. The overlay management program according to any one of claims 16 to 18, wherein a set of logical identifiers or ranges thereof is generated. 20. The overlay management program according to claim 18 or 19, wherein, in the logical identifier range dividing process, a set of logical identifier ranges is divided based on the logical identifier stored in the routing table.