Title

Efficient allocation and composition of distributed storage

Authors

Authors

J. Secretan; M. Lawson;L. Boloni

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

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 (2) c) 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(nlog 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.

Journal Title

Journal of Supercomputing

Volume

47

Issue/Number

3

Publication Date

1-1-2009

Document Type

Article

First Page

286

Last Page

310

WOS Identifier

WOS:000263391600003

ISSN

0920-8542

Share

COinS