J. Secretan, M. Lawson, and L. Bölöni

Efficient Allocation and Composition of Distributed Storage


Cite as:

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.

Download:

Download 

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.

BibTeX:

@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 Thu Sep 26, 2019 13:02:58