System and method for searching a peer-to-peer network

• US 20050080858A1
• Filed: 10/10/2003
• Published: 04/14/2005
• Est. Priority Date: 10/10/2003
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Pessach, Yaniv
• Application Number:
  US10/684,126
• Publication Number:
  US 20050080858A1
• Time in Patent Office: Days
• US Class Current: 709/206
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1068 Discovery involving direct consultation or announcement among potential requesting and potential source peers
• CPC Class Codes: H04L 67/107 with limitation or expansion of the discovery scope

Abstract

A peer-to-peer (P2P) search request message may multicast from an originating peer to its neighboring peers. Each neighboring peer may multicast the request message in turn until a search radius is reached. Each peer receiving the request message may conduct a single node search. If the single node search is successful, a P2P search response message may be generated. Each receiving peer may filter duplicate messages and may multicast to less than 100% of its neighbors. Responses may be cached and cached responses sent in response to request messages, expanding the effective search radius of a given P2P search. The multicast probability for a neighbor may be a function of how frequently the neighbor has previously responded to a particular search type. To reduce abuse by impolite or malicious peers, in addition to rate-based throttling, originating peers may be required to solve a computationally expensive puzzle.

Claims

1. A computer-readable medium having thereon computer-executable instructions for performing a method comprising:

formatting a peer-to-peer search request message;

solving a distributed throttling computational puzzle for the peer-to-peer search request message; and

sending the peer-to-peer search request message to at least one receiving peer in a peer-to-peer network.

2. The computer-readable medium of claim 1, wherein the method further comprises:

generating a globally unique identifier for the peer-to-peer search request message; and

formatting the peer-to-peer search request message results in a peer-to-peer search request message format comprising the globally unique identifier for the peer-to-peer search request message.

3. The computer-readable medium of claim 2, wherein:

the method further comprises generating a globally unique identifier for the peer-to-peer search request; and

the peer-to-peer search request message format further comprises the globally unique identifier for the peer-to-peer search request.

4. The computer-readable medium of claim 1, wherein:

the peer-to-peer search request message is sent from a sending peer to said at least one receiving peer; and

each receiving peer is a neighbor of the sending peer in the peer-to-peer network.

5. The computer-readable medium of claim 1, wherein said at least one receiving peer processes the peer-to-peer search request message if the distributed throttling computational puzzle is solved.

6. The computer-readable medium of claim 1, wherein verifying that the distributed throttling computational puzzle is solved is less computationally expensive than solving the distributed throttling computational puzzle.

7. The computer-readable medium of claim 1, wherein solving the distributed throttling computational puzzle for the peer-to-peer search request message comprises transforming the peer-to-peer search request message in combination with the distributed throttling computational puzzle solution with a one way function.

8. The computer-readable medium of claim 1, wherein:

the peer-to-peer search request message is associated with a peer-to-peer search having a peer-to-peer search radius; and

solving the distributed throttling computational puzzle has a computational cost that is a function of the peer-to-peer search radius.

9. The computer-readable medium of claim 1, wherein sending the peer-to-peer search request message to at least one receiving peer in the peer-to-peer network comprises:

selecting a multicast set from said at least one receiving peer, each receiving peer having a peer-to-peer search multicast probability of being included in the multicast set; and

sending the peer-to-peer search request message to each receiving peer in the multicast set.

10. A computer-readable medium having thereon computer-executable instructions for performing a method comprising:

formatting a peer-to-peer search request message;

selecting a multicast set from at least one neighboring peer of a sending peer, each neighboring peer of the sending peer having a peer-to-peer search multicast probability of being included in the multicast set, and the peer-to-peer search multicast probability is a function comprising the number of neighboring peers of the sending peer; and

sending the peer-to-peer search request message to each neighboring peer of the sending peer in the multicast set.

11. The computer-readable medium of claim 10, wherein selecting the multicast set comprises randomly selecting the multicast set.

12. The computer-readable medium of claim 11, wherein selecting the multicast set comprises:

generating a random number for each neighboring peer of the sending peer; and

including the neighboring peer in the multicast set if the pseudo-random number for the neighboring peer is less than the peer-to-peer multicast probability.

13. The computer-readable medium of claim 10, wherein the peer-to-peer search multicast probability of the neighboring peer being included in the multicast set is capable of varying for each neighboring peer.

14. The computer-readable medium of claim 10, wherein:

each peer-to-peer search request message has a peer-to-peer search type;

the sending peer records a frequency with which each neighboring peer of the sending peer responds to each peer-to-peer search type; and

the peer-to-peer search multicast probability of the neighboring peer being included in the multicast set is a function further comprising the frequency with which the neighboring peer responds to the peer-to-peer search type of the peer-to-peer search request message.

15. The computer-readable medium of claim 10, wherein the method further comprises, after a delay, sending the peer-to-peer search request message to each neighboring peer of the sending peer not in the multicast set.

16. The computer-readable medium of claim 10, wherein the method further comprises solving a distributed throttling computational puzzle for the peer-to-peer search request message.

17. A computer-readable medium having thereon computer-executable instructions for performing a method comprising:

parsing a peer-to-peer search request message, the peer-to-peer search request message comprising a plurality of data fields, the plurality of data fields comprising;

a first data field containing a search request message identifier; and

a second data field containing a search request identifier;

discarding the peer-to-peer search request message if the search request message identifier in the first data field of the peer-to-peer search request message is in a search request cache; and

passing at least one data field of the peer-to-peer search request message to at least one registered application if the search request identifier in the second data field of the peer-to-peer search request message is not in the search request cache.

