Interest-based connections in peer-to-peer networks

• US 7,174,382 B2
• Filed: 04/09/2002
• Issued: 02/06/2007
• Est. Priority Date: 04/09/2002
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Pruyne, James Christopher, Kalogeraki, Vasiliki, Ramanathan, Murali Krishna
• Primary Examiner(s): Wiley; David
• Assistant Examiner(s): Avellino; Joseph E.
• Application Number:
  US10/119,449
• Publication Number:
  US 20030191828A1
• Time in Patent Office: 1,764 Days
• Field of Search: 709220-222, 709/201, 709217-219, 709227-229, 709/238, 709/241, 709/244, 709204-206, 713/100
• US Class Current: 709/227
• CPC Class Codes: G06F 16/1837 Management specially adapted to peer-to-peer storage networks topology management mechanisms of peer-to-peer networks H04L67/1042

Abstract

Peers (p) monitor responses received from other peers (s, q) to requests for information and rate the responding peers on their ability to provide information of interest. When a responding peer (s) is discovered to frequently provide good results, the requesting peer (p) attempts to move closer to the responding peer (s) by creating a direct connection (p-s) with that peer and thereby promote the “good” peer to an “immediate” peer. If such a promotion would result in too many direct connections, the least important immediate peer is demoted to an “indirect” peer. The criteria (Imp) used for evaluating the relative importance of at least the immediate peers is preferably a time weighted average (Imp*(t)=α·Imp(t)+β·Imp*(t−1)) that also measures consistency and reliability and preferably includes factors not only representative of the peer'"'"'s ability to provide requested information (Hits), but also of its proximity to the source of that information (1/Hops) so that it can prove that information efficiently. This leads to clusters of peers with similar interests, and in turn reduces the depth of searches typically required to achieve good results.

Claims

1. A method for reconfiguring a node in a peer-to-peer network, comprising:

maintaining a list of addressable nodes on the peer-to-peer network and identifying which are currently considered immediate peers and which are considered indirect peers;

generating a query message to each of the immediate peers for subsequent preparation of a reply message or for forwarding to one or more other peers for a reply;

receiving at least a first unique reply to said query message;

maintaining statistical information on unique replies originating both from said immediate peers and from said indirect peers;

calculating a first metric for at least three peers in the peer-to-peer network, including directly connected first and second immediate peers and an indirect third peer that is not directly connected to the node being reconfigured,

calculating a second metric for at least the first and second immediate peers, and

dropping the direct connection to said second peer and establishing a direct connection to said third peer if the calculated first metric for the third peer is greater than a corresponding first metric for at least one of the first and second immediate peers and the calculated second metric value for the second peer is less than a corresponding second metric value for other immediate peers.

2. The method of claim 1 wherein at least the first metric is representative of the peer'"'"'s interests and measures for an immediate peer not only received content originating at that immediate peer, but also received content received from indirect peers in response to queries forwarded by that indirect peer.

3. The method of claim 2 wherein at least the second metric also includes a measure of the logical distance between the local peer originating the query and a remote peer associated with the received content.

4. The method of claim 3 wherein at least the second metric takes into account a time weighted average of previous calculations of said second metric.

5. A method for dynamically measuring the current importance of a directly connected peer in a peer-to-peer network, comprising:

maintaining a list of said addressable nodes and identifying which are currently considered immediate peers and which are considered indirect peers;

generating a query message to each of the immediate peers for subsequent preparation of a reply message or for forwarding to one or more other peers for a reply;

receiving at least a first unique reply to said query message;

maintaining statistical information on unique replies originating both from said immediate peers and from said indirect peers;

calculating a first factor representative of the current contribution of a peer in the peer-to-peer network, measured based at least in part on the number of unique replies first received via said peer;

calculating a second factor representative of the current efficiency of the peer being measured based at least in part on the number of hops traveled by the first unique replies received via said peer;

using both said first factor and said second factor to calculate said current importance; and

replacing one of the immediate peers based on the calculated current importance.

6. The method of claim 5 further comprising the step of calculating a time weighted importance derived from at least two successive current importance calculations.

7. The method of claim 6 wherein said time weighted average importance gives a higher ranking to a connection that maintains a relatively high contribution and a relatively high efficiency over a relatively long period of time.

8. The method of claim 6 wherein said time weighted average importance gives a greater weight to a more recent measurement.

9. A dynamically reconfigurable peer-peer network comprising a plurality of physically connected addressable nodes, each said node comprising:

an addressing module for maintaining a list of said addressable nodes and identifying which are currently considered immediate peers and which are considered indirect peers;

a query module for generating a query message to each of the immediate peers for subsequent preparation of a reply message or for forwarding to one or more other peers for a reply;

a response module for receiving at least a first unique reply to said query message;

a history module for maintaining statistical information on unique replies originating both from said immediate peers and from said indirect peers;

a calculator module for calculating;

a contribution score for each of said peers based at least in part on the number of unique first replies originating at or received via the peer being measured over a predetermined period of time, and

an importance score for at least each of said immediate peers based at least in part on the logical distance to the peer from which each said unique first reply originated; and

a reconfiguration module responsive to the addressing module and to the calculator module for replacing a direct peer-to-peer connection to an immediate peer having a first importance score with a corresponding connection to an indirect peer having a second contribution score, the second contribution score being higher than the first contribution score.

10. The network of claim 9 wherein said importance score is also based on a corresponding said contribution score.

11. The network of claim 10 wherein said importance score is a time weighted importance derived from at least two successive importance score calculations.

12. The network of claim 11 wherein said time weighted importance gives a higher ranking to a connection that maintains a relatively high said contribution and a relatively said logical distance over a relatively long period of time.

13. The network of claim 11 wherein said time weighted importance gives a greater weight to a more recent measurement.

14. A node in a peer-to-peer network, comprising:

a query module configured to transmit queries to the node'"'"'s immediate peers over the peer-to-peer network;

a reception module configured to receive at least a first unique reply to said query message;

a history module configured to maintain statistical information on unique replies originating both from said immediate peers and from indirect peers on the peer-to-peer network;

an evaluation module configured periodically evaluate importance of the immediate and indirect peers on the peer-to-peer network based at least in part on at least one of (i) a number of unique first replies originating at or received via the peer being measured over a predetermined period of time, and (ii) a logical distance to the peer from which each said unique first reply originated; and

a reconfiguration module configured to modify who the node'"'"'s immediate peers are based on results provided by the evaluation module.

15. A node according to claim 14, wherein the importance of a peer is determined by the evaluation module based on a quantity of responses received from that peer.

16. A node according to claim 15, wherein the importance of the peer also is determined by the evaluation module based on a logical distance associated with a response.

17. A node according to claim 14, wherein the importance of a peer is determined by the evaluation module by giving greater importance to more recent responses.

18. A node according to claim 14, wherein the number of the immediate peers is limited to a specified maximum so that when the maximum is reached, an addition of another immediate peer requires removal of an existing immediate peer.

19. A node according to claim 18, wherein the removal of the existing immediate peer is based on a relative importance of the immediate peers as determined by the evaluation module.