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 Fri Oct 06, 2017 18:15:24