18. The computer-readable medium of claim 17, wherein the method further comprises adding the contents of a plurality of data fields of the peer-to-peer search request message to the search request cache.

19. The computer-readable medium of claim 17, wherein the method further comprises verifying that a distributed throttling computational puzzle for the peer-to-peer search request message is solved.

20. A computer-readable medium having thereon computer-executable instructions for performing a method comprising:

parsing a peer-to-peer search request message;

verifying that a distributed throttling computational puzzle for the peer-to-peer search request message is solved; and

discarding the peer-to-peer search request message if the distributed throttling computational puzzle for the peer-to-peer search request message is not solved.

21. The computer-readable medium of claim 20, wherein verifying that the distributed throttling computational puzzle for the peer-to-peer search request message is solved comprises transforming the peer-to-peer search request message in combination with the distributed throttling computational puzzle solution with a one way function.

22. The computer-readable medium of claim 20, wherein the peer-to-peer search request message comprises at least one data field, said at least one data field comprising a data field containing the distributed throttling computational puzzle solution.

23. The computer-readable medium of claim 20, wherein the method further comprises:

receiving the peer-to-peer search request message from a sending peer; and

discarding the peer-to-peer search request message if the rate of receipt of peer-to-peer search request messages from the sending peer exceeds a maximum peer-to-peer search request rate.

24. A computer-readable medium having thereon computer-executable instructions for performing a method comprising:

updating a peer-to-peer routing path of a peer-to-peer search request message to include a forwarding peer;

determining that a forwarding condition is true for each neighboring peer of the forwarding peer in a peer-to-peer network, the forwarding condition comprising that the neighboring peer is not in the peer-to-peer routing path of the peer-to-peer search request message; and

forwarding the peer-to-peer search request message to the neighboring peer if the forwarding condition is true for the neighboring peer.

25. The computer-readable medium of claim 24, wherein the forwarding condition comprises:

that the neighboring peer is not in the peer-to-peer routing path of the peer-to-peer search request message; and

that the neighboring peer did not send a duplicate of the peer-to-peer search request message to the forwarding peer.

26. The computer-readable medium of claim 25, wherein:

the peer-to-peer search request message has a peer-to-peer search request message identifier; and

the neighboring peer did send the duplicate of the peer-to-peer search request message to the forwarding peer if a search request cache contains the peer-to-peer search request message identifier of the peer-to-peer search request message.

27. The computer-readable medium of claim 24, wherein the forwarding condition comprises:

that the neighboring peer is not in the peer-to-peer routing path of the peer-to-peer search request message; and

a random determination with a peer-to-peer search multicast probability.

28. A computer-readable medium having thereon computer-executable instructions for performing a method comprising:

formatting a peer-to-peer search response message in response to a peer-to-peer search request message, the peer-to-peer search request message having a peer-to-peer routing path, the peer-to-peer routing path listing, in order, at least one peer in a peer-to-peer network traversed by the peer-to-peer search request message, the peer-to-peer routing path listing beginning with an originating peer of the peer-to-peer search request message; and

sending, from a responding peer, the peer-to-peer search response message to the first peer in the peer-to-peer routing path that is a neighboring peer of the responding peer.

29. A computer-readable medium having thereon computer-executable instructions for performing a method comprising:

parsing a peer-to-peer search response message sent in response to a peer-to-peer search request message, the peer-to-peer search response message having a peer-to-peer request routing path, the peer-to-peer request routing path listing, in order, at least one peer in a peer-to-peer network traversed by the peer-to-peer search request message, the peer-to-peer routing path listing beginning with an originating peer of the peer-to-peer search request message; and

forwarding, from a forwarding peer, the peer-to-peer search response message to the first peer in the peer-to-peer request routing path that is a neighboring peer of the forwarding peer.

30. A computerized system, comprising a search message filter module configured to, at least, discard an incoming peer-to-peer search request message if the incoming peer-to-peer search request message does not include a valid solution to a distributed throttling computational puzzle for the incoming peer-to-peer search request message.

31. The computerized system of claim 30, further comprising:

a search request cache configured to, at least, cache information regarding incoming peer-to-peer search request messages;

wherein the incoming peer-to-peer search request message includes a search request message identifier; and

wherein the search message filter module is further configured to, at least, discard the incoming peer-to-peer search request message if the search request cache contains the search request message identifier of the incoming peer-to-peer search request message.

32. The computerized system of claim 31, further comprising:

an application peer-to-peer search registry configured to, at least, pass incoming peer-to-peer search requests to registered applications;

wherein the incoming peer-to-peer search request message includes a search request identifier; and

wherein the search message filter module is further configured to, at least, pass the incoming peer-to-peer search request message to the application peer-to-peer search registry if the search request cache does not contain the search request identifier of the incoming peer-to-peer search request message.

33. The computerized system of claim 30, further comprising a forward search request module configured to, at least:

select a multicast set from at least one neighboring peer of a forwarding peer, each neighboring peer of the forwarding peer having a peer-to-peer search multicast probability of being included in the multicast set; and

forwarding the incoming peer-to-peer search request message to each neighboring peer of the forwarding peer in the multicast set.

34. The computerized system of claim 30, further comprising:

a forward search response module configured to, at least, forward a peer-to-peer search response message from a forwarding peer to the first peer in a peer-to-peer request routing path that is a neighboring peer of the forwarding peer; and

wherein the peer-to-peer search response message was sent to the forwarding peer in response to a peer-to-peer search request message, and the peer-to-peer request routing path contains, in order, at least one peer in a peer-to-peer network traversed by the peer-to-peer search request message, beginning with an originating peer of the peer-to-peer search request message.