Method for on demand distributed hash table update

• US 20070230482A1
• Filed: 03/31/2006
• Published: 10/04/2007
• Est. Priority Date: 03/31/2006
• Status: Active Grant

• Current Assignee: Panasonic Corporation (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Narayanan, Sathya, Shim, Eunsoo
• Granted Patent: US 7,881,223 B2
• Time in Patent Office: Days
• US Class Current: 370/400
• CPC Class Codes: H04L 12/42 Loop networks
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1046 Joining mechanisms
• CPC Class Codes: H04L 67/1048 Departure or maintenance mechanisms
• CPC Class Codes: H04L 67/1065 Discovery involving distributed pre-established resource-based relationships among peers, e.g. based on distributed hash tables [DHT] pre-configuration of logical or physical connections H04L67/1053

Abstract

A method for managing communication in a peer-to-peer network in which overlay information is updated on-demand such that neighboring node information is updated at least periodically and other overlay information is updated on-demand (from standard communications). For example, in one aspect, the network includes a plurality of nodes, and the method includes looking up at least one neighboring node, sending a joining message from a joining node to the neighboring node, the joining message including information relating to the joining node, joining the joining node to the network by updating each neighboring node exclusive of any other nodes of the plurality of nodes, sending reply messages from each neighboring node to the joining node, and updating the joining node with information from each neighboring node, exclusive of any other nodes of the plurality of nodes.

Claims

1. A method for joining a network device to a peer-to-peer network that includes a plurality of nodes, each node having a node ID, each respective node of the peer-to-peer network being associated with a different network device, the method comprising the steps of:

a) looking up at least one neighboring node;

b) sending a joining message from a joining node that is joining the peer-to-peer network to the at least one neighboring node of the joining node, the at least one neighboring node of the joining node being determined from the node ID of the joining node, the joining message including information relating to the joining node;

c) joining the joining node to the peer-to-peer network by

(c-1) updating each of said at least one neighboring node exclusive of any other nodes of the plurality of nodes with the information from the joining message,

(c-2) sending reply messages from each of said at least one neighboring node to the joining node, and

(c-3) updating the joining node with information from each of said at least one neighboring node, exclusive of any other nodes of the plurality of nodes.

2. The method of claim 1, wherein the peer-to-peer network is a Chord network, each respective node is assigned at least a successor node and a predecessor node, and the at least one neighboring node is the successor node and the predecessor node of the joining node, the method further comprising the step of receiving, by the joining node, a node ID of the predecessor of the joining node from the successor node.

3. The method of claim 2, wherein the information from the successor and predecessor nodes is one of node IDs of the successor and predecessor nodes or the information included in finger tables of the successor and predecessor node.

27. A computer readable medium including software that is configured to control a general purpose computer to control communication from a device in the communication system by implementing a method according to claim 1.

4. A method for a network device to leave a peer-to-peer network that includes a plurality of nodes, each node having a node ID, each respective node of the peer-to-peer network being associated with a different network device, the method comprising the steps of:

a) sending, from a leaving node that is leaving the peer-to-peer network, a leave message, including information relating to the leaving node, to at least one neighboring node of the leaving node, the at least one neighboring node being at least one node known to the leaving node; and

b) updating the at least one neighboring node exclusive of any other node of the plurality of nodes with the information from the leave message.

5. The method of claim 4, wherein the peer-to-peer network is a Chord network, each respective node is assigned at least a successor node and a predecessor node, and the at least one neighboring node is the successor node and the predecessor node of the leaving node.

6. A method for a network device to leave a peer-to-peer network that includes a plurality of nodes, each node having a node ID, each respective node of the peer-to-peer network being associated with a different network device, the method comprising the steps of:

a) responsive to a lack of a reply to at least one message sent from at least one neighboring node of a leaving node to the leaving node, updating the respective at the at least one neighboring node, exclusive of other nodes of the plurality of nodes, that the leaving node has left the peer-to-peer network.

7. The method of claim 6, wherein the peer-to-peer network is a Chord network, each respective node is assigned at least a successor node and a predecessor node, and the at least one neighboring node is the successor node and the predecessor node of the leaving node such that (1) responsive to a lack of a reply to a first message sent from the predecessor node to the leaving node, updating the predecessor node, exclusive of any other node, that the leaving node has left the peer-to-peer network;

