Method and system for identifying available resources in a peer-to-peer network

• US 20050021758A1
• Filed: 05/27/2004
• Published: 01/27/2005
• Est. Priority Date: 06/04/2003
• Status: Active Grant

• Current Assignee: Sony Interactive Entertainment Inc. (Sony Group Corp.)
• Original Assignee: Sony Computer Entertainment Incorporated (Sony Group Corp.)
• Inventors: White, Payton R.
• Granted Patent: US 7,603,464 B2
• Time in Patent Office: Days
• US Class Current: 709/226
• 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/1089 Hierarchical topologies
• CPC Class Codes: H04L 67/51 Discovery or management thereof, e.g. service location protocol [SLP] or web services

Abstract

A method for a peer of a peer-to-peer network to search for an available resource is provided. The method initiates with representing a request for the available resource as a request bit string. The method includes transmitting the request to a parent of the peer. Then, an aggregate availability bit string associated with the parent is accessed. The aggregate availability bit string represents an aggregate resource availability for all children of the parent. Next, a logical operation is performed with the bits of the aggregate availability bit string and the bits of the request bit string. Then, it is determined whether any of the children of the parent are able to provide the available resource based upon a result of the logical operation. A peer-to-peer grid and a system for publishing and identifying an available resource in a peer-to-peer distributed network are also provided.

Claims

1. A method for a peer of a peer-to-peer network to publish available resources, comprising method operations of:

determining an available resource of the peer;

expressing the available resource as a bit string; and

transmitting the bit string to a parent of the peer.

2. The method of claim 1, further comprising:

organizing peers of the peer-to-peer network in a structured tree prior to transmitting the bit string.

3. The method of claim 1, wherein the method operation of expressing the available resource as a bit string includes,

designating a first portion of the bit string as a binary value;

and

designating a second portion of the bit string as a power law value.

4. The method of claim 1, further comprising:

aggregating the bit string with additional bit strings received by the parent.

5. The method of claim 2, wherein the method operation of organizing peers of the peer-to-peer network in a structured tree includes,

organizing the peers in one of a regular recursive tree or a self organizing tree.

6. The method of claim 5, wherein the self organizing tree is assembled based upon locality of peers.

7. A method for a peer of a peer-to-peer network to search for an available resource, comprising method operations of:

representing a request for the available resource as a request bit string;

transmitting the request to a parent of the peer;

accessing an aggregate availability bit string associated with the parent, the aggregate availability bit string representing an aggregate resource availability for all children of the parent

performing a logical operation with bits of the aggregate availability bit string and bits of the request bit string; and

determining whether any of the children of the parent are able to provide the available resource based upon a result of the logical operation.

8. The method of claim 7, further comprising:

organizing peers of the peer-to-peer network in a hierarchical structure prior to transmitting the bit string.

9. The method of claim 8, wherein organizing peers of the peer-to-peer network in a structured tree prior to transmitting the bit string includes,

organizing the peers in the hierarchical structure based upon locality of the peers.

10. The method of claim 7, wherein the method operation of representing a request for the available resource as a request bit string includes,

establishing a first portion of the request bit string to be read as a binary number;

and

establishing a second portion of the bit string to read as a power law value.

11. The method of claim 7, wherein the method operation of accessing an availability bit string associated with the parent includes,

communicating individual availability strings to the parent from each child;

and

combining the individual availability strings with an availability string of the parent to define the aggregate resource availability.

12. The method of claim 11, wherein the method operation of performing a logical operation with bits of the aggregate availability bit string and bits of the request bit string includes,

combining each bit of the request bit string with a corresponding bit of the aggregate availability bit string through a logical AND operation;

and

determining if the individual availability strings can fulfill the request based on results of the logical AND operation.

13. The method of claim 7, further comprising:

if any of the children are able to provide the available resource, the method includes,

transmitting an address of the any of the children to the peer.

14. A computer readable medium having program instructions for a peer of a peer-to-peer network to publish available resources, comprising method operations of:

program instructions for determining an available resource of the peer;

program instructions for expressing the available resource as a bit string; and

program instructions for transmitting the bit string to a parent of the peer.

15. The computer readable medium of claim 14, further comprising:

program instructions for organizing peers of the peer-to-peer network in a structured tree prior to transmitting the bit string.

16. The computer readable medium of claim 14, wherein the program instructions for expressing the available resource as a bit string includes,

program instructions for designating a first portion of the bit string as a binary value;

and

program instructions for designating a second portion of the bit string as a power law value.

17. The computer readable medium of claim 14, further comprising:

program instructions for aggregating the bit string with additional bit strings received by the parent.

18. The computer readable medium of claim 15, wherein the program instructions for organizing peers of the peer-to-peer network in a structured tree includes,

program instructions for organizing the peers in one of a regular recursive tree or a self organizing tree.

19. The computer readable medium of claim 18, wherein the self organizing tree is assembled based upon locality of peers.

20. A computer readable medium having program instructions for a peer of a peer-to-peer network to search for an available resource, comprising:

program instructions for representing a request for the available resource as a request bit string;

program instructions for transmitting the request to a parent of the peer;

program instructions for accessing an aggregate availability bit string associated with the parent, the aggregate availability bit string representing an aggregate resource availability for all children of the parent;

