Placing an object at a node in a peer-to-peer system based on storage utilization

• US 7,555,553 B2
• Filed: 10/01/2002
• Issued: 06/30/2009
• Est. Priority Date: 10/01/2002
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Zhang, Zheng, Xu, Zhichen, Tang, Wenting, Mahalingam, Mallik
• Primary Examiner(s): Coulter; Kenneth R
• Application Number:
  US10/260,430
• Publication Number:
  US 20040064556A1
• Time in Patent Office: 2,464 Days
• Field of Search: 718/105, 718/104, 718/102, 709/226
• US Class Current: 709/226
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: H04L 61/4552 Lookup mechanisms between a plurality of directories; Synchronisation of directories, e.g. metadirectories
• CPC Class Codes: H04L 61/58 Caching of addresses or names
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1076 Resource dissemination mechanisms or network resource keeping policies for optimal resource availability in the overlay network
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

A peer-to-peer system includes a plurality of nodes. The plurality of nodes includes at least an initial node and a neighboring node. The initial node is operable to determine whether to place an object at either the initial node or another node in the system based on a comparison of storage utilizations for the initial node and the neighboring node.

Claims

1. A method implemented with hardware for placing a selected object in a peer-to-peer system comprising steps of:

selecting an initial node as a candidate to place the object;

determining a storage utilization for the current candidate;

identifying a neighboring node of the current candidate, wherein the identified neighboring node has a lowest storage utilization among at least some neighbor nodes of the current candidate; and

comparing the storage utilization of the current candidate to the storage utilization of the identified neighboring node for placing the object.

2. The method of claim 1, further comprising placing the object on the current candidate or handing over the object to the identified neighboring node based on the comparison.

3. The method of claim 1, wherein the step of comparing further comprises steps of:

determining whether the storage utilization of the identified neighboring node is less than the storage utilization of the current candidate ; and

placing the object at the current candidate in response to the storage utilization of the identified neighboring node not being less than the storage utilization of the current candidate.

4. The method of claim 3, wherein the step of comparing further comprises steps of:

determining whether a difference between the storage utilization of the current candidate and the storage utilization of the identified neighboring node is greater than a threshold in response to the storage utilization of the identified neighboring node being less than the storage utilization of the current candidate;

placing the object at the current candidate in response to the difference not being greater than the threshold; and

determining whether a time-to-live (TTL) value associated with placement of the object is greater than a TTL threshold in response to the difference being greater than the threshold.

5. The method of claim 4, wherein the step of comparing further comprises steps of:

in response to the TTL value not being greater than the TTL threshold, handing the object over from the current candidate to the identified neighboring node, wherein the identified neighboring node becomes the current candidate and the steps of determining, identifying and comparing from claim 1 are repeated.

6. The method of claim 4, wherein the step of comparing further comprises steps of:

in response to the TTL value being greater than the TTL threshold, randomly placing the object at a node in the peer-to-peer system that previously decided not to host the object based on a comparison of storage utilization with the neighboring nodes.

7. The method of claim 1, wherein the step of comparing further comprises steps of:

determining whether the storage utilization of the current candidate and the identified neighboring node is substantially equal; and

randomly selecting either the initial node or the identified neighbor node to place the object in response to storage utilization of the current candidate and the identified neighboring node being substantially equal.

8. The method of claim 1, wherein the step of selecting the initial node further comprises steps of:

identifying a location of a parent object of the object;

identifying a logical space relative to the location of the parent object; and

selecting a node within the logical space to be the initial node.

9. The method of claim 8, wherein the step of selecting the node within the logical space further comprises a step of randomly selecting the node within the logical space.

10. The method of claim 8, wherein the peer-to-peer system comprises a distributed file system overlaid on the peer-to-peer system, and the parent object includes the location of the object.

11. The method of claim 10, wherein the logical space has a predetermined area within a CAN Cartesian coordinate space.

12. The method of claim 11, wherein the logical space comprises a space having a size based on a distance R from the parent node, the space containing neighboring nodes to the parent node.

13. The method of claim 12, wherein the distance R is based on a predetermined number of logical hops.

14. A peer-to-peer system comprising:

a plurality of nodes functioning as a distributed, shared, file system, the plurality of nodes including at least an initial node and a plurality of neighbor nodes to the initial node; and

the initial node is operable to identify a selected neighboring node of the plurality of neighboring nodes having a lowest storage utilization and is operable to determine whether to place an object on itself or to hand over the object to the identified neighboring node based on a comparison of storage utilizations for the initial node and the selected neighboring node.

15. The system of claim 14, wherein the initial node is operable to place the object at the initial node in response to the storage utilization of the identified neighboring node being greater than the storage utilization of the initial node.

16. The system of claim 15, wherein the initial node is operable to determining whether a difference between the storage utilization of the initial node and the storage utilization of the identified neighboring node is greater than a threshold in response to the storage utilization of the identified neighboring node being less than the storage utilization of the initial node.

17. The system of claim 16 wherein the initial node is operable to place the object at the initial node in response to the difference being less than the threshold;

determine whether a time-to-live (TTL) value associated with placement of the object is greater than a TTL threshold in response to the difference being greater than the threshold; and

in response to the TTL value not being greater than the TTL threshold, handing over the object to the identified neighboring node, in response to the TTL value being greater than the TTL threshold, place the object randomly at one of the nodes that previously rejected a placement request for the object.

18. The system of claim 14, wherein the plurality of nodes function as a distributed, shared, file system, the file system including a plurality of parent objects including name and logical location of the associated child objects;

and the object being placed is a child object of one of the plurality of parent objects.

19. The system of claim 18, wherein the initial node is a node randomly selected from a plurality of nodes within a logical space relative to a parent node, the parent node being a node hosting the parent object of the object being placed.

20. The system of claim 19, wherein the logical space is based on a predetermined distance from the parent node, the predetermined distance being in terms of logical hops.

21. A node in a peer-to-peer system comprising:

means for determining a storage utilization for the node, the node being a current candidate for placing an object;

means for identifying a neighboring node of the current candidate, wherein the identified neighboring node has a lowest storage utilization among at least some neighbor nodes of the current candidate; and

means for comparing the storage utilization of the current candidate to the storage utilization of the identified neighboring node for placing the object.

22. The node of claim 21, wherein the means for comparing further comprises:

means for determining whether the storage utilization of the identified neighboring node is less than the storage utilization of the current candidate; and

means for placing the object at the current candidate in response to the storage utilization of the identified neighboring node being greater than the storage utilization of the current candidate.

23. The node of claim 22, wherein the means for comparing further comprises:

means for determining whether a difference between the storage utilization of the current candidate and the storage utilization of the identified neighboring node is greater than a threshold in response to the storage utilization of the identified neighboring node being less than the storage utilization of the initial node;

means for placing the object at the current candidate node in response to the difference being less than the threshold; and

means for determining whether a time-to-live (TTL) value associated with placement of the object is greater than a TTL threshold in response to the difference being greater than the threshold.

24. The node of claim 23, wherein the means for comparing further comprises:

means for placing the object at the current candidate in response to the TTL value being greater than the TTL threshold; and

means for determining not to place the object at the current candidate in response to the TTL value being less than the TTL threshold and handing over the object to another neighboring node becoming a new current candidate for placing the object.