JP5915522B2 - Adjacent node selection method, node, and program - Google Patents

Description

  The present invention relates to an adjacent node selection method, a node, and a program used when configuring a distributed hash table.

  A distributed hash table (DHT) is widely used in order to realize efficient data retrieval in fields such as a peer-to-peer (P2P) network and a distributed database.

  In a search using DHT, a hash value is generated from a data search target keyword using a hash function, and data is stored for each node corresponding to the hash value. When searching for data, a hash value is generated from the search target keyword using a hash function, and only the node corresponding to the hash value is searched. As examples of the DHT protocol, Chord, Pastry, Tapestry, CAN (Content Addressable Network), and the like are widely known. In these DHT protocols, a node selects an adjacent node based on a node ID (ID: identifier) according to a predetermined rule. Here, “adjacent node” refers to a node connected to the own node.

  Here, the node ID is assigned regardless of the proximity (that is, the magnitude of the delay) between the nodes. For this reason, nodes that are close (that is, have a small delay) are not necessarily selected as adjacent nodes. Therefore, there is a problem that the end-to-end delay at the time of data search may increase.

  In order to deal with such a problem, as disclosed in Patent Document 1, there is also a method of assigning a node ID itself based on the proximity of the node to reduce a delay in end-to-end search. However, such a method can be applied to a DHT protocol in which a node ID is mapped in an n-dimensional orthogonal coordinate space such as CAN and there is no shortcut link. The above method cannot be applied to a DHT protocol such as Chord or Tapestry that takes a ring structure or a Plaxton structure.

  Therefore, in a DHT protocol such as Chord or Tapestry that takes a ring structure or a Platton structure, as a technique for shortening a search delay, a proximity-based adjacent node selection method (PNS) disclosed in Non-Patent Document 1 or the like is disclosed. Proximity Neighbor Selection) has been proposed. PNS is a method of selecting a candidate node with the shortest delay as an adjacent node when an adjacent node can be selected from a plurality of candidates. By reducing the delay of each hop as much as possible in this way, the effect of reducing the end-to-end delay at the time of retrieval can be obtained.

  A method for realizing PNS in Chord will be described with reference to FIGS. 8A and 8B. In Chord, a node (node n) having an ID of n selects an adjacent node (referred to as finger in Chord) from the area shown in Expression (1).

However, i is a natural number not more than the maximum bit length of ID. ID indicates the ID of an adjacent node.
In a normal Chord protocol that does not perform PNS, the node n selects a node having the smallest ID among the nodes having an ID greater than n + 2i−1 as an adjacent node in the area shown in Expression (1). FIG. 8A shows a method for selecting an adjacent node in the normal Chord protocol.
On the other hand, when performing PNS in Chord, node n selects the node with the smallest delay from its own node as an adjacent node in the area shown in Equation (1). FIG. 8B shows a method for selecting an adjacent node in the Chord protocol when PNS is applied.

  As a peer-to-peer information transfer technique, Patent Document 2 describes the following technique. The information transfer device of Patent Document 2 measures a logical distance, which is a distance that can be changed according to a message attribute, between a communication unit that transmits and receives a message to and from a transfer destination node and a destination node. A logical distance storage unit that stores the logical distance measured by the distance measurement unit and the logical distance measurement unit in association with the attribute of the message, the identification code of the destination node, and the network address of the destination node; A forwarding destination determination unit that determines a forwarding destination node of a message using a logical distance according to a destination node of the forwarding message and an attribute of the message. By adopting such a configuration, the message transfer is made efficient according to the attribute of the message. In the technique described in Patent Document 2, each node needs to measure a physical distance, and each node needs to output the physical distance to a storage unit.

Japanese Unexamined Patent Publication No. 2008-299586 Japanese Unexamined Patent Publication No. 2009-218728

K. Gummadi, R.A. Gummadi, S.M. Gribble, S.M. Ratnasamy, S .; Shenker, I.D. Stoica, “The Impact of DHT Routing Geometry on Resilience and Proximity”, Proceedings of the 2003 SIGCOMM, August 2003

  As described above, PNS is an effective method for reducing the end-to-end delay at the time of data search in the DHT protocol such as Chord and Tapestry that adopts a ring structure or a Plaxton structure. However, in order to realize an ideal PNS, it is necessary to know all the nodes existing in the region shown in Expression (1). In addition, it is necessary to measure delay to each node. For this reason, overhead is required. Therefore, it is difficult to realize an ideal PNS.

