Method of determining lower bound for replication cost
First Claim
1. A method of determining a lower bound for a minimum cost of placing data objects onto nodes of a distributed storage system comprising the steps of:
- for each data object, assigning a placement of the data object to a node and a time interval which meets a benefit criterion, thereby assigning the placement of the data object to a node-interval;
for each data object, continuing to assign additional placements of the data object to other node-intervals which each meet the benefit criterion until a performance reaches a performance threshold; and
calculating a sum of storage costs and creation costs for the placement and the additional placements of the data objects.
1 Assignment
0 Petitions
Accused Products
Abstract
An embodiment of a method of determining a lower bound for a minimum cost of placing data objects onto nodes of a distributed storage system begins with a first step of assigning a placement of a data object to a node and a time interval which meets a benefit criterion. Assignment of the placement of the data object to the node and the time interval comprises assigning the placement of the data object to a node-interval. The method continues with a second step of continuing to assign additional placements of the data object to other node-intervals which each meet the benefit criterion until a performance reaches a performance threshold. The method performs the first and second steps for each of the data objects. The method concludes with a step of calculating a sum of storage costs and creation costs for the placement and the additional placements of the data objects. According to another embodiment, the data object placed in the first and second steps is chosen on a basis of a triplet of the data object, the node, and the interval which meets the benefit criterion.
-
Citations
23 Claims
-
1. A method of determining a lower bound for a minimum cost of placing data objects onto nodes of a distributed storage system comprising the steps of:
-
for each data object, assigning a placement of the data object to a node and a time interval which meets a benefit criterion, thereby assigning the placement of the data object to a node-interval;
for each data object, continuing to assign additional placements of the data object to other node-intervals which each meet the benefit criterion until a performance reaches a performance threshold; and
calculating a sum of storage costs and creation costs for the placement and the additional placements of the data objects. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
-
-
17. A method of determining a lower bound for a minimum cost of placing data objects onto nodes of a distributed storage system comprising the steps of:
-
assigning a placement of a data object to a node and a time interval for which the data object, the node, and the time interval meet a benefit criterion, thereby assigning the placement of the data object on a basis of a data object-node-interval triplet which meets the benefit criterion;
continuing to assign additional placements of the data objects in which each placement is selected on the basis of the data object-node-interval triplet which meets the benefit criterion until a performance reaches a performance threshold; and
calculating a sum of storage costs and creation costs for the placement and the additional placements of the data objects.
-
-
18. A method of determining a lower bound for a minimum cost of placing data objects onto nodes of a distributed storage system comprising the steps of:
-
identifying a minimal number of non-overlapping sets which cover the nodes in the distributed storage system, each non-overlapping set comprising an effective node;
for each data object, performing the steps of;
for each effective node, determining a candidate time interval for placing the data object onto the effective node that meets a first benefit criterion;
while a performance threshold exceeds a performance, iteratively performing the steps of;
assigning a placement of the data object onto the effective node for the candidate time interval which meets a second benefit criterion, thereby reducing non-placement time intervals for the effective node by the candidate time interval; and
determining a new candidate time interval for the effective node selected from the non-placement time intervals, the new candidate time interval meeting the first benefit criterion; and
calculating a sum of storage costs and creation costs for the placements of the data objects. - View Dependent Claims (19, 20)
-
-
21. A computer readable memory comprising computer code for implementing a method of determining a lower bound for a minimum cost of placing data objects onto nodes of a distributed storage system, the method of determining the lower bound for the minimum cost of placing the data objects comprising the steps of:
-
for each data object, assigning a placement of the data object to a node and a time interval which meets a benefit criterion, thereby assigning the placement of the data object to a node-interval;
for each data object, continuing to assign additional placements of the data object to other node-intervals which each meet the benefit criterion until a performance reaches a performance threshold; and
calculating a sum of storage costs and creation costs for the placement and the additional placements of the data objects.
-
-
22. A computer readable memory comprising computer code for implementing a method of determining a lower bound for a minimum cost of placing data objects onto nodes of a distributed storage system, the method of determining the lower bound for the minimum cost of placing the data objects comprising the steps of:
-
assigning a placement of a data object to a node and a time interval for which the data object, the node, and the time interval meet a benefit criterion, thereby assigning the placement of a data object-node-interval triplet;
continuing to assign additional placements of the data objects in which each placement is selected on a basis of the data object-node-interval triplet which meets the benefit criterion until a performance reaches a performance threshold; and
calculating a sum of storage costs and creation costs for the placement and the additional placements of the data objects.
-
-
23. A computer readable memory comprising computer code for implementing a method of determining a lower bound for a minimum cost of placing data objects onto nodes of a distributed storage system, the method of determining the lower bound for the minimum cost of placing the data objects comprising the steps of:
-
identifying a minimal number of non-overlapping sets which cover the nodes in the distributed storage system, each non-overlapping set comprising an effective node;
for each data object, performing the steps of;
for each effective node, determining a candidate time interval for placing the data object onto the effective node that provides a maximum nodal benefit;
while a performance threshold exceeds a performance, iteratively performing the steps of;
assigning a placement of the data object onto the effective node for the candidate time interval which provides a maximum benefit, thereby reducing non-placement time intervals for the effective node by the candidate time interval; and
determining a new candidate time interval for the effective node selected from the non-placement time intervals, the new candidate time interval providing the maximum nodal benefit; and
calculating a sum of storage costs and creation costs for the placements of the data objects.
-
Specification