Method and system for creating a peer-to-peer overlay network

• US 7,401,132 B1
• Filed: 12/20/2002
• Issued: 07/15/2008
• Est. Priority Date: 12/20/2002
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Operating Corporation (Gen Digital Inc.)
• Inventors: Jorapurkar, Girish, Slaughter, Gregory L., Muth, John, Czarnik, Paul, Krumel, Andrew, Borrill, Paul L.
• Primary Examiner(s): Jaroenchonwanit; Bunjob
• Assistant Examiner(s): WIDHALM, ANGELA M
• Application Number:
  US10/327,545
• Time in Patent Office: 2,034 Days
• Field of Search: None
• US Class Current: 709/220
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1046 Joining mechanisms
• CPC Class Codes: H04L 67/1055 involving connection limits involving dynamic management of active down- or uploading connections H04L67/1085
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A method and system for creating a peer-to-peer overlay network. The method includes discovering a set of node characteristics for each of a subset of existing nodes of a network. The method also includes scaling each of the discovered set of node characteristics to a value which is within a predetermined range of values. The method also includes generating a set of weighted values for each of the subset of nodes by applying a weighting function to each of the scaled values. In addition, the method includes generating a node rank value for each of the subset of nodes by summing the weighted values of each respective set of weighted values. Further, the method includes determining whether to connect to any of the subset of nodes based upon the node rank value.

Claims

1. A method for creating from a network of existing nodes, a peer-to-peer overlay network having no centralized server, said method comprising:

discovering a plurality of node characteristics for each node of a subset of said existing nodes;

scaling each of said discovered plurality of node characteristics to a value which is within a predetermined range of values;

generating a plurality of weighted values for each of said subset of existing nodes by applying a separate weighting function to each of said scaled values;

generating a node rank value for each of said subset of existing nodes by summing said plurality of weighted values;

determining which of said subset of said existing nodes are eligible nodes, wherein each of said eligible nodes have a node rank value that is greater than a dynamically programmable minimum node rank value;

determining a maximum number of nodes of said eligible nodes to establish a connection by generating a random number between zero and a dynamically programmable maximum number;

determining to which nodes of said eligible nodes to establish a connection by randomly selecting said maximum number of nodes from said eligible nodes; and

establishing a connection to said selected nodes.

2. The method as recited in claim 1, wherein said predetermined range of values is zero to one, inclusive.

3. The method as recited in claim 1 further comprising generating a random value which is within said predetermined range of values for each of said subset of existing nodes, and modifying said dynamically programmable minimum node rank value with said random value during operation.

4. The method as recited in claim 3 further comprising selectively connecting to a given eligible node of said subset of existing nodes in response to determining that a node rank value corresponding to said given eligible node is greater than said random value.

5. The method as recited in claim 1, wherein applying a separate weighting function includes multiplying a respective predetermined weight associated with a given node characteristic with said scaled value corresponding to said given node characteristic.

6. The method as recited in claim 1, wherein said plurality of node characteristics includes a communication latency.

7. The method as recited in claim 1, wherein said plurality of node characteristics includes observed bandwidth.

8. The method as recited in claim 1, wherein said plurality of node characteristics includes available storage capacity.

9. The method as recited in claim 1, wherein discovering said plurality of node characteristics includes gathering said node characteristics by querying said subset of existing nodes.

10. The method as recited in claim 4, further comprising creating a grouping of possible nodes including all existing nodes having node rank value greater than said random value.

11. The method as recited in claim 10, further comprising randomly choosing to which nodes of said grouping of possible nodes to connect by generating a number of random node numbers from said grouping of possible nodes, wherein said number of random node numbers is indicated by said maximum node number.

24. The method as recited in claim 1, wherein discovering said set of node characteristics includes gathering said node characteristics by monitoring network traffic by monitoring communications between different nodes.

25. The method as recited in claim 1, wherein said set of node characteristics includes availability of a node backup power supply.

26. The method as recited in claim 1, further comprising modifying said dynamically programmable minimum node rank value during operation as an environment corresponding to said network of existing nodes changes.

27. The method as recited in claim 1, further comprising modifying said dynamically programmable maximum number during operation as an environment corresponding to said network of existing nodes changes.

28. The method as recited in claim 1, further comprising assigning to a given node a node rank value of zero in response to determining the given node does not include a specific characteristic.

12. A storage medium including program instructions executable by a processor to implement the method of:

discovering a plurality of node characteristics for each node of a subset of said existing nodes;

scaling each of said discovered plurality of node characteristics to a value which is within a predetermined range of values;

generating a plurality of weighted values for each of said subset of existing nodes by applying a separate weighting function to each of said scaled values;

generating a node rank value for each of said subset of existing nodes by summing said plurality of weighted values;

determining which of said subset of said existing nodes are eligible nodes, wherein each of said eligible nodes have a node rank value that is greater than a dynamically programmable minimum node rank value;