and (2) responsive to a lack of a reply to a second message sent from the successor node to the leaving node, updating the successor node, exclusive of any other node, that the leaving node has left the peer-to-peer network.

8. A method for a network device to leave a peer-to-peer network that includes a plurality of nodes, each node having a node ID, each respective node of the peer-to-peer network being associated with a different network device, the method comprising the steps of:

a) responsive to non-reception of any message from the leaving node by at least one neighboring node for more than a threshold period, updating the at least one neighboring node , exclusive of other nodes of the plurality of nodes, that has not received any message from the leaving node that the leaving node has left the peer-to-peer network.

9. The method of claim 8, wherein the peer-to-peer network is a Chord network, each respective node is assigned at least a successor node and a predecessor node, and the at least one neighboring node is the successor node and the predecessor node of the leaving node.

10. A method for communicating between or among network devices of a peer-to-peer network that includes a plurality of nodes, each node having a node ID and managing resources in a portion of the peer-to-peer network based on the node ID, each respective node of the peer-to-peer network being associated with a different network device, each node including a routing table with entries indicating a plurality of node IDs of nodes corresponding to respective portions of the peer-to-peer network, the method comprising the steps of:

a) sending a message from a first node to a second node, the selection of the second node as the recipient of the message being based on which one of the node IDs in the routing table of the first node is a closest node ID to a resource ID of a resource to be located;

b) determining at the second node whether the second node neighbors the resource ID and whether the second node has a resource corresponding to the resource ID;

c) if the second node neighbors the resource ID and the second node does not have the resource corresponding to the resource ID, determining at the second node whether the second node is responsible for the resource ID; and

d) if the second node is not responsible for the resource ID, sending a reply message indicating a routing failure to the first node and including alternative routing information based on the which one of the node IDs in the routing table of the second node is a closest node ID to the resource ID of the resource to be located.

11. The method of claim 10, wherein:

the peer-to peer network is a Chord network and each respective node of the peer-to-peer network is assigned at least a successor node and a predecessor node that are adjacent to the respective node based on the nodes ID of the peer-to-peer network;

step (b) of determining at the second node whether the second node neighbors the resource ID includes determining whether the node ID of the second node succeeds the resource ID;

step (c) determining at the second node whether the second node is responsible for the resource ID includes determining at the second node whether a predecessor of the second node precedes the resource ID; and

step (d) of including alternative routing information based on the which one of the node IDs in the routing table of the second node is a closest node ID to the resource ID of the resource to be located includes including alternative routing information based on the which one of the node IDs in the routing table of the second node is a closest preceding node ID to the resource ID of the resource to be located.

12. The method of claim 11, wherein when the resource ID of the resource to be located is between a resource ID and a corresponding node ID of a respective finger table entry, the closest node ID is defined as the corresponding node ID stored in the finger table and when the resource ID of the resource to be located is not between the resource ID and the corresponding node ID of any finger table entry, the closest node is defined as the closest predecessor node.

13. The method of claim 11, further comprising the step of:

e) responsive to the determination in step (c) that the predecessor of the second node precedes the resource ID, sending a reply to the first node that the resource is nonexistent.

14. The method of claim 11, further comprising the steps of:

monitoring, by one or more intermediate nodes, each message routed via the one or more intermediate nodes from a source node to a destination node; and

updating finger table entries at each of the intermediate nodes based on node ID information included in each respective message.

15. The method of claim 11, further comprising the step of:

e) sending from a sending node, a handshake message including information that is stored in the sending node, to the predecessor and successor of the node to indicate that the node is active.

16. The method of claim 15, wherein the handshake message includes:

(1) the predecessor node;

(2) the successor node;

(3) a list of nodes in the finger table of the sending node;

(4) a list of other nodes detected by the sending node, and/or (5) a list of nodes detected as inactive, and further includes a time-to-live indicator which decreases with each transfer of the information that is stored in the sending node.

17. The method of claim 11, further comprising the step of:

e) receiving at the first node the reply message indicating the routing failure;