An object of the present invention is to provide an adjacent node selection method, a node, and a program that can solve the above-described problems.
According to the present invention, for each predetermined identifier area of an identifier for identifying each node participating in the distributed hash table protocol, information related to an adjacent node is stored in a receiving node, and a message including information related to a transmitting node is stored in the receiving node. Receiving and deriving a first communication environment between the transmitting node and the receiving node at the receiving node based on the information regarding the transmitting node, the information regarding the neighboring node and the information regarding the transmitting node And the receiving node derives a second communication environment between the current adjacent node selected as the current adjacent node for the identifier region corresponding to the transmitting node and the receiving node, and the first communication An environment and the second communication environment are compared at the receiving node, and the first communication environment is compared with the second communication environment. If it is good, a neighbor node selection method to replace the current neighbor node selected as the current neighbor node for the identifier region corresponding to the transmitting node by the transmitting node, the first communication environments and the The second communication environment is a delay time between nodes, and for each site participating in the distributed hash table protocol, a site that is a group composed of nodes existing in the same management domain, A site identifier for identifying a site is assigned, and the information about the adjacent node includes a site identifier assigned to a site to which the adjacent node belongs and an identifier for identifying the adjacent node, The delay time from the site to which each node belongs to each other site is maintained, and the message Includes, as the information on the transmitting node, a first site identifier assigned to a first site to which the transmitting node belongs and a first identifier that identifies the transmitting node, wherein the receiving node The first site identifier and the first identifier are extracted, and based on the held delay time, the second site and the first site to which the receiving node to which the second site identifier is assigned belong A first delay time between the second site and the third site to which the current adjacent node belongs based on the held delay time. A delay time is obtained, and the receiving node compares the first delay time with the second delay time, and when the first delay time is smaller than the second delay time, the transmission node This is an adjacent node selection method in which the second identifier of the current adjacent node currently stored as the adjacent node for the identifier region corresponding to the node is replaced with the first identifier .

In addition, the present invention receives, for each predetermined identifier area of an identifier for identifying each node participating in the distributed hash table protocol, a storage unit that stores information related to an adjacent node, and a message that includes information related to a transmission node. A message receiving unit, a first communication environment deriving unit for deriving a first communication environment between the transmitting node that is a transmission source of the message and the own node based on the information about the transmitting node; Based on the information on the neighboring node and the information on the sending node, a second communication environment between the current neighboring node selected as the current neighboring node and the own node is derived for the identifier region corresponding to the sending node. A second communication environment deriving unit that compares the first communication environment with the second communication environment, and compares the first communication environment with the first communication environment. Node There comprising said if it is better than the second communication environment, replacing the current neighbor node selected as the current neighbor node for the identifier region corresponding to the transmitting node by the transmitting node adjacent node selection unit The first communication environment and the second communication environment are delay times between nodes, and the nodes existing in the same management domain among the nodes participating in the distributed hash table protocol. A site identifier for identifying the site is assigned to a site that is a group to be configured, and the information on the adjacent node specifies the site identifier assigned to the site to which the adjacent node belongs and the adjacent node. The self-node has a delay from the site to which it belongs to each other site. Time is retained, and the message includes, as the information about the transmitting node, a first site identifier assigned to a first site to which the transmitting node belongs and a first identifier that identifies the transmitting node; The first communication environment deriving unit extracts the first site identifier and the first identifier from the message, and the own node to which the second site identifier is allocated is based on the held delay time. A first delay time between the second site to which the first site belongs and the first site is obtained, and the second communication environment deriving unit determines whether the second node to which the current adjacent node belongs is based on the held delay time. A second delay time between the third site and the second site, the adjacent node selection unit compares the first delay time with the second delay time, and When delayed A node that replaces the second identifier of the current adjacent node stored as the current adjacent node for the identifier region corresponding to the transmitting node with the first identifier when the interval is smaller than the second delay time is there.

The present invention also includes a step of storing information related to adjacent nodes for each predetermined identifier area of an identifier for identifying each node participating in the distributed hash table protocol, and a step of receiving a message including information related to a transmission node Deriving a first communication environment between the transmission node that is the transmission source of the message and the own node based on the information about the transmission node, the information about the adjacent node, and the transmission node Deriving a second communication environment between the current adjacent node and the current node selected as the current adjacent node for the identifier region corresponding to the transmitting node based on the information about the transmitting node; and the first communication Comparing the environment with the second communication environment, and wherein the first communication environment is the second communication If more boundary is good, a program for executing a step of replacing the current neighbor node selected as the current neighbor node for the identifier region corresponding to the transmitting node by the transmitting node to the computer, the first The first communication environment and the second communication environment are delay times between nodes, and are a group composed of nodes existing in the same management domain among the nodes participating in the distributed hash table protocol. A site identifier for identifying the site is assigned to the site, and the information regarding the adjacent node includes a site identifier assigned to the site to which the adjacent node belongs and an identifier for identifying the adjacent node, A node has a delay from the site to which it belongs to each other site. The message includes, as the information on the transmission node, a first site identifier assigned to a first site to which the transmission node belongs and a first identifier that identifies the transmission node, In the step of deriving one communication environment, the first node identifier and the first identifier are extracted from the message, and the own node to which the second site identifier is assigned based on the held delay time In the step of obtaining a first delay time between the second site to which the user belongs and the first site and deriving the second communication environment, the current adjacent node is based on the held delay time. Determining the second delay time between the third site to which the second site belongs and the second site, and comparing the first communication environment with the second communication environment, In the step of comparing the first delay time with the second delay time and replacing the current adjacent node with the transmitting node, when the first delay time is smaller than the second delay time, The program replaces the second identifier of the current adjacent node currently stored as the adjacent node for the identifier area corresponding to the transmission node with the first identifier .

  In the present invention, a node receives a message from another node and derives a communication environment between the node that has transmitted the message and its own node. If the communication environment between the transmission source node and the own node is better than the communication environment between the current adjacent node currently selected as the adjacent node and the own node, the current adjacent node is set as the transmission node. It is replaced with. In this way, a message is received from another node, and a node having a better communication environment with the own node is updated as an adjacent node. Therefore, it is possible to select an adjacent node with less overhead, which is an ideal PNS situation. You can get closer.