determining a maximum number of nodes of said eligible nodes to establish a connection by generating a random number between zero and a dynamically programmable maximum number;

determining to which nodes of said eligible nodes to establish a connection by randomly selecting said maximum number of nodes from said eligible nodes; and

establishing a connection to said selected nodes.

13. The storage medium as recited in claim 12, wherein said predetermined range of values is zero to one, inclusive.

14. The storage medium as recited in claim 12, wherein applying a separate weighting function includes multiplying a respective predetermined weight associated with a given node characteristic with said scaled value corresponding to said given node characteristic.

15. The storage medium as recited in claim 12, wherein said program instructions are further executable to generate a random value which is within said predetermined range of values for each of said subset of existing nodes, and to modify said dynamically programmable minimum node rank value with said random value during operation.

16. The storage medium as recited in claim 15, wherein said program instructions are further executable to selectively connect to a given eligible node of said subset of existing nodes in response to determining that a node rank value corresponding to said given eligible node is greater than said random value.

17. The storage medium as recited in claim 16, wherein said program instructions are further executable to create a grouping of possible nodes including all existing nodes having node rank value greater than said random value.

18. The storage medium as recited in claim 17, wherein said program instructions are further executable to randomly choose to which nodes of said grouping of possible nodes to connect by generating a number of random node numbers from said grouping of possible nodes, wherein said number of random node numbers is indicated by said maximum node number.

19. A computer system comprising:

a plurality of nodes interconnected via a network, wherein each of said plurality of nodes includes;

a processor; and

a memory coupled to said processor, said memory including program instructions executable by the processor to;

create from a subset of nodes of said plurality of nodes, a peer-to-peer overlay network having no centralized server

discover a plurality of node characteristics for each node of a subset of said existing nodes;

scale each of said discovered plurality of node characteristics to a value which is within a predetermined range of values;

generate a plurality of weighted values for each of said subset of existing nodes by applying a separate weighting function to each of said scaled values;

generate a node rank value for each of said subset of existing nodes by summing said plurality of weighted values;

determine which of said subset of said existing nodes are eligible nodes, wherein each of said eligible nodes have a node rank value that is greater than a dynamically programmable minimum node rank value;

determine a maximum number of nodes of said eligible nodes to establish a connection by generating a random number between zero and a dynamically programmable maximum number;

determine to which nodes of said eligible nodes to establish a connection by randomly selecting said maximum number of nodes from said eligible nodes; and

establish a connection to said selected nodes.

20. The computer system as recited in claim 19, wherein the program instructions are further executable by the processor to generate a random value which is within said predetermined range of values for each of said subset of nodes, and to modify said dynamically programmable minimum node rank value with said random value during operation.

21. The computer system as recited in claim 20, wherein the program instructions are further executable by the processor to selectively connect to a given eligible node of said plurality of nodes in response to determining that a node rank value corresponding to said given eligible node is greater than said random value.

22. A computer system comprising:

a plurality of nodes interconnected via a network, wherein each of said plurality of nodes includes;

a processor;

a memory coupled to said processor and configured to store instructions and data; and

a network connection manager coupled to said processor and configured to create from a subset of nodes of said plurality of nodes, a peer-to-peer overlay network having no centralized server, wherein the network connection manager is further configured to;

discover a plurality of node characteristics for each node of a subset of nodes of said plurality of nodes;

scale each of said discovered plurality of node characteristics to a value which is within a predetermined range of values;

generate a plurality of weighted values for each of said subset of nodes by applying a separate weighting function to each of said scaled values;

generate a node rank value for each of said subset of nodes by summing said plurality of weighted values;

determine which of said subset of said nodes are eligible nodes, wherein each of said eligible nodes have a node rank value that is greater than a dynamically programmable minimum node rank value;

determine a maximum number of nodes of said eligible nodes to establish a connection by generating a random number between zero and a dynamically programmable maximum number;

determine to which nodes of said eligible nodes to establish a connection by randomly selecting said maximum number of nodes from said eligible nodes; and

establish a connection to said selected nodes.

23. A computer system comprising:

means for discovering a plurality of node characteristics for each of a subset of nodes of a plurality of nodes of a network;

means for scaling each of said discovered plurality of node characteristics to a value which is within a predetermined range of values;

means for generating a plurality of weighted values for each of said subset of nodes by applying a separate weighting function to each of said scaled values;

means for generating a node rank value for each of said subset of nodes by summing said plurality of weighted values;

means for determining which of said subset of said existing nodes are eligible nodes, wherein each of said eligible nodes have a node rank value that is greater than a dynamically programmable minimum node rank value;

means for determining a maximum number of nodes of said eligible nodes to establish a connection by generating a random number between zero and a dynamically programmable maximum number;

means for determining to which nodes of said eligible nodes to establish a connection by randomly selecting said maximum number of nodes from said eligible nodes; and

means for establishing a connection to said selected nodes.