Network topology configuring method and node

• US 7,496,051 B2
• Filed: 01/10/2005
• Issued: 02/24/2009
• Est. Priority Date: 01/09/2004
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Inventors: Kato, Takeshi, Omata, Eiji, Ishikawa, Norihiro, Wan, Haoyi, Sumino, Hiromitsu
• Primary Examiner(s): Phunkulh; Bob A
• Application Number:
  US11/031,007
• Publication Number:
  US 20050237948A1
• Time in Patent Office: 1,506 Days
• Field of Search: None
• US Class Current: 370/254
• CPC Class Codes: H04L 41/0806 for initial configuration or provisioning, e.g. plug-and-play
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 61/35 involving non-standard use of addresses for implementing network functionalities, e.g. coding subscription information within the address or functional addressing, i.e. assigning an address to a function
• CPC Class Codes: H04L 61/50 Address allocation
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1046 Joining 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
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A node includes a manager configured to manage the hash value of the node and the hash values of adjacent nodes, and a calculator configured to calculate an insertion position of a new entry node in a ring network, based on the hash value of the new entry node, the hash value of the node and the hash values of the adjacent nodes.

Claims

1. A node constituting a part of an autonomous distributed ring network, comprising:

a manager configured to manage a distributed hash table which includes a hash value of the node generated from identification information on the node and a hash value of an adjacent node generated from identification information on the adjacent node; and

a calculator configured to calculate an insertion position in the ring network of a new entry node newly joining the ring network, based on a hash value of the new entry node generated from identification information on the new entry node, the hash value of the node and the hash value of the adjacent node and when calculator determines that the insertion position of the new entry node of the ring network will be between the node and the adjacent node, the calculator replaces the hash value of the adjacent node with the hash value of the new entry node in the distributed hash table, establishes a new connection with the new entry node, and notifies the adjacent node the new insertion position of the new entry node.

2. The node as set forth in claim 1, further comprising:

an obtainer configured to obtain the hash value of the new entry node from the new entry node; and

a informer configured to inform the insertion position of the new entry node in the ring network to the new entry node.

3. The node as set forth in claim 2, wherein the informer is configured to limit nodes to which the insertion position of the new entry node is informed, to the new entry node and the adjacent node.

4. The node as set forth in claim 1, wherein the calculator is configured to compare the hash value of the new entry node with the hash value of the node and the hash value of the adjacent node, and to calculate the insertion position of the new entry node so that each node is arranged in the order of the hash values in the ring network.

5. The node as set forth in claim 1, wherein:

the manager is configured to manage hash values of all nodes constituting the ring network, the hash values being generated from identification information on the all nodes; and

the calculator is configured to calculate the insertion position of the new entry node in the ring network, based on the hash value of the new entry node and the hash values of all the nodes.

6. The node as recited in claim 1, wherein when the node determines that the insertion position of the new entry node is not between the node and the adjacent node, the calculator determines that the insertion position of the new entry node is unknown, and transmits a network topology configuration information including the hash value of the insertion position of the new entry node to the adjacent node.

7. A new entry node newly joining an autonomous distributed ring network constituted by a plurality of nodes, comprising:

a manager configured to manage a distributed hash table which includes a hash value of the new entry node generated from identification information on the new entry node;

a receiver configured to receive a network topology configuration information from one node of the plurality of nodes, the network topology configuration information including a hash value of the one node, which is generated from identification information on the one node, and a hash value of an adjacent node of the one node, which is generated from identification information on the adjacent node;

a determiner configured to determine whether or not an insertion position of the new entry node is between the one node and the adjacent node;

a connection establisher configured to establish connections with the one node and with the adjacent node, respectively, when the determiner determines that the insertion position of the new entry node is between the one node and the adjacent node; and

an updater configured to update the distributed hash table to include a hash value of the one node and the hash value of the adjacent node in addition to the hash value of the new entry node.

8. A method of configuring a network topology in an autonomous distributed ring network constituted by a plurality of nodes, comprising:

calculating an insertion position in a node of the ring network for a new entry node newly joining the ring network, based on a hash value of the new entry node generated from identification information on the new entry node, and hash values of at least one nodes constituting the ring network, generated from identification information on the at least one nodes;

replacing the hash value of an adjacent node with the hash value of the new entry node in a distributed hash table when said calculating determines that the insertion position of the new entry node of the ring network will be between the node and the adjacent node;

establishing a new connection with new entry node; and

notifying the adjacent node the new insertion position of the entry node.

9. The method of configuring a network topology as set forth in claim 8, further comprising:

storing the hash value generated from identification information of the new entry node, and configured to store hash values of the at least one nodes constituting the ring network.

10. The method of configuring a network topology as set forth in claim 8, further comprising:

comparing the hash value of the new entry node with the hash value of the at least one nodes and the hash value of an adjacent node to the at least one nodes; and

calculating the insertion position of the new entry node so that each node is arranged in the order of the hash values in the ring network.