J. Secretan, M. Lawson, and L. Bölöni. Efficient Allocation and Composition of Distributed Storage. Journal of Supercomputing, 47(3):286–310, March 2009.
In this paper we investigate the composition of cheap network storage resources to meet specific availability and capacity requirements. We show that the problem of finding the optimal composition for availability and price requirements can be reduced to the knapsack problem, and propose three techniques for efficiently finding approximate solutions. The first algorithm uses a dynamic programming approach to find mirrored storage resources for high availability requirements, and runs in the pseudo-polynomial $O(n^2c)$ time where $n$ is the number of sellers' resources to choose from and $c$ is a capacity function of the requested and minimum availability. The second technique is a heuristic which finds resources to be agglomerated into a larger coherent resource, with complexity of $O(n \log n)$. The third technique finds a compromise between capacity and availability (which in our phrasing is a complex integer programming problem) using a genetic algorithm. The algorithms can be implemented on a broker that intermediates between buyers and sellers of storage resources. Finally, we show that a broker in an open storage market, using the combination of the three algorithms can more frequently meet user requests and lower the cost of requests that are met compared to a broker that simply matches single resources to requests.
@article{Secretan-2009-Supercomputing,
author = "J. Secretan and M. Lawson and L. B{\"o}l{\"o}ni",
title = "Efficient Allocation and Composition of Distributed Storage",
journal = "Journal of Supercomputing",
year = "2009",
volume = "47",
number = "3",
pages = "286-310",
month = "March",
abstract = {
In this paper we investigate the composition of cheap network storage
resources to meet specific availability and capacity requirements. We show
that the problem of finding the optimal composition for availability and
price requirements can be reduced to the knapsack problem, and propose
three techniques for efficiently finding approximate solutions. The first
algorithm uses a dynamic programming approach to find mirrored storage
resources for high availability requirements, and runs in the
pseudo-polynomial $O(n^2c)$ time where $n$ is the number of sellers'
resources to choose from and $c$ is a capacity function of the requested
and minimum availability. The second technique is a heuristic which finds
resources to be agglomerated into a larger coherent resource, with
complexity of $O(n \log n)$. The third technique finds a compromise
between capacity and availability (which in our phrasing is a complex
integer programming problem) using a genetic algorithm. The algorithms can
be implemented on a broker that intermediates between buyers and sellers
of storage resources. Finally, we show that a broker in an open storage
market, using the combination of the three algorithms can more frequently
meet user requests and lower the cost of requests that are met compared to
a broker that simply matches single resources to requests.
}
}
Generated by bib2html.pl (written by Patrick Riley, Lotzi Boloni ) on Fri Jan 13, 2012 11:42:30