1 is a block diagram showing an overall configuration of a system according to a first embodiment of the present invention. It is explanatory drawing of an example of the adjacent node and coordinate table in the 1st Embodiment of this invention. It is a flowchart used for description of the 1st Embodiment of this invention. It is a block diagram which shows the whole structure of the system which concerns on the 2nd Embodiment of this invention. It is explanatory drawing of an example of the table of the delay between sites in the 2nd Embodiment of this invention. It is explanatory drawing of an example of the adjacent node site ID table in the 2nd Embodiment of this invention. It is a flowchart used for description of the 2nd Embodiment of this invention. It is explanatory drawing which shows the selection method of the adjacent node in a normal Chord protocol. It is explanatory drawing which shows the selection method of the adjacent node in Chord protocol at the time of applying PNS.

Hereinafter, embodiments of the present invention will be described with reference to the drawings.
<First Embodiment>
FIG. 1 is a block diagram showing the overall configuration of a system according to the first embodiment of the present invention. Referring to FIG. 1, the system according to the first embodiment of the present invention includes a node A1, a node A2, and a base network B1.

  The nodes A1 and A2 are connected to the base network B1. Note that the nodes A1 and A2 are configured similarly. Hereinafter, only the node A1 will be described in principle. In practice, a configuration in which a plurality of nodes exist in addition to the node A1 and the node A2 is generally used. However, here, for simplicity, the description will be made assuming that the node A2 exists on behalf of the other nodes of the node A1. In this embodiment, a case where Chord is used as the DHT protocol used by the nodes A1 and A2 will be described as an example.

  The node A1 includes a DHT protocol unit 11 and a TCP / IP (Transmission Control Protocol / Internet Protocol) communication unit 12. Similarly, the node A2 includes a DHT protocol unit 21 and a TCP / IP communication unit 22. The DHT protocol unit 11 includes a coordinate calculation unit 111, a message transmission unit 112, a message reception unit 113, a DHT protocol processing unit 114, a distance calculation unit 115, an adjacent node selection unit 116, and an adjacent node / coordinate storage unit. 117.

  The coordinate calculation unit 111 maps the position of the node A1 in the network to coordinates in a predetermined coordinate space based on a delay between nodes participating in the DHT protocol. That is, the coordinate calculation unit 111 calculates the coordinates of the approximate position in the network of the node A1 from the matrix of inter-node delays. Thus, when each node is mapped to the approximated coordinates, the delay between any two nodes can be estimated using the distance between the coordinates of these nodes. In addition, the coordinate calculation unit 111 holds the calculated coordinates of the node A1, and appropriately updates the coordinates.

As an example of the mapping method to such approximated coordinates, there is a method using coordinate calculation disclosed in the following reference (Vivaldi).
[References]
F. Dabek, R.A. Cox, F.M. Kaashhoek, R.A. Morris, “Vivaldi: A Decentralized Network Coordinate System,” In Proceedings of the 2004 SIGCOMM, August 2004.

  In Vivaldi, the current coordinates of node i and node j are pi (old) and pj (old), respectively, and the measured delay between node i and node j is rtt, the coordinate pi (new) of node i is Update according to equation (2).

  Here, δ is a constant and u is a unit vector. That is, Vivaldi employs an algorithm in which each node updates coordinates in an autonomous and distributed manner so that the difference between the inter-node delay and the inter-coordinate distance is minimized. In Vivaldi, it is assumed that Euclidean space or spherical coordinates are used as the coordinate system.

  The message transmission unit 112 has a function of transmitting a message in the DHT protocol. The message to be transmitted is transferred to another node via the TCP / IP communication unit 12. Examples of message types include a find_successor message that returns a node that manages a certain hash value and a search request (query) message in the case of Chord. Further, the message transmission unit 112 includes the coordinates of the node A1 and the node ID of the node A1 calculated by the coordinate calculation unit 111 in the message when the message is transmitted. Here, whether or not to include the coordinates of the node A1 and the node ID in the message may be changed according to the type of the message.

  The message receiving unit 113 has a function of receiving a message in the DHT protocol. The received message is delivered via the TCP / IP communication unit 12. When the received message contains information about coordinates (hereinafter referred to as “coordinate information”), the message receiving unit 113 receives the received coordinate information and node information corresponding to the coordinates indicated by the coordinate information. And the extracted information is passed to the distance calculation unit 115. In addition, the message receiving unit 113 passes a part other than the coordinate information and the node ID in the received message to the DHT protocol processing unit 114.

  The DHT protocol processing unit 114 has a function of performing protocol processing according to the type of message on the received DHT message. For example, in the Chord protocol, when a find_successor message (a message for finding the ID of a successor node of an ID included as a key) is received, the DHT protocol processing unit 114, based on the ID included as a key, transmits the message to an appropriate neighbor. A process of transferring to a node or returning a reply message is performed. When transferring a message including coordinate information, the DHT protocol processing unit 114 transfers the message as it is including the coordinate information. When a protocol other than the Chord protocol is used, the DHT protocol processing unit 114 performs processing according to the protocol used.

  The distance calculation unit 115 calculates the distance between the own node and the node that first transmitted the message based on the coordinate information extracted by the message reception unit 113. If the node A2 transmits a message including coordinate information, the distance calculation unit 115 calculates the distance from the coordinates of the node A2 and the coordinates of the node A1 held in the coordinate calculation unit 111. Determine the distance between. Assuming that the coordinate system is a two-dimensional Euclidean space and the coordinates of the node A1 and the node A2 are (xi, yi) and (xj, yj), respectively, the distance d is obtained according to the equation (3).

  The distance calculation unit 115 passes the calculated distance to the adjacent node selection unit 116 together with the ID of the node A2 (that is, the ID of the node that transmitted the message including the coordinate information).