f) updating the finger table entry of the first node to reflect the alternative routing information provided by the second node; and

g) sending another message from the first node to a third node based on the alternative routing information included in the reply message from the second node.

18. The method of claim 17, wherein the messages in steps (a) and (g) are communicated to the second and third nodes, respectively, via a sequence of other nodes based on the finger table entry of a closest node ID to the resource ID to be located of each respective node in the sequence of other nodes.

28. A computer readable medium including software that is configured to control a general purpose computer to control communication from a device in the communication system by implementing a method according to claim 10.

19. A method for communicating between or among network devices of a peer-to-peer network that includes a plurality of nodes, each node having a node ID and managing resources in a portion of the peer-to-peer network based on the node ID, each respective node of the peer-to-peer network being associated with a different network device, each node including a routing table with entries indicating a plurality of node IDs of nodes corresponding to respective portions of the peer-to-peer network, the method comprising the steps of:

a) sending a message from a first node to a second node, the selection of the second node as the recipient of the message being based on which one of the node IDs in the routing table of the first node is a closest node ID to a resource ID of a resource to be located;

b) including in the sent message in step (a) information indicating the node or nodes used to locate the resource, as a tracking history of the message;

c) responsive to receipt of the message by the second node, determining at the second node whether the node ID of the second node neighbors the resource ID of the resource that is being located;

d) if the node ID of the second node does not neighbor the resource ID of the node being located, determining at the second node whether the node ID in the routing table of the second node that is a closest node ID to the resource ID of the resource to be located is a node that is in the tracking history of the message; and

e) if the node ID in the routing table of the second node that is a closest node ID to the resource ID of the resource to be located matches any node that is in the tracking history of the message;

routing the message to an other node in the routing table of the second node that does not match to any node that is in the tracking history of the message.

20. The method of claim 19, wherein the peer-to-peer network is a Chord network, the routing table is a Chord finger table and when the resource ID of the resource to be located is between a resource ID and a corresponding node ID of a respective finger table entry, the closest node ID is defined as the corresponding node ID stored in the finger table and when the resource ID of the resource to be located is not between the resource ID and the corresponding node ID of any routing table entry, the closest node is defined as the closest predecessor node.

21. The method of claim 19, wherein step (e) of routing the message to the other node in the finger table includes the step of selecting the other node as the closest node that is not in the tracking history of the message.

22. The method of claim 19, wherein step (a) of sending a message from a first node to a second node is communicated to the second node via a sequence of other nodes based on the routing table entry of a closest node ID to the resource ID to be located that is not in the tracking history of the message of each respective node in the sequence of other nodes.

23. A method for communicating between or among network devices of a peer-to-peer network that includes a plurality of nodes, each node having a node ID, each respective node of the peer-to-peer network being associated with a different network device, each node including a routing table with entries indicating a plurality of node IDs of nodes corresponding to respective portions of the peer-to-peer network, the method comprising the steps of:

a) sending a message from a previous node to a subsequent node based on the node ID in the routing table of a previous node;

b) determining whether the subsequent node is inactive;

c) if the subsequent node is inactive,

c-1) adding information to the message indicating the inactive status of the node determined to be inactive in step (b), and

c-2) resending the message from a previous node to an alternative node that is active based on an other node ID in the routing table of a previous node; and

d) sending the message from one of the subsequent node or the alternative node to a further node that does not match any node ID indicated in the message to be inactive.

24. The method of claim 23, wherein step (a) of sending the message from the previous node to the subsequent node is based on the node ID in the routing table of the previous node that is a closest node ID to a resource ID of a resource to be located.

25. The method of claim 23, wherein step (c-2) of resending the message includes

checking which of the node IDs in the routing table of the previous node do not match any of the node IDs added in step (c-1);

and

selecting the node ID that does not match any of node IDs added in step (c-1) that is a closest node ID to a resource ID of a resource to be located.

26. The method of claim 23, further comprising the steps of

f) including in the sent message in step (a) node ID information indicating the node ID or nodes IDs of nodes used to locate the resource, as a tracking history of the message;

and

g) sending the message from one of the subsequent node or the alternative node to the further node that does not match any node ID indicated in the tracking history of the message.