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. accepted, in early access at Journal of Supercomputing, 2008.

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-2008-Supercomputing,
    author = "J. Secretan and M. Lawson and L. B{\"o}l{\"o}ni",
    title = "Efficient Allocation and Composition of Distributed Storage",
    journal = "accepted, in early access at Journal of Supercomputing",
    year = "2008",
    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 Mon Feb 16, 2009 21:37:46