The adjacent node selection unit 116 sets the ID of the node (hereinafter referred to as “transmission node”) that has passed the message including the coordinate information passed from the distance calculation unit 115 and the distance between the transmission node and the own node. Based on this, it is determined whether to select the transmitting node as an adjacent node. Here, whether or not to select the transmission node as an adjacent node is determined as follows, for example.
First, the adjacent node selection unit 116 refers to the current adjacent node list held in the adjacent node / coordinate storage unit 117 to obtain information on the current adjacent node in the area corresponding to the ID of the transmission node. Then, the adjacent node selection unit 116 calculates the distance between the current adjacent node and the own node in the corresponding region, and compares the calculated distance with the distance between the transmission node and the own node. To do. If the distance between the transmission node and the own node is smaller, the adjacent node selection unit 116 determines that the transmission node is selected as an adjacent node, and replaces the current adjacent node in the corresponding area with the transmission node. When replacing the current adjacent node with the transmission node, the adjacent node selection unit 116 rewrites the information on the adjacent node in the adjacent node / coordinate storage unit 117 with the information on the transmission node. On the other hand, when the distance between the transmitting node and the own node is not smaller, the adjacent node selection unit 116 determines that the transmitting node is not selected as an adjacent node, and the adjacent node remains as it is.

The adjacent node / coordinate storage unit 117 holds the current adjacent node in the node A1 in a list format. An example of information held in the adjacent node / coordinate storage unit 117 is shown in FIG.
FIG. 2 shows an adjacent node / coordinate table 101 held in the adjacent node / coordinate storage unit 117. Referring to the adjacent node / coordinate table 101 in FIG. 2, information on the currently selected adjacent node (finger) is shown for each area (“ID area” in the figure) for selecting an adjacent node in Chord. In the example of the adjacent node / coordinate table 101, a two-dimensional Euclidean space is used as the coordinate system, and the ID of the node A1 is n. From FIG. 2, it can be seen that the ID region corresponding to the first adjacent node is as shown in Expression (4), ID = n1, and its coordinates are (x1, y1).

  Similarly, 2nd to 4th adjacent node information and corresponding coordinates are shown. There are m entries in the adjacent node / coordinate table 101 where m is the maximum ID bit length.

  Here, since Chord is taken as an example of the DHT protocol, an adjacent node is selected for each predetermined ID area. On the other hand, in the case of the DHT protocol having a Plotton structure such as Tastry or Pastry, an adjacent node is selected from nodes having the same ID prefix (or suffix). Here, adjacent nodes are selected for each length of the same prefix (or suffix). Therefore, in the case of the DHT protocol having the Platton structure, the ID area is composed of ID groups having the same prefix (or suffix).

  The TCP / IP communication unit 12 has a function of performing communication with other nodes using the TCP / IP protocol. The TCP / IP stack provided in the OS (Operating System) of the node A1 corresponds to the TCP / IP communication unit 12.

  The base network B1 is a network to which the node A1 and the node A2 are connected, and enables communication between any two nodes.

  Next, with reference to FIG. 3, the operation when the node A1 receives a message from another node A2 in the first embodiment of the present invention will be described in detail. FIG. 3 is a flowchart showing an operation when the node A1 receives a message from the node A2, which is another node, in the first embodiment of the present invention. In this operation example, it is assumed that a two-dimensional Euclidean space is used as a coordinate system of coordinates possessed by each node.

  First, the message receiving unit 113 of the node A1 receives a message from the node A2 (step S101). Next, the message receiving unit 113 checks whether coordinate information is included in the message received in step S101 (step S102).

  When it is determined in step S102 that the coordinate information is included in the message (step S102: YES), the message receiving unit 113 displays the included coordinate information and the node information corresponding to the coordinates (that is, the node of the node A2). ID) is extracted from the received message, and the extracted information is passed to the distance calculation unit 115 (step S103). If it is determined in step S102 that the coordinate information is not included in the message (step S102: NO), the process of the node A1 proceeds to step S107 described later.

  After step S103, the distance calculation unit 115 calculates the distance between the own node and the node A2 according to the equation (3) based on the coordinate information extracted in step S103, and the calculated result together with the ID of the node A2. The data is passed to the adjacent node selection unit 116 (step S104).

  Next, the adjacent node selection unit 116 refers to the adjacent node / coordinate storage unit 117, and in the ID area corresponding to the node A2, the distance between the node currently selected as the adjacent node and the own node, The distance between the node calculated in S104 and the node A2 is compared (step S105).

  In step S105, when the distance between the node A2 calculated in step S104 and the own node is smaller than the current distance between the adjacent node and the own node (step S105: YES), the adjacent node selection unit 116 The adjacent node currently selected in the ID area corresponding to A2 is replaced with node A2 (step S106). On the other hand, when the distance between the node A2 and the own node is greater than or equal to the current distance between the adjacent node and the own node in step S105, the adjacent node selection unit 116 keeps the adjacent node current. Then, the process of the node A1 moves to step S107.

  After step S106, the message receiving unit 113 passes the portion other than the coordinate information and the node ID in the received message to the DHT protocol processing unit 114. The DHT protocol processing unit 114 performs protocol processing according to the type of message (step S107).

  In the example described above, when coordinate information is included in the received message, the node corresponding to the coordinate is the node A2 that transmitted the message to the node A1.

  However, the coordinate information of nodes other than the node A2 may be included in the message. For example, when a node other than the node A2 (hereinafter referred to as node X) transmits a message first, and the node A2 forwards the message to the node A1, the coordinate information of the node X is included in the message. include. Therefore, in such a case, the message receiving unit 113 extracts the node ID of the node X as the node ID corresponding to the coordinate information.

  Next, effects of the first exemplary embodiment of the present invention will be described. In the first embodiment of the present invention, each node calculates the coordinates of its own node based on the delay between the nodes, and transmits the coordinates and the node ID of its own node included in a message in the DHT protocol. Then, the node that has received the message including the coordinates of the transmitting node calculates the distance between the transmitting node and its own node from the coordinates of these nodes, and the calculated distance corresponds to the ID of the transmitting node. If it is smaller than the distance between the adjacent node currently adjacent in the ID area and the own node, the adjacent node is replaced with the transmitting node.

  As a result of the processing described above, message reception from other nodes can be an opportunity to update a node closer to the own node as an adjacent node. Therefore, it can be expected that the closer to an ideal PNS situation, the more messages are received from more nodes.