program instructions for performing a logical operation with bits of the aggregate availability bit string and bits of the request bit string; and

program instructions for determining whether any of the children of the parent are able to provide the available resource based upon a result of the logical operation.

21. The computer readable medium of claim 20, further comprising:

program instructions for organizing peers of the peer-to-peer network in a hierarchical structure prior to transmitting the bit string.

22. The computer readable medium of claim 21, wherein the program instructions for organizing peers of the peer-to-peer network in a structured tree prior to transmitting the bit string includes,

program instructions for organizing the peers in the hierarchical structure based upon locality of the peers.

23. The computer readable medium of claim 20, wherein the program instructions for representing a request for the available resource as a request bit string includes,

program instructions for establishing a first portion of the request bit string to be read as a binary number;

and

program instructions for establishing a second portion of the bit string to read as a power law value.

24. The computer readable medium of claim 20, wherein the program instructions for accessing an availability bit string associated with the parent includes,

program instructions for communicating individual availability strings to the parent from each child;

and

program instructions for combining the individual availability strings with an availability string of the parent to define the aggregate resource availability.

25. The computer readable medium of claim 24, wherein the program instructions for performing a logical operation with bits of the aggregate availability bit string and bits of the request bit string includes,

program instructions for combining each bit of the request bit string with a corresponding bit of the aggregate availability bit string through a logical AND operation;

and

program instructions for determining if the individual availability strings can fulfill the request based on results of the logical AND operation.

26. A system for publishing and identifying an available resource in a peer-to-peer distributed network, comprising:

topology management logic for organizing nodes within the peer-to-peer distributed network into a hierarchical tree; and

resource level logic configured to determine availability of a resource contained within a node of the hierarchical tree, the resource level logic further configured to represent the availability of the resource as a first bit string for transmission to a parent of the node, wherein the parent is configured to compare a request string to the first bit string through a logical operation in order to determine whether the resource can be fulfilled by the node.

27. The system of claim 26, further comprising:

domain level application logic configured to provide the functionality for using the resource after the resource is determined as being available through the resource level logic.

28. The system of claim 26, wherein the hierarchical tree is one of a regular recursive tree or a self-organizing tree.

29. The system of claim 28, wherein the self organizing tree organizes parents and corresponding children based upon locality of the parents and corresponding children.

30. The system of claim 26, wherein the parent is further configured to provide an address of the node if the node can provide the resource.

31. The system of claim 26, wherein the logical operation compares each corresponding bit of the request string and the first bit string.

32. The system of claim 26, wherein both the request string and the first bit string are hybrid bit strings having a first portion representing a binary number and a second portion representing a power law distribution.

33. A peer-to-peer grid, comprising:

a plurality of peers configured to arranged in a hierarchical tree;

the plurality of peers including,

a first peer in communication with a second peer, the first peer being configured to transmit an availability string to the second peer, the availability string representing availability of a resource associated with the first peer;

a third peer configured to generate a request string representing a request for the resource; and

logic for comparing bits of the availability string to bits of the request string in order to determine if the second string can fulfill the request for the resource, the logic locally available to each of the plurality of peers.

34. The peer-to-peer grid of claim 33, wherein both the request string and the availability string include a first portion representing a binary number and a second portion representing a power law distribution.

35. The peer-to-peer grid of claim 34, wherein each peer includes an evaluator configured to recognize the first portion as the binary number and the second portion as the power law distribution.

36. The peer-to-peer grid of claim 33, wherein the second peer is configured to receive multiple availability strings, the second peer further configured to aggregate the multiple availability strings.

37. The peer-to-peer grid of claim 33, wherein the hierarchical tree is one of a regular recursive tree or a self-organizing tree.

38. A peer-to-peer network capable of being searched for an available resource, comprising:

means for representing a request for the available resource as a request bit string;

means for transmitting the request to a parent of the peer;

means for accessing an aggregate availability bit string associated with the parent, the aggregate availability bit string representing an aggregate resource availability for all children of the parent;

means for performing a logical operation with bits of the aggregate availability bit string and bits of the request bit string; and

means for determining whether any of the children of the parent are able to provide the available resource based upon a result of the logical operation.

39. The method of claim 38, further comprising:

means for organizing peers of the peer-to-peer network in a hierarchical structure prior to transmitting the bit string.

40. The method of claim 39, wherein the means for organizing peers of the peer-to-peer network in a structured tree prior to transmitting the bit string includes,

means for organizing the peers in the hierarchical structure based upon locality of the peers.

41. The method of claim 38, wherein the means for representing a request for the available resource as a request bit string includes,

means for establishing a first portion of the request bit string to be read as a binary number;

and

means for establishing a second portion of the bit string to read as a power law value.

42. The method of claim 38, wherein the means for accessing an availability bit string associated with the parent includes,

means for communicating individual availability strings to the parent from each child;

and

means for combining the individual availability strings with an availability string of the parent to define the aggregate resource availability.

43. The method of claim 38, wherein the means for performing a logical operation with bits of the aggregate availability bit string and bits of the request bit string includes,

means for combining each bit of the request bit string with a corresponding bit of the aggregate availability bit string through a logical AND operation;

and

means for determining if the individual availability strings can fulfill the request based on results of the logical AND operation.