Interest-based connections in peer-to-peer networks

• US 20030191828A1
• Filed: 04/09/2002
• Published: 10/09/2003
• Est. Priority Date: 04/09/2002
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Kalogeraki, Vasiliki, Pruyne, James Christopher, Ramanathan, Murali Krishna
• Granted Patent: US 7,174,382 B2
• Time in Patent Office: Days
• US Class Current: 709/221
• 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 (p) in a peer-to-peer network, comprising:

calculating a first metric (Hits) for at least three other peers, including directly connected first and second immediate peers (q1,q1) and a remote third peer (s) that is not directly connected to the node being reconfigured,

calculating a second metric (Hits, Hits/Hops, and/or fn(Hits(t), Hops(t)) for at least the immediate peers (q1,q1), 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 metric for at least one of the immediate peers and the calculated second metric for the second peer is less than a corresponding 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 (Hits) originating at that immediate peer (q), but also received content (Hits) 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 (hops) between the local peer originating the query and a remote peer (s,q) associated with the received content.

4. The method of claim 3

wherein at least the second metric takes into account a time weighted average (importance) 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:

calculating a first factor representative of the current contribution of the peer being 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, and

using both said first factor and said second factor to calculate said 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-to-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 and/or forwarding to one or more other peers;

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 relatively low importance score with a corresponding connection to an indirect peer having a relatively high 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.