<Second Embodiment>
Next, a second embodiment of the present invention will be described in detail with reference to the drawings. FIG. 4 is a block diagram showing an overall configuration of a system according to the second embodiment of the present invention. Similar to the first embodiment of the present invention shown in FIG. 1, the system according to the second embodiment of the present invention includes a base network B1, and a node A3 and a node A4 connected to the base network B1. I have.

  In this embodiment, the case where the DHT protocol used by the node A3 and the node A4 is Chord will be described as an example. Node A3 and node A4 have the same configuration. Hereinafter, only the node A3 will be described in principle.

  Referring to FIG. 4, the node A3 includes a DHT protocol unit 31 and a TCP / IP communication unit 32. Similarly, the node A4 includes a DHT protocol unit 41 and a TCP / IP communication unit 42. The TCP / IP communication unit 32 has the same function as that of the TCP / IP communication unit 12 described in the first embodiment, and performs the same operation as the TCP / IP communication unit 12, so detailed description thereof is omitted. To do.

  The DHT protocol unit 31 includes an inter-site delay storage unit 311, a message transmission unit 312, a message reception unit 313, a DHT protocol processing unit 314, a delay calculation unit 315, an adjacent node selection unit 316, and an adjacent node / site. An ID storage unit 317.

  The DHT protocol processing unit 314 has the same function as that of the DHT protocol processing unit 114 shown in the first embodiment and performs the same operation as the DHT protocol processing unit 114, and thus detailed description thereof is omitted.

  The inter-site delay storage unit 311 stores a delay from the site to which the node belongs to another site. Here, a site is a group composed of nodes that are close to each other (for example, nodes that exist in the same management domain). Specifically, an AS (Autonomous System) in an IP network, a base in a VPN (Virtual Private Network), or the like is used as a site unit, and each node belongs to one site. For example, when AS is used as a unit of site, nodes belonging to the same AS are treated as belonging to the same site. Each site is assigned a unique ID (site ID). Further, as a method of knowing the delay from the site to which the own node belongs to another site, there is a method of measuring the delay from the representative node of the own node to the representative node in each site in advance or periodically.

  An example of the inter-site delay table stored in the inter-site delay storage unit 311 is shown in FIG. Referring to FIG. 5, an inter-site delay table 102 is shown, showing a delay from the site to which the own node (node A3) belongs to another site. For example, the node A3 belongs to the site “3”, the node belonging to the site “1” has a delay of 100 msec, the node belonging to the site “2” has a delay of 20 msec, and the own site (site “3”) It can be seen that there is a 1 msec delay for nodes belonging to, and a 50 msec delay for nodes belonging to site “4”.

  The message transmission unit 312 has a function of transmitting a message according to the DHT protocol, like the message transmission unit 112 in the first embodiment. However, the difference is that when sending a message, the coordinate and the node ID are not included in the message, but the site ID of the site to which the node A3 belongs and the node ID of the node A3 are included. Whether or not to include the site ID and node ID of the node A3 in the message may be changed according to the type of message.

  The message receiving unit 313 has a function of receiving a message in the DHT protocol, like the message receiving unit 113 in the first embodiment. However, instead of extracting coordinate information from the received message when receiving the message, if the received message contains a site ID, the received site ID and node information corresponding to the site ID are received. The difference is that the extracted information is passed to the delay calculation unit 315 and the extracted information is passed to the delay calculation unit 315.

  Based on the site ID extracted by the message reception unit 313, the delay calculation unit 315 calculates a delay between the node that transmitted the message including the site ID and the own node. For example, it is assumed that the message including the site ID is received by the node A3 from the node A4, and the message includes the site “4” that is the ID of the site to which the node A4 belongs. The delay calculation unit 315 of the node A3 refers to the inter-site delay storage unit 311 and checks the delay between the site A4 and the site to which the own node A3 belongs. If the inter-site delay is as shown in the inter-site delay table 102 shown in FIG. 5, the delay between the node A3 and the node A4 is calculated to be 50 msec. The delay calculation unit 315 passes the obtained delay to the adjacent node selection unit 316 together with the ID of the node A4 (that is, the ID of the node that transmitted the message including the site ID).

  The adjacent node selection unit 316 is based on the ID of the node that transmitted the message including the site ID (hereinafter referred to as a transmission node) passed from the delay calculation unit 315 and the delay between the transmission node and the own node. , It is determined whether to select the transmitting node as an adjacent node. In determining whether to select the transmission node as an adjacent node, the adjacent node selection unit 316 first sets the ID of the transmission node from the current adjacent node list held in the adjacent node / site ID storage unit 317. Refer to the information of the current adjacent node in the corresponding area. Then, the adjacent node selection unit 316 compares the delay between the current adjacent node and the own node in the corresponding region with the delay between the transmission node and the own node. If the delay between the transmission node and the own node is smaller, the adjacent node selection unit 316 replaces the current adjacent node in the corresponding area with the transmission node. When replacing the current adjacent node with the transmission node, the adjacent node selection unit 316 rewrites the information on the adjacent node in the adjacent node / site ID storage unit 317 with the information on the transmission node. On the other hand, when the delay between the transmitting node and the own node is not smaller, the adjacent node selection unit 316 keeps the adjacent node as it is.

  Similar to the adjacent node / coordinate storage unit 117 in the first embodiment, the adjacent node / site ID storage unit 317 holds the current adjacent node in the node A3 in a list format. However, the adjacent node / site ID storage unit 317 is different from the adjacent node / coordinate storage unit 117 in that it stores the site ID to which the adjacent node belongs instead of the coordinates of the adjacent node. An example of information held in the adjacent node / site ID storage unit 317 is shown in FIG.

  Referring to the adjacent node / site ID table 103 in FIG. 6, the first adjacent node has a corresponding ID area as shown in Expression (4), ID = n5, and the site ID to which the node belongs is the site ID It turns out that it is "4". Similarly, the second to fourth neighbor node information and the corresponding site ID are shown.

  Next, with reference to FIG. 7, the operation when the node A3 receives a message from the other node A4 in the second mode of the present invention will be described in detail. FIG. 7 is a flowchart showing processing when the node A3 receives a message from the node A4 which is another node in the second mode of the present invention.

  First, the message receiving unit 313 of the node A3 receives a message from the node A4 (step S201). Next, the message receiving unit 313 checks whether the site ID is included in the message received in step S201 (step S202).

  If it is determined in step S202 that the site ID is included in the message (step S202: YES), the message receiving unit 313 transmits the information including the included site ID and the message including the site ID (that is, the node ID). Node ID of node A4) is extracted from the message, and the extracted information is passed to delay calculation unit 315 (step S203). If it is determined in step S202 that the site ID is not included in the message (step S202: NO), the processing of the node A3 proceeds to step S207 described later.

  After step S203, the delay calculation unit 315 calculates a delay between the own node and the node A4 based on the site ID extracted in step S203, and sends the calculated result to the adjacent node selection unit 316 together with the ID of the node A4. (Step S204).

  Next, the adjacent node selection unit 316 refers to the adjacent node / site ID storage unit 317, and in the ID area corresponding to the node A4, a delay between the node currently selected as the adjacent node and the own node, The delay between the node calculated in step S204 and the node A4 is compared (step S205).

  In step S205, when the delay between the node A4 calculated in step S204 and the current node is smaller than the delay between the current adjacent node and the current node (step S205: YES), the adjacent node selection unit 316 The adjacent node currently selected in the ID area corresponding to A4 is replaced with node A4 (step S206). In Step S205, when the delay between the node A4 calculated in Step S204 and the own node is equal to or greater than the delay between the current adjacent node and the own node (Step S205: NO), the adjacent node selection unit 316 Keep neighboring nodes current. Then, the process of the node A3 moves to step S207.

  After step S206, the message receiving unit 313 passes the part other than the site ID and node ID in the message to the DHT protocol processing unit 314. The DHT protocol processing unit 314 performs protocol processing according to the type of message (step S207).

  In the example described above, when the received message includes a site ID, the node corresponding to the site ID is the node A4 that transmitted the message to the node A3.

  However, the site ID of a site to which a node other than the node A4 belongs may be included in the message. For example, when a node other than the node A4 (hereinafter referred to as a node Y) transmits a message first and the node A4 forwards the message to the node A3, the message of the site to which the node Y belongs is included in the message. The site ID is included. Therefore, in such a case, the message receiving unit 313 needs to extract the ID of the node Y as the node ID corresponding to the site ID included in the message.

  Next, effects of the second exemplary embodiment of the present invention will be described. In the second embodiment of the present invention, nodes in the vicinity of each other belong to the same site, and each node includes the site ID of the site to which the own node belongs and the node ID of the own node in a message in the DHT protocol. Include and send. Then, the node that has received the message including the site ID of the site to which the transmitting node belongs, obtains the delay between the transmitting node and the own node based on the inter-site delay measured in advance or periodically, If the obtained delay is smaller than the delay between the adjacent node and the current node in the ID area corresponding to the ID of the transmitting node, the adjacent node is replaced with the transmitting node.

  In this way, message reception from other nodes can be used as an opportunity to update a node closer to the own node as an adjacent node. Therefore, it can be expected that the closer to an ideal PNS situation, the more messages are received from more nodes.

  The present invention has been described above with reference to the embodiments. However, the present invention is not limited to the above-described embodiments. Various modifications that can be understood by those skilled in the art can be made to the configuration and details of the present invention within the scope of the present invention.

  The above nodes may have a computer system inside. In this case, the operation of each processing unit described above is stored in a computer-readable recording medium in the form of a program. Then, the computer reads this program, the computer executes the read program, and the above processing is performed. Here, the computer-readable recording medium includes a magnetic disk, a magneto-optical disk, a CD-ROM (Compact Disc-Read Only Memory), a DVD (Digital Versatile Disc) -ROM, a semiconductor memory, and the like. Alternatively, the computer program may be distributed to the computer via a communication line, and the computer that has received the distribution may execute the program.

  The program may be for realizing a part of the functions described above. Furthermore, what can implement | achieve the function mentioned above in combination with the program already recorded on the computer system, and what is called a difference file (difference program) may be sufficient.

  This application claims the priority on the basis of Japanese application Japanese Patent Application No. 2010-036553 for which it applied on March 10, 2010, and takes in those the indications of all here.

  The present invention can be used for, for example, a node having a distributed hash table and a system having such a node. In the present invention, an adjacent node can be selected with little overhead.

