Method for on demand distributed hash table update

• US 8,130,676 B2
• Filed: 11/09/2010
• Issued: 03/06/2012
• Est. Priority Date: 03/31/2006
• Status: Active Grant

• Current Assignee: Panasonic Corporation (Panasonic Holdings Corporation)
• Original Assignee: Panasonic Corporation (Panasonic Holdings Corporation)
• Inventors: Shim, Eunsoo, Narayanan, Sathya
• Primary Examiner(s): Shah, Chirag
• Assistant Examiner(s): NGUYEN, MINH TRANG T
• Application Number:
  US12/942,400
• Publication Number:
  US 20110060843A1
• Time in Patent Office: 483 Days
• Field of Search: None
• 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 sending a leaving message from a leaving node to the predecessor and successor nodes of the leaving node, the leaving message including information relating to the leaving node, updating each of the predecessor and successor nodes exclusive of any other nodes of the plurality of nodes.

Claims

1. A method for managing 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, 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 a successor node and a predecessor node of the leaving node, as two neighboring nodes of the leaving node, the two neighboring nodes being nodes known to the leaving node;

b) updating the two neighboring nodes exclusive of any other node of the plurality of at least four nodes with the information from the leave message;

c) routing a message from a source node to a destination node using respective ones of the plurality of at least four nodes including the leaving node based on a first routing scheme; and

d) (1) routing of a message from the predecessor node to a further predecessor node, the routed message including a time-to-live (TTL) value (2) decrementing the TTL value;

(3) if the decremented TTL value is greater than zero, routing the message to another further predecessor node; and

(4) repeating steps (2) and (3) until the TTL value is zero.

2. The method of claim 1 wherein the peer-to-peer network is a Chord network.

3. 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.

4. A method for managing 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, the method comprising the steps of:

a) responsive to a lack of a reply to at least one message sent from one of a successor node or a predecessor node of a leaving node, to the leaving node, updating the successor and predecessor nodes, as two neighboring nodes, exclusive of other nodes of the plurality of at least four nodes, that the leaving node has left the peer-to-peer network;

b) routing a message from a source node to a destination node using respective ones of the plurality of at least four nodes including the leaving node based on a first routing scheme; and

c) (1) routing a message from the predecessor node to a further predecessor node, the routed message including a time-to-live (TTL) value;

(2) decrementing the TTL value;

(3) if the decremented TTL value is greater than zero, routing the message to another further predecessor node; and

(4) repeating steps (2) and (3) until the TTL value is zero.

5. The method of claim 4, wherein the peer-to-peer network is a Chord network.

6. A method for managing 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, the method comprising the steps of:

a) responsive to non-reception of any message from a leaving node by a successor node or a predecessor node for more than a threshold period, updating the successor node and the predecessor node, as two neighboring nodes, exclusive of other nodes of the plurality of at least four nodes, that the leaving node has left the peer-to-peer network;

b) routing a message from a source node to a destination node using respective ones of the plurality of at least four nodes including the leaving node based on a first routing scheme;

c) (1) routing of the message from the predecessor node to a further predecessor node, the routed message including a time-to-live (TTL) value;

(2) decrementing the TTL value;

(3) if the decremented TTL value is greater than zero, routing the message to another further predecessor node; and

(4) repeating steps (2) and (3) until the TTL value is zero.

7. The method of claim 6, wherein the peer-to-peer network is a Chord network.