Placing an object at a node in a peer-to-peer system based on a zoom-in algorithm

1. A method for placing an object in a peer-to-peer system using a zoom-in algorithm, the method comprising steps of:

selecting a parent zone having a plurality of nodes in the peer-to-peer system, the parent zone including a node hosting a parent object;

dividing the parent zone into k subzones;

selecting one of the subzones;

selecting a node in the selected subzone;

placing the object in the selected node, where the object is a child object to the parent object;

setting the subzone where the child object is placed to be the parent zone; and

placing a second child object by repeating the steps of dividing the parent zone;

selecting one of the subzones; and selecting a node for placing to second child object, wherein the second child object is a child of the child object.

2. The method of claim 1 , wherein the step of selecting one of the subzones comprises randomly selecting one of the subzones.

3. The method of claim 1 , wherein the step of selecting the node in the selected subzone further comprises randomly selecting the node in the selected subzone.

4. The method of claim 3 , wherein the step of selecting a node in the selected subzone further comprises steps of:

determining a storage utilization for the randomly selected node;

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

comparing the storage utilization of the randomly selected node to the storage utilization of the identified neighbor node for placing the object.

5. The method of claim 4 , wherein the step of selecting the node in the selected subzone further comprises a step of selecting one of the randomly selected node and the identified neighbor node based on the comparison.

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

determining whether the storage utilization of the identified neighbor node is less than the storage utilization of the randomly selected node; and

selecting the randomly selected node in response to the storage utilization of the identified neighbor node being greater than the storage utilization of the randomly selected node.

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

determining whether a difference between the storage utilization of the randomly selected node and the storage utilization of the identified neighbor node is greater than a threshold in response to the storage utilization of the identified neighbor node being less than the storage utilization of the randomly selected node;

selecting the randomly selected node in response to the difference being less than the threshold; and

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

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

in response to the TTL value not being greater than the TTL threshold, comparing the storage utilization of the identified neighbor node with a storage utilization of a second neighbor node for placing the object, the second neighbor node being a neighbor to the identified neighbor node; and

determining whether to select one of the identified neighbor node, the second neighbor node and another node in the peer-to-peer system based on the comparison.

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

in response to the TTL value being greater than the TTL threshold, selecting the randomly selected node.

10. The method of claim 1 , wherein k is one of 2, 4, and 8.

11. The method of claim 1 , wherein a distributed file system having a known tree structure is overlaid on the peer-to-peer system, and the step of dividing the parent zone further comprises steps of:

traversing the entire tree to assign a weight to each node, the weight being associated with a storage requirement for a sub-tree rooted at each node; and

assigning each node to a zone having a zone size proportional to the weight assigned to that node.

12. The method of claim 11 , wherein the step of selecting one of the subzones further comprises steps of:

determining whether the shape of the tree is changed due to new objects being placed; and

selecting one of the subzones having the least number of nodes.

13. A peer-to-peer system comprising:

a plurality of nodes including a parent node hosting a parent object;

the parent node being operable to identify a parent zone including the parent node and to divide the patent zone into a plurality of subzones for placing a child object associated with the parent object; and

a second node in one of the plurality of subzones, wherein the child object is placed at the second node; the second node being operable to identify a second parent zone including the child object and to divide the second parent zone into a plurality of subzones for placing a second child object, wherein the second child object is a child of the child object.

14. The pear-to-peer system of claim 13 , wherein the parent node is further operable to randomly select one of the plurality of subzones for placing the child object.

15. The peer-to-peer system of claim 14 , wherein the parent node is further operable to randomly select a node in the selected subzone for placing the child object.

16. The peer-to-peer system of claim 15 , wherein the plurality of nodes function as a distributed, file system having a tree structure including a plurality of parent objects and child objects.