11 DHT protocol unit 12 TCP / IP communication unit 21 DHT protocol unit 22 TCP / IP communication unit 31 DHT protocol unit 32 TCP / IP communication unit 41 DHT protocol unit 42 TCP / IP communication unit 101 Adjacent node / coordinate table 102 Inter-site delay Table 103 Adjacent node / site ID table 111 Coordinate calculator 112 Message transmitter 113 Message receiver 114 DHT protocol processor 115 Distance calculator (first communication environment deriving unit)
116 Adjacent node selection unit (second communication environment deriving unit, adjacent node selection unit)
117 Adjacent node / coordinate storage unit (storage unit)
311 Inter-site delay storage unit 312 Message transmission unit 313 Message reception unit 314 DHT protocol processing unit 315 Delay calculation unit (first communication environment deriving unit)
316 Adjacent node selection unit (second communication environment deriving unit, adjacent node selection unit)
317 Adjacent node / site ID storage unit (storage unit)

Claims (3)

For each predetermined identifier area of an identifier that identifies each node participating in the distributed hash table protocol, information related to neighboring nodes is stored at the receiving node,
Receiving at the receiving node a message containing information about the sending node;
Deriving a first communication environment between the transmitting node and the receiving node at the receiving node based on the information about the transmitting node;
A second communication environment between the current adjacent node and the receiving node selected as the current adjacent node for the identifier region corresponding to the transmitting node based on the information regarding the adjacent node and the information regarding the transmitting node; Is derived at the receiving node,
The first communication environment is compared with the second communication environment at the reception node, and the identifier corresponding to the transmission node when the first communication environment is better than the second communication environment An adjacent node selection method of replacing the current adjacent node currently selected as an adjacent node for an area with the transmitting node ,
The first communication environment and the second communication environment are delay times between nodes,
Among the nodes participating in the distributed hash table protocol, a site identifier for identifying the site is assigned to a site that is a group composed of nodes existing in the same management domain,
The information regarding the neighboring node includes a site identifier assigned to a site to which the neighboring node belongs and an identifier for identifying the neighboring node;
Each node holds a delay time from the site to which each node belongs to each other site,
The message includes, as the information on the transmission node, a first site identifier assigned to a first site to which the transmission node belongs and a first identifier that identifies the transmission node;
The receiving node extracts the first site identifier and the first identifier from the message, and based on the held delay time, the second receiving node to which the second site identifier is assigned belongs. A first delay time between the first site and the first site,
The receiving node obtains a second delay time between the third site to which the current adjacent node belongs and the second site based on the held delay time;
The receiving node compares the first delay time and the second delay time, and when the first delay time is smaller than the second delay time, the identifier region corresponding to the transmitting node Replacing the second identifier of the current adjacent node currently stored as the adjacent node with the first identifier
Adjacent node selection method. A storage unit that stores information about adjacent nodes for each predetermined identifier region of an identifier that identifies each node participating in the distributed hash table protocol;
A message receiving unit for receiving a message including information on the sending node;
A first communication environment deriving unit for deriving a first communication environment between the transmission node that is a transmission source of the message and the own node based on the information on the transmission node;
Based on the information about the neighboring node and the information about the sending node,
A second communication environment deriving unit for deriving a second communication environment between the current adjacent node currently selected as the adjacent node and the own node for the identifier region corresponding to the transmission node;
The first communication environment is compared with the second communication environment, and the first communication environment is the second communication environment.
If from the communication environment is good, a node and a neighboring node selecting unit to replace the current neighbor node selected as the current neighbor node for the identifier region corresponding to the transmitting node by the transmitting node,
The first communication environment and the second communication environment are delay times between nodes,
Among the nodes participating in the distributed hash table protocol, a site identifier for identifying the site is assigned to a site that is a group composed of nodes existing in the same management domain,
The information regarding the neighboring node includes a site identifier assigned to a site to which the neighboring node belongs and an identifier for identifying the neighboring node;
The own node holds the delay time from the site to which it belongs to each other site,
The message includes, as the information on the transmission node, a first site identifier assigned to a first site to which the transmission node belongs and a first identifier that identifies the transmission node;
The first communication environment deriving unit extracts the first site identifier and the first identifier from the message, and the own node to which the second site identifier is assigned based on the held delay time Determining a first delay time between the second site to which the
The second communication environment deriving unit obtains a second delay time between the third site to which the current adjacent node belongs and the second site based on the held delay time,
The adjacent node selection unit compares the first delay time with the second delay time, and when the first delay time is smaller than the second delay time, the adjacent node selection unit corresponds to the transmission node. Replace the second identifier of the current adjacent node currently stored as the adjacent node for the identifier area with the first identifier.
node. Storing information about neighboring nodes for each predetermined identifier region of an identifier that identifies each node participating in the distributed hash table protocol;
Receiving a message containing information about the sending node;
Deriving a first communication environment between the sending node that is the source of the message and the own node based on the information about the sending node;
Based on the information on the adjacent node and the information on the transmitting node, a second communication environment between the current adjacent node and the current node selected as the current adjacent node for the identifier region corresponding to the transmitting node is Deriving steps;
Comparing the first communication environment and the second communication environment;
If the first communication environment is better than the second communication environment, replacing the current adjacent node currently selected as the adjacent node for the identifier region corresponding to the transmitting node with the transmitting node; a program causing a computer to execute the,
The first communication environment and the second communication environment are delay times between nodes,
Among the nodes participating in the distributed hash table protocol, a site identifier for identifying the site is assigned to a site that is a group composed of nodes existing in the same management domain,
The information regarding the neighboring node includes a site identifier assigned to a site to which the neighboring node belongs and an identifier for identifying the neighboring node;
The own node holds the delay time from the site to which it belongs to each other site,
The message includes, as the information on the transmission node, a first site identifier assigned to a first site to which the transmission node belongs and a first identifier that identifies the transmission node;
In the step of deriving the first communication environment, the first site identifier and the first identifier are extracted from the message, and a second site identifier is assigned based on the held delay time. Determining a first delay time between the second site to which the node belongs and the first site;
In the step of deriving the second communication environment, a second delay time between the third site to which the current adjacent node belongs and the second site is obtained based on the held delay time,
In the step of comparing the first communication environment and the second communication environment, the first delay time is compared with the second delay time;
In the step of replacing the current adjacent node with the transmitting node, the identifier area corresponding to the transmitting node is stored as the current adjacent node when the first delay time is smaller than the second delay time. Replace the second identifier of the current adjacent node with the first identifier
program.

Images