Method for on demand distributed hash table update

• US 7,881,223 B2
• Filed: 03/31/2006
• Issued: 02/01/2011
• Est. Priority Date: 03/31/2006
• Status: Expired due to Fees

• Current Assignee: Panasonic Corporation (Panasonic Holdings Corporation)
• Original Assignee: Panasonic Corporation (Panasonic Holdings Corporation)
• Inventors: Narayanan, Sathya, Shim, Eunsoo
• Primary Examiner(s): Shah; Chirag G
• Assistant Examiner(s): NGUYEN, MINH TRANG T
• Application Number:
  US11/395,820
• Publication Number:
  US 20070230482A1
• Time in Patent Office: 1,768 Days
• Field of Search: 370/252, 370/254, 370/255, 370/312, 370/400, 370/401, 370/406
• US Class Current: 370/254
• 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 managing a network device in a peer-to-peer network that includes a plurality of at least three 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 a successor node for a joining node that is joining the peer-to-peer network;

b) receiving, by the joining node, a message identifying the successor node;

c) sending a first joining message from the joining node that is joining the peer-to-peer network to the successor node of the joining node, the successor node of the joining node being determined from the node ID of the joining node, the first joining message including information relating to the joining node;

d) receiving, by the joining node from the successor node, another message indicating the successor node and a predecessor of the successor node, as two neighboring nodes of the joining node;

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

(e-1) sending a second joining message to the predecessor node including the information relating to the joining node,

(e-2) updating each of said two neighboring nodes exclusive of any other nodes of the plurality of at least three nodes with the information from the first and second joining messages,

(e-3) sending reply messages from each of said two neighboring nodes to the joining node during the joining of the joining node to the peer-to-peer network, and

(e-4) updating the joining node with node information of said two neighboring nodes from the reply messages, exclusive of any other node information of the plurality of at least three nodes.

2. The method of claim 1, wherein the peer-to-peer network is a Chord network, the method further comprising the step of receiving, by the joining node, a node ID of the predecessor node of the joining

node from the successor node.

3. The method of claim 2, wherein the information from the successor and predecessor nodes is node IDs of the successor and predecessor nodes.

4. A non-transitory computer readable storage medium storing 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.

5. The method of claim 1, wherein:

each of the joining node and first and second ones of the two neighboring nodes include a corresponding node ID,

the first one of the two neighboring nodes replies to the at least one joining message with information informing the joining node of the node IDs of the first and second ones of the two neighboring nodes and the second one of the neighboring nodes confirms the node ID of the first one of the two neighboring nodes as a neighboring node prior to the joining node joining the peer-to-peer network.

6. The method of claim 1, wherein:

the sending of reply messages from each of said two neighboring nodes to the joining node includes sending, by each of the two neighboring nodes a reply message directly to the joining node; and

the updating of the joining node with node information includes establishing node IDs of each of the two neighboring nodes as neighboring node IDs in the joining node.

7. The method of claim 1, further comprising the steps of:

routing a message from a source node to a destination node using respective ones of the plurality of nodes based on a first routing scheme; and

during routing of the message from the source node to the destination node, (1) detecting a routing error based on routing information associated with routing of the message; and

(2) changing the first routing scheme to another routing scheme to avoid the detected routing error.

8. The method of claim 7, wherein:

the detecting of the routing error includes identifying a type of the routing error; and

the changing of the first routing scheme to the another routing scheme includes selecting the another routing scheme based on the identified type of the routing error.

9. A method for communicating between or among network devices of a peer-to-peer network that includes a plurality of at least four 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, a selection of the second node as a 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 to reach the resource corresponding to the resource ID based on 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.

10. The method of claim 9, 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 corresponding successor node and a corresponding 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) of determining, at the second node, whether the second node is responsible for the resource ID includes determining at the second node whether the predecessor node of the second node precedes the resource ID; and

step (d) of including alternative routing information based on which one of the node IDs in the routing table of the second node is the closest node ID to the resource ID of the resource to be located includes including alternative routing information based on 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.

11. The method of claim 10, 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 routing 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.

12. The method of claim 10, further comprising the step of:

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

13. The method of claim 10, 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.

14. The method of claim 10, 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.

15. The method of claim 14, 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.

16. The method of claim 10, further comprising the steps of:

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

f) updating a 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.

17. The method of claim 16, 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.

18. A non-transitory computer readable storage medium storing 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 9.

19. A method for communicating between or among network devices of a peer-to-peer network that includes a plurality of at least four 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) routing a message from a first node to a second node, a selection of the second node as a 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 the message had been routed through during routing 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 the 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 the 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 a closest predecessor node.

21. The method of claim 20, 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 the message from the first node to the second node includes sending the message to the second node via a sequence of other nodes based on the routing table entry of the 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 at least four 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;

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.

24. A method for communicating between or among network devices of a peer-to-peer network that includes a plurality of at least four 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;

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;

e) 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

f) 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.